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