1
/* $XdotOrg: xserver/xorg/mi/miarc.c,v 1.6 2005/07/03 08:53:51 daniels Exp $ */
2
/* $XFree86: xc/programs/Xserver/mi/miarc.c,v 3.14 2003/10/29 22:57:48 tsi Exp $ */
3
/***********************************************************
5
Copyright 1987, 1998 The Open Group
7
Permission to use, copy, modify, distribute, and sell this software and its
8
documentation for any purpose is hereby granted without fee, provided that
9
the above copyright notice appear in all copies and that both that
10
copyright notice and this permission notice appear in supporting
13
The above copyright notice and this permission notice shall be included in
14
all copies or substantial portions of the Software.
16
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19
OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
20
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23
Except as contained in this notice, the name of The Open Group shall not be
24
used in advertising or otherwise to promote the sale, use or other dealings
25
in this Software without prior written authorization from The Open Group.
28
Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
32
Permission to use, copy, modify, and distribute this software and its
33
documentation for any purpose and without fee is hereby granted,
34
provided that the above copyright notice appear in all copies and that
35
both that copyright notice and this permission notice appear in
36
supporting documentation, and that the name of Digital not be
37
used in advertising or publicity pertaining to distribution of the
38
software without specific, written prior permission.
40
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
41
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
42
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
43
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
44
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
45
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
48
******************************************************************/
49
/* $Xorg: miarc.c,v 1.4 2001/02/09 02:05:20 xorgcvs Exp $ */
50
/* Author: Keith Packard and Bob Scheifler */
51
/* Warning: this code is toxic, do not dally very long here. */
53
#ifdef HAVE_DIX_CONFIG_H
54
#include <dix-config.h>
57
#if defined(_XOPEN_SOURCE) || defined(__QNXNTO__) \
58
|| (defined(sun) && defined(__SVR4))
61
#define _XOPEN_SOURCE /* to get prototype for hypot on some systems */
66
#include <X11/Xprotostr.h>
69
#include "scrnintstr.h"
70
#include "pixmapstr.h"
71
#include "windowstr.h"
74
#include "mifillarc.h"
75
#include <X11/Xfuncproto.h>
77
static double miDsin(double a);
78
static double miDcos(double a);
79
static double miDasin(double v);
80
static double miDatan2(double dy, double dx);
88
* some interesting sematic interpretation of the protocol:
90
* Self intersecting arcs (i.e. those spanning 360 degrees)
91
* never join with other arcs, and are drawn without caps
92
* (unless on/off dashed, in which case each dash segment
93
* is capped, except when the last segment meets the
94
* first segment, when no caps are drawn)
96
* double dash arcs are drawn in two parts, first the
97
* odd dashes (drawn in background) then the even dashes
98
* (drawn in foreground). This means that overlapping
99
* sections of foreground/background are drawn twice,
100
* first in background then in foreground. The double-draw
101
* occurs even when the function uses the destination values
102
* (e.g. xor mode). This is the same way the wide-line
103
* code works and should be "fixed".
110
#if defined (__GNUC__) && !defined (__STRICT_ANSI__)
115
inline static const int max (const int x, const int y)
120
inline static const int min (const int x, const int y)
149
#define boundedLe(value, bounds)\
150
((bounds).min <= (value) && (value) <= (bounds).max)
157
#define intersectLine(y,line) (line.m * (y) + line.b)
160
* these are all y value bounds
164
struct bound ellipse;
169
struct ibound inneri;
170
struct ibound outeri;
173
struct accelerators {
184
struct line left, right;
195
# define todeg(xAngle) (((double) (xAngle)) / 64.0)
200
typedef struct _miArcJoin {
201
int arcIndex0, arcIndex1;
204
} miArcJoinRec, *miArcJoinPtr;
206
typedef struct _miArcCap {
209
} miArcCapRec, *miArcCapPtr;
211
typedef struct _miArcFace {
214
SppPointRec counterClock;
215
} miArcFaceRec, *miArcFacePtr;
217
typedef struct _miArcData {
219
int render; /* non-zero means render after drawing */
220
int join; /* related join */
221
int cap; /* related cap */
222
int selfJoin; /* final dash meets first dash */
223
miArcFaceRec bounds[2];
224
double x0, y0, x1, y1;
225
} miArcDataRec, *miArcDataPtr;
228
* This is an entire sequence of arcs, computed and categorized according
229
* to operation. miDashArcs generates either one or two of these.
232
typedef struct _miPolyArc {
239
} miPolyArcRec, *miPolyArcPtr;
241
#define GCValsFunction 0
242
#define GCValsForeground 1
243
#define GCValsBackground 2
244
#define GCValsLineWidth 3
245
#define GCValsCapStyle 4
246
#define GCValsJoinStyle 5
247
#define GCValsMask (GCFunction | GCForeground | GCBackground | \
248
GCLineWidth | GCCapStyle | GCJoinStyle)
249
static CARD32 gcvals[6];
251
static void fillSpans(DrawablePtr pDrawable, GCPtr pGC);
252
static void newFinalSpan(int y, register int xmin, register int xmax);
253
static void drawArc(xArc *tarc, int l, int a0, int a1, miArcFacePtr right,
255
static void drawZeroArc(DrawablePtr pDraw, GCPtr pGC, xArc *tarc, int lw,
256
miArcFacePtr left, miArcFacePtr right);
257
static void miArcJoin(DrawablePtr pDraw, GCPtr pGC, miArcFacePtr pLeft,
258
miArcFacePtr pRight, int xOrgLeft, int yOrgLeft,
259
double xFtransLeft, double yFtransLeft,
260
int xOrgRight, int yOrgRight,
261
double xFtransRight, double yFtransRight);
262
static void miArcCap(DrawablePtr pDraw, GCPtr pGC, miArcFacePtr pFace,
263
int end, int xOrg, int yOrg, double xFtrans,
265
static void miRoundCap(DrawablePtr pDraw, GCPtr pGC, SppPointRec pCenter,
266
SppPointRec pEnd, SppPointRec pCorner,
267
SppPointRec pOtherCorner, int fLineEnd,
268
int xOrg, int yOrg, double xFtrans, double yFtrans);
269
static void miFreeArcs(miPolyArcPtr arcs, GCPtr pGC);
270
static miPolyArcPtr miComputeArcs(xArc *parcs, int narcs, GCPtr pGC);
271
static int miGetArcPts(SppArcPtr parc, int cpt, SppPointPtr *ppPts);
273
# define CUBED_ROOT_2 1.2599210498948732038115849718451499938964
274
# define CUBED_ROOT_4 1.5874010519681993173435330390930175781250
277
* draw one segment of the arc using the arc spans generation routines
288
int l = pGC->lineWidth;
289
int a0, a1, startAngle, endAngle;
295
if (tarc.width == 0 || tarc.height == 0) {
296
drawZeroArc (pDraw, pGC, &tarc, l, left, right);
300
if (pGC->miTranslate) {
309
else if (a1 < -FULLCIRCLE)
312
startAngle = a0 + a1;
322
* bounds check the two angles
325
startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
326
if (startAngle >= FULLCIRCLE)
327
startAngle = startAngle % FULLCIRCLE;
329
endAngle = FULLCIRCLE - (-endAngle) % FULLCIRCLE;
330
if (endAngle > FULLCIRCLE)
331
endAngle = (endAngle-1) % FULLCIRCLE + 1;
332
if ((startAngle == endAngle) && a1) {
334
endAngle = FULLCIRCLE;
337
drawArc (&tarc, l, startAngle, endAngle, right, left);
342
Three equations combine to describe the boundaries of the arc
344
x^2/w^2 + y^2/h^2 = 1 ellipse itself
345
(X-x)^2 + (Y-y)^2 = r^2 circle at (x, y) on the ellipse
346
(Y-y) = (X-x)*w^2*y/(h^2*x) normal at (x, y) on the ellipse
348
These lead to a quartic relating Y and y
350
y^4 - (2Y)y^3 + (Y^2 + (h^4 - w^2*r^2)/(w^2 - h^2))y^2
351
- (2Y*h^4/(w^2 - h^2))y + (Y^2*h^4)/(w^2 - h^2) = 0
353
The reducible cubic obtained from this quartic is
355
z^3 - (3N)z^2 - 2V = 0
359
N = (Y^2 + (h^4 - w^2*r^2/(w^2 - h^2)))/6
360
V = w^2*r^2*Y^2*h^4/(4 *(w^2 - h^2)^2)
372
The discriminant of this cubic is
376
When D > 0, a real root is obtained as
378
z = N + cbrt(-q+sqrt(D)) + cbrt(-q-sqrt(D))
380
When D < 0, a real root is obtained as
382
z = N - 2m*cos(acos(-q/m^3)/3)
386
m = sqrt(|p|) * sign(q)
388
Given a real root Z of the cubic, the roots of the quartic are the roots
389
of the two quadratics
391
y^2 + ((b+A)/2)y + (Z + (bZ - d)/A) = 0
395
A = +/- sqrt(8Z + b^2 - 4c)
396
b, c, d are the cubic, quadratic, and linear coefficients of the quartic
398
Some experimentation is then required to determine which solutions
399
correspond to the inner and outer boundaries.
404
short lx, lw, rx, rw;
409
int count1, count2, k;
414
unsigned long lrustamp;
416
unsigned short width, height;
417
miArcSpanData *spdata;
422
static void drawQuadrant(struct arc_def *def, struct accelerators *acc,
423
int a0, int a1, int mask, miArcFacePtr right,
424
miArcFacePtr left, miArcSpanData *spdata);
426
static arcCacheRec arcCache[CACHESIZE];
427
static unsigned long lrustamp;
428
static arcCacheRec *lastCacheHit = &arcCache[0];
429
static RESTYPE cacheType;
432
* External so it can be called when low on memory.
433
* Call with a zero ID in that case.
437
miFreeArcCache (data, id)
447
for (k = CACHESIZE, cent = &arcCache[0]; --k >= 0; cent++)
462
miComputeCircleSpans(
465
miArcSpanData *spdata)
467
register miArcSpan *span;
469
register int x, y, e;
470
int xk, yk, xm, ym, dx, dy;
471
register int slw, inslw;
472
int inx = 0, iny, ine = 0;
473
int inxk = 0, inyk = 0, inxm = 0, inym = 0;
476
slw = parc->width - doinner;
477
y = parc->height >> 1;
478
dy = parc->height & 1;
480
MIWIDEARCSETUP(x, y, dy, slw, e, xk, xm, yk, ym);
481
inslw = parc->width + doinner;
484
spdata->hole = spdata->top;
485
MIWIDEARCSETUP(inx, iny, dy, inslw, ine, inxk, inxm, inyk, inym);
489
spdata->hole = FALSE;
492
spdata->count1 = -doinner - spdata->top;
493
spdata->count2 = y + doinner;
494
span = spdata->spans;
503
span->rw = span->lx + slw;
507
MIFILLINARCSTEP(inslw);
509
span->rx = dy - inx + inslw;
510
span->rw = inx - x + slw - inslw;
520
if (lw > (int)parc->height)
521
span[-1].rx = span[-1].rw = -((lw - (int)parc->height) >> 1);
530
miComputeEllipseSpans(
533
miArcSpanData *spdata)
535
register miArcSpan *span;
536
double w, h, r, xorg;
537
double Hs, Hf, WH, K, Vk, Nk, Fk, Vr, N, Nc, Z, rs;
538
double A, T, b, d, x, y, t, inx, outx = 0.0, hepp, hepm;
541
w = (double)parc->width / 2.0;
542
h = (double)parc->height / 2.0;
548
Vk = (Nk * Hs) / (WH + WH);
550
Nk = (Hf - Nk * Nk) / WH;
554
K = h + ((lw - 1) >> 1);
555
span = spdata->spans;
568
spdata->hole = (spdata->top &&
569
(int)parc->height * lw <= (int)(parc->width * parc->width) &&
570
lw < (int)parc->height);
571
for (; K > 0.0; K -= 1.0)
573
N = (K * K + Nk) / 6.0;
581
if ( (b < 0.0) == (t < 0.0) )
586
Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);
587
if ( (Z < 0.0) == (Vr < 0.0) )
595
Z = N + cbrt(t + d) + cbrt(t - d);
598
A = sqrt((Z + Z) - Nk);
599
T = (Fk - Z) * K / A;
603
d = b * b - 4 * (Z + T);
608
if ((y >= 0.0) && (y < hepp))
614
x = w * sqrt(1 - (t * t));
616
if (rs - (t * t) >= 0)
617
t = sqrt(rs - (t * t));
627
d = b * b - 4 * (Z - T);
628
/* Because of the large magnitudes involved, we lose enough precision
629
* that sometimes we end up with a negative value near the axis, when
630
* it should be positive. This is a workaround.
632
if (d < 0 && !solution)
642
x = w * sqrt(1 - (t * t));
644
if (rs - (t * t) >= 0)
645
inx = x - sqrt(rs - (t * t));
655
x = w * sqrt(1 - (t * t));
657
if (rs - (t * t) >= 0)
658
t = sqrt(rs - (t * t));
667
span->lx = ICEIL(xorg - outx);
671
span->lw = ICEIL(xorg + outx) - span->lx;
672
span->rx = ICEIL(xorg + inx);
673
span->rw = -ICEIL(xorg - inx);
678
span->lw = ICEIL(xorg - inx) - span->lx;
679
span->rx = ICEIL(xorg + inx);
680
span->rw = ICEIL(xorg + outx) - span->rx;
687
if (r >= h && r <= w)
689
else if (Nk < 0.0 && -Nk < Hs)
691
inx = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);
697
span->lx = ICEIL(xorg - outx);
700
span->lw = ICEIL(xorg + outx) - span->lx;
701
span->rx = ICEIL(xorg + inx);
702
span->rw = -ICEIL(xorg - inx);
706
span->lw = ICEIL(xorg - inx) - span->lx;
707
span->rx = ICEIL(xorg + inx);
708
span->rw = ICEIL(xorg + outx) - span->rx;
713
span = &spdata->spans[spdata->count1];
714
span->lw = -span->lx;
726
struct arc_bound *bounds,
727
struct accelerators *acc)
730
double Hs, Hf, WH, Vk, Nk, Fk, Vr, N, Nc, Z, rs;
731
double A, T, b, d, x, y, t, hepp, hepm;
743
Vk = (Nk * Hs) / (WH + WH);
745
Nk = (Hf - Nk * Nk) / WH;
747
if (Nk < 0.0 && -Nk < Hs) {
748
xs[0] = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);
750
if (acc->left.valid && boundedLe(K, bounds->left) &&
751
!boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)
753
if (acc->right.valid && boundedLe(K, bounds->right) &&
754
!boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)
763
N = (K * K + Nk) / 6.0;
773
if ( (b < 0.0) == (t < 0.0) )
778
Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);
779
if ( (Z < 0.0) == (Vr < 0.0) )
787
Z = N + cbrt(t + d) + cbrt(t - d);
790
A = sqrt((Z + Z) - Nk);
791
T = (Fk - Z) * K / A;
794
d = b * b - 4 * (Z + T);
795
if (d >= 0 && flip == 2)
799
if ((y >= 0.0) && (y < hepp))
805
x = w * sqrt(1 - (t * t));
807
if (rs - (t * t) >= 0)
808
t = sqrt(rs - (t * t));
815
d = b * b - 4 * (Z - T);
816
/* Because of the large magnitudes involved, we lose enough precision
817
* that sometimes we end up with a negative value near the axis, when
818
* it should be positive. This is a workaround.
820
if (d < 0 && !solution)
830
x = w * sqrt(1 - (t * t));
832
if (rs - (t * t) >= 0)
833
*xp++ = x - sqrt(rs - (t * t));
838
if (y >= 0.0 && flip == 1)
843
x = w * sqrt(1 - (t * t));
845
if (rs - (t * t) >= 0)
846
t = sqrt(rs - (t * t));
853
if (acc->left.valid && boundedLe(K, bounds->left) &&
854
!boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)
856
if (acc->right.valid && boundedLe(K, bounds->right) &&
857
!boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)
863
static miArcSpanData *
864
miComputeWideEllipse(
869
register miArcSpanData *spdata;
870
register arcCacheRec *cent, *lruent;
876
if (parc->height <= 1500)
880
if (cent->lw == lw &&
881
cent->width == parc->width && cent->height == parc->height)
883
cent->lrustamp = ++lrustamp;
886
lruent = &arcCache[0];
887
for (k = CACHESIZE, cent = lruent; --k >= 0; cent++)
889
if (cent->lw == lw &&
890
cent->width == parc->width && cent->height == parc->height)
892
cent->lrustamp = ++lrustamp;
896
if (cent->lrustamp < lruent->lrustamp)
901
cacheType = CreateNewResourceType(miFreeArcCache);
902
(void) AddResource(FakeClientID(0), cacheType, NULL);
906
lruent->spdata = NULL;
909
k = (parc->height >> 1) + ((lw - 1) >> 1);
910
spdata = lruent->spdata;
911
if (!spdata || spdata->k != k)
915
spdata = (miArcSpanData *)xalloc(sizeof(miArcSpanData) +
916
sizeof(miArcSpan) * (k + 2));
917
lruent->spdata = spdata;
920
lruent->lrustamp = 0;
924
spdata->spans = (miArcSpan *)(spdata + 1);
927
spdata->top = !(lw & 1) && !(parc->width & 1);
928
spdata->bot = !(parc->height & 1);
929
lruent->lrustamp = ++lrustamp;
931
lruent->width = parc->width;
932
lruent->height = parc->height;
933
if (lruent != &fakeent)
934
lastCacheHit = lruent;
935
if (parc->width == parc->height)
936
miComputeCircleSpans(lw, parc, spdata);
938
miComputeEllipseSpans(lw, parc, spdata);
949
register DDXPointPtr pts;
952
miArcSpanData *spdata;
954
register miArcSpan *span;
955
register int xorg, yorgu, yorgl;
958
yorgu = parc->height + pGC->lineWidth;
959
n = (sizeof(int) * 2) * yorgu;
960
widths = (int *)ALLOCATE_LOCAL(n + (sizeof(DDXPointRec) * 2) * yorgu);
963
points = (DDXPointPtr)((char *)widths + n);
964
spdata = miComputeWideEllipse((int)pGC->lineWidth, parc, &mustFree);
967
DEALLOCATE_LOCAL(widths);
972
span = spdata->spans;
973
xorg = parc->x + (parc->width >> 1);
974
yorgu = parc->y + (parc->height >> 1);
975
yorgl = yorgu + (parc->height & 1);
976
if (pGC->miTranslate)
992
for (n = spdata->count1; --n >= 0; )
994
pts[0].x = xorg + span->lx;
1014
for (n = spdata->count2; --n >= 0; )
1016
pts[0].x = xorg + span->lx;
1019
pts[1].x = xorg + span->rx;
1020
pts[1].y = pts[0].y;
1022
pts[2].x = pts[0].x;
1025
pts[3].x = pts[1].x;
1026
pts[3].y = pts[2].y;
1038
pts[0].x = xorg + span->lx;
1046
pts[0].x = xorg + span->lx;
1049
pts[1].x = xorg + span->rx;
1050
pts[1].y = pts[0].y;
1058
(*pGC->ops->FillSpans)(pDraw, pGC, pts - points, points, widths, FALSE);
1060
DEALLOCATE_LOCAL(widths);
1064
* miPolyArc strategy:
1066
* If arc is zero width and solid, we don't have to worry about the rasterop
1067
* or join styles. For wide solid circles, we use a fast integer algorithm.
1068
* For wide solid ellipses, we use special case floating point code.
1069
* Otherwise, we set up pDrawTo and pGCTo according to the rasterop, then
1070
* draw using pGCTo and pDrawTo. If the raster-op was "tricky," that is,
1071
* if it involves the destination, then we use PushPixels to move the bits
1072
* from the scratch drawable to pDraw. (See the wide line code for a
1073
* fuller explanation of this.)
1077
miPolyArc(pDraw, pGC, narcs, parcs)
1085
int xMin, xMax, yMin, yMax;
1086
int pixmapWidth = 0, pixmapHeight = 0;
1087
int xOrg = 0, yOrg = 0;
1090
DrawablePtr pDrawTo;
1093
miPolyArcPtr polyArcs;
1094
int cap[2], join[2];
1098
width = pGC->lineWidth;
1099
if(width == 0 && pGC->lineStyle == LineSolid)
1101
for(i = narcs, parc = parcs; --i >= 0; parc++)
1102
miArcSegment( pDraw, pGC, *parc,
1103
(miArcFacePtr) 0, (miArcFacePtr) 0 );
1104
fillSpans (pDraw, pGC);
1108
if ((pGC->lineStyle == LineSolid) && narcs)
1110
while (parcs->width && parcs->height &&
1111
(parcs->angle2 >= FULLCIRCLE ||
1112
parcs->angle2 <= -FULLCIRCLE))
1114
miFillWideEllipse(pDraw, pGC, parcs);
1121
/* Set up pDrawTo and pGCTo based on the rasterop */
1124
case GXclear: /* 0 */
1125
case GXcopy: /* src */
1126
case GXcopyInverted: /* NOT src */
1135
/* find bounding box around arcs */
1136
xMin = yMin = MAXSHORT;
1137
xMax = yMax = MINSHORT;
1139
for(i = narcs, parc = parcs; --i >= 0; parc++)
1141
xMin = min (xMin, parc->x);
1142
yMin = min (yMin, parc->y);
1143
xMax = max (xMax, (parc->x + (int) parc->width));
1144
yMax = max (yMax, (parc->y + (int) parc->height));
1147
/* expand box to deal with line widths */
1148
halfWidth = (width + 1)/2;
1154
/* compute pixmap size; limit it to size of drawable */
1155
xOrg = max(xMin, 0);
1156
yOrg = max(yMin, 0);
1157
pixmapWidth = min(xMax, pDraw->width) - xOrg;
1158
pixmapHeight = min(yMax, pDraw->height) - yOrg;
1160
/* if nothing left, return */
1161
if ( (pixmapWidth <= 0) || (pixmapHeight <= 0) ) return;
1163
for(i = narcs, parc = parcs; --i >= 0; parc++)
1168
if (pGC->miTranslate)
1174
/* set up scratch GC */
1176
pGCTo = GetScratchGC(1, pDraw->pScreen);
1179
gcvals[GCValsFunction] = GXcopy;
1180
gcvals[GCValsForeground] = 1;
1181
gcvals[GCValsBackground] = 0;
1182
gcvals[GCValsLineWidth] = pGC->lineWidth;
1183
gcvals[GCValsCapStyle] = pGC->capStyle;
1184
gcvals[GCValsJoinStyle] = pGC->joinStyle;
1185
dixChangeGC(NullClient, pGCTo, GCValsMask, gcvals, NULL);
1187
/* allocate a 1 bit deep pixmap of the appropriate size, and
1189
pDrawTo = (DrawablePtr)(*pDraw->pScreen->CreatePixmap)
1190
(pDraw->pScreen, pixmapWidth, pixmapHeight, 1);
1193
FreeScratchGC(pGCTo);
1196
ValidateGC(pDrawTo, pGCTo);
1197
miClearDrawable(pDrawTo, pGCTo);
1202
if ((pGC->fillStyle == FillTiled) ||
1203
(pGC->fillStyle == FillOpaqueStippled))
1204
bg = fg; /* the protocol sez these don't cause color changes */
1206
polyArcs = miComputeArcs (parcs, narcs, pGC);
1211
(*pDraw->pScreen->DestroyPixmap) ((PixmapPtr)pDrawTo);
1212
FreeScratchGC (pGCTo);
1217
cap[0] = cap[1] = 0;
1218
join[0] = join[1] = 0;
1219
for (iphase = ((pGC->lineStyle == LineDoubleDash) ? 1 : 0);
1224
dixChangeGC (NullClient, pGC, GCForeground, &bg, NULL);
1225
ValidateGC (pDraw, pGC);
1226
} else if (pGC->lineStyle == LineDoubleDash) {
1227
dixChangeGC (NullClient, pGC, GCForeground, &fg, NULL);
1228
ValidateGC (pDraw, pGC);
1230
for (i = 0; i < polyArcs[iphase].narcs; i++) {
1231
miArcDataPtr arcData;
1233
arcData = &polyArcs[iphase].arcs[i];
1234
miArcSegment(pDrawTo, pGCTo, arcData->arc,
1235
&arcData->bounds[RIGHT_END],
1236
&arcData->bounds[LEFT_END]);
1237
if (polyArcs[iphase].arcs[i].render) {
1238
fillSpans (pDrawTo, pGCTo);
1240
* don't cap self-joining arcs
1242
if (polyArcs[iphase].arcs[i].selfJoin &&
1243
cap[iphase] < polyArcs[iphase].arcs[i].cap)
1245
while (cap[iphase] < polyArcs[iphase].arcs[i].cap) {
1247
miArcDataPtr arcData0;
1249
arcIndex = polyArcs[iphase].caps[cap[iphase]].arcIndex;
1250
end = polyArcs[iphase].caps[cap[iphase]].end;
1251
arcData0 = &polyArcs[iphase].arcs[arcIndex];
1252
miArcCap (pDrawTo, pGCTo,
1253
&arcData0->bounds[end], end,
1254
arcData0->arc.x, arcData0->arc.y,
1255
(double) arcData0->arc.width / 2.0,
1256
(double) arcData0->arc.height / 2.0);
1259
while (join[iphase] < polyArcs[iphase].arcs[i].join) {
1260
int arcIndex0, arcIndex1, end0, end1;
1262
miArcDataPtr arcData0, arcData1;
1265
joinp = &polyArcs[iphase].joins[join[iphase]];
1266
arcIndex0 = joinp->arcIndex0;
1268
arcIndex1 = joinp->arcIndex1;
1270
phase0 = joinp->phase0;
1271
phase1 = joinp->phase1;
1272
arcData0 = &polyArcs[phase0].arcs[arcIndex0];
1273
arcData1 = &polyArcs[phase1].arcs[arcIndex1];
1274
miArcJoin (pDrawTo, pGCTo,
1275
&arcData0->bounds[end0],
1276
&arcData1->bounds[end1],
1277
arcData0->arc.x, arcData0->arc.y,
1278
(double) arcData0->arc.width / 2.0,
1279
(double) arcData0->arc.height / 2.0,
1280
arcData1->arc.x, arcData1->arc.y,
1281
(double) arcData1->arc.width / 2.0,
1282
(double) arcData1->arc.height / 2.0);
1286
if (pGC->serialNumber != pDraw->serialNumber)
1287
ValidateGC (pDraw, pGC);
1288
(*pGC->ops->PushPixels) (pGC, (PixmapPtr)pDrawTo,
1289
pDraw, pixmapWidth, pixmapHeight, xOrg, yOrg);
1290
miClearDrawable ((DrawablePtr) pDrawTo, pGCTo);
1295
miFreeArcs(polyArcs, pGC);
1299
(*pGCTo->pScreen->DestroyPixmap)((PixmapPtr)pDrawTo);
1300
FreeScratchGC(pGCTo);
1306
angleBetween (SppPointRec center, SppPointRec point1, SppPointRec point2)
1311
* reflect from X coordinates back to ellipse
1312
* coordinates -- y increasing upwards
1314
a1 = miDatan2 (- (point1.y - center.y), point1.x - center.x);
1315
a2 = miDatan2 (- (point2.y - center.y), point2.x - center.x);
1338
b->counterClock.x -= fx;
1339
b->counterClock.y -= fy;
1343
miArcJoin(DrawablePtr pDraw, GCPtr pGC, miArcFacePtr pLeft,
1344
miArcFacePtr pRight, int xOrgLeft, int yOrgLeft,
1345
double xFtransLeft, double yFtransLeft,
1346
int xOrgRight, int yOrgRight,
1347
double xFtransRight, double yFtransRight)
1349
SppPointRec center, corner, otherCorner;
1350
SppPointRec poly[5], e;
1351
SppPointPtr pArcPts;
1354
miArcFaceRec Right, Left;
1357
double xFtrans, yFtrans;
1359
double ae, ac2, ec2, bc2, de;
1362
xOrg = (xOrgRight + xOrgLeft) / 2;
1363
yOrg = (yOrgRight + yOrgLeft) / 2;
1364
xFtrans = (xFtransLeft + xFtransRight) / 2;
1365
yFtrans = (yFtransLeft + yFtransRight) / 2;
1367
translateBounds (&Right, xOrg - xOrgRight, yOrg - yOrgRight,
1368
xFtrans - xFtransRight, yFtrans - yFtransRight);
1370
translateBounds (&Left, xOrg - xOrgLeft, yOrg - yOrgLeft,
1371
xFtrans - xFtransLeft, yFtrans - yFtransLeft);
1375
if (pRight->clock.x == pLeft->counterClock.x &&
1376
pRight->clock.y == pLeft->counterClock.y)
1378
center = pRight->center;
1379
if (0 <= (a = angleBetween (center, pRight->clock, pLeft->counterClock))
1382
corner = pRight->clock;
1383
otherCorner = pLeft->counterClock;
1385
a = angleBetween (center, pLeft->clock, pRight->counterClock);
1386
corner = pLeft->clock;
1387
otherCorner = pRight->counterClock;
1389
switch (pGC->joinStyle) {
1391
width = (pGC->lineWidth ? (double)pGC->lineWidth : (double)1);
1393
arc.x = center.x - width/2;
1394
arc.y = center.y - width/2;
1397
arc.angle1 = -miDatan2 (corner.y - center.y, corner.x - center.x);
1399
pArcPts = (SppPointPtr) xalloc (3 * sizeof (SppPointRec));
1402
pArcPts[0].x = otherCorner.x;
1403
pArcPts[0].y = otherCorner.y;
1404
pArcPts[1].x = center.x;
1405
pArcPts[1].y = center.y;
1406
pArcPts[2].x = corner.x;
1407
pArcPts[2].y = corner.y;
1408
if( (cpt = miGetArcPts(&arc, 3, &pArcPts)) )
1410
/* by drawing with miFillSppPoly and setting the endpoints of the arc
1411
* to be the corners, we assure that the cap will meet up with the
1412
* rest of the line */
1413
miFillSppPoly(pDraw, pGC, cpt, pArcPts, xOrg, yOrg, xFtrans, yFtrans);
1419
* don't miter arcs with less than 11 degrees between them
1424
poly[2] = otherCorner;
1425
bc2 = (corner.x - otherCorner.x) * (corner.x - otherCorner.x) +
1426
(corner.y - otherCorner.y) * (corner.y - otherCorner.y);
1428
ac2 = (corner.x - center.x) * (corner.x - center.x) +
1429
(corner.y - center.y) * (corner.y - center.y);
1430
ae = sqrt (ac2 - ec2);
1432
e.x = (corner.x + otherCorner.x) / 2;
1433
e.y = (corner.y + otherCorner.y) / 2;
1434
poly[3].x = e.x + de * (e.x - center.x) / ae;
1435
poly[3].y = e.y + de * (e.y - center.y) / ae;
1443
poly[2] = otherCorner;
1448
miFillSppPoly (pDraw, pGC, polyLen, poly, xOrg, yOrg, xFtrans, yFtrans);
1463
SppPointRec corner, otherCorner, center, endPoint, poly[5];
1465
corner = pFace->clock;
1466
otherCorner = pFace->counterClock;
1467
center = pFace->center;
1468
switch (pGC->capStyle) {
1470
poly[0].x = otherCorner.x;
1471
poly[0].y = otherCorner.y;
1472
poly[1].x = corner.x;
1473
poly[1].y = corner.y;
1474
poly[2].x = corner.x -
1475
(center.y - corner.y);
1476
poly[2].y = corner.y +
1477
(center.x - corner.x);
1478
poly[3].x = otherCorner.x -
1479
(otherCorner.y - center.y);
1480
poly[3].y = otherCorner.y +
1481
(otherCorner.x - center.x);
1482
poly[4].x = otherCorner.x;
1483
poly[4].y = otherCorner.y;
1484
miFillSppPoly (pDraw, pGC, 5, poly, xOrg, yOrg, xFtrans, yFtrans);
1488
* miRoundCap just needs these to be unequal.
1491
endPoint.x = endPoint.x + 100;
1492
miRoundCap (pDraw, pGC, center, endPoint, corner, otherCorner, 0,
1493
-xOrg, -yOrg, xFtrans, yFtrans);
1498
/* MIROUNDCAP -- a private helper function
1499
* Put Rounded cap on end. pCenter is the center of this end of the line
1500
* pEnd is the center of the other end of the line. pCorner is one of the
1501
* two corners at this end of the line.
1502
* NOTE: pOtherCorner must be counter-clockwise from pCorner.
1509
SppPointRec pCenter,
1511
SppPointRec pCorner,
1512
SppPointRec pOtherCorner,
1522
SppPointPtr pArcPts;
1524
width = (pGC->lineWidth ? (double)pGC->lineWidth : (double)1);
1526
arc.x = pCenter.x - width/2;
1527
arc.y = pCenter.y - width/2;
1530
arc.angle1 = -miDatan2 (pCorner.y - pCenter.y, pCorner.x - pCenter.x);
1531
if(PTISEQUAL(pCenter, pEnd))
1532
arc.angle2 = - 180.0;
1534
arc.angle2 = -miDatan2 (pOtherCorner.y - pCenter.y, pOtherCorner.x - pCenter.x) - arc.angle1;
1536
arc.angle2 += 360.0;
1538
pArcPts = (SppPointPtr) NULL;
1539
if( (cpt = miGetArcPts(&arc, 0, &pArcPts)) )
1541
/* by drawing with miFillSppPoly and setting the endpoints of the arc
1542
* to be the corners, we assure that the cap will meet up with the
1543
* rest of the line */
1544
miFillSppPoly(pDraw, pGC, cpt, pArcPts, -xOrg, -yOrg, xFtrans, yFtrans);
1550
* To avoid inaccuracy at the cardinal points, use trig functions
1551
* which are exact for those angles
1555
#define M_PI 3.14159265358979323846
1558
#define M_PI_2 1.57079632679489661923
1561
# define Dsin(d) ((d) == 0.0 ? 0.0 : ((d) == 90.0 ? 1.0 : sin(d*M_PI/180.0)))
1562
# define Dcos(d) ((d) == 0.0 ? 1.0 : ((d) == 90.0 ? 0.0 : cos(d*M_PI/180.0)))
1563
# define mod(a,b) ((a) >= 0 ? (a) % (b) : (b) - (-a) % (b))
1570
if (floor (a/90) == a/90) {
1572
switch (mod (i, 4)) {
1579
return cos (a * M_PI / 180.0);
1587
if (floor (a/90) == a/90) {
1589
switch (mod (i, 4)) {
1596
return sin (a * M_PI / 180.0);
1608
return asin(v) * (180.0 / M_PI);
1612
miDatan2 (double dy, double dx)
1618
} else if (dx == 0) {
1622
} else if (Fabs (dy) == Fabs (dx)) {
1633
return atan2 (dy, dx) * (180.0 / M_PI);
1637
/* MIGETARCPTS -- Converts an arc into a set of line segments -- a helper
1638
* routine for filled arc and line (round cap) code.
1639
* Returns the number of points in the arc. Note that it takes a pointer
1640
* to a pointer to where it should put the points and an index (cpt).
1641
* This procedure allocates the space necessary to fit the arc points.
1642
* Sometimes it's convenient for those points to be at the end of an existing
1643
* array. (For example, if we want to leave a spare point to make sectors
1644
* instead of segments.) So we pass in the xalloc()ed chunk that contains the
1645
* array and an index saying where we should start stashing the points.
1646
* If there isn't an array already, we just pass in a null pointer and
1647
* count on xrealloc() to handle the null pointer correctly.
1651
SppArcPtr parc, /* points to an arc */
1652
int cpt, /* number of points already in arc list */
1653
SppPointPtr *ppPts) /* pointer to pointer to arc-list -- modified */
1655
double st, /* Start Theta, start angle */
1656
et, /* End Theta, offset from start theta */
1657
dt, /* Delta Theta, angle to sweep ellipse */
1658
cdt, /* Cos Delta Theta, actually 2 cos(dt) */
1659
x0, y0, /* the recurrence formula needs two points to start */
1661
x2, y2, /* this will be the new point generated */
1662
xc, yc; /* the center point */
1666
/* The spec says that positive angles indicate counterclockwise motion.
1667
* Given our coordinate system (with 0,0 in the upper left corner),
1668
* the screen appears flipped in Y. The easiest fix is to negate the
1671
st = - parc->angle1;
1673
et = - parc->angle2;
1675
/* Try to get a delta theta that is within 1/2 pixel. Then adjust it
1676
* so that it divides evenly into the total.
1677
* I'm just using cdt 'cause I'm lazy.
1680
if (parc->height > cdt)
1687
dt = miDasin ( 1.0 / cdt ); /* minimum step necessary */
1689
count = abs(count) + 1;
1693
cdt = 2 * miDcos(dt);
1694
if (!(poly = (SppPointPtr) xrealloc((pointer)*ppPts,
1695
(cpt + count) * sizeof(SppPointRec))))
1699
xc = parc->width/2.0; /* store half width and half height */
1700
yc = parc->height/2.0;
1702
x0 = xc * miDcos(st);
1703
y0 = yc * miDsin(st);
1704
x1 = xc * miDcos(st + dt);
1705
y1 = yc * miDsin(st + dt);
1706
xc += parc->x; /* by adding initial point, these become */
1707
yc += parc->y; /* the center point */
1709
poly[cpt].x = (xc + x0);
1710
poly[cpt].y = (yc + y0);
1711
poly[cpt + 1].x = (xc + x1);
1712
poly[cpt + 1].y = (yc + y1);
1714
for(i = 2; i < count; i++)
1719
poly[cpt + i].x = (xc + x2);
1720
poly[cpt + i].y = (yc + y2);
1725
/* adjust the last point */
1726
if (abs(parc->angle2) >= 360.0)
1727
poly[cpt +i -1] = poly[0];
1729
poly[cpt +i -1].x = (miDcos(st + et) * parc->width/2.0 + xc);
1730
poly[cpt +i -1].y = (miDsin(st + et) * parc->height/2.0 + yc);
1737
double x0, y0, x1, y1;
1741
# define ADD_REALLOC_STEP 20
1754
if (*ncapsp == *sizep)
1756
newsize = *sizep + ADD_REALLOC_STEP;
1757
cap = (miArcCapPtr) xrealloc (*capsp,
1758
newsize * sizeof (**capsp));
1764
cap = &(*capsp)[*ncapsp];
1766
cap->arcIndex = arcIndex;
1772
miArcJoinPtr *joinsp,
1785
if (*njoinsp == *sizep)
1787
newsize = *sizep + ADD_REALLOC_STEP;
1788
join = (miArcJoinPtr) xrealloc (*joinsp,
1789
newsize * sizeof (**joinsp));
1795
join = &(*joinsp)[*njoinsp];
1797
join->arcIndex0 = index0;
1798
join->phase0 = phase0;
1800
join->arcIndex1 = index1;
1801
join->phase1 = phase1;
1807
miArcDataPtr *arcsp,
1815
if (*narcsp == *sizep)
1817
newsize = *sizep + ADD_REALLOC_STEP;
1818
arc = (miArcDataPtr) xrealloc (*arcsp,
1819
newsize * sizeof (**arcsp));
1821
return (miArcDataPtr)NULL;
1825
arc = &(*arcsp)[*narcsp];
1838
for (iphase = ((pGC->lineStyle == LineDoubleDash) ? 1 : 0);
1842
if (arcs[iphase].narcs > 0)
1843
xfree(arcs[iphase].arcs);
1844
if (arcs[iphase].njoins > 0)
1845
xfree(arcs[iphase].joins);
1846
if (arcs[iphase].ncaps > 0)
1847
xfree(arcs[iphase].caps);
1853
* map angles to radial distance. This only deals with the first quadrant
1857
* a polygonal approximation to the arc for computing arc lengths
1860
# define DASH_MAP_SIZE 91
1862
# define dashIndexToAngle(di) ((((double) (di)) * 90.0) / ((double) DASH_MAP_SIZE - 1))
1863
# define xAngleToDashIndex(xa) ((((long) (xa)) * (DASH_MAP_SIZE - 1)) / (90 * 64))
1864
# define dashIndexToXAngle(di) ((((long) (di)) * (90 * 64)) / (DASH_MAP_SIZE - 1))
1865
# define dashXAngleStep (((double) (90 * 64)) / ((double) (DASH_MAP_SIZE - 1)))
1868
double map[DASH_MAP_SIZE];
1871
static int computeAngleFromPath(int startAngle, int endAngle, dashMap *map,
1872
int *lenp, int backwards);
1880
double a, x, y, prevx = 0.0, prevy = 0.0, dist;
1882
for (di = 0; di < DASH_MAP_SIZE; di++) {
1883
a = dashIndexToAngle (di);
1884
x = ((double) arcp->width / 2.0) * miDcos (a);
1885
y = ((double) arcp->height / 2.0) * miDsin (a);
1889
dist = hypot (x - prevx, y - prevy);
1890
map->map[di] = map->map[di - 1] + dist;
1897
typedef enum {HORIZONTAL, VERTICAL, OTHER} arcTypes;
1899
/* this routine is a bit gory */
1907
int isDashed, isDoubleDash;
1910
int start, i, j, k = 0, nexti, nextk = 0;
1916
struct arcData *data;
1919
int iphase, prevphase = 0, joinphase;
1923
int iDash = 0, dashRemaining;
1924
int iDashStart = 0, dashRemainingStart = 0, iphaseStart;
1925
int startAngle, spanAngle, endAngle, backwards = 0;
1926
int prevDashAngle, dashAngle;
1929
isDashed = !(pGC->lineStyle == LineSolid);
1930
isDoubleDash = (pGC->lineStyle == LineDoubleDash);
1931
dashOffset = pGC->dashOffset;
1933
data = (struct arcData *) ALLOCATE_LOCAL (narcs * sizeof (struct arcData));
1935
return (miPolyArcPtr)NULL;
1936
arcs = (miPolyArcPtr) xalloc (sizeof (*arcs) * (isDoubleDash ? 2 : 1));
1939
DEALLOCATE_LOCAL(data);
1940
return (miPolyArcPtr)NULL;
1942
for (i = 0; i < narcs; i++) {
1943
a0 = todeg (parcs[i].angle1);
1944
angle2 = parcs[i].angle2;
1945
if (angle2 > FULLCIRCLE)
1946
angle2 = FULLCIRCLE;
1947
else if (angle2 < -FULLCIRCLE)
1948
angle2 = -FULLCIRCLE;
1949
data[i].selfJoin = angle2 == FULLCIRCLE || angle2 == -FULLCIRCLE;
1950
a1 = todeg (parcs[i].angle1 + angle2);
1951
data[i].x0 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a0));
1952
data[i].y0 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a0));
1953
data[i].x1 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a1));
1954
data[i].y1 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a1));
1957
for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++) {
1958
arcs[iphase].njoins = 0;
1959
arcs[iphase].joins = 0;
1960
joinSize[iphase] = 0;
1962
arcs[iphase].ncaps = 0;
1963
arcs[iphase].caps = 0;
1964
capSize[iphase] = 0;
1966
arcs[iphase].narcs = 0;
1967
arcs[iphase].arcs = 0;
1968
arcSize[iphase] = 0;
1974
dashRemaining = pGC->dash[0];
1975
while (dashOffset > 0) {
1976
if (dashOffset >= dashRemaining) {
1977
dashOffset -= dashRemaining;
1978
iphase = iphase ? 0 : 1;
1980
if (iDash == pGC->numInDashList)
1982
dashRemaining = pGC->dash[iDash];
1984
dashRemaining -= dashOffset;
1989
dashRemainingStart = dashRemaining;
1991
iphaseStart = iphase;
1993
for (i = narcs - 1; i >= 0; i--) {
1997
if (data[i].selfJoin || i == j ||
1998
(UNEQUAL (data[i].x1, data[j].x0) ||
1999
UNEQUAL (data[i].y1, data[j].y0)))
2001
if (iphase == 0 || isDoubleDash)
2002
addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
2003
&capSize[iphase], RIGHT_END, 0);
2020
** deal with dashed arcs. Use special rules for certain 0 area arcs.
2021
** Presumably, the other 0 area arcs still aren't done right.
2023
arcTypes arcType = OTHER;
2026
if (parcs[i].height == 0
2027
&& (parcs[i].angle1 % FULLCIRCLE) == 0x2d00
2028
&& parcs[i].angle2 == 0x2d00)
2029
arcType = HORIZONTAL;
2030
else if (parcs[i].width == 0
2031
&& (parcs[i].angle1 % FULLCIRCLE) == 0x1680
2032
&& parcs[i].angle2 == 0x2d00)
2034
if (arcType == OTHER) {
2036
* precompute an approximation map
2038
computeDashMap (&parcs[i], &map);
2040
* compute each individual dash segment using the path
2043
startAngle = parcs[i].angle1;
2044
spanAngle = parcs[i].angle2;
2045
if (spanAngle > FULLCIRCLE)
2046
spanAngle = FULLCIRCLE;
2047
else if (spanAngle < -FULLCIRCLE)
2048
spanAngle = -FULLCIRCLE;
2050
startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
2051
if (startAngle >= FULLCIRCLE)
2052
startAngle = startAngle % FULLCIRCLE;
2053
endAngle = startAngle + spanAngle;
2054
backwards = spanAngle < 0;
2057
if (arcType == VERTICAL) {
2058
xarc.angle1 = 0x1680;
2059
startAngle = parcs[i].y;
2060
endAngle = startAngle + parcs[i].height;
2062
xarc.angle1 = 0x2d00;
2063
startAngle = parcs[i].x;
2064
endAngle = startAngle + parcs[i].width;
2067
dashAngle = startAngle;
2068
selfJoin = data[i].selfJoin &&
2069
(iphase == 0 || isDoubleDash);
2071
* add dashed arcs to each bucket
2074
while (dashAngle != endAngle) {
2075
prevDashAngle = dashAngle;
2076
if (arcType == OTHER) {
2077
dashAngle = computeAngleFromPath (prevDashAngle, endAngle,
2078
&map, &dashRemaining, backwards);
2079
/* avoid troubles with huge arcs and small dashes */
2080
if (dashAngle == prevDashAngle) {
2087
thisLength = (dashAngle + dashRemaining <= endAngle) ?
2088
dashRemaining : endAngle - dashAngle;
2089
if (arcType == VERTICAL) {
2091
xarc.height = thisLength;
2094
xarc.width = thisLength;
2096
dashAngle += thisLength;
2097
dashRemaining -= thisLength;
2099
if (iphase == 0 || isDoubleDash) {
2100
if (arcType == OTHER) {
2102
spanAngle = prevDashAngle;
2104
spanAngle = FULLCIRCLE - (-spanAngle) % FULLCIRCLE;
2105
if (spanAngle >= FULLCIRCLE)
2106
spanAngle = spanAngle % FULLCIRCLE;
2107
xarc.angle1 = spanAngle;
2108
spanAngle = dashAngle - prevDashAngle;
2110
if (dashAngle > prevDashAngle)
2111
spanAngle = - FULLCIRCLE + spanAngle;
2113
if (dashAngle < prevDashAngle)
2114
spanAngle = FULLCIRCLE + spanAngle;
2116
if (spanAngle > FULLCIRCLE)
2117
spanAngle = FULLCIRCLE;
2118
if (spanAngle < -FULLCIRCLE)
2119
spanAngle = -FULLCIRCLE;
2120
xarc.angle2 = spanAngle;
2122
arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
2123
&arcSize[iphase], &xarc);
2127
* cap each end of an on/off dash
2129
if (!isDoubleDash) {
2130
if (prevDashAngle != startAngle) {
2131
addCap (&arcs[iphase].caps,
2132
&arcs[iphase].ncaps,
2133
&capSize[iphase], RIGHT_END,
2134
arc - arcs[iphase].arcs);
2137
if (dashAngle != endAngle) {
2138
addCap (&arcs[iphase].caps,
2139
&arcs[iphase].ncaps,
2140
&capSize[iphase], LEFT_END,
2141
arc - arcs[iphase].arcs);
2144
arc->cap = arcs[iphase].ncaps;
2145
arc->join = arcs[iphase].njoins;
2148
if (dashAngle == endAngle)
2149
arc->selfJoin = selfJoin;
2152
if (dashRemaining <= 0) {
2154
if (iDash == pGC->numInDashList)
2156
iphase = iphase ? 0:1;
2157
dashRemaining = pGC->dash[iDash];
2161
* make sure a place exists for the position data when
2162
* drawing a zero-length arc
2164
if (startAngle == endAngle) {
2166
if (!isDoubleDash && iphase == 1)
2168
arc = addArc (&arcs[prevphase].arcs, &arcs[prevphase].narcs,
2169
&arcSize[prevphase], &parcs[i]);
2172
arc->join = arcs[prevphase].njoins;
2173
arc->cap = arcs[prevphase].ncaps;
2174
arc->selfJoin = data[i].selfJoin;
2177
arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
2178
&arcSize[iphase], &parcs[i]);
2181
arc->join = arcs[iphase].njoins;
2182
arc->cap = arcs[iphase].ncaps;
2183
arc->selfJoin = data[i].selfJoin;
2186
if (prevphase == 0 || isDoubleDash)
2187
k = arcs[prevphase].narcs - 1;
2188
if (iphase == 0 || isDoubleDash)
2189
nextk = arcs[iphase].narcs;
2190
if (nexti == start) {
2194
iphase = iphaseStart;
2195
dashRemaining = dashRemainingStart;
2198
arcsJoin = narcs > 1 && i != j &&
2199
ISEQUAL (data[i].x1, data[j].x0) &&
2200
ISEQUAL (data[i].y1, data[j].y0) &&
2201
!data[i].selfJoin && !data[j].selfJoin;
2210
(prevphase == 0 || isDoubleDash) &&
2211
(iphase == 0 || isDoubleDash))
2216
joinphase = iphaseStart;
2218
* if the join is right at the dash,
2219
* draw the join in foreground
2220
* This is because the foreground
2221
* arcs are computed second, the results
2222
* of which are needed to draw the join
2224
if (joinphase != prevphase)
2227
if (joinphase == 0 || isDoubleDash) {
2228
addJoin (&arcs[joinphase].joins,
2229
&arcs[joinphase].njoins,
2230
&joinSize[joinphase],
2231
LEFT_END, k, prevphase,
2232
RIGHT_END, nextk, iphase);
2233
arc->join = arcs[prevphase].njoins;
2237
* cap the left end of this arc
2238
* unless it joins itself
2240
if ((prevphase == 0 || isDoubleDash) &&
2243
addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,
2244
&capSize[prevphase], LEFT_END, k);
2245
arc->cap = arcs[prevphase].ncaps;
2247
if (isDashed && !arcsJoin) {
2249
iphase = iphaseStart;
2250
dashRemaining = dashRemainingStart;
2252
nextk = arcs[iphase].narcs;
2253
if (nexti == start) {
2256
iphase = iphaseStart;
2257
dashRemaining = dashRemainingStart;
2260
* cap the right end of the next arc. If the
2261
* next arc is actually the first arc, only
2262
* cap it if it joins with this arc. This
2263
* case will occur when the final dash segment
2264
* of an on/off dash is off. Of course, this
2265
* cap will be drawn at a strange time, but that
2268
if ((iphase == 0 || isDoubleDash) &&
2269
(nexti != start || (arcsJoin && isDashed)))
2270
addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
2271
&capSize[iphase], RIGHT_END, nextk);
2278
* make sure the last section is rendered
2280
for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++)
2281
if (arcs[iphase].narcs > 0) {
2282
arcs[iphase].arcs[arcs[iphase].narcs-1].render = 1;
2283
arcs[iphase].arcs[arcs[iphase].narcs-1].join =
2284
arcs[iphase].njoins;
2285
arcs[iphase].arcs[arcs[iphase].narcs-1].cap =
2288
DEALLOCATE_LOCAL(data);
2291
miFreeArcs(arcs, pGC);
2292
DEALLOCATE_LOCAL(data);
2293
return (miPolyArcPtr)NULL;
2301
double len, excesslen, sidelen = map->map[DASH_MAP_SIZE - 1], totallen;
2304
Bool oddSide = FALSE;
2308
while (angle >= 90 * 64) {
2310
totallen += sidelen;
2316
totallen -= sidelen;
2321
angle = 90 * 64 - angle;
2323
di = xAngleToDashIndex (angle);
2324
excess = angle - dashIndexToXAngle (di);
2328
* linearly interpolate between this point and the next
2331
excesslen = (map->map[di + 1] - map->map[di]) *
2332
((double) excess) / dashXAngleStep;
2336
totallen += (sidelen - len);
2343
* len is along the arc, but may be more than one rotation
2351
double sidelen = map->map[DASH_MAP_SIZE - 1];
2352
int angle, angleexcess;
2353
Bool oddSide = FALSE;
2358
* step around the ellipse, subtracting sidelens and
2359
* adding 90 degrees. oddSide will tell if the
2360
* map should be interpolated in reverse
2364
return 2 * FULLCIRCLE; /* infinity */
2365
while (len >= sidelen) {
2372
return -2 * FULLCIRCLE; /* infinity */
2380
len = sidelen - len;
2382
a1 = DASH_MAP_SIZE - 1;
2384
* binary search for the closest pre-computed length
2386
while (a1 - a0 > 1) {
2388
if (len > map->map[a])
2393
angleexcess = dashIndexToXAngle (a0);
2395
* linearly interpolate to the next point
2397
angleexcess += (len - map->map[a0]) /
2398
(map->map[a0+1] - map->map[a0]) * dashXAngleStep;
2400
angle += (90 * 64) - angleexcess;
2402
angle += angleexcess;
2407
* compute the angle of an ellipse which cooresponds to
2408
* the given path length. Note that the correct solution
2409
* to this problem is an eliptic integral, we'll punt and
2410
* approximate (it's only for dashes anyway). This
2411
* approximation uses a polygon.
2413
* The remaining portion of len is stored in *lenp -
2414
* this will be negative if the arc extends beyond
2415
* len and positive if len extends beyond the arc.
2419
computeAngleFromPath (
2421
int endAngle, /* normalized absolute angles in *64 degrees */
2435
* flip the problem around to always be
2438
a0 = FULLCIRCLE - a0;
2439
a1 = FULLCIRCLE - a1;
2443
len0 = angleToLength (a0, map);
2444
a = lengthToAngle (len0 + len, map);
2447
len -= angleToLength (a1, map) - len0;
2457
* scan convert wide arcs.
2461
* draw zero width/height arcs
2473
double x0 = 0.0, y0 = 0.0, x1 = 0.0, y1 = 0.0, w, h, x, y;
2474
double xmax, ymax, xmin, ymin;
2476
double a, startAngle, endAngle;
2482
if (a1 > FULLCIRCLE)
2484
else if (a1 < -FULLCIRCLE)
2486
w = (double)tarc->width / 2.0;
2487
h = (double)tarc->height / 2.0;
2489
* play in X coordinates right away
2491
startAngle = - ((double) a0 / 64.0);
2492
endAngle = - ((double) (a0 + a1) / 64.0);
2503
if (a == startAngle)
2523
if (a1 < 0) /* clockwise */
2525
if (floor (a / 90.0) == floor (endAngle / 90.0))
2528
a = 90 * (floor (a/90.0) + 1);
2532
if (ceil (a / 90.0) == ceil (endAngle / 90.0))
2535
a = 90 * (ceil (a/90.0) - 1);
2539
if ((x1 - x0) + (y1 - y0) < 0)
2550
right->center.x = x0;
2551
right->center.y = y0;
2552
right->clock.x = x0 - lx;
2553
right->clock.y = y0 - ly;
2554
right->counterClock.x = x0 + lx;
2555
right->counterClock.y = y0 + ly;
2559
left->center.x = x1;
2560
left->center.y = y1;
2561
left->clock.x = x1 + lx;
2562
left->clock.y = y1 + ly;
2563
left->counterClock.x = x1 - lx;
2564
left->counterClock.y = y1 - ly;
2578
if (xmax != xmin && ymax != ymin) {
2579
int minx, maxx, miny, maxy;
2582
minx = ICEIL (xmin + w) + tarc->x;
2583
maxx = ICEIL (xmax + w) + tarc->x;
2584
miny = ICEIL (ymin + h) + tarc->y;
2585
maxy = ICEIL (ymax + h) + tarc->y;
2588
rect.width = maxx - minx;
2589
rect.height = maxy - miny;
2590
(*pGC->ops->PolyFillRect) (pDraw, pGC, 1, &rect);
2595
* this computes the ellipse y value associated with the
2596
* bottom of the tail.
2601
struct arc_def *def,
2602
struct accelerators *acc)
2607
if (def->w == def->h)
2609
t = def->l * def->w;
2610
if (def->w > def->h) {
2617
t = 2.0 * def->h * t;
2618
t = (CUBED_ROOT_4 * acc->h2 - cbrt(t * t)) / acc->h2mw2;
2620
acc->tail_y = def->h / CUBED_ROOT_2 * sqrt(t);
2624
* inverse functions -- compute edge coordinates
2632
struct arc_def *def,
2633
struct accelerators *acc)
2635
return x + (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2642
struct arc_def *def,
2643
struct accelerators *acc)
2645
return y + (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2652
struct arc_def *def,
2653
struct accelerators *acc)
2655
return x - (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2662
struct arc_def *def,
2663
struct accelerators *acc)
2665
return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2671
struct arc_def *def,
2672
struct accelerators *acc)
2676
x = (def->w / def->h) * sqrt (acc->h2 - y*y);
2678
return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
2692
line->m = (x1 - x2) / (y1 - y2);
2693
line->b = x1 - y1 * line->m;
2699
* compute various accelerators for an ellipse. These
2700
* are simply values that are used repeatedly in
2708
struct arc_def *def,
2709
struct accelerators *acc)
2711
def->w = ((double) tarc->width) / 2.0;
2712
def->h = ((double) tarc->height) / 2.0;
2713
def->l = ((double) lw) / 2.0;
2714
acc->h2 = def->h * def->h;
2715
acc->w2 = def->w * def->w;
2716
acc->h4 = acc->h2 * acc->h2;
2717
acc->w4 = acc->w2 * acc->w2;
2718
acc->h2l = acc->h2 * def->l;
2719
acc->w2l = acc->w2 * def->l;
2720
acc->h2mw2 = acc->h2 - acc->w2;
2721
acc->fromIntX = (tarc->width & 1) ? 0.5 : 0.0;
2722
acc->fromIntY = (tarc->height & 1) ? 0.5 : 0.0;
2723
acc->xorg = tarc->x + (tarc->width >> 1);
2724
acc->yorgu = tarc->y + (tarc->height >> 1);
2725
acc->yorgl = acc->yorgu + (tarc->height & 1);
2726
tailEllipseY (def, acc);
2730
* compute y value bounds of various portions of the arc,
2731
* the outer edge, the ellipse and the inner edge.
2736
struct arc_def *def,
2737
struct arc_bound *bound,
2738
struct accelerators *acc,
2745
struct bound innerx, outerx;
2746
struct bound ellipsex;
2748
bound->ellipse.min = Dsin (def->a0) * def->h;
2749
bound->ellipse.max = Dsin (def->a1) * def->h;
2750
if (def->a0 == 45 && def->w == def->h)
2751
ellipsex.min = bound->ellipse.min;
2753
ellipsex.min = Dcos (def->a0) * def->w;
2754
if (def->a1 == 45 && def->w == def->h)
2755
ellipsex.max = bound->ellipse.max;
2757
ellipsex.max = Dcos (def->a1) * def->w;
2758
bound->outer.min = outerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2759
bound->outer.max = outerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2760
bound->inner.min = innerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2761
bound->inner.max = innerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2763
outerx.min = outerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2764
outerx.max = outerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2765
innerx.min = innerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
2766
innerx.max = innerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
2769
* save the line end points for the
2770
* cap code to use. Careful here, these are
2771
* in cartesean coordinates (y increasing upwards)
2772
* while the cap code uses inverted coordinates
2773
* (y increasing downwards)
2777
right->counterClock.y = bound->outer.min;
2778
right->counterClock.x = outerx.min;
2779
right->center.y = bound->ellipse.min;
2780
right->center.x = ellipsex.min;
2781
right->clock.y = bound->inner.min;
2782
right->clock.x = innerx.min;
2786
left->clock.y = bound->outer.max;
2787
left->clock.x = outerx.max;
2788
left->center.y = bound->ellipse.max;
2789
left->center.x = ellipsex.max;
2790
left->counterClock.y = bound->inner.max;
2791
left->counterClock.x = innerx.max;
2794
bound->left.min = bound->inner.max;
2795
bound->left.max = bound->outer.max;
2796
bound->right.min = bound->inner.min;
2797
bound->right.max = bound->outer.min;
2799
computeLine (innerx.min, bound->inner.min, outerx.min, bound->outer.min,
2801
computeLine (innerx.max, bound->inner.max, outerx.max, bound->outer.max,
2804
if (bound->inner.min > bound->inner.max) {
2805
t = bound->inner.min;
2806
bound->inner.min = bound->inner.max;
2807
bound->inner.max = t;
2809
tail_y = acc->tail_y;
2810
if (tail_y > bound->ellipse.max)
2811
tail_y = bound->ellipse.max;
2812
else if (tail_y < bound->ellipse.min)
2813
tail_y = bound->ellipse.min;
2814
innerTaily = innerYfromY (tail_y, def, acc);
2815
if (bound->inner.min > innerTaily)
2816
bound->inner.min = innerTaily;
2817
if (bound->inner.max < innerTaily)
2818
bound->inner.max = innerTaily;
2819
bound->inneri.min = ICEIL(bound->inner.min - acc->fromIntY);
2820
bound->inneri.max = floor(bound->inner.max - acc->fromIntY);
2821
bound->outeri.min = ICEIL(bound->outer.min - acc->fromIntY);
2822
bound->outeri.max = floor(bound->outer.max - acc->fromIntY);
2826
* this section computes the x value of the span at y
2827
* intersected with the specified face of the ellipse.
2829
* this is the min/max X value over the set of normal
2830
* lines to the entire ellipse, the equation of the
2834
* x = ------------ y + ellipse_x (1 - --- )
2837
* compute the derivative with-respect-to ellipse_y and solve
2840
* (w^2 - h^2) ellipse_y^3 + h^4 y
2841
* 0 = - ----------------------------------
2842
* h w ellipse_y^2 sqrt (h^2 - ellipse_y^2)
2845
* ellipse_y = ( ---------- ) ^ (1/3)
2848
* The other two solutions to the equation are imaginary.
2850
* This gives the position on the ellipse which generates
2851
* the normal with the largest/smallest x intersection point.
2853
* Now compute the second derivative to check whether
2854
* the intersection is a minimum or maximum:
2856
* h (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2857
* - -------------------------------------------
2858
* w y0^3 (sqrt (h^2 - y^2)) ^ 3
2860
* as we only care about the sign,
2862
* - (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
2864
* or (to use accelerators),
2866
* y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2)
2871
* computes the position on the ellipse whose normal line
2872
* intersects the given scan line maximally
2878
struct arc_bound *bound,
2879
struct accelerators *acc,
2884
if (acc->h2mw2 == 0) {
2885
if ( (scan_y > 0 && !left) || (scan_y < 0 && left) )
2886
return bound->ellipse.min;
2887
return bound->ellipse.max;
2889
ret = (acc->h4 * scan_y) / (acc->h2mw2);
2893
return -cbrt (-ret);
2897
* computes the X value of the intersection of the
2898
* given scan line with the right side of the lower hook
2904
struct arc_def *def,
2905
struct arc_bound *bound,
2906
struct accelerators *acc,
2909
double ellipse_y, x;
2912
if (def->w != def->h) {
2913
ellipse_y = hookEllipseY (scan_y, bound, acc, left);
2914
if (boundedLe (ellipse_y, bound->ellipse)) {
2916
* compute the value of the second
2919
maxMin = ellipse_y*ellipse_y*ellipse_y * acc->h2mw2 -
2920
acc->h2 * scan_y * (3 * ellipse_y*ellipse_y - 2*acc->h2);
2921
if ((left && maxMin > 0) || (!left && maxMin < 0)) {
2923
return def->w + left ? -def->l : def->l;
2924
x = (acc->h2 * scan_y - ellipse_y * acc->h2mw2) *
2925
sqrt (acc->h2 - ellipse_y * ellipse_y) /
2926
(def->h * def->w * ellipse_y);
2932
if (acc->left.valid && boundedLe (scan_y, bound->left)) {
2933
x = intersectLine (scan_y, acc->left);
2935
if (acc->right.valid)
2936
x = intersectLine (scan_y, acc->right);
2938
x = def->w - def->l;
2941
if (acc->right.valid && boundedLe (scan_y, bound->right)) {
2942
x = intersectLine (scan_y, acc->right);
2944
if (acc->left.valid)
2945
x = intersectLine (scan_y, acc->left);
2947
x = def->w - def->l;
2954
* generate the set of spans with
2955
* the given y coordinate
2965
struct arc_def *def,
2966
struct arc_bound *bounds,
2967
struct accelerators *acc,
2970
int linx, loutx, rinx, routx;
2973
if (boundedLe (y, bounds->inneri)) {
2978
* intersection with left face
2980
x = hookX (y + acc->fromIntY, def, bounds, acc, 1);
2981
if (acc->right.valid &&
2982
boundedLe (y + acc->fromIntY, bounds->right))
2984
altx = intersectLine (y + acc->fromIntY, acc->right);
2988
linx = -ICEIL(acc->fromIntX - x);
2989
rinx = ICEIL(acc->fromIntX + x);
2991
if (boundedLe (y, bounds->outeri)) {
2996
* intersection with right face
2998
x = hookX (y + acc->fromIntY, def, bounds, acc, 0);
2999
if (acc->left.valid &&
3000
boundedLe (y + acc->fromIntY, bounds->left))
3003
x = intersectLine (y + acc->fromIntY, acc->left);
3007
loutx = -ICEIL(acc->fromIntX - x);
3008
routx = ICEIL(acc->fromIntX + x);
3012
newFinalSpan (acc->yorgu - y,
3013
acc->xorg + rinx, acc->xorg + routx);
3015
newFinalSpan (acc->yorgl + y,
3016
acc->xorg + rinx, acc->xorg + routx);
3020
newFinalSpan (acc->yorgu - y,
3021
acc->xorg - loutx, acc->xorg - linx);
3023
newFinalSpan (acc->yorgl + y,
3024
acc->xorg - loutx, acc->xorg - linx);
3034
struct arc_def *def,
3035
struct arc_bound *bounds,
3036
struct accelerators *acc,
3041
if (boundedLe (0, bounds->inneri) &&
3042
acc->left.valid && boundedLe (0, bounds->left) &&
3045
x = def->w - def->l;
3046
if (acc->left.b < x)
3048
lw = ICEIL(acc->fromIntX - x) - lx;
3050
rx = ICEIL(acc->fromIntX + x);
3053
arcSpan (0, lx, lw, rx, rw, def, bounds, acc, mask);
3061
struct arc_def *def,
3062
struct arc_bound *bounds,
3063
struct accelerators *acc,
3066
double yy, xalt, x, lx, rx;
3069
if (boundedLe(y, bounds->outeri))
3070
arcSpan (y, 0, lw, -rw, rw, def, bounds, acc, mask);
3071
else if (def->w != def->h) {
3072
yy = y + acc->fromIntY;
3073
x = tailX(yy, def, bounds, acc);
3074
if (yy == 0.0 && x == -rw - acc->fromIntX)
3076
if (acc->right.valid && boundedLe (yy, bounds->right)) {
3079
xalt = intersectLine (yy, acc->right);
3080
if (xalt >= -rw - acc->fromIntX && xalt <= rx)
3082
n = ICEIL(acc->fromIntX + lx);
3085
newFinalSpan (acc->yorgu - y,
3086
acc->xorg + n, acc->xorg + lw);
3088
newFinalSpan (acc->yorgl + y,
3089
acc->xorg + n, acc->xorg + lw);
3091
n = ICEIL(acc->fromIntX + rx);
3094
newFinalSpan (acc->yorgu - y,
3095
acc->xorg - rw, acc->xorg + n);
3097
newFinalSpan (acc->yorgl + y,
3098
acc->xorg - rw, acc->xorg + n);
3102
ICEIL(acc->fromIntX - x), 0,
3103
ICEIL(acc->fromIntX + x), 0,
3104
def, bounds, acc, mask);
3109
* create whole arcs out of pieces. This code is
3113
static struct finalSpan **finalSpans = NULL;
3114
static int finalMiny = 0, finalMaxy = -1;
3115
static int finalSize = 0;
3117
static int nspans = 0; /* total spans, not just y coords */
3120
struct finalSpan *next;
3121
int min, max; /* x values */
3124
static struct finalSpan *freeFinalSpans, *tmpFinalSpan;
3126
# define allocFinalSpan() (freeFinalSpans ?\
3127
((tmpFinalSpan = freeFinalSpans), \
3128
(freeFinalSpans = freeFinalSpans->next), \
3129
(tmpFinalSpan->next = 0), \
3133
# define SPAN_CHUNK_SIZE 128
3135
struct finalSpanChunk {
3136
struct finalSpan data[SPAN_CHUNK_SIZE];
3137
struct finalSpanChunk *next;
3140
static struct finalSpanChunk *chunks;
3145
register struct finalSpanChunk *newChunk;
3146
register struct finalSpan *span;
3149
newChunk = (struct finalSpanChunk *) xalloc (sizeof (struct finalSpanChunk));
3151
return (struct finalSpan *) NULL;
3152
newChunk->next = chunks;
3154
freeFinalSpans = span = newChunk->data + 1;
3155
for (i = 1; i < SPAN_CHUNK_SIZE-1; i++) {
3156
span->next = span+1;
3160
span = newChunk->data;
3166
disposeFinalSpans (void)
3168
struct finalSpanChunk *chunk, *next;
3170
for (chunk = chunks; chunk; chunk = next) {
3182
DrawablePtr pDrawable,
3185
register struct finalSpan *span;
3186
register DDXPointPtr xSpan;
3187
register int *xWidth;
3189
register struct finalSpan **f;
3196
xSpan = xSpans = (DDXPointPtr) ALLOCATE_LOCAL (nspans * sizeof (DDXPointRec));
3197
xWidth = xWidths = (int *) ALLOCATE_LOCAL (nspans * sizeof (int));
3198
if (xSpans && xWidths)
3202
for (spany = finalMiny; spany <= finalMaxy; spany++, f++) {
3203
for (span = *f; span; span=span->next) {
3204
if (span->max <= span->min)
3206
xSpan->x = span->min;
3209
*xWidth++ = span->max - span->min;
3213
(*pGC->ops->FillSpans) (pDrawable, pGC, i, xSpans, xWidths, TRUE);
3215
disposeFinalSpans ();
3217
DEALLOCATE_LOCAL (xSpans);
3219
DEALLOCATE_LOCAL (xWidths);
3226
# define SPAN_REALLOC 100
3228
# define findSpan(y) ((finalMiny <= (y) && (y) <= finalMaxy) ? \
3229
&finalSpans[(y) - finalMiny] : \
3232
static struct finalSpan **
3233
realFindSpan (int y)
3235
struct finalSpan **newSpans;
3236
int newSize, newMiny, newMaxy;
3240
if (y < finalMiny || y > finalMaxy) {
3246
change = finalMiny - y;
3248
change = y - finalMaxy;
3249
if (change >= SPAN_REALLOC)
3250
change += SPAN_REALLOC;
3252
change = SPAN_REALLOC;
3253
newSize = finalSize + change;
3254
newSpans = (struct finalSpan **) xalloc
3255
(newSize * sizeof (struct finalSpan *));
3257
return (struct finalSpan **)NULL;
3258
newMiny = finalMiny;
3259
newMaxy = finalMaxy;
3261
newMiny = finalMiny - change;
3263
newMaxy = finalMaxy + change;
3265
memmove(((char *) newSpans) + (finalMiny-newMiny) * sizeof (struct finalSpan *),
3266
(char *) finalSpans,
3267
finalSize * sizeof (struct finalSpan *));
3270
if ((i = finalMiny - newMiny) > 0)
3271
bzero ((char *)newSpans, i * sizeof (struct finalSpan *));
3272
if ((i = newMaxy - finalMaxy) > 0)
3273
bzero ((char *)(newSpans + newSize - i),
3274
i * sizeof (struct finalSpan *));
3275
finalSpans = newSpans;
3276
finalMaxy = newMaxy;
3277
finalMiny = newMiny;
3278
finalSize = newSize;
3280
return &finalSpans[y - finalMiny];
3289
register struct finalSpan *x;
3290
register struct finalSpan **f;
3291
struct finalSpan *oldx;
3292
struct finalSpan *prev;
3300
for (x = *f; x; x=x->next) {
3305
if (x->min <= xmax && xmin <= x->max) {
3307
oldx->min = min (x->min, xmin);
3308
oldx->max = max (x->max, xmax);
3310
prev->next = x->next;
3315
x->min = min (x->min, xmin);
3316
x->max = max (x->max, xmax);
3329
x = allocFinalSpan ();
3344
SppPointPtr sppPoint)
3350
sppPoint->x = -sppPoint->x;
3353
sppPoint->x = -sppPoint->x;
3354
sppPoint->y = -sppPoint->y;
3357
sppPoint->y = -sppPoint->y;
3361
* and translate to X coordinate system
3363
sppPoint->y = -sppPoint->y;
3367
* split an arc into pieces which are scan-converted
3368
* in the first-quadrant and mirrored into position.
3369
* This is necessary as the scan-conversion code can
3370
* only deal with arcs completely contained in the
3381
miArcFacePtr left) /* save end line points */
3384
struct accelerators acc;
3385
int startq, endq, curq;
3386
int rightq, leftq = 0, righta = 0, lefta = 0;
3387
miArcFacePtr passRight, passLeft;
3388
int q0 = 0, q1 = 0, mask;
3392
} band[5], sweep[20];
3393
int bandno, sweepno;
3395
int flipRight = 0, flipLeft = 0;
3397
miArcSpanData *spdata;
3400
spdata = miComputeWideEllipse(l, tarc, &mustFree);
3406
startq = a0 / (90 * 64);
3410
endq = (a1-1) / (90 * 64);
3422
q1 = min (a1, 90 * 64);
3425
if (curq == startq && a0 == q0 && rightq < 0) {
3429
if (curq == endq && a1 == q1) {
3438
q0 = 180 * 64 - min (a1, 180 * 64);
3442
q1 = 180 * 64 - max (a0, 90 * 64);
3443
if (curq == startq && 180 * 64 - a0 == q1) {
3447
if (curq == endq && 180 * 64 - a1 == q0) {
3456
q0 = max (a0, 180 * 64) - 180 * 64;
3460
q1 = min (a1, 270 * 64) - 180 * 64;
3461
if (curq == startq && a0 - 180*64 == q0) {
3465
if (curq == endq && a1 - 180 * 64 == q1) {
3474
q0 = 360 * 64 - min (a1, 360 * 64);
3475
q1 = 360 * 64 - max (a0, 270 * 64);
3476
if (curq == startq && 360 * 64 - a0 == q1) {
3480
if (curq == endq && 360 * 64 - a1 == q0) {
3486
band[bandno].a0 = q0;
3487
band[bandno].a1 = q1;
3488
band[bandno].mask = 1 << curq;
3505
* find left-most point
3507
for (i = 0; i < bandno; i++)
3508
if (band[i].a0 <= q0) {
3511
mask = band[i].mask;
3516
* locate next point of change
3518
for (i = 0; i < bandno; i++)
3519
if (!(mask & band[i].mask)) {
3520
if (band[i].a0 == q0) {
3521
if (band[i].a1 < q1)
3523
mask |= band[i].mask;
3524
} else if (band[i].a0 < q1)
3528
* create a new sweep
3530
sweep[sweepno].a0 = q0;
3531
sweep[sweepno].a1 = q1;
3532
sweep[sweepno].mask = mask;
3535
* subtract the sweep from the affected bands
3537
for (i = 0; i < bandno; i++)
3538
if (band[i].a0 == q0) {
3541
* check if this band is empty
3543
if (band[i].a0 == band[i].a1)
3544
band[i].a1 = band[i].a0 = 90 * 64 + 1;
3547
computeAcc (tarc, l, &def, &acc);
3548
for (j = 0; j < sweepno; j++) {
3549
mask = sweep[j].mask;
3550
passRight = passLeft = 0;
3551
if (mask & (1 << rightq)) {
3552
if (sweep[j].a0 == righta)
3554
else if (sweep[j].a1 == righta) {
3559
if (mask & (1 << leftq)) {
3560
if (sweep[j].a1 == lefta)
3566
else if (sweep[j].a0 == lefta) {
3573
drawQuadrant (&def, &acc, sweep[j].a0, sweep[j].a1, mask,
3574
passRight, passLeft, spdata);
3577
* when copyEnd is set, both ends of the arc were computed
3578
* at the same time; drawQuadrant only takes one end though,
3579
* so the left end will be the only one holding the data. Copy
3585
* mirror the coordinates generated for the
3589
mirrorSppPoint (rightq, &right->clock);
3590
mirrorSppPoint (rightq, &right->center);
3591
mirrorSppPoint (rightq, &right->counterClock);
3595
temp = right->clock;
3596
right->clock = right->counterClock;
3597
right->counterClock = temp;
3601
mirrorSppPoint (leftq, &left->counterClock);
3602
mirrorSppPoint (leftq, &left->center);
3603
mirrorSppPoint (leftq, &left->clock);
3608
left->clock = left->counterClock;
3609
left->counterClock = temp;
3618
struct arc_def *def,
3619
struct accelerators *acc,
3625
miArcSpanData *spdata)
3627
struct arc_bound bound;
3633
def->a0 = ((double) a0) / 64.0;
3634
def->a1 = ((double) a1) / 64.0;
3635
computeBound (def, &bound, acc, right, left);
3636
yy = bound.inner.min;
3637
if (bound.outer.min < yy)
3638
yy = bound.outer.min;
3639
miny = ICEIL(yy - acc->fromIntY);
3640
yy = bound.inner.max;
3641
if (bound.outer.max > yy)
3642
yy = bound.outer.max;
3643
maxy = floor(yy - acc->fromIntY);
3645
span = spdata->spans;
3648
if (a1 == 90 * 64 && (mask & 1))
3649
newFinalSpan (acc->yorgu - y - 1, acc->xorg, acc->xorg + 1);
3652
for (n = spdata->count1; --n >= 0; )
3658
span->lx, -span->lx, 0, span->lx + span->lw,
3659
def, &bound, acc, mask);
3660
if (span->rw + span->rx)
3661
tailSpan (y, -span->rw, -span->rx, def, &bound, acc, mask);
3671
arcSpan (y, 0, 0, 0, 1, def, &bound, acc, mask & 0xc);
3673
for (n = spdata->count2; --n >= 0; )
3678
arcSpan (y, span->lx, span->lw, span->rx, span->rw,
3679
def, &bound, acc, mask);
3683
if (spdata->bot && miny <= y && y <= maxy)
3688
if (span->rw <= 0) {
3689
arcSpan0 (span->lx, -span->lx, 0, span->lx + span->lw,
3690
def, &bound, acc, n);
3691
if (span->rw + span->rx)
3692
tailSpan (y, -span->rw, -span->rx, def, &bound, acc, n);
3695
arcSpan0 (span->lx, span->lw, span->rx, span->rw,
3696
def, &bound, acc, n);
3700
yy = y + acc->fromIntY;
3701
if (def->w == def->h) {
3702
xalt = def->w - def->l;
3703
x = -sqrt(xalt * xalt - yy * yy);
3705
x = tailX(yy, def, &bound, acc);
3706
if (acc->left.valid && boundedLe (yy, bound.left)) {
3707
xalt = intersectLine (yy, acc->left);
3711
if (acc->right.valid && boundedLe (yy, bound.right)) {
3712
xalt = intersectLine (yy, acc->right);
3718
ICEIL(acc->fromIntX - x), 0,
3719
ICEIL(acc->fromIntX + x), 0,
3720
def, &bound, acc, mask);
added
removed
mi/miarc.c
