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