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 ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg,
 975           right_seg->x[0], right_seg->y0,
 976           right_seg->x[1], right_seg->y1);
 977 #endif
 978
 979 #ifdef CHEAP_SANITYCHECK
 980   if (right_seg->x[0] < left_seg->x[(left_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) {
 981       /* notice: if we test *only* the line equation here, dd might be < 0, even though
 982          right_seg was inserted to the right of left_seg correctly, due to numerical
 983          instabilities */
 984       double dd = right_seg->x[0] * left_seg->a + right_seg->y0 * left_seg->b + left_seg->c;
 985       if(dd < 0) {
 986           //art_warn ("segment %08x[%d] isn't to the left of %08x[%d]. d=%.16f\n",
 987           //        left_seg, left_seg->n_stack,
 988           //        right_seg, right_seg->n_stack,
 989           //        dd);
 990       }
 991   }
 992 #endif
 993
 994   if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0])
 995     {
 996       /* Top points of left and right segments coincide. This case
 997          feels like a bit of duplication - we may want to merge it
 998          with the cases below. However, this way, we're sure that this
 999          logic makes only localized changes. */
1000
1001       if (left_y1 < right_y1)
1002         {
1003           /* Test left (x1, y1) against right segment */
1004           double left_x1 = left_seg->x[1];
1005
1006           if (left_x1 <
1007               right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
1008               left_y1 == right_seg->y0)
1009             return ART_FALSE;
1010           d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1011           if (d < -EPSILON_A)
1012
1013               return ART_FALSE;
1014           else if (d < EPSILON_A) /* should we use zero here? */
1015             {
1016 #ifdef VERBOSE
1017                 art_dprint("break %08x because of common top point, left_y1 < right_y1\n", right_seg);
1018 #endif
1019               /* I'm unsure about the break flags here. */
1020               double right_x1 = art_svp_intersect_break (ctx, right_seg,
1021                                                          left_x1, left_y1,
1022                                                          ART_BREAK_RIGHT);
1023
1024               /* this is always true due to ART_BREAK_RIGHT right_x1>=left_x1 if
1025                  _break uses x_ref clipping */
1026               if (left_x1 <= right_x1) {
1027                 return ART_FALSE;
1028               }
1029             }
1030         }
1031       else if (left_y1 > right_y1)
1032         {
1033           /* Test right (x1, y1) against left segment */
1034           double right_x1 = right_seg->x[1];
1035
1036           if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
1037               right_y1 == left_seg->y0)
1038
1039               return ART_FALSE;
1040           d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
1041           if (d > EPSILON_A)
1042             return ART_FALSE;
1043           else if (d > -EPSILON_A) /* should we use zero here? */
1044             {
1045 #ifdef VERBOSE
1046               art_dprint("break %08x because of common top point, left_y1 > right_y1\n", left_seg);
1047 #endif
1048               /* See above regarding break flags. */
1049               double left_x1 = art_svp_intersect_break (ctx, left_seg,
1050                                                         right_x1, right_y1,
1051                                                         ART_BREAK_LEFT);
1052
1053               /* this is always true, due to ART_BREAK_LEFT left_x1<=right_x1, if
1054                  _break uses x_ref clipping
1055                */
1056               if (left_x1 <= right_x1) {
1057                 return ART_FALSE;
1058               }
1059             }
1060         }
1061       else /* left_y1 == right_y1 */
1062         {
1063           double left_x1 = left_seg->x[1];
1064           double right_x1 = right_seg->x[1];
1065
1066
1067           if (left_x1 <= right_x1)
1068             return ART_FALSE;
1069         }
1070
1071       //int wind_left = left_seg->wind_left;
1072       //int wind_right = right_seg->wind_left;
1073       art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1074       //left_seg->wind_left = wind_right;
1075       //right_seg->wind_left = wind_left;
1076
1077       return ART_TRUE;
1078     }
1079
1080   if (left_y1 < right_y1)
1081     {
1082       /* Test left (x1, y1) against right segment */
1083       double left_x1 = left_seg->x[1];
1084
1085       if (left_x1 <
1086           right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
1087           left_y1 == right_seg->y0)
1088         return ART_FALSE;
1089
1090       if(left_y1 < right_seg->y0) {
1091           art_warn("left_y1 < right_seg->y0\n");
1092           return ART_FALSE;
1093       }
1094
1095       /* we might want to output a warning for left_y1 < right_seg->y0 */
1096
1097       d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1098       if (d < -EPSILON_A)
1099         return ART_FALSE;
1100       else if (d < EPSILON_A)
1101         {
1102 #ifdef VERBOSE
1103           art_dprint("break %08x at %.16f because left_y1 < right_y1\n", right_seg, left_y1);
1104           art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg,
1105                   right_seg->x[0], right_seg->y0,
1106                   right_seg->x[1], right_seg->y1);
1107 #endif
1108           double right_x1 = art_svp_intersect_break (ctx, right_seg,
1109                                                      left_x1, left_y1,
1110                                                      ART_BREAK_RIGHT);
1111 #ifdef VERBOSE
1112           art_dprint("after break:\n", right_seg);
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           /* this is always true if _break uses x_ref clipping */
1118           if (left_x1 <= right_x1)
1119             return ART_FALSE;
1120         }
1121     }
1122   else if (left_y1 > right_y1)
1123     {
1124       /* Test right (x1, y1) against left segment */
1125       double right_x1 = right_seg->x[1];
1126
1127       if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
1128           right_y1 == left_seg->y0)
1129         return ART_FALSE;
1130
1131       if(right_y1 < left_seg->y0) {
1132           art_warn("left_y1 < right_seg->y0\n");
1133           return ART_FALSE;
1134       }
1135
1136       /* we might want to output a warning for right_y1 < left_seg->y0 */
1137
1138       d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
1139       if (d > EPSILON_A)
1140         return ART_FALSE;
1141       else if (d > -EPSILON_A)
1142         {
1143 #ifdef VERBOSE
1144           art_dprint("break %08x because left_y1 > right_y1\n", right_seg);
1145 #endif
1146           double left_x1 = art_svp_intersect_break (ctx, left_seg,
1147                                                     right_x1, right_y1,
1148                                                     ART_BREAK_LEFT);
1149           /* this is always true if _break uses x_ref clipping */
1150           if (left_x1 <= right_x1)
1151             return ART_FALSE;
1152         }
1153     }
1154   else /* left_y1 == right_y1 */
1155     {
1156       double left_x1 = left_seg->x[1];
1157       double right_x1 = right_seg->x[1];
1158
1159       if (left_x1 <= right_x1)
1160         return ART_FALSE;
1161     }
1162
1163
1164   /* The segments cross. Find the intersection point. */
1165
1166   in_seg = left_seg->in_seg;
1167   in_curs = left_seg->in_curs;
1168   left_x0 = in_seg->points[in_curs - 1].x;
1169   left_y0 = in_seg->points[in_curs - 1].y;
1170   left_x1 = in_seg->points[in_curs].x;
1171   left_y1 = in_seg->points[in_curs].y;
1172
1173 #if 0
1174   /* check for endpoint = firstpoint cases */
1175   if(left_seg->y0 == right_seg->y1 && left_seg->x[0] == right_seg->x[1])
1176       return ART_FALSE;
1177   if(left_seg->y1 == right_seg->y0 && left_seg->x[1] == right_seg->x[0])
1178       return ART_FALSE;
1179 #endif
1180
1181   d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c;
1182   d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1183   if (d0 == d1)
1184     {
1185       x = left_x0;
1186       y = left_y0;
1187     }
1188   else
1189     {
1190       /* Is this division always safe? It could possibly overflow. */
1191       t = d0 / (d0 - d1);
1192       if (t <= 0)
1193         {
1194           x = left_x0;
1195           y = left_y0;
1196         }
1197       else if (t >= 1)
1198         {
1199           x = left_x1;
1200           y = left_y1;
1201         }
1202       else
1203         {
1204           x = left_x0 + t * (left_x1 - left_x0);
1205           y = left_y0 + t * (left_y1 - left_y0);
1206         }
1207     }
1208
1209   /* Make sure intersection point is within bounds of right seg. */
1210   if (y < right_seg->y0)
1211     {
1212       x = right_seg->x[0];
1213       y = right_seg->y0;
1214     }
1215   else if (y > right_seg->y1)
1216     {
1217       x = right_seg->x[1];
1218       y = right_seg->y1;
1219     }
1220   else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1])
1221     x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1];
1222   else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG])
1223     x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG];
1224
1225   x = double_precision(x);
1226   y = double_precision(y);
1227
1228   assert(ctx->y >= left_seg->y0);
1229 #ifdef VERBOSE
1230   art_dprint ("intersect at %.16f %.16f\n", x, y);
1231 #endif
1232
1233
1234   if(y < ctx->y) {
1235       /* as we use the full segment length (not just the subsegment currently
1236          under evaluation), intersection points may be above the current scanline.
1237          As we're not able to process these anymore, we also don't need to add
1238          anything to the active list or pq */
1239       if(ctx->y -  y > EPSILON_A) {
1240         art_warn("ignoring previously unhandled intersection point %.16f,%.16f between segments %08x and %08x, dy = %.16f\n",
1241                    x, y, left_seg, right_seg,
1242                    ctx->y - y);
1243         art_abort();
1244       }
1245
1246       return ART_FALSE;
1247   }
1248
1249   if(y > left_seg->y1) {
1250       /* not within the subsegment we're currently looking into- this is not an intersection */
1251       return ART_FALSE;
1252   }
1253
1254   if (y == left_seg->y0)
1255     {
1256       if (y != right_seg->y0)
1257         {
1258 #ifdef VERBOSE
1259           art_dprint ("art_svp_intersect_test_cross: intersection (%.16f, %.16f) matches former y0 of %08x, [%08x]\n",
1260                     x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1261 #endif
1262           art_svp_intersect_push_pt (ctx, right_seg, x, y);
1263           if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1264             art_svp_intersect_add_point (ctx, x, y, right_seg->right,
1265                                          break_flags);
1266         }
1267       else
1268         {
1269 #ifdef VERBOSE
1270           art_dprint ("art_svp_intersect_test_cross: intersection (%.16f, %.16f) at current scan line (y=ly0=ry0)\n",
1271                     x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1272 #endif
1273           /* Intersection takes place at current scan line, with
1274              left->x0 <= x <= right->x0, left->x0 != right->x0.
1275
1276              This happens if one of the lines is horizontal, or very near
1277              horizontal. (true horizontal lines are processed by _horiz())
1278
1279              Process immediately rather than queueing intersection point into
1280              priq. */
1281           ArtActiveSeg *winner, *loser;
1282
1283           /* Choose "most vertical" segement */
1284           if (left_seg->a > right_seg->a)
1285             {
1286               winner = left_seg;
1287               loser = right_seg;
1288             }
1289           else
1290             {
1291               winner = right_seg;
1292               loser = left_seg;
1293             }
1294 #ifdef VERBOSE
1295           art_dprint ("           x = %.16f\n", x);
1296           art_dprint (" loser->x[0] = %.16f\n", loser->x[0]);
1297           art_dprint ("winner->x[0] = %.16f\n", winner->x[0]);
1298 #endif
1299           loser->x[0] = winner->x[0];
1300           loser->horiz_x = loser->x[0];
1301           loser->horiz_delta_wind += loser->delta_wind;
1302           winner->horiz_delta_wind -= loser->delta_wind;
1303
1304           art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1305           return ART_TRUE;
1306         }
1307     }
1308   else if (y == right_seg->y0)
1309     {
1310 #ifdef VERBOSE
1311       art_dprint ("*** art_svp_intersect_test_cross: intersection (%.16f, %.16f) matches latter y0 of [%08x], %08x\n",
1312               x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1313       art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", left_seg,
1314               left_seg->x[0], left_seg->y0,
1315               left_seg->x[1], left_seg->y1);
1316       art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg,
1317               right_seg->x[0], right_seg->y0,
1318               right_seg->x[1], right_seg->y1);
1319
1320 #endif
1321       art_svp_intersect_push_pt (ctx, left_seg, x, y);
1322       if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1323         art_svp_intersect_add_point (ctx, x, y, left_seg->left,
1324                                      break_flags);
1325     }
1326   else
1327     {
1328 #ifdef VERBOSE
1329       art_dprint ("Inserting (%.16f, %.16f) into %08x, %08x\n",
1330               x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1331 #endif
1332       /* Insert the intersection point into both segments. */
1333       art_svp_intersect_push_pt (ctx, left_seg, x, y);
1334       art_svp_intersect_push_pt (ctx, right_seg, x, y);
1335       if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1336         art_svp_intersect_add_point (ctx, x, y, left_seg->left, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1337       if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1338         art_svp_intersect_add_point (ctx, x, y, right_seg->right, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1339     }
1340   return ART_FALSE;
1341 }
1342
1343 /**
1344  * art_svp_intersect_active_delete: Delete segment from active list.
1345  * @ctx: Intersection context.
1346  * @seg: Segment to delete.
1347  *
1348  * Deletes @seg from the active list.
1349  **/
1350 static /* todo inline */ void
1351 art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1352 {
1353   ArtActiveSeg *left = seg->left, *right = seg->right;
1354
1355   if (left != NULL)
1356     left->right = right;
1357   else
1358     ctx->active_head = right;
1359   if (right != NULL)
1360     right->left = left;
1361 }
1362
1363 /**
1364  * art_svp_intersect_active_free: Free an active segment.
1365  * @seg: Segment to delete.
1366  *
1367  * Frees @seg.
1368  **/
1369 static /* todo inline */ void
1370 art_svp_intersect_active_free (ArtActiveSeg *seg)
1371 {
1372   art_free (seg->stack);
1373 #ifdef VERBOSE
1374   art_dprint ("Freeing %08x\n", (unsigned long) seg);
1375 #else
1376   // !!!
1377   art_free (seg);
1378 #endif
1379 }
1380
1381 /**
1382  * art_svp_intersect_insert_cross: Test crossings of newly inserted line.
1383  *
1384  * Tests @seg against its left and right neighbors for intersections.
1385  * Precondition: the line in @seg is not purely horizontal.
1386  **/
1387 static void
1388 art_svp_intersect_insert_cross (ArtIntersectCtx *ctx,
1389                                 ArtActiveSeg *seg)
1390 {
1391   ArtActiveSeg *left = seg, *right = seg;
1392
1393   for (;;)
1394     {
1395       if (left != NULL)
1396         {
1397           ArtActiveSeg *leftc;
1398
1399           for (leftc = left->left; leftc != NULL; leftc = leftc->left)
1400             if (!(leftc->flags & ART_ACTIVE_FLAGS_DEL))
1401               break;
1402           if (leftc != NULL &&
1403               art_svp_intersect_test_cross (ctx, leftc, left,
1404                                             ART_BREAK_LEFT))
1405             {
1406               if (left == right || right == NULL)
1407                 right = left->right;
1408             }
1409           else
1410             {
1411               left = NULL;
1412             }
1413         }
1414       else if (right != NULL && right->right != NULL)
1415         {
1416           ArtActiveSeg *rightc;
1417
1418           for (rightc = right->right; rightc != NULL; rightc = rightc->right)
1419             if (!(rightc->flags & ART_ACTIVE_FLAGS_DEL))
1420               break;
1421           if (rightc != NULL &&
1422               art_svp_intersect_test_cross (ctx, right, rightc,
1423                                             ART_BREAK_RIGHT))
1424             {
1425               if (left == right || left == NULL)
1426                 left = right->left;
1427             }
1428           else
1429             {
1430               right = NULL;
1431             }
1432         }
1433       else
1434         break;
1435     }
1436 }
1437
1438 /**
1439  * art_svp_intersect_horiz: Add horizontal line segment.
1440  * @ctx: Intersector context.
1441  * @seg: Segment on which to add horizontal line.
1442  * @x0: Old x position.
1443  * @x1: New x position.
1444  *
1445  * Adds a horizontal line from @x0 to @x1, and updates the current
1446  * location of @seg to @x1.
1447  **/
1448 static void
1449 art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1450                          double x0, double x1)
1451 {
1452   ArtActiveSeg *hs;
1453
1454   if (x0 == x1)
1455     return;
1456
1457 #ifdef VERBOSE
1458   art_dprint("horiz: seg=%08x x0=%f x1=%f segid=%08x flags=%s delta_wind=%d\n", seg, x0, x1, seg->seg_id,
1459           seg->flags & ART_ACTIVE_FLAGS_OUT?"out":"", seg->delta_wind);
1460 #endif
1461
1462   hs = art_new (ArtActiveSeg, 1);
1463
1464   hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT);
1465   if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1466     {
1467       ArtSvpWriter *swr = ctx->out;
1468
1469       swr->add_point (swr, seg->seg_id, x0, ctx->y);
1470     }
1471   hs->seg_id = seg->seg_id;
1472   hs->horiz_x = x0;
1473   hs->horiz_delta_wind = seg->delta_wind;
1474   hs->stack = NULL;
1475
1476   /* Ideally, the (a, b, c) values will never be read. However, there
1477      are probably some tests remaining that don't check for _DEL
1478      before evaluating the line equation. For those, these
1479      initializations will at least prevent a UMR of the values, which
1480      can crash on some platforms. */
1481   hs->a = 0.0;
1482   hs->b = 0.0;
1483   hs->c = 0.0;
1484
1485   seg->horiz_delta_wind -= seg->delta_wind;
1486
1487   art_svp_intersect_add_horiz (ctx, hs);
1488
1489   if (x0 > x1)
1490     {
1491       ArtActiveSeg *left;
1492       art_boolean first = ART_TRUE;
1493
1494       for (left = seg->left; left != NULL; left = seg->left)
1495         {
1496           int left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG;
1497
1498           if (left->x[left_bneg] <= x1)
1499             break;
1500           if (left->x[left_bneg ^ 1] <= x1 &&
1501               x1 * left->a + ctx->y * left->b + left->c >= 0)
1502             break;
1503           if (left->y0 != ctx->y && left->y1 != ctx->y)
1504             {
1505               art_svp_intersect_break (ctx, left, x1, ctx->y, ART_BREAK_LEFT);
1506             }
1507 #ifdef VERBOSE
1508           art_dprint ("x0=%.16f > x1=%.16f, swapping %08x, %08x\n",
1509                   x0, x1, (unsigned long)left, (unsigned long)seg);
1510 #endif
1511           art_svp_intersect_swap_active (ctx, left, seg);
1512           if (first && left->right != NULL)
1513             {
1514               art_svp_intersect_test_cross (ctx, left, left->right,
1515                                             ART_BREAK_RIGHT);
1516               first = ART_FALSE;
1517             }
1518         }
1519     }
1520   else
1521     {
1522       ArtActiveSeg *right;
1523       art_boolean first = ART_TRUE;
1524
1525       for (right = seg->right; right != NULL; right = seg->right)
1526         {
1527           int right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG;
1528
1529           if (right->x[right_bneg ^ 1] >= x1)
1530             break;
1531           if (right->x[right_bneg] >= x1 &&
1532               x1 * right->a + ctx->y * right->b + right->c <= 0)
1533             break;
1534           if (right->y0 != ctx->y && right->y1 != ctx->y)
1535             {
1536               art_svp_intersect_break (ctx, right, x1, ctx->y,
1537                                        ART_BREAK_LEFT);
1538             }
1539 #ifdef VERBOSE
1540           art_dprint ("[right]x0=%.16f < x1=%.16f, swapping %08x, %08x\n",
1541                   x0, x1, (unsigned long)seg, (unsigned long)right);
1542 #endif
1543           art_svp_intersect_swap_active (ctx, seg, right);
1544           if (first && right->left != NULL)
1545             {
1546               art_svp_intersect_test_cross (ctx, right->left, right,
1547                                             ART_BREAK_RIGHT);
1548               first = ART_FALSE;
1549             }
1550         }
1551     }
1552
1553   seg->x[0] = x1;
1554   seg->x[1] = x1;
1555   seg->horiz_x = x1;
1556   seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1557 }
1558
1559 /**
1560  * art_svp_intersect_insert_line: Insert a line into the active list.
1561  * @ctx: Intersector context.
1562  * @seg: Segment containing line to insert.
1563  *
1564  * Inserts the line into the intersector context, taking care of any
1565  * intersections, and adding the appropriate horizontal points to the
1566  * active list.
1567  **/
1568 static void
1569 art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1570 {
1571   if (seg->y1 == seg->y0)
1572     {
1573 #ifdef VERBOSE
1574       art_dprint ("art_svp_intersect_insert_line(%d): %08x is horizontal\n", seg->flags&ART_ACTIVE_FLAGS_IN_ACTIVE, (unsigned long)seg);
1575 #endif
1576       art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]);
1577     }
1578   else
1579     {
1580 #ifdef VERBOSE
1581       art_dprint ("art_svp_intersect_insert_line(%d): %08x is non-horizontal\n", seg->flags&ART_ACTIVE_FLAGS_IN_ACTIVE, (unsigned long)seg);
1582 #endif
1583       art_svp_intersect_insert_cross (ctx, seg);
1584       art_svp_intersect_add_horiz (ctx, seg);
1585     }
1586
1587   seg->flags |= ART_ACTIVE_FLAGS_IN_ACTIVE; //q
1588 }
1589
1590 static void
1591 art_svp_intersect_process_intersection (ArtIntersectCtx *ctx,
1592                                         ArtActiveSeg *seg)
1593 {
1594   int n_stack = --seg->n_stack;
1595   seg->x[1] = seg->stack[n_stack - 1].x;
1596   seg->y1 = seg->stack[n_stack - 1].y;
1597   seg->x[0] = seg->stack[n_stack].x;
1598   seg->y0 = seg->stack[n_stack].y;
1599   seg->horiz_x = seg->x[0];
1600 #ifdef VERBOSE
1601   art_dprint("process intersection %08x (%.16f,%.16f-%.16f,%.16f)\n", seg, seg->x[0], seg->y0, seg->x[1], seg->y1);
1602 #endif
1603   art_svp_intersect_insert_line (ctx, seg);
1604 }
1605
1606 static void
1607 art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1608                                   ArtPriPoint *pri_pt)
1609 {
1610   const ArtSVPSeg *in_seg = seg->in_seg;
1611   int in_curs = seg->in_curs;
1612   ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL;
1613
1614   if (swr != NULL)
1615     swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1);
1616   if (in_curs + 1 >= in_seg->n_points)
1617     {
1618       ArtActiveSeg *left = seg->left, *right = seg->right;
1619
1620 #if 0
1621       if (swr != NULL)
1622         swr->close_segment (swr, seg->seg_id);
1623       seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1624 #endif
1625       seg->flags |= ART_ACTIVE_FLAGS_DEL;
1626       art_svp_intersect_add_horiz (ctx, seg);
1627       art_svp_intersect_active_delete (ctx, seg);
1628       if (left != NULL && right != NULL)
1629         art_svp_intersect_test_cross (ctx, left, right,
1630                                       ART_BREAK_LEFT | ART_BREAK_RIGHT);
1631       art_free (pri_pt);
1632     }
1633   else
1634     {
1635       seg->horiz_x = seg->x[1];
1636
1637       art_svp_intersect_setup_seg (seg, pri_pt);
1638       art_pri_insert (ctx->pq, pri_pt);
1639       art_svp_intersect_insert_line (ctx, seg);
1640     }
1641 }
1642
1643 static void
1644 art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg)
1645 {
1646   ArtActiveSeg *seg = art_new (ArtActiveSeg, 1);
1647   ArtActiveSeg *test;
1648   double x0, y0;
1649   ArtActiveSeg *beg_range;
1650   ArtActiveSeg *last = NULL;
1651   ArtActiveSeg *left, *right;
1652   ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1);
1653
1654   seg->flags = 0;
1655   seg->in_seg = in_seg;
1656   seg->in_curs = 0;
1657
1658   seg->n_stack_max = 4;
1659   seg->stack = art_new (ArtPoint, seg->n_stack_max);
1660
1661   seg->horiz_delta_wind = 0;
1662
1663   seg->wind_left = 0;
1664
1665   pri_pt->user_data = seg;
1666   art_svp_intersect_setup_seg (seg, pri_pt);
1667   art_pri_insert (ctx->pq, pri_pt);
1668
1669   /* Find insertion place for new segment */
1670   /* This is currently a left-to-right scan, but should be replaced
1671      with a binary search as soon as it's validated. */
1672
1673   x0 = in_seg->points[0].x;
1674   y0 = in_seg->points[0].y;
1675   beg_range = NULL;
1676   for (test = ctx->active_head; test != NULL; test = test->right)
1677     {
1678       double d;
1679       int test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG;
1680
1681       if (x0 < test->x[test_bneg])
1682         {
1683           if (x0 < test->x[test_bneg ^ 1]) {
1684 #ifdef VERBOSE
1685             art_dprint("inserting segment %08x before %08x (x0 < xmin)\n", seg, test);
1686 #endif
1687             break;
1688           }
1689           d = x0 * test->a + y0 * test->b + test->c;
1690           if (d < 0) {
1691 #ifdef VERBOSE
1692             art_dprint("inserting segment %08x before %08x (d = %.16f)\n", seg, test, d);
1693 #endif
1694             break;
1695           }
1696 #ifdef VERBOSE
1697           art_dprint("segment %08x is to the right of %08x d=%.16f\n", seg, test, d);
1698 #endif
1699         } else {
1700 #ifdef VERBOSE
1701             d = x0 * test->a + y0 * test->b + test->c;
1702             art_dprint("segment %08x is to the right of %08x d=%.16f (not used)\n", seg, test, d);
1703 #endif
1704         }
1705       last = test;
1706     }
1707
1708   left = art_svp_intersect_add_point (ctx, x0, y0, last, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1709
1710 #ifdef VERBOSE
1711   art_dprint("left=%08x x0=%.16f y=%.16f\n", left, x0, y0);
1712 #endif
1713
1714   seg->left = left;
1715   if (left == NULL)
1716     {
1717       right = ctx->active_head;
1718       ctx->active_head = seg;
1719     }
1720   else
1721     {
1722       right = left->right;
1723       left->right = seg;
1724     }
1725   seg->right = right;
1726   if (right != NULL)
1727     right->left = seg;
1728
1729   seg->delta_wind = in_seg->dir ? 1 : -1;
1730   seg->horiz_x = x0;
1731
1732   art_svp_intersect_insert_line (ctx, seg);
1733 }
1734
1735 #ifdef SANITYCHECK
1736 static void
1737 art_svp_intersect_sanitycheck_winding (ArtIntersectCtx *ctx)
1738 {
1739 #if 0
1740   /* At this point, we seem to be getting false positives, so it's
1741      turned off for now. */
1742
1743   ArtActiveSeg *seg;
1744   int winding_number = 0;
1745
1746   for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1747     {
1748       /* Check winding number consistency. */
1749       if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1750         {
1751           if (winding_number != seg->wind_left)
1752             art_warn ("*** art_svp_intersect_sanitycheck_winding: seg %08x has wind_left of %d, expected %d\n",
1753                   (unsigned long) seg, seg->wind_left, winding_number);
1754           winding_number = seg->wind_left + seg->delta_wind;
1755         }
1756     }
1757   if (winding_number != 0)
1758     art_warn ("*** art_svp_intersect_sanitycheck_winding: non-balanced winding number %d\n",
1759               winding_number);
1760 #endif
1761 }
1762 #endif
1763
1764 /**
1765  * art_svp_intersect_horiz_commit: Commit points in horiz list to output.
1766  * @ctx: Intersection context.
1767  *
1768  * The main function of the horizontal commit is to output new
1769  * points to the output writer.
1770  *
1771  * This "commit" pass is also where winding numbers are assigned,
1772  * because doing it here provides much greater tolerance for inputs
1773  * which are not in strict SVP order.
1774  *
1775  * Each cluster in the horiz_list contains both segments that are in
1776  * the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not,
1777  * and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We
1778  * need to deal with both.
1779  **/
1780 static void
1781 art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx)
1782 {
1783   ArtActiveSeg *seg;
1784   int winding_number = 0; /* initialization just to avoid warning */
1785   int horiz_wind = 0;
1786   double last_x = 0; /* initialization just to avoid warning */
1787
1788 #ifdef VERBOSE
1789   art_dprint ("art_svp_intersect_horiz_commit: y=%.16f\n", ctx->y);
1790   for (seg = ctx->horiz_first; seg != NULL; seg = seg->horiz_right)
1791     art_dprint (" %08x: %.16f %+d segid=%d\n",
1792             (unsigned long)seg, seg->horiz_x, seg->horiz_delta_wind, seg->seg_id);
1793 #endif
1794
1795   /* Output points to svp writer. */
1796   for (seg = ctx->horiz_first; seg != NULL;)
1797     {
1798       /* Find a cluster with common horiz_x, */
1799       ArtActiveSeg *curs;
1800       double x = seg->horiz_x;
1801
1802       /* Generate any horizontal segments. */
1803       if (horiz_wind != 0)
1804         {
1805           ArtSvpWriter *swr = ctx->out;
1806           int seg_id;
1807
1808 #ifdef VERBOSE
1809           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);
1810 #endif
1811           seg_id = swr->add_segment (swr, winding_number, horiz_wind,
1812                                      last_x, ctx->y);
1813           swr->add_point (swr, seg_id, x, ctx->y);
1814           swr->close_segment (swr, seg_id);
1815         }
1816
1817       /* Find first active segment in cluster. */
1818
1819       for (curs = seg; curs != NULL && curs->horiz_x == x;
1820            curs = curs->horiz_right)
1821         if (!(curs->flags & ART_ACTIVE_FLAGS_DEL))
1822           break;
1823
1824       if (curs != NULL && curs->horiz_x == x)
1825         {
1826           /* There exists at least one active segment in this cluster. */
1827
1828           /* Find beginning of cluster. */
1829           for (; curs->left != NULL; curs = curs->left)
1830             if (curs->left->horiz_x != x)
1831               break;
1832
1833           if (curs->left != NULL)
1834             winding_number = curs->left->wind_left + curs->left->delta_wind;
1835           else
1836             winding_number = 0;
1837
1838           do
1839             {
1840 #ifdef VERBOSE
1841               art_dprint (" curs %08x: winding_number = %d += %d\n", (unsigned long)curs, winding_number, curs->delta_wind);
1842 #endif
1843               if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) ||
1844                   curs->wind_left != winding_number)
1845                 {
1846                   ArtSvpWriter *swr = ctx->out;
1847
1848                   if (curs->flags & ART_ACTIVE_FLAGS_OUT)
1849                     {
1850                       swr->add_point (swr, curs->seg_id,
1851                                       curs->horiz_x, ctx->y);
1852                       swr->close_segment (swr, curs->seg_id);
1853                     }
1854
1855                   curs->seg_id = swr->add_segment (swr, winding_number,
1856                                                    curs->delta_wind,
1857                                                    x, ctx->y);
1858                   curs->flags |= ART_ACTIVE_FLAGS_OUT;
1859                 }
1860               curs->wind_left = winding_number;
1861               winding_number += curs->delta_wind;
1862               curs = curs->right;
1863             }
1864           while (curs != NULL && curs->horiz_x == x);
1865         }
1866
1867       /* Skip past cluster. */
1868       do
1869         {
1870           ArtActiveSeg *next = seg->horiz_right;
1871
1872           seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ;
1873           horiz_wind += seg->horiz_delta_wind;
1874           seg->horiz_delta_wind = 0;
1875           if (seg->flags & ART_ACTIVE_FLAGS_DEL)
1876             {
1877               if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1878                 {
1879                   ArtSvpWriter *swr = ctx->out;
1880                   swr->close_segment (swr, seg->seg_id);
1881                 }
1882               art_svp_intersect_active_free (seg);
1883             }
1884           seg = next;
1885         }
1886       while (seg != NULL && seg->horiz_x == x);
1887
1888       last_x = x;
1889     }
1890   ctx->horiz_first = NULL;
1891   ctx->horiz_last = NULL;
1892 #ifdef SANITYCHECK
1893   art_svp_intersect_sanitycheck_winding (ctx);
1894 #endif
1895 }
1896
1897 #ifdef SANITYCHECK
1898 static void
1899 art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx, double y)
1900 {
1901   ArtActiveSeg *seg;
1902   ArtActiveSeg *last = NULL;
1903   double d;
1904
1905 #ifdef VERbOSE
1906   art_dprint ("Active list (y = %.16f (new: %.16f)):\n", ctx->y, y);
1907 #endif
1908
1909   for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1910     {
1911 #ifdef VERBOSE
1912       char c1=' ',c2=' ',e1=' ';
1913       if(seg->y0 > ctx->y) c1='!';
1914       if(seg->y0 > y) c2='!';
1915       if(seg->y0 > seg->y1) e1='E';
1916 #endif
1917
1918       if (seg->left != last)
1919         {
1920           art_warn ("*** art_svp_intersect_sanitycheck: last=%08x, seg->left=%08x\n",
1921                     (unsigned long)last, (unsigned long)seg->left);
1922         }
1923       if (last != NULL)
1924         {
1925           /* pairwise compare with previous seg */
1926
1927           /* First the top. */
1928           if (last->y0 < seg->y0)
1929             {
1930             }
1931           else
1932             {
1933             }
1934
1935           /* Then the bottom. */
1936           if (last->y1 < seg->y1)
1937             {
1938               if (!((last->x[1] <
1939                      seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) ||
1940                     last->y1 == seg->y0))
1941                 {
1942                   d = last->x[1] * seg->a + last->y1 * seg->b + seg->c;
1943                   if (d >= EPSILON_A) {
1944                     art_warn ("*** bottom (%.16f, %.16f) of %08x is not clear of %08x to right (d = %g)\n",
1945                               last->x[1], last->y1, (unsigned long) last,
1946                               (unsigned long) seg, d);
1947                     art_abort();
1948                   } else {
1949 #ifdef VERBOSE
1950                       art_dprint("is to the left (d=%.16f of previous x1,y1) of\n", d);
1951 #endif
1952                   }
1953                 } else {
1954 #ifdef VERBOSE
1955                     art_dprint("is to the left (previous x1 < next x%d) of\n", (seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1);
1956 #endif
1957                 }
1958             }
1959           else if (last->y1 > seg->y1)
1960
1961             {
1962               if (!((seg->x[1] >
1963                      last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) ||
1964                     seg->y1 == last->y0))
1965               {
1966                 d = seg->x[1] * last->a + seg->y1 * last->b + last->c;
1967                 if (d < -EPSILON_A) {
1968                   art_warn ("*** bottom (%.16f, %.16f) of %08x is not clear of %08x to left (d = %.16f)\n",
1969                               seg->x[1], seg->y1, (unsigned long) seg,
1970                               (unsigned long) last, d);
1971                   art_abort();
1972                 } else {
1973 #ifdef VERBOSE
1974                   art_dprint("is to the left (d=%.16f of next x1,y1) of\n", d);
1975 #endif
1976                 }
1977               } else {
1978 #ifdef VERBOSE
1979                   art_dprint("is to the left (next x1 > previous x%d) of\n", last->flags & ART_ACTIVE_FLAGS_BNEG);
1980 #endif
1981               }
1982             }
1983           else
1984             {
1985               if (last->x[1] - seg->x[1] > EPSILON_A) {
1986                 art_warn ("*** bottoms (%.16f, %.16f) of %08x and (%.16f, %.16f) of %08x out of order\n",
1987                           last->x[1], last->y1, (unsigned long)last,
1988                           seg->x[1], seg->y1, (unsigned long)seg);
1989                 art_abort();
1990               } else {
1991 #ifdef VERBOSE
1992                   art_dprint("is to the left (y1s equal, previous x1 < next x1)\n");
1993 #endif
1994               }
1995             }
1996         }
1997
1998 #ifdef VERBOSE
1999       art_dprint ("%c%08x: %c%c %02d (%.16f, %.16f)-(%.16f, %.16f) ",
2000               e1,
2001               (unsigned long)seg, c1, c2, seg->flags,
2002               seg->x[0], seg->y0, seg->x[1], seg->y1);
2003 #endif
2004
2005       last = seg;
2006     }
2007 #ifdef VERBOSE
2008   art_dprint("\n");
2009 #endif
2010 }
2011 #endif
2012
2013 void
2014 art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out)
2015 {
2016   ArtIntersectCtx *ctx;
2017   ArtPriQ *pq;
2018   ArtPriPoint *first_point;
2019 #ifdef VERBOSE
2020   int count = 0;
2021 #endif
2022
2023   if (in->n_segs == 0)
2024     return;
2025
2026   current_svp = in;
2027
2028 #ifdef VERBOSE
2029   int t;
2030   art_dprint("Segments: %d\n", in->n_segs);
2031   for(t=0;t<in->n_segs;t++) {
2032       const ArtSVPSeg* seg = &in->segs[t];
2033       art_dprint("Segment %08x(%d): %d points, %s, BBox: (%f,%f,%f,%f)\n",
2034               seg, t, seg->n_points, seg->dir==0?"UP  ":"DOWN",
2035               seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
2036       int p;
2037       for(p=0;p<seg->n_points;p++) {
2038           ArtPoint* point = &seg->points[p];
2039           art_dprint("        (%.16f,%.16f)\n", point->x, point->y);
2040       }
2041   }
2042   art_dprint("\n");
2043 #endif
2044
2045   ctx = art_new (ArtIntersectCtx, 1);
2046   ctx->in = in;
2047   ctx->out = out;
2048   pq = art_pri_new ();
2049   ctx->pq = pq;
2050
2051   ctx->active_head = NULL;
2052
2053   ctx->horiz_first = NULL;
2054   ctx->horiz_last = NULL;
2055
2056   ctx->in_curs = 0;
2057   first_point = art_new (ArtPriPoint, 1);
2058   first_point->x = in->segs[0].points[0].x;
2059   first_point->y = in->segs[0].points[0].y;
2060   first_point->user_data = NULL;
2061   ctx->y = first_point->y;
2062   art_pri_insert (pq, first_point);
2063
2064   double lasty = -HUGE_VAL;
2065   while (!art_pri_empty (pq))
2066     {
2067       ArtPriPoint *pri_point = art_pri_choose (pq);
2068       ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data;
2069
2070 #ifdef VERBOSE
2071       art_dprint ("\nIntersector step %d (%d items in pq)\n", count++, pq->n_items);
2072 #endif
2073 #ifdef SANITYCHECK
2074       art_svp_intersect_sanitycheck(ctx, pri_point->y);
2075 #endif
2076 #ifdef VERBOSE
2077       art_dprint ("priq choose (%.16f, %.16f) %08x\n", pri_point->x, pri_point->y,
2078               (unsigned long)pri_point->user_data);
2079       if(seg) {
2080           art_dprint ("            %08x = %.16f,%.16f -> %.16f %.16f\n", seg, seg->x[0], seg->y0, seg->x[1], seg->y1);
2081       }
2082       //int t;
2083       //for(t=0;t<pq->n_items;t++) {
2084       //    art_dprint("pq[%d] %.16f,%.16f %08x\n",
2085       //            t,
2086       //            pq->items[t]->x,
2087       //            pq->items[t]->y,
2088       //            pq->items[t]->user_data);
2089       //}
2090 #endif
2091
2092       //art_dprint("y=%f %08x\n", pri_point->y, pri_point->user_data);
2093       if (ctx->y != pri_point->y)
2094         {
2095           art_svp_intersect_horiz_commit (ctx);
2096           ctx->y = pri_point->y;
2097         }
2098
2099       if(ctx->y < lasty) {
2100           art_warn("y decreased\n");
2101           art_abort();
2102       }
2103
2104       if (seg == NULL)
2105         {
2106           /* Insert new segment from input */
2107           const ArtSVPSeg *in_seg = 0;
2108
2109           while(1) {
2110               in_seg = &in->segs[ctx->in_curs++];
2111               if(in_seg->n_points > 1)
2112                   break;
2113               if(ctx->in_curs == in->n_segs) {
2114                   in_seg = 0;
2115                   break;
2116               }
2117
2118 #ifdef VERBOSE
2119               art_dprint("ignoring input segment %08x- it only contains %d point(s)\n",
2120                       in_seg, in_seg->n_points);
2121 #endif
2122           }
2123
2124           if(in_seg) {
2125               int t;
2126               int error = 0;
2127               for(t=0;t<in_seg->n_points-1;t++) {
2128                   if(!(in_seg->points[t].y <= in_seg->points[t+1].y)) {
2129                       error = 1;
2130                   }
2131               }
2132               if(error) {
2133                   art_warn("bad input: contains a segment with descending y\n");
2134                   for(t=0;t<in_seg->n_points;t++) {
2135                       art_dprint("%d) %.16f %.16f\n", t, in_seg->points[t].x, in_seg->points[t].y);
2136                   }
2137                   art_abort();
2138               }
2139
2140 #ifdef VERBOSE
2141               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);
2142 #endif
2143               art_svp_intersect_add_seg (ctx, in_seg);
2144               if (ctx->in_curs < in->n_segs)
2145                 {
2146                   const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs];
2147                   pri_point->x = next_seg->points[0].x;
2148                   pri_point->y = next_seg->points[0].y;
2149                   /* user_data is already NULL */
2150                   art_pri_insert (pq, pri_point);
2151                 }
2152               else
2153                 art_free(pri_point);pri_point =0;
2154           } else {
2155             art_free(pri_point);pri_point = 0;
2156           }
2157         }
2158       else
2159         {
2160           int n_stack = seg->n_stack;
2161
2162           if (n_stack > 1)
2163             {
2164               art_svp_intersect_process_intersection (ctx, seg);
2165               art_free (pri_point);
2166             }
2167           else
2168             {
2169               art_svp_intersect_advance_cursor (ctx, seg, pri_point);
2170             }
2171         }
2172         lasty = ctx->y;
2173     }
2174
2175   art_svp_intersect_horiz_commit (ctx);
2176
2177   art_pri_free (pq);
2178   art_free (ctx);
2179   current_svp = 0;
2180 }