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#include "reallocarray.h"
59
60/*
61 *     InsertEdgeInET
62 *
63 *     Insert the given edge into the edge table.
64 *     First we must find the correct bucket in the
65 *     Edge table, then find the right slot in the
66 *     bucket.  Finally, we can insert it.
67 *
68 */
69static void
70InsertEdgeInET(
71    EdgeTable *ET,
72    EdgeTableEntry *ETE,
73    int scanline,
74    ScanLineListBlock **SLLBlock,
75    int *iSLLBlock)
76{
77    register EdgeTableEntry *start, *prev;
78    register ScanLineList *pSLL, *pPrevSLL;
79    ScanLineListBlock *tmpSLLBlock;
80
81    /*
82     * find the right bucket to put the edge into
83     */
84    pPrevSLL = &ET->scanlines;
85    pSLL = pPrevSLL->next;
86    while (pSLL && (pSLL->scanline < scanline))
87    {
88        pPrevSLL = pSLL;
89        pSLL = pSLL->next;
90    }
91
92    /*
93     * reassign pSLL (pointer to ScanLineList) if necessary
94     */
95    if ((!pSLL) || (pSLL->scanline > scanline))
96    {
97        if (*iSLLBlock > SLLSPERBLOCK-1)
98        {
99            tmpSLLBlock = 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(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 = Xreallocarray(reg->rects, numRects, sizeof(BOX)))) {
414	Xfree(prevRects);
415	return(0);
416    }
417
418    reg->size = numRects;
419    CurPtBlock = FirstPtBlock;
420    rects = reg->rects - 1;
421    numRects = 0;
422    extents->x1 = MAXSHORT,  extents->x2 = MINSHORT;
423
424    for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
425	/* the loop uses 2 points per iteration */
426	i = NUMPTSTOBUFFER >> 1;
427	if (!numFullPtBlocks)
428	    i = iCurPtBlock >> 1;
429	for (pts = CurPtBlock->pts; i--; pts += 2) {
430	    if (pts->x == pts[1].x)
431		continue;
432	    if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&
433		pts[1].x == rects->x2 &&
434		(numRects == 1 || rects[-1].y1 != rects->y1) &&
435		(i && pts[2].y > pts[1].y)) {
436		rects->y2 = pts[1].y + 1;
437		continue;
438	    }
439	    numRects++;
440	    rects++;
441	    rects->x1 = pts->x;  rects->y1 = pts->y;
442	    rects->x2 = pts[1].x;  rects->y2 = pts[1].y + 1;
443	    if (rects->x1 < extents->x1)
444		extents->x1 = rects->x1;
445	    if (rects->x2 > extents->x2)
446		extents->x2 = rects->x2;
447        }
448	CurPtBlock = CurPtBlock->next;
449    }
450
451    if (numRects) {
452	extents->y1 = reg->rects->y1;
453	extents->y2 = rects->y2;
454    } else {
455	extents->x1 = 0;
456	extents->y1 = 0;
457	extents->x2 = 0;
458	extents->y2 = 0;
459    }
460    reg->numRects = numRects;
461
462    return(TRUE);
463}
464
465/*
466 *     polytoregion
467 *
468 *     Scan converts a polygon by returning a run-length
469 *     encoding of the resultant bitmap -- the run-length
470 *     encoding is in the form of an array of rectangles.
471 */
472Region
473XPolygonRegion(
474    XPoint     *Pts,		     /* the pts                 */
475    int       Count,                 /* number of pts           */
476    int	rule)			     /* winding rule */
477{
478    Region region;
479    register EdgeTableEntry *pAET;   /* Active Edge Table       */
480    register int y;                  /* current scanline        */
481    register int iPts = 0;           /* number of pts in buffer */
482    register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
483    register ScanLineList *pSLL;     /* current scanLineList    */
484    register XPoint *pts;             /* output buffer           */
485    EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
486    EdgeTable ET;                    /* header node for ET      */
487    EdgeTableEntry AET;              /* header node for AET     */
488    EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
489    ScanLineListBlock SLLBlock;      /* header for scanlinelist */
490    int fixWAET = FALSE;
491    POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
492    POINTBLOCK *tmpPtBlock;
493    int numFullPtBlocks = 0;
494
495    if (! (region = XCreateRegion())) return (Region) NULL;
496
497    /* special case a rectangle */
498    pts = Pts;
499    if (((Count == 4) ||
500	 ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
501	(((pts[0].y == pts[1].y) &&
502	  (pts[1].x == pts[2].x) &&
503	  (pts[2].y == pts[3].y) &&
504	  (pts[3].x == pts[0].x)) ||
505	 ((pts[0].x == pts[1].x) &&
506	  (pts[1].y == pts[2].y) &&
507	  (pts[2].x == pts[3].x) &&
508	  (pts[3].y == pts[0].y)))) {
509	region->extents.x1 = min(pts[0].x, pts[2].x);
510	region->extents.y1 = min(pts[0].y, pts[2].y);
511	region->extents.x2 = max(pts[0].x, pts[2].x);
512	region->extents.y2 = max(pts[0].y, pts[2].y);
513	if ((region->extents.x1 != region->extents.x2) &&
514	    (region->extents.y1 != region->extents.y2)) {
515	    region->numRects = 1;
516	    *(region->rects) = region->extents;
517	}
518	return(region);
519    }
520
521    if (Count < 2) return region;
522
523    if (! (pETEs = Xmallocarray(Count, sizeof(EdgeTableEntry)))) {
524	XDestroyRegion(region);
525	return (Region) NULL;
526    }
527
528    pts = FirstPtBlock.pts;
529    CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
530    pSLL = ET.scanlines.next;
531    curPtBlock = &FirstPtBlock;
532
533    if (rule == EvenOddRule) {
534        /*
535         *  for each scanline
536         */
537        for (y = ET.ymin; y < ET.ymax; y++) {
538            /*
539             *  Add a new edge to the active edge table when we
540             *  get to the next edge.
541             */
542            if (pSLL != NULL && y == pSLL->scanline) {
543                loadAET(&AET, pSLL->edgelist);
544                pSLL = pSLL->next;
545            }
546            pPrevAET = &AET;
547            pAET = AET.next;
548
549            /*
550             *  for each active edge
551             */
552            while (pAET) {
553                pts->x = pAET->bres.minor_axis,  pts->y = y;
554                pts++, iPts++;
555
556                /*
557                 *  send out the buffer
558                 */
559                if (iPts == NUMPTSTOBUFFER) {
560                    tmpPtBlock = Xmalloc(sizeof(POINTBLOCK));
561                    curPtBlock->next = tmpPtBlock;
562                    curPtBlock = tmpPtBlock;
563                    pts = curPtBlock->pts;
564                    numFullPtBlocks++;
565                    iPts = 0;
566                }
567                EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
568            }
569            (void) InsertionSort(&AET);
570        }
571    }
572    else {
573        /*
574         *  for each scanline
575         */
576        for (y = ET.ymin; y < ET.ymax; y++) {
577            /*
578             *  Add a new edge to the active edge table when we
579             *  get to the next edge.
580             */
581            if (pSLL != NULL && y == pSLL->scanline) {
582                loadAET(&AET, pSLL->edgelist);
583                computeWAET(&AET);
584                pSLL = pSLL->next;
585            }
586            pPrevAET = &AET;
587            pAET = AET.next;
588            pWETE = pAET;
589
590            /*
591             *  for each active edge
592             */
593            while (pAET) {
594                /*
595                 *  add to the buffer only those edges that
596                 *  are in the Winding active edge table.
597                 */
598                if (pWETE == pAET) {
599                    pts->x = pAET->bres.minor_axis,  pts->y = y;
600                    pts++, iPts++;
601
602                    /*
603                     *  send out the buffer
604                     */
605                    if (iPts == NUMPTSTOBUFFER) {
606                        tmpPtBlock = Xmalloc(sizeof(POINTBLOCK));
607                        curPtBlock->next = tmpPtBlock;
608                        curPtBlock = tmpPtBlock;
609                        pts = curPtBlock->pts;
610                        numFullPtBlocks++;    iPts = 0;
611                    }
612                    pWETE = pWETE->nextWETE;
613                }
614                EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
615            }
616
617            /*
618             *  recompute the winding active edge table if
619             *  we just resorted or have exited an edge.
620             */
621            if (InsertionSort(&AET) || fixWAET) {
622                computeWAET(&AET);
623                fixWAET = FALSE;
624            }
625        }
626    }
627    FreeStorage(SLLBlock.next);
628    (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
629    for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
630	tmpPtBlock = curPtBlock->next;
631	Xfree(curPtBlock);
632	curPtBlock = tmpPtBlock;
633    }
634    Xfree(pETEs);
635    return(region);
636}
637