Initial revision

1 files changed, 456 insertions, 0 deletions

diff --git a/src/glu/mesa/tesselat.c b/src/glu/mesa/tesselat.c
new file mode 100644
index 00000000000..1e424c17ca7
--- /dev/null
+++ b/src/glu/mesa/tesselat.c
@@ -0,0 +1,456 @@
+/* $Id: tesselat.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: tesselat.c,v $
+ * Revision 1.1  1999/08/19 00:55:42  jtg
+ * Initial revision
+ *
+ * Revision 1.5  1997/07/24 01:28:44  brianp
+ * changed precompiled header symbol from PCH to PC_HEADER
+ *
+ * Revision 1.4  1997/05/28 02:29:38  brianp
+ * added support for precompiled headers (PCH), inserted APIENTRY keyword
+ *
+ * Revision 1.3  1997/02/17 17:24:58  brianp
+ * more tesselation changes (Randy Frank)
+ *
+ * Revision 1.2  1997/02/13 18:31:57  brianp
+ * fixed some numerical precision problems (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 <stdlib.h>
+#include <math.h>
+#include "tess.h"
+#endif
+
+
+
+static GLboolean edge_flag;
+
+static void emit_triangle(GLUtriangulatorObj *, tess_vertex *,
+	tess_vertex *,tess_vertex *);
+
+static void emit_triangle_with_edge_flag(GLUtriangulatorObj *,
+	 tess_vertex *,GLboolean,tess_vertex *,GLboolean,
+	 tess_vertex *,GLboolean);
+
+static GLdouble twice_the_triangle_area(
+	tess_vertex *va,
+	tess_vertex *vb,
+	tess_vertex *vc)
+{
+	return	 (vb->x - va->x)*(vc->y - va->y) - (vb->y - va->y)*(vc->x - va->x);
+}
+
+static GLboolean left(
+	GLdouble A,
+	GLdouble B,
+	GLdouble C,
+	GLdouble x,
+	GLdouble y)
+{
+	if(A*x+B*y+C > -EPSILON)
+		return GL_TRUE;
+	else
+		return GL_FALSE;
+}
+
+static GLboolean right(
+	GLdouble A,
+	GLdouble B,
+	GLdouble C,
+	GLdouble x,
+	GLdouble y)
+{
+	if(A*x+B*y+C < EPSILON)
+		return GL_TRUE;
+	else
+		return GL_FALSE;
+}
+
+static GLint convex_ccw(
+	tess_vertex *va,
+	tess_vertex *vb,
+	tess_vertex *vc,
+	GLUtriangulatorObj *tobj)
+{
+	GLdouble	d;
+
+	d = twice_the_triangle_area(va,vb,vc);
+
+	if (d > EPSILON ) {
+		return 1;
+	} else if (d < -EPSILON ) {
+		return 0;
+	} else {
+		return -1;
+	}
+}
+
+static GLint convex_cw(
+	tess_vertex *va,
+	tess_vertex *vb,
+	tess_vertex *vc,
+	GLUtriangulatorObj *tobj)
+{
+	GLdouble	d;
+
+	d = twice_the_triangle_area(va,vb,vc);
+
+	if (d < -EPSILON ) {
+		return 1;
+	} else if (d > EPSILON ) {
+		return 0;
+	} else {
+		return -1;
+	}
+}
+
+static GLboolean diagonal_ccw(
+	tess_vertex *va,
+	tess_vertex *vb,
+	GLUtriangulatorObj *tobj,
+	tess_contour *contour)
+{
+	tess_vertex *vc=va->next , *vertex , *shadow_vertex;
+	struct
+	{
+		GLdouble A,B,C;
+	} ac,cb,ba;
+	GLdouble x,y;
+
+	GLint	 res = convex_ccw(va,vc,vb,tobj);
+	if (res == 0) return GL_FALSE;
+	if (res == -1) return GL_TRUE;
+
+	ba.A=vb->y - va->y;
+	ba.B=va->x - vb->x;
+	ba.C= -ba.A*va->x - ba.B*va->y;
+	ac.A=va->y - vc->y;
+	ac.B=vc->x - va->x;
+	ac.C= -ac.A*vc->x - ac.B*vc->y;
+	cb.A=vc->y - vb->y;
+	cb.B=vb->x - vc->x;
+	cb.C= -cb.A*vb->x - cb.B*vb->y;
+	for(vertex=vb->next;vertex!=va;vertex=vertex->next)
+	{
+		shadow_vertex=vertex->shadow_vertex;
+		if(shadow_vertex!=NULL && 
+			(shadow_vertex==va || shadow_vertex==vb || shadow_vertex==vc))
+			continue;
+		x=vertex->x;
+		y=vertex->y;
+		if(left(ba.A,ba.B,ba.C,x,y) &&
+			left(ac.A,ac.B,ac.C,x,y) &&
+			left(cb.A,cb.B,cb.C,x,y))
+			return GL_FALSE;
+	}
+	return GL_TRUE;
+}
+
+static GLboolean diagonal_cw(
+	tess_vertex *va,
+	tess_vertex *vb,
+	GLUtriangulatorObj *tobj,
+	tess_contour *contour)
+{
+	tess_vertex *vc=va->next , *vertex , *shadow_vertex;
+	struct
+	{
+		GLdouble A,B,C;
+	} ac,cb,ba;
+	GLdouble x,y;
+
+	GLint	 res = convex_cw(va,vc,vb,tobj);
+	if (res == 0) return GL_FALSE;
+	if (res == -1) return GL_TRUE;
+
+	ba.A=vb->y - va->y;
+	ba.B=va->x - vb->x;
+	ba.C= -ba.A*va->x - ba.B*va->y;
+	ac.A=va->y - vc->y;
+	ac.B=vc->x - va->x;
+	ac.C= -ac.A*vc->x - ac.B*vc->y;
+	cb.A=vc->y - vb->y;
+	cb.B=vb->x - vc->x;
+	cb.C= -cb.A*vb->x - cb.B*vb->y;
+	for(vertex=vb->next;vertex!=va;vertex=vertex->next)
+	{
+		shadow_vertex=vertex->shadow_vertex;
+		if(shadow_vertex!=NULL && 
+			(shadow_vertex==va || shadow_vertex==vb || shadow_vertex==vc))
+			continue;
+		x=vertex->x;
+		y=vertex->y;
+		if(right(ba.A,ba.B,ba.C,x,y) &&
+			right(ac.A,ac.B,ac.C,x,y) &&
+			right(cb.A,cb.B,cb.C,x,y))
+			return GL_FALSE;
+	}
+	return GL_TRUE;
+}
+
+static void clip_ear(
+	GLUtriangulatorObj *tobj,
+	tess_vertex *v,
+	tess_contour *contour)
+{
+	emit_triangle(tobj,v->previous,v,v->next);
+	/* the first in the list */
+	if(contour->vertices==v)
+	{
+		contour->vertices=v->next;
+		contour->last_vertex->next=v->next;
+		v->next->previous=contour->last_vertex;
+	}
+	else
+	/* the last ? */
+	if(contour->last_vertex==v)
+	{
+		contour->vertices->previous=v->previous;
+		v->previous->next=v->next;
+		contour->last_vertex=v->previous;
+	}
+	else
+	{
+		v->next->previous=v->previous;
+		v->previous->next=v->next;
+	}
+	free(v);
+	--(contour->vertex_cnt);
+}
+
+static void clip_ear_with_edge_flag(
+	GLUtriangulatorObj *tobj,
+	tess_vertex *v,
+	tess_contour *contour)
+{
+	emit_triangle_with_edge_flag(tobj,v->previous,v->previous->edge_flag,
+		v,v->edge_flag,v->next,GL_FALSE);
+	v->previous->edge_flag=GL_FALSE;
+	/* the first in the list */
+	if(contour->vertices==v)
+	{
+		contour->vertices=v->next;
+		contour->last_vertex->next=v->next;
+		v->next->previous=contour->last_vertex;
+	}
+	else
+	/* the last ? */
+	if(contour->last_vertex==v)
+	{
+		contour->vertices->previous=v->previous;
+		v->previous->next=v->next;
+		contour->last_vertex=v->previous;
+	}
+	else
+	{
+		v->next->previous=v->previous;
+		v->previous->next=v->next;
+	}
+	free(v);
+	--(contour->vertex_cnt);
+}
+
+static void triangulate_ccw(
+	GLUtriangulatorObj *tobj,
+	tess_contour *contour)
+{
+	tess_vertex *vertex;
+	GLuint vertex_cnt=contour->vertex_cnt;
+
+	while(vertex_cnt > 3)
+	{
+		vertex=contour->vertices;
+		while(diagonal_ccw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
+			tobj->error==GLU_NO_ERROR)
+			vertex=vertex->next;
+		if(tobj->error!=GLU_NO_ERROR)
+			return;
+		clip_ear(tobj,vertex->next,contour);
+		--vertex_cnt;
+	}
+}
+
+static void triangulate_cw(
+	GLUtriangulatorObj *tobj,
+	tess_contour *contour)
+{
+	tess_vertex *vertex;
+	GLuint vertex_cnt=contour->vertex_cnt;
+
+	while(vertex_cnt > 3)
+	{
+		vertex=contour->vertices;
+		while(diagonal_cw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
+			tobj->error==GLU_NO_ERROR)
+			vertex=vertex->next;
+		if(tobj->error!=GLU_NO_ERROR)
+			return;
+		clip_ear(tobj,vertex->next,contour);
+		--vertex_cnt;
+	}
+}
+
+static void triangulate_ccw_with_edge_flag(
+	GLUtriangulatorObj *tobj,
+	tess_contour *contour)
+{
+	tess_vertex *vertex;
+	GLuint vertex_cnt=contour->vertex_cnt;
+
+	while(vertex_cnt > 3)
+	{
+		vertex=contour->vertices;
+		while(diagonal_ccw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
+			tobj->error==GLU_NO_ERROR)
+			vertex=vertex->next;
+		if(tobj->error!=GLU_NO_ERROR)
+			return;
+		clip_ear_with_edge_flag(tobj,vertex->next,contour);
+		--vertex_cnt;
+	}
+}
+
+static void triangulate_cw_with_edge_flag(
+	GLUtriangulatorObj *tobj,
+	tess_contour *contour)
+{
+	tess_vertex *vertex;
+	GLuint vertex_cnt=contour->vertex_cnt;
+
+	while(vertex_cnt > 3)
+	{
+		vertex=contour->vertices;
+		while(diagonal_cw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
+			tobj->error==GLU_NO_ERROR)
+			vertex=vertex->next;
+		if(tobj->error!=GLU_NO_ERROR)
+			return;
+		clip_ear_with_edge_flag(tobj,vertex->next,contour);
+		--vertex_cnt;
+	}
+}
+
+void tess_tesselate(GLUtriangulatorObj *tobj)
+{
+	tess_contour *contour;
+
+	for(contour=tobj->contours;contour!=NULL;contour=contour->next)
+	{
+		if(contour->orientation==GLU_CCW) {
+			triangulate_ccw(tobj,contour);
+		} else {
+			triangulate_cw(tobj,contour);
+		}
+		if(tobj->error!=GLU_NO_ERROR)
+			return;
+
+		/* emit the last triangle */
+		emit_triangle(tobj,contour->vertices,contour->vertices->next,
+			contour->vertices->next->next);
+	}
+}
+
+void tess_tesselate_with_edge_flag(GLUtriangulatorObj *tobj)
+{
+	tess_contour *contour;
+
+	edge_flag=GL_TRUE;
+	/* first callback with edgeFlag set to GL_TRUE */
+	(tobj->callbacks.edgeFlag)(GL_TRUE);
+
+	for(contour=tobj->contours;contour!=NULL;contour=contour->next)
+	{
+		if(contour->orientation==GLU_CCW)
+			triangulate_ccw_with_edge_flag(tobj,contour);
+		else
+			triangulate_cw_with_edge_flag(tobj,contour);
+		if(tobj->error!=GLU_NO_ERROR)
+			return;
+		/* emit the last triangle */
+		emit_triangle_with_edge_flag(tobj,contour->vertices,
+			contour->vertices->edge_flag,contour->vertices->next,
+			contour->vertices->next->edge_flag,contour->vertices->next->next,
+			contour->vertices->next->next->edge_flag);
+	}
+}
+
+static void emit_triangle(
+	GLUtriangulatorObj *tobj,
+	tess_vertex *v1,
+	tess_vertex *v2,
+	tess_vertex *v3)
+{
+	(tobj->callbacks.begin)(GL_TRIANGLES);
+	(tobj->callbacks.vertex)(v1->data);
+	(tobj->callbacks.vertex)(v2->data);
+	(tobj->callbacks.vertex)(v3->data);
+	(tobj->callbacks.end)();
+}
+
+static void emit_triangle_with_edge_flag(
+	GLUtriangulatorObj *tobj,
+	tess_vertex *v1,
+	GLboolean edge_flag1,
+	tess_vertex *v2,
+	GLboolean edge_flag2,
+	tess_vertex *v3,
+	GLboolean edge_flag3)
+{
+	(tobj->callbacks.begin)(GL_TRIANGLES);
+	if(edge_flag1!=edge_flag)
+	{
+		edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
+		(tobj->callbacks.edgeFlag)(edge_flag);
+	}
+	(tobj->callbacks.vertex)(v1->data);
+	if(edge_flag2!=edge_flag)
+	{
+		edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
+		(tobj->callbacks.edgeFlag)(edge_flag);
+	}
+	(tobj->callbacks.vertex)(v2->data);
+	if(edge_flag3!=edge_flag)
+	{
+		edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
+		(tobj->callbacks.edgeFlag)(edge_flag);
+	}
+	(tobj->callbacks.vertex)(v3->data);
+	(tobj->callbacks.end)();
+}