1 /* $Id: polytest.c,v 1.2 2003/08/22 20:11:43 brianp Exp $ */
4 * Mesa 3-D graphics library
6 * Copyright (C) 1995-2000 Brian Paul
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.
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.
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.
25 * This file is part of the polygon tesselation code contributed by
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
*,
53 static void add_interior_with_hierarchy_check(GLUtriangulatorObj
*,
54 tess_contour
*, tess_contour
*);
55 static void reverse_hierarchy_and_add_exterior(GLUtriangulatorObj
*,
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
*,
62 static GLenum
cut_out_hole(GLUtriangulatorObj
*, tess_contour
*,
64 static GLenum
merge_hole_with_contour(GLUtriangulatorObj
*,
65 tess_contour
*, tess_contour
*,
66 tess_vertex
*, tess_vertex
*);
69 find_normal(GLUtriangulatorObj
* tobj
)
71 tess_polygon
*polygon
= tobj
->current_polygon
;
72 tess_vertex
*va
, *vb
, *vc
;
74 GLdouble A0
, A1
, A2
, B0
, B1
, B2
;
76 va
= polygon
->vertices
;
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
) {
93 -A
* va
->location
[0] - B
* va
->location
[1] - C
* va
->location
[2];
97 tess_call_user_error(tobj
, GLU_TESS_ERROR7
);
102 tess_test_polygon(GLUtriangulatorObj
* tobj
)
104 tess_polygon
*polygon
= tobj
->current_polygon
;
106 /* any vertices defined? */
107 if (polygon
->vertex_cnt
< 3) {
108 free_current_polygon(polygon
);
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
)
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
;
129 tobj
->projection
= OXY
;
130 else if (fabs(polygon
->B
) > fabs(polygon
->C
))
131 tobj
->projection
= OXZ
;
133 tobj
->projection
= OXY
;
137 tess_vertex
*vertex
= polygon
->vertices
;
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
) {
151 tess_call_user_error(tobj
, GLU_TESS_ERROR9
);
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
);
162 prepare_projection_info(tobj
);
163 if (verify_edge_vertex_intersections(tobj
) == GLU_ERROR
)
165 if (test_for_overlapping_contours(tobj
) == GLU_ERROR
)
167 if (store_polygon_as_contour(tobj
) == GLU_ERROR
)
172 test_for_overlapping_contours(GLUtriangulatorObj
* tobj
)
174 tess_contour
*contour
;
175 tess_polygon
*polygon
;
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
);
187 store_polygon_as_contour(GLUtriangulatorObj
* tobj
)
189 tess_polygon
*polygon
= tobj
->current_polygon
;
190 tess_contour
*contour
= tobj
->contours
;
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
);
199 tobj
->contours
= tobj
->last_contour
= contour
;
200 contour
->next
= contour
->previous
= NULL
;
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
);
208 contour
->previous
= tobj
->last_contour
;
209 tobj
->last_contour
->next
= contour
;
210 tobj
->last_contour
= contour
;
211 contour
->next
= NULL
;
213 /* mark all vertices in new contour as not special */
214 /* and all are boundary edges */
217 GLuint vertex_cnt
, i
;
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
;
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
);
238 free_current_polygon(tess_polygon
* polygon
)
240 tess_vertex
*vertex
, *vertex_tmp
;
243 /* free current_polygon structures */
244 for (vertex
= polygon
->vertices
, i
= 0; i
< polygon
->vertex_cnt
; i
++) {
245 vertex_tmp
= vertex
->next
;
249 polygon
->vertices
= polygon
->last_vertex
= NULL
;
250 polygon
->vertex_cnt
= 0;
254 prepare_projection_info(GLUtriangulatorObj
* tobj
)
256 tess_polygon
*polygon
= tobj
->current_polygon
;
257 tess_vertex
*vertex
, *last_vertex_ptr
;
260 last_vertex_ptr
= polygon
->last_vertex
;
261 switch (tobj
->projection
) {
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];
268 last_vertex_ptr
->x
= last_vertex_ptr
->location
[0];
269 last_vertex_ptr
->y
= last_vertex_ptr
->location
[1];
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];
277 last_vertex_ptr
->x
= last_vertex_ptr
->location
[0];
278 last_vertex_ptr
->y
= last_vertex_ptr
->location
[2];
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];
286 last_vertex_ptr
->x
= last_vertex_ptr
->location
[1];
287 last_vertex_ptr
->y
= last_vertex_ptr
->location
[2];
290 area
= twice_the_polygon_area(polygon
->vertices
, polygon
->last_vertex
);
292 polygon
->orientation
= GLU_CCW
;
293 polygon
->area
= area
;
296 polygon
->orientation
= GLU_CW
;
297 polygon
->area
= -area
;
302 twice_the_polygon_area(tess_vertex
* vertex
, tess_vertex
* last_vertex
)
310 vertex
= vertex
->next
;
311 for (; vertex
!= last_vertex
; vertex
= vertex
->next
) {
314 (vertex
->x
- x
) * (next
->y
- y
) - (vertex
->y
- y
) * (next
->x
- x
);
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 */
323 edge_edge_intersect(tess_vertex
* a
,
324 tess_vertex
* b
, tess_vertex
* c
, tess_vertex
* d
)
326 GLdouble denom
, r
, s
;
327 GLdouble xba
, ydc
, yba
, xdc
, yac
, xac
;
335 denom
= xba
* ydc
- yba
* xdc
;
336 r
= yac
* xdc
- xac
* ydc
;
338 if (fabs(denom
) < EPSILON
) {
339 if (fabs(r
) < EPSILON
) {
341 if (fabs(xba
) < EPSILON
) {
342 /* compare the Y coordinate */
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
;
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
;
362 /* compare the X coordinate */
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
;
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
;
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
;
392 /* test for crossing */
393 if (r
> -EPSILON
&& r
< 1.0 + EPSILON
&& s
> -EPSILON
&& s
< 1.0 + EPSILON
) {
394 return GLU_TESS_ERROR8
;
400 verify_edge_vertex_intersections(GLUtriangulatorObj
* tobj
)
402 tess_polygon
*polygon
= tobj
->current_polygon
;
403 tess_vertex
*vertex1
, *last_vertex
, *vertex2
;
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
,
412 if (test
!= GLU_NO_ERROR
) {
413 tess_call_user_error(tobj
, test
);
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
,
423 if (test
!= GLU_NO_ERROR
) {
424 tess_call_user_error(tobj
, test
);
436 area_compare(const void *a
, const void *b
)
438 GLdouble area1
, area2
;
440 area1
= (*((tess_contour
**) a
))->area
;
441 area2
= (*((tess_contour
**) b
))->area
;
450 tess_find_contour_hierarchies(GLUtriangulatorObj
* tobj
)
452 tess_contour
**contours
; /* dinamic array of pointers */
453 tess_contour
*tmp_contour_ptr
= tobj
->contours
;
456 GLboolean hierarchy_changed
;
459 if (tobj
->contour_cnt
< 2) {
460 tobj
->contours
->type
= GLU_EXTERIOR
;
463 if ((contours
= (tess_contour
**)
464 malloc(sizeof(tess_contour
*) * (tobj
->contour_cnt
))) == NULL
) {
465 tess_call_user_error(tobj
, GLU_OUT_OF_MEMORY
);
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
*),
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
;
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
]);
493 /* now we have to check if contour is inside 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 */
501 /* or it may contain some interiors, then change */
502 /* the contained interiors to exterior ones */
503 add_interior_with_hierarchy_check(tobj
,
508 /* not in interior, add as new interior contour */
509 add_new_interior(tobj
, tmp_contour_ptr
, contours
[i
]);
511 hierarchy_changed
= GL_TRUE
;
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
,
519 hierarchy_changed
= GL_TRUE
;
527 if (hierarchy_changed
)
528 break; /* break from for loop */
530 if (hierarchy_changed
== GL_FALSE
) {
531 /* disjoint with all contours, add to contour list */
532 add_new_exterior(tobj
, contours
[i
]);
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 */
542 is_contour_contained_in(tess_contour
* outer
, tess_contour
* inner
)
544 GLenum relation_flag
;
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
;
551 relation_flag
= GLU_EXTERIOR
;
552 if (relation_flag
== GLU_INTERIOR
)
554 if (point_in_polygon(inner
, outer
->vertices
->x
, outer
->vertices
->y
))
560 point_in_polygon(tess_contour
* contour
, GLdouble x
, GLdouble y
)
562 tess_vertex
*v1
, *v2
;
563 GLuint i
, vertex_cnt
;
564 GLdouble xp1
, yp1
, xp2
, yp2
;
568 v1
= contour
->vertices
;
569 v2
= contour
->vertices
->previous
;
570 for (i
= 0, vertex_cnt
= contour
->vertex_cnt
; i
< vertex_cnt
; i
++) {
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
);
585 contours_overlap(tess_contour
* contour
, tess_polygon
* polygon
)
587 tess_vertex
*vertex1
, *vertex2
;
588 GLuint vertex1_cnt
, vertex2_cnt
, i
, j
;
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
)
605 add_new_exterior(GLUtriangulatorObj
* tobj
, tess_contour
* contour
)
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
;
615 add_new_interior(GLUtriangulatorObj
* tobj
,
616 tess_contour
* outer
, tess_contour
* contour
)
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
;
629 add_interior_with_hierarchy_check(GLUtriangulatorObj
* tobj
,
630 tess_contour
* outer
,
631 tess_contour
* contour
)
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
) {
641 for (ptr
= outer
->next
; ptr
!= NULL
&& ptr
->type
== GLU_INTERIOR
;
643 test
= is_contour_contained_in(ptr
, contour
);
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
);
651 /* another exterior */
652 add_new_exterior(tobj
, contour
);
654 add_exterior_with_check(tobj
, ptr
, contour
);
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
);
670 /* add contour to the interior sequence */
671 add_new_interior(tobj
, outer
, contour
);
675 reverse_hierarchy_and_add_exterior(GLUtriangulatorObj
* tobj
,
676 tess_contour
* outer
,
677 tess_contour
* contour
)
681 /* reverse INTERIORS to EXTERIORS */
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
;
696 outer
->previous
->next
= contour
;
697 contour
->previous
= outer
->previous
;
699 outer
->previous
= contour
;
703 shift_interior_to_exterior(GLUtriangulatorObj
* tobj
, tess_contour
* contour
)
705 contour
->previous
->next
= contour
->next
;
706 if (contour
->next
!= NULL
)
707 contour
->next
->previous
= contour
->previous
;
709 tobj
->last_contour
= contour
->previous
;
713 add_exterior_with_check(GLUtriangulatorObj
* tobj
,
714 tess_contour
* outer
, tess_contour
* contour
)
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
);
724 /* now we have to check if contour is inside 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 */
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
);
736 /* not in interior, add as new interior contour */
737 add_new_interior(tobj
, outer
, contour
);
747 /* add contour to the exterior sequence */
748 add_new_exterior(tobj
, contour
);
752 tess_handle_holes(GLUtriangulatorObj
* tobj
)
754 tess_contour
*contour
, *hole
;
755 GLenum exterior_orientation
;
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
);
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
)
775 hole
= contour
->next
;
777 contour
= contour
->next
;
782 cut_out_hole(GLUtriangulatorObj
* tobj
,
783 tess_contour
* contour
, tess_contour
* hole
)
785 tess_contour
*tmp_hole
;
786 tess_vertex
*v1
, *v2
, *tmp_vertex
;
787 GLuint vertex1_cnt
, vertex2_cnt
, tmp_vertex_cnt
;
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
)
804 test
= edge_edge_intersect(v1
, v2
, tmp_vertex
, tmp_vertex
->next
);
805 if (test
!= GLU_NO_ERROR
)
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
)
817 edge_edge_intersect(v1
, v2
, tmp_vertex
, tmp_vertex
->next
);
818 if (test
!= GLU_NO_ERROR
)
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
,
832 if (test
!= GLU_NO_ERROR
)
835 if (test
!= GLU_NO_ERROR
)
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
)
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 */
860 hole
->previous
= tobj
->last_contour
;
861 tobj
->last_contour
->next
= hole
;
862 tobj
->last_contour
= hole
;
865 tmp_hole
->previous
->next
= hole
;
866 hole
->previous
= tmp_hole
->previous
;
867 tmp_hole
->previous
= hole
;
868 hole
->next
= tmp_hole
;
870 hole
= contour
->next
;
871 /* try once again - recurse */
872 return cut_out_hole(tobj
, contour
, hole
);
876 merge_hole_with_contour(GLUtriangulatorObj
* tobj
,
877 tess_contour
* contour
,
879 tess_vertex
* v1
, tess_vertex
* v2
)
881 tess_vertex
*v1_new
, *v2_new
;
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
);
888 if ((v2_new
= (tess_vertex
*) malloc(sizeof(tess_vertex
))) == NULL
) {
889 tess_call_user_error(tobj
, GLU_OUT_OF_MEMORY
);
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];
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
;
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];
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
;
918 /* link together the two lists */
920 v2_new
->previous
= v1
;
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
;
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
;