/* * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the "Software"), * to deal in the Software without restriction, including without limitation * the rights to use, copy, modify, merge, publish, distribute, sublicense, * and/or sell copies of the Software, and to permit persons to whom the * Software is furnished to do so, subject to the following conditions: * * The above copyright notice including the dates of first publication and * either this permission notice or a reference to * http://oss.sgi.com/projects/FreeB/ * shall be included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. * * Except as contained in this notice, the name of Silicon Graphics, Inc. * shall not be used in advertising or otherwise to promote the sale, use or * other dealings in this Software without prior written authorization from * Silicon Graphics, Inc. */ /* ** Author: Eric Veach, July 1994. ** */ #include "gluos.h" #include #include #include #include "mesh.h" #include "tess.h" #include "render.h" #ifndef TRUE #define TRUE 1 #endif #ifndef FALSE #define FALSE 0 #endif /* 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) do { \ while( (t) != NULL ) { \ (t)->marked = FALSE; t = (t)->trail; \ } \ } while(0) /* 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; } } } //printf("%f, %f, %f -- %d\n", norm[0], norm[1], norm[2], sign); 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; }