radiant/patch.cpp

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