Remove -Wno-sign-compare
[xonotic/netradiant.git] / radiant / patch.cpp
1 /*
2    Copyright (C) 2001-2006, William Joseph.
3    All Rights Reserved.
4
5    This file is part of GtkRadiant.
6
7    GtkRadiant is free software; you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 2 of the License, or
10    (at your option) any later version.
11
12    GtkRadiant is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with GtkRadiant; if not, write to the Free Software
19    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
20  */
21
22 #include "patch.h"
23
24 #include <glib.h>
25 #include "preferences.h"
26 #include "brush_primit.h"
27 #include "signal/signal.h"
28
29
30 Signal0 g_patchTextureChangedCallbacks;
31
32 void Patch_addTextureChangedCallback( const SignalHandler& handler ){
33         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                 float f = 1 / cos( M_PI / n );
1361                 for ( std::size_t i = 0; i < width; ++i )
1362                 {
1363                         float angle = ( M_PI * i ) / n; // 0 to 2pi
1364                         float x = vPos[1][0] + ( vPos[2][0] - vPos[1][0] ) * cos( angle ) * ( ( i & 1 ) ? f : 1.0f );
1365                         float y = vPos[1][1] + ( vPos[2][1] - vPos[1][1] ) * sin( angle ) * ( ( i & 1 ) ? f : 1.0f );
1366                         for ( std::size_t j = 0; j < height; ++j )
1367                         {
1368                                 float z = vPos[0][2] + ( vPos[2][2] - vPos[0][2] ) * ( j / (float)( height - 1 ) );
1369                                 PatchControl *v;
1370                                 v = &m_ctrl.data()[j * width + i];
1371                                 v->m_vertex[0] = x;
1372                                 v->m_vertex[1] = y;
1373                                 v->m_vertex[2] = z;
1374                         }
1375                 }
1376         }
1377         else if ( eType == eXactCone ) {
1378                 int n = ( width - 1 ) / 2; // n = number of segments
1379                 setDims( width, height );
1380
1381                 // vPos[0] = vector3_subtracted(aabb.origin, aabb.extents);
1382                 // vPos[1] = aabb.origin;
1383                 // vPos[2] = vector3_added(aabb.origin, aabb.extents);
1384
1385                 float f = 1 / cos( M_PI / n );
1386                 for ( std::size_t i = 0; i < width; ++i )
1387                 {
1388                         float angle = ( M_PI * i ) / n;
1389                         for ( std::size_t j = 0; j < height; ++j )
1390                         {
1391                                 float x = vPos[1][0] + ( 1.0f - ( j / (float)( height - 1 ) ) ) * ( vPos[2][0] - vPos[1][0] ) * cos( angle ) * ( ( i & 1 ) ? f : 1.0f );
1392                                 float y = vPos[1][1] + ( 1.0f - ( j / (float)( height - 1 ) ) ) * ( vPos[2][1] - vPos[1][1] ) * sin( angle ) * ( ( i & 1 ) ? f : 1.0f );
1393                                 float z = vPos[0][2] + ( vPos[2][2] - vPos[0][2] ) * ( j / (float)( height - 1 ) );
1394                                 PatchControl *v;
1395                                 v = &m_ctrl.data()[j * width + i];
1396                                 v->m_vertex[0] = x;
1397                                 v->m_vertex[1] = y;
1398                                 v->m_vertex[2] = z;
1399                         }
1400                 }
1401         }
1402         else if ( eType == eXactSphere ) {
1403                 int n = ( width - 1 ) / 2; // n = number of segments (yaw)
1404                 int m = ( height - 1 ) / 2; // m = number of segments (pitch)
1405                 setDims( width, height );
1406
1407                 // vPos[0] = vector3_subtracted(aabb.origin, aabb.extents);
1408                 // vPos[1] = aabb.origin;
1409                 // vPos[2] = vector3_added(aabb.origin, aabb.extents);
1410
1411                 float f = 1 / cos( M_PI / n );
1412                 float g = 1 / cos( M_PI / ( 2 * m ) );
1413                 for ( std::size_t i = 0; i < width; ++i )
1414                 {
1415                         float angle = ( M_PI * i ) / n;
1416                         for ( std::size_t j = 0; j < height; ++j )
1417                         {
1418                                 float angle2 = ( M_PI * j ) / ( 2 * m );
1419                                 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 );
1420                                 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 );
1421                                 float z = vPos[1][2] + ( vPos[2][2] - vPos[1][2] ) * -cos( angle2 ) * ( ( j & 1 ) ? g : 1.0f );
1422                                 PatchControl *v;
1423                                 v = &m_ctrl.data()[j * width + i];
1424                                 v->m_vertex[0] = x;
1425                                 v->m_vertex[1] = y;
1426                                 v->m_vertex[2] = z;
1427                         }
1428                 }
1429         }
1430         else if  ( eType == eBevel ) {
1431                 unsigned char *pIndex;
1432                 unsigned char pBevIndex[] =
1433                 {
1434                         0, 0,
1435                         2, 0,
1436                         2, 2,
1437                 };
1438
1439                 setDims( 3, 3 );
1440
1441                 PatchControl* pCtrl = m_ctrl.data();
1442                 for ( std::size_t h = 0; h < 3; h++ )
1443                 {
1444                         pIndex = pBevIndex;
1445                         for ( std::size_t w = 0; w < 3; w++, pIndex += 2, pCtrl++ )
1446                         {
1447                                 pCtrl->m_vertex[0] = vPos[pIndex[0]][0];
1448                                 pCtrl->m_vertex[1] = vPos[pIndex[1]][1];
1449                                 pCtrl->m_vertex[2] = vPos[h][2];
1450                         }
1451                 }
1452         }
1453         else if ( eType == eEndCap ) {
1454                 unsigned char *pIndex;
1455                 unsigned char pEndIndex[] =
1456                 {
1457                         2, 0,
1458                         2, 2,
1459                         1, 2,
1460                         0, 2,
1461                         0, 0,
1462                 };
1463
1464                 setDims( 5, 3 );
1465
1466                 PatchControl* pCtrl = m_ctrl.data();
1467                 for ( std::size_t h = 0; h < 3; h++ )
1468                 {
1469                         pIndex = pEndIndex;
1470                         for ( std::size_t w = 0; w < 5; w++, pIndex += 2, pCtrl++ )
1471                         {
1472                                 pCtrl->m_vertex[0] = vPos[pIndex[0]][0];
1473                                 pCtrl->m_vertex[1] = vPos[pIndex[1]][1];
1474                                 pCtrl->m_vertex[2] = vPos[h][2];
1475                         }
1476                 }
1477         }
1478
1479         if ( eType == eDenseCylinder ) {
1480                 InsertRemove( true, false, true );
1481         }
1482
1483         if ( eType == eVeryDenseCylinder ) {
1484                 InsertRemove( true, false, false );
1485                 InsertRemove( true, false, true );
1486         }
1487
1488         NaturalTexture();
1489 }
1490
1491 void Patch::RenderDebug( RenderStateFlags state ) const {
1492         for ( std::size_t i = 0; i < m_tess.m_numStrips; i++ )
1493         {
1494                 glBegin( GL_QUAD_STRIP );
1495                 for ( std::size_t j = 0; j < m_tess.m_lenStrips; j++ )
1496                 {
1497                         glNormal3fv( normal3f_to_array( ( m_tess.m_vertices.data() + m_tess.m_indices[i * m_tess.m_lenStrips + j] )->normal ) );
1498                         glTexCoord2fv( texcoord2f_to_array( ( m_tess.m_vertices.data() + m_tess.m_indices[i * m_tess.m_lenStrips + j] )->texcoord ) );
1499                         glVertex3fv( vertex3f_to_array( ( m_tess.m_vertices.data() + m_tess.m_indices[i * m_tess.m_lenStrips + j] )->vertex ) );
1500                 }
1501                 glEnd();
1502         }
1503 }
1504
1505 void RenderablePatchSolid::RenderNormals() const {
1506         const std::size_t width = m_tess.m_numStrips + 1;
1507         const std::size_t height = m_tess.m_lenStrips >> 1;
1508         glBegin( GL_LINES );
1509         for ( std::size_t i = 0; i < width; i++ )
1510         {
1511                 for ( std::size_t j = 0; j < height; j++ )
1512                 {
1513                         {
1514                                 Vector3 vNormal(
1515                                         vector3_added(
1516                                                 vertex3f_to_vector3( ( m_tess.m_vertices.data() + ( j * width + i ) )->vertex ),
1517                                                 vector3_scaled( normal3f_to_vector3( ( m_tess.m_vertices.data() + ( j * width + i ) )->normal ), 8 )
1518                                                 )
1519                                         );
1520                                 glVertex3fv( vertex3f_to_array( ( m_tess.m_vertices.data() + ( j * width + i ) )->vertex ) );
1521                                 glVertex3fv( &vNormal[0] );
1522                         }
1523                         {
1524                                 Vector3 vNormal(
1525                                         vector3_added(
1526                                                 vertex3f_to_vector3( ( m_tess.m_vertices.data() + ( j * width + i ) )->vertex ),
1527                                                 vector3_scaled( normal3f_to_vector3( ( m_tess.m_vertices.data() + ( j * width + i ) )->tangent ), 8 )
1528                                                 )
1529                                         );
1530                                 glVertex3fv( vertex3f_to_array( ( m_tess.m_vertices.data() + ( j * width + i ) )->vertex ) );
1531                                 glVertex3fv( &vNormal[0] );
1532                         }
1533                         {
1534                                 Vector3 vNormal(
1535                                         vector3_added(
1536                                                 vertex3f_to_vector3( ( m_tess.m_vertices.data() + ( j * width + i ) )->vertex ),
1537                                                 vector3_scaled( normal3f_to_vector3( ( m_tess.m_vertices.data() + ( j * width + i ) )->bitangent ), 8 )
1538                                                 )
1539                                         );
1540                                 glVertex3fv( vertex3f_to_array( ( m_tess.m_vertices.data() + ( j * width + i ) )->vertex ) );
1541                                 glVertex3fv( &vNormal[0] );
1542                         }
1543                 }
1544         }
1545         glEnd();
1546 }
1547
1548 #define DEGEN_0a  0x01
1549 #define DEGEN_1a  0x02
1550 #define DEGEN_2a  0x04
1551 #define DEGEN_0b  0x08
1552 #define DEGEN_1b  0x10
1553 #define DEGEN_2b  0x20
1554 #define SPLIT     0x40
1555 #define AVERAGE   0x80
1556
1557
1558 unsigned int subarray_get_degen( PatchControlIter subarray, std::size_t strideU, std::size_t strideV ){
1559         unsigned int nDegen = 0;
1560         const PatchControl* p1;
1561         const PatchControl* p2;
1562
1563         p1 = subarray;
1564         p2 = p1 + strideU;
1565         if ( vector3_equal( p1->m_vertex, p2->m_vertex ) ) {
1566                 nDegen |= DEGEN_0a;
1567         }
1568         p1 = p2;
1569         p2 = p1 + strideU;
1570         if ( vector3_equal( p1->m_vertex, p2->m_vertex ) ) {
1571                 nDegen |= DEGEN_0b;
1572         }
1573
1574         p1 = subarray + strideV;
1575         p2 = p1 + strideU;
1576         if ( vector3_equal( p1->m_vertex, p2->m_vertex ) ) {
1577                 nDegen |= DEGEN_1a;
1578         }
1579         p1 = p2;
1580         p2 = p1 + strideU;
1581         if ( vector3_equal( p1->m_vertex, p2->m_vertex ) ) {
1582                 nDegen |= DEGEN_1b;
1583         }
1584
1585         p1 = subarray + ( strideV << 1 );
1586         p2 = p1 + strideU;
1587         if ( vector3_equal( p1->m_vertex, p2->m_vertex ) ) {
1588                 nDegen |= DEGEN_2a;
1589         }
1590         p1 = p2;
1591         p2 = p1 + strideU;
1592         if ( vector3_equal( p1->m_vertex, p2->m_vertex ) ) {
1593                 nDegen |= DEGEN_2b;
1594         }
1595
1596         return nDegen;
1597 }
1598
1599
1600 inline void deCasteljau3( const Vector3& P0, const Vector3& P1, const Vector3& P2, Vector3& P01, Vector3& P12, Vector3& P012 ){
1601         P01 = vector3_mid( P0, P1 );
1602         P12 = vector3_mid( P1, P2 );
1603         P012 = vector3_mid( P01, P12 );
1604 }
1605
1606 inline void BezierInterpolate3( const Vector3& start, Vector3& left, Vector3& mid, Vector3& right, const Vector3& end ){
1607         left = vector3_mid( start, mid );
1608         right = vector3_mid( mid, end );
1609         mid = vector3_mid( left, right );
1610 }
1611
1612 inline void BezierInterpolate2( const Vector2& start, Vector2& left, Vector2& mid, Vector2& right, const Vector2& end ){
1613         left[0] = float_mid( start[0], mid[0] );
1614         left[1] = float_mid( start[1], mid[1] );
1615         right[0] = float_mid( mid[0], end[0] );
1616         right[1] = float_mid( mid[1], end[1] );
1617         mid[0] = float_mid( left[0], right[0] );
1618         mid[1] = float_mid( left[1], right[1] );
1619 }
1620
1621
1622 inline Vector2& texcoord_for_index( Array<ArbitraryMeshVertex>& vertices, std::size_t index ){
1623         return reinterpret_cast<Vector2&>( vertices[index].texcoord );
1624 }
1625
1626 inline Vector3& vertex_for_index( Array<ArbitraryMeshVertex>& vertices, std::size_t index ){
1627         return reinterpret_cast<Vector3&>( vertices[index].vertex );
1628 }
1629
1630 inline Vector3& normal_for_index( Array<ArbitraryMeshVertex>& vertices, std::size_t index ){
1631         return reinterpret_cast<Vector3&>( vertices[index].normal );
1632 }
1633
1634 inline Vector3& tangent_for_index( Array<ArbitraryMeshVertex>& vertices, std::size_t index ){
1635         return reinterpret_cast<Vector3&>( vertices[index].tangent );
1636 }
1637
1638 inline Vector3& bitangent_for_index( Array<ArbitraryMeshVertex>& vertices, std::size_t index ){
1639         return reinterpret_cast<Vector3&>( vertices[index].bitangent );
1640 }
1641
1642 inline const Vector2& texcoord_for_index( const Array<ArbitraryMeshVertex>& vertices, std::size_t index ){
1643         return reinterpret_cast<const Vector2&>( vertices[index].texcoord );
1644 }
1645
1646 inline const Vector3& vertex_for_index( const Array<ArbitraryMeshVertex>& vertices, std::size_t index ){
1647         return reinterpret_cast<const Vector3&>( vertices[index].vertex );
1648 }
1649
1650 inline const Vector3& normal_for_index( const Array<ArbitraryMeshVertex>& vertices, std::size_t index ){
1651         return reinterpret_cast<const Vector3&>( vertices[index].normal );
1652 }
1653
1654 inline const Vector3& tangent_for_index( const Array<ArbitraryMeshVertex>& vertices, std::size_t index ){
1655         return reinterpret_cast<const Vector3&>( vertices[index].tangent );
1656 }
1657
1658 inline const Vector3& bitangent_for_index( const Array<ArbitraryMeshVertex>& vertices, std::size_t index ){
1659         return reinterpret_cast<const Vector3&>( vertices[index].bitangent );
1660 }
1661
1662 #include "math/curve.h"
1663
1664 inline PatchControl QuadraticBezier_evaluate( const PatchControl* firstPoint, double t ){
1665         PatchControl result = { Vector3( 0, 0, 0 ), Vector2( 0, 0 ) };
1666         double denominator = 0;
1667
1668         {
1669                 double weight = BernsteinPolynomial<Zero, Two>::apply( t );
1670                 vector3_add( result.m_vertex, vector3_scaled( firstPoint[0].m_vertex, weight ) );
1671                 vector2_add( result.m_texcoord, vector2_scaled( firstPoint[0].m_texcoord, weight ) );
1672                 denominator += weight;
1673         }
1674         {
1675                 double weight = BernsteinPolynomial<One, Two>::apply( t );
1676                 vector3_add( result.m_vertex, vector3_scaled( firstPoint[1].m_vertex, weight ) );
1677                 vector2_add( result.m_texcoord, vector2_scaled( firstPoint[1].m_texcoord, weight ) );
1678                 denominator += weight;
1679         }
1680         {
1681                 double weight = BernsteinPolynomial<Two, Two>::apply( t );
1682                 vector3_add( result.m_vertex, vector3_scaled( firstPoint[2].m_vertex, weight ) );
1683                 vector2_add( result.m_texcoord, vector2_scaled( firstPoint[2].m_texcoord, weight ) );
1684                 denominator += weight;
1685         }
1686
1687         vector3_divide( result.m_vertex, denominator );
1688         vector2_divide( result.m_texcoord, denominator );
1689         return result;
1690 }
1691
1692 inline Vector3 vector3_linear_interpolated( const Vector3& a, const Vector3& b, double t ){
1693         return vector3_added( vector3_scaled( a, 1.0 - t ), vector3_scaled( b, t ) );
1694 }
1695
1696 inline Vector2 vector2_linear_interpolated( const Vector2& a, const Vector2& b, double t ){
1697         return vector2_added( vector2_scaled( a, 1.0 - t ), vector2_scaled( b, t ) );
1698 }
1699
1700 void normalise_safe( Vector3& normal ){
1701         if ( !vector3_equal( normal, g_vector3_identity ) ) {
1702                 vector3_normalise( normal );
1703         }
1704 }
1705
1706 inline void QuadraticBezier_evaluate( const PatchControl& a, const PatchControl& b, const PatchControl& c, double t, PatchControl& point, PatchControl& left, PatchControl& right ){
1707         left.m_vertex = vector3_linear_interpolated( a.m_vertex, b.m_vertex, t );
1708         left.m_texcoord = vector2_linear_interpolated( a.m_texcoord, b.m_texcoord, t );
1709         right.m_vertex = vector3_linear_interpolated( b.m_vertex, c.m_vertex, t );
1710         right.m_texcoord = vector2_linear_interpolated( b.m_texcoord, c.m_texcoord, t );
1711         point.m_vertex = vector3_linear_interpolated( left.m_vertex, right.m_vertex, t );
1712         point.m_texcoord = vector2_linear_interpolated( left.m_texcoord, right.m_texcoord, t );
1713 }
1714
1715 void Patch::TesselateSubMatrixFixed( ArbitraryMeshVertex* vertices, std::size_t strideX, std::size_t strideY, unsigned int nFlagsX, unsigned int nFlagsY, PatchControl* subMatrix[3][3] ){
1716         double incrementU = 1.0 / m_subdivisions_x;
1717         double incrementV = 1.0 / m_subdivisions_y;
1718         const std::size_t width = m_subdivisions_x + 1;
1719         const std::size_t height = m_subdivisions_y + 1;
1720
1721         for ( std::size_t i = 0; i != width; ++i )
1722         {
1723                 double tU = ( i + 1 == width ) ? 1 : i * incrementU;
1724                 PatchControl pointX[3];
1725                 PatchControl leftX[3];
1726                 PatchControl rightX[3];
1727                 QuadraticBezier_evaluate( *subMatrix[0][0], *subMatrix[0][1], *subMatrix[0][2], tU, pointX[0], leftX[0], rightX[0] );
1728                 QuadraticBezier_evaluate( *subMatrix[1][0], *subMatrix[1][1], *subMatrix[1][2], tU, pointX[1], leftX[1], rightX[1] );
1729                 QuadraticBezier_evaluate( *subMatrix[2][0], *subMatrix[2][1], *subMatrix[2][2], tU, pointX[2], leftX[2], rightX[2] );
1730
1731                 ArbitraryMeshVertex* p = vertices + i * strideX;
1732                 for ( std::size_t j = 0; j != height; ++j )
1733                 {
1734                         if ( ( j == 0 || j + 1 == height ) && ( i == 0 || i + 1 == width ) ) {
1735                         }
1736                         else
1737                         {
1738                                 double tV = ( j + 1 == height ) ? 1 : j * incrementV;
1739
1740                                 PatchControl pointY[3];
1741                                 PatchControl leftY[3];
1742                                 PatchControl rightY[3];
1743                                 QuadraticBezier_evaluate( *subMatrix[0][0], *subMatrix[1][0], *subMatrix[2][0], tV, pointY[0], leftY[0], rightY[0] );
1744                                 QuadraticBezier_evaluate( *subMatrix[0][1], *subMatrix[1][1], *subMatrix[2][1], tV, pointY[1], leftY[1], rightY[1] );
1745                                 QuadraticBezier_evaluate( *subMatrix[0][2], *subMatrix[1][2], *subMatrix[2][2], tV, pointY[2], leftY[2], rightY[2] );
1746
1747                                 PatchControl point;
1748                                 PatchControl left;
1749                                 PatchControl right;
1750                                 QuadraticBezier_evaluate( pointX[0], pointX[1], pointX[2], tV, point, left, right );
1751                                 PatchControl up;
1752                                 PatchControl down;
1753                                 QuadraticBezier_evaluate( pointY[0], pointY[1], pointY[2], tU, point, up, down );
1754
1755                                 vertex3f_to_vector3( p->vertex ) = point.m_vertex;
1756                                 texcoord2f_to_vector2( p->texcoord ) = point.m_texcoord;
1757
1758                                 ArbitraryMeshVertex a, b, c;
1759
1760                                 a.vertex = vertex3f_for_vector3( left.m_vertex );
1761                                 a.texcoord = texcoord2f_for_vector2( left.m_texcoord );
1762                                 b.vertex = vertex3f_for_vector3( right.m_vertex );
1763                                 b.texcoord = texcoord2f_for_vector2( right.m_texcoord );
1764
1765                                 if ( i != 0 ) {
1766                                         c.vertex = vertex3f_for_vector3( up.m_vertex );
1767                                         c.texcoord = texcoord2f_for_vector2( up.m_texcoord );
1768                                 }
1769                                 else
1770                                 {
1771                                         c.vertex = vertex3f_for_vector3( down.m_vertex );
1772                                         c.texcoord = texcoord2f_for_vector2( down.m_texcoord );
1773                                 }
1774
1775                                 Vector3 normal = vector3_normalised( vector3_cross( right.m_vertex - left.m_vertex, up.m_vertex - down.m_vertex ) );
1776
1777                                 Vector3 tangent, bitangent;
1778                                 ArbitraryMeshTriangle_calcTangents( a, b, c, tangent, bitangent );
1779                                 vector3_normalise( tangent );
1780                                 vector3_normalise( bitangent );
1781
1782                                 if ( ( ( nFlagsX & AVERAGE ) != 0 && i == 0 ) || ( ( nFlagsY & AVERAGE ) != 0  && j == 0 ) ) {
1783                                         normal3f_to_vector3( p->normal ) = vector3_normalised( vector3_added( normal3f_to_vector3( p->normal ), normal ) );
1784                                         normal3f_to_vector3( p->tangent ) = vector3_normalised( vector3_added( normal3f_to_vector3( p->tangent ), tangent ) );
1785                                         normal3f_to_vector3( p->bitangent ) = vector3_normalised( vector3_added( normal3f_to_vector3( p->bitangent ), bitangent ) );
1786                                 }
1787                                 else
1788                                 {
1789                                         normal3f_to_vector3( p->normal ) = normal;
1790                                         normal3f_to_vector3( p->tangent ) = tangent;
1791                                         normal3f_to_vector3( p->bitangent ) = bitangent;
1792                                 }
1793                         }
1794
1795                         p += strideY;
1796                 }
1797         }
1798 }
1799
1800 void Patch::TesselateSubMatrix( const BezierCurveTree *BX, const BezierCurveTree *BY,
1801                                                                 std::size_t offStartX, std::size_t offStartY,
1802                                                                 std::size_t offEndX, std::size_t offEndY,
1803                                                                 std::size_t nFlagsX, std::size_t nFlagsY,
1804                                                                 Vector3& left, Vector3& mid, Vector3& right,
1805                                                                 Vector2& texLeft, Vector2& texMid, Vector2& texRight,
1806                                                                 bool bTranspose ){
1807         int newFlagsX, newFlagsY;
1808
1809         Vector3 tmp;
1810         Vector3 vertex_0_0, vertex_0_1, vertex_1_0, vertex_1_1, vertex_2_0, vertex_2_1;
1811         Vector2 texTmp;
1812         Vector2 texcoord_0_0, texcoord_0_1, texcoord_1_0, texcoord_1_1, texcoord_2_0, texcoord_2_1;
1813
1814         {
1815                 // texcoords
1816
1817                 BezierInterpolate2( texcoord_for_index( m_tess.m_vertices, offStartX + offStartY ),
1818                                                         texcoord_0_0,
1819                                                         texcoord_for_index( m_tess.m_vertices, BX->index + offStartY ),
1820                                                         texcoord_0_1,
1821                                                         texcoord_for_index( m_tess.m_vertices, offEndX + offStartY ) );
1822
1823
1824                 BezierInterpolate2( texcoord_for_index( m_tess.m_vertices, offStartX + offEndY ),
1825                                                         texcoord_2_0,
1826                                                         texcoord_for_index( m_tess.m_vertices, BX->index + offEndY ),
1827                                                         texcoord_2_1,
1828                                                         texcoord_for_index( m_tess.m_vertices, offEndX + offEndY ) );
1829
1830                 texTmp = texMid;
1831
1832                 BezierInterpolate2( texLeft,
1833                                                         texcoord_1_0,
1834                                                         texTmp,
1835                                                         texcoord_1_1,
1836                                                         texRight );
1837
1838                 if ( !BezierCurveTree_isLeaf( BY ) ) {
1839                         texcoord_for_index( m_tess.m_vertices, BX->index + BY->index ) = texTmp;
1840                 }
1841
1842
1843                 if ( !BezierCurveTree_isLeaf( BX->left ) ) {
1844                         texcoord_for_index( m_tess.m_vertices, BX->left->index + offStartY ) = texcoord_0_0;
1845                         texcoord_for_index( m_tess.m_vertices, BX->left->index + offEndY ) = texcoord_2_0;
1846
1847                         if ( !BezierCurveTree_isLeaf( BY ) ) {
1848                                 texcoord_for_index( m_tess.m_vertices, BX->left->index + BY->index ) = texcoord_1_0;
1849                         }
1850                 }
1851                 if ( !BezierCurveTree_isLeaf( BX->right ) ) {
1852                         texcoord_for_index( m_tess.m_vertices, BX->right->index + offStartY ) = texcoord_0_1;
1853                         texcoord_for_index( m_tess.m_vertices, BX->right->index + offEndY ) = texcoord_2_1;
1854
1855                         if ( !BezierCurveTree_isLeaf( BY ) ) {
1856                                 texcoord_for_index( m_tess.m_vertices, BX->right->index + BY->index ) = texcoord_1_1;
1857                         }
1858                 }
1859
1860
1861                 // verts
1862
1863                 BezierInterpolate3( vertex_for_index( m_tess.m_vertices, offStartX + offStartY ),
1864                                                         vertex_0_0,
1865                                                         vertex_for_index( m_tess.m_vertices, BX->index + offStartY ),
1866                                                         vertex_0_1,
1867                                                         vertex_for_index( m_tess.m_vertices, offEndX + offStartY ) );
1868
1869
1870                 BezierInterpolate3( vertex_for_index( m_tess.m_vertices, offStartX + offEndY ),
1871                                                         vertex_2_0,
1872                                                         vertex_for_index( m_tess.m_vertices, BX->index + offEndY ),
1873                                                         vertex_2_1,
1874                                                         vertex_for_index( m_tess.m_vertices, offEndX + offEndY ) );
1875
1876
1877                 tmp = mid;
1878
1879                 BezierInterpolate3( left,
1880                                                         vertex_1_0,
1881                                                         tmp,
1882                                                         vertex_1_1,
1883                                                         right );
1884
1885                 if ( !BezierCurveTree_isLeaf( BY ) ) {
1886                         vertex_for_index( m_tess.m_vertices, BX->index + BY->index ) = tmp;
1887                 }
1888
1889
1890                 if ( !BezierCurveTree_isLeaf( BX->left ) ) {
1891                         vertex_for_index( m_tess.m_vertices, BX->left->index + offStartY ) = vertex_0_0;
1892                         vertex_for_index( m_tess.m_vertices, BX->left->index + offEndY ) = vertex_2_0;
1893
1894                         if ( !BezierCurveTree_isLeaf( BY ) ) {
1895                                 vertex_for_index( m_tess.m_vertices, BX->left->index + BY->index ) = vertex_1_0;
1896                         }
1897                 }
1898                 if ( !BezierCurveTree_isLeaf( BX->right ) ) {
1899                         vertex_for_index( m_tess.m_vertices, BX->right->index + offStartY ) = vertex_0_1;
1900                         vertex_for_index( m_tess.m_vertices, BX->right->index + offEndY ) = vertex_2_1;
1901
1902                         if ( !BezierCurveTree_isLeaf( BY ) ) {
1903                                 vertex_for_index( m_tess.m_vertices, BX->right->index + BY->index ) = vertex_1_1;
1904                         }
1905                 }
1906
1907                 // normals
1908
1909                 if ( nFlagsX & SPLIT ) {
1910                         ArbitraryMeshVertex a, b, c;
1911                         Vector3 tangentU;
1912
1913                         if ( !( nFlagsX & DEGEN_0a ) || !( nFlagsX & DEGEN_0b ) ) {
1914                                 tangentU = vector3_subtracted( vertex_0_1, vertex_0_0 );
1915                                 a.vertex = vertex3f_for_vector3( vertex_0_0 );
1916                                 a.texcoord = texcoord2f_for_vector2( texcoord_0_0 );
1917                                 c.vertex = vertex3f_for_vector3( vertex_0_1 );
1918                                 c.texcoord = texcoord2f_for_vector2( texcoord_0_1 );
1919                         }
1920                         else if ( !( nFlagsX & DEGEN_1a ) || !( nFlagsX & DEGEN_1b ) ) {
1921                                 tangentU = vector3_subtracted( vertex_1_1, vertex_1_0 );
1922                                 a.vertex = vertex3f_for_vector3( vertex_1_0 );
1923                                 a.texcoord = texcoord2f_for_vector2( texcoord_1_0 );
1924                                 c.vertex = vertex3f_for_vector3( vertex_1_1 );
1925                                 c.texcoord = texcoord2f_for_vector2( texcoord_1_1 );
1926                         }
1927                         else
1928                         {
1929                                 tangentU = vector3_subtracted( vertex_2_1, vertex_2_0 );
1930                                 a.vertex = vertex3f_for_vector3( vertex_2_0 );
1931                                 a.texcoord = texcoord2f_for_vector2( texcoord_2_0 );
1932                                 c.vertex = vertex3f_for_vector3( vertex_2_1 );
1933                                 c.texcoord = texcoord2f_for_vector2( texcoord_2_1 );
1934                         }
1935
1936                         Vector3 tangentV;
1937
1938                         if ( ( nFlagsY & DEGEN_0a ) && ( nFlagsY & DEGEN_1a ) && ( nFlagsY & DEGEN_2a ) ) {
1939                                 tangentV = vector3_subtracted( vertex_for_index( m_tess.m_vertices, BX->index + offEndY ), tmp );
1940                                 b.vertex = vertex3f_for_vector3( tmp ); //m_tess.m_vertices[BX->index + offEndY].vertex;
1941                                 b.texcoord = texcoord2f_for_vector2( texTmp ); //m_tess.m_vertices[BX->index + offEndY].texcoord;
1942                         }
1943                         else
1944                         {
1945                                 tangentV = vector3_subtracted( tmp, vertex_for_index( m_tess.m_vertices, BX->index + offStartY ) );
1946                                 b.vertex = vertex3f_for_vector3( tmp ); //m_tess.m_vertices[BX->index + offStartY].vertex;
1947                                 b.texcoord = texcoord2f_for_vector2( texTmp ); //m_tess.m_vertices[BX->index + offStartY].texcoord;
1948                         }
1949
1950
1951                         Vector3 normal, s, t;
1952                         ArbitraryMeshVertex& v = m_tess.m_vertices[offStartY + BX->index];
1953                         Vector3& p = normal3f_to_vector3( v.normal );
1954                         Vector3& ps = normal3f_to_vector3( v.tangent );
1955                         Vector3& pt = normal3f_to_vector3( v.bitangent );
1956
1957                         if ( bTranspose ) {
1958                                 normal = vector3_cross( tangentV, tangentU );
1959                         }
1960                         else
1961                         {
1962                                 normal = vector3_cross( tangentU, tangentV );
1963                         }
1964                         normalise_safe( normal );
1965
1966                         ArbitraryMeshTriangle_calcTangents( a, b, c, s, t );
1967                         normalise_safe( s );
1968                         normalise_safe( t );
1969
1970                         if ( nFlagsX & AVERAGE ) {
1971                                 p = vector3_normalised( vector3_added( p, normal ) );
1972                                 ps = vector3_normalised( vector3_added( ps, s ) );
1973                                 pt = vector3_normalised( vector3_added( pt, t ) );
1974                         }
1975                         else
1976                         {
1977                                 p = normal;
1978                                 ps = s;
1979                                 pt = t;
1980                         }
1981                 }
1982
1983                 {
1984                         ArbitraryMeshVertex a, b, c;
1985                         Vector3 tangentU;
1986
1987                         if ( !( nFlagsX & DEGEN_2a ) || !( nFlagsX & DEGEN_2b ) ) {
1988                                 tangentU = vector3_subtracted( vertex_2_1, vertex_2_0 );
1989                                 a.vertex = vertex3f_for_vector3( vertex_2_0 );
1990                                 a.texcoord = texcoord2f_for_vector2( texcoord_2_0 );
1991                                 c.vertex = vertex3f_for_vector3( vertex_2_1 );
1992                                 c.texcoord = texcoord2f_for_vector2( texcoord_2_1 );
1993                         }
1994                         else if ( !( nFlagsX & DEGEN_1a ) || !( nFlagsX & DEGEN_1b ) ) {
1995                                 tangentU = vector3_subtracted( vertex_1_1, vertex_1_0 );
1996                                 a.vertex = vertex3f_for_vector3( vertex_1_0 );
1997                                 a.texcoord = texcoord2f_for_vector2( texcoord_1_0 );
1998                                 c.vertex = vertex3f_for_vector3( vertex_1_1 );
1999                                 c.texcoord = texcoord2f_for_vector2( texcoord_1_1 );
2000                         }
2001                         else
2002                         {
2003                                 tangentU = vector3_subtracted( vertex_0_1, vertex_0_0 );
2004                                 a.vertex = vertex3f_for_vector3( vertex_0_0 );
2005                                 a.texcoord = texcoord2f_for_vector2( texcoord_0_0 );
2006                                 c.vertex = vertex3f_for_vector3( vertex_0_1 );
2007                                 c.texcoord = texcoord2f_for_vector2( texcoord_0_1 );
2008                         }
2009
2010                         Vector3 tangentV;
2011
2012                         if ( ( nFlagsY & DEGEN_0b ) && ( nFlagsY & DEGEN_1b ) && ( nFlagsY & DEGEN_2b ) ) {
2013                                 tangentV = vector3_subtracted( tmp, vertex_for_index( m_tess.m_vertices, BX->index + offStartY ) );
2014                                 b.vertex = vertex3f_for_vector3( tmp ); //m_tess.m_vertices[BX->index + offStartY].vertex;
2015                                 b.texcoord = texcoord2f_for_vector2( texTmp ); //m_tess.m_vertices[BX->index + offStartY].texcoord;
2016                         }
2017                         else
2018                         {
2019                                 tangentV = vector3_subtracted( vertex_for_index( m_tess.m_vertices, BX->index + offEndY ), tmp );
2020                                 b.vertex = vertex3f_for_vector3( tmp ); //m_tess.m_vertices[BX->index + offEndY].vertex;
2021                                 b.texcoord = texcoord2f_for_vector2( texTmp ); //m_tess.m_vertices[BX->index + offEndY].texcoord;
2022                         }
2023
2024                         ArbitraryMeshVertex& v = m_tess.m_vertices[offEndY + BX->index];
2025                         Vector3& p = normal3f_to_vector3( v.normal );
2026                         Vector3& ps = normal3f_to_vector3( v.tangent );
2027                         Vector3& pt = normal3f_to_vector3( v.bitangent );
2028
2029                         if ( bTranspose ) {
2030                                 p = vector3_cross( tangentV, tangentU );
2031                         }
2032                         else
2033                         {
2034                                 p = vector3_cross( tangentU, tangentV );
2035                         }
2036                         normalise_safe( p );
2037
2038                         ArbitraryMeshTriangle_calcTangents( a, b, c, ps, pt );
2039                         normalise_safe( ps );
2040                         normalise_safe( pt );
2041                 }
2042         }
2043
2044
2045         newFlagsX = newFlagsY = 0;
2046
2047         if ( ( nFlagsX & DEGEN_0a ) && ( nFlagsX & DEGEN_0b ) ) {
2048                 newFlagsX |= DEGEN_0a;
2049                 newFlagsX |= DEGEN_0b;
2050         }
2051         if ( ( nFlagsX & DEGEN_1a ) && ( nFlagsX & DEGEN_1b ) ) {
2052                 newFlagsX |= DEGEN_1a;
2053                 newFlagsX |= DEGEN_1b;
2054         }
2055         if ( ( nFlagsX & DEGEN_2a ) && ( nFlagsX & DEGEN_2b ) ) {
2056                 newFlagsX |= DEGEN_2a;
2057                 newFlagsX |= DEGEN_2b;
2058         }
2059         if ( ( nFlagsY & DEGEN_0a ) && ( nFlagsY & DEGEN_1a ) && ( nFlagsY & DEGEN_2a ) ) {
2060                 newFlagsY |= DEGEN_0a;
2061                 newFlagsY |= DEGEN_1a;
2062                 newFlagsY |= DEGEN_2a;
2063         }
2064         if ( ( nFlagsY & DEGEN_0b ) && ( nFlagsY & DEGEN_1b ) && ( nFlagsY & DEGEN_2b ) ) {
2065                 newFlagsY |= DEGEN_0b;
2066                 newFlagsY |= DEGEN_1b;
2067                 newFlagsY |= DEGEN_2b;
2068         }
2069
2070
2071         //if((nFlagsX & DEGEN_0a) && (nFlagsX & DEGEN_1a) && (nFlagsX & DEGEN_2a)) { newFlagsX |= DEGEN_0a; newFlagsX |= DEGEN_1a; newFlagsX |= DEGEN_2a; }
2072         //if((nFlagsX & DEGEN_0b) && (nFlagsX & DEGEN_1b) && (nFlagsX & DEGEN_2b)) { newFlagsX |= DEGEN_0b; newFlagsX |= DEGEN_1b; newFlagsX |= DEGEN_2b; }
2073
2074         newFlagsX |= ( nFlagsX & SPLIT );
2075         newFlagsX |= ( nFlagsX & AVERAGE );
2076
2077         if ( !BezierCurveTree_isLeaf( BY ) ) {
2078                 {
2079                         int nTemp = newFlagsY;
2080
2081                         if ( ( nFlagsY & DEGEN_0a ) && ( nFlagsY & DEGEN_0b ) ) {
2082                                 newFlagsY |= DEGEN_0a;
2083                                 newFlagsY |= DEGEN_0b;
2084                         }
2085                         newFlagsY |= ( nFlagsY & SPLIT );
2086                         newFlagsY |= ( nFlagsY & AVERAGE );
2087
2088                         Vector3& p = vertex_for_index( m_tess.m_vertices, BX->index + BY->index );
2089                         Vector3 vTemp( p );
2090
2091                         Vector2& p2 = texcoord_for_index( m_tess.m_vertices, BX->index + BY->index );
2092                         Vector2 stTemp( p2 );
2093
2094                         TesselateSubMatrix( BY, BX->left,
2095                                                                 offStartY, offStartX,
2096                                                                 offEndY, BX->index,
2097                                                                 newFlagsY, newFlagsX,
2098                                                                 vertex_0_0, vertex_1_0, vertex_2_0,
2099                                                                 texcoord_0_0, texcoord_1_0, texcoord_2_0,
2100                                                                 !bTranspose );
2101
2102                         newFlagsY = nTemp;
2103                         p = vTemp;
2104                         p2 = stTemp;
2105                 }
2106
2107                 if ( ( nFlagsY & DEGEN_2a ) && ( nFlagsY & DEGEN_2b ) ) {
2108                         newFlagsY |= DEGEN_2a; newFlagsY |= DEGEN_2b;
2109                 }
2110
2111                 TesselateSubMatrix( BY, BX->right,
2112                                                         offStartY, BX->index,
2113                                                         offEndY, offEndX,
2114                                                         newFlagsY, newFlagsX,
2115                                                         vertex_0_1, vertex_1_1, vertex_2_1,
2116                                                         texcoord_0_1, texcoord_1_1, texcoord_2_1,
2117                                                         !bTranspose );
2118         }
2119         else
2120         {
2121                 if ( !BezierCurveTree_isLeaf( BX->left ) ) {
2122                         TesselateSubMatrix( BX->left,  BY,
2123                                                                 offStartX, offStartY,
2124                                                                 BX->index, offEndY,
2125                                                                 newFlagsX, newFlagsY,
2126                                                                 left, vertex_1_0, tmp,
2127                                                                 texLeft, texcoord_1_0, texTmp,
2128                                                                 bTranspose );
2129                 }
2130
2131                 if ( !BezierCurveTree_isLeaf( BX->right ) ) {
2132                         TesselateSubMatrix( BX->right, BY,
2133                                                                 BX->index, offStartY,
2134                                                                 offEndX, offEndY,
2135                                                                 newFlagsX, newFlagsY,
2136                                                                 tmp, vertex_1_1, right,
2137                                                                 texTmp, texcoord_1_1, texRight,
2138                                                                 bTranspose );
2139                 }
2140         }
2141
2142 }
2143
2144 void Patch::BuildTesselationCurves( EMatrixMajor major ){
2145         std::size_t nArrayStride, length, cross, strideU, strideV;
2146         switch ( major )
2147         {
2148         case ROW:
2149                 nArrayStride = 1;
2150                 length = ( m_width - 1 ) >> 1;
2151                 cross = m_height;
2152                 strideU = 1;
2153                 strideV = m_width;
2154
2155                 if ( !m_patchDef3 ) {
2156                         BezierCurveTreeArray_deleteAll( m_tess.m_curveTreeU );
2157                 }
2158
2159                 break;
2160         case COL:
2161                 nArrayStride = m_tess.m_nArrayWidth;
2162                 length = ( m_height - 1 ) >> 1;
2163                 cross = m_width;
2164                 strideU = m_width;
2165                 strideV = 1;
2166
2167                 if ( !m_patchDef3 ) {
2168                         BezierCurveTreeArray_deleteAll( m_tess.m_curveTreeV );
2169                 }
2170
2171                 break;
2172         default:
2173                 ERROR_MESSAGE( "neither row-major nor column-major" );
2174                 return;
2175         }
2176
2177         Array<std::size_t> arrayLength( length );
2178         Array<BezierCurveTree*> pCurveTree( length );
2179
2180         std::size_t nArrayLength = 1;
2181
2182         if ( m_patchDef3 ) {
2183                 for ( Array<std::size_t>::iterator i = arrayLength.begin(); i != arrayLength.end(); ++i )
2184                 {
2185                         *i = Array<std::size_t>::value_type( ( major == ROW ) ? m_subdivisions_x : m_subdivisions_y );
2186                         nArrayLength += *i;
2187                 }
2188         }
2189         else
2190         {
2191                 // create a list of the horizontal control curves in each column of sub-patches
2192                 // adaptively tesselate each horizontal control curve in the list
2193                 // create a binary tree representing the combined tesselation of the list
2194                 for ( std::size_t i = 0; i != length; ++i )
2195                 {
2196                         PatchControl* p1 = m_ctrlTransformed.data() + ( i * 2 * strideU );
2197                         GSList* pCurveList = 0;
2198                         for ( std::size_t j = 0; j < cross; j += 2 )
2199                         {
2200                                 PatchControl* p2 = p1 + strideV;
2201                                 PatchControl* p3 = p2 + strideV;
2202
2203                                 // directly taken from one row of control points
2204                                 {
2205                                         BezierCurve* pCurve = new BezierCurve;
2206                                         pCurve->crd = ( p1 + strideU )->m_vertex;
2207                                         pCurve->left = p1->m_vertex;
2208                                         pCurve->right = ( p1 + ( strideU << 1 ) )->m_vertex;
2209                                         pCurveList = g_slist_prepend( pCurveList, pCurve );
2210                                 }
2211
2212                                 if ( j + 2 >= cross ) {
2213                                         break;
2214                                 }
2215
2216                                 // interpolated from three columns of control points
2217                                 {
2218                                         BezierCurve* pCurve = new BezierCurve;
2219                                         pCurve->crd = vector3_mid( ( p1 + strideU )->m_vertex, ( p3 + strideU )->m_vertex );
2220                                         pCurve->left = vector3_mid( p1->m_vertex, p3->m_vertex );
2221                                         pCurve->right = vector3_mid( ( p1 + ( strideU << 1 ) )->m_vertex, ( p3 + ( strideU << 1 ) )->m_vertex );
2222
2223                                         pCurve->crd = vector3_mid( pCurve->crd, ( p2 + strideU )->m_vertex );
2224                                         pCurve->left = vector3_mid( pCurve->left, p2->m_vertex );
2225                                         pCurve->right = vector3_mid( pCurve->right, ( p2 + ( strideU << 1 ) )->m_vertex );
2226                                         pCurveList = g_slist_prepend( pCurveList, pCurve );
2227                                 }
2228
2229                                 p1 = p3;
2230                         }
2231
2232                         pCurveTree[i] = new BezierCurveTree;
2233                         BezierCurveTree_FromCurveList( pCurveTree[i], pCurveList );
2234                         for ( GSList* l = pCurveList; l != 0; l = g_slist_next( l ) )
2235                         {
2236                                 delete static_cast<BezierCurve*>( ( *l ).data );
2237                         }
2238                         g_slist_free( pCurveList );
2239
2240                         // set up array indices for binary tree
2241                         // accumulate subarray width
2242                         arrayLength[i] = Array<std::size_t>::value_type( BezierCurveTree_Setup( pCurveTree[i], nArrayLength, nArrayStride ) - ( nArrayLength - 1 ) );
2243                         // accumulate total array width
2244                         nArrayLength += arrayLength[i];
2245                 }
2246         }
2247
2248         switch ( major )
2249         {
2250         case ROW:
2251                 m_tess.m_nArrayWidth = nArrayLength;
2252                 std::swap( m_tess.m_arrayWidth, arrayLength );
2253
2254                 if ( !m_patchDef3 ) {
2255                         std::swap( m_tess.m_curveTreeU, pCurveTree );
2256                 }
2257                 break;
2258         case COL:
2259                 m_tess.m_nArrayHeight = nArrayLength;
2260                 std::swap( m_tess.m_arrayHeight, arrayLength );
2261
2262                 if ( !m_patchDef3 ) {
2263                         std::swap( m_tess.m_curveTreeV, pCurveTree );
2264                 }
2265                 break;
2266         }
2267 }
2268
2269 inline void vertex_assign_ctrl( ArbitraryMeshVertex& vertex, const PatchControl& ctrl ){
2270         vertex.vertex = vertex3f_for_vector3( ctrl.m_vertex );
2271         vertex.texcoord = texcoord2f_for_vector2( ctrl.m_texcoord );
2272 }
2273
2274 inline void vertex_clear_normal( ArbitraryMeshVertex& vertex ){
2275         vertex.normal = Normal3f( 0, 0, 0 );
2276         vertex.tangent = Normal3f( 0, 0, 0 );
2277         vertex.bitangent = Normal3f( 0, 0, 0 );
2278 }
2279
2280 inline void tangents_remove_degenerate( Vector3 tangents[6], Vector2 textureTangents[6], unsigned int flags ){
2281         if ( flags & DEGEN_0a ) {
2282                 const std::size_t i =
2283                         ( flags & DEGEN_0b )
2284                         ? ( flags & DEGEN_1a )
2285                         ? ( flags & DEGEN_1b )
2286                         ? ( flags & DEGEN_2a )
2287                         ? 5
2288                         : 4
2289                         : 3
2290                         : 2
2291                         : 1;
2292                 tangents[0] = tangents[i];
2293                 textureTangents[0] = textureTangents[i];
2294         }
2295         if ( flags & DEGEN_0b ) {
2296                 const std::size_t i =
2297                         ( flags & DEGEN_0a )
2298                         ? ( flags & DEGEN_1b )
2299                         ? ( flags & DEGEN_1a )
2300                         ? ( flags & DEGEN_2b )
2301                         ? 4
2302                         : 5
2303                         : 2
2304                         : 3
2305                         : 0;
2306                 tangents[1] = tangents[i];
2307                 textureTangents[1] = textureTangents[i];
2308         }
2309         if ( flags & DEGEN_2a ) {
2310                 const std::size_t i =
2311                         ( flags & DEGEN_2b )
2312                         ? ( flags & DEGEN_1a )
2313                         ? ( flags & DEGEN_1b )
2314                         ? ( flags & DEGEN_0a )
2315                         ? 1
2316                         : 0
2317                         : 3
2318                         : 2
2319                         : 5;
2320                 tangents[4] = tangents[i];
2321                 textureTangents[4] = textureTangents[i];
2322         }
2323         if ( flags & DEGEN_2b ) {
2324                 const std::size_t i =
2325                         ( flags & DEGEN_2a )
2326                         ? ( flags & DEGEN_1b )
2327                         ? ( flags & DEGEN_1a )
2328                         ? ( flags & DEGEN_0b )
2329                         ? 0
2330                         : 1
2331                         : 2
2332                         : 3
2333                         : 4;
2334                 tangents[5] = tangents[i];
2335                 textureTangents[5] = textureTangents[i];
2336         }
2337 }
2338
2339 void bestTangents00( unsigned int degenerateFlags, double dot, double length, std::size_t& index0, std::size_t& index1 ){
2340         if ( fabs( dot + length ) < 0.001 ) { // opposing direction = degenerate
2341                 if ( !( degenerateFlags & DEGEN_1a ) ) { // if this tangent is degenerate we cannot use it
2342                         index0 = 2;
2343                         index1 = 0;
2344                 }
2345                 else if ( !( degenerateFlags & DEGEN_0b ) ) {
2346                         index0 = 0;
2347                         index1 = 1;
2348                 }
2349                 else
2350                 {
2351                         index0 = 1;
2352                         index1 = 0;
2353                 }
2354         }
2355         else if ( fabs( dot - length ) < 0.001 ) { // same direction = degenerate
2356                 if ( degenerateFlags & DEGEN_0b ) {
2357                         index0 = 0;
2358                         index1 = 1;
2359                 }
2360                 else
2361                 {
2362                         index0 = 1;
2363                         index1 = 0;
2364                 }
2365         }
2366 }
2367
2368 void bestTangents01( unsigned int degenerateFlags, double dot, double length, std::size_t& index0, std::size_t& index1 ){
2369         if ( fabs( dot - length ) < 0.001 ) { // same direction = degenerate
2370                 if ( !( degenerateFlags & DEGEN_1a ) ) { // if this tangent is degenerate we cannot use it
2371                         index0 = 2;
2372                         index1 = 1;
2373                 }
2374                 else if ( !( degenerateFlags & DEGEN_2b ) ) {
2375                         index0 = 4;
2376                         index1 = 0;
2377                 }
2378                 else
2379                 {
2380                         index0 = 5;
2381                         index1 = 1;
2382                 }
2383         }
2384         else if ( fabs( dot + length ) < 0.001 ) { // opposing direction = degenerate
2385                 if ( degenerateFlags & DEGEN_2b ) {
2386                         index0 = 4;
2387                         index1 = 0;
2388                 }
2389                 else
2390                 {
2391                         index0 = 5;
2392                         index1 = 1;
2393                 }
2394         }
2395 }
2396
2397 void bestTangents10( unsigned int degenerateFlags, double dot, double length, std::size_t& index0, std::size_t& index1 ){
2398         if ( fabs( dot - length ) < 0.001 ) { // same direction = degenerate
2399                 if ( !( degenerateFlags & DEGEN_1b ) ) { // if this tangent is degenerate we cannot use it
2400                         index0 = 3;
2401                         index1 = 4;
2402                 }
2403                 else if ( !( degenerateFlags & DEGEN_0a ) ) {
2404                         index0 = 1;
2405                         index1 = 5;
2406                 }
2407                 else
2408                 {
2409                         index0 = 0;
2410                         index1 = 4;
2411                 }
2412         }
2413         else if ( fabs( dot + length ) < 0.001 ) { // opposing direction = degenerate
2414                 if ( degenerateFlags & DEGEN_0a ) {
2415                         index0 = 1;
2416                         index1 = 5;
2417                 }
2418                 else
2419                 {
2420                         index0 = 0;
2421                         index1 = 4;
2422                 }
2423         }
2424 }
2425
2426 void bestTangents11( unsigned int degenerateFlags, double dot, double length, std::size_t& index0, std::size_t& index1 ){
2427         if ( fabs( dot + length ) < 0.001 ) { // opposing direction = degenerate
2428                 if ( !( degenerateFlags & DEGEN_1b ) ) { // if this tangent is degenerate we cannot use it
2429                         index0 = 3;
2430                         index1 = 5;
2431                 }
2432                 else if ( !( degenerateFlags & DEGEN_2a ) ) {
2433                         index0 = 5;
2434                         index1 = 4;
2435                 }
2436                 else
2437                 {
2438                         index0 = 4;
2439                         index1 = 5;
2440                 }
2441         }
2442         else if ( fabs( dot - length ) < 0.001 ) { // same direction = degenerate
2443                 if ( degenerateFlags & DEGEN_2a ) {
2444                         index0 = 5;
2445                         index1 = 4;
2446                 }
2447                 else
2448                 {
2449                         index0 = 4;
2450                         index1 = 5;
2451                 }
2452         }
2453 }
2454
2455 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 ){
2456         {
2457                 Vector3 normal( vector3_cross( tangentX[index0], tangentY[index1] ) );
2458                 if ( !vector3_equal( normal, g_vector3_identity ) ) {
2459                         vector3_add( normal_for_index( m_tess.m_vertices, index ), vector3_normalised( normal ) );
2460                 }
2461         }
2462
2463         {
2464                 ArbitraryMeshVertex a, b, c;
2465                 a.vertex = Vertex3f( 0, 0, 0 );
2466                 a.texcoord = TexCoord2f( 0, 0 );
2467                 b.vertex = vertex3f_for_vector3( tangentX[index0] );
2468                 b.texcoord = texcoord2f_for_vector2( tangentS[index0] );
2469                 c.vertex = vertex3f_for_vector3( tangentY[index1] );
2470                 c.texcoord = texcoord2f_for_vector2( tangentT[index1] );
2471
2472                 Vector3 s, t;
2473                 ArbitraryMeshTriangle_calcTangents( a, b, c, s, t );
2474                 if ( !vector3_equal( s, g_vector3_identity ) ) {
2475                         vector3_add( tangent_for_index( m_tess.m_vertices, index ), vector3_normalised( s ) );
2476                 }
2477                 if ( !vector3_equal( t, g_vector3_identity ) ) {
2478                         vector3_add( bitangent_for_index( m_tess.m_vertices, index ), vector3_normalised( t ) );
2479                 }
2480         }
2481 }
2482
2483 const std::size_t PATCH_MAX_VERTEX_ARRAY = 1048576;
2484
2485 void Patch::BuildVertexArray(){
2486         const std::size_t strideU = 1;
2487         const std::size_t strideV = m_width;
2488
2489         const std::size_t numElems = m_tess.m_nArrayWidth * m_tess.m_nArrayHeight; // total number of elements in vertex array
2490
2491         const bool bWidthStrips = ( m_tess.m_nArrayWidth >= m_tess.m_nArrayHeight ); // decide if horizontal strips are longer than vertical
2492
2493
2494         // allocate vertex, normal, texcoord and primitive-index arrays
2495         m_tess.m_vertices.resize( numElems );
2496         m_tess.m_indices.resize( m_tess.m_nArrayWidth * 2 * ( m_tess.m_nArrayHeight - 1 ) );
2497
2498         // set up strip indices
2499         if ( bWidthStrips ) {
2500                 m_tess.m_numStrips = m_tess.m_nArrayHeight - 1;
2501                 m_tess.m_lenStrips = m_tess.m_nArrayWidth * 2;
2502
2503                 for ( std::size_t i = 0; i < m_tess.m_nArrayWidth; i++ )
2504                 {
2505                         for ( std::size_t j = 0; j < m_tess.m_numStrips; j++ )
2506                         {
2507                                 m_tess.m_indices[( j * m_tess.m_lenStrips ) + i * 2] = RenderIndex( j * m_tess.m_nArrayWidth + i );
2508                                 m_tess.m_indices[( j * m_tess.m_lenStrips ) + i * 2 + 1] = RenderIndex( ( j + 1 ) * m_tess.m_nArrayWidth + i );
2509                                 // reverse because radiant uses CULL_FRONT
2510                                 //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2+1] = RenderIndex(j*m_tess.m_nArrayWidth+i);
2511                                 //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2] = RenderIndex((j+1)*m_tess.m_nArrayWidth+i);
2512                         }
2513                 }
2514         }
2515         else
2516         {
2517                 m_tess.m_numStrips = m_tess.m_nArrayWidth - 1;
2518                 m_tess.m_lenStrips = m_tess.m_nArrayHeight * 2;
2519
2520                 for ( std::size_t i = 0; i < m_tess.m_nArrayHeight; i++ )
2521                 {
2522                         for ( std::size_t j = 0; j < m_tess.m_numStrips; j++ )
2523                         {
2524                                 m_tess.m_indices[( j * m_tess.m_lenStrips ) + i * 2] = RenderIndex( ( ( m_tess.m_nArrayHeight - 1 ) - i ) * m_tess.m_nArrayWidth + j );
2525                                 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 );
2526                                 // reverse because radiant uses CULL_FRONT
2527                                 //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2+1] = RenderIndex(((m_tess.m_nArrayHeight-1)-i)*m_tess.m_nArrayWidth+j);
2528                                 //m_tess.m_indices[(j*m_tess.m_lenStrips)+i*2] = RenderIndex(((m_tess.m_nArrayHeight-1)-i)*m_tess.m_nArrayWidth+j+1);
2529
2530                         }
2531                 }
2532         }
2533
2534         {
2535                 PatchControlIter pCtrl = m_ctrlTransformed.data();
2536                 for ( std::size_t j = 0, offStartY = 0; j + 1 < m_height; j += 2, pCtrl += ( strideU + strideV ) )
2537                 {
2538                         // set up array offsets for this sub-patch
2539                         const bool leafY = ( m_patchDef3 ) ? false : BezierCurveTree_isLeaf( m_tess.m_curveTreeV[j >> 1] );
2540                         const std::size_t offMidY = ( m_patchDef3 ) ? 0 : m_tess.m_curveTreeV[j >> 1]->index;
2541                         const std::size_t widthY = m_tess.m_arrayHeight[j >> 1] * m_tess.m_nArrayWidth;
2542                         const std::size_t offEndY = offStartY + widthY;
2543
2544                         for ( std::size_t i = 0, offStartX = 0; i + 1 < m_width; i += 2, pCtrl += ( strideU << 1 ) )
2545                         {
2546                                 const bool leafX = ( m_patchDef3 ) ? false : BezierCurveTree_isLeaf( m_tess.m_curveTreeU[i >> 1] );
2547                                 const std::size_t offMidX = ( m_patchDef3 ) ? 0 : m_tess.m_curveTreeU[i >> 1]->index;
2548                                 const std::size_t widthX = m_tess.m_arrayWidth[i >> 1];
2549                                 const std::size_t offEndX = offStartX + widthX;
2550
2551                                 PatchControl *subMatrix[3][3];
2552                                 subMatrix[0][0] = pCtrl;
2553                                 subMatrix[0][1] = subMatrix[0][0] + strideU;
2554                                 subMatrix[0][2] = subMatrix[0][1] + strideU;
2555                                 subMatrix[1][0] = subMatrix[0][0] + strideV;
2556                                 subMatrix[1][1] = subMatrix[1][0] + strideU;
2557                                 subMatrix[1][2] = subMatrix[1][1] + strideU;
2558                                 subMatrix[2][0] = subMatrix[1][0] + strideV;
2559                                 subMatrix[2][1] = subMatrix[2][0] + strideU;
2560                                 subMatrix[2][2] = subMatrix[2][1] + strideU;
2561
2562                                 // assign on-patch control points to vertex array
2563                                 if ( i == 0 && j == 0 ) {
2564                                         vertex_clear_normal( m_tess.m_vertices[offStartX + offStartY] );
2565                                 }
2566                                 vertex_assign_ctrl( m_tess.m_vertices[offStartX + offStartY], *subMatrix[0][0] );
2567                                 if ( j == 0 ) {
2568                                         vertex_clear_normal( m_tess.m_vertices[offEndX + offStartY] );
2569                                 }
2570                                 vertex_assign_ctrl( m_tess.m_vertices[offEndX + offStartY], *subMatrix[0][2] );
2571                                 if ( i == 0 ) {
2572                                         vertex_clear_normal( m_tess.m_vertices[offStartX + offEndY] );
2573                                 }
2574                                 vertex_assign_ctrl( m_tess.m_vertices[offStartX + offEndY], *subMatrix[2][0] );
2575
2576                                 vertex_clear_normal( m_tess.m_vertices[offEndX + offEndY] );
2577                                 vertex_assign_ctrl( m_tess.m_vertices[offEndX + offEndY], *subMatrix[2][2] );
2578
2579                                 if ( !m_patchDef3 ) {
2580                                         // assign remaining control points to vertex array
2581                                         if ( !leafX ) {
2582                                                 vertex_assign_ctrl( m_tess.m_vertices[offMidX + offStartY], *subMatrix[0][1] );
2583                                                 vertex_assign_ctrl( m_tess.m_vertices[offMidX + offEndY], *subMatrix[2][1] );
2584                                         }
2585                                         if ( !leafY ) {
2586                                                 vertex_assign_ctrl( m_tess.m_vertices[offStartX + offMidY], *subMatrix[1][0] );
2587                                                 vertex_assign_ctrl( m_tess.m_vertices[offEndX + offMidY], *subMatrix[1][2] );
2588
2589                                                 if ( !leafX ) {
2590                                                         vertex_assign_ctrl( m_tess.m_vertices[offMidX + offMidY], *subMatrix[1][1] );
2591                                                 }
2592                                         }
2593                                 }
2594
2595                                 // test all 12 edges for degeneracy
2596                                 unsigned int nFlagsX = subarray_get_degen( pCtrl, strideU, strideV );
2597                                 unsigned int nFlagsY = subarray_get_degen( pCtrl, strideV, strideU );
2598                                 Vector3 tangentX[6], tangentY[6];
2599                                 Vector2 tangentS[6], tangentT[6];
2600
2601                                 // set up tangents for each of the 12 edges if they were not degenerate
2602                                 if ( !( nFlagsX & DEGEN_0a ) ) {
2603                                         tangentX[0] = vector3_subtracted( subMatrix[0][1]->m_vertex, subMatrix[0][0]->m_vertex );
2604                                         tangentS[0] = vector2_subtracted( subMatrix[0][1]->m_texcoord, subMatrix[0][0]->m_texcoord );
2605                                 }
2606                                 if ( !( nFlagsX & DEGEN_0b ) ) {
2607                                         tangentX[1] = vector3_subtracted( subMatrix[0][2]->m_vertex, subMatrix[0][1]->m_vertex );
2608                                         tangentS[1] = vector2_subtracted( subMatrix[0][2]->m_texcoord, subMatrix[0][1]->m_texcoord );
2609                                 }
2610                                 if ( !( nFlagsX & DEGEN_1a ) ) {
2611                                         tangentX[2] = vector3_subtracted( subMatrix[1][1]->m_vertex, subMatrix[1][0]->m_vertex );
2612                                         tangentS[2] = vector2_subtracted( subMatrix[1][1]->m_texcoord, subMatrix[1][0]->m_texcoord );
2613                                 }
2614                                 if ( !( nFlagsX & DEGEN_1b ) ) {
2615                                         tangentX[3] = vector3_subtracted( subMatrix[1][2]->m_vertex, subMatrix[1][1]->m_vertex );
2616                                         tangentS[3] = vector2_subtracted( subMatrix[1][2]->m_texcoord, subMatrix[1][1]->m_texcoord );
2617                                 }
2618                                 if ( !( nFlagsX & DEGEN_2a ) ) {
2619                                         tangentX[4] = vector3_subtracted( subMatrix[2][1]->m_vertex, subMatrix[2][0]->m_vertex );
2620                                         tangentS[4] = vector2_subtracted( subMatrix[2][1]->m_texcoord, subMatrix[2][0]->m_texcoord );
2621                                 }
2622                                 if ( !( nFlagsX & DEGEN_2b ) ) {
2623                                         tangentX[5] = vector3_subtracted( subMatrix[2][2]->m_vertex, subMatrix[2][1]->m_vertex );
2624                                         tangentS[5] = vector2_subtracted( subMatrix[2][2]->m_texcoord, subMatrix[2][1]->m_texcoord );
2625                                 }
2626
2627                                 if ( !( nFlagsY & DEGEN_0a ) ) {
2628                                         tangentY[0] = vector3_subtracted( subMatrix[1][0]->m_vertex, subMatrix[0][0]->m_vertex );
2629                                         tangentT[0] = vector2_subtracted( subMatrix[1][0]->m_texcoord, subMatrix[0][0]->m_texcoord );
2630                                 }
2631                                 if ( !( nFlagsY & DEGEN_0b ) ) {
2632                                         tangentY[1] = vector3_subtracted( subMatrix[2][0]->m_vertex, subMatrix[1][0]->m_vertex );
2633                                         tangentT[1] = vector2_subtracted( subMatrix[2][0]->m_texcoord, subMatrix[1][0]->m_texcoord );
2634                                 }
2635                                 if ( !( nFlagsY & DEGEN_1a ) ) {
2636                                         tangentY[2] = vector3_subtracted( subMatrix[1][1]->m_vertex, subMatrix[0][1]->m_vertex );
2637                                         tangentT[2] = vector2_subtracted( subMatrix[1][1]->m_texcoord, subMatrix[0][1]->m_texcoord );
2638                                 }
2639                                 if ( !( nFlagsY & DEGEN_1b ) ) {
2640                                         tangentY[3] = vector3_subtracted( subMatrix[2][1]->m_vertex, subMatrix[1][1]->m_vertex );
2641                                         tangentT[3] = vector2_subtracted( subMatrix[2][1]->m_texcoord, subMatrix[1][1]->m_texcoord );
2642                                 }
2643                                 if ( !( nFlagsY & DEGEN_2a ) ) {
2644                                         tangentY[4] = vector3_subtracted( subMatrix[1][2]->m_vertex, subMatrix[0][2]->m_vertex );
2645                                         tangentT[4] = vector2_subtracted( subMatrix[1][2]->m_texcoord, subMatrix[0][2]->m_texcoord );
2646                                 }
2647                                 if ( !( nFlagsY & DEGEN_2b ) ) {
2648                                         tangentY[5] = vector3_subtracted( subMatrix[2][2]->m_vertex, subMatrix[1][2]->m_vertex );
2649                                         tangentT[5] = vector2_subtracted( subMatrix[2][2]->m_texcoord, subMatrix[1][2]->m_texcoord );
2650                                 }
2651
2652                                 // set up remaining edge tangents by borrowing the tangent from the closest parallel non-degenerate edge
2653                                 tangents_remove_degenerate( tangentX, tangentS, nFlagsX );
2654                                 tangents_remove_degenerate( tangentY, tangentT, nFlagsY );
2655
2656                                 {
2657                                         // x=0, y=0
2658                                         std::size_t index = offStartX + offStartY;
2659                                         std::size_t index0 = 0;
2660                                         std::size_t index1 = 0;
2661
2662                                         double dot = vector3_dot( tangentX[index0], tangentY[index1] );
2663                                         double length = vector3_length( tangentX[index0] ) * vector3_length( tangentY[index1] );
2664
2665                                         bestTangents00( nFlagsX, dot, length, index0, index1 );
2666
2667                                         accumulateVertexTangentSpace( index, tangentX, tangentY, tangentS, tangentT, index0, index1 );
2668                                 }
2669
2670                                 {
2671                                         // x=1, y=0
2672                                         std::size_t index = offEndX + offStartY;
2673                                         std::size_t index0 = 1;
2674                                         std::size_t index1 = 4;
2675
2676                                         double dot = vector3_dot( tangentX[index0],tangentY[index1] );
2677                                         double length = vector3_length( tangentX[index0] ) * vector3_length( tangentY[index1] );
2678
2679                                         bestTangents10( nFlagsX, dot, length, index0, index1 );
2680
2681                                         accumulateVertexTangentSpace( index, tangentX, tangentY, tangentS, tangentT, index0, index1 );
2682                                 }
2683
2684                                 {
2685                                         // x=0, y=1
2686                                         std::size_t index = offStartX + offEndY;
2687                                         std::size_t index0 = 4;
2688                                         std::size_t index1 = 1;
2689
2690                                         double dot = vector3_dot( tangentX[index0], tangentY[index1] );
2691                                         double length = vector3_length( tangentX[index1] ) * vector3_length( tangentY[index1] );
2692
2693                                         bestTangents01( nFlagsX, dot, length, index0, index1 );
2694
2695                                         accumulateVertexTangentSpace( index, tangentX, tangentY, tangentS, tangentT, index0, index1 );
2696                                 }
2697
2698                                 {
2699                                         // x=1, y=1
2700                                         std::size_t index = offEndX + offEndY;
2701                                         std::size_t index0 = 5;
2702                                         std::size_t index1 = 5;
2703
2704                                         double dot = vector3_dot( tangentX[index0],tangentY[index1] );
2705                                         double length = vector3_length( tangentX[index0] ) * vector3_length( tangentY[index1] );
2706
2707                                         bestTangents11( nFlagsX, dot, length, index0, index1 );
2708
2709                                         accumulateVertexTangentSpace( index, tangentX, tangentY, tangentS, tangentT, index0, index1 );
2710                                 }
2711
2712                                 //normalise normals that won't be accumulated again
2713                                 if ( i != 0 || j != 0 ) {
2714                                         normalise_safe( normal_for_index( m_tess.m_vertices, offStartX + offStartY ) );
2715                                         normalise_safe( tangent_for_index( m_tess.m_vertices, offStartX + offStartY ) );
2716                                         normalise_safe( bitangent_for_index( m_tess.m_vertices, offStartX + offStartY ) );
2717                                 }
2718                                 if ( i + 3 == m_width ) {
2719                                         normalise_safe( normal_for_index( m_tess.m_vertices, offEndX + offStartY ) );
2720                                         normalise_safe( tangent_for_index( m_tess.m_vertices, offEndX + offStartY ) );
2721                                         normalise_safe( bitangent_for_index( m_tess.m_vertices, offEndX + offStartY ) );
2722                                 }
2723                                 if ( j + 3 == m_height ) {
2724                                         normalise_safe( normal_for_index( m_tess.m_vertices, offStartX + offEndY ) );
2725                                         normalise_safe( tangent_for_index( m_tess.m_vertices, offStartX + offEndY ) );
2726                                         normalise_safe( bitangent_for_index( m_tess.m_vertices, offStartX + offEndY ) );
2727                                 }
2728                                 if ( i + 3 == m_width && j + 3 == m_height ) {
2729                                         normalise_safe( normal_for_index( m_tess.m_vertices, offEndX + offEndY ) );
2730                                         normalise_safe( tangent_for_index( m_tess.m_vertices, offEndX + offEndY ) );
2731                                         normalise_safe( bitangent_for_index( m_tess.m_vertices, offEndX + offEndY ) );
2732                                 }
2733
2734                                 // set flags to average normals between shared edges
2735                                 if ( j != 0 ) {
2736                                         nFlagsX |= AVERAGE;
2737                                 }
2738                                 if ( i != 0 ) {
2739                                         nFlagsY |= AVERAGE;
2740                                 }
2741                                 // set flags to save evaluating shared edges twice
2742                                 nFlagsX |= SPLIT;
2743                                 nFlagsY |= SPLIT;
2744
2745                                 // if the patch is curved.. tesselate recursively
2746                                 // use the relevant control curves for this sub-patch
2747                                 if ( m_patchDef3 ) {
2748                                         TesselateSubMatrixFixed( m_tess.m_vertices.data() + offStartX + offStartY, 1, m_tess.m_nArrayWidth, nFlagsX, nFlagsY, subMatrix );
2749                                 }
2750                                 else
2751                                 {
2752                                         if ( !leafX ) {
2753                                                 TesselateSubMatrix( m_tess.m_curveTreeU[i >> 1], m_tess.m_curveTreeV[j >> 1],
2754                                                                                         offStartX, offStartY, offEndX, offEndY, // array offsets
2755                                                                                         nFlagsX, nFlagsY,
2756                                                                                         subMatrix[1][0]->m_vertex, subMatrix[1][1]->m_vertex, subMatrix[1][2]->m_vertex,
2757                                                                                         subMatrix[1][0]->m_texcoord, subMatrix[1][1]->m_texcoord, subMatrix[1][2]->m_texcoord,
2758                                                                                         false );
2759                                         }
2760                                         else if ( !leafY ) {
2761                                                 TesselateSubMatrix( m_tess.m_curveTreeV[j >> 1], m_tess.m_curveTreeU[i >> 1],
2762                                                                                         offStartY, offStartX, offEndY, offEndX, // array offsets
2763                                                                                         nFlagsY, nFlagsX,
2764                                                                                         subMatrix[0][1]->m_vertex, subMatrix[1][1]->m_vertex, subMatrix[2][1]->m_vertex,
2765                                                                                         subMatrix[0][1]->m_texcoord, subMatrix[1][1]->m_texcoord, subMatrix[2][1]->m_texcoord,
2766                                                                                         true );
2767                                         }
2768                                 }
2769
2770                                 offStartX = offEndX;
2771                         }
2772                         offStartY = offEndY;
2773                 }
2774         }
2775 }
2776
2777
2778
2779 class PatchFilterWrapper : public Filter
2780 {
2781 bool m_active;
2782 bool m_invert;
2783 PatchFilter& m_filter;
2784 public:
2785 PatchFilterWrapper( PatchFilter& filter, bool invert ) : m_invert( invert ), m_filter( filter ){
2786 }
2787 void setActive( bool active ){
2788         m_active = active;
2789 }
2790 bool active(){
2791         return m_active;
2792 }
2793 bool filter( const Patch& patch ){
2794         return m_invert ^ m_filter.filter( patch );
2795 }
2796 };
2797
2798
2799 typedef std::list<PatchFilterWrapper> PatchFilters;
2800 PatchFilters g_patchFilters;
2801
2802 void add_patch_filter( PatchFilter& filter, int mask, bool invert ){
2803         g_patchFilters.push_back( PatchFilterWrapper( filter, invert ) );
2804         GlobalFilterSystem().addFilter( g_patchFilters.back(), mask );
2805 }
2806
2807 bool patch_filtered( Patch& patch ){
2808         for ( PatchFilters::iterator i = g_patchFilters.begin(); i != g_patchFilters.end(); ++i )
2809         {
2810                 if ( ( *i ).active() && ( *i ).filter( patch ) ) {
2811                         return true;
2812                 }
2813         }
2814         return false;
2815 }