1 /* Libart_LGPL - library of basic graphic primitives
2 * Copyright (C) 2001 Raph Levien
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
18 */
19
20 /* This file contains a testbed implementation of the new intersection
21 code.
22 */
23
24 #include "config.h"
25 #include "art_svp_intersect.h"
26
27 #include <math.h> /* for sqrt */
28
29 /* Sanitychecking verifies the main invariant on every priority queue
30 point. Do not use in production, as it slows things down way too
31 much. */
32 #define noSANITYCHECK
33
34 /* This can be used in production, to prevent hangs. Eventually, it
35 should not be necessary. */
36 #define CHEAP_SANITYCHECK
37
38 #define noVERBOSE
39
40 #include "art_misc.h"
41
42 /* A priority queue - perhaps move to a separate file if it becomes
43 needed somewhere else */
44
45 #define ART_PRIQ_USE_HEAP
46
47 typedef struct _ArtPriQ ArtPriQ;
48 typedef struct _ArtPriPoint ArtPriPoint;
49
50 struct _ArtPriQ {
51 int n_items;
52 int n_items_max;
53 ArtPriPoint **items;
54 };
55
56 struct _ArtPriPoint {
57 double x;
58 double y;
59 void *user_data;
60 };
61
62 static ArtPriQ *
art_pri_new(void)63 art_pri_new (void)
64 {
65 ArtPriQ *result = art_new (ArtPriQ, 1);
66
67 result->n_items = 0;
68 result->n_items_max = 16;
69 result->items = art_new (ArtPriPoint *, result->n_items_max);
70 return result;
71 }
72
73 static void
art_pri_free(ArtPriQ * pq)74 art_pri_free (ArtPriQ *pq)
75 {
76 art_free (pq->items);
77 art_free (pq);
78 }
79
80 static art_boolean
art_pri_empty(ArtPriQ * pq)81 art_pri_empty (ArtPriQ *pq)
82 {
83 return pq->n_items == 0;
84 }
85
86 #ifdef ART_PRIQ_USE_HEAP
87
88 /* This heap implementation is based on Vasek Chvatal's course notes:
89 http://www.cs.rutgers.edu/~chvatal/notes/pq.html#heap */
90
91 static void
art_pri_bubble_up(ArtPriQ * pq,int vacant,ArtPriPoint * missing)92 art_pri_bubble_up (ArtPriQ *pq, int vacant, ArtPriPoint *missing)
93 {
94 ArtPriPoint **items = pq->items;
95 int parent;
96
97 parent = (vacant - 1) >> 1;
98 while (vacant > 0 && (missing->y < items[parent]->y ||
99 (missing->y == items[parent]->y &&
100 missing->x < items[parent]->x)))
101 {
102 items[vacant] = items[parent];
103 vacant = parent;
104 parent = (vacant - 1) >> 1;
105 }
106
107 items[vacant] = missing;
108 }
109
110 static void
art_pri_insert(ArtPriQ * pq,ArtPriPoint * point)111 art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
112 {
113 if (pq->n_items == pq->n_items_max)
114 art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
115
116 art_pri_bubble_up (pq, pq->n_items++, point);
117 }
118
119 static void
art_pri_sift_down_from_root(ArtPriQ * pq,ArtPriPoint * missing)120 art_pri_sift_down_from_root (ArtPriQ *pq, ArtPriPoint *missing)
121 {
122 ArtPriPoint **items = pq->items;
123 int vacant = 0, child = 2;
124 int n = pq->n_items;
125
126 while (child < n)
127 {
128 if (items[child - 1]->y < items[child]->y ||
129 (items[child - 1]->y == items[child]->y &&
130 items[child - 1]->x < items[child]->x))
131 child--;
132 items[vacant] = items[child];
133 vacant = child;
134 child = (vacant + 1) << 1;
135 }
136 if (child == n)
137 {
138 items[vacant] = items[n - 1];
139 vacant = n - 1;
140 }
141
142 art_pri_bubble_up (pq, vacant, missing);
143 }
144
145 static ArtPriPoint *
art_pri_choose(ArtPriQ * pq)146 art_pri_choose (ArtPriQ *pq)
147 {
148 ArtPriPoint *result = pq->items[0];
149
150 art_pri_sift_down_from_root (pq, pq->items[--pq->n_items]);
151 return result;
152 }
153
154 #else
155
156 /* Choose least point in queue */
157 static ArtPriPoint *
art_pri_choose(ArtPriQ * pq)158 art_pri_choose (ArtPriQ *pq)
159 {
160 int i;
161 int best = 0;
162 double best_x, best_y;
163 double y;
164 ArtPriPoint *result;
165
166 if (pq->n_items == 0)
167 return NULL;
168
169 best_x = pq->items[best]->x;
170 best_y = pq->items[best]->y;
171
172 for (i = 1; i < pq->n_items; i++)
173 {
174 y = pq->items[i]->y;
175 if (y < best_y || (y == best_y && pq->items[i]->x < best_x))
176 {
177 best = i;
178 best_x = pq->items[best]->x;
179 best_y = y;
180 }
181 }
182 result = pq->items[best];
183 pq->items[best] = pq->items[--pq->n_items];
184 return result;
185 }
186
187 static void
art_pri_insert(ArtPriQ * pq,ArtPriPoint * point)188 art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
189 {
190 if (pq->n_items == pq->n_items_max)
191 art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
192
193 pq->items[pq->n_items++] = point;
194 }
195
196 #endif
197
198 #ifdef TEST_PRIQ
199
200 #include <stdlib.h> /* for rand() */
201 #include <stdio.h>
202
203 static double
double_rand(double lo,double hi,int quant)204 double_rand (double lo, double hi, int quant)
205 {
206 int tmp = rand () / (RAND_MAX * (1.0 / quant)) + 0.5;
207 return lo + tmp * ((hi - lo) / quant);
208 }
209
210 /*
211 * This custom allocator for priority queue points is here so I can
212 * test speed. It doesn't look like it will be that significant, but
213 * if I want a small improvement later, it's something.
214 */
215
216 typedef ArtPriPoint *ArtPriPtPool;
217
218 static ArtPriPtPool *
art_pri_pt_pool_new(void)219 art_pri_pt_pool_new (void)
220 {
221 ArtPriPtPool *result = art_new (ArtPriPtPool, 1);
222 *result = NULL;
223 return result;
224 }
225
226 static ArtPriPoint *
art_pri_pt_alloc(ArtPriPtPool * pool)227 art_pri_pt_alloc (ArtPriPtPool *pool)
228 {
229 ArtPriPoint *result = *pool;
230 if (result == NULL)
231 return art_new (ArtPriPoint, 1);
232 else
233 {
234 *pool = result->user_data;
235 return result;
236 }
237 }
238
239 static void
art_pri_pt_free(ArtPriPtPool * pool,ArtPriPoint * pt)240 art_pri_pt_free (ArtPriPtPool *pool, ArtPriPoint *pt)
241 {
242 pt->user_data = *pool;
243 *pool = pt;
244 }
245
246 static void
art_pri_pt_pool_free(ArtPriPtPool * pool)247 art_pri_pt_pool_free (ArtPriPtPool *pool)
248 {
249 ArtPriPoint *pt = *pool;
250 while (pt != NULL)
251 {
252 ArtPriPoint *next = pt->user_data;
253 art_free (pt);
254 pt = next;
255 }
256 art_free (pool);
257 }
258
259 int
main(int argc,char ** argv)260 main (int argc, char **argv)
261 {
262 ArtPriPtPool *pool = art_pri_pt_pool_new ();
263 ArtPriQ *pq;
264 int i, j;
265 const int n_iter = 1;
266 const int pq_size = 100;
267
268 for (j = 0; j < n_iter; j++)
269 {
270 pq = art_pri_new ();
271
272 for (i = 0; i < pq_size; i++)
273 {
274 ArtPriPoint *pt = art_pri_pt_alloc (pool);
275 pt->x = double_rand (0, 1, 100);
276 pt->y = double_rand (0, 1, 100);
277 pt->user_data = (void *)i;
278 art_pri_insert (pq, pt);
279 }
280
281 while (!art_pri_empty (pq))
282 {
283 ArtPriPoint *pt = art_pri_choose (pq);
284 if (n_iter == 1)
285 printf ("(%g, %g), %d\n", pt->x, pt->y, (int)pt->user_data);
286 art_pri_pt_free (pool, pt);
287 }
288
289 art_pri_free (pq);
290 }
291 art_pri_pt_pool_free (pool);
292 return 0;
293 }
294
295 #else /* TEST_PRIQ */
296
297 /* A virtual class for an "svp writer". A client of this object creates an
298 SVP by repeatedly calling "add segment" and "add point" methods on it.
299 */
300
301 typedef struct _ArtSvpWriterRewind ArtSvpWriterRewind;
302
303 /* An implementation of the svp writer virtual class that applies the
304 winding rule. */
305
306 struct _ArtSvpWriterRewind {
307 ArtSvpWriter super;
308 ArtWindRule rule;
309 ArtSVP *svp;
310 int n_segs_max;
311 int *n_points_max;
312 };
313
314 static int
art_svp_writer_rewind_add_segment(ArtSvpWriter * self,int wind_left,int delta_wind,double x,double y)315 art_svp_writer_rewind_add_segment (ArtSvpWriter *self, int wind_left,
316 int delta_wind, double x, double y)
317 {
318 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
319 ArtSVP *svp;
320 ArtSVPSeg *seg;
321 art_boolean left_filled, right_filled;
322 int wind_right = wind_left + delta_wind;
323 int seg_num;
324 const int init_n_points_max = 4;
325
326 switch (swr->rule)
327 {
328 case ART_WIND_RULE_NONZERO:
329 left_filled = (wind_left != 0);
330 right_filled = (wind_right != 0);
331 break;
332 case ART_WIND_RULE_INTERSECT:
333 left_filled = (wind_left > 1);
334 right_filled = (wind_right > 1);
335 break;
336 case ART_WIND_RULE_ODDEVEN:
337 left_filled = (wind_left & 1);
338 right_filled = (wind_right & 1);
339 break;
340 case ART_WIND_RULE_POSITIVE:
341 left_filled = (wind_left > 0);
342 right_filled = (wind_right > 0);
343 break;
344 default:
345 art_die ("Unknown wind rule %d\n", swr->rule);
346 }
347 if (left_filled == right_filled)
348 {
349 /* discard segment now */
350 #ifdef VERBOSE
351 art_dprint ("swr add_segment: %d += %d (%g, %g) --> -1\n",
352 wind_left, delta_wind, x, y);
353 #endif
354 return -1;
355 }
356
357 svp = swr->svp;
358 seg_num = svp->n_segs++;
359 if (swr->n_segs_max == seg_num)
360 {
361 swr->n_segs_max <<= 1;
362 svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
363 (swr->n_segs_max - 1) *
364 sizeof(ArtSVPSeg));
365 swr->svp = svp;
366 swr->n_points_max = art_renew (swr->n_points_max, int,
367 swr->n_segs_max);
368 }
369 seg = &svp->segs[seg_num];
370 seg->n_points = 1;
371 seg->dir = right_filled;
372 swr->n_points_max[seg_num] = init_n_points_max;
373 seg->bbox.x0 = x;
374 seg->bbox.y0 = y;
375 seg->bbox.x1 = x;
376 seg->bbox.y1 = y;
377 seg->points = art_new (ArtPoint, init_n_points_max);
378 seg->points[0].x = x;
379 seg->points[0].y = y;
380 #ifdef VERBOSE
381 art_dprint ("swr add_segment: %d += %d (%g, %g) --> %d(%s)\n",
382 wind_left, delta_wind, x, y, seg_num,
383 seg->dir ? "v" : "^");
384 #endif
385 return seg_num;
386 }
387
388 static void
art_svp_writer_rewind_add_point(ArtSvpWriter * self,int seg_id,double x,double y)389 art_svp_writer_rewind_add_point (ArtSvpWriter *self, int seg_id,
390 double x, double y)
391 {
392 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
393 ArtSVPSeg *seg;
394 int n_points;
395
396 #ifdef VERBOSE
397 art_dprint ("swr add_point: %d (%g, %g)\n", seg_id, x, y);
398 #endif
399 if (seg_id < 0)
400 /* omitted segment */
401 return;
402
403 seg = &swr->svp->segs[seg_id];
404 n_points = seg->n_points++;
405 if (swr->n_points_max[seg_id] == n_points)
406 art_expand (seg->points, ArtPoint, swr->n_points_max[seg_id]);
407 seg->points[n_points].x = x;
408 seg->points[n_points].y = y;
409 if (x < seg->bbox.x0)
410 seg->bbox.x0 = x;
411 if (x > seg->bbox.x1)
412 seg->bbox.x1 = x;
413 seg->bbox.y1 = y;
414 }
415
416 static void
art_svp_writer_rewind_close_segment(ArtSvpWriter * self,int seg_id)417 art_svp_writer_rewind_close_segment (ArtSvpWriter *self, int seg_id)
418 {
419 /* Not needed for this simple implementation. A potential future
420 optimization is to merge segments that can be merged safely. */
421 #ifdef SANITYCHECK
422 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
423 ArtSVPSeg *seg;
424
425 if (seg_id >= 0)
426 {
427 seg = &swr->svp->segs[seg_id];
428 if (seg->n_points < 2)
429 art_warn ("*** closing segment %d with only %d point%s\n",
430 seg_id, seg->n_points, seg->n_points == 1 ? "" : "s");
431 }
432 #endif
433
434 #ifdef VERBOSE
435 art_dprint ("swr close_segment: %d\n", seg_id);
436 #endif
437 }
438
439 ArtSVP *
art_svp_writer_rewind_reap(ArtSvpWriter * self)440 art_svp_writer_rewind_reap (ArtSvpWriter *self)
441 {
442 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
443 ArtSVP *result = swr->svp;
444
445 art_free (swr->n_points_max);
446 art_free (swr);
447 return result;
448 }
449
450 ArtSvpWriter *
art_svp_writer_rewind_new(ArtWindRule rule)451 art_svp_writer_rewind_new (ArtWindRule rule)
452 {
453 ArtSvpWriterRewind *result = art_new (ArtSvpWriterRewind, 1);
454
455 result->super.add_segment = art_svp_writer_rewind_add_segment;
456 result->super.add_point = art_svp_writer_rewind_add_point;
457 result->super.close_segment = art_svp_writer_rewind_close_segment;
458
459 result->rule = rule;
460 result->n_segs_max = 16;
461 result->svp = art_alloc (sizeof(ArtSVP) +
462 (result->n_segs_max - 1) * sizeof(ArtSVPSeg));
463 result->svp->n_segs = 0;
464 result->n_points_max = art_new (int, result->n_segs_max);
465
466 return &result->super;
467 }
468
469 /* Now, data structures for the active list */
470
471 typedef struct _ArtActiveSeg ArtActiveSeg;
472
473 /* Note: BNEG is 1 for \ lines, and 0 for /. Thus,
474 x[(flags & BNEG) ^ 1] <= x[flags & BNEG] */
475 #define ART_ACTIVE_FLAGS_BNEG 1
476
477 /* This flag is set if the segment has been inserted into the active
478 list. */
479 #define ART_ACTIVE_FLAGS_IN_ACTIVE 2
480
481 /* This flag is set when the segment is to be deleted in the
482 horiz commit process. */
483 #define ART_ACTIVE_FLAGS_DEL 4
484
485 /* This flag is set if the seg_id is a valid output segment. */
486 #define ART_ACTIVE_FLAGS_OUT 8
487
488 /* This flag is set if the segment is in the horiz list. */
489 #define ART_ACTIVE_FLAGS_IN_HORIZ 16
490
491 struct _ArtActiveSeg {
492 int flags;
493 int wind_left, delta_wind;
494 ArtActiveSeg *left, *right; /* doubly linked list structure */
495
496 const ArtSVPSeg *in_seg;
497 int in_curs;
498
499 double x[2];
500 double y0, y1;
501 double a, b, c; /* line equation; ax+by+c = 0 for the line, a^2 + b^2 = 1,
502 and a>0 */
503
504 /* bottom point and intersection point stack */
505 int n_stack;
506 int n_stack_max;
507 ArtPoint *stack;
508
509 /* horiz commit list */
510 ArtActiveSeg *horiz_left, *horiz_right;
511 double horiz_x;
512 int horiz_delta_wind;
513 int seg_id;
514 };
515
516 typedef struct _ArtIntersectCtx ArtIntersectCtx;
517
518 struct _ArtIntersectCtx {
519 const ArtSVP *in;
520 ArtSvpWriter *out;
521
522 ArtPriQ *pq;
523
524 ArtActiveSeg *active_head;
525
526 double y;
527 ArtActiveSeg *horiz_first;
528 ArtActiveSeg *horiz_last;
529
530 /* segment index of next input segment to be added to pri q */
531 int in_curs;
532 };
533
534 #define EPSILON_A 1e-5 /* Threshold for breaking lines at point insertions */
535
536 /**
537 * art_svp_intersect_setup_seg: Set up an active segment from input segment.
538 * @seg: Active segment.
539 * @pri_pt: Priority queue point to initialize.
540 *
541 * Sets the x[], a, b, c, flags, and stack fields according to the
542 * line from the current cursor value. Sets the priority queue point
543 * to the bottom point of this line. Also advances the input segment
544 * cursor.
545 **/
546 static void
art_svp_intersect_setup_seg(ArtActiveSeg * seg,ArtPriPoint * pri_pt)547 art_svp_intersect_setup_seg (ArtActiveSeg *seg, ArtPriPoint *pri_pt)
548 {
549 const ArtSVPSeg *in_seg = seg->in_seg;
550 int in_curs = seg->in_curs++;
551 double x0, y0, x1, y1;
552 double dx, dy, s;
553 double a, b, r2;
554
555 x0 = in_seg->points[in_curs].x;
556 y0 = in_seg->points[in_curs].y;
557 x1 = in_seg->points[in_curs + 1].x;
558 y1 = in_seg->points[in_curs + 1].y;
559 pri_pt->x = x1;
560 pri_pt->y = y1;
561 dx = x1 - x0;
562 dy = y1 - y0;
563 r2 = dx * dx + dy * dy;
564 s = r2 == 0 ? 1 : 1 / sqrt (r2);
565 seg->a = a = dy * s;
566 seg->b = b = -dx * s;
567 seg->c = -(a * x0 + b * y0);
568 seg->flags = (seg->flags & ~ART_ACTIVE_FLAGS_BNEG) | (dx > 0);
569 seg->x[0] = x0;
570 seg->x[1] = x1;
571 seg->y0 = y0;
572 seg->y1 = y1;
573 seg->n_stack = 1;
574 seg->stack[0].x = x1;
575 seg->stack[0].y = y1;
576 }
577
578 /**
579 * art_svp_intersect_add_horiz: Add point to horizontal list.
580 * @ctx: Intersector context.
581 * @seg: Segment with point to insert into horizontal list.
582 *
583 * Inserts @seg into horizontal list, keeping it in ascending horiz_x
584 * order.
585 *
586 * Note: the horiz_commit routine processes "clusters" of segs in the
587 * horiz list, all sharing the same horiz_x value. The cluster is
588 * processed in active list order, rather than horiz list order. Thus,
589 * the order of segs in the horiz list sharing the same horiz_x
590 * _should_ be irrelevant. Even so, we use b as a secondary sorting key,
591 * as a "belt and suspenders" defensive coding tactic.
592 **/
593 static void
art_svp_intersect_add_horiz(ArtIntersectCtx * ctx,ArtActiveSeg * seg)594 art_svp_intersect_add_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
595 {
596 ArtActiveSeg **pp = &ctx->horiz_last;
597 ArtActiveSeg *place;
598 ArtActiveSeg *place_right = NULL;
599
600
601 #ifdef CHEAP_SANITYCHECK
602 if (seg->flags & ART_ACTIVE_FLAGS_IN_HORIZ)
603 {
604 art_warn ("*** attempt to put segment in horiz list twice\n");
605 return;
606 }
607 seg->flags |= ART_ACTIVE_FLAGS_IN_HORIZ;
608 #endif
609
610 #ifdef VERBOSE
611 art_dprint ("add_horiz %lx, x = %g\n", (unsigned long) seg, seg->horiz_x);
612 #endif
613 for (place = *pp; place != NULL && (place->horiz_x > seg->horiz_x ||
614 (place->horiz_x == seg->horiz_x &&
615 place->b < seg->b));
616 place = *pp)
617 {
618 place_right = place;
619 pp = &place->horiz_left;
620 }
621 *pp = seg;
622 seg->horiz_left = place;
623 seg->horiz_right = place_right;
624 if (place == NULL)
625 ctx->horiz_first = seg;
626 else
627 place->horiz_right = seg;
628 }
629
630 static void
art_svp_intersect_push_pt(ArtIntersectCtx * ctx,ArtActiveSeg * seg,double x,double y)631 art_svp_intersect_push_pt (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
632 double x, double y)
633 {
634 ArtPriPoint *pri_pt;
635 int n_stack = seg->n_stack;
636
637 if (n_stack == seg->n_stack_max)
638 art_expand (seg->stack, ArtPoint, seg->n_stack_max);
639 seg->stack[n_stack].x = x;
640 seg->stack[n_stack].y = y;
641 seg->n_stack++;
642
643 seg->x[1] = x;
644 seg->y1 = y;
645
646 pri_pt = art_new (ArtPriPoint, 1);
647 pri_pt->x = x;
648 pri_pt->y = y;
649 pri_pt->user_data = seg;
650 art_pri_insert (ctx->pq, pri_pt);
651 }
652
653 typedef enum {
654 ART_BREAK_LEFT = 1,
655 ART_BREAK_RIGHT = 2
656 } ArtBreakFlags;
657
658 /**
659 * art_svp_intersect_break: Break an active segment.
660 *
661 * Note: y must be greater than the top point's y, and less than
662 * the bottom's.
663 *
664 * Return value: x coordinate of break point.
665 */
666 static double
art_svp_intersect_break(ArtIntersectCtx * ctx,ArtActiveSeg * seg,double x_ref,double y,ArtBreakFlags break_flags)667 art_svp_intersect_break (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
668 double x_ref, double y, ArtBreakFlags break_flags)
669 {
670 double x0, y0, x1, y1;
671 const ArtSVPSeg *in_seg = seg->in_seg;
672 int in_curs = seg->in_curs;
673 double x;
674
675 x0 = in_seg->points[in_curs - 1].x;
676 y0 = in_seg->points[in_curs - 1].y;
677 x1 = in_seg->points[in_curs].x;
678 y1 = in_seg->points[in_curs].y;
679 x = x0 + (x1 - x0) * ((y - y0) / (y1 - y0));
680 if ((break_flags == ART_BREAK_LEFT && x > x_ref) ||
681 (break_flags == ART_BREAK_RIGHT && x < x_ref))
682 {
683 #ifdef VERBOSE
684 art_dprint ("art_svp_intersect_break: limiting x to %f, was %f, %s\n",
685 x_ref, x, break_flags == ART_BREAK_LEFT ? "left" : "right");
686 x = x_ref;
687 #endif
688 }
689
690 /* I think we can count on min(x0, x1) <= x <= max(x0, x1) with sane
691 arithmetic, but it might be worthwhile to check just in case. */
692
693 if (y > ctx->y)
694 art_svp_intersect_push_pt (ctx, seg, x, y);
695 else
696 {
697 seg->x[0] = x;
698 seg->y0 = y;
699 seg->horiz_x = x;
700 art_svp_intersect_add_horiz (ctx, seg);
701 }
702
703 return x;
704 }
705
706 /**
707 * art_svp_intersect_add_point: Add a point, breaking nearby neighbors.
708 * @ctx: Intersector context.
709 * @x: X coordinate of point to add.
710 * @y: Y coordinate of point to add.
711 * @seg: "nearby" segment, or NULL if leftmost.
712 *
713 * Return value: Segment immediately to the left of the new point, or
714 * NULL if the new point is leftmost.
715 **/
716 static ArtActiveSeg *
art_svp_intersect_add_point(ArtIntersectCtx * ctx,double x,double y,ArtActiveSeg * seg,ArtBreakFlags break_flags)717 art_svp_intersect_add_point (ArtIntersectCtx *ctx, double x, double y,
718 ArtActiveSeg *seg, ArtBreakFlags break_flags)
719 {
720 ArtActiveSeg *left, *right;
721 double x_min = x, x_max = x;
722 art_boolean left_live, right_live;
723 double d;
724 double new_x;
725 ArtActiveSeg *test, *result = NULL;
726 double x_test;
727
728 left = seg;
729 if (left == NULL)
730 right = ctx->active_head;
731 else
732 right = left->right;
733 left_live = (break_flags & ART_BREAK_LEFT) && (left != NULL);
734 right_live = (break_flags & ART_BREAK_RIGHT) && (right != NULL);
735 while (left_live || right_live)
736 {
737 if (left_live)
738 {
739 if (x <= left->x[left->flags & ART_ACTIVE_FLAGS_BNEG] &&
740 /* It may be that one of these conjuncts turns out to be always
741 true. We test both anyway, to be defensive. */
742 y != left->y0 && y < left->y1)
743 {
744 d = x_min * left->a + y * left->b + left->c;
745 if (d < EPSILON_A)
746 {
747 new_x = art_svp_intersect_break (ctx, left, x_min, y,
748 ART_BREAK_LEFT);
749 if (new_x > x_max)
750 {
751 x_max = new_x;
752 right_live = (right != NULL);
753 }
754 else if (new_x < x_min)
755 x_min = new_x;
756 left = left->left;
757 left_live = (left != NULL);
758 }
759 else
760 left_live = ART_FALSE;
761 }
762 else
763 left_live = ART_FALSE;
764 }
765 else if (right_live)
766 {
767 if (x >= right->x[(right->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] &&
768 /* It may be that one of these conjuncts turns out to be always
769 true. We test both anyway, to be defensive. */
770 y != right->y0 && y < right->y1)
771 {
772 d = x_max * right->a + y * right->b + right->c;
773 if (d > -EPSILON_A)
774 {
775 new_x = art_svp_intersect_break (ctx, right, x_max, y,
776 ART_BREAK_RIGHT);
777 if (new_x < x_min)
778 {
779 x_min = new_x;
780 left_live = (left != NULL);
781 }
782 else if (new_x >= x_max)
783 x_max = new_x;
784 right = right->right;
785 right_live = (right != NULL);
786 }
787 else
788 right_live = ART_FALSE;
789 }
790 else
791 right_live = ART_FALSE;
792 }
793 }
794
795 /* Ascending order is guaranteed by break_flags. Thus, we don't need
796 to actually fix up non-ascending pairs. */
797
798 /* Now, (left, right) defines an interval of segments broken. Sort
799 into ascending x order. */
800 test = left == NULL ? ctx->active_head : left->right;
801 result = left;
802 if (test != NULL && test != right)
803 {
804 if (y == test->y0)
805 x_test = test->x[0];
806 else /* assert y == test->y1, I think */
807 x_test = test->x[1];
808 for (;;)
809 {
810 if (x_test <= x)
811 result = test;
812 test = test->right;
813 if (test == right)
814 break;
815 new_x = x_test;
816 if (new_x < x_test)
817 {
818 art_warn ("art_svp_intersect_add_point: non-ascending x\n");
819 }
820 x_test = new_x;
821 }
822 }
823 return result;
824 }
825
826 static void
art_svp_intersect_swap_active(ArtIntersectCtx * ctx,ArtActiveSeg * left_seg,ArtActiveSeg * right_seg)827 art_svp_intersect_swap_active (ArtIntersectCtx *ctx,
828 ArtActiveSeg *left_seg, ArtActiveSeg *right_seg)
829 {
830 right_seg->left = left_seg->left;
831 if (right_seg->left != NULL)
832 right_seg->left->right = right_seg;
833 else
834 ctx->active_head = right_seg;
835 left_seg->right = right_seg->right;
836 if (left_seg->right != NULL)
837 left_seg->right->left = left_seg;
838 left_seg->left = right_seg;
839 right_seg->right = left_seg;
840 }
841
842 /**
843 * art_svp_intersect_test_cross: Test crossing of a pair of active segments.
844 * @ctx: Intersector context.
845 * @left_seg: Left segment of the pair.
846 * @right_seg: Right segment of the pair.
847 * @break_flags: Flags indicating whether to break neighbors.
848 *
849 * Tests crossing of @left_seg and @right_seg. If there is a crossing,
850 * inserts the intersection point into both segments.
851 *
852 * Return value: True if the intersection took place at the current
853 * scan line, indicating further iteration is needed.
854 **/
855 static art_boolean
art_svp_intersect_test_cross(ArtIntersectCtx * ctx,ArtActiveSeg * left_seg,ArtActiveSeg * right_seg,ArtBreakFlags break_flags)856 art_svp_intersect_test_cross (ArtIntersectCtx *ctx,
857 ArtActiveSeg *left_seg, ArtActiveSeg *right_seg,
858 ArtBreakFlags break_flags)
859 {
860 double left_x0, left_y0, left_x1;
861 double left_y1 = left_seg->y1;
862 double right_y1 = right_seg->y1;
863 double d;
864
865 const ArtSVPSeg *in_seg;
866 int in_curs;
867 double d0, d1, t;
868 double x, y; /* intersection point */
869
870 #ifdef VERBOSE
871 static int count = 0;
872
873 art_dprint ("art_svp_intersect_test_cross %lx <-> %lx: count=%d\n",
874 (unsigned long)left_seg, (unsigned long)right_seg, count++);
875 #endif
876
877 if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0])
878 {
879 /* Top points of left and right segments coincide. This case
880 feels like a bit of duplication - we may want to merge it
881 with the cases below. However, this way, we're sure that this
882 logic makes only localized changes. */
883
884 if (left_y1 < right_y1)
885 {
886 /* Test left (x1, y1) against right segment */
887 double left_x1 = left_seg->x[1];
888
889 if (left_x1 <
890 right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
891 left_y1 == right_seg->y0)
892 return ART_FALSE;
893 d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
894 if (d < -EPSILON_A)
895 return ART_FALSE;
896 else if (d < EPSILON_A)
897 {
898 /* I'm unsure about the break flags here. */
899 double right_x1 = art_svp_intersect_break (ctx, right_seg,
900 left_x1, left_y1,
901 ART_BREAK_RIGHT);
902 if (left_x1 <= right_x1)
903 return ART_FALSE;
904 }
905 }
906 else if (left_y1 > right_y1)
907 {
908 /* Test right (x1, y1) against left segment */
909 double right_x1 = right_seg->x[1];
910
911 if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
912 right_y1 == left_seg->y0)
913 return ART_FALSE;
914 d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
915 if (d > EPSILON_A)
916 return ART_FALSE;
917 else if (d > -EPSILON_A)
918 {
919 /* See above regarding break flags. */
920 double left_x1 = art_svp_intersect_break (ctx, left_seg,
921 right_x1, right_y1,
922 ART_BREAK_LEFT);
923 if (left_x1 <= right_x1)
924 return ART_FALSE;
925 }
926 }
927 else /* left_y1 == right_y1 */
928 {
929 double left_x1 = left_seg->x[1];
930 double right_x1 = right_seg->x[1];
931
932 if (left_x1 <= right_x1)
933 return ART_FALSE;
934 }
935 art_svp_intersect_swap_active (ctx, left_seg, right_seg);
936 return ART_TRUE;
937 }
938
939 if (left_y1 < right_y1)
940 {
941 /* Test left (x1, y1) against right segment */
942 double left_x1 = left_seg->x[1];
943
944 if (left_x1 <
945 right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
946 left_y1 == right_seg->y0)
947 return ART_FALSE;
948 d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
949 if (d < -EPSILON_A)
950 return ART_FALSE;
951 else if (d < EPSILON_A)
952 {
953 double right_x1 = art_svp_intersect_break (ctx, right_seg,
954 left_x1, left_y1,
955 ART_BREAK_RIGHT);
956 if (left_x1 <= right_x1)
957 return ART_FALSE;
958 }
959 }
960 else if (left_y1 > right_y1)
961 {
962 /* Test right (x1, y1) against left segment */
963 double right_x1 = right_seg->x[1];
964
965 if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
966 right_y1 == left_seg->y0)
967 return ART_FALSE;
968 d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
969 if (d > EPSILON_A)
970 return ART_FALSE;
971 else if (d > -EPSILON_A)
972 {
973 double left_x1 = art_svp_intersect_break (ctx, left_seg,
974 right_x1, right_y1,
975 ART_BREAK_LEFT);
976 if (left_x1 <= right_x1)
977 return ART_FALSE;
978 }
979 }
980 else /* left_y1 == right_y1 */
981 {
982 double left_x1 = left_seg->x[1];
983 double right_x1 = right_seg->x[1];
984
985 if (left_x1 <= right_x1)
986 return ART_FALSE;
987 }
988
989 /* The segments cross. Find the intersection point. */
990
991 in_seg = left_seg->in_seg;
992 in_curs = left_seg->in_curs;
993 left_x0 = in_seg->points[in_curs - 1].x;
994 left_y0 = in_seg->points[in_curs - 1].y;
995 left_x1 = in_seg->points[in_curs].x;
996 left_y1 = in_seg->points[in_curs].y;
997 d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c;
998 d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
999 if (d0 == d1)
1000 {
1001 x = left_x0;
1002 y = left_y0;
1003 }
1004 else
1005 {
1006 /* Is this division always safe? It could possibly overflow. */
1007 t = d0 / (d0 - d1);
1008 if (t <= 0)
1009 {
1010 x = left_x0;
1011 y = left_y0;
1012 }
1013 else if (t >= 1)
1014 {
1015 x = left_x1;
1016 y = left_y1;
1017 }
1018 else
1019 {
1020 x = left_x0 + t * (left_x1 - left_x0);
1021 y = left_y0 + t * (left_y1 - left_y0);
1022 }
1023 }
1024
1025 /* Make sure intersection point is within bounds of right seg. */
1026 if (y < right_seg->y0)
1027 {
1028 x = right_seg->x[0];
1029 y = right_seg->y0;
1030 }
1031 else if (y > right_seg->y1)
1032 {
1033 x = right_seg->x[1];
1034 y = right_seg->y1;
1035 }
1036 else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1])
1037 x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1];
1038 else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG])
1039 x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG];
1040
1041 if (y == left_seg->y0)
1042 {
1043 if (y != right_seg->y0)
1044 {
1045 #ifdef VERBOSE
1046 art_dprint ("art_svp_intersect_test_cross: intersection (%g, %g) matches former y0 of %lx, %lx\n",
1047 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1048 #endif
1049 art_svp_intersect_push_pt (ctx, right_seg, x, y);
1050 if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1051 art_svp_intersect_add_point (ctx, x, y, right_seg->right,
1052 break_flags);
1053 }
1054 else
1055 {
1056 /* Intersection takes place at current scan line; process
1057 immediately rather than queueing intersection point into
1058 priq. */
1059 ArtActiveSeg *winner, *loser;
1060
1061 /* Choose "most vertical" segement */
1062 if (left_seg->a > right_seg->a)
1063 {
1064 winner = left_seg;
1065 loser = right_seg;
1066 }
1067 else
1068 {
1069 winner = right_seg;
1070 loser = left_seg;
1071 }
1072
1073 loser->x[0] = winner->x[0];
1074 loser->horiz_x = loser->x[0];
1075 loser->horiz_delta_wind += loser->delta_wind;
1076 winner->horiz_delta_wind -= loser->delta_wind;
1077
1078 art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1079 return ART_TRUE;
1080 }
1081 }
1082 else if (y == right_seg->y0)
1083 {
1084 #ifdef VERBOSE
1085 art_dprint ("*** art_svp_intersect_test_cross: intersection (%g, %g) matches latter y0 of %lx, %lx\n",
1086 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1087 #endif
1088 art_svp_intersect_push_pt (ctx, left_seg, x, y);
1089 if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1090 art_svp_intersect_add_point (ctx, x, y, left_seg->left,
1091 break_flags);
1092 }
1093 else
1094 {
1095 #ifdef VERBOSE
1096 art_dprint ("Inserting (%g, %g) into %lx, %lx\n",
1097 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1098 #endif
1099 /* Insert the intersection point into both segments. */
1100 art_svp_intersect_push_pt (ctx, left_seg, x, y);
1101 art_svp_intersect_push_pt (ctx, right_seg, x, y);
1102 if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1103 art_svp_intersect_add_point (ctx, x, y, left_seg->left, break_flags);
1104 if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1105 art_svp_intersect_add_point (ctx, x, y, right_seg->right, break_flags);
1106 }
1107 return ART_FALSE;
1108 }
1109
1110 /**
1111 * art_svp_intersect_active_delete: Delete segment from active list.
1112 * @ctx: Intersection context.
1113 * @seg: Segment to delete.
1114 *
1115 * Deletes @seg from the active list.
1116 **/
1117 static /* todo inline */ void
art_svp_intersect_active_delete(ArtIntersectCtx * ctx,ArtActiveSeg * seg)1118 art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1119 {
1120 ArtActiveSeg *left = seg->left, *right = seg->right;
1121
1122 if (left != NULL)
1123 left->right = right;
1124 else
1125 ctx->active_head = right;
1126 if (right != NULL)
1127 right->left = left;
1128 }
1129
1130 /**
1131 * art_svp_intersect_active_free: Free an active segment.
1132 * @seg: Segment to delete.
1133 *
1134 * Frees @seg.
1135 **/
1136 static /* todo inline */ void
art_svp_intersect_active_free(ArtActiveSeg * seg)1137 art_svp_intersect_active_free (ArtActiveSeg *seg)
1138 {
1139 art_free (seg->stack);
1140 #ifdef VERBOSE
1141 art_dprint ("Freeing %lx\n", (unsigned long) seg);
1142 #endif
1143 art_free (seg);
1144 }
1145
1146 /**
1147 * art_svp_intersect_insert_cross: Test crossings of newly inserted line.
1148 *
1149 * Tests @seg against its left and right neighbors for intersections.
1150 * Precondition: the line in @seg is not purely horizontal.
1151 **/
1152 static void
art_svp_intersect_insert_cross(ArtIntersectCtx * ctx,ArtActiveSeg * seg)1153 art_svp_intersect_insert_cross (ArtIntersectCtx *ctx,
1154 ArtActiveSeg *seg)
1155 {
1156 ArtActiveSeg *left = seg, *right = seg;
1157
1158 for (;;)
1159 {
1160 if (left != NULL)
1161 {
1162 ArtActiveSeg *leftc;
1163
1164 for (leftc = left->left; leftc != NULL; leftc = leftc->left)
1165 if (!(leftc->flags & ART_ACTIVE_FLAGS_DEL))
1166 break;
1167 if (leftc != NULL &&
1168 art_svp_intersect_test_cross (ctx, leftc, left,
1169 ART_BREAK_LEFT))
1170 {
1171 if (left == right || right == NULL)
1172 right = left->right;
1173 }
1174 else
1175 {
1176 left = NULL;
1177 }
1178 }
1179 else if (right != NULL && right->right != NULL)
1180 {
1181 ArtActiveSeg *rightc;
1182
1183 for (rightc = right->right; rightc != NULL; rightc = rightc->right)
1184 if (!(rightc->flags & ART_ACTIVE_FLAGS_DEL))
1185 break;
1186 if (rightc != NULL &&
1187 art_svp_intersect_test_cross (ctx, right, rightc,
1188 ART_BREAK_RIGHT))
1189 {
1190 if (left == right || left == NULL)
1191 left = right->left;
1192 }
1193 else
1194 {
1195 right = NULL;
1196 }
1197 }
1198 else
1199 break;
1200 }
1201 }
1202
1203 /**
1204 * art_svp_intersect_horiz: Add horizontal line segment.
1205 * @ctx: Intersector context.
1206 * @seg: Segment on which to add horizontal line.
1207 * @x0: Old x position.
1208 * @x1: New x position.
1209 *
1210 * Adds a horizontal line from @x0 to @x1, and updates the current
1211 * location of @seg to @x1.
1212 **/
1213 static void
art_svp_intersect_horiz(ArtIntersectCtx * ctx,ArtActiveSeg * seg,double x0,double x1)1214 art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1215 double x0, double x1)
1216 {
1217 ArtActiveSeg *hs;
1218
1219 if (x0 == x1)
1220 return;
1221
1222 hs = art_new (ArtActiveSeg, 1);
1223
1224 hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT);
1225 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1226 {
1227 ArtSvpWriter *swr = ctx->out;
1228
1229 swr->add_point (swr, seg->seg_id, x0, ctx->y);
1230 }
1231 hs->seg_id = seg->seg_id;
1232 hs->horiz_x = x0;
1233 hs->horiz_delta_wind = seg->delta_wind;
1234 hs->stack = NULL;
1235
1236 /* Ideally, the (a, b, c) values will never be read. However, there
1237 are probably some tests remaining that don't check for _DEL
1238 before evaluating the line equation. For those, these
1239 initializations will at least prevent a UMR of the values, which
1240 can crash on some platforms. */
1241 hs->a = 0.0;
1242 hs->b = 0.0;
1243 hs->c = 0.0;
1244
1245 seg->horiz_delta_wind -= seg->delta_wind;
1246
1247 art_svp_intersect_add_horiz (ctx, hs);
1248
1249 if (x0 > x1)
1250 {
1251 ArtActiveSeg *left;
1252 art_boolean first = ART_TRUE;
1253
1254 for (left = seg->left; left != NULL; left = seg->left)
1255 {
1256 int left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG;
1257
1258 if (left->x[left_bneg] <= x1)
1259 break;
1260 if (left->x[left_bneg ^ 1] <= x1 &&
1261 x1 * left->a + ctx->y * left->b + left->c >= 0)
1262 break;
1263 if (left->y0 != ctx->y && left->y1 != ctx->y)
1264 {
1265 art_svp_intersect_break (ctx, left, x1, ctx->y, ART_BREAK_LEFT);
1266 }
1267 #ifdef VERBOSE
1268 art_dprint ("x0=%g > x1=%g, swapping %lx, %lx\n",
1269 x0, x1, (unsigned long)left, (unsigned long)seg);
1270 #endif
1271 art_svp_intersect_swap_active (ctx, left, seg);
1272 if (first && left->right != NULL)
1273 {
1274 art_svp_intersect_test_cross (ctx, left, left->right,
1275 ART_BREAK_RIGHT);
1276 first = ART_FALSE;
1277 }
1278 }
1279 }
1280 else
1281 {
1282 ArtActiveSeg *right;
1283 art_boolean first = ART_TRUE;
1284
1285 for (right = seg->right; right != NULL; right = seg->right)
1286 {
1287 int right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG;
1288
1289 if (right->x[right_bneg ^ 1] >= x1)
1290 break;
1291 if (right->x[right_bneg] >= x1 &&
1292 x1 * right->a + ctx->y * right->b + right->c <= 0)
1293 break;
1294 if (right->y0 != ctx->y && right->y1 != ctx->y)
1295 {
1296 art_svp_intersect_break (ctx, right, x1, ctx->y,
1297 ART_BREAK_LEFT);
1298 }
1299 #ifdef VERBOSE
1300 art_dprint ("[right]x0=%g < x1=%g, swapping %lx, %lx\n",
1301 x0, x1, (unsigned long)seg, (unsigned long)right);
1302 #endif
1303 art_svp_intersect_swap_active (ctx, seg, right);
1304 if (first && right->left != NULL)
1305 {
1306 art_svp_intersect_test_cross (ctx, right->left, right,
1307 ART_BREAK_RIGHT);
1308 first = ART_FALSE;
1309 }
1310 }
1311 }
1312
1313 seg->x[0] = x1;
1314 seg->x[1] = x1;
1315 seg->horiz_x = x1;
1316 seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1317 }
1318
1319 /**
1320 * art_svp_intersect_insert_line: Insert a line into the active list.
1321 * @ctx: Intersector context.
1322 * @seg: Segment containing line to insert.
1323 *
1324 * Inserts the line into the intersector context, taking care of any
1325 * intersections, and adding the appropriate horizontal points to the
1326 * active list.
1327 **/
1328 static void
art_svp_intersect_insert_line(ArtIntersectCtx * ctx,ArtActiveSeg * seg)1329 art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1330 {
1331 if (seg->y1 == seg->y0)
1332 {
1333 #ifdef VERBOSE
1334 art_dprint ("art_svp_intersect_insert_line: %lx is horizontal\n",
1335 (unsigned long)seg);
1336 #endif
1337 art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]);
1338 }
1339 else
1340 {
1341 art_svp_intersect_insert_cross (ctx, seg);
1342 art_svp_intersect_add_horiz (ctx, seg);
1343 }
1344 }
1345
1346 static void
art_svp_intersect_process_intersection(ArtIntersectCtx * ctx,ArtActiveSeg * seg)1347 art_svp_intersect_process_intersection (ArtIntersectCtx *ctx,
1348 ArtActiveSeg *seg)
1349 {
1350 int n_stack = --seg->n_stack;
1351 seg->x[1] = seg->stack[n_stack - 1].x;
1352 seg->y1 = seg->stack[n_stack - 1].y;
1353 seg->x[0] = seg->stack[n_stack].x;
1354 seg->y0 = seg->stack[n_stack].y;
1355 seg->horiz_x = seg->x[0];
1356 art_svp_intersect_insert_line (ctx, seg);
1357 }
1358
1359 static void
art_svp_intersect_advance_cursor(ArtIntersectCtx * ctx,ArtActiveSeg * seg,ArtPriPoint * pri_pt)1360 art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1361 ArtPriPoint *pri_pt)
1362 {
1363 const ArtSVPSeg *in_seg = seg->in_seg;
1364 int in_curs = seg->in_curs;
1365 ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL;
1366
1367 if (swr != NULL)
1368 swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1);
1369 if (in_curs + 1 == in_seg->n_points)
1370 {
1371 ArtActiveSeg *left = seg->left, *right = seg->right;
1372
1373 #if 0
1374 if (swr != NULL)
1375 swr->close_segment (swr, seg->seg_id);
1376 seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1377 #endif
1378 seg->flags |= ART_ACTIVE_FLAGS_DEL;
1379 art_svp_intersect_add_horiz (ctx, seg);
1380 art_svp_intersect_active_delete (ctx, seg);
1381 if (left != NULL && right != NULL)
1382 art_svp_intersect_test_cross (ctx, left, right,
1383 ART_BREAK_LEFT | ART_BREAK_RIGHT);
1384 art_free (pri_pt);
1385 }
1386 else
1387 {
1388 seg->horiz_x = seg->x[1];
1389
1390 art_svp_intersect_setup_seg (seg, pri_pt);
1391 art_pri_insert (ctx->pq, pri_pt);
1392 art_svp_intersect_insert_line (ctx, seg);
1393 }
1394 }
1395
1396 static void
art_svp_intersect_add_seg(ArtIntersectCtx * ctx,const ArtSVPSeg * in_seg)1397 art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg)
1398 {
1399 ArtActiveSeg *seg = art_new (ArtActiveSeg, 1);
1400 ArtActiveSeg *test;
1401 double x0, y0;
1402 ArtActiveSeg *beg_range;
1403 ArtActiveSeg *last = NULL;
1404 ArtActiveSeg *left, *right;
1405 ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1);
1406
1407 seg->flags = 0;
1408 seg->in_seg = in_seg;
1409 seg->in_curs = 0;
1410
1411 seg->n_stack_max = 4;
1412 seg->stack = art_new (ArtPoint, seg->n_stack_max);
1413
1414 seg->horiz_delta_wind = 0;
1415
1416 seg->wind_left = 0;
1417
1418 pri_pt->user_data = seg;
1419 art_svp_intersect_setup_seg (seg, pri_pt);
1420 art_pri_insert (ctx->pq, pri_pt);
1421
1422 /* Find insertion place for new segment */
1423 /* This is currently a left-to-right scan, but should be replaced
1424 with a binary search as soon as it's validated. */
1425
1426 x0 = in_seg->points[0].x;
1427 y0 = in_seg->points[0].y;
1428 beg_range = NULL;
1429 for (test = ctx->active_head; test != NULL; test = test->right)
1430 {
1431 double d;
1432 int test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG;
1433
1434 if (x0 < test->x[test_bneg])
1435 {
1436 if (x0 < test->x[test_bneg ^ 1])
1437 break;
1438 d = x0 * test->a + y0 * test->b + test->c;
1439 if (d < 0)
1440 break;
1441 }
1442 last = test;
1443 }
1444
1445 left = art_svp_intersect_add_point (ctx, x0, y0, last, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1446 seg->left = left;
1447 if (left == NULL)
1448 {
1449 right = ctx->active_head;
1450 ctx->active_head = seg;
1451 }
1452 else
1453 {
1454 right = left->right;
1455 left->right = seg;
1456 }
1457 seg->right = right;
1458 if (right != NULL)
1459 right->left = seg;
1460
1461 seg->delta_wind = in_seg->dir ? 1 : -1;
1462 seg->horiz_x = x0;
1463
1464 art_svp_intersect_insert_line (ctx, seg);
1465 }
1466
1467 #ifdef SANITYCHECK
1468 static void
art_svp_intersect_sanitycheck_winding(ArtIntersectCtx * ctx)1469 art_svp_intersect_sanitycheck_winding (ArtIntersectCtx *ctx)
1470 {
1471 #if 0
1472 /* At this point, we seem to be getting false positives, so it's
1473 turned off for now. */
1474
1475 ArtActiveSeg *seg;
1476 int winding_number = 0;
1477
1478 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1479 {
1480 /* Check winding number consistency. */
1481 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1482 {
1483 if (winding_number != seg->wind_left)
1484 art_warn ("*** art_svp_intersect_sanitycheck_winding: seg %lx has wind_left of %d, expected %d\n",
1485 (unsigned long) seg, seg->wind_left, winding_number);
1486 winding_number = seg->wind_left + seg->delta_wind;
1487 }
1488 }
1489 if (winding_number != 0)
1490 art_warn ("*** art_svp_intersect_sanitycheck_winding: non-balanced winding number %d\n",
1491 winding_number);
1492 #endif
1493 }
1494 #endif
1495
1496 /**
1497 * art_svp_intersect_horiz_commit: Commit points in horiz list to output.
1498 * @ctx: Intersection context.
1499 *
1500 * The main function of the horizontal commit is to output new
1501 * points to the output writer.
1502 *
1503 * This "commit" pass is also where winding numbers are assigned,
1504 * because doing it here provides much greater tolerance for inputs
1505 * which are not in strict SVP order.
1506 *
1507 * Each cluster in the horiz_list contains both segments that are in
1508 * the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not,
1509 * and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We
1510 * need to deal with both.
1511 **/
1512 static void
art_svp_intersect_horiz_commit(ArtIntersectCtx * ctx)1513 art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx)
1514 {
1515 ArtActiveSeg *seg;
1516 int winding_number = 0; /* initialization just to avoid warning */
1517 int horiz_wind = 0;
1518 double last_x = 0; /* initialization just to avoid warning */
1519
1520 #ifdef VERBOSE
1521 art_dprint ("art_svp_intersect_horiz_commit: y=%g\n", ctx->y);
1522 for (seg = ctx->horiz_first; seg != NULL; seg = seg->horiz_right)
1523 art_dprint (" %lx: %g %+d\n",
1524 (unsigned long)seg, seg->horiz_x, seg->horiz_delta_wind);
1525 #endif
1526
1527 /* Output points to svp writer. */
1528 for (seg = ctx->horiz_first; seg != NULL;)
1529 {
1530 /* Find a cluster with common horiz_x, */
1531 ArtActiveSeg *curs;
1532 double x = seg->horiz_x;
1533
1534 /* Generate any horizontal segments. */
1535 if (horiz_wind != 0)
1536 {
1537 ArtSvpWriter *swr = ctx->out;
1538 int seg_id;
1539
1540 seg_id = swr->add_segment (swr, winding_number, horiz_wind,
1541 last_x, ctx->y);
1542 swr->add_point (swr, seg_id, x, ctx->y);
1543 swr->close_segment (swr, seg_id);
1544 }
1545
1546 /* Find first active segment in cluster. */
1547
1548 for (curs = seg; curs != NULL && curs->horiz_x == x;
1549 curs = curs->horiz_right)
1550 if (!(curs->flags & ART_ACTIVE_FLAGS_DEL))
1551 break;
1552
1553 if (curs != NULL && curs->horiz_x == x)
1554 {
1555 /* There exists at least one active segment in this cluster. */
1556
1557 /* Find beginning of cluster. */
1558 for (; curs->left != NULL; curs = curs->left)
1559 if (curs->left->horiz_x != x)
1560 break;
1561
1562 if (curs->left != NULL)
1563 winding_number = curs->left->wind_left + curs->left->delta_wind;
1564 else
1565 winding_number = 0;
1566
1567 do
1568 {
1569 #ifdef VERBOSE
1570 art_dprint (" curs %lx: winding_number = %d += %d\n",
1571 (unsigned long)curs, winding_number, curs->delta_wind);
1572 #endif
1573 if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) ||
1574 curs->wind_left != winding_number)
1575 {
1576 ArtSvpWriter *swr = ctx->out;
1577
1578 if (curs->flags & ART_ACTIVE_FLAGS_OUT)
1579 {
1580 swr->add_point (swr, curs->seg_id,
1581 curs->horiz_x, ctx->y);
1582 swr->close_segment (swr, curs->seg_id);
1583 }
1584
1585 curs->seg_id = swr->add_segment (swr, winding_number,
1586 curs->delta_wind,
1587 x, ctx->y);
1588 curs->flags |= ART_ACTIVE_FLAGS_OUT;
1589 }
1590 curs->wind_left = winding_number;
1591 winding_number += curs->delta_wind;
1592 curs = curs->right;
1593 }
1594 while (curs != NULL && curs->horiz_x == x);
1595 }
1596
1597 /* Skip past cluster. */
1598 do
1599 {
1600 ArtActiveSeg *next = seg->horiz_right;
1601
1602 seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ;
1603 horiz_wind += seg->horiz_delta_wind;
1604 seg->horiz_delta_wind = 0;
1605 if (seg->flags & ART_ACTIVE_FLAGS_DEL)
1606 {
1607 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1608 {
1609 ArtSvpWriter *swr = ctx->out;
1610 swr->close_segment (swr, seg->seg_id);
1611 }
1612 art_svp_intersect_active_free (seg);
1613 }
1614 seg = next;
1615 }
1616 while (seg != NULL && seg->horiz_x == x);
1617
1618 last_x = x;
1619 }
1620 ctx->horiz_first = NULL;
1621 ctx->horiz_last = NULL;
1622 #ifdef SANITYCHECK
1623 art_svp_intersect_sanitycheck_winding (ctx);
1624 #endif
1625 }
1626
1627 #ifdef VERBOSE
1628 static void
art_svp_intersect_print_active(ArtIntersectCtx * ctx)1629 art_svp_intersect_print_active (ArtIntersectCtx *ctx)
1630 {
1631 ArtActiveSeg *seg;
1632
1633 art_dprint ("Active list (y = %g):\n", ctx->y);
1634 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1635 {
1636 art_dprint (" %lx: (%g, %g)-(%g, %g), (a, b, c) = (%g, %g, %g)\n",
1637 (unsigned long)seg,
1638 seg->x[0], seg->y0, seg->x[1], seg->y1,
1639 seg->a, seg->b, seg->c);
1640 }
1641 }
1642 #endif
1643
1644 #ifdef SANITYCHECK
1645 static void
art_svp_intersect_sanitycheck(ArtIntersectCtx * ctx)1646 art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx)
1647 {
1648 ArtActiveSeg *seg;
1649 ArtActiveSeg *last = NULL;
1650 double d;
1651
1652 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1653 {
1654 if (seg->left != last)
1655 {
1656 art_warn ("*** art_svp_intersect_sanitycheck: last=%lx, seg->left=%lx\n",
1657 (unsigned long)last, (unsigned long)seg->left);
1658 }
1659 if (last != NULL)
1660 {
1661 /* pairwise compare with previous seg */
1662
1663 /* First the top. */
1664 if (last->y0 < seg->y0)
1665 {
1666 }
1667 else
1668 {
1669 }
1670
1671 /* Then the bottom. */
1672 if (last->y1 < seg->y1)
1673 {
1674 if (!((last->x[1] <
1675 seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) ||
1676 last->y1 == seg->y0))
1677 {
1678 d = last->x[1] * seg->a + last->y1 * seg->b + seg->c;
1679 if (d >= -EPSILON_A)
1680 art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to right (d = %g)\n",
1681 last->x[1], last->y1, (unsigned long) last,
1682 (unsigned long) seg, d);
1683 }
1684 }
1685 else if (last->y1 > seg->y1)
1686
1687 {
1688 if (!((seg->x[1] >
1689 last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) ||
1690 seg->y1 == last->y0))
1691 {
1692 d = seg->x[1] * last->a + seg->y1 * last->b + last->c;
1693 if (d <= EPSILON_A)
1694 art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to left (d = %g)\n",
1695 seg->x[1], seg->y1, (unsigned long) seg,
1696 (unsigned long) last, d);
1697 }
1698 }
1699 else
1700 {
1701 if (last->x[1] > seg->x[1])
1702 art_warn ("*** bottoms (%g, %g) of %lx and (%g, %g) of %lx out of order\n",
1703 last->x[1], last->y1, (unsigned long)last,
1704 seg->x[1], seg->y1, (unsigned long)seg);
1705 }
1706 }
1707 last = seg;
1708 }
1709 }
1710 #endif
1711
1712 void
art_svp_intersector(const ArtSVP * in,ArtSvpWriter * out)1713 art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out)
1714 {
1715 ArtIntersectCtx *ctx;
1716 ArtPriQ *pq;
1717 ArtPriPoint *first_point;
1718 #ifdef VERBOSE
1719 int count = 0;
1720 #endif
1721
1722 if (in->n_segs == 0)
1723 return;
1724
1725 ctx = art_new (ArtIntersectCtx, 1);
1726 ctx->in = in;
1727 ctx->out = out;
1728 pq = art_pri_new ();
1729 ctx->pq = pq;
1730
1731 ctx->active_head = NULL;
1732
1733 ctx->horiz_first = NULL;
1734 ctx->horiz_last = NULL;
1735
1736 ctx->in_curs = 0;
1737 first_point = art_new (ArtPriPoint, 1);
1738 first_point->x = in->segs[0].points[0].x;
1739 first_point->y = in->segs[0].points[0].y;
1740 first_point->user_data = NULL;
1741 ctx->y = first_point->y;
1742 art_pri_insert (pq, first_point);
1743
1744 while (!art_pri_empty (pq))
1745 {
1746 ArtPriPoint *pri_point = art_pri_choose (pq);
1747 ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data;
1748
1749 #ifdef VERBOSE
1750 art_dprint ("\nIntersector step %d\n", count++);
1751 art_svp_intersect_print_active (ctx);
1752 art_dprint ("priq choose (%g, %g) %lx\n", pri_point->x, pri_point->y,
1753 (unsigned long)pri_point->user_data);
1754 #endif
1755 #ifdef SANITYCHECK
1756 art_svp_intersect_sanitycheck(ctx);
1757 #endif
1758
1759 if (ctx->y != pri_point->y)
1760 {
1761 art_svp_intersect_horiz_commit (ctx);
1762 ctx->y = pri_point->y;
1763 }
1764
1765 if (seg == NULL)
1766 {
1767 /* Insert new segment from input */
1768 const ArtSVPSeg *in_seg = &in->segs[ctx->in_curs++];
1769 art_svp_intersect_add_seg (ctx, in_seg);
1770 if (ctx->in_curs < in->n_segs)
1771 {
1772 const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs];
1773 pri_point->x = next_seg->points[0].x;
1774 pri_point->y = next_seg->points[0].y;
1775 /* user_data is already NULL */
1776 art_pri_insert (pq, pri_point);
1777 }
1778 else
1779 art_free (pri_point);
1780 }
1781 else
1782 {
1783 int n_stack = seg->n_stack;
1784
1785 if (n_stack > 1)
1786 {
1787 art_svp_intersect_process_intersection (ctx, seg);
1788 art_free (pri_point);
1789 }
1790 else
1791 {
1792 art_svp_intersect_advance_cursor (ctx, seg, pri_point);
1793 }
1794 }
1795 }
1796
1797 art_svp_intersect_horiz_commit (ctx);
1798
1799 art_pri_free (pq);
1800 art_free (ctx);
1801 }
1802
1803 #endif /* not TEST_PRIQ */
1804