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