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