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