reactos/dll/win32/glu32/libtess/render.c

   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 ** Author: Eric Veach, July 1994.
  37 **
  38 ** $Date$ $Revision: 1.1 $
  39 ** $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libtess/render.c,v 1.1 2004/02/02 16:39:15 navaraf Exp $
  40 */
  41
  42 #include "gluos.h"
  43 #include <assert.h>
  44 #include <stddef.h>
  45 #include "mesh.h"
  46 #include "tess.h"
  47 #include "render.h"
  48
  49 #define TRUE 1
  50 #define FALSE 0
  51
  52 /* This structure remembers the information we need about a primitive
  53  * to be able to render it later, once we have determined which
  54  * primitive is able to use the most triangles.
  55  */
  56 struct FaceCount {
  57   long          size;           /* number of triangles used */
  58   GLUhalfEdge   *eStart;        /* edge where this primitive starts */
  59   void          (*render)(GLUtesselator *, GLUhalfEdge *, long);
  60                                 /* routine to render this primitive */
  61 };
  62
  63 static struct FaceCount MaximumFan( GLUhalfEdge *eOrig );
  64 static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig );
  65
  66 static void RenderFan( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
  67 static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
  68 static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *eStart,
  69                             long size );
  70
  71 static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig );
  72 static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *head );
  73
  74
  75
  76 /************************ Strips and Fans decomposition ******************/
  77
  78 /* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle
  79  * fans, strips, and separate triangles.  A substantial effort is made
  80  * to use as few rendering primitives as possible (ie. to make the fans
  81  * and strips as large as possible).
  82  *
  83  * The rendering output is provided as callbacks (see the api).
  84  */
  85 void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh )
  86 {
  87   GLUface *f;
  88
  89   /* Make a list of separate triangles so we can render them all at once */
  90   tess->lonelyTriList = NULL;
  91
  92   for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
  93     f->marked = FALSE;
  94   }
  95   for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
  96
  97     /* We examine all faces in an arbitrary order.  Whenever we find
  98      * an unprocessed face F, we output a group of faces including F
  99      * whose size is maximum.
 100      */
 101     if( f->inside && ! f->marked ) {
 102       RenderMaximumFaceGroup( tess, f );
 103       assert( f->marked );
 104     }
 105   }
 106   if( tess->lonelyTriList != NULL ) {
 107     RenderLonelyTriangles( tess, tess->lonelyTriList );
 108     tess->lonelyTriList = NULL;
 109   }
 110 }
 111
 112
 113 static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig )
 114 {
 115   /* We want to find the largest triangle fan or strip of unmarked faces
 116    * which includes the given face fOrig.  There are 3 possible fans
 117    * passing through fOrig (one centered at each vertex), and 3 possible
 118    * strips (one for each CCW permutation of the vertices).  Our strategy
 119    * is to try all of these, and take the primitive which uses the most
 120    * triangles (a greedy approach).
 121    */
 122   GLUhalfEdge *e = fOrig->anEdge;
 123   struct FaceCount max, newFace;
 124
 125   max.size = 1;
 126   max.eStart = e;
 127   max.render = &RenderTriangle;
 128
 129   if( ! tess->flagBoundary ) {
 130     newFace = MaximumFan( e ); if( newFace.size > max.size ) { max = newFace; }
 131     newFace = MaximumFan( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
 132     newFace = MaximumFan( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
 133
 134     newFace = MaximumStrip( e ); if( newFace.size > max.size ) { max = newFace; }
 135     newFace = MaximumStrip( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
 136     newFace = MaximumStrip( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
 137   }
 138   (*(max.render))( tess, max.eStart, max.size );
 139 }
 140
 141
 142 /* Macros which keep track of faces we have marked temporarily, and allow
 143  * us to backtrack when necessary.  With triangle fans, this is not
 144  * really necessary, since the only awkward case is a loop of triangles
 145  * around a single origin vertex.  However with strips the situation is
 146  * more complicated, and we need a general tracking method like the
 147  * one here.
 148  */
 149 #define Marked(f)       (! (f)->inside || (f)->marked)
 150
 151 #define AddToTrail(f,t) ((f)->trail = (t), (t) = (f), (f)->marked = TRUE)
 152
 153 #define FreeTrail(t)    if( 1 ) { \
 154                           while( (t) != NULL ) { \
 155                             (t)->marked = FALSE; t = (t)->trail; \
 156                           } \
 157                         } else /* absorb trailing semicolon */
 158
 159
 160
 161 static struct FaceCount MaximumFan( GLUhalfEdge *eOrig )
 162 {
 163   /* eOrig->Lface is the face we want to render.  We want to find the size
 164    * of a maximal fan around eOrig->Org.  To do this we just walk around
 165    * the origin vertex as far as possible in both directions.
 166    */
 167   struct FaceCount newFace = { 0, NULL, &RenderFan };
 168   GLUface *trail = NULL;
 169   GLUhalfEdge *e;
 170
 171   for( e = eOrig; ! Marked( e->Lface ); e = e->Onext ) {
 172     AddToTrail( e->Lface, trail );
 173     ++newFace.size;
 174   }
 175   for( e = eOrig; ! Marked( e->Rface ); e = e->Oprev ) {
 176     AddToTrail( e->Rface, trail );
 177     ++newFace.size;
 178   }
 179   newFace.eStart = e;
 180   /*LINTED*/
 181   FreeTrail( trail );
 182   return newFace;
 183 }
 184
 185
 186 #define IsEven(n)       (((n) & 1) == 0)
 187
 188 static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig )
 189 {
 190   /* Here we are looking for a maximal strip that contains the vertices
 191    * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the
 192    * reverse, such that all triangles are oriented CCW).
 193    *
 194    * Again we walk forward and backward as far as possible.  However for
 195    * strips there is a twist: to get CCW orientations, there must be
 196    * an *even* number of triangles in the strip on one side of eOrig.
 197    * We walk the strip starting on a side with an even number of triangles;
 198    * if both side have an odd number, we are forced to shorten one side.
 199    */
 200   struct FaceCount newFace = { 0, NULL, &RenderStrip };
 201   long headSize = 0, tailSize = 0;
 202   GLUface *trail = NULL;
 203   GLUhalfEdge *e, *eTail, *eHead;
 204
 205   for( e = eOrig; ! Marked( e->Lface ); ++tailSize, e = e->Onext ) {
 206     AddToTrail( e->Lface, trail );
 207     ++tailSize;
 208     e = e->Dprev;
 209     if( Marked( e->Lface )) break;
 210     AddToTrail( e->Lface, trail );
 211   }
 212   eTail = e;
 213
 214   for( e = eOrig; ! Marked( e->Rface ); ++headSize, e = e->Dnext ) {
 215     AddToTrail( e->Rface, trail );
 216     ++headSize;
 217     e = e->Oprev;
 218     if( Marked( e->Rface )) break;
 219     AddToTrail( e->Rface, trail );
 220   }
 221   eHead = e;
 222
 223   newFace.size = tailSize + headSize;
 224   if( IsEven( tailSize )) {
 225     newFace.eStart = eTail->Sym;
 226   } else if( IsEven( headSize )) {
 227     newFace.eStart = eHead;
 228   } else {
 229     /* Both sides have odd length, we must shorten one of them.  In fact,
 230      * we must start from eHead to guarantee inclusion of eOrig->Lface.
 231      */
 232     --newFace.size;
 233     newFace.eStart = eHead->Onext;
 234   }
 235   /*LINTED*/
 236   FreeTrail( trail );
 237   return newFace;
 238 }
 239
 240
 241 static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *e, long size )
 242 {
 243   /* Just add the triangle to a triangle list, so we can render all
 244    * the separate triangles at once.
 245    */
 246   assert( size == 1 );
 247   AddToTrail( e->Lface, tess->lonelyTriList );
 248 }
 249
 250
 251 static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *f )
 252 {
 253   /* Now we render all the separate triangles which could not be
 254    * grouped into a triangle fan or strip.
 255    */
 256   GLUhalfEdge *e;
 257   int newState;
 258   int edgeState = -1;   /* force edge state output for first vertex */
 259
 260   CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLES );
 261
 262   for( ; f != NULL; f = f->trail ) {
 263     /* Loop once for each edge (there will always be 3 edges) */
 264
 265     e = f->anEdge;
 266     do {
 267       if( tess->flagBoundary ) {
 268         /* Set the "edge state" to TRUE just before we output the
 269          * first vertex of each edge on the polygon boundary.
 270          */
 271         newState = ! e->Rface->inside;
 272         if( edgeState != newState ) {
 273           edgeState = newState;
 274           CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( edgeState );
 275         }
 276       }
 277       CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
 278
 279       e = e->Lnext;
 280     } while( e != f->anEdge );
 281   }
 282   CALL_END_OR_END_DATA();
 283 }
 284
 285
 286 static void RenderFan( GLUtesselator *tess, GLUhalfEdge *e, long size )
 287 {
 288   /* Render as many CCW triangles as possible in a fan starting from
 289    * edge "e".  The fan *should* contain exactly "size" triangles
 290    * (otherwise we've goofed up somewhere).
 291    */
 292   CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_FAN );
 293   CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
 294   CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
 295
 296   while( ! Marked( e->Lface )) {
 297     e->Lface->marked = TRUE;
 298     --size;
 299     e = e->Onext;
 300     CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
 301   }
 302
 303   assert( size == 0 );
 304   CALL_END_OR_END_DATA();
 305 }
 306
 307
 308 static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *e, long size )
 309 {
 310   /* Render as many CCW triangles as possible in a strip starting from
 311    * edge "e".  The strip *should* contain exactly "size" triangles
 312    * (otherwise we've goofed up somewhere).
 313    */
 314   CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_STRIP );
 315   CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
 316   CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
 317
 318   while( ! Marked( e->Lface )) {
 319     e->Lface->marked = TRUE;
 320     --size;
 321     e = e->Dprev;
 322     CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
 323     if( Marked( e->Lface )) break;
 324
 325     e->Lface->marked = TRUE;
 326     --size;
 327     e = e->Onext;
 328     CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
 329   }
 330
 331   assert( size == 0 );
 332   CALL_END_OR_END_DATA();
 333 }
 334
 335
 336 /************************ Boundary contour decomposition ******************/
 337
 338 /* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one
 339  * contour for each face marked "inside".  The rendering output is
 340  * provided as callbacks (see the api).
 341  */
 342 void __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh )
 343 {
 344   GLUface *f;
 345   GLUhalfEdge *e;
 346
 347   for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
 348     if( f->inside ) {
 349       CALL_BEGIN_OR_BEGIN_DATA( GL_LINE_LOOP );
 350       e = f->anEdge;
 351       do {
 352         CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
 353         e = e->Lnext;
 354       } while( e != f->anEdge );
 355       CALL_END_OR_END_DATA();
 356     }
 357   }
 358 }
 359
 360
 361 /************************ Quick-and-dirty decomposition ******************/
 362
 363 #define SIGN_INCONSISTENT 2
 364
 365 static int ComputeNormal( GLUtesselator *tess, GLdouble norm[3], int check )
 366 /*
 367  * If check==FALSE, we compute the polygon normal and place it in norm[].
 368  * If check==TRUE, we check that each triangle in the fan from v0 has a
 369  * consistent orientation with respect to norm[].  If triangles are
 370  * consistently oriented CCW, return 1; if CW, return -1; if all triangles
 371  * are degenerate return 0; otherwise (no consistent orientation) return
 372  * SIGN_INCONSISTENT.
 373  */
 374 {
 375   CachedVertex *v0 = tess->cache;
 376   CachedVertex *vn = v0 + tess->cacheCount;
 377   CachedVertex *vc;
 378   GLdouble dot, xc, yc, zc, xp, yp, zp, n[3];
 379   int sign = 0;
 380
 381   /* Find the polygon normal.  It is important to get a reasonable
 382    * normal even when the polygon is self-intersecting (eg. a bowtie).
 383    * Otherwise, the computed normal could be very tiny, but perpendicular
 384    * to the true plane of the polygon due to numerical noise.  Then all
 385    * the triangles would appear to be degenerate and we would incorrectly
 386    * decompose the polygon as a fan (or simply not render it at all).
 387    *
 388    * We use a sum-of-triangles normal algorithm rather than the more
 389    * efficient sum-of-trapezoids method (used in CheckOrientation()
 390    * in normal.c).  This lets us explicitly reverse the signed area
 391    * of some triangles to get a reasonable normal in the self-intersecting
 392    * case.
 393    */
 394   if( ! check ) {
 395     norm[0] = norm[1] = norm[2] = 0.0;
 396   }
 397
 398   vc = v0 + 1;
 399   xc = vc->coords[0] - v0->coords[0];
 400   yc = vc->coords[1] - v0->coords[1];
 401   zc = vc->coords[2] - v0->coords[2];
 402   while( ++vc < vn ) {
 403     xp = xc; yp = yc; zp = zc;
 404     xc = vc->coords[0] - v0->coords[0];
 405     yc = vc->coords[1] - v0->coords[1];
 406     zc = vc->coords[2] - v0->coords[2];
 407
 408     /* Compute (vp - v0) cross (vc - v0) */
 409     n[0] = yp*zc - zp*yc;
 410     n[1] = zp*xc - xp*zc;
 411     n[2] = xp*yc - yp*xc;
 412
 413     dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*norm[2];
 414     if( ! check ) {
 415       /* Reverse the contribution of back-facing triangles to get
 416        * a reasonable normal for self-intersecting polygons (see above)
 417        */
 418       if( dot >= 0 ) {
 419         norm[0] += n[0]; norm[1] += n[1]; norm[2] += n[2];
 420       } else {
 421         norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= n[2];
 422       }
 423     } else if( dot != 0 ) {
 424       /* Check the new orientation for consistency with previous triangles */
 425       if( dot > 0 ) {
 426         if( sign < 0 ) return SIGN_INCONSISTENT;
 427         sign = 1;
 428       } else {
 429         if( sign > 0 ) return SIGN_INCONSISTENT;
 430         sign = -1;
 431       }
 432     }
 433   }
 434   return sign;
 435 }
 436
 437 /* __gl_renderCache( tess ) takes a single contour and tries to render it
 438  * as a triangle fan.  This handles convex polygons, as well as some
 439  * non-convex polygons if we get lucky.
 440  *
 441  * Returns TRUE if the polygon was successfully rendered.  The rendering
 442  * output is provided as callbacks (see the api).
 443  */
 444 GLboolean __gl_renderCache( GLUtesselator *tess )
 445 {
 446   CachedVertex *v0 = tess->cache;
 447   CachedVertex *vn = v0 + tess->cacheCount;
 448   CachedVertex *vc;
 449   GLdouble norm[3];
 450   int sign;
 451
 452   if( tess->cacheCount < 3 ) {
 453     /* Degenerate contour -- no output */
 454     return TRUE;
 455   }
 456
 457   norm[0] = tess->normal[0];
 458   norm[1] = tess->normal[1];
 459   norm[2] = tess->normal[2];
 460   if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) {
 461     ComputeNormal( tess, norm, FALSE );
 462   }
 463
 464   sign = ComputeNormal( tess, norm, TRUE );
 465   if( sign == SIGN_INCONSISTENT ) {
 466     /* Fan triangles did not have a consistent orientation */
 467     return FALSE;
 468   }
 469   if( sign == 0 ) {
 470     /* All triangles were degenerate */
 471     return TRUE;
 472   }
 473
 474   /* Make sure we do the right thing for each winding rule */
 475   switch( tess->windingRule ) {
 476   case GLU_TESS_WINDING_ODD:
 477   case GLU_TESS_WINDING_NONZERO:
 478     break;
 479   case GLU_TESS_WINDING_POSITIVE:
 480     if( sign < 0 ) return TRUE;
 481     break;
 482   case GLU_TESS_WINDING_NEGATIVE:
 483     if( sign > 0 ) return TRUE;
 484     break;
 485   case GLU_TESS_WINDING_ABS_GEQ_TWO:
 486     return TRUE;
 487   }
 488
 489   CALL_BEGIN_OR_BEGIN_DATA( tess->boundaryOnly ? GL_LINE_LOOP
 490                           : (tess->cacheCount > 3) ? GL_TRIANGLE_FAN
 491                           : GL_TRIANGLES );
 492
 493   CALL_VERTEX_OR_VERTEX_DATA( v0->data );
 494   if( sign > 0 ) {
 495     for( vc = v0+1; vc < vn; ++vc ) {
 496       CALL_VERTEX_OR_VERTEX_DATA( vc->data );
 497     }
 498   } else {
 499     for( vc = vn-1; vc > v0; --vc ) {
 500       CALL_VERTEX_OR_VERTEX_DATA( vc->data );
 501     }
 502   }
 503   CALL_END_OR_END_DATA();
 504   return TRUE;
 505 }