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