Debian Codegraph @

nx-X11/lib/src/PolyReg.c

raw
1 /************************************************************************
2
3 Copyright 1987, 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
26 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
27
28 All Rights Reserved
29
30 Permission to use, copy, modify, and distribute this software and its
31 documentation for any purpose and without fee is hereby granted,
32 provided that the above copyright notice appear in all copies and that
33 both that copyright notice and this permission notice appear in
34 supporting documentation, and that the name of Digital not be
35 used in advertising or publicity pertaining to distribution of the
36 software without specific, written prior permission.
37
38 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
39 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
40 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
41 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
42 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
43 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
44 SOFTWARE.
45
46 ************************************************************************/
47
48 #define LARGE_COORDINATE 1000000
49 #define SMALL_COORDINATE -LARGE_COORDINATE
50
51 #ifdef HAVE_CONFIG_H
52 #include <config.h>
53 #endif
54 #include "Xlibint.h"
55 #include "Xutil.h"
56 #include <nx-X11/Xregion.h>
57 #include "poly.h"
58 #include "reallocarray.h"
59
60 /*
61 * InsertEdgeInET
62 *
63 * Insert the given edge into the edge table.
64 * First we must find the correct bucket in the
65 * Edge table, then find the right slot in the
66 * bucket. Finally, we can insert it.
67 *
68 */
69 static void
70 InsertEdgeInET(
71 EdgeTable *ET,
72 EdgeTableEntry *ETE,
73 int scanline,
74 ScanLineListBlock **SLLBlock,
75 int *iSLLBlock)
76 {
77 register EdgeTableEntry *start, *prev;
78 register ScanLineList *pSLL, *pPrevSLL;
79 ScanLineListBlock *tmpSLLBlock;
80
81 /*
82 * find the right bucket to put the edge into
83 */
84 pPrevSLL = &ET->scanlines;
85 pSLL = pPrevSLL->next;
86 while (pSLL && (pSLL->scanline < scanline))
87 {
88 pPrevSLL = pSLL;
89 pSLL = pSLL->next;
90 }
91
92 /*
93 * reassign pSLL (pointer to ScanLineList) if necessary
94 */
95 if ((!pSLL) || (pSLL->scanline > scanline))
96 {
97 if (*iSLLBlock > SLLSPERBLOCK-1)
98 {
99 tmpSLLBlock = Xmalloc(sizeof(ScanLineListBlock));
100 (*SLLBlock)->next = tmpSLLBlock;
101 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
102 *SLLBlock = tmpSLLBlock;
103 *iSLLBlock = 0;
104 }
105 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
106
107 pSLL->next = pPrevSLL->next;
108 pSLL->edgelist = (EdgeTableEntry *)NULL;
109 pPrevSLL->next = pSLL;
110 }
111 pSLL->scanline = scanline;
112
113 /*
114 * now insert the edge in the right bucket
115 */
116 prev = (EdgeTableEntry *)NULL;
117 start = pSLL->edgelist;
118 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
119 {
120 prev = start;
121 start = start->next;
122 }
123 ETE->next = start;
124
125 if (prev)
126 prev->next = ETE;
127 else
128 pSLL->edgelist = ETE;
129 }
130
131 /*
132 * CreateEdgeTable
133 *
134 * This routine creates the edge table for
135 * scan converting polygons.
136 * The Edge Table (ET) looks like:
137 *
138 * EdgeTable
139 * --------
140 * | ymax | ScanLineLists
141 * |scanline|-->------------>-------------->...
142 * -------- |scanline| |scanline|
143 * |edgelist| |edgelist|
144 * --------- ---------
145 * | |
146 * | |
147 * V V
148 * list of ETEs list of ETEs
149 *
150 * where ETE is an EdgeTableEntry data structure,
151 * and there is one ScanLineList per scanline at
152 * which an edge is initially entered.
153 *
154 */
155
156 static void
157 CreateETandAET(
158 register int count,
159 register XPoint *pts,
160 EdgeTable *ET,
161 EdgeTableEntry *AET,
162 register EdgeTableEntry *pETEs,
163 ScanLineListBlock *pSLLBlock)
164 {
165 register XPoint *top, *bottom;
166 register XPoint *PrevPt, *CurrPt;
167 int iSLLBlock = 0;
168 int dy;
169
170 if (count < 2) return;
171
172 /*
173 * initialize the Active Edge Table
174 */
175 AET->next = (EdgeTableEntry *)NULL;
176 AET->back = (EdgeTableEntry *)NULL;
177 AET->nextWETE = (EdgeTableEntry *)NULL;
178 AET->bres.minor_axis = SMALL_COORDINATE;
179
180 /*
181 * initialize the Edge Table.
182 */
183 ET->scanlines.next = (ScanLineList *)NULL;
184 ET->ymax = SMALL_COORDINATE;
185 ET->ymin = LARGE_COORDINATE;
186 pSLLBlock->next = (ScanLineListBlock *)NULL;
187
188 PrevPt = &pts[count-1];
189
190 /*
191 * for each vertex in the array of points.
192 * In this loop we are dealing with two vertices at
193 * a time -- these make up one edge of the polygon.
194 */
195 while (count--)
196 {
197 CurrPt = pts++;
198
199 /*
200 * find out which point is above and which is below.
201 */
202 if (PrevPt->y > CurrPt->y)
203 {
204 bottom = PrevPt, top = CurrPt;
205 pETEs->ClockWise = 0;
206 }
207 else
208 {
209 bottom = CurrPt, top = PrevPt;
210 pETEs->ClockWise = 1;
211 }
212
213 /*
214 * don't add horizontal edges to the Edge table.
215 */
216 if (bottom->y != top->y)
217 {
218 pETEs->ymax = bottom->y-1; /* -1 so we don't get last scanline */
219
220 /*
221 * initialize integer edge algorithm
222 */
223 dy = bottom->y - top->y;
224 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
225
226 InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
227
228 if (PrevPt->y > ET->ymax)
229 ET->ymax = PrevPt->y;
230 if (PrevPt->y < ET->ymin)
231 ET->ymin = PrevPt->y;
232 pETEs++;
233 }
234
235 PrevPt = CurrPt;
236 }
237 }
238
239 /*
240 * loadAET
241 *
242 * This routine moves EdgeTableEntries from the
243 * EdgeTable into the Active Edge Table,
244 * leaving them sorted by smaller x coordinate.
245 *
246 */
247
248 static void
249 loadAET(
250 register EdgeTableEntry *AET,
251 register EdgeTableEntry *ETEs)
252 {
253 register EdgeTableEntry *pPrevAET;
254 register EdgeTableEntry *tmp;
255
256 pPrevAET = AET;
257 AET = AET->next;
258 while (ETEs)
259 {
260 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
261 {
262 pPrevAET = AET;
263 AET = AET->next;
264 }
265 tmp = ETEs->next;
266 ETEs->next = AET;
267 if (AET)
268 AET->back = ETEs;
269 ETEs->back = pPrevAET;
270 pPrevAET->next = ETEs;
271 pPrevAET = ETEs;
272
273 ETEs = tmp;
274 }
275 }
276
277 /*
278 * computeWAET
279 *
280 * This routine links the AET by the
281 * nextWETE (winding EdgeTableEntry) link for
282 * use by the winding number rule. The final
283 * Active Edge Table (AET) might look something
284 * like:
285 *
286 * AET
287 * ---------- --------- ---------
288 * |ymax | |ymax | |ymax |
289 * | ... | |... | |... |
290 * |next |->|next |->|next |->...
291 * |nextWETE| |nextWETE| |nextWETE|
292 * --------- --------- ^--------
293 * | | |
294 * V-------------------> V---> ...
295 *
296 */
297 static void
298 computeWAET(
299 register EdgeTableEntry *AET)
300 {
301 register EdgeTableEntry *pWETE;
302 register int inside = 1;
303 register int isInside = 0;
304
305 AET->nextWETE = (EdgeTableEntry *)NULL;
306 pWETE = AET;
307 AET = AET->next;
308 while (AET)
309 {
310 if (AET->ClockWise)
311 isInside++;
312 else
313 isInside--;
314
315 if ((!inside && !isInside) ||
316 ( inside && isInside))
317 {
318 pWETE->nextWETE = AET;
319 pWETE = AET;
320 inside = !inside;
321 }
322 AET = AET->next;
323 }
324 pWETE->nextWETE = (EdgeTableEntry *)NULL;
325 }
326
327 /*
328 * InsertionSort
329 *
330 * Just a simple insertion sort using
331 * pointers and back pointers to sort the Active
332 * Edge Table.
333 *
334 */
335
336 static int
337 InsertionSort(
338 register EdgeTableEntry *AET)
339 {
340 register EdgeTableEntry *pETEchase;
341 register EdgeTableEntry *pETEinsert;
342 register EdgeTableEntry *pETEchaseBackTMP;
343 register int changed = 0;
344
345 AET = AET->next;
346 while (AET)
347 {
348 pETEinsert = AET;
349 pETEchase = AET;
350 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
351 pETEchase = pETEchase->back;
352
353 AET = AET->next;
354 if (pETEchase != pETEinsert)
355 {
356 pETEchaseBackTMP = pETEchase->back;
357 pETEinsert->back->next = AET;
358 if (AET)
359 AET->back = pETEinsert->back;
360 pETEinsert->next = pETEchase;
361 pETEchase->back->next = pETEinsert;
362 pETEchase->back = pETEinsert;
363 pETEinsert->back = pETEchaseBackTMP;
364 changed = 1;
365 }
366 }
367 return(changed);
368 }
369
370 /*
371 * Clean up our act.
372 */
373 static void
374 FreeStorage(
375 register ScanLineListBlock *pSLLBlock)
376 {
377 register ScanLineListBlock *tmpSLLBlock;
378
379 while (pSLLBlock)
380 {
381 tmpSLLBlock = pSLLBlock->next;
382 Xfree(pSLLBlock);
383 pSLLBlock = tmpSLLBlock;
384 }
385 }
386
387 /*
388 * Create an array of rectangles from a list of points.
389 * If indeed these things (POINTS, RECTS) are the same,
390 * then this proc is still needed, because it allocates
391 * storage for the array, which was allocated on the
392 * stack by the calling procedure.
393 *
394 */
395 static int PtsToRegion(
396 register int numFullPtBlocks,
397 register int iCurPtBlock,
398 POINTBLOCK *FirstPtBlock,
399 REGION *reg)
400 {
401 register BOX *rects;
402 register XPoint *pts;
403 register POINTBLOCK *CurPtBlock;
404 register int i;
405 register BOX *extents;
406 register int numRects;
407 BOX *prevRects = reg->rects;
408
409 extents = &reg->extents;
410
411 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
412
413 if (!(reg->rects = Xreallocarray(reg->rects, numRects, sizeof(BOX)))) {
414 Xfree(prevRects);
415 return(0);
416 }
417
418 reg->size = numRects;
419 CurPtBlock = FirstPtBlock;
420 rects = reg->rects - 1;
421 numRects = 0;
422 extents->x1 = MAXSHORT, extents->x2 = MINSHORT;
423
424 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
425 /* the loop uses 2 points per iteration */
426 i = NUMPTSTOBUFFER >> 1;
427 if (!numFullPtBlocks)
428 i = iCurPtBlock >> 1;
429 for (pts = CurPtBlock->pts; i--; pts += 2) {
430 if (pts->x == pts[1].x)
431 continue;
432 if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&
433 pts[1].x == rects->x2 &&
434 (numRects == 1 || rects[-1].y1 != rects->y1) &&
435 (i && pts[2].y > pts[1].y)) {
436 rects->y2 = pts[1].y + 1;
437 continue;
438 }
439 numRects++;
440 rects++;
441 rects->x1 = pts->x; rects->y1 = pts->y;
442 rects->x2 = pts[1].x; rects->y2 = pts[1].y + 1;
443 if (rects->x1 < extents->x1)
444 extents->x1 = rects->x1;
445 if (rects->x2 > extents->x2)
446 extents->x2 = rects->x2;
447 }
448 CurPtBlock = CurPtBlock->next;
449 }
450
451 if (numRects) {
452 extents->y1 = reg->rects->y1;
453 extents->y2 = rects->y2;
454 } else {
455 extents->x1 = 0;
456 extents->y1 = 0;
457 extents->x2 = 0;
458 extents->y2 = 0;
459 }
460 reg->numRects = numRects;
461
462 return(TRUE);
463 }
464
465 /*
466 * polytoregion
467 *
468 * Scan converts a polygon by returning a run-length
469 * encoding of the resultant bitmap -- the run-length
470 * encoding is in the form of an array of rectangles.
471 */
472 Region
473 XPolygonRegion(
474 XPoint *Pts, /* the pts */
475 int Count, /* number of pts */
476 int rule) /* winding rule */
477 {
478 Region region;
479 register EdgeTableEntry *pAET; /* Active Edge Table */
480 register int y; /* current scanline */
481 register int iPts = 0; /* number of pts in buffer */
482 register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
483 register ScanLineList *pSLL; /* current scanLineList */
484 register XPoint *pts; /* output buffer */
485 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
486 EdgeTable ET; /* header node for ET */
487 EdgeTableEntry AET; /* header node for AET */
488 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
489 ScanLineListBlock SLLBlock; /* header for scanlinelist */
490 int fixWAET = FALSE;
491 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
492 POINTBLOCK *tmpPtBlock;
493 int numFullPtBlocks = 0;
494
495 if (! (region = XCreateRegion())) return (Region) NULL;
496
497 /* special case a rectangle */
498 pts = Pts;
499 if (((Count == 4) ||
500 ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
501 (((pts[0].y == pts[1].y) &&
502 (pts[1].x == pts[2].x) &&
503 (pts[2].y == pts[3].y) &&
504 (pts[3].x == pts[0].x)) ||
505 ((pts[0].x == pts[1].x) &&
506 (pts[1].y == pts[2].y) &&
507 (pts[2].x == pts[3].x) &&
508 (pts[3].y == pts[0].y)))) {
509 region->extents.x1 = min(pts[0].x, pts[2].x);
510 region->extents.y1 = min(pts[0].y, pts[2].y);
511 region->extents.x2 = max(pts[0].x, pts[2].x);
512 region->extents.y2 = max(pts[0].y, pts[2].y);
513 if ((region->extents.x1 != region->extents.x2) &&
514 (region->extents.y1 != region->extents.y2)) {
515 region->numRects = 1;
516 *(region->rects) = region->extents;
517 }
518 return(region);
519 }
520
521 if (Count < 2) return region;
522
523 if (! (pETEs = Xmallocarray(Count, sizeof(EdgeTableEntry)))) {
524 XDestroyRegion(region);
525 return (Region) NULL;
526 }
527
528 pts = FirstPtBlock.pts;
529 CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
530 pSLL = ET.scanlines.next;
531 curPtBlock = &FirstPtBlock;
532
533 if (rule == EvenOddRule) {
534 /*
535 * for each scanline
536 */
537 for (y = ET.ymin; y < ET.ymax; y++) {
538 /*
539 * Add a new edge to the active edge table when we
540 * get to the next edge.
541 */
542 if (pSLL != NULL && y == pSLL->scanline) {
543 loadAET(&AET, pSLL->edgelist);
544 pSLL = pSLL->next;
545 }
546 pPrevAET = &AET;
547 pAET = AET.next;
548
549 /*
550 * for each active edge
551 */
552 while (pAET) {
553 pts->x = pAET->bres.minor_axis, pts->y = y;
554 pts++, iPts++;
555
556 /*
557 * send out the buffer
558 */
559 if (iPts == NUMPTSTOBUFFER) {
560 tmpPtBlock = Xmalloc(sizeof(POINTBLOCK));
561 curPtBlock->next = tmpPtBlock;
562 curPtBlock = tmpPtBlock;
563 pts = curPtBlock->pts;
564 numFullPtBlocks++;
565 iPts = 0;
566 }
567 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
568 }
569 (void) InsertionSort(&AET);
570 }
571 }
572 else {
573 /*
574 * for each scanline
575 */
576 for (y = ET.ymin; y < ET.ymax; y++) {
577 /*
578 * Add a new edge to the active edge table when we
579 * get to the next edge.
580 */
581 if (pSLL != NULL && y == pSLL->scanline) {
582 loadAET(&AET, pSLL->edgelist);
583 computeWAET(&AET);
584 pSLL = pSLL->next;
585 }
586 pPrevAET = &AET;
587 pAET = AET.next;
588 pWETE = pAET;
589
590 /*
591 * for each active edge
592 */
593 while (pAET) {
594 /*
595 * add to the buffer only those edges that
596 * are in the Winding active edge table.
597 */
598 if (pWETE == pAET) {
599 pts->x = pAET->bres.minor_axis, pts->y = y;
600 pts++, iPts++;
601
602 /*
603 * send out the buffer
604 */
605 if (iPts == NUMPTSTOBUFFER) {
606 tmpPtBlock = Xmalloc(sizeof(POINTBLOCK));
607 curPtBlock->next = tmpPtBlock;
608 curPtBlock = tmpPtBlock;
609 pts = curPtBlock->pts;
610 numFullPtBlocks++; iPts = 0;
611 }
612 pWETE = pWETE->nextWETE;
613 }
614 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
615 }
616
617 /*
618 * recompute the winding active edge table if
619 * we just resorted or have exited an edge.
620 */
621 if (InsertionSort(&AET) || fixWAET) {
622 computeWAET(&AET);
623 fixWAET = FALSE;
624 }
625 }
626 }
627 FreeStorage(SLLBlock.next);
628 (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
629 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
630 tmpPtBlock = curPtBlock->next;
631 Xfree(curPtBlock);
632 curPtBlock = tmpPtBlock;
633 }
634 Xfree(pETEs);
635 return(region);
636 }