/* $Id: polytest.c,v 1.2 2003-08-22 20:11:43 brianp Exp $ */ /* * Mesa 3-D graphics library * Version: 3.3 * Copyright (C) 1995-2000 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. */ /* * 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; 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 #ifdef WIN32 __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 = 0; /* 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; }