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