radiant/patch.cpp

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