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 ,int a_pts_xmin,int a_pts_ymin,int a_pts_ymax
0100 )
0101 /***************************************************************************/
0102 /*
0103 * CreateEdgeTable
0104 *
0105 * This routine creates the edge table for
0106 * scan converting polygons.
0107 * The Edge Table (ET) looks like:
0108 *
0109 * EdgeTable
0110 * --------
0111 * | ymax | ScanLineLists
0112 * |scanline|-->------------>-------------->...
0113 * -------- |scanline| |scanline|
0114 * |edgelist| |edgelist|
0115 * --------- ---------
0116 * | |
0117 * | |
0118 * V V
0119 * list of ETEs list of ETEs
0120 *
0121 * where ETE is an EdgeTableEntry data structure,
0122 * and there is one ScanLineList per scanline at
0123 * which an edge is initially entered.
0124 *
0125 */
0126 /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
0127 {
0128 point *top, *bottom;
0129 point *PrevPt, *CurrPt;
0130 int iSLLBlock = 0;
0131 int dy;
0132 /*.........................................................................*/
0133
0134 if (count < 2) return;
0135
0136 /*
0137 * initialize the Active Edge Table
0138 */
0139 AET->next = (EdgeTableEntry *)NULL;
0140 AET->back = (EdgeTableEntry *)NULL;
0141 AET->nextWETE = (EdgeTableEntry *)NULL;
0142 AET->bres.minor_axis = a_pts_xmin;
0143
0144 /*
0145 * initialize the Edge Table.
0146 */
0147 ET->scanlines.next = (ScanLineList *)NULL;
0148 ET->ymax = a_pts_ymin;
0149 ET->ymin = a_pts_ymax;
0150 pSLLBlock->next = (ScanLineListBlock *)NULL;
0151
0152 PrevPt = &pts[count-1];
0153
0154 /*
0155 * for each vertex in the array of points.
0156 * In this loop we are dealing with two vertices at
0157 * a time -- these make up one edge of the polygon.
0158 */
0159 while (count--)
0160 {
0161 CurrPt = pts++;
0162
0163 /*
0164 * find out which point is above and which is below.
0165 */
0166 if (PrevPt->y > CurrPt->y)
0167 {
0168 bottom = PrevPt, top = CurrPt;
0169 pETEs->ClockWise = 0;
0170 }
0171 else
0172 {
0173 bottom = CurrPt, top = PrevPt;
0174 pETEs->ClockWise = 1;
0175 }
0176
0177 /*
0178 * don't add horizontal edges to the Edge table.
0179 */
0180 if (bottom->y != top->y)
0181 {
0182 pETEs->ymax = (int)(bottom->y-1); /* -1 so we don't get last scanline */
0183
0184 /*
0185 * initialize integer edge algorithm
0186 */
0187 dy = (int)(bottom->y - top->y);
0188 BRESINITPGONSTRUCT (dy,(int)top->x,(int)bottom->x, pETEs->bres)
0189
0190 InsertEdgeInET (ET, pETEs, (int)top->y, &pSLLBlock, &iSLLBlock);
0191
0192 if (PrevPt->y > ET->ymax) ET->ymax = (int) PrevPt->y;
0193 if (PrevPt->y < ET->ymin) ET->ymin = (int) PrevPt->y;
0194 pETEs++;
0195 }
0196
0197 PrevPt = CurrPt;
0198 }
0199 }
0200
0201 inline void LoadAET(EdgeTableEntry* AET,EdgeTableEntry* ETEs) {
0202 /*
0203 * LoadAET
0204 *
0205 * This routine moves EdgeTableEntries from the
0206 * EdgeTable into the Active Edge Table,
0207 * leaving them sorted by smaller x coordinate.
0208 *
0209 */
0210 EdgeTableEntry *pPrevAET;
0211 EdgeTableEntry *tmp;
0212
0213 pPrevAET = AET;
0214 AET = AET->next;
0215 while(ETEs) {
0216 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
0217 {
0218 pPrevAET = AET;
0219 AET = AET->next;
0220 }
0221 tmp = ETEs->next;
0222 ETEs->next = AET;
0223 if (AET!=NULL)
0224 AET->back = ETEs;
0225 ETEs->back = pPrevAET;
0226 pPrevAET->next = ETEs;
0227 pPrevAET = ETEs;
0228
0229 ETEs = tmp;
0230 }
0231 }
0232
0233 inline void ComputeWAET(EdgeTableEntry* AET) {
0234 /*
0235 * ComputeWAET
0236 *
0237 * This routine links the AET by the
0238 * nextWETE (winding EdgeTableEntry) link for
0239 * use by the winding number rule. The final
0240 * Active Edge Table (AET) might look something
0241 * like:
0242 *
0243 * AET
0244 * ---------- --------- ---------
0245 * |ymax | |ymax | |ymax |
0246 * | ... | |... | |... |
0247 * |next |->|next |->|next |->...
0248 * |nextWETE| |nextWETE| |nextWETE|
0249 * --------- --------- ^--------
0250 * | | |
0251 * V-------------------> V---> ...
0252 *
0253 */
0254 EdgeTableEntry *pWETE;
0255 int inside = 1;
0256 int isInside = 0;
0257
0258 AET->nextWETE = (EdgeTableEntry *)NULL;
0259 pWETE = AET;
0260 AET = AET->next;
0261 while(AET) {
0262 if (AET->ClockWise!=0)
0263 isInside++;
0264 else
0265 isInside--;
0266
0267 if (( (inside==0) && (isInside==0) ) ||
0268 ( (inside!=0) && (isInside!=0) ))
0269 {
0270 pWETE->nextWETE = AET;
0271 pWETE = AET;
0272 inside = !inside;
0273 }
0274 AET = AET->next;
0275 }
0276 pWETE->nextWETE = (EdgeTableEntry *)NULL;
0277 }
0278
0279 inline int InsertAndSort(EdgeTableEntry* AET) {
0280 // InsertAndSort
0281 // Just a simple insertion sort using
0282 // pointers and back pointers to sort the Active
0283 // Edge Table.
0284
0285 EdgeTableEntry *pETEchase;
0286 EdgeTableEntry *pETEinsert;
0287 EdgeTableEntry *pETEchaseBackTMP;
0288 int changed = 0;
0289
0290 AET = AET->next;
0291 while(AET) {
0292 pETEinsert = AET;
0293 pETEchase = AET;
0294 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
0295 pETEchase = pETEchase->back;
0296
0297 AET = AET->next;
0298 if (pETEchase != pETEinsert)
0299 {
0300 pETEchaseBackTMP = pETEchase->back;
0301 pETEinsert->back->next = AET;
0302 if (AET!=NULL)
0303 AET->back = pETEinsert->back;
0304 pETEinsert->next = pETEchase;
0305 pETEchase->back->next = pETEinsert;
0306 pETEchase->back = pETEinsert;
0307 pETEinsert->back = pETEchaseBackTMP;
0308 changed = 1;
0309 }
0310 }
0311 return(changed);
0312 }
0313
0314 inline void FreeStorage(ScanLineListBlock* pSLLBlock){
0315 // Clean up our act.
0316 ScanLineListBlock* tmpSLLBlock;
0317 while(pSLLBlock) {
0318 tmpSLLBlock = pSLLBlock->next;
0319 cmem_free(pSLLBlock);
0320 pSLLBlock = tmpSLLBlock;
0321 }
0322 }
0323
0324 }}
0325
0326 #endif
