| /* $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; |
| } |