radiant/patch.cpp

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