| 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 in |
| 12 |
all copies or substantial portions of the Software. |
| 13 |
|
| 14 |
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 15 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 16 |
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| 17 |
OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN |
| 18 |
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 19 |
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 20 |
|
| 21 |
Except as contained in this notice, the name of The Open Group shall not be |
| 22 |
used in advertising or otherwise to promote the sale, use or other dealings |
| 23 |
in this Software without prior written authorization from The Open Group. |
| 24 |
|
| 25 |
|
| 26 |
Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. |
| 27 |
|
| 28 |
All Rights Reserved |
| 29 |
|
| 30 |
Permission to use, copy, modify, and distribute this software and its |
| 31 |
documentation for any purpose and without fee is hereby granted, |
| 32 |
provided that the above copyright notice appear in all copies and that |
| 33 |
both that copyright notice and this permission notice appear in |
| 34 |
supporting documentation, and that the name of Digital not be |
| 35 |
used in advertising or publicity pertaining to distribution of the |
| 36 |
software without specific, written prior permission. |
| 37 |
|
| 38 |
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING |
| 39 |
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL |
| 40 |
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR |
| 41 |
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
| 42 |
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, |
| 43 |
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS |
| 44 |
SOFTWARE. |
| 45 |
|
| 46 |
************************************************************************/ |
| 47 |
|
| 48 |
/* |
| 49 |
* This file contains a few macros to help track |
| 50 |
* the edge of a filled object. The object is assumed |
| 51 |
* to be filled in scanline order, and thus the |
| 52 |
* algorithm used is an extension of Bresenham's line |
| 53 |
* drawing algorithm which assumes that y is always the |
| 54 |
* major axis. |
| 55 |
* Since these pieces of code are the same for any filled shape, |
| 56 |
* it is more convenient to gather the library in one |
| 57 |
* place, but since these pieces of code are also in |
| 58 |
* the inner loops of output primitives, procedure call |
| 59 |
* overhead is out of the question. |
| 60 |
* See the author for a derivation if needed. |
| 61 |
*/ |
| 62 |
|
| 63 |
|
| 64 |
/* |
| 65 |
* In scan converting polygons, we want to choose those pixels |
| 66 |
* which are inside the polygon. Thus, we add .5 to the starting |
| 67 |
* x coordinate for both left and right edges. Now we choose the |
| 68 |
* first pixel which is inside the pgon for the left edge and the |
| 69 |
* first pixel which is outside the pgon for the right edge. |
| 70 |
* Draw the left pixel, but not the right. |
| 71 |
* |
| 72 |
* How to add .5 to the starting x coordinate: |
| 73 |
* If the edge is moving to the right, then subtract dy from the |
| 74 |
* error term from the general form of the algorithm. |
| 75 |
* If the edge is moving to the left, then add dy to the error term. |
| 76 |
* |
| 77 |
* The reason for the difference between edges moving to the left |
| 78 |
* and edges moving to the right is simple: If an edge is moving |
| 79 |
* to the right, then we want the algorithm to flip immediately. |
| 80 |
* If it is moving to the left, then we don't want it to flip until |
| 81 |
* we traverse an entire pixel. |
| 82 |
*/ |
| 83 |
#define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \ |
| 84 |
int dx; /* local storage */ \ |
| 85 |
\ |
| 86 |
/* \ |
| 87 |
* if the edge is horizontal, then it is ignored \ |
| 88 |
* and assumed not to be processed. Otherwise, do this stuff. \ |
| 89 |
*/ \ |
| 90 |
if ((dy) != 0) { \ |
| 91 |
xStart = (x1); \ |
| 92 |
dx = (x2) - xStart; \ |
| 93 |
if (dx < 0) { \ |
| 94 |
m = dx / (dy); \ |
| 95 |
m1 = m - 1; \ |
| 96 |
incr1 = -2 * dx + 2 * (dy) * m1; \ |
| 97 |
incr2 = -2 * dx + 2 * (dy) * m; \ |
| 98 |
d = 2 * m * (dy) - 2 * dx - 2 * (dy); \ |
| 99 |
} else { \ |
| 100 |
m = dx / (dy); \ |
| 101 |
m1 = m + 1; \ |
| 102 |
incr1 = 2 * dx - 2 * (dy) * m1; \ |
| 103 |
incr2 = 2 * dx - 2 * (dy) * m; \ |
| 104 |
d = -2 * m * (dy) + 2 * dx; \ |
| 105 |
} \ |
| 106 |
} \ |
| 107 |
} |
| 108 |
|
| 109 |
#define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \ |
| 110 |
if (m1 > 0) { \ |
| 111 |
if (d > 0) { \ |
| 112 |
minval += m1; \ |
| 113 |
d += incr1; \ |
| 114 |
} \ |
| 115 |
else { \ |
| 116 |
minval += m; \ |
| 117 |
d += incr2; \ |
| 118 |
} \ |
| 119 |
} else {\ |
| 120 |
if (d >= 0) { \ |
| 121 |
minval += m1; \ |
| 122 |
d += incr1; \ |
| 123 |
} \ |
| 124 |
else { \ |
| 125 |
minval += m; \ |
| 126 |
d += incr2; \ |
| 127 |
} \ |
| 128 |
} \ |
| 129 |
} |
| 130 |
|
| 131 |
|
| 132 |
/* |
| 133 |
* This structure contains all of the information needed |
| 134 |
* to run the bresenham algorithm. |
| 135 |
* The variables may be hardcoded into the declarations |
| 136 |
* instead of using this structure to make use of |
| 137 |
* register declarations. |
| 138 |
*/ |
| 139 |
typedef struct { |
| 140 |
int minor_axis; /* minor axis */ |
| 141 |
int d; /* decision variable */ |
| 142 |
int m, m1; /* slope and slope+1 */ |
| 143 |
int incr1, incr2; /* error increments */ |
| 144 |
} BRESINFO; |
| 145 |
|
| 146 |
|
| 147 |
#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \ |
| 148 |
BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \ |
| 149 |
bres.m, bres.m1, bres.incr1, bres.incr2) |
| 150 |
|
| 151 |
#define BRESINCRPGONSTRUCT(bres) \ |
| 152 |
BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2) |
| 153 |
|
| 154 |
|
| 155 |
|
| 156 |
/* |
| 157 |
* These are the data structures needed to scan |
| 158 |
* convert regions. Two different scan conversion |
| 159 |
* methods are available -- the even-odd method, and |
| 160 |
* the winding number method. |
| 161 |
* The even-odd rule states that a point is inside |
| 162 |
* the polygon if a ray drawn from that point in any |
| 163 |
* direction will pass through an odd number of |
| 164 |
* path segments. |
| 165 |
* By the winding number rule, a point is decided |
| 166 |
* to be inside the polygon if a ray drawn from that |
| 167 |
* point in any direction passes through a different |
| 168 |
* number of clockwise and counter-clockwise path |
| 169 |
* segments. |
| 170 |
* |
| 171 |
* These data structures are adapted somewhat from |
| 172 |
* the algorithm in (Foley/Van Dam) for scan converting |
| 173 |
* polygons. |
| 174 |
* The basic algorithm is to start at the top (smallest y) |
| 175 |
* of the polygon, stepping down to the bottom of |
| 176 |
* the polygon by incrementing the y coordinate. We |
| 177 |
* keep a list of edges which the current scanline crosses, |
| 178 |
* sorted by x. This list is called the Active Edge Table (AET) |
| 179 |
* As we change the y-coordinate, we update each entry in |
| 180 |
* in the active edge table to reflect the edges new xcoord. |
| 181 |
* This list must be sorted at each scanline in case |
| 182 |
* two edges intersect. |
| 183 |
* We also keep a data structure known as the Edge Table (ET), |
| 184 |
* which keeps track of all the edges which the current |
| 185 |
* scanline has not yet reached. The ET is basically a |
| 186 |
* list of ScanLineList structures containing a list of |
| 187 |
* edges which are entered at a given scanline. There is one |
| 188 |
* ScanLineList per scanline at which an edge is entered. |
| 189 |
* When we enter a new edge, we move it from the ET to the AET. |
| 190 |
* |
| 191 |
* From the AET, we can implement the even-odd rule as in |
| 192 |
* (Foley/Van Dam). |
| 193 |
* The winding number rule is a little trickier. We also |
| 194 |
* keep the EdgeTableEntries in the AET linked by the |
| 195 |
* nextWETE (winding EdgeTableEntry) link. This allows |
| 196 |
* the edges to be linked just as before for updating |
| 197 |
* purposes, but only uses the edges linked by the nextWETE |
| 198 |
* link as edges representing spans of the polygon to |
| 199 |
* drawn (as with the even-odd rule). |
| 200 |
*/ |
| 201 |
|
| 202 |
/* |
| 203 |
* for the winding number rule |
| 204 |
*/ |
| 205 |
#define CLOCKWISE 1 |
| 206 |
#define COUNTERCLOCKWISE -1 |
| 207 |
|
| 208 |
typedef struct _EdgeTableEntry { |
| 209 |
int ymax; /* ycoord at which we exit this edge. */ |
| 210 |
BRESINFO bres; /* Bresenham info to run the edge */ |
| 211 |
struct _EdgeTableEntry *next; /* next in the list */ |
| 212 |
struct _EdgeTableEntry *back; /* for insertion sort */ |
| 213 |
struct _EdgeTableEntry *nextWETE; /* for winding num rule */ |
| 214 |
int ClockWise; /* flag for winding number rule */ |
| 215 |
} EdgeTableEntry; |
| 216 |
|
| 217 |
|
| 218 |
typedef struct _ScanLineList{ |
| 219 |
int scanline; /* the scanline represented */ |
| 220 |
EdgeTableEntry *edgelist; /* header node */ |
| 221 |
struct _ScanLineList *next; /* next in the list */ |
| 222 |
} ScanLineList; |
| 223 |
|
| 224 |
|
| 225 |
typedef struct { |
| 226 |
int ymax; /* ymax for the polygon */ |
| 227 |
int ymin; /* ymin for the polygon */ |
| 228 |
ScanLineList scanlines; /* header node */ |
| 229 |
} EdgeTable; |
| 230 |
|
| 231 |
|
| 232 |
/* |
| 233 |
* Here is a struct to help with storage allocation |
| 234 |
* so we can allocate a big chunk at a time, and then take |
| 235 |
* pieces from this heap when we need to. |
| 236 |
*/ |
| 237 |
#define SLLSPERBLOCK 25 |
| 238 |
|
| 239 |
typedef struct _ScanLineListBlock { |
| 240 |
ScanLineList SLLs[SLLSPERBLOCK]; |
| 241 |
struct _ScanLineListBlock *next; |
| 242 |
} ScanLineListBlock; |
| 243 |
|
| 244 |
|
| 245 |
|
| 246 |
/* |
| 247 |
* |
| 248 |
* a few macros for the inner loops of the fill code where |
| 249 |
* performance considerations don't allow a procedure call. |
| 250 |
* |
| 251 |
* Evaluate the given edge at the given scanline. |
| 252 |
* If the edge has expired, then we leave it and fix up |
| 253 |
* the active edge table; otherwise, we increment the |
| 254 |
* x value to be ready for the next scanline. |
| 255 |
* The winding number rule is in effect, so we must notify |
| 256 |
* the caller when the edge has been removed so he |
| 257 |
* can reorder the Winding Active Edge Table. |
| 258 |
*/ |
| 259 |
#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \ |
| 260 |
if (pAET->ymax == y) { /* leaving this edge */ \ |
| 261 |
pPrevAET->next = pAET->next; \ |
| 262 |
pAET = pPrevAET->next; \ |
| 263 |
fixWAET = 1; \ |
| 264 |
if (pAET) \ |
| 265 |
pAET->back = pPrevAET; \ |
| 266 |
} \ |
| 267 |
else { \ |
| 268 |
BRESINCRPGONSTRUCT(pAET->bres); \ |
| 269 |
pPrevAET = pAET; \ |
| 270 |
pAET = pAET->next; \ |
| 271 |
} \ |
| 272 |
} |
| 273 |
|
| 274 |
|
| 275 |
/* |
| 276 |
* Evaluate the given edge at the given scanline. |
| 277 |
* If the edge has expired, then we leave it and fix up |
| 278 |
* the active edge table; otherwise, we increment the |
| 279 |
* x value to be ready for the next scanline. |
| 280 |
* The even-odd rule is in effect. |
| 281 |
*/ |
| 282 |
#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \ |
| 283 |
if (pAET->ymax == y) { /* leaving this edge */ \ |
| 284 |
pPrevAET->next = pAET->next; \ |
| 285 |
pAET = pPrevAET->next; \ |
| 286 |
if (pAET) \ |
| 287 |
pAET->back = pPrevAET; \ |
| 288 |
} \ |
| 289 |
else { \ |
| 290 |
BRESINCRPGONSTRUCT(pAET->bres); \ |
| 291 |
pPrevAET = pAET; \ |
| 292 |
pAET = pAET->next; \ |
| 293 |
} \ |
| 294 |
} |