mikew@wyse.wyse.com (Mike Wexler) (12/13/88)
Submitted-by: Xstuff service <xstuff@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