radiant/patch.cpp

   1 /*
   2    Copyright (C) 2001-2006, William Joseph.
   3    All Rights Reserved.
   4
   5    This file is part of GtkRadiant.
   6
   7    GtkRadiant is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    GtkRadiant is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GtkRadiant; if not, write to the Free Software
  19    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20  */
  21
  22 #include "patch.h"
  23
  24 #include <glib.h>
  25 #include "preferences.h"
  26 #include "brush_primit.h"
  27 #include "signal/signal.h"
  28
  29
  30 Signal0 g_patchTextureChangedCallbacks;
  31
  32 void Patch_addTextureChangedCallback(const SignalHandler &handler)
  33 {
  34     g_patchTextureChangedCallbacks.connectLast(handler);
  35 }
  36
  37 void Patch_textureChanged()
  38 {
  39     g_patchTextureChangedCallbacks();
  40 }
  41
  42
  43 Shader *PatchInstance::m_state_selpoint;
  44 Shader *Patch::m_state_ctrl;
  45 Shader *Patch::m_state_lattice;
  46 EPatchType Patch::m_type;
  47
  48
  49 std::size_t MAX_PATCH_WIDTH = 0;
  50 std::size_t MAX_PATCH_HEIGHT = 0;
  51
  52 int g_PatchSubdivideThreshold = 4;
  53
  54 void BezierCurveTree_Delete(BezierCurveTree *pCurve)
  55 {
  56     if (pCurve) {
  57         BezierCurveTree_Delete(pCurve->left);
  58         BezierCurveTree_Delete(pCurve->right);
  59         delete pCurve;
  60     }
  61 }
  62
  63 std::size_t BezierCurveTree_Setup(BezierCurveTree *pCurve, std::size_t index, std::size_t stride)
  64 {
  65     if (pCurve) {
  66         if (pCurve->left && pCurve->right) {
  67             index = BezierCurveTree_Setup(pCurve->left, index, stride);
  68             pCurve->index = index * stride;
  69             index++;
  70             index = BezierCurveTree_Setup(pCurve->right, index, stride);
  71         } else {
  72             pCurve->index = BEZIERCURVETREE_MAX_INDEX;
  73         }
  74     }
  75
  76     return index;
  77 }
  78
  79 bool BezierCurve_IsCurved(BezierCurve *pCurve)
  80 {
  81     Vector3 vTemp(vector3_subtracted(pCurve->right, pCurve->left));
  82     Vector3 v1(vector3_subtracted(pCurve->crd, pCurve->left));
  83     Vector3 v2(vector3_subtracted(pCurve->right, pCurve->crd));
  84
  85     if (vector3_equal(v1, g_vector3_identity) || vector3_equal(vTemp, v1)) { // return 0 if 1->2 == 0 or 1->2 == 1->3
  86         return false;
  87     }
  88
  89     vector3_normalise(v1);
  90     vector3_normalise(v2);
  91     if (vector3_equal(v1, v2)) {
  92         return false;
  93     }
  94
  95     Vector3 v3(vTemp);
  96     const double width = vector3_length(v3);
  97     vector3_scale(v3, 1.0 / width);
  98
  99     if (vector3_equal(v1, v3) && vector3_equal(v2, v3)) {
 100         return false;
 101     }
 102
 103     const double angle = acos(vector3_dot(v1, v2)) / c_pi;
 104
 105     const double index = width * angle;
 106
 107     if (index > static_cast<double>( g_PatchSubdivideThreshold )) {
 108         return true;
 109     }
 110     return false;
 111 }
 112
 113 void BezierInterpolate(BezierCurve *pCurve)
 114 {
 115     pCurve->left = vector3_mid(pCurve->left, pCurve->crd);
 116     pCurve->right = vector3_mid(pCurve->crd, pCurve->right);
 117     pCurve->crd = vector3_mid(pCurve->left, pCurve->right);
 118 }
 119
 120 const std::size_t PATCH_MAX_SUBDIVISION_DEPTH = 16;
 121
 122 void BezierCurveTree_FromCurveList(BezierCurveTree *pTree, GSList *pCurveList, std::size_t depth = 0)
 123 {
 124     GSList *pLeftList = 0;
 125     GSList *pRightList = 0;
 126     BezierCurve *pCurve, *pLeftCurve, *pRightCurve;
 127     bool bSplit = false;
 128
 129     for (GSList *l = pCurveList; l; l = l->next) {
 130         pCurve = (BezierCurve *) (l->data);
 131         if (bSplit || BezierCurve_IsCurved(pCurve)) {
 132             bSplit = true;
 133             pLeftCurve = new BezierCurve;
 134             pRightCurve = new BezierCurve;
 135             pLeftCurve->left = pCurve->left;
 136             pRightCurve->right = pCurve->right;
 137             BezierInterpolate(pCurve);
 138             pLeftCurve->crd = pCurve->left;
 139             pRightCurve->crd = pCurve->right;
 140             pLeftCurve->right = pCurve->crd;
 141             pRightCurve->left = pCurve->crd;
 142
 143             pLeftList = g_slist_prepend(pLeftList, pLeftCurve);
 144             pRightList = g_slist_prepend(pRightList, pRightCurve);
 145         }
 146     }
 147
 148     if (pLeftList != 0 && pRightList != 0 && depth != PATCH_MAX_SUBDIVISION_DEPTH) {
 149         pTree->left = new BezierCurveTree;
 150         pTree->right = new BezierCurveTree;
 151         BezierCurveTree_FromCurveList(pTree->left, pLeftList, depth + 1);
 152         BezierCurveTree_FromCurveList(pTree->right, pRightList, depth + 1);
 153
 154         for (GSList *l = pLeftList; l != 0; l = g_slist_next(l)) {
 155             delete (BezierCurve *) l->data;
 156         }
 157
 158         for (GSList *l = pRightList; l != 0; l = g_slist_next(l)) {
 159             delete (BezierCurve *) l->data;
 160         }
 161
 162         g_slist_free(pLeftList);
 163         g_slist_free(pRightList);
 164     } else {
 165         pTree->left = 0;
 166         pTree->right = 0;
 167     }
 168 }
 169
 170
 171 int Patch::m_CycleCapIndex = 0;
 172
 173
 174 void Patch::setDims(std::size_t w, std::size_t h)
 175 {
 176     if ((w % 2) == 0) {
 177         w -= 1;
 178     }
 179     ASSERT_MESSAGE(w <= MAX_PATCH_WIDTH, "patch too wide");
 180     if (w > MAX_PATCH_WIDTH) {
 181         w = MAX_PATCH_WIDTH;
 182     } else if (w < MIN_PATCH_WIDTH) {
 183         w = MIN_PATCH_WIDTH;
 184     }
 185
 186     if ((h % 2) == 0) {
 187         m_height -= 1;
 188     }
 189     ASSERT_MESSAGE(h <= MAX_PATCH_HEIGHT, "patch too tall");
 190     if (h > MAX_PATCH_HEIGHT) {
 191         h = MAX_PATCH_HEIGHT;
 192     } else if (h < MIN_PATCH_HEIGHT) {
 193         h = MIN_PATCH_HEIGHT;
 194     }
 195
 196     m_width = w;
 197     m_height = h;
 198
 199     if (m_width * m_height != m_ctrl.size()) {
 200         m_ctrl.resize(m_width * m_height);
 201         onAllocate(m_ctrl.size());
 202     }
 203 }
 204
 205 inline const Colour4b &colour_for_index(std::size_t i, std::size_t width)
 206 {
 207     return (i % 2 || (i / width) % 2) ? colour_inside : colour_corner;
 208 }
 209
 210 inline bool float_valid(float f)
 211 {
 212     return f == f;
 213 }
 214
 215 bool Patch::isValid() const
 216 {
 217     if (!m_width || !m_height) {
 218         return false;
 219     }
 220
 221     for (const_iterator i = m_ctrl.begin(); i != m_ctrl.end(); ++i) {
 222         if (!float_valid((*i).m_vertex.x())
 223             || !float_valid((*i).m_vertex.y())
 224             || !float_valid((*i).m_vertex.z())
 225             || !float_valid((*i).m_texcoord.x())
 226             || !float_valid((*i).m_texcoord.y())) {
 227             globalErrorStream() << "patch has invalid control points\n";
 228             return false;
 229         }
 230     }
 231     return true;
 232 }
 233
 234 void Patch::UpdateCachedData()
 235 {
 236     m_ctrl_vertices.clear();
 237     m_lattice_indices.clear();
 238
 239     if (!isValid()) {
 240         m_tess.m_numStrips = 0;
 241         m_tess.m_lenStrips = 0;
 242         m_tess.m_nArrayHeight = 0;
 243         m_tess.m_nArrayWidth = 0;
 244         m_tess.m_curveTreeU.resize(0);
 245         m_tess.m_curveTreeV.resize(0);
 246         m_tess.m_indices.resize(0);
 247         m_tess.m_vertices.resize(0);
 248         m_tess.m_arrayHeight.resize(0);
 249         m_tess.m_arrayWidth.resize(0);
 250         m_aabb_local = AABB();
 251         return;
 252     }
 253
 254     BuildTesselationCurves(ROW);
 255     BuildTesselationCurves(COL);
 256     BuildVertexArray();
 257     AccumulateBBox();
 258
 259     IndexBuffer ctrl_indices;
 260
 261     m_lattice_indices.reserve(((m_width * (m_height - 1)) + (m_height * (m_width - 1))) << 1);
 262     ctrl_indices.reserve(m_ctrlTransformed.size());
 263     {
 264         UniqueVertexBuffer<PointVertex> inserter(m_ctrl_vertices);
 265         for (iterator i = m_ctrlTransformed.begin(); i != m_ctrlTransformed.end(); ++i) {
 266             ctrl_indices.insert(inserter.insert(pointvertex_quantised(
 267                     PointVertex(reinterpret_cast<const Vertex3f &>((*i).m_vertex ),
 268                                 colour_for_index(i - m_ctrlTransformed.begin(), m_width)))));
 269         }
 270     }
 271     {
 272         for (IndexBuffer::iterator i = ctrl_indices.begin(); i != ctrl_indices.end(); ++i) {
 273             if (std::size_t(i - ctrl_indices.begin()) % m_width) {
 274                 m_lattice_indices.insert(*(i - 1));
 275                 m_lattice_indices.insert(*i);
 276             }
 277             if (std::size_t(i - ctrl_indices.begin()) >= m_width) {
 278                 m_lattice_indices.insert(*(i - m_width));
 279                 m_lattice_indices.insert(*i);
 280             }
 281         }
 282     }
 283
 284 #if 0
 285                                                                                                                             {
 286                 Array<RenderIndex>::iterator first = m_tess.m_indices.begin();
 287                 for ( std::size_t s = 0; s < m_tess.m_numStrips; s++ )
 288                 {
 289                         Array<RenderIndex>::iterator last = first + m_tess.m_lenStrips;
 290
 291                         for ( Array<RenderIndex>::iterator i( first ); i + 2 != last; i += 2 )
 292                         {
 293                                 ArbitraryMeshTriangle_sumTangents( m_tess.m_vertices[*( i + 0 )], m_tess.m_vertices[*( i + 1 )], m_tess.m_vertices[*( i + 2 )] );
 294                                 ArbitraryMeshTriangle_sumTangents( m_tess.m_vertices[*( i + 2 )], m_tess.m_vertices[*( i + 1 )], m_tess.m_vertices[*( i + 3 )] );
 295                         }
 296
 297                         first = last;
 298                 }
 299
 300                 for ( Array<ArbitraryMeshVertex>::iterator i = m_tess.m_vertices.begin(); i != m_tess.m_vertices.end(); ++i )
 301                 {
 302                         vector3_normalise( reinterpret_cast<Vector3&>( ( *i ).tangent ) );
 303                         vector3_normalise( reinterpret_cast<Vector3&>( ( *i ).bitangent ) );
 304                 }
 305         }
 306 #endif
 307
 308     SceneChangeNotify();
 309 }
 310
 311 void Patch::InvertMatrix()
 312 {
 313     undoSave();
 314
 315     PatchControlArray_invert(m_ctrl, m_width, m_height);
 316
 317     controlPointsChanged();
 318 }
 319
 320 void Patch::TransposeMatrix()
 321 {
 322     undoSave();
 323
 324     {
 325         Array<PatchControl> tmp(m_width * m_height);
 326         copy_ctrl(tmp.data(), m_ctrl.data(), m_ctrl.data() + m_width * m_height);
 327
 328         PatchControlIter from = tmp.data();
 329         for (std::size_t h = 0; h != m_height; ++h) {
 330             PatchControlIter to = m_ctrl.data() + h;
 331             for (std::size_t w = 0; w != m_width; ++w, ++from, to += m_height) {
 332                 *to = *from;
 333             }
 334         }
 335     }
 336
 337     {
 338         std::size_t tmp = m_width;
 339         m_width = m_height;
 340         m_height = tmp;
 341     }
 342
 343     controlPointsChanged();
 344 }
 345
 346 void Patch::Redisperse(EMatrixMajor mt)
 347 {
 348     std::size_t w, h, width, height, row_stride, col_stride;
 349     PatchControl *p1, *p2, *p3;
 350
 351     undoSave();
 352
 353     switch (mt) {
 354         case COL:
 355             width = (m_width - 1) >> 1;
 356             height = m_height;
 357             col_stride = 1;
 358             row_stride = m_width;
 359             break;
 360         case ROW:
 361             width = (m_height - 1) >> 1;
 362             height = m_width;
 363             col_stride = m_width;
 364             row_stride = 1;
 365             break;
 366         default:
 367             ERROR_MESSAGE("neither row-major nor column-major");
 368             return;
 369     }
 370
 371     for (h = 0; h < height; h++) {
 372         p1 = m_ctrl.data() + (h * row_stride);
 373         for (w = 0; w < width; w++) {
 374             p2 = p1 + col_stride;
 375             p3 = p2 + col_stride;
 376             p2->m_vertex = vector3_mid(p1->m_vertex, p3->m_vertex);
 377             p1 = p3;
 378         }
 379     }
 380
 381     controlPointsChanged();
 382 }
 383
 384 void Patch::Smooth(EMatrixMajor mt)
 385 {
 386     std::size_t w, h, width, height, row_stride, col_stride;
 387     bool wrap;
 388     PatchControl *p1, *p2, *p3, *p2b;
 389
 390     undoSave();
 391
 392     switch (mt) {
 393         case COL:
 394             width = (m_width - 1) >> 1;
 395             height = m_height;
 396             col_stride = 1;
 397             row_stride = m_width;
 398             break;
 399         case ROW:
 400             width = (m_height - 1) >> 1;
 401             height = m_width;
 402             col_stride = m_width;
 403             row_stride = 1;
 404             break;
 405         default:
 406             ERROR_MESSAGE("neither row-major nor column-major");
 407             return;
 408     }
 409
 410     wrap = true;
 411     for (h = 0; h < height; h++) {
 412         p1 = m_ctrl.data() + (h * row_stride);
 413         p2 = p1 + (2 * width) * col_stride;
 414         //globalErrorStream() << "compare " << p1->m_vertex << " and " << p2->m_vertex << "\n";
 415         if (vector3_length_squared(vector3_subtracted(p1->m_vertex, p2->m_vertex)) > 1.0) {
 416             //globalErrorStream() << "too far\n";
 417             wrap = false;
 418             break;
 419         }
 420     }
 421
 422     for (h = 0; h < height; h++) {
 423         p1 = m_ctrl.data() + (h * row_stride) + col_stride;
 424         for (w = 0; w < width - 1; w++) {
 425             p2 = p1 + col_stride;
 426             p3 = p2 + col_stride;
 427             p2->m_vertex = vector3_mid(p1->m_vertex, p3->m_vertex);
 428             p1 = p3;
 429         }
 430         if (wrap) {
 431             p1 = m_ctrl.data() + (h * row_stride) + (2 * width - 1) * col_stride;
 432             p2 = m_ctrl.data() + (h * row_stride);
 433             p2b = m_ctrl.data() + (h * row_stride) + (2 * width) * col_stride;
 434             p3 = m_ctrl.data() + (h * row_stride) + col_stride;
 435             p2->m_vertex = p2b->m_vertex = vector3_mid(p1->m_vertex, p3->m_vertex);
 436         }
 437     }
 438
 439     controlPointsChanged();
 440 }
 441
 442 void Patch::InsertRemove(bool bInsert, bool bColumn, bool bFirst)
 443 {
 444     undoSave();
 445
 446     if (bInsert) {
 447         if (bColumn && (m_width + 2 <= MAX_PATCH_WIDTH)) {
 448             InsertPoints(COL, bFirst);
 449         } else if (m_height + 2 <= MAX_PATCH_HEIGHT) {
 450             InsertPoints(ROW, bFirst);
 451         }
 452     } else {
 453         if (bColumn && (m_width - 2 >= MIN_PATCH_WIDTH)) {
 454             RemovePoints(COL, bFirst);
 455         } else if (m_height - 2 >= MIN_PATCH_HEIGHT) {
 456             RemovePoints(ROW, bFirst);
 457         }
 458     }
 459
 460     controlPointsChanged();
 461 }
 462
 463 Patch *Patch::MakeCap(Patch *patch, EPatchCap eType, EMatrixMajor mt, bool bFirst)
 464 {
 465     std::size_t i, width, height;
 466
 467     switch (mt) {
 468         case ROW:
 469             width = m_width;
 470             height = m_height;
 471             break;
 472         case COL:
 473             width = m_height;
 474             height = m_width;
 475             break;
 476         default:
 477             ERROR_MESSAGE("neither row-major nor column-major");
 478             return 0;
 479     }
 480
 481     Array<Vector3> p(width);
 482
 483     std::size_t nIndex = (bFirst) ? 0 : height - 1;
 484     if (mt == ROW) {
 485         for (i = 0; i < width; i++) {
 486             p[(bFirst) ? i : (width - 1) - i] = ctrlAt(nIndex, i).m_vertex;
 487         }
 488     } else {
 489         for (i = 0; i < width; i++) {
 490             p[(bFirst) ? i : (width - 1) - i] = ctrlAt(i, nIndex).m_vertex;
 491         }
 492     }
 493
 494     patch->ConstructSeam(eType, p.data(), width);
 495     return patch;
 496 }
 497
 498 void Patch::FlipTexture(int nAxis)
 499 {
 500     undoSave();
 501
 502     for (PatchControlIter i = m_ctrl.data(); i != m_ctrl.data() + m_ctrl.size(); ++i) {
 503         (*i).m_texcoord[nAxis] = -(*i).m_texcoord[nAxis];
 504     }
 505
 506     controlPointsChanged();
 507 }
 508
 509 void Patch::TranslateTexture(float s, float t)
 510 {
 511     undoSave();
 512
 513     s = -1 * s / m_state->getTexture().width;
 514     t = t / m_state->getTexture().height;
 515
 516     for (PatchControlIter i = m_ctrl.data(); i != m_ctrl.data() + m_ctrl.size(); ++i) {
 517         (*i).m_texcoord[0] += s;
 518         (*i).m_texcoord[1] += t;
 519     }
 520
 521     controlPointsChanged();
 522 }
 523
 524 void Patch::ScaleTexture(float s, float t)
 525 {
 526     undoSave();
 527
 528     for (PatchControlIter i = m_ctrl.data(); i != m_ctrl.data() + m_ctrl.size(); ++i) {
 529         (*i).m_texcoord[0] *= s;
 530         (*i).m_texcoord[1] *= t;
 531     }
 532
 533     controlPointsChanged();
 534 }
 535
 536 void Patch::RotateTexture(float angle)
 537 {
 538     undoSave();
 539
 540     const float s = static_cast<float>( sin(degrees_to_radians(angle)));
 541     const float c = static_cast<float>( cos(degrees_to_radians(angle)));
 542
 543     for (PatchControlIter i = m_ctrl.data(); i != m_ctrl.data() + m_ctrl.size(); ++i) {
 544         const float x = (*i).m_texcoord[0];
 545         const float y = (*i).m_texcoord[1];
 546         (*i).m_texcoord[0] = (x * c) - (y * s);
 547         (*i).m_texcoord[1] = (y * c) + (x * s);
 548     }
 549
 550     controlPointsChanged();
 551 }
 552
 553
 554 void Patch::SetTextureRepeat(float s, float t)
 555 {
 556     std::size_t w, h;
 557     float si, ti, sc, tc;
 558     PatchControl *pDest;
 559
 560     undoSave();
 561
 562     si = s / (float) (m_width - 1);
 563     ti = t / (float) (m_height - 1);
 564
 565     pDest = m_ctrl.data();
 566     for (h = 0, tc = 0.0f; h < m_height; h++, tc += ti) {
 567         for (w = 0, sc = 0.0f; w < m_width; w++, sc += si) {
 568             pDest->m_texcoord[0] = sc;
 569             pDest->m_texcoord[1] = tc;
 570             pDest++;
 571         }
 572     }
 573
 574     controlPointsChanged();
 575 }
 576
 577 /*
 578    void Patch::SetTextureInfo(texdef_t *pt)
 579    {
 580    if(pt->getShift()[0] || pt->getShift()[1])
 581     TranslateTexture (pt->getShift()[0], pt->getShift()[1]);
 582    else if(pt->getScale()[0] || pt->getScale()[1])
 583    {
 584     if(pt->getScale()[0] == 0.0f) pt->setScale(0, 1.0f);
 585     if(pt->getScale()[1] == 0.0f) pt->setScale(1, 1.0f);
 586     ScaleTexture (pt->getScale()[0], pt->getScale()[1]);
 587    }
 588    else if(pt->rotate)
 589     RotateTexture (pt->rotate);
 590    }
 591  */
 592
 593 inline int texture_axis(const Vector3 &normal)
 594 {
 595     // axis dominance order: Z, X, Y
 596     return (normal.x() >= normal.y()) ? (normal.x() > normal.z()) ? 0 : 2 : (normal.y() > normal.z()) ? 1 : 2;
 597 }
 598
 599 void Patch::CapTexture()
 600 {
 601     const PatchControl &p1 = m_ctrl[m_width];
 602     const PatchControl &p2 = m_ctrl[m_width * (m_height - 1)];
 603     const PatchControl &p3 = m_ctrl[(m_width * m_height) - 1];
 604
 605
 606     Vector3 normal(g_vector3_identity);
 607
 608     {
 609         Vector3 tmp(vector3_cross(
 610                 vector3_subtracted(p2.m_vertex, m_ctrl[0].m_vertex),
 611                 vector3_subtracted(p3.m_vertex, m_ctrl[0].m_vertex)
 612         ));
 613         if (!vector3_equal(tmp, g_vector3_identity)) {
 614             vector3_add(normal, tmp);
 615         }
 616     }
 617     {
 618         Vector3 tmp(vector3_cross(
 619                 vector3_subtracted(p1.m_vertex, p3.m_vertex),
 620                 vector3_subtracted(m_ctrl[0].m_vertex, p3.m_vertex)
 621         ));
 622         if (!vector3_equal(tmp, g_vector3_identity)) {
 623             vector3_add(normal, tmp);
 624         }
 625     }
 626
 627     ProjectTexture(texture_axis(normal));
 628 }
 629
 630 // uses longest parallel chord to calculate texture coords for each row/col
 631 void Patch::NaturalTexture()
 632 {
 633     undoSave();
 634
 635     {
 636         float fSize = (float) m_state->getTexture().width * Texdef_getDefaultTextureScale();
 637
 638         double texBest = 0;
 639         double tex = 0;
 640         PatchControl *pWidth = m_ctrl.data();
 641         for (std::size_t w = 0; w < m_width; w++, pWidth++) {
 642             {
 643                 PatchControl *pHeight = pWidth;
 644                 for (std::size_t h = 0; h < m_height; h++, pHeight += m_width) {
 645                     pHeight->m_texcoord[0] = static_cast<float>( tex );
 646                 }
 647             }
 648
 649             if (w + 1 == m_width) {
 650                 break;
 651             }
 652
 653             {
 654                 PatchControl *pHeight = pWidth;
 655                 for (std::size_t h = 0; h < m_height; h++, pHeight += m_width) {
 656                     Vector3 v(vector3_subtracted(pHeight->m_vertex, (pHeight + 1)->m_vertex));
 657                     double length = tex + (vector3_length(v) / fSize);
 658                     if (fabs(length) > texBest) {
 659                         texBest = length;
 660                     }
 661                 }
 662             }
 663
 664             tex = texBest;
 665         }
 666     }
 667
 668     {
 669         float fSize = -(float) m_state->getTexture().height * Texdef_getDefaultTextureScale();
 670
 671         double texBest = 0;
 672         double tex = 0;
 673         PatchControl *pHeight = m_ctrl.data();
 674         for (std::size_t h = 0; h < m_height; h++, pHeight += m_width) {
 675             {
 676                 PatchControl *pWidth = pHeight;
 677                 for (std::size_t w = 0; w < m_width; w++, pWidth++) {
 678                     pWidth->m_texcoord[1] = static_cast<float>( tex );
 679                 }
 680             }
 681
 682             if (h + 1 == m_height) {
 683                 break;
 684             }
 685
 686             {
 687                 PatchControl *pWidth = pHeight;
 688                 for (std::size_t w = 0; w < m_width; w++, pWidth++) {
 689                     Vector3 v(vector3_subtracted(pWidth->m_vertex, (pWidth + m_width)->m_vertex));
 690                     double length = tex + (vector3_length(v) / fSize);
 691                     if (fabs(length) > texBest) {
 692                         texBest = length;
 693                     }
 694                 }
 695             }
 696
 697             tex = texBest;
 698         }
 699     }
 700
 701     controlPointsChanged();
 702 }
 703
 704
 705
 706 // private:
 707
 708 void Patch::AccumulateBBox()
 709 {
 710     m_aabb_local = AABB();
 711
 712     for (PatchControlArray::iterator i = m_ctrlTransformed.begin(); i != m_ctrlTransformed.end(); ++i) {
 713         aabb_extend_by_point_safe(m_aabb_local, (*i).m_vertex);
 714     }
 715
 716     m_boundsChanged();
 717     m_lightsChanged();
 718 }
 719
 720 void Patch::InsertPoints(EMatrixMajor mt, bool bFirst)
 721 {
 722     std::size_t width, height, row_stride, col_stride;
 723
 724     switch (mt) {
 725         case ROW:
 726             col_stride = 1;
 727             row_stride = m_width;
 728             width = m_width;
 729             height = m_height;
 730             break;
 731         case COL:
 732             col_stride = m_width;
 733             row_stride = 1;
 734             width = m_height;
 735             height = m_width;
 736             break;
 737         default:
 738             ERROR_MESSAGE("neither row-major nor column-major");
 739             return;
 740     }
 741
 742     std::size_t pos = 0;
 743     {
 744         PatchControl *p1 = m_ctrl.data();
 745         /*
 746                    if(GlobalSelectionSystem().countSelected() != 0)
 747                    {
 748                       scene::Instance& instance = GlobalSelectionSystem().ultimateSelected();
 749                       PatchInstance* patch = Instance_getPatch(instance);
 750                       patch->m_selectable.isSelected();
 751                    }
 752                  */
 753         for (std::size_t w = 0; w != width; ++w, p1 += col_stride) {
 754             {
 755                 PatchControl *p2 = p1;
 756                 for (std::size_t h = 1; h < height; h += 2, p2 += 2 * row_stride) {
 757                     if (0) { //p2->m_selectable.isSelected())
 758                         pos = h;
 759                         break;
 760                     }
 761                 }
 762                 if (pos != 0) {
 763                     break;
 764                 }
 765             }
 766
 767             {
 768                 PatchControl *p2 = p1;
 769                 for (std::size_t h = 0; h < height; h += 2, p2 += 2 * row_stride) {
 770                     if (0) { //p2->m_selectable.isSelected())
 771                         pos = h;
 772                         break;
 773                     }
 774                 }
 775                 if (pos != 0) {
 776                     break;
 777                 }
 778             }
 779         }
 780     }
 781
 782     Array<PatchControl> tmp(m_ctrl);
 783
 784     std::size_t row_stride2, col_stride2;
 785     switch (mt) {
 786         case ROW:
 787             setDims(m_width, m_height + 2);
 788             col_stride2 = 1;
 789             row_stride2 = m_width;
 790             break;
 791         case COL:
 792             setDims(m_width + 2, m_height);
 793             col_stride2 = m_width;
 794             row_stride2 = 1;
 795             break;
 796         default:
 797             ERROR_MESSAGE("neither row-major nor column-major");
 798             return;
 799     }
 800     if (bFirst) {
 801         pos = height - 1;
 802     } else {
 803         pos = 2;
 804     }
 805
 806     if (pos >= height) {
 807         if (bFirst) {
 808             pos = height - 1;
 809         } else {
 810             pos = 2;
 811         }
 812     } else if (pos == 0) {
 813         pos = 2;
 814     } else if (pos % 2) {
 815         ++pos;
 816     }
 817
 818
 819     for (std::size_t w = 0; w != width; ++w) {
 820         PatchControl *p1 = tmp.data() + (w * col_stride);
 821         PatchControl *p2 = m_ctrl.data() + (w * col_stride2);
 822         for (std::size_t h = 0; h != height; ++h, p2 += row_stride2, p1 += row_stride) {
 823             if (h == pos) {
 824                 p2 += 2 * row_stride2;
 825             }
 826             *p2 = *p1;
 827         }
 828
 829         p1 = tmp.data() + (w * col_stride + pos * row_stride);
 830         p2 = m_ctrl.data() + (w * col_stride2 + pos * row_stride2);
 831
 832         PatchControl *r2a = (p2 + row_stride2);
 833         PatchControl *r2b = (p2 - row_stride2);
 834         PatchControl *c2a = (p1 - 2 * row_stride);
 835         PatchControl *c2b = (p1 - row_stride);
 836
 837         // set two new row points
 838         *(p2 + 2 * row_stride2) = *p1;
 839         *r2a = *c2b;
 840
 841         for (std::size_t i = 0; i != 3; ++i) {
 842             r2a->m_vertex[i] = float_mid(c2b->m_vertex[i], p1->m_vertex[i]);
 843
 844             r2b->m_vertex[i] = float_mid(c2a->m_vertex[i], c2b->m_vertex[i]);
 845
 846             p2->m_vertex[i] = float_mid(r2a->m_vertex[i], r2b->m_vertex[i]);
 847         }
 848         for (std::size_t i = 0; i != 2; ++i) {
 849             r2a->m_texcoord[i] = float_mid(c2b->m_texcoord[i], p1->m_texcoord[i]);
 850
 851             r2b->m_texcoord[i] = float_mid(c2a->m_texcoord[i], c2b->m_texcoord[i]);
 852
 853             p2->m_texcoord[i] = float_mid(r2a->m_texcoord[i], r2b->m_texcoord[i]);
 854         }
 855     }
 856 }
 857
 858 void Patch::RemovePoints(EMatrixMajor mt, bool bFirst)
 859 {
 860     std::size_t width, height, row_stride, col_stride;
 861
 862     switch (mt) {
 863         case ROW:
 864             col_stride = 1;
 865             row_stride = m_width;
 866             width = m_width;
 867             height = m_height;
 868             break;
 869         case COL:
 870             col_stride = m_width;
 871             row_stride = 1;
 872             width = m_height;
 873             height = m_width;
 874             break;
 875         default:
 876             ERROR_MESSAGE("neither row-major nor column-major");
 877             return;
 878     }
 879
 880     std::size_t pos = 0;
 881     {
 882         PatchControl *p1 = m_ctrl.data();
 883         for (std::size_t w = 0; w != width; ++w, p1 += col_stride) {
 884             {
 885                 PatchControl *p2 = p1;
 886                 for (std::size_t h = 1; h < height; h += 2, p2 += 2 * row_stride) {
 887                     if (0) { //p2->m_selectable.isSelected())
 888                         pos = h;
 889                         break;
 890                     }
 891                 }
 892                 if (pos != 0) {
 893                     break;
 894                 }
 895             }
 896
 897             {
 898                 PatchControl *p2 = p1;
 899                 for (std::size_t h = 0; h < height; h += 2, p2 += 2 * row_stride) {
 900                     if (0) { //p2->m_selectable.isSelected())
 901                         pos = h;
 902                         break;
 903                     }
 904                 }
 905                 if (pos != 0) {
 906                     break;
 907                 }
 908             }
 909         }
 910     }
 911
 912     Array<PatchControl> tmp(m_ctrl);
 913
 914     std::size_t row_stride2, col_stride2;
 915     switch (mt) {
 916         case ROW:
 917             setDims(m_width, m_height - 2);
 918             col_stride2 = 1;
 919             row_stride2 = m_width;
 920             break;
 921         case COL:
 922             setDims(m_width - 2, m_height);
 923             col_stride2 = m_width;
 924             row_stride2 = 1;
 925             break;
 926         default:
 927             ERROR_MESSAGE("neither row-major nor column-major");
 928             return;
 929     }
 930     if (bFirst) {
 931         pos = height - 3;
 932     } else {
 933         pos = 2;
 934     }
 935     if (pos >= height) {
 936         if (bFirst) {
 937             pos = height - 3;
 938         } else {
 939             pos = 2;
 940         }
 941     } else if (pos == 0) {
 942         pos = 2;
 943     } else if (pos > height - 3) {
 944         pos = height - 3;
 945     } else if (pos % 2) {
 946         ++pos;
 947     }
 948
 949     for (std::size_t w = 0; w != width; w++) {
 950         PatchControl *p1 = tmp.data() + (w * col_stride);
 951         PatchControl *p2 = m_ctrl.data() + (w * col_stride2);
 952         for (std::size_t h = 0; h != height; ++h, p2 += row_stride2, p1 += row_stride) {
 953             if (h == pos) {
 954                 p1 += 2 * row_stride2;
 955                 h += 2;
 956             }
 957             *p2 = *p1;
 958         }
 959
 960         p1 = tmp.data() + (w * col_stride + pos * row_stride);
 961         p2 = m_ctrl.data() + (w * col_stride2 + pos * row_stride2);
 962
 963         for (std::size_t i = 0; i < 3; i++) {
 964             (p2 - row_stride2)->m_vertex[i] =
 965                     ((p1 + 2 * row_stride)->m_vertex[i] + (p1 - 2 * row_stride)->m_vertex[i]) * 0.5f;
 966
 967             (p2 - row_stride2)->m_vertex[i] =
 968                     (p2 - row_stride2)->m_vertex[i] + (2.0f * ((p1)->m_vertex[i] - (p2 - row_stride2)->m_vertex[i]));
 969         }
 970         for (std::size_t i = 0; i < 2; i++) {
 971             (p2 - row_stride2)->m_texcoord[i] =
 972                     ((p1 + 2 * row_stride)->m_texcoord[i] + (p1 - 2 * row_stride)->m_texcoord[i]) * 0.5f;
 973
 974             (p2 - row_stride2)->m_texcoord[i] = (p2 - row_stride2)->m_texcoord[i] +
 975                                                 (2.0f * ((p1)->m_texcoord[i] - (p2 - row_stride2)->m_texcoord[i]));
 976         }
 977     }
 978 }
 979
 980 void Patch::ConstructSeam(EPatchCap eType, Vector3 *p, std::size_t width)
 981 {
 982     switch (eType) {
 983         case eCapIBevel: {
 984             setDims(3, 3);
 985             m_ctrl[0].m_vertex = p[0];
 986             m_ctrl[1].m_vertex = p[1];
 987             m_ctrl[2].m_vertex = p[1];
 988             m_ctrl[3].m_vertex = p[1];
 989             m_ctrl[4].m_vertex = p[1];
 990             m_ctrl[5].m_vertex = p[1];
 991             m_ctrl[6].m_vertex = p[2];
 992             m_ctrl[7].m_vertex = p[1];
 993             m_ctrl[8].m_vertex = p[1];
 994         }
 995             break;
 996         case eCapBevel: {
 997             setDims(3, 3);
 998             Vector3 p3(vector3_added(p[2], vector3_subtracted(p[0], p[1])));
 999             m_ctrl[0].m_vertex = p3;
1000             m_ctrl[1].m_vertex = p3;
1001             m_ctrl[2].m_vertex = p[2];
1002             m_ctrl[3].m_vertex = p3;
1003             m_ctrl[4].m_vertex = p3;
1004             m_ctrl[5].m_vertex = p[1];
1005             m_ctrl[6].m_vertex = p3;
1006             m_ctrl[7].m_vertex = p3;
1007             m_ctrl[8].m_vertex = p[0];
1008         }
1009             break;
1010         case eCapEndCap: {
1011             Vector3 p5(vector3_mid(p[0], p[4]));
1012
1013             setDims(3, 3);
1014             m_ctrl[0].m_vertex = p[0];
1015             m_ctrl[1].m_vertex = p5;
1016             m_ctrl[2].m_vertex = p[4];
1017             m_ctrl[3].m_vertex = p[1];
1018             m_ctrl[4].m_vertex = p[2];
1019             m_ctrl[5].m_vertex = p[3];
1020             m_ctrl[6].m_vertex = p[2];
1021             m_ctrl[7].m_vertex = p[2];
1022             m_ctrl[8].m_vertex = p[2];
1023         }
1024             break;
1025         case eCapIEndCap: {
1026             setDims(5, 3);
1027             m_ctrl[0].m_vertex = p[4];
1028             m_ctrl[1].m_vertex = p[3];
1029             m_ctrl[2].m_vertex = p[2];
1030             m_ctrl[3].m_vertex = p[1];
1031             m_ctrl[4].m_vertex = p[0];
1032             m_ctrl[5].m_vertex = p[3];
1033             m_ctrl[6].m_vertex = p[3];
1034             m_ctrl[7].m_vertex = p[2];
1035             m_ctrl[8].m_vertex = p[1];
1036             m_ctrl[9].m_vertex = p[1];
1037             m_ctrl[10].m_vertex = p[3];
1038             m_ctrl[11].m_vertex = p[3];
1039             m_ctrl[12].m_vertex = p[2];
1040             m_ctrl[13].m_vertex = p[1];
1041             m_ctrl[14].m_vertex = p[1];
1042         }
1043             break;
1044         case eCapCylinder: {
1045             std::size_t mid = (width - 1) >> 1;
1046
1047             bool degenerate = (mid % 2) != 0;
1048
1049             std::size_t newHeight = mid + (degenerate ? 2 : 1);
1050
1051             setDims(3, newHeight);
1052
1053             if (degenerate) {
1054                 ++mid;
1055                 for (std::size_t i = width; i != width + 2; ++i) {
1056                     p[i] = p[width - 1];
1057                 }
1058             }
1059
1060             {
1061                 PatchControl *pCtrl = m_ctrl.data();
1062                 for (std::size_t i = 0; i != m_height; ++i, pCtrl += m_width) {
1063                     pCtrl->m_vertex = p[i];
1064                 }
1065             }
1066             {
1067                 PatchControl *pCtrl = m_ctrl.data() + 2;
1068                 std::size_t h = m_height - 1;
1069                 for (std::size_t i = 0; i != m_height; ++i, pCtrl += m_width) {
1070                     pCtrl->m_vertex = p[h + (h - i)];
1071                 }
1072             }
1073
1074             Redisperse(COL);
1075         }
1076             break;
1077         default:
1078             ERROR_MESSAGE("invalid patch-cap type");
1079             return;
1080     }
1081     CapTexture();
1082     controlPointsChanged();
1083 }
1084
1085 void Patch::ProjectTexture(int nAxis)
1086 {
1087     undoSave();
1088
1089     int s, t;
1090
1091     switch (nAxis) {
1092         case 2:
1093             s = 0;
1094             t = 1;
1095             break;
1096         case 0:
1097             s = 1;
1098             t = 2;
1099             break;
1100         case 1:
1101             s = 0;
1102             t = 2;
1103             break;
1104         default:
1105             ERROR_MESSAGE("invalid axis");
1106             return;
1107     }
1108
1109     float fWidth = 1 / (m_state->getTexture().width * Texdef_getDefaultTextureScale());
1110     float fHeight = 1 / (m_state->getTexture().height * -Texdef_getDefaultTextureScale());
1111
1112     for (PatchControlIter i = m_ctrl.data(); i != m_ctrl.data() + m_ctrl.size(); ++i) {
1113         (*i).m_texcoord[0] = (*i).m_vertex[s] * fWidth;
1114         (*i).m_texcoord[1] = (*i).m_vertex[t] * fHeight;
1115     }
1116
1117     controlPointsChanged();
1118 }
1119
1120 void Patch::constructPlane(const AABB &aabb, int axis, std::size_t width, std::size_t height)
1121 {
1122     setDims(width, height);
1123
1124     int x, y, z;
1125     switch (axis) {
1126         case 2:
1127             x = 0;
1128             y = 1;
1129             z = 2;
1130             break;
1131         case 1:
1132             x = 0;
1133             y = 2;
1134             z = 1;
1135             break;
1136         case 0:
1137             x = 1;
1138             y = 2;
1139             z = 0;
1140             break;
1141         default:
1142             ERROR_MESSAGE("invalid view-type");
1143             return;
1144     }
1145
1146     if (m_width < MIN_PATCH_WIDTH || m_width > MAX_PATCH_WIDTH) {
1147         m_width = 3;
1148     }
1149     if (m_height < MIN_PATCH_HEIGHT || m_height > MAX_PATCH_HEIGHT) {
1150         m_height = 3;
1151     }
1152
1153     Vector3 vStart;
1154     vStart[x] = aabb.origin[x] - aabb.extents[x];
1155     vStart[y] = aabb.origin[y] - aabb.extents[y];
1156     vStart[z] = aabb.origin[z];
1157
1158     float xAdj = fabsf((vStart[x] - (aabb.origin[x] + aabb.extents[x])) / (float) (m_width - 1));
1159     float yAdj = fabsf((vStart[y] - (aabb.origin[y] + aabb.extents[y])) / (float) (m_height - 1));
1160
1161     Vector3 vTmp;
1162     vTmp[z] = vStart[z];
1163     PatchControl *pCtrl = m_ctrl.data();
1164
1165     vTmp[y] = vStart[y];
1166     for (std::size_t h = 0; h < m_height; h++) {
1167         vTmp[x] = vStart[x];
1168         for (std::size_t w = 0; w < m_width; w++, ++pCtrl) {
1169             pCtrl->m_vertex = vTmp;
1170             vTmp[x] += xAdj;
1171         }
1172         vTmp[y] += yAdj;
1173     }
1174
1175     NaturalTexture();
1176 }
1177
1178 void Patch::ConstructPrefab(const AABB &aabb, EPatchPrefab eType, int axis, std::size_t width, std::size_t height)
1179 {
1180     Vector3 vPos[3];
1181
1182     if (eType != ePlane) {
1183         vPos[0] = vector3_subtracted(aabb.origin, aabb.extents);
1184         vPos[1] = aabb.origin;
1185         vPos[2] = vector3_added(aabb.origin, aabb.extents);
1186     }
1187
1188     if (eType == ePlane) {
1189         constructPlane(aabb, axis, width, height);
1190     } else if (eType == eSqCylinder
1191                || eType == eCylinder
1192                || eType == eDenseCylinder
1193                || eType == eVeryDenseCylinder
1194                || eType == eCone
1195                || eType == eSphere) {
1196         unsigned char *pIndex;
1197         unsigned char pCylIndex[] =
1198                 {
1199                         0, 0,
1200                         1, 0,
1201                         2, 0,
1202                         2, 1,
1203                         2, 2,
1204                         1, 2,
1205                         0, 2,
1206                         0, 1,
1207                         0, 0
1208                 };
1209
1210
1211         PatchControl *pStart;
1212         switch (eType) {
1213             case eSqCylinder:
1214                 setDims(9, 3);
1215                 pStart = m_ctrl.data();
1216                 break;
1217             case eDenseCylinder:
1218             case eVeryDenseCylinder:
1219             case eCylinder:
1220                 setDims(9, 3);
1221                 pStart = m_ctrl.data() + 1;
1222                 break;
1223             case eCone:
1224                 setDims(9, 3);
1225                 pStart = m_ctrl.data() + 1;
1226                 break;
1227             case eSphere:
1228                 setDims(9, 5);
1229                 pStart = m_ctrl.data() + (9 + 1);
1230                 break;
1231             default:
1232                 ERROR_MESSAGE("this should be unreachable");
1233                 return;
1234         }
1235
1236         for (std::size_t h = 0; h < 3; h++, pStart += 9) {
1237             pIndex = pCylIndex;
1238             PatchControl *pCtrl = pStart;
1239             for (std::size_t w = 0; w < 8; w++, pCtrl++) {
1240                 pCtrl->m_vertex[0] = vPos[pIndex[0]][0];
1241                 pCtrl->m_vertex[1] = vPos[pIndex[1]][1];
1242                 pCtrl->m_vertex[2] = vPos[h][2];
1243                 pIndex += 2;
1244             }
1245         }
1246
1247         switch (eType) {
1248             case eSqCylinder: {
1249                 PatchControl *pCtrl = m_ctrl.data();
1250                 for (std::size_t h = 0; h < 3; h++, pCtrl += 9) {
1251                     pCtrl[8].m_vertex = pCtrl[0].m_vertex;
1252                 }
1253             }
1254                 break;
1255             case eDenseCylinder:
1256             case eVeryDenseCylinder:
1257             case eCylinder: {
1258                 PatchControl *pCtrl = m_ctrl.data();
1259                 for (std::size_t h = 0; h < 3; h++, pCtrl += 9) {
1260                     pCtrl[0].m_vertex = pCtrl[8].m_vertex;
1261                 }
1262             }
1263                 break;
1264             case eCone: {
1265                 PatchControl *pCtrl = m_ctrl.data();
1266                 for (std::size_t h = 0; h < 2; h++, pCtrl += 9) {
1267                     pCtrl[0].m_vertex = pCtrl[8].m_vertex;
1268                 }
1269             }
1270                 {
1271                     PatchControl *pCtrl = m_ctrl.data() + 9 * 2;
1272                     for (std::size_t w = 0; w < 9; w++, pCtrl++) {
1273                         pCtrl->m_vertex[0] = vPos[1][0];
1274                         pCtrl->m_vertex[1] = vPos[1][1];
1275                         pCtrl->m_vertex[2] = vPos[2][2];
1276                     }
1277                 }
1278                 break;
1279             case eSphere: {
1280                 PatchControl *pCtrl = m_ctrl.data() + 9;
1281                 for (std::size_t h = 0; h < 3; h++, pCtrl += 9) {
1282                     pCtrl[0].m_vertex = pCtrl[8].m_vertex;
1283                 }
1284             }
1285                 {
1286                     PatchControl *pCtrl = m_ctrl.data();
1287                     for (std::size_t w = 0; w < 9; w++, pCtrl++) {
1288                         pCtrl->m_vertex[0] = vPos[1][0];
1289                         pCtrl->m_vertex[1] = vPos[1][1];
1290                         pCtrl->m_vertex[2] = vPos[0][2];
1291                     }
1292                 }
1293                 {
1294                     PatchControl *pCtrl = m_ctrl.data() + (9 * 4);
1295                     for (std::size_t w = 0; w < 9; w++, pCtrl++) {
1296                         pCtrl->m_vertex[0] = vPos[1][0];
1297                         pCtrl->m_vertex[1] = vPos[1][1];
1298                         pCtrl->m_vertex[2] = vPos[2][2];
1299                     }
1300                 }
1301                 break;
1302             default:
1303                 ERROR_MESSAGE("this should be unreachable");
1304                 return;
1305         }
1306     } else if (eType == eXactCylinder) {
1307         int n = (width - 1) / 2; // n = number of segments
1308         setDims(width, height);
1309
1310         // vPos[0] = vector3_subtracted(aabb.origin, aabb.extents);
1311         // vPos[1] = aabb.origin;
1312         // vPos[2] = vector3_added(aabb.origin, aabb.extents);
1313
1314         float f = 1 / cos(M_PI / n);
1315         for (std::size_t i = 0; i < width; ++i) {
1316             float angle = (M_PI * i) / n; // 0 to 2pi
1317             float x = vPos[1][0] + (vPos[2][0] - vPos[1][0]) * cos(angle) * ((i & 1) ? f : 1.0f);
1318             float y = vPos[1][1] + (vPos[2][1] - vPos[1][1]) * sin(angle) * ((i & 1) ? f : 1.0f);
1319             for (std::size_t j = 0; j < height; ++j) {
1320                 float z = vPos[0][2] + (vPos[2][2] - vPos[0][2]) * (j / (float) (height - 1));
1321                 PatchControl *v;
1322                 v = &m_ctrl.data()[j * width + i];
1323                 v->m_vertex[0] = x;
1324                 v->m_vertex[1] = y;
1325                 v->m_vertex[2] = z;
1326             }
1327         }
1328     } else if (eType == eXactCone) {
1329         int n = (width - 1) / 2; // n = number of segments
1330         setDims(width, height);
1331
1332         // vPos[0] = vector3_subtracted(aabb.origin, aabb.extents);
1333         // vPos[1] = aabb.origin;
1334         // vPos[2] = vector3_added(aabb.origin, aabb.extents);
1335
1336         float f = 1 / cos(M_PI / n);
1337         for (std::size_t i = 0; i < width; ++i) {
1338             float angle = (M_PI * i) / n;
1339             for (std::size_t j = 0; j < height; ++j) {
1340                 float x = vPos[1][0] + (1.0f - (j / (float) (height - 1))) * (vPos[2][0] - vPos[1][0]) * cos(angle) *
1341                                        ((i & 1) ? f : 1.0f);
1342                 float y = vPos[1][1] + (1.0f - (j / (float) (height - 1))) * (vPos[2][1] - vPos[1][1]) * sin(angle) *
1343                                        ((i & 1) ? f : 1.0f);
1344                 float z = vPos[0][2] + (vPos[2][2] - vPos[0][2]) * (j / (float) (height - 1));
1345                 PatchControl *v;
1346                 v = &m_ctrl.data()[j * width + i];
1347                 v->m_vertex[0] = x;
1348                 v->m_vertex[1] = y;
1349                 v->m_vertex[2] = z;
1350             }
1351         }
1352     } else if (eType == eXactSphere) {
1353         int n = (width - 1) / 2; // n = number of segments (yaw)
1354         int m = (height - 1) / 2; // m = number of segments (pitch)
1355         setDims(width, height);
1356
1357         // vPos[0] = vector3_subtracted(aabb.origin, aabb.extents);
1358         // vPos[1] = aabb.origin;
1359         // vPos[2] = vector3_added(aabb.origin, aabb.extents);
1360
1361         float f = 1 / cos(M_PI / n);
1362         float g = 1 / cos(M_PI / (2 * m));
1363         for (std::size_t i = 0; i < width; ++i) {
1364             float angle = (M_PI * i) / n;
1365             for (std::size_t j = 0; j < height; ++j) {
1366                 float angle2 = (M_PI * j) / (2 * m);
1367                 float x = vPos[1][0] + (vPos[2][0] - vPos[1][0]) * sin(angle2) * ((j & 1) ? g : 1.0f) * cos(angle) *
1368                                        ((i & 1) ? f : 1.0f);
1369                 float y = vPos[1][1] + (vPos[2][1] - vPos[1][1]) * sin(angle2) * ((j & 1) ? g : 1.0f) * sin(angle) *
1370                                        ((i & 1) ? f : 1.0f);
1371                 float z = vPos[1][2] + (vPos[2][2] - vPos[1][2]) * -cos(angle2) * ((j & 1) ? g : 1.0f);
1372                 PatchControl *v;
1373                 v = &m_ctrl.data()[j * width + i];
1374                 v->m_vertex[0] = x;
1375                 v->m_vertex[1] = y;
1376                 v->m_vertex[2] = z;
1377             }
1378         }
1379     } else if (eType == eBevel) {
1380         unsigned char *pIndex;
1381         unsigned char pBevIndex[] =
1382                 {
1383                         0, 0,
1384                         2, 0,
1385                         2, 2,
1386                 };
1387
1388         setDims(3, 3);
1389
1390         PatchControl *pCtrl = m_ctrl.data();
1391         for (std::size_t h = 0; h < 3; h++) {
1392             pIndex = pBevIndex;
1393             for (std::size_t w = 0; w < 3; w++, pIndex += 2, pCtrl++) {
1394                 pCtrl->m_vertex[0] = vPos[pIndex[0]][0];
1395                 pCtrl->m_vertex[1] = vPos[pIndex[1]][1];
1396                 pCtrl->m_vertex[2] = vPos[h][2];
1397             }
1398         }
1399     } else if (eType == eEndCap) {
1400         unsigned char *pIndex;
1401         unsigned char pEndIndex[] =
1402                 {
1403                         2, 0,
1404                         2, 2,
1405                         1, 2,
1406                         0, 2,
1407                         0, 0,
1408                 };
1409
1410         setDims(5, 3);
1411
1412         PatchControl *pCtrl = m_ctrl.data();
1413         for (std::size_t h = 0; h < 3; h++) {
1414             pIndex = pEndIndex;
1415             for (std::size_t w = 0; w < 5; w++, pIndex += 2, pCtrl++) {
1416                 pCtrl->m_vertex[0] = vPos[pIndex[0]][0];
1417                 pCtrl->m_vertex[1] = vPos[pIndex[1]][1];
1418                 pCtrl->m_vertex[2] = vPos[h][2];
1419             }
1420         }
1421     }
1422
1423     if (eType == eDenseCylinder) {
1424         InsertRemove(true, false, true);
1425     }
1426
1427     if (eType == eVeryDenseCylinder) {
1428         InsertRemove(true, false, false);
1429         InsertRemove(true, false, true);
1430     }
1431
1432     NaturalTexture();
1433 }
1434
1435 void Patch::RenderDebug(RenderStateFlags state) const
1436 {
1437     for (std::size_t i = 0; i < m_tess.m_numStrips; i++) {
1438         glBegin(GL_QUAD_STRIP);
1439         for (std::size_t j = 0; j < m_tess.m_lenStrips; j++) {
1440             glNormal3fv(normal3f_to_array(
1441                     (m_tess.m_vertices.data() + m_tess.m_indices[i * m_tess.m_lenStrips + j])->normal));
1442             glTexCoord2fv(texcoord2f_to_array(
1443                     (m_tess.m_vertices.data() + m_tess.m_indices[i * m_tess.m_lenStrips + j])->texcoord));
1444             glVertex3fv(vertex3f_to_array(
1445                     (m_tess.m_vertices.data() + m_tess.m_indices[i * m_tess.m_lenStrips + j])->vertex));
1446         }
1447         glEnd();
1448     }
1449 }
1450
1451 void RenderablePatchSolid::RenderNormals() const
1452 {
1453     const std::size_t width = m_tess.m_numStrips + 1;
1454     const std::size_t height = m_tess.m_lenStrips >> 1;
1455     glBegin(GL_LINES);
1456     for (std::size_t i = 0; i < width; i++) {
1457         for (std::size_t j = 0; j < height; j++) {
1458             {
1459                 Vector3 vNormal(
1460                         vector3_added(
1461                                 vertex3f_to_vector3((m_tess.m_vertices.data() + (j * width + i))->vertex),
1462                                 vector3_scaled(
1463                                         normal3f_to_vector3((m_tess.m_vertices.data() + (j * width + i))->normal), 8)
1464                         )
1465                 );
1466                 glVertex3fv(vertex3f_to_array((m_tess.m_vertices.data() + (j * width + i))->vertex));
1467                 glVertex3fv(&vNormal[0]);
1468             }
1469             {
1470                 Vector3 vNormal(
1471                         vector3_added(
1472                                 vertex3f_to_vector3((m_tess.m_vertices.data() + (j * width + i))->vertex),
1473                                 vector3_scaled(
1474                                         normal3f_to_vector3((m_tess.m_vertices.data() + (j * width + i))->tangent), 8)
1475                         )
1476                 );
1477                 glVertex3fv(vertex3f_to_array((m_tess.m_vertices.data() + (j * width + i))->vertex));
1478                 glVertex3fv(&vNormal[0]);
1479             }
1480             {
1481                 Vector3 vNormal(
1482                         vector3_added(
1483                                 vertex3f_to_vector3((m_tess.m_vertices.data() + (j * width + i))->vertex),
1484                                 vector3_scaled(
1485                                         normal3f_to_vector3((m_tess.m_vertices.data() + (j * width + i))->bitangent), 8)
1486                         )
1487                 );
1488                 glVertex3fv(vertex3f_to_array((m_tess.m_vertices.data() + (j * width + i))->vertex));
1489                 glVertex3fv(&vNormal[0]);
1490             }
1491         }
1492     }
1493     glEnd();
1494 }
1495
1496 const int DEGEN_0a = 0x01;
1497 const int DEGEN_1a = 0x02;
1498 const int DEGEN_2a = 0x04;
1499 const int DEGEN_0b = 0x08;
1500 const int DEGEN_1b = 0x10;
1501 const int DEGEN_2b = 0x20;
1502 const int SPLIT = 0x40;
1503 const int AVERAGE = 0x80;
1504
1505
1506 unsigned int subarray_get_degen(PatchControlIter subarray, std::size_t strideU, std::size_t strideV)
1507 {
1508     unsigned int nDegen = 0;
1509     const PatchControl *p1;
1510     const PatchControl *p2;
1511
1512     p1 = subarray;
1513     p2 = p1 + strideU;
1514     if (vector3_equal(p1->m_vertex, p2->m_vertex)) {
1515         nDegen |= DEGEN_0a;
1516     }
1517     p1 = p2;
1518     p2 = p1 + strideU;
1519     if (vector3_equal(p1->m_vertex, p2->m_vertex)) {
1520         nDegen |= DEGEN_0b;
1521     }
1522
1523     p1 = subarray + strideV;
1524     p2 = p1 + strideU;
1525     if (vector3_equal(p1->m_vertex, p2->m_vertex)) {
1526         nDegen |= DEGEN_1a;
1527     }
1528     p1 = p2;
1529     p2 = p1 + strideU;
1530     if (vector3_equal(p1->m_vertex, p2->m_vertex)) {
1531         nDegen |= DEGEN_1b;
1532     }
1533
1534     p1 = subarray + (strideV << 1);
1535     p2 = p1 + strideU;
1536     if (vector3_equal(p1->m_vertex, p2->m_vertex)) {
1537         nDegen |= DEGEN_2a;
1538     }
1539     p1 = p2;
1540     p2 = p1 + strideU;
1541     if (vector3_equal(p1->m_vertex, p2->m_vertex)) {
1542         nDegen |= DEGEN_2b;
1543     }
1544
1545     return nDegen;
1546 }
1547
1548
1549 inline void
1550 deCasteljau3(const Vector3 &P0, const Vector3 &P1, const Vector3 &P2, Vector3 &P01, Vector3 &P12, Vector3 &P012)
1551 {
1552     P01 = vector3_mid(P0, P1);
1553     P12 = vector3_mid(P1, P2);
1554     P012 = vector3_mid(P01, P12);
1555 }
1556
1557 inline void BezierInterpolate3(const Vector3 &start, Vector3 &left, Vector3 &mid, Vector3 &right, const Vector3 &end)
1558 {
1559     left = vector3_mid(start, mid);
1560     right = vector3_mid(mid, end);
1561     mid = vector3_mid(left, right);
1562 }
1563
1564 inline void BezierInterpolate2(const Vector2 &start, Vector2 &left, Vector2 &mid, Vector2 &right, const Vector2 &end)
1565 {
1566     left[0] = float_mid(start[0], mid[0]);
1567     left[1] = float_mid(start[1], mid[1]);
1568     right[0] = float_mid(mid[0], end[0]);
1569     right[1] = float_mid(mid[1], end[1]);
1570     mid[0] = float_mid(left[0], right[0]);
1571     mid[1] = float_mid(left[1], right[1]);
1572 }
1573
1574
1575 inline Vector2 &texcoord_for_index(Array<ArbitraryMeshVertex> &vertices, std::size_t index)
1576 {
1577     return reinterpret_cast<Vector2 &>( vertices[index].texcoord );
1578 }
1579
1580 inline Vector3 &vertex_for_index(Array<ArbitraryMeshVertex> &vertices, std::size_t index)
1581 {
1582     return reinterpret_cast<Vector3 &>( vertices[index].vertex );
1583 }
1584
1585 inline Vector3 &normal_for_index(Array<ArbitraryMeshVertex> &vertices, std::size_t index)
1586 {
1587     return reinterpret_cast<Vector3 &>( vertices[index].normal );
1588 }
1589
1590 inline Vector3 &tangent_for_index(Array<ArbitraryMeshVertex> &vertices, std::size_t index)
1591 {
1592     return reinterpret_cast<Vector3 &>( vertices[index].tangent );
1593 }
1594
1595 inline Vector3 &bitangent_for_index(Array<ArbitraryMeshVertex> &vertices, std::size_t index)
1596 {
1597     return reinterpret_cast<Vector3 &>( vertices[index].bitangent );
1598 }
1599
1600 inline const Vector2 &texcoord_for_index(const Array<ArbitraryMeshVertex> &vertices, std::size_t index)
1601 {
1602     return reinterpret_cast<const Vector2 &>( vertices[index].texcoord );
1603 }
1604
1605 inline const Vector3 &vertex_for_index(const Array<ArbitraryMeshVertex> &vertices, std::size_t index)
1606 {
1607     return reinterpret_cast<const Vector3 &>( vertices[index].vertex );
1608 }
1609
1610 inline const Vector3 &normal_for_index(const Array<ArbitraryMeshVertex> &vertices, std::size_t index)
1611 {
1612     return reinterpret_cast<const Vector3 &>( vertices[index].normal );
1613 }
1614
1615 inline const Vector3 &tangent_for_index(const Array<ArbitraryMeshVertex> &vertices, std::size_t index)
1616 {
1617     return reinterpret_cast<const Vector3 &>( vertices[index].tangent );
1618 }
1619
1620 inline const Vector3 &bitangent_for_index(const Array<ArbitraryMeshVertex> &vertices, std::size_t index)
1621 {
1622     return reinterpret_cast<const Vector3 &>( vertices[index].bitangent );
1623 }
1624
1625 #include "math/curve.h"
1626
1627 inline PatchControl QuadraticBezier_evaluate(const PatchControl *firstPoint, double t)
1628 {
1629     PatchControl result = {Vector3(0, 0, 0), Vector2(0, 0)};
1630     double denominator = 0;
1631
1632     {
1633         double weight = BernsteinPolynomial<Zero, Two>::apply(t);
1634         vector3_add(result.m_vertex, vector3_scaled(firstPoint[0].m_vertex, weight));
1635         vector2_add(result.m_texcoord, vector2_scaled(firstPoint[0].m_texcoord, weight));
1636         denominator += weight;
1637     }
1638     {
1639         double weight = BernsteinPolynomial<One, Two>::apply(t);
1640         vector3_add(result.m_vertex, vector3_scaled(firstPoint[1].m_vertex, weight));
1641         vector2_add(result.m_texcoord, vector2_scaled(firstPoint[1].m_texcoord, weight));
1642         denominator += weight;
1643     }
1644     {
1645         double weight = BernsteinPolynomial<Two, Two>::apply(t);
1646         vector3_add(result.m_vertex, vector3_scaled(firstPoint[2].m_vertex, weight));
1647         vector2_add(result.m_texcoord, vector2_scaled(firstPoint[2].m_texcoord, weight));
1648         denominator += weight;
1649     }
1650
1651     vector3_divide(result.m_vertex, denominator);
1652     vector2_divide(result.m_texcoord, denominator);
1653     return result;
1654 }
1655
1656 inline Vector3 vector3_linear_interpolated(const Vector3 &a, const Vector3 &b, double t)
1657 {
1658     return vector3_added(vector3_scaled(a, 1.0 - t), vector3_scaled(b, t));
1659 }
1660
1661 inline Vector2 vector2_linear_interpolated(const Vector2 &a, const Vector2 &b, double t)
1662 {
1663     return vector2_added(vector2_scaled(a, 1.0 - t), vector2_scaled(b, t));
1664 }
1665
1666 void normalise_safe(Vector3 &normal)
1667 {
1668     if (!vector3_equal(normal, g_vector3_identity)) {
1669         vector3_normalise(normal);
1670     }
1671 }
1672
1673 inline void QuadraticBezier_evaluate(const PatchControl &a, const PatchControl &b, const PatchControl &c, double t,
1674                                      PatchControl &point, PatchControl &left, PatchControl &right)
1675 {
1676     left.m_vertex = vector3_linear_interpolated(a.m_vertex, b.m_vertex, t);
1677     left.m_texcoord = vector2_linear_interpolated(a.m_texcoord, b.m_texcoord, t);
1678     right.m_vertex = vector3_linear_interpolated(b.m_vertex, c.m_vertex, t);
1679     right.m_texcoord = vector2_linear_interpolated(b.m_texcoord, c.m_texcoord, t);
1680     point.m_vertex = vector3_linear_interpolated(left.m_vertex, right.m_vertex, t);
1681     point.m_texcoord = vector2_linear_interpolated(left.m_texcoord, right.m_texcoord, t);
1682 }
1683
1684 void Patch::TesselateSubMatrixFixed(ArbitraryMeshVertex *vertices, std::size_t strideX, std::size_t strideY,
1685                                     unsigned int nFlagsX, unsigned int nFlagsY, PatchControl *subMatrix[3][3])
1686 {
1687     double incrementU = 1.0 / m_subdivisions_x;
1688     double incrementV = 1.0 / m_subdivisions_y;
1689     const std::size_t width = m_subdivisions_x + 1;
1690     const std::size_t height = m_subdivisions_y + 1;
1691
1692     for (std::size_t i = 0; i != width; ++i) {
1693         double tU = (i + 1 == width) ? 1 : i * incrementU;
1694         PatchControl pointX[3];
1695         PatchControl leftX[3];
1696         PatchControl rightX[3];
1697         QuadraticBezier_evaluate(*subMatrix[0][0], *subMatrix[0][1], *subMatrix[0][2], tU, pointX[0], leftX[0],
1698                                  rightX[0]);
1699         QuadraticBezier_evaluate(*subMatrix[1][0], *subMatrix[1][1], *subMatrix[1][2], tU, pointX[1], leftX[1],
1700                                  rightX[1]);
1701         QuadraticBezier_evaluate(*subMatrix[2][0], *subMatrix[2][1], *subMatrix[2][2], tU, pointX[2], leftX[2],
1702                                  rightX[2]);
1703
1704         ArbitraryMeshVertex *p = vertices + i * strideX;
1705         for (std::size_t j = 0; j != height; ++j) {
1706             if ((j == 0 || j + 1 == height) && (i == 0 || i + 1 == width)) {
1707             } else {
1708                 double tV = (j + 1 == height) ? 1 : j * incrementV;
1709
1710                 PatchControl pointY[3];
1711                 PatchControl leftY[3];
1712                 PatchControl rightY[3];
1713                 QuadraticBezier_evaluate(*subMatrix[0][0], *subMatrix[1][0], *subMatrix[2][0], tV, pointY[0], leftY[0],
1714                                          rightY[0]);
1715                 QuadraticBezier_evaluate(*subMatrix[0][1], *subMatrix[1][1], *subMatrix[2][1], tV, pointY[1], leftY[1],
1716                                          rightY[1]);
1717                 QuadraticBezier_evaluate(*subMatrix[0][2], *subMatrix[1][2], *subMatrix[2][2], tV, pointY[2], leftY[2],
1718                                          rightY[2]);
1719
1720                 PatchControl point;
1721                 PatchControl left;
1722                 PatchControl right;
1723                 QuadraticBezier_evaluate(pointX[0], pointX[1], pointX[2], tV, point, left, right);
1724                 PatchControl up;
1725                 PatchControl down;
1726                 QuadraticBezier_evaluate(pointY[0], pointY[1], pointY[2], tU, point, up, down);
1727
1728                 vertex3f_to_vector3(p->vertex) = point.m_vertex;
1729                 texcoord2f_to_vector2(p->texcoord) = point.m_texcoord;
1730
1731                 ArbitraryMeshVertex a, b, c;
1732
1733                 a.vertex = vertex3f_for_vector3(left.m_vertex);
1734                 a.texcoord = texcoord2f_for_vector2(left.m_texcoord);
1735                 b.vertex = vertex3f_for_vector3(right.m_vertex);
1736                 b.texcoord = texcoord2f_for_vector2(right.m_texcoord);
1737
1738                 if (i != 0) {
1739                     c.vertex = vertex3f_for_vector3(up.m_vertex);
1740                     c.texcoord = texcoord2f_for_vector2(up.m_texcoord);
1741                 } else {
1742                     c.vertex = vertex3f_for_vector3(down.m_vertex);
1743                     c.texcoord = texcoord2f_for_vector2(down.m_texcoord);
1744                 }
1745
1746                 Vector3 normal = vector3_normalised(
1747                         vector3_cross(right.m_vertex - left.m_vertex, up.m_vertex - down.m_vertex));
1748
1749                 Vector3 tangent, bitangent;
1750                 ArbitraryMeshTriangle_calcTangents(a, b, c, tangent, bitangent);
1751                 vector3_normalise(tangent);
1752                 vector3_normalise(bitangent);
1753
1754                 if (((nFlagsX & AVERAGE) != 0 && i == 0) || ((nFlagsY & AVERAGE) != 0 && j == 0)) {
1755                     normal3f_to_vector3(p->normal) = vector3_normalised(
1756                             vector3_added(normal3f_to_vector3(p->normal), normal));
1757                     normal3f_to_vector3(p->tangent) = vector3_normalised(
1758                             vector3_added(normal3f_to_vector3(p->tangent), tangent));
1759                     normal3f_to_vector3(p->bitangent) = vector3_normalised(
1760                             vector3_added(normal3f_to_vector3(p->bitangent), bitangent));
1761                 } else {
1762                     normal3f_to_vector3(p->normal) = normal;
1763                     normal3f_to_vector3(p->tangent) = tangent;
1764                     normal3f_to_vector3(p->bitangent) = bitangent;
1765                 }
1766             }
1767
1768             p += strideY;
1769         }
1770     }
1771 }
1772
1773 void Patch::TesselateSubMatrix(const BezierCurveTree *BX, const BezierCurveTree *BY,
1774                                std::size_t offStartX, std::size_t offStartY,
1775                                std::size_t offEndX, std::size_t offEndY,
1776                                std::size_t nFlagsX, std::size_t nFlagsY,
1777                                Vector3 &left, Vector3 &mid, Vector3 &right,
1778                                Vector2 &texLeft, Vector2 &texMid, Vector2 &texRight,
1779                                bool bTranspose)
1780 {
1781     int newFlagsX, newFlagsY;
1782
1783     Vector3 tmp;
1784     Vector3 vertex_0_0, vertex_0_1, vertex_1_0, vertex_1_1, vertex_2_0, vertex_2_1;
1785     Vector2 texTmp;
1786     Vector2 texcoord_0_0, texcoord_0_1, texcoord_1_0, texcoord_1_1, texcoord_2_0, texcoord_2_1;
1787
1788     {
1789         // texcoords
1790
1791         BezierInterpolate2(texcoord_for_index(m_tess.m_vertices, offStartX + offStartY),
1792                            texcoord_0_0,
1793                            texcoord_for_index(m_tess.m_vertices, BX->index + offStartY),
1794                            texcoord_0_1,
1795                            texcoord_for_index(m_tess.m_vertices, offEndX + offStartY));
1796
1797
1798         BezierInterpolate2(texcoord_for_index(m_tess.m_vertices, offStartX + offEndY),
1799                            texcoord_2_0,
1800                            texcoord_for_index(m_tess.m_vertices, BX->index + offEndY),
1801                            texcoord_2_1,
1802                            texcoord_for_index(m_tess.m_vertices, offEndX + offEndY));
1803
1804         texTmp = texMid;
1805
1806         BezierInterpolate2(texLeft,
1807                            texcoord_1_0,
1808                            texTmp,
1809                            texcoord_1_1,
1810                            texRight);
1811
1812         if (!BezierCurveTree_isLeaf(BY)) {
1813             texcoord_for_index(m_tess.m_vertices, BX->index + BY->index) = texTmp;
1814         }
1815
1816
1817         if (!BezierCurveTree_isLeaf(BX->left)) {
1818             texcoord_for_index(m_tess.m_vertices, BX->left->index + offStartY) = texcoord_0_0;
1819             texcoord_for_index(m_tess.m_vertices, BX->left->index + offEndY) = texcoord_2_0;
1820
1821             if (!BezierCurveTree_isLeaf(BY)) {
1822                 texcoord_for_index(m_tess.m_vertices, BX->left->index + BY->index) = texcoord_1_0;
1823             }
1824         }
1825         if (!BezierCurveTree_isLeaf(BX->right)) {
1826             texcoord_for_index(m_tess.m_vertices, BX->right->index + offStartY) = texcoord_0_1;
1827             texcoord_for_index(m_tess.m_vertices, BX->right->index + offEndY) = texcoord_2_1;
1828
1829             if (!BezierCurveTree_isLeaf(BY)) {
1830                 texcoord_for_index(m_tess.m_vertices, BX->right->index + BY->index) = texcoord_1_1;
1831             }
1832         }
1833
1834
1835         // verts
1836
1837         BezierInterpolate3(vertex_for_index(m_tess.m_vertices, offStartX + offStartY),
1838                            vertex_0_0,
1839                            vertex_for_index(m_tess.m_vertices, BX->index + offStartY),
1840                            vertex_0_1,
1841                            vertex_for_index(m_tess.m_vertices, offEndX + offStartY));
1842
1843
1844         BezierInterpolate3(vertex_for_index(m_tess.m_vertices, offStartX + offEndY),
1845                            vertex_2_0,
1846                            vertex_for_index(m_tess.m_vertices, BX->index + offEndY),
1847                            vertex_2_1,
1848                            vertex_for_index(m_tess.m_vertices, offEndX + offEndY));
1849
1850
1851         tmp = mid;
1852
1853         BezierInterpolate3(left,
1854                            vertex_1_0,
1855                            tmp,
1856                            vertex_1_1,
1857                            right);
1858
1859         if (!BezierCurveTree_isLeaf(BY)) {
1860             vertex_for_index(m_tess.m_vertices, BX->index + BY->index) = tmp;
1861         }
1862
1863
1864         if (!BezierCurveTree_isLeaf(BX->left)) {
1865             vertex_for_index(m_tess.m_vertices, BX->left->index + offStartY) = vertex_0_0;
1866             vertex_for_index(m_tess.m_vertices, BX->left->index + offEndY) = vertex_2_0;
1867
1868             if (!BezierCurveTree_isLeaf(BY)) {
1869                 vertex_for_index(m_tess.m_vertices, BX->left->index + BY->index) = vertex_1_0;
1870             }
1871         }
1872         if (!BezierCurveTree_isLeaf(BX->right)) {
1873             vertex_for_index(m_tess.m_vertices, BX->right->index + offStartY) = vertex_0_1;
1874             vertex_for_index(m_tess.m_vertices, BX->right->index + offEndY) = vertex_2_1;
1875
1876             if (!BezierCurveTree_isLeaf(BY)) {
1877                 vertex_for_index(m_tess.m_vertices, BX->right->index + BY->index) = vertex_1_1;
1878             }
1879         }
1880
1881         // normals
1882
1883         if (nFlagsX & SPLIT) {
1884             ArbitraryMeshVertex a, b, c;
1885             Vector3 tangentU;
1886
1887             if (!(nFlagsX & DEGEN_0a) || !(nFlagsX & DEGEN_0b)) {
1888                 tangentU = vector3_subtracted(vertex_0_1, vertex_0_0);
1889                 a.vertex = vertex3f_for_vector3(vertex_0_0);
1890                 a.texcoord = texcoord2f_for_vector2(texcoord_0_0);
1891                 c.vertex = vertex3f_for_vector3(vertex_0_1);
1892                 c.texcoord = texcoord2f_for_vector2(texcoord_0_1);
1893             } else if (!(nFlagsX & DEGEN_1a) || !(nFlagsX & DEGEN_1b)) {
1894                 tangentU = vector3_subtracted(vertex_1_1, vertex_1_0);
1895                 a.vertex = vertex3f_for_vector3(vertex_1_0);
1896                 a.texcoord = texcoord2f_for_vector2(texcoord_1_0);
1897                 c.vertex = vertex3f_for_vector3(vertex_1_1);
1898                 c.texcoord = texcoord2f_for_vector2(texcoord_1_1);
1899             } else {
1900                 tangentU = vector3_subtracted(vertex_2_1, vertex_2_0);
1901                 a.vertex = vertex3f_for_vector3(vertex_2_0);
1902                 a.texcoord = texcoord2f_for_vector2(texcoord_2_0);
1903                 c.vertex = vertex3f_for_vector3(vertex_2_1);
1904                 c.texcoord = texcoord2f_for_vector2(texcoord_2_1);
1905             }
1906
1907             Vector3 tangentV;
1908
1909             if ((nFlagsY & DEGEN_0a) && (nFlagsY & DEGEN_1a) && (nFlagsY & DEGEN_2a)) {
1910                 tangentV = vector3_subtracted(vertex_for_index(m_tess.m_vertices, BX->index + offEndY), tmp);
1911                 b.vertex = vertex3f_for_vector3(tmp); //m_tess.m_vertices[BX->index + offEndY].vertex;
1912                 b.texcoord = texcoord2f_for_vector2(texTmp); //m_tess.m_vertices[BX->index + offEndY].texcoord;
1913             } else {
1914                 tangentV = vector3_subtracted(tmp, vertex_for_index(m_tess.m_vertices, BX->index + offStartY));
1915                 b.vertex = vertex3f_for_vector3(tmp); //m_tess.m_vertices[BX->index + offStartY].vertex;
1916                 b.texcoord = texcoord2f_for_vector2(texTmp); //m_tess.m_vertices[BX->index + offStartY].texcoord;
1917             }
1918
1919
1920             Vector3 normal, s, t;
1921             ArbitraryMeshVertex &v = m_tess.m_vertices[offStartY + BX->index];
1922             Vector3 &p = normal3f_to_vector3(v.normal);
1923             Vector3 &ps = normal3f_to_vector3(v.tangent);
1924             Vector3 &pt = normal3f_to_vector3(v.bitangent);
1925
1926             if (bTranspose) {
1927                 normal = vector3_cross(tangentV, tangentU);
1928             } else {
1929                 normal = vector3_cross(tangentU, tangentV);
1930             }
1931             normalise_safe(normal);
1932
1933             ArbitraryMeshTriangle_calcTangents(a, b, c, s, t);
1934             normalise_safe(s);
1935             normalise_safe(t);
1936
1937             if (nFlagsX & AVERAGE) {
1938                 p = vector3_normalised(vector3_added(p, normal));
1939                 ps = vector3_normalised(vector3_added(ps, s));
1940                 pt = vector3_normalised(vector3_added(pt, t));
1941             } else {
1942                 p = normal;
1943                 ps = s;
1944                 pt = t;
1945             }
1946         }
1947
1948         {
1949             ArbitraryMeshVertex a, b, c;
1950             Vector3 tangentU;
1951
1952             if (!(nFlagsX & DEGEN_2a) || !(nFlagsX & DEGEN_2b)) {
1953                 tangentU = vector3_subtracted(vertex_2_1, vertex_2_0);
1954                 a.vertex = vertex3f_for_vector3(vertex_2_0);
1955                 a.texcoord = texcoord2f_for_vector2(texcoord_2_0);
1956                 c.vertex = vertex3f_for_vector3(vertex_2_1);
1957                 c.texcoord = texcoord2f_for_vector2(texcoord_2_1);
1958             } else if (!(nFlagsX & DEGEN_1a) || !(nFlagsX & DEGEN_1b)) {
1959                 tangentU = vector3_subtracted(vertex_1_1, vertex_1_0);
1960                 a.vertex = vertex3f_for_vector3(vertex_1_0);
1961                 a.texcoord = texcoord2f_for_vector2(texcoord_1_0);
1962                 c.vertex = vertex3f_for_vector3(vertex_1_1);
1963                 c.texcoord = texcoord2f_for_vector2(texcoord_1_1);
1964             } else {
1965                 tangentU = vector3_subtracted(vertex_0_1, vertex_0_0);
1966                 a.vertex = vertex3f_for_vector3(vertex_0_0);
1967                 a.texcoord = texcoord2f_for_vector2(texcoord_0_0);
1968                 c.vertex = vertex3f_for_vector3(vertex_0_1);
1969                 c.texcoord = texcoord2f_for_vector2(texcoord_0_1);
1970             }
1971
1972             Vector3 tangentV;
1973
1974             if ((nFlagsY & DEGEN_0b) && (nFlagsY & DEGEN_1b) && (nFlagsY & DEGEN_2b)) {
1975                 tangentV = vector3_subtracted(tmp, vertex_for_index(m_tess.m_vertices, BX->index + offStartY));
1976                 b.vertex = vertex3f_for_vector3(tmp); //m_tess.m_vertices[BX->index + offStartY].vertex;
1977                 b.texcoord = texcoord2f_for_vector2(texTmp); //m_tess.m_vertices[BX->index + offStartY].texcoord;
1978             } else {
1979                 tangentV = vector3_subtracted(vertex_for_index(m_tess.m_vertices, BX->index + offEndY), tmp);
1980                 b.vertex = vertex3f_for_vector3(tmp); //m_tess.m_vertices[BX->index + offEndY].vertex;
1981                 b.texcoord = texcoord2f_for_vector2(texTmp); //m_tess.m_vertices[BX->index + offEndY].texcoord;
1982             }
1983
1984             ArbitraryMeshVertex &v = m_tess.m_vertices[offEndY + BX->index];
1985             Vector3 &p = normal3f_to_vector3(v.normal);
1986             Vector3 &ps = normal3f_to_vector3(v.tangent);
1987             Vector3 &pt = normal3f_to_vector3(v.bitangent);
1988
1989             if (bTranspose) {
1990                 p = vector3_cross(tangentV, tangentU);
1991             } else {
1992                 p = vector3_cross(tangentU, tangentV);
1993             }
1994             normalise_safe(p);
1995
1996             ArbitraryMeshTriangle_calcTangents(a, b, c, ps, pt);
1997             normalise_safe(ps);
1998             normalise_safe(pt);
1999         }
2000     }
2001
2002
2003     newFlagsX = newFlagsY = 0;
2004
2005     if ((nFlagsX & DEGEN_0a) && (nFlagsX & DEGEN_0b)) {
2006         newFlagsX |= DEGEN_0a;
2007         newFlagsX |= DEGEN_0b;
2008     }
2009     if ((nFlagsX & DEGEN_1a) && (nFlagsX & DEGEN_1b)) {
2010         newFlagsX |= DEGEN_1a;
2011         newFlagsX |= DEGEN_1b;
2012     }
2013     if ((nFlagsX & DEGEN_2a) && (nFlagsX & DEGEN_2b)) {
2014         newFlagsX |= DEGEN_2a;
2015         newFlagsX |= DEGEN_2b;
2016     }
2017     if ((nFlagsY & DEGEN_0a) && (nFlagsY & DEGEN_1a) && (nFlagsY & DEGEN_2a)) {
2018         newFlagsY |= DEGEN_0a;
2019         newFlagsY |= DEGEN_1a;
2020         newFlagsY |= DEGEN_2a;
2021     }
2022     if ((nFlagsY & DEGEN_0b) && (nFlagsY & DEGEN_1b) && (nFlagsY & DEGEN_2b)) {
2023         newFlagsY |= DEGEN_0b;
2024         newFlagsY |= DEGEN_1b;
2025         newFlagsY |= DEGEN_2b;
2026     }
2027
2028
2029     //if((nFlagsX & DEGEN_0a) && (nFlagsX & DEGEN_1a) && (nFlagsX & DEGEN_2a)) { newFlagsX |= DEGEN_0a; newFlagsX |= DEGEN_1a; newFlagsX |= DEGEN_2a; }
2030     //if((nFlagsX & DEGEN_0b) && (nFlagsX & DEGEN_1b) && (nFlagsX & DEGEN_2b)) { newFlagsX |= DEGEN_0b; newFlagsX |= DEGEN_1b; newFlagsX |= DEGEN_2b; }
2031
2032     newFlagsX |= (nFlagsX & SPLIT);
2033     newFlagsX |= (nFlagsX & AVERAGE);
2034
2035     if (!BezierCurveTree_isLeaf(BY)) {
2036         {
2037             int nTemp = newFlagsY;
2038
2039             if ((nFlagsY & DEGEN_0a) && (nFlagsY & DEGEN_0b)) {
2040                 newFlagsY |= DEGEN_0a;
2041                 newFlagsY |= DEGEN_0b;
2042             }
2043             newFlagsY |= (nFlagsY & SPLIT);
2044             newFlagsY |= (nFlagsY & AVERAGE);
2045
2046             Vector3 &p = vertex_for_index(m_tess.m_vertices, BX->index + BY->index);
2047             Vector3 vTemp(p);
2048
2049             Vector2 &p2 = texcoord_for_index(m_tess.m_vertices, BX->index + BY->index);
2050             Vector2 stTemp(p2);
2051
2052             TesselateSubMatrix(BY, BX->left,
2053                                offStartY, offStartX,
2054                                offEndY, BX->index,
2055                                newFlagsY, newFlagsX,
2056                                vertex_0_0, vertex_1_0, vertex_2_0,
2057                                texcoord_0_0, texcoord_1_0, texcoord_2_0,
2058                                !bTranspose);
2059
2060             newFlagsY = nTemp;
2061             p = vTemp;
2062             p2 = stTemp;
2063         }
2064
2065         if ((nFlagsY & DEGEN_2a) && (nFlagsY & DEGEN_2b)) {
2066             newFlagsY |= DEGEN_2a;
2067             newFlagsY |= DEGEN_2b;
2068         }
2069
2070         TesselateSubMatrix(BY, BX->right,
2071                            offStartY, BX->index,
2072                            offEndY, offEndX,
2073                            newFlagsY, newFlagsX,
2074                            vertex_0_1, vertex_1_1, vertex_2_1,
2075                            texcoord_0_1, texcoord_1_1, texcoord_2_1,
2076                            !bTranspose);
2077     } else {
2078         if (!BezierCurveTree_isLeaf(BX->left)) {
2079             TesselateSubMatrix(BX->left, BY,
2080                                offStartX, offStartY,
2081                                BX->index, offEndY,
2082                                newFlagsX, newFlagsY,
2083                                left, vertex_1_0, tmp,
2084                                texLeft, texcoord_1_0, texTmp,
2085                                bTranspose);
2086         }
2087
2088         if (!BezierCurveTree_isLeaf(BX->right)) {
2089             TesselateSubMatrix(BX->right, BY,
2090                                BX->index, offStartY,
2091                                offEndX, offEndY,
2092                                newFlagsX, newFlagsY,
2093                                tmp, vertex_1_1, right,
2094                                texTmp, texcoord_1_1, texRight,
2095                                bTranspose);
2096         }
2097     }
2098
2099 }
2100
2101 void Patch::BuildTesselationCurves(EMatrixMajor major)
2102 {
2103     std::size_t nArrayStride, length, cross, strideU, strideV;
2104     switch (major) {
2105         case ROW:
2106             nArrayStride = 1;
2107             length = (m_width - 1) >> 1;
2108             cross = m_height;
2109             strideU = 1;
2110             strideV = m_width;
2111
2112             if (!m_patchDef3) {
2113                 BezierCurveTreeArray_deleteAll(m_tess.m_curveTreeU);
2114             }
2115
2116             break;
2117         case COL:
2118             nArrayStride = m_tess.m_nArrayWidth;
2119             length = (m_height - 1) >> 1;
2120             cross = m_width;
2121             strideU = m_width;
2122             strideV = 1;
2123
2124             if (!m_patchDef3) {
2125                 BezierCurveTreeArray_deleteAll(m_tess.m_curveTreeV);
2126             }
2127
2128             break;
2129         default:
2130             ERROR_MESSAGE("neither row-major nor column-major");
2131             return;
2132     }
2133
2134     Array<std::size_t> arrayLength(length);
2135     Array<BezierCurveTree *> pCurveTree(length);
2136
2137     std::size_t nArrayLength = 1;
2138
2139     if (m_patchDef3) {
2140         for (Array<std::size_t>::iterator i = arrayLength.begin(); i != arrayLength.end(); ++i) {
2141             *i = Array<std::size_t>::value_type((major == ROW) ? m_subdivisions_x : m_subdivisions_y);
2142             nArrayLength += *i;
2143         }
2144     } else {
2145         // create a list of the horizontal control curves in each column of sub-patches
2146         // adaptively tesselate each horizontal control curve in the list
2147         // create a binary tree representing the combined tesselation of the list
2148         for (std::size_t i = 0; i != length; ++i) {
2149             PatchControl *p1 = m_ctrlTransformed.data() + (i * 2 * strideU);
2150             GSList *pCurveList = 0;
2151             for (std::size_t j = 0; j < cross; j += 2) {
2152                 PatchControl *p2 = p1 + strideV;
2153                 PatchControl *p3 = p2 + strideV;
2154
2155                 // directly taken from one row of control points
2156                 {
2157                     BezierCurve *pCurve = new BezierCurve;
2158                     pCurve->crd = (p1 + strideU)->m_vertex;
2159                     pCurve->left = p1->m_vertex;
2160                     pCurve->right = (p1 + (strideU << 1))->m_vertex;
2161                     pCurveList = g_slist_prepend(pCurveList, pCurve);
2162                 }
2163
2164                 if (j + 2 >= cross) {
2165                     break;
2166                 }
2167
2168                 // interpolated from three columns of control points
2169                 {
2170                     BezierCurve *pCurve = new BezierCurve;
2171                     pCurve->crd = vector3_mid((p1 + strideU)->m_vertex, (p3 + strideU)->m_vertex);
2172                     pCurve->left = vector3_mid(p1->m_vertex, p3->m_vertex);
2173                     pCurve->right = vector3_mid((p1 + (strideU << 1))->m_vertex, (p3 + (strideU << 1))->m_vertex);
2174
2175                     pCurve->crd = vector3_mid(pCurve->crd, (p2 + strideU)->m_vertex);
2176                     pCurve->left = vector3_mid(pCurve->left, p2->m_vertex);
2177                     pCurve->right = vector3_mid(pCurve->right, (p2 + (strideU << 1))->m_vertex);
2178                     pCurveList = g_slist_prepend(pCurveList, pCurve);
2179                 }
2180
2181                 p1 = p3;
2182             }
2183
2184             pCurveTree[i] = new BezierCurveTree;
2185             BezierCurveTree_FromCurveList(pCurveTree[i], pCurveList);
2186             for (GSList *l = pCurveList; l != 0; l = g_slist_next(l)) {
2187                 delete static_cast<BezierCurve *>((*l).data );
2188             }
2189             g_slist_free(pCurveList);
2190
2191             // set up array indices for binary tree
2192             // accumulate subarray width
2193             arrayLength[i] = Array<std::size_t>::value_type(
2194                     BezierCurveTree_Setup(pCurveTree[i], nArrayLength, nArrayStride) - (nArrayLength - 1));
2195             // accumulate total array width
2196             nArrayLength += arrayLength[i];
2197         }
2198     }
2199
2200     switch (major) {
2201         case ROW:
2202             m_tess.m_nArrayWidth = nArrayLength;
2203             std::swap(m_tess.m_arrayWidth, arrayLength);
2204
2205             if (!m_patchDef3) {
2206                 std::swap(m_tess.m_curveTreeU, pCurveTree);
2207             }
2208             break;
2209         case COL:
2210             m_tess.m_nArrayHeight = nArrayLength;
2211             std::swap(m_tess.m_arrayHeight, arrayLength);
2212
2213             if (!m_patchDef3) {
2214                 std::swap(m_tess.m_curveTreeV, pCurveTree);
2215             }
2216             break;
2217     }
2218 }
2219
2220 inline void vertex_assign_ctrl(ArbitraryMeshVertex &vertex, const PatchControl &ctrl)
2221 {
2222     vertex.vertex = vertex3f_for_vector3(ctrl.m_vertex);
2223     vertex.texcoord = texcoord2f_for_vector2(ctrl.m_texcoord);
2224 }
2225
2226 inline void vertex_clear_normal(ArbitraryMeshVertex &vertex)
2227 {
2228     vertex.normal = Normal3f(0, 0, 0);
2229     vertex.tangent = Normal3f(0, 0, 0);
2230     vertex.bitangent = Normal3f(0, 0, 0);
2231 }
2232
2233 inline void tangents_remove_degenerate(Vector3 tangents[6], Vector2 textureTangents[6], unsigned int flags)
2234 {
2235     if (flags & DEGEN_0a) {
2236         const std::size_t i =
2237                 (flags & DEGEN_0b)
2238                 ? (flags & DEGEN_1a)
2239                   ? (flags & DEGEN_1b)
2240                     ? (flags & DEGEN_2a)
2241                       ? 5
2242                       : 4
2243                     : 3
2244                   : 2
2245                 : 1;
2246         tangents[0] = tangents[i];
2247         textureTangents[0] = textureTangents[i];
2248     }
2249     if (flags & DEGEN_0b) {
2250         const std::size_t i =
2251                 (flags & DEGEN_0a)
2252                 ? (flags & DEGEN_1b)
2253                   ? (flags & DEGEN_1a)
2254                     ? (flags & DEGEN_2b)
2255                       ? 4
2256                       : 5
2257                     : 2
2258                   : 3
2259                 : 0;
2260         tangents[1] = tangents[i];
2261         textureTangents[1] = textureTangents[i];
2262     }
2263     if (flags & DEGEN_2a) {
2264         const std::size_t i =
2265                 (flags & DEGEN_2b)
2266                 ? (flags & DEGEN_1a)
2267                   ? (flags & DEGEN_1b)
2268                     ? (flags & DEGEN_0a)
2269                       ? 1
2270                       : 0
2271                     : 3
2272                   : 2
2273                 : 5;
2274         tangents[4] = tangents[i];
2275         textureTangents[4] = textureTangents[i];
2276     }
2277     if (flags & DEGEN_2b) {
2278         const std::size_t i =
2279                 (flags & DEGEN_2a)
2280                 ? (flags & DEGEN_1b)
2281                   ? (flags & DEGEN_1a)
2282                     ? (flags & DEGEN_0b)
2283                       ? 0
2284                       : 1
2285                     : 2
2286                   : 3
2287                 : 4;
2288         tangents[5] = tangents[i];
2289         textureTangents[5] = textureTangents[i];
2290     }
2291 }
2292
2293 void bestTangents00(unsigned int degenerateFlags, double dot, double length, std::size_t &index0, std::size_t &index1)
2294 {
2295     if (fabs(dot + length) < 0.001) { // opposing direction = degenerate
2296         if (!(degenerateFlags & DEGEN_1a)) { // if this tangent is degenerate we cannot use it
2297             index0 = 2;
2298             index1 = 0;
2299         } else if (!(degenerateFlags & DEGEN_0b)) {
2300             index0 = 0;
2301             index1 = 1;
2302         } else {
2303             index0 = 1;
2304             index1 = 0;
2305         }
2306     } else if (fabs(dot - length) < 0.001) { // same direction = degenerate
2307         if (degenerateFlags & DEGEN_0b) {
2308             index0 = 0;
2309             index1 = 1;
2310         } else {
2311             index0 = 1;
2312             index1 = 0;
2313         }
2314     }
2315 }
2316
2317 void bestTangents01(unsigned int degenerateFlags, double dot, double length, std::size_t &index0, std::size_t &index1)
2318 {
2319     if (fabs(dot - length) < 0.001) { // same direction = degenerate
2320         if (!(degenerateFlags & DEGEN_1a)) { // if this tangent is degenerate we cannot use it
2321             index0 = 2;
2322             index1 = 1;
2323         } else if (!(degenerateFlags & DEGEN_2b)) {
2324             index0 = 4;
2325             index1 = 0;
2326         } else {
2327             index0 = 5;
2328             index1 = 1;
2329         }
2330     } else if (fabs(dot + length) < 0.001) { // opposing direction = degenerate
2331         if (degenerateFlags & DEGEN_2b) {
2332             index0 = 4;
2333             index1 = 0;
2334         } else {
2335             index0 = 5;
2336             index1 = 1;
2337         }
2338     }
2339 }
2340
2341 void bestTangents10(unsigned int degenerateFlags, double dot, double length, std::size_t &index0, std::size_t &index1)
2342 {
2343     if (fabs(dot - length) < 0.001) { // same direction = degenerate
2344         if (!(degenerateFlags & DEGEN_1b)) { // if this tangent is degenerate we cannot use it
2345             index0 = 3;
2346             index1 = 4;
2347         } else if (!(degenerateFlags & DEGEN_0a)) {
2348             index0 = 1;
2349             index1 = 5;
2350         } else {
2351             index0 = 0;
2352             index1 = 4;
2353         }
2354     } else if (fabs(dot + length) < 0.001) { // opposing direction = degenerate
2355         if (degenerateFlags & DEGEN_0a) {
2356             index0 = 1;
2357             index1 = 5;
2358         } else {
2359             index0 = 0;
2360             index1 = 4;
2361         }
2362     }
2363 }
2364
2365 void bestTangents11(unsigned int degenerateFlags, double dot, double length, std::size_t &index0, std::size_t &index1)
2366 {
2367     if (fabs(dot + length) < 0.001) { // opposing direction = degenerate
2368         if (!(degenerateFlags & DEGEN_1b)) { // if this tangent is degenerate we cannot use it
2369             index0 = 3;
2370             index1 = 5;
2371         } else if (!(degenerateFlags & DEGEN_2a)) {
2372             index0 = 5;
2373             index1 = 4;
2374         } else {
2375             index0 = 4;
2376             index1 = 5;
2377         }
2378     } else if (fabs(dot - length) < 0.001) { // same direction = degenerate
2379         if (degenerateFlags & DEGEN_2a) {
2380             index0 = 5;
2381             index1 = 4;
2382         } else {
2383             index0 = 4;
2384             index1 = 5;
2385         }
2386     }
2387 }
2388
2389 void
2390 Patch::accumulateVertexTangentSpace(std::size_t index, Vector3 tangentX[6], Vector3 tangentY[6], Vector2 tangentS[6],
2391                                     Vector2 tangentT[6], std::size_t index0, std::size_t index1)
2392 {
2393     {
2394         Vector3 normal(vector3_cross(tangentX[index0], tangentY[index1]));
2395         if (!vector3_equal(normal, g_vector3_identity)) {
2396             vector3_add(normal_for_index(m_tess.m_vertices, index), vector3_normalised(normal));
2397         }
2398     }
2399
2400     {
2401         ArbitraryMeshVertex a, b, c;
2402         a.vertex = Vertex3f(0, 0, 0);
2403         a.texcoord = TexCoord2f(0, 0);
2404         b.vertex = vertex3f_for_vector3(tangentX[index0]);
2405         b.texcoord = texcoord2f_for_vector2(tangentS[index0]);
2406         c.vertex = vertex3f_for_vector3(tangentY[index1]);
2407         c.texcoord = texcoord2f_for_vector2(tangentT[index1]);
2408
2409         Vector3 s, t;
2410         ArbitraryMeshTriangle_calcTangents(a, b, c, s, t);
2411         if (!vector3_equal(s, g_vector3_identity)) {
2412             vector3_add(tangent_for_index(m_tess.m_vertices, index), vector3_normalised(s));
2413         }
2414         if (!vector3_equal(t, g_vector3_identity)) {
2415             vector3_add(bitangent_for_index(m_tess.m_vertices, index), vector3_normalised(t));
2416         }
2417     }
2418 }
2419
2420 const std::size_t PATCH_MAX_VERTEX_ARRAY = 1048576;
2421
2422 void Patch::BuildVertexArray()
2423 {
2424     const std::size_t strideU = 1;
2425     const std::size_t strideV = m_width;
2426
2427     const std::size_t numElems =
2428             m_tess.m_nArrayWidth * m_tess.m_nArrayHeight; // total number of elements in vertex array
2429
2430     const bool bWidthStrips = (m_tess.m_nArrayWidth >=
2431                                m_tess.m_nArrayHeight); // decide if horizontal strips are longer than vertical
2432
2433
2434     // allocate vertex, normal, texcoord and primitive-index arrays
2435     m_tess.m_vertices.resize(numElems);
2436     m_tess.m_indices.resize(m_tess.m_nArrayWidth * 2 * (m_tess.m_nArrayHeight - 1));
2437
2438     // set up strip indices
2439     if (bWidthStrips) {
2440         m_tess.m_numStrips = m_tess.m_nArrayHeight - 1;
2441         m_tess.m_lenStrips = m_tess.m_nArrayWidth * 2;
2442
2443         for (std::size_t i = 0; i < m_tess.m_nArrayWidth; i++) {
2444             for (std::size_t j = 0; j < m_tess.m_numStrips; j++) {
2445                 m_tess.m_indices[(j * m_tess.m_lenStrips) + i * 2] = RenderIndex(j * m_tess.m_nArrayWidth + i);
2446                 m_tess.m_indices[(j * m_tess.m_lenStrips) + i * 2 + 1] = RenderIndex(
2447                         (j + 1) * m_tess.m_nArrayWidth + i);
2448                 // reverse because radiant uses CULL_FRONT
2449                 //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2+1] = RenderIndex(j*m_tess.m_nArrayWidth+i);
2450                 //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2] = RenderIndex((j+1)*m_tess.m_nArrayWidth+i);
2451             }
2452         }
2453     } else {
2454         m_tess.m_numStrips = m_tess.m_nArrayWidth - 1;
2455         m_tess.m_lenStrips = m_tess.m_nArrayHeight * 2;
2456
2457         for (std::size_t i = 0; i < m_tess.m_nArrayHeight; i++) {
2458             for (std::size_t j = 0; j < m_tess.m_numStrips; j++) {
2459                 m_tess.m_indices[(j * m_tess.m_lenStrips) + i * 2] = RenderIndex(
2460                         ((m_tess.m_nArrayHeight - 1) - i) * m_tess.m_nArrayWidth + j);
2461                 m_tess.m_indices[(j * m_tess.m_lenStrips) + i * 2 + 1] = RenderIndex(
2462                         ((m_tess.m_nArrayHeight - 1) - i) * m_tess.m_nArrayWidth + j + 1);
2463                 // reverse because radiant uses CULL_FRONT
2464                 //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2+1] = RenderIndex(((m_tess.m_nArrayHeight-1)-i)*m_tess.m_nArrayWidth+j);
2465                 //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2] = RenderIndex(((m_tess.m_nArrayHeight-1)-i)*m_tess.m_nArrayWidth+j+1);
2466
2467             }
2468         }
2469     }
2470
2471     {
2472         PatchControlIter pCtrl = m_ctrlTransformed.data();
2473         for (std::size_t j = 0, offStartY = 0; j + 1 < m_height; j += 2, pCtrl += (strideU + strideV)) {
2474             // set up array offsets for this sub-patch
2475             const bool leafY = (m_patchDef3) ? false : BezierCurveTree_isLeaf(m_tess.m_curveTreeV[j >> 1]);
2476             const std::size_t offMidY = (m_patchDef3) ? 0 : m_tess.m_curveTreeV[j >> 1]->index;
2477             const std::size_t widthY = m_tess.m_arrayHeight[j >> 1] * m_tess.m_nArrayWidth;
2478             const std::size_t offEndY = offStartY + widthY;
2479
2480             for (std::size_t i = 0, offStartX = 0; i + 1 < m_width; i += 2, pCtrl += (strideU << 1)) {
2481                 const bool leafX = (m_patchDef3) ? false : BezierCurveTree_isLeaf(m_tess.m_curveTreeU[i >> 1]);
2482                 const std::size_t offMidX = (m_patchDef3) ? 0 : m_tess.m_curveTreeU[i >> 1]->index;
2483                 const std::size_t widthX = m_tess.m_arrayWidth[i >> 1];
2484                 const std::size_t offEndX = offStartX + widthX;
2485
2486                 PatchControl *subMatrix[3][3];
2487                 subMatrix[0][0] = pCtrl;
2488                 subMatrix[0][1] = subMatrix[0][0] + strideU;
2489                 subMatrix[0][2] = subMatrix[0][1] + strideU;
2490                 subMatrix[1][0] = subMatrix[0][0] + strideV;
2491                 subMatrix[1][1] = subMatrix[1][0] + strideU;
2492                 subMatrix[1][2] = subMatrix[1][1] + strideU;
2493                 subMatrix[2][0] = subMatrix[1][0] + strideV;
2494                 subMatrix[2][1] = subMatrix[2][0] + strideU;
2495                 subMatrix[2][2] = subMatrix[2][1] + strideU;
2496
2497                 // assign on-patch control points to vertex array
2498                 if (i == 0 && j == 0) {
2499                     vertex_clear_normal(m_tess.m_vertices[offStartX + offStartY]);
2500                 }
2501                 vertex_assign_ctrl(m_tess.m_vertices[offStartX + offStartY], *subMatrix[0][0]);
2502                 if (j == 0) {
2503                     vertex_clear_normal(m_tess.m_vertices[offEndX + offStartY]);
2504                 }
2505                 vertex_assign_ctrl(m_tess.m_vertices[offEndX + offStartY], *subMatrix[0][2]);
2506                 if (i == 0) {
2507                     vertex_clear_normal(m_tess.m_vertices[offStartX + offEndY]);
2508                 }
2509                 vertex_assign_ctrl(m_tess.m_vertices[offStartX + offEndY], *subMatrix[2][0]);
2510
2511                 vertex_clear_normal(m_tess.m_vertices[offEndX + offEndY]);
2512                 vertex_assign_ctrl(m_tess.m_vertices[offEndX + offEndY], *subMatrix[2][2]);
2513
2514                 if (!m_patchDef3) {
2515                     // assign remaining control points to vertex array
2516                     if (!leafX) {
2517                         vertex_assign_ctrl(m_tess.m_vertices[offMidX + offStartY], *subMatrix[0][1]);
2518                         vertex_assign_ctrl(m_tess.m_vertices[offMidX + offEndY], *subMatrix[2][1]);
2519                     }
2520                     if (!leafY) {
2521                         vertex_assign_ctrl(m_tess.m_vertices[offStartX + offMidY], *subMatrix[1][0]);
2522                         vertex_assign_ctrl(m_tess.m_vertices[offEndX + offMidY], *subMatrix[1][2]);
2523
2524                         if (!leafX) {
2525                             vertex_assign_ctrl(m_tess.m_vertices[offMidX + offMidY], *subMatrix[1][1]);
2526                         }
2527                     }
2528                 }
2529
2530                 // test all 12 edges for degeneracy
2531                 unsigned int nFlagsX = subarray_get_degen(pCtrl, strideU, strideV);
2532                 unsigned int nFlagsY = subarray_get_degen(pCtrl, strideV, strideU);
2533                 Vector3 tangentX[6], tangentY[6];
2534                 Vector2 tangentS[6], tangentT[6];
2535
2536                 // set up tangents for each of the 12 edges if they were not degenerate
2537                 if (!(nFlagsX & DEGEN_0a)) {
2538                     tangentX[0] = vector3_subtracted(subMatrix[0][1]->m_vertex, subMatrix[0][0]->m_vertex);
2539                     tangentS[0] = vector2_subtracted(subMatrix[0][1]->m_texcoord, subMatrix[0][0]->m_texcoord);
2540                 }
2541                 if (!(nFlagsX & DEGEN_0b)) {
2542                     tangentX[1] = vector3_subtracted(subMatrix[0][2]->m_vertex, subMatrix[0][1]->m_vertex);
2543                     tangentS[1] = vector2_subtracted(subMatrix[0][2]->m_texcoord, subMatrix[0][1]->m_texcoord);
2544                 }
2545                 if (!(nFlagsX & DEGEN_1a)) {
2546                     tangentX[2] = vector3_subtracted(subMatrix[1][1]->m_vertex, subMatrix[1][0]->m_vertex);
2547                     tangentS[2] = vector2_subtracted(subMatrix[1][1]->m_texcoord, subMatrix[1][0]->m_texcoord);
2548                 }
2549                 if (!(nFlagsX & DEGEN_1b)) {
2550                     tangentX[3] = vector3_subtracted(subMatrix[1][2]->m_vertex, subMatrix[1][1]->m_vertex);
2551                     tangentS[3] = vector2_subtracted(subMatrix[1][2]->m_texcoord, subMatrix[1][1]->m_texcoord);
2552                 }
2553                 if (!(nFlagsX & DEGEN_2a)) {
2554                     tangentX[4] = vector3_subtracted(subMatrix[2][1]->m_vertex, subMatrix[2][0]->m_vertex);
2555                     tangentS[4] = vector2_subtracted(subMatrix[2][1]->m_texcoord, subMatrix[2][0]->m_texcoord);
2556                 }
2557                 if (!(nFlagsX & DEGEN_2b)) {
2558                     tangentX[5] = vector3_subtracted(subMatrix[2][2]->m_vertex, subMatrix[2][1]->m_vertex);
2559                     tangentS[5] = vector2_subtracted(subMatrix[2][2]->m_texcoord, subMatrix[2][1]->m_texcoord);
2560                 }
2561
2562                 if (!(nFlagsY & DEGEN_0a)) {
2563                     tangentY[0] = vector3_subtracted(subMatrix[1][0]->m_vertex, subMatrix[0][0]->m_vertex);
2564                     tangentT[0] = vector2_subtracted(subMatrix[1][0]->m_texcoord, subMatrix[0][0]->m_texcoord);
2565                 }
2566                 if (!(nFlagsY & DEGEN_0b)) {
2567                     tangentY[1] = vector3_subtracted(subMatrix[2][0]->m_vertex, subMatrix[1][0]->m_vertex);
2568                     tangentT[1] = vector2_subtracted(subMatrix[2][0]->m_texcoord, subMatrix[1][0]->m_texcoord);
2569                 }
2570                 if (!(nFlagsY & DEGEN_1a)) {
2571                     tangentY[2] = vector3_subtracted(subMatrix[1][1]->m_vertex, subMatrix[0][1]->m_vertex);
2572                     tangentT[2] = vector2_subtracted(subMatrix[1][1]->m_texcoord, subMatrix[0][1]->m_texcoord);
2573                 }
2574                 if (!(nFlagsY & DEGEN_1b)) {
2575                     tangentY[3] = vector3_subtracted(subMatrix[2][1]->m_vertex, subMatrix[1][1]->m_vertex);
2576                     tangentT[3] = vector2_subtracted(subMatrix[2][1]->m_texcoord, subMatrix[1][1]->m_texcoord);
2577                 }
2578                 if (!(nFlagsY & DEGEN_2a)) {
2579                     tangentY[4] = vector3_subtracted(subMatrix[1][2]->m_vertex, subMatrix[0][2]->m_vertex);
2580                     tangentT[4] = vector2_subtracted(subMatrix[1][2]->m_texcoord, subMatrix[0][2]->m_texcoord);
2581                 }
2582                 if (!(nFlagsY & DEGEN_2b)) {
2583                     tangentY[5] = vector3_subtracted(subMatrix[2][2]->m_vertex, subMatrix[1][2]->m_vertex);
2584                     tangentT[5] = vector2_subtracted(subMatrix[2][2]->m_texcoord, subMatrix[1][2]->m_texcoord);
2585                 }
2586
2587                 // set up remaining edge tangents by borrowing the tangent from the closest parallel non-degenerate edge
2588                 tangents_remove_degenerate(tangentX, tangentS, nFlagsX);
2589                 tangents_remove_degenerate(tangentY, tangentT, nFlagsY);
2590
2591                 {
2592                     // x=0, y=0
2593                     std::size_t index = offStartX + offStartY;
2594                     std::size_t index0 = 0;
2595                     std::size_t index1 = 0;
2596
2597                     double dot = vector3_dot(tangentX[index0], tangentY[index1]);
2598                     double length = vector3_length(tangentX[index0]) * vector3_length(tangentY[index1]);
2599
2600                     bestTangents00(nFlagsX, dot, length, index0, index1);
2601
2602                     accumulateVertexTangentSpace(index, tangentX, tangentY, tangentS, tangentT, index0, index1);
2603                 }
2604
2605                 {
2606                     // x=1, y=0
2607                     std::size_t index = offEndX + offStartY;
2608                     std::size_t index0 = 1;
2609                     std::size_t index1 = 4;
2610
2611                     double dot = vector3_dot(tangentX[index0], tangentY[index1]);
2612                     double length = vector3_length(tangentX[index0]) * vector3_length(tangentY[index1]);
2613
2614                     bestTangents10(nFlagsX, dot, length, index0, index1);
2615
2616                     accumulateVertexTangentSpace(index, tangentX, tangentY, tangentS, tangentT, index0, index1);
2617                 }
2618
2619                 {
2620                     // x=0, y=1
2621                     std::size_t index = offStartX + offEndY;
2622                     std::size_t index0 = 4;
2623                     std::size_t index1 = 1;
2624
2625                     double dot = vector3_dot(tangentX[index0], tangentY[index1]);
2626                     double length = vector3_length(tangentX[index1]) * vector3_length(tangentY[index1]);
2627
2628                     bestTangents01(nFlagsX, dot, length, index0, index1);
2629
2630                     accumulateVertexTangentSpace(index, tangentX, tangentY, tangentS, tangentT, index0, index1);
2631                 }
2632
2633                 {
2634                     // x=1, y=1
2635                     std::size_t index = offEndX + offEndY;
2636                     std::size_t index0 = 5;
2637                     std::size_t index1 = 5;
2638
2639                     double dot = vector3_dot(tangentX[index0], tangentY[index1]);
2640                     double length = vector3_length(tangentX[index0]) * vector3_length(tangentY[index1]);
2641
2642                     bestTangents11(nFlagsX, dot, length, index0, index1);
2643
2644                     accumulateVertexTangentSpace(index, tangentX, tangentY, tangentS, tangentT, index0, index1);
2645                 }
2646
2647                 //normalise normals that won't be accumulated again
2648                 if (i != 0 || j != 0) {
2649                     normalise_safe(normal_for_index(m_tess.m_vertices, offStartX + offStartY));
2650                     normalise_safe(tangent_for_index(m_tess.m_vertices, offStartX + offStartY));
2651                     normalise_safe(bitangent_for_index(m_tess.m_vertices, offStartX + offStartY));
2652                 }
2653                 if (i + 3 == m_width) {
2654                     normalise_safe(normal_for_index(m_tess.m_vertices, offEndX + offStartY));
2655                     normalise_safe(tangent_for_index(m_tess.m_vertices, offEndX + offStartY));
2656                     normalise_safe(bitangent_for_index(m_tess.m_vertices, offEndX + offStartY));
2657                 }
2658                 if (j + 3 == m_height) {
2659                     normalise_safe(normal_for_index(m_tess.m_vertices, offStartX + offEndY));
2660                     normalise_safe(tangent_for_index(m_tess.m_vertices, offStartX + offEndY));
2661                     normalise_safe(bitangent_for_index(m_tess.m_vertices, offStartX + offEndY));
2662                 }
2663                 if (i + 3 == m_width && j + 3 == m_height) {
2664                     normalise_safe(normal_for_index(m_tess.m_vertices, offEndX + offEndY));
2665                     normalise_safe(tangent_for_index(m_tess.m_vertices, offEndX + offEndY));
2666                     normalise_safe(bitangent_for_index(m_tess.m_vertices, offEndX + offEndY));
2667                 }
2668
2669                 // set flags to average normals between shared edges
2670                 if (j != 0) {
2671                     nFlagsX |= AVERAGE;
2672                 }
2673                 if (i != 0) {
2674                     nFlagsY |= AVERAGE;
2675                 }
2676                 // set flags to save evaluating shared edges twice
2677                 nFlagsX |= SPLIT;
2678                 nFlagsY |= SPLIT;
2679
2680                 // if the patch is curved.. tesselate recursively
2681                 // use the relevant control curves for this sub-patch
2682                 if (m_patchDef3) {
2683                     TesselateSubMatrixFixed(m_tess.m_vertices.data() + offStartX + offStartY, 1, m_tess.m_nArrayWidth,
2684                                             nFlagsX, nFlagsY, subMatrix);
2685                 } else {
2686                     if (!leafX) {
2687                         TesselateSubMatrix(m_tess.m_curveTreeU[i >> 1], m_tess.m_curveTreeV[j >> 1],
2688                                            offStartX, offStartY, offEndX, offEndY, // array offsets
2689                                            nFlagsX, nFlagsY,
2690                                            subMatrix[1][0]->m_vertex, subMatrix[1][1]->m_vertex,
2691                                            subMatrix[1][2]->m_vertex,
2692                                            subMatrix[1][0]->m_texcoord, subMatrix[1][1]->m_texcoord,
2693                                            subMatrix[1][2]->m_texcoord,
2694                                            false);
2695                     } else if (!leafY) {
2696                         TesselateSubMatrix(m_tess.m_curveTreeV[j >> 1], m_tess.m_curveTreeU[i >> 1],
2697                                            offStartY, offStartX, offEndY, offEndX, // array offsets
2698                                            nFlagsY, nFlagsX,
2699                                            subMatrix[0][1]->m_vertex, subMatrix[1][1]->m_vertex,
2700                                            subMatrix[2][1]->m_vertex,
2701                                            subMatrix[0][1]->m_texcoord, subMatrix[1][1]->m_texcoord,
2702                                            subMatrix[2][1]->m_texcoord,
2703                                            true);
2704                     }
2705                 }
2706
2707                 offStartX = offEndX;
2708             }
2709             offStartY = offEndY;
2710         }
2711     }
2712 }
2713
2714
2715 class PatchFilterWrapper : public Filter {
2716     bool m_active;
2717     bool m_invert;
2718     PatchFilter &m_filter;
2719 public:
2720     PatchFilterWrapper(PatchFilter &filter, bool invert) : m_invert(invert), m_filter(filter)
2721     {
2722     }
2723
2724     void setActive(bool active)
2725     {
2726         m_active = active;
2727     }
2728
2729     bool active()
2730     {
2731         return m_active;
2732     }
2733
2734     bool filter(const Patch &patch)
2735     {
2736         return m_invert ^ m_filter.filter(patch);
2737     }
2738 };
2739
2740
2741 typedef std::list<PatchFilterWrapper> PatchFilters;
2742 PatchFilters g_patchFilters;
2743
2744 void add_patch_filter(PatchFilter &filter, int mask, bool invert)
2745 {
2746     g_patchFilters.push_back(PatchFilterWrapper(filter, invert));
2747     GlobalFilterSystem().addFilter(g_patchFilters.back(), mask);
2748 }
2749
2750 bool patch_filtered(Patch &patch)
2751 {
2752     for (PatchFilters::iterator i = g_patchFilters.begin(); i != g_patchFilters.end(); ++i) {
2753         if ((*i).active() && (*i).filter(patch)) {
2754             return true;
2755         }
2756     }
2757     return false;
2758 }