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_polygon 4 #ifndef tools_zb_polygon 5 #define tools_zb_polygon 5 #define tools_zb_polygon 6 6 7 #include "edge_table" 7 #include "edge_table" 8 #include "../mnmx" 8 #include "../mnmx" 9 9 10 namespace tools { 10 namespace tools { 11 namespace zb { 11 namespace zb { 12 12 13 class polygon { 13 class polygon { 14 14 15 static const int NUMPTSTOBUFFER = 200; 15 static const int NUMPTSTOBUFFER = 200; 16 16 17 typedef struct _POINTBLOCK { 17 typedef struct _POINTBLOCK { 18 point pts[NUMPTSTOBUFFER]; 18 point pts[NUMPTSTOBUFFER]; 19 struct _POINTBLOCK* next; 19 struct _POINTBLOCK* next; 20 } POINTBLOCK; 20 } POINTBLOCK; 21 21 22 int m_pETEn; 22 int m_pETEn; 23 EdgeTableEntry* m_pETEs; 23 EdgeTableEntry* m_pETEs; 24 int m_numAllocPtBlocks; 24 int m_numAllocPtBlocks; 25 POINTBLOCK m_FirstPtBlock; 25 POINTBLOCK m_FirstPtBlock; 26 public: 26 public: 27 polygon():m_pETEn(0),m_pETEs(NULL),m_numAllo 27 polygon():m_pETEn(0),m_pETEs(NULL),m_numAllocPtBlocks(0){} 28 virtual ~polygon(){clear();} 28 virtual ~polygon(){clear();} 29 protected: 29 protected: 30 polygon(const polygon&){} 30 polygon(const polygon&){} 31 polygon& operator=(const polygon&){return *t 31 polygon& operator=(const polygon&){return *this;} 32 public: 32 public: 33 void clear(){ 33 void clear(){ 34 POINTBLOCK* curPtBlock; 34 POINTBLOCK* curPtBlock; 35 cmem_free(m_pETEs); 35 cmem_free(m_pETEs); 36 m_pETEn = 0; 36 m_pETEn = 0; 37 for(curPtBlock = m_FirstPtBlock.next; --m_ 37 for(curPtBlock = m_FirstPtBlock.next; --m_numAllocPtBlocks >= 0;){ 38 POINTBLOCK* tmpPtBlock; 38 POINTBLOCK* tmpPtBlock; 39 tmpPtBlock = curPtBlock->next; 39 tmpPtBlock = curPtBlock->next; 40 cmem_free(curPtBlock); 40 cmem_free(curPtBlock); 41 curPtBlock = tmpPtBlock; 41 curPtBlock = tmpPtBlock; 42 } 42 } 43 m_numAllocPtBlocks = 0; 43 m_numAllocPtBlocks = 0; 44 } 44 } 45 45 46 typedef void (*scan_func)(void*,int,int,int) 46 typedef void (*scan_func)(void*,int,int,int); 47 47 48 void scan(int Count, /* number of 48 void scan(int Count, /* number of pts */ 49 const point* Pts, /* the pts 49 const point* Pts, /* the pts */ 50 int rule, /* winding r 50 int rule, /* winding rule */ 51 scan_func a_proc,void* a_tag){ 51 scan_func a_proc,void* a_tag){ 52 // polytoregion 52 // polytoregion 53 // Scan converts a polygon by returning 53 // Scan converts a polygon by returning a run-length 54 // encoding of the resultant bitmap -- t 54 // encoding of the resultant bitmap -- the run-length 55 // encoding is in the form of an array o 55 // encoding is in the form of an array of rectangles. 56 56 57 EdgeTableEntry* pAET; /* Active Edge Tab 57 EdgeTableEntry* pAET; /* Active Edge Table */ 58 int y; /* current scanlin 58 int y; /* current scanline */ 59 int iPts = 0; /* number of pts i 59 int iPts = 0; /* number of pts in buffer */ 60 EdgeTableEntry* pWETE; /* Winding Edge Ta 60 EdgeTableEntry* pWETE; /* Winding Edge Table Entry*/ 61 ScanLineList* pSLL; /* current scanLin 61 ScanLineList* pSLL; /* current scanLineList */ 62 62 63 EdgeTableEntry* pPrevAET; /* ptr to 63 EdgeTableEntry* pPrevAET; /* ptr to previous AET */ 64 EdgeTable ET; /* header 64 EdgeTable ET; /* header node for ET */ 65 EdgeTableEntry AET; /* header 65 EdgeTableEntry AET; /* header node for AET */ 66 ScanLineListBlock SLLBlock; /* header 66 ScanLineListBlock SLLBlock; /* header for scanlinelist */ 67 int fixWAET = 0; 67 int fixWAET = 0; 68 POINTBLOCK* curPtBlock; 68 POINTBLOCK* curPtBlock; 69 int numFullPtBlocks = 0; 69 int numFullPtBlocks = 0; 70 70 71 if(a_proc==NULL) return; 71 if(a_proc==NULL) return; 72 if(Count==0) return; 72 if(Count==0) return; 73 73 74 /* special case a rectangle */ 74 /* special case a rectangle */ 75 point* pts = (point*)Pts; 75 point* pts = (point*)Pts; 76 if (((Count == 4) || 76 if (((Count == 4) || 77 ((Count == 5) && (pts[4].x == pts[0].x) && 77 ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) && 78 (((pts[0].y == pts[1].y) && 78 (((pts[0].y == pts[1].y) && 79 (pts[1].x == pts[2].x) && 79 (pts[1].x == pts[2].x) && 80 (pts[2].y == pts[3].y) && 80 (pts[2].y == pts[3].y) && 81 (pts[3].x == pts[0].x)) || 81 (pts[3].x == pts[0].x)) || 82 ((pts[0].x == pts[1].x) && 82 ((pts[0].x == pts[1].x) && 83 (pts[1].y == pts[2].y) && 83 (pts[1].y == pts[2].y) && 84 (pts[2].x == pts[3].x) && 84 (pts[2].x == pts[3].x) && 85 (pts[3].y == pts[0].y)))) 85 (pts[3].y == pts[0].y)))) 86 { 86 { 87 int xmin,xmax,ymin,ymax; 87 int xmin,xmax,ymin,ymax; 88 xmin = (int)mn(pts[0].x, pts[2].x); 88 xmin = (int)mn(pts[0].x, pts[2].x); 89 ymin = (int)mn(pts[0].y, pts[2].y); 89 ymin = (int)mn(pts[0].y, pts[2].y); 90 xmax = (int)mx(pts[0].x, pts[2].x); 90 xmax = (int)mx(pts[0].x, pts[2].x); 91 ymax = (int)mx(pts[0].y, pts[2].y); 91 ymax = (int)mx(pts[0].y, pts[2].y); 92 if ((xmin != xmax) && (ymin != ymax)) 92 if ((xmin != xmax) && (ymin != ymax)) 93 { 93 { 94 for(y=ymin;y<=ymax;y++) a_proc( 94 for(y=ymin;y<=ymax;y++) a_proc(a_tag,xmin ,xmax ,y); 95 } 95 } 96 return; 96 return; 97 } 97 } 98 98 99 if(Count>m_pETEn) 99 if(Count>m_pETEn) 100 { 100 { 101 cmem_free(m_pETEs); 101 cmem_free(m_pETEs); 102 m_pETEn = Count; 102 m_pETEn = Count; 103 m_pETEs = cmem_alloc<EdgeTableEntry>(m_pETEn 103 m_pETEs = cmem_alloc<EdgeTableEntry>(m_pETEn); 104 if(m_pETEs==NULL) 104 if(m_pETEs==NULL) 105 { 105 { 106 m_pETEn = 0; 106 m_pETEn = 0; 107 return; 107 return; 108 } 108 } 109 } 109 } 110 110 111 /*G.Barrand : quiet g++-11 warnings : begi 111 /*G.Barrand : quiet g++-11 warnings : begin :*/ 112 ET.scanlines.next = (ScanLineList*)NULL; 112 ET.scanlines.next = (ScanLineList*)NULL; 113 ET.ymax = SMALL_COORDINATE; 113 ET.ymax = SMALL_COORDINATE; 114 ET.ymin = LARGE_COORDINATE; 114 ET.ymin = LARGE_COORDINATE; 115 115 116 AET.next = (EdgeTableEntry*)NULL; 116 AET.next = (EdgeTableEntry*)NULL; 117 AET.back = (EdgeTableEntry*)NULL; 117 AET.back = (EdgeTableEntry*)NULL; 118 AET.nextWETE = (EdgeTableEntry*)NULL; 118 AET.nextWETE = (EdgeTableEntry*)NULL; 119 AET.bres.minor_axis = SMALL_COORDINATE; 119 AET.bres.minor_axis = SMALL_COORDINATE; 120 120 121 SLLBlock.next = (ScanLineListBlock*)NULL; 121 SLLBlock.next = (ScanLineListBlock*)NULL; 122 /*G.Barrand : end.*/ 122 /*G.Barrand : end.*/ 123 123 124 CreateETandAET (Count,(point*)Pts, &ET, &A 124 CreateETandAET (Count,(point*)Pts, &ET, &AET, m_pETEs, &SLLBlock); 125 125 126 pSLL = ET.scanlines.next; 126 pSLL = ET.scanlines.next; 127 127 128 curPtBlock = &m_FirstPtBlock; 128 curPtBlock = &m_FirstPtBlock; 129 pts = m_FirstPtBlock.pts; 129 pts = m_FirstPtBlock.pts; 130 130 131 131 132 if (rule==0) 132 if (rule==0) 133 { 133 { 134 /* 134 /* 135 * for each scanline 135 * for each scanline 136 */ 136 */ 137 for (y = ET.ymin; y < ET.ymax; y++) { 137 for (y = ET.ymin; y < ET.ymax; y++) { 138 /* 138 /* 139 * Add a new edge to the active e 139 * Add a new edge to the active edge table when we 140 * get to the next edge. 140 * get to the next edge. 141 */ 141 */ 142 if (pSLL != NULL && y == pSLL->sca 142 if (pSLL != NULL && y == pSLL->scanline) 143 { 143 { 144 LoadAET(&AET, pSLL->edgelist); 144 LoadAET(&AET, pSLL->edgelist); 145 pSLL = pSLL->next; 145 pSLL = pSLL->next; 146 } 146 } 147 pPrevAET = &AET; 147 pPrevAET = &AET; 148 pAET = AET.next; 148 pAET = AET.next; 149 149 150 /* 150 /* 151 * for each active edge 151 * for each active edge 152 */ 152 */ 153 while (pAET) { 153 while (pAET) { 154 pts->x = pAET->bres.minor_axis 154 pts->x = pAET->bres.minor_axis; 155 pts->y = y; 155 pts->y = y; 156 pts++; 156 pts++; 157 iPts++; 157 iPts++; 158 158 159 /* 159 /* 160 * send out the buffer 160 * send out the buffer 161 */ 161 */ 162 if (iPts == NUMPTSTOBUFFER) 162 if (iPts == NUMPTSTOBUFFER) 163 { 163 { 164 if(numFullPtBlocks < m_num 164 if(numFullPtBlocks < m_numAllocPtBlocks) 165 { 165 { 166 curPtBlock = curPtBloc 166 curPtBlock = curPtBlock->next; 167 } 167 } 168 else 168 else 169 { 169 { 170 POINTBLOCK* tmpPtBlock = cmem_alloc<POIN 170 POINTBLOCK* tmpPtBlock = cmem_alloc<POINTBLOCK>(1); 171 if(tmpPtBlock==NULL) 171 if(tmpPtBlock==NULL) 172 { 172 { 173 FreeStorage(SLLBlock.next); 173 FreeStorage(SLLBlock.next); 174 return; 174 return; 175 } 175 } 176 tmpPtBlock->next = NULL; /*Barrand*/ 176 tmpPtBlock->next = NULL; /*Barrand*/ 177 curPtBlock->next = tmpPtBlock; 177 curPtBlock->next = tmpPtBlock; 178 curPtBlock = tmpPtBlock; 178 curPtBlock = tmpPtBlock; 179 m_numAllocPtBlocks++; 179 m_numAllocPtBlocks++; 180 } 180 } 181 numFullPtBlocks++; 181 numFullPtBlocks++; 182 pts = curPtBlock->pts; 182 pts = curPtBlock->pts; 183 iPts = 0; 183 iPts = 0; 184 } 184 } 185 185 186 EVALUATEEDGEEVENODD(pAET, pPre 186 EVALUATEEDGEEVENODD(pAET, pPrevAET, y) 187 } 187 } 188 (void) InsertAndSort(&AET); 188 (void) InsertAndSort(&AET); 189 } 189 } 190 } 190 } 191 else 191 else 192 { 192 { 193 /* 193 /* 194 * for each scanline 194 * for each scanline 195 */ 195 */ 196 for (y = ET.ymin; y < ET.ymax; y++) { 196 for (y = ET.ymin; y < ET.ymax; y++) { 197 /* 197 /* 198 * Add a new edge to the active e 198 * Add a new edge to the active edge table when we 199 * get to the next edge. 199 * get to the next edge. 200 */ 200 */ 201 if (pSLL != NULL && y == pSLL->sca 201 if (pSLL != NULL && y == pSLL->scanline) 202 { 202 { 203 LoadAET(&AET, pSLL->edgelist); 203 LoadAET(&AET, pSLL->edgelist); 204 ComputeWAET(&AET); 204 ComputeWAET(&AET); 205 pSLL = pSLL->next; 205 pSLL = pSLL->next; 206 } 206 } 207 pPrevAET = &AET; 207 pPrevAET = &AET; 208 pAET = AET.next; 208 pAET = AET.next; 209 pWETE = pAET; 209 pWETE = pAET; 210 210 211 /* 211 /* 212 * for each active edge 212 * for each active edge 213 */ 213 */ 214 while (pAET) { 214 while (pAET) { 215 /* 215 /* 216 * add to the buffer only tho 216 * add to the buffer only those edges that 217 * are in the Winding active 217 * are in the Winding active edge table. 218 */ 218 */ 219 if (pWETE == pAET) { 219 if (pWETE == pAET) { 220 pts->x = pAET->bres.minor_ 220 pts->x = pAET->bres.minor_axis; 221 pts->y = y; 221 pts->y = y; 222 pts++; 222 pts++; 223 iPts++; 223 iPts++; 224 224 225 /* 225 /* 226 * send out the buffer 226 * send out the buffer 227 */ 227 */ 228 if (iPts == NUMPTSTOBUFFER) 228 if (iPts == NUMPTSTOBUFFER) 229 { 229 { 230 if(numFullPtBlocks < m_numAllocPtBlocks) 230 if(numFullPtBlocks < m_numAllocPtBlocks) 231 { 231 { 232 curPtBlock = curPtBlock->next; 232 curPtBlock = curPtBlock->next; 233 } 233 } 234 else 234 else 235 { 235 { 236 POINTBLOCK* tmpPtBlock = cmem_alloc< 236 POINTBLOCK* tmpPtBlock = cmem_alloc<POINTBLOCK>(1); 237 if(tmpPtBlock==NUL 237 if(tmpPtBlock==NULL) 238 { 238 { 239 FreeStorage(SLLBlock.next); 239 FreeStorage(SLLBlock.next); 240 return; 240 return; 241 } 241 } 242 tmpPtBlock->next = NULL; /*Barrand*/ 242 tmpPtBlock->next = NULL; /*Barrand*/ 243 curPtBlock->next = tmpPtBlock; 243 curPtBlock->next = tmpPtBlock; 244 curPtBlock = tmpPtBlock; 244 curPtBlock = tmpPtBlock; 245 m_numAllocPtBlocks++; 245 m_numAllocPtBlocks++; 246 } 246 } 247 numFullPtBlocks++; 247 numFullPtBlocks++; 248 pts = curPtBlock->pts; 248 pts = curPtBlock->pts; 249 iPts = 0; 249 iPts = 0; 250 } 250 } 251 pWETE = pWETE->nextWETE; 251 pWETE = pWETE->nextWETE; 252 } 252 } 253 EVALUATEEDGEWINDING(pAET, pPre 253 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) 254 } 254 } 255 255 256 /* 256 /* 257 * recompute the winding active e 257 * recompute the winding active edge table if 258 * we just resorted or have exite 258 * we just resorted or have exited an edge. 259 */ 259 */ 260 if ( (InsertAndSort(&AET)!=0) || ( 260 if ( (InsertAndSort(&AET)!=0) || (fixWAET!=0) ) 261 { 261 { 262 ComputeWAET(&AET); 262 ComputeWAET(&AET); 263 fixWAET = 0; 263 fixWAET = 0; 264 } 264 } 265 } 265 } 266 } 266 } 267 FreeStorage (SLLBlock.next); 267 FreeStorage (SLLBlock.next); 268 268 269 ScanPoints (numFullPtBlocks, iPts, &m_Firs 269 ScanPoints (numFullPtBlocks, iPts, &m_FirstPtBlock,a_proc,a_tag); 270 270 271 } 271 } 272 protected: 272 protected: 273 void ScanPoints (int numFullPtBlocks, 273 void ScanPoints (int numFullPtBlocks, 274 int iCurPtBlock, 274 int iCurPtBlock, 275 POINTBLOCK* FirstPtBlock, 275 POINTBLOCK* FirstPtBlock, 276 scan_func a_proc,void* a_ta 276 scan_func a_proc,void* a_tag) { 277 point* pts; 277 point* pts; 278 POINTBLOCK* CurPtBlock; 278 POINTBLOCK* CurPtBlock; 279 int i; 279 int i; 280 CurPtBlock = FirstPtBlock; 280 CurPtBlock = FirstPtBlock; 281 for ( ; numFullPtBlocks >= 0; numFullPtBlo 281 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) 282 { 282 { 283 /* the loop uses 2 points per iteratio 283 /* the loop uses 2 points per iteration */ 284 i = numFullPtBlocks!=0 ? NUMPTSTOBUFFE 284 i = numFullPtBlocks!=0 ? NUMPTSTOBUFFER >> 1 : iCurPtBlock >> 1 ; 285 for (pts = CurPtBlock->pts; i--; pts + 285 for (pts = CurPtBlock->pts; i--; pts += 2) 286 { 286 { 287 a_proc (a_tag,(int)(pts->x),(int)pts[1]. 287 a_proc (a_tag,(int)(pts->x),(int)pts[1].x,(int)pts->y); 288 } 288 } 289 CurPtBlock = CurPtBlock->next; 289 CurPtBlock = CurPtBlock->next; 290 } 290 } 291 } 291 } 292 292 293 293 294 }; 294 }; 295 295 296 }} 296 }} 297 297 298 #endif 298 #endif