1 /* ______ ___ ___
2 * /\ _ \ /\_ \ /\_ \
3 * \ \ \L\ \\//\ \ \//\ \ __ __ _ __ ___
4 * \ \ __ \ \ \ \ \ \ \ /'__`\ /'_ `\/\`'__\/ __`\
5 * \ \ \/\ \ \_\ \_ \_\ \_/\ __//\ \L\ \ \ \//\ \L\ \
6 * \ \_\ \_\/\____\/\____\ \____\ \____ \ \_\\ \____/
7 * \/_/\/_/\/____/\/____/\/____/\/___L\ \/_/ \/___/
8 * /\____/
9 * \_/__/
10 *
11 * Polygon triangulation with holes.
12 *
13 *
14 * By Michał Cichoń.
15 *
16 * See readme.txt for copyright information.
17 */
18
19
20 # include "allegro5/allegro.h"
21 # include "allegro5/allegro_primitives.h"
22 # include "allegro5/internal/aintern_prim.h"
23 # include "allegro5/internal/aintern_list.h"
24 # include <float.h>
25 # include <math.h>
26
27
28 # define POLY_DEBUG 0
29
30
31 /* */
32 # define POLY_VERTEX_ATTR_REFLEX 0x0001
33 # define POLY_VERTEX_ATTR_EAR_CLIP 0x0002
34 # define POLY_VERTEX_ATTR_ALL (POLY_VERTEX_ATTR_REFLEX | POLY_VERTEX_ATTR_EAR_CLIP)
35
36
37 typedef void (*POLY_EMIT_TRIANGLE)(int, int, int, void*);
38
39 typedef struct POLY {
40 const float* vertex_buffer;
41 size_t vertex_stride;
42 size_t vertex_count;
43 const int* split_indices;
44 size_t split_stride;
45 size_t split_count;
46 POLY_EMIT_TRIANGLE emit;
47 void* userdata;
48 _AL_LIST* vertex_list;
49 _AL_LIST* reflex_list;
50 _AL_LIST* ear_list;
51 } POLY;
52
53 typedef struct POLY_SPLIT {
54 int begin;
55 size_t size;
56 float* point;
57 int max_index;
58 } POLY_SPLIT;
59
60
61 # if POLY_DEBUG
62 typedef void (*poly_debug_draw_text_t)(float x, float y, int line, const char* format, ...);
63
64 #if defined _MSC_VER
65 #define EXPORT __declspec(dllexport)
66 #else
67 #define EXPORT
68 #define __noop ((void)0)
69 #endif
70
71 EXPORT int g_poly_debug_split_step = -1;
72 EXPORT int g_poly_debug_step = -1;
73 EXPORT int g_poly_debug_step_current = 0;
74 EXPORT poly_debug_draw_text_t g_poly_debug_draw_text = NULL;
75 EXPORT float g_poly_debug_scale = 1.0f;
76
77 #undef EXPORT
78
79 # define POLY_DEBUG_TEXT(x,y,...) (g_poly_debug_draw_text ? g_poly_debug_draw_text(x,y,INT_MAX,__VA_ARGS__) : __noop)
80 # define POLY_DEBUG_TEXT_LINE(x,y,line,...) (g_poly_debug_draw_text ? g_poly_debug_draw_text(x,y,line,__VA_ARGS__) : __noop)
81
82 # endif
83
84
85 /* Internal functions. */
86 static bool poly_initialize(POLY* poly);
87 static void poly_classify_vertices(_AL_LIST* vertices, _AL_LIST* reflex, _AL_LIST* ear);
88 static void poly_classify_vertices_in_range(_AL_LIST_ITEM* begin, _AL_LIST_ITEM* end, _AL_LIST* vertices, _AL_LIST* reflex, _AL_LIST* ear);
89 static void poly_do_triangulate(POLY* poly);
90
91 static _AL_LIST* poly_create_split_list(POLY* polygon);
92 static void poly_split_list_dtor(void* user_data);
93
94
95 /*
96 * Seek for closest intersection point of polygon with a ray directed
97 * to the right.
98 *
99 * Returns true if intersection was found. 'point', 'edge0' and 'edge1'
100 * are set to proper values (if not NULL).
101 * Returns false if intersection was not fount and none of above
102 * are modified.
103 */
poly_find_closest_intersection(_AL_LIST * vertices,const float * vertex,float * point,_AL_LIST_ITEM ** edge0,_AL_LIST_ITEM ** edge1)104 static bool poly_find_closest_intersection(_AL_LIST* vertices, const float* vertex, float* point, _AL_LIST_ITEM** edge0, _AL_LIST_ITEM** edge1)
105 {
106 size_t i;
107 const float* v0 = NULL;
108 float v1[2];
109 float intersection[2];
110 float t0, t1;
111 float best_point[2] = {0, 0};
112 float best_t;
113 _AL_LIST_ITEM* item = NULL;
114 _AL_LIST_ITEM* next = NULL;
115 _AL_LIST_ITEM* best_e0 = NULL;
116 _AL_LIST_ITEM* best_e1 = NULL;
117
118 /* Assemble line pointing to the right. */
119 v0 = vertex;
120 v1[0] = v0[0] + 1.0f;
121 v1[1] = v0[1];
122
123 /* Seek for the closest intersection. */
124 best_t = FLT_MAX;
125 item = _al_list_front(vertices);
126 next = _al_list_next_circular(vertices, item);
127 for (i = 0; i < _al_list_size(vertices); ++i, item = next, next = _al_list_next_circular(vertices, next)) {
128
129 float* p0 = (float*)_al_list_item_data(item);
130 float* p1 = (float*)_al_list_item_data(next);
131
132 /* Perform quick rejection.
133 *
134 * We are interested only with outer edges. That mean only those
135 * whose go from the bottom to the up. Note we cannot intersect
136 * parallel line.
137 *
138 * Second condition reject edges lying completely on the left
139 * side of ray origin.
140 */
141 if ((p0[1] < p1[1]) || (p0[0] <= vertex[0] && p1[0] <= vertex[0]))
142 continue;
143
144 if (_al_prim_intersect_segment(v0, v1, p0, p1, intersection, &t0, &t1) && (t1 >= 0.0f) && (t1 <= 1.0f) && (t0 >= 0.0f) && (t0 < best_t)) {
145
146 best_t = t0;
147 best_point[0] = intersection[0];
148 best_point[1] = intersection[1];
149 best_e0 = item;
150 best_e1 = next;
151 }
152 }
153
154 if (NULL != best_e0) {
155
156 if (NULL != point) {
157
158 point[0] = best_point[0];
159 point[1] = best_point[1];
160 }
161
162 if (NULL != edge0)
163 *edge0 = best_e0;
164
165 if (NULL != edge1)
166 *edge1 = best_e1;
167
168 # if POLY_DEBUG
169 //al_draw_line(v0[0], v0[1], point[0], point[1], al_map_rgb(255, 0, 0), 0.0f);
170 # endif
171
172 return true;
173 }
174 else
175 return false;
176 }
177
178
179 /*
180 * Seek for the best vertex in polygon for doing split.
181 *
182 * Returns vertex after which split (hole) vertices
183 * can be inserted.
184 */
poly_find_outter_split_vertex(POLY * polygon,POLY_SPLIT * split)185 static _AL_LIST_ITEM* poly_find_outter_split_vertex(POLY* polygon, POLY_SPLIT* split)
186 {
187 float intersection[2];
188 _AL_LIST_ITEM* edge_vertex_0;
189 _AL_LIST_ITEM* edge_vertex_1;
190 _AL_LIST_ITEM* vertex;
191 _AL_LIST_ITEM* reflex_item;
192 _AL_LIST_ITEM* best_vertex;
193 float best_distance;
194 float* p0;
195 float* p1;
196 float* p;
197
198 if (!poly_find_closest_intersection(polygon->vertex_list, split->point, intersection, &edge_vertex_0, &edge_vertex_1))
199 return NULL;
200
201 p0 = (float*)_al_list_item_data(edge_vertex_0);
202 p1 = (float*)_al_list_item_data(edge_vertex_1);
203
204 /* Maybe we hit an edge vertex? */
205 if (_al_prim_are_points_equal(split->point, p0))
206 return edge_vertex_0;
207
208 if (_al_prim_are_points_equal(split->point, p1))
209 return edge_vertex_1;
210
211 /* No luck. Pick point which most far away from us. */
212 if (p0[0] > p1[0]) {
213
214 vertex = edge_vertex_0;
215 p = p0;
216 }
217 else {
218
219 vertex = edge_vertex_1;
220 p = p1;
221 }
222
223 /* Seek in reflex vertices. */
224 best_vertex = NULL;
225 best_distance = FLT_MAX;
226
227 for (reflex_item = _al_list_front(polygon->reflex_list); reflex_item; reflex_item = _al_list_next(polygon->reflex_list, reflex_item)) {
228
229 _AL_LIST_ITEM* reflex_vertex = (_AL_LIST_ITEM*)_al_list_item_data(reflex_item);
230
231 float* reflex_point = (float*)_al_list_item_data(reflex_vertex);
232
233 if (_al_prim_is_point_in_triangle(reflex_point, split->point, p, intersection)) {
234
235 float diff_x = reflex_point[0] - split->point[0];
236 float diff_y = reflex_point[1] - split->point[1];
237
238 float dist = diff_x * diff_x + diff_y * diff_y;
239
240 if (dist < best_distance) {
241
242 best_distance = dist;
243 best_vertex = reflex_vertex;
244 }
245 }
246 }
247
248 if (NULL != best_vertex)
249 vertex = best_vertex;
250
251 //# if POLY_DEBUG
252 // p0 = (float*)_al_list_item_data(vertex);
253 // al_draw_line(p0[0], p0[1], intersection[0], intersection[1], al_map_rgb(255, 0, 0), 0.0f);
254 //# endif
255
256 return vertex;
257 }
258
259
260 # define POLY_VERTEX(index) ((float*)(((uint8_t*)polygon->vertex_buffer) + (index) * polygon->vertex_stride))
261 # define POLY_SPLIT(index) (*((int*)(((uint8_t*)polygon->split_indices) + (index) * polygon->split_stride)))
262 # define POLY_SPLIT_INDEX(split) (((uint8_t*)split - (uint8_t*)polygon->split_indices) / polygon->split_stride)
263
264
265 /*
266 * Create list of the splits.
267 */
poly_create_split_list(POLY * polygon)268 static _AL_LIST* poly_create_split_list(POLY* polygon)
269 {
270 int i;
271 int last_split;
272
273 _AL_LIST* list = _al_list_create_static(polygon->split_count);
274 POLY_SPLIT* splits = (POLY_SPLIT*)al_malloc(polygon->split_count * sizeof(POLY_SPLIT));
275
276 if ((NULL == list) || (NULL == splits)) {
277
278 _al_list_destroy(list);
279 al_free(splits);
280
281 return NULL;
282 }
283
284 /* Set list destructor, so we will don't worry about
285 * manually releasing allocated memory.
286 */
287 _al_list_set_dtor(list, poly_split_list_dtor);
288 _al_list_set_user_data(list, splits);
289
290 last_split = POLY_SPLIT(0);
291 for (i = 1; i < (int)polygon->split_count; ++i) {
292
293 int j;
294 float max;
295 POLY_SPLIT* split = splits + i;
296 _AL_LIST_ITEM* where;
297
298 split->begin = last_split;
299 split->size = POLY_SPLIT(i) - last_split;
300 last_split = last_split + split->size;
301
302 max = -FLT_MAX;
303 split->max_index = -1;
304 for (j = split->begin; j < split->begin + (int)split->size; ++j) {
305
306 float* point = POLY_VERTEX(j);
307
308 if (point[0] >= max) {
309
310 max = point[0];
311 split->point = point;
312 split->max_index = j;
313 }
314 }
315
316 split->max_index -= split->begin;
317
318 ASSERT(split->max_index >= 0);
319
320 where = NULL;
321 if (!_al_list_is_empty(list)) {
322
323 for (where = _al_list_front(list); where; where = _al_list_next(list, where)) {
324
325 POLY_SPLIT* local_split = (POLY_SPLIT*)_al_list_item_data(where);
326
327 if (local_split->point[0] < max)
328 break;
329 }
330 }
331
332 if (NULL == where)
333 _al_list_push_back(list, split);
334 else
335 _al_list_insert_before(list, where, split);
336 }
337
338 return list;
339 }
340
341
342 /*
343 * Release memory allocated by split list. This method
344 * serve as callback to the list.
345 */
poly_split_list_dtor(void * user_data)346 static void poly_split_list_dtor(void* user_data)
347 {
348 /* This is array of POLY_SPLIT. */
349 al_free(user_data);
350 }
351
352
353 /*
354 * Perform initialization step to polygon triangulation.
355 *
356 * Three linked list are initialized: vertex_list, reflex_list
357 * and ear_list.
358 *
359 * All provided splits (holes) are resolved in this step.
360 * Therefore at the end we have simple polygon.
361 */
poly_initialize(POLY * polygon)362 static bool poly_initialize(POLY* polygon)
363 {
364 _AL_LIST* vertex_list;
365 _AL_LIST* reflex_list;
366 _AL_LIST* ear_list;
367 _AL_LIST* split_list;
368 _AL_LIST_ITEM* split_item;
369 size_t vertex_count;
370 bool use_split_list;
371 size_t j;
372 int i;
373
374 # if POLY_DEBUG
375 if (g_poly_debug_split_step >= 0)
376 polygon->split_count = min(g_poly_debug_split_step, polygon->split_count);
377 # endif
378
379 /* Every hole add two extra vertices to the list. */
380 vertex_count = polygon->vertex_count + (polygon->split_count - 1) * 2;
381
382 /* Create lists for polygon. */
383 vertex_list = _al_list_create_static(vertex_count);
384 reflex_list = _al_list_create_static(vertex_count);
385 ear_list = _al_list_create_static(vertex_count);
386
387 if (polygon->split_count > 1) {
388
389 split_list = poly_create_split_list(polygon);
390 use_split_list = true;
391 }
392 else {
393 split_list = NULL;
394 use_split_list = false;
395 }
396
397 if ((NULL == vertex_list) || (NULL == reflex_list) || (NULL == ear_list) || (use_split_list && (NULL == split_list))) {
398
399 _al_list_destroy(vertex_list);
400 _al_list_destroy(reflex_list);
401 _al_list_destroy(ear_list);
402 _al_list_destroy(split_list);
403
404 return false;
405 }
406
407 /* Store lists in polygon. */
408 polygon->vertex_list = vertex_list;
409 polygon->reflex_list = reflex_list;
410 polygon->ear_list = ear_list;
411
412 /* Push main polygon outline. */
413 for (i = 0; i < POLY_SPLIT(0); ++i)
414 _al_list_push_back(vertex_list, POLY_VERTEX(i));
415
416 if (use_split_list) {
417
418 # if POLY_DEBUG
419 int current_split = 0;
420 # endif
421
422 poly_classify_vertices(vertex_list, reflex_list, NULL);
423
424 /* Resolve all holes. */
425 for (split_item = _al_list_front(split_list); split_item; split_item = _al_list_next(split_list, split_item)) {
426
427 _AL_LIST_ITEM* first_vertex;
428 _AL_LIST_ITEM* last_vertex;
429 POLY_SPLIT* split;
430
431 # if POLY_DEBUG
432 if (g_poly_debug_split_step >= 0 && current_split >= g_poly_debug_split_step)
433 break;
434
435 ++current_split;
436 # endif
437
438 split = (POLY_SPLIT*)_al_list_item_data(split_item);
439
440 first_vertex = poly_find_outter_split_vertex(polygon, split);
441
442 if (NULL == first_vertex)
443 break;
444
445 /* Insert hole vertices. */
446 last_vertex = first_vertex;
447 for (j = 0; j <= split->size; ++j)
448 last_vertex = _al_list_insert_after(vertex_list, last_vertex,
449 POLY_VERTEX(split->begin + ((j + split->max_index) % split->size)));
450 last_vertex = _al_list_insert_after(vertex_list, last_vertex, _al_list_item_data(first_vertex));
451
452 _al_list_remove(reflex_list, first_vertex);
453
454 poly_classify_vertices_in_range(first_vertex, _al_list_next(vertex_list, last_vertex), vertex_list, reflex_list, NULL);
455 }
456
457 _al_list_destroy(split_list);
458
459 poly_classify_vertices(vertex_list, NULL, ear_list);
460 }
461 else
462 /* Initialize reflex and ear vertex lists. */
463 poly_classify_vertices(vertex_list, reflex_list, ear_list);
464
465 return true;
466 }
467
468 # undef POLY_VERTEX
469 # undef POLY_SPLIT
470 # undef POLY_SPLIT_INDEX
471
472
473 /*
474 * Compute polygon vertex attributes. Currently supported attributes are:
475 * - ear clip
476 * - reflex
477 *
478 * Vertex is an ear clip when triangle made by their edges does not contain
479 * any other vertices.
480 *
481 * Vertex is a reflex when angle between edges is greater or equal
482 * to 180 degrees.
483 *
484 * Optionally function may take reflex list (if not NULL). In this case test
485 * for ear clip is performed only on reflex vertices not on entire polygon.
486 * This is used for triangulation speed optimization, because convex
487 * (non reflect) vertices will never became reflex.
488 *
489 * Flags are used to determine for which attribute we want to check.
490 * Use POLY_VERTEX_ATTR_ALL to test for all attributes.
491 */
poly_compute_vertex_attributes(_AL_LIST * vertices,_AL_LIST_ITEM * item,int flags,_AL_LIST * reflex)492 static int poly_compute_vertex_attributes(_AL_LIST* vertices, _AL_LIST_ITEM* item, int flags, _AL_LIST* reflex)
493 {
494 size_t i;
495 _AL_LIST_ITEM* prev = _al_list_previous_circular(vertices, item);
496 _AL_LIST_ITEM* next = _al_list_next_circular(vertices, item);
497 _AL_LIST_ITEM* point = NULL;
498 int result = 0;
499 float* v0;
500 float* v1;
501 float* v2;
502 float cross;
503
504 // Oops, degenerate triangle in store.
505 if (_al_list_size(vertices) < 3)
506 return result;
507
508 // Get points.
509 v0 = (float*)_al_list_item_data(prev);
510 v1 = (float*)_al_list_item_data(item);
511 v2 = (float*)_al_list_item_data(next);
512
513 // Compute the cross product between the two edges
514 cross = (v0[0] - v1[0]) * (v2[1] - v1[1]) - (v0[1] - v1[1]) * (v2[0] - v1[0]);
515
516 # if POLY_DEBUG
517 if (g_poly_debug_step == g_poly_debug_step_current) {
518
519 float step = 0.25f * 0.0f;
520
521 float dir0[2] = { v0[0] - v1[0], v0[1] - v1[1] };
522 float dir2[2] = { v2[0] - v1[0], v2[1] - v1[1] };
523
524 POLY_DEBUG_TEXT(v1[0], v1[1], "%d", cross > 0);
525
526 al_draw_line(v1[0], v1[1], v1[0] + dir0[0] * step, v1[1] + dir0[1] * step, al_map_rgb(255, 0, 0), 4.0f * g_poly_debug_scale);
527 al_draw_line(v1[0], v1[1], v1[0] + dir2[0] * step, v1[1] + dir2[1] * step, al_map_rgb(255, 0, 0), 4.0f * g_poly_debug_scale);
528 }
529 # endif
530
531 // If internal angle is less than 180 degrees then we may
532 // have an ear clip vertex, otherwise we have reflex.
533 if (cross >= 0)
534 {
535 if (flags & POLY_VERTEX_ATTR_EAR_CLIP)
536 {
537 _AL_LIST_ITEM* start;
538 _AL_LIST* search_list;
539 size_t size;
540
541 if (reflex) {
542
543 search_list = reflex;
544 size = _al_list_size(search_list);
545 start = _al_list_front(reflex);
546 }
547 else {
548 search_list = vertices;
549 size = _al_list_size(search_list) - 3;
550 start = _al_list_next_circular(search_list, next);
551 }
552
553 // Check for ear vertex.
554 point = start;
555 for (i = 0; i < size; ++i, point = _al_list_next_circular(search_list, point)) {
556
557 float* v;
558
559 // TODO: optimize this by removing if
560 if (search_list == reflex)
561 v = (float*)_al_list_item_data((_AL_LIST_ITEM*)_al_list_item_data(point));
562 else
563 v = (float*)_al_list_item_data(point);
564
565 // Ignore vertices which belong to the triangle.
566 if ((v == v0) || (v == v1) || (v == v2))
567 continue;
568
569 // Set point to NULL if we find any point inside the triangle.
570 if (_al_prim_is_point_in_triangle(v, v0, v1, v2)) {
571 point = NULL;
572 break;
573 }
574 }
575
576 // If point is not NULL, we have ear vertex.
577 if ((NULL != point) || _al_list_is_empty(search_list))
578 result |= POLY_VERTEX_ATTR_EAR_CLIP;
579 }
580 }
581 else if (flags & POLY_VERTEX_ATTR_REFLEX)
582 result |= POLY_VERTEX_ATTR_REFLEX;
583
584 return result;
585 }
586
587
588 /*
589 * Classify all vertices into reflex or ear group.
590 *
591 * One of target group may be NULL so it will be simply ignored.
592 */
poly_classify_vertices(_AL_LIST * vertices,_AL_LIST * reflex,_AL_LIST * ear)593 static void poly_classify_vertices(_AL_LIST* vertices, _AL_LIST* reflex, _AL_LIST* ear)
594 {
595 poly_classify_vertices_in_range(_al_list_front(vertices), NULL, vertices, reflex, ear);
596 }
597
598
599 /*
600 * Classify selected range of vertices [begin, end) into
601 * reflex or ear group.
602 *
603 * One of target group may be NULL so it will be simply ignored.
604 */
poly_classify_vertices_in_range(_AL_LIST_ITEM * begin,_AL_LIST_ITEM * end,_AL_LIST * vertices,_AL_LIST * reflex,_AL_LIST * ear)605 static void poly_classify_vertices_in_range(_AL_LIST_ITEM* begin, _AL_LIST_ITEM* end, _AL_LIST* vertices, _AL_LIST* reflex, _AL_LIST* ear)
606 {
607 _AL_LIST_ITEM* item = NULL;
608 int attribute_mask = 0;
609
610 if (NULL != ear)
611 attribute_mask |= POLY_VERTEX_ATTR_EAR_CLIP;
612
613 if (NULL != reflex)
614 attribute_mask |= POLY_VERTEX_ATTR_REFLEX;
615
616 for (item = begin; item != end; item = _al_list_next(vertices, item))
617 {
618 int attr = poly_compute_vertex_attributes(vertices, item, attribute_mask, NULL);
619
620 if (0 == attr)
621 continue;
622
623 if (attr & POLY_VERTEX_ATTR_EAR_CLIP)
624 _al_list_push_back(ear, item);
625
626 if (attr & POLY_VERTEX_ATTR_REFLEX)
627 _al_list_push_back(reflex, item);
628 }
629 }
630
631
632 /*
633 * Reclassify vertex. After triangle was emitted one vertex
634 * is removed from the list. Two neighbor vertices may
635 * change their attributes. In this place we have general
636 * function which update lists to match new attributes
637 * of provided vertex.
638 */
poly_update_vertex_attributes(_AL_LIST * vertices,_AL_LIST * reflex,_AL_LIST * ear,_AL_LIST_ITEM * vertex)639 static void poly_update_vertex_attributes(_AL_LIST* vertices, _AL_LIST* reflex, _AL_LIST* ear, _AL_LIST_ITEM* vertex)
640 {
641 _AL_LIST_ITEM* item;
642
643 int attr = poly_compute_vertex_attributes(vertices, vertex, POLY_VERTEX_ATTR_ALL, reflex);
644
645 // Update reflex list only if an attribute change.
646 item = _al_list_find_first(reflex, vertex);
647 if (attr & POLY_VERTEX_ATTR_REFLEX) {
648
649 if (NULL == item)
650 _al_list_push_back(reflex, vertex);
651
652 _al_list_remove(ear, vertex);
653 }
654 else {
655
656 if (NULL != item)
657 _al_list_erase(reflex, item);
658
659 item = _al_list_find_first(ear, vertex);
660 if (attr & POLY_VERTEX_ATTR_EAR_CLIP) {
661
662 if (NULL == item)
663 _al_list_push_front(ear, vertex);
664 }
665 else {
666
667 if (NULL != item)
668 _al_list_erase(ear, item);
669 }
670 }
671 }
672
673
674 /*
675 * Triangulator iterate trough list of ear vertices
676 * and clip isolated triangles. This process repeats
677 * until there are ear vertices.
678 */
poly_do_triangulate(POLY * polygon)679 static void poly_do_triangulate(POLY* polygon)
680 {
681 # define VERTEX_INDEX(vertex) ((((uint8_t*)vertex) - ((uint8_t*)polygon->vertex_buffer)) / polygon->vertex_stride)
682
683 # if POLY_DEBUG
684 g_poly_debug_step_current = 0;
685
686 {
687 _AL_LIST_ITEM* item;
688 _AL_LIST_ITEM* next;
689 int* histogram = al_calloc(_al_list_size(polygon->vertex_list), sizeof(int));
690
691 /*std::map<float*, int> histogram;*/
692
693 int index = 0;
694 for (item = _al_list_front(polygon->vertex_list); item; item = _al_list_next(polygon->vertex_list, item)) {
695
696 float* point0;
697 float* point1;
698 float n[2];
699 float l, r;
700 char status[3] = { 0 };
701 int status_index = 0;
702
703 next = _al_list_next_circular(polygon->vertex_list, item);
704
705 point0 = (float*)_al_list_item_data(item);
706 point1 = (float*)_al_list_item_data(next);
707
708 n[0] = -(point1[1] - point0[1]);
709 n[1] = point1[0] - point0[0];
710
711 l = 2.0f * sqrtf(n[0] * n[0] + n[1] * n[1]);
712
713 n[0] /= l;
714 n[1] /= l;
715
716 r = 1.0f * 0.0f;
717
718 al_draw_line(point0[0] + n[0] * r, point0[1] + n[1] * r, point1[0] + n[0] * r, point1[1] + n[1] * r, al_map_rgba(255, 0, 255, 128), r * g_poly_debug_scale);
719
720 if (_al_list_contains(polygon->reflex_list, item))
721 status[status_index++] = 'R';
722 if (_al_list_contains(polygon->ear_list, item))
723 status[status_index++] = 'E';
724
725 POLY_DEBUG_TEXT_LINE(point0[0], point0[1], -histogram[VERTEX_INDEX(point0)], "%s %d", status, index++);
726
727 ++histogram[VERTEX_INDEX(point0)];
728 }
729
730 al_free(histogram);
731 }
732 # endif
733
734 // Repeat until there are ear clips.
735 while (!_al_list_is_empty(polygon->ear_list)) {
736
737 _AL_LIST_ITEM* ear_item;
738 _AL_LIST_ITEM* vertex_item;
739 _AL_LIST_ITEM* next;
740 _AL_LIST_ITEM* prev;
741 float* v0;
742 float* v1;
743 float* v2;
744
745 // Get point and corresponding item on polygon->vertex_list list.
746 ear_item = _al_list_front(polygon->ear_list);
747 vertex_item = (_AL_LIST_ITEM*)_al_list_item_data(ear_item);
748 prev = _al_list_previous_circular(polygon->vertex_list, vertex_item);
749 next = _al_list_next_circular(polygon->vertex_list, vertex_item);
750 v0 = (float*)_al_list_item_data(prev);
751 v1 = (float*)_al_list_item_data(vertex_item);
752 v2 = (float*)_al_list_item_data(next);
753
754 # if POLY_DEBUG
755 if (g_poly_debug_step == g_poly_debug_step_current) {
756 _AL_LIST_ITEM* item;
757 ALLEGRO_COLOR color;
758 int second = 0;
759
760 al_draw_filled_triangle(v0[0], v0[1], v1[0], v1[1], v2[0], v2[1], al_map_rgba(0, 0, 255, 64));
761
762 for (item = _al_list_front(polygon->vertex_list); item; item = _al_list_next(polygon->vertex_list, item)) {
763
764 float* point = (float*)_al_list_item_data(item);
765 al_draw_filled_circle(point[0], point[1], 6.0f * g_poly_debug_scale, al_map_rgb(255, 255, 255));
766 }
767
768 for (item = _al_list_front(polygon->reflex_list); item; item = _al_list_next(polygon->reflex_list, item)) {
769
770 float* point = (float*)_al_list_item_data((_AL_LIST_ITEM*)_al_list_item_data(item));
771
772 al_draw_filled_circle(point[0], point[1], 6.0f * g_poly_debug_scale, al_map_rgb(255, 255, 0));
773 }
774
775 color = al_map_rgb(255, 0, 0);
776 second = _al_list_size(polygon->ear_list) - 1;
777 for (item = _al_list_back(polygon->ear_list); item; item = _al_list_previous(polygon->ear_list, item), --second) {
778
779 float* point = (float*)_al_list_item_data((_AL_LIST_ITEM*)_al_list_item_data(item));
780
781 if (second == 0)
782 color = al_map_rgb(0, 255, 0);
783 else if (second == 1)
784 color = al_map_rgb(0, 0, 255);
785
786 al_draw_circle(point[0], point[1], 9.0f * g_poly_debug_scale, color, 2.0f * g_poly_debug_scale);
787 }
788 }
789 if (g_poly_debug_step >= 0 && g_poly_debug_step_current >= g_poly_debug_step)
790 break;
791 g_poly_debug_step_current++;
792 # endif
793
794 // Emit triangle.
795 polygon->emit(VERTEX_INDEX(v0), VERTEX_INDEX(v1), VERTEX_INDEX(v2), polygon->userdata);
796
797 // Remove polygon->ear_list clip from all lists.
798 _al_list_erase(polygon->ear_list, ear_item);
799 _al_list_erase(polygon->vertex_list, vertex_item);
800 _al_list_erase(polygon->reflex_list, _al_list_find_first(polygon->reflex_list, vertex_item));
801
802 // Update attributes of corner vertices.
803 poly_update_vertex_attributes(polygon->vertex_list, polygon->reflex_list, polygon->ear_list, prev);
804 poly_update_vertex_attributes(polygon->vertex_list, polygon->reflex_list, polygon->ear_list, next);
805 }
806
807 # undef VERTEX_INDEX
808 }
809
810
811 /* Function: al_triangulate_polygon
812 * General triangulation function.
813 */
al_triangulate_polygon(const float * vertices,size_t vertex_stride,const int * vertex_counts,void (* emit_triangle)(int,int,int,void *),void * userdata)814 bool al_triangulate_polygon(
815 const float* vertices, size_t vertex_stride, const int* vertex_counts,
816 void (*emit_triangle)(int, int, int, void*), void* userdata)
817 {
818 POLY polygon;
819 int vertex_count;
820 int split_count;
821 int *splits;
822 int i;
823 bool ret;
824
825 for (i = 0; vertex_counts[i] > 0; i++) {
826 /* do nothing */
827 }
828 ASSERT(i > 0);
829 split_count = i;
830
831 splits = malloc(split_count * sizeof(int));
832 if (!splits) {
833 return false;
834 }
835 vertex_count = 0;
836 for (i = 0; i < split_count; i++) {
837 vertex_count += vertex_counts[i];
838 splits[i] = vertex_count;
839 }
840
841 memset(&polygon, 0, sizeof(polygon));
842 polygon.vertex_buffer = vertices;
843 polygon.vertex_stride = vertex_stride;
844 polygon.vertex_count = vertex_count;
845 polygon.split_indices = splits;
846 polygon.split_stride = sizeof(int); /* XXX can simplify code now */
847 polygon.split_count = split_count;
848 polygon.emit = emit_triangle;
849 polygon.userdata = userdata;
850
851 if (poly_initialize(&polygon)) {
852
853 poly_do_triangulate(&polygon);
854
855 _al_list_destroy(polygon.vertex_list);
856 _al_list_destroy(polygon.reflex_list);
857 _al_list_destroy(polygon.ear_list);
858
859 ret = true;
860 }
861 else {
862 ret = false;
863 }
864
865 free(splits);
866
867 return ret;
868 }
869
870 /* vim: set sts=3 sw=3 et: */
871