This is polytest.c in view mode; [Download] [Up]
/* $Id: polytest.c,v 1.1 1996/09/27 01:19:39 brianp Exp $ */
/*
* Mesa 3-D graphics library
* Version: 2.0
* Copyright (C) 1995-1996 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 1996/09/27 01:19:39 brianp
* Initial revision
*
*/
/*
* This file is part of the polygon tesselation code contributed by
* Bogdan Sikorski
*/
#include <math.h>
#include <stdlib.h>
#include "gluP.h"
#include "tess.h"
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;
/* free current_polygon structures */
for(vertex=polygon->vertices;vertex!=polygon->last_vertex;)
{
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 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;
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.