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 = (ArtSVP*)art_alloc (sizeof(ArtSVP) +
 462                            (result->n_segs_max - 1) * sizeof(ArtSVPSeg));
 463   result->svp->n_segs = 0;
 464   result->n_points_max = (int*)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 #define ART_BREAK_LEFT 1
 654 #define ART_BREAK_RIGHT 2
 655
 656 /**
 657  * art_svp_intersect_break: Break an active segment.
 658  *
 659  * Note: y must be greater than the top point's y, and less than
 660  * the bottom's.
 661  *
 662  * Return value: x coordinate of break point.
 663  */
 664 static double
 665 art_svp_intersect_break (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
 666                          double x_ref, double y, int break_flags)
 667 {
 668   double x0, y0, x1, y1;
 669   const ArtSVPSeg *in_seg = seg->in_seg;
 670   int in_curs = seg->in_curs;
 671   double x;
 672
 673   x0 = in_seg->points[in_curs - 1].x;
 674   y0 = in_seg->points[in_curs - 1].y;
 675   x1 = in_seg->points[in_curs].x;
 676   y1 = in_seg->points[in_curs].y;
 677   x = x0 + (x1 - x0) * ((y - y0) / (y1 - y0));
 678   if ((break_flags == ART_BREAK_LEFT && x > x_ref) ||
 679       (break_flags == ART_BREAK_RIGHT && x < x_ref))
 680     {
 681 #ifdef VERBOSE
 682       art_dprint ("art_svp_intersect_break: limiting x to %f, was %f, %s\n",
 683                   x_ref, x, break_flags == ART_BREAK_LEFT ? "left" : "right");
 684       x = x_ref;
 685 #endif
 686     }
 687
 688   /* I think we can count on min(x0, x1) <= x <= max(x0, x1) with sane
 689      arithmetic, but it might be worthwhile to check just in case. */
 690
 691   if (y > ctx->y)
 692     art_svp_intersect_push_pt (ctx, seg, x, y);
 693   else
 694     {
 695       seg->x[0] = x;
 696       seg->y0 = y;
 697       seg->horiz_x = x;
 698       art_svp_intersect_add_horiz (ctx, seg);
 699     }
 700
 701   return x;
 702 }
 703
 704 /**
 705  * art_svp_intersect_add_point: Add a point, breaking nearby neighbors.
 706  * @ctx: Intersector context.
 707  * @x: X coordinate of point to add.
 708  * @y: Y coordinate of point to add.
 709  * @seg: "nearby" segment, or NULL if leftmost.
 710  *
 711  * Return value: Segment immediately to the left of the new point, or
 712  * NULL if the new point is leftmost.
 713  **/
 714 static ArtActiveSeg *
 715 art_svp_intersect_add_point (ArtIntersectCtx *ctx, double x, double y,
 716                              ArtActiveSeg *seg, int break_flags)
 717 {
 718   ArtActiveSeg *left, *right;
 719   double x_min = x, x_max = x;
 720   art_boolean left_live, right_live;
 721   double d;
 722   double new_x;
 723   ArtActiveSeg *test, *result = NULL;
 724   double x_test;
 725
 726   left = seg;
 727   if (left == NULL)
 728     right = ctx->active_head;
 729   else
 730     right = left->right;
 731   left_live = (break_flags & ART_BREAK_LEFT) && (left != NULL);
 732   right_live = (break_flags & ART_BREAK_RIGHT) && (right != NULL);
 733   while (left_live || right_live)
 734     {
 735       if (left_live)
 736         {
 737           if (x <= left->x[left->flags & ART_ACTIVE_FLAGS_BNEG] &&
 738               /* It may be that one of these conjuncts turns out to be always
 739                  true. We test both anyway, to be defensive. */
 740               y != left->y0 && y < left->y1)
 741             {
 742               d = x_min * left->a + y * left->b + left->c;
 743               if (d < EPSILON_A)
 744                 {
 745                   new_x = art_svp_intersect_break (ctx, left, x_min, y,
 746                                                    ART_BREAK_LEFT);
 747                   if (new_x > x_max)
 748                     {
 749                       x_max = new_x;
 750                       right_live = (right != NULL);
 751                     }
 752                   else if (new_x < x_min)
 753                     x_min = new_x;
 754                   left = left->left;
 755                   left_live = (left != NULL);
 756                 }
 757               else
 758                 left_live = ART_FALSE;
 759             }
 760           else
 761             left_live = ART_FALSE;
 762         }
 763       else if (right_live)
 764         {
 765           if (x >= right->x[(right->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] &&
 766               /* It may be that one of these conjuncts turns out to be always
 767                  true. We test both anyway, to be defensive. */
 768               y != right->y0 && y < right->y1)
 769             {
 770               d = x_max * right->a + y * right->b + right->c;
 771               if (d > -EPSILON_A)
 772                 {
 773                   new_x = art_svp_intersect_break (ctx, right, x_max, y,
 774                                                    ART_BREAK_RIGHT);
 775                   if (new_x < x_min)
 776                     {
 777                       x_min = new_x;
 778                       left_live = (left != NULL);
 779                     }
 780                   else if (new_x >= x_max)
 781                     x_max = new_x;
 782                   right = right->right;
 783                   right_live = (right != NULL);
 784                 }
 785               else
 786                 right_live = ART_FALSE;
 787             }
 788           else
 789             right_live = ART_FALSE;
 790         }
 791     }
 792
 793   /* Ascending order is guaranteed by break_flags. Thus, we don't need
 794      to actually fix up non-ascending pairs. */
 795
 796   /* Now, (left, right) defines an interval of segments broken. Sort
 797      into ascending x order. */
 798   test = left == NULL ? ctx->active_head : left->right;
 799   result = left;
 800   if (test != NULL && test != right)
 801     {
 802       if (y == test->y0)
 803         x_test = test->x[0];
 804       else /* assert y == test->y1, I think */
 805         x_test = test->x[1];
 806       for (;;)
 807         {
 808           if (x_test <= x)
 809             result = test;
 810           test = test->right;
 811           if (test == right)
 812             break;
 813           new_x = x_test;
 814           if (new_x < x_test)
 815             {
 816               art_warn ("art_svp_intersect_add_point: non-ascending x\n");
 817             }
 818           x_test = new_x;
 819         }
 820     }
 821   return result;
 822 }
 823
 824 static void
 825 art_svp_intersect_swap_active (ArtIntersectCtx *ctx,
 826                                ArtActiveSeg *left_seg, ArtActiveSeg *right_seg)
 827 {
 828   right_seg->left = left_seg->left;
 829   if (right_seg->left != NULL)
 830     right_seg->left->right = right_seg;
 831   else
 832     ctx->active_head = right_seg;
 833   left_seg->right = right_seg->right;
 834   if (left_seg->right != NULL)
 835     left_seg->right->left = left_seg;
 836   left_seg->left = right_seg;
 837   right_seg->right = left_seg;
 838 }
 839
 840 /**
 841  * art_svp_intersect_test_cross: Test crossing of a pair of active segments.
 842  * @ctx: Intersector context.
 843  * @left_seg: Left segment of the pair.
 844  * @right_seg: Right segment of the pair.
 845  * @break_flags: Flags indicating whether to break neighbors.
 846  *
 847  * Tests crossing of @left_seg and @right_seg. If there is a crossing,
 848  * inserts the intersection point into both segments.
 849  *
 850  * Return value: True if the intersection took place at the current
 851  * scan line, indicating further iteration is needed.
 852  **/
 853 static art_boolean
 854 art_svp_intersect_test_cross (ArtIntersectCtx *ctx,
 855                               ArtActiveSeg *left_seg, ArtActiveSeg *right_seg,
 856                               int break_flags)
 857 {
 858   double left_x0, left_y0, left_x1;
 859   double left_y1 = left_seg->y1;
 860   double right_y1 = right_seg->y1;
 861   double d;
 862
 863   const ArtSVPSeg *in_seg;
 864   int in_curs;
 865   double d0, d1, t;
 866   double x, y; /* intersection point */
 867
 868 #ifdef VERBOSE
 869   static int count = 0;
 870
 871   art_dprint ("art_svp_intersect_test_cross %lx <-> %lx: count=%d\n",
 872           (unsigned long)left_seg, (unsigned long)right_seg, count++);
 873 #endif
 874
 875   if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0])
 876     {
 877       /* Top points of left and right segments coincide. This case
 878          feels like a bit of duplication - we may want to merge it
 879          with the cases below. However, this way, we're sure that this
 880          logic makes only localized changes. */
 881
 882       if (left_y1 < right_y1)
 883         {
 884           /* Test left (x1, y1) against right segment */
 885           double left_x1 = left_seg->x[1];
 886
 887           if (left_x1 <
 888               right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
 889               left_y1 == right_seg->y0)
 890             return ART_FALSE;
 891           d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
 892           if (d < -EPSILON_A)
 893             return ART_FALSE;
 894           else if (d < EPSILON_A)
 895             {
 896               /* I'm unsure about the break flags here. */
 897               double right_x1 = art_svp_intersect_break (ctx, right_seg,
 898                                                          left_x1, left_y1,
 899                                                          ART_BREAK_RIGHT);
 900               if (left_x1 <= right_x1)
 901                 return ART_FALSE;
 902             }
 903         }
 904       else if (left_y1 > right_y1)
 905         {
 906           /* Test right (x1, y1) against left segment */
 907           double right_x1 = right_seg->x[1];
 908
 909           if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
 910               right_y1 == left_seg->y0)
 911             return ART_FALSE;
 912           d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
 913           if (d > EPSILON_A)
 914             return ART_FALSE;
 915           else if (d > -EPSILON_A)
 916             {
 917               /* See above regarding break flags. */
 918               double left_x1 = art_svp_intersect_break (ctx, left_seg,
 919                                                         right_x1, right_y1,
 920                                                         ART_BREAK_LEFT);
 921               if (left_x1 <= right_x1)
 922                 return ART_FALSE;
 923             }
 924         }
 925       else /* left_y1 == right_y1 */
 926         {
 927           double left_x1 = left_seg->x[1];
 928           double right_x1 = right_seg->x[1];
 929
 930           if (left_x1 <= right_x1)
 931             return ART_FALSE;
 932         }
 933       art_svp_intersect_swap_active (ctx, left_seg, right_seg);
 934       return ART_TRUE;
 935     }
 936
 937   if (left_y1 < right_y1)
 938     {
 939       /* Test left (x1, y1) against right segment */
 940       double left_x1 = left_seg->x[1];
 941
 942       if (left_x1 <
 943           right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
 944           left_y1 == right_seg->y0)
 945         return ART_FALSE;
 946       d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
 947       if (d < -EPSILON_A)
 948         return ART_FALSE;
 949       else if (d < EPSILON_A)
 950         {
 951           double right_x1 = art_svp_intersect_break (ctx, right_seg,
 952                                                      left_x1, left_y1,
 953                                                      ART_BREAK_RIGHT);
 954           if (left_x1 <= right_x1)
 955             return ART_FALSE;
 956         }
 957     }
 958   else if (left_y1 > right_y1)
 959     {
 960       /* Test right (x1, y1) against left segment */
 961       double right_x1 = right_seg->x[1];
 962
 963       if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
 964           right_y1 == left_seg->y0)
 965         return ART_FALSE;
 966       d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
 967       if (d > EPSILON_A)
 968         return ART_FALSE;
 969       else if (d > -EPSILON_A)
 970         {
 971           double left_x1 = art_svp_intersect_break (ctx, left_seg,
 972                                                     right_x1, right_y1,
 973                                                     ART_BREAK_LEFT);
 974           if (left_x1 <= right_x1)
 975             return ART_FALSE;
 976         }
 977     }
 978   else /* left_y1 == right_y1 */
 979     {
 980       double left_x1 = left_seg->x[1];
 981       double right_x1 = right_seg->x[1];
 982
 983       if (left_x1 <= right_x1)
 984         return ART_FALSE;
 985     }
 986
 987   /* The segments cross. Find the intersection point. */
 988
 989   in_seg = left_seg->in_seg;
 990   in_curs = left_seg->in_curs;
 991   left_x0 = in_seg->points[in_curs - 1].x;
 992   left_y0 = in_seg->points[in_curs - 1].y;
 993   left_x1 = in_seg->points[in_curs].x;
 994   left_y1 = in_seg->points[in_curs].y;
 995   d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c;
 996   d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
 997   if (d0 == d1)
 998     {
 999       x = left_x0;
1000       y = left_y0;
1001     }
1002   else
1003     {
1004       /* Is this division always safe? It could possibly overflow. */
1005       t = d0 / (d0 - d1);
1006       if (t <= 0)
1007         {
1008           x = left_x0;
1009           y = left_y0;
1010         }
1011       else if (t >= 1)
1012         {
1013           x = left_x1;
1014           y = left_y1;
1015         }
1016       else
1017         {
1018           x = left_x0 + t * (left_x1 - left_x0);
1019           y = left_y0 + t * (left_y1 - left_y0);
1020         }
1021     }
1022
1023   /* Make sure intersection point is within bounds of right seg. */
1024   if (y < right_seg->y0)
1025     {
1026       x = right_seg->x[0];
1027       y = right_seg->y0;
1028     }
1029   else if (y > right_seg->y1)
1030     {
1031       x = right_seg->x[1];
1032       y = right_seg->y1;
1033     }
1034   else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1])
1035     x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1];
1036   else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG])
1037     x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG];
1038
1039   if (y == left_seg->y0)
1040     {
1041       if (y != right_seg->y0)
1042         {
1043 #ifdef VERBOSE
1044           art_dprint ("art_svp_intersect_test_cross: intersection (%g, %g) matches former y0 of %lx, %lx\n",
1045                     x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1046 #endif
1047           art_svp_intersect_push_pt (ctx, right_seg, x, y);
1048           if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1049             art_svp_intersect_add_point (ctx, x, y, right_seg->right,
1050                                          break_flags);
1051         }
1052       else
1053         {
1054           /* Intersection takes place at current scan line; process
1055              immediately rather than queueing intersection point into
1056              priq. */
1057           ArtActiveSeg *winner, *loser;
1058
1059           /* Choose "most vertical" segement */
1060           if (left_seg->a > right_seg->a)
1061             {
1062               winner = left_seg;
1063               loser = right_seg;
1064             }
1065           else
1066             {
1067               winner = right_seg;
1068               loser = left_seg;
1069             }
1070
1071           loser->x[0] = winner->x[0];
1072           loser->horiz_x = loser->x[0];
1073           loser->horiz_delta_wind += loser->delta_wind;
1074           winner->horiz_delta_wind -= loser->delta_wind;
1075
1076           art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1077           return ART_TRUE;
1078         }
1079     }
1080   else if (y == right_seg->y0)
1081     {
1082 #ifdef VERBOSE
1083       art_dprint ("*** art_svp_intersect_test_cross: intersection (%g, %g) matches latter y0 of %lx, %lx\n",
1084               x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1085 #endif
1086       art_svp_intersect_push_pt (ctx, left_seg, x, y);
1087       if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1088         art_svp_intersect_add_point (ctx, x, y, left_seg->left,
1089                                      break_flags);
1090     }
1091   else
1092     {
1093 #ifdef VERBOSE
1094       art_dprint ("Inserting (%g, %g) into %lx, %lx\n",
1095               x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1096 #endif
1097       /* Insert the intersection point into both segments. */
1098       art_svp_intersect_push_pt (ctx, left_seg, x, y);
1099       art_svp_intersect_push_pt (ctx, right_seg, x, y);
1100       if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1101         art_svp_intersect_add_point (ctx, x, y, left_seg->left, break_flags);
1102       if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1103         art_svp_intersect_add_point (ctx, x, y, right_seg->right, break_flags);
1104     }
1105   return ART_FALSE;
1106 }
1107
1108 /**
1109  * art_svp_intersect_active_delete: Delete segment from active list.
1110  * @ctx: Intersection context.
1111  * @seg: Segment to delete.
1112  *
1113  * Deletes @seg from the active list.
1114  **/
1115 static /* todo inline */ void
1116 art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1117 {
1118   ArtActiveSeg *left = seg->left, *right = seg->right;
1119
1120   if (left != NULL)
1121     left->right = right;
1122   else
1123     ctx->active_head = right;
1124   if (right != NULL)
1125     right->left = left;
1126 }
1127
1128 /**
1129  * art_svp_intersect_active_free: Free an active segment.
1130  * @seg: Segment to delete.
1131  *
1132  * Frees @seg.
1133  **/
1134 static /* todo inline */ void
1135 art_svp_intersect_active_free (ArtActiveSeg *seg)
1136 {
1137   art_free (seg->stack);
1138 #ifdef VERBOSE
1139   art_dprint ("Freeing %lx\n", (unsigned long) seg);
1140 #endif
1141   art_free (seg);
1142 }
1143
1144 /**
1145  * art_svp_intersect_insert_cross: Test crossings of newly inserted line.
1146  *
1147  * Tests @seg against its left and right neighbors for intersections.
1148  * Precondition: the line in @seg is not purely horizontal.
1149  **/
1150 static void
1151 art_svp_intersect_insert_cross (ArtIntersectCtx *ctx,
1152                                 ArtActiveSeg *seg)
1153 {
1154   ArtActiveSeg *left = seg, *right = seg;
1155
1156   for (;;)
1157     {
1158       if (left != NULL)
1159         {
1160           ArtActiveSeg *leftc;
1161
1162           for (leftc = left->left; leftc != NULL; leftc = leftc->left)
1163             if (!(leftc->flags & ART_ACTIVE_FLAGS_DEL))
1164               break;
1165           if (leftc != NULL &&
1166               art_svp_intersect_test_cross (ctx, leftc, left,
1167                                             ART_BREAK_LEFT))
1168             {
1169               if (left == right || right == NULL)
1170                 right = left->right;
1171             }
1172           else
1173             {
1174               left = NULL;
1175             }
1176         }
1177       else if (right != NULL && right->right != NULL)
1178         {
1179           ArtActiveSeg *rightc;
1180
1181           for (rightc = right->right; rightc != NULL; rightc = rightc->right)
1182             if (!(rightc->flags & ART_ACTIVE_FLAGS_DEL))
1183               break;
1184           if (rightc != NULL &&
1185               art_svp_intersect_test_cross (ctx, right, rightc,
1186                                             ART_BREAK_RIGHT))
1187             {
1188               if (left == right || left == NULL)
1189                 left = right->left;
1190             }
1191           else
1192             {
1193               right = NULL;
1194             }
1195         }
1196       else
1197         break;
1198     }
1199 }
1200
1201 /**
1202  * art_svp_intersect_horiz: Add horizontal line segment.
1203  * @ctx: Intersector context.
1204  * @seg: Segment on which to add horizontal line.
1205  * @x0: Old x position.
1206  * @x1: New x position.
1207  *
1208  * Adds a horizontal line from @x0 to @x1, and updates the current
1209  * location of @seg to @x1.
1210  **/
1211 static void
1212 art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1213                          double x0, double x1)
1214 {
1215   ArtActiveSeg *hs;
1216
1217   if (x0 == x1)
1218     return;
1219
1220   hs = art_new (ArtActiveSeg, 1);
1221
1222   hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT);
1223   if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1224     {
1225       ArtSvpWriter *swr = ctx->out;
1226
1227       swr->add_point (swr, seg->seg_id, x0, ctx->y);
1228     }
1229   hs->seg_id = seg->seg_id;
1230   hs->horiz_x = x0;
1231   hs->horiz_delta_wind = seg->delta_wind;
1232   hs->stack = NULL;
1233
1234   /* Ideally, the (a, b, c) values will never be read. However, there
1235      are probably some tests remaining that don't check for _DEL
1236      before evaluating the line equation. For those, these
1237      initializations will at least prevent a UMR of the values, which
1238      can crash on some platforms. */
1239   hs->a = 0.0;
1240   hs->b = 0.0;
1241   hs->c = 0.0;
1242
1243   seg->horiz_delta_wind -= seg->delta_wind;
1244
1245   art_svp_intersect_add_horiz (ctx, hs);
1246
1247   if (x0 > x1)
1248     {
1249       ArtActiveSeg *left;
1250       art_boolean first = ART_TRUE;
1251
1252       for (left = seg->left; left != NULL; left = seg->left)
1253         {
1254           int left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG;
1255
1256           if (left->x[left_bneg] <= x1)
1257             break;
1258           if (left->x[left_bneg ^ 1] <= x1 &&
1259               x1 * left->a + ctx->y * left->b + left->c >= 0)
1260             break;
1261           if (left->y0 != ctx->y && left->y1 != ctx->y)
1262             {
1263               art_svp_intersect_break (ctx, left, x1, ctx->y, ART_BREAK_LEFT);
1264             }
1265 #ifdef VERBOSE
1266           art_dprint ("x0=%g > x1=%g, swapping %lx, %lx\n",
1267                   x0, x1, (unsigned long)left, (unsigned long)seg);
1268 #endif
1269           art_svp_intersect_swap_active (ctx, left, seg);
1270           if (first && left->right != NULL)
1271             {
1272               art_svp_intersect_test_cross (ctx, left, left->right,
1273                                             ART_BREAK_RIGHT);
1274               first = ART_FALSE;
1275             }
1276         }
1277     }
1278   else
1279     {
1280       ArtActiveSeg *right;
1281       art_boolean first = ART_TRUE;
1282
1283       for (right = seg->right; right != NULL; right = seg->right)
1284         {
1285           int right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG;
1286
1287           if (right->x[right_bneg ^ 1] >= x1)
1288             break;
1289           if (right->x[right_bneg] >= x1 &&
1290               x1 * right->a + ctx->y * right->b + right->c <= 0)
1291             break;
1292           if (right->y0 != ctx->y && right->y1 != ctx->y)
1293             {
1294               art_svp_intersect_break (ctx, right, x1, ctx->y,
1295                                        ART_BREAK_LEFT);
1296             }
1297 #ifdef VERBOSE
1298           art_dprint ("[right]x0=%g < x1=%g, swapping %lx, %lx\n",
1299                   x0, x1, (unsigned long)seg, (unsigned long)right);
1300 #endif
1301           art_svp_intersect_swap_active (ctx, seg, right);
1302           if (first && right->left != NULL)
1303             {
1304               art_svp_intersect_test_cross (ctx, right->left, right,
1305                                             ART_BREAK_RIGHT);
1306               first = ART_FALSE;
1307             }
1308         }
1309     }
1310
1311   seg->x[0] = x1;
1312   seg->x[1] = x1;
1313   seg->horiz_x = x1;
1314   seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1315 }
1316
1317 /**
1318  * art_svp_intersect_insert_line: Insert a line into the active list.
1319  * @ctx: Intersector context.
1320  * @seg: Segment containing line to insert.
1321  *
1322  * Inserts the line into the intersector context, taking care of any
1323  * intersections, and adding the appropriate horizontal points to the
1324  * active list.
1325  **/
1326 static void
1327 art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1328 {
1329   if (seg->y1 == seg->y0)
1330     {
1331 #ifdef VERBOSE
1332       art_dprint ("art_svp_intersect_insert_line: %lx is horizontal\n",
1333               (unsigned long)seg);
1334 #endif
1335       art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]);
1336     }
1337   else
1338     {
1339       art_svp_intersect_insert_cross (ctx, seg);
1340       art_svp_intersect_add_horiz (ctx, seg);
1341     }
1342 }
1343
1344 static void
1345 art_svp_intersect_process_intersection (ArtIntersectCtx *ctx,
1346                                         ArtActiveSeg *seg)
1347 {
1348   int n_stack = --seg->n_stack;
1349   seg->x[1] = seg->stack[n_stack - 1].x;
1350   seg->y1 = seg->stack[n_stack - 1].y;
1351   seg->x[0] = seg->stack[n_stack].x;
1352   seg->y0 = seg->stack[n_stack].y;
1353   seg->horiz_x = seg->x[0];
1354   art_svp_intersect_insert_line (ctx, seg);
1355 }
1356
1357 static void
1358 art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1359                                   ArtPriPoint *pri_pt)
1360 {
1361   const ArtSVPSeg *in_seg = seg->in_seg;
1362   int in_curs = seg->in_curs;
1363   ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL;
1364
1365   if (swr != NULL)
1366     swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1);
1367   if (in_curs + 1 == in_seg->n_points)
1368     {
1369       ArtActiveSeg *left = seg->left, *right = seg->right;
1370
1371 #if 0
1372       if (swr != NULL)
1373         swr->close_segment (swr, seg->seg_id);
1374       seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1375 #endif
1376       seg->flags |= ART_ACTIVE_FLAGS_DEL;
1377       art_svp_intersect_add_horiz (ctx, seg);
1378       art_svp_intersect_active_delete (ctx, seg);
1379       if (left != NULL && right != NULL)
1380         art_svp_intersect_test_cross (ctx, left, right,
1381                                       ART_BREAK_LEFT | ART_BREAK_RIGHT);
1382       art_free (pri_pt);
1383     }
1384   else
1385     {
1386       seg->horiz_x = seg->x[1];
1387
1388       art_svp_intersect_setup_seg (seg, pri_pt);
1389       art_pri_insert (ctx->pq, pri_pt);
1390       art_svp_intersect_insert_line (ctx, seg);
1391     }
1392 }
1393
1394 static void
1395 art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg)
1396 {
1397   ArtActiveSeg *seg = art_new (ArtActiveSeg, 1);
1398   ArtActiveSeg *test;
1399   double x0, y0;
1400   ArtActiveSeg *beg_range;
1401   ArtActiveSeg *last = NULL;
1402   ArtActiveSeg *left, *right;
1403   ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1);
1404
1405   seg->flags = 0;
1406   seg->in_seg = in_seg;
1407   seg->in_curs = 0;
1408
1409   seg->n_stack_max = 4;
1410   seg->stack = art_new (ArtPoint, seg->n_stack_max);
1411
1412   seg->horiz_delta_wind = 0;
1413
1414   seg->wind_left = 0;
1415
1416   pri_pt->user_data = seg;
1417   art_svp_intersect_setup_seg (seg, pri_pt);
1418   art_pri_insert (ctx->pq, pri_pt);
1419
1420   /* Find insertion place for new segment */
1421   /* This is currently a left-to-right scan, but should be replaced
1422      with a binary search as soon as it's validated. */
1423
1424   x0 = in_seg->points[0].x;
1425   y0 = in_seg->points[0].y;
1426   beg_range = NULL;
1427   for (test = ctx->active_head; test != NULL; test = test->right)
1428     {
1429       double d;
1430       int test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG;
1431
1432       if (x0 < test->x[test_bneg])
1433         {
1434           if (x0 < test->x[test_bneg ^ 1])
1435             break;
1436           d = x0 * test->a + y0 * test->b + test->c;
1437           if (d < 0)
1438             break;
1439         }
1440       last = test;
1441     }
1442
1443   left = art_svp_intersect_add_point (ctx, x0, y0, last, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1444   seg->left = left;
1445   if (left == NULL)
1446     {
1447       right = ctx->active_head;
1448       ctx->active_head = seg;
1449     }
1450   else
1451     {
1452       right = left->right;
1453       left->right = seg;
1454     }
1455   seg->right = right;
1456   if (right != NULL)
1457     right->left = seg;
1458
1459   seg->delta_wind = in_seg->dir ? 1 : -1;
1460   seg->horiz_x = x0;
1461
1462   art_svp_intersect_insert_line (ctx, seg);
1463 }
1464
1465 #ifdef SANITYCHECK
1466 static void
1467 art_svp_intersect_sanitycheck_winding (ArtIntersectCtx *ctx)
1468 {
1469 #if 0
1470   /* At this point, we seem to be getting false positives, so it's
1471      turned off for now. */
1472
1473   ArtActiveSeg *seg;
1474   int winding_number = 0;
1475
1476   for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1477     {
1478       /* Check winding number consistency. */
1479       if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1480         {
1481           if (winding_number != seg->wind_left)
1482             art_warn ("*** art_svp_intersect_sanitycheck_winding: seg %lx has wind_left of %d, expected %d\n",
1483                   (unsigned long) seg, seg->wind_left, winding_number);
1484           winding_number = seg->wind_left + seg->delta_wind;
1485         }
1486     }
1487   if (winding_number != 0)
1488     art_warn ("*** art_svp_intersect_sanitycheck_winding: non-balanced winding number %d\n",
1489               winding_number);
1490 #endif
1491 }
1492 #endif
1493
1494 /**
1495  * art_svp_intersect_horiz_commit: Commit points in horiz list to output.
1496  * @ctx: Intersection context.
1497  *
1498  * The main function of the horizontal commit is to output new
1499  * points to the output writer.
1500  *
1501  * This "commit" pass is also where winding numbers are assigned,
1502  * because doing it here provides much greater tolerance for inputs
1503  * which are not in strict SVP order.
1504  *
1505  * Each cluster in the horiz_list contains both segments that are in
1506  * the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not,
1507  * and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We
1508  * need to deal with both.
1509  **/
1510 static void
1511 art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx)
1512 {
1513   ArtActiveSeg *seg;
1514   int winding_number = 0; /* initialization just to avoid warning */
1515   int horiz_wind = 0;
1516   double last_x = 0; /* initialization just to avoid warning */
1517
1518 #ifdef VERBOSE
1519   art_dprint ("art_svp_intersect_horiz_commit: y=%g\n", ctx->y);
1520   for (seg = ctx->horiz_first; seg != NULL; seg = seg->horiz_right)
1521     art_dprint (" %lx: %g %+d\n",
1522             (unsigned long)seg, seg->horiz_x, seg->horiz_delta_wind);
1523 #endif
1524
1525   /* Output points to svp writer. */
1526   for (seg = ctx->horiz_first; seg != NULL;)
1527     {
1528       /* Find a cluster with common horiz_x, */
1529       ArtActiveSeg *curs;
1530       double x = seg->horiz_x;
1531
1532       /* Generate any horizontal segments. */
1533       if (horiz_wind != 0)
1534         {
1535           ArtSvpWriter *swr = ctx->out;
1536           int seg_id;
1537
1538           seg_id = swr->add_segment (swr, winding_number, horiz_wind,
1539                                      last_x, ctx->y);
1540           swr->add_point (swr, seg_id, x, ctx->y);
1541           swr->close_segment (swr, seg_id);
1542         }
1543
1544       /* Find first active segment in cluster. */
1545
1546       for (curs = seg; curs != NULL && curs->horiz_x == x;
1547            curs = curs->horiz_right)
1548         if (!(curs->flags & ART_ACTIVE_FLAGS_DEL))
1549           break;
1550
1551       if (curs != NULL && curs->horiz_x == x)
1552         {
1553           /* There exists at least one active segment in this cluster. */
1554
1555           /* Find beginning of cluster. */
1556           for (; curs->left != NULL; curs = curs->left)
1557             if (curs->left->horiz_x != x)
1558               break;
1559
1560           if (curs->left != NULL)
1561             winding_number = curs->left->wind_left + curs->left->delta_wind;
1562           else
1563             winding_number = 0;
1564
1565           do
1566             {
1567 #ifdef VERBOSE
1568               art_dprint (" curs %lx: winding_number = %d += %d\n",
1569                       (unsigned long)curs, winding_number, curs->delta_wind);
1570 #endif
1571               if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) ||
1572                   curs->wind_left != winding_number)
1573                 {
1574                   ArtSvpWriter *swr = ctx->out;
1575
1576                   if (curs->flags & ART_ACTIVE_FLAGS_OUT)
1577                     {
1578                       swr->add_point (swr, curs->seg_id,
1579                                       curs->horiz_x, ctx->y);
1580                       swr->close_segment (swr, curs->seg_id);
1581                     }
1582
1583                   curs->seg_id = swr->add_segment (swr, winding_number,
1584                                                    curs->delta_wind,
1585                                                    x, ctx->y);
1586                   curs->flags |= ART_ACTIVE_FLAGS_OUT;
1587                 }
1588               curs->wind_left = winding_number;
1589               winding_number += curs->delta_wind;
1590               curs = curs->right;
1591             }
1592           while (curs != NULL && curs->horiz_x == x);
1593         }
1594
1595       /* Skip past cluster. */
1596       do
1597         {
1598           ArtActiveSeg *next = seg->horiz_right;
1599
1600           seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ;
1601           horiz_wind += seg->horiz_delta_wind;
1602           seg->horiz_delta_wind = 0;
1603           if (seg->flags & ART_ACTIVE_FLAGS_DEL)
1604             {
1605               if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1606                 {
1607                   ArtSvpWriter *swr = ctx->out;
1608                   swr->close_segment (swr, seg->seg_id);
1609                 }
1610               art_svp_intersect_active_free (seg);
1611             }
1612           seg = next;
1613         }
1614       while (seg != NULL && seg->horiz_x == x);
1615
1616       last_x = x;
1617     }
1618   ctx->horiz_first = NULL;
1619   ctx->horiz_last = NULL;
1620 #ifdef SANITYCHECK
1621   art_svp_intersect_sanitycheck_winding (ctx);
1622 #endif
1623 }
1624
1625 #ifdef VERBOSE
1626 static void
1627 art_svp_intersect_print_active (ArtIntersectCtx *ctx)
1628 {
1629   ArtActiveSeg *seg;
1630
1631   art_dprint ("Active list (y = %g):\n", ctx->y);
1632   for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1633     {
1634       art_dprint (" %lx: (%g, %g)-(%g, %g), (a, b, c) = (%g, %g, %g)\n",
1635               (unsigned long)seg,
1636               seg->x[0], seg->y0, seg->x[1], seg->y1,
1637               seg->a, seg->b, seg->c);
1638     }
1639 }
1640 #endif
1641
1642 #ifdef SANITYCHECK
1643 static void
1644 art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx)
1645 {
1646   ArtActiveSeg *seg;
1647   ArtActiveSeg *last = NULL;
1648   double d;
1649
1650   for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1651     {
1652       if (seg->left != last)
1653         {
1654           art_warn ("*** art_svp_intersect_sanitycheck: last=%lx, seg->left=%lx\n",
1655                     (unsigned long)last, (unsigned long)seg->left);
1656         }
1657       if (last != NULL)
1658         {
1659           /* pairwise compare with previous seg */
1660
1661           /* First the top. */
1662           if (last->y0 < seg->y0)
1663             {
1664             }
1665           else
1666             {
1667             }
1668
1669           /* Then the bottom. */
1670           if (last->y1 < seg->y1)
1671             {
1672               if (!((last->x[1] <
1673                      seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) ||
1674                     last->y1 == seg->y0))
1675                 {
1676                   d = last->x[1] * seg->a + last->y1 * seg->b + seg->c;
1677                   if (d >= -EPSILON_A)
1678                     art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to right (d = %g)\n",
1679                               last->x[1], last->y1, (unsigned long) last,
1680                               (unsigned long) seg, d);
1681                 }
1682             }
1683           else if (last->y1 > seg->y1)
1684
1685             {
1686               if (!((seg->x[1] >
1687                      last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) ||
1688                     seg->y1 == last->y0))
1689               {
1690                 d = seg->x[1] * last->a + seg->y1 * last->b + last->c;
1691                 if (d <= EPSILON_A)
1692                   art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to left (d = %g)\n",
1693                               seg->x[1], seg->y1, (unsigned long) seg,
1694                               (unsigned long) last, d);
1695               }
1696             }
1697           else
1698             {
1699               if (last->x[1] > seg->x[1])
1700                 art_warn ("*** bottoms (%g, %g) of %lx and (%g, %g) of %lx out of order\n",
1701                           last->x[1], last->y1, (unsigned long)last,
1702                           seg->x[1], seg->y1, (unsigned long)seg);
1703             }
1704         }
1705       last = seg;
1706     }
1707 }
1708 #endif
1709
1710 void
1711 art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out)
1712 {
1713   ArtIntersectCtx *ctx;
1714   ArtPriQ *pq;
1715   ArtPriPoint *first_point;
1716 #ifdef VERBOSE
1717   int count = 0;
1718 #endif
1719
1720   if (in->n_segs == 0)
1721     return;
1722
1723   ctx = art_new (ArtIntersectCtx, 1);
1724   ctx->in = in;
1725   ctx->out = out;
1726   pq = art_pri_new ();
1727   ctx->pq = pq;
1728
1729   ctx->active_head = NULL;
1730
1731   ctx->horiz_first = NULL;
1732   ctx->horiz_last = NULL;
1733
1734   ctx->in_curs = 0;
1735   first_point = art_new (ArtPriPoint, 1);
1736   first_point->x = in->segs[0].points[0].x;
1737   first_point->y = in->segs[0].points[0].y;
1738   first_point->user_data = NULL;
1739   ctx->y = first_point->y;
1740   art_pri_insert (pq, first_point);
1741
1742   while (!art_pri_empty (pq))
1743     {
1744       ArtPriPoint *pri_point = art_pri_choose (pq);
1745       ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data;
1746
1747 #ifdef VERBOSE
1748       art_dprint ("\nIntersector step %d\n", count++);
1749       art_svp_intersect_print_active (ctx);
1750       art_dprint ("priq choose (%g, %g) %lx\n", pri_point->x, pri_point->y,
1751               (unsigned long)pri_point->user_data);
1752 #endif
1753 #ifdef SANITYCHECK
1754       art_svp_intersect_sanitycheck(ctx);
1755 #endif
1756
1757       if (ctx->y != pri_point->y)
1758         {
1759           art_svp_intersect_horiz_commit (ctx);
1760           ctx->y = pri_point->y;
1761         }
1762
1763       if (seg == NULL)
1764         {
1765           /* Insert new segment from input */
1766           const ArtSVPSeg *in_seg = &in->segs[ctx->in_curs++];
1767           art_svp_intersect_add_seg (ctx, in_seg);
1768           if (ctx->in_curs < in->n_segs)
1769             {
1770               const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs];
1771               pri_point->x = next_seg->points[0].x;
1772               pri_point->y = next_seg->points[0].y;
1773               /* user_data is already NULL */
1774               art_pri_insert (pq, pri_point);
1775             }
1776           else
1777             art_free (pri_point);
1778         }
1779       else
1780         {
1781           int n_stack = seg->n_stack;
1782
1783           if (n_stack > 1)
1784             {
1785               art_svp_intersect_process_intersection (ctx, seg);
1786               art_free (pri_point);
1787             }
1788           else
1789             {
1790               art_svp_intersect_advance_cursor (ctx, seg, pri_point);
1791             }
1792         }
1793     }
1794
1795   art_svp_intersect_horiz_commit (ctx);
1796
1797   art_pri_free (pq);
1798   art_free (ctx);
1799 }
1800
1801 #endif /* not TEST_PRIQ */