1 /*
2
3 Copyright 1988, 1998 The Open Group
4
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
9 documentation.
10
11 The above copyright notice and this permission notice shall be included
12 in all copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17 IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
18 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 OTHER DEALINGS IN THE SOFTWARE.
21
22 Except as contained in this notice, the name of The Open Group shall
23 not be used in advertising or otherwise to promote the sale, use or
24 other dealings in this Software without prior written authorization
25 from The Open Group.
26
27 Copyright 1989 by Digital Equipment Corporation, Maynard, Massachusetts.
28
29 All Rights Reserved
30
31 Permission to use, copy, modify, and distribute this software and its
32 documentation for any purpose and without fee is hereby granted,
33 provided that the above copyright notice appear in all copies and that
34 both that copyright notice and this permission notice appear in
35 supporting documentation, and that the name of Digital not be
36 used in advertising or publicity pertaining to distribution of the
37 software without specific, written prior permission.
38
39 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
40 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
41 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
42 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
43 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
44 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
45 SOFTWARE.
46 */
47
48 /* Author: Keith Packard, MIT X Consortium */
49
50 /*
51 * Mostly integer wideline code. Uses a technique similar to
52 * bresenham zero-width lines, except walks an X edge
53 */
54
55 #ifdef HAVE_DIX_CONFIG_H
56 #include <dix-config.h>
57 #endif
58
59 #include <stdio.h>
60 #ifdef _XOPEN_SOURCE
61 #include <math.h>
62 #else
63 #define _XOPEN_SOURCE /* to get prototype for hypot on some systems */
64 #include <math.h>
65 #undef _XOPEN_SOURCE
66 #endif
67 #include <X11/X.h>
68 #include "windowstr.h"
69 #include "gcstruct.h"
70 #include "regionstr.h"
71 #include "miwideline.h"
72 #include "mi.h"
73
74 #if 0
75 #ifdef HAVE_DIX_CONFIG_H
76 #include <dix-config.h>
77 #endif
78
79 #include "misc.h"
80 #include "pixmapstr.h"
81 #include "gcstruct.h"
82 #endif
83
84 typedef struct {
85 int count; /* number of spans */
86 DDXPointPtr points; /* pointer to list of start points */
87 int *widths; /* pointer to list of widths */
88 } Spans;
89
90 typedef struct {
91 int size; /* Total number of *Spans allocated */
92 int count; /* Number of *Spans actually in group */
93 Spans *group; /* List of Spans */
94 int ymin, ymax; /* Min, max y values encountered */
95 } SpanGroup;
96
97 /* Rops which must use span groups */
98 #define miSpansCarefulRop(rop) (((rop) & 0xc) == 0x8 || ((rop) & 0x3) == 0x2)
99 #define miSpansEasyRop(rop) (!miSpansCarefulRop(rop))
100
101 /*
102
103 These routines maintain lists of Spans, in order to implement the
104 ``touch-each-pixel-once'' rules of wide lines and arcs.
105
106 Written by Joel McCormack, Summer 1989.
107
108 */
109
110 static void
miInitSpanGroup(SpanGroup * spanGroup)111 miInitSpanGroup(SpanGroup * spanGroup)
112 {
113 spanGroup->size = 0;
114 spanGroup->count = 0;
115 spanGroup->group = NULL;
116 spanGroup->ymin = MAXSHORT;
117 spanGroup->ymax = MINSHORT;
118 } /* InitSpanGroup */
119
120 #define YMIN(spans) (spans->points[0].y)
121 #define YMAX(spans) (spans->points[spans->count-1].y)
122
123 static void
miSubtractSpans(SpanGroup * spanGroup,Spans * sub)124 miSubtractSpans(SpanGroup * spanGroup, Spans * sub)
125 {
126 int i, subCount, spansCount;
127 int ymin, ymax, xmin, xmax;
128 Spans *spans;
129 DDXPointPtr subPt, spansPt;
130 int *subWid, *spansWid;
131 int extra;
132
133 ymin = YMIN(sub);
134 ymax = YMAX(sub);
135 spans = spanGroup->group;
136 for (i = spanGroup->count; i; i--, spans++) {
137 if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
138 subCount = sub->count;
139 subPt = sub->points;
140 subWid = sub->widths;
141 spansCount = spans->count;
142 spansPt = spans->points;
143 spansWid = spans->widths;
144 extra = 0;
145 for (;;) {
146 while (spansCount && spansPt->y < subPt->y) {
147 spansPt++;
148 spansWid++;
149 spansCount--;
150 }
151 if (!spansCount)
152 break;
153 while (subCount && subPt->y < spansPt->y) {
154 subPt++;
155 subWid++;
156 subCount--;
157 }
158 if (!subCount)
159 break;
160 if (subPt->y == spansPt->y) {
161 xmin = subPt->x;
162 xmax = xmin + *subWid;
163 if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax) {
164 ;
165 }
166 else if (xmin <= spansPt->x) {
167 if (xmax >= spansPt->x + *spansWid) {
168 memmove(spansPt, spansPt + 1,
169 sizeof *spansPt * (spansCount - 1));
170 memmove(spansWid, spansWid + 1,
171 sizeof *spansWid * (spansCount - 1));
172 spansPt--;
173 spansWid--;
174 spans->count--;
175 extra++;
176 }
177 else {
178 *spansWid = *spansWid - (xmax - spansPt->x);
179 spansPt->x = xmax;
180 }
181 }
182 else {
183 if (xmax >= spansPt->x + *spansWid) {
184 *spansWid = xmin - spansPt->x;
185 }
186 else {
187 if (!extra) {
188 DDXPointPtr newPt;
189 int *newwid;
190
191 #define EXTRA 8
192 newPt = reallocarray(spans->points,
193 spans->count + EXTRA,
194 sizeof(DDXPointRec));
195 if (!newPt)
196 break;
197 spansPt = newPt + (spansPt - spans->points);
198 spans->points = newPt;
199 newwid = reallocarray(spans->widths,
200 spans->count + EXTRA,
201 sizeof(int));
202 if (!newwid)
203 break;
204 spansWid = newwid + (spansWid - spans->widths);
205 spans->widths = newwid;
206 extra = EXTRA;
207 }
208 memmove(spansPt + 1, spansPt,
209 sizeof *spansPt * (spansCount));
210 memmove(spansWid + 1, spansWid,
211 sizeof *spansWid * (spansCount));
212 spans->count++;
213 extra--;
214 *spansWid = xmin - spansPt->x;
215 spansWid++;
216 spansPt++;
217 *spansWid = *spansWid - (xmax - spansPt->x);
218 spansPt->x = xmax;
219 }
220 }
221 }
222 spansPt++;
223 spansWid++;
224 spansCount--;
225 }
226 }
227 }
228 }
229
230 static void
miAppendSpans(SpanGroup * spanGroup,SpanGroup * otherGroup,Spans * spans)231 miAppendSpans(SpanGroup * spanGroup, SpanGroup * otherGroup, Spans * spans)
232 {
233 int ymin, ymax;
234 int spansCount;
235
236 spansCount = spans->count;
237 if (spansCount > 0) {
238 if (spanGroup->size == spanGroup->count) {
239 spanGroup->size = (spanGroup->size + 8) * 2;
240 spanGroup->group =
241 reallocarray(spanGroup->group, sizeof(Spans), spanGroup->size);
242 }
243
244 spanGroup->group[spanGroup->count] = *spans;
245 (spanGroup->count)++;
246 ymin = spans->points[0].y;
247 if (ymin < spanGroup->ymin)
248 spanGroup->ymin = ymin;
249 ymax = spans->points[spansCount - 1].y;
250 if (ymax > spanGroup->ymax)
251 spanGroup->ymax = ymax;
252 if (otherGroup && otherGroup->ymin < ymax && ymin < otherGroup->ymax) {
253 miSubtractSpans(otherGroup, spans);
254 }
255 }
256 else {
257 free(spans->points);
258 free(spans->widths);
259 }
260 } /* AppendSpans */
261
262 static void
miFreeSpanGroup(SpanGroup * spanGroup)263 miFreeSpanGroup(SpanGroup * spanGroup)
264 {
265 free(spanGroup->group);
266 }
267
268 static void
QuickSortSpansX(DDXPointRec points[],int widths[],int numSpans)269 QuickSortSpansX(DDXPointRec points[], int widths[], int numSpans)
270 {
271 int x;
272 int i, j, m;
273 DDXPointPtr r;
274
275 /* Always called with numSpans > 1 */
276 /* Sorts only by x, as all y should be the same */
277
278 #define ExchangeSpans(a, b) \
279 { \
280 DDXPointRec tpt; \
281 int tw; \
282 \
283 tpt = points[a]; points[a] = points[b]; points[b] = tpt; \
284 tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
285 }
286
287 do {
288 if (numSpans < 9) {
289 /* Do insertion sort */
290 int xprev;
291
292 xprev = points[0].x;
293 i = 1;
294 do { /* while i != numSpans */
295 x = points[i].x;
296 if (xprev > x) {
297 /* points[i] is out of order. Move into proper location. */
298 DDXPointRec tpt;
299 int tw, k;
300
301 for (j = 0; x >= points[j].x; j++) {
302 }
303 tpt = points[i];
304 tw = widths[i];
305 for (k = i; k != j; k--) {
306 points[k] = points[k - 1];
307 widths[k] = widths[k - 1];
308 }
309 points[j] = tpt;
310 widths[j] = tw;
311 x = points[i].x;
312 } /* if out of order */
313 xprev = x;
314 i++;
315 } while (i != numSpans);
316 return;
317 }
318
319 /* Choose partition element, stick in location 0 */
320 m = numSpans / 2;
321 if (points[m].x > points[0].x)
322 ExchangeSpans(m, 0);
323 if (points[m].x > points[numSpans - 1].x)
324 ExchangeSpans(m, numSpans - 1);
325 if (points[m].x > points[0].x)
326 ExchangeSpans(m, 0);
327 x = points[0].x;
328
329 /* Partition array */
330 i = 0;
331 j = numSpans;
332 do {
333 r = &(points[i]);
334 do {
335 r++;
336 i++;
337 } while (i != numSpans && r->x < x);
338 r = &(points[j]);
339 do {
340 r--;
341 j--;
342 } while (x < r->x);
343 if (i < j)
344 ExchangeSpans(i, j);
345 } while (i < j);
346
347 /* Move partition element back to middle */
348 ExchangeSpans(0, j);
349
350 /* Recurse */
351 if (numSpans - j - 1 > 1)
352 QuickSortSpansX(&points[j + 1], &widths[j + 1], numSpans - j - 1);
353 numSpans = j;
354 } while (numSpans > 1);
355 } /* QuickSortSpans */
356
357 static int
UniquifySpansX(Spans * spans,DDXPointRec * newPoints,int * newWidths)358 UniquifySpansX(Spans * spans, DDXPointRec * newPoints, int *newWidths)
359 {
360 int newx1, newx2, oldpt, i, y;
361 DDXPointRec *oldPoints;
362 int *oldWidths;
363 int *startNewWidths;
364
365 /* Always called with numSpans > 1 */
366 /* Uniquify the spans, and stash them into newPoints and newWidths. Return the
367 number of unique spans. */
368
369 startNewWidths = newWidths;
370
371 oldPoints = spans->points;
372 oldWidths = spans->widths;
373
374 y = oldPoints->y;
375 newx1 = oldPoints->x;
376 newx2 = newx1 + *oldWidths;
377
378 for (i = spans->count - 1; i != 0; i--) {
379 oldPoints++;
380 oldWidths++;
381 oldpt = oldPoints->x;
382 if (oldpt > newx2) {
383 /* Write current span, start a new one */
384 newPoints->x = newx1;
385 newPoints->y = y;
386 *newWidths = newx2 - newx1;
387 newPoints++;
388 newWidths++;
389 newx1 = oldpt;
390 newx2 = oldpt + *oldWidths;
391 }
392 else {
393 /* extend current span, if old extends beyond new */
394 oldpt = oldpt + *oldWidths;
395 if (oldpt > newx2)
396 newx2 = oldpt;
397 }
398 } /* for */
399
400 /* Write final span */
401 newPoints->x = newx1;
402 *newWidths = newx2 - newx1;
403 newPoints->y = y;
404
405 return (newWidths - startNewWidths) + 1;
406 } /* UniquifySpansX */
407
408 static void
miDisposeSpanGroup(SpanGroup * spanGroup)409 miDisposeSpanGroup(SpanGroup * spanGroup)
410 {
411 int i;
412 Spans *spans;
413
414 for (i = 0; i < spanGroup->count; i++) {
415 spans = spanGroup->group + i;
416 free(spans->points);
417 free(spans->widths);
418 }
419 }
420
421 static void
miFillUniqueSpanGroup(DrawablePtr pDraw,GCPtr pGC,SpanGroup * spanGroup)422 miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup * spanGroup)
423 {
424 int i;
425 Spans *spans;
426 Spans *yspans;
427 int *ysizes;
428 int ymin, ylength;
429
430 /* Outgoing spans for one big call to FillSpans */
431 DDXPointPtr points;
432 int *widths;
433 int count;
434
435 if (spanGroup->count == 0)
436 return;
437
438 if (spanGroup->count == 1) {
439 /* Already should be sorted, unique */
440 spans = spanGroup->group;
441 (*pGC->ops->FillSpans)
442 (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
443 free(spans->points);
444 free(spans->widths);
445 }
446 else {
447 /* Yuck. Gross. Radix sort into y buckets, then sort x and uniquify */
448 /* This seems to be the fastest thing to do. I've tried sorting on
449 both x and y at the same time rather than creating into all those
450 y buckets, but it was somewhat slower. */
451
452 ymin = spanGroup->ymin;
453 ylength = spanGroup->ymax - ymin + 1;
454
455 /* Allocate Spans for y buckets */
456 yspans = xallocarray(ylength, sizeof(Spans));
457 ysizes = xallocarray(ylength, sizeof(int));
458
459 if (!yspans || !ysizes) {
460 free(yspans);
461 free(ysizes);
462 miDisposeSpanGroup(spanGroup);
463 return;
464 }
465
466 for (i = 0; i != ylength; i++) {
467 ysizes[i] = 0;
468 yspans[i].count = 0;
469 yspans[i].points = NULL;
470 yspans[i].widths = NULL;
471 }
472
473 /* Go through every single span and put it into the correct bucket */
474 count = 0;
475 for (i = 0, spans = spanGroup->group;
476 i != spanGroup->count; i++, spans++) {
477 int index;
478 int j;
479
480 for (j = 0, points = spans->points, widths = spans->widths;
481 j != spans->count; j++, points++, widths++) {
482 index = points->y - ymin;
483 if (index >= 0 && index < ylength) {
484 Spans *newspans = &(yspans[index]);
485
486 if (newspans->count == ysizes[index]) {
487 DDXPointPtr newpoints;
488 int *newwidths;
489
490 ysizes[index] = (ysizes[index] + 8) * 2;
491 newpoints = reallocarray(newspans->points,
492 ysizes[index],
493 sizeof(DDXPointRec));
494 newwidths = reallocarray(newspans->widths,
495 ysizes[index], sizeof(int));
496 if (!newpoints || !newwidths) {
497 for (i = 0; i < ylength; i++) {
498 free(yspans[i].points);
499 free(yspans[i].widths);
500 }
501 free(yspans);
502 free(ysizes);
503 free(newpoints);
504 free(newwidths);
505 miDisposeSpanGroup(spanGroup);
506 return;
507 }
508 newspans->points = newpoints;
509 newspans->widths = newwidths;
510 }
511 newspans->points[newspans->count] = *points;
512 newspans->widths[newspans->count] = *widths;
513 (newspans->count)++;
514 } /* if y value of span in range */
515 } /* for j through spans */
516 count += spans->count;
517 free(spans->points);
518 spans->points = NULL;
519 free(spans->widths);
520 spans->widths = NULL;
521 } /* for i thorough Spans */
522
523 /* Now sort by x and uniquify each bucket into the final array */
524 points = xallocarray(count, sizeof(DDXPointRec));
525 widths = xallocarray(count, sizeof(int));
526 if (!points || !widths) {
527 for (i = 0; i < ylength; i++) {
528 free(yspans[i].points);
529 free(yspans[i].widths);
530 }
531 free(yspans);
532 free(ysizes);
533 free(points);
534 free(widths);
535 return;
536 }
537 count = 0;
538 for (i = 0; i != ylength; i++) {
539 int ycount = yspans[i].count;
540
541 if (ycount > 0) {
542 if (ycount > 1) {
543 QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
544 count += UniquifySpansX
545 (&(yspans[i]), &(points[count]), &(widths[count]));
546 }
547 else {
548 points[count] = yspans[i].points[0];
549 widths[count] = yspans[i].widths[0];
550 count++;
551 }
552 free(yspans[i].points);
553 free(yspans[i].widths);
554 }
555 }
556
557 (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
558 free(points);
559 free(widths);
560 free(yspans);
561 free(ysizes); /* use (DE)xalloc for these? */
562 }
563
564 spanGroup->count = 0;
565 spanGroup->ymin = MAXSHORT;
566 spanGroup->ymax = MINSHORT;
567 }
568
569 static Bool
InitSpans(Spans * spans,size_t nspans)570 InitSpans(Spans * spans, size_t nspans)
571 {
572 spans->points = xallocarray(nspans, sizeof(*spans->points));
573 if (!spans->points)
574 return FALSE;
575 spans->widths = xallocarray(nspans, sizeof(*spans->widths));
576 if (!spans->widths) {
577 free(spans->points);
578 return FALSE;
579 }
580 return TRUE;
581 }
582
583 /*
584 * interface data to span-merging polygon filler
585 */
586
587 typedef struct _SpanData {
588 SpanGroup fgGroup, bgGroup;
589 } SpanDataRec, *SpanDataPtr;
590
591 static void
AppendSpanGroup(GCPtr pGC,unsigned long pixel,Spans * spanPtr,SpanDataPtr spanData)592 AppendSpanGroup(GCPtr pGC, unsigned long pixel, Spans * spanPtr,
593 SpanDataPtr spanData)
594 {
595 SpanGroup *group, *othergroup = NULL;
596
597 if (pixel == pGC->fgPixel) {
598 group = &spanData->fgGroup;
599 if (pGC->lineStyle == LineDoubleDash)
600 othergroup = &spanData->bgGroup;
601 }
602 else {
603 group = &spanData->bgGroup;
604 othergroup = &spanData->fgGroup;
605 }
606 miAppendSpans(group, othergroup, spanPtr);
607 }
608
609 static void miLineArc(DrawablePtr pDraw, GCPtr pGC,
610 unsigned long pixel, SpanDataPtr spanData,
611 LineFacePtr leftFace,
612 LineFacePtr rightFace,
613 double xorg, double yorg, Bool isInt);
614
615 /*
616 * spans-based polygon filler
617 */
618
619 static void
fillSpans(DrawablePtr pDrawable,GCPtr pGC,unsigned long pixel,Spans * spans,SpanDataPtr spanData)620 fillSpans(DrawablePtr pDrawable, GCPtr pGC, unsigned long pixel, Spans * spans,
621 SpanDataPtr spanData)
622 {
623 if (!spanData) {
624 ChangeGCVal oldPixel, tmpPixel;
625
626 oldPixel.val = pGC->fgPixel;
627 if (pixel != oldPixel.val) {
628 tmpPixel.val = (XID) pixel;
629 ChangeGC(NullClient, pGC, GCForeground, &tmpPixel);
630 ValidateGC(pDrawable, pGC);
631 }
632 (*pGC->ops->FillSpans) (pDrawable, pGC, spans->count, spans->points,
633 spans->widths, TRUE);
634 free(spans->widths);
635 free(spans->points);
636 if (pixel != oldPixel.val) {
637 ChangeGC(NullClient, pGC, GCForeground, &oldPixel);
638 ValidateGC(pDrawable, pGC);
639 }
640 }
641 else
642 AppendSpanGroup(pGC, pixel, spans, spanData);
643 }
644
645 static void
miFillPolyHelper(DrawablePtr pDrawable,GCPtr pGC,unsigned long pixel,SpanDataPtr spanData,int y,int overall_height,PolyEdgePtr left,PolyEdgePtr right,int left_count,int right_count)646 miFillPolyHelper(DrawablePtr pDrawable, GCPtr pGC, unsigned long pixel,
647 SpanDataPtr spanData, int y, int overall_height,
648 PolyEdgePtr left, PolyEdgePtr right,
649 int left_count, int right_count)
650 {
651 int left_x = 0, left_e = 0;
652 int left_stepx = 0;
653 int left_signdx = 0;
654 int left_dy = 0, left_dx = 0;
655
656 int right_x = 0, right_e = 0;
657 int right_stepx = 0;
658 int right_signdx = 0;
659 int right_dy = 0, right_dx = 0;
660
661 int height = 0;
662 int left_height = 0, right_height = 0;
663
664 DDXPointPtr ppt;
665 int *pwidth;
666 int xorg;
667 Spans spanRec;
668
669 if (!InitSpans(&spanRec, overall_height))
670 return;
671 ppt = spanRec.points;
672 pwidth = spanRec.widths;
673
674 xorg = 0;
675 if (pGC->miTranslate) {
676 y += pDrawable->y;
677 xorg = pDrawable->x;
678 }
679 while ((left_count || left_height) && (right_count || right_height)) {
680 if (!left_height && left_count) {
681 left_height = left->height;
682 left_x = left->x;
683 left_stepx = left->stepx;
684 left_signdx = left->signdx;
685 left_e = left->e;
686 left_dy = left->dy;
687 left_dx = left->dx;
688 --left_count;
689 ++left;
690 }
691
692 if (!right_height && right_count) {
693 right_height = right->height;
694 right_x = right->x;
695 right_stepx = right->stepx;
696 right_signdx = right->signdx;
697 right_e = right->e;
698 right_dy = right->dy;
699 right_dx = right->dx;
700 --right_count;
701 ++right;
702 }
703
704 height = left_height;
705 if (height > right_height)
706 height = right_height;
707
708 left_height -= height;
709 right_height -= height;
710
711 while (--height >= 0) {
712 if (right_x >= left_x) {
713 ppt->y = y;
714 ppt->x = left_x + xorg;
715 ppt++;
716 *pwidth++ = right_x - left_x + 1;
717 }
718 y++;
719
720 left_x += left_stepx;
721 left_e += left_dx;
722 if (left_e > 0) {
723 left_x += left_signdx;
724 left_e -= left_dy;
725 }
726
727 right_x += right_stepx;
728 right_e += right_dx;
729 if (right_e > 0) {
730 right_x += right_signdx;
731 right_e -= right_dy;
732 }
733 }
734 }
735 spanRec.count = ppt - spanRec.points;
736 fillSpans(pDrawable, pGC, pixel, &spanRec, spanData);
737 }
738
739 static void
miFillRectPolyHelper(DrawablePtr pDrawable,GCPtr pGC,unsigned long pixel,SpanDataPtr spanData,int x,int y,int w,int h)740 miFillRectPolyHelper(DrawablePtr pDrawable,
741 GCPtr pGC,
742 unsigned long pixel,
743 SpanDataPtr spanData, int x, int y, int w, int h)
744 {
745 DDXPointPtr ppt;
746 int *pwidth;
747 ChangeGCVal oldPixel, tmpPixel;
748 Spans spanRec;
749 xRectangle rect;
750
751 if (!spanData) {
752 rect.x = x;
753 rect.y = y;
754 rect.width = w;
755 rect.height = h;
756 oldPixel.val = pGC->fgPixel;
757 if (pixel != oldPixel.val) {
758 tmpPixel.val = (XID) pixel;
759 ChangeGC(NullClient, pGC, GCForeground, &tmpPixel);
760 ValidateGC(pDrawable, pGC);
761 }
762 (*pGC->ops->PolyFillRect) (pDrawable, pGC, 1, &rect);
763 if (pixel != oldPixel.val) {
764 ChangeGC(NullClient, pGC, GCForeground, &oldPixel);
765 ValidateGC(pDrawable, pGC);
766 }
767 }
768 else {
769 if (!InitSpans(&spanRec, h))
770 return;
771 ppt = spanRec.points;
772 pwidth = spanRec.widths;
773
774 if (pGC->miTranslate) {
775 y += pDrawable->y;
776 x += pDrawable->x;
777 }
778 while (h--) {
779 ppt->x = x;
780 ppt->y = y;
781 ppt++;
782 *pwidth++ = w;
783 y++;
784 }
785 spanRec.count = ppt - spanRec.points;
786 AppendSpanGroup(pGC, pixel, &spanRec, spanData);
787 }
788 }
789
790 static int
miPolyBuildEdge(double x0,double y0,double k,int dx,int dy,int xi,int yi,int left,PolyEdgePtr edge)791 miPolyBuildEdge(double x0, double y0, double k, /* x0 * dy - y0 * dx */
792 int dx, int dy, int xi, int yi, int left, PolyEdgePtr edge)
793 {
794 int x, y, e;
795 int xady;
796
797 if (dy < 0) {
798 dy = -dy;
799 dx = -dx;
800 k = -k;
801 }
802
803 #ifdef NOTDEF
804 {
805 double realk, kerror;
806
807 realk = x0 * dy - y0 * dx;
808 kerror = fabs(realk - k);
809 if (kerror > .1)
810 printf("realk: %g k: %g\n", realk, k);
811 }
812 #endif
813 y = ICEIL(y0);
814 xady = ICEIL(k) + y * dx;
815
816 if (xady <= 0)
817 x = -(-xady / dy) - 1;
818 else
819 x = (xady - 1) / dy;
820
821 e = xady - x * dy;
822
823 if (dx >= 0) {
824 edge->signdx = 1;
825 edge->stepx = dx / dy;
826 edge->dx = dx % dy;
827 }
828 else {
829 edge->signdx = -1;
830 edge->stepx = -(-dx / dy);
831 edge->dx = -dx % dy;
832 e = dy - e + 1;
833 }
834 edge->dy = dy;
835 edge->x = x + left + xi;
836 edge->e = e - dy; /* bias to compare against 0 instead of dy */
837 return y + yi;
838 }
839
840 #define StepAround(v, incr, max) (((v) + (incr) < 0) ? (max - 1) : ((v) + (incr) == max) ? 0 : ((v) + (incr)))
841
842 static int
miPolyBuildPoly(PolyVertexPtr vertices,PolySlopePtr slopes,int count,int xi,int yi,PolyEdgePtr left,PolyEdgePtr right,int * pnleft,int * pnright,int * h)843 miPolyBuildPoly(PolyVertexPtr vertices,
844 PolySlopePtr slopes,
845 int count,
846 int xi,
847 int yi,
848 PolyEdgePtr left,
849 PolyEdgePtr right, int *pnleft, int *pnright, int *h)
850 {
851 int top, bottom;
852 double miny, maxy;
853 int i;
854 int j;
855 int clockwise;
856 int slopeoff;
857 int s;
858 int nright, nleft;
859 int y, lasty = 0, bottomy, topy = 0;
860
861 /* find the top of the polygon */
862 maxy = miny = vertices[0].y;
863 bottom = top = 0;
864 for (i = 1; i < count; i++) {
865 if (vertices[i].y < miny) {
866 top = i;
867 miny = vertices[i].y;
868 }
869 if (vertices[i].y >= maxy) {
870 bottom = i;
871 maxy = vertices[i].y;
872 }
873 }
874 clockwise = 1;
875 slopeoff = 0;
876
877 i = top;
878 j = StepAround(top, -1, count);
879
880 if ((int64_t) slopes[j].dy * slopes[i].dx >
881 (int64_t) slopes[i].dy * slopes[j].dx) {
882 clockwise = -1;
883 slopeoff = -1;
884 }
885
886 bottomy = ICEIL(maxy) + yi;
887
888 nright = 0;
889
890 s = StepAround(top, slopeoff, count);
891 i = top;
892 while (i != bottom) {
893 if (slopes[s].dy != 0) {
894 y = miPolyBuildEdge(vertices[i].x, vertices[i].y,
895 slopes[s].k,
896 slopes[s].dx, slopes[s].dy,
897 xi, yi, 0, &right[nright]);
898 if (nright != 0)
899 right[nright - 1].height = y - lasty;
900 else
901 topy = y;
902 nright++;
903 lasty = y;
904 }
905
906 i = StepAround(i, clockwise, count);
907 s = StepAround(s, clockwise, count);
908 }
909 if (nright != 0)
910 right[nright - 1].height = bottomy - lasty;
911
912 if (slopeoff == 0)
913 slopeoff = -1;
914 else
915 slopeoff = 0;
916
917 nleft = 0;
918 s = StepAround(top, slopeoff, count);
919 i = top;
920 while (i != bottom) {
921 if (slopes[s].dy != 0) {
922 y = miPolyBuildEdge(vertices[i].x, vertices[i].y,
923 slopes[s].k,
924 slopes[s].dx, slopes[s].dy, xi, yi, 1,
925 &left[nleft]);
926
927 if (nleft != 0)
928 left[nleft - 1].height = y - lasty;
929 nleft++;
930 lasty = y;
931 }
932 i = StepAround(i, -clockwise, count);
933 s = StepAround(s, -clockwise, count);
934 }
935 if (nleft != 0)
936 left[nleft - 1].height = bottomy - lasty;
937 *pnleft = nleft;
938 *pnright = nright;
939 *h = bottomy - topy;
940 return topy;
941 }
942
943 static void
miLineOnePoint(DrawablePtr pDrawable,GCPtr pGC,unsigned long pixel,SpanDataPtr spanData,int x,int y)944 miLineOnePoint(DrawablePtr pDrawable,
945 GCPtr pGC,
946 unsigned long pixel, SpanDataPtr spanData, int x, int y)
947 {
948 DDXPointRec pt;
949 int wid;
950 unsigned long oldPixel;
951
952 MILINESETPIXEL(pDrawable, pGC, pixel, oldPixel);
953 if (pGC->fillStyle == FillSolid) {
954 pt.x = x;
955 pt.y = y;
956 (*pGC->ops->PolyPoint) (pDrawable, pGC, CoordModeOrigin, 1, &pt);
957 }
958 else {
959 wid = 1;
960 if (pGC->miTranslate) {
961 x += pDrawable->x;
962 y += pDrawable->y;
963 }
964 pt.x = x;
965 pt.y = y;
966 (*pGC->ops->FillSpans) (pDrawable, pGC, 1, &pt, &wid, TRUE);
967 }
968 MILINERESETPIXEL(pDrawable, pGC, pixel, oldPixel);
969 }
970
971 static void
miLineJoin(DrawablePtr pDrawable,GCPtr pGC,unsigned long pixel,SpanDataPtr spanData,LineFacePtr pLeft,LineFacePtr pRight)972 miLineJoin(DrawablePtr pDrawable,
973 GCPtr pGC,
974 unsigned long pixel,
975 SpanDataPtr spanData, LineFacePtr pLeft, LineFacePtr pRight)
976 {
977 double mx = 0, my = 0;
978 double denom = 0.0;
979 PolyVertexRec vertices[4];
980 PolySlopeRec slopes[4];
981 int edgecount;
982 PolyEdgeRec left[4], right[4];
983 int nleft, nright;
984 int y, height;
985 int swapslopes;
986 int joinStyle = pGC->joinStyle;
987 int lw = pGC->lineWidth;
988
989 if (lw == 1 && !spanData) {
990 /* See if one of the lines will draw the joining pixel */
991 if (pLeft->dx > 0 || (pLeft->dx == 0 && pLeft->dy > 0))
992 return;
993 if (pRight->dx > 0 || (pRight->dx == 0 && pRight->dy > 0))
994 return;
995 if (joinStyle != JoinRound) {
996 denom =
997 -pLeft->dx * (double) pRight->dy +
998 pRight->dx * (double) pLeft->dy;
999 if (denom == 0)
1000 return; /* no join to draw */
1001 }
1002 if (joinStyle != JoinMiter) {
1003 miLineOnePoint(pDrawable, pGC, pixel, spanData, pLeft->x, pLeft->y);
1004 return;
1005 }
1006 }
1007 else {
1008 if (joinStyle == JoinRound) {
1009 miLineArc(pDrawable, pGC, pixel, spanData,
1010 pLeft, pRight, (double) 0.0, (double) 0.0, TRUE);
1011 return;
1012 }
1013 denom =
1014 -pLeft->dx * (double) pRight->dy + pRight->dx * (double) pLeft->dy;
1015 if (denom == 0.0)
1016 return; /* no join to draw */
1017 }
1018
1019 swapslopes = 0;
1020 if (denom > 0) {
1021 pLeft->xa = -pLeft->xa;
1022 pLeft->ya = -pLeft->ya;
1023 pLeft->dx = -pLeft->dx;
1024 pLeft->dy = -pLeft->dy;
1025 }
1026 else {
1027 swapslopes = 1;
1028 pRight->xa = -pRight->xa;
1029 pRight->ya = -pRight->ya;
1030 pRight->dx = -pRight->dx;
1031 pRight->dy = -pRight->dy;
1032 }
1033
1034 vertices[0].x = pRight->xa;
1035 vertices[0].y = pRight->ya;
1036 slopes[0].dx = -pRight->dy;
1037 slopes[0].dy = pRight->dx;
1038 slopes[0].k = 0;
1039
1040 vertices[1].x = 0;
1041 vertices[1].y = 0;
1042 slopes[1].dx = pLeft->dy;
1043 slopes[1].dy = -pLeft->dx;
1044 slopes[1].k = 0;
1045
1046 vertices[2].x = pLeft->xa;
1047 vertices[2].y = pLeft->ya;
1048
1049 if (joinStyle == JoinMiter) {
1050 my = (pLeft->dy * (pRight->xa * pRight->dy - pRight->ya * pRight->dx) -
1051 pRight->dy * (pLeft->xa * pLeft->dy - pLeft->ya * pLeft->dx)) /
1052 denom;
1053 if (pLeft->dy != 0) {
1054 mx = pLeft->xa + (my - pLeft->ya) *
1055 (double) pLeft->dx / (double) pLeft->dy;
1056 }
1057 else {
1058 mx = pRight->xa + (my - pRight->ya) *
1059 (double) pRight->dx / (double) pRight->dy;
1060 }
1061 /* check miter limit */
1062 if ((mx * mx + my * my) * 4 > SQSECANT * lw * lw)
1063 joinStyle = JoinBevel;
1064 }
1065
1066 if (joinStyle == JoinMiter) {
1067 slopes[2].dx = pLeft->dx;
1068 slopes[2].dy = pLeft->dy;
1069 slopes[2].k = pLeft->k;
1070 if (swapslopes) {
1071 slopes[2].dx = -slopes[2].dx;
1072 slopes[2].dy = -slopes[2].dy;
1073 slopes[2].k = -slopes[2].k;
1074 }
1075 vertices[3].x = mx;
1076 vertices[3].y = my;
1077 slopes[3].dx = pRight->dx;
1078 slopes[3].dy = pRight->dy;
1079 slopes[3].k = pRight->k;
1080 if (swapslopes) {
1081 slopes[3].dx = -slopes[3].dx;
1082 slopes[3].dy = -slopes[3].dy;
1083 slopes[3].k = -slopes[3].k;
1084 }
1085 edgecount = 4;
1086 }
1087 else {
1088 double scale, dx, dy, adx, ady;
1089
1090 adx = dx = pRight->xa - pLeft->xa;
1091 ady = dy = pRight->ya - pLeft->ya;
1092 if (adx < 0)
1093 adx = -adx;
1094 if (ady < 0)
1095 ady = -ady;
1096 scale = ady;
1097 if (adx > ady)
1098 scale = adx;
1099 slopes[2].dx = (dx * 65536) / scale;
1100 slopes[2].dy = (dy * 65536) / scale;
1101 slopes[2].k = ((pLeft->xa + pRight->xa) * slopes[2].dy -
1102 (pLeft->ya + pRight->ya) * slopes[2].dx) / 2.0;
1103 edgecount = 3;
1104 }
1105
1106 y = miPolyBuildPoly(vertices, slopes, edgecount, pLeft->x, pLeft->y,
1107 left, right, &nleft, &nright, &height);
1108 miFillPolyHelper(pDrawable, pGC, pixel, spanData, y, height, left, right,
1109 nleft, nright);
1110 }
1111
1112 static int
miLineArcI(DrawablePtr pDraw,GCPtr pGC,int xorg,int yorg,DDXPointPtr points,int * widths)1113 miLineArcI(DrawablePtr pDraw,
1114 GCPtr pGC, int xorg, int yorg, DDXPointPtr points, int *widths)
1115 {
1116 DDXPointPtr tpts, bpts;
1117 int *twids, *bwids;
1118 int x, y, e, ex, slw;
1119
1120 tpts = points;
1121 twids = widths;
1122 if (pGC->miTranslate) {
1123 xorg += pDraw->x;
1124 yorg += pDraw->y;
1125 }
1126 slw = pGC->lineWidth;
1127 if (slw == 1) {
1128 tpts->x = xorg;
1129 tpts->y = yorg;
1130 *twids = 1;
1131 return 1;
1132 }
1133 bpts = tpts + slw;
1134 bwids = twids + slw;
1135 y = (slw >> 1) + 1;
1136 if (slw & 1)
1137 e = -((y << 2) + 3);
1138 else
1139 e = -(y << 3);
1140 ex = -4;
1141 x = 0;
1142 while (y) {
1143 e += (y << 3) - 4;
1144 while (e >= 0) {
1145 x++;
1146 e += (ex = -((x << 3) + 4));
1147 }
1148 y--;
1149 slw = (x << 1) + 1;
1150 if ((e == ex) && (slw > 1))
1151 slw--;
1152 tpts->x = xorg - x;
1153 tpts->y = yorg - y;
1154 tpts++;
1155 *twids++ = slw;
1156 if ((y != 0) && ((slw > 1) || (e != ex))) {
1157 bpts--;
1158 bpts->x = xorg - x;
1159 bpts->y = yorg + y;
1160 *--bwids = slw;
1161 }
1162 }
1163 return pGC->lineWidth;
1164 }
1165
1166 #define CLIPSTEPEDGE(edgey,edge,edgeleft) \
1167 if (ybase == edgey) \
1168 { \
1169 if (edgeleft) \
1170 { \
1171 if (edge->x > xcl) \
1172 xcl = edge->x; \
1173 } \
1174 else \
1175 { \
1176 if (edge->x < xcr) \
1177 xcr = edge->x; \
1178 } \
1179 edgey++; \
1180 edge->x += edge->stepx; \
1181 edge->e += edge->dx; \
1182 if (edge->e > 0) \
1183 { \
1184 edge->x += edge->signdx; \
1185 edge->e -= edge->dy; \
1186 } \
1187 }
1188
1189 static int
miLineArcD(DrawablePtr pDraw,GCPtr pGC,double xorg,double yorg,DDXPointPtr points,int * widths,PolyEdgePtr edge1,int edgey1,Bool edgeleft1,PolyEdgePtr edge2,int edgey2,Bool edgeleft2)1190 miLineArcD(DrawablePtr pDraw,
1191 GCPtr pGC,
1192 double xorg,
1193 double yorg,
1194 DDXPointPtr points,
1195 int *widths,
1196 PolyEdgePtr edge1,
1197 int edgey1,
1198 Bool edgeleft1, PolyEdgePtr edge2, int edgey2, Bool edgeleft2)
1199 {
1200 DDXPointPtr pts;
1201 int *wids;
1202 double radius, x0, y0, el, er, yk, xlk, xrk, k;
1203 int xbase, ybase, y, boty, xl, xr, xcl, xcr;
1204 int ymin, ymax;
1205 Bool edge1IsMin, edge2IsMin;
1206 int ymin1, ymin2;
1207
1208 pts = points;
1209 wids = widths;
1210 xbase = floor(xorg);
1211 x0 = xorg - xbase;
1212 ybase = ICEIL(yorg);
1213 y0 = yorg - ybase;
1214 if (pGC->miTranslate) {
1215 xbase += pDraw->x;
1216 ybase += pDraw->y;
1217 edge1->x += pDraw->x;
1218 edge2->x += pDraw->x;
1219 edgey1 += pDraw->y;
1220 edgey2 += pDraw->y;
1221 }
1222 xlk = x0 + x0 + 1.0;
1223 xrk = x0 + x0 - 1.0;
1224 yk = y0 + y0 - 1.0;
1225 radius = ((double) pGC->lineWidth) / 2.0;
1226 y = floor(radius - y0 + 1.0);
1227 ybase -= y;
1228 ymin = ybase;
1229 ymax = 65536;
1230 edge1IsMin = FALSE;
1231 ymin1 = edgey1;
1232 if (edge1->dy >= 0) {
1233 if (!edge1->dy) {
1234 if (edgeleft1)
1235 edge1IsMin = TRUE;
1236 else
1237 ymax = edgey1;
1238 edgey1 = 65536;
1239 }
1240 else {
1241 if ((edge1->signdx < 0) == edgeleft1)
1242 edge1IsMin = TRUE;
1243 }
1244 }
1245 edge2IsMin = FALSE;
1246 ymin2 = edgey2;
1247 if (edge2->dy >= 0) {
1248 if (!edge2->dy) {
1249 if (edgeleft2)
1250 edge2IsMin = TRUE;
1251 else
1252 ymax = edgey2;
1253 edgey2 = 65536;
1254 }
1255 else {
1256 if ((edge2->signdx < 0) == edgeleft2)
1257 edge2IsMin = TRUE;
1258 }
1259 }
1260 if (edge1IsMin) {
1261 ymin = ymin1;
1262 if (edge2IsMin && ymin1 > ymin2)
1263 ymin = ymin2;
1264 }
1265 else if (edge2IsMin)
1266 ymin = ymin2;
1267 el = radius * radius - ((y + y0) * (y + y0)) - (x0 * x0);
1268 er = el + xrk;
1269 xl = 1;
1270 xr = 0;
1271 if (x0 < 0.5) {
1272 xl = 0;
1273 el -= xlk;
1274 }
1275 boty = (y0 < -0.5) ? 1 : 0;
1276 if (ybase + y - boty > ymax)
1277 boty = ymax - ybase - y;
1278 while (y > boty) {
1279 k = (y << 1) + yk;
1280 er += k;
1281 while (er > 0.0) {
1282 xr++;
1283 er += xrk - (xr << 1);
1284 }
1285 el += k;
1286 while (el >= 0.0) {
1287 xl--;
1288 el += (xl << 1) - xlk;
1289 }
1290 y--;
1291 ybase++;
1292 if (ybase < ymin)
1293 continue;
1294 xcl = xl + xbase;
1295 xcr = xr + xbase;
1296 CLIPSTEPEDGE(edgey1, edge1, edgeleft1);
1297 CLIPSTEPEDGE(edgey2, edge2, edgeleft2);
1298 if (xcr >= xcl) {
1299 pts->x = xcl;
1300 pts->y = ybase;
1301 pts++;
1302 *wids++ = xcr - xcl + 1;
1303 }
1304 }
1305 er = xrk - (xr << 1) - er;
1306 el = (xl << 1) - xlk - el;
1307 boty = floor(-y0 - radius + 1.0);
1308 if (ybase + y - boty > ymax)
1309 boty = ymax - ybase - y;
1310 while (y > boty) {
1311 k = (y << 1) + yk;
1312 er -= k;
1313 while ((er >= 0.0) && (xr >= 0)) {
1314 xr--;
1315 er += xrk - (xr << 1);
1316 }
1317 el -= k;
1318 while ((el > 0.0) && (xl <= 0)) {
1319 xl++;
1320 el += (xl << 1) - xlk;
1321 }
1322 y--;
1323 ybase++;
1324 if (ybase < ymin)
1325 continue;
1326 xcl = xl + xbase;
1327 xcr = xr + xbase;
1328 CLIPSTEPEDGE(edgey1, edge1, edgeleft1);
1329 CLIPSTEPEDGE(edgey2, edge2, edgeleft2);
1330 if (xcr >= xcl) {
1331 pts->x = xcl;
1332 pts->y = ybase;
1333 pts++;
1334 *wids++ = xcr - xcl + 1;
1335 }
1336 }
1337 return pts - points;
1338 }
1339
1340 static int
miRoundJoinFace(LineFacePtr face,PolyEdgePtr edge,Bool * leftEdge)1341 miRoundJoinFace(LineFacePtr face, PolyEdgePtr edge, Bool *leftEdge)
1342 {
1343 int y;
1344 int dx, dy;
1345 double xa, ya;
1346 Bool left;
1347
1348 dx = -face->dy;
1349 dy = face->dx;
1350 xa = face->xa;
1351 ya = face->ya;
1352 left = 1;
1353 if (ya > 0) {
1354 ya = 0.0;
1355 xa = 0.0;
1356 }
1357 if (dy < 0 || (dy == 0 && dx > 0)) {
1358 dx = -dx;
1359 dy = -dy;
1360 left = !left;
1361 }
1362 if (dx == 0 && dy == 0)
1363 dy = 1;
1364 if (dy == 0) {
1365 y = ICEIL(face->ya) + face->y;
1366 edge->x = -32767;
1367 edge->stepx = 0;
1368 edge->signdx = 0;
1369 edge->e = -1;
1370 edge->dy = 0;
1371 edge->dx = 0;
1372 edge->height = 0;
1373 }
1374 else {
1375 y = miPolyBuildEdge(xa, ya, 0.0, dx, dy, face->x, face->y, !left, edge);
1376 edge->height = 32767;
1377 }
1378 *leftEdge = !left;
1379 return y;
1380 }
1381
1382 static void
miRoundJoinClip(LineFacePtr pLeft,LineFacePtr pRight,PolyEdgePtr edge1,PolyEdgePtr edge2,int * y1,int * y2,Bool * left1,Bool * left2)1383 miRoundJoinClip(LineFacePtr pLeft, LineFacePtr pRight,
1384 PolyEdgePtr edge1, PolyEdgePtr edge2,
1385 int *y1, int *y2, Bool *left1, Bool *left2)
1386 {
1387 double denom;
1388
1389 denom = -pLeft->dx * (double) pRight->dy + pRight->dx * (double) pLeft->dy;
1390
1391 if (denom >= 0) {
1392 pLeft->xa = -pLeft->xa;
1393 pLeft->ya = -pLeft->ya;
1394 }
1395 else {
1396 pRight->xa = -pRight->xa;
1397 pRight->ya = -pRight->ya;
1398 }
1399 *y1 = miRoundJoinFace(pLeft, edge1, left1);
1400 *y2 = miRoundJoinFace(pRight, edge2, left2);
1401 }
1402
1403 static int
miRoundCapClip(LineFacePtr face,Bool isInt,PolyEdgePtr edge,Bool * leftEdge)1404 miRoundCapClip(LineFacePtr face, Bool isInt, PolyEdgePtr edge, Bool *leftEdge)
1405 {
1406 int y;
1407 int dx, dy;
1408 double xa, ya, k;
1409 Bool left;
1410
1411 dx = -face->dy;
1412 dy = face->dx;
1413 xa = face->xa;
1414 ya = face->ya;
1415 k = 0.0;
1416 if (!isInt)
1417 k = face->k;
1418 left = 1;
1419 if (dy < 0 || (dy == 0 && dx > 0)) {
1420 dx = -dx;
1421 dy = -dy;
1422 xa = -xa;
1423 ya = -ya;
1424 left = !left;
1425 }
1426 if (dx == 0 && dy == 0)
1427 dy = 1;
1428 if (dy == 0) {
1429 y = ICEIL(face->ya) + face->y;
1430 edge->x = -32767;
1431 edge->stepx = 0;
1432 edge->signdx = 0;
1433 edge->e = -1;
1434 edge->dy = 0;
1435 edge->dx = 0;
1436 edge->height = 0;
1437 }
1438 else {
1439 y = miPolyBuildEdge(xa, ya, k, dx, dy, face->x, face->y, !left, edge);
1440 edge->height = 32767;
1441 }
1442 *leftEdge = !left;
1443 return y;
1444 }
1445
1446 static void
miLineArc(DrawablePtr pDraw,GCPtr pGC,unsigned long pixel,SpanDataPtr spanData,LineFacePtr leftFace,LineFacePtr rightFace,double xorg,double yorg,Bool isInt)1447 miLineArc(DrawablePtr pDraw,
1448 GCPtr pGC,
1449 unsigned long pixel,
1450 SpanDataPtr spanData,
1451 LineFacePtr leftFace,
1452 LineFacePtr rightFace, double xorg, double yorg, Bool isInt)
1453 {
1454 int xorgi = 0, yorgi = 0;
1455 Spans spanRec;
1456 int n;
1457 PolyEdgeRec edge1 = { 0 }, edge2 = { 0 };
1458 int edgey1, edgey2;
1459 Bool edgeleft1, edgeleft2;
1460
1461 if (isInt) {
1462 xorgi = leftFace ? leftFace->x : rightFace->x;
1463 yorgi = leftFace ? leftFace->y : rightFace->y;
1464 }
1465 edgey1 = 65536;
1466 edgey2 = 65536;
1467 edge1.x = 0; /* not used, keep memory checkers happy */
1468 edge1.dy = -1;
1469 edge2.x = 0; /* not used, keep memory checkers happy */
1470 edge2.dy = -1;
1471 edgeleft1 = FALSE;
1472 edgeleft2 = FALSE;
1473 if ((pGC->lineStyle != LineSolid || pGC->lineWidth > 2) &&
1474 ((pGC->capStyle == CapRound && pGC->joinStyle != JoinRound) ||
1475 (pGC->joinStyle == JoinRound && pGC->capStyle == CapButt))) {
1476 if (isInt) {
1477 xorg = (double) xorgi;
1478 yorg = (double) yorgi;
1479 }
1480 if (leftFace && rightFace) {
1481 miRoundJoinClip(leftFace, rightFace, &edge1, &edge2,
1482 &edgey1, &edgey2, &edgeleft1, &edgeleft2);
1483 }
1484 else if (leftFace) {
1485 edgey1 = miRoundCapClip(leftFace, isInt, &edge1, &edgeleft1);
1486 }
1487 else if (rightFace) {
1488 edgey2 = miRoundCapClip(rightFace, isInt, &edge2, &edgeleft2);
1489 }
1490 isInt = FALSE;
1491 }
1492 if (!InitSpans(&spanRec, pGC->lineWidth))
1493 return;
1494 if (isInt)
1495 n = miLineArcI(pDraw, pGC, xorgi, yorgi, spanRec.points,
1496 spanRec.widths);
1497 else
1498 n = miLineArcD(pDraw, pGC, xorg, yorg, spanRec.points, spanRec.widths,
1499 &edge1, edgey1, edgeleft1, &edge2, edgey2, edgeleft2);
1500 spanRec.count = n;
1501 fillSpans(pDraw, pGC, pixel, &spanRec, spanData);
1502 }
1503
1504 static void
miLineProjectingCap(DrawablePtr pDrawable,GCPtr pGC,unsigned long pixel,SpanDataPtr spanData,LineFacePtr face,Bool isLeft,double xorg,double yorg,Bool isInt)1505 miLineProjectingCap(DrawablePtr pDrawable, GCPtr pGC, unsigned long pixel,
1506 SpanDataPtr spanData, LineFacePtr face, Bool isLeft,
1507 double xorg, double yorg, Bool isInt)
1508 {
1509 int xorgi = 0, yorgi = 0;
1510 int lw;
1511 PolyEdgeRec lefts[4], rights[4];
1512 int lefty, righty, topy, bottomy;
1513 PolyEdgePtr left, right;
1514 PolyEdgePtr top, bottom;
1515 double xa, ya;
1516 double k;
1517 double xap, yap;
1518 int dx, dy;
1519 double projectXoff, projectYoff;
1520 double maxy;
1521 int finaly;
1522
1523 if (isInt) {
1524 xorgi = face->x;
1525 yorgi = face->y;
1526 }
1527 lw = pGC->lineWidth;
1528 dx = face->dx;
1529 dy = face->dy;
1530 k = face->k;
1531 if (dy == 0) {
1532 lefts[0].height = lw;
1533 lefts[0].x = xorgi;
1534 if (isLeft)
1535 lefts[0].x -= (lw >> 1);
1536 lefts[0].stepx = 0;
1537 lefts[0].signdx = 1;
1538 lefts[0].e = -lw;
1539 lefts[0].dx = 0;
1540 lefts[0].dy = lw;
1541 rights[0].height = lw;
1542 rights[0].x = xorgi;
1543 if (!isLeft)
1544 rights[0].x += ((lw + 1) >> 1);
1545 rights[0].stepx = 0;
1546 rights[0].signdx = 1;
1547 rights[0].e = -lw;
1548 rights[0].dx = 0;
1549 rights[0].dy = lw;
1550 miFillPolyHelper(pDrawable, pGC, pixel, spanData, yorgi - (lw >> 1), lw,
1551 lefts, rights, 1, 1);
1552 }
1553 else if (dx == 0) {
1554 if (dy < 0) {
1555 dy = -dy;
1556 isLeft = !isLeft;
1557 }
1558 topy = yorgi;
1559 bottomy = yorgi + dy;
1560 if (isLeft)
1561 topy -= (lw >> 1);
1562 else
1563 bottomy += (lw >> 1);
1564 lefts[0].height = bottomy - topy;
1565 lefts[0].x = xorgi - (lw >> 1);
1566 lefts[0].stepx = 0;
1567 lefts[0].signdx = 1;
1568 lefts[0].e = -dy;
1569 lefts[0].dx = dx;
1570 lefts[0].dy = dy;
1571
1572 rights[0].height = bottomy - topy;
1573 rights[0].x = lefts[0].x + (lw - 1);
1574 rights[0].stepx = 0;
1575 rights[0].signdx = 1;
1576 rights[0].e = -dy;
1577 rights[0].dx = dx;
1578 rights[0].dy = dy;
1579 miFillPolyHelper(pDrawable, pGC, pixel, spanData, topy, bottomy - topy,
1580 lefts, rights, 1, 1);
1581 }
1582 else {
1583 xa = face->xa;
1584 ya = face->ya;
1585 projectXoff = -ya;
1586 projectYoff = xa;
1587 if (dx < 0) {
1588 right = &rights[1];
1589 left = &lefts[0];
1590 top = &rights[0];
1591 bottom = &lefts[1];
1592 }
1593 else {
1594 right = &rights[0];
1595 left = &lefts[1];
1596 top = &lefts[0];
1597 bottom = &rights[1];
1598 }
1599 if (isLeft) {
1600 righty = miPolyBuildEdge(xa, ya, k, dx, dy, xorgi, yorgi, 0, right);
1601
1602 xa = -xa;
1603 ya = -ya;
1604 k = -k;
1605 lefty = miPolyBuildEdge(xa - projectXoff, ya - projectYoff,
1606 k, dx, dy, xorgi, yorgi, 1, left);
1607 if (dx > 0) {
1608 ya = -ya;
1609 xa = -xa;
1610 }
1611 xap = xa - projectXoff;
1612 yap = ya - projectYoff;
1613 topy = miPolyBuildEdge(xap, yap, xap * dx + yap * dy,
1614 -dy, dx, xorgi, yorgi, dx > 0, top);
1615 bottomy = miPolyBuildEdge(xa, ya,
1616 0.0, -dy, dx, xorgi, yorgi, dx < 0,
1617 bottom);
1618 maxy = -ya;
1619 }
1620 else {
1621 righty = miPolyBuildEdge(xa - projectXoff, ya - projectYoff,
1622 k, dx, dy, xorgi, yorgi, 0, right);
1623
1624 xa = -xa;
1625 ya = -ya;
1626 k = -k;
1627 lefty = miPolyBuildEdge(xa, ya, k, dx, dy, xorgi, yorgi, 1, left);
1628 if (dx > 0) {
1629 ya = -ya;
1630 xa = -xa;
1631 }
1632 xap = xa - projectXoff;
1633 yap = ya - projectYoff;
1634 topy =
1635 miPolyBuildEdge(xa, ya, 0.0, -dy, dx, xorgi, xorgi, dx > 0,
1636 top);
1637 bottomy =
1638 miPolyBuildEdge(xap, yap, xap * dx + yap * dy, -dy, dx, xorgi,
1639 xorgi, dx < 0, bottom);
1640 maxy = -ya + projectYoff;
1641 }
1642 finaly = ICEIL(maxy) + yorgi;
1643 if (dx < 0) {
1644 left->height = bottomy - lefty;
1645 right->height = finaly - righty;
1646 top->height = righty - topy;
1647 }
1648 else {
1649 right->height = bottomy - righty;
1650 left->height = finaly - lefty;
1651 top->height = lefty - topy;
1652 }
1653 bottom->height = finaly - bottomy;
1654 miFillPolyHelper(pDrawable, pGC, pixel, spanData, topy,
1655 bottom->height + bottomy - topy, lefts, rights, 2, 2);
1656 }
1657 }
1658
1659 static void
miWideSegment(DrawablePtr pDrawable,GCPtr pGC,unsigned long pixel,SpanDataPtr spanData,int x1,int y1,int x2,int y2,Bool projectLeft,Bool projectRight,LineFacePtr leftFace,LineFacePtr rightFace)1660 miWideSegment(DrawablePtr pDrawable,
1661 GCPtr pGC,
1662 unsigned long pixel,
1663 SpanDataPtr spanData,
1664 int x1,
1665 int y1,
1666 int x2,
1667 int y2,
1668 Bool projectLeft,
1669 Bool projectRight, LineFacePtr leftFace, LineFacePtr rightFace)
1670 {
1671 double l, L, r;
1672 double xa, ya;
1673 double projectXoff = 0.0, projectYoff = 0.0;
1674 double k;
1675 double maxy;
1676 int x, y;
1677 int dx, dy;
1678 int finaly;
1679 PolyEdgePtr left, right;
1680 PolyEdgePtr top, bottom;
1681 int lefty, righty, topy, bottomy;
1682 int signdx;
1683 PolyEdgeRec lefts[4], rights[4];
1684 LineFacePtr tface;
1685 int lw = pGC->lineWidth;
1686
1687 /* draw top-to-bottom always */
1688 if (y2 < y1 || (y2 == y1 && x2 < x1)) {
1689 x = x1;
1690 x1 = x2;
1691 x2 = x;
1692
1693 y = y1;
1694 y1 = y2;
1695 y2 = y;
1696
1697 x = projectLeft;
1698 projectLeft = projectRight;
1699 projectRight = x;
1700
1701 tface = leftFace;
1702 leftFace = rightFace;
1703 rightFace = tface;
1704 }
1705
1706 dy = y2 - y1;
1707 signdx = 1;
1708 dx = x2 - x1;
1709 if (dx < 0)
1710 signdx = -1;
1711
1712 leftFace->x = x1;
1713 leftFace->y = y1;
1714 leftFace->dx = dx;
1715 leftFace->dy = dy;
1716
1717 rightFace->x = x2;
1718 rightFace->y = y2;
1719 rightFace->dx = -dx;
1720 rightFace->dy = -dy;
1721
1722 if (dy == 0) {
1723 rightFace->xa = 0;
1724 rightFace->ya = (double) lw / 2.0;
1725 rightFace->k = -(double) (lw * dx) / 2.0;
1726 leftFace->xa = 0;
1727 leftFace->ya = -rightFace->ya;
1728 leftFace->k = rightFace->k;
1729 x = x1;
1730 if (projectLeft)
1731 x -= (lw >> 1);
1732 y = y1 - (lw >> 1);
1733 dx = x2 - x;
1734 if (projectRight)
1735 dx += ((lw + 1) >> 1);
1736 dy = lw;
1737 miFillRectPolyHelper(pDrawable, pGC, pixel, spanData, x, y, dx, dy);
1738 }
1739 else if (dx == 0) {
1740 leftFace->xa = (double) lw / 2.0;
1741 leftFace->ya = 0;
1742 leftFace->k = (double) (lw * dy) / 2.0;
1743 rightFace->xa = -leftFace->xa;
1744 rightFace->ya = 0;
1745 rightFace->k = leftFace->k;
1746 y = y1;
1747 if (projectLeft)
1748 y -= lw >> 1;
1749 x = x1 - (lw >> 1);
1750 dy = y2 - y;
1751 if (projectRight)
1752 dy += ((lw + 1) >> 1);
1753 dx = lw;
1754 miFillRectPolyHelper(pDrawable, pGC, pixel, spanData, x, y, dx, dy);
1755 }
1756 else {
1757 l = ((double) lw) / 2.0;
1758 L = hypot((double) dx, (double) dy);
1759
1760 if (dx < 0) {
1761 right = &rights[1];
1762 left = &lefts[0];
1763 top = &rights[0];
1764 bottom = &lefts[1];
1765 }
1766 else {
1767 right = &rights[0];
1768 left = &lefts[1];
1769 top = &lefts[0];
1770 bottom = &rights[1];
1771 }
1772 r = l / L;
1773
1774 /* coord of upper bound at integral y */
1775 ya = -r * dx;
1776 xa = r * dy;
1777
1778 if (projectLeft | projectRight) {
1779 projectXoff = -ya;
1780 projectYoff = xa;
1781 }
1782
1783 /* xa * dy - ya * dx */
1784 k = l * L;
1785
1786 leftFace->xa = xa;
1787 leftFace->ya = ya;
1788 leftFace->k = k;
1789 rightFace->xa = -xa;
1790 rightFace->ya = -ya;
1791 rightFace->k = k;
1792
1793 if (projectLeft)
1794 righty = miPolyBuildEdge(xa - projectXoff, ya - projectYoff,
1795 k, dx, dy, x1, y1, 0, right);
1796 else
1797 righty = miPolyBuildEdge(xa, ya, k, dx, dy, x1, y1, 0, right);
1798
1799 /* coord of lower bound at integral y */
1800 ya = -ya;
1801 xa = -xa;
1802
1803 /* xa * dy - ya * dx */
1804 k = -k;
1805
1806 if (projectLeft)
1807 lefty = miPolyBuildEdge(xa - projectXoff, ya - projectYoff,
1808 k, dx, dy, x1, y1, 1, left);
1809 else
1810 lefty = miPolyBuildEdge(xa, ya, k, dx, dy, x1, y1, 1, left);
1811
1812 /* coord of top face at integral y */
1813
1814 if (signdx > 0) {
1815 ya = -ya;
1816 xa = -xa;
1817 }
1818
1819 if (projectLeft) {
1820 double xap = xa - projectXoff;
1821 double yap = ya - projectYoff;
1822
1823 topy = miPolyBuildEdge(xap, yap, xap * dx + yap * dy,
1824 -dy, dx, x1, y1, dx > 0, top);
1825 }
1826 else
1827 topy = miPolyBuildEdge(xa, ya, 0.0, -dy, dx, x1, y1, dx > 0, top);
1828
1829 /* coord of bottom face at integral y */
1830
1831 if (projectRight) {
1832 double xap = xa + projectXoff;
1833 double yap = ya + projectYoff;
1834
1835 bottomy = miPolyBuildEdge(xap, yap, xap * dx + yap * dy,
1836 -dy, dx, x2, y2, dx < 0, bottom);
1837 maxy = -ya + projectYoff;
1838 }
1839 else {
1840 bottomy = miPolyBuildEdge(xa, ya,
1841 0.0, -dy, dx, x2, y2, dx < 0, bottom);
1842 maxy = -ya;
1843 }
1844
1845 finaly = ICEIL(maxy) + y2;
1846
1847 if (dx < 0) {
1848 left->height = bottomy - lefty;
1849 right->height = finaly - righty;
1850 top->height = righty - topy;
1851 }
1852 else {
1853 right->height = bottomy - righty;
1854 left->height = finaly - lefty;
1855 top->height = lefty - topy;
1856 }
1857 bottom->height = finaly - bottomy;
1858 miFillPolyHelper(pDrawable, pGC, pixel, spanData, topy,
1859 bottom->height + bottomy - topy, lefts, rights, 2, 2);
1860 }
1861 }
1862
1863 static SpanDataPtr
miSetupSpanData(GCPtr pGC,SpanDataPtr spanData,int npt)1864 miSetupSpanData(GCPtr pGC, SpanDataPtr spanData, int npt)
1865 {
1866 if ((npt < 3 && pGC->capStyle != CapRound) || miSpansEasyRop(pGC->alu))
1867 return (SpanDataPtr) NULL;
1868 if (pGC->lineStyle == LineDoubleDash)
1869 miInitSpanGroup(&spanData->bgGroup);
1870 miInitSpanGroup(&spanData->fgGroup);
1871 return spanData;
1872 }
1873
1874 static void
miCleanupSpanData(DrawablePtr pDrawable,GCPtr pGC,SpanDataPtr spanData)1875 miCleanupSpanData(DrawablePtr pDrawable, GCPtr pGC, SpanDataPtr spanData)
1876 {
1877 if (pGC->lineStyle == LineDoubleDash) {
1878 ChangeGCVal oldPixel, pixel;
1879
1880 pixel.val = pGC->bgPixel;
1881 oldPixel.val = pGC->fgPixel;
1882 if (pixel.val != oldPixel.val) {
1883 ChangeGC(NullClient, pGC, GCForeground, &pixel);
1884 ValidateGC(pDrawable, pGC);
1885 }
1886 miFillUniqueSpanGroup(pDrawable, pGC, &spanData->bgGroup);
1887 miFreeSpanGroup(&spanData->bgGroup);
1888 if (pixel.val != oldPixel.val) {
1889 ChangeGC(NullClient, pGC, GCForeground, &oldPixel);
1890 ValidateGC(pDrawable, pGC);
1891 }
1892 }
1893 miFillUniqueSpanGroup(pDrawable, pGC, &spanData->fgGroup);
1894 miFreeSpanGroup(&spanData->fgGroup);
1895 }
1896
1897 void
miWideLine(DrawablePtr pDrawable,GCPtr pGC,int mode,int npt,DDXPointPtr pPts)1898 miWideLine(DrawablePtr pDrawable, GCPtr pGC,
1899 int mode, int npt, DDXPointPtr pPts)
1900 {
1901 int x1, y1, x2, y2;
1902 SpanDataRec spanDataRec;
1903 SpanDataPtr spanData;
1904 long pixel;
1905 Bool projectLeft, projectRight;
1906 LineFaceRec leftFace, rightFace, prevRightFace;
1907 LineFaceRec firstFace;
1908 int first;
1909 Bool somethingDrawn = FALSE;
1910 Bool selfJoin;
1911
1912 spanData = miSetupSpanData(pGC, &spanDataRec, npt);
1913 pixel = pGC->fgPixel;
1914 x2 = pPts->x;
1915 y2 = pPts->y;
1916 first = TRUE;
1917 selfJoin = FALSE;
1918 if (npt > 1) {
1919 if (mode == CoordModePrevious) {
1920 int nptTmp;
1921 DDXPointPtr pPtsTmp;
1922
1923 x1 = x2;
1924 y1 = y2;
1925 nptTmp = npt;
1926 pPtsTmp = pPts + 1;
1927 while (--nptTmp) {
1928 x1 += pPtsTmp->x;
1929 y1 += pPtsTmp->y;
1930 ++pPtsTmp;
1931 }
1932 if (x2 == x1 && y2 == y1)
1933 selfJoin = TRUE;
1934 }
1935 else if (x2 == pPts[npt - 1].x && y2 == pPts[npt - 1].y) {
1936 selfJoin = TRUE;
1937 }
1938 }
1939 projectLeft = pGC->capStyle == CapProjecting && !selfJoin;
1940 projectRight = FALSE;
1941 while (--npt) {
1942 x1 = x2;
1943 y1 = y2;
1944 ++pPts;
1945 x2 = pPts->x;
1946 y2 = pPts->y;
1947 if (mode == CoordModePrevious) {
1948 x2 += x1;
1949 y2 += y1;
1950 }
1951 if (x1 != x2 || y1 != y2) {
1952 somethingDrawn = TRUE;
1953 if (npt == 1 && pGC->capStyle == CapProjecting && !selfJoin)
1954 projectRight = TRUE;
1955 miWideSegment(pDrawable, pGC, pixel, spanData, x1, y1, x2, y2,
1956 projectLeft, projectRight, &leftFace, &rightFace);
1957 if (first) {
1958 if (selfJoin)
1959 firstFace = leftFace;
1960 else if (pGC->capStyle == CapRound) {
1961 if (pGC->lineWidth == 1 && !spanData)
1962 miLineOnePoint(pDrawable, pGC, pixel, spanData, x1, y1);
1963 else
1964 miLineArc(pDrawable, pGC, pixel, spanData,
1965 &leftFace, (LineFacePtr) NULL,
1966 (double) 0.0, (double) 0.0, TRUE);
1967 }
1968 }
1969 else {
1970 miLineJoin(pDrawable, pGC, pixel, spanData, &leftFace,
1971 &prevRightFace);
1972 }
1973 prevRightFace = rightFace;
1974 first = FALSE;
1975 projectLeft = FALSE;
1976 }
1977 if (npt == 1 && somethingDrawn) {
1978 if (selfJoin)
1979 miLineJoin(pDrawable, pGC, pixel, spanData, &firstFace,
1980 &rightFace);
1981 else if (pGC->capStyle == CapRound) {
1982 if (pGC->lineWidth == 1 && !spanData)
1983 miLineOnePoint(pDrawable, pGC, pixel, spanData, x2, y2);
1984 else
1985 miLineArc(pDrawable, pGC, pixel, spanData,
1986 (LineFacePtr) NULL, &rightFace,
1987 (double) 0.0, (double) 0.0, TRUE);
1988 }
1989 }
1990 }
1991 /* handle crock where all points are coincedent */
1992 if (!somethingDrawn) {
1993 projectLeft = pGC->capStyle == CapProjecting;
1994 miWideSegment(pDrawable, pGC, pixel, spanData,
1995 x2, y2, x2, y2, projectLeft, projectLeft,
1996 &leftFace, &rightFace);
1997 if (pGC->capStyle == CapRound) {
1998 miLineArc(pDrawable, pGC, pixel, spanData,
1999 &leftFace, (LineFacePtr) NULL,
2000 (double) 0.0, (double) 0.0, TRUE);
2001 rightFace.dx = -1; /* sleezy hack to make it work */
2002 miLineArc(pDrawable, pGC, pixel, spanData,
2003 (LineFacePtr) NULL, &rightFace,
2004 (double) 0.0, (double) 0.0, TRUE);
2005 }
2006 }
2007 if (spanData)
2008 miCleanupSpanData(pDrawable, pGC, spanData);
2009 }
2010
2011 #define V_TOP 0
2012 #define V_RIGHT 1
2013 #define V_BOTTOM 2
2014 #define V_LEFT 3
2015
2016 static void
miWideDashSegment(DrawablePtr pDrawable,GCPtr pGC,SpanDataPtr spanData,int * pDashOffset,int * pDashIndex,int x1,int y1,int x2,int y2,Bool projectLeft,Bool projectRight,LineFacePtr leftFace,LineFacePtr rightFace)2017 miWideDashSegment(DrawablePtr pDrawable,
2018 GCPtr pGC,
2019 SpanDataPtr spanData,
2020 int *pDashOffset,
2021 int *pDashIndex,
2022 int x1,
2023 int y1,
2024 int x2,
2025 int y2,
2026 Bool projectLeft,
2027 Bool projectRight,
2028 LineFacePtr leftFace, LineFacePtr rightFace)
2029 {
2030 int dashIndex, dashRemain;
2031 unsigned char *pDash;
2032 double L, l;
2033 double k;
2034 PolyVertexRec vertices[4];
2035 PolyVertexRec saveRight, saveBottom;
2036 PolySlopeRec slopes[4];
2037 PolyEdgeRec left[4], right[4];
2038 LineFaceRec lcapFace, rcapFace;
2039 int nleft, nright;
2040 int h;
2041 int y;
2042 int dy, dx;
2043 unsigned long pixel;
2044 double LRemain;
2045 double r;
2046 double rdx, rdy;
2047 double dashDx, dashDy;
2048 double saveK = 0.0;
2049 Bool first = TRUE;
2050 double lcenterx, lcentery, rcenterx = 0.0, rcentery = 0.0;
2051 unsigned long fgPixel, bgPixel;
2052
2053 dx = x2 - x1;
2054 dy = y2 - y1;
2055 dashIndex = *pDashIndex;
2056 pDash = pGC->dash;
2057 dashRemain = pDash[dashIndex] - *pDashOffset;
2058 fgPixel = pGC->fgPixel;
2059 bgPixel = pGC->bgPixel;
2060 if (pGC->fillStyle == FillOpaqueStippled || pGC->fillStyle == FillTiled) {
2061 bgPixel = fgPixel;
2062 }
2063
2064 l = ((double) pGC->lineWidth) / 2.0;
2065 if (dx == 0) {
2066 L = dy;
2067 rdx = 0;
2068 rdy = l;
2069 if (dy < 0) {
2070 L = -dy;
2071 rdy = -l;
2072 }
2073 }
2074 else if (dy == 0) {
2075 L = dx;
2076 rdx = l;
2077 rdy = 0;
2078 if (dx < 0) {
2079 L = -dx;
2080 rdx = -l;
2081 }
2082 }
2083 else {
2084 L = hypot((double) dx, (double) dy);
2085 r = l / L;
2086
2087 rdx = r * dx;
2088 rdy = r * dy;
2089 }
2090 k = l * L;
2091 LRemain = L;
2092 /* All position comments are relative to a line with dx and dy > 0,
2093 * but the code does not depend on this */
2094 /* top */
2095 slopes[V_TOP].dx = dx;
2096 slopes[V_TOP].dy = dy;
2097 slopes[V_TOP].k = k;
2098 /* right */
2099 slopes[V_RIGHT].dx = -dy;
2100 slopes[V_RIGHT].dy = dx;
2101 slopes[V_RIGHT].k = 0;
2102 /* bottom */
2103 slopes[V_BOTTOM].dx = -dx;
2104 slopes[V_BOTTOM].dy = -dy;
2105 slopes[V_BOTTOM].k = k;
2106 /* left */
2107 slopes[V_LEFT].dx = dy;
2108 slopes[V_LEFT].dy = -dx;
2109 slopes[V_LEFT].k = 0;
2110
2111 /* preload the start coordinates */
2112 vertices[V_RIGHT].x = vertices[V_TOP].x = rdy;
2113 vertices[V_RIGHT].y = vertices[V_TOP].y = -rdx;
2114
2115 vertices[V_BOTTOM].x = vertices[V_LEFT].x = -rdy;
2116 vertices[V_BOTTOM].y = vertices[V_LEFT].y = rdx;
2117
2118 if (projectLeft) {
2119 vertices[V_TOP].x -= rdx;
2120 vertices[V_TOP].y -= rdy;
2121
2122 vertices[V_LEFT].x -= rdx;
2123 vertices[V_LEFT].y -= rdy;
2124
2125 slopes[V_LEFT].k = rdx * dx + rdy * dy;
2126 }
2127
2128 lcenterx = x1;
2129 lcentery = y1;
2130
2131 if (pGC->capStyle == CapRound) {
2132 lcapFace.dx = dx;
2133 lcapFace.dy = dy;
2134 lcapFace.x = x1;
2135 lcapFace.y = y1;
2136
2137 rcapFace.dx = -dx;
2138 rcapFace.dy = -dy;
2139 rcapFace.x = x1;
2140 rcapFace.y = y1;
2141 }
2142 while (LRemain > dashRemain) {
2143 dashDx = (dashRemain * dx) / L;
2144 dashDy = (dashRemain * dy) / L;
2145
2146 rcenterx = lcenterx + dashDx;
2147 rcentery = lcentery + dashDy;
2148
2149 vertices[V_RIGHT].x += dashDx;
2150 vertices[V_RIGHT].y += dashDy;
2151
2152 vertices[V_BOTTOM].x += dashDx;
2153 vertices[V_BOTTOM].y += dashDy;
2154
2155 slopes[V_RIGHT].k = vertices[V_RIGHT].x * dx + vertices[V_RIGHT].y * dy;
2156
2157 if (pGC->lineStyle == LineDoubleDash || !(dashIndex & 1)) {
2158 if (pGC->lineStyle == LineOnOffDash &&
2159 pGC->capStyle == CapProjecting) {
2160 saveRight = vertices[V_RIGHT];
2161 saveBottom = vertices[V_BOTTOM];
2162 saveK = slopes[V_RIGHT].k;
2163
2164 if (!first) {
2165 vertices[V_TOP].x -= rdx;
2166 vertices[V_TOP].y -= rdy;
2167
2168 vertices[V_LEFT].x -= rdx;
2169 vertices[V_LEFT].y -= rdy;
2170
2171 slopes[V_LEFT].k = vertices[V_LEFT].x *
2172 slopes[V_LEFT].dy -
2173 vertices[V_LEFT].y * slopes[V_LEFT].dx;
2174 }
2175
2176 vertices[V_RIGHT].x += rdx;
2177 vertices[V_RIGHT].y += rdy;
2178
2179 vertices[V_BOTTOM].x += rdx;
2180 vertices[V_BOTTOM].y += rdy;
2181
2182 slopes[V_RIGHT].k = vertices[V_RIGHT].x *
2183 slopes[V_RIGHT].dy -
2184 vertices[V_RIGHT].y * slopes[V_RIGHT].dx;
2185 }
2186 y = miPolyBuildPoly(vertices, slopes, 4, x1, y1,
2187 left, right, &nleft, &nright, &h);
2188 pixel = (dashIndex & 1) ? bgPixel : fgPixel;
2189 miFillPolyHelper(pDrawable, pGC, pixel, spanData, y, h, left, right,
2190 nleft, nright);
2191
2192 if (pGC->lineStyle == LineOnOffDash) {
2193 switch (pGC->capStyle) {
2194 case CapProjecting:
2195 vertices[V_BOTTOM] = saveBottom;
2196 vertices[V_RIGHT] = saveRight;
2197 slopes[V_RIGHT].k = saveK;
2198 break;
2199 case CapRound:
2200 if (!first) {
2201 if (dx < 0) {
2202 lcapFace.xa = -vertices[V_LEFT].x;
2203 lcapFace.ya = -vertices[V_LEFT].y;
2204 lcapFace.k = slopes[V_LEFT].k;
2205 }
2206 else {
2207 lcapFace.xa = vertices[V_TOP].x;
2208 lcapFace.ya = vertices[V_TOP].y;
2209 lcapFace.k = -slopes[V_LEFT].k;
2210 }
2211 miLineArc(pDrawable, pGC, pixel, spanData,
2212 &lcapFace, (LineFacePtr) NULL,
2213 lcenterx, lcentery, FALSE);
2214 }
2215 if (dx < 0) {
2216 rcapFace.xa = vertices[V_BOTTOM].x;
2217 rcapFace.ya = vertices[V_BOTTOM].y;
2218 rcapFace.k = slopes[V_RIGHT].k;
2219 }
2220 else {
2221 rcapFace.xa = -vertices[V_RIGHT].x;
2222 rcapFace.ya = -vertices[V_RIGHT].y;
2223 rcapFace.k = -slopes[V_RIGHT].k;
2224 }
2225 miLineArc(pDrawable, pGC, pixel, spanData,
2226 (LineFacePtr) NULL, &rcapFace,
2227 rcenterx, rcentery, FALSE);
2228 break;
2229 }
2230 }
2231 }
2232 LRemain -= dashRemain;
2233 ++dashIndex;
2234 if (dashIndex == pGC->numInDashList)
2235 dashIndex = 0;
2236 dashRemain = pDash[dashIndex];
2237
2238 lcenterx = rcenterx;
2239 lcentery = rcentery;
2240
2241 vertices[V_TOP] = vertices[V_RIGHT];
2242 vertices[V_LEFT] = vertices[V_BOTTOM];
2243 slopes[V_LEFT].k = -slopes[V_RIGHT].k;
2244 first = FALSE;
2245 }
2246
2247 if (pGC->lineStyle == LineDoubleDash || !(dashIndex & 1)) {
2248 vertices[V_TOP].x -= dx;
2249 vertices[V_TOP].y -= dy;
2250
2251 vertices[V_LEFT].x -= dx;
2252 vertices[V_LEFT].y -= dy;
2253
2254 vertices[V_RIGHT].x = rdy;
2255 vertices[V_RIGHT].y = -rdx;
2256
2257 vertices[V_BOTTOM].x = -rdy;
2258 vertices[V_BOTTOM].y = rdx;
2259
2260 if (projectRight) {
2261 vertices[V_RIGHT].x += rdx;
2262 vertices[V_RIGHT].y += rdy;
2263
2264 vertices[V_BOTTOM].x += rdx;
2265 vertices[V_BOTTOM].y += rdy;
2266 slopes[V_RIGHT].k = vertices[V_RIGHT].x *
2267 slopes[V_RIGHT].dy - vertices[V_RIGHT].y * slopes[V_RIGHT].dx;
2268 }
2269 else
2270 slopes[V_RIGHT].k = 0;
2271
2272 if (!first && pGC->lineStyle == LineOnOffDash &&
2273 pGC->capStyle == CapProjecting) {
2274 vertices[V_TOP].x -= rdx;
2275 vertices[V_TOP].y -= rdy;
2276
2277 vertices[V_LEFT].x -= rdx;
2278 vertices[V_LEFT].y -= rdy;
2279 slopes[V_LEFT].k = vertices[V_LEFT].x *
2280 slopes[V_LEFT].dy - vertices[V_LEFT].y * slopes[V_LEFT].dx;
2281 }
2282 else
2283 slopes[V_LEFT].k += dx * dx + dy * dy;
2284
2285 y = miPolyBuildPoly(vertices, slopes, 4, x2, y2,
2286 left, right, &nleft, &nright, &h);
2287
2288 pixel = (dashIndex & 1) ? pGC->bgPixel : pGC->fgPixel;
2289 miFillPolyHelper(pDrawable, pGC, pixel, spanData, y, h, left, right,
2290 nleft, nright);
2291 if (!first && pGC->lineStyle == LineOnOffDash &&
2292 pGC->capStyle == CapRound) {
2293 lcapFace.x = x2;
2294 lcapFace.y = y2;
2295 if (dx < 0) {
2296 lcapFace.xa = -vertices[V_LEFT].x;
2297 lcapFace.ya = -vertices[V_LEFT].y;
2298 lcapFace.k = slopes[V_LEFT].k;
2299 }
2300 else {
2301 lcapFace.xa = vertices[V_TOP].x;
2302 lcapFace.ya = vertices[V_TOP].y;
2303 lcapFace.k = -slopes[V_LEFT].k;
2304 }
2305 miLineArc(pDrawable, pGC, pixel, spanData,
2306 &lcapFace, (LineFacePtr) NULL, rcenterx, rcentery, FALSE);
2307 }
2308 }
2309 dashRemain = ((double) dashRemain) - LRemain;
2310 if (dashRemain == 0) {
2311 dashIndex++;
2312 if (dashIndex == pGC->numInDashList)
2313 dashIndex = 0;
2314 dashRemain = pDash[dashIndex];
2315 }
2316
2317 leftFace->x = x1;
2318 leftFace->y = y1;
2319 leftFace->dx = dx;
2320 leftFace->dy = dy;
2321 leftFace->xa = rdy;
2322 leftFace->ya = -rdx;
2323 leftFace->k = k;
2324
2325 rightFace->x = x2;
2326 rightFace->y = y2;
2327 rightFace->dx = -dx;
2328 rightFace->dy = -dy;
2329 rightFace->xa = -rdy;
2330 rightFace->ya = rdx;
2331 rightFace->k = k;
2332
2333 *pDashIndex = dashIndex;
2334 *pDashOffset = pDash[dashIndex] - dashRemain;
2335 }
2336
2337 void
miWideDash(DrawablePtr pDrawable,GCPtr pGC,int mode,int npt,DDXPointPtr pPts)2338 miWideDash(DrawablePtr pDrawable, GCPtr pGC,
2339 int mode, int npt, DDXPointPtr pPts)
2340 {
2341 int x1, y1, x2, y2;
2342 unsigned long pixel;
2343 Bool projectLeft, projectRight;
2344 LineFaceRec leftFace, rightFace, prevRightFace;
2345 LineFaceRec firstFace;
2346 int first;
2347 int dashIndex, dashOffset;
2348 int prevDashIndex;
2349 SpanDataRec spanDataRec;
2350 SpanDataPtr spanData;
2351 Bool somethingDrawn = FALSE;
2352 Bool selfJoin;
2353 Bool endIsFg = FALSE, startIsFg = FALSE;
2354 Bool firstIsFg = FALSE, prevIsFg = FALSE;
2355
2356 #if 0
2357 /* XXX backward compatibility */
2358 if (pGC->lineWidth == 0) {
2359 miZeroDashLine(pDrawable, pGC, mode, npt, pPts);
2360 return;
2361 }
2362 #endif
2363 if (pGC->lineStyle == LineDoubleDash &&
2364 (pGC->fillStyle == FillOpaqueStippled || pGC->fillStyle == FillTiled)) {
2365 miWideLine(pDrawable, pGC, mode, npt, pPts);
2366 return;
2367 }
2368 if (npt == 0)
2369 return;
2370 spanData = miSetupSpanData(pGC, &spanDataRec, npt);
2371 x2 = pPts->x;
2372 y2 = pPts->y;
2373 first = TRUE;
2374 selfJoin = FALSE;
2375 if (mode == CoordModePrevious) {
2376 int nptTmp;
2377 DDXPointPtr pPtsTmp;
2378
2379 x1 = x2;
2380 y1 = y2;
2381 nptTmp = npt;
2382 pPtsTmp = pPts + 1;
2383 while (--nptTmp) {
2384 x1 += pPtsTmp->x;
2385 y1 += pPtsTmp->y;
2386 ++pPtsTmp;
2387 }
2388 if (x2 == x1 && y2 == y1)
2389 selfJoin = TRUE;
2390 }
2391 else if (x2 == pPts[npt - 1].x && y2 == pPts[npt - 1].y) {
2392 selfJoin = TRUE;
2393 }
2394 projectLeft = pGC->capStyle == CapProjecting && !selfJoin;
2395 projectRight = FALSE;
2396 dashIndex = 0;
2397 dashOffset = 0;
2398 miStepDash((int) pGC->dashOffset, &dashIndex,
2399 pGC->dash, (int) pGC->numInDashList, &dashOffset);
2400 while (--npt) {
2401 x1 = x2;
2402 y1 = y2;
2403 ++pPts;
2404 x2 = pPts->x;
2405 y2 = pPts->y;
2406 if (mode == CoordModePrevious) {
2407 x2 += x1;
2408 y2 += y1;
2409 }
2410 if (x1 != x2 || y1 != y2) {
2411 somethingDrawn = TRUE;
2412 if (npt == 1 && pGC->capStyle == CapProjecting &&
2413 (!selfJoin || !firstIsFg))
2414 projectRight = TRUE;
2415 prevDashIndex = dashIndex;
2416 miWideDashSegment(pDrawable, pGC, spanData, &dashOffset, &dashIndex,
2417 x1, y1, x2, y2,
2418 projectLeft, projectRight, &leftFace, &rightFace);
2419 startIsFg = !(prevDashIndex & 1);
2420 endIsFg = (dashIndex & 1) ^ (dashOffset != 0);
2421 if (pGC->lineStyle == LineDoubleDash || startIsFg) {
2422 pixel = startIsFg ? pGC->fgPixel : pGC->bgPixel;
2423 if (first || (pGC->lineStyle == LineOnOffDash && !prevIsFg)) {
2424 if (first && selfJoin) {
2425 firstFace = leftFace;
2426 firstIsFg = startIsFg;
2427 }
2428 else if (pGC->capStyle == CapRound)
2429 miLineArc(pDrawable, pGC, pixel, spanData,
2430 &leftFace, (LineFacePtr) NULL,
2431 (double) 0.0, (double) 0.0, TRUE);
2432 }
2433 else {
2434 miLineJoin(pDrawable, pGC, pixel, spanData, &leftFace,
2435 &prevRightFace);
2436 }
2437 }
2438 prevRightFace = rightFace;
2439 prevIsFg = endIsFg;
2440 first = FALSE;
2441 projectLeft = FALSE;
2442 }
2443 if (npt == 1 && somethingDrawn) {
2444 if (pGC->lineStyle == LineDoubleDash || endIsFg) {
2445 pixel = endIsFg ? pGC->fgPixel : pGC->bgPixel;
2446 if (selfJoin && (pGC->lineStyle == LineDoubleDash || firstIsFg)) {
2447 miLineJoin(pDrawable, pGC, pixel, spanData, &firstFace,
2448 &rightFace);
2449 }
2450 else {
2451 if (pGC->capStyle == CapRound)
2452 miLineArc(pDrawable, pGC, pixel, spanData,
2453 (LineFacePtr) NULL, &rightFace,
2454 (double) 0.0, (double) 0.0, TRUE);
2455 }
2456 }
2457 else {
2458 /* glue a cap to the start of the line if
2459 * we're OnOffDash and ended on odd dash
2460 */
2461 if (selfJoin && firstIsFg) {
2462 pixel = pGC->fgPixel;
2463 if (pGC->capStyle == CapProjecting)
2464 miLineProjectingCap(pDrawable, pGC, pixel, spanData,
2465 &firstFace, TRUE,
2466 (double) 0.0, (double) 0.0, TRUE);
2467 else if (pGC->capStyle == CapRound)
2468 miLineArc(pDrawable, pGC, pixel, spanData,
2469 &firstFace, (LineFacePtr) NULL,
2470 (double) 0.0, (double) 0.0, TRUE);
2471 }
2472 }
2473 }
2474 }
2475 /* handle crock where all points are coincident */
2476 if (!somethingDrawn &&
2477 (pGC->lineStyle == LineDoubleDash || !(dashIndex & 1))) {
2478 /* not the same as endIsFg computation above */
2479 pixel = (dashIndex & 1) ? pGC->bgPixel : pGC->fgPixel;
2480 switch (pGC->capStyle) {
2481 case CapRound:
2482 miLineArc(pDrawable, pGC, pixel, spanData,
2483 (LineFacePtr) NULL, (LineFacePtr) NULL,
2484 (double) x2, (double) y2, FALSE);
2485 break;
2486 case CapProjecting:
2487 x1 = pGC->lineWidth;
2488 miFillRectPolyHelper(pDrawable, pGC, pixel, spanData,
2489 x2 - (x1 >> 1), y2 - (x1 >> 1), x1, x1);
2490 break;
2491 }
2492 }
2493 if (spanData)
2494 miCleanupSpanData(pDrawable, pGC, spanData);
2495 }
2496
2497 void
miPolylines(DrawablePtr drawable,GCPtr gc,int mode,int n,DDXPointPtr points)2498 miPolylines(DrawablePtr drawable,
2499 GCPtr gc,
2500 int mode,
2501 int n,
2502 DDXPointPtr points)
2503 {
2504 if (gc->lineWidth == 0) {
2505 if (gc->lineStyle == LineSolid)
2506 miZeroLine(drawable, gc, mode, n, points);
2507 else
2508 miZeroDashLine(drawable, gc, mode, n, points);
2509 } else {
2510 if (gc->lineStyle == LineSolid)
2511 miWideLine(drawable, gc, mode, n, points);
2512 else
2513 miWideDash(drawable, gc, mode, n, points);
2514 }
2515 }
2516