Merging in work from 3.1/3.2 branch. Tessellator is essentially fully

functional now.

5 files changed, 555 insertions, 477 deletions

diff --git a/src/glu/mesa/Makefile.BeOS b/src/glu/mesa/Makefile.BeOS
index 989ad7c157d..e8851dea444 100644
--- a/src/glu/mesa/Makefile.BeOS
+++ b/src/glu/mesa/Makefile.BeOS
@@ -30,7 +30,7 @@ LIBDIR = ../lib
 
 SOURCES = glu.c mipmap.c nurbs.c nurbscrv.c nurbssrf.c nurbsutl.c \
 	project.c quadric.c tess.c tess_fist.c tess_hash.c tess_heap.c \
-	tess_winding.c
+	tess_winding.c tess_clip.c
 
 OBJECTS = $(SOURCES:.c=.o)
 
diff --git a/src/glu/mesa/Makefile.BeOS-R4 b/src/glu/mesa/Makefile.BeOS-R4
index 1285db4c333..ebe3a689d38 100644
--- a/src/glu/mesa/Makefile.BeOS-R4
+++ b/src/glu/mesa/Makefile.BeOS-R4
@@ -19,9 +19,13 @@
 # Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
 
-# $Id: Makefile.BeOS-R4,v 1.5 1999/10/03 00:53:38 gareth Exp $
+# $Id: Makefile.BeOS-R4,v 1.6 1999/12/06 09:39:34 gareth Exp $
 
 # $Log: Makefile.BeOS-R4,v $
+# Revision 1.6  1999/12/06 09:39:34  gareth
+# Merging in work from 3.1/3.2 branch.  Tessellator is essentially fully
+# functional now.
+#
 # Revision 1.5  1999/10/03 00:53:38  gareth
 # Added tessellation winding rule files.
 #
@@ -59,7 +63,7 @@ LIBDIR = ../lib
 
 SOURCES = glu.c mipmap.c nurbs.c nurbscrv.c nurbssrf.c nurbsutl.c \
 	project.c quadric.c tess.c tess_fist.c tess_hash.c tess_heap.c \
-	tess_winding.c
+	tess_winding.c tess_clip.c
 
 OBJECTS = $(SOURCES:.c=.o)
 
diff --git a/src/glu/mesa/Makefile.X11 b/src/glu/mesa/Makefile.X11
index 3036001776c..4373c8f2b4d 100644
--- a/src/glu/mesa/Makefile.X11
+++ b/src/glu/mesa/Makefile.X11
@@ -1,4 +1,4 @@
-# $Id: Makefile.X11,v 1.6 1999/10/03 00:53:38 gareth Exp $
+# $Id: Makefile.X11,v 1.7 1999/12/06 09:39:34 gareth Exp $
 
 # Mesa 3-D graphics library
 # Version:  3.1
@@ -20,7 +20,7 @@ LIBDIR = ../lib
 
 SOURCES = glu.c mipmap.c nurbs.c nurbscrv.c nurbssrf.c nurbsutl.c \
 	project.c quadric.c tess.c tess_fist.c tess_hash.c tess_heap.c \
-	tess_winding.c
+	tess_winding.c tess_clip.c
 
 OBJECTS = $(SOURCES:.c=.o)
 
diff --git a/src/glu/mesa/tess.c b/src/glu/mesa/tess.c
index 7f1b5a56823..f48c6a01719 100644
--- a/src/glu/mesa/tess.c
+++ b/src/glu/mesa/tess.c
@@ -1,4 +1,4 @@
-/* $Id: tess.c,v 1.21 1999/11/11 03:21:43 kendallb Exp $ */
+/* $Id: tess.c,v 1.22 1999/12/06 09:39:34 gareth Exp $ */
 
 /*
  * Mesa 3-D graphics library
@@ -33,7 +33,9 @@
 #include <stdarg.h>
 #include <stdio.h>
 #include <stdlib.h>
-#include <GL/glu.h>
+#include <math.h>
+
+#include "gluP.h"
 
 #include "tess.h"
 #include "tess_macros.h"
@@ -42,23 +44,503 @@
 #include "tess_grid.h"
 #endif
 
+
+#define TESS_CHECK_ERRORS(t)	if ( (t)->error != GLU_NO_ERROR ) goto cleanup
+
+#ifdef DEBUG
+GLint		tess_dbg_level;
+#endif
+
+
 /*****************************************************************************
- * Internal function prototypes:
+ * tess_error_callback
+ *
+ * Internal error handler.  Call the user-registered error callback.
+ *
+ * 2nd arg changed from 'errno' to 'errnum' since MSVC defines errnum as
+ *  a macro (of all things) and thus breaks the build -tjump
  *****************************************************************************/
+void tess_error_callback( GLUtesselator *tobj, GLenum errnum )
+{
+    if ( tobj->error == GLU_NO_ERROR )
+    {
+	tobj->error = errnum;
+    }
 
-static void init_callbacks( tess_callbacks_t *callbacks );
+    if ( tobj->callbacks.errorData != NULL )
+    {
+	( tobj->callbacks.errorData )( errnum, tobj->data );
+    }
+    else if ( tobj->callbacks.error != NULL )
+    {
+	( tobj->callbacks.error )( errnum );
+    }
+}
 
-static void tess_cleanup( GLUtesselator *tobj );
-static void inspect_current_contour( GLUtesselator *tobj );
 
-void delete_contour( tess_contour_t **contour );
-static void delete_all_contours( GLUtesselator *tobj );
+/*****************************************************************************
+ * init_callbacks
+ *****************************************************************************/
+static void init_callbacks( tess_callbacks_t *callbacks )
+{
+    callbacks->begin        = ( void (GLCALLBACKP)(GLenum) ) NULL;
+    callbacks->beginData    = ( void (GLCALLBACKP)(GLenum, void *) ) NULL;
+    callbacks->edgeFlag     = ( void (GLCALLBACKP)(GLboolean) ) NULL;
+    callbacks->edgeFlagData = ( void (GLCALLBACKP)(GLboolean, void *) ) NULL;
+    callbacks->vertex       = ( void (GLCALLBACKP)(void *) ) NULL;
+    callbacks->vertexData   = ( void (GLCALLBACKP)(void *, void *) ) NULL;
+    callbacks->end          = ( void (GLCALLBACKP)(void) ) NULL;
+    callbacks->endData      = ( void (GLCALLBACKP)(void *) ) NULL;
+    callbacks->error        = ( void (GLCALLBACKP)(GLenum) ) NULL;
+    callbacks->errorData    = ( void (GLCALLBACKP)(GLenum, void *) ) NULL;
+    callbacks->combine      = ( void (GLCALLBACKP)(GLdouble [3], void *[4],
+						   GLfloat [4], void **) ) NULL;
+    callbacks->combineData  = ( void (GLCALLBACKP)(GLdouble [3], void *[4],
+						   GLfloat [4], void **,
+						   void *) ) NULL;
+}
 
-#define TESS_CHECK_ERRORS(t)	if ( (t)->error != GLU_NO_ERROR ) goto cleanup
 
+/*****************************************************************************
+ * find_normal
+ *****************************************************************************/
+static GLenum find_normal( GLUtesselator *tobj )
+{
+    tess_contour_t	*contour = tobj->current_contour;
+    tess_vertex_t	*va, *vb, *vc;
+    GLdouble		a[3], b[3], c[3];
+
+    MSG( 15, "      --> find_normal( tobj:%p )\n", tobj );
+
+    if ( contour == NULL ) { return GLU_ERROR; }
+
+    va = contour->vertices;
+    vb = va->next;
+
+    /* If va and vb are the same point, keep looking for a different vertex. */
+
+    while ( IS_EQUAL_3DV( va->coords, vb->coords ) && ( vb != va ) ) {
+	vb = vb->next;
+    }
+
+    if ( vb == va ) {
+	/* FIXME: What error is this? */
+	tess_error_callback( tobj, GLU_TESS_ERROR7 );
+    }
+
+    SUB_3V( a, vb->coords, va->coords );
+
+    for ( vc = vb->next; vc != va; vc = vc->next )
+    {
+	SUB_3V( b, vc->coords, va->coords );
+
+	CROSS_3V( c, a, b );
+
+	if ( ! IS_ZERO_3DV( c ) )
+	{
+	    MSG( 15, "            using (%.2f,%.2f) -> (%.2f,%.2f) -> (%.2f,%.2f)\n",
+		 va->coords[X], va->coords[Y],
+		 vb->coords[X], vb->coords[Y],
+		 vc->coords[X], vc->coords[Y] );
+
+	    COPY_3V( contour->plane.normal, c );
+	    NORMALIZE_3DV( contour->plane.normal );
+
+	    contour->plane.dist = - DOT_3V( contour->plane.normal,
+					    va->coords );
+
+	    MSG( 15, "      <-- find_normal( tobj:%p ) n: (%.2f, %.2f, %.2f)\n", tobj, contour->plane.normal[X], contour->plane.normal[Y], contour->plane.normal[Z] );
+	    return GLU_NO_ERROR;
+	}
+    }
+    /* FIXME: What error is this? */
+    tess_error_callback( tobj, GLU_TESS_ERROR7 );
+
+    return GLU_ERROR;
+}
+
+/*****************************************************************************
+ * twice_contour_area
+ *
+ * Calculate the twice the signed area of the given contour.  Used to
+ * determine the contour's orientation amongst other things.
+ *****************************************************************************/
+GLdouble twice_contour_area( tess_contour_t *contour )
+{
+    tess_vertex_t	*vertex = contour->vertices;
+    GLdouble		area, x, y;
+
+    area = 0.0;
+
+    x = vertex->v[X];
+    y = vertex->v[Y];
+
+    vertex = vertex->next;
+
+    do
+    {
+	area += ( (vertex->v[X] - x) * (vertex->next->v[Y] - y) -
+		  (vertex->v[Y] - y) * (vertex->next->v[X] - x) );
+	vertex = vertex->next;
+    }
+    while ( vertex != contour->vertices );
+
+    return area;
+}
+
+/*****************************************************************************
+ * project_current_contour
+ *
+ * Project the contour's vertices onto the tessellation plane.  We perform
+ * a complex rotation here to allow non-axis-aligned tessellation normals.
+ *****************************************************************************/
+static void project_current_contour( GLUtesselator *tobj )
+{
+    tess_contour_t	*current = tobj->current_contour;
+    tess_vertex_t	*vertex;
+    GLdouble		zaxis[3] = { 0.0, 0.0, 1.0 }, znormal[3], xnormal[3];
+    GLdouble		dot, rotx, roty;
+    GLint		i;
+
+    MSG( 15, "      --> project_current_contour( tobj:%p )\n", tobj );
+
+    if ( current == NULL ) { return; }
+
+    /* Rotate the plane normal around the y-axis. */
+
+    znormal[X] = current->plane.normal[X];
+    znormal[Y] = 0.0;
+    znormal[Z] = current->plane.normal[Z];
+
+    dot = DOT_3V( znormal, zaxis );
+    current->roty = roty = acos( dot );
+
+    /* Rotate the plane normal around the x-axis. */
+
+    xnormal[X] = cos( roty ) * znormal[X] - sin( roty ) * znormal[Z];
+    xnormal[Y] = znormal[Y];
+    xnormal[Z] = sin( roty ) * znormal[X] + cos( roty ) * znormal[Z];
+
+    dot = DOT_3V( xnormal, zaxis );
+    current->rotx = rotx = acos( dot );
+
+    for ( vertex = current->vertices, i = 0;
+	  i < current->num_vertices; vertex = vertex->next, i++ )
+    {
+	tess_plane_t	*plane = &current->plane;
+	GLdouble	proj[3], yrot[3], xrot[3];
+
+	/* FIXME: This needs a cleanup, 'cos I'm sure it's inefficient. */
+
+	proj[X] = vertex->coords[X] - plane->dist * plane->normal[X];
+	proj[Y] = vertex->coords[Y] - plane->dist * plane->normal[Y];
+	proj[Z] = vertex->coords[Z] - plane->dist * plane->normal[Z];
+
+	yrot[X] = cos( roty ) * proj[X] - sin( roty ) * proj[Z];
+	yrot[Y] = proj[Y];
+	yrot[Z] = sin( roty ) * proj[X] + cos( roty ) * proj[Z];
+
+	xrot[X] = yrot[X];
+	xrot[Y] = cos( rotx ) * yrot[Y] - sin( rotx ) * yrot[Z];
+	xrot[Z] = sin( rotx ) * yrot[Y] + cos( rotx ) * yrot[Z];
+
+	vertex->v[X] = xrot[X];
+	vertex->v[Y] = xrot[Y];
+
+	ACC_BBOX_2V( vertex->v, tobj->mins, tobj->maxs );
+	ACC_BBOX_2V( vertex->v, current->mins, current->maxs );
+    }
+
+    current->area = twice_contour_area( current );
+    current->orientation = ( current->area >= 0.0 ) ? GLU_CCW : GLU_CW;
+
+    MSG( 15, "            area: %.2f orientation: %s\n",
+	 current->area, ( current->orientation == GLU_CCW ) ? "CCW" : "CW" );
+
+    MSG( 15, "      <-- project_current_contour( tobj:%p )\n", tobj );
+}
+
+/*****************************************************************************
+ * save_current_contour
+ *****************************************************************************/
+static GLenum save_current_contour( GLUtesselator *tobj )
+{
+    tess_contour_t	*current = tobj->current_contour;
+    tess_vertex_t	*vertex;
+    GLint		i;
+
+    if ( current == NULL ) { return GLU_ERROR; }
+
+    if ( tobj->contours == NULL )
+    {
+	tobj->contours = tobj->last_contour = current;
+	current->next = current->prev = NULL;
+
+	tobj->orientation = current->orientation;
+    }
+    else
+    {
+	current->prev = tobj->last_contour;
+
+	tobj->last_contour->next = current;
+	tobj->last_contour = current;
+
+	current->next = NULL;
+    }
+
+    for ( vertex = current->vertices, i = 0;
+	  i < current->num_vertices; vertex = vertex->next, i++ )
+    {
+	vertex->edge_flag = GL_TRUE;
+    }
+
+    current->type = GLU_UNKNOWN;
+
+    tobj->num_contours++;
+    tobj->current_contour = NULL;
+
+    return GLU_NO_ERROR;
+}
+
+/*****************************************************************************
+ * inspect_current_contour
+ *****************************************************************************/
+static void inspect_current_contour( GLUtesselator *tobj )
+{
+    tess_contour_t	*current = tobj->current_contour;
+    GLdouble		origin[3] = { 0.0, 0.0, 0.0 };
+    GLboolean		calc_normal = GL_FALSE;
+
+    MSG( 15, "    --> inspect_current_contour( tobj:%p )\n", tobj );
+
+    if ( current->num_vertices < 3 )
+    {
+	MSG( 15, "          count %d < 3, deleting\n", current->num_vertices );
+	delete_contour( &tobj->current_contour );
+	return;
+    }
+
+    current->last_vertex->next = current->vertices;
+    current->vertices->prev = current->last_vertex;
+
+    MSG( 15, "          current normal: (%.2f, %.2f, %.2f)\n", current->plane.normal[X], current->plane.normal[Y], current->plane.normal[Z] );
+
+    if ( IS_EQUAL_3DV( current->plane.normal, origin ) )
+    {
+	/* We haven't been given a normal, so let's take a guess. */
+	if ( find_normal( tobj ) == GLU_ERROR ) {
+	    return;
+	}
+
+	COPY_3V( tobj->plane.normal, current->plane.normal );
+	tobj->plane.dist = current->plane.dist;
+
+	calc_normal = GL_TRUE;
+    }
+
+    project_current_contour( tobj );
+
+    if ( calc_normal && ( tobj->current_contour->orientation == GLU_CW ) )
+    {
+	MSG( 15, "          oops, let's try that again...\n" );
+
+	/*
+	 * FIXME: We've used a reflex angle to calculate the normal.  At
+	 * the moment, we simply reverse the normal and re-project the
+	 * contour, but this is sloooow...
+	 */
+	NEG_3V( tobj->plane.normal );
+	NEG_3V( tobj->current_contour->plane.normal );
+
+	project_current_contour( tobj );
+    }
+
+    if ( save_current_contour( tobj ) == GLU_ERROR ) {
+	return;
+    }
+
+    MSG( 15, "    <-- inspect_current_contour( tobj:%p )\n", tobj );
+}
+
+/*****************************************************************************
+ * reverse_contour
+ *****************************************************************************/
+void reverse_contour( tess_contour_t *contour )
+{
+    tess_vertex_t	*current = contour->vertices;
+    GLint		i;
+
+    for ( i = 0 ; i < contour->num_vertices ; i++ )
+    {
+	tess_vertex_t	*next = current->next;
+	tess_vertex_t	*prev = current->prev;
+
+	current->next = prev;
+	current->prev = next;
+
+	current = next;
+    }
+
+    contour->orientation =
+	( contour->orientation == GLU_CCW ) ? GLU_CW : GLU_CCW;
+
+    contour->last_vertex = contour->vertices->prev;
+}
+
+/*****************************************************************************
+ * orient_contours
+ *
+ * Sum the signed areas of the contours, and orient the contours such that
+ * this sum is nonnegative.
+ *****************************************************************************/
+static void orient_contours( GLUtesselator *tobj )
+{
+    tess_contour_t	*contour = tobj->contours;
+    GLdouble		sum = 0.0;
+    GLint		i;
+
+    MSG( 15, "    --> orient_contours( tobj:%p )\n", tobj );
+
+    /* Sum the signed areas of all contours */
+    for ( i = 0 ; i < tobj->num_contours ; i++ )
+    {
+	sum += contour->area;
+	contour = contour->next;
+    }
+
+    MSG( 15, "          signed area: %.2f\n", sum );
+
+    if ( sum < -GLU_TESS_EPSILON )
+    {
+	for ( i = 0 ; i < tobj->num_contours ; i++ )
+	{
+	    contour->area = ABSD( contour->area );
+	    reverse_contour( contour );
+
+	    contour = contour->next;
+	}
+    }
+    else
+    {
+	for ( i = 0 ; i < tobj->num_contours ; i++ )
+	{
+	    contour->area = ABSD( contour->area );
+
+	    contour = contour->next;
+	}
+    }
+
+    tobj->orientation = tobj->contours->orientation;
+
+    MSG( 15, "    <-- orient_contours( tobj:%p ) orient: %s\n",
+	 tobj, ( tobj->orientation == GLU_CCW ) ? "GLU_CCW" : "GLU_CW" );
+}
+
+
+/*****************************************************************************
+ * delete_contour
+ *
+ * Delete the given contour and set the pointer to NULL.
+ *****************************************************************************/
+void delete_contour( tess_contour_t **contour )
+{
+    tess_vertex_t	*vertex, *next;
+    GLint		i;
+
+    if ( *contour == NULL ) { return; }
+
+    vertex = (*contour)->vertices;
+
+    for ( i = 0 ; i < (*contour)->num_vertices ; i++ )
+    {
+	next = vertex->next;
+	free( vertex );
+	vertex = next;
+    }
+
+    free( *contour );
+    *contour = NULL;
+}
+
+/*****************************************************************************
+ * delete_all_contours
+ *****************************************************************************/
+static void delete_all_contours( GLUtesselator *tobj )
+{
+    tess_contour_t	*current, *next_contour;
+    GLint		i;
+
+    if ( tobj->current_contour != NULL ) {
+	delete_contour( &tobj->current_contour );
+    }
+
+    for ( current = tobj->contours, i = 0 ; i < tobj->num_contours ; i++ )
+    {
+	tess_vertex_t	*vertex = current->vertices, *next_vertex;
+	GLint		j;
+
+	for ( j = 0 ; j < current->num_vertices ; j ++ )
+	{
+	    next_vertex = vertex->next;
+	    free( vertex );
+	    vertex = next_vertex;
+	}
+	next_contour = current->next;
+
+	free( current );
+	current = next_contour;
+    }
+
+    tobj->num_contours = tobj->num_vertices = 0;
+    tobj->contours = tobj->last_contour = NULL;
+
+    CLEAR_BBOX_2DV( tobj->mins, tobj->maxs );
+}
+
+
+/*****************************************************************************
+ * tess_cleanup
+ *****************************************************************************/
+static void tess_cleanup( GLUtesselator *tobj )
+{
+    MSG( 15, "  -> tess_cleanup( tobj:%p )\n", tobj );
+
+    if ( tobj->current_contour != NULL ) {
+	delete_contour( &tobj->current_contour );
+    }
+    if ( tobj->contours != NULL ) {
+	delete_all_contours( tobj );
+    }
+
+    MSG( 15, "  <- tess_cleanup( tobj:%p )\n", tobj );
+}
+
+
+/*****************************************************************************
+ * tess_msg
+ *****************************************************************************/
+INLINE void tess_msg( GLint level, char *format, ... )
+{
 #ifdef DEBUG
-GLint		tess_dbg_level;
+    va_list ap;
+    va_start( ap, format );
+
+    if ( level <= tess_dbg_level ) {
+	vfprintf( DBG_STREAM, format, ap );
+	fflush( DBG_STREAM );
+    }
+
+    va_end( ap );
 #endif
+}
+
+INLINE void tess_info( char *file, GLint line )
+{
+#ifdef DEBUG
+    fprintf( DBG_STREAM, "%9.9s:%d:\t ", file, line );
+#endif
+}
+
 
 
 /*****************************************************************************
@@ -92,31 +574,30 @@ GLUtesselator* GLAPIENTRY gluNewTess( void )
 
     init_callbacks( &tobj->callbacks );
 
-    tobj->boundary_only = GL_FALSE;
     tobj->winding_rule = GLU_TESS_WINDING_ODD;
-    tobj->tolerance = 0.0;
+    tobj->boundary_only = GL_FALSE;
+    tobj->tolerance = GLU_TESS_EPSILON;
+    tobj->orientation = GLU_UNKNOWN;
 
-    tobj->plane.normal[X] = 0.0;
-    tobj->plane.normal[Y] = 0.0;
-    tobj->plane.normal[Z] = 0.0;
-    tobj->plane.dist = 0.0;
+    tobj->data = NULL;
 
-    tobj->contour_count = 0;
+    tobj->num_contours = 0;
     tobj->contours = tobj->last_contour = NULL;
     tobj->current_contour = NULL;
 
     CLEAR_BBOX_2DV( tobj->mins, tobj->maxs );
 
-    tobj->vertex_count = 0;
+    tobj->num_vertices = 0;
     tobj->sorted_vertices = NULL;
 #if 0
     tobj->grid = NULL;
 #endif
-    tobj->cvc_lists = NULL;
-    tobj->data = NULL;
     tobj->edge_flag = GL_FALSE;
     tobj->label = 0;
 
+    ZERO_3V( tobj->plane.normal );
+    tobj->plane.dist = 0.0;
+
     tobj->error = GLU_NO_ERROR;
 
     MSG( 15, "<- gluNewTess() tobj:%p\n", tobj );
@@ -131,7 +612,7 @@ void GLAPIENTRY gluDeleteTess( GLUtesselator *tobj )
 {
     MSG( 15, "-> gluDeleteTess( tobj:%p )\n", tobj );
 
-    if ( ( tobj->error == GLU_NO_ERROR ) && ( tobj->contour_count > 0 ) )
+    if ( ( tobj->error == GLU_NO_ERROR ) && ( tobj->num_contours > 0 ) )
     {
 	/* gluEndPolygon was not called. */
 	tess_error_callback( tobj, GLU_TESS_ERROR3 );
@@ -161,8 +642,8 @@ void GLAPIENTRY gluTessBeginPolygon( GLUtesselator *tobj, void *polygon_data )
 	tess_cleanup( tobj );
     }
 
-    tobj->vertex_count = 0;
     tobj->data = polygon_data;
+    tobj->num_vertices = 0;
     tobj->edge_flag = GL_FALSE;
     tobj->label = 0;
 
@@ -200,17 +681,16 @@ void GLAPIENTRY gluTessBeginContour( GLUtesselator *tobj )
     tobj->current_contour->label = 0;
     tobj->current_contour->winding = 0;
 
-    tobj->current_contour->rotx = tobj->current_contour->roty = 0.0;
+    /*tobj->current_contour->rotx = tobj->current_contour->roty = 0.0;*/
 
     CLEAR_BBOX_2DV( tobj->current_contour->mins,
 		    tobj->current_contour->maxs );
 
-    tobj->current_contour->vertex_count = 0;
+    tobj->current_contour->num_vertices = 0;
     tobj->current_contour->vertices =
 	tobj->current_contour->last_vertex = NULL;
 
     tobj->current_contour->reflex_vertices = NULL;
-    tobj->current_contour->cross_vertices = hashtable_init( HT_DEFAULT_SIZE );
 
  cleanup:
     MSG( 15, "  <- gluTessBeginContour( tobj:%p )\n", tobj );
@@ -237,7 +717,7 @@ void GLAPIENTRY gluTessVertex( GLUtesselator *tobj, GLdouble coords[3],
 	return;
     }
 
-    tobj->vertex_count++;
+    tobj->num_vertices++;
 
     last_vertex = current->last_vertex;
 
@@ -259,14 +739,17 @@ void GLAPIENTRY gluTessVertex( GLUtesselator *tobj, GLdouble coords[3],
 	last_vertex->coords[Y] = coords[Y];
 	last_vertex->coords[Z] = coords[Z];
 
+	last_vertex->v[X] = 0.0;
+	last_vertex->v[Y] = 0.0;
+
+	last_vertex->edge_flag = GL_TRUE;
+
 	last_vertex->side = 0.0;
-	last_vertex->label = 0;
-	last_vertex->mark = 0;
 
 	last_vertex->next = NULL;
-	last_vertex->previous = NULL;
+	last_vertex->prev = NULL;
 
-	current->vertex_count++;
+	current->num_vertices++;
     }
     else
     {
@@ -285,14 +768,17 @@ void GLAPIENTRY gluTessVertex( GLUtesselator *tobj, GLdouble coords[3],
 	vertex->coords[Y] = coords[Y];
 	vertex->coords[Z] = coords[Z];
 
+	vertex->v[X] = 0.0;
+	vertex->v[Y] = 0.0;
+
+	vertex->edge_flag = GL_TRUE;
+
 	vertex->side = 0.0;
-	vertex->label = 0;
-	vertex->mark = 0;
 
 	vertex->next = NULL;
-	vertex->previous = last_vertex;
+	vertex->prev = last_vertex;
 
-	current->vertex_count++;
+	current->num_vertices++;
 
 	last_vertex->next = vertex;
 	current->last_vertex = vertex;
@@ -319,7 +805,7 @@ void GLAPIENTRY gluTessEndContour( GLUtesselator *tobj )
 	return;
     }
 
-    if ( tobj->current_contour->vertex_count > 0 ) {
+    if ( tobj->current_contour->num_vertices > 0 ) {
 	inspect_current_contour( tobj );
     } else {
 	delete_contour( &tobj->current_contour );
@@ -351,7 +837,7 @@ void GLAPIENTRY gluTessEndPolygon( GLUtesselator *tobj )
      * Ensure we have at least one contour to tessellate.  If we have none,
      *  clean up and exit gracefully.
      */
-    if ( tobj->contour_count == 0 ) {
+    if ( tobj->num_contours == 0 ) {
 	tess_cleanup( tobj );
 	return;
     }
@@ -359,10 +845,13 @@ void GLAPIENTRY gluTessEndPolygon( GLUtesselator *tobj )
     /* Wrap the contour list. */
 
     tobj->last_contour->next = tobj->contours;
-    tobj->contours->previous = tobj->last_contour;
+    tobj->contours->prev = tobj->last_contour;
 
     TESS_CHECK_ERRORS( tobj );
 
+    /* Orient the contours correctly */
+    orient_contours( tobj );
+
     /*
      * Before we tessellate the contours, ensure we have the appropriate
      *  callbacks registered.  We at least need the begin, vertex and end
@@ -406,7 +895,7 @@ void GLAPIENTRY gluTessCallback( GLUtesselator *tobj, GLenum which,
 	break;
     case GLU_TESS_EDGE_FLAG_DATA:
 	tobj->callbacks.edgeFlagData =
-		(void (GLCALLBACKP)(GLboolean, void *)) fn;
+	    (void (GLCALLBACKP)(GLboolean, void *)) fn;
 	break;
 
 	/* Register the vertex callbacks. */
@@ -436,12 +925,12 @@ void GLAPIENTRY gluTessCallback( GLUtesselator *tobj, GLenum which,
 	/* Register the combine callbacks. */
     case GLU_TESS_COMBINE:
 	tobj->callbacks.combine =
-		(void (GLCALLBACKP)(GLdouble[3], void *[4],
+	    (void (GLCALLBACKP)(GLdouble[3], void *[4],
 				GLfloat [4], void **)) fn;
 	break;
     case GLU_TESS_COMBINE_DATA:
 	tobj->callbacks.combineData =
-		(void (GLCALLBACKP)(GLdouble[3], void *[4], GLfloat [4],
+	    (void (GLCALLBACKP)(GLdouble[3], void *[4], GLfloat [4],
 				void **, void *)) fn;
 	break;
 
@@ -524,9 +1013,7 @@ void GLAPIENTRY gluTessNormal( GLUtesselator *tobj, GLdouble x,
 {
     MSG( 15, "   gluTessNormal( tobj:%p n:(%.2f,%.2f,%.2f) )\n", tobj, x, y, z );
 
-    tobj->plane.normal[X] = x;
-    tobj->plane.normal[Y] = y;
-    tobj->plane.normal[Z] = z;
+    ASSIGN_3V( tobj->plane.normal, x, y, z );
 }
 
 
@@ -554,422 +1041,3 @@ void GLAPIENTRY gluEndPolygon( GLUtesselator *tobj )
     gluTessEndContour( tobj );
     gluTessEndPolygon( tobj );
 }
-
-
-
-/*****************************************************************************
- * tess_error_callback
- *
- * Internal error handler.  Call the user-registered error callback.
- *
- * 2nd arg changed from 'errno' to 'errnum' since MSVC defines errnum as
- *  a macro (of all things) and thus breaks the build -tjump
- *****************************************************************************/
-
-void tess_error_callback( GLUtesselator *tobj, GLenum errnum )
-{
-    if ( tobj->error == GLU_NO_ERROR )
-    {
-	tobj->error = errnum;
-    }
-
-    if ( tobj->callbacks.errorData != NULL )
-    {
-	( tobj->callbacks.errorData )( errnum, tobj->data );
-    }
-    else if ( tobj->callbacks.error != NULL )
-    {
-	( tobj->callbacks.error )( errnum );
-    }
-}
-
-
-
-/*****************************************************************************
- *
- *				INTERNAL FUNCTIONS
- *
- *****************************************************************************/
-
-
-/*****************************************************************************
- * init_callbacks
- *****************************************************************************/
-static void init_callbacks( tess_callbacks_t *callbacks )
-{
-	callbacks->begin        = ( void (GLCALLBACKP)(GLenum) ) NULL;
-	callbacks->beginData    = ( void (GLCALLBACKP)(GLenum, void *) ) NULL;
-	callbacks->edgeFlag     = ( void (GLCALLBACKP)(GLboolean) ) NULL;
-	callbacks->edgeFlagData = ( void (GLCALLBACKP)(GLboolean, void *) ) NULL;
-	callbacks->vertex       = ( void (GLCALLBACKP)(void *) ) NULL;
-	callbacks->vertexData   = ( void (GLCALLBACKP)(void *, void *) ) NULL;
-	callbacks->end          = ( void (GLCALLBACKP)(void) ) NULL;
-	callbacks->endData      = ( void (GLCALLBACKP)(void *) ) NULL;
-	callbacks->error        = ( void (GLCALLBACKP)(GLenum) ) NULL;
-	callbacks->errorData    = ( void (GLCALLBACKP)(GLenum, void *) ) NULL;
-	callbacks->combine      = ( void (GLCALLBACKP)(GLdouble [3], void *[4],
-						   GLfloat [4], void **) ) NULL;
-	callbacks->combineData  = ( void (GLCALLBACKP)(GLdouble [3], void *[4],
-						   GLfloat [4], void **,
-						   void *) ) NULL;
-}
-
-
-/*****************************************************************************
- * tess_cleanup
- *****************************************************************************/
-static void tess_cleanup( GLUtesselator *tobj )
-{
-    MSG( 15, "  -> tess_cleanup( tobj:%p )\n", tobj );
-
-    if ( tobj->current_contour != NULL ) {
-	delete_contour( &tobj->current_contour );
-    }
-    if ( tobj->contours != NULL ) {
-	delete_all_contours( tobj );
-    }
-
-    MSG( 15, "  <- tess_cleanup( tobj:%p )\n", tobj );
-}
-
-
-/*****************************************************************************
- * inspect_current_contour
- *****************************************************************************/
-static GLenum	find_normal( GLUtesselator *tobj );
-static void	project_current_contour( GLUtesselator *tobj );
-static GLenum	save_current_contour( GLUtesselator *tobj );
-
-static void inspect_current_contour( GLUtesselator *tobj )
-{
-    tess_contour_t *current = tobj->current_contour;
-    GLdouble origin[3] = { 0.0, 0.0, 0.0 };
-
-    MSG( 15, "    -> inspect_current_contour( tobj:%p )\n", tobj );
-
-    if ( current->vertex_count < 3 )
-    {
-	MSG( 15, "         count %d < 3, deleting\n", current->vertex_count );
-	delete_contour( &tobj->current_contour );
-	return;
-    }
-
-    current->last_vertex->next = current->vertices;
-    current->vertices->previous = current->last_vertex;
-
-    if ( ( tobj->contours == NULL ) &&
-	 ( COMPARE_3DV( current->plane.normal, origin ) ) )
-    {
-	/* We haven't been given a normal, so let's take a guess. */
-	if ( find_normal( tobj ) == GLU_ERROR ) {
-	    return;
-	}
-	COPY_3V( tobj->plane.normal, current->plane.normal );
-	tobj->plane.dist = current->plane.dist;
-    }
-    else
-    {
-	MSG( 15, "         normal: (%.2f,%.2f,%.2f)\n", tobj->plane.normal[X], tobj->plane.normal[Y], tobj->plane.normal[Z] );
-    }
-
-    project_current_contour( tobj );
-
-    if ( save_current_contour( tobj ) == GLU_ERROR ) {
-	return;
-    }
-
-    MSG( 15, "    <- inspect_current_contour( tobj:%p )\n", tobj );
-}
-
-/*****************************************************************************
- * find_normal
- *****************************************************************************/
-static GLenum find_normal( GLUtesselator *tobj )
-{
-    tess_contour_t	*contour = tobj->current_contour;
-    tess_vertex_t	*va, *vb, *vc;
-    GLdouble		a[3], b[3], c[3];
-
-    MSG( 15, "      -> find_normal( tobj:%p )\n", tobj );
-
-    if ( contour == NULL ) { return GLU_ERROR; }
-
-    va = contour->vertices;
-    vb = va->next;
-
-    /* If va and vb are the same point, keep looking for a different vertex. */
-
-    while ( COMPARE_3DV( va->coords, vb->coords ) && ( vb != va ) ) {
-	vb = vb->next;
-    }
-
-    if ( vb == va ) {
-	/* FIXME: What error is this? */
-	tess_error_callback( tobj, GLU_TESS_ERROR7 );
-    }
-
-    SUB_3V( a, vb->coords, va->coords );
-
-    for ( vc = vb->next; vc != va; vc = vc->next )
-    {
-	SUB_3V( b, vc->coords, va->coords );
-
-	CROSS3( c, a, b );
-
-	if ( ( ABSD( c[X] ) > EQUAL_EPSILON ) ||
-	     ( ABSD( c[Y] ) > EQUAL_EPSILON ) ||
-	     ( ABSD( c[Z] ) > EQUAL_EPSILON ) )
-	{
-	    COPY_3V( contour->plane.normal, c );
-	    NORMALIZE_3DV( contour->plane.normal );
-
-	    contour->plane.dist = - DOT3( contour->plane.normal, va->coords );
-
-	    MSG( 15, "      <- find_normal( tobj:%p ) n: (%.2f,%.2f,%.2f)\n", tobj, contour->plane.normal[X], contour->plane.normal[Y], contour->plane.normal[Z] );
-	    return GLU_NO_ERROR;
-	}
-    }
-    /* FIXME: What error is this? */
-    tess_error_callback( tobj, GLU_TESS_ERROR7 );
-
-    return GLU_ERROR;
-}
-
-/*****************************************************************************
- * project_current_contour
- *****************************************************************************/
-static GLdouble twice_contour_area( tess_vertex_t *vertex,
-				    tess_vertex_t *last_vertex );
-
-static void project_current_contour( GLUtesselator *tobj )
-{
-    tess_contour_t	*current = tobj->current_contour;
-    tess_vertex_t	*vertex;
-    GLdouble		area;
-    GLdouble		zaxis[3] = { 0.0, 0.0, 1.0 }, znormal[3], xnormal[3];
-    GLdouble		dot, rotx, roty;
-    GLuint		i;
-
-    MSG( 15, "      -> project_current_contour( tobj:%p )\n", tobj );
-
-    if ( current == NULL ) { return; }
-
-    /* Rotate the plane normal around the y-axis. */
-
-    znormal[X] = current->plane.normal[X];
-    znormal[Y] = 0.0;
-    znormal[Z] = current->plane.normal[Z];
-
-    dot = DOT3( znormal, zaxis );
-    current->roty = roty = acos( dot );
-
-    /* Rotate the plane normal around the x-axis. */
-
-    xnormal[X] = cos( roty ) * znormal[X] - sin( roty ) * znormal[Z];
-    xnormal[Y] = znormal[Y];
-    xnormal[Z] = sin( roty ) * znormal[X] + cos( roty ) * znormal[Z];
-
-    dot = DOT3( xnormal, zaxis );
-    current->rotx = rotx = acos( dot );
-
-    for ( vertex = current->vertices, i = 0;
-	  i < current->vertex_count; vertex = vertex->next, i++ )
-    {
-	tess_plane_t	*plane = &current->plane;
-	GLdouble	proj[3], yrot[3], xrot[3];
-
-	/* FIXME: This needs a cleanup, 'cos I'm sure it's inefficient. */
-
-	proj[X] = vertex->coords[X] - plane->dist * plane->normal[X];
-	proj[Y] = vertex->coords[Y] - plane->dist * plane->normal[Y];
-	proj[Z] = vertex->coords[Z] - plane->dist * plane->normal[Z];
-
-	yrot[X] = cos( roty ) * proj[X] - sin( roty ) * proj[Z];
-	yrot[Y] = proj[Y];
-	yrot[Z] = sin( roty ) * proj[X] + cos( roty ) * proj[Z];
-
-	xrot[X] = yrot[X];
-	xrot[Y] = cos( rotx ) * yrot[Y] - sin( rotx ) * yrot[Z];
-	xrot[Z] = sin( rotx ) * yrot[Y] + cos( rotx ) * yrot[Z];
-
-	vertex->v[X] = xrot[X];
-	vertex->v[Y] = xrot[Y];
-
-	ACC_BBOX_2V( vertex->v, tobj->mins, tobj->maxs );
-	ACC_BBOX_2V( vertex->v, current->mins, current->maxs );
-    }
-
-    area = twice_contour_area( current->vertices,
-			       current->last_vertex );
-    if ( area >= 0.0 )
-    {
-	current->orientation = GLU_CCW;
-	current->area = area;
-    }
-    else
-    {
-	current->orientation = GLU_CW;
-	current->area = -area;
-    }
-
-    MSG( 15, "      <- project_current_contour( tobj:%p )\n", tobj );
-}
-
-/*****************************************************************************
- * twice_contour_area
- *****************************************************************************/
-static GLdouble twice_contour_area( tess_vertex_t *vertex,
-				    tess_vertex_t *last_vertex )
-{
-    tess_vertex_t	*next;
-    GLdouble		area, x, y;
-
-    area = 0.0;
-
-    x = vertex->v[X];
-    y = vertex->v[Y];
-
-    vertex = vertex->next;
-
-    while ( vertex != last_vertex )
-    {
-	next = vertex->next;
-	area +=
-	    (vertex->v[X] - x) * (next->v[Y] - y) -
-	    (vertex->v[Y] - y) * (next->v[X] - x);
-
-	vertex = vertex->next;
-    }
-    return area;
-}
-
-
-/*****************************************************************************
- * save_current_contour
- *****************************************************************************/
-static GLenum save_current_contour( GLUtesselator *tobj )
-{
-    tess_contour_t	*current = tobj->current_contour;
-    tess_vertex_t	*vertex;
-    GLuint			i;
-
-    if ( current == NULL ) { return GLU_ERROR; }
-
-    if ( tobj->contours == NULL )
-    {
-	tobj->contours = tobj->last_contour = current;
-	current->next = current->previous = NULL;
-    }
-    else
-    {
-	current->previous = tobj->last_contour;
-
-	tobj->last_contour->next = current;
-	tobj->last_contour = current;
-
-	current->next = NULL;
-    }
-
-    for ( vertex = current->vertices, i = 0;
-	  i < current->vertex_count; vertex = vertex->next, i++ )
-    {
-	vertex->shadow_vertex = NULL;
-	vertex->edge_flag = GL_TRUE;
-    }
-
-    current->type = GLU_UNKNOWN;
-
-    tobj->contour_count++;
-    tobj->current_contour = NULL;
-
-    return GLU_NO_ERROR;
-}
-
-/*****************************************************************************
- * delete_contour
- *
- * Delete the given contour and set the pointer to NULL.
- *****************************************************************************/
-void delete_contour( tess_contour_t **contour )
-{
-    tess_vertex_t	*vertex, *next;
-    GLuint		i;
-
-    if ( *contour == NULL ) { return; }
-
-    vertex = (*contour)->vertices;
-
-    for ( i = 0 ; i < (*contour)->vertex_count ; i++ )
-    {
-	next = vertex->next;
-	free( vertex );
-	vertex = next;
-    }
-
-    free( *contour );
-    *contour = NULL;
-}
-
-/*****************************************************************************
- * delete_all_contours
- *****************************************************************************/
-static void delete_all_contours( GLUtesselator *tobj )
-{
-    tess_contour_t	*current, *next_contour;
-    GLuint		i;
-
-    if ( tobj->current_contour != NULL ) {
-	delete_contour( &tobj->current_contour );
-    }
-
-    for ( current = tobj->contours, i = 0 ; i < tobj->contour_count ; i++ )
-    {
-	tess_vertex_t	*vertex = current->vertices, *next_vertex;
-	GLuint		j;
-
-	for ( j = 0 ; j < current->vertex_count ; j ++ )
-	{
-	    next_vertex = vertex->next;
-	    free( vertex );
-	    vertex = next_vertex;
-	}
-	next_contour = current->next;
-
-	free( current );
-	current = next_contour;
-    }
-
-    tobj->contour_count = tobj->vertex_count = 0;
-    tobj->contours = tobj->last_contour = NULL;
-
-    CLEAR_BBOX_2DV( tobj->mins, tobj->maxs );
-
-    ZERO_3V( tobj->plane.normal );
-    tobj->plane.dist = 0.0;
-}
-
-
-/*****************************************************************************
- * tess_msg
- *****************************************************************************/
-INLINE void tess_msg( int level, char *format, ... )
-{
-#ifdef DEBUG
-    va_list ap;
-    va_start( ap, format );
-
-    if ( level <= tess_dbg_level ) {
-	vfprintf( DBG_STREAM, format, ap );
-	fflush( DBG_STREAM );
-    }
-
-    va_end( ap );
-#endif
-}
-
-INLINE void tess_info( char *file, char *line )
-{
-#ifdef DEBUG
-    fprintf( DBG_STREAM, "%9.9s:%d:\t ", file, line );
-#endif
-}
diff --git a/src/glu/mesa/tess.h b/src/glu/mesa/tess.h
index 504ebd0872f..55681830735 100644
--- a/src/glu/mesa/tess.h
+++ b/src/glu/mesa/tess.h
@@ -1,4 +1,4 @@
-/* $Id: tess.h,v 1.15 1999/11/05 20:37:14 gareth Exp $ */
+/* $Id: tess.h,v 1.16 1999/12/06 09:39:34 gareth Exp $ */
 
 /*
  * Mesa 3-D graphics library
@@ -56,33 +56,39 @@ extern "C" {
 struct GLUtesselator
 {
     tess_callbacks_t	callbacks;
-    GLboolean		boundary_only;
     GLenum		winding_rule;
+    GLboolean		boundary_only;
     GLdouble		tolerance;
-    tess_plane_t	plane;
-    GLuint		contour_count;
+    GLenum		orientation;
+    void		*data;
+    GLint		num_contours;
     tess_contour_t	*contours, *last_contour;
     tess_contour_t	*current_contour;
     GLdouble		mins[2], maxs[2];
-    GLuint		vertex_count;
+    GLint		num_vertices;
     tess_vertex_t	**sorted_vertices;
 #if 0
     tess_grid_t		*grid;			/* Not currently used... */
 #endif
     heap_t		*ears;
-    hashtable_t		*cvc_lists;
-    void		*data;
     GLboolean		edge_flag;
     GLuint		label;
+    tess_plane_t	plane;
     GLenum		error;
 };
 
 
 /*****************************************************************************
- * Tessellation error handler:
+ * Common tessellation functions:
  *****************************************************************************/
 extern void tess_error_callback( GLUtesselator *, GLenum );
 
+extern GLdouble twice_contour_area( tess_contour_t *contour );
+extern void reverse_contour( tess_contour_t *contour );
+extern void delete_contour( tess_contour_t **contour );
+
+extern void contour_dump( tess_contour_t *contour );
+
 
 /*****************************************************************************
  * Debugging output:
@@ -115,8 +121,8 @@ extern	int	tess_dbg_level;
 #define MSG		tess_msg
 #endif /* DEBUG */
 
-extern INLINE void tess_msg( int level, char *format, ... );
-extern INLINE void tess_info( char *file, char *line );
+extern INLINE void tess_msg( GLint level, char *format, ... );
+extern INLINE void tess_info( char *file, GLint line );
 
 #ifdef __cplusplus
 }