Geant4 Cross Reference

Cross-Referencing   Geant4
Geant4/externals/g4tools/include/tools/zb/line

Version: [ ReleaseNotes ] [ 1.0 ] [ 1.1 ] [ 2.0 ] [ 3.0 ] [ 3.1 ] [ 3.2 ] [ 4.0 ] [ 4.0.p1 ] [ 4.0.p2 ] [ 4.1 ] [ 4.1.p1 ] [ 5.0 ] [ 5.0.p1 ] [ 5.1 ] [ 5.1.p1 ] [ 5.2 ] [ 5.2.p1 ] [ 5.2.p2 ] [ 6.0 ] [ 6.0.p1 ] [ 6.1 ] [ 6.2 ] [ 6.2.p1 ] [ 6.2.p2 ] [ 7.0 ] [ 7.0.p1 ] [ 7.1 ] [ 7.1.p1 ] [ 8.0 ] [ 8.0.p1 ] [ 8.1 ] [ 8.1.p1 ] [ 8.1.p2 ] [ 8.2 ] [ 8.2.p1 ] [ 8.3 ] [ 8.3.p1 ] [ 8.3.p2 ] [ 9.0 ] [ 9.0.p1 ] [ 9.0.p2 ] [ 9.1 ] [ 9.1.p1 ] [ 9.1.p2 ] [ 9.1.p3 ] [ 9.2 ] [ 9.2.p1 ] [ 9.2.p2 ] [ 9.2.p3 ] [ 9.2.p4 ] [ 9.3 ] [ 9.3.p1 ] [ 9.3.p2 ] [ 9.4 ] [ 9.4.p1 ] [ 9.4.p2 ] [ 9.4.p3 ] [ 9.4.p4 ] [ 9.5 ] [ 9.5.p1 ] [ 9.5.p2 ] [ 9.6 ] [ 9.6.p1 ] [ 9.6.p2 ] [ 9.6.p3 ] [ 9.6.p4 ] [ 10.0 ] [ 10.0.p1 ] [ 10.0.p2 ] [ 10.0.p3 ] [ 10.0.p4 ] [ 10.1 ] [ 10.1.p1 ] [ 10.1.p2 ] [ 10.1.p3 ] [ 10.2 ] [ 10.2.p1 ] [ 10.2.p2 ] [ 10.2.p3 ] [ 10.3 ] [ 10.3.p1 ] [ 10.3.p2 ] [ 10.3.p3 ] [ 10.4 ] [ 10.4.p1 ] [ 10.4.p2 ] [ 10.4.p3 ] [ 10.5 ] [ 10.5.p1 ] [ 10.6 ] [ 10.6.p1 ] [ 10.6.p2 ] [ 10.6.p3 ] [ 10.7 ] [ 10.7.p1 ] [ 10.7.p2 ] [ 10.7.p3 ] [ 10.7.p4 ] [ 11.0 ] [ 11.0.p1 ] [ 11.0.p2 ] [ 11.0.p3, ] [ 11.0.p4 ] [ 11.1 ] [ 11.1.1 ] [ 11.1.2 ] [ 11.1.3 ] [ 11.2 ] [ 11.2.1 ] [ 11.2.2 ] [ 11.3.0 ]

  1 // Copyright (C) 2010, Guy Barrand. All rights reserved.
  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 track
 11  *     the edge of a filled object.  The object is assumed
 12  *     to be filled in scanline order, and thus the
 13  *     algorithm used is an extension of Bresenham's line
 14  *     drawing algorithm which assumes that y is always the
 15  *     major axis.
 16  *     Since these pieces of code are the same for any filled shape,
 17  *     it is more convenient to gather the library in one
 18  *     place, but since these pieces of code are also in
 19  *     the inner loops of output primitives, procedure call
 20  *     overhead is out of the question.
 21  *     See the author for a derivation if needed.
 22  */
 23 
 24 
 25 /*
 26  *  In scan converting polygons, we want to choose those pixels
 27  *  which are inside the polygon.  Thus, we add .5 to the starting
 28  *  x coordinate for both left and right edges.  Now we choose the
 29  *  first pixel which is inside the pgon for the left edge and the
 30  *  first pixel which is outside the pgon for the right edge.
 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, then subtract dy from the
 35  *  error term from the general form of the algorithm.
 36  *      If the edge is moving to the left, then add dy to the error term.
 37  *
 38  *  The reason for the difference between edges moving to the left
 39  *  and edges moving to the right is simple:  If an edge is moving
 40  *  to the right, then we want the algorithm to flip immediately.
 41  *  If it is moving to the left, then we don't want it to flip until
 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, m1, incr1, incr2) { \
 48     int dx;      /* local storage */ \
 49 \
 50     /* \
 51      *  if the edge is horizontal, then it is ignored \
 52      *  and assumed not to be processed.  Otherwise, do this stuff. \
 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 * (dy); \
 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, incr2) { \
 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 information needed
 98  *     to run the bresenham algorithm.
 99  *     The variables may be hardcoded into the declarations
100  *     instead of using this structure to make use of
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, bres) \
112   BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
113                      bres.m, bres.m1, bres.incr1, bres.incr2)
114 
115 #define BRESINCRPGONSTRUCT(bres) \
116         BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
117 
118 
119 
120 /*
121  *     These are the data structures needed to scan
122  *     convert regions.  Two different scan conversion
123  *     methods are available -- the even-odd method, and
124  *     the winding number method.
125  *     The even-odd rule states that a point is inside
126  *     the polygon if a ray drawn from that point in any
127  *     direction will pass through an odd number of
128  *     path segments.
129  *     By the winding number rule, a point is decided
130  *     to be inside the polygon if a ray drawn from that
131  *     point in any direction passes through a different
132  *     number of clockwise and counter-clockwise path
133  *     segments.
134  *
135  *     These data structures are adapted somewhat from
136  *     the algorithm in (Foley/Van Dam) for scan converting
137  *     polygons.
138  *     The basic algorithm is to start at the top (smallest y)
139  *     of the polygon, stepping down to the bottom of
140  *     the polygon by incrementing the y coordinate.  We
141  *     keep a list of edges which the current scanline crosses,
142  *     sorted by x.  This list is called the Active Edge Table (AET)
143  *     As we change the y-coordinate, we update each entry in
144  *     in the active edge table to reflect the edges new xcoord.
145  *     This list must be sorted at each scanline in case
146  *     two edges intersect.
147  *     We also keep a data structure known as the Edge Table (ET),
148  *     which keeps track of all the edges which the current
149  *     scanline has not yet reached.  The ET is basically a
150  *     list of ScanLineList structures containing a list of
151  *     edges which are entered at a given scanline.  There is one
152  *     ScanLineList per scanline at which an edge is entered.
153  *     When we enter a new edge, we move it from the ET to the AET.
154  *
155  *     From the AET, we can implement the even-odd rule as in
156  *     (Foley/Van Dam).
157  *     The winding number rule is a little trickier.  We also
158  *     keep the EdgeTableEntries in the AET linked by the
159  *     nextWETE (winding EdgeTableEntry) link.  This allows
160  *     the edges to be linked just as before for updating
161  *     purposes, but only uses the edges linked by the nextWETE
162  *     link as edges representing spans of the polygon to
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 we exit this edge. */
174      BRESINFO bres;        /* Bresenham info to run the edge     */
175      struct _EdgeTableEntry *next;       /* next in the list     */
176      struct _EdgeTableEntry *back;       /* for insertion sort   */
177      struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
178      int ClockWise;        /* flag for winding number rule       */
179 } EdgeTableEntry;
180 
181 
182 typedef struct _ScanLineList{
183      int scanline;              /* the scanline represented */
184      EdgeTableEntry *edgelist;  /* header node              */
185      struct _ScanLineList *next;  /* next in the list       */
186 } ScanLineList;
187 
188 
189 typedef struct {
190      int ymax;                 /* ymax for the polygon     */
191      int ymin;                 /* ymin for the polygon     */
192      ScanLineList scanlines;   /* header node              */
193 } EdgeTable;
194 
195 
196 /*
197  * Here is a struct to help with storage allocation
198  * so we can allocate a big chunk at a time, and then take
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 fill code where
213  *     performance considerations don't allow a procedure call.
214  *
215  *     Evaluate the given edge at the given scanline.
216  *     If the edge has expired, then we leave it and fix up
217  *     the active edge table; otherwise, we increment the
218  *     x value to be ready for the next scanline.
219  *     The winding number rule is in effect, so we must notify
220  *     the caller when the edge has been removed so he
221  *     can reorder the Winding Active Edge Table.
222  */
223 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
224    if (pAET->ymax == y) {          /* leaving this edge */ \
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 scanline.
241  *     If the edge has expired, then we leave it and fix up
242  *     the active edge table; otherwise, we increment the
243  *     x value to be ready for the next scanline.
244  *     The even-odd rule is in effect.
245  */
246 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
247    if (pAET->ymax == y) {          /* leaving this edge */ \
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