| Geant4 Cross Reference |
1 // Copyright (C) 2010, Guy Barrand. All rights reserved.
2 // See the file tools.license for terms.
3
4 #ifndef tools_zb_edge_table
5 #define tools_zb_edge_table
6
7 #include "line"
8 #include "point"
9
10 #include "../cmemT"
11 #include <cstdio> //NULL
12
13 namespace tools {
14 namespace zb {
15
16 /***************************************************************************/
17 inline void InsertEdgeInET (
18 EdgeTable* ET
19 ,EdgeTableEntry* ETE
20 ,int scanline
21 ,ScanLineListBlock** SLLBlock
22 ,int* iSLLBlock
23 )
24 /***************************************************************************/
25 /*
26 * InsertEdgeInET
27 *
28 * Insert the given edge into the edge table.
29 * First we must find the correct bucket in the
30 * Edge table, then find the right slot in the
31 * bucket. Finally, we can insert it.
32 *
33 */
34 /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
35 {
36 EdgeTableEntry *start, *prev;
37 ScanLineList *pSLL, *pPrevSLL;
38 ScanLineListBlock *tmpSLLBlock;
39 /*.........................................................................*/
40
41 /*
42 * find the right bucket to put the edge into
43 */
44 pPrevSLL = &ET->scanlines;
45 pSLL = pPrevSLL->next;
46 while (pSLL && (pSLL->scanline < scanline))
47 {
48 pPrevSLL = pSLL;
49 pSLL = pSLL->next;
50 }
51
52 /*
53 * reassign pSLL (pointer to ScanLineList) if necessary
54 */
55 if ( (pSLL==NULL) || (pSLL->scanline > scanline))
56 {
57 if (*iSLLBlock > SLLSPERBLOCK-1)
58 {
59 tmpSLLBlock = cmem_alloc<ScanLineListBlock>(1);
60 (*SLLBlock)->next = tmpSLLBlock;
61 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
62 *SLLBlock = tmpSLLBlock;
63 *iSLLBlock = 0;
64 }
65 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
66
67 pSLL->next = pPrevSLL->next;
68 pSLL->edgelist = (EdgeTableEntry *)NULL;
69 pPrevSLL->next = pSLL;
70 }
71 pSLL->scanline = scanline;
72
73 /*
74 * now insert the edge in the right bucket
75 */
76 prev = (EdgeTableEntry *)NULL;
77 start = pSLL->edgelist;
78 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
79 {
80 prev = start;
81 start = start->next;
82 }
83 ETE->next = start;
84
85 if (prev!=NULL)
86 prev->next = ETE;
87 else
88 pSLL->edgelist = ETE;
89 }
90
91 /***************************************************************************/
92 inline void CreateETandAET (
93 int count
94 ,point* pts
95 ,EdgeTable* ET
96 ,EdgeTableEntry* AET
97 ,EdgeTableEntry* pETEs
98 ,ScanLineListBlock* pSLLBlock
99 )
100 /***************************************************************************/
101 /*
102 * CreateEdgeTable
103 *
104 * This routine creates the edge table for
105 * scan converting polygons.
106 * The Edge Table (ET) looks like:
107 *
108 * EdgeTable
109 * --------
110 * | ymax | ScanLineLists
111 * |scanline|-->------------>-------------->...
112 * -------- |scanline| |scanline|
113 * |edgelist| |edgelist|
114 * --------- ---------
115 * | |
116 * | |
117 * V V
118 * list of ETEs list of ETEs
119 *
120 * where ETE is an EdgeTableEntry data structure,
121 * and there is one ScanLineList per scanline at
122 * which an edge is initially entered.
123 *
124 */
125 /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
126 {
127 point *top, *bottom;
128 point *PrevPt, *CurrPt;
129 int iSLLBlock = 0;
130 int dy;
131 /*.........................................................................*/
132
133 if (count < 2) return;
134
135 /*
136 * initialize the Active Edge Table
137 */
138 AET->next = (EdgeTableEntry *)NULL;
139 AET->back = (EdgeTableEntry *)NULL;
140 AET->nextWETE = (EdgeTableEntry *)NULL;
141 AET->bres.minor_axis = SMALL_COORDINATE;
142
143 /*
144 * initialize the Edge Table.
145 */
146 ET->scanlines.next = (ScanLineList *)NULL;
147 ET->ymax = SMALL_COORDINATE;
148 ET->ymin = LARGE_COORDINATE;
149 pSLLBlock->next = (ScanLineListBlock *)NULL;
150
151 PrevPt = &pts[count-1];
152
153 /*
154 * for each vertex in the array of points.
155 * In this loop we are dealing with two vertices at
156 * a time -- these make up one edge of the polygon.
157 */
158 while (count--)
159 {
160 CurrPt = pts++;
161
162 /*
163 * find out which point is above and which is below.
164 */
165 if (PrevPt->y > CurrPt->y)
166 {
167 bottom = PrevPt, top = CurrPt;
168 pETEs->ClockWise = 0;
169 }
170 else
171 {
172 bottom = CurrPt, top = PrevPt;
173 pETEs->ClockWise = 1;
174 }
175
176 /*
177 * don't add horizontal edges to the Edge table.
178 */
179 if (bottom->y != top->y)
180 {
181 pETEs->ymax = (int)(bottom->y-1); /* -1 so we don't get last scanline */
182
183 /*
184 * initialize integer edge algorithm
185 */
186 dy = (int)(bottom->y - top->y);
187 BRESINITPGONSTRUCT (dy,(int)top->x,(int)bottom->x, pETEs->bres)
188
189 InsertEdgeInET (ET, pETEs, (int)top->y, &pSLLBlock, &iSLLBlock);
190
191 if (PrevPt->y > ET->ymax) ET->ymax = (int) PrevPt->y;
192 if (PrevPt->y < ET->ymin) ET->ymin = (int) PrevPt->y;
193 pETEs++;
194 }
195
196 PrevPt = CurrPt;
197 }
198 }
199
200 inline void LoadAET(EdgeTableEntry* AET,EdgeTableEntry* ETEs) {
201 /*
202 * LoadAET
203 *
204 * This routine moves EdgeTableEntries from the
205 * EdgeTable into the Active Edge Table,
206 * leaving them sorted by smaller x coordinate.
207 *
208 */
209 EdgeTableEntry *pPrevAET;
210 EdgeTableEntry *tmp;
211
212 pPrevAET = AET;
213 AET = AET->next;
214 while(ETEs) {
215 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
216 {
217 pPrevAET = AET;
218 AET = AET->next;
219 }
220 tmp = ETEs->next;
221 ETEs->next = AET;
222 if (AET!=NULL)
223 AET->back = ETEs;
224 ETEs->back = pPrevAET;
225 pPrevAET->next = ETEs;
226 pPrevAET = ETEs;
227
228 ETEs = tmp;
229 }
230 }
231
232 inline void ComputeWAET(EdgeTableEntry* AET) {
233 /*
234 * ComputeWAET
235 *
236 * This routine links the AET by the
237 * nextWETE (winding EdgeTableEntry) link for
238 * use by the winding number rule. The final
239 * Active Edge Table (AET) might look something
240 * like:
241 *
242 * AET
243 * ---------- --------- ---------
244 * |ymax | |ymax | |ymax |
245 * | ... | |... | |... |
246 * |next |->|next |->|next |->...
247 * |nextWETE| |nextWETE| |nextWETE|
248 * --------- --------- ^--------
249 * | | |
250 * V-------------------> V---> ...
251 *
252 */
253 EdgeTableEntry *pWETE;
254 int inside = 1;
255 int isInside = 0;
256
257 AET->nextWETE = (EdgeTableEntry *)NULL;
258 pWETE = AET;
259 AET = AET->next;
260 while(AET) {
261 if (AET->ClockWise!=0)
262 isInside++;
263 else
264 isInside--;
265
266 if (( (inside==0) && (isInside==0) ) ||
267 ( (inside!=0) && (isInside!=0) ))
268 {
269 pWETE->nextWETE = AET;
270 pWETE = AET;
271 inside = !inside;
272 }
273 AET = AET->next;
274 }
275 pWETE->nextWETE = (EdgeTableEntry *)NULL;
276 }
277
278 inline int InsertAndSort(EdgeTableEntry* AET) {
279 // InsertAndSort
280 // Just a simple insertion sort using
281 // pointers and back pointers to sort the Active
282 // Edge Table.
283
284 EdgeTableEntry *pETEchase;
285 EdgeTableEntry *pETEinsert;
286 EdgeTableEntry *pETEchaseBackTMP;
287 int changed = 0;
288
289 AET = AET->next;
290 while(AET) {
291 pETEinsert = AET;
292 pETEchase = AET;
293 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
294 pETEchase = pETEchase->back;
295
296 AET = AET->next;
297 if (pETEchase != pETEinsert)
298 {
299 pETEchaseBackTMP = pETEchase->back;
300 pETEinsert->back->next = AET;
301 if (AET!=NULL)
302 AET->back = pETEinsert->back;
303 pETEinsert->next = pETEchase;
304 pETEchase->back->next = pETEinsert;
305 pETEchase->back = pETEinsert;
306 pETEinsert->back = pETEchaseBackTMP;
307 changed = 1;
308 }
309 }
310 return(changed);
311 }
312
313 inline void FreeStorage(ScanLineListBlock* pSLLBlock){
314 // Clean up our act.
315 ScanLineListBlock* tmpSLLBlock;
316 while(pSLLBlock) {
317 tmpSLLBlock = pSLLBlock->next;
318 cmem_free(pSLLBlock);
319 pSLLBlock = tmpSLLBlock;
320 }
321 }
322
323 }}
324
325 #endif