diff options
Diffstat (limited to 'engines/sword25/tools/swfdisplay/art_svp_intersect.cpp')
| -rw-r--r-- | engines/sword25/tools/swfdisplay/art_svp_intersect.cpp | 1329 |
1 files changed, 1329 insertions, 0 deletions
diff --git a/engines/sword25/tools/swfdisplay/art_svp_intersect.cpp b/engines/sword25/tools/swfdisplay/art_svp_intersect.cpp new file mode 100644 index 0000000000..56164996b6 --- /dev/null +++ b/engines/sword25/tools/swfdisplay/art_svp_intersect.cpp @@ -0,0 +1,1329 @@ +/* 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 "art.h" +#include "art_svp_intersect.h" + +#include <math.h> /* for sqrt */ + +/* This can be used in production, to prevent hangs. Eventually, it + should not be necessary. */ +#define CHEAP_SANITYCHECK + +/* 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 { + int n_items; + int n_items_max; + ArtPriPoint **items; +}; + +struct _ArtPriPoint { + double x; + double y; + void *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) { + free(pq->items); + 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, int vacant, ArtPriPoint *missing) { + ArtPriPoint **items = pq->items; + int 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; + int vacant = 0, child = 2; + int 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) { + int i; + int best = 0; + double best_x, best_y; + double 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 + +/* 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; + int n_segs_max; + int *n_points_max; +}; + +static int +art_svp_writer_rewind_add_segment(ArtSvpWriter *self, int wind_left, + int delta_wind, double x, double y) { + ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self; + ArtSVP *svp; + ArtSVPSeg *seg; + art_boolean left_filled, right_filled; + int wind_right = wind_left + delta_wind; + int seg_num; + const int 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 *)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, int seg_id, + double x, double y) { + ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self; + ArtSVPSeg *seg; + int 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, int seg_id) { + /* Not needed for this simple implementation. A potential future + optimization is to merge segments that can be merged safely. */ +} + +ArtSVP * +art_svp_writer_rewind_reap(ArtSvpWriter *self) { + ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self; + ArtSVP *result = swr->svp; + + free(swr->n_points_max); + 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 = (ArtSVP *)malloc(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 { + int flags; + int wind_left, delta_wind; + ArtActiveSeg *left, *right; /* doubly linked list structure */ + + const ArtSVPSeg *in_seg; + int in_curs; + + double x[2]; + double y0, y1; + double 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 */ + int n_stack; + int n_stack_max; + ArtPoint *stack; + + /* horiz commit list */ + ArtActiveSeg *horiz_left, *horiz_right; + double horiz_x; + int horiz_delta_wind; + int seg_id; +}; + +typedef struct _ArtIntersectCtx ArtIntersectCtx; + +struct _ArtIntersectCtx { + const ArtSVP *in; + ArtSvpWriter *out; + + ArtPriQ *pq; + + ArtActiveSeg *active_head; + + double y; + ArtActiveSeg *horiz_first; + ArtActiveSeg *horiz_last; + + /* segment index of next input segment to be added to pri q */ + int 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; + int in_curs = seg->in_curs++; + double x0, y0, x1, y1; + double dx, dy, s; + double 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, + double x, double y) { + ArtPriPoint *pri_pt; + int 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, + double x_ref, double y, ArtBreakFlags break_flags) { + double x0, y0, x1, y1; + const ArtSVPSeg *in_seg = seg->in_seg; + int in_curs = seg->in_curs; + double 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, double x, double y, + ArtActiveSeg *seg, ArtBreakFlags break_flags) { + ArtActiveSeg *left, *right; + double x_min = x, x_max = x; + art_boolean left_live, right_live; + double d; + double new_x; + ArtActiveSeg *test, *result = NULL; + double 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) { + double left_x0, left_y0, left_x1; + double left_y1 = left_seg->y1; + double right_y1 = right_seg->y1; + double d; + + const ArtSVPSeg *in_seg; + int in_curs; + double d0, d1, t; + double 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 */ + 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. */ + double 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 */ + double 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. */ + 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 */ + left_x1 = left_seg->x[1]; + double 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 */ + 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) { + double 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 */ + double 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) { + 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 */ + left_x1 = left_seg->x[1]; + double 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) { + free(seg->stack); + 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, + double x0, double 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) { + int 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) { + int 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) { + int 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; + int 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, + (ArtBreakFlags)(ART_BREAK_LEFT | ART_BREAK_RIGHT)); + 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; + double 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) { + double d; + int 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, (ArtBreakFlags)(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; + int winding_number = 0; /* initialization just to avoid warning */ + int horiz_wind = 0; + double 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; + double x = seg->horiz_x; + + /* Generate any horizontal segments. */ + if (horiz_wind != 0) { + ArtSvpWriter *swr = ctx->out; + int 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; +} + +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; + + 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 + free(pri_point); + } else { + int n_stack = seg->n_stack; + + if (n_stack > 1) { + art_svp_intersect_process_intersection(ctx, seg); + free(pri_point); + } else { + art_svp_intersect_advance_cursor(ctx, seg, pri_point); + } + } + } + + art_svp_intersect_horiz_commit(ctx); + + art_pri_free(pq); + free(ctx); +} |