diff options
Diffstat (limited to 'src/glu/mesa/polytest.c')
| -rw-r--r-- | src/glu/mesa/polytest.c | 938 |
1 files changed, 938 insertions, 0 deletions
diff --git a/src/glu/mesa/polytest.c b/src/glu/mesa/polytest.c new file mode 100644 index 0000000000..0995cb032f --- /dev/null +++ b/src/glu/mesa/polytest.c @@ -0,0 +1,938 @@ +/* $Id: polytest.c,v 1.3 2000/07/11 14:11:04 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 <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 +#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; + + /* 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; +} |