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