/* $Id: polytest.c,v 1.1 2003-02-28 11:42:07 pj Exp $ */
/*
* Mesa 3-D graphics library
* Version: 3.3
* Copyright (C) 1995-2000 Brian Paul
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the Free
* Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
/*
* This file is part of the polygon tesselation code contributed by
* Bogdan Sikorski
*/
#ifdef PC_HEADER
#include "all.h"
#else
#include <math.h>
#include <stdlib.h>
#include "gluP.h"
#include "tess.h"
#endif
static GLenum store_polygon_as_contour
(GLUtriangulatorObj
*);
static void free_current_polygon
(tess_polygon
*);
static void prepare_projection_info
(GLUtriangulatorObj
*);
static GLdouble twice_the_polygon_area
(tess_vertex
*, tess_vertex
*);
static GLenum verify_edge_vertex_intersections
(GLUtriangulatorObj
*);
void tess_find_contour_hierarchies
(GLUtriangulatorObj
*);
static GLenum test_for_overlapping_contours
(GLUtriangulatorObj
*);
static GLenum contours_overlap
(tess_contour
*, tess_polygon
*);
static GLenum is_contour_contained_in
(tess_contour
*, tess_contour
*);
static void add_new_exterior
(GLUtriangulatorObj
*, tess_contour
*);
static void add_new_interior
(GLUtriangulatorObj
*, tess_contour
*,
tess_contour
*);
static void add_interior_with_hierarchy_check
(GLUtriangulatorObj
*,
tess_contour
*, tess_contour
*);
static void reverse_hierarchy_and_add_exterior
(GLUtriangulatorObj
*,
tess_contour
*,
tess_contour
*);
static GLboolean point_in_polygon
(tess_contour
*, GLdouble
, GLdouble
);
static void shift_interior_to_exterior
(GLUtriangulatorObj
*, tess_contour
*);
static void add_exterior_with_check
(GLUtriangulatorObj
*, tess_contour
*,
tess_contour
*);
static GLenum cut_out_hole
(GLUtriangulatorObj
*, tess_contour
*,
tess_contour
*);
static GLenum merge_hole_with_contour
(GLUtriangulatorObj
*,
tess_contour
*, tess_contour
*,
tess_vertex
*, tess_vertex
*);
static GLenum
find_normal
(GLUtriangulatorObj
* tobj
)
{
tess_polygon
*polygon
= tobj
->current_polygon
;
tess_vertex
*va
, *vb
, *vc
;
GLdouble A
, B
, C
;
GLdouble A0
, A1
, A2
, B0
, B1
, B2
;
va
= polygon
->vertices
;
vb
= va
->next
;
A0
= vb
->location
[0] - va
->location
[0];
A1
= vb
->location
[1] - va
->location
[1];
A2
= vb
->location
[2] - va
->location
[2];
for (vc
= vb
->next
; vc
!= va
; vc
= vc
->next
) {
B0
= vc
->location
[0] - va
->location
[0];
B1
= vc
->location
[1] - va
->location
[1];
B2
= vc
->location
[2] - va
->location
[2];
A
= A1
* B2
- A2
* B1
;
B
= A2
* B0
- A0
* B2
;
C
= A0
* B1
- A1
* B0
;
if (fabs(A
) > EPSILON
|| fabs(B
) > EPSILON
|| fabs(C
) > EPSILON
) {
polygon
->A
= A
;
polygon
->B
= B
;
polygon
->C
= C
;
polygon
->D
=
-A
* va
->location
[0] - B
* va
->location
[1] - C
* va
->location
[2];
return GLU_NO_ERROR
;
}
}
tess_call_user_error
(tobj
, GLU_TESS_ERROR7
);
return GLU_ERROR
;
}
void
tess_test_polygon
(GLUtriangulatorObj
* tobj
)
{
tess_polygon
*polygon
= tobj
->current_polygon
;
/* any vertices defined? */
if (polygon
->vertex_cnt
< 3) {
free_current_polygon
(polygon
);
return;
}
/* wrap pointers */
polygon
->last_vertex
->next
= polygon
->vertices
;
polygon
->vertices
->previous
= polygon
->last_vertex
;
/* determine the normal */
if (find_normal
(tobj
) == GLU_ERROR
)
return;
/* compare the normals of previously defined contours and this one */
/* first contour define ? */
if (tobj
->contours
== NULL
) {
tobj
->A
= polygon
->A
;
tobj
->B
= polygon
->B
;
tobj
->C
= polygon
->C
;
tobj
->D
= polygon
->D
;
/* determine the best projection to use */
if (fabs(polygon
->A
) > fabs(polygon
->B
))
if (fabs(polygon
->A
) > fabs(polygon
->C
))
tobj
->projection
= OYZ
;
else
tobj
->projection
= OXY
;
else if (fabs(polygon
->B
) > fabs(polygon
->C
))
tobj
->projection
= OXZ
;
else
tobj
->projection
= OXY
;
}
else {
GLdouble a
[3], b
[3];
tess_vertex
*vertex
= polygon
->vertices
;
a
[0] = tobj
->A
;
a
[1] = tobj
->B
;
a
[2] = tobj
->C
;
b
[0] = polygon
->A
;
b
[1] = polygon
->B
;
b
[2] = polygon
->C
;
/* compare the normals */
if (fabs(a
[1] * b
[2] - a
[2] * b
[1]) > EPSILON
||
fabs(a
[2] * b
[0] - a
[0] * b
[2]) > EPSILON
||
fabs(a
[0] * b
[1] - a
[1] * b
[0]) > EPSILON
) {
/* not coplanar */
tess_call_user_error
(tobj
, GLU_TESS_ERROR9
);
return;
}
/* the normals are parallel - test for plane equation */
if (fabs(a
[0] * vertex
->location
[0] + a
[1] * vertex
->location
[1] +
a
[2] * vertex
->location
[2] + tobj
->D
) > EPSILON
) {
/* not the same plane */
tess_call_user_error
(tobj
, GLU_TESS_ERROR9
);
return;
}
}
prepare_projection_info
(tobj
);
if (verify_edge_vertex_intersections
(tobj
) == GLU_ERROR
)
return;
if (test_for_overlapping_contours
(tobj
) == GLU_ERROR
)
return;
if (store_polygon_as_contour
(tobj
) == GLU_ERROR
)
return;
}
static GLenum
test_for_overlapping_contours
(GLUtriangulatorObj
* tobj
)
{
tess_contour
*contour
;
tess_polygon
*polygon
;
polygon
= tobj
->current_polygon
;
for (contour
= tobj
->contours
; contour
!= NULL
; contour
= contour
->next
)
if (contours_overlap
(contour
, polygon
) != GLU_NO_ERROR
) {
tess_call_user_error
(tobj
, GLU_TESS_ERROR5
);
return GLU_ERROR
;
}
return GLU_NO_ERROR
;
}
static GLenum
store_polygon_as_contour
(GLUtriangulatorObj
* tobj
)
{
tess_polygon
*polygon
= tobj
->current_polygon
;
tess_contour
*contour
= tobj
->contours
;
/* the first contour defined */
if (contour
== NULL
) {
if ((contour
= (tess_contour
*) malloc(sizeof(tess_contour
))) == NULL
) {
tess_call_user_error
(tobj
, GLU_OUT_OF_MEMORY
);
free_current_polygon
(polygon
);
return GLU_ERROR
;
}
tobj
->contours
= tobj
->last_contour
= contour
;
contour
->next
= contour
->previous
= NULL
;
}
else {
if ((contour
= (tess_contour
*) malloc(sizeof(tess_contour
))) == NULL
) {
tess_call_user_error
(tobj
, GLU_OUT_OF_MEMORY
);
free_current_polygon
(polygon
);
return GLU_ERROR
;
}
contour
->previous
= tobj
->last_contour
;
tobj
->last_contour
->next
= contour
;
tobj
->last_contour
= contour
;
contour
->next
= NULL
;
}
/* mark all vertices in new contour as not special */
/* and all are boundary edges */
{
tess_vertex
*vertex
;
GLuint vertex_cnt
, i
;
for (vertex
= polygon
->vertices
, i
= 0, vertex_cnt
=
polygon
->vertex_cnt
; i
< vertex_cnt
; vertex
= vertex
->next
, i
++) {
vertex
->shadow_vertex
= NULL
;
vertex
->edge_flag
= GL_TRUE
;
}
}
contour
->vertex_cnt
= polygon
->vertex_cnt
;
contour
->area
= polygon
->area
;
contour
->orientation
= polygon
->orientation
;
contour
->type
= GLU_UNKNOWN
;
contour
->vertices
= polygon
->vertices
;
contour
->last_vertex
= polygon
->last_vertex
;
polygon
->vertices
= polygon
->last_vertex
= NULL
;
polygon
->vertex_cnt
= 0;
++(tobj
->contour_cnt
);
return GLU_NO_ERROR
;
}
static void
free_current_polygon
(tess_polygon
* polygon
)
{
tess_vertex
*vertex
, *vertex_tmp
;
GLuint i
;
/* free current_polygon structures */
for (vertex
= polygon
->vertices
, i
= 0; i
< polygon
->vertex_cnt
; i
++) {
vertex_tmp
= vertex
->next
;
free(vertex
);
vertex
= vertex_tmp
;
}
polygon
->vertices
= polygon
->last_vertex
= NULL
;
polygon
->vertex_cnt
= 0;
}
static void
prepare_projection_info
(GLUtriangulatorObj
* tobj
)
{
tess_polygon
*polygon
= tobj
->current_polygon
;
tess_vertex
*vertex
, *last_vertex_ptr
;
GLdouble area
;
last_vertex_ptr
= polygon
->last_vertex
;
switch (tobj
->projection
) {
case OXY
:
for (vertex
= polygon
->vertices
; vertex
!= last_vertex_ptr
;
vertex
= vertex
->next
) {
vertex
->x
= vertex
->location
[0];
vertex
->y
= vertex
->location
[1];
}
last_vertex_ptr
->x
= last_vertex_ptr
->location
[0];
last_vertex_ptr
->y
= last_vertex_ptr
->location
[1];
break;
case OXZ
:
for (vertex
= polygon
->vertices
; vertex
!= last_vertex_ptr
;
vertex
= vertex
->next
) {
vertex
->x
= vertex
->location
[0];
vertex
->y
= vertex
->location
[2];
}
last_vertex_ptr
->x
= last_vertex_ptr
->location
[0];
last_vertex_ptr
->y
= last_vertex_ptr
->location
[2];
break;
case OYZ
:
for (vertex
= polygon
->vertices
; vertex
!= last_vertex_ptr
;
vertex
= vertex
->next
) {
vertex
->x
= vertex
->location
[1];
vertex
->y
= vertex
->location
[2];
}
last_vertex_ptr
->x
= last_vertex_ptr
->location
[1];
last_vertex_ptr
->y
= last_vertex_ptr
->location
[2];
break;
}
area
= twice_the_polygon_area
(polygon
->vertices
, polygon
->last_vertex
);
if (area
>= 0.0) {
polygon
->orientation
= GLU_CCW
;
polygon
->area
= area
;
}
else {
polygon
->orientation
= GLU_CW
;
polygon
->area
= -area
;
}
}
static GLdouble
twice_the_polygon_area
(tess_vertex
* vertex
, tess_vertex
* last_vertex
)
{
tess_vertex
*next
;
GLdouble area
, x
, y
;
area
= 0.0;
x
= vertex
->x
;
y
= vertex
->y
;
vertex
= vertex
->next
;
for (; vertex
!= last_vertex
; vertex
= vertex
->next
) {
next
= vertex
->next
;
area
+=
(vertex
->x
- x
) * (next
->y
- y
) - (vertex
->y
- y
) * (next
->x
- x
);
}
return area
;
}
/* test if edges ab and cd intersect */
/* if not return GLU_NO_ERROR, else if cross return GLU_TESS_ERROR8, */
/* else if adjacent return GLU_TESS_ERROR4 */
static GLenum
edge_edge_intersect
(tess_vertex
* a
,
tess_vertex
* b
, tess_vertex
* c
, tess_vertex
* d
)
{
GLdouble denom
, r
, s
;
GLdouble xba
, ydc
, yba
, xdc
, yac
, xac
;
xba
= b
->x
- a
->x
;
yba
= b
->y
- a
->y
;
xdc
= d
->x
- c
->x
;
ydc
= d
->y
- c
->y
;
xac
= a
->x
- c
->x
;
yac
= a
->y
- c
->y
;
denom
= xba
* ydc
- yba
* xdc
;
r
= yac
* xdc
- xac
* ydc
;
/* parallel? */
if (fabs(denom
) < EPSILON
) {
if (fabs(r
) < EPSILON
) {
/* colinear */
if (fabs(xba
) < EPSILON
) {
/* compare the Y coordinate */
if (yba
> 0.0) {
if (
(fabs(a
->y
- c
->y
) < EPSILON
&& fabs(c
->y
- b
->y
) < EPSILON
)
|| (fabs(a
->y
- d
->y
) < EPSILON
&& fabs(d
->y
- b
->y
) <
EPSILON
)) return GLU_TESS_ERROR4
;
}
else {
if (
(fabs(b
->y
- c
->y
) < EPSILON
&& fabs(c
->y
- a
->y
) < EPSILON
)
|| (fabs(b
->y
- d
->y
) < EPSILON
&& fabs(d
->y
- a
->y
) <
EPSILON
)) return GLU_TESS_ERROR4
;
}
}
else {
/* compare the X coordinate */
if (xba
> 0.0) {
if (
(fabs(a
->x
- c
->x
) < EPSILON
&& fabs(c
->x
- b
->x
) < EPSILON
)
|| (fabs(a
->x
- d
->x
) < EPSILON
&& fabs(d
->x
- b
->x
) <
EPSILON
)) return GLU_TESS_ERROR4
;
}
else {
if (
(fabs(b
->x
- c
->x
) < EPSILON
&& fabs(c
->x
- a
->x
) < EPSILON
)
|| (fabs(b
->x
- d
->x
) < EPSILON
&& fabs(d
->x
- a
->x
) <
EPSILON
)) return GLU_TESS_ERROR4
;
}
}
}
return GLU_NO_ERROR
;
}
r
/= denom
;
s
= (yac
* xba
- xac
* yba
) / denom
;
/* test if one vertex lies on other edge */
if (((fabs(r
) < EPSILON
|| (r
< 1.0 + EPSILON
&& r
> 1.0 - EPSILON
)) &&
s
> -EPSILON
&& s
< 1.0 + EPSILON
) ||
((fabs(s
) < EPSILON
|| (s
< 1.0 + EPSILON
&& s
> 1.0 - EPSILON
)) &&
r
> -EPSILON
&& r
< 1.0 + EPSILON
)) {
return GLU_TESS_ERROR4
;
}
/* test for crossing */
if (r
> -EPSILON
&& r
< 1.0 + EPSILON
&& s
> -EPSILON
&& s
< 1.0 + EPSILON
) {
return GLU_TESS_ERROR8
;
}
return GLU_NO_ERROR
;
}
static GLenum
verify_edge_vertex_intersections
(GLUtriangulatorObj
* tobj
)
{
tess_polygon
*polygon
= tobj
->current_polygon
;
tess_vertex
*vertex1
, *last_vertex
, *vertex2
;
GLenum test
;
last_vertex
= polygon
->last_vertex
;
vertex1
= last_vertex
;
for (vertex2
= vertex1
->next
->next
;
vertex2
->next
!= last_vertex
; vertex2
= vertex2
->next
) {
test
= edge_edge_intersect
(vertex1
, vertex1
->next
, vertex2
,
vertex2
->next
);
if (test
!= GLU_NO_ERROR
) {
tess_call_user_error
(tobj
, test
);
return GLU_ERROR
;
}
}
for (vertex1
= polygon
->vertices
;
vertex1
->next
->next
!= last_vertex
; vertex1
= vertex1
->next
) {
for (vertex2
= vertex1
->next
->next
;
vertex2
!= last_vertex
; vertex2
= vertex2
->next
) {
test
= edge_edge_intersect
(vertex1
, vertex1
->next
, vertex2
,
vertex2
->next
);
if (test
!= GLU_NO_ERROR
) {
tess_call_user_error
(tobj
, test
);
return GLU_ERROR
;
}
}
}
return GLU_NO_ERROR
;
}
static int
#ifdef WIN32
__cdecl
#endif
area_compare
(const void *a
, const void *b
)
{
GLdouble area1
, area2
;
area1
= (*((tess_contour
**) a
))->area
;
area2
= (*((tess_contour
**) b
))->area
;
if (area1
< area2
)
return 1;
if (area1
> area2
)
return -1;
return 0;
}
void
tess_find_contour_hierarchies
(GLUtriangulatorObj
* tobj
)
{
tess_contour
**contours
; /* dinamic array of pointers */
tess_contour
*tmp_contour_ptr
= tobj
->contours
;
GLuint cnt
, i
;
GLenum result
;
GLboolean hierarchy_changed
;
/* any contours? */
if (tobj
->contour_cnt
< 2) {
tobj
->contours
->type
= GLU_EXTERIOR
;
return;
}
if ((contours
= (tess_contour
**)
malloc(sizeof(tess_contour
*) * (tobj
->contour_cnt
))) == NULL
) {
tess_call_user_error
(tobj
, GLU_OUT_OF_MEMORY
);
return;
}
for (tmp_contour_ptr
= tobj
->contours
, cnt
= 0;
tmp_contour_ptr
!= NULL
; tmp_contour_ptr
= tmp_contour_ptr
->next
)
contours
[cnt
++] = tmp_contour_ptr
;
/* now sort the contours in decreasing area size order */
qsort((void *) contours
, (size_t) cnt
, (size_t) sizeof(tess_contour
*),
area_compare
);
/* we leave just the first contour - remove others from list */
tobj
->contours
= contours
[0];
tobj
->contours
->next
= tobj
->contours
->previous
= NULL
;
tobj
->last_contour
= tobj
->contours
;
tobj
->contour_cnt
= 1;
/* first contour is the one with greatest area */
/* must be EXTERIOR */
tobj
->contours
->type
= GLU_EXTERIOR
;
tmp_contour_ptr
= tobj
->contours
;
/* now we play! */
for (i
= 1; i
< cnt
; i
++) {
hierarchy_changed
= GL_FALSE
;
for (tmp_contour_ptr
= tobj
->contours
;
tmp_contour_ptr
!= NULL
; tmp_contour_ptr
= tmp_contour_ptr
->next
) {
if (tmp_contour_ptr
->type
== GLU_EXTERIOR
) {
/* check if contour completely contained in EXTERIOR */
result
= is_contour_contained_in
(tmp_contour_ptr
, contours
[i
]);
switch (result
) {
case GLU_INTERIOR
:
/* now we have to check if contour is inside interiors */
/* or not */
/* any interiors? */
if (tmp_contour_ptr
->next
!= NULL
&&
tmp_contour_ptr
->next
->type
== GLU_INTERIOR
) {
/* for all interior, check if inside any of them */
/* if not inside any of interiors, its another */
/* interior */
/* or it may contain some interiors, then change */
/* the contained interiors to exterior ones */
add_interior_with_hierarchy_check
(tobj
,
tmp_contour_ptr
,
contours
[i
]);
}
else {
/* not in interior, add as new interior contour */
add_new_interior
(tobj
, tmp_contour_ptr
, contours
[i
]);
}
hierarchy_changed
= GL_TRUE
;
break;
case GLU_EXTERIOR
:
/* ooops, the marked as EXTERIOR (contours[i]) is */
/* actually an interior of tmp_contour_ptr */
/* reverse the local hierarchy */
reverse_hierarchy_and_add_exterior
(tobj
, tmp_contour_ptr
,
contours
[i
]);
hierarchy_changed
= GL_TRUE
;
break;
case GLU_NO_ERROR
:
break;
default:
abort();
}
}
if (hierarchy_changed
)
break; /* break from for loop */
}
if (hierarchy_changed
== GL_FALSE
) {
/* disjoint with all contours, add to contour list */
add_new_exterior
(tobj
, contours
[i
]);
}
}
free(contours
);
}
/* returns GLU_INTERIOR if inner is completey enclosed within outer */
/* returns GLU_EXTERIOR if outer is completely enclosed within inner */
/* returns GLU_NO_ERROR if contours are disjoint */
static GLenum
is_contour_contained_in
(tess_contour
* outer
, tess_contour
* inner
)
{
GLenum relation_flag
;
/* set relation_flag to relation of containment of first inner vertex */
/* regarding outer contour */
if (point_in_polygon
(outer
, inner
->vertices
->x
, inner
->vertices
->y
))
relation_flag
= GLU_INTERIOR
;
else
relation_flag
= GLU_EXTERIOR
;
if (relation_flag
== GLU_INTERIOR
)
return GLU_INTERIOR
;
if (point_in_polygon
(inner
, outer
->vertices
->x
, outer
->vertices
->y
))
return GLU_EXTERIOR
;
return GLU_NO_ERROR
;
}
static GLboolean
point_in_polygon
(tess_contour
* contour
, GLdouble x
, GLdouble y
)
{
tess_vertex
*v1
, *v2
;
GLuint i
, vertex_cnt
;
GLdouble xp1
, yp1
, xp2
, yp2
;
GLboolean tst
;
tst
= GL_FALSE
;
v1
= contour
->vertices
;
v2
= contour
->vertices
->previous
;
for (i
= 0, vertex_cnt
= contour
->vertex_cnt
; i
< vertex_cnt
; i
++) {
xp1
= v1
->x
;
yp1
= v1
->y
;
xp2
= v2
->x
;
yp2
= v2
->y
;
if ((((yp1
<= y
) && (y
< yp2
)) || ((yp2
<= y
) && (y
< yp1
))) &&
(x
< (xp2
- xp1
) * (y
- yp1
) / (yp2
- yp1
) + xp1
))
tst
= (tst
== GL_FALSE
? GL_TRUE
: GL_FALSE
);
v2
= v1
;
v1
= v1
->next
;
}
return tst
;
}
static GLenum
contours_overlap
(tess_contour
* contour
, tess_polygon
* polygon
)
{
tess_vertex
*vertex1
, *vertex2
;
GLuint vertex1_cnt
, vertex2_cnt
, i
, j
;
GLenum test
;
vertex1
= contour
->vertices
;
vertex2
= polygon
->vertices
;
vertex1_cnt
= contour
->vertex_cnt
;
vertex2_cnt
= polygon
->vertex_cnt
;
for (i
= 0; i
< vertex1_cnt
; vertex1
= vertex1
->next
, i
++) {
for (j
= 0; j
< vertex2_cnt
; vertex2
= vertex2
->next
, j
++)
if ((test
= edge_edge_intersect
(vertex1
, vertex1
->next
, vertex2
,
vertex2
->next
)) != GLU_NO_ERROR
)
return test
;
}
return GLU_NO_ERROR
;
}
static void
add_new_exterior
(GLUtriangulatorObj
* tobj
, tess_contour
* contour
)
{
contour
->type
= GLU_EXTERIOR
;
contour
->next
= NULL
;
contour
->previous
= tobj
->last_contour
;
tobj
->last_contour
->next
= contour
;
tobj
->last_contour
= contour
;
}
static void
add_new_interior
(GLUtriangulatorObj
* tobj
,
tess_contour
* outer
, tess_contour
* contour
)
{
contour
->type
= GLU_INTERIOR
;
contour
->next
= outer
->next
;
contour
->previous
= outer
;
if (outer
->next
!= NULL
)
outer
->next
->previous
= contour
;
outer
->next
= contour
;
if (tobj
->last_contour
== outer
)
tobj
->last_contour
= contour
;
}
static void
add_interior_with_hierarchy_check
(GLUtriangulatorObj
* tobj
,
tess_contour
* outer
,
tess_contour
* contour
)
{
tess_contour
*ptr
;
/* for all interiors of outer check if they are interior of contour */
/* if so, change that interior to exterior and move it of of the */
/* interior sequence */
if (outer
->next
!= NULL
&& outer
->next
->type
== GLU_INTERIOR
) {
GLenum test
;
for (ptr
= outer
->next
; ptr
!= NULL
&& ptr
->type
== GLU_INTERIOR
;
ptr
= ptr
->next
) {
test
= is_contour_contained_in
(ptr
, contour
);
switch (test
) {
case GLU_INTERIOR
:
/* contour is contained in one of the interiors */
/* check if possibly contained in other exteriors */
/* move ptr to first EXTERIOR */
for (; ptr
!= NULL
&& ptr
->type
== GLU_INTERIOR
; ptr
= ptr
->next
);
if (ptr
== NULL
)
/* another exterior */
add_new_exterior
(tobj
, contour
);
else
add_exterior_with_check
(tobj
, ptr
, contour
);
return;
case GLU_EXTERIOR
:
/* one of the interiors is contained in the contour */
/* change it to EXTERIOR, and shift it away from the */
/* interior sequence */
shift_interior_to_exterior
(tobj
, ptr
);
break;
case GLU_NO_ERROR
:
/* disjoint */
break;
default:
abort();
}
}
}
/* add contour to the interior sequence */
add_new_interior
(tobj
, outer
, contour
);
}
static void
reverse_hierarchy_and_add_exterior
(GLUtriangulatorObj
* tobj
,
tess_contour
* outer
,
tess_contour
* contour
)
{
tess_contour
*ptr
;
/* reverse INTERIORS to EXTERIORS */
/* any INTERIORS? */
if (outer
->next
!= NULL
&& outer
->next
->type
== GLU_INTERIOR
)
for (ptr
= outer
->next
; ptr
!= NULL
&& ptr
->type
== GLU_INTERIOR
;
ptr
= ptr
->next
) ptr
->type
= GLU_EXTERIOR
;
/* the outer now becomes inner */
outer
->type
= GLU_INTERIOR
;
/* contour is the EXTERIOR */
contour
->next
= outer
;
if (tobj
->contours
== outer
) {
/* first contour beeing reversed */
contour
->previous
= NULL
;
tobj
->contours
= contour
;
}
else {
outer
->previous
->next
= contour
;
contour
->previous
= outer
->previous
;
}
outer
->previous
= contour
;
}
static void
shift_interior_to_exterior
(GLUtriangulatorObj
* tobj
, tess_contour
* contour
)
{
contour
->previous
->next
= contour
->next
;
if (contour
->next
!= NULL
)
contour
->next
->previous
= contour
->previous
;
else
tobj
->last_contour
= contour
->previous
;
}
static void
add_exterior_with_check
(GLUtriangulatorObj
* tobj
,
tess_contour
* outer
, tess_contour
* contour
)
{
GLenum test
;
/* this contour might be interior to further exteriors - check */
/* if not, just add as a new exterior */
for (; outer
!= NULL
&& outer
->type
== GLU_EXTERIOR
; outer
= outer
->next
) {
test
= is_contour_contained_in
(outer
, contour
);
switch (test
) {
case GLU_INTERIOR
:
/* now we have to check if contour is inside interiors */
/* or not */
/* any interiors? */
if (outer
->next
!= NULL
&& outer
->next
->type
== GLU_INTERIOR
) {
/* for all interior, check if inside any of them */
/* if not inside any of interiors, its another */
/* interior */
/* or it may contain some interiors, then change */
/* the contained interiors to exterior ones */
add_interior_with_hierarchy_check
(tobj
, outer
, contour
);
}
else {
/* not in interior, add as new interior contour */
add_new_interior
(tobj
, outer
, contour
);
}
return;
case GLU_NO_ERROR
:
/* disjoint */
break;
default:
abort();
}
}
/* add contour to the exterior sequence */
add_new_exterior
(tobj
, contour
);
}
void
tess_handle_holes
(GLUtriangulatorObj
* tobj
)
{
tess_contour
*contour
, *hole
;
GLenum exterior_orientation
;
/* verify hole orientation */
for (contour
= tobj
->contours
; contour
!= NULL
;) {
exterior_orientation
= contour
->orientation
;
for (contour
= contour
->next
;
contour
!= NULL
&& contour
->type
== GLU_INTERIOR
;
contour
= contour
->next
) {
if (contour
->orientation
== exterior_orientation
) {
tess_call_user_error
(tobj
, GLU_TESS_ERROR5
);
return;
}
}
}
/* now cut-out holes */
for (contour
= tobj
->contours
; contour
!= NULL
;) {
hole
= contour
->next
;
while (hole
!= NULL
&& hole
->type
== GLU_INTERIOR
) {
if (cut_out_hole
(tobj
, contour
, hole
) == GLU_ERROR
)
return;
hole
= contour
->next
;
}
contour
= contour
->next
;
}
}
static GLenum
cut_out_hole
(GLUtriangulatorObj
* tobj
,
tess_contour
* contour
, tess_contour
* hole
)
{
tess_contour
*tmp_hole
;
tess_vertex
*v1
, *v2
, *tmp_vertex
;
GLuint vertex1_cnt
, vertex2_cnt
, tmp_vertex_cnt
;
GLuint i
, j
, k
;
GLenum test
= 0;
/* find an edge connecting contour and hole not intersecting any other */
/* edge belonging to either the contour or any of the other holes */
for (v1
= contour
->vertices
, vertex1_cnt
= contour
->vertex_cnt
, i
= 0;
i
< vertex1_cnt
; i
++, v1
= v1
->next
) {
for (v2
= hole
->vertices
, vertex2_cnt
= hole
->vertex_cnt
, j
= 0;
j
< vertex2_cnt
; j
++, v2
= v2
->next
) {
/* does edge (v1,v2) intersect any edge of contour */
for (tmp_vertex
= contour
->vertices
, tmp_vertex_cnt
=
contour
->vertex_cnt
, k
= 0; k
< tmp_vertex_cnt
;
tmp_vertex
= tmp_vertex
->next
, k
++) {
/* skip edge tests for edges directly connected */
if (v1
== tmp_vertex
|| v1
== tmp_vertex
->next
)
continue;
test
= edge_edge_intersect
(v1
, v2
, tmp_vertex
, tmp_vertex
->next
);
if (test
!= GLU_NO_ERROR
)
break;
}
if (test
== GLU_NO_ERROR
) {
/* does edge (v1,v2) intersect any edge of hole */
for (tmp_vertex
= hole
->vertices
,
tmp_vertex_cnt
= hole
->vertex_cnt
, k
= 0;
k
< tmp_vertex_cnt
; tmp_vertex
= tmp_vertex
->next
, k
++) {
/* skip edge tests for edges directly connected */
if (v2
== tmp_vertex
|| v2
== tmp_vertex
->next
)
continue;
test
=
edge_edge_intersect
(v1
, v2
, tmp_vertex
, tmp_vertex
->next
);
if (test
!= GLU_NO_ERROR
)
break;
}
if (test
== GLU_NO_ERROR
) {
/* does edge (v1,v2) intersect any other hole? */
for (tmp_hole
= hole
->next
;
tmp_hole
!= NULL
&& tmp_hole
->type
== GLU_INTERIOR
;
tmp_hole
= tmp_hole
->next
) {
/* does edge (v1,v2) intersect any edge of hole */
for (tmp_vertex
= tmp_hole
->vertices
,
tmp_vertex_cnt
= tmp_hole
->vertex_cnt
, k
= 0;
k
< tmp_vertex_cnt
; tmp_vertex
= tmp_vertex
->next
, k
++) {
test
= edge_edge_intersect
(v1
, v2
, tmp_vertex
,
tmp_vertex
->next
);
if (test
!= GLU_NO_ERROR
)
break;
}
if (test
!= GLU_NO_ERROR
)
break;
}
}
}
if (test
== GLU_NO_ERROR
) {
/* edge (v1,v2) is good for eliminating the hole */
if (merge_hole_with_contour
(tobj
, contour
, hole
, v1
, v2
)
== GLU_NO_ERROR
)
return GLU_NO_ERROR
;
else
return GLU_ERROR
;
}
}
}
/* other holes are blocking all possible connections of hole */
/* with contour, we shift this hole as the last hole and retry */
for (tmp_hole
= hole
;
tmp_hole
!= NULL
&& tmp_hole
->type
== GLU_INTERIOR
;
tmp_hole
= tmp_hole
->next
);
contour
->next
= hole
->next
;
hole
->next
->previous
= contour
;
if (tmp_hole
== NULL
) {
/* last EXTERIOR contour, shift hole as last contour */
hole
->next
= NULL
;
hole
->previous
= tobj
->last_contour
;
tobj
->last_contour
->next
= hole
;
tobj
->last_contour
= hole
;
}
else {
tmp_hole
->previous
->next
= hole
;
hole
->previous
= tmp_hole
->previous
;
tmp_hole
->previous
= hole
;
hole
->next
= tmp_hole
;
}
hole
= contour
->next
;
/* try once again - recurse */
return cut_out_hole
(tobj
, contour
, hole
);
}
static GLenum
merge_hole_with_contour
(GLUtriangulatorObj
* tobj
,
tess_contour
* contour
,
tess_contour
* hole
,
tess_vertex
* v1
, tess_vertex
* v2
)
{
tess_vertex
*v1_new
, *v2_new
;
/* make copies of v1 and v2, place them respectively after their originals */
if ((v1_new
= (tess_vertex
*) malloc(sizeof(tess_vertex
))) == NULL
) {
tess_call_user_error
(tobj
, GLU_OUT_OF_MEMORY
);
return GLU_ERROR
;
}
if ((v2_new
= (tess_vertex
*) malloc(sizeof(tess_vertex
))) == NULL
) {
tess_call_user_error
(tobj
, GLU_OUT_OF_MEMORY
);
return GLU_ERROR
;
}
v1_new
->edge_flag
= GL_TRUE
;
v1_new
->data
= v1
->data
;
v1_new
->location
[0] = v1
->location
[0];
v1_new
->location
[1] = v1
->location
[1];
v1_new
->location
[2] = v1
->location
[2];
v1_new
->x
= v1
->x
;
v1_new
->y
= v1
->y
;
v1_new
->shadow_vertex
= v1
;
v1
->shadow_vertex
= v1_new
;
v1_new
->next
= v1
->next
;
v1_new
->previous
= v1
;
v1
->next
->previous
= v1_new
;
v1
->next
= v1_new
;
v2_new
->edge_flag
= GL_TRUE
;
v2_new
->data
= v2
->data
;
v2_new
->location
[0] = v2
->location
[0];
v2_new
->location
[1] = v2
->location
[1];
v2_new
->location
[2] = v2
->location
[2];
v2_new
->x
= v2
->x
;
v2_new
->y
= v2
->y
;
v2_new
->shadow_vertex
= v2
;
v2
->shadow_vertex
= v2_new
;
v2_new
->next
= v2
->next
;
v2_new
->previous
= v2
;
v2
->next
->previous
= v2_new
;
v2
->next
= v2_new
;
/* link together the two lists */
v1
->next
= v2_new
;
v2_new
->previous
= v1
;
v2
->next
= v1_new
;
v1_new
->previous
= v2
;
/* update the vertex count of the contour */
contour
->vertex_cnt
+= hole
->vertex_cnt
+ 2;
/* remove the INTERIOR contour */
contour
->next
= hole
->next
;
if (hole
->next
!= NULL
)
hole
->next
->previous
= contour
;
free(hole
);
/* update tobj structure */
--(tobj
->contour_cnt
);
if (contour
->last_vertex
== v1
)
contour
->last_vertex
= v1_new
;
/* mark two vertices with edge_flag */
v2
->edge_flag
= GL_FALSE
;
v1
->edge_flag
= GL_FALSE
;
return GLU_NO_ERROR
;
}