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