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