create multinames from strings (for now)
[swftools.git] / lib / art / art_svp_intersect.c
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 <stdio.h>
25 #include <assert.h>
26 #include "config.h"
27 #include "art_svp_intersect.h"
28
29 #include <math.h> /* for sqrt */
30
31 /* Sanitychecking verifies the main invariant on every priority queue
32    point. Do not use in production, as it slows things down way too
33    much. */
34 #define noSANITYCHECK
35
36 /* This can be used in production, to prevent hangs. Eventually, it
37    should not be necessary. */
38 #define CHEAP_SANITYCHECK
39
40 #define noVERBOSE
41
42 #define noABORT_ON_ERROR
43
44 #include "art_misc.h"
45
46 /* A priority queue - perhaps move to a separate file if it becomes
47    needed somewhere else */
48
49 #define ART_PRIQ_USE_HEAP
50
51 typedef struct _ArtPriQ ArtPriQ;
52 typedef struct _ArtPriPoint ArtPriPoint;
53
54 struct _ArtPriQ {
55   int n_items;
56   int n_items_max;
57   ArtPriPoint **items;
58 };
59
60 struct _ArtPriPoint {
61   double x;
62   double y;
63   void *user_data;
64 };
65
66 static ArtPriQ *
67 art_pri_new (void)
68 {
69   ArtPriQ *result = art_new (ArtPriQ, 1);
70
71   result->n_items = 0;
72   result->n_items_max = 16;
73   result->items = art_new (ArtPriPoint *, result->n_items_max);
74   return result;
75 }
76
77 static void
78 art_pri_free (ArtPriQ *pq)
79 {
80   art_free (pq->items);
81   art_free (pq);
82 }
83
84 static art_boolean
85 art_pri_empty (ArtPriQ *pq)
86 {
87   return pq->n_items == 0;
88 }
89
90 /* This heap implementation is based on Vasek Chvatal's course notes:
91    http://www.cs.rutgers.edu/~chvatal/notes/pq.html#heap */
92
93 static void
94 art_pri_bubble_up (ArtPriQ *pq, int vacant, ArtPriPoint *missing)
95 {
96   ArtPriPoint **items = pq->items;
97   int parent;
98
99   parent = (vacant - 1) >> 1;
100   while (vacant > 0 && (missing->y < items[parent]->y ||
101                         (missing->y == items[parent]->y &&
102                          missing->x < items[parent]->x)))
103     {
104       items[vacant] = items[parent];
105       vacant = parent;
106       parent = (vacant - 1) >> 1;
107     }
108
109   items[vacant] = missing;
110 }
111
112 static void
113 art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
114 {
115 #ifdef VERBOSE
116   art_dprint("insert into pq %08x: %.16f,%.16f %08x\n", pq, point->x, point->y, point->user_data);
117 #endif
118   if (pq->n_items == pq->n_items_max)
119     art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
120
121   art_pri_bubble_up (pq, pq->n_items++, point);
122 }
123
124 static void
125 art_pri_sift_down_from_root (ArtPriQ *pq, ArtPriPoint *missing)
126 {
127   ArtPriPoint **items = pq->items;
128   int vacant = 0, child = 2;
129   int n = pq->n_items;
130
131   while (child < n)
132     {
133       if (items[child - 1]->y < items[child]->y ||
134           (items[child - 1]->y == items[child]->y &&
135            items[child - 1]->x < items[child]->x))
136         child--;
137       items[vacant] = items[child];
138       vacant = child;
139       child = (vacant + 1) << 1;
140     }
141   if (child == n)
142     {
143       items[vacant] = items[n - 1];
144       vacant = n - 1;
145     }
146
147   art_pri_bubble_up (pq, vacant, missing);
148 }
149
150 static ArtPriPoint *
151 art_pri_choose (ArtPriQ *pq)
152 {
153   ArtPriPoint *result = pq->items[0];
154
155   art_pri_sift_down_from_root (pq, pq->items[--pq->n_items]);
156   return result;
157 }
158
159 /* TODO: this is *not* thread save */
160 const ArtSVP* current_svp = 0;
161 int art_error_in_intersector=0;
162
163 void art_report_error()
164 {
165     art_error_in_intersector = 1;
166 #ifdef ABORT_ON_ERROR
167     if(!current_svp) {
168         fprintf(stderr, "internal error: no current polygon\n");
169         exit(1);
170     }
171     const ArtSVP*svp = current_svp;
172     FILE*fi = fopen("svp.ps", "wb");
173     int i, j;
174     fprintf(fi, "%% begin\n");
175     for (i = 0; i < svp->n_segs; i++)
176     {
177         fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
178         for (j = 0; j < svp->segs[i].n_points; j++)
179           {
180             fprintf(fi, "%.32f %.32f %s\n",
181                     svp->segs[i].points[j].x,
182                     svp->segs[i].points[j].y,
183                     j ? "lineto" : "moveto");
184           }
185         fprintf(fi, "stroke\n");
186     }
187     fprintf(fi, "showpage\n");
188     fclose(fi);
189
190     fprintf(stderr, "There was an error during polygon processing.\n");
191     fprintf(stderr, "I saved a debug file, called svp.ps, to the current directory.\n");
192     fprintf(stderr, "Please help making this tool more stable by mailing\n");
193     fprintf(stderr, "this file to debug@swftools.org. Thank you!\n");
194     exit(1);
195 #endif
196 }
197
198 /* A virtual class for an "svp writer". A client of this object creates an
199    SVP by repeatedly calling "add segment" and "add point" methods on it.
200 */
201
202 typedef struct _ArtSvpWriterRewind ArtSvpWriterRewind;
203
204 /* An implementation of the svp writer virtual class that applies the
205    winding rule. */
206
207 struct _ArtSvpWriterRewind {
208   ArtSvpWriter super;
209   ArtWindRule rule;
210   ArtSVP *svp;
211   int n_segs_max;
212   int *n_points_max;
213 };
214
215 static int
216 art_svp_writer_rewind_add_segment (ArtSvpWriter *self, int wind_left,
217                                    int delta_wind, double x, double y)
218 {
219   ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
220   ArtSVP *svp;
221   ArtSVPSeg *seg;
222   art_boolean left_filled, right_filled;
223   int wind_right = wind_left + delta_wind;
224   int seg_num;
225   const int init_n_points_max = 4;
226
227   switch (swr->rule)
228     {
229     case ART_WIND_RULE_NONZERO:
230       left_filled = (wind_left != 0);
231       right_filled = (wind_right != 0);
232       break;
233     case ART_WIND_RULE_INTERSECT:
234       left_filled = (wind_left > 1);
235       right_filled = (wind_right > 1);
236       break;
237     case ART_WIND_RULE_ODDEVEN:
238       left_filled = (wind_left & 1);
239       right_filled = (wind_right & 1);
240       break;
241     case ART_WIND_RULE_POSITIVE:
242       left_filled = (wind_left > 0);
243       right_filled = (wind_right > 0);
244       break;
245     default:
246       art_die ("Unknown wind rule %d\n", swr->rule);
247     }
248
249 #ifdef VERBOSE
250   art_dprint("New svp segment %d: %.32f %.32f left_filled=%d, right_filled=%d\n", swr->svp->n_segs, x, y, left_filled, right_filled);
251 #endif
252
253   if (left_filled == right_filled)
254     {
255       /* discard segment now */
256 #ifdef VERBOSE
257       art_dprint ("  discarding segment: %d += %d (%.16f, %.16f)\n",
258               wind_left, delta_wind, x, y);
259 #endif
260       return -1;
261    }
262
263   svp = swr->svp;
264   seg_num = svp->n_segs++;
265   if (swr->n_segs_max == seg_num)
266     {
267       swr->n_segs_max += 10;
268       svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
269                                    (swr->n_segs_max - 1) *
270                                    sizeof(ArtSVPSeg));
271       swr->svp = svp;
272       swr->n_points_max = art_renew (swr->n_points_max, int,
273                                      swr->n_segs_max);
274     }
275   seg = &svp->segs[seg_num];
276   seg->n_points = 1;
277   seg->dir = right_filled;
278   swr->n_points_max[seg_num] = init_n_points_max;
279   seg->bbox.x0 = x;
280   seg->bbox.y0 = y;
281   seg->bbox.x1 = x;
282   seg->bbox.y1 = y;
283   seg->points = art_new (ArtPoint, init_n_points_max);
284   seg->points[0].x = x;
285   seg->points[0].y = y;
286 #ifdef VERBOSE
287     art_dprint ("swr add_segment: %d += %d (%.16f, %.16f) --> %d (%s)\n",
288             wind_left, delta_wind, x, y, seg_num,
289             seg->dir ? "filled" : "non-filled");
290 #endif
291   return seg_num;
292 }
293
294 static void
295 art_svp_writer_rewind_add_point (ArtSvpWriter *self, int seg_id,
296                                  double x, double y)
297 {
298
299   ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
300   ArtSVPSeg *seg;
301   int n_points;
302
303 #ifdef VERBOSE
304   art_dprint ("swr add_point: %d (%.16f, %.16f)\n", seg_id, x, y);
305 #endif
306   if (seg_id < 0)
307     /* omitted segment */
308     return;
309
310   seg = &swr->svp->segs[seg_id];
311
312   if(n_points &&
313         seg->points[seg->n_points-1].x == x &&
314         seg->points[seg->n_points-1].y == y) {
315       //art_warn("duplicate point %.16f,%.16f in segment %08x\n", 
316       //        x, y, seg_id);
317       return;
318   }
319
320   n_points = seg->n_points++;
321   if (swr->n_points_max[seg_id] == n_points)
322     art_expand (seg->points, ArtPoint, swr->n_points_max[seg_id]);
323
324   if(0 && n_points>=2) {
325       double dx1 = seg->points[n_points-1].x - seg->points[n_points-2].x;
326       double dy1 = seg->points[n_points-1].y - seg->points[n_points-2].y;
327       double dx2 = x - seg->points[n_points-2].x;
328       double dy2 = y - seg->points[n_points-2].y;
329       if(fabs(dx1*dy2 - dx2*dy1) < 1e-10) {
330           seg->n_points--;
331           n_points--; // remove previous point pointing in the same direction
332
333          //art_warn("redundant point %.16f,%.16f in segment %08x\n", 
334          //        seg->points[n_points-1].x, seg->points[n_points-1].y,
335          //        seg_id);
336       }
337   }
338   
339   if(n_points && seg->points[n_points-1].y > y) {
340       art_warn("non-increasing segment (%.16f -> %.16f)\n", seg->points[n_points-1].y, y);
341       art_report_error();
342   }
343
344   seg->points[n_points].x = x;
345   seg->points[n_points].y = y;
346   if (x < seg->bbox.x0)
347     seg->bbox.x0 = x;
348   if (x > seg->bbox.x1)
349     seg->bbox.x1 = x;
350   seg->bbox.y1 = y;
351 }
352
353 static void
354 art_svp_writer_rewind_close_segment (ArtSvpWriter *self, int seg_id)
355 {
356   /* Not needed for this simple implementation. A potential future
357      optimization is to merge segments that can be merged safely. */
358 #ifdef CHEAP_SANITYCHECK
359   ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
360   ArtSVPSeg *seg;
361
362   if (seg_id >= 0)
363     {
364       seg = &swr->svp->segs[seg_id];
365       if (seg->n_points < 2)
366         art_warn ("*** closing segment %d with only %d point%s\n",
367                   seg_id, seg->n_points, seg->n_points == 1 ? "" : "s");
368     }
369 #endif
370
371 #ifdef VERBOSE
372   art_dprint ("swr close_segment: %d\n", seg_id);
373 #endif
374 }
375
376 ArtSVP *
377 art_svp_writer_rewind_reap (ArtSvpWriter *self)
378 {
379   ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
380   ArtSVP *result = swr->svp;
381
382   art_free (swr->n_points_max);
383   art_free (swr);
384   return result;
385 }
386
387 ArtSvpWriter *
388 art_svp_writer_rewind_new (ArtWindRule rule)
389 {
390   ArtSvpWriterRewind *result = art_new (ArtSvpWriterRewind, 1);
391
392   result->super.add_segment = art_svp_writer_rewind_add_segment;
393   result->super.add_point = art_svp_writer_rewind_add_point;
394   result->super.close_segment = art_svp_writer_rewind_close_segment;
395
396   result->rule = rule;
397   result->n_segs_max = 16;
398   result->svp = (ArtSVP*)art_alloc (sizeof(ArtSVP) + 
399                            (result->n_segs_max - 1) * sizeof(ArtSVPSeg));
400   result->svp->n_segs = 0;
401   result->n_points_max = (int*)art_new (int, result->n_segs_max);
402
403   return &result->super;
404 }
405
406 /* Now, data structures for the active list.
407
408    signs:
409                /  |
410         b<0   /   |   \ b>0, c<0
411         c>0  /\   |   /\
412             /  \  |  /  \
413            /    \ | /     
414                  \|/
415      -------------+--------------------
416                  /|\ 
417              \  / | \  /
418               \/  |  \/ b<0, c<0
419         b>0    \  |  /
420         c>0     \ | /
421  */
422
423 typedef struct _ArtActiveSeg ArtActiveSeg;
424
425 /* Note: BNEG is 1 for \ lines, and 0 for /. Thus,
426    x[(flags & BNEG) ^ 1] <= x[flags & BNEG] */
427 #define ART_ACTIVE_FLAGS_BNEG 1
428
429 /* This flag is set if the segment has been inserted into the active
430    list. */
431 #define ART_ACTIVE_FLAGS_IN_ACTIVE 2
432
433 /* This flag is set when the segment is to be deleted in the
434    horiz commit process. */
435 #define ART_ACTIVE_FLAGS_DEL 4
436
437 /* This flag is set if the seg_id is a valid output segment. */
438 #define ART_ACTIVE_FLAGS_OUT 8
439
440 /* This flag is set if the segment is in the horiz list. */
441 #define ART_ACTIVE_FLAGS_IN_HORIZ 16
442
443 struct _ArtActiveSeg {
444   int flags;
445   int wind_left, delta_wind;
446   ArtActiveSeg *left, *right; /* doubly linked list structure */
447
448   const ArtSVPSeg *in_seg;
449   int in_curs;
450
451   double x[2];
452   double y0, y1;
453   double a, b, c; /* line equation; ax+by+c = 0 for the line, a^2 + b^2 = 1,
454                      and a>0 */
455
456   /* bottom point and intersection point stack */
457   int n_stack;
458   int n_stack_max;
459   ArtPoint *stack;
460
461   /* horiz commit list */
462   ArtActiveSeg *horiz_left, *horiz_right;
463   double horiz_x;
464   int horiz_delta_wind;
465   int seg_id;
466 };
467
468 typedef struct _ArtIntersectCtx ArtIntersectCtx;
469
470 struct _ArtIntersectCtx {
471   const ArtSVP *in;
472   ArtSvpWriter *out;
473
474   ArtPriQ *pq;
475
476   ArtActiveSeg *active_head;
477
478   double y;
479   ArtActiveSeg *horiz_first;
480   ArtActiveSeg *horiz_last;
481
482   /* segment index of next input segment to be added to pri q */
483   int in_curs;
484 };
485
486 #define EPSILON_A 1e-5 /* Threshold for breaking lines at point insertions */
487
488 /**
489  * art_svp_intersect_setup_seg: Set up an active segment from input segment.
490  * @seg: Active segment.
491  * @pri_pt: Priority queue point to initialize.
492  *
493  * Sets the x[], a, b, c, flags, and stack fields according to the
494  * line from the current cursor value. Sets the priority queue point
495  * to the bottom point of this line. Also advances the input segment
496  * cursor.
497  **/
498 static void
499 art_svp_intersect_setup_seg (ArtActiveSeg *seg, ArtPriPoint *pri_pt)
500 {
501   const ArtSVPSeg *in_seg = seg->in_seg;
502   int in_curs = 0;
503   double x0, y0, x1, y1;
504   double dx, dy, s;
505   double a, b, r2;
506
507   //do {
508     in_curs = seg->in_curs++;
509   //} while(in_seg->points[in_curs].x == in_seg->points[in_curs + 1].x &&
510   //        in_seg->points[in_curs].y == in_seg->points[in_curs + 1].y &&
511   //        in_curs < in_seg->n_points-1
512   //       );
513
514   x0 = in_seg->points[in_curs].x;
515   y0 = in_seg->points[in_curs].y;
516   x1 = in_seg->points[in_curs + 1].x;
517   y1 = in_seg->points[in_curs + 1].y;
518   pri_pt->x = x1;
519   pri_pt->y = y1;
520   dx = x1 - x0;
521   dy = y1 - y0;
522   r2 = dx * dx + dy * dy;
523   if(r2 == 0) {
524       //art_warn("segment %08x has zero length\n", seg);
525   }
526   s = r2 == 0 ? 1 : 1 / sqrt (r2);
527   seg->a = a = dy * s;
528   seg->b = b = -dx * s;
529   seg->c = -(a * x0 + b * y0);
530   seg->flags = (seg->flags & ~ART_ACTIVE_FLAGS_BNEG) | (dx > 0);
531   seg->x[0] = x0;
532   seg->x[1] = x1;
533   seg->y0 = y0;
534   seg->y1 = y1;
535   seg->n_stack = 1;
536   seg->stack[0].x = x1;
537   seg->stack[0].y = y1;
538
539   if(y1 < y0) {
540       art_warn("art_svp_intersect.c: bad input polygon %08x, contains decreasing y values\n", seg->in_seg);
541       art_report_error();
542   }
543 #ifdef VERBOSE
544   art_dprint("segment %08x (top: %.16f,%.16f) starts with endpoint at %.16f,%.16f\n", seg, 
545           x0, y0,
546           x1, y1);
547 #endif
548 }
549
550 /**
551  * art_svp_intersect_add_horiz: Add point to horizontal list.
552  * @ctx: Intersector context.
553  * @seg: Segment with point to insert into horizontal list.
554  *
555  * Inserts @seg into horizontal list, keeping it in ascending horiz_x
556  * order.
557  *
558  * Note: the horiz_commit routine processes "clusters" of segs in the
559  * horiz list, all sharing the same horiz_x value. The cluster is
560  * processed in active list order, rather than horiz list order. Thus,
561  * the order of segs in the horiz list sharing the same horiz_x
562  * _should_ be irrelevant. Even so, we use b as a secondary sorting key,
563  * as a "belt and suspenders" defensive coding tactic.
564  **/
565 static void
566 art_svp_intersect_add_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
567 {
568   ArtActiveSeg **pp = &ctx->horiz_last;
569   ArtActiveSeg *place;
570   ArtActiveSeg *place_right = NULL;
571
572 #ifdef CHEAP_SANITYCHECK
573   if (seg->flags & ART_ACTIVE_FLAGS_IN_HORIZ)
574     {
575       double dx = seg->x[1] - seg->x[0];
576       double dy = seg->y1 - seg->y0;
577       double len = sqrt(dx*dx+dy*dy);
578       art_warn("attempt to put segment %08x %.16f,%.16f (len:%.16f) in horiz list twice\n", seg, seg->x[0], seg->y0, len);
579       return;
580     }
581   seg->flags |= ART_ACTIVE_FLAGS_IN_HORIZ;
582 #endif
583
584 #ifdef VERBOSE
585   art_dprint ("add_horiz %08x, x = %.16f\n", (unsigned long) seg, seg->horiz_x);
586 #endif
587   for (place = *pp; place != NULL && (place->horiz_x > seg->horiz_x ||
588                                       (place->horiz_x == seg->horiz_x &&
589                                        place->b < seg->b));
590        place = *pp)
591     {
592       place_right = place;
593       pp = &place->horiz_left;
594     }
595   *pp = seg;
596   seg->horiz_left = place;
597   seg->horiz_right = place_right;
598
599   if (place == NULL)
600     ctx->horiz_first = seg;
601   else
602     place->horiz_right = seg;
603
604 #ifdef VERBOSE
605   art_dprint("horiz_list:\n");
606   ArtActiveSeg*s = ctx->horiz_first;
607   while(s) {
608       art_dprint("  %08x x=%.16f wind_left=%d delta_wind=%d horiz_delta_wind=%d\n", s, s->horiz_x, 
609               s->wind_left, s->delta_wind, s->horiz_delta_wind);
610       s = s->horiz_right;
611   }
612 #endif
613 }
614
615 static void
616 art_svp_intersect_push_pt (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
617                            double x, double y)
618 {
619   ArtPriPoint *pri_pt;
620   int n_stack = seg->n_stack;
621
622   if (n_stack == seg->n_stack_max)
623     art_expand (seg->stack, ArtPoint, seg->n_stack_max);
624
625
626   seg->stack[n_stack].x = x;
627   seg->stack[n_stack].y = y;
628   seg->n_stack++;
629
630 #ifdef VERBOSE
631   int t;
632   art_dprint("art_svp_intersect_push_pt %08x |top %.16f,%.16f\n", seg, seg->x[0], seg->y0);
633   for(t=seg->n_stack-1;t>=0;t--) {
634       if(t!=seg->n_stack-1)
635           art_dprint("art_svp_intersect_push_pt %08x |pt  %.16f,%.16f\n", seg, seg->stack[t].x, seg->stack[t].y);
636       else
637           art_dprint("art_svp_intersect_push_pt %08x |new %.16f,%.16f\n", seg, seg->stack[t].x, seg->stack[t].y);
638   }
639 #endif
640 #ifdef VERBOSE
641   art_dprint("(shortening segment %08x to %.16f,%.16f)\n", seg, x, y);
642 #endif
643   
644   if(seg->stack[seg->n_stack-1].y == seg->y0) {
645       art_warn("duplicate y coordinate (=y0) in point stack\n");
646   }
647
648   if(n_stack) {
649       if(seg->stack[seg->n_stack-2].y < seg->stack[seg->n_stack-1].y) {
650           art_warn("bad shortening- segment got *longer*\n");
651           art_report_error();
652       }
653   }
654
655
656   seg->x[1] = x;
657   seg->y1 = y;
658
659   pri_pt = art_new (ArtPriPoint, 1);
660   pri_pt->x = x;
661   pri_pt->y = y;
662   pri_pt->user_data = seg;
663   art_pri_insert (ctx->pq, pri_pt);
664 }
665
666 #define ART_BREAK_LEFT 1
667 #define ART_BREAK_RIGHT 2
668
669 /**
670  * art_svp_intersect_break: Break an active segment.
671  *
672  * Note: y must be greater than the top point's y, and less than
673  * the bottom's.
674  *
675  * Return value: x coordinate of break point.
676  */
677 static double
678 art_svp_intersect_break (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
679                          double x_ref, double y, int break_flags)
680 {
681   double x0, y0, x1, y1;
682   const ArtSVPSeg *in_seg = seg->in_seg;
683   int in_curs = seg->in_curs;
684   double x;
685
686   x0 = in_seg->points[in_curs - 1].x;
687   y0 = in_seg->points[in_curs - 1].y;
688   x1 = in_seg->points[in_curs].x;
689   y1 = in_seg->points[in_curs].y;
690
691   x = x0 + (x1 - x0) * ((y - y0) / (y1 - y0));
692
693   //printf("%d %.16f %.16f %d\n", break_flags&ART_BREAK_LEFT, x, x_ref, x > x_ref);
694   //printf("%d %.16f %.16f %d\n", break_flags&ART_BREAK_RIGHT, x, x_ref, x < x_ref);
695
696   if ((break_flags == ART_BREAK_LEFT && x > x_ref) ||
697       (break_flags == ART_BREAK_RIGHT && x < x_ref))
698     {
699 #ifdef VERBOSE
700       art_dprint ("art_svp_intersect_break %08x: limiting x to %.16f, was %.16f, %s\n", seg,
701                   x_ref, x, break_flags == ART_BREAK_LEFT ? "left" : "right");
702 #endif
703       //x = x_ref; //used to be *within* the VERBOSE comment
704     }
705   
706   if(y < y0 || y > y1) {
707       art_warn("!! bad break %.16f of %.16f-%.16f\n", y, y0, y1);
708       art_report_error();
709       return x;
710   }
711
712   /* I think we can count on min(x0, x1) <= x <= max(x0, x1) with sane
713      arithmetic, but it might be worthwhile to check just in case. */
714
715   /* TODO: should we check seg instead of in_seg ? */
716   if(x0<x1) {
717       if(x<x0 || x>x1) {
718           art_warn("bad x value %.16f in intersect_break: not between %.16f and %.16f\n", x, x0, x1);
719           art_report_error();
720       } 
721   } else {
722       if(x<x1 || x>x0) {
723           art_warn("bad x value %.16f in intersect_break:  not between %.16f and %.16f\n", x, x1, x0);
724           art_report_error();
725       } 
726   }
727
728
729   if (y > ctx->y)
730     art_svp_intersect_push_pt (ctx, seg, x, y);
731   else
732     {
733       if(y < ctx->y) {
734           art_warn("intersect_break at a y above the current scanline (%.16f < %.16f)", y, ctx->y);
735           art_report_error();
736       }
737       seg->x[0] = x;
738       seg->y0 = y;
739       seg->horiz_x = x;
740       art_svp_intersect_add_horiz (ctx, seg);
741     }
742
743   return x;
744 }
745
746 /**
747  * art_svp_intersect_add_point: Add a point, breaking nearby neighbors.
748  * @ctx: Intersector context.
749  * @x: X coordinate of point to add.
750  * @y: Y coordinate of point to add.
751  * @seg: "nearby" segment, or NULL if leftmost.
752  *
753  * Return value: Segment immediately to the left of the new point, or
754  * NULL if the new point is leftmost.
755  **/
756 static ArtActiveSeg *
757 art_svp_intersect_add_point (ArtIntersectCtx *ctx, double x, double y,
758                              ArtActiveSeg *seg, int break_flags)
759 {
760   ArtActiveSeg *left, *right;
761   double x_min = x, x_max = x;
762   art_boolean left_live, right_live;
763   double d;
764   double new_x;
765   ArtActiveSeg *test, *result = NULL;
766   double x_test;
767
768   left = seg;
769   if (left == NULL)
770     right = ctx->active_head;
771   else
772     right = left->right; 
773   left_live = (break_flags & ART_BREAK_LEFT) && (left != NULL);
774   right_live = (break_flags & ART_BREAK_RIGHT) && (right != NULL);
775
776 #ifdef VERBOSE
777   double dd = 0;
778   if(seg)
779       dd = seg->a*x + seg->b*y + seg->c;
780   art_dprint("add_point seg=%08x %f,%f%s%s (left=%08x, right=%08x) d=%f\n", seg, x, y, 
781           break_flags&ART_BREAK_LEFT?" BREAK_LEFT":"",
782           break_flags&ART_BREAK_LEFT?" BREAK_RIGHT":"",
783           seg?seg->left:0, seg?seg->right:0, dd);
784 #endif
785   /* add_point relies on the fact that the active list is ascending-
786      no checks are done for lines which are not in strict order.
787
788      a point position (x,y) is tested against left (if break_flags&ART_BREAK_LEFT)
789      and right (if break_flags&ART_BREAK_RIGHT) neighboring segments which are
790      within EPSILON_A distance of the point. If they are, they are split at y. 
791      For ART_BREAK_LEFT, the "intersection point" on the line (which is to the left
792      of (x,y) will never be to the right of "our" (x,y)- new_x will be shifted
793      by _break to make sure of that. (Which should only happen for horizontal
794      line segments) Likewise for ART_BREAK_RIGHT. 
795
796      The horizontal area around (x,y) (x_min, x_max) will be extended into the
797      break direction for every cut we make.
798    */
799                   
800   //new_x = art_svp_intersect_break (ctx, left, x_min, y, ART_BREAK_LEFT);
801
802   while (left_live || right_live)
803     {
804 #ifdef VERBOSE
805       art_dprint("  left: %08x (%d) right: %08x (%d)\n", left, left_live, right, right_live);
806 #endif
807       if (left_live)
808         {
809           if (x <= left->x[left->flags & ART_ACTIVE_FLAGS_BNEG] &&
810               /* It may be that one of these conjuncts turns out to be always
811                  true. We test both anyway, to be defensive. */
812               y != left->y0 && y < left->y1)
813             {
814               d = x_min * left->a + y * left->b + left->c;
815               if (d < EPSILON_A)
816                 {
817                   new_x = art_svp_intersect_break (ctx, left, x_min, y,
818                                                    ART_BREAK_LEFT);
819 #ifdef VERBOSE
820                   art_dprint("break %08x at x<=%.16f,y=%.16f, new_x=%f\n", left, x_min, y, new_x);
821 #endif
822                   if (new_x > x_max)
823                     {
824                       x_max = new_x;
825                       right_live = (right != NULL);
826                     }
827                   else if (new_x < x_min)
828                     x_min = new_x;
829                   left = left->left;
830                   left_live = (left != NULL);
831                 }
832               else
833                 left_live = ART_FALSE;
834             }
835           else
836             left_live = ART_FALSE;
837         }
838       else if (right_live)
839         {
840           if (x >= right->x[(right->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] &&
841               /* It may be that one of these conjuncts turns out to be always
842                  true. We test both anyway, to be defensive. */
843               y != right->y0 && y < right->y1)
844             {
845               d = x_max * right->a + y * right->b + right->c;
846               if (d > -EPSILON_A)
847                 {
848                   new_x = art_svp_intersect_break (ctx, right, x_max, y,
849                                                    ART_BREAK_RIGHT);
850 #ifdef VERBOSE
851                   art_dprint("break %08x at x>=%.16f,y=%.16f, new_x=%f\n", right, x_max, y, new_x);
852 #endif
853                   if (new_x < x_min)
854                     {
855                       x_min = new_x;
856                       left_live = (left != NULL);
857                     }
858                   else if (new_x >= x_max)
859                     x_max = new_x;
860                   right = right->right;
861                   right_live = (right != NULL);
862                 }
863               else
864                 right_live = ART_FALSE;
865             }
866           else
867             right_live = ART_FALSE;
868         }
869     }
870
871   /* Ascending order is guaranteed by break_flags. Thus, we don't need
872      to actually fix up non-ascending pairs. */
873
874   /* Now, (left, right) defines an interval of segments broken. Sort
875      into ascending x order. (find segment to the left of the new point) */
876   test = left == NULL ? ctx->active_head : left->right;
877   result = left;
878   if (test != NULL && test != right)
879     {
880       if (y == test->y0)
881         x_test = test->x[0];
882       else if(y == test->y1)
883         x_test = test->x[1];
884       else {
885         art_warn ("internal error in add_point: y=%.16f is between %.16f and %.16f\n", y, test->y0, test->y1);
886         x_test = test->x[1];
887         art_report_error();
888       }
889
890       for (;;)
891         {
892           if (x_test <= x)
893             result = test;
894           test = test->right;
895           if (test == right)
896             break;
897
898           /* FIXME the following code doesn't do anything (?) */
899           new_x = x_test;
900           if (new_x < x_test)
901             {
902               art_warn ("art_svp_intersect_add_point: non-ascending x\n");
903             }
904           x_test = new_x;
905         }
906     }
907   return result;
908 }
909
910 static void
911 art_svp_intersect_swap_active (ArtIntersectCtx *ctx,
912                                ArtActiveSeg *left_seg, ArtActiveSeg *right_seg)
913 {
914   if((left_seg && left_seg->right != right_seg) ||
915      (right_seg && right_seg->left != left_seg)) {
916       art_warn("error: active list in disarray\n");
917       art_report_error();
918   }
919
920   right_seg->left = left_seg->left;
921   if (right_seg->left != NULL)
922     right_seg->left->right = right_seg;
923   else
924     ctx->active_head = right_seg;
925   left_seg->right = right_seg->right;
926   if (left_seg->right != NULL)
927     left_seg->right->left = left_seg;
928   left_seg->left = right_seg;
929   right_seg->right = left_seg;
930 }
931
932 volatile char add0 = 0;
933 static double double_precision(double x)
934 {
935     /* make sure x has exactly 11 bits exponent and 52 bit mantissa-
936        there is probably a more elegant (or faster) way to trick the compiler
937        into doing this, but this works for now. */
938     unsigned char xx[8];
939     *(double*)xx = x;
940     xx[0]+=add0; xx[1]+=add0; xx[2]+=add0; xx[3]+=add0;
941     xx[4]+=add0; xx[5]+=add0; xx[6]+=add0; xx[7]+=add0;
942     return *(double*)xx;
943 }
944
945 /**
946  * art_svp_intersect_test_cross: Test crossing of a pair of active segments.
947  * @ctx: Intersector context.
948  * @left_seg: Left segment of the pair.
949  * @right_seg: Right segment of the pair.
950  * @break_flags: Flags indicating whether to break neighbors.
951  *
952  * Tests crossing of @left_seg and @right_seg. If there is a crossing,
953  * inserts the intersection point into both segments.
954  *
955  * Return value: True if the intersection took place at the current
956  * scan line, indicating further iteration is needed.
957  **/
958 static art_boolean
959 art_svp_intersect_test_cross (ArtIntersectCtx *ctx,
960                               ArtActiveSeg *left_seg, ArtActiveSeg *right_seg,
961                               int break_flags)
962 {
963   double left_x0, left_y0, left_x1;
964   double left_y1 = left_seg->y1;
965   double right_y1 = right_seg->y1;
966   double d;
967
968   const ArtSVPSeg *in_seg;
969   int in_curs;
970   double d0, d1, t;
971   double x, y; /* intersection point */
972
973 #ifdef VERBOSE 
974   static int count = 0;
975
976   art_dprint ("art_svp_intersect_test_cross %08x <-> %08x: count=%d\n",
977           (unsigned long)left_seg, (unsigned long)right_seg, count++);
978   art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", left_seg, 
979           left_seg->x[0], left_seg->y0,
980           left_seg->x[1], left_seg->y1);
981   art_dprint ("(full:     %.16f,%.16f -> %.16f %.16f)\n", 
982           left_seg->in_seg->points[left_seg->in_curs - 1].x, left_seg->in_seg->points[left_seg->in_curs - 1].y,
983           left_seg->in_seg->points[left_seg->in_curs].x, left_seg->in_seg->points[left_seg->in_curs].y
984           );
985
986   art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg, 
987           right_seg->x[0], right_seg->y0,
988           right_seg->x[1], right_seg->y1);
989   art_dprint ("(full:     %.16f,%.16f -> %.16f %.16f)\n", 
990           right_seg->in_seg->points[right_seg->in_curs - 1].x, right_seg->in_seg->points[right_seg->in_curs - 1].y,
991           right_seg->in_seg->points[right_seg->in_curs].x, right_seg->in_seg->points[right_seg->in_curs].y
992           );
993 #endif
994
995 #ifdef CHEAP_SANITYCHECK
996   if (right_seg->x[0] < left_seg->x[(left_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) {
997       /* notice: if we test *only* the line equation here, dd might be < 0, even though
998          right_seg was inserted to the right of left_seg correctly, due to numerical
999          instabilities */
1000       double dd = right_seg->x[0] * left_seg->a + right_seg->y0 * left_seg->b + left_seg->c;
1001       if(dd < 0) {
1002           //art_warn ("segment %08x[%d] isn't to the left of %08x[%d]. d=%.16f\n", 
1003           //        left_seg, left_seg->n_stack,
1004           //        right_seg, right_seg->n_stack,
1005           //        dd);
1006       }
1007   }
1008 #endif
1009
1010   if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0])
1011     {
1012       /* Top points of left and right segments coincide. This case
1013          feels like a bit of duplication - we may want to merge it
1014          with the cases below. However, this way, we're sure that this
1015          logic makes only localized changes. */
1016
1017       if (left_y1 < right_y1)
1018         {
1019           /* Test left (x1, y1) against right segment */
1020           double left_x1 = left_seg->x[1];
1021
1022           if (left_x1 <
1023               right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
1024               left_y1 == right_seg->y0)
1025             return ART_FALSE;
1026           d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1027           if (d < -EPSILON_A)
1028             
1029               return ART_FALSE;
1030           else if (d < EPSILON_A) /* should we use zero here? */
1031             {
1032 #ifdef VERBOSE 
1033                 art_dprint("break %08x because of common top point, left_y1 < right_y1\n", right_seg);
1034 #endif
1035               /* I'm unsure about the break flags here. */
1036               double right_x1 = art_svp_intersect_break (ctx, right_seg,
1037                                                          left_x1, left_y1,
1038                                                          ART_BREAK_RIGHT);
1039               
1040               /* this is always true due to ART_BREAK_RIGHT right_x1>=left_x1 if 
1041                  _break uses x_ref clipping */
1042               if (left_x1 <= right_x1) {
1043                 return ART_FALSE;
1044               }
1045             }
1046         }
1047       else if (left_y1 > right_y1)
1048         {
1049           /* Test right (x1, y1) against left segment */
1050           double right_x1 = right_seg->x[1];
1051
1052           if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
1053               right_y1 == left_seg->y0)
1054             
1055               return ART_FALSE;
1056           d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
1057           if (d > EPSILON_A)
1058             return ART_FALSE;
1059           else if (d > -EPSILON_A) /* should we use zero here? */
1060             {
1061 #ifdef VERBOSE 
1062               art_dprint("break %08x because of common top point, left_y1 > right_y1\n", left_seg);
1063 #endif
1064               /* See above regarding break flags. */
1065               double left_x1 = art_svp_intersect_break (ctx, left_seg,
1066                                                         right_x1, right_y1,
1067                                                         ART_BREAK_LEFT);
1068
1069               /* this is always true, due to ART_BREAK_LEFT left_x1<=right_x1, if
1070                  _break uses x_ref clipping
1071                */
1072               if (left_x1 <= right_x1) {
1073                 return ART_FALSE;
1074               }
1075             }
1076         }
1077       else /* left_y1 == right_y1 */
1078         {
1079           double left_x1 = left_seg->x[1];
1080           double right_x1 = right_seg->x[1];
1081
1082           
1083           if (left_x1 <= right_x1)
1084             return ART_FALSE;
1085         }
1086
1087       //int wind_left = left_seg->wind_left;
1088       //int wind_right = right_seg->wind_left;
1089       art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1090       //left_seg->wind_left = wind_right;
1091       //right_seg->wind_left = wind_left;
1092
1093       return ART_TRUE;
1094     }
1095
1096   if (left_y1 < right_y1)
1097     {
1098       /* Test left (x1, y1) against right segment */
1099       double left_x1 = left_seg->x[1];
1100
1101       if (left_x1 <
1102           right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
1103           left_y1 == right_seg->y0)
1104         return ART_FALSE;
1105
1106       if(left_y1 < right_seg->y0) {
1107           art_warn("left_y1 < right_seg->y0\n");
1108           return ART_FALSE;
1109       }
1110
1111       /* we might want to output a warning for left_y1 < right_seg->y0 */
1112
1113       d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1114       if (d < -EPSILON_A)
1115         return ART_FALSE;
1116       else if (d < EPSILON_A)
1117         {
1118 #ifdef VERBOSE 
1119           art_dprint("break %08x at %.16f because left_y1 < right_y1\n", right_seg, left_y1);
1120           art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg, 
1121                   right_seg->x[0], right_seg->y0,
1122                   right_seg->x[1], right_seg->y1);
1123 #endif
1124           double right_x1 = art_svp_intersect_break (ctx, right_seg,
1125                                                      left_x1, left_y1,
1126                                                      ART_BREAK_RIGHT);
1127 #ifdef VERBOSE 
1128           art_dprint("after break:\n", right_seg);
1129           art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg, 
1130                   right_seg->x[0], right_seg->y0,
1131                   right_seg->x[1], right_seg->y1);
1132 #endif
1133           /* this is always true if _break uses x_ref clipping */
1134           if (left_x1 <= right_x1)
1135             return ART_FALSE;
1136         }
1137     }
1138   else if (left_y1 > right_y1)
1139     {
1140       /* Test right (x1, y1) against left segment */
1141       double right_x1 = right_seg->x[1];
1142
1143       if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
1144           right_y1 == left_seg->y0)
1145         return ART_FALSE;
1146       
1147       if(right_y1 < left_seg->y0) {
1148           art_warn("left_y1 < right_seg->y0\n");
1149           return ART_FALSE;
1150       }
1151       
1152       /* we might want to output a warning for right_y1 < left_seg->y0 */
1153
1154       d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
1155       if (d > EPSILON_A)
1156         return ART_FALSE;
1157       else if (d > -EPSILON_A)
1158         {
1159 #ifdef VERBOSE 
1160           art_dprint("break %08x because left_y1 > right_y1\n", right_seg);
1161 #endif
1162           double left_x1 = art_svp_intersect_break (ctx, left_seg,
1163                                                     right_x1, right_y1,
1164                                                     ART_BREAK_LEFT);
1165           /* this is always true if _break uses x_ref clipping */
1166           if (left_x1 <= right_x1)
1167             return ART_FALSE;
1168         }
1169     }
1170   else /* left_y1 == right_y1 */
1171     { 
1172       double left_x1 = left_seg->x[1];
1173       double right_x1 = right_seg->x[1];
1174
1175       if (left_x1 <= right_x1)
1176         return ART_FALSE;
1177     }
1178
1179
1180   /* The segments cross. Find the intersection point. */
1181
1182   in_seg = left_seg->in_seg;
1183   in_curs = left_seg->in_curs;
1184   left_x0 = in_seg->points[in_curs - 1].x;
1185   left_y0 = in_seg->points[in_curs - 1].y;
1186   left_x1 = in_seg->points[in_curs].x;
1187   left_y1 = in_seg->points[in_curs].y;
1188
1189 #if 0
1190   /* check for endpoint = firstpoint cases */
1191   if(left_seg->y0 == right_seg->y1 && left_seg->x[0] == right_seg->x[1])
1192       return ART_FALSE;
1193   if(left_seg->y1 == right_seg->y0 && left_seg->x[1] == right_seg->x[0])
1194       return ART_FALSE;
1195 #endif
1196
1197   d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c;
1198   d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1199   if (d0 == d1)
1200     {
1201       x = left_x0;
1202       y = left_y0;
1203     }
1204   else
1205     {
1206       /* Is this division always safe? It could possibly overflow. */
1207       t = d0 / (d0 - d1);
1208       if (t <= 0)
1209         {
1210           x = left_x0;
1211           y = left_y0;
1212         }
1213       else if (t >= 1)
1214         {
1215           x = left_x1;
1216           y = left_y1;
1217         }
1218       else
1219         {
1220           x = left_x0 + t * (left_x1 - left_x0);
1221           y = left_y0 + t * (left_y1 - left_y0);
1222         }
1223     }
1224
1225   /* Make sure intersection point is within bounds of right seg. */
1226   if (y < right_seg->y0)
1227     {
1228       x = right_seg->x[0];
1229       y = right_seg->y0;
1230     }
1231   else if (y > right_seg->y1)
1232     {
1233       x = right_seg->x[1];
1234       y = right_seg->y1;
1235     }
1236   else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1])
1237     x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1];
1238   else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG])
1239     x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG];
1240
1241   x = double_precision(x);
1242   y = double_precision(y);
1243
1244   assert(ctx->y >= left_seg->y0);
1245 #ifdef VERBOSE
1246   art_dprint ("intersect at %.16f %.16f\n", x, y);
1247 #endif
1248
1249
1250   if(y < ctx->y) {
1251       /* as we use the full segment length (not just the subsegment currently
1252          under evaluation), intersection points may be above the current scanline.
1253          As we're not able to process these anymore, we also don't need to add
1254          anything to the active list or pq.
1255
1256          Intersection points above the current scanline happen if an
1257          intersection is handled twice- once when the line is inserted, and
1258          once when e.g. some other intersection point triggers insert_cross.
1259       */
1260       art_warn ("previously unhandled intersection point %.16f %.16f (dy=%.16f)\n", x, y, ctx->y - y);
1261       return ART_FALSE;
1262   }
1263   
1264   if(y > left_seg->y1) {
1265       /* not within the subsegment we're currently looking into- this is not an intersection */
1266       return ART_FALSE;
1267   }
1268
1269   if (y == left_seg->y0)
1270     {
1271       if (y != right_seg->y0)
1272         {
1273 #ifdef VERBOSE
1274           art_dprint ("art_svp_intersect_test_cross: intersection (%.16f, %.16f) matches former y0 of %08x, [%08x]\n",
1275                     x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1276 #endif
1277           art_svp_intersect_push_pt (ctx, right_seg, x, y);
1278           if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1279             art_svp_intersect_add_point (ctx, x, y, right_seg->right,
1280                                          break_flags);
1281         }
1282       else
1283         {
1284 #ifdef VERBOSE
1285           art_dprint ("art_svp_intersect_test_cross: intersection (%.16f, %.16f) at current scan line (y=ly0=ry0)\n",
1286                     x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1287 #endif
1288           /* Intersection takes place at current scan line, with
1289              left->x0 <= x <= right->x0, left->x0 != right->x0.
1290
1291              This happens if one of the lines is horizontal, or very near
1292              horizontal. (true horizontal lines are processed by _horiz())
1293              
1294              Process immediately rather than queueing intersection point into
1295              priq. */
1296           ArtActiveSeg *winner, *loser;
1297
1298           /* Choose "most vertical" segement */
1299           if (left_seg->a > right_seg->a)
1300             {
1301               winner = left_seg;
1302               loser = right_seg;
1303             }
1304           else
1305             {
1306               winner = right_seg;
1307               loser = left_seg;
1308             }
1309 #ifdef VERBOSE
1310           art_dprint ("           x = %.16f\n", x);
1311           art_dprint (" loser->x[0] = %.16f\n", loser->x[0]);
1312           art_dprint ("winner->x[0] = %.16f\n", winner->x[0]);
1313 #endif
1314           loser->x[0] = winner->x[0];
1315           loser->horiz_x = loser->x[0];
1316           loser->horiz_delta_wind += loser->delta_wind;
1317           winner->horiz_delta_wind -= loser->delta_wind;
1318
1319           art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1320           return ART_TRUE;
1321         }
1322     }
1323   else if (y == right_seg->y0)
1324     {
1325 #ifdef VERBOSE
1326       art_dprint ("*** art_svp_intersect_test_cross: intersection (%.16f, %.16f) matches latter y0 of [%08x], %08x\n",
1327               x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1328       art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", left_seg, 
1329               left_seg->x[0], left_seg->y0,
1330               left_seg->x[1], left_seg->y1);
1331       art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg, 
1332               right_seg->x[0], right_seg->y0,
1333               right_seg->x[1], right_seg->y1);
1334
1335 #endif
1336       art_svp_intersect_push_pt (ctx, left_seg, x, y);
1337       if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1338         art_svp_intersect_add_point (ctx, x, y, left_seg->left,
1339                                      break_flags);
1340     }
1341   else
1342     {
1343 #ifdef VERBOSE
1344       art_dprint ("Inserting (%.16f, %.16f) into %08x, %08x\n",
1345               x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1346 #endif
1347       /* Insert the intersection point into both segments. */
1348       art_svp_intersect_push_pt (ctx, left_seg, x, y);
1349       art_svp_intersect_push_pt (ctx, right_seg, x, y);
1350       if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1351         art_svp_intersect_add_point (ctx, x, y, left_seg->left, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1352       if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1353         art_svp_intersect_add_point (ctx, x, y, right_seg->right, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1354     }
1355   return ART_FALSE;
1356 }
1357
1358 /**
1359  * art_svp_intersect_active_delete: Delete segment from active list.
1360  * @ctx: Intersection context.
1361  * @seg: Segment to delete.
1362  *
1363  * Deletes @seg from the active list.
1364  **/
1365 static /* todo inline */ void
1366 art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1367 {
1368   ArtActiveSeg *left = seg->left, *right = seg->right;
1369
1370   if (left != NULL)
1371     left->right = right;
1372   else
1373     ctx->active_head = right;
1374   if (right != NULL)
1375     right->left = left;
1376 }
1377
1378 /**
1379  * art_svp_intersect_active_free: Free an active segment.
1380  * @seg: Segment to delete.
1381  *
1382  * Frees @seg.
1383  **/
1384 static /* todo inline */ void
1385 art_svp_intersect_active_free (ArtActiveSeg *seg)
1386 {
1387   art_free (seg->stack);
1388 #ifdef VERBOSE
1389   art_dprint ("Freeing %08x\n", (unsigned long) seg);
1390 #else
1391   // !!!
1392   art_free (seg);
1393 #endif
1394 }
1395
1396 /**
1397  * art_svp_intersect_insert_cross: Test crossings of newly inserted line.
1398  *
1399  * Tests @seg against its left and right neighbors for intersections.
1400  * Precondition: the line in @seg is not purely horizontal.
1401  **/
1402 static void
1403 art_svp_intersect_insert_cross (ArtIntersectCtx *ctx,
1404                                 ArtActiveSeg *seg)
1405 {
1406   ArtActiveSeg *left = seg, *right = seg;
1407
1408   for (;;)
1409     {
1410       if (left != NULL)
1411         {
1412           ArtActiveSeg *leftc;
1413
1414           for (leftc = left->left; leftc != NULL; leftc = leftc->left)
1415             if (!(leftc->flags & ART_ACTIVE_FLAGS_DEL))
1416               break;
1417           if (leftc != NULL &&
1418               art_svp_intersect_test_cross (ctx, leftc, left,
1419                                             ART_BREAK_LEFT))
1420             {
1421               if (left == right || right == NULL)
1422                 right = left->right;
1423             }
1424           else
1425             {
1426               left = NULL;
1427             }
1428         }
1429       else if (right != NULL && right->right != NULL)
1430         {
1431           ArtActiveSeg *rightc;
1432
1433           for (rightc = right->right; rightc != NULL; rightc = rightc->right)
1434             if (!(rightc->flags & ART_ACTIVE_FLAGS_DEL))
1435               break;
1436           if (rightc != NULL &&
1437               art_svp_intersect_test_cross (ctx, right, rightc,
1438                                             ART_BREAK_RIGHT))
1439             {
1440               if (left == right || left == NULL)
1441                 left = right->left;
1442             }
1443           else
1444             {
1445               right = NULL;
1446             }
1447         }
1448       else
1449         break;
1450     }
1451 }
1452
1453 /**
1454  * art_svp_intersect_horiz: Add horizontal line segment.
1455  * @ctx: Intersector context.
1456  * @seg: Segment on which to add horizontal line.
1457  * @x0: Old x position.
1458  * @x1: New x position.
1459  *
1460  * Adds a horizontal line from @x0 to @x1, and updates the current
1461  * location of @seg to @x1.
1462  **/
1463 static void
1464 art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1465                          double x0, double x1)
1466 {
1467   ArtActiveSeg *hs;
1468
1469   if (x0 == x1)
1470     return;
1471
1472 #ifdef VERBOSE
1473   art_dprint("horiz: seg=%08x x0=%f x1=%f segid=%08x flags=%s delta_wind=%d\n", seg, x0, x1, seg->seg_id,
1474           seg->flags & ART_ACTIVE_FLAGS_OUT?"out":"", seg->delta_wind);
1475 #endif
1476
1477   hs = art_new (ArtActiveSeg, 1);
1478
1479   hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT);
1480   if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1481     {
1482       ArtSvpWriter *swr = ctx->out;
1483
1484       swr->add_point (swr, seg->seg_id, x0, ctx->y);
1485     }
1486   hs->seg_id = seg->seg_id;
1487   hs->horiz_x = x0;
1488   hs->horiz_delta_wind = seg->delta_wind;
1489   hs->stack = NULL;
1490
1491   /* Ideally, the (a, b, c) values will never be read. However, there
1492      are probably some tests remaining that don't check for _DEL
1493      before evaluating the line equation. For those, these
1494      initializations will at least prevent a UMR of the values, which
1495      can crash on some platforms. */
1496   hs->a = 0.0;
1497   hs->b = 0.0;
1498   hs->c = 0.0;
1499
1500   seg->horiz_delta_wind -= seg->delta_wind;
1501
1502   art_svp_intersect_add_horiz (ctx, hs);
1503
1504   if (x0 > x1)
1505     {
1506       ArtActiveSeg *left;
1507       art_boolean first = ART_TRUE;
1508
1509       for (left = seg->left; left != NULL; left = seg->left)
1510         {
1511           int left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG;
1512
1513           if (left->x[left_bneg] <= x1)
1514             break;
1515           if (left->x[left_bneg ^ 1] <= x1 &&
1516               x1 * left->a + ctx->y * left->b + left->c >= 0)
1517             break;
1518           if (left->y0 != ctx->y && left->y1 != ctx->y)
1519             {
1520               art_svp_intersect_break (ctx, left, x1, ctx->y, ART_BREAK_LEFT);
1521             }
1522 #ifdef VERBOSE
1523           art_dprint ("x0=%.16f > x1=%.16f, swapping %08x, %08x\n",
1524                   x0, x1, (unsigned long)left, (unsigned long)seg);
1525 #endif
1526           art_svp_intersect_swap_active (ctx, left, seg);
1527           if (first && left->right != NULL)
1528             {
1529               art_svp_intersect_test_cross (ctx, left, left->right,
1530                                             ART_BREAK_RIGHT);
1531               first = ART_FALSE;
1532             }
1533         }
1534     }
1535   else
1536     {
1537       ArtActiveSeg *right;
1538       art_boolean first = ART_TRUE;
1539
1540       for (right = seg->right; right != NULL; right = seg->right)
1541         {
1542           int right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG;
1543
1544           if (right->x[right_bneg ^ 1] >= x1)
1545             break;
1546           if (right->x[right_bneg] >= x1 &&
1547               x1 * right->a + ctx->y * right->b + right->c <= 0)
1548             break;
1549           if (right->y0 != ctx->y && right->y1 != ctx->y)
1550             {
1551               art_svp_intersect_break (ctx, right, x1, ctx->y,
1552                                        ART_BREAK_LEFT);
1553             }
1554 #ifdef VERBOSE
1555           art_dprint ("[right]x0=%.16f < x1=%.16f, swapping %08x, %08x\n",
1556                   x0, x1, (unsigned long)seg, (unsigned long)right);
1557 #endif
1558           art_svp_intersect_swap_active (ctx, seg, right);
1559           if (first && right->left != NULL)
1560             {
1561               art_svp_intersect_test_cross (ctx, right->left, right,
1562                                             ART_BREAK_RIGHT);
1563               first = ART_FALSE;
1564             }
1565         }
1566     }
1567
1568   seg->x[0] = x1;
1569   seg->x[1] = x1;
1570   seg->horiz_x = x1;
1571   seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1572 }
1573
1574 /**
1575  * art_svp_intersect_insert_line: Insert a line into the active list.
1576  * @ctx: Intersector context.
1577  * @seg: Segment containing line to insert.
1578  *
1579  * Inserts the line into the intersector context, taking care of any
1580  * intersections, and adding the appropriate horizontal points to the
1581  * active list.
1582  **/
1583 static void
1584 art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1585 {
1586   if (seg->y1 == seg->y0)
1587     {
1588 #ifdef VERBOSE
1589       art_dprint ("art_svp_intersect_insert_line(%d): %08x is horizontal\n", seg->flags&ART_ACTIVE_FLAGS_IN_ACTIVE, (unsigned long)seg);
1590 #endif
1591       art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]);
1592     }
1593   else
1594     {
1595 #ifdef VERBOSE
1596       art_dprint ("art_svp_intersect_insert_line(%d): %08x is non-horizontal\n", seg->flags&ART_ACTIVE_FLAGS_IN_ACTIVE, (unsigned long)seg);
1597 #endif
1598       art_svp_intersect_insert_cross (ctx, seg);
1599       art_svp_intersect_add_horiz (ctx, seg);
1600     }
1601
1602   seg->flags |= ART_ACTIVE_FLAGS_IN_ACTIVE; //q
1603 }
1604
1605 static void
1606 art_svp_intersect_process_intersection (ArtIntersectCtx *ctx,
1607                                         ArtActiveSeg *seg)
1608 {
1609   int n_stack = --seg->n_stack;
1610   seg->x[1] = seg->stack[n_stack - 1].x;
1611   seg->y1 = seg->stack[n_stack - 1].y;
1612   seg->x[0] = seg->stack[n_stack].x;
1613   seg->y0 = seg->stack[n_stack].y;
1614   seg->horiz_x = seg->x[0];
1615 #ifdef VERBOSE
1616   art_dprint("process intersection %08x (%.16f,%.16f-%.16f,%.16f)\n", seg, seg->x[0], seg->y0, seg->x[1], seg->y1);
1617 #endif
1618   art_svp_intersect_insert_line (ctx, seg);
1619 }
1620
1621 static void
1622 art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1623                                   ArtPriPoint *pri_pt)
1624 {
1625   const ArtSVPSeg *in_seg = seg->in_seg;
1626   int in_curs = seg->in_curs;
1627   ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL;
1628
1629   if (swr != NULL)
1630     swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1);
1631   if (in_curs + 1 >= in_seg->n_points)
1632     {
1633       ArtActiveSeg *left = seg->left, *right = seg->right;
1634
1635 #if 0
1636       if (swr != NULL)
1637         swr->close_segment (swr, seg->seg_id);
1638       seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1639 #endif
1640       seg->flags |= ART_ACTIVE_FLAGS_DEL;
1641       art_svp_intersect_add_horiz (ctx, seg);
1642       art_svp_intersect_active_delete (ctx, seg);
1643       if (left != NULL && right != NULL)
1644         art_svp_intersect_test_cross (ctx, left, right,
1645                                       ART_BREAK_LEFT | ART_BREAK_RIGHT);
1646       art_free (pri_pt);
1647     }
1648   else
1649     {
1650       seg->horiz_x = seg->x[1];
1651
1652       art_svp_intersect_setup_seg (seg, pri_pt);
1653       art_pri_insert (ctx->pq, pri_pt);
1654       art_svp_intersect_insert_line (ctx, seg);
1655     }
1656 }
1657
1658 static void
1659 art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg)
1660 {
1661   ArtActiveSeg *seg = art_new (ArtActiveSeg, 1);
1662   ArtActiveSeg *test;
1663   double x0, y0;
1664   ArtActiveSeg *beg_range;
1665   ArtActiveSeg *last = NULL;
1666   ArtActiveSeg *left, *right;
1667   ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1);
1668
1669   seg->flags = 0;
1670   seg->in_seg = in_seg;
1671   seg->in_curs = 0;
1672
1673   seg->n_stack_max = 4;
1674   seg->stack = art_new (ArtPoint, seg->n_stack_max);
1675
1676   seg->horiz_delta_wind = 0;
1677   
1678   seg->wind_left = 0;
1679
1680   pri_pt->user_data = seg;
1681   art_svp_intersect_setup_seg (seg, pri_pt);
1682   art_pri_insert (ctx->pq, pri_pt);
1683
1684   /* Find insertion place for new segment */
1685   /* This is currently a left-to-right scan, but should be replaced
1686      with a binary search as soon as it's validated. */
1687
1688   x0 = in_seg->points[0].x;
1689   y0 = in_seg->points[0].y;
1690   beg_range = NULL;
1691   for (test = ctx->active_head; test != NULL; test = test->right)
1692     {
1693       double d;
1694       int test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG;
1695
1696       if (x0 < test->x[test_bneg])
1697         {
1698           if (x0 < test->x[test_bneg ^ 1]) {
1699 #ifdef VERBOSE
1700             art_dprint("inserting segment %08x before %08x (x0 < xmin)\n", seg, test);
1701 #endif
1702             break;
1703           }
1704           d = x0 * test->a + y0 * test->b + test->c;
1705           if (d < 0) {
1706 #ifdef VERBOSE
1707             art_dprint("inserting segment %08x before %08x (d = %.16f)\n", seg, test, d);
1708 #endif
1709             break;
1710           }
1711 #ifdef VERBOSE
1712           art_dprint("segment %08x is to the right of %08x d=%.16f\n", seg, test, d);
1713 #endif
1714         } else {
1715 #ifdef VERBOSE
1716             d = x0 * test->a + y0 * test->b + test->c;
1717             art_dprint("segment %08x is to the right of %08x d=%.16f (not used)\n", seg, test, d);
1718 #endif
1719         }
1720       last = test;
1721     }
1722
1723   left = art_svp_intersect_add_point (ctx, x0, y0, last, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1724
1725 #ifdef VERBOSE
1726   art_dprint("left=%08x x0=%.16f y=%.16f\n", left, x0, y0);
1727 #endif
1728
1729   seg->left = left;
1730   if (left == NULL)
1731     {
1732       right = ctx->active_head;
1733       ctx->active_head = seg;
1734     }
1735   else
1736     {
1737       right = left->right;
1738       left->right = seg;
1739     }
1740   seg->right = right;
1741   if (right != NULL)
1742     right->left = seg;
1743
1744   seg->delta_wind = in_seg->dir ? 1 : -1;
1745   seg->horiz_x = x0;
1746
1747   art_svp_intersect_insert_line (ctx, seg);
1748 }
1749
1750 #ifdef SANITYCHECK
1751 static void
1752 art_svp_intersect_sanitycheck_winding (ArtIntersectCtx *ctx)
1753 {
1754 #if 0
1755   /* At this point, we seem to be getting false positives, so it's
1756      turned off for now. */
1757
1758   ArtActiveSeg *seg;
1759   int winding_number = 0;
1760
1761   for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1762     {
1763       /* Check winding number consistency. */
1764       if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1765         {
1766           if (winding_number != seg->wind_left)
1767             art_warn ("*** art_svp_intersect_sanitycheck_winding: seg %08x has wind_left of %d, expected %d\n",
1768                   (unsigned long) seg, seg->wind_left, winding_number);
1769           winding_number = seg->wind_left + seg->delta_wind;
1770         }
1771     }
1772   if (winding_number != 0)
1773     art_warn ("*** art_svp_intersect_sanitycheck_winding: non-balanced winding number %d\n",
1774               winding_number);
1775 #endif
1776 }
1777 #endif
1778
1779 /**
1780  * art_svp_intersect_horiz_commit: Commit points in horiz list to output.
1781  * @ctx: Intersection context.
1782  *
1783  * The main function of the horizontal commit is to output new
1784  * points to the output writer.
1785  *
1786  * This "commit" pass is also where winding numbers are assigned,
1787  * because doing it here provides much greater tolerance for inputs
1788  * which are not in strict SVP order.
1789  *
1790  * Each cluster in the horiz_list contains both segments that are in
1791  * the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not,
1792  * and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We
1793  * need to deal with both.
1794  **/
1795 static void
1796 art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx)
1797 {
1798   ArtActiveSeg *seg;
1799   int winding_number = 0; /* initialization just to avoid warning */
1800   int horiz_wind = 0;
1801   double last_x = 0; /* initialization just to avoid warning */
1802
1803 #ifdef VERBOSE
1804   art_dprint ("art_svp_intersect_horiz_commit: y=%.16f\n", ctx->y);
1805   for (seg = ctx->horiz_first; seg != NULL; seg = seg->horiz_right)
1806     art_dprint (" %08x: %.16f %+d segid=%d\n",
1807             (unsigned long)seg, seg->horiz_x, seg->horiz_delta_wind, seg->seg_id);
1808 #endif
1809
1810   /* Output points to svp writer. */
1811   for (seg = ctx->horiz_first; seg != NULL;)
1812     {
1813       /* Find a cluster with common horiz_x, */
1814       ArtActiveSeg *curs;
1815       double x = seg->horiz_x;
1816
1817       /* Generate any horizontal segments. */
1818       if (horiz_wind != 0)
1819         {
1820           ArtSvpWriter *swr = ctx->out;
1821           int seg_id;
1822
1823 #ifdef VERBOSE
1824           art_dprint ("generate horizontal segment: y=%.16f x=%.16f-%.16f wind=%d horiz_wind=%d\n", ctx->y, last_x, x, winding_number, horiz_wind);
1825 #endif
1826           seg_id = swr->add_segment (swr, winding_number, horiz_wind,
1827                                      last_x, ctx->y);
1828           swr->add_point (swr, seg_id, x, ctx->y);
1829           swr->close_segment (swr, seg_id);
1830         }
1831
1832       /* Find first active segment in cluster. */
1833
1834       for (curs = seg; curs != NULL && curs->horiz_x == x;
1835            curs = curs->horiz_right)
1836         if (!(curs->flags & ART_ACTIVE_FLAGS_DEL))
1837           break;
1838
1839       if (curs != NULL && curs->horiz_x == x)
1840         {
1841           /* There exists at least one active segment in this cluster. */
1842
1843           /* Find beginning of cluster. */
1844           for (; curs->left != NULL; curs = curs->left)
1845             if (curs->left->horiz_x != x)
1846               break;
1847
1848           if (curs->left != NULL)
1849             winding_number = curs->left->wind_left + curs->left->delta_wind;
1850           else
1851             winding_number = 0;
1852
1853           do
1854             {
1855 #ifdef VERBOSE
1856               art_dprint (" curs %08x: winding_number = %d += %d\n", (unsigned long)curs, winding_number, curs->delta_wind);
1857 #endif
1858               if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) ||
1859                   curs->wind_left != winding_number)
1860                 {
1861                   ArtSvpWriter *swr = ctx->out;
1862
1863                   if (curs->flags & ART_ACTIVE_FLAGS_OUT)
1864                     {
1865                       swr->add_point (swr, curs->seg_id,
1866                                       curs->horiz_x, ctx->y);
1867                       swr->close_segment (swr, curs->seg_id);
1868                     }
1869
1870                   curs->seg_id = swr->add_segment (swr, winding_number,
1871                                                    curs->delta_wind,
1872                                                    x, ctx->y);
1873                   curs->flags |= ART_ACTIVE_FLAGS_OUT;
1874                 }
1875               curs->wind_left = winding_number;
1876               winding_number += curs->delta_wind;
1877               curs = curs->right;
1878             }
1879           while (curs != NULL && curs->horiz_x == x);
1880         }
1881
1882       /* Skip past cluster. */
1883       do
1884         {
1885           ArtActiveSeg *next = seg->horiz_right;
1886
1887           seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ;
1888           horiz_wind += seg->horiz_delta_wind;
1889           seg->horiz_delta_wind = 0;
1890           if (seg->flags & ART_ACTIVE_FLAGS_DEL)
1891             {
1892               if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1893                 {
1894                   ArtSvpWriter *swr = ctx->out;
1895                   swr->close_segment (swr, seg->seg_id);
1896                 }
1897               art_svp_intersect_active_free (seg);
1898             }
1899           seg = next;
1900         }
1901       while (seg != NULL && seg->horiz_x == x);
1902
1903       last_x = x;
1904     }
1905   ctx->horiz_first = NULL;
1906   ctx->horiz_last = NULL;
1907 #ifdef SANITYCHECK
1908   art_svp_intersect_sanitycheck_winding (ctx);
1909 #endif
1910 }
1911
1912 #ifdef SANITYCHECK
1913 static void
1914 art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx, double y)
1915 {
1916   ArtActiveSeg *seg;
1917   ArtActiveSeg *last = NULL;
1918   double d;
1919
1920 #ifdef VERbOSE
1921   art_dprint ("Active list (y = %.16f (new: %.16f)):\n", ctx->y, y);
1922 #endif
1923
1924   for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1925     {
1926 #ifdef VERBOSE
1927       char c1=' ',c2=' ',e1=' ';
1928       if(seg->y0 > ctx->y) c1='!';
1929       if(seg->y0 > y) c2='!';
1930       if(seg->y0 > seg->y1) e1='E';
1931 #endif
1932
1933       if (seg->left != last)
1934         {
1935           art_warn ("*** art_svp_intersect_sanitycheck: last=%08x, seg->left=%08x\n",
1936                     (unsigned long)last, (unsigned long)seg->left);
1937         }
1938       if (last != NULL)
1939         {
1940           /* pairwise compare with previous seg */
1941
1942           /* First the top. */
1943           if (last->y0 < seg->y0)
1944             {
1945             }
1946           else
1947             {
1948             }
1949
1950           /* Then the bottom. */
1951           if (last->y1 < seg->y1)
1952             {
1953               if (!((last->x[1] <
1954                      seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) ||
1955                     last->y1 == seg->y0))
1956                 {
1957                   d = last->x[1] * seg->a + last->y1 * seg->b + seg->c;
1958                   if (d >= EPSILON_A) {
1959                     art_warn ("*** bottom (%.16f, %.16f) of %08x is not clear of %08x to right (d = %g)\n",
1960                               last->x[1], last->y1, (unsigned long) last,
1961                               (unsigned long) seg, d);
1962                     art_report_error();
1963                   } else {
1964 #ifdef VERBOSE
1965                       art_dprint("is to the left (d=%.16f of previous x1,y1) of\n", d);
1966 #endif
1967                   }
1968                 } else {
1969 #ifdef VERBOSE
1970                     art_dprint("is to the left (previous x1 < next x%d) of\n", (seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1);
1971 #endif
1972                 }
1973             }
1974           else if (last->y1 > seg->y1)
1975
1976             {
1977               if (!((seg->x[1] >
1978                      last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) ||
1979                     seg->y1 == last->y0))
1980               {
1981                 d = seg->x[1] * last->a + seg->y1 * last->b + last->c;
1982                 if (d < -EPSILON_A) {
1983                   art_warn ("*** bottom (%.16f, %.16f) of %08x is not clear of %08x to left (d = %.16f)\n",
1984                               seg->x[1], seg->y1, (unsigned long) seg,
1985                               (unsigned long) last, d);
1986                   art_report_error();
1987                 } else {
1988 #ifdef VERBOSE
1989                   art_dprint("is to the left (d=%.16f of next x1,y1) of\n", d);
1990 #endif
1991                 } 
1992               } else {
1993 #ifdef VERBOSE
1994                   art_dprint("is to the left (next x1 > previous x%d) of\n", last->flags & ART_ACTIVE_FLAGS_BNEG);
1995 #endif
1996               }
1997             }
1998           else
1999             {
2000               if (last->x[1] - seg->x[1] > EPSILON_A) {
2001                 art_warn ("*** bottoms (%.16f, %.16f) of %08x and (%.16f, %.16f) of %08x out of order\n",
2002                           last->x[1], last->y1, (unsigned long)last,
2003                           seg->x[1], seg->y1, (unsigned long)seg);
2004                 art_report_error();
2005               } else {
2006 #ifdef VERBOSE
2007                   art_dprint("is to the left (y1s equal, previous x1 < next x1)\n");
2008 #endif
2009               }
2010             }
2011         }
2012
2013 #ifdef VERBOSE
2014       art_dprint ("%c%08x: %c%c %02d (%.16f, %.16f)-(%.16f, %.16f) ",
2015               e1,
2016               (unsigned long)seg, c1, c2, seg->flags,
2017               seg->x[0], seg->y0, seg->x[1], seg->y1);
2018 #endif
2019
2020       last = seg;
2021     }
2022 #ifdef VERBOSE
2023   art_dprint("\n");
2024 #endif
2025 }
2026 #endif
2027
2028 void
2029 art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out)
2030 {
2031   ArtIntersectCtx *ctx;
2032   ArtPriQ *pq;
2033   ArtPriPoint *first_point;
2034 #ifdef VERBOSE
2035   int count = 0;
2036 #endif
2037
2038   if (in->n_segs == 0)
2039     return;
2040   
2041   current_svp = in;
2042
2043 #ifdef VERBOSE
2044   int t;
2045   art_dprint("Segments: %d\n", in->n_segs);
2046   for(t=0;t<in->n_segs;t++) {
2047       const ArtSVPSeg* seg = &in->segs[t];
2048       art_dprint("Segment %08x(%d): %d points, %s, BBox: (%f,%f,%f,%f)\n", 
2049               seg, t, seg->n_points, seg->dir==0?"UP  ":"DOWN",
2050               seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
2051       int p;
2052       for(p=0;p<seg->n_points;p++) {
2053           ArtPoint* point = &seg->points[p];
2054           art_dprint("        (%.16f,%.16f)\n", point->x, point->y);
2055       }
2056   }
2057   art_dprint("\n");
2058 #endif
2059
2060   ctx = art_new (ArtIntersectCtx, 1);
2061   ctx->in = in;
2062   ctx->out = out;
2063   pq = art_pri_new ();
2064   ctx->pq = pq;
2065
2066   ctx->active_head = NULL;
2067
2068   ctx->horiz_first = NULL;
2069   ctx->horiz_last = NULL;
2070
2071   ctx->in_curs = 0;
2072   first_point = art_new (ArtPriPoint, 1);
2073   first_point->x = in->segs[0].points[0].x;
2074   first_point->y = in->segs[0].points[0].y;
2075   first_point->user_data = NULL;
2076   ctx->y = first_point->y;
2077   art_pri_insert (pq, first_point);
2078
2079   double lasty = -HUGE_VAL;
2080   while (!art_pri_empty (pq))
2081     {
2082       ArtPriPoint *pri_point = art_pri_choose (pq);
2083       ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data;
2084
2085 #ifdef VERBOSE
2086       art_dprint ("\nIntersector step %d (%d items in pq)\n", count++, pq->n_items);
2087 #endif
2088 #ifdef SANITYCHECK
2089       art_svp_intersect_sanitycheck(ctx, pri_point->y);
2090 #endif
2091 #ifdef VERBOSE
2092       art_dprint ("priq choose (%.16f, %.16f) %08x\n", pri_point->x, pri_point->y,
2093               (unsigned long)pri_point->user_data);
2094       if(seg) {
2095           art_dprint ("            %08x = %.16f,%.16f -> %.16f %.16f\n", seg, seg->x[0], seg->y0, seg->x[1], seg->y1);
2096       }
2097       //int t;
2098       //for(t=0;t<pq->n_items;t++) {
2099       //    art_dprint("pq[%d] %.16f,%.16f %08x\n", 
2100       //            t,
2101       //            pq->items[t]->x,
2102       //            pq->items[t]->y,
2103       //            pq->items[t]->user_data);
2104       //}
2105 #endif
2106
2107       //art_dprint("y=%f %08x\n", pri_point->y, pri_point->user_data);
2108       if (ctx->y != pri_point->y)
2109         {
2110           art_svp_intersect_horiz_commit (ctx);
2111           ctx->y = pri_point->y;
2112         }
2113
2114       if(ctx->y < lasty) {
2115           art_warn("y decreased\n");
2116           art_report_error();
2117       }
2118
2119       if (seg == NULL)
2120         {
2121           /* Insert new segment from input */
2122           const ArtSVPSeg *in_seg = 0;
2123           
2124           while(1) {
2125               in_seg = &in->segs[ctx->in_curs++];
2126               if(in_seg->n_points > 1)
2127                   break;
2128               if(ctx->in_curs == in->n_segs) {
2129                   in_seg = 0;
2130                   break;
2131               }
2132
2133 #ifdef VERBOSE 
2134               art_dprint("ignoring input segment %08x- it only contains %d point(s)\n", 
2135                       in_seg, in_seg->n_points);
2136 #endif
2137           }
2138         
2139           if(in_seg) {
2140               int t;
2141               int error = 0;
2142               for(t=0;t<in_seg->n_points-1;t++) {
2143                   if(!(in_seg->points[t].y <= in_seg->points[t+1].y)) {
2144                       error = 1;
2145                   }
2146               }
2147               if(error) {
2148                   art_warn("bad input: contains a segment with descending y\n");
2149                   for(t=0;t<in_seg->n_points;t++) {
2150                       art_dprint("%d) %.16f %.16f\n", t, in_seg->points[t].x, in_seg->points[t].y);
2151                   }
2152                   art_report_error();
2153               }
2154
2155 #ifdef VERBOSE
2156               art_dprint("insert new segment from input (%.16f,%.16f) dir=%d\n", in_seg->points[0].x, in_seg->points[0].y, in_seg->dir);
2157 #endif
2158               art_svp_intersect_add_seg (ctx, in_seg);
2159               if (ctx->in_curs < in->n_segs)
2160                 {
2161                   const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs];
2162                   pri_point->x = next_seg->points[0].x;
2163                   pri_point->y = next_seg->points[0].y;
2164                   /* user_data is already NULL */
2165                   art_pri_insert (pq, pri_point);
2166                 }
2167               else
2168                 art_free(pri_point);pri_point =0;
2169           } else {
2170             art_free(pri_point);pri_point = 0;
2171           }
2172         }
2173       else
2174         {
2175           int n_stack = seg->n_stack;
2176
2177           if (n_stack > 1)
2178             {
2179               art_svp_intersect_process_intersection (ctx, seg);
2180               art_free (pri_point);
2181             }
2182           else
2183             {
2184               art_svp_intersect_advance_cursor (ctx, seg, pri_point);
2185             }
2186         }
2187         lasty = ctx->y;
2188     }
2189
2190   art_svp_intersect_horiz_commit (ctx);
2191
2192   art_pri_free (pq);
2193   art_free (ctx);
2194   current_svp = 0;
2195 }