radiant/patch.cpp

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