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[2][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     default:
1352       ERROR_MESSAGE("this should be unreachable");
1353       return;
1354     }
1355   }
1356   else if  (eType == eBevel)
1357   {
1358     unsigned char *pIndex;
1359     unsigned char pBevIndex[] =
1360     {
1361       0, 0,
1362       2, 0,
1363       2, 2,
1364     };
1365
1366     setDims(3, 3);
1367
1368     PatchControl* pCtrl = m_ctrl.data();
1369     for(std::size_t h=0; h<3; h++)
1370     {
1371       pIndex=pBevIndex;
1372       for(std::size_t w=0; w<3; w++, pIndex+=2, pCtrl++)
1373       {
1374         pCtrl->m_vertex[0] = vPos[pIndex[0]][0];
1375         pCtrl->m_vertex[1] = vPos[pIndex[1]][1];
1376         pCtrl->m_vertex[2] = vPos[h][2];
1377       }
1378     }
1379   }
1380   else if(eType == eEndCap)
1381   {
1382     unsigned char *pIndex;
1383     unsigned char pEndIndex[] =
1384     {
1385       2, 0,
1386       2, 2,
1387       1, 2,
1388       0, 2,
1389       0, 0,
1390     };
1391
1392     setDims(5, 3);
1393
1394     PatchControl* pCtrl = m_ctrl.data();
1395     for(std::size_t h=0; h<3; h++)
1396     {
1397       pIndex=pEndIndex;
1398       for(std::size_t w=0; w<5; w++, pIndex+=2, pCtrl++)
1399       {
1400         pCtrl->m_vertex[0] = vPos[pIndex[0]][0];
1401         pCtrl->m_vertex[1] = vPos[pIndex[1]][1];
1402         pCtrl->m_vertex[2] = vPos[h][2];
1403       }
1404     }
1405   }
1406
1407   if(eType == eDenseCylinder)
1408   {
1409     InsertRemove(true, false, true);
1410   }
1411
1412   if(eType == eVeryDenseCylinder)
1413   {
1414     InsertRemove(true, false, false);
1415     InsertRemove(true, false, true);
1416   }
1417
1418   NaturalTexture();
1419 }
1420
1421 void Patch::RenderDebug(RenderStateFlags state) const
1422 {
1423   for (std::size_t i = 0; i<m_tess.m_numStrips; i++)
1424   {
1425     glBegin(GL_QUAD_STRIP);
1426     for (std::size_t j = 0; j<m_tess.m_lenStrips; j++)
1427     {
1428       glNormal3fv(normal3f_to_array((m_tess.m_vertices.data() + m_tess.m_indices[i*m_tess.m_lenStrips+j])->normal));
1429       glTexCoord2fv(texcoord2f_to_array((m_tess.m_vertices.data() + m_tess.m_indices[i*m_tess.m_lenStrips+j])->texcoord));
1430       glVertex3fv(vertex3f_to_array((m_tess.m_vertices.data() + m_tess.m_indices[i*m_tess.m_lenStrips+j])->vertex));
1431     }
1432     glEnd();
1433   }
1434 }
1435
1436 void RenderablePatchSolid::RenderNormals() const
1437 {
1438   const std::size_t width = m_tess.m_numStrips+1;
1439   const std::size_t height = m_tess.m_lenStrips>>1;
1440   glBegin(GL_LINES);
1441   for(std::size_t i=0;i<width;i++)
1442   {
1443     for(std::size_t j=0;j<height;j++)
1444     {
1445       {
1446         Vector3 vNormal(
1447           vector3_added(
1448             vertex3f_to_vector3((m_tess.m_vertices.data() + (j*width+i))->vertex),
1449             vector3_scaled(normal3f_to_vector3((m_tess.m_vertices.data() + (j*width+i))->normal), 8)
1450           )
1451         );
1452         glVertex3fv(vertex3f_to_array((m_tess.m_vertices.data() + (j*width+i))->vertex));
1453         glVertex3fv(&vNormal[0]);
1454       }
1455       {
1456         Vector3 vNormal(
1457           vector3_added(
1458             vertex3f_to_vector3((m_tess.m_vertices.data() + (j*width+i))->vertex),
1459             vector3_scaled(normal3f_to_vector3((m_tess.m_vertices.data() + (j*width+i))->tangent), 8)
1460           )
1461         );
1462         glVertex3fv(vertex3f_to_array((m_tess.m_vertices.data() + (j*width+i))->vertex));
1463         glVertex3fv(&vNormal[0]);
1464       }
1465       {
1466         Vector3 vNormal(
1467           vector3_added(
1468             vertex3f_to_vector3((m_tess.m_vertices.data() + (j*width+i))->vertex),
1469             vector3_scaled(normal3f_to_vector3((m_tess.m_vertices.data() + (j*width+i))->bitangent), 8)
1470           )
1471         );
1472         glVertex3fv(vertex3f_to_array((m_tess.m_vertices.data() + (j*width+i))->vertex));
1473         glVertex3fv(&vNormal[0]);
1474       }
1475     }
1476   }
1477   glEnd();
1478 }
1479
1480 #define DEGEN_0a  0x01
1481 #define DEGEN_1a  0x02
1482 #define DEGEN_2a  0x04
1483 #define DEGEN_0b  0x08
1484 #define DEGEN_1b  0x10
1485 #define DEGEN_2b  0x20
1486 #define SPLIT     0x40
1487 #define AVERAGE   0x80
1488
1489
1490 unsigned int subarray_get_degen(PatchControlIter subarray, std::size_t strideU, std::size_t strideV)
1491 {
1492   unsigned int nDegen = 0;
1493   const PatchControl* p1;
1494   const PatchControl* p2;
1495
1496   p1 = subarray;
1497   p2 = p1 + strideU;
1498   if(vector3_equal(p1->m_vertex, p2->m_vertex))
1499     nDegen |= DEGEN_0a;
1500   p1 = p2;
1501   p2 = p1 + strideU;
1502   if(vector3_equal(p1->m_vertex, p2->m_vertex))
1503     nDegen |= DEGEN_0b;
1504
1505   p1 = subarray + strideV;
1506   p2 = p1 + strideU;
1507   if(vector3_equal(p1->m_vertex, p2->m_vertex))
1508     nDegen |= DEGEN_1a;
1509   p1 = p2;
1510   p2 = p1 + strideU;
1511   if(vector3_equal(p1->m_vertex, p2->m_vertex))
1512     nDegen |= DEGEN_1b;
1513
1514   p1 = subarray + (strideV << 1);
1515   p2 = p1 + strideU;
1516   if(vector3_equal(p1->m_vertex, p2->m_vertex))
1517     nDegen |= DEGEN_2a;
1518   p1 = p2;
1519   p2 = p1 + strideU;
1520   if(vector3_equal(p1->m_vertex, p2->m_vertex))
1521     nDegen |= DEGEN_2b;
1522
1523   return nDegen;
1524 }
1525
1526
1527 inline void deCasteljau3(const Vector3& P0, const Vector3& P1, const Vector3& P2, Vector3& P01, Vector3& P12, Vector3& P012)
1528 {
1529   P01 = vector3_mid(P0, P1);
1530   P12 = vector3_mid(P1, P2);
1531   P012 = vector3_mid(P01, P12);
1532 }
1533
1534 inline void BezierInterpolate3( const Vector3& start, Vector3& left, Vector3& mid, Vector3& right, const Vector3& end )
1535 {
1536   left = vector3_mid(start, mid);
1537   right = vector3_mid(mid, end);
1538   mid = vector3_mid(left, right);
1539 }
1540
1541 inline void BezierInterpolate2( const Vector2& start, Vector2& left, Vector2& mid, Vector2& right, const Vector2& end )
1542 {
1543   left[0]= float_mid(start[0], mid[0]);
1544   left[1] = float_mid(start[1], mid[1]);
1545   right[0] = float_mid(mid[0], end[0]);
1546   right[1] = float_mid(mid[1], end[1]);
1547   mid[0] = float_mid(left[0], right[0]);
1548   mid[1] = float_mid(left[1], right[1]);
1549 }
1550
1551
1552 inline Vector2& texcoord_for_index(Array<ArbitraryMeshVertex>& vertices, std::size_t index)
1553 {
1554   return reinterpret_cast<Vector2&>(vertices[index].texcoord);
1555 }
1556
1557 inline Vector3& vertex_for_index(Array<ArbitraryMeshVertex>& vertices, std::size_t index)
1558 {
1559   return reinterpret_cast<Vector3&>(vertices[index].vertex);
1560 }
1561
1562 inline Vector3& normal_for_index(Array<ArbitraryMeshVertex>& vertices, std::size_t index)
1563 {
1564   return reinterpret_cast<Vector3&>(vertices[index].normal);
1565 }
1566
1567 inline Vector3& tangent_for_index(Array<ArbitraryMeshVertex>& vertices, std::size_t index)
1568 {
1569   return reinterpret_cast<Vector3&>(vertices[index].tangent);
1570 }
1571
1572 inline Vector3& bitangent_for_index(Array<ArbitraryMeshVertex>& vertices, std::size_t index)
1573 {
1574   return reinterpret_cast<Vector3&>(vertices[index].bitangent);
1575 }
1576
1577 inline const Vector2& texcoord_for_index(const Array<ArbitraryMeshVertex>& vertices, std::size_t index)
1578 {
1579   return reinterpret_cast<const Vector2&>(vertices[index].texcoord);
1580 }
1581
1582 inline const Vector3& vertex_for_index(const Array<ArbitraryMeshVertex>& vertices, std::size_t index)
1583 {
1584   return reinterpret_cast<const Vector3&>(vertices[index].vertex);
1585 }
1586
1587 inline const Vector3& normal_for_index(const Array<ArbitraryMeshVertex>& vertices, std::size_t index)
1588 {
1589   return reinterpret_cast<const Vector3&>(vertices[index].normal);
1590 }
1591
1592 inline const Vector3& tangent_for_index(const Array<ArbitraryMeshVertex>& vertices, std::size_t index)
1593 {
1594   return reinterpret_cast<const Vector3&>(vertices[index].tangent);
1595 }
1596
1597 inline const Vector3& bitangent_for_index(const Array<ArbitraryMeshVertex>& vertices, std::size_t index)
1598 {
1599   return reinterpret_cast<const Vector3&>(vertices[index].bitangent);
1600 }
1601
1602 #include "math/curve.h"
1603
1604 inline PatchControl QuadraticBezier_evaluate(const PatchControl* firstPoint, double t)
1605 {
1606   PatchControl result = { Vector3(0, 0, 0), Vector2(0, 0) };
1607   double denominator = 0;
1608
1609   {
1610     double weight = BernsteinPolynomial<Zero, Two>::apply(t);
1611     vector3_add(result.m_vertex, vector3_scaled(firstPoint[0].m_vertex, weight));
1612     vector2_add(result.m_texcoord, vector2_scaled(firstPoint[0].m_texcoord, weight));
1613     denominator += weight;
1614   }
1615   {
1616     double weight = BernsteinPolynomial<One, Two>::apply(t);
1617     vector3_add(result.m_vertex, vector3_scaled(firstPoint[1].m_vertex, weight));
1618     vector2_add(result.m_texcoord, vector2_scaled(firstPoint[1].m_texcoord, weight));
1619     denominator += weight;
1620   }
1621   {
1622     double weight = BernsteinPolynomial<Two, Two>::apply(t);
1623     vector3_add(result.m_vertex, vector3_scaled(firstPoint[2].m_vertex, weight));
1624     vector2_add(result.m_texcoord, vector2_scaled(firstPoint[2].m_texcoord, weight));
1625     denominator += weight;
1626   }
1627
1628   vector3_divide(result.m_vertex, denominator);
1629   vector2_divide(result.m_texcoord, denominator);
1630   return result;
1631 }
1632
1633 inline Vector3 vector3_linear_interpolated(const Vector3& a, const Vector3& b, double t)
1634 {
1635   return vector3_added(vector3_scaled(a, 1.0 - t), vector3_scaled(b, t));
1636 }
1637
1638 inline Vector2 vector2_linear_interpolated(const Vector2& a, const Vector2& b, double t)
1639 {
1640   return vector2_added(vector2_scaled(a, 1.0 - t), vector2_scaled(b, t));
1641 }
1642
1643 void normalise_safe(Vector3& normal)
1644 {
1645   if(!vector3_equal(normal, g_vector3_identity))
1646   {
1647     vector3_normalise(normal);
1648   }
1649 }
1650
1651 inline void QuadraticBezier_evaluate(const PatchControl& a, const PatchControl& b, const PatchControl& c, double t, PatchControl& point, PatchControl& left, PatchControl& right)
1652 {
1653   left.m_vertex = vector3_linear_interpolated(a.m_vertex, b.m_vertex, t);
1654   left.m_texcoord = vector2_linear_interpolated(a.m_texcoord, b.m_texcoord, t);
1655   right.m_vertex = vector3_linear_interpolated(b.m_vertex, c.m_vertex, t);
1656   right.m_texcoord = vector2_linear_interpolated(b.m_texcoord, c.m_texcoord, t);
1657   point.m_vertex = vector3_linear_interpolated(left.m_vertex, right.m_vertex, t);
1658   point.m_texcoord = vector2_linear_interpolated(left.m_texcoord, right.m_texcoord, t);
1659 }
1660
1661 void Patch::TesselateSubMatrixFixed(ArbitraryMeshVertex* vertices, std::size_t strideX, std::size_t strideY, unsigned int nFlagsX, unsigned int nFlagsY, PatchControl* subMatrix[3][3])
1662 {
1663   double incrementU = 1.0 / m_subdivisions_x;
1664   double incrementV = 1.0 / m_subdivisions_y;
1665   const std::size_t width = m_subdivisions_x + 1;
1666   const std::size_t height = m_subdivisions_y + 1;
1667
1668   for(std::size_t i = 0; i != width; ++i)
1669   {
1670     double tU = (i + 1 == width) ? 1 : i * incrementU;
1671     PatchControl pointX[3];
1672     PatchControl leftX[3];
1673     PatchControl rightX[3];
1674     QuadraticBezier_evaluate(*subMatrix[0][0], *subMatrix[0][1], *subMatrix[0][2], tU, pointX[0], leftX[0], rightX[0]);
1675     QuadraticBezier_evaluate(*subMatrix[1][0], *subMatrix[1][1], *subMatrix[1][2], tU, pointX[1], leftX[1], rightX[1]);
1676     QuadraticBezier_evaluate(*subMatrix[2][0], *subMatrix[2][1], *subMatrix[2][2], tU, pointX[2], leftX[2], rightX[2]);
1677
1678     ArbitraryMeshVertex* p = vertices + i * strideX;
1679     for(std::size_t j = 0; j != height; ++j)
1680     {
1681       if((j == 0 || j + 1 == height) && (i == 0 || i + 1 == width))
1682       {
1683       }
1684       else
1685       {
1686         double tV = (j + 1 == height) ? 1 : j * incrementV;
1687
1688         PatchControl pointY[3];
1689         PatchControl leftY[3];
1690         PatchControl rightY[3];
1691         QuadraticBezier_evaluate(*subMatrix[0][0], *subMatrix[1][0], *subMatrix[2][0], tV, pointY[0], leftY[0], rightY[0]);
1692         QuadraticBezier_evaluate(*subMatrix[0][1], *subMatrix[1][1], *subMatrix[2][1], tV, pointY[1], leftY[1], rightY[1]);
1693         QuadraticBezier_evaluate(*subMatrix[0][2], *subMatrix[1][2], *subMatrix[2][2], tV, pointY[2], leftY[2], rightY[2]);
1694
1695         PatchControl point;
1696         PatchControl left;
1697         PatchControl right;
1698         QuadraticBezier_evaluate(pointX[0], pointX[1], pointX[2], tV, point, left, right);
1699         PatchControl up;
1700         PatchControl down;
1701         QuadraticBezier_evaluate(pointY[0], pointY[1], pointY[2], tU, point, up, down);
1702
1703         vertex3f_to_vector3(p->vertex) = point.m_vertex;
1704         texcoord2f_to_vector2(p->texcoord) = point.m_texcoord;
1705
1706         ArbitraryMeshVertex a, b, c;
1707
1708         a.vertex = vertex3f_for_vector3(left.m_vertex);
1709         a.texcoord = texcoord2f_for_vector2(left.m_texcoord);
1710         b.vertex = vertex3f_for_vector3(right.m_vertex);
1711         b.texcoord = texcoord2f_for_vector2(right.m_texcoord);
1712
1713         if(i != 0)
1714         {
1715           c.vertex = vertex3f_for_vector3(up.m_vertex);
1716           c.texcoord = texcoord2f_for_vector2(up.m_texcoord);
1717         }
1718         else
1719         {
1720           c.vertex = vertex3f_for_vector3(down.m_vertex);
1721           c.texcoord = texcoord2f_for_vector2(down.m_texcoord);
1722         }
1723
1724         Vector3 normal = vector3_normalised(vector3_cross(right.m_vertex - left.m_vertex, up.m_vertex - down.m_vertex));
1725
1726         Vector3 tangent, bitangent;
1727         ArbitraryMeshTriangle_calcTangents(a, b, c, tangent, bitangent);
1728         vector3_normalise(tangent);
1729         vector3_normalise(bitangent);
1730
1731         if(((nFlagsX & AVERAGE) != 0 && i == 0) || ((nFlagsY & AVERAGE) != 0  && j == 0))
1732         {
1733           normal3f_to_vector3(p->normal) = vector3_normalised(vector3_added(normal3f_to_vector3(p->normal), normal));
1734           normal3f_to_vector3(p->tangent) = vector3_normalised(vector3_added(normal3f_to_vector3(p->tangent), tangent));
1735           normal3f_to_vector3(p->bitangent) = vector3_normalised(vector3_added(normal3f_to_vector3(p->bitangent), bitangent));
1736         }
1737         else
1738         {
1739           normal3f_to_vector3(p->normal) = normal;
1740           normal3f_to_vector3(p->tangent) = tangent;
1741           normal3f_to_vector3(p->bitangent) = bitangent;
1742         }
1743       }
1744
1745       p += strideY;
1746     }
1747   }
1748 }
1749
1750 void Patch::TesselateSubMatrix( const BezierCurveTree *BX, const BezierCurveTree *BY,
1751                                         std::size_t offStartX, std::size_t offStartY,
1752                                         std::size_t offEndX, std::size_t offEndY,
1753                                         std::size_t nFlagsX, std::size_t nFlagsY,
1754                                         Vector3& left, Vector3& mid, Vector3& right,
1755                                         Vector2& texLeft, Vector2& texMid, Vector2& texRight,
1756                                         bool bTranspose )
1757 {
1758   int newFlagsX, newFlagsY;
1759
1760   Vector3 tmp;
1761   Vector3 vertex_0_0, vertex_0_1, vertex_1_0, vertex_1_1, vertex_2_0, vertex_2_1;
1762   Vector2 texTmp;
1763   Vector2 texcoord_0_0, texcoord_0_1, texcoord_1_0, texcoord_1_1, texcoord_2_0, texcoord_2_1;
1764
1765   {
1766    // texcoords
1767
1768     BezierInterpolate2( texcoord_for_index(m_tess.m_vertices, offStartX + offStartY),
1769                      texcoord_0_0,
1770                      texcoord_for_index(m_tess.m_vertices, BX->index + offStartY),
1771                      texcoord_0_1,
1772                      texcoord_for_index(m_tess.m_vertices, offEndX + offStartY) );
1773
1774
1775     BezierInterpolate2( texcoord_for_index(m_tess.m_vertices, offStartX + offEndY),
1776                      texcoord_2_0,
1777                      texcoord_for_index(m_tess.m_vertices, BX->index + offEndY),
1778                      texcoord_2_1,
1779                      texcoord_for_index(m_tess.m_vertices, offEndX + offEndY) );
1780
1781     texTmp = texMid;
1782
1783     BezierInterpolate2(texLeft,
1784                       texcoord_1_0,
1785                       texTmp,
1786                       texcoord_1_1,
1787                       texRight);
1788
1789     if(!BezierCurveTree_isLeaf(BY))
1790     {
1791       texcoord_for_index(m_tess.m_vertices, BX->index + BY->index) = texTmp;
1792     }
1793
1794
1795     if(!BezierCurveTree_isLeaf(BX->left))
1796     {
1797       texcoord_for_index(m_tess.m_vertices, BX->left->index + offStartY) = texcoord_0_0;
1798       texcoord_for_index(m_tess.m_vertices, BX->left->index + offEndY) = texcoord_2_0;
1799
1800       if(!BezierCurveTree_isLeaf(BY))
1801       {
1802         texcoord_for_index(m_tess.m_vertices, BX->left->index + BY->index) = texcoord_1_0;
1803       }
1804     }
1805     if(!BezierCurveTree_isLeaf(BX->right))
1806     {
1807       texcoord_for_index(m_tess.m_vertices, BX->right->index + offStartY) = texcoord_0_1;
1808       texcoord_for_index(m_tess.m_vertices, BX->right->index + offEndY) = texcoord_2_1;
1809
1810       if(!BezierCurveTree_isLeaf(BY))
1811       {
1812         texcoord_for_index(m_tess.m_vertices, BX->right->index + BY->index) = texcoord_1_1;
1813       }
1814     }
1815
1816
1817     // verts
1818
1819     BezierInterpolate3( vertex_for_index(m_tess.m_vertices, offStartX + offStartY),
1820                      vertex_0_0,
1821                      vertex_for_index(m_tess.m_vertices, BX->index + offStartY),
1822                      vertex_0_1,
1823                      vertex_for_index(m_tess.m_vertices, offEndX + offStartY) );
1824
1825
1826     BezierInterpolate3( vertex_for_index(m_tess.m_vertices, offStartX + offEndY),
1827                      vertex_2_0,
1828                      vertex_for_index(m_tess.m_vertices, BX->index + offEndY),
1829                      vertex_2_1,
1830                      vertex_for_index(m_tess.m_vertices, offEndX + offEndY) );
1831
1832
1833     tmp = mid;
1834
1835     BezierInterpolate3( left,
1836                      vertex_1_0,
1837                      tmp,
1838                      vertex_1_1,
1839                      right );
1840
1841     if(!BezierCurveTree_isLeaf(BY))
1842     {
1843       vertex_for_index(m_tess.m_vertices, BX->index + BY->index) = tmp;
1844     }
1845
1846
1847     if(!BezierCurveTree_isLeaf(BX->left))
1848     {
1849       vertex_for_index(m_tess.m_vertices, BX->left->index + offStartY) = vertex_0_0;
1850       vertex_for_index(m_tess.m_vertices, BX->left->index + offEndY) = vertex_2_0;
1851
1852       if(!BezierCurveTree_isLeaf(BY))
1853       {
1854         vertex_for_index(m_tess.m_vertices, BX->left->index + BY->index) = vertex_1_0;
1855       }
1856     }
1857     if(!BezierCurveTree_isLeaf(BX->right))
1858     {
1859       vertex_for_index(m_tess.m_vertices, BX->right->index + offStartY) = vertex_0_1;
1860       vertex_for_index(m_tess.m_vertices, BX->right->index + offEndY) = vertex_2_1;
1861
1862       if(!BezierCurveTree_isLeaf(BY))
1863       {
1864         vertex_for_index(m_tess.m_vertices, BX->right->index + BY->index) = vertex_1_1;
1865       }
1866     }
1867
1868     // normals
1869
1870     if(nFlagsX & SPLIT)
1871     {
1872       ArbitraryMeshVertex a, b, c;
1873       Vector3 tangentU;
1874
1875       if(!(nFlagsX & DEGEN_0a) || !(nFlagsX & DEGEN_0b))
1876       {
1877         tangentU = vector3_subtracted(vertex_0_1, vertex_0_0);
1878         a.vertex = vertex3f_for_vector3(vertex_0_0);
1879         a.texcoord = texcoord2f_for_vector2(texcoord_0_0);
1880         c.vertex = vertex3f_for_vector3(vertex_0_1);
1881         c.texcoord = texcoord2f_for_vector2(texcoord_0_1);
1882       }
1883       else if(!(nFlagsX & DEGEN_1a) || !(nFlagsX & DEGEN_1b))
1884       {
1885         tangentU = vector3_subtracted(vertex_1_1, vertex_1_0);
1886         a.vertex = vertex3f_for_vector3(vertex_1_0);
1887         a.texcoord = texcoord2f_for_vector2(texcoord_1_0);
1888         c.vertex = vertex3f_for_vector3(vertex_1_1);
1889         c.texcoord = texcoord2f_for_vector2(texcoord_1_1);
1890       }
1891       else
1892       {
1893         tangentU = vector3_subtracted(vertex_2_1, vertex_2_0);
1894         a.vertex = vertex3f_for_vector3(vertex_2_0);
1895         a.texcoord = texcoord2f_for_vector2(texcoord_2_0);
1896         c.vertex = vertex3f_for_vector3(vertex_2_1);
1897         c.texcoord = texcoord2f_for_vector2(texcoord_2_1);
1898       }
1899
1900       Vector3 tangentV;
1901
1902       if((nFlagsY & DEGEN_0a) && (nFlagsY & DEGEN_1a) && (nFlagsY & DEGEN_2a))
1903       {
1904         tangentV = vector3_subtracted(vertex_for_index(m_tess.m_vertices, BX->index + offEndY), tmp);
1905         b.vertex = vertex3f_for_vector3(tmp);//m_tess.m_vertices[BX->index + offEndY].vertex;
1906         b.texcoord = texcoord2f_for_vector2(texTmp);//m_tess.m_vertices[BX->index + offEndY].texcoord;
1907       }
1908       else
1909       {
1910         tangentV = vector3_subtracted(tmp, vertex_for_index(m_tess.m_vertices, BX->index + offStartY));
1911         b.vertex = vertex3f_for_vector3(tmp);//m_tess.m_vertices[BX->index + offStartY].vertex;
1912         b.texcoord = texcoord2f_for_vector2(texTmp); //m_tess.m_vertices[BX->index + offStartY].texcoord;
1913       }
1914
1915
1916       Vector3 normal, s, t;
1917       ArbitraryMeshVertex& v = m_tess.m_vertices[offStartY + BX->index];
1918       Vector3& p = normal3f_to_vector3(v.normal);
1919       Vector3& ps = normal3f_to_vector3(v.tangent);
1920       Vector3& pt = normal3f_to_vector3(v.bitangent);
1921
1922       if(bTranspose)
1923       {
1924         normal = vector3_cross(tangentV, tangentU);
1925       }
1926       else
1927       {
1928         normal = vector3_cross(tangentU, tangentV);
1929       }
1930       normalise_safe(normal);
1931
1932       ArbitraryMeshTriangle_calcTangents(a, b, c, s, t);
1933       normalise_safe(s);
1934       normalise_safe(t);
1935
1936       if(nFlagsX & AVERAGE)
1937       {
1938         p = vector3_normalised(vector3_added(p, normal));
1939         ps = vector3_normalised(vector3_added(ps, s));
1940         pt = vector3_normalised(vector3_added(pt, t));
1941       }
1942       else
1943       {
1944         p = normal;
1945         ps = s;
1946         pt = t;
1947       }
1948     }
1949
1950     {
1951       ArbitraryMeshVertex a, b, c;
1952       Vector3 tangentU;
1953
1954       if(!(nFlagsX & DEGEN_2a) || !(nFlagsX & DEGEN_2b))
1955       {
1956         tangentU = vector3_subtracted(vertex_2_1, vertex_2_0);
1957         a.vertex = vertex3f_for_vector3(vertex_2_0);
1958         a.texcoord = texcoord2f_for_vector2(texcoord_2_0);
1959         c.vertex = vertex3f_for_vector3(vertex_2_1);
1960         c.texcoord = texcoord2f_for_vector2(texcoord_2_1);
1961       }
1962       else if(!(nFlagsX & DEGEN_1a) || !(nFlagsX & DEGEN_1b))
1963       {
1964         tangentU = vector3_subtracted(vertex_1_1, vertex_1_0);
1965         a.vertex = vertex3f_for_vector3(vertex_1_0);
1966         a.texcoord = texcoord2f_for_vector2(texcoord_1_0);
1967         c.vertex = vertex3f_for_vector3(vertex_1_1);
1968         c.texcoord = texcoord2f_for_vector2(texcoord_1_1);
1969       }
1970       else
1971       {
1972         tangentU = vector3_subtracted(vertex_0_1, vertex_0_0);
1973         a.vertex = vertex3f_for_vector3(vertex_0_0);
1974         a.texcoord = texcoord2f_for_vector2(texcoord_0_0);
1975         c.vertex = vertex3f_for_vector3(vertex_0_1);
1976         c.texcoord = texcoord2f_for_vector2(texcoord_0_1);
1977       }
1978
1979       Vector3 tangentV;
1980
1981       if((nFlagsY & DEGEN_0b) && (nFlagsY & DEGEN_1b) && (nFlagsY & DEGEN_2b))
1982       {
1983         tangentV = vector3_subtracted(tmp, vertex_for_index(m_tess.m_vertices, BX->index + offStartY));
1984         b.vertex = vertex3f_for_vector3(tmp);//m_tess.m_vertices[BX->index + offStartY].vertex;
1985         b.texcoord = texcoord2f_for_vector2(texTmp);//m_tess.m_vertices[BX->index + offStartY].texcoord;
1986       }
1987       else
1988       {
1989         tangentV = vector3_subtracted(vertex_for_index(m_tess.m_vertices, BX->index + offEndY), tmp);
1990         b.vertex = vertex3f_for_vector3(tmp);//m_tess.m_vertices[BX->index + offEndY].vertex;
1991         b.texcoord = texcoord2f_for_vector2(texTmp);//m_tess.m_vertices[BX->index + offEndY].texcoord;
1992       }
1993
1994       ArbitraryMeshVertex& v = m_tess.m_vertices[offEndY+BX->index];
1995       Vector3& p = normal3f_to_vector3(v.normal);
1996       Vector3& ps = normal3f_to_vector3(v.tangent);
1997       Vector3& pt = normal3f_to_vector3(v.bitangent);
1998
1999       if(bTranspose)
2000       {
2001         p = vector3_cross(tangentV, tangentU);
2002       }
2003       else
2004       {
2005         p = vector3_cross(tangentU, tangentV);
2006       }
2007       normalise_safe(p);
2008
2009       ArbitraryMeshTriangle_calcTangents(a, b, c, ps, pt);
2010       normalise_safe(ps);
2011       normalise_safe(pt);
2012     }
2013   }
2014
2015
2016   newFlagsX = newFlagsY = 0;
2017
2018   if((nFlagsX & DEGEN_0a) && (nFlagsX & DEGEN_0b))
2019   {
2020     newFlagsX |= DEGEN_0a;
2021     newFlagsX |= DEGEN_0b;
2022   }
2023   if((nFlagsX & DEGEN_1a) && (nFlagsX & DEGEN_1b))
2024   {
2025     newFlagsX |= DEGEN_1a;
2026     newFlagsX |= DEGEN_1b;
2027   }
2028   if((nFlagsX & DEGEN_2a) && (nFlagsX & DEGEN_2b))
2029   {
2030     newFlagsX |= DEGEN_2a;
2031     newFlagsX |= DEGEN_2b;
2032   }
2033   if((nFlagsY & DEGEN_0a) && (nFlagsY & DEGEN_1a) && (nFlagsY & DEGEN_2a))
2034   {
2035     newFlagsY |= DEGEN_0a;
2036     newFlagsY |= DEGEN_1a;
2037     newFlagsY |= DEGEN_2a;
2038   }
2039   if((nFlagsY & DEGEN_0b) && (nFlagsY & DEGEN_1b) && (nFlagsY & DEGEN_2b))
2040   {
2041     newFlagsY |= DEGEN_0b;
2042     newFlagsY |= DEGEN_1b;
2043     newFlagsY |= DEGEN_2b;
2044   }
2045
2046
2047   //if((nFlagsX & DEGEN_0a) && (nFlagsX & DEGEN_1a) && (nFlagsX & DEGEN_2a)) { newFlagsX |= DEGEN_0a; newFlagsX |= DEGEN_1a; newFlagsX |= DEGEN_2a; }
2048   //if((nFlagsX & DEGEN_0b) && (nFlagsX & DEGEN_1b) && (nFlagsX & DEGEN_2b)) { newFlagsX |= DEGEN_0b; newFlagsX |= DEGEN_1b; newFlagsX |= DEGEN_2b; }
2049
2050   newFlagsX |= (nFlagsX & SPLIT);
2051   newFlagsX |= (nFlagsX & AVERAGE);
2052
2053   if(!BezierCurveTree_isLeaf(BY))
2054   {
2055     {
2056       int nTemp = newFlagsY;
2057
2058       if((nFlagsY & DEGEN_0a) && (nFlagsY & DEGEN_0b))
2059       {
2060         newFlagsY |= DEGEN_0a;
2061         newFlagsY |= DEGEN_0b;
2062       }
2063       newFlagsY |= (nFlagsY & SPLIT);
2064       newFlagsY |= (nFlagsY & AVERAGE);
2065
2066       Vector3& p = vertex_for_index(m_tess.m_vertices, BX->index+BY->index);
2067       Vector3 vTemp(p);
2068
2069       Vector2& p2 = texcoord_for_index(m_tess.m_vertices, BX->index+BY->index);
2070       Vector2 stTemp(p2);
2071
2072       TesselateSubMatrix( BY, BX->left,
2073                           offStartY, offStartX,
2074                           offEndY, BX->index,
2075                           newFlagsY, newFlagsX,
2076                           vertex_0_0, vertex_1_0, vertex_2_0,
2077                           texcoord_0_0, texcoord_1_0, texcoord_2_0,
2078                           !bTranspose );
2079
2080       newFlagsY = nTemp;
2081       p = vTemp;
2082       p2 = stTemp;
2083     }
2084
2085     if((nFlagsY & DEGEN_2a) && (nFlagsY & DEGEN_2b)) { newFlagsY |= DEGEN_2a; newFlagsY |= DEGEN_2b; }
2086
2087     TesselateSubMatrix( BY, BX->right,
2088                         offStartY, BX->index,
2089                         offEndY, offEndX,
2090                         newFlagsY, newFlagsX,
2091                         vertex_0_1, vertex_1_1, vertex_2_1,
2092                         texcoord_0_1, texcoord_1_1, texcoord_2_1,
2093                         !bTranspose );
2094   }
2095   else
2096   {
2097     if(!BezierCurveTree_isLeaf(BX->left))
2098     {
2099       TesselateSubMatrix( BX->left,  BY,
2100                           offStartX, offStartY,
2101                           BX->index, offEndY,
2102                           newFlagsX, newFlagsY,
2103                           left, vertex_1_0, tmp,
2104                           texLeft, texcoord_1_0, texTmp,
2105                           bTranspose );
2106     }
2107
2108     if(!BezierCurveTree_isLeaf(BX->right))
2109     {
2110       TesselateSubMatrix( BX->right, BY,
2111                           BX->index, offStartY,
2112                           offEndX, offEndY,
2113                           newFlagsX, newFlagsY,
2114                           tmp, vertex_1_1, right,
2115                           texTmp, texcoord_1_1, texRight,
2116                           bTranspose );
2117     }
2118   }
2119
2120 }
2121
2122 void Patch::BuildTesselationCurves(EMatrixMajor major)
2123 {
2124   std::size_t nArrayStride, length, cross, strideU, strideV;
2125   switch(major)
2126   {
2127   case ROW:
2128     nArrayStride = 1;
2129     length = (m_width - 1) >> 1;
2130     cross = m_height;
2131     strideU = 1;
2132     strideV = m_width;
2133
2134     if(!m_patchDef3)
2135     {
2136       BezierCurveTreeArray_deleteAll(m_tess.m_curveTreeU);
2137     }
2138
2139     break;
2140   case COL:
2141     nArrayStride = m_tess.m_nArrayWidth;
2142     length = (m_height - 1) >> 1;
2143     cross = m_width;
2144     strideU = m_width;
2145     strideV = 1;
2146
2147     if(!m_patchDef3)
2148     {
2149       BezierCurveTreeArray_deleteAll(m_tess.m_curveTreeV);
2150     }
2151
2152     break;
2153   default:
2154     ERROR_MESSAGE("neither row-major nor column-major");
2155     return;
2156   }
2157
2158   Array<std::size_t> arrayLength(length);
2159   Array<BezierCurveTree*> pCurveTree(length);
2160
2161   std::size_t nArrayLength = 1;
2162
2163   if(m_patchDef3)
2164   {
2165     for(Array<std::size_t>::iterator i = arrayLength.begin(); i != arrayLength.end(); ++i)
2166     {
2167       *i = Array<std::size_t>::value_type((major == ROW) ? m_subdivisions_x : m_subdivisions_y);
2168       nArrayLength += *i;
2169     }
2170   }
2171   else
2172   {
2173     // create a list of the horizontal control curves in each column of sub-patches
2174     // adaptively tesselate each horizontal control curve in the list
2175     // create a binary tree representing the combined tesselation of the list
2176     for(std::size_t i = 0; i != length; ++i)
2177     {
2178       PatchControl* p1 = m_ctrlTransformed.data() + (i * 2 * strideU);
2179       GSList* pCurveList = 0;
2180       for(std::size_t j = 0; j < cross; j += 2)
2181       {
2182         PatchControl* p2 = p1+strideV;
2183         PatchControl* p3 = p2+strideV;
2184
2185         // directly taken from one row of control points
2186         {
2187           BezierCurve* pCurve = new BezierCurve;
2188           pCurve->crd = (p1+strideU)->m_vertex;
2189           pCurve->left = p1->m_vertex;
2190           pCurve->right = (p1+(strideU<<1))->m_vertex;
2191           pCurveList = g_slist_prepend(pCurveList, pCurve);
2192         }
2193
2194         if(j+2 >= cross)
2195         {
2196           break;
2197         }
2198
2199         // interpolated from three columns of control points
2200         {
2201           BezierCurve* pCurve = new BezierCurve;
2202           pCurve->crd = vector3_mid((p1+strideU)->m_vertex, (p3+strideU)->m_vertex);
2203           pCurve->left = vector3_mid(p1->m_vertex, p3->m_vertex);
2204           pCurve->right = vector3_mid((p1+(strideU<<1))->m_vertex, (p3+(strideU<<1))->m_vertex);
2205
2206           pCurve->crd = vector3_mid(pCurve->crd, (p2+strideU)->m_vertex);
2207           pCurve->left = vector3_mid(pCurve->left, p2->m_vertex);
2208           pCurve->right = vector3_mid(pCurve->right, (p2+(strideU<<1))->m_vertex);
2209           pCurveList = g_slist_prepend(pCurveList, pCurve);
2210         }
2211
2212         p1 = p3;
2213       }
2214
2215       pCurveTree[i] = new BezierCurveTree;
2216       BezierCurveTree_FromCurveList(pCurveTree[i], pCurveList);
2217       for(GSList* l = pCurveList; l != 0; l = g_slist_next(l))
2218       {
2219         delete static_cast<BezierCurve*>((*l).data);
2220       }
2221       g_slist_free(pCurveList);
2222
2223       // set up array indices for binary tree
2224       // accumulate subarray width
2225       arrayLength[i] = Array<std::size_t>::value_type(BezierCurveTree_Setup(pCurveTree[i], nArrayLength, nArrayStride) - (nArrayLength - 1));
2226       // accumulate total array width
2227       nArrayLength += arrayLength[i];
2228     }
2229   }
2230
2231   switch(major)
2232   {
2233   case ROW:
2234     m_tess.m_nArrayWidth = nArrayLength;
2235     std::swap(m_tess.m_arrayWidth, arrayLength);
2236
2237     if(!m_patchDef3)
2238     {
2239       std::swap(m_tess.m_curveTreeU, pCurveTree);
2240     }
2241     break;
2242   case COL:
2243     m_tess.m_nArrayHeight = nArrayLength;
2244     std::swap(m_tess.m_arrayHeight, arrayLength);
2245
2246     if(!m_patchDef3)
2247     {
2248       std::swap(m_tess.m_curveTreeV, pCurveTree);
2249     }
2250     break;
2251   }
2252 }
2253
2254 inline void vertex_assign_ctrl(ArbitraryMeshVertex& vertex, const PatchControl& ctrl)
2255 {
2256   vertex.vertex = vertex3f_for_vector3(ctrl.m_vertex);
2257   vertex.texcoord = texcoord2f_for_vector2(ctrl.m_texcoord);
2258 }
2259
2260 inline void vertex_clear_normal(ArbitraryMeshVertex& vertex)
2261 {
2262   vertex.normal = Normal3f(0, 0, 0);
2263   vertex.tangent = Normal3f(0, 0, 0);
2264   vertex.bitangent = Normal3f(0, 0, 0);
2265 }
2266
2267 inline void tangents_remove_degenerate(Vector3 tangents[6], Vector2 textureTangents[6], unsigned int flags)
2268 {
2269   if(flags & DEGEN_0a)
2270   {
2271     const std::size_t i =
2272       (flags & DEGEN_0b)
2273       ? (flags & DEGEN_1a)
2274         ? (flags & DEGEN_1b)
2275           ? (flags & DEGEN_2a)
2276             ? 5
2277             : 4
2278           : 3
2279         : 2
2280       : 1;
2281     tangents[0] = tangents[i];
2282     textureTangents[0] = textureTangents[i];
2283   }
2284   if(flags & DEGEN_0b)
2285   {
2286     const std::size_t i =
2287       (flags & DEGEN_0a)
2288       ? (flags & DEGEN_1b)
2289         ? (flags & DEGEN_1a)
2290           ? (flags & DEGEN_2b)
2291             ? 4
2292             : 5
2293           : 2
2294         : 3
2295       : 0;
2296     tangents[1] = tangents[i];
2297     textureTangents[1] = textureTangents[i];
2298   }
2299   if(flags & DEGEN_2a)
2300   {
2301     const std::size_t i =
2302       (flags & DEGEN_2b)
2303       ? (flags & DEGEN_1a)
2304         ? (flags & DEGEN_1b)
2305           ? (flags & DEGEN_0a)
2306             ? 1
2307             : 0
2308           : 3
2309         : 2
2310       : 5;
2311     tangents[4] = tangents[i];
2312     textureTangents[4] = textureTangents[i];
2313   }
2314   if(flags & DEGEN_2b)
2315   {
2316     const std::size_t i =
2317       (flags & DEGEN_2a)
2318       ? (flags & DEGEN_1b)
2319         ? (flags & DEGEN_1a)
2320           ? (flags & DEGEN_0b)
2321             ? 0
2322             : 1
2323           : 2
2324         : 3
2325       : 4;
2326     tangents[5] = tangents[i];
2327     textureTangents[5] = textureTangents[i];
2328   }
2329 }
2330
2331 void bestTangents00(unsigned int degenerateFlags, double dot, double length, std::size_t& index0, std::size_t& index1)
2332 {
2333   if(fabs(dot + length) < 0.001) // opposing direction = degenerate
2334   {
2335     if(!(degenerateFlags & DEGEN_1a)) // if this tangent is degenerate we cannot use it
2336     {
2337       index0 = 2;
2338       index1 = 0;
2339     }
2340     else if(!(degenerateFlags & DEGEN_0b))
2341     {
2342       index0 = 0;
2343       index1 = 1;
2344     }
2345     else
2346     {
2347       index0 = 1;
2348       index1 = 0;
2349     }
2350   }
2351   else if(fabs(dot - length) < 0.001) // same direction = degenerate
2352   {
2353     if(degenerateFlags & DEGEN_0b)
2354     {
2355       index0 = 0;
2356       index1 = 1;
2357     }
2358     else
2359     {
2360       index0 = 1;
2361       index1 = 0;
2362     }
2363   }
2364 }
2365
2366 void bestTangents01(unsigned int degenerateFlags, double dot, double length, std::size_t& index0, std::size_t& index1)
2367 {
2368   if(fabs(dot - length) < 0.001) // same direction = degenerate
2369   {
2370     if(!(degenerateFlags & DEGEN_1a)) // if this tangent is degenerate we cannot use it
2371     {
2372       index0 = 2;
2373       index1 = 1;
2374     }
2375     else if(!(degenerateFlags & DEGEN_2b))
2376     {
2377       index0 = 4;
2378       index1 = 0;
2379     }
2380     else
2381     {
2382       index0 = 5;
2383       index1 = 1;
2384     }
2385   }
2386   else if(fabs(dot + length) < 0.001) // opposing direction = degenerate
2387   {
2388     if(degenerateFlags & DEGEN_2b)
2389     {
2390       index0 = 4;
2391       index1 = 0;
2392     }
2393     else
2394     {
2395       index0 = 5;
2396       index1 = 1;
2397     }
2398   }
2399 }
2400
2401 void bestTangents10(unsigned int degenerateFlags, double dot, double length, std::size_t& index0, std::size_t& index1)
2402 {
2403   if(fabs(dot - length) < 0.001) // same direction = degenerate
2404   {
2405     if(!(degenerateFlags & DEGEN_1b)) // if this tangent is degenerate we cannot use it
2406     {
2407       index0 = 3;
2408       index1 = 4;
2409     }
2410     else if(!(degenerateFlags & DEGEN_0a))
2411     {
2412       index0 = 1;
2413       index1 = 5;
2414     }
2415     else
2416     {
2417       index0 = 0;
2418       index1 = 4;
2419     }
2420   }
2421   else if(fabs(dot + length) < 0.001) // opposing direction = degenerate
2422   {
2423     if(degenerateFlags & DEGEN_0a)
2424     {
2425       index0 = 1;
2426       index1 = 5;
2427     }
2428     else
2429     {
2430       index0 = 0;
2431       index1 = 4;
2432     }
2433   }
2434 }
2435
2436 void bestTangents11(unsigned int degenerateFlags, double dot, double length, std::size_t& index0, std::size_t& index1)
2437 {
2438   if(fabs(dot + length) < 0.001) // opposing direction = degenerate
2439   {
2440     if(!(degenerateFlags & DEGEN_1b)) // if this tangent is degenerate we cannot use it
2441     {
2442       index0 = 3;
2443       index1 = 5;
2444     }
2445     else if(!(degenerateFlags & DEGEN_2a))
2446     {
2447       index0 = 5;
2448       index1 = 4;
2449     }
2450     else
2451     {
2452       index0 = 4;
2453       index1 = 5;
2454     }
2455   }
2456   else if(fabs(dot - length) < 0.001) // same direction = degenerate
2457   {
2458     if(degenerateFlags & DEGEN_2a)
2459     {
2460       index0 = 5;
2461       index1 = 4;
2462     }
2463     else
2464     {
2465       index0 = 4;
2466       index1 = 5;
2467     }
2468   }
2469 }
2470
2471 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)
2472 {
2473   {
2474     Vector3 normal(vector3_cross(tangentX[index0], tangentY[index1]));
2475     if(!vector3_equal(normal, g_vector3_identity))
2476     {
2477       vector3_add(normal_for_index(m_tess.m_vertices, index), vector3_normalised(normal));
2478     }
2479   }
2480
2481   {
2482     ArbitraryMeshVertex a, b, c;
2483     a.vertex = Vertex3f(0, 0, 0);
2484     a.texcoord = TexCoord2f(0, 0);
2485     b.vertex = vertex3f_for_vector3(tangentX[index0]);
2486     b.texcoord = texcoord2f_for_vector2(tangentS[index0]);
2487     c.vertex = vertex3f_for_vector3(tangentY[index1]);
2488     c.texcoord = texcoord2f_for_vector2(tangentT[index1]);
2489
2490     Vector3 s, t;
2491     ArbitraryMeshTriangle_calcTangents(a, b, c, s, t);
2492     if(!vector3_equal(s, g_vector3_identity))
2493     {
2494       vector3_add(tangent_for_index(m_tess.m_vertices, index), vector3_normalised(s));
2495     }
2496     if(!vector3_equal(t, g_vector3_identity))
2497     {
2498       vector3_add(bitangent_for_index(m_tess.m_vertices, index), vector3_normalised(t));
2499     }
2500   }
2501 }
2502
2503 const std::size_t PATCH_MAX_VERTEX_ARRAY = 1048576;
2504
2505 void Patch::BuildVertexArray()
2506 {
2507   const std::size_t strideU = 1;
2508   const std::size_t strideV = m_width;
2509
2510   const std::size_t numElems = m_tess.m_nArrayWidth*m_tess.m_nArrayHeight; // total number of elements in vertex array
2511
2512   const bool bWidthStrips = (m_tess.m_nArrayWidth >= m_tess.m_nArrayHeight); // decide if horizontal strips are longer than vertical
2513
2514
2515   // allocate vertex, normal, texcoord and primitive-index arrays
2516   m_tess.m_vertices.resize(numElems);
2517   m_tess.m_indices.resize(m_tess.m_nArrayWidth *2 * (m_tess.m_nArrayHeight - 1));
2518
2519   // set up strip indices
2520   if(bWidthStrips)
2521   {
2522     m_tess.m_numStrips = m_tess.m_nArrayHeight-1;
2523     m_tess.m_lenStrips = m_tess.m_nArrayWidth*2;
2524
2525     for(std::size_t i=0; i<m_tess.m_nArrayWidth; i++)
2526     {
2527       for(std::size_t j=0; j<m_tess.m_numStrips; j++)
2528       {
2529         m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2] = RenderIndex(j*m_tess.m_nArrayWidth+i);
2530         m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2+1] = RenderIndex((j+1)*m_tess.m_nArrayWidth+i);
2531         // reverse because radiant uses CULL_FRONT
2532         //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2+1] = RenderIndex(j*m_tess.m_nArrayWidth+i);
2533         //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2] = RenderIndex((j+1)*m_tess.m_nArrayWidth+i);
2534       }
2535     }
2536   }
2537   else
2538   {
2539     m_tess.m_numStrips = m_tess.m_nArrayWidth-1;
2540     m_tess.m_lenStrips = m_tess.m_nArrayHeight*2;
2541
2542     for(std::size_t i=0; i<m_tess.m_nArrayHeight; i++)
2543     {
2544       for(std::size_t j=0; j<m_tess.m_numStrips; j++)
2545       {
2546         m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2] = RenderIndex(((m_tess.m_nArrayHeight-1)-i)*m_tess.m_nArrayWidth+j);
2547         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);
2548         // reverse because radiant uses CULL_FRONT
2549         //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2+1] = RenderIndex(((m_tess.m_nArrayHeight-1)-i)*m_tess.m_nArrayWidth+j);
2550         //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2] = RenderIndex(((m_tess.m_nArrayHeight-1)-i)*m_tess.m_nArrayWidth+j+1);
2551
2552       }
2553     }
2554   }
2555
2556   {
2557     PatchControlIter pCtrl = m_ctrlTransformed.data();
2558     for(std::size_t j = 0, offStartY = 0; j+1 < m_height; j += 2, pCtrl += (strideU + strideV))
2559     {
2560       // set up array offsets for this sub-patch
2561       const bool leafY = (m_patchDef3) ? false : BezierCurveTree_isLeaf(m_tess.m_curveTreeV[j>>1]);
2562       const std::size_t offMidY = (m_patchDef3) ? 0 : m_tess.m_curveTreeV[j>>1]->index;
2563       const std::size_t widthY = m_tess.m_arrayHeight[j>>1] * m_tess.m_nArrayWidth;
2564       const std::size_t offEndY = offStartY + widthY;
2565
2566       for(std::size_t i = 0, offStartX = 0; i+1 < m_width; i += 2, pCtrl += (strideU << 1))
2567       {
2568         const bool leafX = (m_patchDef3) ? false : BezierCurveTree_isLeaf(m_tess.m_curveTreeU[i>>1]);
2569         const std::size_t offMidX = (m_patchDef3) ? 0 : m_tess.m_curveTreeU[i>>1]->index;
2570         const std::size_t widthX = m_tess.m_arrayWidth[i>>1];
2571         const std::size_t offEndX = offStartX + widthX;
2572
2573         PatchControl *subMatrix[3][3];
2574         subMatrix[0][0] = pCtrl;
2575         subMatrix[0][1] = subMatrix[0][0]+strideU;
2576         subMatrix[0][2] = subMatrix[0][1]+strideU;
2577         subMatrix[1][0] = subMatrix[0][0]+strideV;
2578         subMatrix[1][1] = subMatrix[1][0]+strideU;
2579         subMatrix[1][2] = subMatrix[1][1]+strideU;
2580         subMatrix[2][0] = subMatrix[1][0]+strideV;
2581         subMatrix[2][1] = subMatrix[2][0]+strideU;
2582         subMatrix[2][2] = subMatrix[2][1]+strideU;
2583
2584         // assign on-patch control points to vertex array
2585         if(i == 0 && j == 0)
2586         {
2587           vertex_clear_normal(m_tess.m_vertices[offStartX + offStartY]);
2588         }
2589         vertex_assign_ctrl(m_tess.m_vertices[offStartX + offStartY], *subMatrix[0][0]);
2590         if(j == 0)
2591         {
2592           vertex_clear_normal(m_tess.m_vertices[offEndX + offStartY]);
2593         }
2594         vertex_assign_ctrl(m_tess.m_vertices[offEndX + offStartY], *subMatrix[0][2]);
2595         if(i == 0)
2596         {
2597           vertex_clear_normal(m_tess.m_vertices[offStartX + offEndY]);
2598         }
2599         vertex_assign_ctrl(m_tess.m_vertices[offStartX + offEndY], *subMatrix[2][0]);
2600
2601         vertex_clear_normal(m_tess.m_vertices[offEndX + offEndY]);
2602         vertex_assign_ctrl(m_tess.m_vertices[offEndX + offEndY], *subMatrix[2][2]);
2603
2604         if(!m_patchDef3)
2605         {
2606           // assign remaining control points to vertex array
2607           if(!leafX)
2608           {
2609             vertex_assign_ctrl(m_tess.m_vertices[offMidX + offStartY], *subMatrix[0][1]);
2610             vertex_assign_ctrl(m_tess.m_vertices[offMidX + offEndY], *subMatrix[2][1]);
2611           }
2612           if(!leafY)
2613           {
2614             vertex_assign_ctrl(m_tess.m_vertices[offStartX + offMidY], *subMatrix[1][0]);
2615             vertex_assign_ctrl(m_tess.m_vertices[offEndX + offMidY], *subMatrix[1][2]);
2616
2617             if(!leafX)
2618             {
2619               vertex_assign_ctrl(m_tess.m_vertices[offMidX + offMidY], *subMatrix[1][1]);
2620             }
2621           }
2622         }
2623
2624         // test all 12 edges for degeneracy
2625         unsigned int nFlagsX = subarray_get_degen(pCtrl, strideU, strideV);
2626         unsigned int nFlagsY = subarray_get_degen(pCtrl, strideV, strideU);
2627         Vector3 tangentX[6], tangentY[6];
2628         Vector2 tangentS[6], tangentT[6];
2629
2630         // set up tangents for each of the 12 edges if they were not degenerate
2631         if(!(nFlagsX & DEGEN_0a))
2632         {
2633           tangentX[0] = vector3_subtracted(subMatrix[0][1]->m_vertex, subMatrix[0][0]->m_vertex);
2634           tangentS[0] = vector2_subtracted(subMatrix[0][1]->m_texcoord, subMatrix[0][0]->m_texcoord);
2635         }
2636         if(!(nFlagsX & DEGEN_0b))
2637         {
2638           tangentX[1] = vector3_subtracted(subMatrix[0][2]->m_vertex, subMatrix[0][1]->m_vertex);
2639           tangentS[1] = vector2_subtracted(subMatrix[0][2]->m_texcoord, subMatrix[0][1]->m_texcoord);
2640         }
2641         if(!(nFlagsX & DEGEN_1a))
2642         {
2643           tangentX[2] = vector3_subtracted(subMatrix[1][1]->m_vertex, subMatrix[1][0]->m_vertex);
2644           tangentS[2] = vector2_subtracted(subMatrix[1][1]->m_texcoord, subMatrix[1][0]->m_texcoord);
2645         }
2646         if(!(nFlagsX & DEGEN_1b))
2647         {
2648           tangentX[3] = vector3_subtracted(subMatrix[1][2]->m_vertex, subMatrix[1][1]->m_vertex);
2649           tangentS[3] = vector2_subtracted(subMatrix[1][2]->m_texcoord, subMatrix[1][1]->m_texcoord);
2650         }
2651         if(!(nFlagsX & DEGEN_2a))
2652         {
2653           tangentX[4] = vector3_subtracted(subMatrix[2][1]->m_vertex, subMatrix[2][0]->m_vertex);
2654           tangentS[4] = vector2_subtracted(subMatrix[2][1]->m_texcoord, subMatrix[2][0]->m_texcoord);
2655         }
2656         if(!(nFlagsX & DEGEN_2b))
2657         {
2658           tangentX[5] = vector3_subtracted(subMatrix[2][2]->m_vertex, subMatrix[2][1]->m_vertex);
2659           tangentS[5] = vector2_subtracted(subMatrix[2][2]->m_texcoord, subMatrix[2][1]->m_texcoord);
2660         }
2661
2662         if(!(nFlagsY & DEGEN_0a))
2663         {
2664           tangentY[0] = vector3_subtracted(subMatrix[1][0]->m_vertex, subMatrix[0][0]->m_vertex);
2665           tangentT[0] = vector2_subtracted(subMatrix[1][0]->m_texcoord, subMatrix[0][0]->m_texcoord);
2666         }
2667         if(!(nFlagsY & DEGEN_0b))
2668         {
2669           tangentY[1] = vector3_subtracted(subMatrix[2][0]->m_vertex, subMatrix[1][0]->m_vertex);
2670           tangentT[1] = vector2_subtracted(subMatrix[2][0]->m_texcoord, subMatrix[1][0]->m_texcoord);
2671         }
2672         if(!(nFlagsY & DEGEN_1a))
2673         {
2674           tangentY[2] = vector3_subtracted(subMatrix[1][1]->m_vertex, subMatrix[0][1]->m_vertex);
2675           tangentT[2] = vector2_subtracted(subMatrix[1][1]->m_texcoord, subMatrix[0][1]->m_texcoord);
2676         }
2677         if(!(nFlagsY & DEGEN_1b))
2678         {
2679           tangentY[3] = vector3_subtracted(subMatrix[2][1]->m_vertex, subMatrix[1][1]->m_vertex);
2680           tangentT[3] = vector2_subtracted(subMatrix[2][1]->m_texcoord, subMatrix[1][1]->m_texcoord);
2681         }
2682         if(!(nFlagsY & DEGEN_2a))
2683         {
2684           tangentY[4] = vector3_subtracted(subMatrix[1][2]->m_vertex, subMatrix[0][2]->m_vertex);
2685           tangentT[4] = vector2_subtracted(subMatrix[1][2]->m_texcoord, subMatrix[0][2]->m_texcoord);
2686         }
2687         if(!(nFlagsY & DEGEN_2b))
2688         {
2689           tangentY[5] = vector3_subtracted(subMatrix[2][2]->m_vertex, subMatrix[1][2]->m_vertex);
2690           tangentT[5] = vector2_subtracted(subMatrix[2][2]->m_texcoord, subMatrix[1][2]->m_texcoord);
2691         }
2692
2693         // set up remaining edge tangents by borrowing the tangent from the closest parallel non-degenerate edge
2694         tangents_remove_degenerate(tangentX, tangentS, nFlagsX);
2695         tangents_remove_degenerate(tangentY, tangentT, nFlagsY);
2696
2697         {
2698           // x=0, y=0
2699           std::size_t index = offStartX + offStartY;
2700           std::size_t index0 = 0;
2701           std::size_t index1 = 0;
2702
2703           double dot = vector3_dot(tangentX[index0], tangentY[index1]);
2704           double length = vector3_length(tangentX[index0]) * vector3_length(tangentY[index1]);
2705
2706           bestTangents00(nFlagsX, dot, length, index0, index1);
2707
2708           accumulateVertexTangentSpace(index, tangentX, tangentY, tangentS, tangentT, index0, index1);
2709         }
2710
2711         {
2712           // x=1, y=0
2713           std::size_t index = offEndX + offStartY;
2714           std::size_t index0 = 1;
2715           std::size_t index1 = 4;
2716
2717           double dot = vector3_dot(tangentX[index0],tangentY[index1]);
2718           double length = vector3_length(tangentX[index0]) * vector3_length(tangentY[index1]);
2719
2720           bestTangents10(nFlagsX, dot, length, index0, index1);
2721
2722           accumulateVertexTangentSpace(index, tangentX, tangentY, tangentS, tangentT, index0, index1);
2723         }
2724
2725         {
2726           // x=0, y=1
2727           std::size_t index = offStartX + offEndY;
2728           std::size_t index0 = 4;
2729           std::size_t index1 = 1;
2730
2731           double dot = vector3_dot(tangentX[index0], tangentY[index1]);
2732           double length = vector3_length(tangentX[index1]) * vector3_length(tangentY[index1]);
2733
2734           bestTangents01(nFlagsX, dot, length, index0, index1);
2735
2736           accumulateVertexTangentSpace(index, tangentX, tangentY, tangentS, tangentT, index0, index1);
2737         }
2738
2739         {
2740           // x=1, y=1
2741           std::size_t index = offEndX + offEndY;
2742           std::size_t index0 = 5;
2743           std::size_t index1 = 5;
2744
2745           double dot = vector3_dot(tangentX[index0],tangentY[index1]);
2746           double length = vector3_length(tangentX[index0]) * vector3_length(tangentY[index1]);
2747
2748           bestTangents11(nFlagsX, dot, length, index0, index1);
2749
2750           accumulateVertexTangentSpace(index, tangentX, tangentY, tangentS, tangentT, index0, index1);
2751         }
2752
2753         //normalise normals that won't be accumulated again
2754         if(i!=0 || j!=0)
2755         {
2756           normalise_safe(normal_for_index(m_tess.m_vertices, offStartX + offStartY));
2757           normalise_safe(tangent_for_index(m_tess.m_vertices, offStartX + offStartY));
2758           normalise_safe(bitangent_for_index(m_tess.m_vertices, offStartX + offStartY));
2759         }
2760         if(i+3 == m_width)
2761         {
2762           normalise_safe(normal_for_index(m_tess.m_vertices, offEndX + offStartY));
2763           normalise_safe(tangent_for_index(m_tess.m_vertices, offEndX + offStartY));
2764           normalise_safe(bitangent_for_index(m_tess.m_vertices, offEndX + offStartY));
2765         }
2766         if(j+3 == m_height)
2767         {
2768           normalise_safe(normal_for_index(m_tess.m_vertices, offStartX + offEndY));
2769           normalise_safe(tangent_for_index(m_tess.m_vertices, offStartX + offEndY));
2770           normalise_safe(bitangent_for_index(m_tess.m_vertices, offStartX + offEndY));
2771         }
2772         if(i+3 == m_width && j+3 == m_height)
2773         {
2774           normalise_safe(normal_for_index(m_tess.m_vertices, offEndX + offEndY));
2775           normalise_safe(tangent_for_index(m_tess.m_vertices, offEndX + offEndY));
2776           normalise_safe(bitangent_for_index(m_tess.m_vertices, offEndX + offEndY));
2777         }
2778
2779         // set flags to average normals between shared edges
2780         if(j != 0)
2781         {
2782           nFlagsX |= AVERAGE;
2783         }
2784         if(i != 0)
2785         {
2786           nFlagsY |= AVERAGE;
2787         }
2788         // set flags to save evaluating shared edges twice
2789         nFlagsX |= SPLIT;
2790         nFlagsY |= SPLIT;
2791
2792         // if the patch is curved.. tesselate recursively
2793         // use the relevant control curves for this sub-patch
2794         if(m_patchDef3)
2795         {
2796           TesselateSubMatrixFixed(m_tess.m_vertices.data() + offStartX + offStartY, 1, m_tess.m_nArrayWidth, nFlagsX, nFlagsY, subMatrix);
2797         }
2798         else
2799         {
2800           if(!leafX)
2801           {
2802             TesselateSubMatrix( m_tess.m_curveTreeU[i>>1], m_tess.m_curveTreeV[j>>1],
2803                                 offStartX, offStartY, offEndX, offEndY, // array offsets
2804                                 nFlagsX, nFlagsY,
2805                                 subMatrix[1][0]->m_vertex, subMatrix[1][1]->m_vertex, subMatrix[1][2]->m_vertex,
2806                                 subMatrix[1][0]->m_texcoord, subMatrix[1][1]->m_texcoord, subMatrix[1][2]->m_texcoord,
2807                                 false );
2808           }
2809           else if(!leafY)
2810           {
2811             TesselateSubMatrix( m_tess.m_curveTreeV[j>>1], m_tess.m_curveTreeU[i>>1],
2812                                 offStartY, offStartX, offEndY, offEndX, // array offsets
2813                                 nFlagsY, nFlagsX,
2814                                 subMatrix[0][1]->m_vertex, subMatrix[1][1]->m_vertex, subMatrix[2][1]->m_vertex,
2815                                 subMatrix[0][1]->m_texcoord, subMatrix[1][1]->m_texcoord, subMatrix[2][1]->m_texcoord,
2816                                 true );
2817           }
2818         }
2819
2820         offStartX = offEndX;
2821       }
2822       offStartY = offEndY;
2823     }
2824   }
2825 }
2826
2827
2828
2829 class PatchFilterWrapper : public Filter
2830 {
2831   bool m_active;
2832   bool m_invert;
2833   PatchFilter& m_filter;
2834 public:
2835   PatchFilterWrapper(PatchFilter& filter, bool invert) : m_invert(invert), m_filter(filter)
2836   {
2837   }
2838   void setActive(bool active)
2839   {
2840     m_active = active;
2841   }
2842   bool active()
2843   {
2844     return m_active;
2845   }
2846   bool filter(const Patch& patch)
2847   {
2848     return m_invert ^ m_filter.filter(patch);
2849   }
2850 };
2851
2852
2853 typedef std::list<PatchFilterWrapper> PatchFilters;
2854 PatchFilters g_patchFilters;
2855
2856 void add_patch_filter(PatchFilter& filter, int mask, bool invert)
2857 {
2858   g_patchFilters.push_back(PatchFilterWrapper(filter, invert));
2859   GlobalFilterSystem().addFilter(g_patchFilters.back(), mask);
2860 }
2861
2862 bool patch_filtered(Patch& patch)
2863 {
2864   for(PatchFilters::iterator i = g_patchFilters.begin(); i != g_patchFilters.end(); ++i)
2865   {
2866     if((*i).active() && (*i).filter(patch))
2867     {
2868       return true;
2869     }
2870   }
2871   return false;
2872 }