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