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: mifillarc.c,v 5.18 95/01/10 20:59:49 kaleb Exp $ */
31 /* $XFree86: xc/programs/Xserver/mi/mifillarc.c,v 3.2 1995/01/28 16:15:52 dawes Exp $ */
35 #include "Xprotostr.h"
36 #include "miscstruct.h"
38 #include "pixmapstr.h"
41 #include "mifillarc.h"
43 #define QUADRANT (90 * 64)
44 #define HALFCIRCLE (180 * 64)
45 #define QUADRANT3 (270 * 64)
48 #define M_PI 3.14159265358979323846
51 #define Dsin(d) sin((double)d*(M_PI/11520.0))
52 #define Dcos(d) cos((double)d*(M_PI/11520.0))
55 miFillArcSetup(arc, info)
57 register miFillArcRec *info;
59 info->y = arc->height >> 1;
60 info->dy = arc->height & 1;
61 info->yorg = arc->y + info->y;
62 info->dx = arc->width & 1;
63 info->xorg = arc->x + (arc->width >> 1) + info->dx;
64 info->dx = 1 - info->dx;
65 if (arc->width == arc->height)
67 /* (2x - 2xorg)^2 = d^2 - (2y - 2yorg)^2 */
68 /* even: xorg = yorg = 0 odd: xorg = .5, yorg = -.5 */
71 info->yk = info->y << 3;
82 info->e = - (info->y << 3);
87 /* h^2 * (2x - 2xorg)^2 = w^2 * h^2 - w^2 * (2y - 2yorg)^2 */
88 /* even: xorg = yorg = 0 odd: xorg = .5, yorg = -.5 */
89 info->ym = (arc->width * arc->width) << 3;
90 info->xm = (arc->height * arc->height) << 3;
91 info->yk = info->y * info->ym;
93 info->yk -= info->ym >> 1;
97 info->e = - (info->xm >> 3);
102 info->yk += info->ym;
103 info->xk = -(info->xm >> 1);
104 info->e = info->xk - info->yk;
110 miFillArcDSetup(arc, info)
112 register miFillArcDRec *info;
114 /* h^2 * (2x - 2xorg)^2 = w^2 * h^2 - w^2 * (2y - 2yorg)^2 */
115 /* even: xorg = yorg = 0 odd: xorg = .5, yorg = -.5 */
116 info->y = arc->height >> 1;
117 info->dy = arc->height & 1;
118 info->yorg = arc->y + info->y;
119 info->dx = arc->width & 1;
120 info->xorg = arc->x + (arc->width >> 1) + info->dx;
121 info->dx = 1 - info->dx;
122 info->ym = ((double)arc->width) * (arc->width * 8);
123 info->xm = ((double)arc->height) * (arc->height * 8);
124 info->yk = info->y * info->ym;
126 info->yk -= info->ym / 2.0;
130 info->e = - (info->xm / 8.0);
135 info->yk += info->ym;
136 info->xk = -info->xm / 2.0;
137 info->e = info->xk - info->yk;
142 miGetArcEdge(arc, edge, k, top, left)
144 register miSliceEdgePtr edge;
148 register int xady, y;
150 y = arc->height >> 1;
151 if (!(arc->width & 1))
159 xady = k + y * edge->dx;
161 edge->x = - ((-xady) / edge->dy + 1);
163 edge->x = (xady - 1) / edge->dy;
164 edge->e = xady - edge->x * edge->dy;
165 if ((top && (edge->dx < 0)) || (!top && (edge->dx > 0)))
166 edge->e = edge->dy - edge->e + 1;
169 edge->x += arc->x + (arc->width >> 1);
173 edge->stepx = edge->dx / edge->dy;
174 edge->dx = edge->dx % edge->dy;
179 edge->stepx = - ((-edge->dx) / edge->dy);
180 edge->dx = (-edge->dx) % edge->dy;
184 edge->deltax = -edge->deltax;
185 edge->stepx = -edge->stepx;
190 miEllipseAngleToSlope (angle, width, height, dxp, dyp, d_dxp, d_dyp)
200 double d_dx, d_dy, scale;
201 Bool negative_dx, negative_dy;
208 *d_dxp = width / 2.0;
217 *d_dyp = - height / 2.0;
224 *d_dxp = - width / 2.0;
233 *d_dyp = height / 2.0;
237 d_dx = Dcos(angle) * width;
238 d_dy = Dsin(angle) * height;
241 *d_dyp = - d_dy / 2.0;
258 dx = floor ((d_dx * 32768) / scale + 0.5);
262 dy = floor ((d_dy * 32768) / scale + 0.5);
271 miGetPieEdge(arc, angle, edge, top, left)
274 register miSliceEdgePtr edge;
277 register int k, signdx, signdy;
280 miEllipseAngleToSlope (angle, arc->width, arc->height, &dx, &dy, 0, 0);
284 edge->x = left ? -65536 : 65536;
292 edge->x = arc->x + (arc->width >> 1);
293 if (left && (arc->width & 1))
295 else if (!left && !(arc->width & 1))
306 k = (arc->height & 1) ? dx : 0;
311 miGetArcEdge(arc, edge, k, top, left);
315 miFillArcSliceSetup(arc, slice, pGC)
317 register miArcSliceRec *slice;
320 register int angle1, angle2;
322 angle1 = arc->angle1;
326 angle1 += arc->angle2;
329 angle2 = angle1 + arc->angle2;
331 angle1 += FULLCIRCLE;
332 while (angle1 >= FULLCIRCLE)
333 angle1 -= FULLCIRCLE;
335 angle2 += FULLCIRCLE;
336 while (angle2 >= FULLCIRCLE)
337 angle2 -= FULLCIRCLE;
338 slice->min_top_y = 0;
339 slice->max_top_y = arc->height >> 1;
340 slice->min_bot_y = 1 - (arc->height & 1);
341 slice->max_bot_y = slice->max_top_y - 1;
342 slice->flip_top = FALSE;
343 slice->flip_bot = FALSE;
344 if (pGC->arcMode == ArcPieSlice)
346 slice->edge1_top = (angle1 < HALFCIRCLE);
347 slice->edge2_top = (angle2 <= HALFCIRCLE);
348 if ((angle2 == 0) || (angle1 == HALFCIRCLE))
350 if (angle2 ? slice->edge2_top : slice->edge1_top)
351 slice->min_top_y = slice->min_bot_y;
353 slice->min_top_y = arc->height;
354 slice->min_bot_y = 0;
356 else if ((angle1 == 0) || (angle2 == HALFCIRCLE))
358 slice->min_top_y = slice->min_bot_y;
359 if (angle1 ? slice->edge1_top : slice->edge2_top)
360 slice->min_bot_y = arc->height;
362 slice->min_bot_y = 0;
364 else if (slice->edge1_top == slice->edge2_top)
368 slice->flip_top = slice->edge1_top;
369 slice->flip_bot = !slice->edge1_top;
371 else if (slice->edge1_top)
373 slice->min_top_y = 1;
374 slice->min_bot_y = arc->height;
378 slice->min_bot_y = 0;
379 slice->min_top_y = arc->height;
382 miGetPieEdge(arc, angle1, &slice->edge1,
383 slice->edge1_top, !slice->edge1_top);
384 miGetPieEdge(arc, angle2, &slice->edge2,
385 slice->edge2_top, slice->edge2_top);
389 double w2, h2, x1, y1, x2, y2, dx, dy, scale;
390 int signdx, signdy, y, k;
391 Bool isInt1 = TRUE, isInt2 = TRUE;
393 w2 = (double)arc->width / 2.0;
394 h2 = (double)arc->height / 2.0;
395 if ((angle1 == 0) || (angle1 == HALFCIRCLE))
397 x1 = angle1 ? -w2 : w2;
400 else if ((angle1 == QUADRANT) || (angle1 == QUADRANT3))
403 y1 = (angle1 == QUADRANT) ? h2 : -h2;
408 x1 = Dcos(angle1) * w2;
409 y1 = Dsin(angle1) * h2;
411 if ((angle2 == 0) || (angle2 == HALFCIRCLE))
413 x2 = angle2 ? -w2 : w2;
416 else if ((angle2 == QUADRANT) || (angle2 == QUADRANT3))
419 y2 = (angle2 == QUADRANT) ? h2 : -h2;
424 x2 = Dcos(angle2) * w2;
425 y2 = Dsin(angle2) * h2;
453 if (isInt1 && isInt2)
455 slice->edge1.dx = dx * 2;
456 slice->edge1.dy = dy * 2;
460 scale = (dx > dy) ? dx : dy;
461 slice->edge1.dx = floor((dx * 32768) / scale + .5);
462 slice->edge1.dy = floor((dy * 32768) / scale + .5);
464 if (!slice->edge1.dy)
471 slice->min_top_y = y;
472 slice->min_bot_y = arc->height;
476 slice->max_bot_y = -y - (arc->height & 1);
483 slice->max_top_y = y;
486 slice->min_top_y = arc->height;
487 slice->min_bot_y = -y - (arc->height & 1);
490 slice->edge1_top = TRUE;
491 slice->edge1.x = 65536;
492 slice->edge1.stepx = 0;
494 slice->edge1.dx = -1;
495 slice->edge2 = slice->edge1;
496 slice->edge2_top = FALSE;
498 else if (!slice->edge1.dx)
502 slice->edge1.x = ceil(x1);
503 slice->edge1_top = signdy < 0;
504 slice->edge1.x += arc->x + (arc->width >> 1);
505 slice->edge1.stepx = 0;
507 slice->edge1.dx = -1;
508 slice->edge2_top = !slice->edge1_top;
509 slice->edge2 = slice->edge1;
514 slice->edge1.dx = -slice->edge1.dx;
516 slice->edge1.dx = -slice->edge1.dx;
517 k = ceil(((x1 + x2) * slice->edge1.dy - (y1 + y2) * slice->edge1.dx) / 2.0);
518 slice->edge2.dx = slice->edge1.dx;
519 slice->edge2.dy = slice->edge1.dy;
520 slice->edge1_top = signdy < 0;
521 slice->edge2_top = !slice->edge1_top;
522 miGetArcEdge(arc, &slice->edge1, k,
523 slice->edge1_top, !slice->edge1_top);
524 miGetArcEdge(arc, &slice->edge2, k,
525 slice->edge2_top, slice->edge2_top);
536 if (miFillArcLower(slw)) \
539 pts->y = yorg + y + dy; \
545 miFillEllipseI(pDraw, pGC, arc)
550 register int x, y, e;
551 int yk, xk, ym, xm, dx, dy, xorg, yorg;
555 register DDXPointPtr pts;
559 points = (DDXPointPtr)ALLOCATE_LOCAL(sizeof(DDXPointRec) * arc->height);
562 widths = (int *)ALLOCATE_LOCAL(sizeof(int) * arc->height);
565 DEALLOCATE_LOCAL(points);
568 miFillArcSetup(arc, &info);
570 if (pGC->miTranslate)
582 (*pGC->ops->FillSpans)(pDraw, pGC, pts - points, points, widths, FALSE);
583 DEALLOCATE_LOCAL(widths);
584 DEALLOCATE_LOCAL(points);
588 miFillEllipseD(pDraw, pGC, arc)
594 int xorg, yorg, dx, dy, slw;
595 double e, yk, xk, ym, xm;
598 register DDXPointPtr pts;
602 points = (DDXPointPtr)ALLOCATE_LOCAL(sizeof(DDXPointRec) * arc->height);
605 widths = (int *)ALLOCATE_LOCAL(sizeof(int) * arc->height);
608 DEALLOCATE_LOCAL(points);
611 miFillArcDSetup(arc, &info);
613 if (pGC->miTranslate)
625 (*pGC->ops->FillSpans)(pDraw, pGC, pts - points, points, widths, FALSE);
626 DEALLOCATE_LOCAL(widths);
627 DEALLOCATE_LOCAL(points);
630 #define ADDSPAN(l,r) \
636 *wids++ = r - l + 1; \
639 #define ADDSLICESPANS(flip) \
653 miFillArcSliceI(pDraw, pGC, arc)
658 int yk, xk, ym, xm, dx, dy, xorg, yorg, slw;
659 register int x, y, e;
664 register DDXPointPtr pts;
668 miFillArcSetup(arc, &info);
669 miFillArcSliceSetup(arc, &slice, pGC);
672 if (slice.flip_top || slice.flip_bot)
673 slw += (arc->height >> 1) + 1;
674 points = (DDXPointPtr)ALLOCATE_LOCAL(sizeof(DDXPointRec) * slw);
677 widths = (int *)ALLOCATE_LOCAL(sizeof(int) * slw);
680 DEALLOCATE_LOCAL(points);
683 if (pGC->miTranslate)
687 slice.edge1.x += pDraw->x;
688 slice.edge2.x += pDraw->x;
695 MIARCSLICESTEP(slice.edge1);
696 MIARCSLICESTEP(slice.edge2);
697 if (miFillSliceUpper(slice))
700 MIARCSLICEUPPER(xl, xr, slice, slw);
701 ADDSLICESPANS(slice.flip_top);
703 if (miFillSliceLower(slice))
706 MIARCSLICELOWER(xl, xr, slice, slw);
707 ADDSLICESPANS(slice.flip_bot);
710 (*pGC->ops->FillSpans)(pDraw, pGC, pts - points, points, widths, FALSE);
711 DEALLOCATE_LOCAL(widths);
712 DEALLOCATE_LOCAL(points);
716 miFillArcSliceD(pDraw, pGC, arc)
722 int dx, dy, xorg, yorg, slw;
723 double e, yk, xk, ym, xm;
728 register DDXPointPtr pts;
732 miFillArcDSetup(arc, &info);
733 miFillArcSliceSetup(arc, &slice, pGC);
736 if (slice.flip_top || slice.flip_bot)
737 slw += (arc->height >> 1) + 1;
738 points = (DDXPointPtr)ALLOCATE_LOCAL(sizeof(DDXPointRec) * slw);
741 widths = (int *)ALLOCATE_LOCAL(sizeof(int) * slw);
744 DEALLOCATE_LOCAL(points);
747 if (pGC->miTranslate)
751 slice.edge1.x += pDraw->x;
752 slice.edge2.x += pDraw->x;
759 MIARCSLICESTEP(slice.edge1);
760 MIARCSLICESTEP(slice.edge2);
761 if (miFillSliceUpper(slice))
764 MIARCSLICEUPPER(xl, xr, slice, slw);
765 ADDSLICESPANS(slice.flip_top);
767 if (miFillSliceLower(slice))
770 MIARCSLICELOWER(xl, xr, slice, slw);
771 ADDSLICESPANS(slice.flip_bot);
774 (*pGC->ops->FillSpans)(pDraw, pGC, pts - points, points, widths, FALSE);
775 DEALLOCATE_LOCAL(widths);
776 DEALLOCATE_LOCAL(points);
779 /* MIPOLYFILLARC -- The public entry for the PolyFillArc request.
780 * Since we don't have to worry about overlapping segments, we can just
781 * fill each arc as it comes.
784 miPolyFillArc(pDraw, pGC, narcs, parcs)
793 for(i = narcs, arc = parcs; --i >= 0; arc++)
795 if (miFillArcEmpty(arc))
797 if ((arc->angle2 >= FULLCIRCLE) || (arc->angle2 <= -FULLCIRCLE))
799 if (miCanFillArc(arc))
800 miFillEllipseI(pDraw, pGC, arc);
802 miFillEllipseD(pDraw, pGC, arc);
806 if (miCanFillArc(arc))
807 miFillArcSliceI(pDraw, pGC, arc);
809 miFillArcSliceD(pDraw, pGC, arc);