lib/art/art_svp_intersect.c

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