Geant4 Cross Reference |
1 // Copyright (C) 2010, Guy Barrand. All rights 2 // See the file tools.license for terms. 3 4 #ifndef tools_zb_line 5 #define tools_zb_line 6 7 /* from X/poly.h */ 8 9 /* 10 * This file contains a few macros to help 11 * the edge of a filled object. The objec 12 * to be filled in scanline order, and thu 13 * algorithm used is an extension of Brese 14 * drawing algorithm which assumes that y 15 * major axis. 16 * Since these pieces of code are the same 17 * it is more convenient to gather the lib 18 * place, but since these pieces of code a 19 * the inner loops of output primitives, p 20 * overhead is out of the question. 21 * See the author for a derivation if need 22 */ 23 24 25 /* 26 * In scan converting polygons, we want to ch 27 * which are inside the polygon. Thus, we ad 28 * x coordinate for both left and right edges 29 * first pixel which is inside the pgon for t 30 * first pixel which is outside the pgon for 31 * Draw the left pixel, but not the right. 32 * 33 * How to add .5 to the starting x coordinate 34 * If the edge is moving to the right, th 35 * error term from the general form of the al 36 * If the edge is moving to the left, the 37 * 38 * The reason for the difference between edge 39 * and edges moving to the right is simple: 40 * to the right, then we want the algorithm t 41 * If it is moving to the left, then we don't 42 * we traverse an entire pixel. 43 */ 44 #define LARGE_COORDINATE 1000000 45 #define SMALL_COORDINATE -LARGE_COORDINATE 46 47 #define BRESINITPGON(dy, x1, x2, xStart, d, m, 48 int dx; /* local storage */ \ 49 \ 50 /* \ 51 * if the edge is horizontal, then it is 52 * and assumed not to be processed. Othe 53 */ \ 54 if ((dy) != 0) { \ 55 xStart = (x1); \ 56 dx = (x2) - xStart; \ 57 if (dx < 0) { \ 58 m = dx / (dy); \ 59 m1 = m - 1; \ 60 incr1 = -2 * dx + 2 * (dy) * m1; \ 61 incr2 = -2 * dx + 2 * (dy) * m; \ 62 d = 2 * m * (dy) - 2 * dx - 2 * (d 63 } else { \ 64 m = dx / (dy); \ 65 m1 = m + 1; \ 66 incr1 = 2 * dx - 2 * (dy) * m1; \ 67 incr2 = 2 * dx - 2 * (dy) * m; \ 68 d = -2 * m * (dy) + 2 * dx; \ 69 } \ 70 } \ 71 } 72 73 #define BRESINCRPGON(d, minval, m, m1, incr1, 74 if (m1 > 0) { \ 75 if (d > 0) { \ 76 minval += m1; \ 77 d += incr1; \ 78 } \ 79 else { \ 80 minval += m; \ 81 d += incr2; \ 82 } \ 83 } else {\ 84 if (d >= 0) { \ 85 minval += m1; \ 86 d += incr1; \ 87 } \ 88 else { \ 89 minval += m; \ 90 d += incr2; \ 91 } \ 92 } \ 93 } 94 95 96 /* 97 * This structure contains all of the info 98 * to run the bresenham algorithm. 99 * The variables may be hardcoded into the 100 * instead of using this structure to make 101 * register declarations. 102 */ 103 typedef struct { 104 int minor_axis; /* minor axis */ 105 int d; /* decision variable */ 106 int m, m1; /* slope and slope+1 */ 107 int incr1, incr2; /* error increments */ 108 } BRESINFO; 109 110 111 #define BRESINITPGONSTRUCT(dmaj, min1, min2, b 112 BRESINITPGON(dmaj, min1, min2, bres.minor_ax 113 bres.m, bres.m1, bres.inc 114 115 #define BRESINCRPGONSTRUCT(bres) \ 116 BRESINCRPGON(bres.d, bres.minor_axis, 117 118 119 120 /* 121 * These are the data structures needed to 122 * convert regions. Two different scan co 123 * methods are available -- the even-odd m 124 * the winding number method. 125 * The even-odd rule states that a point i 126 * the polygon if a ray drawn from that po 127 * direction will pass through an odd numb 128 * path segments. 129 * By the winding number rule, a point is 130 * to be inside the polygon if a ray drawn 131 * point in any direction passes through a 132 * number of clockwise and counter-clockwi 133 * segments. 134 * 135 * These data structures are adapted somew 136 * the algorithm in (Foley/Van Dam) for sc 137 * polygons. 138 * The basic algorithm is to start at the 139 * of the polygon, stepping down to the bo 140 * the polygon by incrementing the y coord 141 * keep a list of edges which the current 142 * sorted by x. This list is called the A 143 * As we change the y-coordinate, we updat 144 * in the active edge table to reflect the 145 * This list must be sorted at each scanli 146 * two edges intersect. 147 * We also keep a data structure known as 148 * which keeps track of all the edges whic 149 * scanline has not yet reached. The ET i 150 * list of ScanLineList structures contain 151 * edges which are entered at a given scan 152 * ScanLineList per scanline at which an e 153 * When we enter a new edge, we move it fr 154 * 155 * From the AET, we can implement the even 156 * (Foley/Van Dam). 157 * The winding number rule is a little tri 158 * keep the EdgeTableEntries in the AET li 159 * nextWETE (winding EdgeTableEntry) link. 160 * the edges to be linked just as before f 161 * purposes, but only uses the edges linke 162 * link as edges representing spans of the 163 * drawn (as with the even-odd rule). 164 */ 165 166 /* 167 * for the winding number rule 168 */ 169 //#define CLOCKWISE 1 170 //#define COUNTERCLOCKWISE -1 171 172 typedef struct _EdgeTableEntry { 173 int ymax; /* ycoord at which 174 BRESINFO bres; /* Bresenham info t 175 struct _EdgeTableEntry *next; /* ne 176 struct _EdgeTableEntry *back; /* fo 177 struct _EdgeTableEntry *nextWETE; /* fo 178 int ClockWise; /* flag for winding 179 } EdgeTableEntry; 180 181 182 typedef struct _ScanLineList{ 183 int scanline; /* the scanlin 184 EdgeTableEntry *edgelist; /* header node 185 struct _ScanLineList *next; /* next in t 186 } ScanLineList; 187 188 189 typedef struct { 190 int ymax; /* ymax for the 191 int ymin; /* ymin for the 192 ScanLineList scanlines; /* header node 193 } EdgeTable; 194 195 196 /* 197 * Here is a struct to help with storage alloc 198 * so we can allocate a big chunk at a time, a 199 * pieces from this heap when we need to. 200 */ 201 #define SLLSPERBLOCK 25 202 203 typedef struct _ScanLineListBlock { 204 ScanLineList SLLs[SLLSPERBLOCK]; 205 struct _ScanLineListBlock *next; 206 } ScanLineListBlock; 207 208 209 210 /* 211 * 212 * a few macros for the inner loops of the 213 * performance considerations don't allow 214 * 215 * Evaluate the given edge at the given sc 216 * If the edge has expired, then we leave 217 * the active edge table; otherwise, we in 218 * x value to be ready for the next scanli 219 * The winding number rule is in effect, s 220 * the caller when the edge has been remov 221 * can reorder the Winding Active Edge Tab 222 */ 223 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, 224 if (pAET->ymax == y) { /* leaving 225 pPrevAET->next = pAET->next; \ 226 pAET = pPrevAET->next; \ 227 fixWAET = 1; \ 228 if (pAET) \ 229 pAET->back = pPrevAET; \ 230 } \ 231 else { \ 232 BRESINCRPGONSTRUCT(pAET->bres) \ 233 pPrevAET = pAET; \ 234 pAET = pAET->next; \ 235 } \ 236 } 237 238 239 /* 240 * Evaluate the given edge at the given sc 241 * If the edge has expired, then we leave 242 * the active edge table; otherwise, we in 243 * x value to be ready for the next scanli 244 * The even-odd rule is in effect. 245 */ 246 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) 247 if (pAET->ymax == y) { /* leaving 248 pPrevAET->next = pAET->next; \ 249 pAET = pPrevAET->next; \ 250 if (pAET) \ 251 pAET->back = pPrevAET; \ 252 } \ 253 else { \ 254 BRESINCRPGONSTRUCT(pAET->bres) \ 255 pPrevAET = pAET; \ 256 pAET = pAET->next; \ 257 } \ 258 } 259 260 261 #endif