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