Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
55 | pj | 1 | /* $Id: polytest.c,v 1.1 2003-02-28 11:42:07 pj 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 | } |