OB.DAAC Logo
NASA Logo
Ocean Color Science Software

ocssw V2022
mipoly.h
Go to the documentation of this file.
1 /* $XConsortium: mipoly.h,v 1.2 88/09/06 14:49:30 jim Exp $ */
2 /*
3  * fill.h
4  *
5  * Created by Brian Kelleher; Oct 1985
6  *
7  * Include file for filled polygon routines.
8  *
9  * These are the data structures needed to scan
10  * convert regions. Two different scan conversion
11  * methods are available -- the even-odd method, and
12  * the winding number method.
13  * The even-odd rule states that a point is inside
14  * the polygon if a ray drawn from that point in any
15  * direction will pass through an odd number of
16  * path segments.
17  * By the winding number rule, a point is decided
18  * to be inside the polygon if a ray drawn from that
19  * point in any direction passes through a different
20  * number of clockwise and counter-clockwise path
21  * segments.
22  *
23  * These data structures are adapted somewhat from
24  * the algorithm in (Foley/Van Dam) for scan converting
25  * polygons.
26  * The basic algorithm is to start at the top (smallest y)
27  * of the polygon, stepping down to the bottom of
28  * the polygon by incrementing the y coordinate. We
29  * keep a list of edges which the current scanline crosses,
30  * sorted by x. This list is called the Active Edge Table (AET)
31  * As we change the y-coordinate, we update each entry in
32  * in the active edge table to reflect the edges new xcoord.
33  * This list must be sorted at each scanline in case
34  * two edges intersect.
35  * We also keep a data structure known as the Edge Table (ET),
36  * which keeps track of all the edges which the current
37  * scanline has not yet reached. The ET is basically a
38  * list of ScanLineList structures containing a list of
39  * edges which are entered at a given scanline. There is one
40  * ScanLineList per scanline at which an edge is entered.
41  * When we enter a new edge, we move it from the ET to the AET.
42  *
43  * From the AET, we can implement the even-odd rule as in
44  * (Foley/Van Dam).
45  * The winding number rule is a little trickier. We also
46  * keep the EdgeTableEntries in the AET linked by the
47  * nextWETE (winding EdgeTableEntry) link. This allows
48  * the edges to be linked just as before for updating
49  * purposes, but only uses the edges linked by the nextWETE
50  * link as edges representing spans of the polygon to
51  * drawn (as with the even-odd rule).
52  */
53 
54 /*
55  * for the winding number rule
56  */
57 #define CLOCKWISE 1
58 #define COUNTERCLOCKWISE -1
59 
60 typedef struct _EdgeTableEntry {
61  int ymax; /* ycoord at which we exit this edge. */
62  BRESINFO bres; /* Bresenham info to run the edge */
63  struct _EdgeTableEntry *next; /* next in the list */
64  struct _EdgeTableEntry *back; /* for insertion sort */
65  struct _EdgeTableEntry *nextWETE; /* for winding num rule */
66  int ClockWise; /* flag for winding number rule */
67 } EdgeTableEntry;
68 
69 typedef struct _ScanLineList {
70  int scanline; /* the scanline represented */
71  EdgeTableEntry *edgelist; /* header node */
72  struct _ScanLineList *next; /* next in the list */
73 } ScanLineList;
74 
75 typedef struct {
76  int ymax; /* ymax for the polygon */
77  int ymin; /* ymin for the polygon */
78  ScanLineList scanlines; /* header node */
79 } EdgeTable;
80 
81 
82 /*
83  * Here is a struct to help with storage allocation
84  * so we can allocate a big chunk at a time, and then take
85  * pieces from this heap when we need to.
86  */
87 #define SLLSPERBLOCK 25
88 
89 typedef struct _ScanLineListBlock {
90  ScanLineList SLLs[SLLSPERBLOCK];
92 } ScanLineListBlock;
93 
94 /*
95  * number of points to buffer before sending them off
96  * to scanlines() : Must be an even number
97  */
98 #define NUMPTSTOBUFFER 200
99 
100 
101 /*
102  *
103  * a few macros for the inner loops of the fill code where
104  * performance considerations don't allow a procedure call.
105  *
106  * Evaluate the given edge at the given scanline.
107  * If the edge has expired, then we leave it and fix up
108  * the active edge table; otherwise, we increment the
109  * x value to be ready for the next scanline.
110  * The winding number rule is in effect, so we must notify
111  * the caller when the edge has been removed so he
112  * can reorder the Winding Active Edge Table.
113  */
114 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
115  if (pAET->ymax == y) { /* leaving this edge */ \
116  pPrevAET->next = pAET->next; \
117  pAET = pPrevAET->next; \
118  fixWAET = 1; \
119  if (pAET) \
120  pAET->back = pPrevAET; \
121  } \
122  else { \
123  BRESINCRPGONSTRUCT(pAET->bres); \
124  pPrevAET = pAET; \
125  pAET = pAET->next; \
126  } \
127 }
128 
129 
130 /*
131  * Evaluate the given edge at the given scanline.
132  * If the edge has expired, then we leave it and fix up
133  * the active edge table; otherwise, we increment the
134  * x value to be ready for the next scanline.
135  * The even-odd rule is in effect.
136  */
137 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
138  if (pAET->ymax == y) { /* leaving this edge */ \
139  pPrevAET->next = pAET->next; \
140  pAET = pPrevAET->next; \
141  if (pAET) \
142  pAET->back = pPrevAET; \
143  } \
144  else { \
145  BRESINCRPGONSTRUCT(pAET->bres); \
146  pPrevAET = pAET; \
147  pAET = pAET->next; \
148  } \
149 }
int ymin
Definition: mipoly.h:77
ScanLineList SLLs[SLLSPERBLOCK]
Definition: mipoly.h:90
struct _ScanLineListBlock * next
Definition: mipoly.h:91
int ClockWise
Definition: mipoly.h:66
struct _ScanLineList * next
Definition: mipoly.h:72
EdgeTableEntry * edgelist
Definition: mipoly.h:71
struct _EdgeTableEntry * nextWETE
Definition: mipoly.h:65
int ymax
Definition: mipoly.h:76
struct _EdgeTableEntry * next
Definition: mipoly.h:63
BRESINFO bres
Definition: mipoly.h:62
struct _EdgeTableEntry * back
Definition: mipoly.h:64
#define SLLSPERBLOCK
Definition: mipoly.h:87
int scanline
Definition: mipoly.h:70
ScanLineList scanlines
Definition: mipoly.h:78