← Back to branch summary

~ubuntu-branches/ubuntu/quantal/mesa/quantal

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Sebastien Bacher
  • Date: 2007-02-21 12:44:07 UTC
  • mfrom: (1.2.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 22.
  • Revision ID: james.westby@ubuntu.com-20070221124407-rgcacs32mycrtadl
Import upstream version 6.5.2

Show diffs side-by-side

added added

removed removed

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