1 /***********************************************************
2
3 Copyright (c) 1989 X Consortium
4
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:
11
12 The above copyright notice and this permission notice shall be included in
13 all copies or substantial portions of the Software.
14
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.
21
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.
25
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
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 $ */
51
52 #include "misc.h"
53 #include "pixmapstr.h"
54 #include "gcstruct.h"
55 #include "mispans.h"
56
57 /*
58
59 These routines maintain lists of Spans, in order to implement the
60 ``touch-each-pixel-once'' rules of wide lines and arcs.
61
62 Written by Joel McCormack, Summer 1989.
63
64 */
65
66
miInitSpanGroup(spanGroup)67 void miInitSpanGroup(spanGroup)
68 SpanGroup *spanGroup;
69 {
70 spanGroup->size = 0;
71 spanGroup->count = 0;
72 spanGroup->group = NULL;
73 spanGroup->ymin = MAXSHORT;
74 spanGroup->ymax = MINSHORT;
75 } /* InitSpanGroup */
76
77 #define YMIN(spans) (spans->points[0].y)
78 #define YMAX(spans) (spans->points[spans->count-1].y)
79
miSubtractSpans(spanGroup,sub)80 void miSubtractSpans (spanGroup, sub)
81 SpanGroup *spanGroup;
82 Spans *sub;
83 {
84 int i, subCount, spansCount;
85 int ymin, ymax, xmin, xmax;
86 Spans *spans;
87 DDXPointPtr subPt, spansPt;
88 int *subWid, *spansWid;
89 int extra;
90
91 ymin = YMIN(sub);
92 ymax = YMAX(sub);
93 spans = spanGroup->group;
94 for (i = spanGroup->count; i; i--, spans++) {
95 if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
96 subCount = sub->count;
97 subPt = sub->points;
98 subWid = sub->widths;
99 spansCount = spans->count;
100 spansPt = spans->points;
101 spansWid = spans->widths;
102 extra = 0;
103 for (;;)
104 {
105 while (spansCount && spansPt->y < subPt->y)
106 {
107 spansPt++; spansWid++; spansCount--;
108 }
109 if (!spansCount)
110 break;
111 while (subCount && subPt->y < spansPt->y)
112 {
113 subPt++; subWid++; subCount--;
114 }
115 if (!subCount)
116 break;
117 if (subPt->y == spansPt->y)
118 {
119 xmin = subPt->x;
120 xmax = xmin + *subWid;
121 if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax)
122 {
123 ;
124 }
125 else if (xmin <= spansPt->x)
126 {
127 if (xmax >= spansPt->x + *spansWid)
128 {
129 memmove (spansPt, spansPt + 1, sizeof *spansPt * (spansCount - 1));
130 memmove (spansWid, spansWid + 1, sizeof *spansWid * (spansCount - 1));
131 spansPt--;
132 spansWid--;
133 spans->count--;
134 extra++;
135 }
136 else
137 {
138 *spansWid = *spansWid - (xmax - spansPt->x);
139 spansPt->x = xmax;
140 }
141 }
142 else
143 {
144 if (xmax >= spansPt->x + *spansWid)
145 {
146 *spansWid = xmin - spansPt->x;
147 }
148 else
149 {
150 if (!extra) {
151 DDXPointPtr newPt;
152 int *newwid;
153
154 #define EXTRA 8
155 newPt = (DDXPointPtr) xrealloc (spans->points, (spans->count + EXTRA) * sizeof (DDXPointRec));
156 if (!newPt)
157 break;
158 spansPt = newPt + (spansPt - spans->points);
159 spans->points = newPt;
160 newwid = (int *) xrealloc (spans->widths, (spans->count + EXTRA) * sizeof (int));
161 if (!newwid)
162 break;
163 spansWid = newwid + (spansWid - spans->widths);
164 spans->widths = newwid;
165 extra = EXTRA;
166 }
167 memmove (spansPt + 1, spansPt, sizeof *spansPt * (spansCount));
168 memmove (spansWid + 1, spansWid, sizeof *spansWid * (spansCount));
169 spans->count++;
170 extra--;
171 *spansWid = xmin - spansPt->x;
172 spansWid++;
173 spansPt++;
174 *spansWid = *spansWid - (xmax - spansPt->x);
175 spansPt->x = xmax;
176 }
177 }
178 }
179 spansPt++; spansWid++; spansCount--;
180 }
181 }
182 }
183 }
184
miAppendSpans(spanGroup,otherGroup,spans)185 void miAppendSpans(spanGroup, otherGroup, spans)
186 SpanGroup *spanGroup;
187 SpanGroup *otherGroup;
188 Spans *spans;
189 {
190 register int ymin, ymax;
191 register int spansCount;
192
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);
199 }
200
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;
207 if (otherGroup &&
208 otherGroup->ymin < ymax &&
209 ymin < otherGroup->ymax)
210 {
211 miSubtractSpans (otherGroup, spans);
212 }
213 }
214 else
215 {
216 xfree (spans->points);
217 xfree (spans->widths);
218 }
219 } /* AppendSpans */
220
miFreeSpanGroup(spanGroup)221 void miFreeSpanGroup(spanGroup)
222 SpanGroup *spanGroup;
223 {
224 if (spanGroup->group != NULL) xfree(spanGroup->group);
225 }
226
QuickSortSpansX(points,widths,numSpans)227 static void QuickSortSpansX(points, widths, numSpans)
228 register DDXPointRec points[];
229 register int widths[];
230 register int numSpans;
231 {
232 register int x;
233 register int i, j, m;
234 register DDXPointPtr r;
235
236 /* Always called with numSpans > 1 */
237 /* Sorts only by x, as all y should be the same */
238
239 #define ExchangeSpans(a, b) \
240 { \
241 DDXPointRec tpt; \
242 register int tw; \
243 \
244 tpt = points[a]; points[a] = points[b]; points[b] = tpt; \
245 tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
246 }
247
248 do {
249 if (numSpans < 9) {
250 /* Do insertion sort */
251 register int xprev;
252
253 xprev = points[0].x;
254 i = 1;
255 do { /* while i != numSpans */
256 x = points[i].x;
257 if (xprev > x) {
258 /* points[i] is out of order. Move into proper location. */
259 DDXPointRec tpt;
260 int tw, k;
261
262 for (j = 0; x >= points[j].x; j++) {}
263 tpt = points[i];
264 tw = widths[i];
265 for (k = i; k != j; k--) {
266 points[k] = points[k-1];
267 widths[k] = widths[k-1];
268 }
269 points[j] = tpt;
270 widths[j] = tw;
271 x = points[i].x;
272 } /* if out of order */
273 xprev = x;
274 i++;
275 } while (i != numSpans);
276 return;
277 }
278
279 /* Choose partition element, stick in location 0 */
280 m = numSpans / 2;
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);
284 x = points[0].x;
285
286 /* Partition array */
287 i = 0;
288 j = numSpans;
289 do {
290 r = &(points[i]);
291 do {
292 r++;
293 i++;
294 } while (i != numSpans && r->x < x);
295 r = &(points[j]);
296 do {
297 r--;
298 j--;
299 } while (x < r->x);
300 if (i < j) ExchangeSpans(i, j);
301 } while (i < j);
302
303 /* Move partition element back to middle */
304 ExchangeSpans(0, j);
305
306 /* Recurse */
307 if (numSpans-j-1 > 1)
308 QuickSortSpansX(&points[j+1], &widths[j+1], numSpans-j-1);
309 numSpans = j;
310 } while (numSpans > 1);
311 } /* QuickSortSpans */
312
313
UniquifySpansX(spans,newPoints,newWidths)314 static int UniquifySpansX(spans, newPoints, newWidths)
315 Spans *spans;
316 register DDXPointRec *newPoints;
317 register int *newWidths;
318 {
319 register int newx1, newx2, oldpt, i, y;
320 register DDXPointRec *oldPoints;
321 register int *oldWidths;
322 int *startNewWidths;
323
324 /* Always called with numSpans > 1 */
325 /* Uniquify the spans, and stash them into newPoints and newWidths. Return the
326 number of unique spans. */
327
328
329 startNewWidths = newWidths;
330
331 oldPoints = spans->points;
332 oldWidths = spans->widths;
333
334 y = oldPoints->y;
335 newx1 = oldPoints->x;
336 newx2 = newx1 + *oldWidths;
337
338 for (i = spans->count-1; i != 0; i--) {
339 oldPoints++;
340 oldWidths++;
341 oldpt = oldPoints->x;
342 if (oldpt > newx2) {
343 /* Write current span, start a new one */
344 newPoints->x = newx1;
345 newPoints->y = y;
346 *newWidths = newx2 - newx1;
347 newPoints++;
348 newWidths++;
349 newx1 = oldpt;
350 newx2 = oldpt + *oldWidths;
351 } else {
352 /* extend current span, if old extends beyond new */
353 oldpt = oldpt + *oldWidths;
354 if (oldpt > newx2) newx2 = oldpt;
355 }
356 } /* for */
357
358 /* Write final span */
359 newPoints->x = newx1;
360 *newWidths = newx2 - newx1;
361 newPoints->y = y;
362
363 return (newWidths - startNewWidths) + 1;
364 } /* UniquifySpansX */
365
366 void
miDisposeSpanGroup(spanGroup)367 miDisposeSpanGroup (spanGroup)
368 SpanGroup *spanGroup;
369 {
370 int i;
371 Spans *spans;
372
373 for (i = 0; i < spanGroup->count; i++)
374 {
375 spans = spanGroup->group + i;
376 xfree (spans->points);
377 xfree (spans->widths);
378 }
379 }
380
miFillUniqueSpanGroup(pDraw,pGC,spanGroup)381 void miFillUniqueSpanGroup(pDraw, pGC, spanGroup)
382 DrawablePtr pDraw;
383 GCPtr pGC;
384 SpanGroup *spanGroup;
385 {
386 register int i;
387 register Spans *spans;
388 register Spans *yspans;
389 register int *ysizes;
390 register int ymin, ylength;
391
392 /* Outgoing spans for one big call to FillSpans */
393 register DDXPointPtr points;
394 register int *widths;
395 register int count;
396
397 if (spanGroup->count == 0) return;
398
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);
406 }
407 else
408 {
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. */
413
414 ymin = spanGroup->ymin;
415 ylength = spanGroup->ymax - ymin + 1;
416
417 /* Allocate Spans for y buckets */
418 yspans = (Spans *) xalloc(ylength * sizeof(Spans));
419 ysizes = (int *) xalloc(ylength * sizeof (int));
420
421 if (!yspans || !ysizes)
422 {
423 if (yspans)
424 xfree (yspans);
425 if (ysizes)
426 xfree (ysizes);
427 miDisposeSpanGroup (spanGroup);
428 return;
429 }
430
431 for (i = 0; i != ylength; i++) {
432 ysizes[i] = 0;
433 yspans[i].count = 0;
434 yspans[i].points = NULL;
435 yspans[i].widths = NULL;
436 }
437
438 /* Go through every single span and put it into the correct bucket */
439 count = 0;
440 for (i = 0, spans = spanGroup->group;
441 i != spanGroup->count;
442 i++, spans++) {
443 int index;
444 int j;
445
446 for (j = 0, points = spans->points, widths = spans->widths;
447 j != spans->count;
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;
454 int *newwidths;
455 ysizes[index] = (ysizes[index] + 8) * 2;
456 newpoints = (DDXPointPtr) xrealloc(
457 newspans->points,
458 ysizes[index] * sizeof(DDXPointRec));
459 newwidths = (int *) xrealloc(
460 newspans->widths,
461 ysizes[index] * sizeof(int));
462 if (!newpoints || !newwidths)
463 {
464 int i;
465
466 for (i = 0; i < ylength; i++)
467 {
468 xfree (yspans[i].points);
469 xfree (yspans[i].widths);
470 }
471 xfree (yspans);
472 xfree (ysizes);
473 miDisposeSpanGroup (spanGroup);
474 return;
475 }
476 newspans->points = newpoints;
477 newspans->widths = newwidths;
478 }
479 newspans->points[newspans->count] = *points;
480 newspans->widths[newspans->count] = *widths;
481 (newspans->count)++;
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 */
490
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)
495 {
496 int i;
497
498 for (i = 0; i < ylength; i++)
499 {
500 xfree (yspans[i].points);
501 xfree (yspans[i].widths);
502 }
503 xfree (yspans);
504 xfree (ysizes);
505 if (points)
506 xfree (points);
507 if (widths)
508 xfree (widths);
509 return;
510 }
511 count = 0;
512 for (i = 0; i != ylength; i++) {
513 int ycount = yspans[i].count;
514 if (ycount > 0) {
515 if (ycount > 1) {
516 QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
517 count += UniquifySpansX
518 (&(yspans[i]), &(points[count]), &(widths[count]));
519 } else {
520 points[count] = yspans[i].points[0];
521 widths[count] = yspans[i].widths[0];
522 count++;
523 }
524 xfree(yspans[i].points);
525 xfree(yspans[i].widths);
526 }
527 }
528
529 (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
530 xfree(points);
531 xfree(widths);
532 xfree(yspans);
533 xfree(ysizes); /* use (DE)ALLOCATE_LOCAL for these? */
534 }
535
536 spanGroup->count = 0;
537 spanGroup->ymin = MAXSHORT;
538 spanGroup->ymax = MINSHORT;
539 }
540
541
miFillSpanGroup(pDraw,pGC,spanGroup)542 void miFillSpanGroup(pDraw, pGC, spanGroup)
543 DrawablePtr pDraw;
544 GCPtr pGC;
545 SpanGroup *spanGroup;
546 {
547 register int i;
548 register Spans *spans;
549
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);
555 }
556
557 spanGroup->count = 0;
558 spanGroup->ymin = MAXSHORT;
559 spanGroup->ymax = MINSHORT;
560 } /* FillSpanGroup */
561