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