/* 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. * */ /* * This code is based on Libart_LGPL - library of basic graphic primitives * * Copyright (c) 1998 Raph Levien * * Licensed under GNU LGPL v2 * */ /* Various utility functions RLL finds useful. */ #include "common/textconsole.h" #include "sword25/gfx/image/art.h" namespace Sword25 { /** * art_svp_free: Free an #ArtSVP structure. * @svp: #ArtSVP to free. * * Frees an #ArtSVP structure and all the segments in it. **/ void art_svp_free(ArtSVP *svp) { int n_segs = svp->n_segs; int i; for (i = 0; i < n_segs; i++) free(svp->segs[i].points); free(svp); } #define EPSILON 0 /** * art_svp_seg_compare: Compare two segments of an svp. * @seg1: First segment to compare. * @seg2: Second segment to compare. * * 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) { const ArtSVPSeg *seg1 = (const ArtSVPSeg *)s1; const ArtSVPSeg *seg2 = (const ArtSVPSeg *)s2; if (seg1->points[0].y - EPSILON > seg2->points[0].y) return 1; else if (seg1->points[0].y + EPSILON < seg2->points[0].y) return -1; else if (seg1->points[0].x - EPSILON > seg2->points[0].x) return 1; else if (seg1->points[0].x + EPSILON < seg2->points[0].x) return -1; else if ((seg1->points[1].x - seg1->points[0].x) * (seg2->points[1].y - seg2->points[0].y) - (seg1->points[1].y - seg1->points[0].y) * (seg2->points[1].x - seg2->points[0].x) > 0) return 1; else return -1; } /** * art_vpath_add_point: Add point to 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. * @code: The pathcode for the new point. * @x: The X coordinate of the new point. * @y: The Y coordinate of the new point. * * Adds a new point to *@p_vpath, reallocating and updating *@p_vpath * and *@pn_points_max as necessary. *@pn_points is incremented. * * This routine always adds the point after all points already in the * 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, ArtPathcode code, double x, double y) { int i; i = (*pn_points)++; if (i == *pn_points_max) art_expand(*p_vpath, ArtVpath, *pn_points_max); (*p_vpath)[i].code = code; (*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)); if (!svp) error("[art_svp_from_vpath] Cannot allocate memory"); 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; ArtSVP *tmp = (ArtSVP *)realloc(svp, sizeof(ArtSVP) + (n_segs_max - 1) * sizeof(ArtSVPSeg)); if (!tmp) error("Cannot reallocate memory in art_svp_from_vpath()"); svp = tmp; } 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; ArtSVP *tmp = (ArtSVP *)realloc(svp, sizeof(ArtSVP) + (n_segs_max - 1) * sizeof(ArtSVPSeg)); if (!tmp) error("Cannot reallocate memory in art_svp_from_vpath()"); svp = tmp; } 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; ArtSVP *tmp = (ArtSVP *)realloc(svp, sizeof(ArtSVP) + (n_segs_max - 1) * sizeof(ArtSVPSeg)); if (!tmp) error("Cannot reallocate memory in art_svp_from_vpath()"); svp = tmp; } 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) { /* 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... */ bool subDivide = false; double x3_0 = x3 - x0; double y3_0 = y3 - y0; // z3_0_dot is dist z0-z3 squared double 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)) subDivide = true; } else { /* 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 double max_perp_sq = flatness * flatness * z3_0_dot; double z1_perp = (y1 - y0) * x3_0 - (x1 - x0) * y3_0; if (z1_perp * z1_perp > max_perp_sq) { subDivide = true; } else { double z2_perp = (y3 - y2) * x3_0 - (x3 - x2) * y3_0; if (z2_perp * z2_perp > max_perp_sq) { subDivide = true; } else { double z1_dot = (x1 - x0) * x3_0 + (y1 - y0) * y3_0; if (z1_dot < 0 && z1_dot * z1_dot > max_perp_sq) { subDivide = true; } else { double z2_dot = (x3 - x2) * x3_0 + (y3 - y2) * y3_0; if (z2_dot < 0 && z2_dot * z2_dot > max_perp_sq) subDivide = true; else if (z1_dot + z1_dot > z3_0_dot) subDivide = true; else if (z2_dot + z2_dot > z3_0_dot) subDivide = true; } } } } if (subDivide) { double xa1 = (x0 + x1) * 0.5; double ya1 = (y0 + y1) * 0.5; double xa2 = (x0 + 2 * x1 + x2) * 0.25; double ya2 = (y0 + 2 * y1 + y2) * 0.25; double xb1 = (x1 + 2 * x2 + x3) * 0.25; double yb1 = (y1 + 2 * y2 + y3) * 0.25; double xb2 = (x2 + x3) * 0.5; double yb2 = (y2 + y3) * 0.5; double x_m = (xa2 + xb1) * 0.5; double 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); } else { // don't subdivide art_vpath_add_point(p_vpath, pn, pn_max, ART_LINETO, x3, y3); } } /** * 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; default: 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 = (int)ceil((th_0 - th_1) / theta); } else { /* curve to the right */ if (th_1 < th_0) th_1 += M_PI * 2; n_pts = (int)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 = (int)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; default: 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); if (!result) error("[art_pri_new] Cannot allocate memory"); 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 bool 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; bool left_filled = 0, right_filled = 0; 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: error("Unknown wind rule %d", 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; int *tmp = art_renew(swr->n_points_max, int, swr->n_segs_max); if (!tmp) error("Cannot reallocate memory in art_svp_writer_rewind_add_segment()"); swr->n_points_max = tmp; } 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); if (!seg->points) error("[art_svp_writer_rewind_add_segment] Cannot allocate memory"); 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); if (!result) error("[art_svp_writer_rewind_new] Cannot allocate memory"); 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)); if (!result->svp) error("[art_svp_writer_rewind_new] Cannot allocate memory"); 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) { warning("attempt to put segment in horiz list twice"); 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); if (!pri_pt) error("[art_svp_intersect_push_pt] Cannot allocate memory"); 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; bool 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 = false; } else left_live = 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 = false; } else right_live = 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) { warning("art_svp_intersect_add_point: non-ascending x"); } 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 bool 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 false; d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c; if (d < -EPSILON_A) return 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 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 false; d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c; if (d > EPSILON_A) return 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 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 false; } art_svp_intersect_swap_active(ctx, left_seg, right_seg); return 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 false; d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c; if (d < -EPSILON_A) return 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 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 false; d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c; if (d > EPSILON_A) return 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 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 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 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 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); if (!hs) error("[art_svp_intersect_horiz] Cannot allocate memory"); 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; bool first = 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 = false; } } } else { ArtActiveSeg *right; bool first = 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 = 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 *last = NULL; ArtActiveSeg *left, *right; ArtPriPoint *pri_pt = art_new(ArtPriPoint, 1); if (!pri_pt) error("[art_svp_intersect_add_seg] Cannot allocate memory"); 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; 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); if (!ctx) error("[art_svp_intersector] Cannot allocate memory"); 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); if (!first_point) error("[art_svp_intersector] Cannot allocate memory"); 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); if (!iter) error("[art_svp_render_aa_iter] Cannot allocate memory"); 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 = (int)((ix_min + 1 - (x_min + x_max) * 0.5) * delta); ADD_STEP(ix_min, xdelta) if (ix_min + 1 < x1) { xdelta = (int)(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 = (int)(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_ = (int)((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_ = (int)(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 = (int)(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); } } // End of namespace Sword25