1 /***********************************************************
3 Copyright 1989, 1998 The Open Group
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
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
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.
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.
25 Copyright 1989 by Digital Equipment Corporation, Maynard, Massachusetts.
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.
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
45 ******************************************************************/
47 #ifdef HAVE_DIX_CONFIG_H
48 #include <dix-config.h>
52 #include "pixmapstr.h"
58 These routines maintain lists of Spans, in order to implement the
59 ``touch-each-pixel-once'' rules of wide lines and arcs.
61 Written by Joel McCormack, Summer 1989.
66 miInitSpanGroup(SpanGroup
* spanGroup
)
70 spanGroup
->group
= NULL
;
71 spanGroup
->ymin
= MAXSHORT
;
72 spanGroup
->ymax
= MINSHORT
;
75 #define YMIN(spans) (spans->points[0].y)
76 #define YMAX(spans) (spans->points[spans->count-1].y)
79 miSubtractSpans(SpanGroup
* spanGroup
, Spans
* sub
)
81 int i
, subCount
, spansCount
;
82 int ymin
, ymax
, xmin
, xmax
;
84 DDXPointPtr subPt
, spansPt
;
85 int *subWid
, *spansWid
;
90 spans
= spanGroup
->group
;
91 for (i
= spanGroup
->count
; i
; i
--, spans
++) {
92 if (YMIN(spans
) <= ymax
&& ymin
<= YMAX(spans
)) {
93 subCount
= sub
->count
;
96 spansCount
= spans
->count
;
97 spansPt
= spans
->points
;
98 spansWid
= spans
->widths
;
101 while (spansCount
&& spansPt
->y
< subPt
->y
) {
108 while (subCount
&& subPt
->y
< spansPt
->y
) {
115 if (subPt
->y
== spansPt
->y
) {
117 xmax
= xmin
+ *subWid
;
118 if (xmin
>= spansPt
->x
+ *spansWid
|| spansPt
->x
>= xmax
) {
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));
133 *spansWid
= *spansWid
- (xmax
- spansPt
->x
);
138 if (xmax
>= spansPt
->x
+ *spansWid
) {
139 *spansWid
= xmin
- spansPt
->x
;
148 (DDXPointPtr
) realloc(spans
->points
,
151 sizeof(DDXPointRec
));
154 spansPt
= newPt
+ (spansPt
- spans
->points
);
155 spans
->points
= newPt
;
157 (int *) realloc(spans
->widths
,
159 EXTRA
) * sizeof(int));
162 spansWid
= newwid
+ (spansWid
- spans
->widths
);
163 spans
->widths
= newwid
;
166 memmove(spansPt
+ 1, spansPt
,
167 sizeof *spansPt
* (spansCount
));
168 memmove(spansWid
+ 1, spansWid
,
169 sizeof *spansWid
* (spansCount
));
172 *spansWid
= xmin
- spansPt
->x
;
175 *spansWid
= *spansWid
- (xmax
- spansPt
->x
);
189 miAppendSpans(SpanGroup
* spanGroup
, SpanGroup
* otherGroup
, Spans
* spans
)
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
);
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
);
221 miFreeSpanGroup(SpanGroup
* spanGroup
)
223 free(spanGroup
->group
);
227 QuickSortSpansX(DDXPointRec points
[], int widths
[], int numSpans
)
233 /* Always called with numSpans > 1 */
234 /* Sorts only by x, as all y should be the same */
236 #define ExchangeSpans(a, b) \
241 tpt = points[a]; points[a] = points[b]; points[b] = tpt; \
242 tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
247 /* Do insertion sort */
252 do { /* while i != numSpans */
255 /* points[i] is out of order. Move into proper location. */
259 for (j
= 0; x
>= points
[j
].x
; j
++) {
263 for (k
= i
; k
!= j
; k
--) {
264 points
[k
] = points
[k
- 1];
265 widths
[k
] = widths
[k
- 1];
270 } /* if out of order */
273 } while (i
!= numSpans
);
277 /* Choose partition element, stick in location 0 */
279 if (points
[m
].x
> points
[0].x
)
281 if (points
[m
].x
> points
[numSpans
- 1].x
)
282 ExchangeSpans(m
, numSpans
- 1);
283 if (points
[m
].x
> points
[0].x
)
287 /* Partition array */
295 } while (i
!= numSpans
&& r
->x
< x
);
305 /* Move partition element back to middle */
309 if (numSpans
- j
- 1 > 1)
310 QuickSortSpansX(&points
[j
+ 1], &widths
[j
+ 1], numSpans
- j
- 1);
312 } while (numSpans
> 1);
313 } /* QuickSortSpans */
316 UniquifySpansX(Spans
* spans
, DDXPointRec
* newPoints
, int *newWidths
)
318 int newx1
, newx2
, oldpt
, i
, y
;
319 DDXPointRec
*oldPoints
;
323 /* Always called with numSpans > 1 */
324 /* Uniquify the spans, and stash them into newPoints and newWidths. Return the
325 number of unique spans. */
327 startNewWidths
= newWidths
;
329 oldPoints
= spans
->points
;
330 oldWidths
= spans
->widths
;
333 newx1
= oldPoints
->x
;
334 newx2
= newx1
+ *oldWidths
;
336 for (i
= spans
->count
- 1; i
!= 0; i
--) {
339 oldpt
= oldPoints
->x
;
341 /* Write current span, start a new one */
342 newPoints
->x
= newx1
;
344 *newWidths
= newx2
- newx1
;
348 newx2
= oldpt
+ *oldWidths
;
351 /* extend current span, if old extends beyond new */
352 oldpt
= oldpt
+ *oldWidths
;
358 /* Write final span */
359 newPoints
->x
= newx1
;
360 *newWidths
= newx2
- newx1
;
363 return (newWidths
- startNewWidths
) + 1;
364 } /* UniquifySpansX */
367 miDisposeSpanGroup(SpanGroup
* spanGroup
)
372 for (i
= 0; i
< spanGroup
->count
; i
++) {
373 spans
= spanGroup
->group
+ i
;
380 miFillUniqueSpanGroup(DrawablePtr pDraw
, GCPtr pGC
, SpanGroup
* spanGroup
)
388 /* Outgoing spans for one big call to FillSpans */
393 if (spanGroup
->count
== 0)
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
);
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. */
410 ymin
= spanGroup
->ymin
;
411 ylength
= spanGroup
->ymax
- ymin
+ 1;
413 /* Allocate Spans for y buckets */
414 yspans
= malloc(ylength
* sizeof(Spans
));
415 ysizes
= malloc(ylength
* sizeof(int));
417 if (!yspans
|| !ysizes
) {
420 miDisposeSpanGroup(spanGroup
);
424 for (i
= 0; i
!= ylength
; i
++) {
427 yspans
[i
].points
= NULL
;
428 yspans
[i
].widths
= NULL
;
431 /* Go through every single span and put it into the correct bucket */
433 for (i
= 0, spans
= spanGroup
->group
;
434 i
!= spanGroup
->count
; i
++, spans
++) {
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
]);
444 if (newspans
->count
== ysizes
[index
]) {
445 DDXPointPtr newpoints
;
448 ysizes
[index
] = (ysizes
[index
] + 8) * 2;
449 newpoints
= (DDXPointPtr
) realloc(newspans
->points
,
451 sizeof(DDXPointRec
));
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
);
464 miDisposeSpanGroup(spanGroup
);
467 newspans
->points
= newpoints
;
468 newspans
->widths
= newwidths
;
470 newspans
->points
[newspans
->count
] = *points
;
471 newspans
->widths
[newspans
->count
] = *widths
;
473 } /* if y value of span in range */
474 } /* for j through spans */
475 count
+= spans
->count
;
477 spans
->points
= NULL
;
479 spans
->widths
= NULL
;
480 } /* for i thorough Spans */
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
);
497 for (i
= 0; i
!= ylength
; i
++) {
498 int ycount
= yspans
[i
].count
;
502 QuickSortSpansX(yspans
[i
].points
, yspans
[i
].widths
, ycount
);
503 count
+= UniquifySpansX
504 (&(yspans
[i
]), &(points
[count
]), &(widths
[count
]));
507 points
[count
] = yspans
[i
].points
[0];
508 widths
[count
] = yspans
[i
].widths
[0];
511 free(yspans
[i
].points
);
512 free(yspans
[i
].widths
);
516 (*pGC
->ops
->FillSpans
) (pDraw
, pGC
, count
, points
, widths
, TRUE
);
520 free(ysizes
); /* use (DE)xalloc for these? */
523 spanGroup
->count
= 0;
524 spanGroup
->ymin
= MAXSHORT
;
525 spanGroup
->ymax
= MINSHORT
;