1 /* This file is part of the GNU libxmi package.
2
3 Copyright (C) 1985, 1986, 1987, 1988, 1989, X Consortium. For an
4 associated permission notice, see the accompanying file README-X.
5
6 GNU enhancements Copyright (C) 1998, 1999, 2000, 2005, Free Software
7 Foundation, Inc.
8
9 The GNU libxmi package is free software. You may redistribute it
10 and/or modify it under the terms of the GNU General Public License as
11 published by the Free Software foundation; either version 2, or (at your
12 option) any later version.
13
14 The GNU libxmi package is distributed in the hope that it will be
15 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 General Public License for more details.
18
19 You should have received a copy of the GNU General Public License along
20 with the GNU plotutils package; see the file COPYING. If not, write to
21 the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor,
22 Boston, MA 02110-1301, USA. */
23
24 /* This module provides several public functions: miNewPaintedSet(),
25 miAddSpansToPaintedSet(), miUniquifyPaintedSet(), miClearPaintedSet(),
26 miDeletePaintedSet(). They maintain a structure called a miPaintedSet,
27 which is essentially an array of SpanGroup structures, one per pixel
28 value. A SpanGroup is essentially an unsorted list of Spans's. A Spans
29 is a list of spans (i.e. horizontal ranges) of miPoints, sorted so that
30 the starting points have increasing y-values. See mi_spans.h.
31
32 Internally, each libxmi drawing function paints to a miPaintedSet by
33 calling miAddSpansToPaintedSet() on one or more Spans's. This function
34 adds a Spans to a miPaintedSet, being careful first to remove each from
35 the miPaintedSet each pixel in the Spans, if it has previously been
36 painted another color. However, for efficiency it does not check
37 whether a pixel in the Spans has been previously painted the same color.
38 So while the drawing function is being called, the Spans in any one of
39 the PaintedSet's SpanGroups may overlap. But different SpanGroups do
40 not overlap. That is an invariant.
41
42 After all calls to miAddSpansToPaintedSet() are completed, duplicate
43 pixels are resolved by invoking miUniquifyPaintedSet(). That takes
44 place in the API wrappers in mi_api.c, just before the drawing function
45 returns.
46
47 The function miCopyPaintedSetToCanvas(), in mi_canvas.c, can copy the
48 contents of a miPaintedSet, i.e. its spans of painted miPoints, to a
49 miCanvas structure. Sophisticated pixel merging is supported. It would
50 be easy to write other functions that copy pixels out of a
51 miPaintedSet. */
52
53 /* Original version written by Joel McCormack, Summer 1989.
54 Hacked by Robert S. Maier, 1998-1999. */
55
56 #include "sys-defines.h"
57 #include "extern.h"
58
59 #include "xmi.h"
60 #include "mi_spans.h"
61 #include "mi_api.h"
62
63 /* spans in a Spans are sorted by y, so these give ymin, ymax for a
64 nonempty Spans */
65 #define YMIN(spans) (spans->points[0].y)
66 #define YMAX(spans) (spans->points[spans->count-1].y)
67
68 /* internal functions */
69 static SpanGroup * miNewSpanGroup (miPixel pixel);
70 static int miUniquifySpansX (const Spans *spans, miPoint *newPoints, unsigned int *newWidths);
71 static void miAddSpansToSpanGroup (const Spans *spans, SpanGroup *spanGroup);
72 static void miDeleteSpanGroup (SpanGroup *spanGroup);
73 static void miQuickSortSpansX (miPoint *points, unsigned int *widths, int numSpans);
74 static void miSubtractSpans (SpanGroup *spanGroup, const Spans *sub);
75 static void miUniquifySpanGroup (SpanGroup *spanGroup);
76
77
78
79 /* The following functions are the public functions of this module. */
80
81 miPaintedSet *
miNewPaintedSet(void)82 miNewPaintedSet (void)
83 {
84 miPaintedSet *paintedSet;
85
86 paintedSet = (miPaintedSet *)mi_xmalloc (sizeof(miPaintedSet));
87 paintedSet->groups = (SpanGroup **)NULL; /* pointer-to-SpanGroup slots */
88 paintedSet->size = 0; /* slots allocated */
89 paintedSet->ngroups = 0; /* slots filled */
90
91 return paintedSet;
92 }
93
94 /* Add a Spans to a miPaintedSet's SpanGroup for a specified pixel values,
95 and also subtract it from the SpanGroups for all other pixel values. */
96 void
miAddSpansToPaintedSet(const Spans * spans,miPaintedSet * paintedSet,miPixel pixel)97 miAddSpansToPaintedSet (const Spans *spans, miPaintedSet *paintedSet, miPixel pixel)
98 {
99 bool found = false;
100 int i;
101 SpanGroup *spanGroup;
102
103 if (spans->count == 0)
104 return;
105
106 for (i = 0; i < paintedSet->ngroups; i++)
107 {
108 miPixel stored_pixel;
109
110 stored_pixel = paintedSet->groups[i]->pixel;
111 if (MI_SAME_PIXEL(pixel, stored_pixel))
112 {
113 found = true; /* have a spanGroup for this pixel value */
114 break;
115 }
116 }
117 if (!found)
118 {
119 if (paintedSet->ngroups == paintedSet->size)
120 /* expand array of SpanGroups */
121 {
122 int old_size = paintedSet->size;
123 int new_size = 2 * (old_size + 8);
124
125 if (old_size == 0)
126 paintedSet->groups = (SpanGroup **)
127 mi_xmalloc(new_size * sizeof(SpanGroup *));
128 else
129 paintedSet->groups = (SpanGroup **)
130 mi_xrealloc(paintedSet->groups, new_size * sizeof(SpanGroup *));
131 paintedSet->size = new_size;
132 }
133
134 /* create a SpanGroup for this pixel value */
135 i = paintedSet->ngroups;
136 paintedSet->groups[i] = miNewSpanGroup (pixel);
137 paintedSet->ngroups++;
138 }
139
140 spanGroup = paintedSet->groups[i];
141 miAddSpansToSpanGroup (spans, spanGroup);
142
143 /* subtract Spans from all other SpanGroups */
144 for (i = 0; i < paintedSet->ngroups; i++)
145 {
146 SpanGroup *otherGroup;
147
148 otherGroup = paintedSet->groups[i];
149 if (otherGroup == spanGroup)
150 continue;
151 miSubtractSpans (otherGroup, spans);
152 }
153 }
154
155 /* Deallocate all of a miPaintedSet's SpanGroups, including the points and
156 width arrays that are part of its component Spans's. So it will
157 effectively become the empty set, as if it had been newly created. */
158 void
miClearPaintedSet(miPaintedSet * paintedSet)159 miClearPaintedSet (miPaintedSet *paintedSet)
160 {
161 int i;
162
163 if (paintedSet == (miPaintedSet *)NULL)
164 return;
165
166 for (i = 0; i < paintedSet->ngroups; i++)
167 miDeleteSpanGroup (paintedSet->groups[i]);
168 if (paintedSet->size > 0)
169 free (paintedSet->groups);
170 paintedSet->size = 0; /* slots allocated */
171 paintedSet->ngroups = 0; /* slots filled */
172 }
173
174 /* Deallocate a miPaintedSet, including the points and width arrays that
175 are part of its component Spans's. */
176 void
miDeletePaintedSet(miPaintedSet * paintedSet)177 miDeletePaintedSet (miPaintedSet *paintedSet)
178 {
179 int i;
180
181 if (paintedSet == (miPaintedSet *)NULL)
182 return;
183
184 for (i = 0; i < paintedSet->ngroups; i++)
185 miDeleteSpanGroup (paintedSet->groups[i]);
186
187 if (paintedSet->size > 0)
188 free (paintedSet->groups);
189 free (paintedSet);
190 }
191
192 /* `Uniquify' a miPaintedSet, i.e. uniquify each of its SpanGroups (see
193 below). */
194 void
miUniquifyPaintedSet(miPaintedSet * paintedSet)195 miUniquifyPaintedSet (miPaintedSet *paintedSet)
196 {
197 int i;
198
199 if (paintedSet == (miPaintedSet *)NULL)
200 return;
201
202 for (i = 0; i < paintedSet->ngroups; i++)
203 {
204 if (paintedSet->groups[i]->count > 0)
205 {
206 miUniquifySpanGroup (paintedSet->groups[i]);
207 }
208 }
209 }
210
211
212 /* Create and initialize a SpanGroup, i.e. an unsorted list of Spans's. */
213 static SpanGroup *
miNewSpanGroup(miPixel pixel)214 miNewSpanGroup (miPixel pixel)
215 {
216 SpanGroup *spanGroup;
217
218 spanGroup = (SpanGroup *)mi_xmalloc (sizeof(SpanGroup));
219 spanGroup->pixel = pixel; /* pixel to be used */
220 spanGroup->size = 0; /* slots allocated */
221 spanGroup->count = 0; /* slots filled */
222 spanGroup->group = (Spans *)NULL; /* slots for Spans's */
223 spanGroup->ymin = INT_MAX; /* min over slots */
224 spanGroup->ymax = INT_MIN; /* max over slots */
225
226 return spanGroup;
227 }
228
229 /* Add a Spans to a SpanGroup, by tacking it on the end; update SpanGroup's
230 ymin, ymax. */
231 static void
miAddSpansToSpanGroup(const Spans * spans,SpanGroup * spanGroup)232 miAddSpansToSpanGroup (const Spans *spans, SpanGroup *spanGroup)
233 {
234 int ymin, ymax;
235
236 if (spans->count == 0)
237 return;
238 if (spanGroup->size == spanGroup->count)
239 /* expand SpanGroup */
240 {
241 spanGroup->size = (spanGroup->size + 8) * 2;
242 spanGroup->group = (Spans *)
243 mi_xrealloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
244 }
245
246 /* tack Spans onto end of SpanGroup, update SpanGroup's ymin and ymax */
247 spanGroup->group[spanGroup->count] = *spans;
248 (spanGroup->count)++;
249 ymin = YMIN(spans);
250 if (ymin < spanGroup->ymin)
251 spanGroup->ymin = ymin;
252 ymax = YMAX(spans);
253 if (ymax > spanGroup->ymax)
254 spanGroup->ymax = ymax;
255 }
256
257 /* Delete a SpanGroup, including the point and width arrays that are part
258 of each Spans. */
259 static void
miDeleteSpanGroup(SpanGroup * spanGroup)260 miDeleteSpanGroup (SpanGroup *spanGroup)
261 {
262 int i;
263
264 if (spanGroup == (SpanGroup *)NULL)
265 return;
266
267 for (i = 0; i < spanGroup->count; i++)
268 {
269 /* free spanGroup->group[i], which is a Spans */
270 free (spanGroup->group[i].points);
271 free (spanGroup->group[i].widths);
272 }
273 if (spanGroup->group)
274 free (spanGroup->group);
275 free (spanGroup);
276 }
277
278 /* Subtract a Spans from a SpanGroup, i.e. from each of its Spans's; update
279 SpanGroup's ymin, ymax. */
280 static void
miSubtractSpans(SpanGroup * spanGroup,const Spans * sub)281 miSubtractSpans (SpanGroup *spanGroup, const Spans *sub)
282 {
283 int i, subCount, spansCount;
284 int ymin, ymax, xmin, xmax;
285 Spans *spans;
286 miPoint *subPt, *spansPt;
287 unsigned int *subWid, *spansWid;
288 int extra;
289 bool gross_change = false;
290
291 if (sub->count == 0) /* nothing to do */
292 return;
293
294 /* y range of Spans to be subtracted */
295 ymin = YMIN(sub);
296 ymax = YMAX(sub);
297
298 /* loop through all Spans's in SpanGroup */
299 spans = spanGroup->group;
300 for (i = spanGroup->count; i > 0; i--, spans++)
301 {
302 if (spans->count == 0)
303 continue;
304
305 /* look only at Spans's with y ranges that overlap with `sub' */
306 if (YMIN(spans) <= ymax && ymin <= YMAX(spans))
307 {
308 /* count, start points, and widths for `sub' */
309 subCount = sub->count;
310 subPt = sub->points;
311 subWid = sub->widths;
312
313 /* count, start points, and widths for current Spans */
314 spansCount = spans->count;
315 spansPt = spans->points;
316 spansWid = spans->widths;
317
318 extra = 0; /* extra span slots available in Spans */
319 for (;;)
320 /* look at pairs of spans, one from each Spans, that have the
321 same value for y (break out when one or the other Spans is
322 exhausted) */
323 {
324 while (spansCount && spansPt->y < subPt->y)
325 {
326 spansPt++;
327 spansWid++;
328 spansCount--;
329 }
330 if (!spansCount)
331 break;
332 while (subCount && subPt->y < spansPt->y)
333 {
334 subPt++;
335 subWid++;
336 subCount--;
337 }
338 if (!subCount)
339 break;
340
341 if (subPt->y == spansPt->y)
342 /* the two spans are at same y value, analyse in detail */
343 {
344 xmin = subPt->x;
345 xmax = xmin + (int)(*subWid); /* just right of sub span */
346 if (xmin >= spansPt->x + (int)(*spansWid)
347 || spansPt->x >= xmax)
348 /* non-overlapping, do nothing */
349 {
350 ;
351 }
352 else if (xmin <= spansPt->x)
353 /* span to be subtracted begins at the same point, or
354 to the left */
355 {
356 if (xmax >= spansPt->x + (int)(*spansWid))
357 /* span to be subtracted ends at the same point,
358 or to the right; delete this span by downshifting */
359 {
360 memmove (spansPt, spansPt + 1,
361 sizeof(miPoint) * (spansCount - 1));
362 memmove (spansWid, spansWid + 1,
363 sizeof(unsigned int) * (spansCount - 1));
364 spansPt--;
365 spansWid--;
366 spans->count--;
367 extra++;
368 gross_change = true; /* span vanished */
369 }
370 else
371 /* span to be subtracted ends to the left of this
372 one's ending point; alter ending point and width */
373 {
374 *spansWid =
375 *spansWid - (unsigned int)(xmax - spansPt->x);
376 spansPt->x = xmax;
377 }
378 }
379 else
380 /* span to be subtracted overlaps with this one, and
381 begins to the right of this one */
382 {
383 if (xmax >= spansPt->x + (int)*spansWid)
384 /* span to be subtracted ends at the same point, or
385 to the right; just update width */
386 *spansWid = (unsigned int)(xmin - spansPt->x);
387 else
388 /* hard case: must split the span */
389 {
390 #define EXTRA 8
391 if (extra == 0)
392 /* reallocate; create EXTRA new span slots */
393 {
394 miPoint *newPt;
395 unsigned int *newwid;
396
397 newPt = (miPoint *)mi_xrealloc (spans->points,
398 (spans->count + EXTRA)*sizeof(miPoint));
399 spansPt = newPt + (spansPt - spans->points);
400 spans->points = newPt;
401 newwid = (unsigned int *)mi_xrealloc (spans->widths,
402 (spans->count + EXTRA)*sizeof(unsigned int));
403 spansWid = newwid + (spansWid - spans->widths);
404 spans->widths = newwid;
405 extra = EXTRA;
406 }
407
408 /* downshift; create two new spans as replacement */
409 memmove (spansPt + 1, spansPt,
410 sizeof(miPoint) * spansCount);
411 memmove (spansWid + 1, spansWid,
412 sizeof(unsigned int) * spansCount);
413 spans->count++;
414 extra--;
415 /* first new span */
416 *spansWid = (unsigned int)(xmin - spansPt->x);
417 spansWid++;
418 spansPt++;
419 /* second new span */
420 *spansWid = *spansWid - (unsigned int)(xmax - spansPt->x);
421 spansPt->x = xmax;
422 }
423 }
424 } /* end of same-value-of-y computations */
425
426 /* on to next span in the Spans */
427 spansPt++;
428 spansWid++;
429 spansCount--;
430 }
431 }
432 }
433
434 if (gross_change)
435 /* at least one span vanished; recompute SpanGroup's ymin, ymax */
436 {
437 ymax = INT_MIN;
438 ymin = INT_MAX;
439
440 /* loop through all Spans's in SpanGroup */
441 spans = spanGroup->group;
442 for (i = spanGroup->count; i > 0; i--, spans++)
443 {
444 int ymin_spans, ymax_spans;
445
446 if (spans->count == 0)
447 continue;
448 ymin_spans = YMIN(spans);
449 ymax_spans = YMAX(spans);
450 if (ymin_spans < ymin)
451 ymin = ymin_spans;
452 if (ymax_spans > ymax)
453 ymax = ymax_spans;
454 }
455
456 spanGroup->ymin = ymin;
457 spanGroup->ymax = ymax;
458 }
459 }
460
461 /* `Uniquify' a SpanGroup: merge all its Spans's into a single Spans, which
462 will be sorted on x as well as on y. */
463 static void
miUniquifySpanGroup(SpanGroup * spanGroup)464 miUniquifySpanGroup (SpanGroup *spanGroup)
465 {
466 int i;
467 Spans *spans;
468 Spans *yspans;
469 int *ysizes;
470 int ymin, ylength;
471
472 /* the new single Spans */
473 miPoint *points;
474 unsigned int *widths;
475 int count;
476
477 if (spanGroup->count == 0)
478 return;
479
480 /* Special case : ymin > ymax, so the Spans's in the SpanGroup, no matter
481 how numerous, must be empty (and can't contain point or width arrays). */
482 if (spanGroup->ymin > spanGroup->ymax)
483 {
484 spanGroup->count = 0;
485 return;
486 }
487
488 /* Yuck. Gross. Radix sort into y buckets, then sort x and uniquify */
489 /* This seems to be the fastest thing to do. I've tried sorting on
490 both x and y at the same time rather than creating into all those
491 y buckets, but it was somewhat slower. */
492
493 ymin = spanGroup->ymin;
494 ylength = spanGroup->ymax - ymin + 1;
495
496 /* allocate Spans's for y buckets (one Spans for every scanline);
497 ysizes[] is number of allocated Span slots in each bucket */
498 yspans = (Spans *)mi_xmalloc (ylength * sizeof(Spans));
499 ysizes = (int *)mi_xmalloc (ylength * sizeof(int));
500 for (i = 0; i < ylength; i++)
501 {
502 ysizes[i] = 0;
503 yspans[i].count = 0;
504 yspans[i].points = (miPoint *)NULL;
505 yspans[i].widths = (unsigned int *)NULL;
506 }
507
508 /* go through every single span and put it into the correct y bucket */
509 count = 0;
510 for (i = 0, spans = spanGroup->group;
511 i < spanGroup->count; i++, spans++)
512 {
513 int j, index;
514
515 for (j = 0, points = spans->points, widths = spans->widths;
516 j < spans->count; j++, points++, widths++)
517 {
518 index = points->y - ymin;
519 if (index >= 0 && index < ylength) /* paranoia */
520 {
521 Spans *newspans = &(yspans[index]);
522
523 if (newspans->count == ysizes[index])
524 /* expand bucket arrays by reallocating */
525 {
526 ysizes[index] = (ysizes[index] + 8) * 2;
527 newspans->points
528 = (miPoint *)mi_xrealloc (newspans->points,
529 ysizes[index] * sizeof(miPoint));
530 newspans->widths
531 = (unsigned int *)mi_xrealloc (newspans->widths,
532 ysizes[index] * sizeof(unsigned int));
533 }
534 newspans->points[newspans->count] = *points;
535 newspans->widths[newspans->count] = *widths;
536 (newspans->count)++;
537 } /* if y value of span in range */
538 } /* for j through spans */
539
540 count += spans->count;
541 } /* for i through Spans */
542 free (ysizes);
543
544 /* now sort each bucket by x and uniquify it into new Spans */
545 points = (miPoint *)mi_xmalloc (count * sizeof(miPoint));
546 widths = (unsigned int *)mi_xmalloc (count * sizeof(unsigned int));
547 count = 0;
548 for (i = 0; i < ylength; i++)
549 {
550 int ycount = yspans[i].count;
551
552 if (ycount > 0)
553 {
554 if (ycount > 1)
555 /* sort the >1 spans at this value of y */
556 {
557 miQuickSortSpansX (yspans[i].points, yspans[i].widths, ycount);
558 count += miUniquifySpansX
559 (&(yspans[i]), &(points[count]), &(widths[count]));
560 }
561 else
562 /* just a single span at this value of y */
563 {
564 points[count] = yspans[i].points[0];
565 widths[count] = yspans[i].widths[0];
566 count++;
567 }
568 free (yspans[i].points);
569 free (yspans[i].widths);
570 }
571 }
572 free (yspans);
573
574 /* free SpanGroup's original Spans's, including Span arrays */
575 for (i = 0; i < spanGroup->count; i++)
576 {
577 free (spanGroup->group[i].points);
578 free (spanGroup->group[i].widths);
579 }
580
581 /* SpanGroup now has only a single Spans */
582 spanGroup->count = 1;
583 spanGroup->group[0].points = points;
584 spanGroup->group[0].widths = widths;
585 spanGroup->group[0].count = count;
586 }
587
588
589 /* Sort each span in a Spans by x. Called only if numSpans > 1. */
590 static void
miQuickSortSpansX(miPoint * points,unsigned int * widths,int numSpans)591 miQuickSortSpansX (miPoint *points, unsigned int *widths, int numSpans)
592 {
593 int x;
594 int i, j, m;
595 miPoint *r;
596
597 #define ExchangeSpans(a, b) \
598 { \
599 miPoint tpt; \
600 unsigned int tw; \
601 \
602 tpt = points[a]; points[a] = points[b]; points[b] = tpt; \
603 tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
604 }
605
606 do
607 {
608 if (numSpans < 9)
609 /* do insertion sort */
610 {
611 int xprev;
612
613 xprev = points[0].x;
614 i = 1;
615 do /* while i != numSpans */
616 {
617 x = points[i].x;
618 if (xprev > x)
619 {
620 /* points[i] is out of order. Move into proper location. */
621 miPoint tpt;
622 unsigned int tw;
623 int k;
624
625 for (j = 0; x >= points[j].x; j++)
626 {
627 }
628 tpt = points[i];
629 tw = widths[i];
630 for (k = i; k != j; k--)
631 {
632 points[k] = points[k-1];
633 widths[k] = widths[k-1];
634 }
635 points[j] = tpt;
636 widths[j] = tw;
637 x = points[i].x;
638 } /* if out of order */
639 xprev = x;
640 i++;
641 } while (i != numSpans);
642
643 /* end of insertion sort */
644 return;
645 }
646
647 /* Choose partition element, stick in location 0 */
648 m = numSpans / 2;
649 if (points[m].x > points[0].x)
650 ExchangeSpans(m, 0);
651 if (points[m].x > points[numSpans-1].x)
652 ExchangeSpans(m, numSpans-1);
653 if (points[m].x > points[0].x)
654 ExchangeSpans(m, 0);
655 x = points[0].x;
656
657 /* Partition array */
658 i = 0;
659 j = numSpans;
660 do
661 {
662 r = &(points[i]);
663 do
664 {
665 r++;
666 i++;
667 }
668 while (i != numSpans && r->x < x)
669 ;
670 r = &(points[j]);
671 do
672 {
673 r--;
674 j--;
675 }
676 while (x < r->x);
677 if (i < j) ExchangeSpans(i, j);
678 }
679 while (i < j);
680
681 /* Move partition element back to middle */
682 ExchangeSpans(0, j);
683
684 /* Recurse */
685 if (numSpans-j-1 > 1)
686 miQuickSortSpansX (&points[j+1], &widths[j+1], numSpans-j-1);
687 numSpans = j;
688 } while (numSpans > 1);
689 }
690
691 /* Sort an unordered list of spans by y, so that it becomes a Spans. */
692 void
miQuickSortSpansY(miPoint * points,unsigned int * widths,int numSpans)693 miQuickSortSpansY (miPoint *points, unsigned int *widths, int numSpans)
694 {
695 int y;
696 int i, j, m;
697 miPoint *r;
698
699 if (numSpans <= 1) /* nothing to do */
700 return;
701
702 #define ExchangeSpans(a, b) \
703 { \
704 miPoint tpt; \
705 unsigned int tw; \
706 \
707 tpt = points[a]; points[a] = points[b]; points[b] = tpt; \
708 tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
709 }
710
711 do
712 {
713 if (numSpans < 9)
714 /* do insertion sort */
715 {
716 int yprev;
717
718 yprev = points[0].y;
719 i = 1;
720 do /* while i != numSpans */
721 {
722 y = points[i].y;
723 if (yprev > y)
724 {
725 /* points[i] is out of order. Move into proper location. */
726 miPoint tpt;
727 unsigned int tw;
728 int k;
729
730 for (j = 0; y >= points[j].y; j++)
731 {
732 }
733 tpt = points[i];
734 tw = widths[i];
735 for (k = i; k != j; k--)
736 {
737 points[k] = points[k-1];
738 widths[k] = widths[k-1];
739 }
740 points[j] = tpt;
741 widths[j] = tw;
742 y = points[i].y;
743 } /* if out of order */
744 yprev = y;
745 i++;
746 } while (i != numSpans);
747
748 /* end of insertion sort */
749 return;
750 }
751
752 /* Choose partition element, stick in location 0 */
753 m = numSpans / 2;
754 if (points[m].y > points[0].y)
755 ExchangeSpans(m, 0);
756 if (points[m].y > points[numSpans-1].y)
757 ExchangeSpans(m, numSpans-1);
758 if (points[m].y > points[0].y)
759 ExchangeSpans(m, 0);
760 y = points[0].y;
761
762 /* Partition array */
763 i = 0;
764 j = numSpans;
765 do
766 {
767 r = &(points[i]);
768 do
769 {
770 r++;
771 i++;
772 }
773 while (i != numSpans && r->y < y)
774 ;
775 r = &(points[j]);
776 do
777 {
778 r--;
779 j--;
780 }
781 while (y < r->y);
782 if (i < j) ExchangeSpans(i, j);
783 }
784 while (i < j);
785
786 /* Move partition element back to middle */
787 ExchangeSpans(0, j);
788
789 /* Recurse */
790 if (numSpans-j-1 > 1)
791 miQuickSortSpansY (&points[j+1], &widths[j+1], numSpans-j-1);
792 numSpans = j;
793 } while (numSpans > 1);
794 }
795
796 /* Uniquify the spans in a Spans. (Spans at each y value are assumed to
797 have been sorted on x, perhaps by calling miQuickSortSpansX() above.)
798 Also, create a new Spans: stash the uniquified spans into the previously
799 allocated arrays newPoints and newWidths. Returns the number of unique
800 spans. Called only if numSpans > 1. */
801 static int
miUniquifySpansX(const Spans * spans,miPoint * newPoints,unsigned int * newWidths)802 miUniquifySpansX (const Spans *spans, miPoint *newPoints, unsigned int *newWidths)
803 {
804 int newx1, newx2, oldpt, i, y;
805 miPoint *oldPoints;
806 unsigned int *oldWidths, *startNewWidths;
807
808 startNewWidths = newWidths;
809 oldPoints = spans->points;
810 oldWidths = spans->widths;
811 y = oldPoints->y;
812 newx1 = oldPoints->x;
813 newx2 = newx1 + (int)(*oldWidths);
814
815 for (i = spans->count - 1; i > 0; i--)
816 {
817 oldPoints++;
818 oldWidths++;
819 oldpt = oldPoints->x;
820 if (oldpt > newx2)
821 {
822 /* write current span, start a new one */
823 newPoints->x = newx1;
824 newPoints->y = y;
825 *newWidths = (unsigned int)(newx2 - newx1);
826 newPoints++;
827 newWidths++;
828 newx1 = oldpt;
829 newx2 = oldpt + (int)(*oldWidths);
830 }
831 else
832 {
833 /* extend current span, if old extends beyond new */
834 oldpt = oldpt + (int)(*oldWidths);
835 if (oldpt > newx2)
836 newx2 = oldpt;
837 }
838 }
839
840 /* write final span */
841 newPoints->x = newx1;
842 *newWidths = (unsigned int)(newx2 - newx1);
843 newPoints->y = y;
844
845 return (int)((newWidths - startNewWidths) + 1);
846 }
847