mipolyutil.c revision 706f2543 
1/***********************************************************
2
3Copyright 1987, 1998  The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21Except as contained in this notice, the name of The Open Group shall not be
22used in advertising or otherwise to promote the sale, use or other dealings
23in this Software without prior written authorization from The Open Group.
24
25
26Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
27
28                        All Rights Reserved
29
30Permission to use, copy, modify, and distribute this software and its
31documentation for any purpose and without fee is hereby granted,
32provided that the above copyright notice appear in all copies and that
33both that copyright notice and this permission notice appear in
34supporting documentation, and that the name of Digital not be
35used in advertising or publicity pertaining to distribution of the
36software without specific, written prior permission.
37
38DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
39ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
40DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
41ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
42WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
43ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
44SOFTWARE.
45
46******************************************************************/
47#ifdef HAVE_DIX_CONFIG_H
48#include <dix-config.h>
49#endif
50
51#include "regionstr.h"
52#include "gc.h"
53#include "miscanfill.h"
54#include "mipoly.h"
55#include "misc.h"	/* MAXINT */
56
57/*
58 *     fillUtils.c
59 *
60 *     Written by Brian Kelleher;  Oct. 1985
61 *
62 *     This module contains all of the utility functions
63 *     needed to scan convert a polygon.
64 *
65 */
66
67/*
68 *     InsertEdgeInET
69 *
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.
74 *
75 */
76static Bool
77miInsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,  int scanline,
78		 ScanLineListBlock **SLLBlock, int *iSLLBlock)
79{
80    EdgeTableEntry *start, *prev;
81    ScanLineList *pSLL, *pPrevSLL;
82    ScanLineListBlock *tmpSLLBlock;
83
84    /*
85     * find the right bucket to put the edge into
86     */
87    pPrevSLL = &ET->scanlines;
88    pSLL = pPrevSLL->next;
89    while (pSLL && (pSLL->scanline < scanline))
90    {
91        pPrevSLL = pSLL;
92        pSLL = pSLL->next;
93    }
94
95    /*
96     * reassign pSLL (pointer to ScanLineList) if necessary
97     */
98    if ((!pSLL) || (pSLL->scanline > scanline))
99    {
100        if (*iSLLBlock > SLLSPERBLOCK-1)
101        {
102            tmpSLLBlock = malloc(sizeof(ScanLineListBlock));
103	    if (!tmpSLLBlock)
104		return FALSE;
105            (*SLLBlock)->next = tmpSLLBlock;
106            tmpSLLBlock->next = NULL;
107            *SLLBlock = tmpSLLBlock;
108            *iSLLBlock = 0;
109        }
110        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
111
112        pSLL->next = pPrevSLL->next;
113        pSLL->edgelist = NULL;
114        pPrevSLL->next = pSLL;
115    }
116    pSLL->scanline = scanline;
117
118    /*
119     * now insert the edge in the right bucket
120     */
121    prev = NULL;
122    start = pSLL->edgelist;
123    while (start && (start->bres.minor < ETE->bres.minor))
124    {
125        prev = start;
126        start = start->next;
127    }
128    ETE->next = start;
129
130    if (prev)
131        prev->next = ETE;
132    else
133        pSLL->edgelist = ETE;
134    return TRUE;
135}
136
137/*
138 *     CreateEdgeTable
139 *
140 *     This routine creates the edge table for
141 *     scan converting polygons.
142 *     The Edge Table (ET) looks like:
143 *
144 *    EdgeTable
145 *     --------
146 *    |  ymax  |        ScanLineLists
147 *    |scanline|-->------------>-------------->...
148 *     --------   |scanline|   |scanline|
149 *                |edgelist|   |edgelist|
150 *                ---------    ---------
151 *                    |             |
152 *                    |             |
153 *                    V             V
154 *              list of ETEs   list of ETEs
155 *
156 *     where ETE is an EdgeTableEntry data structure,
157 *     and there is one ScanLineList per scanline at
158 *     which an edge is initially entered.
159 *
160 */
161
162Bool
163miCreateETandAET(int count, DDXPointPtr pts, EdgeTable *ET, EdgeTableEntry *AET,
164                 EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
165{
166    DDXPointPtr top, bottom;
167    DDXPointPtr PrevPt, CurrPt;
168    int iSLLBlock = 0;
169
170    int dy;
171
172    if (count < 2)  return TRUE;
173
174    /*
175     *  initialize the Active Edge Table
176     */
177    AET->next = NULL;
178    AET->back = NULL;
179    AET->nextWETE = NULL;
180    AET->bres.minor = MININT;
181
182    /*
183     *  initialize the Edge Table.
184     */
185    ET->scanlines.next = NULL;
186    ET->ymax = MININT;
187    ET->ymin = MAXINT;
188    pSLLBlock->next = NULL;
189
190    PrevPt = &pts[count-1];
191
192    /*
193     *  for each vertex in the array of points.
194     *  In this loop we are dealing with two vertices at
195     *  a time -- these make up one edge of the polygon.
196     */
197    while (count--)
198    {
199        CurrPt = pts++;
200
201        /*
202         *  find out which point is above and which is below.
203         */
204        if (PrevPt->y > CurrPt->y)
205        {
206            bottom = PrevPt, top = CurrPt;
207            pETEs->ClockWise = 0;
208        }
209        else
210        {
211            bottom = CurrPt, top = PrevPt;
212            pETEs->ClockWise = 1;
213        }
214
215        /*
216         * don't add horizontal edges to the Edge table.
217         */
218        if (bottom->y != top->y)
219        {
220            pETEs->ymax = bottom->y-1;  /* -1 so we don't get last scanline */
221
222            /*
223             *  initialize integer edge algorithm
224             */
225            dy = bottom->y - top->y;
226            BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
227
228            if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock))
229	    {
230		miFreeStorage(pSLLBlock->next);
231		return FALSE;
232	    }
233
234            ET->ymax = max(ET->ymax, PrevPt->y);
235            ET->ymin = min(ET->ymin, PrevPt->y);
236            pETEs++;
237        }
238
239        PrevPt = CurrPt;
240    }
241    return TRUE;
242}
243
244/*
245 *     loadAET
246 *
247 *     This routine moves EdgeTableEntries from the
248 *     EdgeTable into the Active Edge Table,
249 *     leaving them sorted by smaller x coordinate.
250 *
251 */
252
253void
254miloadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
255{
256    EdgeTableEntry *pPrevAET;
257    EdgeTableEntry *tmp;
258
259    pPrevAET = AET;
260    AET = AET->next;
261    while (ETEs)
262    {
263        while (AET && (AET->bres.minor < ETEs->bres.minor))
264        {
265            pPrevAET = AET;
266            AET = AET->next;
267        }
268        tmp = ETEs->next;
269        ETEs->next = AET;
270        if (AET)
271            AET->back = ETEs;
272        ETEs->back = pPrevAET;
273        pPrevAET->next = ETEs;
274        pPrevAET = ETEs;
275
276        ETEs = tmp;
277    }
278}
279
280/*
281 *     computeWAET
282 *
283 *     This routine links the AET by the
284 *     nextWETE (winding EdgeTableEntry) link for
285 *     use by the winding number rule.  The final
286 *     Active Edge Table (AET) might look something
287 *     like:
288 *
289 *     AET
290 *     ----------  ---------   ---------
291 *     |ymax    |  |ymax    |  |ymax    |
292 *     | ...    |  |...     |  |...     |
293 *     |next    |->|next    |->|next    |->...
294 *     |nextWETE|  |nextWETE|  |nextWETE|
295 *     ---------   ---------   ^--------
296 *         |                   |       |
297 *         V------------------->       V---> ...
298 *
299 */
300void
301micomputeWAET(EdgeTableEntry *AET)
302{
303    EdgeTableEntry *pWETE;
304    int inside = 1;
305    int isInside = 0;
306
307    AET->nextWETE = NULL;
308    pWETE = AET;
309    AET = AET->next;
310    while (AET)
311    {
312        if (AET->ClockWise)
313            isInside++;
314        else
315            isInside--;
316
317        if ((!inside && !isInside) ||
318            ( inside &&  isInside))
319        {
320            pWETE->nextWETE = AET;
321            pWETE = AET;
322            inside = !inside;
323        }
324        AET = AET->next;
325    }
326    pWETE->nextWETE = NULL;
327}
328
329/*
330 *     InsertionSort
331 *
332 *     Just a simple insertion sort using
333 *     pointers and back pointers to sort the Active
334 *     Edge Table.
335 *
336 */
337
338int
339miInsertionSort(EdgeTableEntry *AET)
340{
341    EdgeTableEntry *pETEchase;
342    EdgeTableEntry *pETEinsert;
343    EdgeTableEntry *pETEchaseBackTMP;
344    int changed = 0;
345
346    AET = AET->next;
347    while (AET)
348    {
349        pETEinsert = AET;
350        pETEchase = AET;
351        while (pETEchase->back->bres.minor > AET->bres.minor)
352            pETEchase = pETEchase->back;
353
354        AET = AET->next;
355        if (pETEchase != pETEinsert)
356        {
357            pETEchaseBackTMP = pETEchase->back;
358            pETEinsert->back->next = AET;
359            if (AET)
360                AET->back = pETEinsert->back;
361            pETEinsert->next = pETEchase;
362            pETEchase->back->next = pETEinsert;
363            pETEchase->back = pETEinsert;
364            pETEinsert->back = pETEchaseBackTMP;
365            changed = 1;
366        }
367    }
368    return changed;
369}
370
371/*
372 *     Clean up our act.
373 */
374void
375miFreeStorage(ScanLineListBlock *pSLLBlock)
376{
377    ScanLineListBlock   *tmpSLLBlock;
378
379    while (pSLLBlock)
380    {
381        tmpSLLBlock = pSLLBlock->next;
382        free(pSLLBlock);
383        pSLLBlock = tmpSLLBlock;
384    }
385}
386