Subversion Repositories shark

Rev

Rev 55 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
55 pj 1
/* $Id: polytest.c,v 1.1 2003-02-28 11:42:07 pj 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
}