Initial revision

1 files changed, 1049 insertions, 0 deletions

diff --git a/src/glu/mesa/polytest.c b/src/glu/mesa/polytest.c
new file mode 100644
index 00000000000..9b42c63477e
--- /dev/null
+++ b/src/glu/mesa/polytest.c
@@ -0,0 +1,1049 @@
+/* $Id: polytest.c,v 1.1 1999/08/19 00:55:42 jtg Exp $ */
+
+/*
+ * Mesa 3-D graphics library
+ * Version:  2.4
+ * Copyright (C) 1995-1997  Brian Paul
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library; if not, write to the Free
+ * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+
+/*
+ * $Log: polytest.c,v $
+ * Revision 1.1  1999/08/19 00:55:42  jtg
+ * Initial revision
+ *
+ * Revision 1.7  1999/06/08 00:44:51  brianp
+ * OpenStep updates ([email protected])
+ *
+ * Revision 1.6  1998/07/26 02:08:52  brianp
+ * updated for Windows compilation per Ted Jump
+ *
+ * Revision 1.5  1997/10/29 02:02:20  brianp
+ * various MS Windows compiler changes (David Bucciarelli, v20 3dfx driver)
+ *
+ * Revision 1.4  1997/07/24 01:28:44  brianp
+ * changed precompiled header symbol from PCH to PC_HEADER
+ *
+ * Revision 1.3  1997/05/28 02:29:38  brianp
+ * added support for precompiled headers (PCH), inserted APIENTRY keyword
+ *
+ * Revision 1.2  1997/05/08 01:53:21  brianp
+ * fixed memory leak in free_current_polygon() reported by Randy Frank
+ *
+ * Revision 1.1  1996/09/27 01:19:39  brianp
+ * Initial revision
+ *
+ */
+
+
+/*
+ * This file is part of the polygon tesselation code contributed by
+ * Bogdan Sikorski
+ */
+
+
+#ifdef PC_HEADER
+#include "all.h"
+#else
+#include <math.h>
+#include <stdlib.h>
+#include "gluP.h"
+#include "tess.h"
+#endif
+
+
+
+static GLenum store_polygon_as_contour(GLUtriangulatorObj *);
+static void free_current_polygon(tess_polygon *);
+static void prepare_projection_info(GLUtriangulatorObj *);
+static GLdouble twice_the_polygon_area(tess_vertex *,tess_vertex *);
+static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *);
+void tess_find_contour_hierarchies(GLUtriangulatorObj *);
+static GLenum test_for_overlapping_contours(GLUtriangulatorObj *);
+static GLenum contours_overlap(tess_contour *, tess_polygon *);
+static GLenum is_contour_contained_in(tess_contour *,tess_contour *);
+static void add_new_exterior(GLUtriangulatorObj *,tess_contour *);
+static void add_new_interior(GLUtriangulatorObj *,tess_contour *,
+	tess_contour *);
+static void add_interior_with_hierarchy_check(GLUtriangulatorObj *,
+	tess_contour *,tess_contour *);
+static void reverse_hierarchy_and_add_exterior(GLUtriangulatorObj *,
+	tess_contour *,tess_contour *);
+static GLboolean point_in_polygon(tess_contour *,GLdouble,GLdouble);
+static void shift_interior_to_exterior(GLUtriangulatorObj *,tess_contour *);
+static void add_exterior_with_check(GLUtriangulatorObj *,tess_contour *,
+	tess_contour *);
+static GLenum cut_out_hole(GLUtriangulatorObj *,tess_contour *,
+	tess_contour *);
+static GLenum merge_hole_with_contour(GLUtriangulatorObj *,
+	tess_contour *,tess_contour *,tess_vertex *,
+	tess_vertex *);
+
+static GLenum
+find_normal(GLUtriangulatorObj *tobj)
+{
+	tess_polygon *polygon=tobj->current_polygon;
+	tess_vertex *va,*vb,*vc;
+	GLdouble A,B,C;
+	GLdouble A0,A1,A2,B0,B1,B2;
+
+	va=polygon->vertices;
+	vb=va->next;
+	A0=vb->location[0]-va->location[0];
+	A1=vb->location[1]-va->location[1];
+	A2=vb->location[2]-va->location[2];
+	for(vc=vb->next;vc!=va;vc=vc->next)
+	{
+		B0=vc->location[0]-va->location[0];
+		B1=vc->location[1]-va->location[1];
+		B2=vc->location[2]-va->location[2];
+		A=A1*B2-A2*B1;
+		B=A2*B0-A0*B2;
+		C=A0*B1-A1*B0;
+		if(fabs(A)>EPSILON || fabs(B)>EPSILON || fabs(C)>EPSILON)
+		{
+			polygon->A=A;
+			polygon->B=B;
+			polygon->C=C;
+			polygon->D= -A*va->location[0]-B*va->location[1]-C*va->location[2];
+			return GLU_NO_ERROR;
+		}
+	}
+	tess_call_user_error(tobj,GLU_TESS_ERROR7);
+	return GLU_ERROR;
+}
+
+void
+tess_test_polygon( GLUtriangulatorObj *tobj )
+{
+	tess_polygon *polygon=tobj->current_polygon;
+
+	/* any vertices defined? */
+	if(polygon->vertex_cnt<3)
+	{
+		free_current_polygon(polygon);
+		return;
+	}
+	/* wrap pointers */
+	polygon->last_vertex->next=polygon->vertices;
+	polygon->vertices->previous=polygon->last_vertex;
+	/* determine the normal */
+	if(find_normal(tobj)==GLU_ERROR)
+		return;
+	/* compare the normals of previously defined contours and this one */
+	/* first contour define ? */
+	if(tobj->contours==NULL)
+	{
+		tobj->A=polygon->A;
+		tobj->B=polygon->B;
+		tobj->C=polygon->C;
+		tobj->D=polygon->D;
+		/* determine the best projection to use */
+		if(fabs(polygon->A) > fabs(polygon->B))
+			if(fabs(polygon->A) > fabs(polygon->C))
+				tobj->projection=OYZ;
+			else
+				tobj->projection=OXY;
+		else
+			if(fabs(polygon->B) > fabs(polygon->C))
+				tobj->projection=OXZ;
+			else
+				tobj->projection=OXY;
+	}
+	else
+	{
+		GLdouble a[3],b[3];
+		tess_vertex *vertex=polygon->vertices;
+
+		a[0]=tobj->A;
+		a[1]=tobj->B;
+		a[2]=tobj->C;
+		b[0]=polygon->A;
+		b[1]=polygon->B;
+		b[2]=polygon->C;
+
+		/* compare the normals */
+		if( fabs(a[1]*b[2]-a[2]*b[1]) > EPSILON ||
+			fabs(a[2]*b[0]-a[0]*b[2]) > EPSILON ||
+			fabs(a[0]*b[1]-a[1]*b[0]) > EPSILON)
+		{
+			/* not coplanar */
+			tess_call_user_error(tobj,GLU_TESS_ERROR9);
+			return;
+		}
+		/* the normals are parallel - test for plane equation */
+		if(fabs(a[0]*vertex->location[0]+a[1]*vertex->location[1]+
+			a[2]*vertex->location[2]+tobj->D) > EPSILON)
+		{
+			/* not the same plane */
+			tess_call_user_error(tobj,GLU_TESS_ERROR9);
+			return;
+		}
+	}
+	prepare_projection_info(tobj);
+	if(verify_edge_vertex_intersections(tobj)==GLU_ERROR)
+		return;
+	if(test_for_overlapping_contours(tobj)==GLU_ERROR)
+		return;
+	if(store_polygon_as_contour(tobj)==GLU_ERROR)
+		return;
+}
+
+static GLenum test_for_overlapping_contours(GLUtriangulatorObj *tobj)
+{
+	tess_contour *contour;
+	tess_polygon *polygon;
+
+	polygon=tobj->current_polygon;
+	for(contour=tobj->contours;contour!=NULL;contour=contour->next)
+		if(contours_overlap(contour,polygon)!=GLU_NO_ERROR)
+		{
+			tess_call_user_error(tobj,GLU_TESS_ERROR5);
+			return GLU_ERROR;
+		}
+	return GLU_NO_ERROR;
+}
+
+static GLenum store_polygon_as_contour(GLUtriangulatorObj *tobj)
+{
+	tess_polygon *polygon=tobj->current_polygon;
+	tess_contour *contour=tobj->contours;
+
+	/* the first contour defined */
+	if(contour==NULL)
+	{
+		if((contour=(tess_contour *)malloc(
+			sizeof(tess_contour)))==NULL)
+		{
+			tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
+			free_current_polygon(polygon);
+			return GLU_ERROR;
+		}
+		tobj->contours=tobj->last_contour=contour;
+		contour->next=contour->previous=NULL;
+	}
+	else
+	{
+		if((contour=(tess_contour *)malloc(
+			sizeof(tess_contour)))==NULL)
+		{
+			tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
+			free_current_polygon(polygon);
+			return GLU_ERROR;
+		}
+		contour->previous=tobj->last_contour;
+		tobj->last_contour->next=contour;
+		tobj->last_contour=contour;
+		contour->next=NULL;
+	}
+	/* mark all vertices in new contour as not special */
+	/* and all are boundary edges */
+	{
+		tess_vertex *vertex;
+		GLuint vertex_cnt,i;
+
+		for(vertex=polygon->vertices , i=0 , vertex_cnt=polygon->vertex_cnt;
+			i<vertex_cnt;
+			vertex=vertex->next , i++)
+		{
+			vertex->shadow_vertex=NULL;
+			vertex->edge_flag=GL_TRUE;
+		}
+	}
+	contour->vertex_cnt=polygon->vertex_cnt;
+	contour->area=polygon->area;
+	contour->orientation=polygon->orientation;
+	contour->type=GLU_UNKNOWN;
+	contour->vertices=polygon->vertices;
+	contour->last_vertex=polygon->last_vertex;
+	polygon->vertices=polygon->last_vertex=NULL;
+	polygon->vertex_cnt=0;
+	++(tobj->contour_cnt);
+	return GLU_NO_ERROR;
+}
+
+static void free_current_polygon(tess_polygon *polygon)
+{
+	tess_vertex *vertex,*vertex_tmp;
+	GLuint	i;
+
+	/* free current_polygon structures */
+	for(vertex=polygon->vertices,i=0;i<polygon->vertex_cnt;i++)
+	{
+		vertex_tmp=vertex->next;
+		free(vertex);
+		vertex=vertex_tmp;
+	}
+	polygon->vertices=polygon->last_vertex=NULL;
+	polygon->vertex_cnt=0;
+}
+
+static void prepare_projection_info(GLUtriangulatorObj *tobj)
+{
+	tess_polygon *polygon=tobj->current_polygon;
+	tess_vertex *vertex,*last_vertex_ptr;
+	GLdouble area;
+
+	last_vertex_ptr=polygon->last_vertex;
+	switch(tobj->projection)
+	{
+		case OXY:
+			for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
+				vertex=vertex->next)
+			{
+				vertex->x=vertex->location[0];
+				vertex->y=vertex->location[1];
+			}
+			last_vertex_ptr->x=last_vertex_ptr->location[0];
+			last_vertex_ptr->y=last_vertex_ptr->location[1];
+			break;
+		case OXZ:
+			for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
+				vertex=vertex->next)
+			{
+				vertex->x=vertex->location[0];
+				vertex->y=vertex->location[2];
+			}
+			last_vertex_ptr->x=last_vertex_ptr->location[0];
+			last_vertex_ptr->y=last_vertex_ptr->location[2];
+			break;
+		case OYZ:
+			for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
+				vertex=vertex->next)
+			{
+				vertex->x=vertex->location[1];
+				vertex->y=vertex->location[2];
+			}
+			last_vertex_ptr->x=last_vertex_ptr->location[1];
+			last_vertex_ptr->y=last_vertex_ptr->location[2];
+			break;
+	}
+	area=twice_the_polygon_area(polygon->vertices,polygon->last_vertex);
+	if(area >= 0.0)
+	{
+		polygon->orientation=GLU_CCW;
+		polygon->area=area;
+	}
+	else
+	{
+		polygon->orientation=GLU_CW;
+		polygon->area= -area;
+	}
+}
+
+static GLdouble twice_the_polygon_area(tess_vertex *vertex,
+	tess_vertex *last_vertex)
+{
+	tess_vertex *next;
+	GLdouble area,x,y;
+
+	area=0.0;
+	x=vertex->x;
+	y=vertex->y;
+	vertex=vertex->next;
+	for(; vertex!=last_vertex; vertex=vertex->next)
+	{
+		next=vertex->next;
+		area+=(vertex->x - x)*(next->y - y) - (vertex->y - y)*(next->x - x);
+	}
+	return area;
+}
+
+/* test if edges ab and cd intersect */
+/* if not return GLU_NO_ERROR, else if cross return GLU_TESS_ERROR8, */
+/* else if adjacent return GLU_TESS_ERROR4 */
+static GLenum edge_edge_intersect(
+	tess_vertex *a,
+	tess_vertex *b,
+	tess_vertex *c,
+	tess_vertex *d)
+{
+	GLdouble denom,r,s;
+	GLdouble xba,ydc,yba,xdc,yac,xac;
+
+	xba=b->x - a->x;
+	yba=b->y - a->y;
+	xdc=d->x - c->x;
+	ydc=d->y - c->y;
+	xac=a->x - c->x;
+	yac=a->y - c->y;
+	denom= xba*ydc - yba*xdc;
+	r = yac*xdc - xac*ydc;
+	/* parallel? */
+	if(fabs(denom) < EPSILON)
+	{
+		if(fabs(r) < EPSILON)
+		{
+			/* colinear */
+			if(fabs(xba) < EPSILON)
+			{
+				/* compare the Y coordinate */
+				if(yba > 0.0)
+				{
+					if((fabs(a->y - c->y)<EPSILON && fabs(c->y - b->y)<EPSILON)
+						||
+						(fabs(a->y - d->y)<EPSILON && fabs(d->y - b->y)<EPSILON))
+					return GLU_TESS_ERROR4;
+
+				}
+				else
+				{
+					if((fabs(b->y - c->y)<EPSILON && fabs(c->y - a->y)<EPSILON)
+						||
+						(fabs(b->y - d->y)<EPSILON && fabs(d->y - a->y)<EPSILON))
+					return GLU_TESS_ERROR4;
+				}
+			}
+			else
+			{
+				/* compare the X coordinate */
+				if(xba > 0.0)
+				{
+					if((fabs(a->x - c->x)<EPSILON && fabs(c->x - b->x)<EPSILON)
+						||
+						(fabs(a->x - d->x)<EPSILON && fabs(d->x - b->x)<EPSILON))
+					return GLU_TESS_ERROR4;
+				}
+				else
+				{
+					if((fabs(b->x - c->x)<EPSILON && fabs(c->x - a->x)<EPSILON)
+						||
+						(fabs(b->x - d->x)<EPSILON && fabs(d->x - a->x)<EPSILON))
+					return GLU_TESS_ERROR4;
+				}
+			}
+		}
+		return GLU_NO_ERROR;
+	}
+	r /= denom;
+	s = (yac*xba - xac*yba) / denom;
+	/* test if one vertex lies on other edge */
+	if(((fabs(r) < EPSILON || (r < 1.0+EPSILON && r > 1.0-EPSILON)) &&
+		s > -EPSILON && s < 1.0+EPSILON) ||
+		((fabs(s) < EPSILON || (s < 1.0+EPSILON && s > 1.0-EPSILON)) &&
+		r > -EPSILON && r < 1.0+EPSILON))
+	{
+		return GLU_TESS_ERROR4;
+	}
+	/* test for crossing */
+	if(r > -EPSILON && r < 1.0+EPSILON &&
+		s > -EPSILON && s < 1.0+EPSILON)
+	{
+		return GLU_TESS_ERROR8;
+	}
+	return GLU_NO_ERROR;
+}
+
+static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *tobj)
+{
+	tess_polygon *polygon=tobj->current_polygon;
+	tess_vertex *vertex1,*last_vertex,*vertex2;
+	GLenum test;
+
+	last_vertex=polygon->last_vertex;
+	vertex1=last_vertex;
+	for(vertex2=vertex1->next->next;
+		vertex2->next!=last_vertex;
+		vertex2=vertex2->next)
+	{
+		test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
+			vertex2->next);
+		if(test!=GLU_NO_ERROR)
+		{
+			tess_call_user_error(tobj,test);
+			return GLU_ERROR;
+		}
+	}
+	for(vertex1=polygon->vertices;
+		vertex1->next->next!=last_vertex;
+		vertex1=vertex1->next)
+	{
+		for(vertex2=vertex1->next->next;
+			vertex2!=last_vertex;
+			vertex2=vertex2->next)
+		{
+			test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
+				vertex2->next);
+			if(test!=GLU_NO_ERROR)
+			{
+				tess_call_user_error(tobj,test);
+				return GLU_ERROR;
+			}
+		}
+	}
+	return GLU_NO_ERROR;
+}
+
+static int
+#if defined(WIN32) && !defined(OPENSTEP)
+__cdecl
+#endif
+area_compare(const void *a,const void *b)
+{
+	GLdouble area1,area2;
+
+	area1=(*((tess_contour **)a))->area;
+	area2=(*((tess_contour **)b))->area;
+	if(area1 < area2)
+		return 1;
+	if(area1 > area2)
+		return -1;
+	return 0;
+}
+
+void tess_find_contour_hierarchies(GLUtriangulatorObj *tobj)
+{
+	tess_contour **contours; /* dinamic array of pointers */
+	tess_contour *tmp_contour_ptr=tobj->contours;
+	GLuint cnt,i;
+	GLenum result;
+	GLboolean hierarchy_changed;
+
+	/* any contours? */
+	if(tobj->contour_cnt < 2)
+	{
+		tobj->contours->type=GLU_EXTERIOR;
+		return;
+	}
+	if((contours=(tess_contour **)
+		malloc(sizeof(tess_contour *)*(tobj->contour_cnt)))==NULL)
+	{
+		tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
+		return;
+	}
+	for(tmp_contour_ptr=tobj->contours , cnt=0;
+		tmp_contour_ptr!=NULL;
+		tmp_contour_ptr=tmp_contour_ptr->next)
+		contours[cnt++]=tmp_contour_ptr;
+	/* now sort the contours in decreasing area size order */
+	qsort((void *)contours,(size_t)cnt,(size_t)sizeof(tess_contour *),area_compare);
+	/* we leave just the first contour - remove others from list */
+	tobj->contours=contours[0];
+	tobj->contours->next=tobj->contours->previous=NULL;
+	tobj->last_contour=tobj->contours;
+	tobj->contour_cnt=1;
+	/* first contour is the one with greatest area */
+	/* must be EXTERIOR */
+	tobj->contours->type=GLU_EXTERIOR;
+	tmp_contour_ptr=tobj->contours;
+	/* now we play! */
+	for(i=1;i<cnt;i++)
+	{
+		hierarchy_changed=GL_FALSE;
+		for(tmp_contour_ptr=tobj->contours;
+			tmp_contour_ptr!=NULL;
+			tmp_contour_ptr=tmp_contour_ptr->next)
+		{
+			if(tmp_contour_ptr->type==GLU_EXTERIOR)
+			{
+				/* check if contour completely contained in EXTERIOR */
+				result=is_contour_contained_in(tmp_contour_ptr,contours[i]);
+				switch(result)
+				{
+					case GLU_INTERIOR:
+						/* now we have to check if contour is inside interiors */
+						/* or not */
+						/* any interiors? */
+						if(tmp_contour_ptr->next!=NULL &&
+							tmp_contour_ptr->next->type==GLU_INTERIOR)
+						{
+							/* for all interior, check if inside any of them */
+							/* if not inside any of interiors, its another */
+							/* interior */
+							/* or it may contain some interiors, then change */
+							/* the contained interiors to exterior ones */
+							add_interior_with_hierarchy_check(tobj,
+								tmp_contour_ptr,contours[i]);
+						}
+						else
+						{
+							/* not in interior, add as new interior contour */
+							add_new_interior(tobj,tmp_contour_ptr,contours[i]);
+						}
+						hierarchy_changed=GL_TRUE;
+						break;
+					case GLU_EXTERIOR:
+						/* ooops, the marked as EXTERIOR (contours[i]) is */
+						/* actually an interior of tmp_contour_ptr */
+						/*  reverse the local hierarchy */
+						reverse_hierarchy_and_add_exterior(tobj,tmp_contour_ptr,
+							contours[i]);
+						hierarchy_changed=GL_TRUE;
+						break;
+					case GLU_NO_ERROR:
+						break;
+					default:
+						abort();
+				}
+			}
+			if(hierarchy_changed)
+				break; /* break from for loop */
+		}
+		if(hierarchy_changed==GL_FALSE)
+		{
+			/* disjoint with all contours, add to contour list */
+			add_new_exterior(tobj,contours[i]);
+		}
+	}
+	free(contours);
+}
+
+/* returns GLU_INTERIOR if inner is completey enclosed within outer */
+/* returns GLU_EXTERIOR if outer is completely enclosed within inner */
+/* returns GLU_NO_ERROR if contours are disjoint */
+static GLenum is_contour_contained_in(
+	tess_contour *outer,
+	tess_contour *inner)
+{
+	GLenum relation_flag;
+
+	/* set relation_flag to relation of containment of first inner vertex */
+	/* regarding outer contour */
+	if(point_in_polygon(outer,inner->vertices->x,inner->vertices->y))
+		relation_flag=GLU_INTERIOR;
+	else
+		relation_flag=GLU_EXTERIOR;
+	if(relation_flag==GLU_INTERIOR)
+		return GLU_INTERIOR;
+	if(point_in_polygon(inner,outer->vertices->x,outer->vertices->y))
+		return GLU_EXTERIOR;
+	return GLU_NO_ERROR;
+}
+
+static GLboolean point_in_polygon(
+	tess_contour *contour,
+	GLdouble x,
+	GLdouble y)
+{
+	tess_vertex *v1,*v2;
+	GLuint i,vertex_cnt;
+	GLdouble xp1,yp1,xp2,yp2;
+	GLboolean tst;
+
+	tst=GL_FALSE;
+	v1=contour->vertices;
+	v2=contour->vertices->previous;
+	for(i=0 , vertex_cnt=contour->vertex_cnt;
+		i < vertex_cnt;
+		i++)
+	{
+		xp1=v1->x;
+		yp1=v1->y;
+		xp2=v2->x;
+		yp2=v2->y;
+		if ((((yp1<=y) && (y<yp2)) || ((yp2<=y)  && (y<yp1))) &&
+			(x < (xp2 - xp1) * (y - yp1) /  (yp2 - yp1) + xp1))
+				tst = (tst==GL_FALSE ? GL_TRUE : GL_FALSE);
+		v2=v1;
+		v1=v1->next;
+	}
+	return tst;
+}
+
+static GLenum contours_overlap(
+	tess_contour *contour,
+	tess_polygon *polygon)
+{
+	tess_vertex *vertex1,*vertex2;
+	GLuint vertex1_cnt,vertex2_cnt,i,j;
+	GLenum test;
+
+	vertex1=contour->vertices;
+	vertex2=polygon->vertices;
+	vertex1_cnt=contour->vertex_cnt;
+	vertex2_cnt=polygon->vertex_cnt;
+	for(i=0; i<vertex1_cnt; vertex1=vertex1->next , i++)
+	{
+		for(j=0; j<vertex2_cnt; vertex2=vertex2->next , j++)
+			if((test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
+				vertex2->next))!=GLU_NO_ERROR)
+				return test;
+	}
+	return GLU_NO_ERROR;
+}
+
+static void add_new_exterior(
+	GLUtriangulatorObj *tobj,
+	tess_contour *contour)
+{
+	contour->type=GLU_EXTERIOR;
+	contour->next=NULL;
+	contour->previous=tobj->last_contour;
+	tobj->last_contour->next=contour;
+	tobj->last_contour=contour;
+}
+
+static void add_new_interior(
+	GLUtriangulatorObj *tobj,
+	tess_contour *outer,
+	tess_contour *contour)
+{
+	contour->type=GLU_INTERIOR;
+	contour->next=outer->next;
+	contour->previous=outer;
+	if(outer->next!=NULL)
+		outer->next->previous=contour;
+	outer->next=contour;
+	if(tobj->last_contour==outer)
+		tobj->last_contour=contour;
+}
+
+static void add_interior_with_hierarchy_check(
+	GLUtriangulatorObj *tobj,
+	tess_contour *outer,
+	tess_contour *contour)
+{
+	tess_contour *ptr;
+
+	/* for all interiors of outer check if they are interior of contour */
+	/* if so, change that interior to exterior and move it of of the */
+	/* interior sequence */
+	if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
+	{
+		GLenum test;
+
+		for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
+		{
+			test=is_contour_contained_in(ptr,contour);
+			switch(test)
+			{
+				case GLU_INTERIOR:
+					/* contour is contained in one of the interiors */
+					/* check if possibly contained in other exteriors */
+					/* move ptr to first EXTERIOR */
+					for(;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next);
+					if(ptr==NULL)
+						/* another exterior */
+						add_new_exterior(tobj,contour);
+					else
+						add_exterior_with_check(tobj,ptr,contour);
+					return;
+				case GLU_EXTERIOR:
+					/* one of the interiors is contained in the contour */
+					/* change it to EXTERIOR, and shift it away from the */
+					/* interior sequence */
+					shift_interior_to_exterior(tobj,ptr);
+					break;
+				case GLU_NO_ERROR:
+					/* disjoint */
+					break;
+				default:
+					abort();
+			}
+		}
+	}
+	/* add contour to the interior sequence */
+	add_new_interior(tobj,outer,contour);
+}
+
+static void reverse_hierarchy_and_add_exterior(
+	GLUtriangulatorObj *tobj,
+	tess_contour *outer,
+	tess_contour *contour)
+{
+	tess_contour *ptr;
+
+	/* reverse INTERIORS to EXTERIORS */
+	/* any INTERIORS? */
+	if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
+		for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
+			ptr->type=GLU_EXTERIOR;
+	/* the outer now becomes inner */
+	outer->type=GLU_INTERIOR;
+	/* contour is the EXTERIOR */
+	contour->next=outer;
+	if(tobj->contours==outer)
+	{
+		/* first contour beeing reversed */
+		contour->previous=NULL;
+		tobj->contours=contour;
+	}
+	else
+	{
+		outer->previous->next=contour;
+		contour->previous=outer->previous;
+	}
+	outer->previous=contour;
+}
+
+static void shift_interior_to_exterior(
+	GLUtriangulatorObj *tobj,
+	tess_contour *contour)
+{
+	contour->previous->next=contour->next;
+	if(contour->next!=NULL)
+		contour->next->previous=contour->previous;
+	else
+		tobj->last_contour=contour->previous;
+}
+
+static void add_exterior_with_check(
+	GLUtriangulatorObj *tobj,
+	tess_contour *outer,
+	tess_contour *contour)
+{
+	GLenum test;
+
+	/* this contour might be interior to further exteriors - check */
+	/* if not, just add as a new exterior */
+	for(;outer!=NULL && outer->type==GLU_EXTERIOR;outer=outer->next)
+	{
+		test=is_contour_contained_in(outer,contour);
+		switch(test)
+		{
+			case GLU_INTERIOR:
+				/* now we have to check if contour is inside interiors */
+				/* or not */
+				/* any interiors? */
+				if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
+				{
+					/* for all interior, check if inside any of them */
+					/* if not inside any of interiors, its another */
+					/* interior */
+					/* or it may contain some interiors, then change */
+					/* the contained interiors to exterior ones */
+					add_interior_with_hierarchy_check(tobj,
+						outer,contour);
+				}
+				else
+				{
+					/* not in interior, add as new interior contour */
+					add_new_interior(tobj,outer,contour);
+				}
+				return;
+			case GLU_NO_ERROR:
+				/* disjoint */
+				break;
+			default:
+				abort();
+		}
+	}
+	/* add contour to the exterior sequence */
+	add_new_exterior(tobj,contour);
+}
+
+void tess_handle_holes(GLUtriangulatorObj *tobj)
+{
+	tess_contour *contour,*hole;
+	GLenum exterior_orientation;
+
+	/* verify hole orientation */
+	for(contour=tobj->contours;contour!=NULL;)
+	{
+		exterior_orientation=contour->orientation;
+		for(contour=contour->next;
+			contour!=NULL && contour->type==GLU_INTERIOR;
+			contour=contour->next)
+		{
+			if(contour->orientation==exterior_orientation)
+			{
+				tess_call_user_error(tobj,GLU_TESS_ERROR5);
+				return;
+			}
+		}
+	}
+	/* now cut-out holes */
+	for(contour=tobj->contours;contour!=NULL;)
+	{
+		hole=contour->next;
+		while(hole!=NULL && hole->type==GLU_INTERIOR)
+		{
+			if(cut_out_hole(tobj,contour,hole)==GLU_ERROR)
+				return;
+			hole=contour->next;
+		}
+		contour=contour->next;
+	}
+}
+
+static GLenum cut_out_hole(
+	GLUtriangulatorObj *tobj,
+	tess_contour *contour,
+	tess_contour *hole)
+{
+	tess_contour *tmp_hole;
+	tess_vertex *v1,*v2,*tmp_vertex;
+	GLuint vertex1_cnt,vertex2_cnt,tmp_vertex_cnt;
+	GLuint i,j,k;
+	GLenum test;
+
+	/* find an edge connecting contour and hole not intersecting any other */
+	/* edge belonging to either the contour or any of the other holes */
+	for(v1=contour->vertices , vertex1_cnt=contour->vertex_cnt , i=0;
+		i<vertex1_cnt;
+		i++ , v1=v1->next)
+	{
+		for(v2=hole->vertices , vertex2_cnt=hole->vertex_cnt , j=0;
+			j<vertex2_cnt;
+			j++ , v2=v2->next)
+		{
+			/* does edge (v1,v2) intersect any edge of contour */
+			for(tmp_vertex=contour->vertices , tmp_vertex_cnt=contour->vertex_cnt ,
+					k=0;
+				k<tmp_vertex_cnt;
+				tmp_vertex=tmp_vertex->next , k++)
+			{
+				/* skip edge tests for edges directly connected */
+				if(v1==tmp_vertex || v1==tmp_vertex->next)
+					continue;
+				test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
+				if(test!=GLU_NO_ERROR)
+					break;
+			}
+			if(test==GLU_NO_ERROR)
+			{
+				/* does edge (v1,v2) intersect any edge of hole */
+				for(tmp_vertex=hole->vertices ,
+						tmp_vertex_cnt=hole->vertex_cnt , k=0;
+					k<tmp_vertex_cnt;
+					tmp_vertex=tmp_vertex->next , k++)
+				{
+					/* skip edge tests for edges directly connected */
+					if(v2==tmp_vertex || v2==tmp_vertex->next)
+						continue;
+					test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
+					if(test!=GLU_NO_ERROR)
+						break;
+				}
+				if(test==GLU_NO_ERROR)
+				{
+					/* does edge (v1,v2) intersect any other hole? */
+					for(tmp_hole=hole->next;
+						tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
+						tmp_hole=tmp_hole->next)
+					{
+						/* does edge (v1,v2) intersect any edge of hole */
+						for(tmp_vertex=tmp_hole->vertices ,
+								tmp_vertex_cnt=tmp_hole->vertex_cnt , k=0;
+							k<tmp_vertex_cnt;
+							tmp_vertex=tmp_vertex->next , k++)
+						{
+							test=edge_edge_intersect(v1,v2,tmp_vertex,
+								tmp_vertex->next);
+							if(test!=GLU_NO_ERROR)
+								break;
+						}
+						if(test!=GLU_NO_ERROR)
+							break;
+					}
+				}
+			}
+			if(test==GLU_NO_ERROR)
+			{
+				/* edge (v1,v2) is good for eliminating the hole */
+				if(merge_hole_with_contour(tobj,contour,hole,v1,v2)
+					==GLU_NO_ERROR)
+					return GLU_NO_ERROR;
+				else
+					return GLU_ERROR;
+			}
+		}
+	}
+	/* other holes are blocking all possible connections of hole */
+	/* with contour, we shift this hole as the last hole and retry */
+	for(tmp_hole=hole;
+		tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
+		tmp_hole=tmp_hole->next);
+	contour->next=hole->next;
+	hole->next->previous=contour;
+	if(tmp_hole==NULL)
+	{
+		/* last EXTERIOR contour, shift hole as last contour */
+		hole->next=NULL;
+		hole->previous=tobj->last_contour;
+		tobj->last_contour->next=hole;
+		tobj->last_contour=hole;
+	}
+	else
+	{
+		tmp_hole->previous->next=hole;
+		hole->previous=tmp_hole->previous;
+		tmp_hole->previous=hole;
+		hole->next=tmp_hole;
+	}
+	hole=contour->next;
+	/* try once again - recurse */
+	return cut_out_hole(tobj,contour,hole);
+}
+
+static GLenum merge_hole_with_contour(
+	GLUtriangulatorObj *tobj,
+	tess_contour *contour,
+	tess_contour *hole,
+	tess_vertex *v1,
+	tess_vertex *v2)
+{
+	tess_vertex *v1_new,*v2_new;
+
+	/* make copies of v1 and v2, place them respectively after their originals */
+	if((v1_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
+	{
+		tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
+		return GLU_ERROR;
+	}
+	if((v2_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
+	{
+		tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
+		return GLU_ERROR;
+	}
+	v1_new->edge_flag=GL_TRUE;
+	v1_new->data=v1->data;
+	v1_new->location[0]=v1->location[0];
+	v1_new->location[1]=v1->location[1];
+	v1_new->location[2]=v1->location[2];
+	v1_new->x=v1->x;
+	v1_new->y=v1->y;
+	v1_new->shadow_vertex=v1;
+	v1->shadow_vertex=v1_new;
+	v1_new->next=v1->next;
+	v1_new->previous=v1;
+	v1->next->previous=v1_new;
+	v1->next=v1_new;
+	v2_new->edge_flag=GL_TRUE;
+	v2_new->data=v2->data;
+	v2_new->location[0]=v2->location[0];
+	v2_new->location[1]=v2->location[1];
+	v2_new->location[2]=v2->location[2];
+	v2_new->x=v2->x;
+	v2_new->y=v2->y;
+	v2_new->shadow_vertex=v2;
+	v2->shadow_vertex=v2_new;
+	v2_new->next=v2->next;
+	v2_new->previous=v2;
+	v2->next->previous=v2_new;
+	v2->next=v2_new;
+	/* link together the two lists */
+	v1->next=v2_new;
+	v2_new->previous=v1;
+	v2->next=v1_new;
+	v1_new->previous=v2;
+	/* update the vertex count of the contour */
+	contour->vertex_cnt += hole->vertex_cnt+2;
+	/* remove the INTERIOR contour */
+	contour->next=hole->next;
+	if(hole->next!=NULL)
+		hole->next->previous=contour;
+	free(hole);
+	/* update tobj structure */
+	--(tobj->contour_cnt);
+	if(contour->last_vertex==v1)
+		contour->last_vertex=v1_new;
+	/* mark two vertices with edge_flag */
+	v2->edge_flag=GL_FALSE;
+	v1->edge_flag=GL_FALSE;
+	return GLU_NO_ERROR;
+}