1 /***********************************************************
3 Copyright (c) 1987 X Consortium
5 Permission is hereby granted, free of charge, to any person obtaining a copy
6 of this software and associated documentation files (the "Software"), to deal
7 in the Software without restriction, including without limitation the rights
8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 copies of the Software, and to permit persons to whom the Software is
10 furnished to do so, subject to the following conditions:
12 The above copyright notice and this permission notice shall be included in
13 all copies or substantial portions of the Software.
15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
19 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 Except as contained in this notice, the name of the X Consortium shall not be
23 used in advertising or otherwise to promote the sale, use or other dealings
24 in this Software without prior written authorization from the X Consortium.
27 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
31 Permission to use, copy, modify, and distribute this software and its
32 documentation for any purpose and without fee is hereby granted,
33 provided that the above copyright notice appear in all copies and that
34 both that copyright notice and this permission notice appear in
35 supporting documentation, and that the name of Digital not be
36 used in advertising or publicity pertaining to distribution of the
37 software without specific, written prior permission.
39 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
40 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
41 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
42 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
43 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
44 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
47 ******************************************************************/
48 /* $XConsortium: mipolyutil.c,v 1.16 94/04/17 20:27:46 dpw Exp $ */
49 #include "miscstruct.h"
51 #include "miscanfill.h"
54 #define MAXINT 0x7fffffff
55 #define MININT -MAXINT
60 * Written by Brian Kelleher; Oct. 1985
62 * This module contains all of the utility functions
63 * needed to scan convert a polygon.
70 * Insert the given edge into the edge table.
71 * First we must find the correct bucket in the
72 * Edge table, then find the right slot in the
73 * bucket. Finally, we can insert it.
77 miInsertEdgeInET(ET, ETE, scanline, SLLBlock, iSLLBlock)
81 ScanLineListBlock **SLLBlock;
84 register EdgeTableEntry *start, *prev;
85 register ScanLineList *pSLL, *pPrevSLL;
86 ScanLineListBlock *tmpSLLBlock;
89 * find the right bucket to put the edge into
91 pPrevSLL = &ET->scanlines;
92 pSLL = pPrevSLL->next;
93 while (pSLL && (pSLL->scanline < scanline))
100 * reassign pSLL (pointer to ScanLineList) if necessary
102 if ((!pSLL) || (pSLL->scanline > scanline))
104 if (*iSLLBlock > SLLSPERBLOCK-1)
107 (ScanLineListBlock *)xalloc(sizeof(ScanLineListBlock));
110 (*SLLBlock)->next = tmpSLLBlock;
111 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
112 *SLLBlock = tmpSLLBlock;
115 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
117 pSLL->next = pPrevSLL->next;
118 pSLL->edgelist = (EdgeTableEntry *)NULL;
119 pPrevSLL->next = pSLL;
121 pSLL->scanline = scanline;
124 * now insert the edge in the right bucket
126 prev = (EdgeTableEntry *)NULL;
127 start = pSLL->edgelist;
128 while (start && (start->bres.minor < ETE->bres.minor))
138 pSLL->edgelist = ETE;
145 * This routine creates the edge table for
146 * scan converting polygons.
147 * The Edge Table (ET) looks like:
151 * | ymax | ScanLineLists
152 * |scanline|-->------------>-------------->...
153 * -------- |scanline| |scanline|
154 * |edgelist| |edgelist|
155 * --------- ---------
159 * list of ETEs list of ETEs
161 * where ETE is an EdgeTableEntry data structure,
162 * and there is one ScanLineList per scanline at
163 * which an edge is initially entered.
168 miCreateETandAET(count, pts, ET, AET, pETEs, pSLLBlock)
170 register DDXPointPtr pts;
173 register EdgeTableEntry *pETEs;
174 ScanLineListBlock *pSLLBlock;
176 register DDXPointPtr top, bottom;
177 register DDXPointPtr PrevPt, CurrPt;
182 if (count < 2) return TRUE;
185 * initialize the Active Edge Table
187 AET->next = (EdgeTableEntry *)NULL;
188 AET->back = (EdgeTableEntry *)NULL;
189 AET->nextWETE = (EdgeTableEntry *)NULL;
190 AET->bres.minor = MININT;
193 * initialize the Edge Table.
195 ET->scanlines.next = (ScanLineList *)NULL;
198 pSLLBlock->next = (ScanLineListBlock *)NULL;
200 PrevPt = &pts[count-1];
203 * for each vertex in the array of points.
204 * In this loop we are dealing with two vertices at
205 * a time -- these make up one edge of the polygon.
212 * find out which point is above and which is below.
214 if (PrevPt->y > CurrPt->y)
216 bottom = PrevPt, top = CurrPt;
217 pETEs->ClockWise = 0;
221 bottom = CurrPt, top = PrevPt;
222 pETEs->ClockWise = 1;
226 * don't add horizontal edges to the Edge table.
228 if (bottom->y != top->y)
230 pETEs->ymax = bottom->y-1; /* -1 so we don't get last scanline */
233 * initialize integer edge algorithm
235 dy = bottom->y - top->y;
236 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
238 if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock))
240 miFreeStorage(pSLLBlock->next);
244 ET->ymax = max(ET->ymax, PrevPt->y);
245 ET->ymin = min(ET->ymin, PrevPt->y);
257 * This routine moves EdgeTableEntries from the
258 * EdgeTable into the Active Edge Table,
259 * leaving them sorted by smaller x coordinate.
265 register EdgeTableEntry *AET, *ETEs;
267 register EdgeTableEntry *pPrevAET;
268 register EdgeTableEntry *tmp;
274 while (AET && (AET->bres.minor < ETEs->bres.minor))
283 ETEs->back = pPrevAET;
284 pPrevAET->next = ETEs;
294 * This routine links the AET by the
295 * nextWETE (winding EdgeTableEntry) link for
296 * use by the winding number rule. The final
297 * Active Edge Table (AET) might look something
301 * ---------- --------- ---------
302 * |ymax | |ymax | |ymax |
303 * | ... | |... | |... |
304 * |next |->|next |->|next |->...
305 * |nextWETE| |nextWETE| |nextWETE|
306 * --------- --------- ^--------
308 * V-------------------> V---> ...
313 register EdgeTableEntry *AET;
315 register EdgeTableEntry *pWETE;
316 register int inside = 1;
317 register int isInside = 0;
319 AET->nextWETE = (EdgeTableEntry *)NULL;
329 if ((!inside && !isInside) ||
330 ( inside && isInside))
332 pWETE->nextWETE = AET;
338 pWETE->nextWETE = (EdgeTableEntry *)NULL;
344 * Just a simple insertion sort using
345 * pointers and back pointers to sort the Active
352 register EdgeTableEntry *AET;
354 register EdgeTableEntry *pETEchase;
355 register EdgeTableEntry *pETEinsert;
356 register EdgeTableEntry *pETEchaseBackTMP;
357 register int changed = 0;
364 while (pETEchase->back->bres.minor > AET->bres.minor)
365 pETEchase = pETEchase->back;
368 if (pETEchase != pETEinsert)
370 pETEchaseBackTMP = pETEchase->back;
371 pETEinsert->back->next = AET;
373 AET->back = pETEinsert->back;
374 pETEinsert->next = pETEchase;
375 pETEchase->back->next = pETEinsert;
376 pETEchase->back = pETEinsert;
377 pETEinsert->back = pETEchaseBackTMP;
388 miFreeStorage(pSLLBlock)
389 register ScanLineListBlock *pSLLBlock;
391 register ScanLineListBlock *tmpSLLBlock;
395 tmpSLLBlock = pSLLBlock->next;
397 pSLLBlock = tmpSLLBlock;