1 /* This file is part of the GNU libxmi package.
2
3 Copyright (C) 1985, 1986, 1987, 1988, 1989, X Consortium. For an
4 associated permission notice, see the accompanying file README-X.
5
6 GNU enhancements Copyright (C) 1998, 1999, 2000, 2005, Free Software
7 Foundation, Inc.
8
9 The GNU libxmi package is free software. You may redistribute it
10 and/or modify it under the terms of the GNU General Public License as
11 published by the Free Software foundation; either version 2, or (at your
12 option) any later version.
13
14 The GNU libxmi package is distributed in the hope that it will be
15 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 General Public License for more details.
18
19 You should have received a copy of the GNU General Public License along
20 with the GNU plotutils package; see the file COPYING. If not, write to
21 the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor,
22 Boston, MA 02110-1301, USA. */
23
24 /* Original author: Bob Scheifler, MIT X Consortium, mid 1980s.
25 Hacked by Robert S. Maier <rsm@math.arizona.edu>, 1998-99 */
26
27 /* Derived from:
28 * "Algorithm for drawing ellipses or hyperbolae with a digital plotter"
29 * by M. L. V. Pitteway
30 * The Computer Journal, November 1967, Volume 10, Number 3, pp. 282-289
31 */
32
33 /* This module contains the miZeroPolyArc() function and its reentrant
34 counterpart miZeroPolyArc_r. They draw single-pixel (Bresenham)
35 polyarcs, either solid or dashed. A fast integer algorithm is used.
36
37 A polyarc is a list of arcs, which may or may not be contiguous. An
38 `arc' is an elliptic arc, i.e., a segment of an ellipse. The principal
39 axes of the ellipse must be aligned with the coordinate axes.
40
41 The cap mode and join mode in the graphics context are ignored.
42
43 All painting goes through the low-level MI_COPY_AND_PAINT_SPANS() and
44 MI_PAINT_SPANS() macros. */
45
46 #include "sys-defines.h"
47 #include "extern.h"
48
49 #include "xmi.h"
50 #include "mi_spans.h"
51 #include "mi_gc.h"
52 #include "mi_api.h"
53 #include "mi_arc.h"
54 #include "mi_zerarc.h"
55
56 #define FULLCIRCLE (360 * 64)
57 #define OCTANT (45 * 64)
58 #define QUADRANT (90 * 64)
59 #define HALFCIRCLE (180 * 64)
60 #define QUADRANT3 (270 * 64)
61
62 /* trig functions, angle specified in 1/64 degrees */
63 #define Dsin(d) ((d) == 0 ? 0.0 : ((d) == QUADRANT ? 1.0 : \
64 ((d) == HALFCIRCLE ? 0.0 : \
65 ((d) == QUADRANT3 ? -1.0 : sin((double)d*(M_PI/11520.0))))))
66
67 #define Dcos(d) ((d) == 0 ? 1.0 : ((d) == QUADRANT ? 0.0 : \
68 ((d) == HALFCIRCLE ? -1.0 : \
69 ((d) == QUADRANT3 ? 0.0 : cos((double)d*(M_PI/11520.0))))))
70
71 #define EPSILON45 64
72
73 typedef struct
74 {
75 bool skipStart;
76 bool haveStart;
77 miPoint startPt;
78 bool haveLast;
79 bool skipLast;
80 miPoint endPt;
81 int dashNum;
82 int dashIndex;
83 int dashOffset;
84 int dashNumInit;
85 int dashIndexInit;
86 int dashOffsetInit;
87 } miDashInfo;
88
89 static const miZeroArcPt _oob_arc_pt = {INT_MAX, INT_MAX, 0};
90
91 /* forward references */
92 static bool miZeroArcSetup (const miArc *arc, miZeroArc *info, bool ok360);
93 static miPoint * miZeroArcPts (const miArc *arc, miPoint *pts);
94 static void miZeroArcDashPts (const miGC *pGC, const miArc *arc, miDashInfo *dinfo, int maxPts, miPoint **pts);
95
96
97 /*
98 * This is the reentrant version, miZeroPolyArc_r. The non-reentrant
99 * version, miZeroPolyArc, simply calls this version, using an in-library
100 * `rasterized ellipse' cache. */
101
102 void
miZeroPolyArc_r(miPaintedSet * paintedSet,const miGC * pGC,int narcs,const miArc * parcs,miEllipseCache * ellipseCache)103 miZeroPolyArc_r (miPaintedSet *paintedSet, const miGC *pGC, int narcs, const miArc *parcs, miEllipseCache *ellipseCache)
104 {
105 const miArc *arc;
106 miDashInfo dinfo;
107 int j;
108
109 if (pGC->lineStyle != (int)MI_LINE_SOLID)
110 /* initialize structure used in dashing */
111 {
112 dinfo.haveStart = false;
113 dinfo.skipStart = false;
114 dinfo.haveLast = false;
115 dinfo.dashIndexInit = 0;
116 dinfo.dashNumInit = 0;
117 dinfo.dashOffsetInit = 0;
118 /* perform initial offsetting into the dash array */
119 miStepDash (pGC->dashOffset, &dinfo.dashNumInit, &dinfo.dashIndexInit,
120 pGC->dash, pGC->numInDashList, &dinfo.dashOffsetInit);
121 }
122
123 for (arc = parcs, j = narcs; --j >= 0; arc++)
124 {
125 if (!MI_CAN_ZERO_ARC(arc))
126 /* Too large an arc for integer algorithm to perform properly, so
127 hand it off to floating-point wide polyarc algorithm, which can
128 do zero-width polyarcs too. */
129 /* N.B. This handoff is lame. If dashing, dash pattern won't be
130 carried over from arc to contiguous arc. */
131 miPolyArc_r (paintedSet, pGC, 1, arc, ellipseCache);
132
133 else
134 /* not unusually large, use integer Bresenham algorithm */
135 {
136 miPoint **ptsInit, **pts;
137 int maxPts = 0, numPts, i, n;
138 int numPixels = pGC->numPixels;
139
140 if (arc->width > arc->height)
141 maxPts = arc->width + (arc->height >> 1);
142 else
143 maxPts = arc->height + (arc->width >> 1);
144 if (maxPts == 0)
145 continue;
146
147 /* max points produced by Bresenham algorithm (overestimate?) */
148 numPts = 4 * maxPts;
149
150 /* generate points (note that if dashing, dash pattern will carry
151 over from arc to contiguous arc) */
152 ptsInit =
153 (miPoint **)mi_xmalloc(numPixels * sizeof(miPoint *));
154 pts =
155 (miPoint **)mi_xmalloc(numPixels * sizeof(miPoint *));
156 if (pGC->lineStyle == (int)MI_LINE_SOLID)
157 {
158 for (i = 0; i < numPixels; i++)
159 {
160 if (i == 1)
161 ptsInit[i] = (miPoint *)mi_xmalloc(numPts * sizeof(miPoint));
162 else /* `solid' uses paint type #1 only */
163 ptsInit[i] = (miPoint *)NULL;
164 pts[i] = ptsInit[i];
165 }
166 /* compute points, return pointer to slot after
167 last-generated point */
168 pts[1] = miZeroArcPts (arc, ptsInit[1]);
169 }
170 else /* on/off dashed or double-dashed */
171 {
172 for (i = 0; i < numPixels; i++)
173 {
174 ptsInit[i] = (miPoint *)mi_xmalloc(numPts * sizeof(miPoint));
175 pts[i] = ptsInit[i];
176 }
177
178 /* compute points, return ptrs to ones after last-generated */
179 dinfo.skipLast = (i == 0 ? false : true);
180 miZeroArcDashPts (pGC, arc, &dinfo, maxPts, pts);
181 dinfo.skipStart = true;
182 }
183
184 /* paint all generated points (except if not double-dashing,
185 don't paint points in paint type #0) */
186 for (i = 0; i < numPixels; i++)
187 {
188 if (ptsInit[i] == (miPoint *)NULL)
189 continue;
190 if (i == 0 && pGC->lineStyle != (int)MI_LINE_DOUBLE_DASH)
191 {
192 free (ptsInit[i]);
193 continue;
194 }
195
196 n = pts[i] - ptsInit[i];
197 if (n > 0)
198 {
199 unsigned int *widths;
200 int k;
201
202 widths = (unsigned int *)mi_xmalloc(n * sizeof(unsigned int));
203 for (k = 0; k < n; k++)
204 widths[k] = 1;
205 miQuickSortSpansY (ptsInit[i], widths, n);
206 MI_PAINT_SPANS(paintedSet, pGC->pixels[i], n, ptsInit[i], widths)
207 }
208 } /* end of drawing loop over paint types */
209
210 /* free arrays of pointers to storage */
211 free (pts);
212 free (ptsInit);
213
214 } /* end of integer Bresenham algorithm applied to a single arc */
215 } /* end of loop over arcs */
216 }
217
218 #ifndef NO_NONREENTRANT_POLYARC_SUPPORT
219 void
miZeroPolyArc(miPaintedSet * paintedSet,const miGC * pGC,int narcs,const miArc * parcs)220 miZeroPolyArc (miPaintedSet *paintedSet, const miGC *pGC, int narcs, const miArc *parcs)
221 {
222 if (_mi_ellipseCache == (miEllipseCache *)NULL)
223 _mi_ellipseCache = miNewEllipseCache ();
224 miZeroPolyArc_r (paintedSet, pGC, narcs, parcs, _mi_ellipseCache);
225 }
226 #endif /* not NO_NONREENTRANT_POLYARC_SUPPORT */
227
228
229 #define Pixelate(pts, xval, yval) \
230 { \
231 pts->x = xval; \
232 pts->y = yval; \
233 pts++; \
234 }
235
236 #define DoPix(pts, mask, idx, xval, yval) \
237 if (mask & (1 << idx)) Pixelate(pts, xval, yval);
238
239 /* Generate points that make up a solid zero-width arc, and write them to
240 pre-allocated storage; return pointer to miPoint after last-generated
241 point. Storage supplied by caller, should be sufficiently large. */
242 static miPoint *
miZeroArcPts(const miArc * arc,miPoint * pts)243 miZeroArcPts (const miArc *arc, miPoint *pts)
244 {
245 miZeroArc info;
246 int x, y, a, b, d;
247 unsigned int mask;
248 int k1, k3, dx, dy;
249 bool do360;
250
251 do360 = miZeroArcSetup(arc, &info, true);
252 MIARCSETUP(info, x, y, k1, k3, a, b, d, dx, dy);
253 mask = info.initialMask;
254 if (!(arc->width & 1)) /* even width */
255 {
256 DoPix (pts, mask, 1, info.xorgo, info.yorg);
257 DoPix (pts, mask, 3, info.xorgo, info.yorgo);
258 }
259 if (!info.end.x || !info.end.y)
260 {
261 mask = info.end.mask;
262 info.end = info.altend;
263 }
264 if (do360 && (arc->width == arc->height) && !(arc->width & 1))
265 /* full circle, even diameter */
266 {
267 int yorgh = info.yorg + info.h;
268 int xorghp = info.xorg + info.h;
269 int xorghn = info.xorg - info.h;
270
271 for ( ; ; )
272 {
273 Pixelate(pts, info.xorg + x, info.yorg + y);
274 Pixelate(pts, info.xorg - x, info.yorg + y);
275 Pixelate(pts, info.xorg - x, info.yorgo - y);
276 Pixelate(pts, info.xorg + x, info.yorgo - y);
277 if (a < 0)
278 break;
279 Pixelate(pts, xorghp - y, yorgh - x);
280 Pixelate(pts, xorghn + y, yorgh - x);
281 Pixelate(pts, xorghn + y, yorgh + x);
282 Pixelate(pts, xorghp - y, yorgh + x);
283 MIARCCIRCLESTEP(x, y, a, b, d, k1, k3, ;);
284 }
285 if (x > 1 && pts[-1].x == pts[-5].x && pts[-1].y == pts[-5].y)
286 pts -= 4;
287 x = info.w;
288 y = info.h;
289 }
290 else if (do360)
291 /* full ellipse */
292 {
293 while (y < (int)info.h || x < (int)info.w)
294 {
295 MIARCOCTANTSHIFT(info, x, y, dx, dy, a, b, d, k1, k3, ;);
296 Pixelate(pts, info.xorg + x, info.yorg + y);
297 Pixelate(pts, info.xorgo - x, info.yorg + y);
298 Pixelate(pts, info.xorgo - x, info.yorgo - y);
299 Pixelate(pts, info.xorg + x, info.yorgo - y);
300 MIARCSTEP(x, y, dx, dy, a, b, d, k1, k3, ;, ;);
301 }
302 }
303 else
304 /* hard case */
305 {
306 while (y < (int)info.h || x < (int)info.w)
307 {
308 MIARCOCTANTSHIFT(info, x, y, dx, dy, a, b, d, k1, k3, ;);
309 if ((x == info.start.x) || (y == info.start.y))
310 {
311 mask = info.start.mask;
312 info.start = info.altstart;
313 }
314 DoPix (pts, mask, 0, info.xorg + x, info.yorg + y);
315 DoPix (pts, mask, 1, info.xorgo - x, info.yorg + y);
316 DoPix (pts, mask, 2, info.xorgo - x, info.yorgo - y);
317 DoPix (pts, mask, 3, info.xorg + x, info.yorgo - y);
318 if ((x == info.end.x) || (y == info.end.y))
319 {
320 mask = info.end.mask;
321 info.end = info.altend;
322 }
323 MIARCSTEP(x, y, dx, dy, a, b, d, k1, k3, ;, ;);
324 }
325 }
326 if ((x == info.start.x) || (y == info.start.y))
327 mask = info.start.mask;
328 DoPix (pts, mask, 0, info.xorg + x, info.yorg + y);
329 DoPix (pts, mask, 2, info.xorgo - x, info.yorgo - y);
330 if (arc->height & 1) /* odd height */
331 {
332 DoPix (pts, mask, 1, info.xorgo - x, info.yorg + y);
333 DoPix (pts, mask, 3, info.xorg + x, info.yorgo - y);
334 }
335
336 return pts;
337 }
338
339
340 #undef DoPix
341 #define DoPix(arcPts, mask, idx, xval, yval) \
342 if (mask & (1 << idx)) \
343 { \
344 arcPts[idx]->x = xval; \
345 arcPts[idx]->y = yval; \
346 arcPts[idx]++; \
347 }
348
349 /* Generate the points that make up a dashed zero-width arc, possibly
350 multicolored; write them to pre-allocated storage, indexed by paint
351 type. */
352
353 /* ARGS: dinfo = updated vars (e.g. dashNum, dashIndex),
354 pts[i] = storage for paint type #i */
355 static void
miZeroArcDashPts(const miGC * pGC,const miArc * arc,miDashInfo * dinfo,int maxPts,miPoint ** pts)356 miZeroArcDashPts (const miGC *pGC, const miArc *arc, miDashInfo *dinfo, int maxPts, miPoint **pts)
357 {
358 miZeroArc info;
359 int x, y, a, b, d;
360 unsigned int mask;
361 int k1, k3, dx, dy;
362 int dashRemaining, numPixels;
363 miPoint *points, *arcPts[4];
364 miPoint *startPts[5], *endPts[5];
365 int deltas[5];
366 miPoint *pt, *startPt, *lastPt;
367 int i, j, seg, startseg;
368
369 /* allocate temp storage, split into four pieces */
370 points = (miPoint *)mi_xmalloc(sizeof(miPoint) * 4 * maxPts);
371 for (i = 0; i < 4; i++)
372 arcPts[i] = points + (i * maxPts);
373
374 miZeroArcSetup (arc, &info, false);
375 MIARCSETUP(info, x, y, k1, k3, a, b, d, dx, dy);
376 mask = info.initialMask;
377 startseg = info.startAngle / QUADRANT;
378 startPt = arcPts[startseg];
379 if (!(arc->width & 1))
380 {
381 DoPix (arcPts, mask, 1, info.xorgo, info.yorg);
382 DoPix (arcPts, mask, 3, info.xorgo, info.yorgo);
383 }
384 if (!info.end.x || !info.end.y)
385 {
386 mask = info.end.mask;
387 info.end = info.altend;
388 }
389 while (y < (int)info.h || x < (int)info.w)
390 {
391 MIARCOCTANTSHIFT(info, x, y, dx, dy, a, b, d, k1, k3, ;);
392 if ((x == info.firstx) || (y == info.firsty))
393 startPt = arcPts[startseg];
394 if ((x == info.start.x) || (y == info.start.y))
395 {
396 mask = info.start.mask;
397 info.start = info.altstart;
398 }
399 DoPix (arcPts, mask, 0, info.xorg + x, info.yorg + y);
400 DoPix (arcPts, mask, 1, info.xorgo - x, info.yorg + y);
401 DoPix (arcPts, mask, 2, info.xorgo - x, info.yorgo - y);
402 DoPix (arcPts, mask, 3, info.xorg + x, info.yorgo - y);
403 if ((x == info.end.x) || (y == info.end.y))
404 {
405 mask = info.end.mask;
406 info.end = info.altend;
407 }
408 MIARCSTEP(x, y, dx, dy, a, b, d, k1, k3, ;, ;);
409 }
410 if ((x == info.firstx) || (y == info.firsty))
411 startPt = arcPts[startseg];
412 if ((x == info.start.x) || (y == info.start.y))
413 mask = info.start.mask;
414 DoPix (arcPts, mask, 0, info.xorg + x, info.yorg + y);
415 DoPix (arcPts, mask, 2, info.xorgo - x, info.yorgo - y);
416 if (arc->height & 1)
417 {
418 DoPix (arcPts, mask, 1, info.xorgo - x, info.yorg + y);
419 DoPix (arcPts, mask, 3, info.xorg + x, info.yorgo - y);
420 }
421 for (i = 0; i < 4; i++)
422 {
423 seg = (startseg + i) & 3;
424 pt = points + (seg * maxPts);
425 if (seg & 1)
426 {
427 startPts[i] = pt;
428 endPts[i] = arcPts[seg];
429 deltas[i] = 1;
430 }
431 else
432 {
433 startPts[i] = arcPts[seg] - 1;
434 endPts[i] = pt - 1;
435 deltas[i] = -1;
436 }
437 }
438 startPts[4] = startPts[0];
439 endPts[4] = startPt;
440 startPts[0] = startPt;
441 if (startseg & 1)
442 {
443 if (startPts[4] != endPts[4])
444 endPts[4]--;
445 deltas[4] = 1;
446 }
447 else
448 {
449 if (startPts[0] > startPts[4])
450 startPts[0]--;
451 if (startPts[4] < endPts[4])
452 endPts[4]--;
453 deltas[4] = -1;
454 }
455 if (arc->angle2 < 0)
456 {
457 miPoint *tmps, *tmpe;
458 int tmpd;
459
460 tmpd = deltas[0];
461 tmps = startPts[0] - tmpd;
462 tmpe = endPts[0] - tmpd;
463 startPts[0] = endPts[4] - deltas[4];
464 endPts[0] = startPts[4] - deltas[4];
465 deltas[0] = -deltas[4];
466 startPts[4] = tmpe;
467 endPts[4] = tmps;
468 deltas[4] = -tmpd;
469 tmpd = deltas[1];
470 tmps = startPts[1] - tmpd;
471 tmpe = endPts[1] - tmpd;
472 startPts[1] = endPts[3] - deltas[3];
473 endPts[1] = startPts[3] - deltas[3];
474 deltas[1] = -deltas[3];
475 startPts[3] = tmpe;
476 endPts[3] = tmps;
477 deltas[3] = -tmpd;
478 tmps = startPts[2] - deltas[2];
479 startPts[2] = endPts[2] - deltas[2];
480 endPts[2] = tmps;
481 deltas[2] = -deltas[2];
482 }
483 for (i = 0; i < 5 && startPts[i] == endPts[i]; i++)
484 ;
485 if (i == 5)
486 return;
487 pt = startPts[i];
488 for (j = 4; startPts[j] == endPts[j]; j--)
489 ;
490 lastPt = endPts[j] - deltas[j];
491 if (dinfo->haveLast &&
492 (pt->x == dinfo->endPt.x) && (pt->y == dinfo->endPt.y))
493 startPts[i] += deltas[i];
494 else /* not contiguous; restart dash pattern */
495 {
496 dinfo->dashNum = dinfo->dashNumInit;
497 dinfo->dashIndex = dinfo->dashIndexInit;
498 dinfo->dashOffset = dinfo->dashOffsetInit;
499 }
500 if (!dinfo->skipStart && (info.startAngle != info.endAngle))
501 {
502 dinfo->startPt = *pt;
503 dinfo->haveStart = true;
504 }
505 else if (!dinfo->skipLast && dinfo->haveStart &&
506 (lastPt->x == dinfo->startPt.x) &&
507 (lastPt->y == dinfo->startPt.y) &&
508 (lastPt != startPts[i]))
509 endPts[j] = lastPt;
510 if (info.startAngle != info.endAngle)
511 {
512 dinfo->haveLast = true;
513 dinfo->endPt = *lastPt;
514 }
515
516 /* iterate through generated points, updating dash information (e.g.,
517 dashNum and paint type), writing points in paint type `i' into
518 pre-allocated array pts[i] */
519
520 dashRemaining = (int)pGC->dash[dinfo->dashIndex] - dinfo->dashOffset;
521 numPixels = pGC->numPixels;
522 for (i = 0; i < 5; i++)
523 {
524 int delta;
525
526 pt = startPts[i];
527 lastPt = endPts[i];
528 delta = deltas[i];
529 while (pt != lastPt)
530 {
531 int dashNum, paintType;
532
533 /* use a paint type that cycles through 1..(numPixels-1) for
534 even-numbered dashes, and is 0 for odd-numbered ones */
535 dashNum = dinfo->dashNum;
536 paintType = (dashNum & 1) ? 0 : 1 + ((dashNum / 2) % (numPixels-1));
537 while ((pt != lastPt) && --dashRemaining >= 0)
538 {
539 *(pts[paintType]++) = *pt;
540 pt += delta;
541 }
542
543 if (dashRemaining <= 0)
544 /* on to next dash */
545 {
546 ++(dinfo->dashNum);
547 if (++(dinfo->dashIndex) == pGC->numInDashList)
548 /* loop to beginning of dash array */
549 dinfo->dashIndex = 0;
550 dashRemaining = (int)pGC->dash[dinfo->dashIndex];
551 }
552 }
553 }
554
555 /* pass back amount left in now-current dash, so that dash pattern will
556 continue from arc to contiguous arc */
557 dinfo->dashOffset = (int)pGC->dash[dinfo->dashIndex] - dashRemaining;
558
559 /* free temp storage */
560 free (points);
561 }
562
563
564 /*
565 * (x - l)^2 / (W/2)^2 + (y + H/2)^2 / (H/2)^2 = 1
566 *
567 * where l is either 0 or .5
568 *
569 * alpha = 4(W^2)
570 * beta = 4(H^2)
571 * gamma = 0
572 * u = 2(W^2)H
573 * v = 4(H^2)l
574 * k = -4(H^2)(l^2)
575 *
576 */
577
578 /* Helper function called by ZeroArcPts() and ZeroArcDashPts() above.
579 Generates a miZeroArc struct for any specified arc. */
580
581 static bool
miZeroArcSetup(const miArc * arc,miZeroArc * info,bool ok360)582 miZeroArcSetup (const miArc *arc, miZeroArc *info, bool ok360)
583 {
584 int l, i;
585 int angle1, angle2;
586 int startseg, endseg;
587 int startAngle, endAngle;
588 miZeroArcPt start, end;
589 bool overlap;
590
591 l = arc->width & 1;
592 if (arc->width == arc->height) /* circular arc */
593 {
594 info->alpha = 4;
595 info->beta = 4;
596 info->k1 = -8;
597 info->k3 = -16;
598 info->b = 12;
599 info->a = (arc->width << 2) - 12;
600 info->d = 17 - (arc->width << 1);
601 if (l)
602 {
603 info->b -= 4;
604 info->a += 4;
605 info->d -= 7;
606 }
607 }
608 else if (arc->width == 0 || arc->height == 0) /* degenerate arc */
609 {
610 info->alpha = 0;
611 info->beta = 0;
612 info->k1 = 0;
613 info->k3 = 0;
614 info->a = -(int)arc->height;
615 info->b = 0;
616 info->d = -1;
617 }
618 else /* non-degenerate non-circular arc */
619 {
620 /* initial conditions */
621 info->alpha = (arc->width * arc->width) << 2;
622 info->beta = (arc->height * arc->height) << 2;
623 info->k1 = info->beta << 1;
624 info->k3 = info->k1 + (info->alpha << 1);
625 info->b = l ? 0 : -info->beta;
626 info->a = info->alpha * arc->height;
627 info->d = info->b - (info->a >> 1) - (info->alpha >> 2);
628 if (l)
629 info->d -= info->beta >> 2;
630 info->a -= info->b;
631 /* take first step, d < 0 always */
632 info->b -= info->k1;
633 info->a += info->k1;
634 info->d += info->b;
635 /* octant change, b < 0 always */
636 info->k1 = -info->k1;
637 info->k3 = -info->k3;
638 info->b = -info->b;
639 info->d = info->b - info->a - info->d;
640 info->a = info->a - (info->b << 1);
641 }
642
643 info->dx = 1;
644 info->dy = 0;
645 info->w = (arc->width + 1) >> 1;
646 info->h = arc->height >> 1;
647 info->xorg = arc->x + (arc->width >> 1);
648 info->yorg = arc->y;
649 info->xorgo = info->xorg + l;
650 info->yorgo = info->yorg + arc->height;
651 if (arc->width == 0)
652 {
653 if (arc->height == 0)
654 {
655 info->x = 0;
656 info->y = 0;
657 info->initialMask = 0;
658 info->startAngle = 0;
659 info->endAngle = 0;
660 info->start = _oob_arc_pt;
661 info->end = _oob_arc_pt;
662 return false;
663 }
664 info->x = 0;
665 info->y = 1;
666 }
667 else
668 {
669 info->x = 1;
670 info->y = 0;
671 }
672
673 angle1 = arc->angle1;
674 angle2 = arc->angle2;
675 if ((angle1 == 0) && (angle2 >= FULLCIRCLE))
676 {
677 startAngle = 0;
678 endAngle = 0;
679 }
680 else
681 {
682 if (angle2 > FULLCIRCLE)
683 angle2 = FULLCIRCLE;
684 else if (angle2 < -FULLCIRCLE)
685 angle2 = -FULLCIRCLE;
686 if (angle2 < 0)
687 {
688 startAngle = angle1 + angle2;
689 endAngle = angle1;
690 }
691 else
692 {
693 startAngle = angle1;
694 endAngle = angle1 + angle2;
695 }
696 if (startAngle < 0)
697 startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
698 if (startAngle >= FULLCIRCLE)
699 startAngle = startAngle % FULLCIRCLE;
700 if (endAngle < 0)
701 endAngle = FULLCIRCLE - (-endAngle) % FULLCIRCLE;
702 if (endAngle >= FULLCIRCLE)
703 endAngle = endAngle % FULLCIRCLE;
704 }
705
706 info->startAngle = startAngle;
707 info->endAngle = endAngle;
708 if (ok360 && (startAngle == endAngle) && arc->angle2
709 && arc->width && arc->height)
710 {
711 info->initialMask = 0xf;
712 info->start = _oob_arc_pt;
713 info->end = _oob_arc_pt;
714 return true;
715 }
716 startseg = startAngle / OCTANT;
717 if (!arc->height || (((startseg + 1) & 2) && arc->width))
718 {
719 start.x = (int)(Dcos(startAngle) * ((arc->width + 1) / 2.0));
720 if (start.x < 0)
721 start.x = -start.x;
722 start.y = -1;
723 }
724 else
725 {
726 start.y = (int)(Dsin(startAngle) * (arc->height / 2.0));
727 if (start.y < 0)
728 start.y = -start.y;
729 start.y = info->h - start.y;
730 start.x = INT_MAX;
731 }
732 endseg = endAngle / OCTANT;
733 if (!arc->height || (((endseg + 1) & 2) && arc->width))
734 {
735 end.x = (int)(Dcos(endAngle) * ((arc->width + 1) / 2.0));
736 if (end.x < 0)
737 end.x = -end.x;
738 end.y = -1;
739 }
740 else
741 {
742 end.y = (int)(Dsin(endAngle) * (arc->height / 2.0));
743 if (end.y < 0)
744 end.y = -end.y;
745 end.y = info->h - end.y;
746 end.x = INT_MAX;
747 }
748 info->firstx = start.x;
749 info->firsty = start.y;
750 info->initialMask = 0;
751 overlap = ((arc->angle2 != 0) && (endAngle <= startAngle)) ? true : false;
752 for (i = 0; i < 4; i++)
753 {
754 if (overlap ?
755 ((i * QUADRANT <= endAngle) || ((i + 1) * QUADRANT > startAngle)) :
756 ((i * QUADRANT <= endAngle) && ((i + 1) * QUADRANT > startAngle)))
757 info->initialMask |= (1 << i);
758 }
759 start.mask = info->initialMask;
760 end.mask = info->initialMask;
761 startseg >>= 1;
762 endseg >>= 1;
763 overlap = (overlap && (endseg == startseg)) ? true : false;
764 if (start.x != end.x || start.y != end.y || !overlap)
765 {
766 if (startseg & 1)
767 {
768 if (!overlap)
769 info->initialMask &= ~(1 << startseg);
770 if (start.x > end.x || start.y > end.y)
771 end.mask &= ~(1 << startseg);
772 }
773 else
774 {
775 start.mask &= ~(1 << startseg);
776 if (((start.x < end.x || start.y < end.y) ||
777 (start.x == end.x && start.y == end.y && (endseg & 1))) &&
778 !overlap)
779 end.mask &= ~(1 << startseg);
780 }
781 if (endseg & 1)
782 {
783 end.mask &= ~(1 << endseg);
784 if (((start.x > end.x || start.y > end.y) ||
785 (start.x == end.x && start.y == end.y && !(startseg & 1))) &&
786 !overlap)
787 start.mask &= ~(1 << endseg);
788 }
789 else
790 {
791 if (!overlap)
792 info->initialMask &= ~(1 << endseg);
793 if (start.x < end.x || start.y < end.y)
794 start.mask &= ~(1 << endseg);
795 }
796 }
797 /* take care of case when start and stop are both near 45 */
798 /* handle here rather than adding extra code to pixelization loops */
799 if (startAngle &&
800 ((start.y < 0 && end.y >= 0) || (start.y >= 0 && end.y < 0)))
801 {
802 i = (startAngle + OCTANT) % OCTANT;
803 if (i < EPSILON45 || i > OCTANT - EPSILON45)
804 {
805 i = (endAngle + OCTANT) % OCTANT;
806 if (i < EPSILON45 || i > OCTANT - EPSILON45)
807 {
808 if (start.y < 0)
809 {
810 i = (int)(Dsin(startAngle) * (arc->height / 2.0));
811 if (i < 0)
812 i = -i;
813 if ((int)info->h - i == end.y)
814 start.mask = end.mask;
815 }
816 else
817 {
818 i = (int)(Dsin(endAngle) * (arc->height / 2.0));
819 if (i < 0)
820 i = -i;
821 if ((int)info->h - i == start.y)
822 end.mask = start.mask;
823 }
824 }
825 }
826 }
827 if (startseg & 1)
828 {
829 info->start = start;
830 info->end = _oob_arc_pt;
831 }
832 else
833 {
834 info->end = start;
835 info->start = _oob_arc_pt;
836 }
837 if (endseg & 1)
838 {
839 info->altend = end;
840 if (info->altend.x < info->end.x || info->altend.y < info->end.y)
841 {
842 miZeroArcPt tmp;
843 tmp = info->altend;
844 info->altend = info->end;
845 info->end = tmp;
846 }
847 info->altstart = _oob_arc_pt;
848 }
849 else
850 {
851 info->altstart = end;
852 if (info->altstart.x < info->start.x ||
853 info->altstart.y < info->start.y)
854 {
855 miZeroArcPt tmp;
856 tmp = info->altstart;
857 info->altstart = info->start;
858 info->start = tmp;
859 }
860 info->altend = _oob_arc_pt;
861 }
862 if (!info->start.x || !info->start.y)
863 {
864 info->initialMask = info->start.mask;
865 info->start = info->altstart;
866 }
867 if (!arc->width && (arc->height == 1))
868 {
869 /* kludge! */
870 info->initialMask |= info->end.mask;
871 info->initialMask |= info->initialMask << 1;
872 info->end.x = 0;
873 info->end.mask = 0;
874 }
875 return false;
876 }
877