src/libnurbs/internals/mesher.cc

   1 /*
   2 ** License Applicability. Except to the extent portions of this file are
   3 ** made subject to an alternative license as permitted in the SGI Free
   4 ** Software License B, Version 1.1 (the "License"), the contents of this
   5 ** file are subject only to the provisions of the License. You may not use
   6 ** this file except in compliance with the License. You may obtain a copy
   7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
   8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
   9 **
  10 ** http://oss.sgi.com/projects/FreeB
  11 **
  12 ** Note that, as provided in the License, the Software is distributed on an
  13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
  14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
  15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
  16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
  17 **
  18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
  19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
  20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
  21 ** Copyright in any portions created by third parties is as indicated
  22 ** elsewhere herein. All Rights Reserved.
  23 **
  24 ** Additional Notice Provisions: The application programming interfaces
  25 ** established by SGI in conjunction with the Original Code are The
  26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
  27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
  28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
  29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
  30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
  31 ** published by SGI, but has not been independently verified as being
  32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
  33 */
  34
  35 /*
  36  * mesher.c++
  37  *
  38  */
  39
  40 #include "glimports.h"
  41 #include "myassert.h"
  42 #include "mystdio.h"
  43 #include "gridvertex.h"
  44 #include "gridtrimvertex.h"
  45 #include "jarcloc.h"
  46 #include "gridline.h"
  47 #include "trimline.h"
  48 #include "uarray.h"
  49 #include "backend.h"
  50 #include "mesher.h"
  51
  52
  53 const float Mesher::ZERO = 0.0;
  54
  55 Mesher::Mesher( Backend& b )
  56         : backend( b ),
  57         p( sizeof( GridTrimVertex ), 100, "GridTrimVertexPool" )
  58 {
  59     stacksize = 0;
  60     vdata = 0;
  61     last[0] = 0;
  62     last[1] = 0;
  63     itop = 0;
  64     lastedge = 0; //needed to prevent purify UMR
  65 }
  66
  67 Mesher::~Mesher( void )
  68 {
  69     if( vdata ) delete[] vdata;
  70 }
  71
  72 void
  73 Mesher::init( unsigned int npts )
  74 {
  75     p.clear();
  76     if( stacksize < npts ) {
  77         stacksize = 2 * npts;
  78         if( vdata ) delete[] vdata;
  79         vdata = new GridTrimVertex_p[stacksize];
  80     }
  81 }
  82
  83 inline void
  84 Mesher::push( GridTrimVertex *gt )
  85 {
  86     assert( itop+1 != (int)stacksize );
  87     vdata[++itop] = gt;
  88 }
  89
  90 inline void
  91 Mesher::pop( long )
  92 {
  93 }
  94
  95 inline void
  96 Mesher::openMesh()
  97 {
  98     backend.bgntmesh( "addedge" );
  99 }
 100
 101 inline void
 102 Mesher::closeMesh()
 103 {
 104     backend.endtmesh();
 105 }
 106
 107 inline void
 108 Mesher::swapMesh()
 109 {
 110     backend.swaptmesh();
 111 }
 112
 113 inline void
 114 Mesher::clearStack()
 115 {
 116     itop = -1;
 117     last[0] = 0;
 118 }
 119
 120 void
 121 Mesher::finishLower( GridTrimVertex *gtlower )
 122 {
 123     for( push(gtlower);
 124          nextlower( gtlower=new(p) GridTrimVertex );
 125          push(gtlower) )
 126             addLower();
 127     addLast();
 128 }
 129
 130 void
 131 Mesher::finishUpper( GridTrimVertex *gtupper )
 132 {
 133     for( push(gtupper);
 134          nextupper( gtupper=new(p) GridTrimVertex );
 135          push(gtupper) )
 136             addUpper();
 137     addLast();
 138 }
 139
 140 void
 141 Mesher::mesh( void )
 142 {
 143     GridTrimVertex *gtlower, *gtupper;
 144
 145     Hull::init( );
 146     nextupper( gtupper = new(p) GridTrimVertex );
 147     nextlower( gtlower = new(p) GridTrimVertex );
 148
 149     clearStack();
 150     openMesh();
 151     push(gtupper);
 152
 153     nextupper( gtupper = new(p) GridTrimVertex );
 154     nextlower( gtlower );
 155
 156     assert( gtupper->t && gtlower->t );
 157
 158     if( gtupper->t->param[0] < gtlower->t->param[0] ) {
 159         push(gtupper);
 160         lastedge = 1;
 161         if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
 162             finishLower(gtlower);
 163             return;
 164         }
 165     } else if( gtupper->t->param[0] > gtlower->t->param[0] ) {
 166         push(gtlower);
 167         lastedge = 0;
 168         if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
 169             finishUpper(gtupper);
 170             return;
 171         }
 172     } else {
 173         if( lastedge == 0 ) {
 174             push(gtupper);
 175             lastedge = 1;
 176             if( nextupper(gtupper=new(p) GridTrimVertex) == 0 ) {
 177                 finishLower(gtlower);
 178                 return;
 179             }
 180         } else {
 181             push(gtlower);
 182             lastedge = 0;
 183             if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
 184                 finishUpper(gtupper);
 185                 return;
 186             }
 187         }
 188     }
 189
 190     while ( 1 ) {
 191         if( gtupper->t->param[0] < gtlower->t->param[0] ) {
 192             push(gtupper);
 193             addUpper();
 194             if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
 195                 finishLower(gtlower);
 196                 return;
 197             }
 198         } else if( gtupper->t->param[0] > gtlower->t->param[0] ) {
 199             push(gtlower);
 200             addLower();
 201             if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
 202                 finishUpper(gtupper);
 203                 return;
 204             }
 205         } else {
 206             if( lastedge == 0 ) {
 207                 push(gtupper);
 208                 addUpper();
 209                 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
 210                     finishLower(gtlower);
 211                     return;
 212                 }
 213             } else {
 214                 push(gtlower);
 215                 addLower();
 216                 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
 217                     finishUpper(gtupper);
 218                     return;
 219                 }
 220             }
 221         }
 222     }
 223 }
 224
 225 inline int
 226 Mesher::isCcw( int ilast )
 227 {
 228     REAL area = det3( vdata[ilast]->t, vdata[itop-1]->t, vdata[itop-2]->t );
 229     return (area < ZERO) ? 0 : 1;
 230 }
 231
 232 inline int
 233 Mesher::isCw( int ilast  )
 234 {
 235     REAL area = det3( vdata[ilast]->t, vdata[itop-1]->t, vdata[itop-2]->t );
 236     return (area > -ZERO) ? 0 : 1;
 237 }
 238
 239 inline int
 240 Mesher::equal( int x, int y )
 241 {
 242     return( last[0] == vdata[x] && last[1] == vdata[y] );
 243 }
 244
 245 inline void
 246 Mesher::copy( int x, int y )
 247 {
 248     last[0] = vdata[x]; last[1] = vdata[y];
 249 }
 250
 251 inline void
 252 Mesher::move( int x, int y )
 253 {
 254     vdata[x] = vdata[y];
 255 }
 256
 257 inline void
 258 Mesher::output( int x )
 259 {
 260     backend.tmeshvert( vdata[x] );
 261 }
 262
 263 /*---------------------------------------------------------------------------
 264  * addedge - addedge an edge to the triangulation
 265  *
 266  *      This code has been re-written to generate large triangle meshes
 267  *      from a monotone polygon.  Although smaller triangle meshes
 268  *      could be generated faster and with less code, larger meshes
 269  *      actually give better SYSTEM performance.  This is because
 270  *      vertices are processed in the backend slower than they are
 271  *      generated by this code and any decrease in the number of vertices
 272  *      results in a decrease in the time spent in the backend.
 273  *---------------------------------------------------------------------------
 274  */
 275
 276 void
 277 Mesher::addLast( )
 278 {
 279     register int ilast = itop;
 280
 281     if( lastedge == 0 ) {
 282         if( equal( 0, 1 ) ) {
 283             output( ilast );
 284             swapMesh();
 285             for( register int i = 2; i < ilast; i++ ) {
 286                 swapMesh();
 287                 output( i );
 288             }
 289             copy( ilast, ilast-1 );
 290         } else if( equal( ilast-2, ilast-1) ) {
 291             swapMesh();
 292             output( ilast );
 293             for( register int i = ilast-3; i >= 0; i-- ) {
 294                 output( i );
 295                 swapMesh();
 296             }
 297             copy( 0, ilast );
 298         } else {
 299             closeMesh();        openMesh();
 300             output( ilast );
 301             output( 0 );
 302             for( register int i = 1; i < ilast; i++ ) {
 303                 swapMesh();
 304                 output( i );
 305             }
 306             copy( ilast, ilast-1 );
 307         }
 308     } else {
 309         if( equal( 1, 0) ) {
 310             swapMesh();
 311             output( ilast );
 312             for( register int i = 2; i < ilast; i++ ) {
 313                 output( i );
 314                 swapMesh();
 315             }
 316             copy( ilast-1, ilast );
 317         } else if( equal( ilast-1, ilast-2) ) {
 318             output( ilast );
 319             swapMesh();
 320             for( register int i = ilast-3; i >= 0; i-- ) {
 321                 swapMesh();
 322                 output( i );
 323             }
 324             copy( ilast, 0 );
 325         } else {
 326             closeMesh();        openMesh();
 327             output( 0 );
 328             output( ilast );
 329             for( register int i = 1; i < ilast; i++ ) {
 330                 output( i );
 331                 swapMesh();
 332             }
 333             copy( ilast-1, ilast );
 334         }
 335     }
 336     closeMesh();
 337     //for( register long k=0; k<=ilast; k++ ) pop( k );
 338 }
 339
 340 void
 341 Mesher::addUpper( )
 342 {
 343     register int ilast = itop;
 344
 345     if( lastedge == 0 ) {
 346         if( equal( 0, 1 ) ) {
 347             output( ilast );
 348             swapMesh();
 349             for( register int i = 2; i < ilast; i++ ) {
 350                 swapMesh();
 351                 output( i );
 352             }
 353             copy( ilast, ilast-1 );
 354         } else if( equal( ilast-2, ilast-1) ) {
 355             swapMesh();
 356             output( ilast );
 357             for( register int i = ilast-3; i >= 0; i-- ) {
 358                 output( i );
 359                 swapMesh();
 360             }
 361             copy( 0, ilast );
 362         } else {
 363             closeMesh();        openMesh();
 364             output( ilast );
 365             output( 0 );
 366             for( register int i = 1; i < ilast; i++ ) {
 367                 swapMesh();
 368                 output( i );
 369             }
 370             copy( ilast, ilast-1 );
 371         }
 372         lastedge = 1;
 373         //for( register long k=0; k<ilast-1; k++ ) pop( k );
 374         move( 0, ilast-1 );
 375         move( 1, ilast );
 376         itop = 1;
 377     } else {
 378         if( ! isCcw( ilast ) ) return;
 379         do {
 380             itop--;
 381         } while( (itop > 1) && isCcw( ilast ) );
 382
 383         if( equal( ilast-1, ilast-2 ) ) {
 384             output( ilast );
 385             swapMesh();
 386             for( register int i=ilast-3; i>=itop-1; i-- ) {
 387                 swapMesh();
 388                 output( i );
 389             }
 390             copy( ilast, itop-1 );
 391         } else if( equal( itop, itop-1 ) ) {
 392             swapMesh();
 393             output( ilast );
 394             for( register int i = itop+1; i < ilast; i++ ) {
 395                 output( i );
 396                 swapMesh();
 397             }
 398             copy( ilast-1, ilast );
 399         } else {
 400             closeMesh();        openMesh();
 401             output( ilast );
 402             output( ilast-1 );
 403             for( register int i=ilast-2; i>=itop-1; i-- ) {
 404                 swapMesh();
 405                 output( i );
 406             }
 407             copy( ilast, itop-1 );
 408         }
 409         //for( register int k=itop; k<ilast; k++ ) pop( k );
 410         move( itop, ilast );
 411     }
 412 }
 413
 414 void
 415 Mesher::addLower()
 416 {
 417     register int ilast = itop;
 418
 419     if( lastedge == 1 ) {
 420         if( equal( 1, 0) ) {
 421             swapMesh();
 422             output( ilast );
 423             for( register int i = 2; i < ilast; i++ ) {
 424                 output( i );
 425                 swapMesh();
 426             }
 427             copy( ilast-1, ilast );
 428         } else if( equal( ilast-1, ilast-2) ) {
 429             output( ilast );
 430             swapMesh();
 431             for( register int i = ilast-3; i >= 0; i-- ) {
 432                 swapMesh();
 433                 output( i );
 434             }
 435             copy( ilast, 0 );
 436         } else {
 437             closeMesh();        openMesh();
 438             output( 0 );
 439             output( ilast );
 440             for( register int i = 1; i < ilast; i++ ) {
 441                 output( i );
 442                 swapMesh();
 443             }
 444             copy( ilast-1, ilast );
 445         }
 446
 447         lastedge = 0;
 448         //for( register long k=0; k<ilast-1; k++ ) pop( k );
 449         move( 0, ilast-1 );
 450         move( 1, ilast );
 451         itop = 1;
 452     } else {
 453         if( ! isCw( ilast ) ) return;
 454         do {
 455             itop--;
 456         } while( (itop > 1) && isCw( ilast ) );
 457
 458         if( equal( ilast-2, ilast-1) ) {
 459             swapMesh();
 460             output( ilast );
 461             for( register int i=ilast-3; i>=itop-1; i--) {
 462                 output( i );
 463                 swapMesh( );
 464             }
 465             copy( itop-1, ilast );
 466         } else if( equal( itop-1, itop) ) {
 467             output( ilast );
 468             swapMesh();
 469             for( register int i=itop+1; i<ilast; i++ ) {
 470                 swapMesh( );
 471                 output( i );
 472             }
 473             copy( ilast, ilast-1 );
 474         } else {
 475             closeMesh();        openMesh();
 476             output( ilast-1 );
 477             output( ilast );
 478             for( register int i=ilast-2; i>=itop-1; i-- ) {
 479                 output( i );
 480                 swapMesh( );
 481             }
 482             copy( itop-1, ilast );
 483         }
 484         //for( register int k=itop; k<ilast; k++ ) pop( k );
 485         move( itop, ilast );
 486     }
 487 }
 488
 489