1 /************************************************************
3 Copyright (c) 1989 X Consortium
5 Permission is hereby granted, free of charge, to any person obtaining a copy
6 of this software and associated documentation files (the "Software"), to deal
7 in the Software without restriction, including without limitation the rights
8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 copies of the Software, and to permit persons to whom the Software is
10 furnished to do so, subject to the following conditions:
12 The above copyright notice and this permission notice shall be included in
13 all copies or substantial portions of the Software.
15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
19 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 Except as contained in this notice, the name of the X Consortium shall not be
23 used in advertising or otherwise to promote the sale, use or other dealings
24 in this Software without prior written authorization from the X Consortium.
26 Author: Bob Scheifler, MIT X Consortium
28 ********************************************************/
30 /* $XConsortium: mizerarc.c,v 5.36 94/04/17 20:28:04 dpw Exp $ */
33 * "Algorithm for drawing ellipses or hyperbolae with a digital plotter"
34 * by M. L. V. Pitteway
35 * The Computer Journal, November 1967, Volume 10, Number 3, pp. 282-289
40 #include "Xprotostr.h"
41 #include "miscstruct.h"
43 #include "pixmapstr.h"
47 #define FULLCIRCLE (360 * 64)
48 #define OCTANT (45 * 64)
49 #define QUADRANT (90 * 64)
50 #define HALFCIRCLE (180 * 64)
51 #define QUADRANT3 (270 * 64)
54 #define M_PI 3.14159265358979323846
57 #define Dsin(d) ((d) == 0 ? 0.0 : ((d) == QUADRANT ? 1.0 : \
58 ((d) == HALFCIRCLE ? 0.0 : \
59 ((d) == QUADRANT3 ? -1.0 : sin((double)d*(M_PI/11520.0))))))
61 #define Dcos(d) ((d) == 0 ? 1.0 : ((d) == QUADRANT ? 0.0 : \
62 ((d) == HALFCIRCLE ? -1.0 : \
63 ((d) == QUADRANT3 ? 0.0 : cos((double)d*(M_PI/11520.0))))))
80 static miZeroArcPtRec oob = {65536, 65536, 0};
83 * (x - l)^2 / (W/2)^2 + (y + H/2)^2 / (H/2)^2 = 1
85 * where l is either 0 or .5
97 miZeroArcSetup(arc, info, ok360)
99 register miZeroArcRec *info;
104 int startseg, endseg;
105 int startAngle, endAngle;
107 miZeroArcPtRec start, end;
110 if (arc->width == arc->height)
117 info->a = (arc->width << 2) - 12;
118 info->d = 17 - (arc->width << 1);
126 else if (!arc->width || !arc->height)
132 info->a = -(int)arc->height;
138 /* initial conditions */
139 info->alpha = (arc->width * arc->width) << 2;
140 info->beta = (arc->height * arc->height) << 2;
141 info->k1 = info->beta << 1;
142 info->k3 = info->k1 + (info->alpha << 1);
143 info->b = l ? 0 : -info->beta;
144 info->a = info->alpha * arc->height;
145 info->d = info->b - (info->a >> 1) - (info->alpha >> 2);
147 info->d -= info->beta >> 2;
149 /* take first step, d < 0 always */
153 /* octant change, b < 0 always */
154 info->k1 = -info->k1;
155 info->k3 = -info->k3;
157 info->d = info->b - info->a - info->d;
158 info->a = info->a - (info->b << 1);
162 info->w = (arc->width + 1) >> 1;
163 info->h = arc->height >> 1;
164 info->xorg = arc->x + (arc->width >> 1);
166 info->xorgo = info->xorg + l;
167 info->yorgo = info->yorg + arc->height;
174 info->initialMask = 0;
175 info->startAngle = 0;
189 angle1 = arc->angle1;
190 angle2 = arc->angle2;
191 if ((angle1 == 0) && (angle2 >= FULLCIRCLE))
198 if (angle2 > FULLCIRCLE)
200 else if (angle2 < -FULLCIRCLE)
201 angle2 = -FULLCIRCLE;
204 startAngle = angle1 + angle2;
210 endAngle = angle1 + angle2;
213 startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
214 if (startAngle >= FULLCIRCLE)
215 startAngle = startAngle % FULLCIRCLE;
217 endAngle = FULLCIRCLE - (-endAngle) % FULLCIRCLE;
218 if (endAngle >= FULLCIRCLE)
219 endAngle = endAngle % FULLCIRCLE;
221 info->startAngle = startAngle;
222 info->endAngle = endAngle;
223 if (ok360 && (startAngle == endAngle) && arc->angle2 &&
224 arc->width && arc->height)
226 info->initialMask = 0xf;
231 startseg = startAngle / OCTANT;
232 if (!arc->height || (((startseg + 1) & 2) && arc->width))
234 start.x = Dcos(startAngle) * ((arc->width + 1) / 2.0);
241 start.y = Dsin(startAngle) * (arc->height / 2.0);
244 start.y = info->h - start.y;
247 endseg = endAngle / OCTANT;
248 if (!arc->height || (((endseg + 1) & 2) && arc->width))
250 end.x = Dcos(endAngle) * ((arc->width + 1) / 2.0);
257 end.y = Dsin(endAngle) * (arc->height / 2.0);
260 end.y = info->h - end.y;
263 info->firstx = start.x;
264 info->firsty = start.y;
265 info->initialMask = 0;
266 overlap = arc->angle2 && (endAngle <= startAngle);
267 for (i = 0; i < 4; i++)
270 ((i * QUADRANT <= endAngle) || ((i + 1) * QUADRANT > startAngle)) :
271 ((i * QUADRANT <= endAngle) && ((i + 1) * QUADRANT > startAngle)))
272 info->initialMask |= (1 << i);
274 start.mask = info->initialMask;
275 end.mask = info->initialMask;
278 overlap = overlap && (endseg == startseg);
279 if (start.x != end.x || start.y != end.y || !overlap)
284 info->initialMask &= ~(1 << startseg);
285 if (start.x > end.x || start.y > end.y)
286 end.mask &= ~(1 << startseg);
290 start.mask &= ~(1 << startseg);
291 if (((start.x < end.x || start.y < end.y) ||
292 (start.x == end.x && start.y == end.y && (endseg & 1))) &&
294 end.mask &= ~(1 << startseg);
298 end.mask &= ~(1 << endseg);
299 if (((start.x > end.x || start.y > end.y) ||
300 (start.x == end.x && start.y == end.y && !(startseg & 1))) &&
302 start.mask &= ~(1 << endseg);
307 info->initialMask &= ~(1 << endseg);
308 if (start.x < end.x || start.y < end.y)
309 start.mask &= ~(1 << endseg);
312 /* take care of case when start and stop are both near 45 */
313 /* handle here rather than adding extra code to pixelization loops */
315 ((start.y < 0 && end.y >= 0) || (start.y >= 0 && end.y < 0)))
317 i = (startAngle + OCTANT) % OCTANT;
318 if (i < EPSILON45 || i > OCTANT - EPSILON45)
320 i = (endAngle + OCTANT) % OCTANT;
321 if (i < EPSILON45 || i > OCTANT - EPSILON45)
325 i = Dsin(startAngle) * (arc->height / 2.0);
328 if (info->h - i == end.y)
329 start.mask = end.mask;
333 i = Dsin(endAngle) * (arc->height / 2.0);
336 if (info->h - i == start.y)
337 end.mask = start.mask;
355 if (info->altend.x < info->end.x || info->altend.y < info->end.y)
359 info->altend = info->end;
362 info->altstart = oob;
366 info->altstart = end;
367 if (info->altstart.x < info->start.x ||
368 info->altstart.y < info->start.y)
371 tmp = info->altstart;
372 info->altstart = info->start;
377 if (!info->start.x || !info->start.y)
379 info->initialMask = info->start.mask;
380 info->start = info->altstart;
382 if (!arc->width && (arc->height == 1))
385 info->initialMask |= info->end.mask;
386 info->initialMask |= info->initialMask << 1;
393 #define Pixelate(xval,yval) \
400 #define DoPix(idx,xval,yval) if (mask & (1 << idx)) Pixelate(xval, yval);
403 miZeroArcPts(arc, pts)
405 register DDXPointPtr pts;
408 register int x, y, a, b, d, mask;
409 register int k1, k3, dx, dy;
412 do360 = miZeroArcSetup(arc, &info, TRUE);
414 mask = info.initialMask;
415 if (!(arc->width & 1))
417 DoPix(1, info.xorgo, info.yorg);
418 DoPix(3, info.xorgo, info.yorgo);
420 if (!info.end.x || !info.end.y)
422 mask = info.end.mask;
423 info.end = info.altend;
425 if (do360 && (arc->width == arc->height) && !(arc->width & 1))
427 int yorgh = info.yorg + info.h;
428 int xorghp = info.xorg + info.h;
429 int xorghn = info.xorg - info.h;
433 Pixelate(info.xorg + x, info.yorg + y);
434 Pixelate(info.xorg - x, info.yorg + y);
435 Pixelate(info.xorg - x, info.yorgo - y);
436 Pixelate(info.xorg + x, info.yorgo - y);
439 Pixelate(xorghp - y, yorgh - x);
440 Pixelate(xorghn + y, yorgh - x);
441 Pixelate(xorghn + y, yorgh + x);
442 Pixelate(xorghp - y, yorgh + x);
445 if (x > 1 && pts[-1].x == pts[-5].x && pts[-1].y == pts[-5].y)
452 while (y < info.h || x < info.w)
455 Pixelate(info.xorg + x, info.yorg + y);
456 Pixelate(info.xorgo - x, info.yorg + y);
457 Pixelate(info.xorgo - x, info.yorgo - y);
458 Pixelate(info.xorg + x, info.yorgo - y);
464 while (y < info.h || x < info.w)
467 if ((x == info.start.x) || (y == info.start.y))
469 mask = info.start.mask;
470 info.start = info.altstart;
472 DoPix(0, info.xorg + x, info.yorg + y);
473 DoPix(1, info.xorgo - x, info.yorg + y);
474 DoPix(2, info.xorgo - x, info.yorgo - y);
475 DoPix(3, info.xorg + x, info.yorgo - y);
476 if ((x == info.end.x) || (y == info.end.y))
478 mask = info.end.mask;
479 info.end = info.altend;
484 if ((x == info.start.x) || (y == info.start.y))
485 mask = info.start.mask;
486 DoPix(0, info.xorg + x, info.yorg + y);
487 DoPix(2, info.xorgo - x, info.yorgo - y);
490 DoPix(1, info.xorgo - x, info.yorg + y);
491 DoPix(3, info.xorg + x, info.yorgo - y);
497 #define DoPix(idx,xval,yval) \
498 if (mask & (1 << idx)) \
500 arcPts[idx]->x = xval; \
501 arcPts[idx]->y = yval; \
506 miZeroArcDashPts(pGC, arc, dinfo, points, maxPts, evenPts, oddPts)
511 register DDXPointPtr points, *evenPts, *oddPts;
514 register int x, y, a, b, d, mask;
515 register int k1, k3, dx, dy;
517 DDXPointPtr arcPts[4];
518 DDXPointPtr startPts[5], endPts[5];
520 DDXPointPtr startPt, pt, lastPt, pts;
521 int i, j, delta, ptsdelta, seg, startseg;
523 for (i = 0; i < 4; i++)
524 arcPts[i] = points + (i * maxPts);
525 (void)miZeroArcSetup(arc, &info, FALSE);
527 mask = info.initialMask;
528 startseg = info.startAngle / QUADRANT;
529 startPt = arcPts[startseg];
530 if (!(arc->width & 1))
532 DoPix(1, info.xorgo, info.yorg);
533 DoPix(3, info.xorgo, info.yorgo);
535 if (!info.end.x || !info.end.y)
537 mask = info.end.mask;
538 info.end = info.altend;
540 while (y < info.h || x < info.w)
543 if ((x == info.firstx) || (y == info.firsty))
544 startPt = arcPts[startseg];
545 if ((x == info.start.x) || (y == info.start.y))
547 mask = info.start.mask;
548 info.start = info.altstart;
550 DoPix(0, info.xorg + x, info.yorg + y);
551 DoPix(1, info.xorgo - x, info.yorg + y);
552 DoPix(2, info.xorgo - x, info.yorgo - y);
553 DoPix(3, info.xorg + x, info.yorgo - y);
554 if ((x == info.end.x) || (y == info.end.y))
556 mask = info.end.mask;
557 info.end = info.altend;
561 if ((x == info.firstx) || (y == info.firsty))
562 startPt = arcPts[startseg];
563 if ((x == info.start.x) || (y == info.start.y))
564 mask = info.start.mask;
565 DoPix(0, info.xorg + x, info.yorg + y);
566 DoPix(2, info.xorgo - x, info.yorgo - y);
569 DoPix(1, info.xorgo - x, info.yorg + y);
570 DoPix(3, info.xorg + x, info.yorgo - y);
572 for (i = 0; i < 4; i++)
574 seg = (startseg + i) & 3;
575 pt = points + (seg * maxPts);
579 endPts[i] = arcPts[seg];
584 startPts[i] = arcPts[seg] - 1;
589 startPts[4] = startPts[0];
591 startPts[0] = startPt;
594 if (startPts[4] != endPts[4])
600 if (startPts[0] > startPts[4])
602 if (startPts[4] < endPts[4])
608 DDXPointPtr tmps, tmpe;
612 tmps = startPts[0] - tmpd;
613 tmpe = endPts[0] - tmpd;
614 startPts[0] = endPts[4] - deltas[4];
615 endPts[0] = startPts[4] - deltas[4];
616 deltas[0] = -deltas[4];
621 tmps = startPts[1] - tmpd;
622 tmpe = endPts[1] - tmpd;
623 startPts[1] = endPts[3] - deltas[3];
624 endPts[1] = startPts[3] - deltas[3];
625 deltas[1] = -deltas[3];
629 tmps = startPts[2] - deltas[2];
630 startPts[2] = endPts[2] - deltas[2];
632 deltas[2] = -deltas[2];
634 for (i = 0; i < 5 && startPts[i] == endPts[i]; i++)
639 for (j = 4; startPts[j] == endPts[j]; j--)
641 lastPt = endPts[j] - deltas[j];
642 if (dinfo->haveLast &&
643 (pt->x == dinfo->endPt.x) && (pt->y == dinfo->endPt.y))
645 startPts[i] += deltas[i];
649 dinfo->dashIndex = dinfo->dashIndexInit;
650 dinfo->dashOffset = dinfo->dashOffsetInit;
652 if (!dinfo->skipStart && (info.startAngle != info.endAngle))
654 dinfo->startPt = *pt;
655 dinfo->haveStart = TRUE;
657 else if (!dinfo->skipLast && dinfo->haveStart &&
658 (lastPt->x == dinfo->startPt.x) &&
659 (lastPt->y == dinfo->startPt.y) &&
660 (lastPt != startPts[i]))
662 if (info.startAngle != info.endAngle)
664 dinfo->haveLast = TRUE;
665 dinfo->endPt = *lastPt;
667 dashRemaining = pGC->dash[dinfo->dashIndex] - dinfo->dashOffset;
668 for (i = 0; i < 5; i++)
675 if (dinfo->dashIndex & 1)
685 while ((pt != lastPt) && --dashRemaining >= 0)
691 if (dinfo->dashIndex & 1)
695 if (dashRemaining <= 0)
697 if (++(dinfo->dashIndex) == pGC->numInDashList)
698 dinfo->dashIndex = 0;
699 dashRemaining = pGC->dash[dinfo->dashIndex];
703 dinfo->dashOffset = pGC->dash[dinfo->dashIndex] - dashRemaining;
707 miZeroPolyArc(pDraw, pGC, narcs, parcs)
714 register int n, maxw;
717 DDXPointPtr points, pts, oddPts;
718 register DDXPointPtr pt;
722 XID fgPixel = pGC->fgPixel;
725 for (arc = parcs, i = narcs; --i >= 0; arc++)
727 if (!miCanZeroArc(arc))
728 miPolyArc(pDraw, pGC, 1, arc);
731 if (arc->width > arc->height)
732 n = arc->width + (arc->height >> 1);
734 n = arc->height + (arc->width >> 1);
741 numPts = maxPts << 2;
742 dospans = (pGC->lineStyle != LineSolid) || (pGC->fillStyle != FillSolid);
745 widths = (int *)ALLOCATE_LOCAL(sizeof(int) * numPts);
750 if (pGC->lineStyle != LineSolid)
753 dinfo.haveStart = FALSE;
754 dinfo.skipStart = FALSE;
755 dinfo.haveLast = FALSE;
756 dinfo.dashIndexInit = 0;
757 dinfo.dashOffsetInit = 0;
758 miStepDash((int)pGC->dashOffset, &dinfo.dashIndexInit,
759 (unsigned char *) pGC->dash, (int)pGC->numInDashList,
760 &dinfo.dashOffsetInit);
762 points = (DDXPointPtr)ALLOCATE_LOCAL(sizeof(DDXPointRec) * numPts);
767 DEALLOCATE_LOCAL(widths);
771 for (arc = parcs, i = narcs; --i >= 0; arc++)
773 if (miCanZeroArc(arc))
775 if (pGC->lineStyle == LineSolid)
776 pts = miZeroArcPts(arc, points);
780 oddPts = &points[(numPts >> 1) - 1];
782 miZeroArcDashPts(pGC, arc, &dinfo,
783 oddPts + 1, maxPts, &pts, &oddPts);
784 dinfo.skipStart = TRUE;
788 (*pGC->ops->PolyPoint)(pDraw, pGC, CoordModeOrigin, n, points);
796 if (pGC->miTranslate)
798 for (pt = points; pt != pts; pt++)
804 (*pGC->ops->FillSpans)(pDraw, pGC, n, points, widths, FALSE);
806 if (pGC->lineStyle != LineDoubleDash)
808 if ((pGC->fillStyle == FillSolid) ||
809 (pGC->fillStyle == FillStippled))
811 DoChangeGC(pGC, GCForeground, (XID *)&pGC->bgPixel, 0);
812 ValidateGC(pDraw, pGC);
814 pts = &points[numPts >> 1];
818 (*pGC->ops->PolyPoint)(pDraw, pGC, CoordModeOrigin, n, oddPts);
826 if (pGC->miTranslate)
828 for (pt = oddPts; pt != pts; pt++)
834 (*pGC->ops->FillSpans)(pDraw, pGC, n, oddPts, widths, FALSE);
836 if ((pGC->fillStyle == FillSolid) ||
837 (pGC->fillStyle == FillStippled))
839 DoChangeGC(pGC, GCForeground, &fgPixel, 0);
840 ValidateGC(pDraw, pGC);
844 DEALLOCATE_LOCAL(points);
847 DEALLOCATE_LOCAL(widths);