Warning, /include/Geant4/tools/zb/edge_table is written in an unsupported language. File is not indexed.
0001 // Copyright (C) 2010, Guy Barrand. All rights reserved.
0002 // See the file tools.license for terms.
0003
0004 #ifndef tools_zb_edge_table
0005 #define tools_zb_edge_table
0006
0007 #include "line"
0008 #include "point"
0009
0010 #include "../cmemT"
0011 #include <cstdio> //NULL
0012
0013 namespace tools {
0014 namespace zb {
0015
0016 /***************************************************************************/
0017 inline void InsertEdgeInET (
0018 EdgeTable* ET
0019 ,EdgeTableEntry* ETE
0020 ,int scanline
0021 ,ScanLineListBlock** SLLBlock
0022 ,int* iSLLBlock
0023 )
0024 /***************************************************************************/
0025 /*
0026 * InsertEdgeInET
0027 *
0028 * Insert the given edge into the edge table.
0029 * First we must find the correct bucket in the
0030 * Edge table, then find the right slot in the
0031 * bucket. Finally, we can insert it.
0032 *
0033 */
0034 /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
0035 {
0036 EdgeTableEntry *start, *prev;
0037 ScanLineList *pSLL, *pPrevSLL;
0038 ScanLineListBlock *tmpSLLBlock;
0039 /*.........................................................................*/
0040
0041 /*
0042 * find the right bucket to put the edge into
0043 */
0044 pPrevSLL = &ET->scanlines;
0045 pSLL = pPrevSLL->next;
0046 while (pSLL && (pSLL->scanline < scanline))
0047 {
0048 pPrevSLL = pSLL;
0049 pSLL = pSLL->next;
0050 }
0051
0052 /*
0053 * reassign pSLL (pointer to ScanLineList) if necessary
0054 */
0055 if ( (pSLL==NULL) || (pSLL->scanline > scanline))
0056 {
0057 if (*iSLLBlock > SLLSPERBLOCK-1)
0058 {
0059 tmpSLLBlock = cmem_alloc<ScanLineListBlock>(1);
0060 (*SLLBlock)->next = tmpSLLBlock;
0061 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
0062 *SLLBlock = tmpSLLBlock;
0063 *iSLLBlock = 0;
0064 }
0065 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
0066
0067 pSLL->next = pPrevSLL->next;
0068 pSLL->edgelist = (EdgeTableEntry *)NULL;
0069 pPrevSLL->next = pSLL;
0070 }
0071 pSLL->scanline = scanline;
0072
0073 /*
0074 * now insert the edge in the right bucket
0075 */
0076 prev = (EdgeTableEntry *)NULL;
0077 start = pSLL->edgelist;
0078 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
0079 {
0080 prev = start;
0081 start = start->next;
0082 }
0083 ETE->next = start;
0084
0085 if (prev!=NULL)
0086 prev->next = ETE;
0087 else
0088 pSLL->edgelist = ETE;
0089 }
0090
0091 /***************************************************************************/
0092 inline void CreateETandAET (
0093 int count
0094 ,point* pts
0095 ,EdgeTable* ET
0096 ,EdgeTableEntry* AET
0097 ,EdgeTableEntry* pETEs
0098 ,ScanLineListBlock* pSLLBlock
0099 )
0100 /***************************************************************************/
0101 /*
0102 * CreateEdgeTable
0103 *
0104 * This routine creates the edge table for
0105 * scan converting polygons.
0106 * The Edge Table (ET) looks like:
0107 *
0108 * EdgeTable
0109 * --------
0110 * | ymax | ScanLineLists
0111 * |scanline|-->------------>-------------->...
0112 * -------- |scanline| |scanline|
0113 * |edgelist| |edgelist|
0114 * --------- ---------
0115 * | |
0116 * | |
0117 * V V
0118 * list of ETEs list of ETEs
0119 *
0120 * where ETE is an EdgeTableEntry data structure,
0121 * and there is one ScanLineList per scanline at
0122 * which an edge is initially entered.
0123 *
0124 */
0125 /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
0126 {
0127 point *top, *bottom;
0128 point *PrevPt, *CurrPt;
0129 int iSLLBlock = 0;
0130 int dy;
0131 /*.........................................................................*/
0132
0133 if (count < 2) return;
0134
0135 /*
0136 * initialize the Active Edge Table
0137 */
0138 AET->next = (EdgeTableEntry *)NULL;
0139 AET->back = (EdgeTableEntry *)NULL;
0140 AET->nextWETE = (EdgeTableEntry *)NULL;
0141 AET->bres.minor_axis = SMALL_COORDINATE;
0142
0143 /*
0144 * initialize the Edge Table.
0145 */
0146 ET->scanlines.next = (ScanLineList *)NULL;
0147 ET->ymax = SMALL_COORDINATE;
0148 ET->ymin = LARGE_COORDINATE;
0149 pSLLBlock->next = (ScanLineListBlock *)NULL;
0150
0151 PrevPt = &pts[count-1];
0152
0153 /*
0154 * for each vertex in the array of points.
0155 * In this loop we are dealing with two vertices at
0156 * a time -- these make up one edge of the polygon.
0157 */
0158 while (count--)
0159 {
0160 CurrPt = pts++;
0161
0162 /*
0163 * find out which point is above and which is below.
0164 */
0165 if (PrevPt->y > CurrPt->y)
0166 {
0167 bottom = PrevPt, top = CurrPt;
0168 pETEs->ClockWise = 0;
0169 }
0170 else
0171 {
0172 bottom = CurrPt, top = PrevPt;
0173 pETEs->ClockWise = 1;
0174 }
0175
0176 /*
0177 * don't add horizontal edges to the Edge table.
0178 */
0179 if (bottom->y != top->y)
0180 {
0181 pETEs->ymax = (int)(bottom->y-1); /* -1 so we don't get last scanline */
0182
0183 /*
0184 * initialize integer edge algorithm
0185 */
0186 dy = (int)(bottom->y - top->y);
0187 BRESINITPGONSTRUCT (dy,(int)top->x,(int)bottom->x, pETEs->bres)
0188
0189 InsertEdgeInET (ET, pETEs, (int)top->y, &pSLLBlock, &iSLLBlock);
0190
0191 if (PrevPt->y > ET->ymax) ET->ymax = (int) PrevPt->y;
0192 if (PrevPt->y < ET->ymin) ET->ymin = (int) PrevPt->y;
0193 pETEs++;
0194 }
0195
0196 PrevPt = CurrPt;
0197 }
0198 }
0199
0200 inline void LoadAET(EdgeTableEntry* AET,EdgeTableEntry* ETEs) {
0201 /*
0202 * LoadAET
0203 *
0204 * This routine moves EdgeTableEntries from the
0205 * EdgeTable into the Active Edge Table,
0206 * leaving them sorted by smaller x coordinate.
0207 *
0208 */
0209 EdgeTableEntry *pPrevAET;
0210 EdgeTableEntry *tmp;
0211
0212 pPrevAET = AET;
0213 AET = AET->next;
0214 while(ETEs) {
0215 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
0216 {
0217 pPrevAET = AET;
0218 AET = AET->next;
0219 }
0220 tmp = ETEs->next;
0221 ETEs->next = AET;
0222 if (AET!=NULL)
0223 AET->back = ETEs;
0224 ETEs->back = pPrevAET;
0225 pPrevAET->next = ETEs;
0226 pPrevAET = ETEs;
0227
0228 ETEs = tmp;
0229 }
0230 }
0231
0232 inline void ComputeWAET(EdgeTableEntry* AET) {
0233 /*
0234 * ComputeWAET
0235 *
0236 * This routine links the AET by the
0237 * nextWETE (winding EdgeTableEntry) link for
0238 * use by the winding number rule. The final
0239 * Active Edge Table (AET) might look something
0240 * like:
0241 *
0242 * AET
0243 * ---------- --------- ---------
0244 * |ymax | |ymax | |ymax |
0245 * | ... | |... | |... |
0246 * |next |->|next |->|next |->...
0247 * |nextWETE| |nextWETE| |nextWETE|
0248 * --------- --------- ^--------
0249 * | | |
0250 * V-------------------> V---> ...
0251 *
0252 */
0253 EdgeTableEntry *pWETE;
0254 int inside = 1;
0255 int isInside = 0;
0256
0257 AET->nextWETE = (EdgeTableEntry *)NULL;
0258 pWETE = AET;
0259 AET = AET->next;
0260 while(AET) {
0261 if (AET->ClockWise!=0)
0262 isInside++;
0263 else
0264 isInside--;
0265
0266 if (( (inside==0) && (isInside==0) ) ||
0267 ( (inside!=0) && (isInside!=0) ))
0268 {
0269 pWETE->nextWETE = AET;
0270 pWETE = AET;
0271 inside = !inside;
0272 }
0273 AET = AET->next;
0274 }
0275 pWETE->nextWETE = (EdgeTableEntry *)NULL;
0276 }
0277
0278 inline int InsertAndSort(EdgeTableEntry* AET) {
0279 // InsertAndSort
0280 // Just a simple insertion sort using
0281 // pointers and back pointers to sort the Active
0282 // Edge Table.
0283
0284 EdgeTableEntry *pETEchase;
0285 EdgeTableEntry *pETEinsert;
0286 EdgeTableEntry *pETEchaseBackTMP;
0287 int changed = 0;
0288
0289 AET = AET->next;
0290 while(AET) {
0291 pETEinsert = AET;
0292 pETEchase = AET;
0293 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
0294 pETEchase = pETEchase->back;
0295
0296 AET = AET->next;
0297 if (pETEchase != pETEinsert)
0298 {
0299 pETEchaseBackTMP = pETEchase->back;
0300 pETEinsert->back->next = AET;
0301 if (AET!=NULL)
0302 AET->back = pETEinsert->back;
0303 pETEinsert->next = pETEchase;
0304 pETEchase->back->next = pETEinsert;
0305 pETEchase->back = pETEinsert;
0306 pETEinsert->back = pETEchaseBackTMP;
0307 changed = 1;
0308 }
0309 }
0310 return(changed);
0311 }
0312
0313 inline void FreeStorage(ScanLineListBlock* pSLLBlock){
0314 // Clean up our act.
0315 ScanLineListBlock* tmpSLLBlock;
0316 while(pSLLBlock) {
0317 tmpSLLBlock = pSLLBlock->next;
0318 cmem_free(pSLLBlock);
0319 pSLLBlock = tmpSLLBlock;
0320 }
0321 }
0322
0323 }}
0324
0325 #endif
