1 /************************************************************
3 Copyright 1989, 1998 The Open Group
5 Permission to use, copy, modify, distribute, and sell this software and its
6 documentation for any purpose is hereby granted without fee, provided that
7 the above copyright notice appear in all copies and that both that
8 copyright notice and this permission notice appear in supporting
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21 Except as contained in this notice, the name of The Open Group shall not be
22 used in advertising or otherwise to promote the sale, use or other dealings
23 in this Software without prior written authorization from The Open Group.
25 Author: Bob Scheifler, MIT X Consortium
27 ********************************************************/
29 #ifdef HAVE_DIX_CONFIG_H
30 #include <dix-config.h>
35 #include <X11/Xprotostr.h>
36 #include "regionstr.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(xArc
* arc
, miFillArcRec
* info
)
57 info
->y
= arc
->height
>> 1;
58 info
->dy
= arc
->height
& 1;
59 info
->yorg
= arc
->y
+ info
->y
;
60 info
->dx
= arc
->width
& 1;
61 info
->xorg
= arc
->x
+ (arc
->width
>> 1) + info
->dx
;
62 info
->dx
= 1 - info
->dx
;
63 if (arc
->width
== arc
->height
) {
64 /* (2x - 2xorg)^2 = d^2 - (2y - 2yorg)^2 */
65 /* even: xorg = yorg = 0 odd: xorg = .5, yorg = -.5 */
68 info
->yk
= info
->y
<< 3;
77 info
->e
= -(info
->y
<< 3);
81 /* h^2 * (2x - 2xorg)^2 = w^2 * h^2 - w^2 * (2y - 2yorg)^2 */
82 /* even: xorg = yorg = 0 odd: xorg = .5, yorg = -.5 */
83 info
->ym
= (arc
->width
* arc
->width
) << 3;
84 info
->xm
= (arc
->height
* arc
->height
) << 3;
85 info
->yk
= info
->y
* info
->ym
;
87 info
->yk
-= info
->ym
>> 1;
90 info
->e
= -(info
->xm
>> 3);
95 info
->xk
= -(info
->xm
>> 1);
96 info
->e
= info
->xk
- info
->yk
;
102 miFillArcDSetup(xArc
* arc
, miFillArcDRec
* info
)
104 /* h^2 * (2x - 2xorg)^2 = w^2 * h^2 - w^2 * (2y - 2yorg)^2 */
105 /* even: xorg = yorg = 0 odd: xorg = .5, yorg = -.5 */
106 info
->y
= arc
->height
>> 1;
107 info
->dy
= arc
->height
& 1;
108 info
->yorg
= arc
->y
+ info
->y
;
109 info
->dx
= arc
->width
& 1;
110 info
->xorg
= arc
->x
+ (arc
->width
>> 1) + info
->dx
;
111 info
->dx
= 1 - info
->dx
;
112 info
->ym
= ((double) arc
->width
) * (arc
->width
* 8);
113 info
->xm
= ((double) arc
->height
) * (arc
->height
* 8);
114 info
->yk
= info
->y
* info
->ym
;
116 info
->yk
-= info
->ym
/ 2.0;
119 info
->e
= -(info
->xm
/ 8.0);
123 info
->yk
+= info
->ym
;
124 info
->xk
= -info
->xm
/ 2.0;
125 info
->e
= info
->xk
- info
->yk
;
130 miGetArcEdge(xArc
* arc
, miSliceEdgePtr edge
, int k
, Bool top
, Bool left
)
134 y
= arc
->height
>> 1;
135 if (!(arc
->width
& 1))
142 xady
= k
+ y
* edge
->dx
;
144 edge
->x
= -((-xady
) / edge
->dy
+ 1);
146 edge
->x
= (xady
- 1) / edge
->dy
;
147 edge
->e
= xady
- edge
->x
* edge
->dy
;
148 if ((top
&& (edge
->dx
< 0)) || (!top
&& (edge
->dx
> 0)))
149 edge
->e
= edge
->dy
- edge
->e
+ 1;
152 edge
->x
+= arc
->x
+ (arc
->width
>> 1);
155 edge
->stepx
= edge
->dx
/ edge
->dy
;
156 edge
->dx
= edge
->dx
% edge
->dy
;
160 edge
->stepx
= -((-edge
->dx
) / edge
->dy
);
161 edge
->dx
= (-edge
->dx
) % edge
->dy
;
164 edge
->deltax
= -edge
->deltax
;
165 edge
->stepx
= -edge
->stepx
;
170 miEllipseAngleToSlope(int angle
, int width
, int height
, int *dxp
, int *dyp
,
171 double *d_dxp
, double *d_dyp
)
174 double d_dx
, d_dy
, scale
;
175 Bool negative_dx
, negative_dy
;
182 *d_dxp
= width
/ 2.0;
191 *d_dyp
= -height
/ 2.0;
198 *d_dxp
= -width
/ 2.0;
207 *d_dyp
= height
/ 2.0;
211 d_dx
= Dcos(angle
) * width
;
212 d_dy
= Dsin(angle
) * height
;
215 *d_dyp
= -d_dy
/ 2.0;
230 dx
= floor((d_dx
* 32768) / scale
+ 0.5);
234 dy
= floor((d_dy
* 32768) / scale
+ 0.5);
243 miGetPieEdge(xArc
* arc
, int angle
, miSliceEdgePtr edge
, Bool top
, Bool left
)
248 miEllipseAngleToSlope(angle
, arc
->width
, arc
->height
, &dx
, &dy
, 0, 0);
251 edge
->x
= left
? -65536 : 65536;
258 edge
->x
= arc
->x
+ (arc
->width
>> 1);
259 if (left
&& (arc
->width
& 1))
261 else if (!left
&& !(arc
->width
& 1))
272 k
= (arc
->height
& 1) ? dx
: 0;
277 miGetArcEdge(arc
, edge
, k
, top
, left
);
281 miFillArcSliceSetup(xArc
* arc
, miArcSliceRec
* slice
, GCPtr pGC
)
285 angle1
= arc
->angle1
;
286 if (arc
->angle2
< 0) {
288 angle1
+= arc
->angle2
;
291 angle2
= angle1
+ arc
->angle2
;
293 angle1
+= FULLCIRCLE
;
294 while (angle1
>= FULLCIRCLE
)
295 angle1
-= FULLCIRCLE
;
297 angle2
+= FULLCIRCLE
;
298 while (angle2
>= FULLCIRCLE
)
299 angle2
-= FULLCIRCLE
;
300 slice
->min_top_y
= 0;
301 slice
->max_top_y
= arc
->height
>> 1;
302 slice
->min_bot_y
= 1 - (arc
->height
& 1);
303 slice
->max_bot_y
= slice
->max_top_y
- 1;
304 slice
->flip_top
= FALSE
;
305 slice
->flip_bot
= FALSE
;
306 if (pGC
->arcMode
== ArcPieSlice
) {
307 slice
->edge1_top
= (angle1
< HALFCIRCLE
);
308 slice
->edge2_top
= (angle2
<= HALFCIRCLE
);
309 if ((angle2
== 0) || (angle1
== HALFCIRCLE
)) {
310 if (angle2
? slice
->edge2_top
: slice
->edge1_top
)
311 slice
->min_top_y
= slice
->min_bot_y
;
313 slice
->min_top_y
= arc
->height
;
314 slice
->min_bot_y
= 0;
316 else if ((angle1
== 0) || (angle2
== HALFCIRCLE
)) {
317 slice
->min_top_y
= slice
->min_bot_y
;
318 if (angle1
? slice
->edge1_top
: slice
->edge2_top
)
319 slice
->min_bot_y
= arc
->height
;
321 slice
->min_bot_y
= 0;
323 else if (slice
->edge1_top
== slice
->edge2_top
) {
324 if (angle2
< angle1
) {
325 slice
->flip_top
= slice
->edge1_top
;
326 slice
->flip_bot
= !slice
->edge1_top
;
328 else if (slice
->edge1_top
) {
329 slice
->min_top_y
= 1;
330 slice
->min_bot_y
= arc
->height
;
333 slice
->min_bot_y
= 0;
334 slice
->min_top_y
= arc
->height
;
337 miGetPieEdge(arc
, angle1
, &slice
->edge1
,
338 slice
->edge1_top
, !slice
->edge1_top
);
339 miGetPieEdge(arc
, angle2
, &slice
->edge2
,
340 slice
->edge2_top
, slice
->edge2_top
);
343 double w2
, h2
, x1
, y1
, x2
, y2
, dx
, dy
, scale
;
344 int signdx
, signdy
, y
, k
;
345 Bool isInt1
= TRUE
, isInt2
= TRUE
;
347 w2
= (double) arc
->width
/ 2.0;
348 h2
= (double) arc
->height
/ 2.0;
349 if ((angle1
== 0) || (angle1
== HALFCIRCLE
)) {
350 x1
= angle1
? -w2
: w2
;
353 else if ((angle1
== QUADRANT
) || (angle1
== QUADRANT3
)) {
355 y1
= (angle1
== QUADRANT
) ? h2
: -h2
;
359 x1
= Dcos(angle1
) * w2
;
360 y1
= Dsin(angle1
) * h2
;
362 if ((angle2
== 0) || (angle2
== HALFCIRCLE
)) {
363 x2
= angle2
? -w2
: w2
;
366 else if ((angle2
== QUADRANT
) || (angle2
== QUADRANT3
)) {
368 y2
= (angle2
== QUADRANT
) ? h2
: -h2
;
372 x2
= Dcos(angle2
) * w2
;
373 y2
= Dsin(angle2
) * h2
;
377 if (arc
->height
& 1) {
381 if (arc
->width
& 1) {
397 if (isInt1
&& isInt2
) {
398 slice
->edge1
.dx
= dx
* 2;
399 slice
->edge1
.dy
= dy
* 2;
402 scale
= (dx
> dy
) ? dx
: dy
;
403 slice
->edge1
.dx
= floor((dx
* 32768) / scale
+ .5);
404 slice
->edge1
.dy
= floor((dy
* 32768) / scale
+ .5);
406 if (!slice
->edge1
.dy
) {
410 slice
->min_top_y
= y
;
411 slice
->min_bot_y
= arc
->height
;
414 slice
->max_bot_y
= -y
- (arc
->height
& 1);
420 slice
->max_top_y
= y
;
422 slice
->min_top_y
= arc
->height
;
423 slice
->min_bot_y
= -y
- (arc
->height
& 1);
426 slice
->edge1_top
= TRUE
;
427 slice
->edge1
.x
= 65536;
428 slice
->edge1
.stepx
= 0;
430 slice
->edge1
.dx
= -1;
431 slice
->edge2
= slice
->edge1
;
432 slice
->edge2_top
= FALSE
;
434 else if (!slice
->edge1
.dx
) {
437 slice
->edge1
.x
= ceil(x1
);
438 slice
->edge1_top
= signdy
< 0;
439 slice
->edge1
.x
+= arc
->x
+ (arc
->width
>> 1);
440 slice
->edge1
.stepx
= 0;
442 slice
->edge1
.dx
= -1;
443 slice
->edge2_top
= !slice
->edge1_top
;
444 slice
->edge2
= slice
->edge1
;
448 slice
->edge1
.dx
= -slice
->edge1
.dx
;
450 slice
->edge1
.dx
= -slice
->edge1
.dx
;
451 k
= ceil(((x1
+ x2
) * slice
->edge1
.dy
-
452 (y1
+ y2
) * slice
->edge1
.dx
) / 2.0);
453 slice
->edge2
.dx
= slice
->edge1
.dx
;
454 slice
->edge2
.dy
= slice
->edge1
.dy
;
455 slice
->edge1_top
= signdy
< 0;
456 slice
->edge2_top
= !slice
->edge1_top
;
457 miGetArcEdge(arc
, &slice
->edge1
, k
,
458 slice
->edge1_top
, !slice
->edge1_top
);
459 miGetArcEdge(arc
, &slice
->edge2
, k
,
460 slice
->edge2_top
, slice
->edge2_top
);
471 if (miFillArcLower(slw)) \
474 pts->y = yorg + y + dy; \
480 miFillEllipseI(DrawablePtr pDraw
, GCPtr pGC
, xArc
* arc
)
483 int yk
, xk
, ym
, xm
, dx
, dy
, xorg
, yorg
;
491 points
= malloc(sizeof(DDXPointRec
) * arc
->height
);
494 widths
= malloc(sizeof(int) * arc
->height
);
499 miFillArcSetup(arc
, &info
);
501 if (pGC
->miTranslate
) {
511 (*pGC
->ops
->FillSpans
) (pDraw
, pGC
, pts
- points
, points
, widths
, FALSE
);
517 miFillEllipseD(DrawablePtr pDraw
, GCPtr pGC
, xArc
* arc
)
520 int xorg
, yorg
, dx
, dy
, slw
;
521 double e
, yk
, xk
, ym
, xm
;
528 points
= malloc(sizeof(DDXPointRec
) * arc
->height
);
531 widths
= malloc(sizeof(int) * arc
->height
);
536 miFillArcDSetup(arc
, &info
);
538 if (pGC
->miTranslate
) {
548 (*pGC
->ops
->FillSpans
) (pDraw
, pGC
, pts
- points
, points
, widths
, FALSE
);
553 #define ADDSPAN(l,r) \
559 *wids++ = r - l + 1; \
562 #define ADDSLICESPANS(flip) \
576 miFillArcSliceI(DrawablePtr pDraw
, GCPtr pGC
, xArc
* arc
)
578 int yk
, xk
, ym
, xm
, dx
, dy
, xorg
, yorg
, slw
;
588 miFillArcSetup(arc
, &info
);
589 miFillArcSliceSetup(arc
, &slice
, pGC
);
592 if (slice
.flip_top
|| slice
.flip_bot
)
593 slw
+= (arc
->height
>> 1) + 1;
594 points
= malloc(sizeof(DDXPointRec
) * slw
);
597 widths
= malloc(sizeof(int) * slw
);
602 if (pGC
->miTranslate
) {
605 slice
.edge1
.x
+= pDraw
->x
;
606 slice
.edge2
.x
+= pDraw
->x
;
612 MIARCSLICESTEP(slice
.edge1
);
613 MIARCSLICESTEP(slice
.edge2
);
614 if (miFillSliceUpper(slice
)) {
616 MIARCSLICEUPPER(xl
, xr
, slice
, slw
);
617 ADDSLICESPANS(slice
.flip_top
);
619 if (miFillSliceLower(slice
)) {
621 MIARCSLICELOWER(xl
, xr
, slice
, slw
);
622 ADDSLICESPANS(slice
.flip_bot
);
625 (*pGC
->ops
->FillSpans
) (pDraw
, pGC
, pts
- points
, points
, widths
, FALSE
);
631 miFillArcSliceD(DrawablePtr pDraw
, GCPtr pGC
, xArc
* arc
)
634 int dx
, dy
, xorg
, yorg
, slw
;
635 double e
, yk
, xk
, ym
, xm
;
644 miFillArcDSetup(arc
, &info
);
645 miFillArcSliceSetup(arc
, &slice
, pGC
);
648 if (slice
.flip_top
|| slice
.flip_bot
)
649 slw
+= (arc
->height
>> 1) + 1;
650 points
= malloc(sizeof(DDXPointRec
) * slw
);
653 widths
= malloc(sizeof(int) * slw
);
658 if (pGC
->miTranslate
) {
661 slice
.edge1
.x
+= pDraw
->x
;
662 slice
.edge2
.x
+= pDraw
->x
;
668 MIARCSLICESTEP(slice
.edge1
);
669 MIARCSLICESTEP(slice
.edge2
);
670 if (miFillSliceUpper(slice
)) {
672 MIARCSLICEUPPER(xl
, xr
, slice
, slw
);
673 ADDSLICESPANS(slice
.flip_top
);
675 if (miFillSliceLower(slice
)) {
677 MIARCSLICELOWER(xl
, xr
, slice
, slw
);
678 ADDSLICESPANS(slice
.flip_bot
);
681 (*pGC
->ops
->FillSpans
) (pDraw
, pGC
, pts
- points
, points
, widths
, FALSE
);
686 /* MIPOLYFILLARC -- The public entry for the PolyFillArc request.
687 * Since we don't have to worry about overlapping segments, we can just
688 * fill each arc as it comes.
691 miPolyFillArc(DrawablePtr pDraw
, GCPtr pGC
, int narcs
, xArc
* parcs
)
696 for (i
= narcs
, arc
= parcs
; --i
>= 0; arc
++) {
697 if (miFillArcEmpty(arc
))
699 if ((arc
->angle2
>= FULLCIRCLE
) || (arc
->angle2
<= -FULLCIRCLE
)) {
700 if (miCanFillArc(arc
))
701 miFillEllipseI(pDraw
, pGC
, arc
);
703 miFillEllipseD(pDraw
, pGC
, arc
);
706 if (miCanFillArc(arc
))
707 miFillArcSliceI(pDraw
, pGC
, arc
);
709 miFillArcSliceD(pDraw
, pGC
, arc
);