v02i043: X11 Release 3, Patch3
Mike Wexler
mikew at wyse.wyse.com
Tue Dec 13 07:19:27 AEST 1988
Submitted-by: Xstuff service <xstuff at EXPO.LCS.MIT.EDU>
Posting-number: Volume 2, Issue 43
Archive-name: x11.3/patch3
This patch optimizes some special cases in the mi arc code. It
affects only server/ddx/mi/miarc.c
Circular arcs are now computed specially with a direct equation, instead of
using the more general elipse solution.
Memory allocation for span generation/merging was rewritten to reduce
the number of small Xalloc calls.
Zero height/width arcs now use pGC->PolyFillRect instead of miSppFillPoly.
All of these changes are based on actual -pg style profiling results run on a
Vaxstation 3200.
Circular arcs are now at least 20 times faster, Zero width/height arcs are
at least 10 times faster on the 3200. I expect more substantial changes on
Suns which don't have floating point hardware, but have no data which
demonstrates this.
*** /tmp/,RCSt1a15146 Fri Dec 9 13:27:24 1988
--- server/ddx/mi/miarc.c Fri Dec 9 13:26:39 1988
***************
*** 21,27 ****
SOFTWARE.
******************************************************************/
! /* $XConsortium: miarc.c,v 1.63 88/10/23 17:07:31 keith Exp $ */
/* Author: Keith Packard */
#include "X.h"
--- 21,27 ----
SOFTWARE.
******************************************************************/
! /* $XConsortium: miarc.c,v 1.67 88/12/09 13:25:56 keith Exp $ */
/* Author: Keith Packard */
#include "X.h"
***************
*** 34,39 ****
--- 34,63 ----
#include "mifpoly.h"
#include "mi.h"
+ /*
+ * some interesting sematic interpretation of the protocol:
+ *
+ * Self intersecting arcs (i.e. those spanning 360 degrees)
+ * never join with other arcs, and are drawn without caps
+ * (unless on/off dashed, in which case each dash segment
+ * is capped, except when the last segment meets the
+ * first segment, when no caps are drawn)
+ *
+ * double dash arcs are drawn in two parts, first the
+ * odd dashes (drawn in background) then the even dashes
+ * (drawn in foreground). This means that overlapping
+ * sections of foreground/background are drawn twice,
+ * first in background then in foreground. The double-draw
+ * occurs even when the function uses the destination values
+ * (e.g. xor mode). This is the same way the wide-line
+ * code works and should be "fixed".
+ *
+ * the wide arc code will never be "correct" -- the protocol
+ * document specifies exact pixelization which is impossible
+ * when calculating pixel positions with complicated floating-
+ * point expressions.
+ */
+
extern double sqrt(), cos(), sin(), atan();
/* these are from our <math.h>, but I'm told some systems don't have
***************
*** 72,91 ****
SppPointRec counterClock;
} miArcFaceRec, *miArcFacePtr;
- /*
- * This is an entire sequence of arcs, computed and categorized according
- * to operation. miDashArcs generates either one or two of these.
- */
-
typedef struct _miArcData {
xArc arc;
int render; /* non-zero means render after drawing */
int join; /* related join */
int cap; /* related cap */
miArcFaceRec bounds[2];
double x0, y0, x1, y1;
} miArcDataRec, *miArcDataPtr;
typedef struct _miPolyArc {
int narcs;
miArcDataPtr arcs;
--- 96,116 ----
SppPointRec counterClock;
} miArcFaceRec, *miArcFacePtr;
typedef struct _miArcData {
xArc arc;
int render; /* non-zero means render after drawing */
int join; /* related join */
int cap; /* related cap */
+ int selfJoin; /* final dash meets first dash */
miArcFaceRec bounds[2];
double x0, y0, x1, y1;
} miArcDataRec, *miArcDataPtr;
+ /*
+ * This is an entire sequence of arcs, computed and categorized according
+ * to operation. miDashArcs generates either one or two of these.
+ */
+
typedef struct _miPolyArc {
int narcs;
miArcDataPtr arcs;
***************
*** 185,190 ****
--- 210,216 ----
* from the scratch drawable to pDraw. (See the wide line code for a
* fuller explanation of this.)
*/
+
void
miPolyArc(pDraw, pGC, narcs, parcs)
DrawablePtr pDraw;
***************
*** 316,321 ****
--- 342,353 ----
&arcData->bounds[LEFT_END]);
if (polyArcs[iphase].arcs[i].render) {
fillSpans (pDrawTo, pGCTo);
+ /*
+ * don't cap self-joining arcs
+ */
+ if (polyArcs[iphase].arcs[i].selfJoin &&
+ cap[iphase] < polyArcs[iphase].arcs[i].cap)
+ cap[iphase]++;
while (cap[iphase] < polyArcs[iphase].arcs[i].cap) {
int arcIndex, end;
miArcDataPtr arcData0;
***************
*** 874,879 ****
--- 906,912 ----
xArc xarc;
int iphase, prevphase, joinphase;
int arcsJoin;
+ int selfJoin;
int iDash, dashRemaining;
int iDashStart, dashRemainingStart, iphaseStart;
***************
*** 937,943 ****
j = i + 1;
if (j == narcs)
j = 0;
! if (!data[i].selfJoin &&
(UNEQUAL (data[i].x1, data[j].x0) ||
UNEQUAL (data[i].y1, data[j].y0)))
{
--- 970,976 ----
j = i + 1;
if (j == narcs)
j = 0;
! if (data[i].selfJoin ||
(UNEQUAL (data[i].x1, data[j].x0) ||
UNEQUAL (data[i].y1, data[j].y0)))
{
***************
*** 959,964 ****
--- 992,1001 ----
if (nexti == narcs)
nexti = 0;
if (isDashed) {
+ /*
+ * compute each individual dash segment using the path
+ * length function
+ */
startAngle = parcs[i].angle1;
spanAngle = parcs[i].angle2;
if (spanAngle > FULLCIRCLE)
***************
*** 972,977 ****
--- 1009,1016 ----
endAngle = startAngle + spanAngle;
backwards = spanAngle < 0;
prevDashAngle = startAngle;
+ selfJoin = data[i].selfJoin &&
+ (iphase == 0 || isDoubleDash);
while (prevDashAngle != endAngle) {
dashAngle = computeAngleFromPath
(prevDashAngle, endAngle,
***************
*** 992,997 ****
--- 1031,1039 ----
xarc.angle2 = spanAngle;
arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
&arcSize[iphase], xarc);
+ /*
+ * cap each end of an on/off dash
+ */
if (!isDoubleDash) {
if (prevDashAngle != startAngle) {
addCap (&arcs[iphase].caps,
***************
*** 1010,1015 ****
--- 1052,1060 ----
arc->cap = arcs[iphase].ncaps;
arc->join = arcs[iphase].njoins;
arc->render = 0;
+ arc->selfJoin = 0;
+ if (dashAngle == endAngle)
+ arc->selfJoin = selfJoin;
}
prevphase = iphase;
if (dashRemaining <= 0) {
***************
*** 1026,1031 ****
--- 1071,1077 ----
&arcSize[iphase], parcs[i]);
arc->join = arcs[iphase].njoins;
arc->cap = arcs[iphase].ncaps;
+ arc->selfJoin = data[i].selfJoin;
prevphase = iphase;
}
if (prevphase == 0 || isDoubleDash)
***************
*** 1042,1048 ****
}
arcsJoin = narcs > 1 &&
ISEQUAL (data[i].x1, data[j].x0) &&
! ISEQUAL (data[i].y1, data[j].y0);
if (arcsJoin)
arc->render = 0;
else
--- 1088,1095 ----
}
arcsJoin = narcs > 1 &&
ISEQUAL (data[i].x1, data[j].x0) &&
! ISEQUAL (data[i].y1, data[j].y0) &&
! !data[i].selfJoin && !data[j].selfJoin;
if (arcsJoin)
arc->render = 0;
else
***************
*** 1074,1081 ****
arc->join = arcs[prevphase].njoins;
}
} else {
if ((prevphase == 0 || isDoubleDash) &&
! !data[i].selfJoin)
{
addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,
&capSize[prevphase], LEFT_END, k);
--- 1121,1132 ----
arc->join = arcs[prevphase].njoins;
}
} else {
+ /*
+ * cap the left end of this arc
+ * unless it joins itself
+ */
if ((prevphase == 0 || isDoubleDash) &&
! !arc->selfJoin)
{
addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,
&capSize[prevphase], LEFT_END, k);
***************
*** 1103,1110 ****
* hardly matters...
*/
if ((iphase == 0 || isDoubleDash) &&
! (nexti != start || arcsJoin && isDashed) &&
! !data[j].selfJoin)
addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
&capSize[iphase], RIGHT_END, nextk);
}
--- 1154,1160 ----
* hardly matters...
*/
if ((iphase == 0 || isDoubleDash) &&
! (nexti != start || arcsJoin && isDashed))
addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
&capSize[iphase], RIGHT_END, nextk);
}
***************
*** 1288,1293 ****
--- 1338,1348 ----
return a1;
}
+ /*
+ * To avoid inaccuracy at the cardinal points, use trig functions
+ * which are exact for those angles
+ */
+
# define Dsin(d) ((d) == 0.0 ? 0.0 : ((d) == 90.0 ? 1.0 : sin(d*M_PI/180.0)))
# define Dcos(d) ((d) == 0.0 ? 1.0 : ((d) == 90.0 ? 0.0 : cos(d*M_PI/180.0)))
***************
*** 1330,1338 ****
}
/*
! * draw zero width/height arcs with the rectangle routines
*/
drawZeroArc (pDraw, pGC, tarc, left, right)
DrawablePtr pDraw;
GCPtr pGC;
--- 1385,1403 ----
}
/*
! * scan convert wide arcs.
*/
+ #undef fabs
+ #undef min
+ #undef max
+
+ extern double ceil (), floor (), fabs (), sin (), cos (), sqrt (), pow ();
+
+ /*
+ * draw zero width/height arcs
+ */
+
drawZeroArc (pDraw, pGC, tarc, left, right)
DrawablePtr pDraw;
GCPtr pGC;
***************
*** 1342,1348 ****
double x0, y0, x1, y1, w, h;
int a0, a1;
double startAngle, endAngle;
- SppPointRec box[4];
double l;
l = pGC->lineWidth;
--- 1407,1412 ----
***************
*** 1386,1401 ****
}
}
if (x1 != x0 && y1 != y0) {
! box[0].x = x0;
! box[0].y = y0;
! box[1].x = x1;
! box[1].y = y0;
! box[2].x = x1;
! box[2].y = y1;
! box[3].x = x0;
! box[3].y = y1;
! miFillSppPoly (pDraw, pGC, 4, box, tarc.x, tarc.y,
! w, h);
}
if (right) {
if (h != 0) {
--- 1450,1481 ----
}
}
if (x1 != x0 && y1 != y0) {
! int minx, maxx, miny, maxy, y, t;
! xRectangle rect;
!
! minx = ceil (x0 + w) + tarc.x;
! maxx = ceil (x1 + w) + tarc.x;
! if (minx > maxx) {
! t = minx;
! minx = maxx;
! maxx = t;
! }
! miny = ceil (y0 + h) + tarc.y;
! maxy = ceil (y1 + h) + tarc.y;
! if (miny > maxy) {
! t = miny;
! miny = maxy;
! maxy = t;
! }
! rect.x = minx;
! rect.y = miny;
! rect.width = maxx - minx;
! rect.height = maxy - miny;
! (*pGC->PolyFillRect) (pDraw, pGC, 1, &rect);
! /*
! for (y = miny; y < maxy; y++)
! newFinalSpan (y, minx, maxx);
! */
}
if (right) {
if (h != 0) {
***************
*** 1433,1449 ****
}
}
-
- /*
- * scan convert wide arcs.
- */
-
- #undef fabs
- #undef min
- #undef max
-
- extern double ceil (), floor (), fabs (), sin (), cos (), sqrt (), pow ();
-
# define BINARY_LIMIT (0.1)
# define NEWTON_LIMIT (0.0000001)
--- 1513,1518 ----
***************
*** 1512,1530 ****
return a < b ? a : b;
}
! boundedLt (value, bounds)
! double value;
! struct bound bounds;
! {
! return bounds.min <= value && value < bounds.max;
! }
! boundedLe (value, bounds)
! double value;
! struct bound bounds;
! {
! return bounds.min <= value && value <= bounds.max;
! }
/*
* this computes the elipse y value associated with the
--- 1581,1591 ----
return a < b ? a : b;
}
! #define boundedLt(value, bounds) \
! ((bounds).min <= (value) && (value) < (bounds).max)
! #define boundedLe(value, bounds)\
! ((bounds).min <= (value) && (value) <= (bounds).max)
/*
* this computes the elipse y value associated with the
***************
*** 1673,1678 ****
--- 1734,1745 ----
return line->m * y + line->b;
}
+ /*
+ * compute various accelerators for an elipse. These
+ * are simply values that are used repeatedly in
+ * the computations
+ */
+
computeAcc (def, acc)
struct arc_def *def;
struct accelerators *acc;
***************
*** 1687,1692 ****
--- 1754,1764 ----
acc->tail_y = tailElipseY (def->w, def->h, def->l);
}
+ /*
+ * compute y value bounds of various portions of the arc,
+ * the outer edge, the elipse and the inner edge.
+ */
+
computeBound (def, bound, acc, right, left)
struct arc_def *def;
struct arc_bound *bound;
***************
*** 1721,1727 ****
/*
* save the line end points for the
! * cap code to use
*/
if (right) {
--- 1793,1802 ----
/*
* save the line end points for the
! * cap code to use. Careful here, these are
! * in cartesean coordinates (y increasing upwards)
! * while the cap code uses inverted coordinates
! * (y increasing downwards)
*/
if (right) {
***************
*** 1772,1778 ****
/*
* using newtons method and a binary search, compute the elipse y value
* associated with the given edge value (either outer or
! * inner)
*/
double
--- 1847,1881 ----
/*
* using newtons method and a binary search, compute the elipse y value
* associated with the given edge value (either outer or
! * inner). This is the heart of the scan conversion code and
! * is generally called three times for each span. It should
! * be optimized further.
! *
! * the general idea here is to solve the equation:
! *
! * w^2 * l
! * edge_y = y + y * -------------------------------
! * 2 * sqrt (x^2 * h^4 + y^2 * w^4)
! *
! * for y. (x, y) is a point on the elipse, so x can be
! * found from y:
! *
! * ( h^2 - y^2 )
! * x = w * sqrt ( --------- )
! * ( h^2 )
! *
! * The information given at the start of the search
! * is two points which are known to bound the desired
! * solution, a binary search starts with these two points
! * and converges close to a solution, which is then
! * refined with newtons method. Newtons method
! * cannot be used in isolation as it does not always
! * converge to the desired solution without a close
! * starting point, the binary search simply provides
! * that point. Increasing the solution interval for
! * the binary search will certainly speed up the
! * solution, but may generate a range which causes
! * the newtons method to fail. This needs study.
*/
double
***************
*** 1781,1794 ****
struct arc_def *def;
struct arc_bound *bound;
struct accelerators *acc;
! double y0, y1;
{
! double w, h, l, h2, h4, w2, w4, x, y2;
! double newtony, binaryy;
! double value0, value1, valuealt;
! double newtonvalue, binaryvalue;
! double minY, maxY;
! double (*f)();
/*
* compute some accelerators
--- 1884,1898 ----
struct arc_def *def;
struct arc_bound *bound;
struct accelerators *acc;
! register double y0, y1;
{
! register double w, h, l, h2, h4, w2, w4, x, y2;
! double newtony, binaryy;
! double value0, value1, valuealt;
! double newtonvalue, binaryvalue;
! double minY, maxY;
! double binarylimit;
! double (*f)();
/*
* compute some accelerators
***************
*** 1816,1821 ****
--- 1920,1928 ----
return y1;
if (value1 > 0 == value0 > 0)
return -1.0; /* an illegal value */
+ binarylimit = fabs ((value1 - value0) / 25.0);
+ if (binarylimit < BINARY_LIMIT)
+ binarylimit = BINARY_LIMIT;
/*
* binary search for a while
*/
***************
*** 1834,1841 ****
binaryvalue = ( binaryy + (binaryy * w2 * l) /
(2 * Sqrt (x*x * h4 + y2 * w4))) - edge_y;
- if (binaryvalue == 0)
- return binaryy;
if (binaryvalue > 0 == value0 > 0) {
y0 = binaryy;
value0 = binaryvalue;
--- 1941,1946 ----
***************
*** 1843,1849 ****
y1 = binaryy;
value1 = binaryvalue;
}
! } while (fabs (value1) > BINARY_LIMIT);
/*
* clean up the estimate with newtons method
--- 1948,1956 ----
y1 = binaryy;
value1 = binaryvalue;
}
! } while (fabs (value1) > binarylimit);
! if (binaryvalue == 0)
! return binaryy;
/*
* clean up the estimate with newtons method
***************
*** 1889,1901 ****
double
outerX (outer_y, def, bound, acc)
! double outer_y;
! struct arc_def *def;
struct arc_bound *bound;
struct accelerators *acc;
{
double y;
if (outer_y == bound->outer.min)
y = bound->elipse.min;
if (outer_y == bound->outer.max)
--- 1996,2018 ----
double
outerX (outer_y, def, bound, acc)
! register double outer_y;
! register struct arc_def *def;
struct arc_bound *bound;
struct accelerators *acc;
{
double y;
+ /*
+ * special case for circles
+ */
+ if (def->w == def->h) {
+ register double x;
+
+ x = def->w + def->l/2.0;
+ x = Sqrt (x * x - outer_y * outer_y);
+ return x;
+ }
if (outer_y == bound->outer.min)
y = bound->elipse.min;
if (outer_y == bound->outer.max)
***************
*** 1902,1908 ****
y = bound->elipse.max;
else
y = elipseY (outer_y, def, bound, acc, 1,
! bound->elipse.min, bound->elipse.max, -1.0);
return outerXfromY (y, def, acc);
}
--- 2019,2025 ----
y = bound->elipse.max;
else
y = elipseY (outer_y, def, bound, acc, 1,
! bound->elipse.min, bound->elipse.max);
return outerXfromY (y, def, acc);
}
***************
*** 1911,1924 ****
*/
innerXs (inner_y, def, bound, acc, innerX1p, innerX2p)
! double inner_y;
struct arc_def *def;
struct arc_bound *bound;
struct accelerators *acc;
double *innerX1p, *innerX2p;
{
! double x1, x2, xalt, y0, y1, altY, elipse_y1, elipse_y2;
if (boundedLe (acc->tail_y, bound->elipse)) {
if (def->h > def->w) {
y0 = bound->elipse.min;
--- 2028,2053 ----
*/
innerXs (inner_y, def, bound, acc, innerX1p, innerX2p)
! register double inner_y;
struct arc_def *def;
struct arc_bound *bound;
struct accelerators *acc;
double *innerX1p, *innerX2p;
{
! register double x1, x2;
! double xalt, y0, y1, altY, elipse_y1, elipse_y2;
+ /*
+ * special case for circles
+ */
+ if (def->w == def->h) {
+ x1 = def->w - def->l/2.0;
+ x2 = Sqrt (x1 * x1 - inner_y * inner_y);
+ if (x1 < 0)
+ x2 = -x2;
+ *innerX1p = *innerX2p = x2;
+ return;
+ }
if (boundedLe (acc->tail_y, bound->elipse)) {
if (def->h > def->w) {
y0 = bound->elipse.min;
***************
*** 2048,2068 ****
double elipse_y, elipse_x, x, xalt;
double maxMin;
! elipse_y = hookElipseY (scan_y, def, bound, acc, left);
! if (boundedLe (elipse_y, bound->elipse)) {
! /*
! * compute the value of the second
! * derivative
! */
! maxMin = elipse_y*elipse_y*elipse_y * acc->h2mw2 -
! acc->h2 * scan_y * (3 * elipse_y*elipse_y - 2*acc->h2);
! if ((left && maxMin > 0) || (!left && maxMin < 0)) {
! if (elipse_y == 0)
! return def->w + left ? -def->l/2 : def->l/2;
! x = (acc->h2 * scan_y - elipse_y * acc->h2mw2) *
! Sqrt (acc->h2 - elipse_y * elipse_y) /
! (def->h * def->w * elipse_y);
! return x;
}
}
if (left) {
--- 2177,2199 ----
double elipse_y, elipse_x, x, xalt;
double maxMin;
! if (def->w != def->h) {
! elipse_y = hookElipseY (scan_y, def, bound, acc, left);
! if (boundedLe (elipse_y, bound->elipse)) {
! /*
! * compute the value of the second
! * derivative
! */
! maxMin = elipse_y*elipse_y*elipse_y * acc->h2mw2 -
! acc->h2 * scan_y * (3 * elipse_y*elipse_y - 2*acc->h2);
! if ((left && maxMin > 0) || (!left && maxMin < 0)) {
! if (elipse_y == 0)
! return def->w + left ? -def->l/2 : def->l/2;
! x = (acc->h2 * scan_y - elipse_y * acc->h2mw2) *
! Sqrt (acc->h2 - elipse_y * elipse_y) /
! (def->h * def->w * elipse_y);
! return x;
! }
}
}
if (left) {
***************
*** 2087,2092 ****
--- 2218,2228 ----
return x;
}
+ /*
+ * generate the set of spans with
+ * the given y coordinate
+ */
+
arcSpan (y, def, bounds, acc)
double y;
struct arc_def *def;
***************
*** 2159,2174 ****
int min, max; /* x values */
};
fillSpans (pDrawable, pGC)
DrawablePtr pDrawable;
GCPtr pGC;
{
! struct finalSpan **f;
! struct finalSpan *span, *nextspan;
! DDXPointPtr xSpans, xSpan;
! int *xWidths, *xWidth;
! int i;
! int spany;
if (nspans == 0)
return;
--- 2295,2365 ----
int min, max; /* x values */
};
+ static struct finalSpan *freeFinalSpans, *tmpFinalSpan;
+
+ # define allocFinalSpan() (freeFinalSpans ?\
+ ((tmpFinalSpan = freeFinalSpans), \
+ (freeFinalSpans = freeFinalSpans->next), \
+ (tmpFinalSpan->next = 0), \
+ tmpFinalSpan) : \
+ realAllocSpan ())
+
+ # define SPAN_CHUNK_SIZE 128
+
+ struct finalSpanChunk {
+ struct finalSpan data[SPAN_CHUNK_SIZE];
+ struct finalSpanChunk *next;
+ };
+
+ static struct finalSpanChunk *chunks;
+
+ struct finalSpan *
+ realAllocSpan ()
+ {
+ register struct finalSpanChunk *newChunk;
+ register struct finalSpan *span;
+ register int i;
+
+ newChunk = (struct finalSpanChunk *) Xalloc (sizeof (struct finalSpanChunk));
+ if (!newChunk)
+ return (struct finalSpan *) Xalloc (sizeof (struct finalSpan));
+ newChunk->next = chunks;
+ chunks = newChunk;
+ freeFinalSpans = span = newChunk->data + 1;
+ for (i = 1; i < SPAN_CHUNK_SIZE-1; i++) {
+ span->next = span+1;
+ span++;
+ }
+ span->next = 0;
+ span = newChunk->data;
+ span->next = 0;
+ return span;
+ }
+
+ disposeFinalSpans ()
+ {
+ struct finalSpanChunk *chunk, *next;
+
+ for (chunk = chunks; chunk; chunk = next) {
+ next = chunk->next;
+ Xfree (chunk);
+ }
+ chunks = 0;
+ freeFinalSpans = 0;
+ }
+
fillSpans (pDrawable, pGC)
DrawablePtr pDrawable;
GCPtr pGC;
{
! register struct finalSpan *span;
! register DDXPointPtr xSpan;
! register int *xWidth;
! register int i;
! register struct finalSpan **f;
! register int spany;
! DDXPointPtr xSpans;
! int *xWidths;
if (nspans == 0)
return;
***************
*** 2177,2194 ****
i = 0;
f = finalSpans;
for (spany = finalMiny; spany < finalMaxy; spany++, f++) {
! for (span = *f; span; span=nextspan) {
! nextspan = span->next;
! if (span->max > span->min) {
! xSpan->x = span->min;
! xSpan->y = spany;
! ++xSpan;
! *xWidth++ = span->max - span->min;
! ++i;
}
! Xfree (span);
}
}
Xfree (finalSpans);
(*pGC->FillSpans) (pDrawable, pGC, i, xSpans, xWidths, TRUE);
Xfree (xSpans);
--- 2368,2386 ----
i = 0;
f = finalSpans;
for (spany = finalMiny; spany < finalMaxy; spany++, f++) {
! for (span = *f; span; span=span->next) {
! if (span->max <= span->min) {
! printf ("span width: %d\n", span->max-span->min);
! continue;
}
! xSpan->x = span->min;
! xSpan->y = spany;
! ++xSpan;
! *xWidth++ = span->max - span->min;
! ++i;
}
}
+ disposeFinalSpans ();
Xfree (finalSpans);
(*pGC->FillSpans) (pDrawable, pGC, i, xSpans, xWidths, TRUE);
Xfree (xSpans);
***************
*** 2200,2214 ****
nspans = 0;
}
! # define SPAN_REALLOC 2048
struct finalSpan **
! findSpan (y)
{
struct finalSpan **newSpans;
int newSize, newMiny, newMaxy;
- int i;
int change;
if (y < finalMiny || y >= finalMaxy) {
if (y < finalMiny)
--- 2392,2410 ----
nspans = 0;
}
! # define SPAN_REALLOC 1024
+ # define findSpan(y) ((finalMiny <= (y) && (y) < finalMaxy) ? \
+ &finalSpans[(y) - finalMiny] : \
+ realFindSpan (y))
+
struct finalSpan **
! realFindSpan (y)
{
struct finalSpan **newSpans;
int newSize, newMiny, newMaxy;
int change;
+ int i;
if (y < finalMiny || y >= finalMaxy) {
if (y < finalMiny)
***************
*** 2234,2243 ****
finalSize * sizeof (struct finalSpan *));
Xfree (finalSpans);
}
! for (i = newMiny; i < finalMiny; i++)
! newSpans[i-newMiny] = 0;
! for (i = finalMaxy; i < newMaxy; i++)
! newSpans[i-newMiny] = 0;
finalSpans = newSpans;
finalMaxy = newMaxy;
finalMiny = newMiny;
--- 2430,2440 ----
finalSize * sizeof (struct finalSpan *));
Xfree (finalSpans);
}
! if ((i = finalMiny - newMiny) > 0)
! bzero (newSpans, i * sizeof (struct finalSpan *));
! if ((i = newMaxy - finalMaxy) > 0)
! bzero (newSpans + finalMaxy - newMiny,
! i * sizeof (struct finalSpan *));
finalSpans = newSpans;
finalMaxy = newMaxy;
finalMiny = newMiny;
***************
*** 2247,2255 ****
}
newFinalSpan (y, xmin, xmax)
{
! struct finalSpan **f;
! struct finalSpan *x, *oldx, *prev;
f = findSpan (y);
oldx = 0;
--- 2444,2456 ----
}
newFinalSpan (y, xmin, xmax)
+ int y;
+ register int xmin, xmax;
{
! register struct finalSpan *x;
! register struct finalSpan **f;
! struct finalSpan *oldx;
! struct finalSpan *prev;
f = findSpan (y);
oldx = 0;
***************
*** 2269,2275 ****
else
*f = x->next;
--nspans;
- Xfree (x);
} else {
x->min = min (x->min, xmin);
x->max = max (x->max, xmax);
--- 2470,2475 ----
***************
*** 2285,2291 ****
break;
}
if (!oldx) {
! x = (struct finalSpan *) Xalloc (sizeof (struct finalSpan));
x->min = xmin;
x->max = xmax;
x->next = *f;
--- 2485,2491 ----
break;
}
if (!oldx) {
! x = allocFinalSpan ();
x->min = xmin;
x->max = xmax;
x->next = *f;
***************
*** 2318,2371 ****
sppPoint->y = -sppPoint->y;
}
! mirrorSpan (quadrant, y, min, max)
! double y;
! double min, max;
! {
! int spany, xmin, xmax;
! double t;
- switch (quadrant) {
- case 0:
- break;
- case 1:
- t = -max;
- max = -min;
- min = t;
- break;
- case 2:
- t = -max;
- max = -min;
- min = t;
- y = -y;
- break;
- case 3:
- y = -y;
- break;
- }
- xmin = (int) ceil (min + arcXcenter) + arcXoffset;
- xmax = (int) ceil (max + arcXcenter) + arcXoffset;
- spany = (int) (ceil (arcYcenter - y)) + arcYoffset;
- if (xmax > xmin)
- newFinalSpan (spany, xmin, xmax);
- }
-
static int quadrantMask;
! mergeSpan (y, min, max)
! double y, min, max;
{
! if (quadrantMask & 1)
! mirrorSpan (0, y, min, max);
! if (quadrantMask & 2)
! mirrorSpan (1, y, min, max);
! if (quadrantMask & 4)
! mirrorSpan (2, y, min, max);
! if (quadrantMask & 8)
! mirrorSpan (3, y, min, max);
}
! static double spanY;
drawArc (x0, y0, w, h, l, a0, a1, right, left)
int x0, y0, w, h, l, a0, a1;
--- 2518,2577 ----
sppPoint->y = -sppPoint->y;
}
! static double spanY;
static int quadrantMask;
! span (left, right)
! double left, right;
{
! register int mask = quadrantMask, bit;
! register double min, max, y;
! int xmin, xmax, spany;
!
! while (mask) {
! bit = lowbit (mask);
! mask &= ~bit;
! switch (bit) {
! case 1:
! min = left;
! max = right;
! y = spanY;
! break;
! case 2:
! min = -right;
! max = -left;
! y = spanY;
! break;
! case 4:
! min = -right;
! max = -left;
! y = -spanY;
! break;
! case 8:
! min = left;
! max = right;
! y = -spanY;
! break;
! default:
! abort ();
! }
! xmin = (int) ceil (min + arcXcenter) + arcXoffset;
! xmax = (int) ceil (max + arcXcenter) + arcXoffset;
! spany = (int) (ceil (arcYcenter - y)) + arcYoffset;
!
! if (xmax > xmin)
! newFinalSpan (spany, xmin, xmax);
! }
}
! /*
! * split an arc into pieces which are scan-converted
! * in the first-quadrant and mirrored into position.
! * This is necessary as the scan-conversion code can
! * only deal with arcs completely contained in the
! * first quadrant.
! */
drawArc (x0, y0, w, h, l, a0, a1, right, left)
int x0, y0, w, h, l, a0, a1;
***************
*** 2555,2560 ****
--- 2761,2770 ----
drawQuadrant (&def, &acc, sweep[j].a0, sweep[j].a1, mask,
passRight, passLeft);
}
+ /*
+ * mirror the coordinates generated for the
+ * faces of the arc
+ */
if (right) {
mirrorSppPoint (rightq, &right->clock);
mirrorSppPoint (rightq, &right->center);
***************
*** 2611,2618 ****
/*
* add the pixel at the top of the arc
*/
! if (a1 == 90 * 64 && (quadrantMask & 1) && ((int) (def->w * 2 + def->l)) & 1)
! mirrorSpan (0, def->h + def->l/2, 0.0, 1.0);
}
max (x, y)
--- 2821,2831 ----
/*
* add the pixel at the top of the arc
*/
! if (a1 == 90 * 64 && (mask & 1) && ((int) (def->w * 2 + def->l)) & 1) {
! quadrantMask = 1;
! spanY = def->h + def->l/2;
! span (0.0, 1.0);
! }
}
max (x, y)
***************
*** 2625,2632 ****
return x<y? x:y;
}
- span (left, right)
- double left, right;
- {
- mergeSpan (spanY, left, right);
- }
--- 2838,2840 ----
--
Mike Wexler(wyse!mikew) Phone: (408)433-1000 x1330
Moderator of comp.sources.x
More information about the Comp.sources.x
mailing list