1 /***********************************************************
3 Copyright 1987, 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 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
29 Permission to use, copy, modify, and distribute this software and its
30 documentation for any purpose and without fee is hereby granted,
31 provided that the above copyright notice appear in all copies and that
32 both that copyright notice and this permission notice appear in
33 supporting documentation, and that the name of Digital not be
34 used in advertising or publicity pertaining to distribution of the
35 software without specific, written prior permission.
37 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
38 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
39 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
40 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
41 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
42 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
45 ******************************************************************/
46 /* Author: Keith Packard and Bob Scheifler */
47 /* Warning: this code is toxic, do not dally very long here. */
49 #ifdef HAVE_DIX_CONFIG_H
50 #include <dix-config.h>
55 #include <X11/Xprotostr.h>
58 #include "scrnintstr.h"
59 #include "pixmapstr.h"
60 #include "windowstr.h"
63 #include "mifillarc.h"
64 #include <X11/Xfuncproto.h>
66 static double miDsin(double a
);
67 static double miDcos(double a
);
68 static double miDasin(double v
);
69 static double miDatan2(double dy
, double dx
);
76 return pow(x
, 1.0 / 3.0);
78 return -pow(-x
, 1.0 / 3.0);
83 * some interesting sematic interpretation of the protocol:
85 * Self intersecting arcs (i.e. those spanning 360 degrees)
86 * never join with other arcs, and are drawn without caps
87 * (unless on/off dashed, in which case each dash segment
88 * is capped, except when the last segment meets the
89 * first segment, when no caps are drawn)
91 * double dash arcs are drawn in two parts, first the
92 * odd dashes (drawn in background) then the even dashes
93 * (drawn in foreground). This means that overlapping
94 * sections of foreground/background are drawn twice,
95 * first in background then in foreground. The double-draw
96 * occurs even when the function uses the destination values
97 * (e.g. xor mode). This is the same way the wide-line
98 * code works and should be "fixed".
106 max(const int x
, const int y
)
108 return x
> y
? x
: y
;
112 min(const int x
, const int y
)
114 return x
< y
? x
: y
;
125 #define boundedLe(value, bounds)\
126 ((bounds).min <= (value) && (value) <= (bounds).max)
133 #define intersectLine(y,line) (line.m * (y) + line.b)
136 * these are all y value bounds
140 struct bound ellipse
;
145 struct ibound inneri
;
146 struct ibound outeri
;
149 struct accelerators
{
160 struct line left
, right
;
171 #define todeg(xAngle) (((double) (xAngle)) / 64.0)
176 typedef struct _miArcJoin
{
177 int arcIndex0
, arcIndex1
;
180 } miArcJoinRec
, *miArcJoinPtr
;
182 typedef struct _miArcCap
{
185 } miArcCapRec
, *miArcCapPtr
;
187 typedef struct _miArcFace
{
190 SppPointRec counterClock
;
191 } miArcFaceRec
, *miArcFacePtr
;
193 typedef struct _miArcData
{
195 int render
; /* non-zero means render after drawing */
196 int join
; /* related join */
197 int cap
; /* related cap */
198 int selfJoin
; /* final dash meets first dash */
199 miArcFaceRec bounds
[2];
200 double x0
, y0
, x1
, y1
;
201 } miArcDataRec
, *miArcDataPtr
;
204 * This is an entire sequence of arcs, computed and categorized according
205 * to operation. miDashArcs generates either one or two of these.
208 typedef struct _miPolyArc
{
215 } miPolyArcRec
, *miPolyArcPtr
;
217 static void fillSpans(DrawablePtr pDrawable
, GCPtr pGC
);
218 static void newFinalSpan(int y
, int xmin
, int xmax
);
219 static void drawArc(xArc
* tarc
, int l
, int a0
, int a1
, miArcFacePtr right
,
221 static void drawZeroArc(DrawablePtr pDraw
, GCPtr pGC
, xArc
* tarc
, int lw
,
222 miArcFacePtr left
, miArcFacePtr right
);
223 static void miArcJoin(DrawablePtr pDraw
, GCPtr pGC
, miArcFacePtr pLeft
,
224 miArcFacePtr pRight
, int xOrgLeft
, int yOrgLeft
,
225 double xFtransLeft
, double yFtransLeft
,
226 int xOrgRight
, int yOrgRight
,
227 double xFtransRight
, double yFtransRight
);
228 static void miArcCap(DrawablePtr pDraw
, GCPtr pGC
, miArcFacePtr pFace
,
229 int end
, int xOrg
, int yOrg
, double xFtrans
,
231 static void miRoundCap(DrawablePtr pDraw
, GCPtr pGC
, SppPointRec pCenter
,
232 SppPointRec pEnd
, SppPointRec pCorner
,
233 SppPointRec pOtherCorner
, int fLineEnd
,
234 int xOrg
, int yOrg
, double xFtrans
, double yFtrans
);
235 static void miFreeArcs(miPolyArcPtr arcs
, GCPtr pGC
);
236 static miPolyArcPtr
miComputeArcs(xArc
* parcs
, int narcs
, GCPtr pGC
);
237 static int miGetArcPts(SppArcPtr parc
, int cpt
, SppPointPtr
* ppPts
);
239 #define CUBED_ROOT_2 1.2599210498948732038115849718451499938964
240 #define CUBED_ROOT_4 1.5874010519681993173435330390930175781250
243 * draw one segment of the arc using the arc spans generation routines
247 miArcSegment(DrawablePtr pDraw
,
248 GCPtr pGC
, xArc tarc
, miArcFacePtr right
, miArcFacePtr left
)
250 int l
= pGC
->lineWidth
;
251 int a0
, a1
, startAngle
, endAngle
;
257 if (tarc
.width
== 0 || tarc
.height
== 0) {
258 drawZeroArc(pDraw
, pGC
, &tarc
, l
, left
, right
);
262 if (pGC
->miTranslate
) {
271 else if (a1
< -FULLCIRCLE
)
274 startAngle
= a0
+ a1
;
285 * bounds check the two angles
288 startAngle
= FULLCIRCLE
- (-startAngle
) % FULLCIRCLE
;
289 if (startAngle
>= FULLCIRCLE
)
290 startAngle
= startAngle
% FULLCIRCLE
;
292 endAngle
= FULLCIRCLE
- (-endAngle
) % FULLCIRCLE
;
293 if (endAngle
> FULLCIRCLE
)
294 endAngle
= (endAngle
- 1) % FULLCIRCLE
+ 1;
295 if ((startAngle
== endAngle
) && a1
) {
297 endAngle
= FULLCIRCLE
;
300 drawArc(&tarc
, l
, startAngle
, endAngle
, right
, left
);
305 Three equations combine to describe the boundaries of the arc
307 x^2/w^2 + y^2/h^2 = 1 ellipse itself
308 (X-x)^2 + (Y-y)^2 = r^2 circle at (x, y) on the ellipse
309 (Y-y) = (X-x)*w^2*y/(h^2*x) normal at (x, y) on the ellipse
311 These lead to a quartic relating Y and y
313 y^4 - (2Y)y^3 + (Y^2 + (h^4 - w^2*r^2)/(w^2 - h^2))y^2
314 - (2Y*h^4/(w^2 - h^2))y + (Y^2*h^4)/(w^2 - h^2) = 0
316 The reducible cubic obtained from this quartic is
318 z^3 - (3N)z^2 - 2V = 0
322 N = (Y^2 + (h^4 - w^2*r^2/(w^2 - h^2)))/6
323 V = w^2*r^2*Y^2*h^4/(4 *(w^2 - h^2)^2)
335 The discriminant of this cubic is
339 When D > 0, a real root is obtained as
341 z = N + cbrt(-q+sqrt(D)) + cbrt(-q-sqrt(D))
343 When D < 0, a real root is obtained as
345 z = N - 2m*cos(acos(-q/m^3)/3)
349 m = sqrt(|p|) * sign(q)
351 Given a real root Z of the cubic, the roots of the quartic are the roots
352 of the two quadratics
354 y^2 + ((b+A)/2)y + (Z + (bZ - d)/A) = 0
358 A = +/- sqrt(8Z + b^2 - 4c)
359 b, c, d are the cubic, quadratic, and linear coefficients of the quartic
361 Some experimentation is then required to determine which solutions
362 correspond to the inner and outer boundaries.
367 short lx
, lw
, rx
, rw
;
372 int count1
, count2
, k
;
376 static void drawQuadrant(struct arc_def
*def
, struct accelerators
*acc
,
377 int a0
, int a1
, int mask
, miArcFacePtr right
,
378 miArcFacePtr left
, miArcSpanData
* spdata
);
381 miComputeCircleSpans(int lw
, xArc
* parc
, miArcSpanData
* spdata
)
386 int xk
, yk
, xm
, ym
, dx
, dy
;
388 int inx
= 0, iny
, ine
= 0;
389 int inxk
= 0, inyk
= 0, inxm
= 0, inym
= 0;
392 slw
= parc
->width
- doinner
;
393 y
= parc
->height
>> 1;
394 dy
= parc
->height
& 1;
396 MIWIDEARCSETUP(x
, y
, dy
, slw
, e
, xk
, xm
, yk
, ym
);
397 inslw
= parc
->width
+ doinner
;
399 spdata
->hole
= spdata
->top
;
400 MIWIDEARCSETUP(inx
, iny
, dy
, inslw
, ine
, inxk
, inxm
, inyk
, inym
);
403 spdata
->hole
= FALSE
;
406 spdata
->count1
= -doinner
- spdata
->top
;
407 spdata
->count2
= y
+ doinner
;
408 span
= spdata
->spans
;
412 if (++doinner
<= 0) {
415 span
->rw
= span
->lx
+ slw
;
418 MIFILLINARCSTEP(inslw
);
420 span
->rx
= dy
- inx
+ inslw
;
421 span
->rw
= inx
- x
+ slw
- inslw
;
429 if (lw
> (int) parc
->height
)
430 span
[-1].rx
= span
[-1].rw
= -((lw
- (int) parc
->height
) >> 1);
439 miComputeEllipseSpans(int lw
, xArc
* parc
, miArcSpanData
* spdata
)
442 double w
, h
, r
, xorg
;
443 double Hs
, Hf
, WH
, K
, Vk
, Nk
, Fk
, Vr
, N
, Nc
, Z
, rs
;
444 double A
, T
, b
, d
, x
, y
, t
, inx
, outx
= 0.0, hepp
, hepm
;
447 w
= (double) parc
->width
/ 2.0;
448 h
= (double) parc
->height
/ 2.0;
454 Vk
= (Nk
* Hs
) / (WH
+ WH
);
456 Nk
= (Hf
- Nk
* Nk
) / WH
;
460 K
= h
+ ((lw
- 1) >> 1);
461 span
= spdata
->spans
;
473 spdata
->hole
= (spdata
->top
&&
474 (int) parc
->height
* lw
<= (int) (parc
->width
* parc
->width
)
475 && lw
< (int) parc
->height
);
476 for (; K
> 0.0; K
-= 1.0) {
477 N
= (K
* K
+ Nk
) / 6.0;
485 if ((b
< 0.0) == (t
< 0.0)) {
489 Z
= N
- 2.0 * b
* cos(acos(-t
/ d
) / 3.0);
490 if ((Z
< 0.0) == (Vr
< 0.0))
497 Z
= N
+ cbrt(t
+ d
) + cbrt(t
- d
);
500 A
= sqrt((Z
+ Z
) - Nk
);
501 T
= (Fk
- Z
) * K
/ A
;
505 d
= b
* b
- 4 * (Z
+ T
);
509 if ((y
>= 0.0) && (y
< hepp
)) {
514 x
= w
* sqrt(1 - (t
* t
));
516 if (rs
- (t
* t
) >= 0)
517 t
= sqrt(rs
- (t
* t
));
527 d
= b
* b
- 4 * (Z
- T
);
528 /* Because of the large magnitudes involved, we lose enough precision
529 * that sometimes we end up with a negative value near the axis, when
530 * it should be positive. This is a workaround.
532 if (d
< 0 && !solution
)
541 x
= w
* sqrt(1 - (t
* t
));
543 if (rs
- (t
* t
) >= 0)
544 inx
= x
- sqrt(rs
- (t
* t
));
553 x
= w
* sqrt(1 - (t
* t
));
555 if (rs
- (t
* t
) >= 0)
556 t
= sqrt(rs
- (t
* t
));
565 span
->lx
= ICEIL(xorg
- outx
);
568 span
->lw
= ICEIL(xorg
+ outx
) - span
->lx
;
569 span
->rx
= ICEIL(xorg
+ inx
);
570 span
->rw
= -ICEIL(xorg
- inx
);
574 span
->lw
= ICEIL(xorg
- inx
) - span
->lx
;
575 span
->rx
= ICEIL(xorg
+ inx
);
576 span
->rw
= ICEIL(xorg
+ outx
) - span
->rx
;
582 if (r
>= h
&& r
<= w
)
584 else if (Nk
< 0.0 && -Nk
< Hs
) {
585 inx
= w
* sqrt(1 + Nk
/ Hs
) - sqrt(rs
+ Nk
);
591 span
->lx
= ICEIL(xorg
- outx
);
593 span
->lw
= ICEIL(xorg
+ outx
) - span
->lx
;
594 span
->rx
= ICEIL(xorg
+ inx
);
595 span
->rw
= -ICEIL(xorg
- inx
);
598 span
->lw
= ICEIL(xorg
- inx
) - span
->lx
;
599 span
->rx
= ICEIL(xorg
+ inx
);
600 span
->rw
= ICEIL(xorg
+ outx
) - span
->rx
;
604 span
= &spdata
->spans
[spdata
->count1
];
605 span
->lw
= -span
->lx
;
615 struct arc_def
*def
, struct arc_bound
*bounds
, struct accelerators
*acc
)
618 double Hs
, Hf
, WH
, Vk
, Nk
, Fk
, Vr
, N
, Nc
, Z
, rs
;
619 double A
, T
, b
, d
, x
, y
, t
, hepp
, hepm
;
631 Vk
= (Nk
* Hs
) / (WH
+ WH
);
633 Nk
= (Hf
- Nk
* Nk
) / WH
;
635 if (Nk
< 0.0 && -Nk
< Hs
) {
636 xs
[0] = w
* sqrt(1 + Nk
/ Hs
) - sqrt(rs
+ Nk
);
638 if (acc
->left
.valid
&& boundedLe(K
, bounds
->left
) &&
639 !boundedLe(K
, bounds
->outer
) && xs
[0] >= 0.0 && xs
[1] >= 0.0)
641 if (acc
->right
.valid
&& boundedLe(K
, bounds
->right
) &&
642 !boundedLe(K
, bounds
->inner
) && xs
[0] <= 0.0 && xs
[1] <= 0.0)
651 N
= (K
* K
+ Nk
) / 6.0;
661 if ((b
< 0.0) == (t
< 0.0)) {
665 Z
= N
- 2.0 * b
* cos(acos(-t
/ d
) / 3.0);
666 if ((Z
< 0.0) == (Vr
< 0.0))
673 Z
= N
+ cbrt(t
+ d
) + cbrt(t
- d
);
676 A
= sqrt((Z
+ Z
) - Nk
);
677 T
= (Fk
- Z
) * K
/ A
;
680 d
= b
* b
- 4 * (Z
+ T
);
681 if (d
>= 0 && flip
== 2) {
684 if ((y
>= 0.0) && (y
< hepp
)) {
689 x
= w
* sqrt(1 - (t
* t
));
691 if (rs
- (t
* t
) >= 0)
692 t
= sqrt(rs
- (t
* t
));
699 d
= b
* b
- 4 * (Z
- T
);
700 /* Because of the large magnitudes involved, we lose enough precision
701 * that sometimes we end up with a negative value near the axis, when
702 * it should be positive. This is a workaround.
704 if (d
< 0 && !solution
)
713 x
= w
* sqrt(1 - (t
* t
));
715 if (rs
- (t
* t
) >= 0)
716 *xp
++ = x
- sqrt(rs
- (t
* t
));
721 if (y
>= 0.0 && flip
== 1) {
725 x
= w
* sqrt(1 - (t
* t
));
727 if (rs
- (t
* t
) >= 0)
728 t
= sqrt(rs
- (t
* t
));
735 if (acc
->left
.valid
&& boundedLe(K
, bounds
->left
) &&
736 !boundedLe(K
, bounds
->outer
) && xs
[0] >= 0.0 && xs
[1] >= 0.0)
738 if (acc
->right
.valid
&& boundedLe(K
, bounds
->right
) &&
739 !boundedLe(K
, bounds
->inner
) && xs
[0] <= 0.0 && xs
[1] <= 0.0)
745 static miArcSpanData
*
746 miComputeWideEllipse(int lw
, xArc
* parc
)
748 miArcSpanData
*spdata
= NULL
;
753 k
= (parc
->height
>> 1) + ((lw
- 1) >> 1);
754 spdata
= malloc(sizeof(miArcSpanData
) + sizeof(miArcSpan
) * (k
+ 2));
757 spdata
->spans
= (miArcSpan
*) (spdata
+ 1);
759 spdata
->top
= !(lw
& 1) && !(parc
->width
& 1);
760 spdata
->bot
= !(parc
->height
& 1);
761 if (parc
->width
== parc
->height
)
762 miComputeCircleSpans(lw
, parc
, spdata
);
764 miComputeEllipseSpans(lw
, parc
, spdata
);
769 miFillWideEllipse(DrawablePtr pDraw
, GCPtr pGC
, xArc
* parc
)
775 miArcSpanData
*spdata
;
777 int xorg
, yorgu
, yorgl
;
780 yorgu
= parc
->height
+ pGC
->lineWidth
;
781 n
= (sizeof(int) * 2) * yorgu
;
782 widths
= malloc(n
+ (sizeof(DDXPointRec
) * 2) * yorgu
);
785 points
= (DDXPointPtr
) ((char *) widths
+ n
);
786 spdata
= miComputeWideEllipse((int) pGC
->lineWidth
, parc
);
793 span
= spdata
->spans
;
794 xorg
= parc
->x
+ (parc
->width
>> 1);
795 yorgu
= parc
->y
+ (parc
->height
>> 1);
796 yorgl
= yorgu
+ (parc
->height
& 1);
797 if (pGC
->miTranslate
) {
811 for (n
= spdata
->count1
; --n
>= 0;) {
812 pts
[0].x
= xorg
+ span
->lx
;
831 for (n
= spdata
->count2
; --n
>= 0;) {
832 pts
[0].x
= xorg
+ span
->lx
;
835 pts
[1].x
= xorg
+ span
->rx
;
852 pts
[0].x
= xorg
+ span
->lx
;
859 pts
[0].x
= xorg
+ span
->lx
;
862 pts
[1].x
= xorg
+ span
->rx
;
870 (*pGC
->ops
->FillSpans
) (pDraw
, pGC
, pts
- points
, points
, widths
, FALSE
);
876 * miPolyArc strategy:
878 * If arc is zero width and solid, we don't have to worry about the rasterop
879 * or join styles. For wide solid circles, we use a fast integer algorithm.
880 * For wide solid ellipses, we use special case floating point code.
881 * Otherwise, we set up pDrawTo and pGCTo according to the rasterop, then
882 * draw using pGCTo and pDrawTo. If the raster-op was "tricky," that is,
883 * if it involves the destination, then we use PushPixels to move the bits
884 * from the scratch drawable to pDraw. (See the wide line code for a
885 * fuller explanation of this.)
889 miPolyArc(DrawablePtr pDraw
, GCPtr pGC
, int narcs
, xArc
* parcs
)
893 int xMin
, xMax
, yMin
, yMax
;
894 int pixmapWidth
= 0, pixmapHeight
= 0;
895 int xOrg
= 0, yOrg
= 0;
901 miPolyArcPtr polyArcs
;
906 width
= pGC
->lineWidth
;
907 if (width
== 0 && pGC
->lineStyle
== LineSolid
) {
908 for (i
= narcs
, parc
= parcs
; --i
>= 0; parc
++)
909 miArcSegment(pDraw
, pGC
, *parc
, (miArcFacePtr
) 0, (miArcFacePtr
) 0);
910 fillSpans(pDraw
, pGC
);
913 if ((pGC
->lineStyle
== LineSolid
) && narcs
) {
914 while (parcs
->width
&& parcs
->height
&&
915 (parcs
->angle2
>= FULLCIRCLE
||
916 parcs
->angle2
<= -FULLCIRCLE
)) {
917 miFillWideEllipse(pDraw
, pGC
, parcs
);
924 /* Set up pDrawTo and pGCTo based on the rasterop */
926 case GXclear
: /* 0 */
927 case GXcopy
: /* src */
928 case GXcopyInverted
: /* NOT src */
937 /* find bounding box around arcs */
938 xMin
= yMin
= MAXSHORT
;
939 xMax
= yMax
= MINSHORT
;
941 for (i
= narcs
, parc
= parcs
; --i
>= 0; parc
++) {
942 xMin
= min(xMin
, parc
->x
);
943 yMin
= min(yMin
, parc
->y
);
944 xMax
= max(xMax
, (parc
->x
+ (int) parc
->width
));
945 yMax
= max(yMax
, (parc
->y
+ (int) parc
->height
));
948 /* expand box to deal with line widths */
949 halfWidth
= (width
+ 1) / 2;
955 /* compute pixmap size; limit it to size of drawable */
958 pixmapWidth
= min(xMax
, pDraw
->width
) - xOrg
;
959 pixmapHeight
= min(yMax
, pDraw
->height
) - yOrg
;
961 /* if nothing left, return */
962 if ((pixmapWidth
<= 0) || (pixmapHeight
<= 0))
965 for (i
= narcs
, parc
= parcs
; --i
>= 0; parc
++) {
969 if (pGC
->miTranslate
) {
974 /* set up scratch GC */
976 pGCTo
= GetScratchGC(1, pDraw
->pScreen
);
980 ChangeGCVal gcvals
[6];
982 gcvals
[0].val
= GXcopy
;
985 gcvals
[3].val
= pGC
->lineWidth
;
986 gcvals
[4].val
= pGC
->capStyle
;
987 gcvals
[5].val
= pGC
->joinStyle
;
988 ChangeGC(NullClient
, pGCTo
, GCFunction
|
989 GCForeground
| GCBackground
| GCLineWidth
|
990 GCCapStyle
| GCJoinStyle
, gcvals
);
993 /* allocate a 1 bit deep pixmap of the appropriate size, and
995 pDrawTo
= (DrawablePtr
) (*pDraw
->pScreen
->CreatePixmap
)
996 (pDraw
->pScreen
, pixmapWidth
, pixmapHeight
, 1,
997 CREATE_PIXMAP_USAGE_SCRATCH
);
999 FreeScratchGC(pGCTo
);
1002 ValidateGC(pDrawTo
, pGCTo
);
1003 miClearDrawable(pDrawTo
, pGCTo
);
1008 if ((pGC
->fillStyle
== FillTiled
) ||
1009 (pGC
->fillStyle
== FillOpaqueStippled
))
1010 bg
= fg
; /* the protocol sez these don't cause color changes */
1012 polyArcs
= miComputeArcs(parcs
, narcs
, pGC
);
1016 (*pDraw
->pScreen
->DestroyPixmap
) ((PixmapPtr
) pDrawTo
);
1017 FreeScratchGC(pGCTo
);
1022 cap
[0] = cap
[1] = 0;
1023 join
[0] = join
[1] = 0;
1024 for (iphase
= ((pGC
->lineStyle
== LineDoubleDash
) ? 1 : 0);
1025 iphase
>= 0; iphase
--) {
1030 ChangeGC(NullClient
, pGC
, GCForeground
, &gcval
);
1031 ValidateGC(pDraw
, pGC
);
1033 else if (pGC
->lineStyle
== LineDoubleDash
) {
1035 ChangeGC(NullClient
, pGC
, GCForeground
, &gcval
);
1036 ValidateGC(pDraw
, pGC
);
1038 for (i
= 0; i
< polyArcs
[iphase
].narcs
; i
++) {
1039 miArcDataPtr arcData
;
1041 arcData
= &polyArcs
[iphase
].arcs
[i
];
1042 miArcSegment(pDrawTo
, pGCTo
, arcData
->arc
,
1043 &arcData
->bounds
[RIGHT_END
],
1044 &arcData
->bounds
[LEFT_END
]);
1045 if (polyArcs
[iphase
].arcs
[i
].render
) {
1046 fillSpans(pDrawTo
, pGCTo
);
1048 * don't cap self-joining arcs
1050 if (polyArcs
[iphase
].arcs
[i
].selfJoin
&&
1051 cap
[iphase
] < polyArcs
[iphase
].arcs
[i
].cap
)
1053 while (cap
[iphase
] < polyArcs
[iphase
].arcs
[i
].cap
) {
1055 miArcDataPtr arcData0
;
1057 arcIndex
= polyArcs
[iphase
].caps
[cap
[iphase
]].arcIndex
;
1058 end
= polyArcs
[iphase
].caps
[cap
[iphase
]].end
;
1059 arcData0
= &polyArcs
[iphase
].arcs
[arcIndex
];
1060 miArcCap(pDrawTo
, pGCTo
,
1061 &arcData0
->bounds
[end
], end
,
1062 arcData0
->arc
.x
, arcData0
->arc
.y
,
1063 (double) arcData0
->arc
.width
/ 2.0,
1064 (double) arcData0
->arc
.height
/ 2.0);
1067 while (join
[iphase
] < polyArcs
[iphase
].arcs
[i
].join
) {
1068 int arcIndex0
, arcIndex1
, end0
, end1
;
1070 miArcDataPtr arcData0
, arcData1
;
1073 joinp
= &polyArcs
[iphase
].joins
[join
[iphase
]];
1074 arcIndex0
= joinp
->arcIndex0
;
1076 arcIndex1
= joinp
->arcIndex1
;
1078 phase0
= joinp
->phase0
;
1079 phase1
= joinp
->phase1
;
1080 arcData0
= &polyArcs
[phase0
].arcs
[arcIndex0
];
1081 arcData1
= &polyArcs
[phase1
].arcs
[arcIndex1
];
1082 miArcJoin(pDrawTo
, pGCTo
,
1083 &arcData0
->bounds
[end0
],
1084 &arcData1
->bounds
[end1
],
1085 arcData0
->arc
.x
, arcData0
->arc
.y
,
1086 (double) arcData0
->arc
.width
/ 2.0,
1087 (double) arcData0
->arc
.height
/ 2.0,
1088 arcData1
->arc
.x
, arcData1
->arc
.y
,
1089 (double) arcData1
->arc
.width
/ 2.0,
1090 (double) arcData1
->arc
.height
/ 2.0);
1094 if (pGC
->serialNumber
!= pDraw
->serialNumber
)
1095 ValidateGC(pDraw
, pGC
);
1096 (*pGC
->ops
->PushPixels
) (pGC
, (PixmapPtr
) pDrawTo
,
1098 pixmapHeight
, xOrg
, yOrg
);
1099 miClearDrawable((DrawablePtr
) pDrawTo
, pGCTo
);
1104 miFreeArcs(polyArcs
, pGC
);
1107 (*pGCTo
->pScreen
->DestroyPixmap
) ((PixmapPtr
) pDrawTo
);
1108 FreeScratchGC(pGCTo
);
1114 angleBetween(SppPointRec center
, SppPointRec point1
, SppPointRec point2
)
1119 * reflect from X coordinates back to ellipse
1120 * coordinates -- y increasing upwards
1122 a1
= miDatan2(-(point1
.y
- center
.y
), point1
.x
- center
.x
);
1123 a2
= miDatan2(-(point2
.y
- center
.y
), point2
.x
- center
.x
);
1133 translateBounds(miArcFacePtr b
, int x
, int y
, double fx
, double fy
)
1141 b
->counterClock
.x
-= fx
;
1142 b
->counterClock
.y
-= fy
;
1146 miArcJoin(DrawablePtr pDraw
, GCPtr pGC
, miArcFacePtr pLeft
,
1147 miArcFacePtr pRight
, int xOrgLeft
, int yOrgLeft
,
1148 double xFtransLeft
, double yFtransLeft
,
1149 int xOrgRight
, int yOrgRight
,
1150 double xFtransRight
, double yFtransRight
)
1152 SppPointRec center
, corner
, otherCorner
;
1153 SppPointRec poly
[5], e
;
1154 SppPointPtr pArcPts
;
1157 miArcFaceRec Right
, Left
;
1160 double xFtrans
, yFtrans
;
1162 double ae
, ac2
, ec2
, bc2
, de
;
1165 xOrg
= (xOrgRight
+ xOrgLeft
) / 2;
1166 yOrg
= (yOrgRight
+ yOrgLeft
) / 2;
1167 xFtrans
= (xFtransLeft
+ xFtransRight
) / 2;
1168 yFtrans
= (yFtransLeft
+ yFtransRight
) / 2;
1170 translateBounds(&Right
, xOrg
- xOrgRight
, yOrg
- yOrgRight
,
1171 xFtrans
- xFtransRight
, yFtrans
- yFtransRight
);
1173 translateBounds(&Left
, xOrg
- xOrgLeft
, yOrg
- yOrgLeft
,
1174 xFtrans
- xFtransLeft
, yFtrans
- yFtransLeft
);
1178 if (pRight
->clock
.x
== pLeft
->counterClock
.x
&&
1179 pRight
->clock
.y
== pLeft
->counterClock
.y
)
1181 center
= pRight
->center
;
1182 if (0 <= (a
= angleBetween(center
, pRight
->clock
, pLeft
->counterClock
))
1184 corner
= pRight
->clock
;
1185 otherCorner
= pLeft
->counterClock
;
1188 a
= angleBetween(center
, pLeft
->clock
, pRight
->counterClock
);
1189 corner
= pLeft
->clock
;
1190 otherCorner
= pRight
->counterClock
;
1192 switch (pGC
->joinStyle
) {
1194 width
= (pGC
->lineWidth
? (double) pGC
->lineWidth
: (double) 1);
1196 arc
.x
= center
.x
- width
/ 2;
1197 arc
.y
= center
.y
- width
/ 2;
1200 arc
.angle1
= -miDatan2(corner
.y
- center
.y
, corner
.x
- center
.x
);
1202 pArcPts
= malloc(3 * sizeof(SppPointRec
));
1205 pArcPts
[0].x
= otherCorner
.x
;
1206 pArcPts
[0].y
= otherCorner
.y
;
1207 pArcPts
[1].x
= center
.x
;
1208 pArcPts
[1].y
= center
.y
;
1209 pArcPts
[2].x
= corner
.x
;
1210 pArcPts
[2].y
= corner
.y
;
1211 if ((cpt
= miGetArcPts(&arc
, 3, &pArcPts
))) {
1212 /* by drawing with miFillSppPoly and setting the endpoints of the arc
1213 * to be the corners, we assure that the cap will meet up with the
1214 * rest of the line */
1215 miFillSppPoly(pDraw
, pGC
, cpt
, pArcPts
, xOrg
, yOrg
, xFtrans
,
1222 * don't miter arcs with less than 11 degrees between them
1227 poly
[2] = otherCorner
;
1228 bc2
= (corner
.x
- otherCorner
.x
) * (corner
.x
- otherCorner
.x
) +
1229 (corner
.y
- otherCorner
.y
) * (corner
.y
- otherCorner
.y
);
1231 ac2
= (corner
.x
- center
.x
) * (corner
.x
- center
.x
) +
1232 (corner
.y
- center
.y
) * (corner
.y
- center
.y
);
1233 ae
= sqrt(ac2
- ec2
);
1235 e
.x
= (corner
.x
+ otherCorner
.x
) / 2;
1236 e
.y
= (corner
.y
+ otherCorner
.y
) / 2;
1237 poly
[3].x
= e
.x
+ de
* (e
.x
- center
.x
) / ae
;
1238 poly
[3].y
= e
.y
+ de
* (e
.y
- center
.y
) / ae
;
1246 poly
[2] = otherCorner
;
1251 miFillSppPoly(pDraw
, pGC
, polyLen
, poly
, xOrg
, yOrg
, xFtrans
, yFtrans
);
1254 /*ARGSUSED*/ static void
1255 miArcCap(DrawablePtr pDraw
,
1258 int end
, int xOrg
, int yOrg
, double xFtrans
, double yFtrans
)
1260 SppPointRec corner
, otherCorner
, center
, endPoint
, poly
[5];
1262 corner
= pFace
->clock
;
1263 otherCorner
= pFace
->counterClock
;
1264 center
= pFace
->center
;
1265 switch (pGC
->capStyle
) {
1267 poly
[0].x
= otherCorner
.x
;
1268 poly
[0].y
= otherCorner
.y
;
1269 poly
[1].x
= corner
.x
;
1270 poly
[1].y
= corner
.y
;
1271 poly
[2].x
= corner
.x
- (center
.y
- corner
.y
);
1272 poly
[2].y
= corner
.y
+ (center
.x
- corner
.x
);
1273 poly
[3].x
= otherCorner
.x
- (otherCorner
.y
- center
.y
);
1274 poly
[3].y
= otherCorner
.y
+ (otherCorner
.x
- center
.x
);
1275 poly
[4].x
= otherCorner
.x
;
1276 poly
[4].y
= otherCorner
.y
;
1277 miFillSppPoly(pDraw
, pGC
, 5, poly
, xOrg
, yOrg
, xFtrans
, yFtrans
);
1281 * miRoundCap just needs these to be unequal.
1284 endPoint
.x
= endPoint
.x
+ 100;
1285 miRoundCap(pDraw
, pGC
, center
, endPoint
, corner
, otherCorner
, 0,
1286 -xOrg
, -yOrg
, xFtrans
, yFtrans
);
1291 /* MIROUNDCAP -- a private helper function
1292 * Put Rounded cap on end. pCenter is the center of this end of the line
1293 * pEnd is the center of the other end of the line. pCorner is one of the
1294 * two corners at this end of the line.
1295 * NOTE: pOtherCorner must be counter-clockwise from pCorner.
1297 /*ARGSUSED*/ static void
1298 miRoundCap(DrawablePtr pDraw
,
1300 SppPointRec pCenter
,
1302 SppPointRec pCorner
,
1303 SppPointRec pOtherCorner
,
1304 int fLineEnd
, int xOrg
, int yOrg
, double xFtrans
, double yFtrans
)
1309 SppPointPtr pArcPts
;
1311 width
= (pGC
->lineWidth
? (double) pGC
->lineWidth
: (double) 1);
1313 arc
.x
= pCenter
.x
- width
/ 2;
1314 arc
.y
= pCenter
.y
- width
/ 2;
1317 arc
.angle1
= -miDatan2(pCorner
.y
- pCenter
.y
, pCorner
.x
- pCenter
.x
);
1318 if (PTISEQUAL(pCenter
, pEnd
))
1319 arc
.angle2
= -180.0;
1322 -miDatan2(pOtherCorner
.y
- pCenter
.y
,
1323 pOtherCorner
.x
- pCenter
.x
) - arc
.angle1
;
1325 arc
.angle2
+= 360.0;
1327 pArcPts
= (SppPointPtr
) NULL
;
1328 if ((cpt
= miGetArcPts(&arc
, 0, &pArcPts
))) {
1329 /* by drawing with miFillSppPoly and setting the endpoints of the arc
1330 * to be the corners, we assure that the cap will meet up with the
1331 * rest of the line */
1332 miFillSppPoly(pDraw
, pGC
, cpt
, pArcPts
, -xOrg
, -yOrg
, xFtrans
, yFtrans
);
1338 * To avoid inaccuracy at the cardinal points, use trig functions
1339 * which are exact for those angles
1343 #define M_PI 3.14159265358979323846
1346 #define M_PI_2 1.57079632679489661923
1349 #define Dsin(d) ((d) == 0.0 ? 0.0 : ((d) == 90.0 ? 1.0 : sin(d*M_PI/180.0)))
1350 #define Dcos(d) ((d) == 0.0 ? 1.0 : ((d) == 90.0 ? 0.0 : cos(d*M_PI/180.0)))
1351 #define mod(a,b) ((a) >= 0 ? (a) % (b) : (b) - (-(a)) % (b))
1358 if (floor(a
/ 90) == a
/ 90) {
1359 i
= (int) (a
/ 90.0);
1360 switch (mod(i
, 4)) {
1371 return cos(a
* M_PI
/ 180.0);
1379 if (floor(a
/ 90) == a
/ 90) {
1380 i
= (int) (a
/ 90.0);
1381 switch (mod(i
, 4)) {
1392 return sin(a
* M_PI
/ 180.0);
1404 return asin(v
) * (180.0 / M_PI
);
1408 miDatan2(double dy
, double dx
)
1420 else if (fabs(dy
) == fabs(dx
)) {
1433 return atan2(dy
, dx
) * (180.0 / M_PI
);
1437 /* MIGETARCPTS -- Converts an arc into a set of line segments -- a helper
1438 * routine for filled arc and line (round cap) code.
1439 * Returns the number of points in the arc. Note that it takes a pointer
1440 * to a pointer to where it should put the points and an index (cpt).
1441 * This procedure allocates the space necessary to fit the arc points.
1442 * Sometimes it's convenient for those points to be at the end of an existing
1443 * array. (For example, if we want to leave a spare point to make sectors
1444 * instead of segments.) So we pass in the malloc()ed chunk that contains the
1445 * array and an index saying where we should start stashing the points.
1446 * If there isn't an array already, we just pass in a null pointer and
1447 * count on realloc() to handle the null pointer correctly.
1450 miGetArcPts(SppArcPtr parc
, /* points to an arc */
1451 int cpt
, /* number of points already in arc list */
1452 SppPointPtr
* ppPts
)
1453 { /* pointer to pointer to arc-list -- modified */
1454 double st
, /* Start Theta, start angle */
1455 et
, /* End Theta, offset from start theta */
1456 dt
, /* Delta Theta, angle to sweep ellipse */
1457 cdt
, /* Cos Delta Theta, actually 2 cos(dt) */
1458 x0
, y0
, /* the recurrence formula needs two points to start */
1459 x1
, y1
, x2
, y2
, /* this will be the new point generated */
1460 xc
, yc
; /* the center point */
1464 /* The spec says that positive angles indicate counterclockwise motion.
1465 * Given our coordinate system (with 0,0 in the upper left corner),
1466 * the screen appears flipped in Y. The easiest fix is to negate the
1473 /* Try to get a delta theta that is within 1/2 pixel. Then adjust it
1474 * so that it divides evenly into the total.
1475 * I'm just using cdt 'cause I'm lazy.
1478 if (parc
->height
> cdt
)
1485 dt
= miDasin(1.0 / cdt
); /* minimum step necessary */
1487 count
= abs(count
) + 1;
1491 cdt
= 2 * miDcos(dt
);
1492 if (!(poly
= (SppPointPtr
) realloc((pointer
) *ppPts
,
1493 (cpt
+ count
) * sizeof(SppPointRec
))))
1497 xc
= parc
->width
/ 2.0; /* store half width and half height */
1498 yc
= parc
->height
/ 2.0;
1500 x0
= xc
* miDcos(st
);
1501 y0
= yc
* miDsin(st
);
1502 x1
= xc
* miDcos(st
+ dt
);
1503 y1
= yc
* miDsin(st
+ dt
);
1504 xc
+= parc
->x
; /* by adding initial point, these become */
1505 yc
+= parc
->y
; /* the center point */
1507 poly
[cpt
].x
= (xc
+ x0
);
1508 poly
[cpt
].y
= (yc
+ y0
);
1509 poly
[cpt
+ 1].x
= (xc
+ x1
);
1510 poly
[cpt
+ 1].y
= (yc
+ y1
);
1512 for (i
= 2; i
< count
; i
++) {
1516 poly
[cpt
+ i
].x
= (xc
+ x2
);
1517 poly
[cpt
+ i
].y
= (yc
+ y2
);
1524 /* adjust the last point */
1525 if (abs(parc
->angle2
) >= 360.0)
1526 poly
[cpt
+ i
- 1] = poly
[0];
1528 poly
[cpt
+ i
- 1].x
= (miDcos(st
+ et
) * parc
->width
/ 2.0 + xc
);
1529 poly
[cpt
+ i
- 1].y
= (miDsin(st
+ et
) * parc
->height
/ 2.0 + yc
);
1536 double x0
, y0
, x1
, y1
;
1540 #define ADD_REALLOC_STEP 20
1543 addCap(miArcCapPtr
* capsp
, int *ncapsp
, int *sizep
, int end
, int arcIndex
)
1548 if (*ncapsp
== *sizep
) {
1549 newsize
= *sizep
+ ADD_REALLOC_STEP
;
1550 cap
= (miArcCapPtr
) realloc(*capsp
, newsize
* sizeof(**capsp
));
1556 cap
= &(*capsp
)[*ncapsp
];
1558 cap
->arcIndex
= arcIndex
;
1563 addJoin(miArcJoinPtr
* joinsp
,
1566 int end0
, int index0
, int phase0
, int end1
, int index1
, int phase1
)
1571 if (*njoinsp
== *sizep
) {
1572 newsize
= *sizep
+ ADD_REALLOC_STEP
;
1573 join
= (miArcJoinPtr
) realloc(*joinsp
, newsize
* sizeof(**joinsp
));
1579 join
= &(*joinsp
)[*njoinsp
];
1581 join
->arcIndex0
= index0
;
1582 join
->phase0
= phase0
;
1584 join
->arcIndex1
= index1
;
1585 join
->phase1
= phase1
;
1590 addArc(miArcDataPtr
* arcsp
, int *narcsp
, int *sizep
, xArc
* xarc
)
1595 if (*narcsp
== *sizep
) {
1596 newsize
= *sizep
+ ADD_REALLOC_STEP
;
1597 arc
= (miArcDataPtr
) realloc(*arcsp
, newsize
* sizeof(**arcsp
));
1603 arc
= &(*arcsp
)[*narcsp
];
1610 miFreeArcs(miPolyArcPtr arcs
, GCPtr pGC
)
1614 for (iphase
= ((pGC
->lineStyle
== LineDoubleDash
) ? 1 : 0);
1615 iphase
>= 0; iphase
--) {
1616 if (arcs
[iphase
].narcs
> 0)
1617 free(arcs
[iphase
].arcs
);
1618 if (arcs
[iphase
].njoins
> 0)
1619 free(arcs
[iphase
].joins
);
1620 if (arcs
[iphase
].ncaps
> 0)
1621 free(arcs
[iphase
].caps
);
1627 * map angles to radial distance. This only deals with the first quadrant
1631 * a polygonal approximation to the arc for computing arc lengths
1634 #define DASH_MAP_SIZE 91
1636 #define dashIndexToAngle(di) ((((double) (di)) * 90.0) / ((double) DASH_MAP_SIZE - 1))
1637 #define xAngleToDashIndex(xa) ((((long) (xa)) * (DASH_MAP_SIZE - 1)) / (90 * 64))
1638 #define dashIndexToXAngle(di) ((((long) (di)) * (90 * 64)) / (DASH_MAP_SIZE - 1))
1639 #define dashXAngleStep (((double) (90 * 64)) / ((double) (DASH_MAP_SIZE - 1)))
1642 double map
[DASH_MAP_SIZE
];
1645 static int computeAngleFromPath(int startAngle
, int endAngle
, dashMap
* map
,
1646 int *lenp
, int backwards
);
1649 computeDashMap(xArc
* arcp
, dashMap
* map
)
1652 double a
, x
, y
, prevx
= 0.0, prevy
= 0.0, dist
;
1654 for (di
= 0; di
< DASH_MAP_SIZE
; di
++) {
1655 a
= dashIndexToAngle(di
);
1656 x
= ((double) arcp
->width
/ 2.0) * miDcos(a
);
1657 y
= ((double) arcp
->height
/ 2.0) * miDsin(a
);
1662 dist
= hypot(x
- prevx
, y
- prevy
);
1663 map
->map
[di
] = map
->map
[di
- 1] + dist
;
1670 typedef enum { HORIZONTAL
, VERTICAL
, OTHER
} arcTypes
;
1672 /* this routine is a bit gory */
1675 miComputeArcs(xArc
* parcs
, int narcs
, GCPtr pGC
)
1677 int isDashed
, isDoubleDash
;
1680 int start
, i
, j
, k
= 0, nexti
, nextk
= 0;
1686 struct arcData
*data
;
1689 int iphase
, prevphase
= 0, joinphase
;
1693 int iDash
= 0, dashRemaining
= 0;
1694 int iDashStart
= 0, dashRemainingStart
= 0, iphaseStart
;
1695 int startAngle
, spanAngle
, endAngle
, backwards
= 0;
1696 int prevDashAngle
, dashAngle
;
1699 isDashed
= !(pGC
->lineStyle
== LineSolid
);
1700 isDoubleDash
= (pGC
->lineStyle
== LineDoubleDash
);
1701 dashOffset
= pGC
->dashOffset
;
1703 data
= malloc(narcs
* sizeof(struct arcData
));
1706 arcs
= malloc(sizeof(*arcs
) * (isDoubleDash
? 2 : 1));
1711 for (i
= 0; i
< narcs
; i
++) {
1712 a0
= todeg(parcs
[i
].angle1
);
1713 angle2
= parcs
[i
].angle2
;
1714 if (angle2
> FULLCIRCLE
)
1715 angle2
= FULLCIRCLE
;
1716 else if (angle2
< -FULLCIRCLE
)
1717 angle2
= -FULLCIRCLE
;
1718 data
[i
].selfJoin
= angle2
== FULLCIRCLE
|| angle2
== -FULLCIRCLE
;
1719 a1
= todeg(parcs
[i
].angle1
+ angle2
);
1721 parcs
[i
].x
+ (double) parcs
[i
].width
/ 2 * (1 + miDcos(a0
));
1723 parcs
[i
].y
+ (double) parcs
[i
].height
/ 2 * (1 - miDsin(a0
));
1725 parcs
[i
].x
+ (double) parcs
[i
].width
/ 2 * (1 + miDcos(a1
));
1727 parcs
[i
].y
+ (double) parcs
[i
].height
/ 2 * (1 - miDsin(a1
));
1730 for (iphase
= 0; iphase
< (isDoubleDash
? 2 : 1); iphase
++) {
1731 arcs
[iphase
].njoins
= 0;
1732 arcs
[iphase
].joins
= 0;
1733 joinSize
[iphase
] = 0;
1735 arcs
[iphase
].ncaps
= 0;
1736 arcs
[iphase
].caps
= 0;
1737 capSize
[iphase
] = 0;
1739 arcs
[iphase
].narcs
= 0;
1740 arcs
[iphase
].arcs
= 0;
1741 arcSize
[iphase
] = 0;
1747 dashRemaining
= pGC
->dash
[0];
1748 while (dashOffset
> 0) {
1749 if (dashOffset
>= dashRemaining
) {
1750 dashOffset
-= dashRemaining
;
1751 iphase
= iphase
? 0 : 1;
1753 if (iDash
== pGC
->numInDashList
)
1755 dashRemaining
= pGC
->dash
[iDash
];
1758 dashRemaining
-= dashOffset
;
1763 dashRemainingStart
= dashRemaining
;
1765 iphaseStart
= iphase
;
1767 for (i
= narcs
- 1; i
>= 0; i
--) {
1771 if (data
[i
].selfJoin
|| i
== j
||
1772 (UNEQUAL(data
[i
].x1
, data
[j
].x0
) ||
1773 UNEQUAL(data
[i
].y1
, data
[j
].y0
))) {
1774 if (iphase
== 0 || isDoubleDash
)
1775 addCap(&arcs
[iphase
].caps
, &arcs
[iphase
].ncaps
,
1776 &capSize
[iphase
], RIGHT_END
, 0);
1793 ** deal with dashed arcs. Use special rules for certain 0 area arcs.
1794 ** Presumably, the other 0 area arcs still aren't done right.
1796 arcTypes arcType
= OTHER
;
1799 if (parcs
[i
].height
== 0
1800 && (parcs
[i
].angle1
% FULLCIRCLE
) == 0x2d00
1801 && parcs
[i
].angle2
== 0x2d00)
1802 arcType
= HORIZONTAL
;
1803 else if (parcs
[i
].width
== 0
1804 && (parcs
[i
].angle1
% FULLCIRCLE
) == 0x1680
1805 && parcs
[i
].angle2
== 0x2d00)
1807 if (arcType
== OTHER
) {
1809 * precompute an approximation map
1811 computeDashMap(&parcs
[i
], &map
);
1813 * compute each individual dash segment using the path
1816 startAngle
= parcs
[i
].angle1
;
1817 spanAngle
= parcs
[i
].angle2
;
1818 if (spanAngle
> FULLCIRCLE
)
1819 spanAngle
= FULLCIRCLE
;
1820 else if (spanAngle
< -FULLCIRCLE
)
1821 spanAngle
= -FULLCIRCLE
;
1823 startAngle
= FULLCIRCLE
- (-startAngle
) % FULLCIRCLE
;
1824 if (startAngle
>= FULLCIRCLE
)
1825 startAngle
= startAngle
% FULLCIRCLE
;
1826 endAngle
= startAngle
+ spanAngle
;
1827 backwards
= spanAngle
< 0;
1831 if (arcType
== VERTICAL
) {
1832 xarc
.angle1
= 0x1680;
1833 startAngle
= parcs
[i
].y
;
1834 endAngle
= startAngle
+ parcs
[i
].height
;
1837 xarc
.angle1
= 0x2d00;
1838 startAngle
= parcs
[i
].x
;
1839 endAngle
= startAngle
+ parcs
[i
].width
;
1842 dashAngle
= startAngle
;
1843 selfJoin
= data
[i
].selfJoin
&& (iphase
== 0 || isDoubleDash
);
1845 * add dashed arcs to each bucket
1848 while (dashAngle
!= endAngle
) {
1849 prevDashAngle
= dashAngle
;
1850 if (arcType
== OTHER
) {
1851 dashAngle
= computeAngleFromPath(prevDashAngle
, endAngle
,
1852 &map
, &dashRemaining
,
1854 /* avoid troubles with huge arcs and small dashes */
1855 if (dashAngle
== prevDashAngle
) {
1863 thisLength
= (dashAngle
+ dashRemaining
<= endAngle
) ?
1864 dashRemaining
: endAngle
- dashAngle
;
1865 if (arcType
== VERTICAL
) {
1867 xarc
.height
= thisLength
;
1871 xarc
.width
= thisLength
;
1873 dashAngle
+= thisLength
;
1874 dashRemaining
-= thisLength
;
1876 if (iphase
== 0 || isDoubleDash
) {
1877 if (arcType
== OTHER
) {
1879 spanAngle
= prevDashAngle
;
1881 spanAngle
= FULLCIRCLE
- (-spanAngle
) % FULLCIRCLE
;
1882 if (spanAngle
>= FULLCIRCLE
)
1883 spanAngle
= spanAngle
% FULLCIRCLE
;
1884 xarc
.angle1
= spanAngle
;
1885 spanAngle
= dashAngle
- prevDashAngle
;
1887 if (dashAngle
> prevDashAngle
)
1888 spanAngle
= -FULLCIRCLE
+ spanAngle
;
1891 if (dashAngle
< prevDashAngle
)
1892 spanAngle
= FULLCIRCLE
+ spanAngle
;
1894 if (spanAngle
> FULLCIRCLE
)
1895 spanAngle
= FULLCIRCLE
;
1896 if (spanAngle
< -FULLCIRCLE
)
1897 spanAngle
= -FULLCIRCLE
;
1898 xarc
.angle2
= spanAngle
;
1900 arc
= addArc(&arcs
[iphase
].arcs
, &arcs
[iphase
].narcs
,
1901 &arcSize
[iphase
], &xarc
);
1905 * cap each end of an on/off dash
1907 if (!isDoubleDash
) {
1908 if (prevDashAngle
!= startAngle
) {
1909 addCap(&arcs
[iphase
].caps
,
1910 &arcs
[iphase
].ncaps
,
1911 &capSize
[iphase
], RIGHT_END
,
1912 arc
- arcs
[iphase
].arcs
);
1915 if (dashAngle
!= endAngle
) {
1916 addCap(&arcs
[iphase
].caps
,
1917 &arcs
[iphase
].ncaps
,
1918 &capSize
[iphase
], LEFT_END
,
1919 arc
- arcs
[iphase
].arcs
);
1922 arc
->cap
= arcs
[iphase
].ncaps
;
1923 arc
->join
= arcs
[iphase
].njoins
;
1926 if (dashAngle
== endAngle
)
1927 arc
->selfJoin
= selfJoin
;
1930 if (dashRemaining
<= 0) {
1932 if (iDash
== pGC
->numInDashList
)
1934 iphase
= iphase
? 0 : 1;
1935 dashRemaining
= pGC
->dash
[iDash
];
1939 * make sure a place exists for the position data when
1940 * drawing a zero-length arc
1942 if (startAngle
== endAngle
) {
1944 if (!isDoubleDash
&& iphase
== 1)
1946 arc
= addArc(&arcs
[prevphase
].arcs
, &arcs
[prevphase
].narcs
,
1947 &arcSize
[prevphase
], &parcs
[i
]);
1950 arc
->join
= arcs
[prevphase
].njoins
;
1951 arc
->cap
= arcs
[prevphase
].ncaps
;
1952 arc
->selfJoin
= data
[i
].selfJoin
;
1956 arc
= addArc(&arcs
[iphase
].arcs
, &arcs
[iphase
].narcs
,
1957 &arcSize
[iphase
], &parcs
[i
]);
1960 arc
->join
= arcs
[iphase
].njoins
;
1961 arc
->cap
= arcs
[iphase
].ncaps
;
1962 arc
->selfJoin
= data
[i
].selfJoin
;
1965 if (prevphase
== 0 || isDoubleDash
)
1966 k
= arcs
[prevphase
].narcs
- 1;
1967 if (iphase
== 0 || isDoubleDash
)
1968 nextk
= arcs
[iphase
].narcs
;
1969 if (nexti
== start
) {
1973 iphase
= iphaseStart
;
1974 dashRemaining
= dashRemainingStart
;
1977 arcsJoin
= narcs
> 1 && i
!= j
&&
1978 ISEQUAL(data
[i
].x1
, data
[j
].x0
) &&
1979 ISEQUAL(data
[i
].y1
, data
[j
].y0
) &&
1980 !data
[i
].selfJoin
&& !data
[j
].selfJoin
;
1988 (prevphase
== 0 || isDoubleDash
) && (iphase
== 0 || isDoubleDash
)) {
1992 joinphase
= iphaseStart
;
1994 * if the join is right at the dash,
1995 * draw the join in foreground
1996 * This is because the foreground
1997 * arcs are computed second, the results
1998 * of which are needed to draw the join
2000 if (joinphase
!= prevphase
)
2003 if (joinphase
== 0 || isDoubleDash
) {
2004 addJoin(&arcs
[joinphase
].joins
,
2005 &arcs
[joinphase
].njoins
,
2006 &joinSize
[joinphase
],
2007 LEFT_END
, k
, prevphase
, RIGHT_END
, nextk
, iphase
);
2008 arc
->join
= arcs
[prevphase
].njoins
;
2013 * cap the left end of this arc
2014 * unless it joins itself
2016 if ((prevphase
== 0 || isDoubleDash
) && !arc
->selfJoin
) {
2017 addCap(&arcs
[prevphase
].caps
, &arcs
[prevphase
].ncaps
,
2018 &capSize
[prevphase
], LEFT_END
, k
);
2019 arc
->cap
= arcs
[prevphase
].ncaps
;
2021 if (isDashed
&& !arcsJoin
) {
2023 iphase
= iphaseStart
;
2024 dashRemaining
= dashRemainingStart
;
2026 nextk
= arcs
[iphase
].narcs
;
2027 if (nexti
== start
) {
2030 iphase
= iphaseStart
;
2031 dashRemaining
= dashRemainingStart
;
2034 * cap the right end of the next arc. If the
2035 * next arc is actually the first arc, only
2036 * cap it if it joins with this arc. This
2037 * case will occur when the final dash segment
2038 * of an on/off dash is off. Of course, this
2039 * cap will be drawn at a strange time, but that
2042 if ((iphase
== 0 || isDoubleDash
) &&
2043 (nexti
!= start
|| (arcsJoin
&& isDashed
)))
2044 addCap(&arcs
[iphase
].caps
, &arcs
[iphase
].ncaps
,
2045 &capSize
[iphase
], RIGHT_END
, nextk
);
2052 * make sure the last section is rendered
2054 for (iphase
= 0; iphase
< (isDoubleDash
? 2 : 1); iphase
++)
2055 if (arcs
[iphase
].narcs
> 0) {
2056 arcs
[iphase
].arcs
[arcs
[iphase
].narcs
- 1].render
= 1;
2057 arcs
[iphase
].arcs
[arcs
[iphase
].narcs
- 1].join
=
2058 arcs
[iphase
].njoins
;
2059 arcs
[iphase
].arcs
[arcs
[iphase
].narcs
- 1].cap
= arcs
[iphase
].ncaps
;
2064 miFreeArcs(arcs
, pGC
);
2070 angleToLength(int angle
, dashMap
* map
)
2072 double len
, excesslen
, sidelen
= map
->map
[DASH_MAP_SIZE
- 1], totallen
;
2075 Bool oddSide
= FALSE
;
2079 while (angle
>= 90 * 64) {
2081 totallen
+= sidelen
;
2088 totallen
-= sidelen
;
2093 angle
= 90 * 64 - angle
;
2095 di
= xAngleToDashIndex(angle
);
2096 excess
= angle
- dashIndexToXAngle(di
);
2100 * linearly interpolate between this point and the next
2103 excesslen
= (map
->map
[di
+ 1] - map
->map
[di
]) *
2104 ((double) excess
) / dashXAngleStep
;
2108 totallen
+= (sidelen
- len
);
2115 * len is along the arc, but may be more than one rotation
2119 lengthToAngle(double len
, dashMap
* map
)
2121 double sidelen
= map
->map
[DASH_MAP_SIZE
- 1];
2122 int angle
, angleexcess
;
2123 Bool oddSide
= FALSE
;
2128 * step around the ellipse, subtracting sidelens and
2129 * adding 90 degrees. oddSide will tell if the
2130 * map should be interpolated in reverse
2134 return 2 * FULLCIRCLE
; /* infinity */
2135 while (len
>= sidelen
) {
2143 return -2 * FULLCIRCLE
; /* infinity */
2151 len
= sidelen
- len
;
2153 a1
= DASH_MAP_SIZE
- 1;
2155 * binary search for the closest pre-computed length
2157 while (a1
- a0
> 1) {
2159 if (len
> map
->map
[a
])
2164 angleexcess
= dashIndexToXAngle(a0
);
2166 * linearly interpolate to the next point
2168 angleexcess
+= (len
- map
->map
[a0
]) /
2169 (map
->map
[a0
+ 1] - map
->map
[a0
]) * dashXAngleStep
;
2171 angle
+= (90 * 64) - angleexcess
;
2173 angle
+= angleexcess
;
2178 * compute the angle of an ellipse which cooresponds to
2179 * the given path length. Note that the correct solution
2180 * to this problem is an eliptic integral, we'll punt and
2181 * approximate (it's only for dashes anyway). This
2182 * approximation uses a polygon.
2184 * The remaining portion of len is stored in *lenp -
2185 * this will be negative if the arc extends beyond
2186 * len and positive if len extends beyond the arc.
2190 computeAngleFromPath(int startAngle
, int endAngle
, /* normalized absolute angles in *64 degrees */
2191 dashMap
* map
, int *lenp
, int backwards
)
2202 * flip the problem around to always be
2205 a0
= FULLCIRCLE
- a0
;
2206 a1
= FULLCIRCLE
- a1
;
2210 len0
= angleToLength(a0
, map
);
2211 a
= lengthToAngle(len0
+ len
, map
);
2214 len
-= angleToLength(a1
, map
) - len0
;
2225 * scan convert wide arcs.
2229 * draw zero width/height arcs
2233 drawZeroArc(DrawablePtr pDraw
,
2235 xArc
* tarc
, int lw
, miArcFacePtr left
, miArcFacePtr right
)
2237 double x0
= 0.0, y0
= 0.0, x1
= 0.0, y1
= 0.0, w
, h
, x
, y
;
2238 double xmax
, ymax
, xmin
, ymin
;
2240 double a
, startAngle
, endAngle
;
2246 if (a1
> FULLCIRCLE
)
2248 else if (a1
< -FULLCIRCLE
)
2250 w
= (double) tarc
->width
/ 2.0;
2251 h
= (double) tarc
->height
/ 2.0;
2253 * play in X coordinates right away
2255 startAngle
= -((double) a0
/ 64.0);
2256 endAngle
= -((double) (a0
+ a1
) / 64.0);
2266 if (a
== startAngle
) {
2270 if (a
== endAngle
) {
2284 if (a1
< 0) { /* clockwise */
2285 if (floor(a
/ 90.0) == floor(endAngle
/ 90.0))
2288 a
= 90 * (floor(a
/ 90.0) + 1);
2291 if (ceil(a
/ 90.0) == ceil(endAngle
/ 90.0))
2294 a
= 90 * (ceil(a
/ 90.0) - 1);
2298 if ((x1
- x0
) + (y1
- y0
) < 0)
2307 right
->center
.x
= x0
;
2308 right
->center
.y
= y0
;
2309 right
->clock
.x
= x0
- lx
;
2310 right
->clock
.y
= y0
- ly
;
2311 right
->counterClock
.x
= x0
+ lx
;
2312 right
->counterClock
.y
= y0
+ ly
;
2315 left
->center
.x
= x1
;
2316 left
->center
.y
= y1
;
2317 left
->clock
.x
= x1
+ lx
;
2318 left
->clock
.y
= y1
+ ly
;
2319 left
->counterClock
.x
= x1
- lx
;
2320 left
->counterClock
.y
= y1
- ly
;
2335 if (xmax
!= xmin
&& ymax
!= ymin
) {
2336 int minx
, maxx
, miny
, maxy
;
2339 minx
= ICEIL(xmin
+ w
) + tarc
->x
;
2340 maxx
= ICEIL(xmax
+ w
) + tarc
->x
;
2341 miny
= ICEIL(ymin
+ h
) + tarc
->y
;
2342 maxy
= ICEIL(ymax
+ h
) + tarc
->y
;
2345 rect
.width
= maxx
- minx
;
2346 rect
.height
= maxy
- miny
;
2347 (*pGC
->ops
->PolyFillRect
) (pDraw
, pGC
, 1, &rect
);
2352 * this computes the ellipse y value associated with the
2353 * bottom of the tail.
2357 tailEllipseY(struct arc_def
*def
, struct accelerators
*acc
)
2362 if (def
->w
== def
->h
)
2364 t
= def
->l
* def
->w
;
2365 if (def
->w
> def
->h
) {
2373 t
= 2.0 * def
->h
* t
;
2374 t
= (CUBED_ROOT_4
* acc
->h2
- cbrt(t
* t
)) / acc
->h2mw2
;
2376 acc
->tail_y
= def
->h
/ CUBED_ROOT_2
* sqrt(t
);
2380 * inverse functions -- compute edge coordinates
2385 outerXfromXY(double x
, double y
, struct arc_def
*def
, struct accelerators
*acc
)
2387 return x
+ (x
* acc
->h2l
) / sqrt(x
* x
* acc
->h4
+ y
* y
* acc
->w4
);
2391 outerYfromXY(double x
, double y
, struct arc_def
*def
, struct accelerators
*acc
)
2393 return y
+ (y
* acc
->w2l
) / sqrt(x
* x
* acc
->h4
+ y
* y
* acc
->w4
);
2397 innerXfromXY(double x
, double y
, struct arc_def
*def
, struct accelerators
*acc
)
2399 return x
- (x
* acc
->h2l
) / sqrt(x
* x
* acc
->h4
+ y
* y
* acc
->w4
);
2403 innerYfromXY(double x
, double y
, struct arc_def
*def
, struct accelerators
*acc
)
2405 return y
- (y
* acc
->w2l
) / sqrt(x
* x
* acc
->h4
+ y
* y
* acc
->w4
);
2409 innerYfromY(double y
, struct arc_def
*def
, struct accelerators
*acc
)
2413 x
= (def
->w
/ def
->h
) * sqrt(acc
->h2
- y
* y
);
2415 return y
- (y
* acc
->w2l
) / sqrt(x
* x
* acc
->h4
+ y
* y
* acc
->w4
);
2419 computeLine(double x1
, double y1
, double x2
, double y2
, struct line
*line
)
2424 line
->m
= (x1
- x2
) / (y1
- y2
);
2425 line
->b
= x1
- y1
* line
->m
;
2431 * compute various accelerators for an ellipse. These
2432 * are simply values that are used repeatedly in
2437 computeAcc(xArc
* tarc
, int lw
, struct arc_def
*def
, struct accelerators
*acc
)
2439 def
->w
= ((double) tarc
->width
) / 2.0;
2440 def
->h
= ((double) tarc
->height
) / 2.0;
2441 def
->l
= ((double) lw
) / 2.0;
2442 acc
->h2
= def
->h
* def
->h
;
2443 acc
->w2
= def
->w
* def
->w
;
2444 acc
->h4
= acc
->h2
* acc
->h2
;
2445 acc
->w4
= acc
->w2
* acc
->w2
;
2446 acc
->h2l
= acc
->h2
* def
->l
;
2447 acc
->w2l
= acc
->w2
* def
->l
;
2448 acc
->h2mw2
= acc
->h2
- acc
->w2
;
2449 acc
->fromIntX
= (tarc
->width
& 1) ? 0.5 : 0.0;
2450 acc
->fromIntY
= (tarc
->height
& 1) ? 0.5 : 0.0;
2451 acc
->xorg
= tarc
->x
+ (tarc
->width
>> 1);
2452 acc
->yorgu
= tarc
->y
+ (tarc
->height
>> 1);
2453 acc
->yorgl
= acc
->yorgu
+ (tarc
->height
& 1);
2454 tailEllipseY(def
, acc
);
2458 * compute y value bounds of various portions of the arc,
2459 * the outer edge, the ellipse and the inner edge.
2463 computeBound(struct arc_def
*def
,
2464 struct arc_bound
*bound
,
2465 struct accelerators
*acc
, miArcFacePtr right
, miArcFacePtr left
)
2470 struct bound innerx
, outerx
;
2471 struct bound ellipsex
;
2473 bound
->ellipse
.min
= Dsin(def
->a0
) * def
->h
;
2474 bound
->ellipse
.max
= Dsin(def
->a1
) * def
->h
;
2475 if (def
->a0
== 45 && def
->w
== def
->h
)
2476 ellipsex
.min
= bound
->ellipse
.min
;
2478 ellipsex
.min
= Dcos(def
->a0
) * def
->w
;
2479 if (def
->a1
== 45 && def
->w
== def
->h
)
2480 ellipsex
.max
= bound
->ellipse
.max
;
2482 ellipsex
.max
= Dcos(def
->a1
) * def
->w
;
2483 bound
->outer
.min
= outerYfromXY(ellipsex
.min
, bound
->ellipse
.min
, def
, acc
);
2484 bound
->outer
.max
= outerYfromXY(ellipsex
.max
, bound
->ellipse
.max
, def
, acc
);
2485 bound
->inner
.min
= innerYfromXY(ellipsex
.min
, bound
->ellipse
.min
, def
, acc
);
2486 bound
->inner
.max
= innerYfromXY(ellipsex
.max
, bound
->ellipse
.max
, def
, acc
);
2488 outerx
.min
= outerXfromXY(ellipsex
.min
, bound
->ellipse
.min
, def
, acc
);
2489 outerx
.max
= outerXfromXY(ellipsex
.max
, bound
->ellipse
.max
, def
, acc
);
2490 innerx
.min
= innerXfromXY(ellipsex
.min
, bound
->ellipse
.min
, def
, acc
);
2491 innerx
.max
= innerXfromXY(ellipsex
.max
, bound
->ellipse
.max
, def
, acc
);
2494 * save the line end points for the
2495 * cap code to use. Careful here, these are
2496 * in cartesean coordinates (y increasing upwards)
2497 * while the cap code uses inverted coordinates
2498 * (y increasing downwards)
2502 right
->counterClock
.y
= bound
->outer
.min
;
2503 right
->counterClock
.x
= outerx
.min
;
2504 right
->center
.y
= bound
->ellipse
.min
;
2505 right
->center
.x
= ellipsex
.min
;
2506 right
->clock
.y
= bound
->inner
.min
;
2507 right
->clock
.x
= innerx
.min
;
2511 left
->clock
.y
= bound
->outer
.max
;
2512 left
->clock
.x
= outerx
.max
;
2513 left
->center
.y
= bound
->ellipse
.max
;
2514 left
->center
.x
= ellipsex
.max
;
2515 left
->counterClock
.y
= bound
->inner
.max
;
2516 left
->counterClock
.x
= innerx
.max
;
2519 bound
->left
.min
= bound
->inner
.max
;
2520 bound
->left
.max
= bound
->outer
.max
;
2521 bound
->right
.min
= bound
->inner
.min
;
2522 bound
->right
.max
= bound
->outer
.min
;
2524 computeLine(innerx
.min
, bound
->inner
.min
, outerx
.min
, bound
->outer
.min
,
2526 computeLine(innerx
.max
, bound
->inner
.max
, outerx
.max
, bound
->outer
.max
,
2529 if (bound
->inner
.min
> bound
->inner
.max
) {
2530 t
= bound
->inner
.min
;
2531 bound
->inner
.min
= bound
->inner
.max
;
2532 bound
->inner
.max
= t
;
2534 tail_y
= acc
->tail_y
;
2535 if (tail_y
> bound
->ellipse
.max
)
2536 tail_y
= bound
->ellipse
.max
;
2537 else if (tail_y
< bound
->ellipse
.min
)
2538 tail_y
= bound
->ellipse
.min
;
2539 innerTaily
= innerYfromY(tail_y
, def
, acc
);
2540 if (bound
->inner
.min
> innerTaily
)
2541 bound
->inner
.min
= innerTaily
;
2542 if (bound
->inner
.max
< innerTaily
)
2543 bound
->inner
.max
= innerTaily
;
2544 bound
->inneri
.min
= ICEIL(bound
->inner
.min
- acc
->fromIntY
);
2545 bound
->inneri
.max
= floor(bound
->inner
.max
- acc
->fromIntY
);
2546 bound
->outeri
.min
= ICEIL(bound
->outer
.min
- acc
->fromIntY
);
2547 bound
->outeri
.max
= floor(bound
->outer
.max
- acc
->fromIntY
);
2551 * this section computes the x value of the span at y
2552 * intersected with the specified face of the ellipse.
2554 * this is the min/max X value over the set of normal
2555 * lines to the entire ellipse, the equation of the
2559 * x = ------------ y + ellipse_x (1 - --- )
2562 * compute the derivative with-respect-to ellipse_y and solve
2565 * (w^2 - h^2) ellipse_y^3 + h^4 y
2566 * 0 = - ----------------------------------
2567 * h w ellipse_y^2 sqrt (h^2 - ellipse_y^2)
2570 * ellipse_y = ( ---------- ) ^ (1/3)
2573 * The other two solutions to the equation are imaginary.
2575 * This gives the position on the ellipse which generates
2576 * the normal with the largest/smallest x intersection point.
2578 * Now compute the second derivative to check whether
2579 * the intersection is a minimum or maximum:
2581 * h (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2582 * - -------------------------------------------
2583 * w y0^3 (sqrt (h^2 - y^2)) ^ 3
2585 * as we only care about the sign,
2587 * - (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2589 * or (to use accelerators),
2591 * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2)
2596 * computes the position on the ellipse whose normal line
2597 * intersects the given scan line maximally
2601 hookEllipseY(double scan_y
,
2602 struct arc_bound
*bound
, struct accelerators
*acc
, int left
)
2606 if (acc
->h2mw2
== 0) {
2607 if ((scan_y
> 0 && !left
) || (scan_y
< 0 && left
))
2608 return bound
->ellipse
.min
;
2609 return bound
->ellipse
.max
;
2611 ret
= (acc
->h4
* scan_y
) / (acc
->h2mw2
);
2619 * computes the X value of the intersection of the
2620 * given scan line with the right side of the lower hook
2624 hookX(double scan_y
,
2625 struct arc_def
*def
,
2626 struct arc_bound
*bound
, struct accelerators
*acc
, int left
)
2628 double ellipse_y
, x
;
2631 if (def
->w
!= def
->h
) {
2632 ellipse_y
= hookEllipseY(scan_y
, bound
, acc
, left
);
2633 if (boundedLe(ellipse_y
, bound
->ellipse
)) {
2635 * compute the value of the second
2638 maxMin
= ellipse_y
* ellipse_y
* ellipse_y
* acc
->h2mw2
-
2639 acc
->h2
* scan_y
* (3 * ellipse_y
* ellipse_y
- 2 * acc
->h2
);
2640 if ((left
&& maxMin
> 0) || (!left
&& maxMin
< 0)) {
2642 return def
->w
+ left
? -def
->l
: def
->l
;
2643 x
= (acc
->h2
* scan_y
- ellipse_y
* acc
->h2mw2
) *
2644 sqrt(acc
->h2
- ellipse_y
* ellipse_y
) /
2645 (def
->h
* def
->w
* ellipse_y
);
2651 if (acc
->left
.valid
&& boundedLe(scan_y
, bound
->left
)) {
2652 x
= intersectLine(scan_y
, acc
->left
);
2655 if (acc
->right
.valid
)
2656 x
= intersectLine(scan_y
, acc
->right
);
2658 x
= def
->w
- def
->l
;
2662 if (acc
->right
.valid
&& boundedLe(scan_y
, bound
->right
)) {
2663 x
= intersectLine(scan_y
, acc
->right
);
2666 if (acc
->left
.valid
)
2667 x
= intersectLine(scan_y
, acc
->left
);
2669 x
= def
->w
- def
->l
;
2676 * generate the set of spans with
2677 * the given y coordinate
2686 struct arc_def
*def
,
2687 struct arc_bound
*bounds
, struct accelerators
*acc
, int mask
)
2689 int linx
, loutx
, rinx
, routx
;
2692 if (boundedLe(y
, bounds
->inneri
)) {
2698 * intersection with left face
2700 x
= hookX(y
+ acc
->fromIntY
, def
, bounds
, acc
, 1);
2701 if (acc
->right
.valid
&& boundedLe(y
+ acc
->fromIntY
, bounds
->right
)) {
2702 altx
= intersectLine(y
+ acc
->fromIntY
, acc
->right
);
2706 linx
= -ICEIL(acc
->fromIntX
- x
);
2707 rinx
= ICEIL(acc
->fromIntX
+ x
);
2709 if (boundedLe(y
, bounds
->outeri
)) {
2715 * intersection with right face
2717 x
= hookX(y
+ acc
->fromIntY
, def
, bounds
, acc
, 0);
2718 if (acc
->left
.valid
&& boundedLe(y
+ acc
->fromIntY
, bounds
->left
)) {
2720 x
= intersectLine(y
+ acc
->fromIntY
, acc
->left
);
2724 loutx
= -ICEIL(acc
->fromIntX
- x
);
2725 routx
= ICEIL(acc
->fromIntX
+ x
);
2729 newFinalSpan(acc
->yorgu
- y
, acc
->xorg
+ rinx
, acc
->xorg
+ routx
);
2731 newFinalSpan(acc
->yorgl
+ y
, acc
->xorg
+ rinx
, acc
->xorg
+ routx
);
2735 newFinalSpan(acc
->yorgu
- y
, acc
->xorg
- loutx
, acc
->xorg
- linx
);
2737 newFinalSpan(acc
->yorgl
+ y
, acc
->xorg
- loutx
, acc
->xorg
- linx
);
2746 struct arc_def
*def
,
2747 struct arc_bound
*bounds
, struct accelerators
*acc
, int mask
)
2751 if (boundedLe(0, bounds
->inneri
) &&
2752 acc
->left
.valid
&& boundedLe(0, bounds
->left
) && acc
->left
.b
> 0) {
2753 x
= def
->w
- def
->l
;
2754 if (acc
->left
.b
< x
)
2756 lw
= ICEIL(acc
->fromIntX
- x
) - lx
;
2758 rx
= ICEIL(acc
->fromIntX
+ x
);
2761 arcSpan(0, lx
, lw
, rx
, rw
, def
, bounds
, acc
, mask
);
2768 struct arc_def
*def
,
2769 struct arc_bound
*bounds
, struct accelerators
*acc
, int mask
)
2771 double yy
, xalt
, x
, lx
, rx
;
2774 if (boundedLe(y
, bounds
->outeri
))
2775 arcSpan(y
, 0, lw
, -rw
, rw
, def
, bounds
, acc
, mask
);
2776 else if (def
->w
!= def
->h
) {
2777 yy
= y
+ acc
->fromIntY
;
2778 x
= tailX(yy
, def
, bounds
, acc
);
2779 if (yy
== 0.0 && x
== -rw
- acc
->fromIntX
)
2781 if (acc
->right
.valid
&& boundedLe(yy
, bounds
->right
)) {
2784 xalt
= intersectLine(yy
, acc
->right
);
2785 if (xalt
>= -rw
- acc
->fromIntX
&& xalt
<= rx
)
2787 n
= ICEIL(acc
->fromIntX
+ lx
);
2790 newFinalSpan(acc
->yorgu
- y
, acc
->xorg
+ n
, acc
->xorg
+ lw
);
2792 newFinalSpan(acc
->yorgl
+ y
, acc
->xorg
+ n
, acc
->xorg
+ lw
);
2794 n
= ICEIL(acc
->fromIntX
+ rx
);
2797 newFinalSpan(acc
->yorgu
- y
, acc
->xorg
- rw
, acc
->xorg
+ n
);
2799 newFinalSpan(acc
->yorgl
+ y
, acc
->xorg
- rw
, acc
->xorg
+ n
);
2803 ICEIL(acc
->fromIntX
- x
), 0,
2804 ICEIL(acc
->fromIntX
+ x
), 0, def
, bounds
, acc
, mask
);
2809 * create whole arcs out of pieces. This code is
2813 static struct finalSpan
**finalSpans
= NULL
;
2814 static int finalMiny
= 0, finalMaxy
= -1;
2815 static int finalSize
= 0;
2817 static int nspans
= 0; /* total spans, not just y coords */
2820 struct finalSpan
*next
;
2821 int min
, max
; /* x values */
2824 static struct finalSpan
*freeFinalSpans
, *tmpFinalSpan
;
2826 #define allocFinalSpan() (freeFinalSpans ?\
2827 ((tmpFinalSpan = freeFinalSpans), \
2828 (freeFinalSpans = freeFinalSpans->next), \
2829 (tmpFinalSpan->next = 0), \
2833 #define SPAN_CHUNK_SIZE 128
2835 struct finalSpanChunk
{
2836 struct finalSpan data
[SPAN_CHUNK_SIZE
];
2837 struct finalSpanChunk
*next
;
2840 static struct finalSpanChunk
*chunks
;
2842 static struct finalSpan
*
2845 struct finalSpanChunk
*newChunk
;
2846 struct finalSpan
*span
;
2849 newChunk
= malloc(sizeof(struct finalSpanChunk
));
2851 return (struct finalSpan
*) NULL
;
2852 newChunk
->next
= chunks
;
2854 freeFinalSpans
= span
= newChunk
->data
+ 1;
2855 for (i
= 1; i
< SPAN_CHUNK_SIZE
- 1; i
++) {
2856 span
->next
= span
+ 1;
2860 span
= newChunk
->data
;
2866 disposeFinalSpans(void)
2868 struct finalSpanChunk
*chunk
, *next
;
2870 for (chunk
= chunks
; chunk
; chunk
= next
) {
2881 fillSpans(DrawablePtr pDrawable
, GCPtr pGC
)
2883 struct finalSpan
*span
;
2887 struct finalSpan
**f
;
2894 xSpan
= xSpans
= malloc(nspans
* sizeof(DDXPointRec
));
2895 xWidth
= xWidths
= malloc(nspans
* sizeof(int));
2896 if (xSpans
&& xWidths
) {
2899 for (spany
= finalMiny
; spany
<= finalMaxy
; spany
++, f
++) {
2900 for (span
= *f
; span
; span
= span
->next
) {
2901 if (span
->max
<= span
->min
)
2903 xSpan
->x
= span
->min
;
2906 *xWidth
++ = span
->max
- span
->min
;
2910 (*pGC
->ops
->FillSpans
) (pDrawable
, pGC
, i
, xSpans
, xWidths
, TRUE
);
2912 disposeFinalSpans();
2921 #define SPAN_REALLOC 100
2923 #define findSpan(y) ((finalMiny <= (y) && (y) <= finalMaxy) ? \
2924 &finalSpans[(y) - finalMiny] : \
2927 static struct finalSpan
**
2930 struct finalSpan
**newSpans
;
2931 int newSize
, newMiny
, newMaxy
;
2935 if (y
< finalMiny
|| y
> finalMaxy
) {
2941 change
= finalMiny
- y
;
2943 change
= y
- finalMaxy
;
2944 if (change
>= SPAN_REALLOC
)
2945 change
+= SPAN_REALLOC
;
2947 change
= SPAN_REALLOC
;
2948 newSize
= finalSize
+ change
;
2949 newSpans
= malloc(newSize
* sizeof(struct finalSpan
*));
2952 newMiny
= finalMiny
;
2953 newMaxy
= finalMaxy
;
2955 newMiny
= finalMiny
- change
;
2957 newMaxy
= finalMaxy
+ change
;
2959 memmove(((char *) newSpans
) +
2960 (finalMiny
- newMiny
) * sizeof(struct finalSpan
*),
2961 (char *) finalSpans
,
2962 finalSize
* sizeof(struct finalSpan
*));
2965 if ((i
= finalMiny
- newMiny
) > 0)
2966 memset((char *) newSpans
, 0, i
* sizeof(struct finalSpan
*));
2967 if ((i
= newMaxy
- finalMaxy
) > 0)
2968 memset((char *) (newSpans
+ newSize
- i
), 0,
2969 i
* sizeof(struct finalSpan
*));
2970 finalSpans
= newSpans
;
2971 finalMaxy
= newMaxy
;
2972 finalMiny
= newMiny
;
2973 finalSize
= newSize
;
2975 return &finalSpans
[y
- finalMiny
];
2979 newFinalSpan(int y
, int xmin
, int xmax
)
2981 struct finalSpan
*x
;
2982 struct finalSpan
**f
;
2983 struct finalSpan
*oldx
;
2984 struct finalSpan
*prev
;
2992 for (x
= *f
; x
; x
= x
->next
) {
2997 if (x
->min
<= xmax
&& xmin
<= x
->max
) {
2999 oldx
->min
= min(x
->min
, xmin
);
3000 oldx
->max
= max(x
->max
, xmax
);
3002 prev
->next
= x
->next
;
3008 x
->min
= min(x
->min
, xmin
);
3009 x
->max
= max(x
->max
, xmax
);
3022 x
= allocFinalSpan();
3034 mirrorSppPoint(int quadrant
, SppPointPtr sppPoint
)
3040 sppPoint
->x
= -sppPoint
->x
;
3043 sppPoint
->x
= -sppPoint
->x
;
3044 sppPoint
->y
= -sppPoint
->y
;
3047 sppPoint
->y
= -sppPoint
->y
;
3051 * and translate to X coordinate system
3053 sppPoint
->y
= -sppPoint
->y
;
3057 * split an arc into pieces which are scan-converted
3058 * in the first-quadrant and mirrored into position.
3059 * This is necessary as the scan-conversion code can
3060 * only deal with arcs completely contained in the
3065 drawArc(xArc
* tarc
,
3066 int l
, int a0
, int a1
, miArcFacePtr right
, miArcFacePtr left
)
3067 { /* save end line points */
3069 struct accelerators acc
;
3070 int startq
, endq
, curq
;
3071 int rightq
, leftq
= 0, righta
= 0, lefta
= 0;
3072 miArcFacePtr passRight
, passLeft
;
3073 int q0
= 0, q1
= 0, mask
;
3077 } band
[5], sweep
[20];
3078 int bandno
, sweepno
;
3080 int flipRight
= 0, flipLeft
= 0;
3082 miArcSpanData
*spdata
;
3084 spdata
= miComputeWideEllipse(l
, tarc
);
3090 startq
= a0
/ (90 * 64);
3094 endq
= (a1
- 1) / (90 * 64);
3106 q1
= min(a1
, 90 * 64);
3109 if (curq
== startq
&& a0
== q0
&& rightq
< 0) {
3113 if (curq
== endq
&& a1
== q1
) {
3122 q0
= 180 * 64 - min(a1
, 180 * 64);
3126 q1
= 180 * 64 - max(a0
, 90 * 64);
3127 if (curq
== startq
&& 180 * 64 - a0
== q1
) {
3131 if (curq
== endq
&& 180 * 64 - a1
== q0
) {
3140 q0
= max(a0
, 180 * 64) - 180 * 64;
3144 q1
= min(a1
, 270 * 64) - 180 * 64;
3145 if (curq
== startq
&& a0
- 180 * 64 == q0
) {
3149 if (curq
== endq
&& a1
- 180 * 64 == q1
) {
3158 q0
= 360 * 64 - min(a1
, 360 * 64);
3159 q1
= 360 * 64 - max(a0
, 270 * 64);
3160 if (curq
== startq
&& 360 * 64 - a0
== q1
) {
3164 if (curq
== endq
&& 360 * 64 - a1
== q0
) {
3170 band
[bandno
].a0
= q0
;
3171 band
[bandno
].a1
= q1
;
3172 band
[bandno
].mask
= 1 << curq
;
3189 * find left-most point
3191 for (i
= 0; i
< bandno
; i
++)
3192 if (band
[i
].a0
<= q0
) {
3195 mask
= band
[i
].mask
;
3200 * locate next point of change
3202 for (i
= 0; i
< bandno
; i
++)
3203 if (!(mask
& band
[i
].mask
)) {
3204 if (band
[i
].a0
== q0
) {
3205 if (band
[i
].a1
< q1
)
3207 mask
|= band
[i
].mask
;
3209 else if (band
[i
].a0
< q1
)
3213 * create a new sweep
3215 sweep
[sweepno
].a0
= q0
;
3216 sweep
[sweepno
].a1
= q1
;
3217 sweep
[sweepno
].mask
= mask
;
3220 * subtract the sweep from the affected bands
3222 for (i
= 0; i
< bandno
; i
++)
3223 if (band
[i
].a0
== q0
) {
3226 * check if this band is empty
3228 if (band
[i
].a0
== band
[i
].a1
)
3229 band
[i
].a1
= band
[i
].a0
= 90 * 64 + 1;
3232 computeAcc(tarc
, l
, &def
, &acc
);
3233 for (j
= 0; j
< sweepno
; j
++) {
3234 mask
= sweep
[j
].mask
;
3235 passRight
= passLeft
= 0;
3236 if (mask
& (1 << rightq
)) {
3237 if (sweep
[j
].a0
== righta
)
3239 else if (sweep
[j
].a1
== righta
) {
3244 if (mask
& (1 << leftq
)) {
3245 if (sweep
[j
].a1
== lefta
) {
3250 else if (sweep
[j
].a0
== lefta
) {
3257 drawQuadrant(&def
, &acc
, sweep
[j
].a0
, sweep
[j
].a1
, mask
,
3258 passRight
, passLeft
, spdata
);
3261 * when copyEnd is set, both ends of the arc were computed
3262 * at the same time; drawQuadrant only takes one end though,
3263 * so the left end will be the only one holding the data. Copy
3269 * mirror the coordinates generated for the
3273 mirrorSppPoint(rightq
, &right
->clock
);
3274 mirrorSppPoint(rightq
, &right
->center
);
3275 mirrorSppPoint(rightq
, &right
->counterClock
);
3279 temp
= right
->clock
;
3280 right
->clock
= right
->counterClock
;
3281 right
->counterClock
= temp
;
3285 mirrorSppPoint(leftq
, &left
->counterClock
);
3286 mirrorSppPoint(leftq
, &left
->center
);
3287 mirrorSppPoint(leftq
, &left
->clock
);
3292 left
->clock
= left
->counterClock
;
3293 left
->counterClock
= temp
;
3300 drawQuadrant(struct arc_def
*def
,
3301 struct accelerators
*acc
,
3305 miArcFacePtr right
, miArcFacePtr left
, miArcSpanData
* spdata
)
3307 struct arc_bound bound
;
3313 def
->a0
= ((double) a0
) / 64.0;
3314 def
->a1
= ((double) a1
) / 64.0;
3315 computeBound(def
, &bound
, acc
, right
, left
);
3316 yy
= bound
.inner
.min
;
3317 if (bound
.outer
.min
< yy
)
3318 yy
= bound
.outer
.min
;
3319 miny
= ICEIL(yy
- acc
->fromIntY
);
3320 yy
= bound
.inner
.max
;
3321 if (bound
.outer
.max
> yy
)
3322 yy
= bound
.outer
.max
;
3323 maxy
= floor(yy
- acc
->fromIntY
);
3325 span
= spdata
->spans
;
3327 if (a1
== 90 * 64 && (mask
& 1))
3328 newFinalSpan(acc
->yorgu
- y
- 1, acc
->xorg
, acc
->xorg
+ 1);
3331 for (n
= spdata
->count1
; --n
>= 0;) {
3336 span
->lx
, -span
->lx
, 0, span
->lx
+ span
->lw
,
3337 def
, &bound
, acc
, mask
);
3338 if (span
->rw
+ span
->rx
)
3339 tailSpan(y
, -span
->rw
, -span
->rx
, def
, &bound
, acc
, mask
);
3348 arcSpan(y
, 0, 0, 0, 1, def
, &bound
, acc
, mask
& 0xc);
3350 for (n
= spdata
->count2
; --n
>= 0;) {
3354 arcSpan(y
, span
->lx
, span
->lw
, span
->rx
, span
->rw
,
3355 def
, &bound
, acc
, mask
);
3359 if (spdata
->bot
&& miny
<= y
&& y
<= maxy
) {
3363 if (span
->rw
<= 0) {
3364 arcSpan0(span
->lx
, -span
->lx
, 0, span
->lx
+ span
->lw
,
3365 def
, &bound
, acc
, n
);
3366 if (span
->rw
+ span
->rx
)
3367 tailSpan(y
, -span
->rw
, -span
->rx
, def
, &bound
, acc
, n
);
3370 arcSpan0(span
->lx
, span
->lw
, span
->rx
, span
->rw
,
3371 def
, &bound
, acc
, n
);
3375 yy
= y
+ acc
->fromIntY
;
3376 if (def
->w
== def
->h
) {
3377 xalt
= def
->w
- def
->l
;
3378 x
= -sqrt(xalt
* xalt
- yy
* yy
);
3381 x
= tailX(yy
, def
, &bound
, acc
);
3382 if (acc
->left
.valid
&& boundedLe(yy
, bound
.left
)) {
3383 xalt
= intersectLine(yy
, acc
->left
);
3387 if (acc
->right
.valid
&& boundedLe(yy
, bound
.right
)) {
3388 xalt
= intersectLine(yy
, acc
->right
);
3394 ICEIL(acc
->fromIntX
- x
), 0,
3395 ICEIL(acc
->fromIntX
+ x
), 0, def
, &bound
, acc
, mask
);