src/glu/sgi/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     lastedge = 0; //needed to prevent purify UMR
  62 }
  63
  64 Mesher::~Mesher( void )
  65 {
  66     if( vdata ) delete[] vdata;
  67 }
  68
  69 void
  70 Mesher::init( unsigned int npts )
  71 {
  72     p.clear();
  73     if( stacksize < npts ) {
  74         stacksize = 2 * npts;
  75         if( vdata ) delete[] vdata;
  76         vdata = new GridTrimVertex_p[stacksize];
  77     }
  78 }
  79
  80 inline void
  81 Mesher::push( GridTrimVertex *gt )
  82 {
  83     assert( itop+1 != (int)stacksize );
  84     vdata[++itop] = gt;
  85 }
  86
  87 inline void
  88 Mesher::pop( long )
  89 {
  90 }
  91
  92 inline void
  93 Mesher::openMesh()
  94 {
  95     backend.bgntmesh( "addedge" );
  96 }
  97
  98 inline void
  99 Mesher::closeMesh()
 100 {
 101     backend.endtmesh();
 102 }
 103
 104 inline void
 105 Mesher::swapMesh()
 106 {
 107     backend.swaptmesh();
 108 }
 109
 110 inline void
 111 Mesher::clearStack()
 112 {
 113     itop = -1;
 114     last[0] = 0;
 115 }
 116
 117 void
 118 Mesher::finishLower( GridTrimVertex *gtlower )
 119 {
 120     for( push(gtlower);
 121          nextlower( gtlower=new(p) GridTrimVertex );
 122          push(gtlower) )
 123             addLower();
 124     addLast();
 125 }
 126
 127 void
 128 Mesher::finishUpper( GridTrimVertex *gtupper )
 129 {
 130     for( push(gtupper);
 131          nextupper( gtupper=new(p) GridTrimVertex );
 132          push(gtupper) )
 133             addUpper();
 134     addLast();
 135 }
 136
 137 void
 138 Mesher::mesh( void )
 139 {
 140     GridTrimVertex *gtlower, *gtupper;
 141
 142     Hull::init( );
 143     nextupper( gtupper = new(p) GridTrimVertex );
 144     nextlower( gtlower = new(p) GridTrimVertex );
 145
 146     clearStack();
 147     openMesh();
 148     push(gtupper);
 149
 150     nextupper( gtupper = new(p) GridTrimVertex );
 151     nextlower( gtlower );
 152
 153     assert( gtupper->t && gtlower->t );
 154
 155     if( gtupper->t->param[0] < gtlower->t->param[0] ) {
 156         push(gtupper);
 157         lastedge = 1;
 158         if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
 159             finishLower(gtlower);
 160             return;
 161         }
 162     } else if( gtupper->t->param[0] > gtlower->t->param[0] ) {
 163         push(gtlower);
 164         lastedge = 0;
 165         if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
 166             finishUpper(gtupper);
 167             return;
 168         }
 169     } else {
 170         if( lastedge == 0 ) {
 171             push(gtupper);
 172             lastedge = 1;
 173             if( nextupper(gtupper=new(p) GridTrimVertex) == 0 ) {
 174                 finishLower(gtlower);
 175                 return;
 176             }
 177         } else {
 178             push(gtlower);
 179             lastedge = 0;
 180             if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
 181                 finishUpper(gtupper);
 182                 return;
 183             }
 184         }
 185     }
 186
 187     while ( 1 ) {
 188         if( gtupper->t->param[0] < gtlower->t->param[0] ) {
 189             push(gtupper);
 190             addUpper();
 191             if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
 192                 finishLower(gtlower);
 193                 return;
 194             }
 195         } else if( gtupper->t->param[0] > gtlower->t->param[0] ) {
 196             push(gtlower);
 197             addLower();
 198             if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
 199                 finishUpper(gtupper);
 200                 return;
 201             }
 202         } else {
 203             if( lastedge == 0 ) {
 204                 push(gtupper);
 205                 addUpper();
 206                 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
 207                     finishLower(gtlower);
 208                     return;
 209                 }
 210             } else {
 211                 push(gtlower);
 212                 addLower();
 213                 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
 214                     finishUpper(gtupper);
 215                     return;
 216                 }
 217             }
 218         }
 219     }
 220 }
 221
 222 inline int
 223 Mesher::isCcw( int ilast )
 224 {
 225     REAL area = det3( vdata[ilast]->t, vdata[itop-1]->t, vdata[itop-2]->t );
 226     return (area < ZERO) ? 0 : 1;
 227 }
 228
 229 inline int
 230 Mesher::isCw( int ilast  )
 231 {
 232     REAL area = det3( vdata[ilast]->t, vdata[itop-1]->t, vdata[itop-2]->t );
 233     return (area > -ZERO) ? 0 : 1;
 234 }
 235
 236 inline int
 237 Mesher::equal( int x, int y )
 238 {
 239     return( last[0] == vdata[x] && last[1] == vdata[y] );
 240 }
 241
 242 inline void
 243 Mesher::copy( int x, int y )
 244 {
 245     last[0] = vdata[x]; last[1] = vdata[y];
 246 }
 247
 248 inline void
 249 Mesher::move( int x, int y )
 250 {
 251     vdata[x] = vdata[y];
 252 }
 253
 254 inline void
 255 Mesher::output( int x )
 256 {
 257     backend.tmeshvert( vdata[x] );
 258 }
 259
 260 /*---------------------------------------------------------------------------
 261  * addedge - addedge an edge to the triangulation
 262  *
 263  *      This code has been re-written to generate large triangle meshes
 264  *      from a monotone polygon.  Although smaller triangle meshes
 265  *      could be generated faster and with less code, larger meshes
 266  *      actually give better SYSTEM performance.  This is because
 267  *      vertices are processed in the backend slower than they are
 268  *      generated by this code and any decrease in the number of vertices
 269  *      results in a decrease in the time spent in the backend.
 270  *---------------------------------------------------------------------------
 271  */
 272
 273 void
 274 Mesher::addLast( )
 275 {
 276     register int ilast = itop;
 277
 278     if( lastedge == 0 ) {
 279         if( equal( 0, 1 ) ) {
 280             output( ilast );
 281             swapMesh();
 282             for( register int i = 2; i < ilast; i++ ) {
 283                 swapMesh();
 284                 output( i );
 285             }
 286             copy( ilast, ilast-1 );
 287         } else if( equal( ilast-2, ilast-1) ) {
 288             swapMesh();
 289             output( ilast );
 290             for( register int i = ilast-3; i >= 0; i-- ) {
 291                 output( i );
 292                 swapMesh();
 293             }
 294             copy( 0, ilast );
 295         } else {
 296             closeMesh();        openMesh();
 297             output( ilast );
 298             output( 0 );
 299             for( register int i = 1; i < ilast; i++ ) {
 300                 swapMesh();
 301                 output( i );
 302             }
 303             copy( ilast, ilast-1 );
 304         }
 305     } else {
 306         if( equal( 1, 0) ) {
 307             swapMesh();
 308             output( ilast );
 309             for( register int i = 2; i < ilast; i++ ) {
 310                 output( i );
 311                 swapMesh();
 312             }
 313             copy( ilast-1, ilast );
 314         } else if( equal( ilast-1, ilast-2) ) {
 315             output( ilast );
 316             swapMesh();
 317             for( register int i = ilast-3; i >= 0; i-- ) {
 318                 swapMesh();
 319                 output( i );
 320             }
 321             copy( ilast, 0 );
 322         } else {
 323             closeMesh();        openMesh();
 324             output( 0 );
 325             output( ilast );
 326             for( register int i = 1; i < ilast; i++ ) {
 327                 output( i );
 328                 swapMesh();
 329             }
 330             copy( ilast-1, ilast );
 331         }
 332     }
 333     closeMesh();
 334     //for( register long k=0; k<=ilast; k++ ) pop( k );
 335 }
 336
 337 void
 338 Mesher::addUpper( )
 339 {
 340     register int ilast = itop;
 341
 342     if( lastedge == 0 ) {
 343         if( equal( 0, 1 ) ) {
 344             output( ilast );
 345             swapMesh();
 346             for( register int i = 2; i < ilast; i++ ) {
 347                 swapMesh();
 348                 output( i );
 349             }
 350             copy( ilast, ilast-1 );
 351         } else if( equal( ilast-2, ilast-1) ) {
 352             swapMesh();
 353             output( ilast );
 354             for( register int i = ilast-3; i >= 0; i-- ) {
 355                 output( i );
 356                 swapMesh();
 357             }
 358             copy( 0, ilast );
 359         } else {
 360             closeMesh();        openMesh();
 361             output( ilast );
 362             output( 0 );
 363             for( register int i = 1; i < ilast; i++ ) {
 364                 swapMesh();
 365                 output( i );
 366             }
 367             copy( ilast, ilast-1 );
 368         }
 369         lastedge = 1;
 370         //for( register long k=0; k<ilast-1; k++ ) pop( k );
 371         move( 0, ilast-1 );
 372         move( 1, ilast );
 373         itop = 1;
 374     } else {
 375         if( ! isCcw( ilast ) ) return;
 376         do {
 377             itop--;
 378         } while( (itop > 1) && isCcw( ilast ) );
 379
 380         if( equal( ilast-1, ilast-2 ) ) {
 381             output( ilast );
 382             swapMesh();
 383             for( register int i=ilast-3; i>=itop-1; i-- ) {
 384                 swapMesh();
 385                 output( i );
 386             }
 387             copy( ilast, itop-1 );
 388         } else if( equal( itop, itop-1 ) ) {
 389             swapMesh();
 390             output( ilast );
 391             for( register int i = itop+1; i < ilast; i++ ) {
 392                 output( i );
 393                 swapMesh();
 394             }
 395             copy( ilast-1, ilast );
 396         } else {
 397             closeMesh();        openMesh();
 398             output( ilast );
 399             output( ilast-1 );
 400             for( register int i=ilast-2; i>=itop-1; i-- ) {
 401                 swapMesh();
 402                 output( i );
 403             }
 404             copy( ilast, itop-1 );
 405         }
 406         //for( register int k=itop; k<ilast; k++ ) pop( k );
 407         move( itop, ilast );
 408     }
 409 }
 410
 411 void
 412 Mesher::addLower()
 413 {
 414     register int ilast = itop;
 415
 416     if( lastedge == 1 ) {
 417         if( equal( 1, 0) ) {
 418             swapMesh();
 419             output( ilast );
 420             for( register int i = 2; i < ilast; i++ ) {
 421                 output( i );
 422                 swapMesh();
 423             }
 424             copy( ilast-1, ilast );
 425         } else if( equal( ilast-1, ilast-2) ) {
 426             output( ilast );
 427             swapMesh();
 428             for( register int i = ilast-3; i >= 0; i-- ) {
 429                 swapMesh();
 430                 output( i );
 431             }
 432             copy( ilast, 0 );
 433         } else {
 434             closeMesh();        openMesh();
 435             output( 0 );
 436             output( ilast );
 437             for( register int i = 1; i < ilast; i++ ) {
 438                 output( i );
 439                 swapMesh();
 440             }
 441             copy( ilast-1, ilast );
 442         }
 443
 444         lastedge = 0;
 445         //for( register long k=0; k<ilast-1; k++ ) pop( k );
 446         move( 0, ilast-1 );
 447         move( 1, ilast );
 448         itop = 1;
 449     } else {
 450         if( ! isCw( ilast ) ) return;
 451         do {
 452             itop--;
 453         } while( (itop > 1) && isCw( ilast ) );
 454
 455         if( equal( ilast-2, ilast-1) ) {
 456             swapMesh();
 457             output( ilast );
 458             for( register int i=ilast-3; i>=itop-1; i--) {
 459                 output( i );
 460                 swapMesh( );
 461             }
 462             copy( itop-1, ilast );
 463         } else if( equal( itop-1, itop) ) {
 464             output( ilast );
 465             swapMesh();
 466             for( register int i=itop+1; i<ilast; i++ ) {
 467                 swapMesh( );
 468                 output( i );
 469             }
 470             copy( ilast, ilast-1 );
 471         } else {
 472             closeMesh();        openMesh();
 473             output( ilast-1 );
 474             output( ilast );
 475             for( register int i=ilast-2; i>=itop-1; i-- ) {
 476                 output( i );
 477                 swapMesh( );
 478             }
 479             copy( itop-1, ilast );
 480         }
 481         //for( register int k=itop; k<ilast; k++ ) pop( k );
 482         move( itop, ilast );
 483     }
 484 }
 485
 486