/* Libart_LGPL - library of basic graphic primitives
* Copyright (C) 2001 Raph Levien
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the
* Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*/
/* This file contains a testbed implementation of the new intersection
code.
*/
#include "config.h"
#include "art_svp_intersect.h"
#include <math.h> /* for sqrt */
/* Sanitychecking verifies the main invariant on every priority queue
point. Do not use in production, as it slows things down way too
much. */
#define noSANITYCHECK
/* This can be used in production, to prevent hangs. Eventually, it
should not be necessary. */
#define CHEAP_SANITYCHECK
#include "art_misc.h"
/* A priority queue - perhaps move to a separate file if it becomes
needed somewhere else */
#define ART_PRIQ_USE_HEAP
typedef struct _ArtPriQ ArtPriQ;
typedef struct _ArtPriPoint ArtPriPoint;
struct _ArtPriQ {
gint n_items;
gint n_items_max;
ArtPriPoint **items;
};
struct _ArtPriPoint {
gdouble x;
gdouble y;
gpointer user_data;
};
static ArtPriQ *
art_pri_new (void)
{
ArtPriQ *result = art_new (ArtPriQ, 1);
result->n_items = 0;
result->n_items_max = 16;
result->items = art_new (ArtPriPoint *, result->n_items_max);
return result;
}
static void
art_pri_free (ArtPriQ *pq)
{
art_free (pq->items);
art_free (pq);
}
static art_boolean
art_pri_empty (ArtPriQ *pq)
{
return pq->n_items == 0;
}
#ifdef ART_PRIQ_USE_HEAP
/* This heap implementation is based on Vasek Chvatal's course notes:
http://www.cs.rutgers.edu/~chvatal/notes/pq.html#heap */
static void
art_pri_bubble_up (ArtPriQ *pq, gint vacant, ArtPriPoint *missing)
{
ArtPriPoint **items = pq->items;
gint parent;
parent = (vacant - 1) >> 1;
while (vacant > 0 && (missing->y < items[parent]->y ||
(missing->y == items[parent]->y &&
missing->x < items[parent]->x)))
{
items[vacant] = items[parent];
vacant = parent;
parent = (vacant - 1) >> 1;
}
items[vacant] = missing;
}
static void
art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
{
if (pq->n_items == pq->n_items_max)
art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
art_pri_bubble_up (pq, pq->n_items++, point);
}
static void
art_pri_sift_down_from_root (ArtPriQ *pq, ArtPriPoint *missing)
{
ArtPriPoint **items = pq->items;
gint vacant = 0, child = 2;
gint n = pq->n_items;
while (child < n)
{
if (items[child - 1]->y < items[child]->y ||
(items[child - 1]->y == items[child]->y &&
items[child - 1]->x < items[child]->x))
child--;
items[vacant] = items[child];
vacant = child;
child = (vacant + 1) << 1;
}
if (child == n)
{
items[vacant] = items[n - 1];
vacant = n - 1;
}
art_pri_bubble_up (pq, vacant, missing);
}
static ArtPriPoint *
art_pri_choose (ArtPriQ *pq)
{
ArtPriPoint *result = pq->items[0];
art_pri_sift_down_from_root (pq, pq->items[--pq->n_items]);
return result;
}
#else
/* Choose least point in queue */
static ArtPriPoint *
art_pri_choose (ArtPriQ *pq)
{
gint i;
gint best = 0;
gdouble best_x, best_y;
gdouble y;
ArtPriPoint *result;
if (pq->n_items == 0)
return NULL;
best_x = pq->items[best]->x;
best_y = pq->items[best]->y;
for (i = 1; i < pq->n_items; i++)
{
y = pq->items[i]->y;
if (y < best_y || (y == best_y && pq->items[i]->x < best_x))
{
best = i;
best_x = pq->items[best]->x;
best_y = y;
}
}
result = pq->items[best];
pq->items[best] = pq->items[--pq->n_items];
return result;
}
static void
art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
{
if (pq->n_items == pq->n_items_max)
art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
pq->items[pq->n_items++] = point;
}
#endif
#ifdef TEST_PRIQ
#include <stdlib.h> /* for rand() */
#include <stdio.h>
static double
double_rand (gdouble lo, gdouble hi, gint quant)
{
gint tmp = rand () / (RAND_MAX * (1.0 / quant)) + 0.5;
return lo + tmp * ((hi - lo) / quant);
}
/*
* This custom allocator for priority queue points is here so I can
* test speed. It doesn't look like it will be that significant, but
* if I want a small improvement later, it's something.
*/
typedef ArtPriPoint *ArtPriPtPool;
static ArtPriPtPool *
art_pri_pt_pool_new (void)
{
ArtPriPtPool *result = art_new (ArtPriPtPool, 1);
*result = NULL;
return result;
}
static ArtPriPoint *
art_pri_pt_alloc (ArtPriPtPool *pool)
{
ArtPriPoint *result = *pool;
if (result == NULL)
return art_new (ArtPriPoint, 1);
else
{
*pool = result->user_data;
return result;
}
}
static void
art_pri_pt_free (ArtPriPtPool *pool, ArtPriPoint *pt)
{
pt->user_data = *pool;
*pool = pt;
}
static void
art_pri_pt_pool_free (ArtPriPtPool *pool)
{
ArtPriPoint *pt = *pool;
while (pt != NULL)
{
ArtPriPoint *next = pt->user_data;
art_free (pt);
pt = next;
}
art_free (pool);
}
gint
main (gint argc, gchar **argv)
{
ArtPriPtPool *pool = art_pri_pt_pool_new ();
ArtPriQ *pq;
gint i, j;
const gint n_iter = 1;
const gint pq_size = 100;
for (j = 0; j < n_iter; j++)
{
pq = art_pri_new ();
for (i = 0; i < pq_size; i++)
{
ArtPriPoint *pt = art_pri_pt_alloc (pool);
pt->x = double_rand (0, 1, 100);
pt->y = double_rand (0, 1, 100);
pt->user_data = (gpointer)i;
art_pri_insert (pq, pt);
}
while (!art_pri_empty (pq))
{
ArtPriPoint *pt = art_pri_choose (pq);
if (n_iter == 1)
printf ("(%g, %g), %d\n", pt->x, pt->y, (gint)pt->user_data);
art_pri_pt_free (pool, pt);
}
art_pri_free (pq);
}
art_pri_pt_pool_free (pool);
return 0;
}
#else /* TEST_PRIQ */
/* A virtual class for an "svp writer". A client of this object creates an
SVP by repeatedly calling "add segment" and "add point" methods on it.
*/
typedef struct _ArtSvpWriterRewind ArtSvpWriterRewind;
/* An implementation of the svp writer virtual class that applies the
winding rule. */
struct _ArtSvpWriterRewind {
ArtSvpWriter super;
ArtWindRule rule;
ArtSVP *svp;
gint n_segs_max;
gint *n_points_max;
};
static gint
art_svp_writer_rewind_add_segment (ArtSvpWriter *self, gint wind_left,
gint delta_wind, gdouble x, gdouble y)
{
ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
ArtSVP *svp;
ArtSVPSeg *seg;
art_boolean left_filled, right_filled;
gint wind_right = wind_left + delta_wind;
gint seg_num;
const gint init_n_points_max = 4;
switch (swr->rule)
{
case ART_WIND_RULE_NONZERO:
left_filled = (wind_left != 0);
right_filled = (wind_right != 0);
break;
case ART_WIND_RULE_INTERSECT:
left_filled = (wind_left > 1);
right_filled = (wind_right > 1);
break;
case ART_WIND_RULE_ODDEVEN:
left_filled = (wind_left & 1);
right_filled = (wind_right & 1);
break;
case ART_WIND_RULE_POSITIVE:
left_filled = (wind_left > 0);
right_filled = (wind_right > 0);
break;
default:
art_die ("Unknown wind rule %d\n", swr->rule);
}
if (left_filled == right_filled)
{
/* discard segment now */
return -1;
}
svp = swr->svp;
seg_num = svp->n_segs++;
if (swr->n_segs_max == seg_num)
{
swr->n_segs_max <<= 1;
svp = (ArtSVP *)art_realloc (svp, sizeof (ArtSVP) +
(swr->n_segs_max - 1) *
sizeof (ArtSVPSeg));
swr->svp = svp;
swr->n_points_max = art_renew (swr->n_points_max, int,
swr->n_segs_max);
}
seg = &svp->segs[seg_num];
seg->n_points = 1;
seg->dir = right_filled;
swr->n_points_max[seg_num] = init_n_points_max;
seg->bbox.x0 = x;
seg->bbox.y0 = y;
seg->bbox.x1 = x;
seg->bbox.y1 = y;
seg->points = art_new (ArtPoint, init_n_points_max);
seg->points[0].x = x;
seg->points[0].y = y;
return seg_num;
}
static void
art_svp_writer_rewind_add_point (ArtSvpWriter *self, gint seg_id,
gdouble x, gdouble y)
{
ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
ArtSVPSeg *seg;
gint n_points;
if (seg_id < 0)
/* omitted segment */
return;
seg = &swr->svp->segs[seg_id];
n_points = seg->n_points++;
if (swr->n_points_max[seg_id] == n_points)
art_expand (seg->points, ArtPoint, swr->n_points_max[seg_id]);
seg->points[n_points].x = x;
seg->points[n_points].y = y;
if (x < seg->bbox.x0)
seg->bbox.x0 = x;
if (x > seg->bbox.x1)
seg->bbox.x1 = x;
seg->bbox.y1 = y;
}
static void
art_svp_writer_rewind_close_segment (ArtSvpWriter *self, gint seg_id)
{
/* Not needed for this simple implementation. A potential future
optimization is to merge segments that can be merged safely. */
#ifdef SANITYCHECK
ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
ArtSVPSeg *seg;
if (seg_id >= 0)
{
seg = &swr->svp->segs[seg_id];
if (seg->n_points < 2)
art_warn ("*** closing segment %d with only %d point%s\n",
seg_id, seg->n_points, seg->n_points == 1 ? "" : "s");
}
#endif
}
ArtSVP *
art_svp_writer_rewind_reap (ArtSvpWriter *self)
{
ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
ArtSVP *result = swr->svp;
art_free (swr->n_points_max);
art_free (swr);
return result;
}
ArtSvpWriter *
art_svp_writer_rewind_new (ArtWindRule rule)
{
ArtSvpWriterRewind *result = art_new (ArtSvpWriterRewind, 1);
result->super.add_segment = art_svp_writer_rewind_add_segment;
result->super.add_point = art_svp_writer_rewind_add_point;
result->super.close_segment = art_svp_writer_rewind_close_segment;
result->rule = rule;
result->n_segs_max = 16;
result->svp = art_alloc (sizeof (ArtSVP) +
(result->n_segs_max - 1) * sizeof (ArtSVPSeg));
result->svp->n_segs = 0;
result->n_points_max = art_new (int, result->n_segs_max);
return &result->super;
}
/* Now, data structures for the active list */
typedef struct _ArtActiveSeg ArtActiveSeg;
/* Note: BNEG is 1 for \ lines, and 0 for /. Thus,
x[(flags & BNEG) ^ 1] <= x[flags & BNEG] */
#define ART_ACTIVE_FLAGS_BNEG 1
/* This flag is set if the segment has been inserted into the active
list. */
#define ART_ACTIVE_FLAGS_IN_ACTIVE 2
/* This flag is set when the segment is to be deleted in the
horiz commit process. */
#define ART_ACTIVE_FLAGS_DEL 4
/* This flag is set if the seg_id is a valid output segment. */
#define ART_ACTIVE_FLAGS_OUT 8
/* This flag is set if the segment is in the horiz list. */
#define ART_ACTIVE_FLAGS_IN_HORIZ 16
struct _ArtActiveSeg {
gint flags;
gint wind_left, delta_wind;
ArtActiveSeg *left, *right; /* doubly linked list structure */
const ArtSVPSeg *in_seg;
gint in_curs;
gdouble x[2];
gdouble y0, y1;
gdouble a, b, c; /* line equation; ax+by+c = 0 for the line, a^2 + b^2 = 1,
and a>0 */
/* bottom point and intersection point stack */
gint n_stack;
gint n_stack_max;
ArtPoint *stack;
/* horiz commit list */
ArtActiveSeg *horiz_left, *horiz_right;
gdouble horiz_x;
gint horiz_delta_wind;
gint seg_id;
};
typedef struct _ArtIntersectCtx ArtIntersectCtx;
struct _ArtIntersectCtx {
const ArtSVP *in;
ArtSvpWriter *out;
ArtPriQ *pq;
ArtActiveSeg *active_head;
gdouble y;
ArtActiveSeg *horiz_first;
ArtActiveSeg *horiz_last;
/* segment index of next input segment to be added to pri q */
gint in_curs;
};
#define EPSILON_A 1e-5 /* Threshold for breaking lines at point insertions */
/**
* art_svp_intersect_setup_seg: Set up an active segment from input segment.
* @seg: Active segment.
* @pri_pt: Priority queue point to initialize.
*
* Sets the x[], a, b, c, flags, and stack fields according to the
* line from the current cursor value. Sets the priority queue point
* to the bottom point of this line. Also advances the input segment
* cursor.
**/
static void
art_svp_intersect_setup_seg (ArtActiveSeg *seg, ArtPriPoint *pri_pt)
{
const ArtSVPSeg *in_seg = seg->in_seg;
gint in_curs = seg->in_curs++;
gdouble x0, y0, x1, y1;
gdouble dx, dy, s;
gdouble a, b, r2;
x0 = in_seg->points[in_curs].x;
y0 = in_seg->points[in_curs].y;
x1 = in_seg->points[in_curs + 1].x;
y1 = in_seg->points[in_curs + 1].y;
pri_pt->x = x1;
pri_pt->y = y1;
dx = x1 - x0;
dy = y1 - y0;
r2 = dx * dx + dy * dy;
s = r2 == 0 ? 1 : 1 / sqrt (r2);
seg->a = a = dy * s;
seg->b = b = -dx * s;
seg->c = -(a * x0 + b * y0);
seg->flags = (seg->flags & ~ART_ACTIVE_FLAGS_BNEG) | (dx > 0);
seg->x[0] = x0;
seg->x[1] = x1;
seg->y0 = y0;
seg->y1 = y1;
seg->n_stack = 1;
seg->stack[0].x = x1;
seg->stack[0].y = y1;
}
/**
* art_svp_intersect_add_horiz: Add point to horizontal list.
* @ctx: Intersector context.
* @seg: Segment with point to insert into horizontal list.
*
* Inserts @seg into horizontal list, keeping it in ascending horiz_x
* order.
*
* Note: the horiz_commit routine processes "clusters" of segs in the
* horiz list, all sharing the same horiz_x value. The cluster is
* processed in active list order, rather than horiz list order. Thus,
* the order of segs in the horiz list sharing the same horiz_x
* _should_ be irrelevant. Even so, we use b as a secondary sorting key,
* as a "belt and suspenders" defensive coding tactic.
**/
static void
art_svp_intersect_add_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
{
ArtActiveSeg **pp = &ctx->horiz_last;
ArtActiveSeg *place;
ArtActiveSeg *place_right = NULL;
#ifdef CHEAP_SANITYCHECK
if (seg->flags & ART_ACTIVE_FLAGS_IN_HORIZ)
{
art_warn ("*** attempt to put segment in horiz list twice\n");
return;
}
seg->flags |= ART_ACTIVE_FLAGS_IN_HORIZ;
#endif
for (place = *pp; place != NULL && (place->horiz_x > seg->horiz_x ||
(place->horiz_x == seg->horiz_x &&
place->b < seg->b));
place = *pp)
{
place_right = place;
pp = &place->horiz_left;
}
*pp = seg;
seg->horiz_left = place;
seg->horiz_right = place_right;
if (place == NULL)
ctx->horiz_first = seg;
else
place->horiz_right = seg;
}
static void
art_svp_intersect_push_pt (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
gdouble x, gdouble y)
{
ArtPriPoint *pri_pt;
gint n_stack = seg->n_stack;
if (n_stack == seg->n_stack_max)
art_expand (seg->stack, ArtPoint, seg->n_stack_max);
seg->stack[n_stack].x = x;
seg->stack[n_stack].y = y;
seg->n_stack++;
seg->x[1] = x;
seg->y1 = y;
pri_pt = art_new (ArtPriPoint, 1);
pri_pt->x = x;
pri_pt->y = y;
pri_pt->user_data = seg;
art_pri_insert (ctx->pq, pri_pt);
}
typedef enum {
ART_BREAK_LEFT = 1,
ART_BREAK_RIGHT = 2
} ArtBreakFlags;
/**
* art_svp_intersect_break: Break an active segment.
*
* Note: y must be greater than the top point's y, and less than
* the bottom's.
*
* Return value: x coordinate of break point.
*/
static double
art_svp_intersect_break (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
gdouble x_ref, gdouble y, ArtBreakFlags break_flags)
{
gdouble x0, y0, x1, y1;
const ArtSVPSeg *in_seg = seg->in_seg;
gint in_curs = seg->in_curs;
gdouble x;
x0 = in_seg->points[in_curs - 1].x;
y0 = in_seg->points[in_curs - 1].y;
x1 = in_seg->points[in_curs].x;
y1 = in_seg->points[in_curs].y;
x = x0 + (x1 - x0) * ((y - y0) / (y1 - y0));
if ((break_flags == ART_BREAK_LEFT && x > x_ref) ||
(break_flags == ART_BREAK_RIGHT && x < x_ref))
{
}
/* I think we can count on min(x0, x1) <= x <= max(x0, x1) with sane
arithmetic, but it might be worthwhile to check just in case. */
if (y > ctx->y)
art_svp_intersect_push_pt (ctx, seg, x, y);
else
{
seg->x[0] = x;
seg->y0 = y;
seg->horiz_x = x;
art_svp_intersect_add_horiz (ctx, seg);
}
return x;
}
/**
* art_svp_intersect_add_point: Add a point, breaking nearby neighbors.
* @ctx: Intersector context.
* @x: X coordinate of point to add.
* @y: Y coordinate of point to add.
* @seg: "nearby" segment, or NULL if leftmost.
*
* Return value: Segment immediately to the left of the new point, or
* NULL if the new point is leftmost.
**/
static ArtActiveSeg *
art_svp_intersect_add_point (ArtIntersectCtx *ctx, gdouble x, gdouble y,
ArtActiveSeg *seg, ArtBreakFlags break_flags)
{
ArtActiveSeg *left, *right;
gdouble x_min = x, x_max = x;
art_boolean left_live, right_live;
gdouble d;
gdouble new_x;
ArtActiveSeg *test, *result = NULL;
gdouble x_test;
left = seg;
if (left == NULL)
right = ctx->active_head;
else
right = left->right;
left_live = (break_flags & ART_BREAK_LEFT) && (left != NULL);
right_live = (break_flags & ART_BREAK_RIGHT) && (right != NULL);
while (left_live || right_live)
{
if (left_live)
{
if (x <= left->x[left->flags & ART_ACTIVE_FLAGS_BNEG] &&
/* It may be that one of these conjuncts turns out to be always
true. We test both anyway, to be defensive. */
y != left->y0 && y < left->y1)
{
d = x_min * left->a + y * left->b + left->c;
if (d < EPSILON_A)
{
new_x = art_svp_intersect_break (ctx, left, x_min, y,
ART_BREAK_LEFT);
if (new_x > x_max)
{
x_max = new_x;
right_live = (right != NULL);
}
else if (new_x < x_min)
x_min = new_x;
left = left->left;
left_live = (left != NULL);
}
else
left_live = ART_FALSE;
}
else
left_live = ART_FALSE;
}
else if (right_live)
{
if (x >= right->x[(right->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] &&
/* It may be that one of these conjuncts turns out to be always
true. We test both anyway, to be defensive. */
y != right->y0 && y < right->y1)
{
d = x_max * right->a + y * right->b + right->c;
if (d > -EPSILON_A)
{
new_x = art_svp_intersect_break (ctx, right, x_max, y,
ART_BREAK_RIGHT);
if (new_x < x_min)
{
x_min = new_x;
left_live = (left != NULL);
}
else if (new_x >= x_max)
x_max = new_x;
right = right->right;
right_live = (right != NULL);
}
else
right_live = ART_FALSE;
}
else
right_live = ART_FALSE;
}
}
/* Ascending order is guaranteed by break_flags. Thus, we don't need
to actually fix up non-ascending pairs. */
/* Now, (left, right) defines an interval of segments broken. Sort
into ascending x order. */
test = left == NULL ? ctx->active_head : left->right;
result = left;
if (test != NULL && test != right)
{
if (y == test->y0)
x_test = test->x[0];
else /* assert y == test->y1, I think */
x_test = test->x[1];
for (;;)
{
if (x_test <= x)
result = test;
test = test->right;
if (test == right)
break;
new_x = x_test;
if (new_x < x_test)
{
art_warn ("art_svp_intersect_add_point: non-ascending x\n");
}
x_test = new_x;
}
}
return result;
}
static void
art_svp_intersect_swap_active (ArtIntersectCtx *ctx,
ArtActiveSeg *left_seg, ArtActiveSeg *right_seg)
{
right_seg->left = left_seg->left;
if (right_seg->left != NULL)
right_seg->left->right = right_seg;
else
ctx->active_head = right_seg;
left_seg->right = right_seg->right;
if (left_seg->right != NULL)
left_seg->right->left = left_seg;
left_seg->left = right_seg;
right_seg->right = left_seg;
}
/**
* art_svp_intersect_test_cross: Test crossing of a pair of active segments.
* @ctx: Intersector context.
* @left_seg: Left segment of the pair.
* @right_seg: Right segment of the pair.
* @break_flags: Flags indicating whether to break neighbors.
*
* Tests crossing of @left_seg and @right_seg. If there is a crossing,
* inserts the intersection point into both segments.
*
* Return value: True if the intersection took place at the current
* scan line, indicating further iteration is needed.
**/
static art_boolean
art_svp_intersect_test_cross (ArtIntersectCtx *ctx,
ArtActiveSeg *left_seg, ArtActiveSeg *right_seg,
ArtBreakFlags break_flags)
{
gdouble left_x0, left_y0, left_x1;
gdouble left_y1 = left_seg->y1;
gdouble right_y1 = right_seg->y1;
gdouble d;
const ArtSVPSeg *in_seg;
gint in_curs;
gdouble d0, d1, t;
gdouble x, y; /* intersection point */
if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0])
{
/* Top points of left and right segments coincide. This case
feels like a bit of duplication - we may want to merge it
with the cases below. However, this way, we're sure that this
logic makes only localized changes. */
if (left_y1 < right_y1)
{
/* Test left (x1, y1) against right segment */
gdouble left_x1 = left_seg->x[1];
if (left_x1 <
right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
left_y1 == right_seg->y0)
return ART_FALSE;
d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
if (d < -EPSILON_A)
return ART_FALSE;
else if (d < EPSILON_A)
{
/* I'm unsure about the break flags here. */
gdouble right_x1 = art_svp_intersect_break (ctx, right_seg,
left_x1, left_y1,
ART_BREAK_RIGHT);
if (left_x1 <= right_x1)
return ART_FALSE;
}
}
else if (left_y1 > right_y1)
{
/* Test right (x1, y1) against left segment */
gdouble right_x1 = right_seg->x[1];
if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
right_y1 == left_seg->y0)
return ART_FALSE;
d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
if (d > EPSILON_A)
return ART_FALSE;
else if (d > -EPSILON_A)
{
/* See above regarding break flags. */
gdouble left_x1 = art_svp_intersect_break (ctx, left_seg,
right_x1, right_y1,
ART_BREAK_LEFT);
if (left_x1 <= right_x1)
return ART_FALSE;
}
}
else /* left_y1 == right_y1 */
{
gdouble left_x1 = left_seg->x[1];
gdouble right_x1 = right_seg->x[1];
if (left_x1 <= right_x1)
return ART_FALSE;
}
art_svp_intersect_swap_active (ctx, left_seg, right_seg);
return ART_TRUE;
}
if (left_y1 < right_y1)
{
/* Test left (x1, y1) against right segment */
gdouble left_x1 = left_seg->x[1];
if (left_x1 <
right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
left_y1 == right_seg->y0)
return ART_FALSE;
d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
if (d < -EPSILON_A)
return ART_FALSE;
else if (d < EPSILON_A)
{
gdouble right_x1 = art_svp_intersect_break (ctx, right_seg,
left_x1, left_y1,
ART_BREAK_RIGHT);
if (left_x1 <= right_x1)
return ART_FALSE;
}
}
else if (left_y1 > right_y1)
{
/* Test right (x1, y1) against left segment */
gdouble right_x1 = right_seg->x[1];
if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
right_y1 == left_seg->y0)
return ART_FALSE;
d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
if (d > EPSILON_A)
return ART_FALSE;
else if (d > -EPSILON_A)
{
gdouble left_x1 = art_svp_intersect_break (ctx, left_seg,
right_x1, right_y1,
ART_BREAK_LEFT);
if (left_x1 <= right_x1)
return ART_FALSE;
}
}
else /* left_y1 == right_y1 */
{
gdouble left_x1 = left_seg->x[1];
gdouble right_x1 = right_seg->x[1];
if (left_x1 <= right_x1)
return ART_FALSE;
}
/* The segments cross. Find the intersection point. */
in_seg = left_seg->in_seg;
in_curs = left_seg->in_curs;
left_x0 = in_seg->points[in_curs - 1].x;
left_y0 = in_seg->points[in_curs - 1].y;
left_x1 = in_seg->points[in_curs].x;
left_y1 = in_seg->points[in_curs].y;
d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c;
d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
if (d0 == d1)
{
x = left_x0;
y = left_y0;
}
else
{
/* Is this division always safe? It could possibly overflow. */
t = d0 / (d0 - d1);
if (t <= 0)
{
x = left_x0;
y = left_y0;
}
else if (t >= 1)
{
x = left_x1;
y = left_y1;
}
else
{
x = left_x0 + t * (left_x1 - left_x0);
y = left_y0 + t * (left_y1 - left_y0);
}
}
/* Make sure intersection point is within bounds of right seg. */
if (y < right_seg->y0)
{
x = right_seg->x[0];
y = right_seg->y0;
}
else if (y > right_seg->y1)
{
x = right_seg->x[1];
y = right_seg->y1;
}
else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1])
x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1];
else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG])
x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG];
if (y == left_seg->y0)
{
if (y != right_seg->y0)
{
art_svp_intersect_push_pt (ctx, right_seg, x, y);
if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
art_svp_intersect_add_point (ctx, x, y, right_seg->right,
break_flags);
}
else
{
/* Intersection takes place at current scan line; process
immediately rather than queueing intersection point into
priq. */
ArtActiveSeg *winner, *loser;
/* Choose "most vertical" segement */
if (left_seg->a > right_seg->a)
{
winner = left_seg;
loser = right_seg;
}
else
{
winner = right_seg;
loser = left_seg;
}
loser->x[0] = winner->x[0];
loser->horiz_x = loser->x[0];
loser->horiz_delta_wind += loser->delta_wind;
winner->horiz_delta_wind -= loser->delta_wind;
art_svp_intersect_swap_active (ctx, left_seg, right_seg);
return ART_TRUE;
}
}
else if (y == right_seg->y0)
{
art_svp_intersect_push_pt (ctx, left_seg, x, y);
if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
art_svp_intersect_add_point (ctx, x, y, left_seg->left,
break_flags);
}
else
{
/* Insert the intersection point into both segments. */
art_svp_intersect_push_pt (ctx, left_seg, x, y);
art_svp_intersect_push_pt (ctx, right_seg, x, y);
if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
art_svp_intersect_add_point (ctx, x, y, left_seg->left, break_flags);
if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
art_svp_intersect_add_point (ctx, x, y, right_seg->right, break_flags);
}
return ART_FALSE;
}
/**
* art_svp_intersect_active_delete: Delete segment from active list.
* @ctx: Intersection context.
* @seg: Segment to delete.
*
* Deletes @seg from the active list.
**/
static /* todo inline */ void
art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
{
ArtActiveSeg *left = seg->left, *right = seg->right;
if (left != NULL)
left->right = right;
else
ctx->active_head = right;
if (right != NULL)
right->left = left;
}
/**
* art_svp_intersect_active_free: Free an active segment.
* @seg: Segment to delete.
*
* Frees @seg.
**/
static /* todo inline */ void
art_svp_intersect_active_free (ArtActiveSeg *seg)
{
art_free (seg->stack);
art_free (seg);
}
/**
* art_svp_intersect_insert_cross: Test crossings of newly inserted line.
*
* Tests @seg against its left and right neighbors for intersections.
* Precondition: the line in @seg is not purely horizontal.
**/
static void
art_svp_intersect_insert_cross (ArtIntersectCtx *ctx,
ArtActiveSeg *seg)
{
ArtActiveSeg *left = seg, *right = seg;
for (;;)
{
if (left != NULL)
{
ArtActiveSeg *leftc;
for (leftc = left->left; leftc != NULL; leftc = leftc->left)
if (!(leftc->flags & ART_ACTIVE_FLAGS_DEL))
break;
if (leftc != NULL &&
art_svp_intersect_test_cross (ctx, leftc, left,
ART_BREAK_LEFT))
{
if (left == right || right == NULL)
right = left->right;
}
else
{
left = NULL;
}
}
else if (right != NULL && right->right != NULL)
{
ArtActiveSeg *rightc;
for (rightc = right->right; rightc != NULL; rightc = rightc->right)
if (!(rightc->flags & ART_ACTIVE_FLAGS_DEL))
break;
if (rightc != NULL &&
art_svp_intersect_test_cross (ctx, right, rightc,
ART_BREAK_RIGHT))
{
if (left == right || left == NULL)
left = right->left;
}
else
{
right = NULL;
}
}
else
break;
}
}
/**
* art_svp_intersect_horiz: Add horizontal line segment.
* @ctx: Intersector context.
* @seg: Segment on which to add horizontal line.
* @x0: Old x position.
* @x1: New x position.
*
* Adds a horizontal line from @x0 to @x1, and updates the current
* location of @seg to @x1.
**/
static void
art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
gdouble x0, gdouble x1)
{
ArtActiveSeg *hs;
if (x0 == x1)
return;
hs = art_new (ArtActiveSeg, 1);
hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT);
if (seg->flags & ART_ACTIVE_FLAGS_OUT)
{
ArtSvpWriter *swr = ctx->out;
swr->add_point (swr, seg->seg_id, x0, ctx->y);
}
hs->seg_id = seg->seg_id;
hs->horiz_x = x0;
hs->horiz_delta_wind = seg->delta_wind;
hs->stack = NULL;
/* Ideally, the (a, b, c) values will never be read. However, there
are probably some tests remaining that don't check for _DEL
before evaluating the line equation. For those, these
initializations will at least prevent a UMR of the values, which
can crash on some platforms. */
hs->a = 0.0;
hs->b = 0.0;
hs->c = 0.0;
seg->horiz_delta_wind -= seg->delta_wind;
art_svp_intersect_add_horiz (ctx, hs);
if (x0 > x1)
{
ArtActiveSeg *left;
art_boolean first = ART_TRUE;
for (left = seg->left; left != NULL; left = seg->left)
{
gint left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG;
if (left->x[left_bneg] <= x1)
break;
if (left->x[left_bneg ^ 1] <= x1 &&
x1 * left->a + ctx->y * left->b + left->c >= 0)
break;
if (left->y0 != ctx->y && left->y1 != ctx->y)
{
art_svp_intersect_break (ctx, left, x1, ctx->y, ART_BREAK_LEFT);
}
art_svp_intersect_swap_active (ctx, left, seg);
if (first && left->right != NULL)
{
art_svp_intersect_test_cross (ctx, left, left->right,
ART_BREAK_RIGHT);
first = ART_FALSE;
}
}
}
else
{
ArtActiveSeg *right;
art_boolean first = ART_TRUE;
for (right = seg->right; right != NULL; right = seg->right)
{
gint right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG;
if (right->x[right_bneg ^ 1] >= x1)
break;
if (right->x[right_bneg] >= x1 &&
x1 * right->a + ctx->y * right->b + right->c <= 0)
break;
if (right->y0 != ctx->y && right->y1 != ctx->y)
{
art_svp_intersect_break (ctx, right, x1, ctx->y,
ART_BREAK_LEFT);
}
art_svp_intersect_swap_active (ctx, seg, right);
if (first && right->left != NULL)
{
art_svp_intersect_test_cross (ctx, right->left, right,
ART_BREAK_RIGHT);
first = ART_FALSE;
}
}
}
seg->x[0] = x1;
seg->x[1] = x1;
seg->horiz_x = x1;
seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
}
/**
* art_svp_intersect_insert_line: Insert a line into the active list.
* @ctx: Intersector context.
* @seg: Segment containing line to insert.
*
* Inserts the line into the intersector context, taking care of any
* intersections, and adding the appropriate horizontal points to the
* active list.
**/
static void
art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
{
if (seg->y1 == seg->y0)
{
art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]);
}
else
{
art_svp_intersect_insert_cross (ctx, seg);
art_svp_intersect_add_horiz (ctx, seg);
}
}
static void
art_svp_intersect_process_intersection (ArtIntersectCtx *ctx,
ArtActiveSeg *seg)
{
gint n_stack = --seg->n_stack;
seg->x[1] = seg->stack[n_stack - 1].x;
seg->y1 = seg->stack[n_stack - 1].y;
seg->x[0] = seg->stack[n_stack].x;
seg->y0 = seg->stack[n_stack].y;
seg->horiz_x = seg->x[0];
art_svp_intersect_insert_line (ctx, seg);
}
static void
art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
ArtPriPoint *pri_pt)
{
const ArtSVPSeg *in_seg = seg->in_seg;
gint in_curs = seg->in_curs;
ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL;
if (swr != NULL)
swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1);
if (in_curs + 1 == in_seg->n_points)
{
ArtActiveSeg *left = seg->left, *right = seg->right;
#if 0
if (swr != NULL)
swr->close_segment (swr, seg->seg_id);
seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
#endif
seg->flags |= ART_ACTIVE_FLAGS_DEL;
art_svp_intersect_add_horiz (ctx, seg);
art_svp_intersect_active_delete (ctx, seg);
if (left != NULL && right != NULL)
art_svp_intersect_test_cross (ctx, left, right,
ART_BREAK_LEFT | ART_BREAK_RIGHT);
art_free (pri_pt);
}
else
{
seg->horiz_x = seg->x[1];
art_svp_intersect_setup_seg (seg, pri_pt);
art_pri_insert (ctx->pq, pri_pt);
art_svp_intersect_insert_line (ctx, seg);
}
}
static void
art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg)
{
ArtActiveSeg *seg = art_new (ArtActiveSeg, 1);
ArtActiveSeg *test;
gdouble x0, y0;
ArtActiveSeg *beg_range;
ArtActiveSeg *last = NULL;
ArtActiveSeg *left, *right;
ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1);
seg->flags = 0;
seg->in_seg = in_seg;
seg->in_curs = 0;
seg->n_stack_max = 4;
seg->stack = art_new (ArtPoint, seg->n_stack_max);
seg->horiz_delta_wind = 0;
seg->wind_left = 0;
pri_pt->user_data = seg;
art_svp_intersect_setup_seg (seg, pri_pt);
art_pri_insert (ctx->pq, pri_pt);
/* Find insertion place for new segment */
/* This is currently a left-to-right scan, but should be replaced
with a binary search as soon as it's validated. */
x0 = in_seg->points[0].x;
y0 = in_seg->points[0].y;
beg_range = NULL;
for (test = ctx->active_head; test != NULL; test = test->right)
{
gdouble d;
gint test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG;
if (x0 < test->x[test_bneg])
{
if (x0 < test->x[test_bneg ^ 1])
break;
d = x0 * test->a + y0 * test->b + test->c;
if (d < 0)
break;
}
last = test;
}
left = art_svp_intersect_add_point (ctx, x0, y0, last,
ART_BREAK_LEFT | ART_BREAK_RIGHT);
seg->left = left;
if (left == NULL)
{
right = ctx->active_head;
ctx->active_head = seg;
}
else
{
right = left->right;
left->right = seg;
}
seg->right = right;
if (right != NULL)
right->left = seg;
seg->delta_wind = in_seg->dir ? 1 : -1;
seg->horiz_x = x0;
art_svp_intersect_insert_line (ctx, seg);
}
/**
* art_svp_intersect_horiz_commit: Commit points in horiz list to output.
* @ctx: Intersection context.
*
* The main function of the horizontal commit is to output new
* points to the output writer.
*
* This "commit" pass is also where winding numbers are assigned,
* because doing it here provides much greater tolerance for inputs
* which are not in strict SVP order.
*
* Each cluster in the horiz_list contains both segments that are in
* the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not,
* and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We
* need to deal with both.
**/
static void
art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx)
{
ArtActiveSeg *seg;
gint winding_number = 0; /* initialization just to avoid warning */
gint horiz_wind = 0;
gdouble last_x = 0; /* initialization just to avoid warning */
/* Output points to svp writer. */
for (seg = ctx->horiz_first; seg != NULL;)
{
/* Find a cluster with common horiz_x, */
ArtActiveSeg *curs;
gdouble x = seg->horiz_x;
/* Generate any horizontal segments. */
if (horiz_wind != 0)
{
ArtSvpWriter *swr = ctx->out;
gint seg_id;
seg_id = swr->add_segment (swr, winding_number, horiz_wind,
last_x, ctx->y);
swr->add_point (swr, seg_id, x, ctx->y);
swr->close_segment (swr, seg_id);
}
/* Find first active segment in cluster. */
for (curs = seg; curs != NULL && curs->horiz_x == x;
curs = curs->horiz_right)
if (!(curs->flags & ART_ACTIVE_FLAGS_DEL))
break;
if (curs != NULL && curs->horiz_x == x)
{
/* There exists at least one active segment in this cluster. */
/* Find beginning of cluster. */
for (; curs->left != NULL; curs = curs->left)
if (curs->left->horiz_x != x)
break;
if (curs->left != NULL)
winding_number = curs->left->wind_left + curs->left->delta_wind;
else
winding_number = 0;
do
{
if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) ||
curs->wind_left != winding_number)
{
ArtSvpWriter *swr = ctx->out;
if (curs->flags & ART_ACTIVE_FLAGS_OUT)
{
swr->add_point (swr, curs->seg_id,
curs->horiz_x, ctx->y);
swr->close_segment (swr, curs->seg_id);
}
curs->seg_id = swr->add_segment (swr, winding_number,
curs->delta_wind,
x, ctx->y);
curs->flags |= ART_ACTIVE_FLAGS_OUT;
}
curs->wind_left = winding_number;
winding_number += curs->delta_wind;
curs = curs->right;
}
while (curs != NULL && curs->horiz_x == x);
}
/* Skip past cluster. */
do
{
ArtActiveSeg *next = seg->horiz_right;
seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ;
horiz_wind += seg->horiz_delta_wind;
seg->horiz_delta_wind = 0;
if (seg->flags & ART_ACTIVE_FLAGS_DEL)
{
if (seg->flags & ART_ACTIVE_FLAGS_OUT)
{
ArtSvpWriter *swr = ctx->out;
swr->close_segment (swr, seg->seg_id);
}
art_svp_intersect_active_free (seg);
}
seg = next;
}
while (seg != NULL && seg->horiz_x == x);
last_x = x;
}
ctx->horiz_first = NULL;
ctx->horiz_last = NULL;
}
#ifdef SANITYCHECK
static void
art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx)
{
ArtActiveSeg *seg;
ArtActiveSeg *last = NULL;
gdouble d;
for (seg = ctx->active_head; seg != NULL; seg = seg->right)
{
if (seg->left != last)
{
art_warn ("*** art_svp_intersect_sanitycheck: last=%lx, seg->left=%lx\n",
(unsigned long)last, (unsigned long)seg->left);
}
if (last != NULL)
{
/* pairwise compare with previous seg */
/* First the top. */
if (last->y0 < seg->y0)
{
}
else
{
}
/* Then the bottom. */
if (last->y1 < seg->y1)
{
if (!((last->x[1] <
seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) ||
last->y1 == seg->y0))
{
d = last->x[1] * seg->a + last->y1 * seg->b + seg->c;
if (d >= -EPSILON_A)
art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to right (d = %g)\n",
last->x[1], last->y1, (unsigned long) last,
(unsigned long) seg, d);
}
}
else if (last->y1 > seg->y1)
{
if (!((seg->x[1] >
last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) ||
seg->y1 == last->y0))
{
d = seg->x[1] * last->a + seg->y1 * last->b + last->c;
if (d <= EPSILON_A)
art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to left (d = %g)\n",
seg->x[1], seg->y1, (unsigned long) seg,
(unsigned long) last, d);
}
}
else
{
if (last->x[1] > seg->x[1])
art_warn ("*** bottoms (%g, %g) of %lx and (%g, %g) of %lx out of order\n",
last->x[1], last->y1, (unsigned long)last,
seg->x[1], seg->y1, (unsigned long)seg);
}
}
last = seg;
}
}
#endif
void
art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out)
{
ArtIntersectCtx *ctx;
ArtPriQ *pq;
ArtPriPoint *first_point;
if (in->n_segs == 0)
return;
ctx = art_new (ArtIntersectCtx, 1);
ctx->in = in;
ctx->out = out;
pq = art_pri_new ();
ctx->pq = pq;
ctx->active_head = NULL;
ctx->horiz_first = NULL;
ctx->horiz_last = NULL;
ctx->in_curs = 0;
first_point = art_new (ArtPriPoint, 1);
first_point->x = in->segs[0].points[0].x;
first_point->y = in->segs[0].points[0].y;
first_point->user_data = NULL;
ctx->y = first_point->y;
art_pri_insert (pq, first_point);
while (!art_pri_empty (pq))
{
ArtPriPoint *pri_point = art_pri_choose (pq);
ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data;
#ifdef SANITYCHECK
art_svp_intersect_sanitycheck (ctx);
#endif
if (ctx->y != pri_point->y)
{
art_svp_intersect_horiz_commit (ctx);
ctx->y = pri_point->y;
}
if (seg == NULL)
{
/* Insert new segment from input */
const ArtSVPSeg *in_seg = &in->segs[ctx->in_curs++];
art_svp_intersect_add_seg (ctx, in_seg);
if (ctx->in_curs < in->n_segs)
{
const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs];
pri_point->x = next_seg->points[0].x;
pri_point->y = next_seg->points[0].y;
/* user_data is already NULL */
art_pri_insert (pq, pri_point);
}
else
art_free (pri_point);
}
else
{
gint n_stack = seg->n_stack;
if (n_stack > 1)
{
art_svp_intersect_process_intersection (ctx, seg);
art_free (pri_point);
}
else
{
art_svp_intersect_advance_cursor (ctx, seg, pri_point);
}
}
}
art_svp_intersect_horiz_commit (ctx);
art_pri_free (pq);
art_free (ctx);
}
#endif /* not TEST_PRIQ */
