1 /* This file is part of the GNU libxmi package.
2
3 Copyright (C) 1985, 1986, 1987, 1988, 1989, X Consortium. For an
4 associated permission notice, see the accompanying file README-X.
5
6 GNU enhancements Copyright (C) 1998, 1999, 2000, 2005, Free Software
7 Foundation, Inc.
8
9 The GNU libxmi package is free software. You may redistribute it
10 and/or modify it under the terms of the GNU General Public License as
11 published by the Free Software foundation; either version 2, or (at your
12 option) any later version.
13
14 The GNU libxmi package is distributed in the hope that it will be
15 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 General Public License for more details.
18
19 You should have received a copy of the GNU General Public License along
20 with the GNU plotutils package; see the file COPYING. If not, write to
21 the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor,
22 Boston, MA 02110-1301, USA. */
23
24 #include "sys-defines.h"
25 #include "extern.h"
26
27 #include "xmi.h"
28 #include "mi_spans.h"
29 #include "mi_gc.h"
30 #include "mi_api.h"
31 #include "mi_scanfill.h"
32 #include "mi_ply.h"
33
34 /*
35 *
36 * Original author: Brian Kelleher, Oct. 1985.
37 * Hacked by Robert S. Maier, 1998-9.
38 *
39 * Routine to fill a general (i.e., possibly non-convex or
40 * self-intersecting) polygon. Two fill rules are supported: WINDING and
41 * EVENODD. All painting goes through the low-level MI_PAINT_SPANS()
42 * macro.
43 *
44 * This calls utility routines in mi_plyutil.c. See mi_scanfill.h for a
45 * complete description of the algorithm. */
46
47 /* ARGS: count = number of points, ptsIn = the points */
48 void
miFillGeneralPoly(miPaintedSet * paintedSet,const miGC * pGC,int count,const miPoint * ptsIn)49 miFillGeneralPoly (miPaintedSet *paintedSet, const miGC *pGC, int count, const miPoint *ptsIn)
50 {
51 EdgeTableEntry *pAET; /* the Active Edge Table */
52 int y; /* the current scanline */
53 int nPts = 0; /* number of pts in buffer */
54 EdgeTableEntry *pWETE; /* Winding Edge Table */
55 ScanLineList *pSLL; /* Current ScanLineList */
56 miPoint *ptsOut; /* ptr to output buffers */
57 unsigned int *width;
58 miPoint FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */
59 unsigned int FirstWidth[NUMPTSTOBUFFER];
60 EdgeTableEntry *pPrevAET; /* previous AET entry */
61 EdgeTable ET; /* Edge Table header node */
62 EdgeTableEntry AET; /* Active ET header node */
63 EdgeTableEntry *pETEs; /* Edge Table Entries buff */
64 ScanLineListBlock SLLBlock; /* header for ScanLineList */
65 bool fixWAET = false;
66
67 if (count <= 2)
68 return;
69
70 pETEs = (EdgeTableEntry *) mi_xmalloc(sizeof(EdgeTableEntry) * count);
71 ptsOut = FirstPoint;
72 width = FirstWidth;
73 miCreateETandAET (count, ptsIn, &ET, &AET, pETEs, &SLLBlock);
74 pSLL = ET.scanlines.next;
75
76 if (pGC->fillRule == (int)MI_EVEN_ODD_RULE)
77 {
78 /*
79 * for each scanline
80 */
81 for (y = ET.ymin; y < ET.ymax; y++)
82 {
83 /*
84 * Add a new edge to the active edge table when we
85 * get to the next edge.
86 */
87 if (pSLL && y == pSLL->scanline)
88 {
89 miloadAET(&AET, pSLL->edgelist);
90 pSLL = pSLL->next;
91 }
92 pPrevAET = &AET;
93 pAET = AET.next;
94
95 /*
96 * for each active edge
97 */
98 while (pAET)
99 {
100 ptsOut->x = pAET->bres.minor_axis;
101 ptsOut++->y = y;
102 *width++ = (unsigned int)(pAET->next->bres.minor_axis - pAET->bres.minor_axis);
103 nPts++;
104
105 /*
106 * send out the buffer when its full
107 */
108 if (nPts == NUMPTSTOBUFFER)
109 {
110 MI_COPY_AND_PAINT_SPANS(paintedSet, pGC->pixels[1], nPts, FirstPoint, FirstWidth)
111 ptsOut = FirstPoint;
112 width = FirstWidth;
113 nPts = 0;
114 }
115 EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
116 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
117 }
118 miInsertionSort(&AET);
119 }
120 }
121 else /* default to WindingNumber */
122 {
123 /*
124 * for each scanline
125 */
126 for (y = ET.ymin; y < ET.ymax; y++)
127 {
128 /*
129 * Add a new edge to the active edge table when we
130 * get to the next edge.
131 */
132 if (pSLL && y == pSLL->scanline)
133 {
134 miloadAET(&AET, pSLL->edgelist);
135 micomputeWAET(&AET);
136 pSLL = pSLL->next;
137 }
138 pPrevAET = &AET;
139 pAET = AET.next;
140 pWETE = pAET;
141
142 /*
143 * for each active edge
144 */
145 while (pAET)
146 {
147 /*
148 * if the next edge in the active edge table is
149 * also the next edge in the winding active edge
150 * table.
151 */
152 if (pWETE == pAET)
153 {
154 ptsOut->x = pAET->bres.minor_axis;
155 ptsOut++->y = y;
156 *width++ = (unsigned int)(pAET->nextWETE->bres.minor_axis - pAET->bres.minor_axis);
157 nPts++;
158
159 /*
160 * send out the buffer
161 */
162 if (nPts == NUMPTSTOBUFFER)
163 {
164 MI_COPY_AND_PAINT_SPANS(paintedSet, pGC->pixels[1], nPts, FirstPoint, FirstWidth)
165 ptsOut = FirstPoint;
166 width = FirstWidth;
167 nPts = 0;
168 }
169
170 pWETE = pWETE->nextWETE;
171 while (pWETE != pAET)
172 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
173 pWETE = pWETE->nextWETE;
174 }
175 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
176 }
177
178 /*
179 * reevaluate the Winding active edge table if we
180 * just had to resort it or if we just exited an edge.
181 */
182 if (miInsertionSort(&AET) || fixWAET)
183 {
184 micomputeWAET(&AET);
185 fixWAET = false;
186 }
187 }
188 }
189
190 /*
191 * Get any spans that we missed by buffering
192 */
193 MI_COPY_AND_PAINT_SPANS(paintedSet, pGC->pixels[1], nPts, FirstPoint, FirstWidth)
194 free (pETEs);
195 miFreeStorage(SLLBlock.next);
196 }
197