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