1 /***********************************************************
3 Copyright (c) 1989 X Consortium
5 Permission is hereby granted, free of charge, to any person obtaining a copy
6 of this software and associated documentation files (the "Software"), to deal
7 in the Software without restriction, including without limitation the rights
8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 copies of the Software, and to permit persons to whom the Software is
10 furnished to do so, subject to the following conditions:
12 The above copyright notice and this permission notice shall be included in
13 all copies or substantial portions of the Software.
15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
19 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 Except as contained in this notice, the name of the X Consortium shall not be
23 used in advertising or otherwise to promote the sale, use or other dealings
24 in this Software without prior written authorization from the X Consortium.
27 Copyright 1989 by Digital Equipment Corporation, Maynard, Massachusetts.
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.
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
47 ******************************************************************/
49 /* $XConsortium: mispans.c,v 5.5 94/04/17 20:27:52 dpw Exp $ */
50 /* $XFree86: xc/programs/Xserver/mi/mispans.c,v 3.0 1995/07/07 15:45:49 dawes Exp $ */
53 #include "pixmapstr.h"
59 These routines maintain lists of Spans, in order to implement the
60 ``touch-each-pixel-once'' rules of wide lines and arcs.
62 Written by Joel McCormack, Summer 1989.
67 void miInitSpanGroup(spanGroup)
72 spanGroup->group = NULL;
73 spanGroup->ymin = MAXSHORT;
74 spanGroup->ymax = MINSHORT;
77 #define YMIN(spans) (spans->points[0].y)
78 #define YMAX(spans) (spans->points[spans->count-1].y)
80 void miSubtractSpans (spanGroup, sub)
84 int i, subCount, spansCount;
85 int ymin, ymax, xmin, xmax;
87 DDXPointPtr subPt, spansPt;
88 int *subWid, *spansWid;
93 spans = spanGroup->group;
94 for (i = spanGroup->count; i; i--, spans++) {
95 if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
96 subCount = sub->count;
99 spansCount = spans->count;
100 spansPt = spans->points;
101 spansWid = spans->widths;
105 while (spansCount && spansPt->y < subPt->y)
107 spansPt++; spansWid++; spansCount--;
111 while (subCount && subPt->y < spansPt->y)
113 subPt++; subWid++; subCount--;
117 if (subPt->y == spansPt->y)
120 xmax = xmin + *subWid;
121 if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax)
125 else if (xmin <= spansPt->x)
127 if (xmax >= spansPt->x + *spansWid)
129 memmove (spansPt, spansPt + 1, sizeof *spansPt * (spansCount - 1));
130 memmove (spansWid, spansWid + 1, sizeof *spansWid * (spansCount - 1));
138 *spansWid = *spansWid - (xmax - spansPt->x);
144 if (xmax >= spansPt->x + *spansWid)
146 *spansWid = xmin - spansPt->x;
155 newPt = (DDXPointPtr) xrealloc (spans->points, (spans->count + EXTRA) * sizeof (DDXPointRec));
158 spansPt = newPt + (spansPt - spans->points);
159 spans->points = newPt;
160 newwid = (int *) xrealloc (spans->widths, (spans->count + EXTRA) * sizeof (int));
163 spansWid = newwid + (spansWid - spans->widths);
164 spans->widths = newwid;
167 memmove (spansPt + 1, spansPt, sizeof *spansPt * (spansCount));
168 memmove (spansWid + 1, spansWid, sizeof *spansWid * (spansCount));
171 *spansWid = xmin - spansPt->x;
174 *spansWid = *spansWid - (xmax - spansPt->x);
179 spansPt++; spansWid++; spansCount--;
185 void miAppendSpans(spanGroup, otherGroup, spans)
186 SpanGroup *spanGroup;
187 SpanGroup *otherGroup;
190 register int ymin, ymax;
191 register int spansCount;
193 spansCount = spans->count;
194 if (spansCount > 0) {
195 if (spanGroup->size == spanGroup->count) {
196 spanGroup->size = (spanGroup->size + 8) * 2;
197 spanGroup->group = (Spans *)
198 xrealloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
201 spanGroup->group[spanGroup->count] = *spans;
202 (spanGroup->count)++;
203 ymin = spans->points[0].y;
204 if (ymin < spanGroup->ymin) spanGroup->ymin = ymin;
205 ymax = spans->points[spansCount - 1].y;
206 if (ymax > spanGroup->ymax) spanGroup->ymax = ymax;
208 otherGroup->ymin < ymax &&
209 ymin < otherGroup->ymax)
211 miSubtractSpans (otherGroup, spans);
216 xfree (spans->points);
217 xfree (spans->widths);
221 void miFreeSpanGroup(spanGroup)
222 SpanGroup *spanGroup;
224 if (spanGroup->group != NULL) xfree(spanGroup->group);
227 static void QuickSortSpansX(points, widths, numSpans)
228 register DDXPointRec points[];
229 register int widths[];
230 register int numSpans;
233 register int i, j, m;
234 register DDXPointPtr r;
236 /* Always called with numSpans > 1 */
237 /* Sorts only by x, as all y should be the same */
239 #define ExchangeSpans(a, b) \
244 tpt = points[a]; points[a] = points[b]; points[b] = tpt; \
245 tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
250 /* Do insertion sort */
255 do { /* while i != numSpans */
258 /* points[i] is out of order. Move into proper location. */
262 for (j = 0; x >= points[j].x; j++) {}
265 for (k = i; k != j; k--) {
266 points[k] = points[k-1];
267 widths[k] = widths[k-1];
272 } /* if out of order */
275 } while (i != numSpans);
279 /* Choose partition element, stick in location 0 */
281 if (points[m].x > points[0].x) ExchangeSpans(m, 0);
282 if (points[m].x > points[numSpans-1].x) ExchangeSpans(m, numSpans-1);
283 if (points[m].x > points[0].x) ExchangeSpans(m, 0);
286 /* Partition array */
294 } while (i != numSpans && r->x < x);
300 if (i < j) ExchangeSpans(i, j);
303 /* Move partition element back to middle */
307 if (numSpans-j-1 > 1)
308 QuickSortSpansX(&points[j+1], &widths[j+1], numSpans-j-1);
310 } while (numSpans > 1);
311 } /* QuickSortSpans */
314 static int UniquifySpansX(spans, newPoints, newWidths)
316 register DDXPointRec *newPoints;
317 register int *newWidths;
319 register int newx1, newx2, oldpt, i, y;
320 register DDXPointRec *oldPoints;
321 register int *oldWidths;
324 /* Always called with numSpans > 1 */
325 /* Uniquify the spans, and stash them into newPoints and newWidths. Return the
326 number of unique spans. */
329 startNewWidths = newWidths;
331 oldPoints = spans->points;
332 oldWidths = spans->widths;
335 newx1 = oldPoints->x;
336 newx2 = newx1 + *oldWidths;
338 for (i = spans->count-1; i != 0; i--) {
341 oldpt = oldPoints->x;
343 /* Write current span, start a new one */
344 newPoints->x = newx1;
346 *newWidths = newx2 - newx1;
350 newx2 = oldpt + *oldWidths;
352 /* extend current span, if old extends beyond new */
353 oldpt = oldpt + *oldWidths;
354 if (oldpt > newx2) newx2 = oldpt;
358 /* Write final span */
359 newPoints->x = newx1;
360 *newWidths = newx2 - newx1;
363 return (newWidths - startNewWidths) + 1;
364 } /* UniquifySpansX */
367 miDisposeSpanGroup (spanGroup)
368 SpanGroup *spanGroup;
373 for (i = 0; i < spanGroup->count; i++)
375 spans = spanGroup->group + i;
376 xfree (spans->points);
377 xfree (spans->widths);
381 void miFillUniqueSpanGroup(pDraw, pGC, spanGroup)
384 SpanGroup *spanGroup;
387 register Spans *spans;
388 register Spans *yspans;
389 register int *ysizes;
390 register int ymin, ylength;
392 /* Outgoing spans for one big call to FillSpans */
393 register DDXPointPtr points;
394 register int *widths;
397 if (spanGroup->count == 0) return;
399 if (spanGroup->count == 1) {
400 /* Already should be sorted, unique */
401 spans = spanGroup->group;
402 (*pGC->ops->FillSpans)
403 (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
404 xfree(spans->points);
405 xfree(spans->widths);
409 /* Yuck. Gross. Radix sort into y buckets, then sort x and uniquify */
410 /* This seems to be the fastest thing to do. I've tried sorting on
411 both x and y at the same time rather than creating into all those
412 y buckets, but it was somewhat slower. */
414 ymin = spanGroup->ymin;
415 ylength = spanGroup->ymax - ymin + 1;
417 /* Allocate Spans for y buckets */
418 yspans = (Spans *) xalloc(ylength * sizeof(Spans));
419 ysizes = (int *) xalloc(ylength * sizeof (int));
421 if (!yspans || !ysizes)
427 miDisposeSpanGroup (spanGroup);
431 for (i = 0; i != ylength; i++) {
434 yspans[i].points = NULL;
435 yspans[i].widths = NULL;
438 /* Go through every single span and put it into the correct bucket */
440 for (i = 0, spans = spanGroup->group;
441 i != spanGroup->count;
446 for (j = 0, points = spans->points, widths = spans->widths;
448 j++, points++, widths++) {
449 index = points->y - ymin;
450 if (index >= 0 && index < ylength) {
451 Spans *newspans = &(yspans[index]);
452 if (newspans->count == ysizes[index]) {
453 DDXPointPtr newpoints;
455 ysizes[index] = (ysizes[index] + 8) * 2;
456 newpoints = (DDXPointPtr) xrealloc(
458 ysizes[index] * sizeof(DDXPointRec));
459 newwidths = (int *) xrealloc(
461 ysizes[index] * sizeof(int));
462 if (!newpoints || !newwidths)
466 for (i = 0; i < ylength; i++)
468 xfree (yspans[i].points);
469 xfree (yspans[i].widths);
473 miDisposeSpanGroup (spanGroup);
476 newspans->points = newpoints;
477 newspans->widths = newwidths;
479 newspans->points[newspans->count] = *points;
480 newspans->widths[newspans->count] = *widths;
482 } /* if y value of span in range */
483 } /* for j through spans */
484 count += spans->count;
485 xfree(spans->points);
486 spans->points = NULL;
487 xfree(spans->widths);
488 spans->widths = NULL;
489 } /* for i thorough Spans */
491 /* Now sort by x and uniquify each bucket into the final array */
492 points = (DDXPointPtr) xalloc(count * sizeof(DDXPointRec));
493 widths = (int *) xalloc(count * sizeof(int));
494 if (!points || !widths)
498 for (i = 0; i < ylength; i++)
500 xfree (yspans[i].points);
501 xfree (yspans[i].widths);
512 for (i = 0; i != ylength; i++) {
513 int ycount = yspans[i].count;
516 QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
517 count += UniquifySpansX
518 (&(yspans[i]), &(points[count]), &(widths[count]));
520 points[count] = yspans[i].points[0];
521 widths[count] = yspans[i].widths[0];
524 xfree(yspans[i].points);
525 xfree(yspans[i].widths);
529 (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
533 xfree(ysizes); /* use (DE)ALLOCATE_LOCAL for these? */
536 spanGroup->count = 0;
537 spanGroup->ymin = MAXSHORT;
538 spanGroup->ymax = MINSHORT;
542 void miFillSpanGroup(pDraw, pGC, spanGroup)
545 SpanGroup *spanGroup;
548 register Spans *spans;
550 for (i = 0, spans = spanGroup->group; i != spanGroup->count; i++, spans++) {
551 (*pGC->ops->FillSpans)
552 (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
553 xfree(spans->points);
554 xfree(spans->widths);
557 spanGroup->count = 0;
558 spanGroup->ymin = MAXSHORT;
559 spanGroup->ymax = MINSHORT;
560 } /* FillSpanGroup */