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