diff options
| -rw-r--r-- | engines/sword25/gfx/image/art.cpp | 2538 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/art.h | 104 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/art_svp_intersect.cpp | 1344 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/art_svp_intersect.h | 73 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/art_svp_render_aa.cpp | 443 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/art_svp_render_aa.h | 70 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/art_svp_vpath.cpp | 207 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/art_svp_vpath.h | 45 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/art_svp_vpath_stroke.cpp | 657 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/art_svp_vpath_stroke.h | 71 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/art_vpath_bpath.cpp | 276 | ||||
| -rw-r--r-- | engines/sword25/gfx/image/vectorimagerenderer.cpp | 4 | ||||
| -rw-r--r-- | engines/sword25/module.mk | 5 |
13 files changed, 2621 insertions, 3216 deletions
diff --git a/engines/sword25/gfx/image/art.cpp b/engines/sword25/gfx/image/art.cpp index 54cf2e3271..b158e437aa 100644 --- a/engines/sword25/gfx/image/art.cpp +++ b/engines/sword25/gfx/image/art.cpp @@ -36,20 +36,13 @@ #include "art.h" -#ifdef HAVE_UINSTD_H -#include <unistd.h> -#endif -#include <stdio.h> -#include <stdarg.h> - /** * art_die: Print the error message to stderr and exit with a return code of 1. * @fmt: The printf-style format for the error message. * * Used for dealing with severe errors. **/ -void -art_die(const char *fmt, ...) { +void art_die(const char *fmt, ...) { va_list ap; va_start(ap, fmt); @@ -64,8 +57,7 @@ art_die(const char *fmt, ...) { * * Used for generating warnings. **/ -void -art_warn(const char *fmt, ...) { +void art_warn(const char *fmt, ...) { va_list ap; va_start(ap, fmt); @@ -79,8 +71,7 @@ art_warn(const char *fmt, ...) { * * Frees an #ArtSVP structure and all the segments in it. **/ -void -art_svp_free(ArtSVP *svp) { +void art_svp_free(ArtSVP *svp) { int n_segs = svp->n_segs; int i; @@ -89,11 +80,7 @@ art_svp_free(ArtSVP *svp) { free(svp); } -#ifdef ART_USE_NEW_INTERSECTOR #define EPSILON 0 -#else -#define EPSILON 1e-6 -#endif /** * art_svp_seg_compare: Compare two segments of an svp. @@ -103,8 +90,7 @@ art_svp_free(ArtSVP *svp) { * Compares two segments of an svp. Return 1 if @seg2 is below or to the * right of @seg1, -1 otherwise. **/ -int -art_svp_seg_compare(const void *s1, const void *s2) { +int art_svp_seg_compare(const void *s1, const void *s2) { const ArtSVPSeg *seg1 = (const ArtSVPSeg *)s1; const ArtSVPSeg *seg2 = (const ArtSVPSeg *)s2; @@ -135,8 +121,7 @@ art_svp_seg_compare(const void *s1, const void *s2) { * vpath. Thus, it should be called in the order the points are * desired. **/ -void -art_vpath_add_point(ArtVpath **p_vpath, int *pn_points, int *pn_points_max, +void art_vpath_add_point(ArtVpath **p_vpath, int *pn_points, int *pn_points_max, ArtPathcode code, double x, double y) { int i; @@ -147,3 +132,2516 @@ art_vpath_add_point(ArtVpath **p_vpath, int *pn_points, int *pn_points_max, (*p_vpath)[i].x = x; (*p_vpath)[i].y = y; } + +/* Sort vector paths into sorted vector paths */ + +/* reverse a list of points in place */ +static void reverse_points(ArtPoint *points, int n_points) { + int i; + ArtPoint tmp_p; + + for (i = 0; i < (n_points >> 1); i++) { + tmp_p = points[i]; + points[i] = points[n_points - (i + 1)]; + points[n_points - (i + 1)] = tmp_p; + } +} + +/** + * art_svp_from_vpath: Convert a vpath to a sorted vector path. + * @vpath: #ArtVPath to convert. + * + * Converts a vector path into sorted vector path form. The svp form is + * more efficient for rendering and other vector operations. + * + * Basically, the implementation is to traverse the vector path, + * generating a new segment for each "run" of points in the vector + * path with monotonically increasing Y values. All the resulting + * values are then sorted. + * + * Note: I'm not sure that the sorting rule is correct with respect + * to numerical stability issues. + * + * Return value: Resulting sorted vector path. + **/ +ArtSVP *art_svp_from_vpath(ArtVpath *vpath) { + int n_segs, n_segs_max; + ArtSVP *svp; + int dir; + int new_dir; + int i; + ArtPoint *points; + int n_points, n_points_max; + double x, y; + double x_min, x_max; + + n_segs = 0; + n_segs_max = 16; + svp = (ArtSVP *)malloc(sizeof(ArtSVP) + + (n_segs_max - 1) * sizeof(ArtSVPSeg)); + + dir = 0; + n_points = 0; + n_points_max = 0; + points = NULL; + i = 0; + + x = y = 0; /* unnecessary, given "first code must not be LINETO" invariant, + but it makes gcc -Wall -ansi -pedantic happier */ + x_min = x_max = 0; /* same */ + + while (vpath[i].code != ART_END) { + if (vpath[i].code == ART_MOVETO || vpath[i].code == ART_MOVETO_OPEN) { + if (points != NULL && n_points >= 2) { + if (n_segs == n_segs_max) { + n_segs_max <<= 1; + svp = (ArtSVP *)realloc(svp, sizeof(ArtSVP) + + (n_segs_max - 1) * + sizeof(ArtSVPSeg)); + } + svp->segs[n_segs].n_points = n_points; + svp->segs[n_segs].dir = (dir > 0); + if (dir < 0) + reverse_points(points, n_points); + svp->segs[n_segs].points = points; + svp->segs[n_segs].bbox.x0 = x_min; + svp->segs[n_segs].bbox.x1 = x_max; + svp->segs[n_segs].bbox.y0 = points[0].y; + svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; + n_segs++; + points = NULL; + } + + if (points == NULL) { + n_points_max = 4; + points = art_new(ArtPoint, n_points_max); + } + + n_points = 1; + points[0].x = x = vpath[i].x; + points[0].y = y = vpath[i].y; + x_min = x; + x_max = x; + dir = 0; + } else { /* must be LINETO */ + new_dir = (vpath[i].y > y || + (vpath[i].y == y && vpath[i].x > x)) ? 1 : -1; + if (dir && dir != new_dir) { + /* new segment */ + x = points[n_points - 1].x; + y = points[n_points - 1].y; + if (n_segs == n_segs_max) { + n_segs_max <<= 1; + svp = (ArtSVP *)realloc(svp, sizeof(ArtSVP) + + (n_segs_max - 1) * + sizeof(ArtSVPSeg)); + } + svp->segs[n_segs].n_points = n_points; + svp->segs[n_segs].dir = (dir > 0); + if (dir < 0) + reverse_points(points, n_points); + svp->segs[n_segs].points = points; + svp->segs[n_segs].bbox.x0 = x_min; + svp->segs[n_segs].bbox.x1 = x_max; + svp->segs[n_segs].bbox.y0 = points[0].y; + svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; + n_segs++; + + n_points = 1; + n_points_max = 4; + points = art_new(ArtPoint, n_points_max); + points[0].x = x; + points[0].y = y; + x_min = x; + x_max = x; + } + + if (points != NULL) { + if (n_points == n_points_max) + art_expand(points, ArtPoint, n_points_max); + points[n_points].x = x = vpath[i].x; + points[n_points].y = y = vpath[i].y; + if (x < x_min) x_min = x; + else if (x > x_max) x_max = x; + n_points++; + } + dir = new_dir; + } + i++; + } + + if (points != NULL) { + if (n_points >= 2) { + if (n_segs == n_segs_max) { + n_segs_max <<= 1; + svp = (ArtSVP *)realloc(svp, sizeof(ArtSVP) + + (n_segs_max - 1) * + sizeof(ArtSVPSeg)); + } + svp->segs[n_segs].n_points = n_points; + svp->segs[n_segs].dir = (dir > 0); + if (dir < 0) + reverse_points(points, n_points); + svp->segs[n_segs].points = points; + svp->segs[n_segs].bbox.x0 = x_min; + svp->segs[n_segs].bbox.x1 = x_max; + svp->segs[n_segs].bbox.y0 = points[0].y; + svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; + n_segs++; + } else + free(points); + } + + svp->n_segs = n_segs; + + qsort(&svp->segs, n_segs, sizeof(ArtSVPSeg), art_svp_seg_compare); + + return svp; +} + + +/* Basic constructors and operations for bezier paths */ + +#define RENDER_LEVEL 4 +#define RENDER_SIZE (1 << (RENDER_LEVEL)) + +/** + * art_vpath_render_bez: Render a bezier segment into the vpath. + * @p_vpath: Where the pointer to the #ArtVpath structure is stored. + * @pn_points: Pointer to the number of points in *@p_vpath. + * @pn_points_max: Pointer to the number of points allocated. + * @x0: X coordinate of starting bezier point. + * @y0: Y coordinate of starting bezier point. + * @x1: X coordinate of first bezier control point. + * @y1: Y coordinate of first bezier control point. + * @x2: X coordinate of second bezier control point. + * @y2: Y coordinate of second bezier control point. + * @x3: X coordinate of ending bezier point. + * @y3: Y coordinate of ending bezier point. + * @flatness: Flatness control. + * + * Renders a bezier segment into the vector path, reallocating and + * updating *@p_vpath and *@pn_vpath_max as necessary. *@pn_vpath is + * incremented by the number of vector points added. + * + * This step includes (@x0, @y0) but not (@x3, @y3). + * + * The @flatness argument guides the amount of subdivision. The Adobe + * PostScript reference manual defines flatness as the maximum + * deviation between the any point on the vpath approximation and the + * corresponding point on the "true" curve, and we follow this + * definition here. A value of 0.25 should ensure high quality for aa + * rendering. +**/ +static void art_vpath_render_bez(ArtVpath **p_vpath, int *pn, int *pn_max, + double x0, double y0, + double x1, double y1, + double x2, double y2, + double x3, double y3, + double flatness) { + double x3_0, y3_0; + double z3_0_dot; + double z1_dot, z2_dot; + double z1_perp, z2_perp; + double max_perp_sq; + + double x_m, y_m; + double xa1, ya1; + double xa2, ya2; + double xb1, yb1; + double xb2, yb2; + + /* It's possible to optimize this routine a fair amount. + + First, once the _dot conditions are met, they will also be met in + all further subdivisions. So we might recurse to a different + routine that only checks the _perp conditions. + + Second, the distance _should_ decrease according to fairly + predictable rules (a factor of 4 with each subdivision). So it might + be possible to note that the distance is within a factor of 4 of + acceptable, and subdivide once. But proving this might be hard. + + Third, at the last subdivision, x_m and y_m can be computed more + expeditiously (as in the routine above). + + Finally, if we were able to subdivide by, say 2 or 3, this would + allow considerably finer-grain control, i.e. fewer points for the + same flatness tolerance. This would speed things up downstream. + + In any case, this routine is unlikely to be the bottleneck. It's + just that I have this undying quest for more speed... + + */ + + x3_0 = x3 - x0; + y3_0 = y3 - y0; + + /* z3_0_dot is dist z0-z3 squared */ + z3_0_dot = x3_0 * x3_0 + y3_0 * y3_0; + + if (z3_0_dot < 0.001) { + /* if start and end point are almost identical, the flatness tests + * don't work properly, so fall back on testing whether both of + * the other two control points are the same as the start point, + * too. + */ + if (hypot(x1 - x0, y1 - y0) < 0.001 + && hypot(x2 - x0, y2 - y0) < 0.001) + goto nosubdivide; + else + goto subdivide; + } + + /* we can avoid subdivision if: + + z1 has distance no more than flatness from the z0-z3 line + + z1 is no more z0'ward than flatness past z0-z3 + + z1 is more z0'ward than z3'ward on the line traversing z0-z3 + + and correspondingly for z2 */ + + /* perp is distance from line, multiplied by dist z0-z3 */ + max_perp_sq = flatness * flatness * z3_0_dot; + + z1_perp = (y1 - y0) * x3_0 - (x1 - x0) * y3_0; + if (z1_perp * z1_perp > max_perp_sq) + goto subdivide; + + z2_perp = (y3 - y2) * x3_0 - (x3 - x2) * y3_0; + if (z2_perp * z2_perp > max_perp_sq) + goto subdivide; + + z1_dot = (x1 - x0) * x3_0 + (y1 - y0) * y3_0; + if (z1_dot < 0 && z1_dot * z1_dot > max_perp_sq) + goto subdivide; + + z2_dot = (x3 - x2) * x3_0 + (y3 - y2) * y3_0; + if (z2_dot < 0 && z2_dot * z2_dot > max_perp_sq) + goto subdivide; + + if (z1_dot + z1_dot > z3_0_dot) + goto subdivide; + + if (z2_dot + z2_dot > z3_0_dot) + goto subdivide; + + +nosubdivide: + /* don't subdivide */ + art_vpath_add_point(p_vpath, pn, pn_max, + ART_LINETO, x3, y3); + return; + +subdivide: + + xa1 = (x0 + x1) * 0.5; + ya1 = (y0 + y1) * 0.5; + xa2 = (x0 + 2 * x1 + x2) * 0.25; + ya2 = (y0 + 2 * y1 + y2) * 0.25; + xb1 = (x1 + 2 * x2 + x3) * 0.25; + yb1 = (y1 + 2 * y2 + y3) * 0.25; + xb2 = (x2 + x3) * 0.5; + yb2 = (y2 + y3) * 0.5; + x_m = (xa2 + xb1) * 0.5; + y_m = (ya2 + yb1) * 0.5; + + art_vpath_render_bez(p_vpath, pn, pn_max, + x0, y0, xa1, ya1, xa2, ya2, x_m, y_m, flatness); + art_vpath_render_bez(p_vpath, pn, pn_max, + x_m, y_m, xb1, yb1, xb2, yb2, x3, y3, flatness); +} + +/** + * art_bez_path_to_vec: Create vpath from bezier path. + * @bez: Bezier path. + * @flatness: Flatness control. + * + * Creates a vector path closely approximating the bezier path defined by + * @bez. The @flatness argument controls the amount of subdivision. In + * general, the resulting vpath deviates by at most @flatness pixels + * from the "ideal" path described by @bez. + * + * Return value: Newly allocated vpath. + **/ +ArtVpath *art_bez_path_to_vec(const ArtBpath *bez, double flatness) { + ArtVpath *vec; + int vec_n, vec_n_max; + int bez_index; + double x, y; + + vec_n = 0; + vec_n_max = RENDER_SIZE; + vec = art_new(ArtVpath, vec_n_max); + + /* Initialization is unnecessary because of the precondition that the + bezier path does not begin with LINETO or CURVETO, but is here + to make the code warning-free. */ + x = 0; + y = 0; + + bez_index = 0; + do { + /* make sure space for at least one more code */ + if (vec_n >= vec_n_max) + art_expand(vec, ArtVpath, vec_n_max); + switch (bez[bez_index].code) { + case ART_MOVETO_OPEN: + case ART_MOVETO: + case ART_LINETO: + x = bez[bez_index].x3; + y = bez[bez_index].y3; + vec[vec_n].code = bez[bez_index].code; + vec[vec_n].x = x; + vec[vec_n].y = y; + vec_n++; + break; + case ART_END: + vec[vec_n].code = bez[bez_index].code; + vec[vec_n].x = 0; + vec[vec_n].y = 0; + vec_n++; + break; + case ART_CURVETO: + art_vpath_render_bez(&vec, &vec_n, &vec_n_max, + x, y, + bez[bez_index].x1, bez[bez_index].y1, + bez[bez_index].x2, bez[bez_index].y2, + bez[bez_index].x3, bez[bez_index].y3, + flatness); + x = bez[bez_index].x3; + y = bez[bez_index].y3; + break; + } + } while (bez[bez_index++].code != ART_END); + return vec; +} + + +#define EPSILON_6 1e-6 +#define EPSILON_2 1e-12 + +/* Render an arc segment starting at (xc + x0, yc + y0) to (xc + x1, + yc + y1), centered at (xc, yc), and with given radius. Both x0^2 + + y0^2 and x1^2 + y1^2 should be equal to radius^2. + + A positive value of radius means curve to the left, negative means + curve to the right. +*/ +static void art_svp_vpath_stroke_arc(ArtVpath **p_vpath, int *pn, int *pn_max, + double xc, double yc, + double x0, double y0, + double x1, double y1, + double radius, + double flatness) { + double theta; + double th_0, th_1; + int n_pts; + int i; + double aradius; + + aradius = fabs(radius); + theta = 2 * M_SQRT2 * sqrt(flatness / aradius); + th_0 = atan2(y0, x0); + th_1 = atan2(y1, x1); + if (radius > 0) { + /* curve to the left */ + if (th_0 < th_1) th_0 += M_PI * 2; + n_pts = ceil((th_0 - th_1) / theta); + } else { + /* curve to the right */ + if (th_1 < th_0) th_1 += M_PI * 2; + n_pts = ceil((th_1 - th_0) / theta); + } + art_vpath_add_point(p_vpath, pn, pn_max, + ART_LINETO, xc + x0, yc + y0); + for (i = 1; i < n_pts; i++) { + theta = th_0 + (th_1 - th_0) * i / n_pts; + art_vpath_add_point(p_vpath, pn, pn_max, + ART_LINETO, xc + cos(theta) * aradius, + yc + sin(theta) * aradius); + } + art_vpath_add_point(p_vpath, pn, pn_max, + ART_LINETO, xc + x1, yc + y1); +} + +/* Assume that forw and rev are at point i0. Bring them to i1, + joining with the vector i1 - i2. + + This used to be true, but isn't now that the stroke_raw code is + filtering out (near)zero length vectors: {It so happens that all + invocations of this function maintain the precondition i1 = i0 + 1, + so we could decrease the number of arguments by one. We haven't + done that here, though.} + + forw is to the line's right and rev is to its left. + + Precondition: no zero-length vectors, otherwise a divide by + zero will happen. */ +static void render_seg(ArtVpath **p_forw, int *pn_forw, int *pn_forw_max, + ArtVpath **p_rev, int *pn_rev, int *pn_rev_max, + ArtVpath *vpath, int i0, int i1, int i2, + ArtPathStrokeJoinType join, + double line_width, double miter_limit, double flatness) { + double dx0, dy0; + double dx1, dy1; + double dlx0, dly0; + double dlx1, dly1; + double dmx, dmy; + double dmr2; + double scale; + double cross; + + /* The vectors of the lines from i0 to i1 and i1 to i2. */ + dx0 = vpath[i1].x - vpath[i0].x; + dy0 = vpath[i1].y - vpath[i0].y; + + dx1 = vpath[i2].x - vpath[i1].x; + dy1 = vpath[i2].y - vpath[i1].y; + + /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise + 90 degrees, and scaled to the length of line_width. */ + scale = line_width / sqrt(dx0 * dx0 + dy0 * dy0); + dlx0 = dy0 * scale; + dly0 = -dx0 * scale; + + /* Set dl[xy]1 to the vector from i1 to i2, rotated counterclockwise + 90 degrees, and scaled to the length of line_width. */ + scale = line_width / sqrt(dx1 * dx1 + dy1 * dy1); + dlx1 = dy1 * scale; + dly1 = -dx1 * scale; + + /* now, forw's last point is expected to be colinear along d[xy]0 + to point i0 - dl[xy]0, and rev with i0 + dl[xy]0. */ + + /* positive for positive area (i.e. left turn) */ + cross = dx1 * dy0 - dx0 * dy1; + + dmx = (dlx0 + dlx1) * 0.5; + dmy = (dly0 + dly1) * 0.5; + dmr2 = dmx * dmx + dmy * dmy; + + if (join == ART_PATH_STROKE_JOIN_MITER && + dmr2 * miter_limit * miter_limit < line_width * line_width) + join = ART_PATH_STROKE_JOIN_BEVEL; + + /* the case when dmr2 is zero or very small bothers me + (i.e. near a 180 degree angle) + ALEX: So, we avoid the optimization when dmr2 is very small. This should + be safe since dmx/y is only used in optimization and in MITER case, and MITER + should be converted to BEVEL when dmr2 is very small. */ + if (dmr2 > EPSILON_2) { + scale = line_width * line_width / dmr2; + dmx *= scale; + dmy *= scale; + } + + if (cross *cross < EPSILON_2 && dx0 *dx1 + dy0 *dy1 >= 0) { + /* going straight */ + art_vpath_add_point(p_forw, pn_forw, pn_forw_max, + ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); + art_vpath_add_point(p_rev, pn_rev, pn_rev_max, + ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); + } else if (cross > 0) { + /* left turn, forw is outside and rev is inside */ + + if ( + (dmr2 > EPSILON_2) && + /* check that i1 + dm[xy] is inside i0-i1 rectangle */ + (dx0 + dmx) * dx0 + (dy0 + dmy) * dy0 > 0 && + /* and that i1 + dm[xy] is inside i1-i2 rectangle */ + ((dx1 - dmx) * dx1 + (dy1 - dmy) * dy1 > 0) +#ifdef PEDANTIC_INNER + && + /* check that i1 + dl[xy]1 is inside i0-i1 rectangle */ + (dx0 + dlx1) * dx0 + (dy0 + dly1) * dy0 > 0 && + /* and that i1 + dl[xy]0 is inside i1-i2 rectangle */ + ((dx1 - dlx0) * dx1 + (dy1 - dly0) * dy1 > 0) +#endif + ) { + /* can safely add single intersection point */ + art_vpath_add_point(p_rev, pn_rev, pn_rev_max, + ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy); + } else { + /* need to loop-de-loop the inside */ + art_vpath_add_point(p_rev, pn_rev, pn_rev_max, + ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); + art_vpath_add_point(p_rev, pn_rev, pn_rev_max, + ART_LINETO, vpath[i1].x, vpath[i1].y); + art_vpath_add_point(p_rev, pn_rev, pn_rev_max, + ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1); + } + + if (join == ART_PATH_STROKE_JOIN_BEVEL) { + /* bevel */ + art_vpath_add_point(p_forw, pn_forw, pn_forw_max, + ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); + art_vpath_add_point(p_forw, pn_forw, pn_forw_max, + ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1); + } else if (join == ART_PATH_STROKE_JOIN_MITER) { + art_vpath_add_point(p_forw, pn_forw, pn_forw_max, + ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy); + } else if (join == ART_PATH_STROKE_JOIN_ROUND) + art_svp_vpath_stroke_arc(p_forw, pn_forw, pn_forw_max, + vpath[i1].x, vpath[i1].y, + -dlx0, -dly0, + -dlx1, -dly1, + line_width, + flatness); + } else { + /* right turn, rev is outside and forw is inside */ + + if ( + (dmr2 > EPSILON_2) && + /* check that i1 - dm[xy] is inside i0-i1 rectangle */ + (dx0 - dmx) * dx0 + (dy0 - dmy) * dy0 > 0 && + /* and that i1 - dm[xy] is inside i1-i2 rectangle */ + ((dx1 + dmx) * dx1 + (dy1 + dmy) * dy1 > 0) +#ifdef PEDANTIC_INNER + && + /* check that i1 - dl[xy]1 is inside i0-i1 rectangle */ + (dx0 - dlx1) * dx0 + (dy0 - dly1) * dy0 > 0 && + /* and that i1 - dl[xy]0 is inside i1-i2 rectangle */ + ((dx1 + dlx0) * dx1 + (dy1 + dly0) * dy1 > 0) +#endif + ) { + /* can safely add single intersection point */ + art_vpath_add_point(p_forw, pn_forw, pn_forw_max, + ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy); + } else { + /* need to loop-de-loop the inside */ + art_vpath_add_point(p_forw, pn_forw, pn_forw_max, + ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); + art_vpath_add_point(p_forw, pn_forw, pn_forw_max, + ART_LINETO, vpath[i1].x, vpath[i1].y); + art_vpath_add_point(p_forw, pn_forw, pn_forw_max, + ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1); + } + + if (join == ART_PATH_STROKE_JOIN_BEVEL) { + /* bevel */ + art_vpath_add_point(p_rev, pn_rev, pn_rev_max, + ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); + art_vpath_add_point(p_rev, pn_rev, pn_rev_max, + ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1); + } else if (join == ART_PATH_STROKE_JOIN_MITER) { + art_vpath_add_point(p_rev, pn_rev, pn_rev_max, + ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy); + } else if (join == ART_PATH_STROKE_JOIN_ROUND) + art_svp_vpath_stroke_arc(p_rev, pn_rev, pn_rev_max, + vpath[i1].x, vpath[i1].y, + dlx0, dly0, + dlx1, dly1, + -line_width, + flatness); + + } +} + +/* caps i1, under the assumption of a vector from i0 */ +static void render_cap(ArtVpath **p_result, int *pn_result, int *pn_result_max, + ArtVpath *vpath, int i0, int i1, + ArtPathStrokeCapType cap, double line_width, double flatness) { + double dx0, dy0; + double dlx0, dly0; + double scale; + int n_pts; + int i; + + dx0 = vpath[i1].x - vpath[i0].x; + dy0 = vpath[i1].y - vpath[i0].y; + + /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise + 90 degrees, and scaled to the length of line_width. */ + scale = line_width / sqrt(dx0 * dx0 + dy0 * dy0); + dlx0 = dy0 * scale; + dly0 = -dx0 * scale; + + switch (cap) { + case ART_PATH_STROKE_CAP_BUTT: + art_vpath_add_point(p_result, pn_result, pn_result_max, + ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); + art_vpath_add_point(p_result, pn_result, pn_result_max, + ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); + break; + case ART_PATH_STROKE_CAP_ROUND: + n_pts = ceil(M_PI / (2.0 * M_SQRT2 * sqrt(flatness / line_width))); + art_vpath_add_point(p_result, pn_result, pn_result_max, + ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); + for (i = 1; i < n_pts; i++) { + double theta, c_th, s_th; + + theta = M_PI * i / n_pts; + c_th = cos(theta); + s_th = sin(theta); + art_vpath_add_point(p_result, pn_result, pn_result_max, + ART_LINETO, + vpath[i1].x - dlx0 * c_th - dly0 * s_th, + vpath[i1].y - dly0 * c_th + dlx0 * s_th); + } + art_vpath_add_point(p_result, pn_result, pn_result_max, + ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); + break; + case ART_PATH_STROKE_CAP_SQUARE: + art_vpath_add_point(p_result, pn_result, pn_result_max, + ART_LINETO, + vpath[i1].x - dlx0 - dly0, + vpath[i1].y - dly0 + dlx0); + art_vpath_add_point(p_result, pn_result, pn_result_max, + ART_LINETO, + vpath[i1].x + dlx0 - dly0, + vpath[i1].y + dly0 + dlx0); + break; + } +} + +/** + * art_svp_from_vpath_raw: Stroke a vector path, raw version + * @vpath: #ArtVPath to stroke. + * @join: Join style. + * @cap: Cap style. + * @line_width: Width of stroke. + * @miter_limit: Miter limit. + * @flatness: Flatness. + * + * Exactly the same as art_svp_vpath_stroke(), except that the resulting + * stroke outline may self-intersect and have regions of winding number + * greater than 1. + * + * Return value: Resulting raw stroked outline in svp format. + **/ +ArtVpath *art_svp_vpath_stroke_raw(ArtVpath *vpath, + ArtPathStrokeJoinType join, + ArtPathStrokeCapType cap, + double line_width, + double miter_limit, + double flatness) { + int begin_idx, end_idx; + int i; + ArtVpath *forw, *rev; + int n_forw, n_rev; + int n_forw_max, n_rev_max; + ArtVpath *result; + int n_result, n_result_max; + double half_lw = 0.5 * line_width; + int closed; + int last, this_, next, second; + double dx, dy; + + n_forw_max = 16; + forw = art_new(ArtVpath, n_forw_max); + + n_rev_max = 16; + rev = art_new(ArtVpath, n_rev_max); + + n_result = 0; + n_result_max = 16; + result = art_new(ArtVpath, n_result_max); + + for (begin_idx = 0; vpath[begin_idx].code != ART_END; begin_idx = end_idx) { + n_forw = 0; + n_rev = 0; + + closed = (vpath[begin_idx].code == ART_MOVETO); + + /* we don't know what the first point joins with until we get to the + last point and see if it's closed. So we start with the second + line in the path. + + Note: this is not strictly true (we now know it's closed from + the opening pathcode), but why fix code that isn't broken? + */ + + this_ = begin_idx; + /* skip over identical points at the beginning of the subpath */ + for (i = this_ + 1; vpath[i].code == ART_LINETO; i++) { + dx = vpath[i].x - vpath[this_].x; + dy = vpath[i].y - vpath[this_].y; + if (dx * dx + dy * dy > EPSILON_2) + break; + } + next = i; + second = next; + + /* invariant: this doesn't coincide with next */ + while (vpath[next].code == ART_LINETO) { + last = this_; + this_ = next; + /* skip over identical points after the beginning of the subpath */ + for (i = this_ + 1; vpath[i].code == ART_LINETO; i++) { + dx = vpath[i].x - vpath[this_].x; + dy = vpath[i].y - vpath[this_].y; + if (dx * dx + dy * dy > EPSILON_2) + break; + } + next = i; + if (vpath[next].code != ART_LINETO) { + /* reached end of path */ + /* make "closed" detection conform to PostScript + semantics (i.e. explicit closepath code rather than + just the fact that end of the path is the beginning) */ + if (closed && + vpath[this_].x == vpath[begin_idx].x && + vpath[this_].y == vpath[begin_idx].y) { + int j; + + /* path is closed, render join to beginning */ + render_seg(&forw, &n_forw, &n_forw_max, + &rev, &n_rev, &n_rev_max, + vpath, last, this_, second, + join, half_lw, miter_limit, flatness); + + /* do forward path */ + art_vpath_add_point(&result, &n_result, &n_result_max, + ART_MOVETO, forw[n_forw - 1].x, + forw[n_forw - 1].y); + for (j = 0; j < n_forw; j++) + art_vpath_add_point(&result, &n_result, &n_result_max, + ART_LINETO, forw[j].x, + forw[j].y); + + /* do reverse path, reversed */ + art_vpath_add_point(&result, &n_result, &n_result_max, + ART_MOVETO, rev[0].x, + rev[0].y); + for (j = n_rev - 1; j >= 0; j--) + art_vpath_add_point(&result, &n_result, &n_result_max, + ART_LINETO, rev[j].x, + rev[j].y); + } else { + /* path is open */ + int j; + + /* add to forw rather than result to ensure that + forw has at least one point. */ + render_cap(&forw, &n_forw, &n_forw_max, + vpath, last, this_, + cap, half_lw, flatness); + art_vpath_add_point(&result, &n_result, &n_result_max, + ART_MOVETO, forw[0].x, + forw[0].y); + for (j = 1; j < n_forw; j++) + art_vpath_add_point(&result, &n_result, &n_result_max, + ART_LINETO, forw[j].x, + forw[j].y); + for (j = n_rev - 1; j >= 0; j--) + art_vpath_add_point(&result, &n_result, &n_result_max, + ART_LINETO, rev[j].x, + rev[j].y); + render_cap(&result, &n_result, &n_result_max, + vpath, second, begin_idx, + cap, half_lw, flatness); + art_vpath_add_point(&result, &n_result, &n_result_max, + ART_LINETO, forw[0].x, + forw[0].y); + } + } else + render_seg(&forw, &n_forw, &n_forw_max, + &rev, &n_rev, &n_rev_max, + vpath, last, this_, next, + join, half_lw, miter_limit, flatness); + } + end_idx = next; + } + + free(forw); + free(rev); + art_vpath_add_point(&result, &n_result, &n_result_max, ART_END, 0, 0); + return result; +} + + +/* Render a vector path into a stroked outline. + + Status of this routine: + + Basic correctness: Only miter and bevel line joins are implemented, + and only butt line caps. Otherwise, seems to be fine. + + Numerical stability: We cheat (adding random perturbation). Thus, + it seems very likely that no numerical stability problems will be + seen in practice. + + Speed: Should be pretty good. + + Precision: The perturbation fuzzes the coordinates slightly, + but not enough to be visible. */ + +/** + * art_svp_vpath_stroke: Stroke a vector path. + * @vpath: #ArtVPath to stroke. + * @join: Join style. + * @cap: Cap style. + * @line_width: Width of stroke. + * @miter_limit: Miter limit. + * @flatness: Flatness. + * + * Computes an svp representing the stroked outline of @vpath. The + * width of the stroked line is @line_width. + * + * Lines are joined according to the @join rule. Possible values are + * ART_PATH_STROKE_JOIN_MITER (for mitered joins), + * ART_PATH_STROKE_JOIN_ROUND (for round joins), and + * ART_PATH_STROKE_JOIN_BEVEL (for bevelled joins). The mitered join + * is converted to a bevelled join if the miter would extend to a + * distance of more than @miter_limit * @line_width from the actual + * join point. + * + * If there are open subpaths, the ends of these subpaths are capped + * according to the @cap rule. Possible values are + * ART_PATH_STROKE_CAP_BUTT (squared cap, extends exactly to end + * point), ART_PATH_STROKE_CAP_ROUND (rounded half-circle centered at + * the end point), and ART_PATH_STROKE_CAP_SQUARE (squared cap, + * extending half @line_width past the end point). + * + * The @flatness parameter controls the accuracy of the rendering. It + * is most important for determining the number of points to use to + * approximate circular arcs for round lines and joins. In general, the + * resulting vector path will be within @flatness pixels of the "ideal" + * path containing actual circular arcs. I reserve the right to use + * the @flatness parameter to convert bevelled joins to miters for very + * small turn angles, as this would reduce the number of points in the + * resulting outline path. + * + * The resulting path is "clean" with respect to self-intersections, i.e. + * the winding number is 0 or 1 at each point. + * + * Return value: Resulting stroked outline in svp format. + **/ +ArtSVP *art_svp_vpath_stroke(ArtVpath *vpath, + ArtPathStrokeJoinType join, + ArtPathStrokeCapType cap, + double line_width, + double miter_limit, + double flatness) { + ArtVpath *vpath_stroke; + ArtSVP *svp, *svp2; + ArtSvpWriter *swr; + + vpath_stroke = art_svp_vpath_stroke_raw(vpath, join, cap, + line_width, miter_limit, flatness); + svp = art_svp_from_vpath(vpath_stroke); + free(vpath_stroke); + + swr = art_svp_writer_rewind_new(ART_WIND_RULE_NONZERO); + art_svp_intersector(svp, swr); + + svp2 = art_svp_writer_rewind_reap(swr); + art_svp_free(svp); + return svp2; +} + + +/* Testbed implementation of the new intersection code. +*/ + +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; +} + +/* 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; +} + +/* 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; + + 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; + + 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 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 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; + + 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); +} + + +/* The spiffy antialiased renderer for sorted vector paths. */ + +typedef double artfloat; + +struct _ArtSVPRenderAAIter { + const ArtSVP *svp; + int x0, x1; + int y; + int seg_ix; + + int *active_segs; + int n_active_segs; + int *cursor; + artfloat *seg_x; + artfloat *seg_dx; + + ArtSVPRenderAAStep *steps; +}; + +static void art_svp_render_insert_active(int i, int *active_segs, int n_active_segs, + artfloat *seg_x, artfloat *seg_dx) { + int j; + artfloat x; + int tmp1, tmp2; + + /* this is a cheap hack to get ^'s sorted correctly */ + x = seg_x[i] + 0.001 * seg_dx[i]; + for (j = 0; j < n_active_segs && seg_x[active_segs[j]] < x; j++); + + tmp1 = i; + while (j < n_active_segs) { + tmp2 = active_segs[j]; + active_segs[j] = tmp1; + tmp1 = tmp2; + j++; + } + active_segs[j] = tmp1; +} + +static void art_svp_render_delete_active(int *active_segs, int j, int n_active_segs) { + int k; + + for (k = j; k < n_active_segs; k++) + active_segs[k] = active_segs[k + 1]; +} + +/* Render the sorted vector path in the given rectangle, antialiased. + + This interface uses a callback for the actual pixel rendering. The + callback is called y1 - y0 times (once for each scan line). The y + coordinate is given as an argument for convenience (it could be + stored in the callback's private data and incremented on each + call). + + The rendered polygon is represented in a semi-runlength format: a + start value and a sequence of "steps". Each step has an x + coordinate and a value delta. The resulting value at position x is + equal to the sum of the start value and all step delta values for + which the step x coordinate is less than or equal to x. An + efficient algorithm will traverse the steps left to right, keeping + a running sum. + + All x coordinates in the steps are guaranteed to be x0 <= x < x1. + (This guarantee is a change from the gfonted vpaar renderer, and is + designed to simplify the callback). + + There is now a further guarantee that no two steps will have the + same x value. This may allow for further speedup and simplification + of renderers. + + The value 0x8000 represents 0% coverage by the polygon, while + 0xff8000 represents 100% coverage. This format is designed so that + >> 16 results in a standard 0x00..0xff value range, with nice + rounding. + + Status of this routine: + + Basic correctness: OK + + Numerical stability: pretty good, although probably not + bulletproof. + + Speed: Needs more aggressive culling of bounding boxes. Can + probably speed up the [x0,x1) clipping of step values. Can do more + of the step calculation in fixed point. + + Precision: No known problems, although it should be tested + thoroughly, especially for symmetry. + +*/ + +ArtSVPRenderAAIter *art_svp_render_aa_iter(const ArtSVP *svp, + int x0, int y0, int x1, int y1) { + ArtSVPRenderAAIter *iter = art_new(ArtSVPRenderAAIter, 1); + + iter->svp = svp; + iter->y = y0; + iter->x0 = x0; + iter->x1 = x1; + iter->seg_ix = 0; + + iter->active_segs = art_new(int, svp->n_segs); + iter->cursor = art_new(int, svp->n_segs); + iter->seg_x = art_new(artfloat, svp->n_segs); + iter->seg_dx = art_new(artfloat, svp->n_segs); + iter->steps = art_new(ArtSVPRenderAAStep, x1 - x0); + iter->n_active_segs = 0; + + return iter; +} + +#define ADD_STEP(xpos, xdelta) \ + /* stereotype code fragment for adding a step */ \ + if (n_steps == 0 || steps[n_steps - 1].x < xpos) \ + { \ + sx = n_steps; \ + steps[sx].x = xpos; \ + steps[sx].delta = xdelta; \ + n_steps++; \ + } \ + else \ + { \ + for (sx = n_steps; sx > 0; sx--) \ + { \ + if (steps[sx - 1].x == xpos) \ + { \ + steps[sx - 1].delta += xdelta; \ + sx = n_steps; \ + break; \ + } \ + else if (steps[sx - 1].x < xpos) \ + { \ + break; \ + } \ + } \ + if (sx < n_steps) \ + { \ + memmove (&steps[sx + 1], &steps[sx], \ + (n_steps - sx) * sizeof(steps[0])); \ + steps[sx].x = xpos; \ + steps[sx].delta = xdelta; \ + n_steps++; \ + } \ + } + +void art_svp_render_aa_iter_step(ArtSVPRenderAAIter *iter, int *p_start, + ArtSVPRenderAAStep **p_steps, int *p_n_steps) { + const ArtSVP *svp = iter->svp; + int *active_segs = iter->active_segs; + int n_active_segs = iter->n_active_segs; + int *cursor = iter->cursor; + artfloat *seg_x = iter->seg_x; + artfloat *seg_dx = iter->seg_dx; + int i = iter->seg_ix; + int j; + int x0 = iter->x0; + int x1 = iter->x1; + int y = iter->y; + int seg_index; + + int x; + ArtSVPRenderAAStep *steps = iter->steps; + int n_steps; + artfloat y_top, y_bot; + artfloat x_top, x_bot; + artfloat x_min, x_max; + int ix_min, ix_max; + artfloat delta; /* delta should be int too? */ + int last, this_; + int xdelta; + artfloat rslope, drslope; + int start; + const ArtSVPSeg *seg; + int curs; + artfloat dy; + + int sx; + + /* insert new active segments */ + for (; i < svp->n_segs && svp->segs[i].bbox.y0 < y + 1; i++) { + if (svp->segs[i].bbox.y1 > y && + svp->segs[i].bbox.x0 < x1) { + seg = &svp->segs[i]; + /* move cursor to topmost vector which overlaps [y,y+1) */ + for (curs = 0; seg->points[curs + 1].y < y; curs++); + cursor[i] = curs; + dy = seg->points[curs + 1].y - seg->points[curs].y; + if (fabs(dy) >= EPSILON_6) + seg_dx[i] = (seg->points[curs + 1].x - seg->points[curs].x) / + dy; + else + seg_dx[i] = 1e12; + seg_x[i] = seg->points[curs].x + + (y - seg->points[curs].y) * seg_dx[i]; + art_svp_render_insert_active(i, active_segs, n_active_segs++, + seg_x, seg_dx); + } + } + + n_steps = 0; + + /* render the runlengths, advancing and deleting as we go */ + start = 0x8000; + + for (j = 0; j < n_active_segs; j++) { + seg_index = active_segs[j]; + seg = &svp->segs[seg_index]; + curs = cursor[seg_index]; + while (curs != seg->n_points - 1 && + seg->points[curs].y < y + 1) { + y_top = y; + if (y_top < seg->points[curs].y) + y_top = seg->points[curs].y; + y_bot = y + 1; + if (y_bot > seg->points[curs + 1].y) + y_bot = seg->points[curs + 1].y; + if (y_top != y_bot) { + delta = (seg->dir ? 16711680.0 : -16711680.0) * + (y_bot - y_top); + x_top = seg_x[seg_index] + (y_top - y) * seg_dx[seg_index]; + x_bot = seg_x[seg_index] + (y_bot - y) * seg_dx[seg_index]; + if (x_top < x_bot) { + x_min = x_top; + x_max = x_bot; + } else { + x_min = x_bot; + x_max = x_top; + } + ix_min = (int)floor(x_min); + ix_max = (int)floor(x_max); + if (ix_min >= x1) { + /* skip; it starts to the right of the render region */ + } else if (ix_max < x0) + /* it ends to the left of the render region */ + start += (int)delta; + else if (ix_min == ix_max) { + /* case 1, antialias a single pixel */ + xdelta = (ix_min + 1 - (x_min + x_max) * 0.5) * delta; + + ADD_STEP(ix_min, xdelta) + + if (ix_min + 1 < x1) { + xdelta = delta - xdelta; + + ADD_STEP(ix_min + 1, xdelta) + } + } else { + /* case 2, antialias a run */ + rslope = 1.0 / fabs(seg_dx[seg_index]); + drslope = delta * rslope; + last = + drslope * 0.5 * + (ix_min + 1 - x_min) * (ix_min + 1 - x_min); + xdelta = last; + if (ix_min >= x0) { + ADD_STEP(ix_min, xdelta) + + x = ix_min + 1; + } else { + start += last; + x = x0; + } + if (ix_max > x1) + ix_max = x1; + for (; x < ix_max; x++) { + this_ = (seg->dir ? 16711680.0 : -16711680.0) * rslope * + (x + 0.5 - x_min); + xdelta = this_ - last; + last = this_; + + ADD_STEP(x, xdelta) + } + if (x < x1) { + this_ = + delta * (1 - 0.5 * + (x_max - ix_max) * (x_max - ix_max) * + rslope); + xdelta = this_ - last; + last = this_; + + ADD_STEP(x, xdelta) + + if (x + 1 < x1) { + xdelta = delta - last; + + ADD_STEP(x + 1, xdelta) + } + } + } + } + curs++; + if (curs != seg->n_points - 1 && + seg->points[curs].y < y + 1) { + dy = seg->points[curs + 1].y - seg->points[curs].y; + if (fabs(dy) >= EPSILON_6) + seg_dx[seg_index] = (seg->points[curs + 1].x - + seg->points[curs].x) / dy; + else + seg_dx[seg_index] = 1e12; + seg_x[seg_index] = seg->points[curs].x + + (y - seg->points[curs].y) * seg_dx[seg_index]; + } + /* break here, instead of duplicating predicate in while? */ + } + if (seg->points[curs].y >= y + 1) { + curs--; + cursor[seg_index] = curs; + seg_x[seg_index] += seg_dx[seg_index]; + } else { + art_svp_render_delete_active(active_segs, j--, + --n_active_segs); + } + } + + *p_start = start; + *p_steps = steps; + *p_n_steps = n_steps; + + iter->seg_ix = i; + iter->n_active_segs = n_active_segs; + iter->y++; +} + +void art_svp_render_aa_iter_done(ArtSVPRenderAAIter *iter) { + free(iter->steps); + + free(iter->seg_dx); + free(iter->seg_x); + free(iter->cursor); + free(iter->active_segs); + free(iter); +} + +/** + * art_svp_render_aa: Render SVP antialiased. + * @svp: The #ArtSVP to render. + * @x0: Left coordinate of destination rectangle. + * @y0: Top coordinate of destination rectangle. + * @x1: Right coordinate of destination rectangle. + * @y1: Bottom coordinate of destination rectangle. + * @callback: The callback which actually paints the pixels. + * @callback_data: Private data for @callback. + * + * Renders the sorted vector path in the given rectangle, antialiased. + * + * This interface uses a callback for the actual pixel rendering. The + * callback is called @y1 - @y0 times (once for each scan line). The y + * coordinate is given as an argument for convenience (it could be + * stored in the callback's private data and incremented on each + * call). + * + * The rendered polygon is represented in a semi-runlength format: a + * start value and a sequence of "steps". Each step has an x + * coordinate and a value delta. The resulting value at position x is + * equal to the sum of the start value and all step delta values for + * which the step x coordinate is less than or equal to x. An + * efficient algorithm will traverse the steps left to right, keeping + * a running sum. + * + * All x coordinates in the steps are guaranteed to be @x0 <= x < @x1. + * (This guarantee is a change from the gfonted vpaar renderer from + * which this routine is derived, and is designed to simplify the + * callback). + * + * The value 0x8000 represents 0% coverage by the polygon, while + * 0xff8000 represents 100% coverage. This format is designed so that + * >> 16 results in a standard 0x00..0xff value range, with nice + * rounding. + * + **/ +void art_svp_render_aa(const ArtSVP *svp, + int x0, int y0, int x1, int y1, + void (*callback)(void *callback_data, + int y, + int start, + ArtSVPRenderAAStep *steps, int n_steps), + void *callback_data) { + ArtSVPRenderAAIter *iter; + int y; + int start; + ArtSVPRenderAAStep *steps; + int n_steps; + + iter = art_svp_render_aa_iter(svp, x0, y0, x1, y1); + + + for (y = y0; y < y1; y++) { + art_svp_render_aa_iter_step(iter, &start, &steps, &n_steps); + (*callback)(callback_data, y, start, steps, n_steps); + } + + art_svp_render_aa_iter_done(iter); +} diff --git a/engines/sword25/gfx/image/art.h b/engines/sword25/gfx/image/art.h index 5888814e77..f0d0d7cacc 100644 --- a/engines/sword25/gfx/image/art.h +++ b/engines/sword25/gfx/image/art.h @@ -86,8 +86,6 @@ art_die(const char *fmt, ...) ART_GNUC_PRINTF(1, 2); void art_warn(const char *fmt, ...) ART_GNUC_PRINTF(1, 2); -#define ART_USE_NEW_INTERSECTOR - typedef struct _ArtDRect ArtDRect; typedef struct _ArtIRect ArtIRect; @@ -173,4 +171,106 @@ art_vpath_add_point(ArtVpath **p_vpath, int *pn_points, int *pn_points_max, ArtVpath *art_bez_path_to_vec(const ArtBpath *bez, double flatness); +/* The funky new SVP intersector. */ + +#ifndef ART_WIND_RULE_DEFINED +#define ART_WIND_RULE_DEFINED +typedef enum { + ART_WIND_RULE_NONZERO, + ART_WIND_RULE_INTERSECT, + ART_WIND_RULE_ODDEVEN, + ART_WIND_RULE_POSITIVE +} ArtWindRule; +#endif + +typedef struct _ArtSvpWriter ArtSvpWriter; + +struct _ArtSvpWriter { + int (*add_segment)(ArtSvpWriter *self, int wind_left, int delta_wind, + double x, double y); + void (*add_point)(ArtSvpWriter *self, int seg_id, double x, double y); + void (*close_segment)(ArtSvpWriter *self, int seg_id); +}; + +ArtSvpWriter * +art_svp_writer_rewind_new(ArtWindRule rule); + +ArtSVP * +art_svp_writer_rewind_reap(ArtSvpWriter *self); + +int +art_svp_seg_compare(const void *s1, const void *s2); + +void +art_svp_intersector(const ArtSVP *in, ArtSvpWriter *out); + + +/* Sort vector paths into sorted vector paths. */ + +ArtSVP * +art_svp_from_vpath(ArtVpath *vpath); + +/* Sort vector paths into sorted vector paths. */ + +typedef enum { + ART_PATH_STROKE_JOIN_MITER, + ART_PATH_STROKE_JOIN_ROUND, + ART_PATH_STROKE_JOIN_BEVEL +} ArtPathStrokeJoinType; + +typedef enum { + ART_PATH_STROKE_CAP_BUTT, + ART_PATH_STROKE_CAP_ROUND, + ART_PATH_STROKE_CAP_SQUARE +} ArtPathStrokeCapType; + +ArtSVP * +art_svp_vpath_stroke(ArtVpath *vpath, + ArtPathStrokeJoinType join, + ArtPathStrokeCapType cap, + double line_width, + double miter_limit, + double flatness); + +/* This version may have winding numbers exceeding 1. */ +ArtVpath * +art_svp_vpath_stroke_raw(ArtVpath *vpath, + ArtPathStrokeJoinType join, + ArtPathStrokeCapType cap, + double line_width, + double miter_limit, + double flatness); + + +/* The spiffy antialiased renderer for sorted vector paths. */ + +typedef struct _ArtSVPRenderAAStep ArtSVPRenderAAStep; +typedef struct _ArtSVPRenderAAIter ArtSVPRenderAAIter; + +struct _ArtSVPRenderAAStep { + int x; + int delta; /* stored with 16 fractional bits */ +}; + +ArtSVPRenderAAIter * +art_svp_render_aa_iter(const ArtSVP *svp, + int x0, int y0, int x1, int y1); + +void +art_svp_render_aa_iter_step(ArtSVPRenderAAIter *iter, int *p_start, + ArtSVPRenderAAStep **p_steps, int *p_n_steps); + +void +art_svp_render_aa_iter_done(ArtSVPRenderAAIter *iter); + +void +art_svp_render_aa(const ArtSVP *svp, + int x0, int y0, int x1, int y1, + void (*callback)(void *callback_data, + int y, + int start, + ArtSVPRenderAAStep *steps, int n_steps), + void *callback_data); + + #endif /* __ART_MISC_H__ */ diff --git a/engines/sword25/gfx/image/art_svp_intersect.cpp b/engines/sword25/gfx/image/art_svp_intersect.cpp deleted file mode 100644 index db0b5643d4..0000000000 --- a/engines/sword25/gfx/image/art_svp_intersect.cpp +++ /dev/null @@ -1,1344 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program 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 General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -/* - * This code is based on Libart_LGPL - library of basic graphic primitives - * - * Copyright (c) 1998 Raph Levien - * - * Licensed under GNU LGPL v2 - * - */ - -/* 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); -} diff --git a/engines/sword25/gfx/image/art_svp_intersect.h b/engines/sword25/gfx/image/art_svp_intersect.h deleted file mode 100644 index 9db21aacff..0000000000 --- a/engines/sword25/gfx/image/art_svp_intersect.h +++ /dev/null @@ -1,73 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program 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 General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -/* - * This code is based on Libart_LGPL - library of basic graphic primitives - * - * Copyright (c) 1998 Raph Levien - * - * Licensed under GNU LGPL v2 - * - */ - -#ifndef __ART_SVP_INTERSECT_H__ -#define __ART_SVP_INTERSECT_H__ - -/* The funky new SVP intersector. */ - -#include "art.h" - -#ifndef ART_WIND_RULE_DEFINED -#define ART_WIND_RULE_DEFINED -typedef enum { - ART_WIND_RULE_NONZERO, - ART_WIND_RULE_INTERSECT, - ART_WIND_RULE_ODDEVEN, - ART_WIND_RULE_POSITIVE -} ArtWindRule; -#endif - -typedef struct _ArtSvpWriter ArtSvpWriter; - -struct _ArtSvpWriter { - int (*add_segment)(ArtSvpWriter *self, int wind_left, int delta_wind, - double x, double y); - void (*add_point)(ArtSvpWriter *self, int seg_id, double x, double y); - void (*close_segment)(ArtSvpWriter *self, int seg_id); -}; - -ArtSvpWriter * -art_svp_writer_rewind_new(ArtWindRule rule); - -ArtSVP * -art_svp_writer_rewind_reap(ArtSvpWriter *self); - -int -art_svp_seg_compare(const void *s1, const void *s2); - -void -art_svp_intersector(const ArtSVP *in, ArtSvpWriter *out); - -#endif /* __ART_SVP_INTERSECT_H__ */ diff --git a/engines/sword25/gfx/image/art_svp_render_aa.cpp b/engines/sword25/gfx/image/art_svp_render_aa.cpp deleted file mode 100644 index da8377ae86..0000000000 --- a/engines/sword25/gfx/image/art_svp_render_aa.cpp +++ /dev/null @@ -1,443 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program 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 General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -/* - * This code is based on Libart_LGPL - library of basic graphic primitives - * - * Copyright (c) 1998 Raph Levien - * - * Licensed under GNU LGPL v2 - * - */ - -/* The spiffy antialiased renderer for sorted vector paths. */ - -#include "art.h" -#include "art_svp_render_aa.h" - -#include <math.h> -#include <string.h> /* for memmove */ - -#include <stdio.h> - -typedef double artfloat; - -struct _ArtSVPRenderAAIter { - const ArtSVP *svp; - int x0, x1; - int y; - int seg_ix; - - int *active_segs; - int n_active_segs; - int *cursor; - artfloat *seg_x; - artfloat *seg_dx; - - ArtSVPRenderAAStep *steps; -}; - -static void -art_svp_render_insert_active(int i, int *active_segs, int n_active_segs, - artfloat *seg_x, artfloat *seg_dx) { - int j; - artfloat x; - int tmp1, tmp2; - - /* this is a cheap hack to get ^'s sorted correctly */ - x = seg_x[i] + 0.001 * seg_dx[i]; - for (j = 0; j < n_active_segs && seg_x[active_segs[j]] < x; j++); - - tmp1 = i; - while (j < n_active_segs) { - tmp2 = active_segs[j]; - active_segs[j] = tmp1; - tmp1 = tmp2; - j++; - } - active_segs[j] = tmp1; -} - -static void -art_svp_render_delete_active(int *active_segs, int j, int n_active_segs) { - int k; - - for (k = j; k < n_active_segs; k++) - active_segs[k] = active_segs[k + 1]; -} - -#define EPSILON 1e-6 - -/* Render the sorted vector path in the given rectangle, antialiased. - - This interface uses a callback for the actual pixel rendering. The - callback is called y1 - y0 times (once for each scan line). The y - coordinate is given as an argument for convenience (it could be - stored in the callback's private data and incremented on each - call). - - The rendered polygon is represented in a semi-runlength format: a - start value and a sequence of "steps". Each step has an x - coordinate and a value delta. The resulting value at position x is - equal to the sum of the start value and all step delta values for - which the step x coordinate is less than or equal to x. An - efficient algorithm will traverse the steps left to right, keeping - a running sum. - - All x coordinates in the steps are guaranteed to be x0 <= x < x1. - (This guarantee is a change from the gfonted vpaar renderer, and is - designed to simplify the callback). - - There is now a further guarantee that no two steps will have the - same x value. This may allow for further speedup and simplification - of renderers. - - The value 0x8000 represents 0% coverage by the polygon, while - 0xff8000 represents 100% coverage. This format is designed so that - >> 16 results in a standard 0x00..0xff value range, with nice - rounding. - - Status of this routine: - - Basic correctness: OK - - Numerical stability: pretty good, although probably not - bulletproof. - - Speed: Needs more aggressive culling of bounding boxes. Can - probably speed up the [x0,x1) clipping of step values. Can do more - of the step calculation in fixed point. - - Precision: No known problems, although it should be tested - thoroughly, especially for symmetry. - -*/ - -ArtSVPRenderAAIter * -art_svp_render_aa_iter(const ArtSVP *svp, - int x0, int y0, int x1, int y1) { - ArtSVPRenderAAIter *iter = art_new(ArtSVPRenderAAIter, 1); - - iter->svp = svp; - iter->y = y0; - iter->x0 = x0; - iter->x1 = x1; - iter->seg_ix = 0; - - iter->active_segs = art_new(int, svp->n_segs); - iter->cursor = art_new(int, svp->n_segs); - iter->seg_x = art_new(artfloat, svp->n_segs); - iter->seg_dx = art_new(artfloat, svp->n_segs); - iter->steps = art_new(ArtSVPRenderAAStep, x1 - x0); - iter->n_active_segs = 0; - - return iter; -} - -#define ADD_STEP(xpos, xdelta) \ - /* stereotype code fragment for adding a step */ \ - if (n_steps == 0 || steps[n_steps - 1].x < xpos) \ - { \ - sx = n_steps; \ - steps[sx].x = xpos; \ - steps[sx].delta = xdelta; \ - n_steps++; \ - } \ - else \ - { \ - for (sx = n_steps; sx > 0; sx--) \ - { \ - if (steps[sx - 1].x == xpos) \ - { \ - steps[sx - 1].delta += xdelta; \ - sx = n_steps; \ - break; \ - } \ - else if (steps[sx - 1].x < xpos) \ - { \ - break; \ - } \ - } \ - if (sx < n_steps) \ - { \ - memmove (&steps[sx + 1], &steps[sx], \ - (n_steps - sx) * sizeof(steps[0])); \ - steps[sx].x = xpos; \ - steps[sx].delta = xdelta; \ - n_steps++; \ - } \ - } - -void -art_svp_render_aa_iter_step(ArtSVPRenderAAIter *iter, int *p_start, - ArtSVPRenderAAStep **p_steps, int *p_n_steps) { - const ArtSVP *svp = iter->svp; - int *active_segs = iter->active_segs; - int n_active_segs = iter->n_active_segs; - int *cursor = iter->cursor; - artfloat *seg_x = iter->seg_x; - artfloat *seg_dx = iter->seg_dx; - int i = iter->seg_ix; - int j; - int x0 = iter->x0; - int x1 = iter->x1; - int y = iter->y; - int seg_index; - - int x; - ArtSVPRenderAAStep *steps = iter->steps; - int n_steps; - artfloat y_top, y_bot; - artfloat x_top, x_bot; - artfloat x_min, x_max; - int ix_min, ix_max; - artfloat delta; /* delta should be int too? */ - int last, this_; - int xdelta; - artfloat rslope, drslope; - int start; - const ArtSVPSeg *seg; - int curs; - artfloat dy; - - int sx; - - /* insert new active segments */ - for (; i < svp->n_segs && svp->segs[i].bbox.y0 < y + 1; i++) { - if (svp->segs[i].bbox.y1 > y && - svp->segs[i].bbox.x0 < x1) { - seg = &svp->segs[i]; - /* move cursor to topmost vector which overlaps [y,y+1) */ - for (curs = 0; seg->points[curs + 1].y < y; curs++); - cursor[i] = curs; - dy = seg->points[curs + 1].y - seg->points[curs].y; - if (fabs(dy) >= EPSILON) - seg_dx[i] = (seg->points[curs + 1].x - seg->points[curs].x) / - dy; - else - seg_dx[i] = 1e12; - seg_x[i] = seg->points[curs].x + - (y - seg->points[curs].y) * seg_dx[i]; - art_svp_render_insert_active(i, active_segs, n_active_segs++, - seg_x, seg_dx); - } - } - - n_steps = 0; - - /* render the runlengths, advancing and deleting as we go */ - start = 0x8000; - - for (j = 0; j < n_active_segs; j++) { - seg_index = active_segs[j]; - seg = &svp->segs[seg_index]; - curs = cursor[seg_index]; - while (curs != seg->n_points - 1 && - seg->points[curs].y < y + 1) { - y_top = y; - if (y_top < seg->points[curs].y) - y_top = seg->points[curs].y; - y_bot = y + 1; - if (y_bot > seg->points[curs + 1].y) - y_bot = seg->points[curs + 1].y; - if (y_top != y_bot) { - delta = (seg->dir ? 16711680.0 : -16711680.0) * - (y_bot - y_top); - x_top = seg_x[seg_index] + (y_top - y) * seg_dx[seg_index]; - x_bot = seg_x[seg_index] + (y_bot - y) * seg_dx[seg_index]; - if (x_top < x_bot) { - x_min = x_top; - x_max = x_bot; - } else { - x_min = x_bot; - x_max = x_top; - } - ix_min = (int)floor(x_min); - ix_max = (int)floor(x_max); - if (ix_min >= x1) { - /* skip; it starts to the right of the render region */ - } else if (ix_max < x0) - /* it ends to the left of the render region */ - start += (int)delta; - else if (ix_min == ix_max) { - /* case 1, antialias a single pixel */ - xdelta = (ix_min + 1 - (x_min + x_max) * 0.5) * delta; - - ADD_STEP(ix_min, xdelta) - - if (ix_min + 1 < x1) { - xdelta = delta - xdelta; - - ADD_STEP(ix_min + 1, xdelta) - } - } else { - /* case 2, antialias a run */ - rslope = 1.0 / fabs(seg_dx[seg_index]); - drslope = delta * rslope; - last = - drslope * 0.5 * - (ix_min + 1 - x_min) * (ix_min + 1 - x_min); - xdelta = last; - if (ix_min >= x0) { - ADD_STEP(ix_min, xdelta) - - x = ix_min + 1; - } else { - start += last; - x = x0; - } - if (ix_max > x1) - ix_max = x1; - for (; x < ix_max; x++) { - this_ = (seg->dir ? 16711680.0 : -16711680.0) * rslope * - (x + 0.5 - x_min); - xdelta = this_ - last; - last = this_; - - ADD_STEP(x, xdelta) - } - if (x < x1) { - this_ = - delta * (1 - 0.5 * - (x_max - ix_max) * (x_max - ix_max) * - rslope); - xdelta = this_ - last; - last = this_; - - ADD_STEP(x, xdelta) - - if (x + 1 < x1) { - xdelta = delta - last; - - ADD_STEP(x + 1, xdelta) - } - } - } - } - curs++; - if (curs != seg->n_points - 1 && - seg->points[curs].y < y + 1) { - dy = seg->points[curs + 1].y - seg->points[curs].y; - if (fabs(dy) >= EPSILON) - seg_dx[seg_index] = (seg->points[curs + 1].x - - seg->points[curs].x) / dy; - else - seg_dx[seg_index] = 1e12; - seg_x[seg_index] = seg->points[curs].x + - (y - seg->points[curs].y) * seg_dx[seg_index]; - } - /* break here, instead of duplicating predicate in while? */ - } - if (seg->points[curs].y >= y + 1) { - curs--; - cursor[seg_index] = curs; - seg_x[seg_index] += seg_dx[seg_index]; - } else { - art_svp_render_delete_active(active_segs, j--, - --n_active_segs); - } - } - - *p_start = start; - *p_steps = steps; - *p_n_steps = n_steps; - - iter->seg_ix = i; - iter->n_active_segs = n_active_segs; - iter->y++; -} - -void -art_svp_render_aa_iter_done(ArtSVPRenderAAIter *iter) { - free(iter->steps); - - free(iter->seg_dx); - free(iter->seg_x); - free(iter->cursor); - free(iter->active_segs); - free(iter); -} - -/** - * art_svp_render_aa: Render SVP antialiased. - * @svp: The #ArtSVP to render. - * @x0: Left coordinate of destination rectangle. - * @y0: Top coordinate of destination rectangle. - * @x1: Right coordinate of destination rectangle. - * @y1: Bottom coordinate of destination rectangle. - * @callback: The callback which actually paints the pixels. - * @callback_data: Private data for @callback. - * - * Renders the sorted vector path in the given rectangle, antialiased. - * - * This interface uses a callback for the actual pixel rendering. The - * callback is called @y1 - @y0 times (once for each scan line). The y - * coordinate is given as an argument for convenience (it could be - * stored in the callback's private data and incremented on each - * call). - * - * The rendered polygon is represented in a semi-runlength format: a - * start value and a sequence of "steps". Each step has an x - * coordinate and a value delta. The resulting value at position x is - * equal to the sum of the start value and all step delta values for - * which the step x coordinate is less than or equal to x. An - * efficient algorithm will traverse the steps left to right, keeping - * a running sum. - * - * All x coordinates in the steps are guaranteed to be @x0 <= x < @x1. - * (This guarantee is a change from the gfonted vpaar renderer from - * which this routine is derived, and is designed to simplify the - * callback). - * - * The value 0x8000 represents 0% coverage by the polygon, while - * 0xff8000 represents 100% coverage. This format is designed so that - * >> 16 results in a standard 0x00..0xff value range, with nice - * rounding. - * - **/ -void -art_svp_render_aa(const ArtSVP *svp, - int x0, int y0, int x1, int y1, - void (*callback)(void *callback_data, - int y, - int start, - ArtSVPRenderAAStep *steps, int n_steps), - void *callback_data) { - ArtSVPRenderAAIter *iter; - int y; - int start; - ArtSVPRenderAAStep *steps; - int n_steps; - - iter = art_svp_render_aa_iter(svp, x0, y0, x1, y1); - - - for (y = y0; y < y1; y++) { - art_svp_render_aa_iter_step(iter, &start, &steps, &n_steps); - (*callback)(callback_data, y, start, steps, n_steps); - } - - art_svp_render_aa_iter_done(iter); -} diff --git a/engines/sword25/gfx/image/art_svp_render_aa.h b/engines/sword25/gfx/image/art_svp_render_aa.h deleted file mode 100644 index 24bf2bb292..0000000000 --- a/engines/sword25/gfx/image/art_svp_render_aa.h +++ /dev/null @@ -1,70 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program 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 General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -/* - * This code is based on Libart_LGPL - library of basic graphic primitives - * - * Copyright (c) 1998 Raph Levien - * - * Licensed under GNU LGPL v2 - * - */ - -#ifndef __ART_SVP_RENDER_AA_H__ -#define __ART_SVP_RENDER_AA_H__ - -/* The spiffy antialiased renderer for sorted vector paths. */ - -#include "art.h" - -typedef struct _ArtSVPRenderAAStep ArtSVPRenderAAStep; -typedef struct _ArtSVPRenderAAIter ArtSVPRenderAAIter; - -struct _ArtSVPRenderAAStep { - int x; - int delta; /* stored with 16 fractional bits */ -}; - -ArtSVPRenderAAIter * -art_svp_render_aa_iter(const ArtSVP *svp, - int x0, int y0, int x1, int y1); - -void -art_svp_render_aa_iter_step(ArtSVPRenderAAIter *iter, int *p_start, - ArtSVPRenderAAStep **p_steps, int *p_n_steps); - -void -art_svp_render_aa_iter_done(ArtSVPRenderAAIter *iter); - -void -art_svp_render_aa(const ArtSVP *svp, - int x0, int y0, int x1, int y1, - void (*callback)(void *callback_data, - int y, - int start, - ArtSVPRenderAAStep *steps, int n_steps), - void *callback_data); - -#endif /* __ART_SVP_RENDER_AA_H__ */ diff --git a/engines/sword25/gfx/image/art_svp_vpath.cpp b/engines/sword25/gfx/image/art_svp_vpath.cpp deleted file mode 100644 index 63ca259fe3..0000000000 --- a/engines/sword25/gfx/image/art_svp_vpath.cpp +++ /dev/null @@ -1,207 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program 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 General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -/* - * This code is based on Libart_LGPL - library of basic graphic primitives - * - * Copyright (c) 1998 Raph Levien - * - * Licensed under GNU LGPL v2 - * - */ - -/* Sort vector paths into sorted vector paths */ - -#include "art.h" - -#include <stdlib.h> -#include <math.h> - -/* reverse a list of points in place */ -static void -reverse_points(ArtPoint *points, int n_points) { - int i; - ArtPoint tmp_p; - - for (i = 0; i < (n_points >> 1); i++) { - tmp_p = points[i]; - points[i] = points[n_points - (i + 1)]; - points[n_points - (i + 1)] = tmp_p; - } -} - -/** - * art_svp_from_vpath: Convert a vpath to a sorted vector path. - * @vpath: #ArtVPath to convert. - * - * Converts a vector path into sorted vector path form. The svp form is - * more efficient for rendering and other vector operations. - * - * Basically, the implementation is to traverse the vector path, - * generating a new segment for each "run" of points in the vector - * path with monotonically increasing Y values. All the resulting - * values are then sorted. - * - * Note: I'm not sure that the sorting rule is correct with respect - * to numerical stability issues. - * - * Return value: Resulting sorted vector path. - **/ -ArtSVP * -art_svp_from_vpath(ArtVpath *vpath) { - int n_segs, n_segs_max; - ArtSVP *svp; - int dir; - int new_dir; - int i; - ArtPoint *points; - int n_points, n_points_max; - double x, y; - double x_min, x_max; - - n_segs = 0; - n_segs_max = 16; - svp = (ArtSVP *)malloc(sizeof(ArtSVP) + - (n_segs_max - 1) * sizeof(ArtSVPSeg)); - - dir = 0; - n_points = 0; - n_points_max = 0; - points = NULL; - i = 0; - - x = y = 0; /* unnecessary, given "first code must not be LINETO" invariant, - but it makes gcc -Wall -ansi -pedantic happier */ - x_min = x_max = 0; /* same */ - - while (vpath[i].code != ART_END) { - if (vpath[i].code == ART_MOVETO || vpath[i].code == ART_MOVETO_OPEN) { - if (points != NULL && n_points >= 2) { - if (n_segs == n_segs_max) { - n_segs_max <<= 1; - svp = (ArtSVP *)realloc(svp, sizeof(ArtSVP) + - (n_segs_max - 1) * - sizeof(ArtSVPSeg)); - } - svp->segs[n_segs].n_points = n_points; - svp->segs[n_segs].dir = (dir > 0); - if (dir < 0) - reverse_points(points, n_points); - svp->segs[n_segs].points = points; - svp->segs[n_segs].bbox.x0 = x_min; - svp->segs[n_segs].bbox.x1 = x_max; - svp->segs[n_segs].bbox.y0 = points[0].y; - svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; - n_segs++; - points = NULL; - } - - if (points == NULL) { - n_points_max = 4; - points = art_new(ArtPoint, n_points_max); - } - - n_points = 1; - points[0].x = x = vpath[i].x; - points[0].y = y = vpath[i].y; - x_min = x; - x_max = x; - dir = 0; - } else { /* must be LINETO */ - new_dir = (vpath[i].y > y || - (vpath[i].y == y && vpath[i].x > x)) ? 1 : -1; - if (dir && dir != new_dir) { - /* new segment */ - x = points[n_points - 1].x; - y = points[n_points - 1].y; - if (n_segs == n_segs_max) { - n_segs_max <<= 1; - svp = (ArtSVP *)realloc(svp, sizeof(ArtSVP) + - (n_segs_max - 1) * - sizeof(ArtSVPSeg)); - } - svp->segs[n_segs].n_points = n_points; - svp->segs[n_segs].dir = (dir > 0); - if (dir < 0) - reverse_points(points, n_points); - svp->segs[n_segs].points = points; - svp->segs[n_segs].bbox.x0 = x_min; - svp->segs[n_segs].bbox.x1 = x_max; - svp->segs[n_segs].bbox.y0 = points[0].y; - svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; - n_segs++; - - n_points = 1; - n_points_max = 4; - points = art_new(ArtPoint, n_points_max); - points[0].x = x; - points[0].y = y; - x_min = x; - x_max = x; - } - - if (points != NULL) { - if (n_points == n_points_max) - art_expand(points, ArtPoint, n_points_max); - points[n_points].x = x = vpath[i].x; - points[n_points].y = y = vpath[i].y; - if (x < x_min) x_min = x; - else if (x > x_max) x_max = x; - n_points++; - } - dir = new_dir; - } - i++; - } - - if (points != NULL) { - if (n_points >= 2) { - if (n_segs == n_segs_max) { - n_segs_max <<= 1; - svp = (ArtSVP *)realloc(svp, sizeof(ArtSVP) + - (n_segs_max - 1) * - sizeof(ArtSVPSeg)); - } - svp->segs[n_segs].n_points = n_points; - svp->segs[n_segs].dir = (dir > 0); - if (dir < 0) - reverse_points(points, n_points); - svp->segs[n_segs].points = points; - svp->segs[n_segs].bbox.x0 = x_min; - svp->segs[n_segs].bbox.x1 = x_max; - svp->segs[n_segs].bbox.y0 = points[0].y; - svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; - n_segs++; - } else - free(points); - } - - svp->n_segs = n_segs; - - qsort(&svp->segs, n_segs, sizeof(ArtSVPSeg), art_svp_seg_compare); - - return svp; -} - diff --git a/engines/sword25/gfx/image/art_svp_vpath.h b/engines/sword25/gfx/image/art_svp_vpath.h deleted file mode 100644 index 59efc34146..0000000000 --- a/engines/sword25/gfx/image/art_svp_vpath.h +++ /dev/null @@ -1,45 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program 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 General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -/* - * This code is based on Libart_LGPL - library of basic graphic primitives - * - * Copyright (c) 1998 Raph Levien - * - * Licensed under GNU LGPL v2 - * - */ - -#ifndef __ART_SVP_VPATH_H__ -#define __ART_SVP_VPATH_H__ - -#include "art.h" - -/* Sort vector paths into sorted vector paths. */ - -ArtSVP * -art_svp_from_vpath(ArtVpath *vpath); - -#endif /* __ART_SVP_VPATH_H__ */ diff --git a/engines/sword25/gfx/image/art_svp_vpath_stroke.cpp b/engines/sword25/gfx/image/art_svp_vpath_stroke.cpp deleted file mode 100644 index 7703ad26ea..0000000000 --- a/engines/sword25/gfx/image/art_svp_vpath_stroke.cpp +++ /dev/null @@ -1,657 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program 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 General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -/* - * This code is based on Libart_LGPL - library of basic graphic primitives - * - * Copyright (c) 1998 Raph Levien - * - * Licensed under GNU LGPL v2 - * - */ - -#include "art.h" -#include "art_svp_vpath_stroke.h" - -#include <stdlib.h> -#include <math.h> - -#include "art_svp_intersect.h" -#include "art_svp_vpath.h" - -#define EPSILON 1e-6 -#define EPSILON_2 1e-12 - -#define yes_OPTIMIZE_INNER - -/* Render an arc segment starting at (xc + x0, yc + y0) to (xc + x1, - yc + y1), centered at (xc, yc), and with given radius. Both x0^2 + - y0^2 and x1^2 + y1^2 should be equal to radius^2. - - A positive value of radius means curve to the left, negative means - curve to the right. -*/ -static void -art_svp_vpath_stroke_arc(ArtVpath **p_vpath, int *pn, int *pn_max, - double xc, double yc, - double x0, double y0, - double x1, double y1, - double radius, - double flatness) { - double theta; - double th_0, th_1; - int n_pts; - int i; - double aradius; - - aradius = fabs(radius); - theta = 2 * M_SQRT2 * sqrt(flatness / aradius); - th_0 = atan2(y0, x0); - th_1 = atan2(y1, x1); - if (radius > 0) { - /* curve to the left */ - if (th_0 < th_1) th_0 += M_PI * 2; - n_pts = ceil((th_0 - th_1) / theta); - } else { - /* curve to the right */ - if (th_1 < th_0) th_1 += M_PI * 2; - n_pts = ceil((th_1 - th_0) / theta); - } -#ifdef VERBOSE - printf("start %f %f; th_0 = %f, th_1 = %f, r = %f, theta = %f\n", x0, y0, th_0, th_1, radius, theta); -#endif - art_vpath_add_point(p_vpath, pn, pn_max, - ART_LINETO, xc + x0, yc + y0); - for (i = 1; i < n_pts; i++) { - theta = th_0 + (th_1 - th_0) * i / n_pts; - art_vpath_add_point(p_vpath, pn, pn_max, - ART_LINETO, xc + cos(theta) * aradius, - yc + sin(theta) * aradius); -#ifdef VERBOSE - printf("mid %f %f\n", cos(theta) * radius, sin(theta) * radius); -#endif - } - art_vpath_add_point(p_vpath, pn, pn_max, - ART_LINETO, xc + x1, yc + y1); -#ifdef VERBOSE - printf("end %f %f\n", x1, y1); -#endif -} - -/* Assume that forw and rev are at point i0. Bring them to i1, - joining with the vector i1 - i2. - - This used to be true, but isn't now that the stroke_raw code is - filtering out (near)zero length vectors: {It so happens that all - invocations of this function maintain the precondition i1 = i0 + 1, - so we could decrease the number of arguments by one. We haven't - done that here, though.} - - forw is to the line's right and rev is to its left. - - Precondition: no zero-length vectors, otherwise a divide by - zero will happen. */ -static void -render_seg(ArtVpath **p_forw, int *pn_forw, int *pn_forw_max, - ArtVpath **p_rev, int *pn_rev, int *pn_rev_max, - ArtVpath *vpath, int i0, int i1, int i2, - ArtPathStrokeJoinType join, - double line_width, double miter_limit, double flatness) { - double dx0, dy0; - double dx1, dy1; - double dlx0, dly0; - double dlx1, dly1; - double dmx, dmy; - double dmr2; - double scale; - double cross; - -#ifdef VERBOSE - printf("join style = %d\n", join); -#endif - - /* The vectors of the lines from i0 to i1 and i1 to i2. */ - dx0 = vpath[i1].x - vpath[i0].x; - dy0 = vpath[i1].y - vpath[i0].y; - - dx1 = vpath[i2].x - vpath[i1].x; - dy1 = vpath[i2].y - vpath[i1].y; - - /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise - 90 degrees, and scaled to the length of line_width. */ - scale = line_width / sqrt(dx0 * dx0 + dy0 * dy0); - dlx0 = dy0 * scale; - dly0 = -dx0 * scale; - - /* Set dl[xy]1 to the vector from i1 to i2, rotated counterclockwise - 90 degrees, and scaled to the length of line_width. */ - scale = line_width / sqrt(dx1 * dx1 + dy1 * dy1); - dlx1 = dy1 * scale; - dly1 = -dx1 * scale; - -#ifdef VERBOSE - printf("%% render_seg: (%g, %g) - (%g, %g) - (%g, %g)\n", - vpath[i0].x, vpath[i0].y, - vpath[i1].x, vpath[i1].y, - vpath[i2].x, vpath[i2].y); - - printf("%% render_seg: d[xy]0 = (%g, %g), dl[xy]0 = (%g, %g)\n", - dx0, dy0, dlx0, dly0); - - printf("%% render_seg: d[xy]1 = (%g, %g), dl[xy]1 = (%g, %g)\n", - dx1, dy1, dlx1, dly1); -#endif - - /* now, forw's last point is expected to be colinear along d[xy]0 - to point i0 - dl[xy]0, and rev with i0 + dl[xy]0. */ - - /* positive for positive area (i.e. left turn) */ - cross = dx1 * dy0 - dx0 * dy1; - - dmx = (dlx0 + dlx1) * 0.5; - dmy = (dly0 + dly1) * 0.5; - dmr2 = dmx * dmx + dmy * dmy; - - if (join == ART_PATH_STROKE_JOIN_MITER && - dmr2 * miter_limit * miter_limit < line_width * line_width) - join = ART_PATH_STROKE_JOIN_BEVEL; - - /* the case when dmr2 is zero or very small bothers me - (i.e. near a 180 degree angle) - ALEX: So, we avoid the optimization when dmr2 is very small. This should - be safe since dmx/y is only used in optimization and in MITER case, and MITER - should be converted to BEVEL when dmr2 is very small. */ - if (dmr2 > EPSILON_2) { - scale = line_width * line_width / dmr2; - dmx *= scale; - dmy *= scale; - } - - if (cross *cross < EPSILON_2 && dx0 *dx1 + dy0 *dy1 >= 0) { - /* going straight */ -#ifdef VERBOSE - printf("%% render_seg: straight\n"); -#endif - art_vpath_add_point(p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); - art_vpath_add_point(p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); - } else if (cross > 0) { - /* left turn, forw is outside and rev is inside */ - -#ifdef VERBOSE - printf("%% render_seg: left\n"); -#endif - if ( -#ifdef NO_OPTIMIZE_INNER - 0 && -#endif - (dmr2 > EPSILON_2) && - /* check that i1 + dm[xy] is inside i0-i1 rectangle */ - (dx0 + dmx) * dx0 + (dy0 + dmy) * dy0 > 0 && - /* and that i1 + dm[xy] is inside i1-i2 rectangle */ - ((dx1 - dmx) * dx1 + (dy1 - dmy) * dy1 > 0) -#ifdef PEDANTIC_INNER - && - /* check that i1 + dl[xy]1 is inside i0-i1 rectangle */ - (dx0 + dlx1) * dx0 + (dy0 + dly1) * dy0 > 0 && - /* and that i1 + dl[xy]0 is inside i1-i2 rectangle */ - ((dx1 - dlx0) * dx1 + (dy1 - dly0) * dy1 > 0) -#endif - ) { - /* can safely add single intersection point */ - art_vpath_add_point(p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy); - } else { - /* need to loop-de-loop the inside */ - art_vpath_add_point(p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); - art_vpath_add_point(p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x, vpath[i1].y); - art_vpath_add_point(p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1); - } - - if (join == ART_PATH_STROKE_JOIN_BEVEL) { - /* bevel */ - art_vpath_add_point(p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); - art_vpath_add_point(p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1); - } else if (join == ART_PATH_STROKE_JOIN_MITER) { - art_vpath_add_point(p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy); - } else if (join == ART_PATH_STROKE_JOIN_ROUND) - art_svp_vpath_stroke_arc(p_forw, pn_forw, pn_forw_max, - vpath[i1].x, vpath[i1].y, - -dlx0, -dly0, - -dlx1, -dly1, - line_width, - flatness); - } else { - /* right turn, rev is outside and forw is inside */ -#ifdef VERBOSE - printf("%% render_seg: right\n"); -#endif - - if ( -#ifdef NO_OPTIMIZE_INNER - 0 && -#endif - (dmr2 > EPSILON_2) && - /* check that i1 - dm[xy] is inside i0-i1 rectangle */ - (dx0 - dmx) * dx0 + (dy0 - dmy) * dy0 > 0 && - /* and that i1 - dm[xy] is inside i1-i2 rectangle */ - ((dx1 + dmx) * dx1 + (dy1 + dmy) * dy1 > 0) -#ifdef PEDANTIC_INNER - && - /* check that i1 - dl[xy]1 is inside i0-i1 rectangle */ - (dx0 - dlx1) * dx0 + (dy0 - dly1) * dy0 > 0 && - /* and that i1 - dl[xy]0 is inside i1-i2 rectangle */ - ((dx1 + dlx0) * dx1 + (dy1 + dly0) * dy1 > 0) -#endif - ) { - /* can safely add single intersection point */ - art_vpath_add_point(p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy); - } else { - /* need to loop-de-loop the inside */ - art_vpath_add_point(p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); - art_vpath_add_point(p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x, vpath[i1].y); - art_vpath_add_point(p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1); - } - - if (join == ART_PATH_STROKE_JOIN_BEVEL) { - /* bevel */ - art_vpath_add_point(p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); - art_vpath_add_point(p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1); - } else if (join == ART_PATH_STROKE_JOIN_MITER) { - art_vpath_add_point(p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy); - } else if (join == ART_PATH_STROKE_JOIN_ROUND) - art_svp_vpath_stroke_arc(p_rev, pn_rev, pn_rev_max, - vpath[i1].x, vpath[i1].y, - dlx0, dly0, - dlx1, dly1, - -line_width, - flatness); - - } -} - -/* caps i1, under the assumption of a vector from i0 */ -static void -render_cap(ArtVpath **p_result, int *pn_result, int *pn_result_max, - ArtVpath *vpath, int i0, int i1, - ArtPathStrokeCapType cap, double line_width, double flatness) { - double dx0, dy0; - double dlx0, dly0; - double scale; - int n_pts; - int i; - - dx0 = vpath[i1].x - vpath[i0].x; - dy0 = vpath[i1].y - vpath[i0].y; - - /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise - 90 degrees, and scaled to the length of line_width. */ - scale = line_width / sqrt(dx0 * dx0 + dy0 * dy0); - dlx0 = dy0 * scale; - dly0 = -dx0 * scale; - -#ifdef VERBOSE - printf("cap style = %d\n", cap); -#endif - - switch (cap) { - case ART_PATH_STROKE_CAP_BUTT: - art_vpath_add_point(p_result, pn_result, pn_result_max, - ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); - art_vpath_add_point(p_result, pn_result, pn_result_max, - ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); - break; - case ART_PATH_STROKE_CAP_ROUND: - n_pts = ceil(M_PI / (2.0 * M_SQRT2 * sqrt(flatness / line_width))); - art_vpath_add_point(p_result, pn_result, pn_result_max, - ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); - for (i = 1; i < n_pts; i++) { - double theta, c_th, s_th; - - theta = M_PI * i / n_pts; - c_th = cos(theta); - s_th = sin(theta); - art_vpath_add_point(p_result, pn_result, pn_result_max, - ART_LINETO, - vpath[i1].x - dlx0 * c_th - dly0 * s_th, - vpath[i1].y - dly0 * c_th + dlx0 * s_th); - } - art_vpath_add_point(p_result, pn_result, pn_result_max, - ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); - break; - case ART_PATH_STROKE_CAP_SQUARE: - art_vpath_add_point(p_result, pn_result, pn_result_max, - ART_LINETO, - vpath[i1].x - dlx0 - dly0, - vpath[i1].y - dly0 + dlx0); - art_vpath_add_point(p_result, pn_result, pn_result_max, - ART_LINETO, - vpath[i1].x + dlx0 - dly0, - vpath[i1].y + dly0 + dlx0); - break; - } -} - -/** - * art_svp_from_vpath_raw: Stroke a vector path, raw version - * @vpath: #ArtVPath to stroke. - * @join: Join style. - * @cap: Cap style. - * @line_width: Width of stroke. - * @miter_limit: Miter limit. - * @flatness: Flatness. - * - * Exactly the same as art_svp_vpath_stroke(), except that the resulting - * stroke outline may self-intersect and have regions of winding number - * greater than 1. - * - * Return value: Resulting raw stroked outline in svp format. - **/ -ArtVpath * -art_svp_vpath_stroke_raw(ArtVpath *vpath, - ArtPathStrokeJoinType join, - ArtPathStrokeCapType cap, - double line_width, - double miter_limit, - double flatness) { - int begin_idx, end_idx; - int i; - ArtVpath *forw, *rev; - int n_forw, n_rev; - int n_forw_max, n_rev_max; - ArtVpath *result; - int n_result, n_result_max; - double half_lw = 0.5 * line_width; - int closed; - int last, this_, next, second; - double dx, dy; - - n_forw_max = 16; - forw = art_new(ArtVpath, n_forw_max); - - n_rev_max = 16; - rev = art_new(ArtVpath, n_rev_max); - - n_result = 0; - n_result_max = 16; - result = art_new(ArtVpath, n_result_max); - - for (begin_idx = 0; vpath[begin_idx].code != ART_END; begin_idx = end_idx) { - n_forw = 0; - n_rev = 0; - - closed = (vpath[begin_idx].code == ART_MOVETO); - - /* we don't know what the first point joins with until we get to the - last point and see if it's closed. So we start with the second - line in the path. - - Note: this is not strictly true (we now know it's closed from - the opening pathcode), but why fix code that isn't broken? - */ - - this_ = begin_idx; - /* skip over identical points at the beginning of the subpath */ - for (i = this_ + 1; vpath[i].code == ART_LINETO; i++) { - dx = vpath[i].x - vpath[this_].x; - dy = vpath[i].y - vpath[this_].y; - if (dx * dx + dy * dy > EPSILON_2) - break; - } - next = i; - second = next; - - /* invariant: this doesn't coincide with next */ - while (vpath[next].code == ART_LINETO) { - last = this_; - this_ = next; - /* skip over identical points after the beginning of the subpath */ - for (i = this_ + 1; vpath[i].code == ART_LINETO; i++) { - dx = vpath[i].x - vpath[this_].x; - dy = vpath[i].y - vpath[this_].y; - if (dx * dx + dy * dy > EPSILON_2) - break; - } - next = i; - if (vpath[next].code != ART_LINETO) { - /* reached end of path */ - /* make "closed" detection conform to PostScript - semantics (i.e. explicit closepath code rather than - just the fact that end of the path is the beginning) */ - if (closed && - vpath[this_].x == vpath[begin_idx].x && - vpath[this_].y == vpath[begin_idx].y) { - int j; - - /* path is closed, render join to beginning */ - render_seg(&forw, &n_forw, &n_forw_max, - &rev, &n_rev, &n_rev_max, - vpath, last, this_, second, - join, half_lw, miter_limit, flatness); - -#ifdef VERBOSE - printf("%% forw %d, rev %d\n", n_forw, n_rev); -#endif - /* do forward path */ - art_vpath_add_point(&result, &n_result, &n_result_max, - ART_MOVETO, forw[n_forw - 1].x, - forw[n_forw - 1].y); - for (j = 0; j < n_forw; j++) - art_vpath_add_point(&result, &n_result, &n_result_max, - ART_LINETO, forw[j].x, - forw[j].y); - - /* do reverse path, reversed */ - art_vpath_add_point(&result, &n_result, &n_result_max, - ART_MOVETO, rev[0].x, - rev[0].y); - for (j = n_rev - 1; j >= 0; j--) - art_vpath_add_point(&result, &n_result, &n_result_max, - ART_LINETO, rev[j].x, - rev[j].y); - } else { - /* path is open */ - int j; - - /* add to forw rather than result to ensure that - forw has at least one point. */ - render_cap(&forw, &n_forw, &n_forw_max, - vpath, last, this_, - cap, half_lw, flatness); - art_vpath_add_point(&result, &n_result, &n_result_max, - ART_MOVETO, forw[0].x, - forw[0].y); - for (j = 1; j < n_forw; j++) - art_vpath_add_point(&result, &n_result, &n_result_max, - ART_LINETO, forw[j].x, - forw[j].y); - for (j = n_rev - 1; j >= 0; j--) - art_vpath_add_point(&result, &n_result, &n_result_max, - ART_LINETO, rev[j].x, - rev[j].y); - render_cap(&result, &n_result, &n_result_max, - vpath, second, begin_idx, - cap, half_lw, flatness); - art_vpath_add_point(&result, &n_result, &n_result_max, - ART_LINETO, forw[0].x, - forw[0].y); - } - } else - render_seg(&forw, &n_forw, &n_forw_max, - &rev, &n_rev, &n_rev_max, - vpath, last, this_, next, - join, half_lw, miter_limit, flatness); - } - end_idx = next; - } - - free(forw); - free(rev); -#ifdef VERBOSE - printf("%% n_result = %d\n", n_result); -#endif - art_vpath_add_point(&result, &n_result, &n_result_max, ART_END, 0, 0); - return result; -} - -#define noVERBOSE - -#ifdef VERBOSE - -#define XOFF 50 -#define YOFF 700 - -static void -print_ps_vpath(ArtVpath *vpath) { - int i; - - for (i = 0; vpath[i].code != ART_END; i++) { - switch (vpath[i].code) { - case ART_MOVETO: - printf("%g %g moveto\n", XOFF + vpath[i].x, YOFF - vpath[i].y); - break; - case ART_LINETO: - printf("%g %g lineto\n", XOFF + vpath[i].x, YOFF - vpath[i].y); - break; - default: - break; - } - } - printf("stroke showpage\n"); -} - -static void -print_ps_svp(ArtSVP *vpath) { - int i, j; - - printf("%% begin\n"); - for (i = 0; i < vpath->n_segs; i++) { - printf("%g setgray\n", vpath->segs[i].dir ? 0.7 : 0); - for (j = 0; j < vpath->segs[i].n_points; j++) { - printf("%g %g %s\n", - XOFF + vpath->segs[i].points[j].x, - YOFF - vpath->segs[i].points[j].y, - j ? "lineto" : "moveto"); - } - printf("stroke\n"); - } - - printf("showpage\n"); -} -#endif - -/* Render a vector path into a stroked outline. - - Status of this routine: - - Basic correctness: Only miter and bevel line joins are implemented, - and only butt line caps. Otherwise, seems to be fine. - - Numerical stability: We cheat (adding random perturbation). Thus, - it seems very likely that no numerical stability problems will be - seen in practice. - - Speed: Should be pretty good. - - Precision: The perturbation fuzzes the coordinates slightly, - but not enough to be visible. */ -/** - * art_svp_vpath_stroke: Stroke a vector path. - * @vpath: #ArtVPath to stroke. - * @join: Join style. - * @cap: Cap style. - * @line_width: Width of stroke. - * @miter_limit: Miter limit. - * @flatness: Flatness. - * - * Computes an svp representing the stroked outline of @vpath. The - * width of the stroked line is @line_width. - * - * Lines are joined according to the @join rule. Possible values are - * ART_PATH_STROKE_JOIN_MITER (for mitered joins), - * ART_PATH_STROKE_JOIN_ROUND (for round joins), and - * ART_PATH_STROKE_JOIN_BEVEL (for bevelled joins). The mitered join - * is converted to a bevelled join if the miter would extend to a - * distance of more than @miter_limit * @line_width from the actual - * join point. - * - * If there are open subpaths, the ends of these subpaths are capped - * according to the @cap rule. Possible values are - * ART_PATH_STROKE_CAP_BUTT (squared cap, extends exactly to end - * point), ART_PATH_STROKE_CAP_ROUND (rounded half-circle centered at - * the end point), and ART_PATH_STROKE_CAP_SQUARE (squared cap, - * extending half @line_width past the end point). - * - * The @flatness parameter controls the accuracy of the rendering. It - * is most important for determining the number of points to use to - * approximate circular arcs for round lines and joins. In general, the - * resulting vector path will be within @flatness pixels of the "ideal" - * path containing actual circular arcs. I reserve the right to use - * the @flatness parameter to convert bevelled joins to miters for very - * small turn angles, as this would reduce the number of points in the - * resulting outline path. - * - * The resulting path is "clean" with respect to self-intersections, i.e. - * the winding number is 0 or 1 at each point. - * - * Return value: Resulting stroked outline in svp format. - **/ -ArtSVP * -art_svp_vpath_stroke(ArtVpath *vpath, - ArtPathStrokeJoinType join, - ArtPathStrokeCapType cap, - double line_width, - double miter_limit, - double flatness) { - ArtVpath *vpath_stroke; - ArtSVP *svp, *svp2; - ArtSvpWriter *swr; - - vpath_stroke = art_svp_vpath_stroke_raw(vpath, join, cap, - line_width, miter_limit, flatness); - svp = art_svp_from_vpath(vpath_stroke); - free(vpath_stroke); - - swr = art_svp_writer_rewind_new(ART_WIND_RULE_NONZERO); - art_svp_intersector(svp, swr); - - svp2 = art_svp_writer_rewind_reap(swr); - art_svp_free(svp); - return svp2; -} diff --git a/engines/sword25/gfx/image/art_svp_vpath_stroke.h b/engines/sword25/gfx/image/art_svp_vpath_stroke.h deleted file mode 100644 index a313c6b58a..0000000000 --- a/engines/sword25/gfx/image/art_svp_vpath_stroke.h +++ /dev/null @@ -1,71 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program 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 General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -/* - * This code is based on Libart_LGPL - library of basic graphic primitives - * - * Copyright (c) 1998 Raph Levien - * - * Licensed under GNU LGPL v2 - * - */ - -#ifndef __ART_SVP_VPATH_STROKE_H__ -#define __ART_SVP_VPATH_STROKE_H__ - -/* Sort vector paths into sorted vector paths. */ - -#include "art.h" - -typedef enum { - ART_PATH_STROKE_JOIN_MITER, - ART_PATH_STROKE_JOIN_ROUND, - ART_PATH_STROKE_JOIN_BEVEL -} ArtPathStrokeJoinType; - -typedef enum { - ART_PATH_STROKE_CAP_BUTT, - ART_PATH_STROKE_CAP_ROUND, - ART_PATH_STROKE_CAP_SQUARE -} ArtPathStrokeCapType; - -ArtSVP * -art_svp_vpath_stroke(ArtVpath *vpath, - ArtPathStrokeJoinType join, - ArtPathStrokeCapType cap, - double line_width, - double miter_limit, - double flatness); - -/* This version may have winding numbers exceeding 1. */ -ArtVpath * -art_svp_vpath_stroke_raw(ArtVpath *vpath, - ArtPathStrokeJoinType join, - ArtPathStrokeCapType cap, - double line_width, - double miter_limit, - double flatness); - -#endif /* __ART_SVP_VPATH_STROKE_H__ */ diff --git a/engines/sword25/gfx/image/art_vpath_bpath.cpp b/engines/sword25/gfx/image/art_vpath_bpath.cpp deleted file mode 100644 index 1191c1fa08..0000000000 --- a/engines/sword25/gfx/image/art_vpath_bpath.cpp +++ /dev/null @@ -1,276 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program 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 General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -/* - * This code is based on Libart_LGPL - library of basic graphic primitives - * - * Copyright (c) 1998 Raph Levien - * - * Licensed under GNU LGPL v2 - * - */ - -/* Basic constructors and operations for bezier paths */ - -#include "art.h" - -#include <math.h> - -#define RENDER_LEVEL 4 -#define RENDER_SIZE (1 << (RENDER_LEVEL)) - -/** - * art_vpath_render_bez: Render a bezier segment into the vpath. - * @p_vpath: Where the pointer to the #ArtVpath structure is stored. - * @pn_points: Pointer to the number of points in *@p_vpath. - * @pn_points_max: Pointer to the number of points allocated. - * @x0: X coordinate of starting bezier point. - * @y0: Y coordinate of starting bezier point. - * @x1: X coordinate of first bezier control point. - * @y1: Y coordinate of first bezier control point. - * @x2: X coordinate of second bezier control point. - * @y2: Y coordinate of second bezier control point. - * @x3: X coordinate of ending bezier point. - * @y3: Y coordinate of ending bezier point. - * @flatness: Flatness control. - * - * Renders a bezier segment into the vector path, reallocating and - * updating *@p_vpath and *@pn_vpath_max as necessary. *@pn_vpath is - * incremented by the number of vector points added. - * - * This step includes (@x0, @y0) but not (@x3, @y3). - * - * The @flatness argument guides the amount of subdivision. The Adobe - * PostScript reference manual defines flatness as the maximum - * deviation between the any point on the vpath approximation and the - * corresponding point on the "true" curve, and we follow this - * definition here. A value of 0.25 should ensure high quality for aa - * rendering. -**/ -static void -art_vpath_render_bez(ArtVpath **p_vpath, int *pn, int *pn_max, - double x0, double y0, - double x1, double y1, - double x2, double y2, - double x3, double y3, - double flatness) { - double x3_0, y3_0; - double z3_0_dot; - double z1_dot, z2_dot; - double z1_perp, z2_perp; - double max_perp_sq; - - double x_m, y_m; - double xa1, ya1; - double xa2, ya2; - double xb1, yb1; - double xb2, yb2; - - /* It's possible to optimize this routine a fair amount. - - First, once the _dot conditions are met, they will also be met in - all further subdivisions. So we might recurse to a different - routine that only checks the _perp conditions. - - Second, the distance _should_ decrease according to fairly - predictable rules (a factor of 4 with each subdivision). So it might - be possible to note that the distance is within a factor of 4 of - acceptable, and subdivide once. But proving this might be hard. - - Third, at the last subdivision, x_m and y_m can be computed more - expeditiously (as in the routine above). - - Finally, if we were able to subdivide by, say 2 or 3, this would - allow considerably finer-grain control, i.e. fewer points for the - same flatness tolerance. This would speed things up downstream. - - In any case, this routine is unlikely to be the bottleneck. It's - just that I have this undying quest for more speed... - - */ - - x3_0 = x3 - x0; - y3_0 = y3 - y0; - - /* z3_0_dot is dist z0-z3 squared */ - z3_0_dot = x3_0 * x3_0 + y3_0 * y3_0; - - if (z3_0_dot < 0.001) { - /* if start and end point are almost identical, the flatness tests - * don't work properly, so fall back on testing whether both of - * the other two control points are the same as the start point, - * too. - */ - if (hypot(x1 - x0, y1 - y0) < 0.001 - && hypot(x2 - x0, y2 - y0) < 0.001) - goto nosubdivide; - else - goto subdivide; - } - - /* we can avoid subdivision if: - - z1 has distance no more than flatness from the z0-z3 line - - z1 is no more z0'ward than flatness past z0-z3 - - z1 is more z0'ward than z3'ward on the line traversing z0-z3 - - and correspondingly for z2 */ - - /* perp is distance from line, multiplied by dist z0-z3 */ - max_perp_sq = flatness * flatness * z3_0_dot; - - z1_perp = (y1 - y0) * x3_0 - (x1 - x0) * y3_0; - if (z1_perp * z1_perp > max_perp_sq) - goto subdivide; - - z2_perp = (y3 - y2) * x3_0 - (x3 - x2) * y3_0; - if (z2_perp * z2_perp > max_perp_sq) - goto subdivide; - - z1_dot = (x1 - x0) * x3_0 + (y1 - y0) * y3_0; - if (z1_dot < 0 && z1_dot * z1_dot > max_perp_sq) - goto subdivide; - - z2_dot = (x3 - x2) * x3_0 + (y3 - y2) * y3_0; - if (z2_dot < 0 && z2_dot * z2_dot > max_perp_sq) - goto subdivide; - - if (z1_dot + z1_dot > z3_0_dot) - goto subdivide; - - if (z2_dot + z2_dot > z3_0_dot) - goto subdivide; - - -nosubdivide: - /* don't subdivide */ - art_vpath_add_point(p_vpath, pn, pn_max, - ART_LINETO, x3, y3); - return; - -subdivide: - - xa1 = (x0 + x1) * 0.5; - ya1 = (y0 + y1) * 0.5; - xa2 = (x0 + 2 * x1 + x2) * 0.25; - ya2 = (y0 + 2 * y1 + y2) * 0.25; - xb1 = (x1 + 2 * x2 + x3) * 0.25; - yb1 = (y1 + 2 * y2 + y3) * 0.25; - xb2 = (x2 + x3) * 0.5; - yb2 = (y2 + y3) * 0.5; - x_m = (xa2 + xb1) * 0.5; - y_m = (ya2 + yb1) * 0.5; -#ifdef VERBOSE - printf("%g,%g %g,%g %g,%g %g,%g\n", xa1, ya1, xa2, ya2, - xb1, yb1, xb2, yb2); -#endif - art_vpath_render_bez(p_vpath, pn, pn_max, - x0, y0, xa1, ya1, xa2, ya2, x_m, y_m, flatness); - art_vpath_render_bez(p_vpath, pn, pn_max, - x_m, y_m, xb1, yb1, xb2, yb2, x3, y3, flatness); -} - -/** - * art_bez_path_to_vec: Create vpath from bezier path. - * @bez: Bezier path. - * @flatness: Flatness control. - * - * Creates a vector path closely approximating the bezier path defined by - * @bez. The @flatness argument controls the amount of subdivision. In - * general, the resulting vpath deviates by at most @flatness pixels - * from the "ideal" path described by @bez. - * - * Return value: Newly allocated vpath. - **/ -ArtVpath * -art_bez_path_to_vec(const ArtBpath *bez, double flatness) { - ArtVpath *vec; - int vec_n, vec_n_max; - int bez_index; - double x, y; - - vec_n = 0; - vec_n_max = RENDER_SIZE; - vec = art_new(ArtVpath, vec_n_max); - - /* Initialization is unnecessary because of the precondition that the - bezier path does not begin with LINETO or CURVETO, but is here - to make the code warning-free. */ - x = 0; - y = 0; - - bez_index = 0; - do { -#ifdef VERBOSE - printf("%s %g %g\n", - bez[bez_index].code == ART_CURVETO ? "curveto" : - bez[bez_index].code == ART_LINETO ? "lineto" : - bez[bez_index].code == ART_MOVETO ? "moveto" : - bez[bez_index].code == ART_MOVETO_OPEN ? "moveto-open" : - "end", bez[bez_index].x3, bez[bez_index].y3); -#endif - /* make sure space for at least one more code */ - if (vec_n >= vec_n_max) - art_expand(vec, ArtVpath, vec_n_max); - switch (bez[bez_index].code) { - case ART_MOVETO_OPEN: - case ART_MOVETO: - case ART_LINETO: - x = bez[bez_index].x3; - y = bez[bez_index].y3; - vec[vec_n].code = bez[bez_index].code; - vec[vec_n].x = x; - vec[vec_n].y = y; - vec_n++; - break; - case ART_END: - vec[vec_n].code = bez[bez_index].code; - vec[vec_n].x = 0; - vec[vec_n].y = 0; - vec_n++; - break; - case ART_CURVETO: -#ifdef VERBOSE - printf("%g,%g %g,%g %g,%g %g,%g\n", x, y, - bez[bez_index].x1, bez[bez_index].y1, - bez[bez_index].x2, bez[bez_index].y2, - bez[bez_index].x3, bez[bez_index].y3); -#endif - art_vpath_render_bez(&vec, &vec_n, &vec_n_max, - x, y, - bez[bez_index].x1, bez[bez_index].y1, - bez[bez_index].x2, bez[bez_index].y2, - bez[bez_index].x3, bez[bez_index].y3, - flatness); - x = bez[bez_index].x3; - y = bez[bez_index].y3; - break; - } - } while (bez[bez_index++].code != ART_END); - return vec; -} - diff --git a/engines/sword25/gfx/image/vectorimagerenderer.cpp b/engines/sword25/gfx/image/vectorimagerenderer.cpp index e1b6ac9122..16d1abf9f9 100644 --- a/engines/sword25/gfx/image/vectorimagerenderer.cpp +++ b/engines/sword25/gfx/image/vectorimagerenderer.cpp @@ -41,9 +41,7 @@ * */ -#include "art_svp_vpath.h" -#include "art_svp_vpath_stroke.h" -#include "art_svp_render_aa.h" +#include "art.h" #include "sword25/gfx/image/vectorimage.h" #include "graphics/colormasks.h" diff --git a/engines/sword25/module.mk b/engines/sword25/module.mk index 917e6d51d8..c936565a1c 100644 --- a/engines/sword25/module.mk +++ b/engines/sword25/module.mk @@ -35,11 +35,6 @@ MODULE_OBJS := \ gfx/image/vectorimage.o \ gfx/image/vectorimagerenderer.o \ gfx/image/art.o \ - gfx/image/art_svp_intersect.o \ - gfx/image/art_svp_render_aa.o \ - gfx/image/art_svp_vpath.o \ - gfx/image/art_svp_vpath_stroke.o \ - gfx/image/art_vpath_bpath.o \ input/inputengine.o \ input/inputengine_script.o \ kernel/callbackregistry.o \ |