]> Pileus Git - ~andy/gtk/blob - gdk/linux-fb/mifillarc.c
Fixes #136082 and #135265, patch by Morten Welinder.
[~andy/gtk] / gdk / linux-fb / mifillarc.c
1 /* $XFree86: xc/programs/Xserver/mi/mifillarc.c,v 3.4 1999/04/11 13:11:20 dawes Exp $ */
2 /************************************************************
3
4 Copyright 1989, 1998  The Open Group
5
6 All Rights Reserved.
7
8 The above copyright notice and this permission notice shall be included in
9 all copies or substantial portions of the Software.
10
11 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
12 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
13 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
14 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
15 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
16 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
17
18 Except as contained in this notice, the name of The Open Group shall not be
19 used in advertising or otherwise to promote the sale, use or other dealings
20 in this Software without prior written authorization from The Open Group.
21
22 Author:  Bob Scheifler, MIT X Consortium
23
24 ********************************************************/
25
26 /* $TOG: mifillarc.c /main/20 1998/02/09 14:46:52 kaleb $ */
27
28 #include <config.h>
29 #include <math.h>
30 #include "mi.h"
31 #include "mifillarc.h"
32 #include "gdkprivate-fb.h"
33
34 #define QUADRANT (90 * 64)
35 #define HALFCIRCLE (180 * 64)
36 #define QUADRANT3 (270 * 64)
37
38 #ifndef M_PI
39 #define M_PI    3.14159265358979323846
40 #endif
41
42 #define Dsin(d) sin((double)d*(M_PI/11520.0))
43 #define Dcos(d) cos((double)d*(M_PI/11520.0))
44
45 void
46 miFillArcSetup(arc, info)
47     register miArc *arc;
48     register miFillArcRec *info;
49 {
50     info->y = arc->height >> 1;
51     info->dy = arc->height & 1;
52     info->yorg = arc->y + info->y;
53     info->dx = arc->width & 1;
54     info->xorg = arc->x + (arc->width >> 1) + info->dx;
55     info->dx = 1 - info->dx;
56     if (arc->width == arc->height)
57     {
58         /* (2x - 2xorg)^2 = d^2 - (2y - 2yorg)^2 */
59         /* even: xorg = yorg = 0   odd:  xorg = .5, yorg = -.5 */
60         info->ym = 8;
61         info->xm = 8;
62         info->yk = info->y << 3;
63         if (!info->dx)
64         {
65             info->xk = 0;
66             info->e = -1;
67         }
68         else
69         {
70             info->y++;
71             info->yk += 4;
72             info->xk = -4;
73             info->e = - (info->y << 3);
74         }
75     }
76     else
77     {
78         /* h^2 * (2x - 2xorg)^2 = w^2 * h^2 - w^2 * (2y - 2yorg)^2 */
79         /* even: xorg = yorg = 0   odd:  xorg = .5, yorg = -.5 */
80         info->ym = (arc->width * arc->width) << 3;
81         info->xm = (arc->height * arc->height) << 3;
82         info->yk = info->y * info->ym;
83         if (!info->dy)
84             info->yk -= info->ym >> 1;
85         if (!info->dx)
86         {
87             info->xk = 0;
88             info->e = - (info->xm >> 3);
89         }
90         else
91         {
92             info->y++;
93             info->yk += info->ym;
94             info->xk = -(info->xm >> 1);
95             info->e = info->xk - info->yk;
96         }
97     }
98 }
99
100 void
101 miFillArcDSetup(arc, info)
102     register miArc *arc;
103     register miFillArcDRec *info;
104 {
105     /* h^2 * (2x - 2xorg)^2 = w^2 * h^2 - w^2 * (2y - 2yorg)^2 */
106     /* even: xorg = yorg = 0   odd:  xorg = .5, yorg = -.5 */
107     info->y = arc->height >> 1;
108     info->dy = arc->height & 1;
109     info->yorg = arc->y + info->y;
110     info->dx = arc->width & 1;
111     info->xorg = arc->x + (arc->width >> 1) + info->dx;
112     info->dx = 1 - info->dx;
113     info->ym = ((double)arc->width) * (arc->width * 8);
114     info->xm = ((double)arc->height) * (arc->height * 8);
115     info->yk = info->y * info->ym;
116     if (!info->dy)
117         info->yk -= info->ym / 2.0;
118     if (!info->dx)
119     {
120         info->xk = 0;
121         info->e = - (info->xm / 8.0);
122     }
123     else
124     {
125         info->y++;
126         info->yk += info->ym;
127         info->xk = -info->xm / 2.0;
128         info->e = info->xk - info->yk;
129     }
130 }
131
132 static void
133 miGetArcEdge(arc, edge, k, top, left)
134     register miArc *arc;
135     register miSliceEdgePtr edge;
136     int k;
137     gboolean top, left;
138 {
139     register int xady, y;
140
141     y = arc->height >> 1;
142     if (!(arc->width & 1))
143         y++;
144     if (!top)
145     {
146         y = -y;
147         if (arc->height & 1)
148             y--;
149     }
150     xady = k + y * edge->dx;
151     if (xady <= 0)
152         edge->x = - ((-xady) / edge->dy + 1);
153     else
154         edge->x = (xady - 1) / edge->dy;
155     edge->e = xady - edge->x * edge->dy;
156     if ((top && (edge->dx < 0)) || (!top && (edge->dx > 0)))
157         edge->e = edge->dy - edge->e + 1;
158     if (left)
159         edge->x++;
160     edge->x += arc->x + (arc->width >> 1);
161     if (edge->dx > 0)
162     {
163         edge->deltax = 1;
164         edge->stepx = edge->dx / edge->dy;
165         edge->dx = edge->dx % edge->dy;
166     }
167     else
168     {
169         edge->deltax = -1;
170         edge->stepx = - ((-edge->dx) / edge->dy);
171         edge->dx = (-edge->dx) % edge->dy;
172     }
173     if (!top)
174     {
175         edge->deltax = -edge->deltax;
176         edge->stepx = -edge->stepx;
177     }
178 }
179
180 void
181 miEllipseAngleToSlope (angle, width, height, dxp, dyp, d_dxp, d_dyp)
182     int     angle;
183     int     width;
184     int     height;
185     int     *dxp;
186     int     *dyp;
187     double  *d_dxp;
188     double  *d_dyp;
189 {
190     int     dx, dy;
191     double  d_dx, d_dy, scale;
192     gboolean    negative_dx, negative_dy;
193
194     switch (angle) {
195     case 0:
196         *dxp = -1;
197         *dyp = 0;
198         if (d_dxp) {
199             *d_dxp = width / 2.0;
200             *d_dyp = 0;
201         }
202         break;
203     case QUADRANT:
204         *dxp = 0;
205         *dyp = 1;
206         if (d_dxp) {
207             *d_dxp = 0;
208             *d_dyp = - height / 2.0;
209         }
210         break;
211     case HALFCIRCLE:
212         *dxp = 1;
213         *dyp = 0;
214         if (d_dxp) {
215             *d_dxp = - width / 2.0;
216             *d_dyp = 0;
217         }
218         break;
219     case QUADRANT3:
220         *dxp = 0;
221         *dyp = -1;
222         if (d_dxp) {
223             *d_dxp = 0;
224             *d_dyp = height / 2.0;
225         }
226         break;
227     default:
228         d_dx = Dcos(angle) * width;
229         d_dy = Dsin(angle) * height;
230         if (d_dxp) {
231             *d_dxp = d_dx / 2.0;
232             *d_dyp = - d_dy / 2.0;
233         }
234         negative_dx = FALSE;
235         if (d_dx < 0.0)
236         {
237             d_dx = -d_dx;
238             negative_dx = TRUE;
239         }
240         negative_dy = FALSE;
241         if (d_dy < 0.0)
242         {
243             d_dy = -d_dy;
244             negative_dy = TRUE;
245         }
246         scale = d_dx;
247         if (d_dy > d_dx)
248             scale = d_dy;
249         dx = floor ((d_dx * 32768) / scale + 0.5);
250         if (negative_dx)
251             dx = -dx;
252         *dxp = dx;
253         dy = floor ((d_dy * 32768) / scale + 0.5);
254         if (negative_dy)
255             dy = -dy;
256         *dyp = dy;
257         break;
258     }
259 }
260
261 static void
262 miGetPieEdge(arc, angle, edge, top, left)
263     register miArc *arc;
264     register int angle;
265     register miSliceEdgePtr edge;
266     gboolean top, left;
267 {
268     register int k;
269     int dx, dy;
270
271     miEllipseAngleToSlope (angle, arc->width, arc->height, &dx, &dy, 0, 0);
272
273     if (dy == 0)
274     {
275         edge->x = left ? -65536 : 65536;
276         edge->stepx = 0;
277         edge->e = 0;
278         edge->dx = -1;
279         return;
280     }
281     if (dx == 0)
282     {
283         edge->x = arc->x + (arc->width >> 1);
284         if (left && (arc->width & 1))
285             edge->x++;
286         else if (!left && !(arc->width & 1))
287             edge->x--;
288         edge->stepx = 0;
289         edge->e = 0;
290         edge->dx = -1;
291         return;
292     }
293     if (dy < 0) {
294         dx = -dx;
295         dy = -dy;
296     }
297     k = (arc->height & 1) ? dx : 0;
298     if (arc->width & 1)
299         k += dy;
300     edge->dx = dx << 1;
301     edge->dy = dy << 1;
302     miGetArcEdge(arc, edge, k, top, left);
303 }
304
305 void
306 miFillArcSliceSetup(arc, slice, pGC)
307     register miArc *arc;
308     register miArcSliceRec *slice;
309     GdkGC* pGC;
310 {
311     register int angle1, angle2;
312
313     angle1 = arc->angle1;
314     if (arc->angle2 < 0)
315     {
316         angle2 = angle1;
317         angle1 += arc->angle2;
318     }
319     else
320         angle2 = angle1 + arc->angle2;
321     while (angle1 < 0)
322         angle1 += FULLCIRCLE;
323     while (angle1 >= FULLCIRCLE)
324         angle1 -= FULLCIRCLE;
325     while (angle2 < 0)
326         angle2 += FULLCIRCLE;
327     while (angle2 >= FULLCIRCLE)
328         angle2 -= FULLCIRCLE;
329     slice->min_top_y = 0;
330     slice->max_top_y = arc->height >> 1;
331     slice->min_bot_y = 1 - (arc->height & 1);
332     slice->max_bot_y = slice->max_top_y - 1;
333     slice->flip_top = FALSE;
334     slice->flip_bot = FALSE;
335     if (1 /* pGC->arcMode == ArcPieSlice */)
336     {
337         slice->edge1_top = (angle1 < HALFCIRCLE);
338         slice->edge2_top = (angle2 <= HALFCIRCLE);
339         if ((angle2 == 0) || (angle1 == HALFCIRCLE))
340         {
341             if (angle2 ? slice->edge2_top : slice->edge1_top)
342                 slice->min_top_y = slice->min_bot_y;
343             else
344                 slice->min_top_y = arc->height;
345             slice->min_bot_y = 0;
346         }
347         else if ((angle1 == 0) || (angle2 == HALFCIRCLE))
348         {
349             slice->min_top_y = slice->min_bot_y;
350             if (angle1 ? slice->edge1_top : slice->edge2_top)
351                 slice->min_bot_y = arc->height;
352             else
353                 slice->min_bot_y = 0;
354         }
355         else if (slice->edge1_top == slice->edge2_top)
356         {
357             if (angle2 < angle1)
358             {
359                 slice->flip_top = slice->edge1_top;
360                 slice->flip_bot = !slice->edge1_top;
361             }
362             else if (slice->edge1_top)
363             {
364                 slice->min_top_y = 1;
365                 slice->min_bot_y = arc->height;
366             }
367             else
368             {
369                 slice->min_bot_y = 0;
370                 slice->min_top_y = arc->height;
371             }
372         }
373         miGetPieEdge(arc, angle1, &slice->edge1,
374                      slice->edge1_top, !slice->edge1_top);
375         miGetPieEdge(arc, angle2, &slice->edge2,
376                      slice->edge2_top, slice->edge2_top);
377     }
378     else
379     {
380         double w2, h2, x1, y1, x2, y2, dx, dy, scale;
381         int signdx, signdy, y, k;
382         gboolean isInt1 = TRUE, isInt2 = TRUE;
383
384         w2 = (double)arc->width / 2.0;
385         h2 = (double)arc->height / 2.0;
386         if ((angle1 == 0) || (angle1 == HALFCIRCLE))
387         {
388             x1 = angle1 ? -w2 : w2;
389             y1 = 0.0;
390         }
391         else if ((angle1 == QUADRANT) || (angle1 == QUADRANT3))
392         {
393             x1 = 0.0;
394             y1 = (angle1 == QUADRANT) ? h2 : -h2;
395         }
396         else
397         {
398             isInt1 = FALSE;
399             x1 = Dcos(angle1) * w2;
400             y1 = Dsin(angle1) * h2;
401         }
402         if ((angle2 == 0) || (angle2 == HALFCIRCLE))
403         {
404             x2 = angle2 ? -w2 : w2;
405             y2 = 0.0;
406         }
407         else if ((angle2 == QUADRANT) || (angle2 == QUADRANT3))
408         {
409             x2 = 0.0;
410             y2 = (angle2 == QUADRANT) ? h2 : -h2;
411         }
412         else
413         {
414             isInt2 = FALSE;
415             x2 = Dcos(angle2) * w2;
416             y2 = Dsin(angle2) * h2;
417         }
418         dx = x2 - x1;
419         dy = y2 - y1;
420         if (arc->height & 1)
421         {
422             y1 -= 0.5;
423             y2 -= 0.5;
424         }
425         if (arc->width & 1)
426         {
427             x1 += 0.5;
428             x2 += 0.5;
429         }
430         if (dy < 0.0)
431         {
432             dy = -dy;
433             signdy = -1;
434         }
435         else
436             signdy = 1;
437         if (dx < 0.0)
438         {
439             dx = -dx;
440             signdx = -1;
441         }
442         else
443             signdx = 1;
444         if (isInt1 && isInt2)
445         {
446             slice->edge1.dx = dx * 2;
447             slice->edge1.dy = dy * 2;
448         }
449         else
450         {
451             scale = (dx > dy) ? dx : dy;
452             slice->edge1.dx = floor((dx * 32768) / scale + .5);
453             slice->edge1.dy = floor((dy * 32768) / scale + .5);
454         }
455         if (!slice->edge1.dy)
456         {
457             if (signdx < 0)
458             {
459                 y = floor(y1 + 1.0);
460                 if (y >= 0)
461                 {
462                     slice->min_top_y = y;
463                     slice->min_bot_y = arc->height;
464                 }
465                 else
466                 {
467                     slice->max_bot_y = -y - (arc->height & 1);
468                 }
469             }
470             else
471             {
472                 y = floor(y1);
473                 if (y >= 0)
474                     slice->max_top_y = y;
475                 else
476                 {
477                     slice->min_top_y = arc->height;
478                     slice->min_bot_y = -y - (arc->height & 1);
479                 }
480             }
481             slice->edge1_top = TRUE;
482             slice->edge1.x = 65536;
483             slice->edge1.stepx = 0;
484             slice->edge1.e = 0;
485             slice->edge1.dx = -1;
486             slice->edge2 = slice->edge1;
487             slice->edge2_top = FALSE;
488         }
489         else if (!slice->edge1.dx)
490         {
491             if (signdy < 0)
492                 x1 -= 1.0;
493             slice->edge1.x = ceil(x1);
494             slice->edge1_top = signdy < 0;
495             slice->edge1.x += arc->x + (arc->width >> 1);
496             slice->edge1.stepx = 0;
497             slice->edge1.e = 0;
498             slice->edge1.dx = -1;
499             slice->edge2_top = !slice->edge1_top;
500             slice->edge2 = slice->edge1;
501         }
502         else
503         {
504             if (signdx < 0)
505                 slice->edge1.dx = -slice->edge1.dx;
506             if (signdy < 0)
507                 slice->edge1.dx = -slice->edge1.dx;
508             k = ceil(((x1 + x2) * slice->edge1.dy - (y1 + y2) * slice->edge1.dx) / 2.0);
509             slice->edge2.dx = slice->edge1.dx;
510             slice->edge2.dy = slice->edge1.dy;
511             slice->edge1_top = signdy < 0;
512             slice->edge2_top = !slice->edge1_top;
513             miGetArcEdge(arc, &slice->edge1, k,
514                          slice->edge1_top, !slice->edge1_top);
515             miGetArcEdge(arc, &slice->edge2, k,
516                          slice->edge2_top, slice->edge2_top);
517         }
518     }
519 }
520
521 #define ADDSPANS() \
522     pts->x = xorg - x; \
523     pts->y = yorg - y; \
524     pts->width = slw; \
525     pts++; \
526     if (miFillArcLower(slw)) \
527     { \
528         pts->x = xorg - x; \
529         pts->y = yorg + y + dy; \
530         pts->width = slw; \
531         pts++; \
532     }
533
534 static void
535 miFillEllipseI(pDraw, pGC, arc)
536     GdkDrawable* pDraw;
537     GdkGC* pGC;
538     miArc *arc;
539 {
540     register int x, y, e;
541     int yk, xk, ym, xm, dx, dy, xorg, yorg;
542     int slw;
543     miFillArcRec info;
544     GdkSpan* points;
545     register GdkSpan* pts;
546
547     points = (GdkSpan*)ALLOCATE_LOCAL(sizeof(GdkSpan) * arc->height);
548     if (!points)
549         return;
550     miFillArcSetup(arc, &info);
551     MIFILLARCSETUP();
552     pts = points;
553     while (y > 0)
554     {
555         MIFILLARCSTEP(slw);
556         ADDSPANS();
557     }
558     gdk_fb_fill_spans(pDraw, pGC, points, pts - points, FALSE);
559
560     DEALLOCATE_LOCAL(points);
561 }
562
563 static void
564 miFillEllipseD(pDraw, pGC, arc)
565     GdkDrawable* pDraw;
566     GdkGC* pGC;
567     miArc *arc;
568 {
569     register int x, y;
570     int xorg, yorg, dx, dy, slw;
571     double e, yk, xk, ym, xm;
572     miFillArcDRec info;
573     GdkSpan* points;
574     register GdkSpan* pts;
575
576     points = (GdkSpan*)ALLOCATE_LOCAL(sizeof(GdkSpan) * arc->height);
577     if (!points)
578         return;
579     miFillArcDSetup(arc, &info);
580     MIFILLARCSETUP();
581     pts = points;
582     while (y > 0)
583     {
584         MIFILLARCSTEP(slw);
585         ADDSPANS();
586     }
587     gdk_fb_fill_spans(pDraw, pGC, points, pts - points, FALSE);
588     DEALLOCATE_LOCAL(points);
589 }
590
591 #define ADDSPAN(l,r) \
592     if (r >= l) \
593     { \
594         pts->x = l; \
595         pts->y = ya; \
596         pts->width = r - l + 1; \
597         pts++; \
598     }
599
600 #define ADDSLICESPANS(flip) \
601     if (!flip) \
602     { \
603         ADDSPAN(xl, xr); \
604     } \
605     else \
606     { \
607         xc = xorg - x; \
608         ADDSPAN(xc, xr); \
609         xc += slw - 1; \
610         ADDSPAN(xl, xc); \
611     }
612
613 static void
614 miFillArcSliceI(pDraw, pGC, arc)
615     GdkDrawable* pDraw;
616     GdkGC* pGC;
617     miArc *arc;
618 {
619     int yk, xk, ym, xm, dx, dy, xorg, yorg, slw;
620     register int x, y, e;
621     miFillArcRec info;
622     miArcSliceRec slice;
623     int ya, xl, xr, xc;
624     GdkSpan* points;
625     register GdkSpan* pts;
626
627     miFillArcSetup(arc, &info);
628     miFillArcSliceSetup(arc, &slice, pGC);
629     MIFILLARCSETUP();
630     slw = arc->height;
631     if (slice.flip_top || slice.flip_bot)
632         slw += (arc->height >> 1) + 1;
633     points = (GdkSpan*)ALLOCATE_LOCAL(sizeof(GdkSpan) * slw);
634     if (!points)
635         return;
636     pts = points;
637     while (y > 0)
638     {
639         MIFILLARCSTEP(slw);
640         MIARCSLICESTEP(slice.edge1);
641         MIARCSLICESTEP(slice.edge2);
642         if (miFillSliceUpper(slice))
643         {
644             ya = yorg - y;
645             MIARCSLICEUPPER(xl, xr, slice, slw);
646             ADDSLICESPANS(slice.flip_top);
647         }
648         if (miFillSliceLower(slice))
649         {
650             ya = yorg + y + dy;
651             MIARCSLICELOWER(xl, xr, slice, slw);
652             ADDSLICESPANS(slice.flip_bot);
653         }
654     }
655     
656     gdk_fb_fill_spans(pDraw, pGC, points, pts - points, FALSE);
657     DEALLOCATE_LOCAL(points);
658 }
659
660 static void
661 miFillArcSliceD(pDraw, pGC, arc)
662     GdkDrawable* pDraw;
663     GdkGC* pGC;
664     miArc *arc;
665 {
666     register int x, y;
667     int dx, dy, xorg, yorg, slw;
668     double e, yk, xk, ym, xm;
669     miFillArcDRec info;
670     miArcSliceRec slice;
671     int ya, xl, xr, xc;
672     GdkSpan* points;
673     register GdkSpan* pts;
674
675     miFillArcDSetup(arc, &info);
676     miFillArcSliceSetup(arc, &slice, pGC);
677     MIFILLARCSETUP();
678     slw = arc->height;
679     if (slice.flip_top || slice.flip_bot)
680         slw += (arc->height >> 1) + 1;
681     points = (GdkSpan*)ALLOCATE_LOCAL(sizeof(GdkSpan) * slw);
682     if (!points)
683         return;
684     pts = points;
685     while (y > 0)
686     {
687         MIFILLARCSTEP(slw);
688         MIARCSLICESTEP(slice.edge1);
689         MIARCSLICESTEP(slice.edge2);
690         if (miFillSliceUpper(slice))
691         {
692             ya = yorg - y;
693             MIARCSLICEUPPER(xl, xr, slice, slw);
694             ADDSLICESPANS(slice.flip_top);
695         }
696         if (miFillSliceLower(slice))
697         {
698             ya = yorg + y + dy;
699             MIARCSLICELOWER(xl, xr, slice, slw);
700             ADDSLICESPANS(slice.flip_bot);
701         }
702     }
703     gdk_fb_fill_spans(pDraw, pGC, points, pts - points, FALSE);
704
705     DEALLOCATE_LOCAL(points);
706 }
707
708 /* MIPOLYFILLARC -- The public entry for the PolyFillArc request.
709  * Since we don't have to worry about overlapping segments, we can just
710  * fill each arc as it comes.
711  */
712 void
713 miPolyFillArc(pDraw, pGC, narcs, parcs)
714     GdkDrawable*        pDraw;
715     GdkGC*      pGC;
716     int         narcs;
717     miArc       *parcs;
718 {
719     register int i;
720     register miArc *arc;
721
722     for(i = narcs, arc = parcs; --i >= 0; arc++)
723     {
724         if (miFillArcEmpty(arc))
725             continue;;
726         if ((arc->angle2 >= FULLCIRCLE) || (arc->angle2 <= -FULLCIRCLE))
727         {
728             if (miCanFillArc(arc))
729                 miFillEllipseI(pDraw, pGC, arc);
730             else
731                 miFillEllipseD(pDraw, pGC, arc);
732         }
733         else
734         {
735             if (miCanFillArc(arc))
736                 miFillArcSliceI(pDraw, pGC, arc);
737             else
738                 miFillArcSliceD(pDraw, pGC, arc);
739         }
740     }
741 }