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