summaryrefslogtreecommitdiffstats
path: root/src/glu/mesa/polytest.c
diff options
context:
space:
mode:
authorBrian Paul <brian.paul@tungstengraphics.com>2000-07-11 14:11:04 +0000
committerBrian Paul <brian.paul@tungstengraphics.com>2000-07-11 14:11:04 +0000
commitf88602394d7cc340cc850622308ce1cbbff332a5 (patch)
tree0a23d3e19af28217550753d29535afafa39ccfea /src/glu/mesa/polytest.c
parentf545e2aedde0d0c09c76a7e772b333163fddba17 (diff)
reverted to old tessellator (GLU 1.1)
Diffstat (limited to 'src/glu/mesa/polytest.c')
-rw-r--r--src/glu/mesa/polytest.c938
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 00000000000..0995cb032f0
--- /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;
+}