1 /* $TOG: PolyReg.c /main/15 1998/02/06 17:47:08 kaleb $ */
2 /************************************************************************
4 Copyright 1987, 1998 The Open Group
8 The above copyright notice and this permission notice shall be included in
9 all copies or substantial portions of the Software.
11 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
12 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
13 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
14 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
15 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
16 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18 Except as contained in this notice, the name of The Open Group shall not be
19 used in advertising or otherwise to promote the sale, use or other dealings
20 in this Software without prior written authorization from The Open Group.
23 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
27 Permission to use, copy, modify, and distribute this software and its
28 documentation for any purpose and without fee is hereby granted,
29 provided that the above copyright notice appear in all copies and that
30 both that copyright notice and this permission notice appear in
31 supporting documentation, and that the name of Digital not be
32 used in advertising or publicity pertaining to distribution of the
33 software without specific, written prior permission.
35 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
36 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
37 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
38 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
39 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
40 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
43 ************************************************************************/
44 /* $XFree86: xc/lib/X11/PolyReg.c,v 1.4 1998/10/03 08:41:21 dawes Exp $ */
46 #define LARGE_COORDINATE 1000000
47 #define SMALL_COORDINATE -LARGE_COORDINATE
51 #include <gdkregion.h>
52 #include "gdkregion-generic.h"
53 #include "gdkpoly-generic.h"
58 * Insert the given edge into the edge table.
59 * First we must find the correct bucket in the
60 * Edge table, then find the right slot in the
61 * bucket. Finally, we can insert it.
65 InsertEdgeInET(ET, ETE, scanline, SLLBlock, iSLLBlock)
69 ScanLineListBlock **SLLBlock;
72 EdgeTableEntry *start, *prev;
73 ScanLineList *pSLL, *pPrevSLL;
74 ScanLineListBlock *tmpSLLBlock;
77 * find the right bucket to put the edge into
79 pPrevSLL = &ET->scanlines;
80 pSLL = pPrevSLL->next;
81 while (pSLL && (pSLL->scanline < scanline))
88 * reassign pSLL (pointer to ScanLineList) if necessary
90 if ((!pSLL) || (pSLL->scanline > scanline))
92 if (*iSLLBlock > SLLSPERBLOCK-1)
95 (ScanLineListBlock *)g_malloc(sizeof(ScanLineListBlock));
96 (*SLLBlock)->next = tmpSLLBlock;
97 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
98 *SLLBlock = tmpSLLBlock;
101 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
103 pSLL->next = pPrevSLL->next;
104 pSLL->edgelist = (EdgeTableEntry *)NULL;
105 pPrevSLL->next = pSLL;
107 pSLL->scanline = scanline;
110 * now insert the edge in the right bucket
112 prev = (EdgeTableEntry *)NULL;
113 start = pSLL->edgelist;
114 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
124 pSLL->edgelist = ETE;
130 * This routine creates the edge table for
131 * scan converting polygons.
132 * The Edge Table (ET) looks like:
136 * | ymax | ScanLineLists
137 * |scanline|-->------------>-------------->...
138 * -------- |scanline| |scanline|
139 * |edgelist| |edgelist|
140 * --------- ---------
144 * list of ETEs list of ETEs
146 * where ETE is an EdgeTableEntry data structure,
147 * and there is one ScanLineList per scanline at
148 * which an edge is initially entered.
153 CreateETandAET(count, pts, ET, AET, pETEs, pSLLBlock)
158 EdgeTableEntry *pETEs;
159 ScanLineListBlock *pSLLBlock;
161 GdkPoint *top, *bottom;
162 GdkPoint *PrevPt, *CurrPt;
166 if (count < 2) return;
169 * initialize the Active Edge Table
171 AET->next = (EdgeTableEntry *)NULL;
172 AET->back = (EdgeTableEntry *)NULL;
173 AET->nextWETE = (EdgeTableEntry *)NULL;
174 AET->bres.minor_axis = SMALL_COORDINATE;
177 * initialize the Edge Table.
179 ET->scanlines.next = (ScanLineList *)NULL;
180 ET->ymax = SMALL_COORDINATE;
181 ET->ymin = LARGE_COORDINATE;
182 pSLLBlock->next = (ScanLineListBlock *)NULL;
184 PrevPt = &pts[count-1];
187 * for each vertex in the array of points.
188 * In this loop we are dealing with two vertices at
189 * a time -- these make up one edge of the polygon.
196 * find out which point is above and which is below.
198 if (PrevPt->y > CurrPt->y)
200 bottom = PrevPt, top = CurrPt;
201 pETEs->ClockWise = 0;
205 bottom = CurrPt, top = PrevPt;
206 pETEs->ClockWise = 1;
210 * don't add horizontal edges to the Edge table.
212 if (bottom->y != top->y)
214 pETEs->ymax = bottom->y-1; /* -1 so we don't get last scanline */
217 * initialize integer edge algorithm
219 dy = bottom->y - top->y;
220 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
222 InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
224 if (PrevPt->y > ET->ymax)
225 ET->ymax = PrevPt->y;
226 if (PrevPt->y < ET->ymin)
227 ET->ymin = PrevPt->y;
238 * This routine moves EdgeTableEntries from the
239 * EdgeTable into the Active Edge Table,
240 * leaving them sorted by smaller x coordinate.
246 EdgeTableEntry *AET, *ETEs;
248 EdgeTableEntry *pPrevAET;
255 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
264 ETEs->back = pPrevAET;
265 pPrevAET->next = ETEs;
275 * This routine links the AET by the
276 * nextWETE (winding EdgeTableEntry) link for
277 * use by the winding number rule. The final
278 * Active Edge Table (AET) might look something
282 * ---------- --------- ---------
283 * |ymax | |ymax | |ymax |
284 * | ... | |... | |... |
285 * |next |->|next |->|next |->...
286 * |nextWETE| |nextWETE| |nextWETE|
287 * --------- --------- ^--------
289 * V-------------------> V---> ...
296 EdgeTableEntry *pWETE;
300 AET->nextWETE = (EdgeTableEntry *)NULL;
310 if ((!inside && !isInside) ||
311 ( inside && isInside))
313 pWETE->nextWETE = AET;
319 pWETE->nextWETE = (EdgeTableEntry *)NULL;
325 * Just a simple insertion sort using
326 * pointers and back pointers to sort the Active
335 EdgeTableEntry *pETEchase;
336 EdgeTableEntry *pETEinsert;
337 EdgeTableEntry *pETEchaseBackTMP;
345 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
346 pETEchase = pETEchase->back;
349 if (pETEchase != pETEinsert)
351 pETEchaseBackTMP = pETEchase->back;
352 pETEinsert->back->next = AET;
354 AET->back = pETEinsert->back;
355 pETEinsert->next = pETEchase;
356 pETEchase->back->next = pETEinsert;
357 pETEchase->back = pETEinsert;
358 pETEinsert->back = pETEchaseBackTMP;
369 FreeStorage(pSLLBlock)
370 ScanLineListBlock *pSLLBlock;
372 ScanLineListBlock *tmpSLLBlock;
376 tmpSLLBlock = pSLLBlock->next;
378 pSLLBlock = tmpSLLBlock;
383 * Create an array of rectangles from a list of points.
384 * If indeed these things (POINTS, RECTS) are the same,
385 * then this proc is still needed, because it allocates
386 * storage for the array, which was allocated on the
387 * stack by the calling procedure.
390 static int PtsToRegion(numFullPtBlocks, iCurPtBlock, FirstPtBlock, reg)
391 int numFullPtBlocks, iCurPtBlock;
392 POINTBLOCK *FirstPtBlock;
397 POINTBLOCK *CurPtBlock;
399 GdkRegionBox *extents;
402 extents = ®->extents;
404 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
406 reg->rects = g_renew (GdkRegionBox, reg->rects, numRects);
408 reg->size = numRects;
409 CurPtBlock = FirstPtBlock;
410 rects = reg->rects - 1;
412 extents->x1 = G_MAXSHORT, extents->x2 = G_MINSHORT;
414 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
415 /* the loop uses 2 points per iteration */
416 i = NUMPTSTOBUFFER >> 1;
417 if (!numFullPtBlocks)
418 i = iCurPtBlock >> 1;
419 for (pts = CurPtBlock->pts; i--; pts += 2) {
420 if (pts->x == pts[1].x)
422 if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&
423 pts[1].x == rects->x2 &&
424 (numRects == 1 || rects[-1].y1 != rects->y1) &&
425 (i && pts[2].y > pts[1].y)) {
426 rects->y2 = pts[1].y + 1;
431 rects->x1 = pts->x; rects->y1 = pts->y;
432 rects->x2 = pts[1].x; rects->y2 = pts[1].y + 1;
433 if (rects->x1 < extents->x1)
434 extents->x1 = rects->x1;
435 if (rects->x2 > extents->x2)
436 extents->x2 = rects->x2;
438 CurPtBlock = CurPtBlock->next;
442 extents->y1 = reg->rects->y1;
443 extents->y2 = rects->y2;
450 reg->numRects = numRects;
458 * Scan converts a polygon by returning a run-length
459 * encoding of the resultant bitmap -- the run-length
460 * encoding is in the form of an array of rectangles.
463 gdk_region_polygon(GdkPoint *Pts, gint Count, GdkFillRule rule)
466 EdgeTableEntry *pAET; /* Active Edge Table */
467 int y; /* current scanline */
468 int iPts = 0; /* number of pts in buffer */
469 EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
470 ScanLineList *pSLL; /* current scanLineList */
471 GdkPoint *pts; /* output buffer */
472 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
473 EdgeTable ET; /* header node for ET */
474 EdgeTableEntry AET; /* header node for AET */
475 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
476 ScanLineListBlock SLLBlock; /* header for scanlinelist */
478 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
479 POINTBLOCK *tmpPtBlock;
480 int numFullPtBlocks = 0;
482 region = gdk_region_new ();
484 /* special case a rectangle */
487 ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
488 (((pts[0].y == pts[1].y) &&
489 (pts[1].x == pts[2].x) &&
490 (pts[2].y == pts[3].y) &&
491 (pts[3].x == pts[0].x)) ||
492 ((pts[0].x == pts[1].x) &&
493 (pts[1].y == pts[2].y) &&
494 (pts[2].x == pts[3].x) &&
495 (pts[3].y == pts[0].y)))) {
496 region->extents.x1 = MIN(pts[0].x, pts[2].x);
497 region->extents.y1 = MIN(pts[0].y, pts[2].y);
498 region->extents.x2 = MAX(pts[0].x, pts[2].x);
499 region->extents.y2 = MAX(pts[0].y, pts[2].y);
500 if ((region->extents.x1 != region->extents.x2) &&
501 (region->extents.y1 != region->extents.y2)) {
502 region->numRects = 1;
503 *(region->rects) = region->extents;
508 pETEs = g_new (EdgeTableEntry, Count);
510 pts = FirstPtBlock.pts;
511 CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
512 pSLL = ET.scanlines.next;
513 curPtBlock = &FirstPtBlock;
515 if (rule == GDK_EVEN_ODD_RULE) {
519 for (y = ET.ymin; y < ET.ymax; y++) {
521 * Add a new edge to the active edge table when we
522 * get to the next edge.
524 if (pSLL != NULL && y == pSLL->scanline) {
525 loadAET(&AET, pSLL->edgelist);
532 * for each active edge
535 pts->x = pAET->bres.minor_axis, pts->y = y;
539 * send out the buffer
541 if (iPts == NUMPTSTOBUFFER) {
542 tmpPtBlock = (POINTBLOCK *)g_malloc(sizeof(POINTBLOCK));
543 tmpPtBlock->next = NULL;
544 curPtBlock->next = tmpPtBlock;
545 curPtBlock = tmpPtBlock;
546 pts = curPtBlock->pts;
550 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
552 (void) InsertionSort(&AET);
559 for (y = ET.ymin; y < ET.ymax; y++) {
561 * Add a new edge to the active edge table when we
562 * get to the next edge.
564 if (pSLL != NULL && y == pSLL->scanline) {
565 loadAET(&AET, pSLL->edgelist);
574 * for each active edge
578 * add to the buffer only those edges that
579 * are in the Winding active edge table.
582 pts->x = pAET->bres.minor_axis, pts->y = y;
586 * send out the buffer
588 if (iPts == NUMPTSTOBUFFER) {
589 tmpPtBlock = (POINTBLOCK *)g_malloc(sizeof(POINTBLOCK));
590 tmpPtBlock->next = NULL;
591 curPtBlock->next = tmpPtBlock;
592 curPtBlock = tmpPtBlock;
593 pts = curPtBlock->pts;
594 numFullPtBlocks++; iPts = 0;
596 pWETE = pWETE->nextWETE;
598 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
602 * recompute the winding active edge table if
603 * we just resorted or have exited an edge.
605 if (InsertionSort(&AET) || fixWAET) {
611 FreeStorage(SLLBlock.next);
612 (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
613 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
614 tmpPtBlock = curPtBlock->next;
616 curPtBlock = tmpPtBlock;