src/glu/mesa/polytest.c

   1
   2 /*
   3  * Mesa 3-D graphics library
   4  * Version:  3.3
   5  * Copyright (C) 1995-2000  Brian Paul
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Library General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Library General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Library General Public
  18  * License along with this library; if not, write to the Free
  19  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20  */
  21
  22
  23 /*
  24  * This file is part of the polygon tesselation code contributed by
  25  * Bogdan Sikorski
  26  */
  27
  28
  29 #ifdef PC_HEADER
  30 #include "all.h"
  31 #else
  32 #include <math.h>
  33 #include <stdlib.h>
  34 #include "gluP.h"
  35 #include "tess.h"
  36 #endif
  37
  38
  39
  40 static GLenum store_polygon_as_contour(GLUtriangulatorObj *);
  41 static void free_current_polygon(tess_polygon *);
  42 static void prepare_projection_info(GLUtriangulatorObj *);
  43 static GLdouble twice_the_polygon_area(tess_vertex *, tess_vertex *);
  44 static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *);
  45 void tess_find_contour_hierarchies(GLUtriangulatorObj *);
  46 static GLenum test_for_overlapping_contours(GLUtriangulatorObj *);
  47 static GLenum contours_overlap(tess_contour *, tess_polygon *);
  48 static GLenum is_contour_contained_in(tess_contour *, tess_contour *);
  49 static void add_new_exterior(GLUtriangulatorObj *, tess_contour *);
  50 static void add_new_interior(GLUtriangulatorObj *, tess_contour *,
  51                              tess_contour *);
  52 static void add_interior_with_hierarchy_check(GLUtriangulatorObj *,
  53                                               tess_contour *, tess_contour *);
  54 static void reverse_hierarchy_and_add_exterior(GLUtriangulatorObj *,
  55                                                tess_contour *,
  56                                                tess_contour *);
  57 static GLboolean point_in_polygon(tess_contour *, GLdouble, GLdouble);
  58 static void shift_interior_to_exterior(GLUtriangulatorObj *, tess_contour *);
  59 static void add_exterior_with_check(GLUtriangulatorObj *, tess_contour *,
  60                                     tess_contour *);
  61 static GLenum cut_out_hole(GLUtriangulatorObj *, tess_contour *,
  62                            tess_contour *);
  63 static GLenum merge_hole_with_contour(GLUtriangulatorObj *,
  64                                       tess_contour *, tess_contour *,
  65                                       tess_vertex *, tess_vertex *);
  66
  67 static GLenum
  68 find_normal(GLUtriangulatorObj * tobj)
  69 {
  70    tess_polygon *polygon = tobj->current_polygon;
  71    tess_vertex *va, *vb, *vc;
  72    GLdouble A, B, C;
  73    GLdouble A0, A1, A2, B0, B1, B2;
  74
  75    va = polygon->vertices;
  76    vb = va->next;
  77    A0 = vb->location[0] - va->location[0];
  78    A1 = vb->location[1] - va->location[1];
  79    A2 = vb->location[2] - va->location[2];
  80    for (vc = vb->next; vc != va; vc = vc->next) {
  81       B0 = vc->location[0] - va->location[0];
  82       B1 = vc->location[1] - va->location[1];
  83       B2 = vc->location[2] - va->location[2];
  84       A = A1 * B2 - A2 * B1;
  85       B = A2 * B0 - A0 * B2;
  86       C = A0 * B1 - A1 * B0;
  87       if (fabs(A) > EPSILON || fabs(B) > EPSILON || fabs(C) > EPSILON) {
  88          polygon->A = A;
  89          polygon->B = B;
  90          polygon->C = C;
  91          polygon->D =
  92             -A * va->location[0] - B * va->location[1] - C * va->location[2];
  93          return GLU_NO_ERROR;
  94       }
  95    }
  96    tess_call_user_error(tobj, GLU_TESS_ERROR7);
  97    return GLU_ERROR;
  98 }
  99
 100 void
 101 tess_test_polygon(GLUtriangulatorObj * tobj)
 102 {
 103    tess_polygon *polygon = tobj->current_polygon;
 104
 105    /* any vertices defined? */
 106    if (polygon->vertex_cnt < 3) {
 107       free_current_polygon(polygon);
 108       return;
 109    }
 110    /* wrap pointers */
 111    polygon->last_vertex->next = polygon->vertices;
 112    polygon->vertices->previous = polygon->last_vertex;
 113    /* determine the normal */
 114    if (find_normal(tobj) == GLU_ERROR)
 115       return;
 116    /* compare the normals of previously defined contours and this one */
 117    /* first contour define ? */
 118    if (tobj->contours == NULL) {
 119       tobj->A = polygon->A;
 120       tobj->B = polygon->B;
 121       tobj->C = polygon->C;
 122       tobj->D = polygon->D;
 123       /* determine the best projection to use */
 124       if (fabs(polygon->A) > fabs(polygon->B))
 125          if (fabs(polygon->A) > fabs(polygon->C))
 126             tobj->projection = OYZ;
 127          else
 128             tobj->projection = OXY;
 129       else if (fabs(polygon->B) > fabs(polygon->C))
 130          tobj->projection = OXZ;
 131       else
 132          tobj->projection = OXY;
 133    }
 134    else {
 135       GLdouble a[3], b[3];
 136       tess_vertex *vertex = polygon->vertices;
 137
 138       a[0] = tobj->A;
 139       a[1] = tobj->B;
 140       a[2] = tobj->C;
 141       b[0] = polygon->A;
 142       b[1] = polygon->B;
 143       b[2] = polygon->C;
 144
 145       /* compare the normals */
 146       if (fabs(a[1] * b[2] - a[2] * b[1]) > EPSILON ||
 147           fabs(a[2] * b[0] - a[0] * b[2]) > EPSILON ||
 148           fabs(a[0] * b[1] - a[1] * b[0]) > EPSILON) {
 149          /* not coplanar */
 150          tess_call_user_error(tobj, GLU_TESS_ERROR9);
 151          return;
 152       }
 153       /* the normals are parallel - test for plane equation */
 154       if (fabs(a[0] * vertex->location[0] + a[1] * vertex->location[1] +
 155                a[2] * vertex->location[2] + tobj->D) > EPSILON) {
 156          /* not the same plane */
 157          tess_call_user_error(tobj, GLU_TESS_ERROR9);
 158          return;
 159       }
 160    }
 161    prepare_projection_info(tobj);
 162    if (verify_edge_vertex_intersections(tobj) == GLU_ERROR)
 163       return;
 164    if (test_for_overlapping_contours(tobj) == GLU_ERROR)
 165       return;
 166    if (store_polygon_as_contour(tobj) == GLU_ERROR)
 167       return;
 168 }
 169
 170 static GLenum
 171 test_for_overlapping_contours(GLUtriangulatorObj * tobj)
 172 {
 173    tess_contour *contour;
 174    tess_polygon *polygon;
 175
 176    polygon = tobj->current_polygon;
 177    for (contour = tobj->contours; contour != NULL; contour = contour->next)
 178       if (contours_overlap(contour, polygon) != GLU_NO_ERROR) {
 179          tess_call_user_error(tobj, GLU_TESS_ERROR5);
 180          return GLU_ERROR;
 181       }
 182    return GLU_NO_ERROR;
 183 }
 184
 185 static GLenum
 186 store_polygon_as_contour(GLUtriangulatorObj * tobj)
 187 {
 188    tess_polygon *polygon = tobj->current_polygon;
 189    tess_contour *contour = tobj->contours;
 190
 191    /* the first contour defined */
 192    if (contour == NULL) {
 193       if ((contour = (tess_contour *) malloc(sizeof(tess_contour))) == NULL) {
 194          tess_call_user_error(tobj, GLU_OUT_OF_MEMORY);
 195          free_current_polygon(polygon);
 196          return GLU_ERROR;
 197       }
 198       tobj->contours = tobj->last_contour = contour;
 199       contour->next = contour->previous = NULL;
 200    }
 201    else {
 202       if ((contour = (tess_contour *) malloc(sizeof(tess_contour))) == NULL) {
 203          tess_call_user_error(tobj, GLU_OUT_OF_MEMORY);
 204          free_current_polygon(polygon);
 205          return GLU_ERROR;
 206       }
 207       contour->previous = tobj->last_contour;
 208       tobj->last_contour->next = contour;
 209       tobj->last_contour = contour;
 210       contour->next = NULL;
 211    }
 212    /* mark all vertices in new contour as not special */
 213    /* and all are boundary edges */
 214    {
 215       tess_vertex *vertex;
 216       GLuint vertex_cnt, i;
 217
 218       for (vertex = polygon->vertices, i = 0, vertex_cnt =
 219            polygon->vertex_cnt; i < vertex_cnt; vertex = vertex->next, i++) {
 220          vertex->shadow_vertex = NULL;
 221          vertex->edge_flag = GL_TRUE;
 222       }
 223    }
 224    contour->vertex_cnt = polygon->vertex_cnt;
 225    contour->area = polygon->area;
 226    contour->orientation = polygon->orientation;
 227    contour->type = GLU_UNKNOWN;
 228    contour->vertices = polygon->vertices;
 229    contour->last_vertex = polygon->last_vertex;
 230    polygon->vertices = polygon->last_vertex = NULL;
 231    polygon->vertex_cnt = 0;
 232    ++(tobj->contour_cnt);
 233    return GLU_NO_ERROR;
 234 }
 235
 236 static void
 237 free_current_polygon(tess_polygon * polygon)
 238 {
 239    tess_vertex *vertex, *vertex_tmp;
 240    GLuint i;
 241
 242    /* free current_polygon structures */
 243    for (vertex = polygon->vertices, i = 0; i < polygon->vertex_cnt; i++) {
 244       vertex_tmp = vertex->next;
 245       free(vertex);
 246       vertex = vertex_tmp;
 247    }
 248    polygon->vertices = polygon->last_vertex = NULL;
 249    polygon->vertex_cnt = 0;
 250 }
 251
 252 static void
 253 prepare_projection_info(GLUtriangulatorObj * tobj)
 254 {
 255    tess_polygon *polygon = tobj->current_polygon;
 256    tess_vertex *vertex, *last_vertex_ptr;
 257    GLdouble area;
 258
 259    last_vertex_ptr = polygon->last_vertex;
 260    switch (tobj->projection) {
 261    case OXY:
 262       for (vertex = polygon->vertices; vertex != last_vertex_ptr;
 263            vertex = vertex->next) {
 264          vertex->x = vertex->location[0];
 265          vertex->y = vertex->location[1];
 266       }
 267       last_vertex_ptr->x = last_vertex_ptr->location[0];
 268       last_vertex_ptr->y = last_vertex_ptr->location[1];
 269       break;
 270    case OXZ:
 271       for (vertex = polygon->vertices; vertex != last_vertex_ptr;
 272            vertex = vertex->next) {
 273          vertex->x = vertex->location[0];
 274          vertex->y = vertex->location[2];
 275       }
 276       last_vertex_ptr->x = last_vertex_ptr->location[0];
 277       last_vertex_ptr->y = last_vertex_ptr->location[2];
 278       break;
 279    case OYZ:
 280       for (vertex = polygon->vertices; vertex != last_vertex_ptr;
 281            vertex = vertex->next) {
 282          vertex->x = vertex->location[1];
 283          vertex->y = vertex->location[2];
 284       }
 285       last_vertex_ptr->x = last_vertex_ptr->location[1];
 286       last_vertex_ptr->y = last_vertex_ptr->location[2];
 287       break;
 288    }
 289    area = twice_the_polygon_area(polygon->vertices, polygon->last_vertex);
 290    if (area >= 0.0) {
 291       polygon->orientation = GLU_CCW;
 292       polygon->area = area;
 293    }
 294    else {
 295       polygon->orientation = GLU_CW;
 296       polygon->area = -area;
 297    }
 298 }
 299
 300 static GLdouble
 301 twice_the_polygon_area(tess_vertex * vertex, tess_vertex * last_vertex)
 302 {
 303    tess_vertex *next;
 304    GLdouble area, x, y;
 305
 306    area = 0.0;
 307    x = vertex->x;
 308    y = vertex->y;
 309    vertex = vertex->next;
 310    for (; vertex != last_vertex; vertex = vertex->next) {
 311       next = vertex->next;
 312       area +=
 313          (vertex->x - x) * (next->y - y) - (vertex->y - y) * (next->x - x);
 314    }
 315    return area;
 316 }
 317
 318 /* test if edges ab and cd intersect */
 319 /* if not return GLU_NO_ERROR, else if cross return GLU_TESS_ERROR8, */
 320 /* else if adjacent return GLU_TESS_ERROR4 */
 321 static GLenum
 322 edge_edge_intersect(tess_vertex * a,
 323                     tess_vertex * b, tess_vertex * c, tess_vertex * d)
 324 {
 325    GLdouble denom, r, s;
 326    GLdouble xba, ydc, yba, xdc, yac, xac;
 327
 328    xba = b->x - a->x;
 329    yba = b->y - a->y;
 330    xdc = d->x - c->x;
 331    ydc = d->y - c->y;
 332    xac = a->x - c->x;
 333    yac = a->y - c->y;
 334    denom = xba * ydc - yba * xdc;
 335    r = yac * xdc - xac * ydc;
 336    /* parallel? */
 337    if (fabs(denom) < EPSILON) {
 338       if (fabs(r) < EPSILON) {
 339          /* colinear */
 340          if (fabs(xba) < EPSILON) {
 341             /* compare the Y coordinate */
 342             if (yba > 0.0) {
 343                if (
 344                    (fabs(a->y - c->y) < EPSILON
 345                     && fabs(c->y - b->y) < EPSILON)
 346                    || (fabs(a->y - d->y) < EPSILON
 347                        && fabs(d->y - b->y) <
 348                        EPSILON)) return GLU_TESS_ERROR4;
 349
 350             }
 351             else {
 352                if (
 353                    (fabs(b->y - c->y) < EPSILON
 354                     && fabs(c->y - a->y) < EPSILON)
 355                    || (fabs(b->y - d->y) < EPSILON
 356                        && fabs(d->y - a->y) <
 357                        EPSILON)) return GLU_TESS_ERROR4;
 358             }
 359          }
 360          else {
 361             /* compare the X coordinate */
 362             if (xba > 0.0) {
 363                if (
 364                    (fabs(a->x - c->x) < EPSILON
 365                     && fabs(c->x - b->x) < EPSILON)
 366                    || (fabs(a->x - d->x) < EPSILON
 367                        && fabs(d->x - b->x) <
 368                        EPSILON)) return GLU_TESS_ERROR4;
 369             }
 370             else {
 371                if (
 372                    (fabs(b->x - c->x) < EPSILON
 373                     && fabs(c->x - a->x) < EPSILON)
 374                    || (fabs(b->x - d->x) < EPSILON
 375                        && fabs(d->x - a->x) <
 376                        EPSILON)) return GLU_TESS_ERROR4;
 377             }
 378          }
 379       }
 380       return GLU_NO_ERROR;
 381    }
 382    r /= denom;
 383    s = (yac * xba - xac * yba) / denom;
 384    /* test if one vertex lies on other edge */
 385    if (((fabs(r) < EPSILON || (r < 1.0 + EPSILON && r > 1.0 - EPSILON)) &&
 386         s > -EPSILON && s < 1.0 + EPSILON) ||
 387        ((fabs(s) < EPSILON || (s < 1.0 + EPSILON && s > 1.0 - EPSILON)) &&
 388         r > -EPSILON && r < 1.0 + EPSILON)) {
 389       return GLU_TESS_ERROR4;
 390    }
 391    /* test for crossing */
 392    if (r > -EPSILON && r < 1.0 + EPSILON && s > -EPSILON && s < 1.0 + EPSILON) {
 393       return GLU_TESS_ERROR8;
 394    }
 395    return GLU_NO_ERROR;
 396 }
 397
 398 static GLenum
 399 verify_edge_vertex_intersections(GLUtriangulatorObj * tobj)
 400 {
 401    tess_polygon *polygon = tobj->current_polygon;
 402    tess_vertex *vertex1, *last_vertex, *vertex2;
 403    GLenum test;
 404
 405    last_vertex = polygon->last_vertex;
 406    vertex1 = last_vertex;
 407    for (vertex2 = vertex1->next->next;
 408         vertex2->next != last_vertex; vertex2 = vertex2->next) {
 409       test = edge_edge_intersect(vertex1, vertex1->next, vertex2,
 410                                  vertex2->next);
 411       if (test != GLU_NO_ERROR) {
 412          tess_call_user_error(tobj, test);
 413          return GLU_ERROR;
 414       }
 415    }
 416    for (vertex1 = polygon->vertices;
 417         vertex1->next->next != last_vertex; vertex1 = vertex1->next) {
 418       for (vertex2 = vertex1->next->next;
 419            vertex2 != last_vertex; vertex2 = vertex2->next) {
 420          test = edge_edge_intersect(vertex1, vertex1->next, vertex2,
 421                                     vertex2->next);
 422          if (test != GLU_NO_ERROR) {
 423             tess_call_user_error(tobj, test);
 424             return GLU_ERROR;
 425          }
 426       }
 427    }
 428    return GLU_NO_ERROR;
 429 }
 430
 431 static int
 432 #ifdef WIN32
 433   __cdecl
 434 #endif
 435 area_compare(const void *a, const void *b)
 436 {
 437    GLdouble area1, area2;
 438
 439    area1 = (*((tess_contour **) a))->area;
 440    area2 = (*((tess_contour **) b))->area;
 441    if (area1 < area2)
 442       return 1;
 443    if (area1 > area2)
 444       return -1;
 445    return 0;
 446 }
 447
 448 void
 449 tess_find_contour_hierarchies(GLUtriangulatorObj * tobj)
 450 {
 451    tess_contour **contours;     /* dinamic array of pointers */
 452    tess_contour *tmp_contour_ptr = tobj->contours;
 453    GLuint cnt, i;
 454    GLenum result;
 455    GLboolean hierarchy_changed;
 456
 457    /* any contours? */
 458    if (tobj->contour_cnt < 2) {
 459       tobj->contours->type = GLU_EXTERIOR;
 460       return;
 461    }
 462    if ((contours = (tess_contour **)
 463         malloc(sizeof(tess_contour *) * (tobj->contour_cnt))) == NULL) {
 464       tess_call_user_error(tobj, GLU_OUT_OF_MEMORY);
 465       return;
 466    }
 467    for (tmp_contour_ptr = tobj->contours, cnt = 0;
 468         tmp_contour_ptr != NULL; tmp_contour_ptr = tmp_contour_ptr->next)
 469       contours[cnt++] = tmp_contour_ptr;
 470    /* now sort the contours in decreasing area size order */
 471    qsort((void *) contours, (size_t) cnt, (size_t) sizeof(tess_contour *),
 472          area_compare);
 473    /* we leave just the first contour - remove others from list */
 474    tobj->contours = contours[0];
 475    tobj->contours->next = tobj->contours->previous = NULL;
 476    tobj->last_contour = tobj->contours;
 477    tobj->contour_cnt = 1;
 478    /* first contour is the one with greatest area */
 479    /* must be EXTERIOR */
 480    tobj->contours->type = GLU_EXTERIOR;
 481    tmp_contour_ptr = tobj->contours;
 482    /* now we play! */
 483    for (i = 1; i < cnt; i++) {
 484       hierarchy_changed = GL_FALSE;
 485       for (tmp_contour_ptr = tobj->contours;
 486            tmp_contour_ptr != NULL; tmp_contour_ptr = tmp_contour_ptr->next) {
 487          if (tmp_contour_ptr->type == GLU_EXTERIOR) {
 488             /* check if contour completely contained in EXTERIOR */
 489             result = is_contour_contained_in(tmp_contour_ptr, contours[i]);
 490             switch (result) {
 491             case GLU_INTERIOR:
 492                /* now we have to check if contour is inside interiors */
 493                /* or not */
 494                /* any interiors? */
 495                if (tmp_contour_ptr->next != NULL &&
 496                    tmp_contour_ptr->next->type == GLU_INTERIOR) {
 497                   /* for all interior, check if inside any of them */
 498                   /* if not inside any of interiors, its another */
 499                   /* interior */
 500                   /* or it may contain some interiors, then change */
 501                   /* the contained interiors to exterior ones */
 502                   add_interior_with_hierarchy_check(tobj,
 503                                                     tmp_contour_ptr,
 504                                                     contours[i]);
 505                }
 506                else {
 507                   /* not in interior, add as new interior contour */
 508                   add_new_interior(tobj, tmp_contour_ptr, contours[i]);
 509                }
 510                hierarchy_changed = GL_TRUE;
 511                break;
 512             case GLU_EXTERIOR:
 513                /* ooops, the marked as EXTERIOR (contours[i]) is */
 514                /* actually an interior of tmp_contour_ptr */
 515                /*  reverse the local hierarchy */
 516                reverse_hierarchy_and_add_exterior(tobj, tmp_contour_ptr,
 517                                                   contours[i]);
 518                hierarchy_changed = GL_TRUE;
 519                break;
 520             case GLU_NO_ERROR:
 521                break;
 522             default:
 523                abort();
 524             }
 525          }
 526          if (hierarchy_changed)
 527             break;              /* break from for loop */
 528       }
 529       if (hierarchy_changed == GL_FALSE) {
 530          /* disjoint with all contours, add to contour list */
 531          add_new_exterior(tobj, contours[i]);
 532       }
 533    }
 534    free(contours);
 535 }
 536
 537 /* returns GLU_INTERIOR if inner is completey enclosed within outer */
 538 /* returns GLU_EXTERIOR if outer is completely enclosed within inner */
 539 /* returns GLU_NO_ERROR if contours are disjoint */
 540 static GLenum
 541 is_contour_contained_in(tess_contour * outer, tess_contour * inner)
 542 {
 543    GLenum relation_flag;
 544
 545    /* set relation_flag to relation of containment of first inner vertex */
 546    /* regarding outer contour */
 547    if (point_in_polygon(outer, inner->vertices->x, inner->vertices->y))
 548       relation_flag = GLU_INTERIOR;
 549    else
 550       relation_flag = GLU_EXTERIOR;
 551    if (relation_flag == GLU_INTERIOR)
 552       return GLU_INTERIOR;
 553    if (point_in_polygon(inner, outer->vertices->x, outer->vertices->y))
 554       return GLU_EXTERIOR;
 555    return GLU_NO_ERROR;
 556 }
 557
 558 static GLboolean
 559 point_in_polygon(tess_contour * contour, GLdouble x, GLdouble y)
 560 {
 561    tess_vertex *v1, *v2;
 562    GLuint i, vertex_cnt;
 563    GLdouble xp1, yp1, xp2, yp2;
 564    GLboolean tst;
 565
 566    tst = GL_FALSE;
 567    v1 = contour->vertices;
 568    v2 = contour->vertices->previous;
 569    for (i = 0, vertex_cnt = contour->vertex_cnt; i < vertex_cnt; i++) {
 570       xp1 = v1->x;
 571       yp1 = v1->y;
 572       xp2 = v2->x;
 573       yp2 = v2->y;
 574       if ((((yp1 <= y) && (y < yp2)) || ((yp2 <= y) && (y < yp1))) &&
 575           (x < (xp2 - xp1) * (y - yp1) / (yp2 - yp1) + xp1))
 576          tst = (tst == GL_FALSE ? GL_TRUE : GL_FALSE);
 577       v2 = v1;
 578       v1 = v1->next;
 579    }
 580    return tst;
 581 }
 582
 583 static GLenum
 584 contours_overlap(tess_contour * contour, tess_polygon * polygon)
 585 {
 586    tess_vertex *vertex1, *vertex2;
 587    GLuint vertex1_cnt, vertex2_cnt, i, j;
 588    GLenum test;
 589
 590    vertex1 = contour->vertices;
 591    vertex2 = polygon->vertices;
 592    vertex1_cnt = contour->vertex_cnt;
 593    vertex2_cnt = polygon->vertex_cnt;
 594    for (i = 0; i < vertex1_cnt; vertex1 = vertex1->next, i++) {
 595       for (j = 0; j < vertex2_cnt; vertex2 = vertex2->next, j++)
 596          if ((test = edge_edge_intersect(vertex1, vertex1->next, vertex2,
 597                                          vertex2->next)) != GLU_NO_ERROR)
 598             return test;
 599    }
 600    return GLU_NO_ERROR;
 601 }
 602
 603 static void
 604 add_new_exterior(GLUtriangulatorObj * tobj, tess_contour * contour)
 605 {
 606    contour->type = GLU_EXTERIOR;
 607    contour->next = NULL;
 608    contour->previous = tobj->last_contour;
 609    tobj->last_contour->next = contour;
 610    tobj->last_contour = contour;
 611 }
 612
 613 static void
 614 add_new_interior(GLUtriangulatorObj * tobj,
 615                  tess_contour * outer, tess_contour * contour)
 616 {
 617    contour->type = GLU_INTERIOR;
 618    contour->next = outer->next;
 619    contour->previous = outer;
 620    if (outer->next != NULL)
 621       outer->next->previous = contour;
 622    outer->next = contour;
 623    if (tobj->last_contour == outer)
 624       tobj->last_contour = contour;
 625 }
 626
 627 static void
 628 add_interior_with_hierarchy_check(GLUtriangulatorObj * tobj,
 629                                   tess_contour * outer,
 630                                   tess_contour * contour)
 631 {
 632    tess_contour *ptr;
 633
 634    /* for all interiors of outer check if they are interior of contour */
 635    /* if so, change that interior to exterior and move it of of the */
 636    /* interior sequence */
 637    if (outer->next != NULL && outer->next->type == GLU_INTERIOR) {
 638       GLenum test;
 639
 640       for (ptr = outer->next; ptr != NULL && ptr->type == GLU_INTERIOR;
 641            ptr = ptr->next) {
 642          test = is_contour_contained_in(ptr, contour);
 643          switch (test) {
 644          case GLU_INTERIOR:
 645             /* contour is contained in one of the interiors */
 646             /* check if possibly contained in other exteriors */
 647             /* move ptr to first EXTERIOR */
 648             for (; ptr != NULL && ptr->type == GLU_INTERIOR; ptr = ptr->next);
 649             if (ptr == NULL)
 650                /* another exterior */
 651                add_new_exterior(tobj, contour);
 652             else
 653                add_exterior_with_check(tobj, ptr, contour);
 654             return;
 655          case GLU_EXTERIOR:
 656             /* one of the interiors is contained in the contour */
 657             /* change it to EXTERIOR, and shift it away from the */
 658             /* interior sequence */
 659             shift_interior_to_exterior(tobj, ptr);
 660             break;
 661          case GLU_NO_ERROR:
 662             /* disjoint */
 663             break;
 664          default:
 665             abort();
 666          }
 667       }
 668    }
 669    /* add contour to the interior sequence */
 670    add_new_interior(tobj, outer, contour);
 671 }
 672
 673 static void
 674 reverse_hierarchy_and_add_exterior(GLUtriangulatorObj * tobj,
 675                                    tess_contour * outer,
 676                                    tess_contour * contour)
 677 {
 678    tess_contour *ptr;
 679
 680    /* reverse INTERIORS to EXTERIORS */
 681    /* any INTERIORS? */
 682    if (outer->next != NULL && outer->next->type == GLU_INTERIOR)
 683       for (ptr = outer->next; ptr != NULL && ptr->type == GLU_INTERIOR;
 684            ptr = ptr->next) ptr->type = GLU_EXTERIOR;
 685    /* the outer now becomes inner */
 686    outer->type = GLU_INTERIOR;
 687    /* contour is the EXTERIOR */
 688    contour->next = outer;
 689    if (tobj->contours == outer) {
 690       /* first contour beeing reversed */
 691       contour->previous = NULL;
 692       tobj->contours = contour;
 693    }
 694    else {
 695       outer->previous->next = contour;
 696       contour->previous = outer->previous;
 697    }
 698    outer->previous = contour;
 699 }
 700
 701 static void
 702 shift_interior_to_exterior(GLUtriangulatorObj * tobj, tess_contour * contour)
 703 {
 704    contour->previous->next = contour->next;
 705    if (contour->next != NULL)
 706       contour->next->previous = contour->previous;
 707    else
 708       tobj->last_contour = contour->previous;
 709 }
 710
 711 static void
 712 add_exterior_with_check(GLUtriangulatorObj * tobj,
 713                         tess_contour * outer, tess_contour * contour)
 714 {
 715    GLenum test;
 716
 717    /* this contour might be interior to further exteriors - check */
 718    /* if not, just add as a new exterior */
 719    for (; outer != NULL && outer->type == GLU_EXTERIOR; outer = outer->next) {
 720       test = is_contour_contained_in(outer, contour);
 721       switch (test) {
 722       case GLU_INTERIOR:
 723          /* now we have to check if contour is inside interiors */
 724          /* or not */
 725          /* any interiors? */
 726          if (outer->next != NULL && outer->next->type == GLU_INTERIOR) {
 727             /* for all interior, check if inside any of them */
 728             /* if not inside any of interiors, its another */
 729             /* interior */
 730             /* or it may contain some interiors, then change */
 731             /* the contained interiors to exterior ones */
 732             add_interior_with_hierarchy_check(tobj, outer, contour);
 733          }
 734          else {
 735             /* not in interior, add as new interior contour */
 736             add_new_interior(tobj, outer, contour);
 737          }
 738          return;
 739       case GLU_NO_ERROR:
 740          /* disjoint */
 741          break;
 742       default:
 743          abort();
 744       }
 745    }
 746    /* add contour to the exterior sequence */
 747    add_new_exterior(tobj, contour);
 748 }
 749
 750 void
 751 tess_handle_holes(GLUtriangulatorObj * tobj)
 752 {
 753    tess_contour *contour, *hole;
 754    GLenum exterior_orientation;
 755
 756    /* verify hole orientation */
 757    for (contour = tobj->contours; contour != NULL;) {
 758       exterior_orientation = contour->orientation;
 759       for (contour = contour->next;
 760            contour != NULL && contour->type == GLU_INTERIOR;
 761            contour = contour->next) {
 762          if (contour->orientation == exterior_orientation) {
 763             tess_call_user_error(tobj, GLU_TESS_ERROR5);
 764             return;
 765          }
 766       }
 767    }
 768    /* now cut-out holes */
 769    for (contour = tobj->contours; contour != NULL;) {
 770       hole = contour->next;
 771       while (hole != NULL && hole->type == GLU_INTERIOR) {
 772          if (cut_out_hole(tobj, contour, hole) == GLU_ERROR)
 773             return;
 774          hole = contour->next;
 775       }
 776       contour = contour->next;
 777    }
 778 }
 779
 780 static GLenum
 781 cut_out_hole(GLUtriangulatorObj * tobj,
 782              tess_contour * contour, tess_contour * hole)
 783 {
 784    tess_contour *tmp_hole;
 785    tess_vertex *v1, *v2, *tmp_vertex;
 786    GLuint vertex1_cnt, vertex2_cnt, tmp_vertex_cnt;
 787    GLuint i, j, k;
 788    GLenum test = 0;
 789
 790    /* find an edge connecting contour and hole not intersecting any other */
 791    /* edge belonging to either the contour or any of the other holes */
 792    for (v1 = contour->vertices, vertex1_cnt = contour->vertex_cnt, i = 0;
 793         i < vertex1_cnt; i++, v1 = v1->next) {
 794       for (v2 = hole->vertices, vertex2_cnt = hole->vertex_cnt, j = 0;
 795            j < vertex2_cnt; j++, v2 = v2->next) {
 796          /* does edge (v1,v2) intersect any edge of contour */
 797          for (tmp_vertex = contour->vertices, tmp_vertex_cnt =
 798               contour->vertex_cnt, k = 0; k < tmp_vertex_cnt;
 799               tmp_vertex = tmp_vertex->next, k++) {
 800             /* skip edge tests for edges directly connected */
 801             if (v1 == tmp_vertex || v1 == tmp_vertex->next)
 802                continue;
 803             test = edge_edge_intersect(v1, v2, tmp_vertex, tmp_vertex->next);
 804             if (test != GLU_NO_ERROR)
 805                break;
 806          }
 807          if (test == GLU_NO_ERROR) {
 808             /* does edge (v1,v2) intersect any edge of hole */
 809             for (tmp_vertex = hole->vertices,
 810                  tmp_vertex_cnt = hole->vertex_cnt, k = 0;
 811                  k < tmp_vertex_cnt; tmp_vertex = tmp_vertex->next, k++) {
 812                /* skip edge tests for edges directly connected */
 813                if (v2 == tmp_vertex || v2 == tmp_vertex->next)
 814                   continue;
 815                test =
 816                   edge_edge_intersect(v1, v2, tmp_vertex, tmp_vertex->next);
 817                if (test != GLU_NO_ERROR)
 818                   break;
 819             }
 820             if (test == GLU_NO_ERROR) {
 821                /* does edge (v1,v2) intersect any other hole? */
 822                for (tmp_hole = hole->next;
 823                     tmp_hole != NULL && tmp_hole->type == GLU_INTERIOR;
 824                     tmp_hole = tmp_hole->next) {
 825                   /* does edge (v1,v2) intersect any edge of hole */
 826                   for (tmp_vertex = tmp_hole->vertices,
 827                        tmp_vertex_cnt = tmp_hole->vertex_cnt, k = 0;
 828                        k < tmp_vertex_cnt; tmp_vertex = tmp_vertex->next, k++) {
 829                      test = edge_edge_intersect(v1, v2, tmp_vertex,
 830                                                 tmp_vertex->next);
 831                      if (test != GLU_NO_ERROR)
 832                         break;
 833                   }
 834                   if (test != GLU_NO_ERROR)
 835                      break;
 836                }
 837             }
 838          }
 839          if (test == GLU_NO_ERROR) {
 840             /* edge (v1,v2) is good for eliminating the hole */
 841             if (merge_hole_with_contour(tobj, contour, hole, v1, v2)
 842                 == GLU_NO_ERROR)
 843                return GLU_NO_ERROR;
 844             else
 845                return GLU_ERROR;
 846          }
 847       }
 848    }
 849    /* other holes are blocking all possible connections of hole */
 850    /* with contour, we shift this hole as the last hole and retry */
 851    for (tmp_hole = hole;
 852         tmp_hole != NULL && tmp_hole->type == GLU_INTERIOR;
 853         tmp_hole = tmp_hole->next);
 854    contour->next = hole->next;
 855    hole->next->previous = contour;
 856    if (tmp_hole == NULL) {
 857       /* last EXTERIOR contour, shift hole as last contour */
 858       hole->next = NULL;
 859       hole->previous = tobj->last_contour;
 860       tobj->last_contour->next = hole;
 861       tobj->last_contour = hole;
 862    }
 863    else {
 864       tmp_hole->previous->next = hole;
 865       hole->previous = tmp_hole->previous;
 866       tmp_hole->previous = hole;
 867       hole->next = tmp_hole;
 868    }
 869    hole = contour->next;
 870    /* try once again - recurse */
 871    return cut_out_hole(tobj, contour, hole);
 872 }
 873
 874 static GLenum
 875 merge_hole_with_contour(GLUtriangulatorObj * tobj,
 876                         tess_contour * contour,
 877                         tess_contour * hole,
 878                         tess_vertex * v1, tess_vertex * v2)
 879 {
 880    tess_vertex *v1_new, *v2_new;
 881
 882    /* make copies of v1 and v2, place them respectively after their originals */
 883    if ((v1_new = (tess_vertex *) malloc(sizeof(tess_vertex))) == NULL) {
 884       tess_call_user_error(tobj, GLU_OUT_OF_MEMORY);
 885       return GLU_ERROR;
 886    }
 887    if ((v2_new = (tess_vertex *) malloc(sizeof(tess_vertex))) == NULL) {
 888       tess_call_user_error(tobj, GLU_OUT_OF_MEMORY);
 889       return GLU_ERROR;
 890    }
 891    v1_new->edge_flag = GL_TRUE;
 892    v1_new->data = v1->data;
 893    v1_new->location[0] = v1->location[0];
 894    v1_new->location[1] = v1->location[1];
 895    v1_new->location[2] = v1->location[2];
 896    v1_new->x = v1->x;
 897    v1_new->y = v1->y;
 898    v1_new->shadow_vertex = v1;
 899    v1->shadow_vertex = v1_new;
 900    v1_new->next = v1->next;
 901    v1_new->previous = v1;
 902    v1->next->previous = v1_new;
 903    v1->next = v1_new;
 904    v2_new->edge_flag = GL_TRUE;
 905    v2_new->data = v2->data;
 906    v2_new->location[0] = v2->location[0];
 907    v2_new->location[1] = v2->location[1];
 908    v2_new->location[2] = v2->location[2];
 909    v2_new->x = v2->x;
 910    v2_new->y = v2->y;
 911    v2_new->shadow_vertex = v2;
 912    v2->shadow_vertex = v2_new;
 913    v2_new->next = v2->next;
 914    v2_new->previous = v2;
 915    v2->next->previous = v2_new;
 916    v2->next = v2_new;
 917    /* link together the two lists */
 918    v1->next = v2_new;
 919    v2_new->previous = v1;
 920    v2->next = v1_new;
 921    v1_new->previous = v2;
 922    /* update the vertex count of the contour */
 923    contour->vertex_cnt += hole->vertex_cnt + 2;
 924    /* remove the INTERIOR contour */
 925    contour->next = hole->next;
 926    if (hole->next != NULL)
 927       hole->next->previous = contour;
 928    free(hole);
 929    /* update tobj structure */
 930    --(tobj->contour_cnt);
 931    if (contour->last_vertex == v1)
 932       contour->last_vertex = v1_new;
 933    /* mark two vertices with edge_flag */
 934    v2->edge_flag = GL_FALSE;
 935    v1->edge_flag = GL_FALSE;
 936    return GLU_NO_ERROR;
 937 }