src/glu/mini/polytest.c

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