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