/*
* 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 <assert.h>
#include <stddef.h>
#include <stdio.h>
#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;
}