Commit | Line | Data |
---|---|---|
a09e091a JB |
1 | /* |
2 | ||
3 | Copyright 1987, 1998 The Open Group | |
4 | ||
5 | Permission to use, copy, modify, distribute, and sell this software and its | |
6 | documentation for any purpose is hereby granted without fee, provided that | |
7 | the above copyright notice appear in all copies and that both that | |
8 | copyright notice and this permission notice appear in supporting | |
9 | documentation. | |
10 | ||
11 | The above copyright notice and this permission notice shall be included | |
12 | in all copies or substantial portions of the Software. | |
13 | ||
14 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS | |
15 | OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF | |
16 | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. | |
17 | IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR | |
18 | OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, | |
19 | ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR | |
20 | OTHER DEALINGS IN THE SOFTWARE. | |
21 | ||
22 | Except as contained in this notice, the name of The Open Group shall | |
23 | not be used in advertising or otherwise to promote the sale, use or | |
24 | other dealings in this Software without prior written authorization | |
25 | from The Open Group. | |
26 | ||
27 | */ | |
28 | ||
29 | /* | |
30 | * fill.h | |
31 | * | |
32 | * Created by Brian Kelleher; Oct 1985 | |
33 | * | |
34 | * Include file for filled polygon routines. | |
35 | * | |
36 | * These are the data structures needed to scan | |
37 | * convert regions. Two different scan conversion | |
38 | * methods are available -- the even-odd method, and | |
39 | * the winding number method. | |
40 | * The even-odd rule states that a point is inside | |
41 | * the polygon if a ray drawn from that point in any | |
42 | * direction will pass through an odd number of | |
43 | * path segments. | |
44 | * By the winding number rule, a point is decided | |
45 | * to be inside the polygon if a ray drawn from that | |
46 | * point in any direction passes through a different | |
47 | * number of clockwise and counter-clockwise path | |
48 | * segments. | |
49 | * | |
50 | * These data structures are adapted somewhat from | |
51 | * the algorithm in (Foley/Van Dam) for scan converting | |
52 | * polygons. | |
53 | * The basic algorithm is to start at the top (smallest y) | |
54 | * of the polygon, stepping down to the bottom of | |
55 | * the polygon by incrementing the y coordinate. We | |
56 | * keep a list of edges which the current scanline crosses, | |
57 | * sorted by x. This list is called the Active Edge Table (AET) | |
58 | * As we change the y-coordinate, we update each entry in | |
59 | * in the active edge table to reflect the edges new xcoord. | |
60 | * This list must be sorted at each scanline in case | |
61 | * two edges intersect. | |
62 | * We also keep a data structure known as the Edge Table (ET), | |
63 | * which keeps track of all the edges which the current | |
64 | * scanline has not yet reached. The ET is basically a | |
65 | * list of ScanLineList structures containing a list of | |
66 | * edges which are entered at a given scanline. There is one | |
67 | * ScanLineList per scanline at which an edge is entered. | |
68 | * When we enter a new edge, we move it from the ET to the AET. | |
69 | * | |
70 | * From the AET, we can implement the even-odd rule as in | |
71 | * (Foley/Van Dam). | |
72 | * The winding number rule is a little trickier. We also | |
73 | * keep the EdgeTableEntries in the AET linked by the | |
74 | * nextWETE (winding EdgeTableEntry) link. This allows | |
75 | * the edges to be linked just as before for updating | |
76 | * purposes, but only uses the edges linked by the nextWETE | |
77 | * link as edges representing spans of the polygon to | |
78 | * drawn (as with the even-odd rule). | |
79 | */ | |
80 | ||
81 | /* | |
82 | * for the winding number rule | |
83 | */ | |
84 | #define CLOCKWISE 1 | |
85 | #define COUNTERCLOCKWISE -1 | |
86 | ||
87 | typedef struct _EdgeTableEntry { | |
88 | int ymax; /* ycoord at which we exit this edge. */ | |
89 | BRESINFO bres; /* Bresenham info to run the edge */ | |
90 | struct _EdgeTableEntry *next; /* next in the list */ | |
91 | struct _EdgeTableEntry *back; /* for insertion sort */ | |
92 | struct _EdgeTableEntry *nextWETE; /* for winding num rule */ | |
93 | int ClockWise; /* flag for winding number rule */ | |
94 | } EdgeTableEntry; | |
95 | ||
96 | typedef struct _ScanLineList { | |
97 | int scanline; /* the scanline represented */ | |
98 | EdgeTableEntry *edgelist; /* header node */ | |
99 | struct _ScanLineList *next; /* next in the list */ | |
100 | } ScanLineList; | |
101 | ||
102 | typedef struct { | |
103 | int ymax; /* ymax for the polygon */ | |
104 | int ymin; /* ymin for the polygon */ | |
105 | ScanLineList scanlines; /* header node */ | |
106 | } EdgeTable; | |
107 | ||
108 | /* | |
109 | * Here is a struct to help with storage allocation | |
110 | * so we can allocate a big chunk at a time, and then take | |
111 | * pieces from this heap when we need to. | |
112 | */ | |
113 | #define SLLSPERBLOCK 25 | |
114 | ||
115 | typedef struct _ScanLineListBlock { | |
116 | ScanLineList SLLs[SLLSPERBLOCK]; | |
117 | struct _ScanLineListBlock *next; | |
118 | } ScanLineListBlock; | |
119 | ||
120 | /* | |
121 | * number of points to buffer before sending them off | |
122 | * to scanlines() : Must be an even number | |
123 | */ | |
124 | #define NUMPTSTOBUFFER 200 | |
125 | \f | |
126 | /* | |
127 | * | |
128 | * a few macros for the inner loops of the fill code where | |
129 | * performance considerations don't allow a procedure call. | |
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 winding number rule is in effect, so we must notify | |
136 | * the caller when the edge has been removed so he | |
137 | * can reorder the Winding Active Edge Table. | |
138 | */ | |
139 | #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \ | |
140 | if (pAET->ymax == y) { /* leaving this edge */ \ | |
141 | pPrevAET->next = pAET->next; \ | |
142 | pAET = pPrevAET->next; \ | |
143 | fixWAET = 1; \ | |
144 | if (pAET) \ | |
145 | pAET->back = pPrevAET; \ | |
146 | } \ | |
147 | else { \ | |
148 | BRESINCRPGONSTRUCT(pAET->bres); \ | |
149 | pPrevAET = pAET; \ | |
150 | pAET = pAET->next; \ | |
151 | } \ | |
152 | } | |
153 | ||
154 | /* | |
155 | * Evaluate the given edge at the given scanline. | |
156 | * If the edge has expired, then we leave it and fix up | |
157 | * the active edge table; otherwise, we increment the | |
158 | * x value to be ready for the next scanline. | |
159 | * The even-odd rule is in effect. | |
160 | */ | |
161 | #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \ | |
162 | if (pAET->ymax == y) { /* leaving this edge */ \ | |
163 | pPrevAET->next = pAET->next; \ | |
164 | pAET = pPrevAET->next; \ | |
165 | if (pAET) \ | |
166 | pAET->back = pPrevAET; \ | |
167 | } \ | |
168 | else { \ | |
169 | BRESINCRPGONSTRUCT(pAET->bres); \ | |
170 | pPrevAET = pAET; \ | |
171 | pAET = pAET->next; \ | |
172 | } \ | |
173 | } | |
174 | ||
175 | /* mipolyutil.c */ | |
176 | ||
177 | extern _X_EXPORT Bool miCreateETandAET(int /*count */ , | |
178 | DDXPointPtr /*pts */ , | |
179 | EdgeTable * /*ET*/, | |
180 | EdgeTableEntry * /*AET*/, | |
181 | EdgeTableEntry * /*pETEs */ , | |
182 | ScanLineListBlock * /*pSLLBlock */ | |
183 | ); | |
184 | ||
185 | extern _X_EXPORT void miloadAET(EdgeTableEntry * /*AET*/, EdgeTableEntry * /*ETEs */ | |
186 | ); | |
187 | ||
188 | extern _X_EXPORT void micomputeWAET(EdgeTableEntry * /*AET*/); | |
189 | ||
190 | extern _X_EXPORT int miInsertionSort(EdgeTableEntry * /*AET*/); | |
191 | ||
192 | extern _X_EXPORT void miFreeStorage(ScanLineListBlock * /*pSLLBlock */ | |
193 | ); |