← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/mesa/jaunty

« back to all changes in this revision

Viewing changes to src/glu/mesa/polytest.c

  • Committer: Bazaar Package Importer
  • Author(s): Timo Aaltonen
  • Date: 2009-01-31 12:38:44 UTC
  • mfrom: (1.2.15 upstream) (3.1.4 experimental)
  • Revision ID: james.westby@ubuntu.com-20090131123844-ncib2eu1l01b1et0
Tags: 7.3-1ubuntu1
* Merge with Debian experimental.
* Drop 102_remove_flip.diff, included in 7.3..

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
 
}