summaryrefslogtreecommitdiffstats
path: root/src/glu/sgi/libtess/render.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/glu/sgi/libtess/render.c')
-rw-r--r--src/glu/sgi/libtess/render.c505
1 files changed, 505 insertions, 0 deletions
diff --git a/src/glu/sgi/libtess/render.c b/src/glu/sgi/libtess/render.c
new file mode 100644
index 00000000000..efbb88d52b8
--- /dev/null
+++ b/src/glu/sgi/libtess/render.c
@@ -0,0 +1,505 @@
+/*
+** License Applicability. Except to the extent portions of this file are
+** made subject to an alternative license as permitted in the SGI Free
+** Software License B, Version 1.1 (the "License"), the contents of this
+** file are subject only to the provisions of the License. You may not use
+** this file except in compliance with the License. You may obtain a copy
+** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
+** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
+**
+** http://oss.sgi.com/projects/FreeB
+**
+** Note that, as provided in the License, the Software is distributed on an
+** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
+** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
+** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
+** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
+**
+** Original Code. The Original Code is: OpenGL Sample Implementation,
+** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
+** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
+** Copyright in any portions created by third parties is as indicated
+** elsewhere herein. All Rights Reserved.
+**
+** Additional Notice Provisions: The application programming interfaces
+** established by SGI in conjunction with the Original Code are The
+** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
+** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
+** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
+** Window System(R) (Version 1.3), released October 19, 1998. This software
+** was created using the OpenGL(R) version 1.2.1 Sample Implementation
+** published by SGI, but has not been independently verified as being
+** compliant with the OpenGL(R) version 1.2.1 Specification.
+**
+*/
+/*
+** Author: Eric Veach, July 1994.
+**
+** $Date: 2001/03/17 00:25:41 $ $Revision: 1.1 $
+** $Header: /cvs/mesa/Mesa/src/glu/sgi/libtess/render.c,v 1.1 2001/03/17 00:25:41 brianp Exp $
+*/
+
+#include "gluos.h"
+#include <assert.h>
+#include <stddef.h>
+#include "mesh.h"
+#include "tess.h"
+#include "render.h"
+
+#define TRUE 1
+#define FALSE 0
+
+/* This structure remembers the information we need about a primitive
+ * to be able to render it later, once we have determined which
+ * primitive is able to use the most triangles.
+ */
+struct FaceCount {
+ long size; /* number of triangles used */
+ GLUhalfEdge *eStart; /* edge where this primitive starts */
+ void (*render)(GLUtesselator *, GLUhalfEdge *, long);
+ /* routine to render this primitive */
+};
+
+static struct FaceCount MaximumFan( GLUhalfEdge *eOrig );
+static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig );
+
+static void RenderFan( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
+static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
+static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *eStart,
+ long size );
+
+static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig );
+static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *head );
+
+
+
+/************************ Strips and Fans decomposition ******************/
+
+/* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle
+ * fans, strips, and separate triangles. A substantial effort is made
+ * to use as few rendering primitives as possible (ie. to make the fans
+ * and strips as large as possible).
+ *
+ * The rendering output is provided as callbacks (see the api).
+ */
+void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh )
+{
+ GLUface *f;
+
+ /* Make a list of separate triangles so we can render them all at once */
+ tess->lonelyTriList = NULL;
+
+ for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
+ f->marked = FALSE;
+ }
+ for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
+
+ /* We examine all faces in an arbitrary order. Whenever we find
+ * an unprocessed face F, we output a group of faces including F
+ * whose size is maximum.
+ */
+ if( f->inside && ! f->marked ) {
+ RenderMaximumFaceGroup( tess, f );
+ assert( f->marked );
+ }
+ }
+ if( tess->lonelyTriList != NULL ) {
+ RenderLonelyTriangles( tess, tess->lonelyTriList );
+ tess->lonelyTriList = NULL;
+ }
+}
+
+
+static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig )
+{
+ /* We want to find the largest triangle fan or strip of unmarked faces
+ * which includes the given face fOrig. There are 3 possible fans
+ * passing through fOrig (one centered at each vertex), and 3 possible
+ * strips (one for each CCW permutation of the vertices). Our strategy
+ * is to try all of these, and take the primitive which uses the most
+ * triangles (a greedy approach).
+ */
+ GLUhalfEdge *e = fOrig->anEdge;
+ struct FaceCount max, newFace;
+
+ max.size = 1;
+ max.eStart = e;
+ max.render = &RenderTriangle;
+
+ if( ! tess->flagBoundary ) {
+ newFace = MaximumFan( e ); if( newFace.size > max.size ) { max = newFace; }
+ newFace = MaximumFan( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
+ newFace = MaximumFan( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
+
+ newFace = MaximumStrip( e ); if( newFace.size > max.size ) { max = newFace; }
+ newFace = MaximumStrip( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
+ newFace = MaximumStrip( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
+ }
+ (*(max.render))( tess, max.eStart, max.size );
+}
+
+
+/* Macros which keep track of faces we have marked temporarily, and allow
+ * us to backtrack when necessary. With triangle fans, this is not
+ * really necessary, since the only awkward case is a loop of triangles
+ * around a single origin vertex. However with strips the situation is
+ * more complicated, and we need a general tracking method like the
+ * one here.
+ */
+#define Marked(f) (! (f)->inside || (f)->marked)
+
+#define AddToTrail(f,t) ((f)->trail = (t), (t) = (f), (f)->marked = TRUE)
+
+#define FreeTrail(t) if( 1 ) { \
+ while( (t) != NULL ) { \
+ (t)->marked = FALSE; t = (t)->trail; \
+ } \
+ } else /* absorb trailing semicolon */
+
+
+
+static struct FaceCount MaximumFan( GLUhalfEdge *eOrig )
+{
+ /* eOrig->Lface is the face we want to render. We want to find the size
+ * of a maximal fan around eOrig->Org. To do this we just walk around
+ * the origin vertex as far as possible in both directions.
+ */
+ struct FaceCount newFace = { 0, NULL, &RenderFan };
+ GLUface *trail = NULL;
+ GLUhalfEdge *e;
+
+ for( e = eOrig; ! Marked( e->Lface ); e = e->Onext ) {
+ AddToTrail( e->Lface, trail );
+ ++newFace.size;
+ }
+ for( e = eOrig; ! Marked( e->Rface ); e = e->Oprev ) {
+ AddToTrail( e->Rface, trail );
+ ++newFace.size;
+ }
+ newFace.eStart = e;
+ /*LINTED*/
+ FreeTrail( trail );
+ return newFace;
+}
+
+
+#define IsEven(n) (((n) & 1) == 0)
+
+static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig )
+{
+ /* Here we are looking for a maximal strip that contains the vertices
+ * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the
+ * reverse, such that all triangles are oriented CCW).
+ *
+ * Again we walk forward and backward as far as possible. However for
+ * strips there is a twist: to get CCW orientations, there must be
+ * an *even* number of triangles in the strip on one side of eOrig.
+ * We walk the strip starting on a side with an even number of triangles;
+ * if both side have an odd number, we are forced to shorten one side.
+ */
+ struct FaceCount newFace = { 0, NULL, &RenderStrip };
+ long headSize = 0, tailSize = 0;
+ GLUface *trail = NULL;
+ GLUhalfEdge *e, *eTail, *eHead;
+
+ for( e = eOrig; ! Marked( e->Lface ); ++tailSize, e = e->Onext ) {
+ AddToTrail( e->Lface, trail );
+ ++tailSize;
+ e = e->Dprev;
+ if( Marked( e->Lface )) break;
+ AddToTrail( e->Lface, trail );
+ }
+ eTail = e;
+
+ for( e = eOrig; ! Marked( e->Rface ); ++headSize, e = e->Dnext ) {
+ AddToTrail( e->Rface, trail );
+ ++headSize;
+ e = e->Oprev;
+ if( Marked( e->Rface )) break;
+ AddToTrail( e->Rface, trail );
+ }
+ eHead = e;
+
+ newFace.size = tailSize + headSize;
+ if( IsEven( tailSize )) {
+ newFace.eStart = eTail->Sym;
+ } else if( IsEven( headSize )) {
+ newFace.eStart = eHead;
+ } else {
+ /* Both sides have odd length, we must shorten one of them. In fact,
+ * we must start from eHead to guarantee inclusion of eOrig->Lface.
+ */
+ --newFace.size;
+ newFace.eStart = eHead->Onext;
+ }
+ /*LINTED*/
+ FreeTrail( trail );
+ return newFace;
+}
+
+
+static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *e, long size )
+{
+ /* Just add the triangle to a triangle list, so we can render all
+ * the separate triangles at once.
+ */
+ assert( size == 1 );
+ AddToTrail( e->Lface, tess->lonelyTriList );
+}
+
+
+static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *f )
+{
+ /* Now we render all the separate triangles which could not be
+ * grouped into a triangle fan or strip.
+ */
+ GLUhalfEdge *e;
+ int newState;
+ int edgeState = -1; /* force edge state output for first vertex */
+
+ CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLES );
+
+ for( ; f != NULL; f = f->trail ) {
+ /* Loop once for each edge (there will always be 3 edges) */
+
+ e = f->anEdge;
+ do {
+ if( tess->flagBoundary ) {
+ /* Set the "edge state" to TRUE just before we output the
+ * first vertex of each edge on the polygon boundary.
+ */
+ newState = ! e->Rface->inside;
+ if( edgeState != newState ) {
+ edgeState = newState;
+ CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( edgeState );
+ }
+ }
+ CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
+
+ e = e->Lnext;
+ } while( e != f->anEdge );
+ }
+ CALL_END_OR_END_DATA();
+}
+
+
+static void RenderFan( GLUtesselator *tess, GLUhalfEdge *e, long size )
+{
+ /* Render as many CCW triangles as possible in a fan starting from
+ * edge "e". The fan *should* contain exactly "size" triangles
+ * (otherwise we've goofed up somewhere).
+ */
+ CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_FAN );
+ CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
+ CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
+
+ while( ! Marked( e->Lface )) {
+ e->Lface->marked = TRUE;
+ --size;
+ e = e->Onext;
+ CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
+ }
+
+ assert( size == 0 );
+ CALL_END_OR_END_DATA();
+}
+
+
+static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *e, long size )
+{
+ /* Render as many CCW triangles as possible in a strip starting from
+ * edge "e". The strip *should* contain exactly "size" triangles
+ * (otherwise we've goofed up somewhere).
+ */
+ CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_STRIP );
+ CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
+ CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
+
+ while( ! Marked( e->Lface )) {
+ e->Lface->marked = TRUE;
+ --size;
+ e = e->Dprev;
+ CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
+ if( Marked( e->Lface )) break;
+
+ e->Lface->marked = TRUE;
+ --size;
+ e = e->Onext;
+ CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data );
+ }
+
+ assert( size == 0 );
+ CALL_END_OR_END_DATA();
+}
+
+
+/************************ Boundary contour decomposition ******************/
+
+/* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one
+ * contour for each face marked "inside". The rendering output is
+ * provided as callbacks (see the api).
+ */
+void __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh )
+{
+ GLUface *f;
+ GLUhalfEdge *e;
+
+ for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
+ if( f->inside ) {
+ CALL_BEGIN_OR_BEGIN_DATA( GL_LINE_LOOP );
+ e = f->anEdge;
+ do {
+ CALL_VERTEX_OR_VERTEX_DATA( e->Org->data );
+ e = e->Lnext;
+ } while( e != f->anEdge );
+ CALL_END_OR_END_DATA();
+ }
+ }
+}
+
+
+/************************ Quick-and-dirty decomposition ******************/
+
+#define SIGN_INCONSISTENT 2
+
+static int ComputeNormal( GLUtesselator *tess, GLdouble norm[3], int check )
+/*
+ * If check==FALSE, we compute the polygon normal and place it in norm[].
+ * If check==TRUE, we check that each triangle in the fan from v0 has a
+ * consistent orientation with respect to norm[]. If triangles are
+ * consistently oriented CCW, return 1; if CW, return -1; if all triangles
+ * are degenerate return 0; otherwise (no consistent orientation) return
+ * SIGN_INCONSISTENT.
+ */
+{
+ CachedVertex *v0 = tess->cache;
+ CachedVertex *vn = v0 + tess->cacheCount;
+ CachedVertex *vc;
+ GLdouble dot, xc, yc, zc, xp, yp, zp, n[3];
+ int sign = 0;
+
+ /* Find the polygon normal. It is important to get a reasonable
+ * normal even when the polygon is self-intersecting (eg. a bowtie).
+ * Otherwise, the computed normal could be very tiny, but perpendicular
+ * to the true plane of the polygon due to numerical noise. Then all
+ * the triangles would appear to be degenerate and we would incorrectly
+ * decompose the polygon as a fan (or simply not render it at all).
+ *
+ * We use a sum-of-triangles normal algorithm rather than the more
+ * efficient sum-of-trapezoids method (used in CheckOrientation()
+ * in normal.c). This lets us explicitly reverse the signed area
+ * of some triangles to get a reasonable normal in the self-intersecting
+ * case.
+ */
+ if( ! check ) {
+ norm[0] = norm[1] = norm[2] = 0.0;
+ }
+
+ vc = v0 + 1;
+ xc = vc->coords[0] - v0->coords[0];
+ yc = vc->coords[1] - v0->coords[1];
+ zc = vc->coords[2] - v0->coords[2];
+ while( ++vc < vn ) {
+ xp = xc; yp = yc; zp = zc;
+ xc = vc->coords[0] - v0->coords[0];
+ yc = vc->coords[1] - v0->coords[1];
+ zc = vc->coords[2] - v0->coords[2];
+
+ /* Compute (vp - v0) cross (vc - v0) */
+ n[0] = yp*zc - zp*yc;
+ n[1] = zp*xc - xp*zc;
+ n[2] = xp*yc - yp*xc;
+
+ dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*norm[2];
+ if( ! check ) {
+ /* Reverse the contribution of back-facing triangles to get
+ * a reasonable normal for self-intersecting polygons (see above)
+ */
+ if( dot >= 0 ) {
+ norm[0] += n[0]; norm[1] += n[1]; norm[2] += n[2];
+ } else {
+ norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= n[2];
+ }
+ } else if( dot != 0 ) {
+ /* Check the new orientation for consistency with previous triangles */
+ if( dot > 0 ) {
+ if( sign < 0 ) return SIGN_INCONSISTENT;
+ sign = 1;
+ } else {
+ if( sign > 0 ) return SIGN_INCONSISTENT;
+ sign = -1;
+ }
+ }
+ }
+ return sign;
+}
+
+/* __gl_renderCache( tess ) takes a single contour and tries to render it
+ * as a triangle fan. This handles convex polygons, as well as some
+ * non-convex polygons if we get lucky.
+ *
+ * Returns TRUE if the polygon was successfully rendered. The rendering
+ * output is provided as callbacks (see the api).
+ */
+GLboolean __gl_renderCache( GLUtesselator *tess )
+{
+ CachedVertex *v0 = tess->cache;
+ CachedVertex *vn = v0 + tess->cacheCount;
+ CachedVertex *vc;
+ GLdouble norm[3];
+ int sign;
+
+ if( tess->cacheCount < 3 ) {
+ /* Degenerate contour -- no output */
+ return TRUE;
+ }
+
+ norm[0] = tess->normal[0];
+ norm[1] = tess->normal[1];
+ norm[2] = tess->normal[2];
+ if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) {
+ ComputeNormal( tess, norm, FALSE );
+ }
+
+ sign = ComputeNormal( tess, norm, TRUE );
+ if( sign == SIGN_INCONSISTENT ) {
+ /* Fan triangles did not have a consistent orientation */
+ return FALSE;
+ }
+ if( sign == 0 ) {
+ /* All triangles were degenerate */
+ return TRUE;
+ }
+
+ /* Make sure we do the right thing for each winding rule */
+ switch( tess->windingRule ) {
+ case GLU_TESS_WINDING_ODD:
+ case GLU_TESS_WINDING_NONZERO:
+ break;
+ case GLU_TESS_WINDING_POSITIVE:
+ if( sign < 0 ) return TRUE;
+ break;
+ case GLU_TESS_WINDING_NEGATIVE:
+ if( sign > 0 ) return TRUE;
+ break;
+ case GLU_TESS_WINDING_ABS_GEQ_TWO:
+ return TRUE;
+ }
+
+ CALL_BEGIN_OR_BEGIN_DATA( tess->boundaryOnly ? GL_LINE_LOOP
+ : (tess->cacheCount > 3) ? GL_TRIANGLE_FAN
+ : GL_TRIANGLES );
+
+ CALL_VERTEX_OR_VERTEX_DATA( v0->data );
+ if( sign > 0 ) {
+ for( vc = v0+1; vc < vn; ++vc ) {
+ CALL_VERTEX_OR_VERTEX_DATA( vc->data );
+ }
+ } else {
+ for( vc = vn-1; vc > v0; --vc ) {
+ CALL_VERTEX_OR_VERTEX_DATA( vc->data );
+ }
+ }
+ CALL_END_OR_END_DATA();
+ return TRUE;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-29 09:48:28 +0000