diff options
Diffstat (limited to 'src/glu/mesa')
| -rw-r--r-- | src/glu/mesa/Makefile.BeOS | 2 | ||||
| -rw-r--r-- | src/glu/mesa/Makefile.BeOS-R4 | 11 | ||||
| -rw-r--r-- | src/glu/mesa/Makefile.X11 | 4 | ||||
| -rw-r--r-- | src/glu/mesa/MesaGLU.def | 13 | ||||
| -rw-r--r-- | src/glu/mesa/descrip.mms | 5 | ||||
| -rw-r--r-- | src/glu/mesa/glu.c | 14 | ||||
| -rw-r--r-- | src/glu/mesa/mms_depend | 5 | ||||
| -rw-r--r-- | src/glu/mesa/polytest.c | 1049 | ||||
| -rw-r--r-- | src/glu/mesa/tess.c | 1174 | ||||
| -rw-r--r-- | src/glu/mesa/tess.h | 185 | ||||
| -rw-r--r-- | src/glu/mesa/tesselat.c | 456 |
11 files changed, 1008 insertions, 1910 deletions
diff --git a/src/glu/mesa/Makefile.BeOS b/src/glu/mesa/Makefile.BeOS index d1e489c1999..016bb580ae3 100644 --- a/src/glu/mesa/Makefile.BeOS +++ b/src/glu/mesa/Makefile.BeOS @@ -29,7 +29,7 @@ INCDIR = ../include LIBDIR = ../lib SOURCES = glu.c mipmap.c nurbs.c nurbscrv.c nurbssrf.c nurbsutl.c \ - project.c quadric.c tess.c tesselat.c polytest.c + project.c quadric.c tess.c tess_fist.c tess_hash.c tess_heap.c OBJECTS = $(SOURCES:.c=.o) diff --git a/src/glu/mesa/Makefile.BeOS-R4 b/src/glu/mesa/Makefile.BeOS-R4 index d664534491d..4584c3201b8 100644 --- a/src/glu/mesa/Makefile.BeOS-R4 +++ b/src/glu/mesa/Makefile.BeOS-R4 @@ -19,11 +19,14 @@ # Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. -# $Id: Makefile.BeOS-R4,v 1.1 1999/08/19 00:55:42 jtg Exp $ +# $Id: Makefile.BeOS-R4,v 1.2 1999/09/10 02:03:31 gareth Exp $ # $Log: Makefile.BeOS-R4,v $ -# Revision 1.1 1999/08/19 00:55:42 jtg -# Initial revision +# Revision 1.2 1999/09/10 02:03:31 gareth +# Added GLU 1.3 tessellation (except winding rule code). +# +# Revision 1.1.1.1 1999/08/19 00:55:42 jtg +# Imported sources # # Revision 1.2 1999/02/02 04:44:40 brianp # fixed some problems @@ -42,7 +45,7 @@ INCDIR = ../include LIBDIR = ../lib SOURCES = glu.c mipmap.c nurbs.c nurbscrv.c nurbssrf.c nurbsutl.c \ - project.c quadric.c tess.c tesselat.c polytest.c + project.c quadric.c tess.c tess_fist.c tess_hash.c tess_heap.c OBJECTS = $(SOURCES:.c=.o) diff --git a/src/glu/mesa/Makefile.X11 b/src/glu/mesa/Makefile.X11 index c155aea9a55..2b123810a57 100644 --- a/src/glu/mesa/Makefile.X11 +++ b/src/glu/mesa/Makefile.X11 @@ -1,4 +1,4 @@ -# $Id: Makefile.X11,v 1.1 1999/08/19 00:55:42 jtg Exp $ +# $Id: Makefile.X11,v 1.2 1999/09/10 02:03:31 gareth Exp $ # Mesa 3-D graphics library # Version: 3.1 @@ -15,7 +15,7 @@ INCDIR = ../include LIBDIR = ../lib SOURCES = glu.c mipmap.c nurbs.c nurbscrv.c nurbssrf.c nurbsutl.c \ - project.c quadric.c tess.c tesselat.c polytest.c + project.c quadric.c tess.c tess_fist.c tess_hash.c tess_heap.c OBJECTS = $(SOURCES:.c=.o) diff --git a/src/glu/mesa/MesaGLU.def b/src/glu/mesa/MesaGLU.def index 8b1c4449ff1..e61782b65a0 100644 --- a/src/glu/mesa/MesaGLU.def +++ b/src/glu/mesa/MesaGLU.def @@ -45,10 +45,17 @@ EXPORTS gluPwlCurve
gluNurbsCallback
gluNewTess
- gluTessCallback
gluDeleteTess
+ gluTessBeginPolygon
+ gluTessBeginContour
+ gluTessVertex
+ gluTessEndContour
+ gluTessEndPolygon
+ gluTessProperty
+ gluTessNormal
+ gluTessCallback
+ gluGetTessProperty
gluBeginPolygon
- gluEndPolygon
gluNextContour
- gluTessVertex
+ gluEndPolygon
gluGetString
diff --git a/src/glu/mesa/descrip.mms b/src/glu/mesa/descrip.mms index b660f6914de..bcce68ff94e 100644 --- a/src/glu/mesa/descrip.mms +++ b/src/glu/mesa/descrip.mms @@ -15,10 +15,11 @@ LIBDIR = [-.lib] CFLAGS = /include=$(INCDIR)/define=(FBIND=1) SOURCES = glu.c mipmap.c nurbs.c nurbscrv.c nurbssrf.c nurbsutl.c \ - project.c quadric.c tess.c tesselat.c polytest.c + project.c quadric.c tess.c tess_fist.c tess_hash.c tess_heap.c OBJECTS =glu.obj,mipmap.obj,nurbs.obj,nurbscrv.obj,nurbssrf.obj,nurbsutl.obj,\ - project.obj,quadric.obj,tess.obj,tesselat.obj,polytest.obj + project.obj,quadric.obj,tess.obj,tess_fist.obj,tess_hash.obj,\ + tess_heap.obj diff --git a/src/glu/mesa/glu.c b/src/glu/mesa/glu.c index 2cceb8b743e..5569ca9d49c 100644 --- a/src/glu/mesa/glu.c +++ b/src/glu/mesa/glu.c @@ -1,4 +1,4 @@ -/* $Id: glu.c,v 1.1 1999/08/19 00:55:42 jtg Exp $ */ +/* $Id: glu.c,v 1.2 1999/09/10 02:03:31 gareth Exp $ */ /* * Mesa 3-D graphics library @@ -23,8 +23,11 @@ /* * $Log: glu.c,v $ - * Revision 1.1 1999/08/19 00:55:42 jtg - * Initial revision + * Revision 1.2 1999/09/10 02:03:31 gareth + * Added GLU 1.3 tessellation (except winding rule code). + * + * Revision 1.1.1.1 1999/08/19 00:55:42 jtg + * Imported sources * * Revision 1.13 1999/03/31 19:07:28 brianp * added GL_EXT_abgr to extensions @@ -220,8 +223,7 @@ const GLubyte* GLAPIENTRY gluErrorString( GLenum errorCode ) "misoriented or self-intersecting loops", "coincident vertices", "colinear vertices", - "intersecting edges", - "not coplanar contours" + "intersecting edges" }; static char *nurbs_error[] = { "spline order un-supported", @@ -301,7 +303,7 @@ const GLubyte* GLAPIENTRY gluErrorString( GLenum errorCode ) else if (errorCode==GLU_INCOMPATIBLE_GL_VERSION) { return (GLubyte *) "incompatible GL version"; } - else if (errorCode>=GLU_TESS_ERROR1 && errorCode<=GLU_TESS_ERROR9) { + else if (errorCode>=GLU_TESS_ERROR1 && errorCode<=GLU_TESS_ERROR8) { return (GLubyte *) tess_error[errorCode-GLU_TESS_ERROR1]; } else if (errorCode>=GLU_NURBS_ERROR1 && errorCode<=GLU_NURBS_ERROR37) { diff --git a/src/glu/mesa/mms_depend b/src/glu/mesa/mms_depend index 372e3fff1e9..37e9eb2b920 100644 --- a/src/glu/mesa/mms_depend +++ b/src/glu/mesa/mms_depend @@ -9,5 +9,6 @@ nurbsutl.obj : gluP.h [-.include.gl]gl.h [-.include.gl]glu.h nurbs.h project.obj : gluP.h [-.include.gl]gl.h [-.include.gl]glu.h quadric.obj : gluP.h [-.include.gl]gl.h [-.include.gl]glu.h tess.obj : gluP.h [-.include.gl]gl.h [-.include.gl]glu.h tess.h -tesselat.obj : gluP.h [-.include.gl]gl.h [-.include.gl]glu.h tess.h -polytest.obj : gluP.h [-.include.gl]gl.h [-.include.gl]glu.h tess.h +tess_fist.obj : gluP.h [-.include.gl]gl.h [-.include.gl]glu.h tess.h +tess_hash.obj : gluP.h [-.include.gl]gl.h [-.include.gl]glu.h tess.h +tess_heap.obj : gluP.h [-.include.gl]gl.h [-.include.gl]glu.h tess.h diff --git a/src/glu/mesa/polytest.c b/src/glu/mesa/polytest.c deleted file mode 100644 index 9b42c63477e..00000000000 --- a/src/glu/mesa/polytest.c +++ /dev/null @@ -1,1049 +0,0 @@ -/* $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; -} diff --git a/src/glu/mesa/tess.c b/src/glu/mesa/tess.c index c773fbaae4b..c2e0e1cd988 100644 --- a/src/glu/mesa/tess.c +++ b/src/glu/mesa/tess.c @@ -1,369 +1,971 @@ -/* $Id: tess.c,v 1.1 1999/08/19 00:55:42 jtg Exp $ */ +/* $Id: tess.c,v 1.2 1999/09/10 02:03:31 gareth Exp $ */ /* * Mesa 3-D graphics library * Version: 3.1 - * Copyright (C) 1995-1999 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. + * + * Copyright (C) 1999 Brian Paul 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 and this permission notice 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 + * BRIAN PAUL 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. */ - -/* - * $Log: tess.c,v $ - * Revision 1.1 1999/08/19 00:55:42 jtg - * Initial revision - * - * Revision 1.11 1999/02/27 13:55:31 brianp - * fixed BeOS-related GLU typedef problems - * - * Revision 1.10 1999/01/03 03:23:15 brianp - * now using GLAPIENTRY and GLCALLBACK keywords (Ted Jump) +/***************************************************************************** * - * Revision 1.9 1998/06/01 01:10:29 brianp - * small update for Next/OpenStep from Alexander Mai + * GLU 1.3 Polygon Tessellation by Gareth Hughes <[email protected]> * - * Revision 1.8 1998/02/04 00:27:58 brianp - * cygnus changes from Stephane Rehel - * - * Revision 1.7 1998/01/16 03:35:26 brianp - * fixed Windows compilation warnings (Theodore Jump) - * - * Revision 1.6 1997/09/17 01:51:48 brianp - * changed glu*Callback() functions to match prototype in glu.h - * - * 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 1996/11/12 01:23:02 brianp - * added test to prevent free(vertex) when vertex==NULL in delete_contours() - * - * Revision 1.2 1996/10/22 22:57:19 brianp - * better error handling in gluBegin/EndPolygon() from Erich Eder + *****************************************************************************/ + +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> +#include <GL/glu.h> + +#include "tess.h" +#include "tess_macros.h" +#include "tess_fist.h" +#if 0 +#include "tess_grid.h" +#endif + +/***************************************************************************** + * Internal function prototypes: + *****************************************************************************/ + +static void init_callbacks( tess_callbacks_t *callbacks ); + +static void tess_cleanup( GLUtesselator *tobj ); +static void inspect_current_contour( GLUtesselator *tobj ); + +static void delete_current_contour( GLUtesselator *tobj ); +static void delete_all_contours( GLUtesselator *tobj ); + +#define TESS_CHECK_ERRORS(t) if ( (t)->error != GLU_NO_ERROR ) goto cleanup + +int tess_debug_level = 0; +GLdouble origin[3] = { 0.0, 0.0, 0.0 }; + + +/***************************************************************************** * - * Revision 1.1 1996/09/27 01:19:39 brianp - * Initial revision + * GLU TESSELLATION FUNCTIONS * - */ + *****************************************************************************/ -/* - * This file is part of the polygon tesselation code contributed by - * Bogdan Sikorski - */ +/***************************************************************************** + * gluNewTess + *****************************************************************************/ +GLUtesselator* GLAPIENTRY gluNewTess( void ) +{ + GLUtesselator *tobj; + if ( ( tobj = (GLUtesselator *) + malloc( sizeof(GLUtesselator) ) ) == NULL ) + { + return NULL; + } -#ifdef PC_HEADER -#include "all.h" -#else -#include <math.h> -#include <stdlib.h> -#include "tess.h" -#endif + init_callbacks( &tobj->callbacks ); + tobj->boundary_only = GL_FALSE; + tobj->winding_rule = GLU_TESS_WINDING_ODD; + tobj->tolerance = 0.0; -/* - * This is ugly, but seems the easiest way to do things to make the - * code work under YellowBox for Windows - */ -#if defined(OPENSTEP) && defined(GLCALLBACK) -#undef GLCALLBACK -#define GLCALLBACK -#endif + tobj->plane.normal[X] = 0.0; + tobj->plane.normal[Y] = 0.0; + tobj->plane.normal[Z] = 0.0; + tobj->plane.dist = 0.0; + tobj->contour_count = 0; + tobj->contours = tobj->last_contour = NULL; + tobj->current_contour = NULL; -extern void tess_test_polygon(GLUtriangulatorObj *); -extern void tess_find_contour_hierarchies(GLUtriangulatorObj *); -extern void tess_handle_holes(GLUtriangulatorObj *); -extern void tess_tesselate(GLUtriangulatorObj *); -extern void tess_tesselate_with_edge_flag(GLUtriangulatorObj *); -static void delete_contours(GLUtriangulatorObj *); + CLEAR_BBOX_2DV( tobj->mins, tobj->maxs ); -#ifdef __CYGWIN32__ -#define _CALLBACK -#else -#define _CALLBACK GLCALLBACK + tobj->vertex_count = 0; + tobj->sorted_vertices = NULL; +#if 0 + tobj->grid = NULL; #endif -void init_callbacks(tess_callbacks *callbacks) + tobj->error = GLU_NO_ERROR; + + return tobj; +} + + +/***************************************************************************** + * gluDeleteTess + *****************************************************************************/ +void GLAPIENTRY gluDeleteTess( GLUtesselator *tobj ) { - callbacks->begin = ( void (_CALLBACK*)(GLenum) ) 0; - callbacks->edgeFlag = ( void (_CALLBACK*)(GLboolean) ) 0; - callbacks->vertex = ( void (_CALLBACK*)(void*) ) 0; - callbacks->end = ( void (_CALLBACK*)(void) ) 0; - callbacks->error = ( void (_CALLBACK*)(GLenum) ) 0; + DEBUGP(2, ("-> gluDeleteTess(tobj: %p)\n", tobj)); + + if ( tobj->error == GLU_NO_ERROR && ( tobj->contour_count > 0 ) ) + { + /* Was gluEndContour called? */ + tess_error_callback( tobj, GLU_TESS_ERROR4, NULL ); + } + + /* Delete all internal structures */ + tess_cleanup( tobj ); + free( tobj ); + + DEBUGP(2, ("<- gluDeleteTess()\n\n")); } -void tess_call_user_error(GLUtriangulatorObj *tobj, GLenum gluerr) + +/***************************************************************************** + * gluTessBeginPolygon + *****************************************************************************/ +void GLAPIENTRY gluTessBeginPolygon( GLUtesselator *tobj, void *polygon_data ) { - if(tobj->error==GLU_NO_ERROR) - tobj->error=gluerr; - if(tobj->callbacks.error!=NULL) - (tobj->callbacks.error)(gluerr); + DEBUGP(2, ("-> gluTessBeginPolygon(tobj: %p, data: %p)\n", + tobj, polygon_data)); + + tobj->error = GLU_NO_ERROR; + + if ( tobj->current_contour != NULL ) + { + /* gluEndPolygon was not called */ + tess_error_callback( tobj, GLU_TESS_ERROR1, NULL ); + + tess_cleanup( tobj ); + } + + DEBUGP(2, ("<- gluTessBeginPolygon(tobj: %p)\n\n", tobj)); } -GLUtriangulatorObj* GLAPIENTRY gluNewTess( void ) + +/***************************************************************************** + * gluTessBeginContour + *****************************************************************************/ +void GLAPIENTRY gluTessBeginContour( GLUtesselator *tobj ) { - GLUtriangulatorObj *tobj; - tobj = (GLUtriangulatorObj *) malloc(sizeof(struct GLUtesselator)); - if (!tobj) - return NULL; - tobj->contours=tobj->last_contour=NULL; - init_callbacks(&tobj->callbacks); - tobj->error=GLU_NO_ERROR; - tobj->current_polygon=NULL; - tobj->contour_cnt=0; - return tobj; + DEBUGP(2, (" -> gluTessBeginContour(tobj: %p)\n", tobj)); + TESS_CHECK_ERRORS( tobj ); + + if ( tobj->current_contour != NULL ) + { + tess_error_callback( tobj, GLU_TESS_ERROR2, NULL ); + return; + } + + if ( ( tobj->current_contour = + (tess_contour_t *) malloc( sizeof(tess_contour_t) ) ) == NULL ) + { + tess_error_callback( tobj, GLU_OUT_OF_MEMORY, NULL ); + return; + } + + COPY_3V( tobj->plane.normal, tobj->current_contour->plane.normal ); + tobj->current_contour->plane.dist = tobj->plane.dist; + + tobj->current_contour->vertex_count = 0; + tobj->current_contour->vertices = + tobj->current_contour->last_vertex = NULL; + + tobj->current_contour->reflex_count = 0; + tobj->current_contour->reflex_vertices = + tobj->current_contour->last_reflex = NULL; + + tobj->current_contour->orientation = GLU_UNKNOWN; + tobj->current_contour->area = 0.0; + + tobj->current_contour->winding = 0; + CLEAR_BBOX_2DV( tobj->current_contour->mins, + tobj->current_contour->maxs ); + + cleanup: + DEBUGP(2, (" <- gluTessBeginContour(tobj: %p)\n\n", tobj)); + return; } -void GLAPIENTRY gluTessCallback( GLUtriangulatorObj *tobj, GLenum which, - void (GLCALLBACK *fn)() ) +/***************************************************************************** + * gluTessVertex + *****************************************************************************/ +void GLAPIENTRY gluTessVertex( GLUtesselator *tobj, GLdouble coords[3], + void *vertex_data ) { - switch(which) + tess_contour_t *current = tobj->current_contour; + tess_vertex_t *last_vertex; + + DEBUGP(2, (" -> gluTessVertex(tobj: %p, (%.2f, %.2f, %.2f))\n", + tobj, coords[X], coords[Y], coords[Z])); + TESS_CHECK_ERRORS( tobj ); + + if ( current == NULL ) { + tess_error_callback( tobj, GLU_TESS_ERROR2, NULL ); + return; + } + + tobj->vertex_count++; + + last_vertex = current->last_vertex; + + if ( last_vertex == NULL ) + { + if ( ( last_vertex = (tess_vertex_t *) + malloc( sizeof(tess_vertex_t) ) ) == NULL ) { - case GLU_BEGIN: - tobj->callbacks.begin = (void (_CALLBACK*)(GLenum)) fn; - break; - case GLU_EDGE_FLAG: - tobj->callbacks.edgeFlag = (void (_CALLBACK*)(GLboolean)) fn; - break; - case GLU_VERTEX: - tobj->callbacks.vertex = (void (_CALLBACK*)(void *)) fn; - break; - case GLU_END: - tobj->callbacks.end = (void (_CALLBACK*)(void)) fn; - break; - case GLU_ERROR: - tobj->callbacks.error = (void (_CALLBACK*)(GLenum)) fn; - break; - default: - tobj->error=GLU_INVALID_ENUM; - break; + tess_error_callback( tobj, GLU_OUT_OF_MEMORY, NULL ); + return; } -} + current->vertices = last_vertex; + current->last_vertex = last_vertex; + + last_vertex->index = -1; + last_vertex->data = vertex_data; + + last_vertex->coords[X] = coords[X]; + last_vertex->coords[Y] = coords[Y]; + last_vertex->coords[Z] = coords[Z]; + + last_vertex->next = NULL; + last_vertex->previous = NULL; + + current->vertex_count++; + } + else + { + tess_vertex_t *vertex; + + if ( ( vertex = (tess_vertex_t *) + malloc( sizeof(tess_vertex_t) ) ) == NULL ) + { + tess_error_callback( tobj, GLU_OUT_OF_MEMORY, NULL ); + return; + } + + vertex->index = -1; + vertex->data = vertex_data; + + vertex->coords[X] = coords[X]; + vertex->coords[Y] = coords[Y]; + vertex->coords[Z] = coords[Z]; + + vertex->next = NULL; + vertex->previous = last_vertex; + current->vertex_count++; + + last_vertex->next = vertex; + current->last_vertex = vertex; + } + + DEBUGP(3, ("\t vertex: (%.2f, %.2f, %.2f)\n", + current->last_vertex->coords[X], + current->last_vertex->coords[Y], + current->last_vertex->coords[Z])); + cleanup: + DEBUGP(2, (" <- gluTessVertex(tobj: %p)\n", tobj)); + return; +} -void GLAPIENTRY gluDeleteTess( GLUtriangulatorObj *tobj ) + +/***************************************************************************** + * gluTessEndContour + *****************************************************************************/ +void GLAPIENTRY gluTessEndContour( GLUtesselator *tobj ) { - if(tobj->error==GLU_NO_ERROR && tobj->contour_cnt) - /* was gluEndPolygon called? */ - tess_call_user_error(tobj,GLU_TESS_ERROR1); - /* delete all internal structures */ - delete_contours(tobj); - free(tobj); + DEBUGIF(2) fprintf( stderr, "\n" ); DEBUGENDIF; + DEBUGP(2, (" -> gluTessEndContour(tobj: %p)\n", tobj)); + + TESS_CHECK_ERRORS( tobj ); + + if ( tobj->current_contour == NULL ) { + tess_error_callback( tobj, GLU_TESS_ERROR2, NULL ); + return; + } + + if ( tobj->current_contour->vertex_count > 0 ) + { + inspect_current_contour( tobj ); + } + + cleanup: + DEBUGP(2, (" <- gluTessEndContour(tobj: %p)\n\n", tobj)); + return; } -void GLAPIENTRY gluBeginPolygon( GLUtriangulatorObj *tobj ) +/***************************************************************************** + * gluTessEndPolygon + *****************************************************************************/ +void GLAPIENTRY gluTessEndPolygon( GLUtesselator *tobj ) { -/* - if(tobj->error!=GLU_NO_ERROR) - return; -*/ - tobj->error = GLU_NO_ERROR; - if(tobj->current_polygon!=NULL) + DEBUGP(2, ("-> gluTessEndPolygon(tobj: %p)\n", tobj)); + TESS_CHECK_ERRORS( tobj ); + + /* + * Ensure gluTessBeginPolygon was called, otherwise we can't do anything. + */ + if ( tobj->current_contour != NULL ) { + tess_error_callback( tobj, GLU_TESS_ERROR2, NULL ); + return; + } + TESS_CHECK_ERRORS( tobj ); + + /* + * Ensure we have at least one contour to tessellate. If we have none, + * clean up and exit gracefully. + */ + if ( tobj->contour_count == 0 ) + { + DEBUGP(2, (" contour count: 0\n")); + + tess_cleanup( tobj ); + return; + } + + /* Wrap the contour list. */ + + tobj->last_contour->next = tobj->contours; + tobj->contours->previous = tobj->last_contour; + + /* tess_find_contour_hierarchies(tobj); */ + + TESS_CHECK_ERRORS( tobj ); + + /* tess_handle_holes(tobj); */ + + TESS_CHECK_ERRORS( tobj ); + + /* + * Before we tessellate the contours, ensure we have the appropriate + * callbacks registered. We at least need the begin, vertex and end + * callbacks to do any meaningful work. + */ + if ( ( ( tobj->callbacks.begin != NULL ) || + ( tobj->callbacks.beginData != NULL ) ) && + ( ( tobj->callbacks.vertex != NULL ) || + ( tobj->callbacks.vertexData != NULL ) ) && + ( ( tobj->callbacks.end != NULL ) || + ( tobj->callbacks.endData != NULL ) ) ) + { + if ( ( tobj->callbacks.edgeFlag == NULL ) && + ( tobj->callbacks.edgeFlagData == NULL ) ) { - /* gluEndPolygon was not called */ - tess_call_user_error(tobj,GLU_TESS_ERROR1); - /* delete all internal structures */ - delete_contours(tobj); + fist_tessellation( tobj ); } else { - if((tobj->current_polygon= - (tess_polygon *)malloc(sizeof(tess_polygon)))==NULL) - { - tess_call_user_error(tobj,GLU_OUT_OF_MEMORY); - return; - } - tobj->current_polygon->vertex_cnt=0; - tobj->current_polygon->vertices= - tobj->current_polygon->last_vertex=NULL; + fist_tessellation( tobj ); } + } + + cleanup: + delete_all_contours( tobj ); + + DEBUGP(2, ("<- gluTessEndPolygon(tobj: %p)\n\n", tobj)); } -void GLAPIENTRY gluEndPolygon( GLUtriangulatorObj *tobj ) +/***************************************************************************** + * gluTessCallback + *****************************************************************************/ +void GLAPIENTRY gluTessCallback( GLUtesselator *tobj, GLenum which, + void (GLCALLBACK *fn)() ) { - /*tess_contour *contour_ptr;*/ + switch ( which ) + { + /* Register the begin callbacks. */ + case GLU_TESS_BEGIN: + tobj->callbacks.begin = (void (GLCALLBACK*)(GLenum)) fn; + break; + case GLU_TESS_BEGIN_DATA: + tobj->callbacks.beginData = (void (GLCALLBACK*)(GLenum, void *)) fn; + break; + + /* Register the edge flag callbacks. */ + case GLU_TESS_EDGE_FLAG: + tobj->callbacks.edgeFlag = (void (GLCALLBACK*)(GLboolean)) fn; + break; + case GLU_TESS_EDGE_FLAG_DATA: + tobj->callbacks.edgeFlagData = + (void (GLCALLBACK*)(GLboolean, void *)) fn; + break; + + /* Register the vertex callbacks. */ + case GLU_TESS_VERTEX: + tobj->callbacks.vertex = (void (GLCALLBACK*)(void *)) fn; + break; + case GLU_TESS_VERTEX_DATA: + tobj->callbacks.vertexData = (void (GLCALLBACK*)(void *, void *)) fn; + break; + + /* Register the end callbacks. */ + case GLU_TESS_END: + tobj->callbacks.end = (void (GLCALLBACK*)(void)) fn; + break; + case GLU_TESS_END_DATA: + tobj->callbacks.endData = (void (GLCALLBACK*)(void *)) fn; + break; + + /* Register the error callbacks. */ + case GLU_TESS_ERROR: + tobj->callbacks.error = (void (GLCALLBACK*)(GLenum)) fn; + break; + case GLU_TESS_ERROR_DATA: + tobj->callbacks.errorData = (void (GLCALLBACK*)(GLenum, void *)) fn; + break; + + /* Register the combine callbacks. */ + case GLU_TESS_COMBINE: + tobj->callbacks.combine = + (void (GLCALLBACK*)(GLdouble[3], void *[4], + GLfloat [4], void **)) fn; + break; + case GLU_TESS_COMBINE_DATA: + tobj->callbacks.combineData = + (void (GLCALLBACK*)(GLdouble[3], void *[4], GLfloat [4], + void **, void *)) fn; + break; + + default: + tobj->error = GLU_INVALID_ENUM; + break; + } +} - /* there was an error */ - if(tobj->error!=GLU_NO_ERROR) goto end; - /* check if gluBeginPolygon was called */ - if(tobj->current_polygon==NULL) - { - tess_call_user_error(tobj,GLU_TESS_ERROR2); - return; - } - tess_test_polygon(tobj); - /* there was an error */ - if(tobj->error!=GLU_NO_ERROR) goto end; +/***************************************************************************** + * gluTessProperty + * + * Set the current value of the given property. + *****************************************************************************/ +void GLAPIENTRY gluTessProperty( GLUtesselator *tobj, GLenum which, + GLdouble value ) +{ + switch ( which ) + { + case GLU_TESS_BOUNDARY_ONLY: + tobj->boundary_only = (GLboolean) value; + break; + + case GLU_TESS_TOLERANCE: + tobj->tolerance = value; + break; + + case GLU_TESS_WINDING_RULE: + tobj->winding_rule = (GLenum) value; + break; + + default: + tobj->error = GLU_INVALID_ENUM; + break; + } +} - /* any real contours? */ - if(tobj->contour_cnt==0) - { - /* delete all internal structures */ - delete_contours(tobj); - return; - } - tess_find_contour_hierarchies(tobj); - /* there was an error */ - if(tobj->error!=GLU_NO_ERROR) goto end; - tess_handle_holes(tobj); - /* there was an error */ - if(tobj->error!=GLU_NO_ERROR) goto end; +/***************************************************************************** + * gluGetTessProperty + * + * Return the current value of the given property. + *****************************************************************************/ +void GLAPIENTRY gluGetTessProperty( GLUtesselator *tobj, GLenum which, + GLdouble *value ) +{ + switch ( which ) + { + case GLU_TESS_BOUNDARY_ONLY: + *value = tobj->boundary_only; + break; + + case GLU_TESS_TOLERANCE: + *value = tobj->tolerance; + break; + + case GLU_TESS_WINDING_RULE: + *value = tobj->winding_rule; + break; + + default: + tobj->error = GLU_INVALID_ENUM; + break; + } +} + + +/***************************************************************************** + * gluTessNormal + * + * Set the current tessellation normal. + *****************************************************************************/ +void GLAPIENTRY gluTessNormal( GLUtesselator *tobj, GLdouble x, + GLdouble y, GLdouble z ) +{ + tobj->plane.normal[X] = x; + tobj->plane.normal[Y] = y; + tobj->plane.normal[Z] = z; +} - /* if no callbacks, nothing to do */ - if(tobj->callbacks.begin!=NULL && tobj->callbacks.vertex!=NULL && - tobj->callbacks.end!=NULL) - { - if(tobj->callbacks.edgeFlag==NULL) - tess_tesselate(tobj); - else - tess_tesselate_with_edge_flag(tobj); - } -end: - /* delete all internal structures */ - delete_contours(tobj); + +/***************************************************************************** + * + * OBSOLETE TESSELLATION FUNCTIONS + * + *****************************************************************************/ + +void GLAPIENTRY gluBeginPolygon( GLUtesselator *tobj ) +{ + gluTessBeginPolygon( tobj, NULL ); + gluTessBeginContour( tobj ); } +void GLAPIENTRY gluNextContour( GLUtesselator *tobj, GLenum type ) +{ + gluTessEndContour( tobj ); + gluTessBeginContour( tobj ); +} -void GLAPIENTRY gluNextContour( GLUtriangulatorObj *tobj, GLenum type ) +void GLAPIENTRY gluEndPolygon( GLUtesselator *tobj ) { - if(tobj->error!=GLU_NO_ERROR) - return; - if(tobj->current_polygon==NULL) - { - tess_call_user_error(tobj,GLU_TESS_ERROR2); - return; - } - /* first contour? */ - if(tobj->current_polygon->vertex_cnt) - tess_test_polygon(tobj); + gluTessEndContour( tobj ); + gluTessEndPolygon( tobj ); } -void GLAPIENTRY gluTessVertex( GLUtriangulatorObj *tobj, GLdouble v[3], void *data ) + +/***************************************************************************** + * tess_error_callback + * + * Internal error handler. Call the user-registered error callback. + *****************************************************************************/ +void tess_error_callback( GLUtesselator *tobj, GLenum errno, void *data ) { - tess_polygon *polygon=tobj->current_polygon; - tess_vertex *last_vertex_ptr; + if ( tobj->error == GLU_NO_ERROR ) + { + tobj->error = errno; + } + + if ( tobj->callbacks.errorData != NULL ) + { + ( tobj->callbacks.errorData )( errno, data ); + } + else if ( tobj->callbacks.error != NULL ) + { + ( tobj->callbacks.error )( errno ); + } +} - if(tobj->error!=GLU_NO_ERROR) - return; - if(polygon==NULL) - { - tess_call_user_error(tobj,GLU_TESS_ERROR2); - return; + + +/***************************************************************************** + * + * INTERNAL FUNCTIONS + * + *****************************************************************************/ + + +/***************************************************************************** + * init_callbacks + *****************************************************************************/ +static void init_callbacks( tess_callbacks_t *callbacks ) +{ + callbacks->begin = ( void (GLCALLBACK*)(GLenum) ) NULL; + callbacks->beginData = ( void (GLCALLBACK*)(GLenum, void *) ) NULL; + callbacks->edgeFlag = ( void (GLCALLBACK*)(GLboolean) ) NULL; + callbacks->edgeFlagData = ( void (GLCALLBACK*)(GLboolean, void *) ) NULL; + callbacks->vertex = ( void (GLCALLBACK*)(void *) ) NULL; + callbacks->vertexData = ( void (GLCALLBACK*)(void *, void *) ) NULL; + callbacks->end = ( void (GLCALLBACK*)(void) ) NULL; + callbacks->endData = ( void (GLCALLBACK*)(void *) ) NULL; + callbacks->error = ( void (GLCALLBACK*)(GLenum) ) NULL; + callbacks->errorData = ( void (GLCALLBACK*)(GLenum, void *) ) NULL; + callbacks->combine = ( void (GLCALLBACK*)(GLdouble [3], void *[4], + GLfloat [4], void **) ) NULL; + callbacks->combineData = ( void (GLCALLBACK*)(GLdouble [3], void *[4], + GLfloat [4], void **, + void *) ) NULL; +} + + +/***************************************************************************** + * tess_cleanup + *****************************************************************************/ +static void tess_cleanup( GLUtesselator *tobj ) +{ + DEBUGP(3, (" -> tess_cleanup(tobj: %p)\n", tobj)); + + if ( tobj->current_contour != NULL ) + { + delete_current_contour( tobj ); + } + + if ( tobj->contours != NULL ) + { + delete_all_contours( tobj ); + } + + DEBUGP(3, (" <- 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; + + DEBUGP(3, (" -> inspect_current_contour(tobj: %p)\n", tobj)); + + if ( current->vertex_count < 3 ) + { + delete_current_contour( tobj ); + 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; } - last_vertex_ptr=polygon->last_vertex; - if(last_vertex_ptr==NULL) + COPY_3V( current->plane.normal, tobj->plane.normal ); + tobj->plane.dist = current->plane.dist; + } + + project_current_contour( tobj ); + + if ( save_current_contour( tobj ) == GLU_ERROR ) { + return; + } + + DEBUGP(3, (" <- 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]; + + DEBUGP(3, (" -> 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 ) { + tess_error_callback( tobj, GLU_TESS_ERROR7, NULL ); + } + + 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 ( ( fabs( c[X] ) > EQUAL_EPSILON ) || + ( fabs( c[Y] ) > EQUAL_EPSILON ) || + ( fabs( c[Z] ) > EQUAL_EPSILON ) ) { - if((last_vertex_ptr=(tess_vertex *) - malloc(sizeof(tess_vertex)))==NULL) - { - tess_call_user_error(tobj,GLU_OUT_OF_MEMORY); - return; - } - polygon->vertices=last_vertex_ptr; - polygon->last_vertex=last_vertex_ptr; - last_vertex_ptr->data=data; - last_vertex_ptr->location[0]=v[0]; - last_vertex_ptr->location[1]=v[1]; - last_vertex_ptr->location[2]=v[2]; - last_vertex_ptr->next=NULL; - last_vertex_ptr->previous=NULL; - ++(polygon->vertex_cnt); + COPY_3V( contour->plane.normal, c ); + NORMALIZE_3DV( contour->plane.normal ); + + contour->plane.dist = - DOT3( contour->plane.normal, va->coords ); + + DEBUGP(3, (" <- find_normal(tobj: %p) (%.2f, %.2f, %.2f)\n", + tobj, contour->plane.normal[X], + contour->plane.normal[Y], contour->plane.normal[Z])); + return GLU_NO_ERROR; } else { - tess_vertex *vertex_ptr; - - /* same point twice? */ - if(fabs(last_vertex_ptr->location[0]-v[0]) < EPSILON && - fabs(last_vertex_ptr->location[1]-v[1]) < EPSILON && - fabs(last_vertex_ptr->location[2]-v[2]) < EPSILON) - { - tess_call_user_error(tobj,GLU_TESS_ERROR6); - return; - } - if((vertex_ptr=(tess_vertex *) - malloc(sizeof(tess_vertex)))==NULL) - { - tess_call_user_error(tobj,GLU_OUT_OF_MEMORY); - return; - } - vertex_ptr->data=data; - vertex_ptr->location[0]=v[0]; - vertex_ptr->location[1]=v[1]; - vertex_ptr->location[2]=v[2]; - vertex_ptr->next=NULL; - vertex_ptr->previous=last_vertex_ptr; - ++(polygon->vertex_cnt); - last_vertex_ptr->next=vertex_ptr; - polygon->last_vertex=vertex_ptr; + DEBUGP(3, (" *** skipping colinear points...\n")); } + } + tess_error_callback( tobj, GLU_TESS_ERROR7, NULL ); + + DEBUGP(3, (" <- find_normal(tobj: %p) ERROR\n", tobj)); + return GLU_ERROR; } +/***************************************************************************** + * project_current_contour + *****************************************************************************/ +static GLdouble twice_contour_area( tess_vertex_t *vertex, + tess_vertex_t *last_vertex ); -static void delete_contours(GLUtriangulatorObj *tobj) +static void project_current_contour( GLUtesselator *tobj ) { - tess_polygon *polygon=tobj->current_polygon; - tess_contour *contour,*contour_tmp; - tess_vertex *vertex,*vertex_tmp; + 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; - /* remove current_polygon list - if exists due to detected error */ - if(polygon!=NULL) - { - if (polygon->vertices) - { - for(vertex=polygon->vertices;vertex!=polygon->last_vertex;) - { - vertex_tmp=vertex->next; - free(vertex); - vertex=vertex_tmp; - } - free(vertex); - } - free(polygon); - tobj->current_polygon=NULL; - } - /* remove all contour data */ - for(contour=tobj->contours;contour!=NULL;) + DEBUGP(3, (" -> project_current_contour(tobj: %p)\n", tobj)); + + if ( current == NULL ) { return; } + + DEBUGP(3, (" normal: (%.2f, %.2f, %.2f) dist: %.2f n: %u\n", + current->plane.normal[X], current->plane.normal[Y], + current->plane.normal[Z], current->plane.dist, + current->vertex_count)); + + /* 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 ); + 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 ); + rotx = acos( dot ); + + for ( vertex = current->vertices, i = 0; + i < current->vertex_count; vertex = vertex->next, i++ ) + { + tess_plane_t *plane = ¤t->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 ); + + DEBUGP(3, (" v %d: (%.2f, %.2f, %.2f) -> (%.2f, %.2f)\n", + i, vertex->coords[X], vertex->coords[Y], + vertex->coords[Z], vertex->v[X], vertex->v[Y])); + } + + 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; + } + + DEBUGP(3, (" <- 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; + + DEBUGP(3, (" -> save_current_contour(tobj: %p)\n", tobj)); + + 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; + + DEBUGP(3, (" <- save_current_contour()\n")); + return GLU_NO_ERROR; +} + +/***************************************************************************** + * delete_current_contour + *****************************************************************************/ +static void delete_current_contour( GLUtesselator *tobj ) +{ + tess_contour_t *current = tobj->current_contour; + tess_vertex_t *vertex, *next; + GLuint i; + + DEBUGP(3, (" -> delete_current_contour(contour: %p)\n", current)); + + if ( current == NULL ) { return; } + + for ( vertex = current->vertices, i = 0; i < current->vertex_count; i++) + { + next = vertex->next; + free( vertex ); + vertex = next; + } + + free( current ); + tobj->current_contour = NULL; + + DEBUGP(3, (" <- delete_current_contour()\n")); +} + +/***************************************************************************** + * delete_all_contours + *****************************************************************************/ +static void delete_all_contours( GLUtesselator *tobj ) +{ + tess_contour_t *current = tobj->current_contour, *next_contour; + tess_vertex_t *vertex, *next_vertex; + GLuint i; + + DEBUGP(3, (" -> delete_all_contours(tobj: %p)\n", tobj)); + + if ( current != NULL ) + { + delete_current_contour( tobj ); + } + + for ( current = tobj->contours, i = 0; i < tobj->contour_count; i++ ) + { + vertex = current->vertices; + + while ( vertex != current->last_vertex ) { - for(vertex=contour->vertices;vertex!=contour->last_vertex;) - { - vertex_tmp=vertex->next; - free(vertex); - vertex=vertex_tmp; - } - free(vertex); - contour_tmp=contour->next; - free(contour); - contour=contour_tmp; + next_vertex = vertex->next; + free( vertex ); + vertex = next_vertex; } - tobj->contours=tobj->last_contour=NULL; - tobj->contour_cnt=0; + free( 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; + + DEBUGP(3, (" <- delete_all_contours(tobj: %p)\n", tobj)); } +/***************************************************************************** + * Debugging output + *****************************************************************************/ +#ifdef _DEBUG +int vdebugstr( char *format_str, ... ) +{ + va_list ap; + va_start( ap, format_str ); + + vfprintf( stderr, format_str, ap ); + va_end( ap ); + return 0; +} +#endif diff --git a/src/glu/mesa/tess.h b/src/glu/mesa/tess.h index 53d673ccbea..fe8296c976c 100644 --- a/src/glu/mesa/tess.h +++ b/src/glu/mesa/tess.h @@ -1,121 +1,108 @@ -/* $Id: tess.h,v 1.1 1999/08/19 00:55:42 jtg Exp $ */ +/* $Id: tess.h,v 1.2 1999/09/10 02:03:31 gareth Exp $ */ /* * Mesa 3-D graphics library * Version: 3.1 - * Copyright (C) 1995-1998 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. + * + * Copyright (C) 1999 Brian Paul 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 and this permission notice 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 + * BRIAN PAUL 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. */ - -/* - * $Log: tess.h,v $ - * Revision 1.1 1999/08/19 00:55:42 jtg - * Initial revision - * - * Revision 1.5 1999/02/27 13:55:31 brianp - * fixed BeOS-related GLU typedef problems - * - * Revision 1.4 1999/01/03 03:23:15 brianp - * now using GLAPIENTRY and GLCALLBACK keywords (Ted Jump) - * - * Revision 1.3 1997/10/29 02:02:20 brianp - * various MS Windows compiler changes (David Bucciarelli, v20 3dfx driver) +/***************************************************************************** * - * Revision 1.2 1997/05/24 13:30:58 brianp - * added TESS_H multi-inclusion prevention test + * GLU 1.3 Polygon Tessellation by Gareth Hughes <[email protected]> * - * 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 - */ - + *****************************************************************************/ -#ifndef TESS_H -#define TESS_H +#ifndef __GLU_TESS_H__ +#define __GLU_TESS_H__ +#include <stdarg.h> +#include <stdio.h> #include "gluP.h" -#define EPSILON 1e-06 /* epsilon for double precision compares */ - -typedef enum -{ - OXY, - OYZ, - OXZ -} projection_type; - -typedef struct callbacks_str -{ - void (GLCALLBACK *begin)( GLenum mode ); - void (GLCALLBACK *edgeFlag)( GLboolean flag ); - void (GLCALLBACK *vertex)( GLvoid *v ); - void (GLCALLBACK *end)( void ); - void (GLCALLBACK *error)( GLenum err ); -} tess_callbacks; - -typedef struct vertex_str -{ - void *data; - GLdouble location[3]; - GLdouble x,y; - GLboolean edge_flag; - struct vertex_str *shadow_vertex; - struct vertex_str *next,*previous; -} tess_vertex; - -typedef struct contour_str -{ - GLenum type; - GLuint vertex_cnt; - GLdouble area; - GLenum orientation; - struct vertex_str *vertices,*last_vertex; - struct contour_str *next,*previous; -} tess_contour; +#include "tess_typedefs.h" +#include "tess_heap.h" +#if 0 +#include "tess_grid.h" +#endif -typedef struct polygon_str -{ - GLuint vertex_cnt; - GLdouble A,B,C,D; - GLdouble area; - GLenum orientation; - struct vertex_str *vertices,*last_vertex; -} tess_polygon; +#ifdef __cplusplus +extern "C" { +#endif +/***************************************************************************** + * The GLUtesselator structure: + *****************************************************************************/ struct GLUtesselator { - tess_contour *contours,*last_contour; - GLuint contour_cnt; - tess_callbacks callbacks; - tess_polygon *current_polygon; - GLenum error; - GLdouble A,B,C,D; - projection_type projection; + tess_callbacks_t callbacks; + GLboolean boundary_only; + GLenum winding_rule; + GLdouble tolerance; + tess_plane_t plane; + GLuint contour_count; + tess_contour_t *contours, *last_contour; + tess_contour_t *current_contour; + GLdouble mins[2], maxs[2]; + GLuint vertex_count; + tess_vertex_t **sorted_vertices; +#if 0 + tess_grid_t *grid; /* Not currently used... */ +#endif + heap_t *heap; + GLenum error; }; -extern void tess_call_user_error(GLUtriangulatorObj *,GLenum); - +/***************************************************************************** + * Tessellation error handler: + *****************************************************************************/ +extern void tess_error_callback( GLUtesselator *, GLenum, void * ); + + +/***************************************************************************** + * Debugging output: (to be removed...) + *****************************************************************************/ +extern int tess_debug_level; +int vdebugstr( char *format_str, ... ); + +#ifdef _DEBUG +#define DEBUGP(level, body) \ + do { \ + if ( tess_debug_level >= level ) { \ + vdebugstr( "%11.11s:%-5d ", __FILE__, __LINE__, level ); \ + vdebugstr body; \ + fflush ( stderr ); \ + } \ + } while ( 0 ) +#define DEBUGIF(level) do { if ( tess_debug_level >= level ) { +#define DEBUGENDIF } } while ( 0 ) +#else +#define DEBUGP(level, body) +#define DEBUGIF(level) while(0) { +#define DEBUGENDIF } +#endif +#ifdef __cplusplus +} #endif + +#endif // __GLU_TESS_H__ diff --git a/src/glu/mesa/tesselat.c b/src/glu/mesa/tesselat.c deleted file mode 100644 index 1e424c17ca7..00000000000 --- a/src/glu/mesa/tesselat.c +++ /dev/null @@ -1,456 +0,0 @@ -/* $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)(); -} |