3 * Mesa 3-D graphics library
5 * Copyright (C) 1995-2000 Brian Paul
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.
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.
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.
24 * This file is part of the polygon tesselation code contributed by
39 static GLboolean edge_flag
;
41 static void emit_triangle(GLUtriangulatorObj
*, tess_vertex
*,
42 tess_vertex
*, tess_vertex
*);
44 static void emit_triangle_with_edge_flag(GLUtriangulatorObj
*,
45 tess_vertex
*, GLboolean
,
46 tess_vertex
*, GLboolean
,
47 tess_vertex
*, GLboolean
);
50 twice_the_triangle_area(tess_vertex
* va
, tess_vertex
* vb
, tess_vertex
* vc
)
52 return (vb
->x
- va
->x
) * (vc
->y
- va
->y
) - (vb
->y
- va
->y
) * (vc
->x
-
57 left(GLdouble A
, GLdouble B
, GLdouble C
, GLdouble x
, GLdouble y
)
59 if (A
* x
+ B
* y
+ C
> -EPSILON
)
66 right(GLdouble A
, GLdouble B
, GLdouble C
, GLdouble x
, GLdouble y
)
68 if (A
* x
+ B
* y
+ C
< EPSILON
)
75 convex_ccw(tess_vertex
* va
,
76 tess_vertex
* vb
, tess_vertex
* vc
, GLUtriangulatorObj
* tobj
)
80 d
= twice_the_triangle_area(va
, vb
, vc
);
85 else if (d
< -EPSILON
) {
94 convex_cw(tess_vertex
* va
,
95 tess_vertex
* vb
, tess_vertex
* vc
, GLUtriangulatorObj
* tobj
)
99 d
= twice_the_triangle_area(va
, vb
, vc
);
104 else if (d
> EPSILON
) {
113 diagonal_ccw(tess_vertex
* va
,
115 GLUtriangulatorObj
* tobj
, tess_contour
* contour
)
117 tess_vertex
*vc
= va
->next
, *vertex
, *shadow_vertex
;
125 GLint res
= convex_ccw(va
, vc
, vb
, tobj
);
131 ba
.A
= vb
->y
- va
->y
;
132 ba
.B
= va
->x
- vb
->x
;
133 ba
.C
= -ba
.A
* va
->x
- ba
.B
* va
->y
;
134 ac
.A
= va
->y
- vc
->y
;
135 ac
.B
= vc
->x
- va
->x
;
136 ac
.C
= -ac
.A
* vc
->x
- ac
.B
* vc
->y
;
137 cb
.A
= vc
->y
- vb
->y
;
138 cb
.B
= vb
->x
- vc
->x
;
139 cb
.C
= -cb
.A
* vb
->x
- cb
.B
* vb
->y
;
140 for (vertex
= vb
->next
; vertex
!= va
; vertex
= vertex
->next
) {
141 shadow_vertex
= vertex
->shadow_vertex
;
142 if (shadow_vertex
!= NULL
&&
143 (shadow_vertex
== va
|| shadow_vertex
== vb
|| shadow_vertex
== vc
))
147 if (left(ba
.A
, ba
.B
, ba
.C
, x
, y
) &&
148 left(ac
.A
, ac
.B
, ac
.C
, x
, y
) && left(cb
.A
, cb
.B
, cb
.C
, x
, y
))
155 diagonal_cw(tess_vertex
* va
,
157 GLUtriangulatorObj
* tobj
, tess_contour
* contour
)
159 tess_vertex
*vc
= va
->next
, *vertex
, *shadow_vertex
;
167 GLint res
= convex_cw(va
, vc
, vb
, tobj
);
173 ba
.A
= vb
->y
- va
->y
;
174 ba
.B
= va
->x
- vb
->x
;
175 ba
.C
= -ba
.A
* va
->x
- ba
.B
* va
->y
;
176 ac
.A
= va
->y
- vc
->y
;
177 ac
.B
= vc
->x
- va
->x
;
178 ac
.C
= -ac
.A
* vc
->x
- ac
.B
* vc
->y
;
179 cb
.A
= vc
->y
- vb
->y
;
180 cb
.B
= vb
->x
- vc
->x
;
181 cb
.C
= -cb
.A
* vb
->x
- cb
.B
* vb
->y
;
182 for (vertex
= vb
->next
; vertex
!= va
; vertex
= vertex
->next
) {
183 shadow_vertex
= vertex
->shadow_vertex
;
184 if (shadow_vertex
!= NULL
&&
185 (shadow_vertex
== va
|| shadow_vertex
== vb
|| shadow_vertex
== vc
))
189 if (right(ba
.A
, ba
.B
, ba
.C
, x
, y
) &&
190 right(ac
.A
, ac
.B
, ac
.C
, x
, y
) && right(cb
.A
, cb
.B
, cb
.C
, x
, y
))
197 clip_ear(GLUtriangulatorObj
* tobj
, tess_vertex
* v
, tess_contour
* contour
)
199 emit_triangle(tobj
, v
->previous
, v
, v
->next
);
200 /* the first in the list */
201 if (contour
->vertices
== v
) {
202 contour
->vertices
= v
->next
;
203 contour
->last_vertex
->next
= v
->next
;
204 v
->next
->previous
= contour
->last_vertex
;
208 if (contour
->last_vertex
== v
) {
209 contour
->vertices
->previous
= v
->previous
;
210 v
->previous
->next
= v
->next
;
211 contour
->last_vertex
= v
->previous
;
214 v
->next
->previous
= v
->previous
;
215 v
->previous
->next
= v
->next
;
218 --(contour
->vertex_cnt
);
222 clip_ear_with_edge_flag(GLUtriangulatorObj
* tobj
,
223 tess_vertex
* v
, tess_contour
* contour
)
225 emit_triangle_with_edge_flag(tobj
, v
->previous
, v
->previous
->edge_flag
,
226 v
, v
->edge_flag
, v
->next
, GL_FALSE
);
227 v
->previous
->edge_flag
= GL_FALSE
;
228 /* the first in the list */
229 if (contour
->vertices
== v
) {
230 contour
->vertices
= v
->next
;
231 contour
->last_vertex
->next
= v
->next
;
232 v
->next
->previous
= contour
->last_vertex
;
236 if (contour
->last_vertex
== v
) {
237 contour
->vertices
->previous
= v
->previous
;
238 v
->previous
->next
= v
->next
;
239 contour
->last_vertex
= v
->previous
;
242 v
->next
->previous
= v
->previous
;
243 v
->previous
->next
= v
->next
;
246 --(contour
->vertex_cnt
);
250 triangulate_ccw(GLUtriangulatorObj
* tobj
, tess_contour
* contour
)
253 GLuint vertex_cnt
= contour
->vertex_cnt
;
255 while (vertex_cnt
> 3) {
256 vertex
= contour
->vertices
;
257 while (diagonal_ccw(vertex
, vertex
->next
->next
, tobj
, contour
) ==
258 GL_FALSE
&& tobj
->error
== GLU_NO_ERROR
)
259 vertex
= vertex
->next
;
260 if (tobj
->error
!= GLU_NO_ERROR
)
262 clip_ear(tobj
, vertex
->next
, contour
);
268 triangulate_cw(GLUtriangulatorObj
* tobj
, tess_contour
* contour
)
271 GLuint vertex_cnt
= contour
->vertex_cnt
;
273 while (vertex_cnt
> 3) {
274 vertex
= contour
->vertices
;
275 while (diagonal_cw(vertex
, vertex
->next
->next
, tobj
, contour
) ==
276 GL_FALSE
&& tobj
->error
== GLU_NO_ERROR
)
277 vertex
= vertex
->next
;
278 if (tobj
->error
!= GLU_NO_ERROR
)
280 clip_ear(tobj
, vertex
->next
, contour
);
286 triangulate_ccw_with_edge_flag(GLUtriangulatorObj
* tobj
,
287 tess_contour
* contour
)
290 GLuint vertex_cnt
= contour
->vertex_cnt
;
292 while (vertex_cnt
> 3) {
293 vertex
= contour
->vertices
;
294 while (diagonal_ccw(vertex
, vertex
->next
->next
, tobj
, contour
) ==
295 GL_FALSE
&& tobj
->error
== GLU_NO_ERROR
)
296 vertex
= vertex
->next
;
297 if (tobj
->error
!= GLU_NO_ERROR
)
299 clip_ear_with_edge_flag(tobj
, vertex
->next
, contour
);
305 triangulate_cw_with_edge_flag(GLUtriangulatorObj
* tobj
,
306 tess_contour
* contour
)
309 GLuint vertex_cnt
= contour
->vertex_cnt
;
311 while (vertex_cnt
> 3) {
312 vertex
= contour
->vertices
;
313 while (diagonal_cw(vertex
, vertex
->next
->next
, tobj
, contour
) ==
314 GL_FALSE
&& tobj
->error
== GLU_NO_ERROR
)
315 vertex
= vertex
->next
;
316 if (tobj
->error
!= GLU_NO_ERROR
)
318 clip_ear_with_edge_flag(tobj
, vertex
->next
, contour
);
324 tess_tesselate(GLUtriangulatorObj
* tobj
)
326 tess_contour
*contour
;
328 for (contour
= tobj
->contours
; contour
!= NULL
; contour
= contour
->next
) {
329 if (contour
->orientation
== GLU_CCW
) {
330 triangulate_ccw(tobj
, contour
);
333 triangulate_cw(tobj
, contour
);
335 if (tobj
->error
!= GLU_NO_ERROR
)
338 /* emit the last triangle */
339 emit_triangle(tobj
, contour
->vertices
, contour
->vertices
->next
,
340 contour
->vertices
->next
->next
);
345 tess_tesselate_with_edge_flag(GLUtriangulatorObj
* tobj
)
347 tess_contour
*contour
;
350 /* first callback with edgeFlag set to GL_TRUE */
351 (tobj
->callbacks
.edgeFlag
) (GL_TRUE
);
353 for (contour
= tobj
->contours
; contour
!= NULL
; contour
= contour
->next
) {
354 if (contour
->orientation
== GLU_CCW
)
355 triangulate_ccw_with_edge_flag(tobj
, contour
);
357 triangulate_cw_with_edge_flag(tobj
, contour
);
358 if (tobj
->error
!= GLU_NO_ERROR
)
360 /* emit the last triangle */
361 emit_triangle_with_edge_flag(tobj
, contour
->vertices
,
362 contour
->vertices
->edge_flag
,
363 contour
->vertices
->next
,
364 contour
->vertices
->next
->edge_flag
,
365 contour
->vertices
->next
->next
,
366 contour
->vertices
->next
->next
->edge_flag
);
371 emit_triangle(GLUtriangulatorObj
* tobj
,
372 tess_vertex
* v1
, tess_vertex
* v2
, tess_vertex
* v3
)
374 (tobj
->callbacks
.begin
) (GL_TRIANGLES
);
375 (tobj
->callbacks
.vertex
) (v1
->data
);
376 (tobj
->callbacks
.vertex
) (v2
->data
);
377 (tobj
->callbacks
.vertex
) (v3
->data
);
378 (tobj
->callbacks
.end
) ();
382 emit_triangle_with_edge_flag(GLUtriangulatorObj
* tobj
,
384 GLboolean edge_flag1
,
386 GLboolean edge_flag2
,
387 tess_vertex
* v3
, GLboolean edge_flag3
)
389 (tobj
->callbacks
.begin
) (GL_TRIANGLES
);
390 if (edge_flag1
!= edge_flag
) {
391 edge_flag
= (edge_flag
== GL_TRUE
? GL_FALSE
: GL_TRUE
);
392 (tobj
->callbacks
.edgeFlag
) (edge_flag
);
394 (tobj
->callbacks
.vertex
) (v1
->data
);
395 if (edge_flag2
!= edge_flag
) {
396 edge_flag
= (edge_flag
== GL_TRUE
? GL_FALSE
: GL_TRUE
);
397 (tobj
->callbacks
.edgeFlag
) (edge_flag
);
399 (tobj
->callbacks
.vertex
) (v2
->data
);
400 if (edge_flag3
!= edge_flag
) {
401 edge_flag
= (edge_flag
== GL_TRUE
? GL_FALSE
: GL_TRUE
);
402 (tobj
->callbacks
.edgeFlag
) (edge_flag
);
404 (tobj
->callbacks
.vertex
) (v3
->data
);
405 (tobj
->callbacks
.end
) ();