radiant/patch.cpp

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