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