/* $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 #include #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; inext , 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;ivertex_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)y - b->y)y - d->y)y - b->y)y - c->y)y - a->y)y - d->y)y - a->y) 0.0) { if((fabs(a->x - c->x)x - b->x)x - d->x)x - b->x)x - c->x)x - a->x)x - d->x)x - a->x) 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;icontours; 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) && (ynext; } 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; inext , i++) { for(j=0; jnext , 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; inext) { for(v2=hole->vertices , vertex2_cnt=hole->vertex_cnt , j=0; jnext) { /* does edge (v1,v2) intersect any edge of contour */ for(tmp_vertex=contour->vertices , tmp_vertex_cnt=contour->vertex_cnt , k=0; knext , 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; knext , 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; knext , 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; }