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_api.h"
30 #include "mi_scanfill.h"
31 #include "mi_ply.h"
32
33 /*
34 * Written by Brian Kelleher; Oct. 1985
35 *
36 * This module contains all of the utility functions
37 * needed to scan-convert a polygon. The driver subroutine,
38 * miFillGeneralPoly(), is in mi_plygen.c.
39 */
40
41
42 /*
43 * InsertEdgeInET
44 *
45 * Insert the given edge into the edge table.
46 * First we must find the correct bucket in the
47 * Edge table, then find the right slot in the
48 * bucket. Finally, we can insert it.
49 *
50 */
51 static void
miInsertEdgeInET(EdgeTable * ET,EdgeTableEntry * ETE,int scanline,ScanLineListBlock ** SLLBlock,int * iSLLBlock)52 miInsertEdgeInET (EdgeTable *ET, EdgeTableEntry *ETE, int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock)
53 {
54 EdgeTableEntry *start, *prev;
55 ScanLineList *pSLL, *pPrevSLL;
56 ScanLineListBlock *tmpSLLBlock;
57
58 /*
59 * find the right bucket to put the edge into
60 */
61 pPrevSLL = &ET->scanlines;
62 pSLL = pPrevSLL->next;
63 while (pSLL && (pSLL->scanline < scanline))
64 {
65 pPrevSLL = pSLL;
66 pSLL = pSLL->next;
67 }
68
69 /*
70 * reassign pSLL (pointer to ScanLineList) if necessary
71 */
72 if ((!pSLL) || (pSLL->scanline > scanline))
73 {
74 if (*iSLLBlock > SLLSPERBLOCK-1)
75 {
76 tmpSLLBlock =
77 (ScanLineListBlock *)mi_xmalloc(sizeof(ScanLineListBlock));
78 (*SLLBlock)->next = tmpSLLBlock;
79 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
80 *SLLBlock = tmpSLLBlock;
81 *iSLLBlock = 0;
82 }
83 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
84
85 pSLL->next = pPrevSLL->next;
86 pSLL->edgelist = (EdgeTableEntry *)NULL;
87 pPrevSLL->next = pSLL;
88 }
89 pSLL->scanline = scanline;
90
91 /*
92 * now insert the edge in the right bucket
93 */
94 prev = (EdgeTableEntry *)NULL;
95 start = pSLL->edgelist;
96 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
97 {
98 prev = start;
99 start = start->next;
100 }
101 ETE->next = start;
102
103 if (prev)
104 prev->next = ETE;
105 else
106 pSLL->edgelist = ETE;
107 }
108
109 /*
110 * CreateEdgeTable
111 *
112 * This routine creates the edge table for
113 * scan converting polygons.
114 * The Edge Table (ET) looks like:
115 *
116 * EdgeTable
117 * --------
118 * | ymax | ScanLineLists
119 * |scanline|-->------------>-------------->...
120 * -------- |scanline| |scanline|
121 * |edgelist| |edgelist|
122 * --------- ---------
123 * | |
124 * | |
125 * V V
126 * list of ETEs list of ETEs
127 *
128 * where ETE is an EdgeTableEntry data structure,
129 * and there is one ScanLineList per scanline at
130 * which an edge is initially entered.
131 *
132 */
133
134 void
miCreateETandAET(int count,const miPoint * pts,EdgeTable * ET,EdgeTableEntry * AET,EdgeTableEntry * pETEs,ScanLineListBlock * pSLLBlock)135 miCreateETandAET(int count, const miPoint *pts, EdgeTable *ET, EdgeTableEntry *AET, EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
136 {
137 const miPoint *top, *bottom;
138 const miPoint *PrevPt, *CurrPt;
139 int iSLLBlock = 0;
140 int dy;
141
142 if (count < 2)
143 return;
144
145 /*
146 * initialize the Active Edge Table
147 */
148 AET->next = (EdgeTableEntry *)NULL;
149 AET->back = (EdgeTableEntry *)NULL;
150 AET->nextWETE = (EdgeTableEntry *)NULL;
151 AET->bres.minor_axis = INT_MIN;
152
153 /*
154 * initialize the Edge Table.
155 */
156 ET->scanlines.next = (ScanLineList *)NULL;
157 ET->ymax = INT_MIN;
158 ET->ymin = INT_MAX;
159 pSLLBlock->next = (ScanLineListBlock *)NULL;
160
161 PrevPt = &pts[count-1];
162
163 /*
164 * for each vertex in the array of points.
165 * In this loop we are dealing with two vertices at
166 * a time -- these make up one edge of the polygon.
167 */
168 while (count--)
169 {
170 CurrPt = pts++;
171
172 /*
173 * find out which point is above and which is below.
174 */
175 if (PrevPt->y > CurrPt->y)
176 {
177 bottom = PrevPt, top = CurrPt;
178 pETEs->ClockWise = false;
179 }
180 else
181 {
182 bottom = CurrPt, top = PrevPt;
183 pETEs->ClockWise = true;
184 }
185
186 /*
187 * don't add horizontal edges to the Edge table.
188 */
189 if (bottom->y != top->y)
190 {
191 pETEs->ymax = bottom->y-1; /* -1 so we don't get last scanline */
192
193 /*
194 * initialize integer edge algorithm
195 */
196 dy = bottom->y - top->y;
197 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
198
199 miInsertEdgeInET (ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
200 ET->ymax = IMAX(ET->ymax, PrevPt->y);
201 ET->ymin = IMIN(ET->ymin, PrevPt->y);
202 pETEs++;
203 }
204
205 PrevPt = CurrPt;
206 }
207 }
208
209 /*
210 * loadAET
211 *
212 * This routine moves EdgeTableEntries from the
213 * EdgeTable into the Active Edge Table,
214 * leaving them sorted by smaller x coordinate.
215 *
216 */
217
218 void
miloadAET(EdgeTableEntry * AET,EdgeTableEntry * ETEs)219 miloadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
220 {
221 EdgeTableEntry *pPrevAET;
222 EdgeTableEntry *tmp;
223
224 pPrevAET = AET;
225 AET = AET->next;
226 while (ETEs)
227 {
228 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
229 {
230 pPrevAET = AET;
231 AET = AET->next;
232 }
233 tmp = ETEs->next;
234 ETEs->next = AET;
235 if (AET)
236 AET->back = ETEs;
237 ETEs->back = pPrevAET;
238 pPrevAET->next = ETEs;
239 pPrevAET = ETEs;
240
241 ETEs = tmp;
242 }
243 }
244
245 /*
246 * computeWAET
247 *
248 * This routine links the AET by the
249 * nextWETE (winding EdgeTableEntry) link for
250 * use by the winding number rule. The final
251 * Active Edge Table (AET) might look something
252 * like:
253 *
254 * AET
255 * ---------- --------- ---------
256 * |ymax | |ymax | |ymax |
257 * | ... | |... | |... |
258 * |next |->|next |->|next |->...
259 * |nextWETE| |nextWETE| |nextWETE|
260 * --------- --------- ^--------
261 * | | |
262 * V-------------------> V---> ...
263 *
264 */
265 void
micomputeWAET(EdgeTableEntry * AET)266 micomputeWAET(EdgeTableEntry *AET)
267 {
268 EdgeTableEntry *pWETE;
269 int inside = 1;
270 int isInside = 0;
271
272 AET->nextWETE = (EdgeTableEntry *)NULL;
273 pWETE = AET;
274 AET = AET->next;
275 while (AET)
276 {
277 if (AET->ClockWise)
278 isInside++;
279 else
280 isInside--;
281
282 if ((!inside && !isInside) ||
283 ( inside && isInside))
284 {
285 pWETE->nextWETE = AET;
286 pWETE = AET;
287 inside = !inside;
288 }
289 AET = AET->next;
290 }
291 pWETE->nextWETE = (EdgeTableEntry *)NULL;
292 }
293
294 /*
295 * InsertionSort
296 *
297 * Just a simple insertion sort using
298 * pointers and back pointers to sort the Active
299 * Edge Table.
300 *
301 */
302
303 bool
miInsertionSort(EdgeTableEntry * AET)304 miInsertionSort(EdgeTableEntry *AET)
305 {
306 EdgeTableEntry *pETEchase;
307 EdgeTableEntry *pETEinsert;
308 EdgeTableEntry *pETEchaseBackTMP;
309 bool changed = false;
310
311 AET = AET->next;
312 while (AET)
313 {
314 pETEinsert = AET;
315 pETEchase = AET;
316 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
317 pETEchase = pETEchase->back;
318
319 AET = AET->next;
320 if (pETEchase != pETEinsert)
321 {
322 pETEchaseBackTMP = pETEchase->back;
323 pETEinsert->back->next = AET;
324 if (AET)
325 AET->back = pETEinsert->back;
326 pETEinsert->next = pETEchase;
327 pETEchase->back->next = pETEinsert;
328 pETEchase->back = pETEinsert;
329 pETEinsert->back = pETEchaseBackTMP;
330 changed = true;
331 }
332 }
333 return changed;
334 }
335
336 /*
337 * Clean up our act.
338 */
339 void
miFreeStorage(ScanLineListBlock * pSLLBlock)340 miFreeStorage(ScanLineListBlock *pSLLBlock)
341 {
342 ScanLineListBlock *tmpSLLBlock;
343
344 while (pSLLBlock)
345 {
346 tmpSLLBlock = pSLLBlock->next;
347 free(pSLLBlock);
348 pSLLBlock = tmpSLLBlock;
349 }
350 }
351