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