diff options
Diffstat (limited to 'src/glu/mesa/polytest.c')
| -rw-r--r-- | src/glu/mesa/polytest.c | 937 |
1 files changed, 0 insertions, 937 deletions
diff --git a/src/glu/mesa/polytest.c b/src/glu/mesa/polytest.c deleted file mode 100644 index 1ff966f61ce..00000000000 --- a/src/glu/mesa/polytest.c +++ /dev/null @@ -1,937 +0,0 @@ - -/* - * 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 = 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; -} |