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