summaryrefslogtreecommitdiff
path: root/src/glu/mesa/polytest.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/glu/mesa/polytest.c')
-rw-r--r--src/glu/mesa/polytest.c1049
1 files changed, 0 insertions, 1049 deletions
diff --git a/src/glu/mesa/polytest.c b/src/glu/mesa/polytest.c
deleted file mode 100644
index 9b42c63477..0000000000
--- 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 (pete@ohm.york.ac.uk)
- *
- * 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;
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-04 02:12:13 +0000