Commit | Line | Data |
---|---|---|
a09e091a JB |
1 | /*********************************************************** |
2 | ||
3 | Copyright 1989, 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 in | |
12 | all copies or substantial portions of the Software. | |
13 | ||
14 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
15 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
16 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
17 | OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN | |
18 | AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | |
19 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |
20 | ||
21 | Except as contained in this notice, the name of The Open Group shall not be | |
22 | used in advertising or otherwise to promote the sale, use or other dealings | |
23 | in this Software without prior written authorization from The Open Group. | |
24 | ||
25 | Copyright 1989 by Digital Equipment Corporation, Maynard, Massachusetts. | |
26 | ||
27 | All Rights Reserved | |
28 | ||
29 | Permission to use, copy, modify, and distribute this software and its | |
30 | documentation for any purpose and without fee is hereby granted, | |
31 | provided that the above copyright notice appear in all copies and that | |
32 | both that copyright notice and this permission notice appear in | |
33 | supporting documentation, and that the name of Digital not be | |
34 | used in advertising or publicity pertaining to distribution of the | |
35 | software without specific, written prior permission. | |
36 | ||
37 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING | |
38 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL | |
39 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR | |
40 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, | |
41 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, | |
42 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS | |
43 | SOFTWARE. | |
44 | ||
45 | ******************************************************************/ | |
46 | ||
47 | #ifdef HAVE_DIX_CONFIG_H | |
48 | #include <dix-config.h> | |
49 | #endif | |
50 | ||
51 | #include "misc.h" | |
52 | #include "pixmapstr.h" | |
53 | #include "gcstruct.h" | |
54 | #include "mispans.h" | |
55 | ||
56 | /* | |
57 | ||
58 | These routines maintain lists of Spans, in order to implement the | |
59 | ``touch-each-pixel-once'' rules of wide lines and arcs. | |
60 | ||
61 | Written by Joel McCormack, Summer 1989. | |
62 | ||
63 | */ | |
64 | ||
65 | void | |
66 | miInitSpanGroup(SpanGroup * spanGroup) | |
67 | { | |
68 | spanGroup->size = 0; | |
69 | spanGroup->count = 0; | |
70 | spanGroup->group = NULL; | |
71 | spanGroup->ymin = MAXSHORT; | |
72 | spanGroup->ymax = MINSHORT; | |
73 | } /* InitSpanGroup */ | |
74 | ||
75 | #define YMIN(spans) (spans->points[0].y) | |
76 | #define YMAX(spans) (spans->points[spans->count-1].y) | |
77 | ||
78 | static void | |
79 | miSubtractSpans(SpanGroup * spanGroup, Spans * sub) | |
80 | { | |
81 | int i, subCount, spansCount; | |
82 | int ymin, ymax, xmin, xmax; | |
83 | Spans *spans; | |
84 | DDXPointPtr subPt, spansPt; | |
85 | int *subWid, *spansWid; | |
86 | int extra; | |
87 | ||
88 | ymin = YMIN(sub); | |
89 | ymax = YMAX(sub); | |
90 | spans = spanGroup->group; | |
91 | for (i = spanGroup->count; i; i--, spans++) { | |
92 | if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) { | |
93 | subCount = sub->count; | |
94 | subPt = sub->points; | |
95 | subWid = sub->widths; | |
96 | spansCount = spans->count; | |
97 | spansPt = spans->points; | |
98 | spansWid = spans->widths; | |
99 | extra = 0; | |
100 | for (;;) { | |
101 | while (spansCount && spansPt->y < subPt->y) { | |
102 | spansPt++; | |
103 | spansWid++; | |
104 | spansCount--; | |
105 | } | |
106 | if (!spansCount) | |
107 | break; | |
108 | while (subCount && subPt->y < spansPt->y) { | |
109 | subPt++; | |
110 | subWid++; | |
111 | subCount--; | |
112 | } | |
113 | if (!subCount) | |
114 | break; | |
115 | if (subPt->y == spansPt->y) { | |
116 | xmin = subPt->x; | |
117 | xmax = xmin + *subWid; | |
118 | if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax) { | |
119 | ; | |
120 | } | |
121 | else if (xmin <= spansPt->x) { | |
122 | if (xmax >= spansPt->x + *spansWid) { | |
123 | memmove(spansPt, spansPt + 1, | |
124 | sizeof *spansPt * (spansCount - 1)); | |
125 | memmove(spansWid, spansWid + 1, | |
126 | sizeof *spansWid * (spansCount - 1)); | |
127 | spansPt--; | |
128 | spansWid--; | |
129 | spans->count--; | |
130 | extra++; | |
131 | } | |
132 | else { | |
133 | *spansWid = *spansWid - (xmax - spansPt->x); | |
134 | spansPt->x = xmax; | |
135 | } | |
136 | } | |
137 | else { | |
138 | if (xmax >= spansPt->x + *spansWid) { | |
139 | *spansWid = xmin - spansPt->x; | |
140 | } | |
141 | else { | |
142 | if (!extra) { | |
143 | DDXPointPtr newPt; | |
144 | int *newwid; | |
145 | ||
146 | #define EXTRA 8 | |
147 | newPt = | |
148 | (DDXPointPtr) realloc(spans->points, | |
149 | (spans->count + | |
150 | EXTRA) * | |
151 | sizeof(DDXPointRec)); | |
152 | if (!newPt) | |
153 | break; | |
154 | spansPt = newPt + (spansPt - spans->points); | |
155 | spans->points = newPt; | |
156 | newwid = | |
157 | (int *) realloc(spans->widths, | |
158 | (spans->count + | |
159 | EXTRA) * sizeof(int)); | |
160 | if (!newwid) | |
161 | break; | |
162 | spansWid = newwid + (spansWid - spans->widths); | |
163 | spans->widths = newwid; | |
164 | extra = EXTRA; | |
165 | } | |
166 | memmove(spansPt + 1, spansPt, | |
167 | sizeof *spansPt * (spansCount)); | |
168 | memmove(spansWid + 1, spansWid, | |
169 | sizeof *spansWid * (spansCount)); | |
170 | spans->count++; | |
171 | extra--; | |
172 | *spansWid = xmin - spansPt->x; | |
173 | spansWid++; | |
174 | spansPt++; | |
175 | *spansWid = *spansWid - (xmax - spansPt->x); | |
176 | spansPt->x = xmax; | |
177 | } | |
178 | } | |
179 | } | |
180 | spansPt++; | |
181 | spansWid++; | |
182 | spansCount--; | |
183 | } | |
184 | } | |
185 | } | |
186 | } | |
187 | ||
188 | void | |
189 | miAppendSpans(SpanGroup * spanGroup, SpanGroup * otherGroup, Spans * spans) | |
190 | { | |
191 | int ymin, ymax; | |
192 | int spansCount; | |
193 | ||
194 | spansCount = spans->count; | |
195 | if (spansCount > 0) { | |
196 | if (spanGroup->size == spanGroup->count) { | |
197 | spanGroup->size = (spanGroup->size + 8) * 2; | |
198 | spanGroup->group = (Spans *) | |
199 | realloc(spanGroup->group, sizeof(Spans) * spanGroup->size); | |
200 | } | |
201 | ||
202 | spanGroup->group[spanGroup->count] = *spans; | |
203 | (spanGroup->count)++; | |
204 | ymin = spans->points[0].y; | |
205 | if (ymin < spanGroup->ymin) | |
206 | spanGroup->ymin = ymin; | |
207 | ymax = spans->points[spansCount - 1].y; | |
208 | if (ymax > spanGroup->ymax) | |
209 | spanGroup->ymax = ymax; | |
210 | if (otherGroup && otherGroup->ymin < ymax && ymin < otherGroup->ymax) { | |
211 | miSubtractSpans(otherGroup, spans); | |
212 | } | |
213 | } | |
214 | else { | |
215 | free(spans->points); | |
216 | free(spans->widths); | |
217 | } | |
218 | } /* AppendSpans */ | |
219 | ||
220 | void | |
221 | miFreeSpanGroup(SpanGroup * spanGroup) | |
222 | { | |
223 | free(spanGroup->group); | |
224 | } | |
225 | ||
226 | static void | |
227 | QuickSortSpansX(DDXPointRec points[], int widths[], int numSpans) | |
228 | { | |
229 | int x; | |
230 | int i, j, m; | |
231 | DDXPointPtr r; | |
232 | ||
233 | /* Always called with numSpans > 1 */ | |
234 | /* Sorts only by x, as all y should be the same */ | |
235 | ||
236 | #define ExchangeSpans(a, b) \ | |
237 | { \ | |
238 | DDXPointRec tpt; \ | |
239 | int tw; \ | |
240 | \ | |
241 | tpt = points[a]; points[a] = points[b]; points[b] = tpt; \ | |
242 | tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \ | |
243 | } | |
244 | ||
245 | do { | |
246 | if (numSpans < 9) { | |
247 | /* Do insertion sort */ | |
248 | int xprev; | |
249 | ||
250 | xprev = points[0].x; | |
251 | i = 1; | |
252 | do { /* while i != numSpans */ | |
253 | x = points[i].x; | |
254 | if (xprev > x) { | |
255 | /* points[i] is out of order. Move into proper location. */ | |
256 | DDXPointRec tpt; | |
257 | int tw, k; | |
258 | ||
259 | for (j = 0; x >= points[j].x; j++) { | |
260 | } | |
261 | tpt = points[i]; | |
262 | tw = widths[i]; | |
263 | for (k = i; k != j; k--) { | |
264 | points[k] = points[k - 1]; | |
265 | widths[k] = widths[k - 1]; | |
266 | } | |
267 | points[j] = tpt; | |
268 | widths[j] = tw; | |
269 | x = points[i].x; | |
270 | } /* if out of order */ | |
271 | xprev = x; | |
272 | i++; | |
273 | } while (i != numSpans); | |
274 | return; | |
275 | } | |
276 | ||
277 | /* Choose partition element, stick in location 0 */ | |
278 | m = numSpans / 2; | |
279 | if (points[m].x > points[0].x) | |
280 | ExchangeSpans(m, 0); | |
281 | if (points[m].x > points[numSpans - 1].x) | |
282 | ExchangeSpans(m, numSpans - 1); | |
283 | if (points[m].x > points[0].x) | |
284 | ExchangeSpans(m, 0); | |
285 | x = points[0].x; | |
286 | ||
287 | /* Partition array */ | |
288 | i = 0; | |
289 | j = numSpans; | |
290 | do { | |
291 | r = &(points[i]); | |
292 | do { | |
293 | r++; | |
294 | i++; | |
295 | } while (i != numSpans && r->x < x); | |
296 | r = &(points[j]); | |
297 | do { | |
298 | r--; | |
299 | j--; | |
300 | } while (x < r->x); | |
301 | if (i < j) | |
302 | ExchangeSpans(i, j); | |
303 | } while (i < j); | |
304 | ||
305 | /* Move partition element back to middle */ | |
306 | ExchangeSpans(0, j); | |
307 | ||
308 | /* Recurse */ | |
309 | if (numSpans - j - 1 > 1) | |
310 | QuickSortSpansX(&points[j + 1], &widths[j + 1], numSpans - j - 1); | |
311 | numSpans = j; | |
312 | } while (numSpans > 1); | |
313 | } /* QuickSortSpans */ | |
314 | ||
315 | static int | |
316 | UniquifySpansX(Spans * spans, DDXPointRec * newPoints, int *newWidths) | |
317 | { | |
318 | int newx1, newx2, oldpt, i, y; | |
319 | DDXPointRec *oldPoints; | |
320 | int *oldWidths; | |
321 | int *startNewWidths; | |
322 | ||
323 | /* Always called with numSpans > 1 */ | |
324 | /* Uniquify the spans, and stash them into newPoints and newWidths. Return the | |
325 | number of unique spans. */ | |
326 | ||
327 | startNewWidths = newWidths; | |
328 | ||
329 | oldPoints = spans->points; | |
330 | oldWidths = spans->widths; | |
331 | ||
332 | y = oldPoints->y; | |
333 | newx1 = oldPoints->x; | |
334 | newx2 = newx1 + *oldWidths; | |
335 | ||
336 | for (i = spans->count - 1; i != 0; i--) { | |
337 | oldPoints++; | |
338 | oldWidths++; | |
339 | oldpt = oldPoints->x; | |
340 | if (oldpt > newx2) { | |
341 | /* Write current span, start a new one */ | |
342 | newPoints->x = newx1; | |
343 | newPoints->y = y; | |
344 | *newWidths = newx2 - newx1; | |
345 | newPoints++; | |
346 | newWidths++; | |
347 | newx1 = oldpt; | |
348 | newx2 = oldpt + *oldWidths; | |
349 | } | |
350 | else { | |
351 | /* extend current span, if old extends beyond new */ | |
352 | oldpt = oldpt + *oldWidths; | |
353 | if (oldpt > newx2) | |
354 | 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 | static void | |
367 | miDisposeSpanGroup(SpanGroup * spanGroup) | |
368 | { | |
369 | int i; | |
370 | Spans *spans; | |
371 | ||
372 | for (i = 0; i < spanGroup->count; i++) { | |
373 | spans = spanGroup->group + i; | |
374 | free(spans->points); | |
375 | free(spans->widths); | |
376 | } | |
377 | } | |
378 | ||
379 | void | |
380 | miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup * spanGroup) | |
381 | { | |
382 | int i; | |
383 | Spans *spans; | |
384 | Spans *yspans; | |
385 | int *ysizes; | |
386 | int ymin, ylength; | |
387 | ||
388 | /* Outgoing spans for one big call to FillSpans */ | |
389 | DDXPointPtr points; | |
390 | int *widths; | |
391 | int count; | |
392 | ||
393 | if (spanGroup->count == 0) | |
394 | return; | |
395 | ||
396 | if (spanGroup->count == 1) { | |
397 | /* Already should be sorted, unique */ | |
398 | spans = spanGroup->group; | |
399 | (*pGC->ops->FillSpans) | |
400 | (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE); | |
401 | free(spans->points); | |
402 | free(spans->widths); | |
403 | } | |
404 | else { | |
405 | /* Yuck. Gross. Radix sort into y buckets, then sort x and uniquify */ | |
406 | /* This seems to be the fastest thing to do. I've tried sorting on | |
407 | both x and y at the same time rather than creating into all those | |
408 | y buckets, but it was somewhat slower. */ | |
409 | ||
410 | ymin = spanGroup->ymin; | |
411 | ylength = spanGroup->ymax - ymin + 1; | |
412 | ||
413 | /* Allocate Spans for y buckets */ | |
414 | yspans = malloc(ylength * sizeof(Spans)); | |
415 | ysizes = malloc(ylength * sizeof(int)); | |
416 | ||
417 | if (!yspans || !ysizes) { | |
418 | free(yspans); | |
419 | free(ysizes); | |
420 | miDisposeSpanGroup(spanGroup); | |
421 | return; | |
422 | } | |
423 | ||
424 | for (i = 0; i != ylength; i++) { | |
425 | ysizes[i] = 0; | |
426 | yspans[i].count = 0; | |
427 | yspans[i].points = NULL; | |
428 | yspans[i].widths = NULL; | |
429 | } | |
430 | ||
431 | /* Go through every single span and put it into the correct bucket */ | |
432 | count = 0; | |
433 | for (i = 0, spans = spanGroup->group; | |
434 | i != spanGroup->count; i++, spans++) { | |
435 | int index; | |
436 | int j; | |
437 | ||
438 | for (j = 0, points = spans->points, widths = spans->widths; | |
439 | j != spans->count; j++, points++, widths++) { | |
440 | index = points->y - ymin; | |
441 | if (index >= 0 && index < ylength) { | |
442 | Spans *newspans = &(yspans[index]); | |
443 | ||
444 | if (newspans->count == ysizes[index]) { | |
445 | DDXPointPtr newpoints; | |
446 | int *newwidths; | |
447 | ||
448 | ysizes[index] = (ysizes[index] + 8) * 2; | |
449 | newpoints = (DDXPointPtr) realloc(newspans->points, | |
450 | ysizes[index] * | |
451 | sizeof(DDXPointRec)); | |
452 | newwidths = | |
453 | (int *) realloc(newspans->widths, | |
454 | ysizes[index] * sizeof(int)); | |
455 | if (!newpoints || !newwidths) { | |
456 | for (i = 0; i < ylength; i++) { | |
457 | free(yspans[i].points); | |
458 | free(yspans[i].widths); | |
459 | } | |
460 | free(yspans); | |
461 | free(ysizes); | |
462 | free(newpoints); | |
463 | free(newwidths); | |
464 | miDisposeSpanGroup(spanGroup); | |
465 | return; | |
466 | } | |
467 | newspans->points = newpoints; | |
468 | newspans->widths = newwidths; | |
469 | } | |
470 | newspans->points[newspans->count] = *points; | |
471 | newspans->widths[newspans->count] = *widths; | |
472 | (newspans->count)++; | |
473 | } /* if y value of span in range */ | |
474 | } /* for j through spans */ | |
475 | count += spans->count; | |
476 | free(spans->points); | |
477 | spans->points = NULL; | |
478 | free(spans->widths); | |
479 | spans->widths = NULL; | |
480 | } /* for i thorough Spans */ | |
481 | ||
482 | /* Now sort by x and uniquify each bucket into the final array */ | |
483 | points = malloc(count * sizeof(DDXPointRec)); | |
484 | widths = malloc(count * sizeof(int)); | |
485 | if (!points || !widths) { | |
486 | for (i = 0; i < ylength; i++) { | |
487 | free(yspans[i].points); | |
488 | free(yspans[i].widths); | |
489 | } | |
490 | free(yspans); | |
491 | free(ysizes); | |
492 | free(points); | |
493 | free(widths); | |
494 | return; | |
495 | } | |
496 | count = 0; | |
497 | for (i = 0; i != ylength; i++) { | |
498 | int ycount = yspans[i].count; | |
499 | ||
500 | if (ycount > 0) { | |
501 | if (ycount > 1) { | |
502 | QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount); | |
503 | count += UniquifySpansX | |
504 | (&(yspans[i]), &(points[count]), &(widths[count])); | |
505 | } | |
506 | else { | |
507 | points[count] = yspans[i].points[0]; | |
508 | widths[count] = yspans[i].widths[0]; | |
509 | count++; | |
510 | } | |
511 | free(yspans[i].points); | |
512 | free(yspans[i].widths); | |
513 | } | |
514 | } | |
515 | ||
516 | (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE); | |
517 | free(points); | |
518 | free(widths); | |
519 | free(yspans); | |
520 | free(ysizes); /* use (DE)xalloc for these? */ | |
521 | } | |
522 | ||
523 | spanGroup->count = 0; | |
524 | spanGroup->ymin = MAXSHORT; | |
525 | spanGroup->ymax = MINSHORT; | |
526 | } |