| 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 | Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. |
| 26 | |
| 27 | All Rights Reserved |
| 28 | |
| 29 | Permission to use, copy, modify, and distribute this software and its |
| 30 | documentation for any purpose and without fee is hereby granted, |
| 31 | provided that the above copyright notice appear in all copies and that |
| 32 | both that copyright notice and this permission notice appear in |
| 33 | supporting documentation, and that the name of Digital not be |
| 34 | used in advertising or publicity pertaining to distribution of the |
| 35 | software without specific, written prior permission. |
| 36 | |
| 37 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING |
| 38 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL |
| 39 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR |
| 40 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
| 41 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, |
| 42 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS |
| 43 | SOFTWARE. |
| 44 | |
| 45 | ******************************************************************/ |
| 46 | #ifdef HAVE_DIX_CONFIG_H |
| 47 | #include <dix-config.h> |
| 48 | #endif |
| 49 | |
| 50 | #include "regionstr.h" |
| 51 | #include "gc.h" |
| 52 | #include "miscanfill.h" |
| 53 | #include "mipoly.h" |
| 54 | #include "misc.h" /* MAXINT */ |
| 55 | |
| 56 | /* |
| 57 | * fillUtils.c |
| 58 | * |
| 59 | * Written by Brian Kelleher; Oct. 1985 |
| 60 | * |
| 61 | * This module contains all of the utility functions |
| 62 | * needed to scan convert a polygon. |
| 63 | * |
| 64 | */ |
| 65 | \f |
| 66 | /* |
| 67 | * InsertEdgeInET |
| 68 | * |
| 69 | * Insert the given edge into the edge table. |
| 70 | * First we must find the correct bucket in the |
| 71 | * Edge table, then find the right slot in the |
| 72 | * bucket. Finally, we can insert it. |
| 73 | * |
| 74 | */ |
| 75 | static Bool |
| 76 | miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline, |
| 77 | ScanLineListBlock ** SLLBlock, int *iSLLBlock) |
| 78 | { |
| 79 | EdgeTableEntry *start, *prev; |
| 80 | ScanLineList *pSLL, *pPrevSLL; |
| 81 | ScanLineListBlock *tmpSLLBlock; |
| 82 | |
| 83 | /* |
| 84 | * find the right bucket to put the edge into |
| 85 | */ |
| 86 | pPrevSLL = &ET->scanlines; |
| 87 | pSLL = pPrevSLL->next; |
| 88 | while (pSLL && (pSLL->scanline < scanline)) { |
| 89 | pPrevSLL = pSLL; |
| 90 | pSLL = pSLL->next; |
| 91 | } |
| 92 | |
| 93 | /* |
| 94 | * reassign pSLL (pointer to ScanLineList) if necessary |
| 95 | */ |
| 96 | if ((!pSLL) || (pSLL->scanline > scanline)) { |
| 97 | if (*iSLLBlock > SLLSPERBLOCK - 1) { |
| 98 | tmpSLLBlock = malloc(sizeof(ScanLineListBlock)); |
| 99 | if (!tmpSLLBlock) |
| 100 | return FALSE; |
| 101 | (*SLLBlock)->next = tmpSLLBlock; |
| 102 | tmpSLLBlock->next = NULL; |
| 103 | *SLLBlock = tmpSLLBlock; |
| 104 | *iSLLBlock = 0; |
| 105 | } |
| 106 | pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]); |
| 107 | |
| 108 | pSLL->next = pPrevSLL->next; |
| 109 | pSLL->edgelist = NULL; |
| 110 | pPrevSLL->next = pSLL; |
| 111 | } |
| 112 | pSLL->scanline = scanline; |
| 113 | |
| 114 | /* |
| 115 | * now insert the edge in the right bucket |
| 116 | */ |
| 117 | prev = NULL; |
| 118 | start = pSLL->edgelist; |
| 119 | while (start && (start->bres.minor < ETE->bres.minor)) { |
| 120 | prev = start; |
| 121 | start = start->next; |
| 122 | } |
| 123 | ETE->next = start; |
| 124 | |
| 125 | if (prev) |
| 126 | prev->next = ETE; |
| 127 | else |
| 128 | pSLL->edgelist = ETE; |
| 129 | return TRUE; |
| 130 | } |
| 131 | \f |
| 132 | /* |
| 133 | * CreateEdgeTable |
| 134 | * |
| 135 | * This routine creates the edge table for |
| 136 | * scan converting polygons. |
| 137 | * The Edge Table (ET) looks like: |
| 138 | * |
| 139 | * EdgeTable |
| 140 | * -------- |
| 141 | * | ymax | ScanLineLists |
| 142 | * |scanline|-->------------>-------------->... |
| 143 | * -------- |scanline| |scanline| |
| 144 | * |edgelist| |edgelist| |
| 145 | * --------- --------- |
| 146 | * | | |
| 147 | * | | |
| 148 | * V V |
| 149 | * list of ETEs list of ETEs |
| 150 | * |
| 151 | * where ETE is an EdgeTableEntry data structure, |
| 152 | * and there is one ScanLineList per scanline at |
| 153 | * which an edge is initially entered. |
| 154 | * |
| 155 | */ |
| 156 | |
| 157 | Bool |
| 158 | miCreateETandAET(int count, DDXPointPtr pts, EdgeTable * ET, |
| 159 | EdgeTableEntry * AET, EdgeTableEntry * pETEs, |
| 160 | ScanLineListBlock * pSLLBlock) |
| 161 | { |
| 162 | DDXPointPtr top, bottom; |
| 163 | DDXPointPtr PrevPt, CurrPt; |
| 164 | int iSLLBlock = 0; |
| 165 | |
| 166 | int dy; |
| 167 | |
| 168 | if (count < 2) |
| 169 | return TRUE; |
| 170 | |
| 171 | /* |
| 172 | * initialize the Active Edge Table |
| 173 | */ |
| 174 | AET->next = NULL; |
| 175 | AET->back = NULL; |
| 176 | AET->nextWETE = NULL; |
| 177 | AET->bres.minor = MININT; |
| 178 | |
| 179 | /* |
| 180 | * initialize the Edge Table. |
| 181 | */ |
| 182 | ET->scanlines.next = NULL; |
| 183 | ET->ymax = MININT; |
| 184 | ET->ymin = MAXINT; |
| 185 | pSLLBlock->next = NULL; |
| 186 | |
| 187 | PrevPt = &pts[count - 1]; |
| 188 | |
| 189 | /* |
| 190 | * for each vertex in the array of points. |
| 191 | * In this loop we are dealing with two vertices at |
| 192 | * a time -- these make up one edge of the polygon. |
| 193 | */ |
| 194 | while (count--) { |
| 195 | CurrPt = pts++; |
| 196 | |
| 197 | /* |
| 198 | * find out which point is above and which is below. |
| 199 | */ |
| 200 | if (PrevPt->y > CurrPt->y) { |
| 201 | bottom = PrevPt, top = CurrPt; |
| 202 | pETEs->ClockWise = 0; |
| 203 | } |
| 204 | else { |
| 205 | bottom = CurrPt, top = PrevPt; |
| 206 | pETEs->ClockWise = 1; |
| 207 | } |
| 208 | |
| 209 | /* |
| 210 | * don't add horizontal edges to the Edge table. |
| 211 | */ |
| 212 | if (bottom->y != top->y) { |
| 213 | pETEs->ymax = bottom->y - 1; /* -1 so we don't get last scanline */ |
| 214 | |
| 215 | /* |
| 216 | * initialize integer edge algorithm |
| 217 | */ |
| 218 | dy = bottom->y - top->y; |
| 219 | BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres); |
| 220 | |
| 221 | if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) { |
| 222 | miFreeStorage(pSLLBlock->next); |
| 223 | return FALSE; |
| 224 | } |
| 225 | |
| 226 | ET->ymax = max(ET->ymax, PrevPt->y); |
| 227 | ET->ymin = min(ET->ymin, PrevPt->y); |
| 228 | pETEs++; |
| 229 | } |
| 230 | |
| 231 | PrevPt = CurrPt; |
| 232 | } |
| 233 | return TRUE; |
| 234 | } |
| 235 | \f |
| 236 | /* |
| 237 | * loadAET |
| 238 | * |
| 239 | * This routine moves EdgeTableEntries from the |
| 240 | * EdgeTable into the Active Edge Table, |
| 241 | * leaving them sorted by smaller x coordinate. |
| 242 | * |
| 243 | */ |
| 244 | |
| 245 | void |
| 246 | miloadAET(EdgeTableEntry * AET, EdgeTableEntry * ETEs) |
| 247 | { |
| 248 | EdgeTableEntry *pPrevAET; |
| 249 | EdgeTableEntry *tmp; |
| 250 | |
| 251 | pPrevAET = AET; |
| 252 | AET = AET->next; |
| 253 | while (ETEs) { |
| 254 | while (AET && (AET->bres.minor < ETEs->bres.minor)) { |
| 255 | pPrevAET = AET; |
| 256 | AET = AET->next; |
| 257 | } |
| 258 | tmp = ETEs->next; |
| 259 | ETEs->next = AET; |
| 260 | if (AET) |
| 261 | AET->back = ETEs; |
| 262 | ETEs->back = pPrevAET; |
| 263 | pPrevAET->next = ETEs; |
| 264 | pPrevAET = ETEs; |
| 265 | |
| 266 | ETEs = tmp; |
| 267 | } |
| 268 | } |
| 269 | \f |
| 270 | /* |
| 271 | * computeWAET |
| 272 | * |
| 273 | * This routine links the AET by the |
| 274 | * nextWETE (winding EdgeTableEntry) link for |
| 275 | * use by the winding number rule. The final |
| 276 | * Active Edge Table (AET) might look something |
| 277 | * like: |
| 278 | * |
| 279 | * AET |
| 280 | * ---------- --------- --------- |
| 281 | * |ymax | |ymax | |ymax | |
| 282 | * | ... | |... | |... | |
| 283 | * |next |->|next |->|next |->... |
| 284 | * |nextWETE| |nextWETE| |nextWETE| |
| 285 | * --------- --------- ^-------- |
| 286 | * | | | |
| 287 | * V-------------------> V---> ... |
| 288 | * |
| 289 | */ |
| 290 | void |
| 291 | micomputeWAET(EdgeTableEntry * AET) |
| 292 | { |
| 293 | EdgeTableEntry *pWETE; |
| 294 | int inside = 1; |
| 295 | int isInside = 0; |
| 296 | |
| 297 | AET->nextWETE = NULL; |
| 298 | pWETE = AET; |
| 299 | AET = AET->next; |
| 300 | while (AET) { |
| 301 | if (AET->ClockWise) |
| 302 | isInside++; |
| 303 | else |
| 304 | isInside--; |
| 305 | |
| 306 | if ((!inside && !isInside) || (inside && isInside)) { |
| 307 | pWETE->nextWETE = AET; |
| 308 | pWETE = AET; |
| 309 | inside = !inside; |
| 310 | } |
| 311 | AET = AET->next; |
| 312 | } |
| 313 | pWETE->nextWETE = NULL; |
| 314 | } |
| 315 | \f |
| 316 | /* |
| 317 | * InsertionSort |
| 318 | * |
| 319 | * Just a simple insertion sort using |
| 320 | * pointers and back pointers to sort the Active |
| 321 | * Edge Table. |
| 322 | * |
| 323 | */ |
| 324 | |
| 325 | int |
| 326 | miInsertionSort(EdgeTableEntry * AET) |
| 327 | { |
| 328 | EdgeTableEntry *pETEchase; |
| 329 | EdgeTableEntry *pETEinsert; |
| 330 | EdgeTableEntry *pETEchaseBackTMP; |
| 331 | int changed = 0; |
| 332 | |
| 333 | AET = AET->next; |
| 334 | while (AET) { |
| 335 | pETEinsert = AET; |
| 336 | pETEchase = AET; |
| 337 | while (pETEchase->back->bres.minor > AET->bres.minor) |
| 338 | pETEchase = pETEchase->back; |
| 339 | |
| 340 | AET = AET->next; |
| 341 | if (pETEchase != pETEinsert) { |
| 342 | pETEchaseBackTMP = pETEchase->back; |
| 343 | pETEinsert->back->next = AET; |
| 344 | if (AET) |
| 345 | AET->back = pETEinsert->back; |
| 346 | pETEinsert->next = pETEchase; |
| 347 | pETEchase->back->next = pETEinsert; |
| 348 | pETEchase->back = pETEinsert; |
| 349 | pETEinsert->back = pETEchaseBackTMP; |
| 350 | changed = 1; |
| 351 | } |
| 352 | } |
| 353 | return changed; |
| 354 | } |
| 355 | \f |
| 356 | /* |
| 357 | * Clean up our act. |
| 358 | */ |
| 359 | void |
| 360 | miFreeStorage(ScanLineListBlock * pSLLBlock) |
| 361 | { |
| 362 | ScanLineListBlock *tmpSLLBlock; |
| 363 | |
| 364 | while (pSLLBlock) { |
| 365 | tmpSLLBlock = pSLLBlock->next; |
| 366 | free(pSLLBlock); |
| 367 | pSLLBlock = tmpSLLBlock; |
| 368 | } |
| 369 | } |