src/glu/sgi/libtess/render.c

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