| File: | mi/mipoly.c |
| Location: | line 645, column 25 |
| Description: | Access to field 'ymax' results in a dereference of a null pointer (loaded from variable 'pAET') |
| 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 | /* | |||||
| 47 | * mipoly.c | |||||
| 48 | * | |||||
| 49 | * Written by Brian Kelleher; June 1986 | |||||
| 50 | */ | |||||
| 51 | #ifdef HAVE_DIX_CONFIG_H1 | |||||
| 52 | #include <dix-config.h> | |||||
| 53 | #endif | |||||
| 54 | ||||||
| 55 | #include <X11/X.h> | |||||
| 56 | #include "windowstr.h" | |||||
| 57 | #include "gcstruct.h" | |||||
| 58 | #include "pixmapstr.h" | |||||
| 59 | #include "mi.h" | |||||
| 60 | #include "miscanfill.h" | |||||
| 61 | #include "mipoly.h" | |||||
| 62 | #include "regionstr.h" | |||||
| 63 | ||||||
| 64 | /* | |||||
| 65 | * Insert the given edge into the edge table. First we must find the correct | |||||
| 66 | * bucket in the Edge table, then find the right slot in the bucket. Finally, | |||||
| 67 | * we can insert it. | |||||
| 68 | */ | |||||
| 69 | static Bool | |||||
| 70 | miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline, | |||||
| 71 | ScanLineListBlock ** SLLBlock, int *iSLLBlock) | |||||
| 72 | { | |||||
| 73 | EdgeTableEntry *start, *prev; | |||||
| 74 | ScanLineList *pSLL, *pPrevSLL; | |||||
| 75 | ScanLineListBlock *tmpSLLBlock; | |||||
| 76 | ||||||
| 77 | /* | |||||
| 78 | * find the right bucket to put the edge into | |||||
| 79 | */ | |||||
| 80 | pPrevSLL = &ET->scanlines; | |||||
| 81 | pSLL = pPrevSLL->next; | |||||
| 82 | while (pSLL && (pSLL->scanline < scanline)) { | |||||
| 83 | pPrevSLL = pSLL; | |||||
| 84 | pSLL = pSLL->next; | |||||
| 85 | } | |||||
| 86 | ||||||
| 87 | /* | |||||
| 88 | * reassign pSLL (pointer to ScanLineList) if necessary | |||||
| 89 | */ | |||||
| 90 | if ((!pSLL) || (pSLL->scanline > scanline)) { | |||||
| 91 | if (*iSLLBlock > SLLSPERBLOCK25 - 1) { | |||||
| 92 | tmpSLLBlock = malloc(sizeof(ScanLineListBlock)); | |||||
| 93 | if (!tmpSLLBlock) | |||||
| 94 | return FALSE0; | |||||
| 95 | (*SLLBlock)->next = tmpSLLBlock; | |||||
| 96 | tmpSLLBlock->next = NULL((void*)0); | |||||
| 97 | *SLLBlock = tmpSLLBlock; | |||||
| 98 | *iSLLBlock = 0; | |||||
| 99 | } | |||||
| 100 | pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]); | |||||
| 101 | ||||||
| 102 | pSLL->next = pPrevSLL->next; | |||||
| 103 | pSLL->edgelist = NULL((void*)0); | |||||
| 104 | pPrevSLL->next = pSLL; | |||||
| 105 | } | |||||
| 106 | pSLL->scanline = scanline; | |||||
| 107 | ||||||
| 108 | /* | |||||
| 109 | * now insert the edge in the right bucket | |||||
| 110 | */ | |||||
| 111 | prev = NULL((void*)0); | |||||
| 112 | start = pSLL->edgelist; | |||||
| 113 | while (start && (start->bres.minor < ETE->bres.minor)) { | |||||
| 114 | prev = start; | |||||
| 115 | start = start->next; | |||||
| 116 | } | |||||
| 117 | ETE->next = start; | |||||
| 118 | ||||||
| 119 | if (prev) | |||||
| 120 | prev->next = ETE; | |||||
| 121 | else | |||||
| 122 | pSLL->edgelist = ETE; | |||||
| 123 | return TRUE1; | |||||
| 124 | } | |||||
| 125 | ||||||
| 126 | static void | |||||
| 127 | miFreeStorage(ScanLineListBlock * pSLLBlock) | |||||
| 128 | { | |||||
| 129 | ScanLineListBlock *tmpSLLBlock; | |||||
| 130 | ||||||
| 131 | while (pSLLBlock) { | |||||
| 132 | tmpSLLBlock = pSLLBlock->next; | |||||
| 133 | free(pSLLBlock); | |||||
| 134 | pSLLBlock = tmpSLLBlock; | |||||
| 135 | } | |||||
| 136 | } | |||||
| 137 | ||||||
| 138 | /* | |||||
| 139 | * CreateEdgeTable | |||||
| 140 | * | |||||
| 141 | * This routine creates the edge table for scan converting polygons. | |||||
| 142 | * The Edge Table (ET) looks like: | |||||
| 143 | * | |||||
| 144 | * EdgeTable | |||||
| 145 | * -------- | |||||
| 146 | * | ymax | ScanLineLists | |||||
| 147 | * |scanline|-->------------>-------------->... | |||||
| 148 | * -------- |scanline| |scanline| | |||||
| 149 | * |edgelist| |edgelist| | |||||
| 150 | * --------- --------- | |||||
| 151 | * | | | |||||
| 152 | * | | | |||||
| 153 | * V V | |||||
| 154 | * list of ETEs list of ETEs | |||||
| 155 | * | |||||
| 156 | * where ETE is an EdgeTableEntry data structure, and there is one ScanLineList | |||||
| 157 | * per scanline at which an edge is initially entered. | |||||
| 158 | */ | |||||
| 159 | ||||||
| 160 | static Bool | |||||
| 161 | miCreateETandAET(int count, DDXPointPtr pts, EdgeTable * ET, | |||||
| 162 | EdgeTableEntry * AET, EdgeTableEntry * pETEs, | |||||
| 163 | ScanLineListBlock * pSLLBlock) | |||||
| 164 | { | |||||
| 165 | DDXPointPtr top, bottom; | |||||
| 166 | DDXPointPtr PrevPt, CurrPt; | |||||
| 167 | int iSLLBlock = 0; | |||||
| 168 | ||||||
| 169 | int dy; | |||||
| 170 | ||||||
| 171 | if (count < 2) | |||||
| 172 | return TRUE1; | |||||
| 173 | ||||||
| 174 | /* | |||||
| 175 | * initialize the Active Edge Table | |||||
| 176 | */ | |||||
| 177 | AET->next = NULL((void*)0); | |||||
| 178 | AET->back = NULL((void*)0); | |||||
| 179 | AET->nextWETE = NULL((void*)0); | |||||
| 180 | AET->bres.minor = MININT(-2147483647 -1); | |||||
| 181 | ||||||
| 182 | /* | |||||
| 183 | * initialize the Edge Table. | |||||
| 184 | */ | |||||
| 185 | ET->scanlines.next = NULL((void*)0); | |||||
| 186 | ET->ymax = MININT(-2147483647 -1); | |||||
| 187 | ET->ymin = MAXINT2147483647; | |||||
| 188 | pSLLBlock->next = NULL((void*)0); | |||||
| 189 | ||||||
| 190 | PrevPt = &pts[count - 1]; | |||||
| 191 | ||||||
| 192 | /* | |||||
| 193 | * for each vertex in the array of points. | |||||
| 194 | * In this loop we are dealing with two vertices at | |||||
| 195 | * a time -- these make up one edge of the polygon. | |||||
| 196 | */ | |||||
| 197 | while (count--) { | |||||
| 198 | CurrPt = pts++; | |||||
| 199 | ||||||
| 200 | /* | |||||
| 201 | * find out which point is above and which is below. | |||||
| 202 | */ | |||||
| 203 | if (PrevPt->y > CurrPt->y) { | |||||
| 204 | bottom = PrevPt, top = CurrPt; | |||||
| 205 | pETEs->ClockWise = 0; | |||||
| 206 | } | |||||
| 207 | else { | |||||
| 208 | bottom = CurrPt, top = PrevPt; | |||||
| 209 | pETEs->ClockWise = 1; | |||||
| 210 | } | |||||
| 211 | ||||||
| 212 | /* | |||||
| 213 | * don't add horizontal edges to the Edge table. | |||||
| 214 | */ | |||||
| 215 | if (bottom->y != top->y) { | |||||
| 216 | pETEs->ymax = bottom->y - 1; /* -1 so we don't get last scanline */ | |||||
| 217 | ||||||
| 218 | /* | |||||
| 219 | * initialize integer edge algorithm | |||||
| 220 | */ | |||||
| 221 | dy = bottom->y - top->y; | |||||
| 222 | BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres){ int dx; if ((dy) != 0) { pETEs->bres.minor = (top->x) ; dx = (bottom->x) - pETEs->bres.minor; if (dx < 0) { pETEs->bres.m = dx / (dy); pETEs->bres.m1 = pETEs-> bres.m - 1; pETEs->bres.incr1 = -2 * dx + 2 * (dy) * pETEs ->bres.m1; pETEs->bres.incr2 = -2 * dx + 2 * (dy) * pETEs ->bres.m; pETEs->bres.d = 2 * pETEs->bres.m * (dy) - 2 * dx - 2 * (dy); } else { pETEs->bres.m = dx / (dy); pETEs ->bres.m1 = pETEs->bres.m + 1; pETEs->bres.incr1 = 2 * dx - 2 * (dy) * pETEs->bres.m1; pETEs->bres.incr2 = 2 * dx - 2 * (dy) * pETEs->bres.m; pETEs->bres.d = -2 * pETEs ->bres.m * (dy) + 2 * dx; } } }; | |||||
| 223 | ||||||
| 224 | if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) { | |||||
| 225 | miFreeStorage(pSLLBlock->next); | |||||
| 226 | return FALSE0; | |||||
| 227 | } | |||||
| 228 | ||||||
| 229 | ET->ymax = max(ET->ymax, PrevPt->y)(((ET->ymax) > (PrevPt->y)) ? (ET->ymax) : (PrevPt ->y)); | |||||
| 230 | ET->ymin = min(ET->ymin, PrevPt->y)(((ET->ymin) < (PrevPt->y)) ? (ET->ymin) : (PrevPt ->y)); | |||||
| 231 | pETEs++; | |||||
| 232 | } | |||||
| 233 | ||||||
| 234 | PrevPt = CurrPt; | |||||
| 235 | } | |||||
| 236 | return TRUE1; | |||||
| 237 | } | |||||
| 238 | ||||||
| 239 | /* | |||||
| 240 | * This routine moves EdgeTableEntries from the EdgeTable into the Active Edge | |||||
| 241 | * Table, leaving them sorted by smaller x coordinate. | |||||
| 242 | */ | |||||
| 243 | ||||||
| 244 | static void | |||||
| 245 | miloadAET(EdgeTableEntry * AET, EdgeTableEntry * ETEs) | |||||
| 246 | { | |||||
| 247 | EdgeTableEntry *pPrevAET; | |||||
| 248 | EdgeTableEntry *tmp; | |||||
| 249 | ||||||
| 250 | pPrevAET = AET; | |||||
| 251 | AET = AET->next; | |||||
| 252 | while (ETEs) { | |||||
| 253 | while (AET && (AET->bres.minor < ETEs->bres.minor)) { | |||||
| 254 | pPrevAET = AET; | |||||
| 255 | AET = AET->next; | |||||
| 256 | } | |||||
| 257 | tmp = ETEs->next; | |||||
| 258 | ETEs->next = AET; | |||||
| 259 | if (AET) | |||||
| 260 | AET->back = ETEs; | |||||
| 261 | ETEs->back = pPrevAET; | |||||
| 262 | pPrevAET->next = ETEs; | |||||
| 263 | pPrevAET = ETEs; | |||||
| 264 | ||||||
| 265 | ETEs = tmp; | |||||
| 266 | } | |||||
| 267 | } | |||||
| 268 | ||||||
| 269 | /* | |||||
| 270 | * computeWAET | |||||
| 271 | * | |||||
| 272 | * This routine links the AET by the nextWETE (winding EdgeTableEntry) link for | |||||
| 273 | * use by the winding number rule. The final Active Edge Table (AET) might | |||||
| 274 | * look something like: | |||||
| 275 | * | |||||
| 276 | * AET | |||||
| 277 | * ---------- --------- --------- | |||||
| 278 | * |ymax | |ymax | |ymax | | |||||
| 279 | * | ... | |... | |... | | |||||
| 280 | * |next |->|next |->|next |->... | |||||
| 281 | * |nextWETE| |nextWETE| |nextWETE| | |||||
| 282 | * --------- --------- ^-------- | |||||
| 283 | * | | | | |||||
| 284 | * V-------------------> V---> ... | |||||
| 285 | * | |||||
| 286 | */ | |||||
| 287 | static void | |||||
| 288 | micomputeWAET(EdgeTableEntry * AET) | |||||
| 289 | { | |||||
| 290 | EdgeTableEntry *pWETE; | |||||
| 291 | int inside = 1; | |||||
| 292 | int isInside = 0; | |||||
| 293 | ||||||
| 294 | AET->nextWETE = NULL((void*)0); | |||||
| 295 | pWETE = AET; | |||||
| 296 | AET = AET->next; | |||||
| 297 | while (AET) { | |||||
| 298 | if (AET->ClockWise) | |||||
| 299 | isInside++; | |||||
| 300 | else | |||||
| 301 | isInside--; | |||||
| 302 | ||||||
| 303 | if ((!inside && !isInside) || (inside && isInside)) { | |||||
| 304 | pWETE->nextWETE = AET; | |||||
| 305 | pWETE = AET; | |||||
| 306 | inside = !inside; | |||||
| 307 | } | |||||
| 308 | AET = AET->next; | |||||
| 309 | } | |||||
| 310 | pWETE->nextWETE = NULL((void*)0); | |||||
| 311 | } | |||||
| 312 | ||||||
| 313 | /* | |||||
| 314 | * Just a simple insertion sort using pointers and back pointers to sort the | |||||
| 315 | * Active Edge Table. | |||||
| 316 | */ | |||||
| 317 | ||||||
| 318 | static int | |||||
| 319 | miInsertionSort(EdgeTableEntry * AET) | |||||
| 320 | { | |||||
| 321 | EdgeTableEntry *pETEchase; | |||||
| 322 | EdgeTableEntry *pETEinsert; | |||||
| 323 | EdgeTableEntry *pETEchaseBackTMP; | |||||
| 324 | int changed = 0; | |||||
| 325 | ||||||
| 326 | AET = AET->next; | |||||
| 327 | while (AET) { | |||||
| 328 | pETEinsert = AET; | |||||
| 329 | pETEchase = AET; | |||||
| 330 | while (pETEchase->back->bres.minor > AET->bres.minor) | |||||
| 331 | pETEchase = pETEchase->back; | |||||
| 332 | ||||||
| 333 | AET = AET->next; | |||||
| 334 | if (pETEchase != pETEinsert) { | |||||
| 335 | pETEchaseBackTMP = pETEchase->back; | |||||
| 336 | pETEinsert->back->next = AET; | |||||
| 337 | if (AET) | |||||
| 338 | AET->back = pETEinsert->back; | |||||
| 339 | pETEinsert->next = pETEchase; | |||||
| 340 | pETEchase->back->next = pETEinsert; | |||||
| 341 | pETEchase->back = pETEinsert; | |||||
| 342 | pETEinsert->back = pETEchaseBackTMP; | |||||
| 343 | changed = 1; | |||||
| 344 | } | |||||
| 345 | } | |||||
| 346 | return changed; | |||||
| 347 | } | |||||
| 348 | ||||||
| 349 | /* Find the index of the point with the smallest y */ | |||||
| 350 | static int | |||||
| 351 | getPolyYBounds(DDXPointPtr pts, int n, int *by, int *ty) | |||||
| 352 | { | |||||
| 353 | DDXPointPtr ptMin; | |||||
| 354 | int ymin, ymax; | |||||
| 355 | DDXPointPtr ptsStart = pts; | |||||
| 356 | ||||||
| 357 | ptMin = pts; | |||||
| 358 | ymin = ymax = (pts++)->y; | |||||
| 359 | ||||||
| 360 | while (--n > 0) { | |||||
| 361 | if (pts->y < ymin) { | |||||
| 362 | ptMin = pts; | |||||
| 363 | ymin = pts->y; | |||||
| 364 | } | |||||
| 365 | if (pts->y > ymax) | |||||
| 366 | ymax = pts->y; | |||||
| 367 | ||||||
| 368 | pts++; | |||||
| 369 | } | |||||
| 370 | ||||||
| 371 | *by = ymin; | |||||
| 372 | *ty = ymax; | |||||
| 373 | return ptMin - ptsStart; | |||||
| 374 | } | |||||
| 375 | ||||||
| 376 | /* | |||||
| 377 | * Written by Brian Kelleher; Dec. 1985. | |||||
| 378 | * | |||||
| 379 | * Fill a convex polygon. If the given polygon is not convex, then the result | |||||
| 380 | * is undefined. The algorithm is to order the edges from smallest y to | |||||
| 381 | * largest by partitioning the array into a left edge list and a right edge | |||||
| 382 | * list. The algorithm used to traverse each edge is an extension of | |||||
| 383 | * Bresenham's line algorithm with y as the major axis. For a derivation of | |||||
| 384 | * the algorithm, see the author of this code. | |||||
| 385 | */ | |||||
| 386 | static Bool | |||||
| 387 | miFillConvexPoly(DrawablePtr dst, GCPtr pgc, int count, DDXPointPtr ptsIn) | |||||
| 388 | { | |||||
| 389 | int xl = 0, xr = 0; /* x vals of left and right edges */ | |||||
| 390 | int dl = 0, dr = 0; /* decision variables */ | |||||
| 391 | int ml = 0, m1l = 0; /* left edge slope and slope+1 */ | |||||
| 392 | int mr = 0, m1r = 0; /* right edge slope and slope+1 */ | |||||
| 393 | int incr1l = 0, incr2l = 0; /* left edge error increments */ | |||||
| 394 | int incr1r = 0, incr2r = 0; /* right edge error increments */ | |||||
| 395 | int dy; /* delta y */ | |||||
| 396 | int y; /* current scanline */ | |||||
| 397 | int left, right; /* indices to first endpoints */ | |||||
| 398 | int i; /* loop counter */ | |||||
| 399 | int nextleft, nextright; /* indices to second endpoints */ | |||||
| 400 | DDXPointPtr ptsOut, FirstPoint; /* output buffer */ | |||||
| 401 | int *width, *FirstWidth; /* output buffer */ | |||||
| 402 | int imin; /* index of smallest vertex (in y) */ | |||||
| 403 | int ymin; /* y-extents of polygon */ | |||||
| 404 | int ymax; | |||||
| 405 | ||||||
| 406 | /* | |||||
| 407 | * find leftx, bottomy, rightx, topy, and the index | |||||
| 408 | * of bottomy. Also translate the points. | |||||
| 409 | */ | |||||
| 410 | imin = getPolyYBounds(ptsIn, count, &ymin, &ymax); | |||||
| 411 | ||||||
| 412 | dy = ymax - ymin + 1; | |||||
| 413 | if ((count < 3) || (dy < 0)) | |||||
| 414 | return TRUE1; | |||||
| 415 | ptsOut = FirstPoint = xallocarray(dy, sizeof(DDXPointRec))xreallocarray(((void*)0), (dy), (sizeof(DDXPointRec))); | |||||
| 416 | width = FirstWidth = xallocarray(dy, sizeof(int))xreallocarray(((void*)0), (dy), (sizeof(int))); | |||||
| 417 | if (!FirstPoint || !FirstWidth) { | |||||
| 418 | free(FirstWidth); | |||||
| 419 | free(FirstPoint); | |||||
| 420 | return FALSE0; | |||||
| 421 | } | |||||
| 422 | ||||||
| 423 | nextleft = nextright = imin; | |||||
| 424 | y = ptsIn[nextleft].y; | |||||
| 425 | ||||||
| 426 | /* | |||||
| 427 | * loop through all edges of the polygon | |||||
| 428 | */ | |||||
| 429 | do { | |||||
| 430 | /* | |||||
| 431 | * add a left edge if we need to | |||||
| 432 | */ | |||||
| 433 | if (ptsIn[nextleft].y == y) { | |||||
| 434 | left = nextleft; | |||||
| 435 | ||||||
| 436 | /* | |||||
| 437 | * find the next edge, considering the end | |||||
| 438 | * conditions of the array. | |||||
| 439 | */ | |||||
| 440 | nextleft++; | |||||
| 441 | if (nextleft >= count) | |||||
| 442 | nextleft = 0; | |||||
| 443 | ||||||
| 444 | /* | |||||
| 445 | * now compute all of the random information | |||||
| 446 | * needed to run the iterative algorithm. | |||||
| 447 | */ | |||||
| 448 | BRESINITPGON(ptsIn[nextleft].y - ptsIn[left].y,{ int dx; if ((ptsIn[nextleft].y - ptsIn[left].y) != 0) { xl = (ptsIn[left].x); dx = (ptsIn[nextleft].x) - xl; if (dx < 0 ) { ml = dx / (ptsIn[nextleft].y - ptsIn[left].y); m1l = ml - 1; incr1l = -2 * dx + 2 * (ptsIn[nextleft].y - ptsIn[left].y ) * m1l; incr2l = -2 * dx + 2 * (ptsIn[nextleft].y - ptsIn[left ].y) * ml; dl = 2 * ml * (ptsIn[nextleft].y - ptsIn[left].y) - 2 * dx - 2 * (ptsIn[nextleft].y - ptsIn[left].y); } else { ml = dx / (ptsIn[nextleft].y - ptsIn[left].y); m1l = ml + 1; incr1l = 2 * dx - 2 * (ptsIn[nextleft].y - ptsIn[left].y) * m1l; incr2l = 2 * dx - 2 * (ptsIn[nextleft].y - ptsIn[left].y) * ml; dl = -2 * ml * (ptsIn[nextleft].y - ptsIn[left].y) + 2 * dx; } } } | |||||
| 449 | ptsIn[left].x, ptsIn[nextleft].x,{ int dx; if ((ptsIn[nextleft].y - ptsIn[left].y) != 0) { xl = (ptsIn[left].x); dx = (ptsIn[nextleft].x) - xl; if (dx < 0 ) { ml = dx / (ptsIn[nextleft].y - ptsIn[left].y); m1l = ml - 1; incr1l = -2 * dx + 2 * (ptsIn[nextleft].y - ptsIn[left].y ) * m1l; incr2l = -2 * dx + 2 * (ptsIn[nextleft].y - ptsIn[left ].y) * ml; dl = 2 * ml * (ptsIn[nextleft].y - ptsIn[left].y) - 2 * dx - 2 * (ptsIn[nextleft].y - ptsIn[left].y); } else { ml = dx / (ptsIn[nextleft].y - ptsIn[left].y); m1l = ml + 1; incr1l = 2 * dx - 2 * (ptsIn[nextleft].y - ptsIn[left].y) * m1l; incr2l = 2 * dx - 2 * (ptsIn[nextleft].y - ptsIn[left].y) * ml; dl = -2 * ml * (ptsIn[nextleft].y - ptsIn[left].y) + 2 * dx; } } } | |||||
| 450 | xl, dl, ml, m1l, incr1l, incr2l){ int dx; if ((ptsIn[nextleft].y - ptsIn[left].y) != 0) { xl = (ptsIn[left].x); dx = (ptsIn[nextleft].x) - xl; if (dx < 0 ) { ml = dx / (ptsIn[nextleft].y - ptsIn[left].y); m1l = ml - 1; incr1l = -2 * dx + 2 * (ptsIn[nextleft].y - ptsIn[left].y ) * m1l; incr2l = -2 * dx + 2 * (ptsIn[nextleft].y - ptsIn[left ].y) * ml; dl = 2 * ml * (ptsIn[nextleft].y - ptsIn[left].y) - 2 * dx - 2 * (ptsIn[nextleft].y - ptsIn[left].y); } else { ml = dx / (ptsIn[nextleft].y - ptsIn[left].y); m1l = ml + 1; incr1l = 2 * dx - 2 * (ptsIn[nextleft].y - ptsIn[left].y) * m1l; incr2l = 2 * dx - 2 * (ptsIn[nextleft].y - ptsIn[left].y) * ml; dl = -2 * ml * (ptsIn[nextleft].y - ptsIn[left].y) + 2 * dx; } } }; | |||||
| 451 | } | |||||
| 452 | ||||||
| 453 | /* | |||||
| 454 | * add a right edge if we need to | |||||
| 455 | */ | |||||
| 456 | if (ptsIn[nextright].y == y) { | |||||
| 457 | right = nextright; | |||||
| 458 | ||||||
| 459 | /* | |||||
| 460 | * find the next edge, considering the end | |||||
| 461 | * conditions of the array. | |||||
| 462 | */ | |||||
| 463 | nextright--; | |||||
| 464 | if (nextright < 0) | |||||
| 465 | nextright = count - 1; | |||||
| 466 | ||||||
| 467 | /* | |||||
| 468 | * now compute all of the random information | |||||
| 469 | * needed to run the iterative algorithm. | |||||
| 470 | */ | |||||
| 471 | BRESINITPGON(ptsIn[nextright].y - ptsIn[right].y,{ int dx; if ((ptsIn[nextright].y - ptsIn[right].y) != 0) { xr = (ptsIn[right].x); dx = (ptsIn[nextright].x) - xr; if (dx < 0) { mr = dx / (ptsIn[nextright].y - ptsIn[right].y); m1r = mr - 1; incr1r = -2 * dx + 2 * (ptsIn[nextright].y - ptsIn[right ].y) * m1r; incr2r = -2 * dx + 2 * (ptsIn[nextright].y - ptsIn [right].y) * mr; dr = 2 * mr * (ptsIn[nextright].y - ptsIn[right ].y) - 2 * dx - 2 * (ptsIn[nextright].y - ptsIn[right].y); } else { mr = dx / (ptsIn[nextright].y - ptsIn[right].y); m1r = mr + 1; incr1r = 2 * dx - 2 * (ptsIn[nextright].y - ptsIn[right]. y) * m1r; incr2r = 2 * dx - 2 * (ptsIn[nextright].y - ptsIn[right ].y) * mr; dr = -2 * mr * (ptsIn[nextright].y - ptsIn[right]. y) + 2 * dx; } } } | |||||
| 472 | ptsIn[right].x, ptsIn[nextright].x,{ int dx; if ((ptsIn[nextright].y - ptsIn[right].y) != 0) { xr = (ptsIn[right].x); dx = (ptsIn[nextright].x) - xr; if (dx < 0) { mr = dx / (ptsIn[nextright].y - ptsIn[right].y); m1r = mr - 1; incr1r = -2 * dx + 2 * (ptsIn[nextright].y - ptsIn[right ].y) * m1r; incr2r = -2 * dx + 2 * (ptsIn[nextright].y - ptsIn [right].y) * mr; dr = 2 * mr * (ptsIn[nextright].y - ptsIn[right ].y) - 2 * dx - 2 * (ptsIn[nextright].y - ptsIn[right].y); } else { mr = dx / (ptsIn[nextright].y - ptsIn[right].y); m1r = mr + 1; incr1r = 2 * dx - 2 * (ptsIn[nextright].y - ptsIn[right]. y) * m1r; incr2r = 2 * dx - 2 * (ptsIn[nextright].y - ptsIn[right ].y) * mr; dr = -2 * mr * (ptsIn[nextright].y - ptsIn[right]. y) + 2 * dx; } } } | |||||
| 473 | xr, dr, mr, m1r, incr1r, incr2r){ int dx; if ((ptsIn[nextright].y - ptsIn[right].y) != 0) { xr = (ptsIn[right].x); dx = (ptsIn[nextright].x) - xr; if (dx < 0) { mr = dx / (ptsIn[nextright].y - ptsIn[right].y); m1r = mr - 1; incr1r = -2 * dx + 2 * (ptsIn[nextright].y - ptsIn[right ].y) * m1r; incr2r = -2 * dx + 2 * (ptsIn[nextright].y - ptsIn [right].y) * mr; dr = 2 * mr * (ptsIn[nextright].y - ptsIn[right ].y) - 2 * dx - 2 * (ptsIn[nextright].y - ptsIn[right].y); } else { mr = dx / (ptsIn[nextright].y - ptsIn[right].y); m1r = mr + 1; incr1r = 2 * dx - 2 * (ptsIn[nextright].y - ptsIn[right]. y) * m1r; incr2r = 2 * dx - 2 * (ptsIn[nextright].y - ptsIn[right ].y) * mr; dr = -2 * mr * (ptsIn[nextright].y - ptsIn[right]. y) + 2 * dx; } } }; | |||||
| 474 | } | |||||
| 475 | ||||||
| 476 | /* | |||||
| 477 | * generate scans to fill while we still have | |||||
| 478 | * a right edge as well as a left edge. | |||||
| 479 | */ | |||||
| 480 | i = min(ptsIn[nextleft].y, ptsIn[nextright].y)(((ptsIn[nextleft].y) < (ptsIn[nextright].y)) ? (ptsIn[nextleft ].y) : (ptsIn[nextright].y)) - y; | |||||
| 481 | /* in case we're called with non-convex polygon */ | |||||
| 482 | if (i < 0) { | |||||
| 483 | free(FirstWidth); | |||||
| 484 | free(FirstPoint); | |||||
| 485 | return TRUE1; | |||||
| 486 | } | |||||
| 487 | while (i-- > 0) { | |||||
| 488 | ptsOut->y = y; | |||||
| 489 | ||||||
| 490 | /* | |||||
| 491 | * reverse the edges if necessary | |||||
| 492 | */ | |||||
| 493 | if (xl < xr) { | |||||
| 494 | *(width++) = xr - xl; | |||||
| 495 | (ptsOut++)->x = xl; | |||||
| 496 | } | |||||
| 497 | else { | |||||
| 498 | *(width++) = xl - xr; | |||||
| 499 | (ptsOut++)->x = xr; | |||||
| 500 | } | |||||
| 501 | y++; | |||||
| 502 | ||||||
| 503 | /* increment down the edges */ | |||||
| 504 | BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l){ if (m1l > 0) { if (dl > 0) { xl += m1l; dl += incr1l; } else { xl += ml; dl += incr2l; } } else { if (dl >= 0) { xl += m1l; dl += incr1l; } else { xl += ml; dl += incr2l; } } }; | |||||
| 505 | BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r){ if (m1r > 0) { if (dr > 0) { xr += m1r; dr += incr1r; } else { xr += mr; dr += incr2r; } } else { if (dr >= 0) { xr += m1r; dr += incr1r; } else { xr += mr; dr += incr2r; } } }; | |||||
| 506 | } | |||||
| 507 | } while (y != ymax); | |||||
| 508 | ||||||
| 509 | /* | |||||
| 510 | * Finally, fill the <remaining> spans | |||||
| 511 | */ | |||||
| 512 | (*pgc->ops->FillSpans) (dst, pgc, | |||||
| 513 | ptsOut - FirstPoint, FirstPoint, FirstWidth, 1); | |||||
| 514 | free(FirstWidth); | |||||
| 515 | free(FirstPoint); | |||||
| 516 | return TRUE1; | |||||
| 517 | } | |||||
| 518 | ||||||
| 519 | /* | |||||
| 520 | * Written by Brian Kelleher; Oct. 1985 | |||||
| 521 | * | |||||
| 522 | * Routine to fill a polygon. Two fill rules are supported: frWINDING and | |||||
| 523 | * frEVENODD. | |||||
| 524 | */ | |||||
| 525 | static Bool | |||||
| 526 | miFillGeneralPoly(DrawablePtr dst, GCPtr pgc, int count, DDXPointPtr ptsIn) | |||||
| 527 | { | |||||
| 528 | EdgeTableEntry *pAET; /* the Active Edge Table */ | |||||
| 529 | int y; /* the current scanline */ | |||||
| 530 | int nPts = 0; /* number of pts in buffer */ | |||||
| 531 | EdgeTableEntry *pWETE; /* Winding Edge Table */ | |||||
| 532 | ScanLineList *pSLL; /* Current ScanLineList */ | |||||
| 533 | DDXPointPtr ptsOut; /* ptr to output buffers */ | |||||
| 534 | int *width; | |||||
| 535 | DDXPointRec FirstPoint[NUMPTSTOBUFFER200]; /* the output buffers */ | |||||
| 536 | int FirstWidth[NUMPTSTOBUFFER200]; | |||||
| 537 | EdgeTableEntry *pPrevAET; /* previous AET entry */ | |||||
| 538 | EdgeTable ET; /* Edge Table header node */ | |||||
| 539 | EdgeTableEntry AET; /* Active ET header node */ | |||||
| 540 | EdgeTableEntry *pETEs; /* Edge Table Entries buff */ | |||||
| 541 | ScanLineListBlock SLLBlock; /* header for ScanLineList */ | |||||
| 542 | int fixWAET = 0; | |||||
| 543 | ||||||
| 544 | if (count < 3) | |||||
| ||||||
| 545 | return TRUE1; | |||||
| 546 | ||||||
| 547 | if (!(pETEs = malloc(sizeof(EdgeTableEntry) * count))) | |||||
| 548 | return FALSE0; | |||||
| 549 | ptsOut = FirstPoint; | |||||
| 550 | width = FirstWidth; | |||||
| 551 | if (!miCreateETandAET(count, ptsIn, &ET, &AET, pETEs, &SLLBlock)) { | |||||
| 552 | free(pETEs); | |||||
| 553 | return FALSE0; | |||||
| 554 | } | |||||
| 555 | pSLL = ET.scanlines.next; | |||||
| 556 | ||||||
| 557 | if (pgc->fillRule == EvenOddRule0) { | |||||
| 558 | /* | |||||
| 559 | * for each scanline | |||||
| 560 | */ | |||||
| 561 | for (y = ET.ymin; y < ET.ymax; y++) { | |||||
| 562 | /* | |||||
| 563 | * Add a new edge to the active edge table when we | |||||
| 564 | * get to the next edge. | |||||
| 565 | */ | |||||
| 566 | if (pSLL && y == pSLL->scanline) { | |||||
| 567 | miloadAET(&AET, pSLL->edgelist); | |||||
| 568 | pSLL = pSLL->next; | |||||
| 569 | } | |||||
| 570 | pPrevAET = &AET; | |||||
| 571 | pAET = AET.next; | |||||
| 572 | ||||||
| 573 | /* | |||||
| 574 | * for each active edge | |||||
| 575 | */ | |||||
| 576 | while (pAET) { | |||||
| 577 | ptsOut->x = pAET->bres.minor; | |||||
| 578 | ptsOut++->y = y; | |||||
| 579 | *width++ = pAET->next->bres.minor - pAET->bres.minor; | |||||
| 580 | nPts++; | |||||
| 581 | ||||||
| 582 | /* | |||||
| 583 | * send out the buffer when its full | |||||
| 584 | */ | |||||
| 585 | if (nPts == NUMPTSTOBUFFER200) { | |||||
| 586 | (*pgc->ops->FillSpans) (dst, pgc, | |||||
| 587 | nPts, FirstPoint, FirstWidth, 1); | |||||
| 588 | ptsOut = FirstPoint; | |||||
| 589 | width = FirstWidth; | |||||
| 590 | nPts = 0; | |||||
| 591 | } | |||||
| 592 | EVALUATEEDGEEVENODD(pAET, pPrevAET, y){ if (pAET->ymax == y) { pPrevAET->next = pAET->next ; pAET = pPrevAET->next; if (pAET) pAET->back = pPrevAET ; } else { { if (pAET->bres.m1 > 0) { if (pAET->bres .d > 0) { pAET->bres.minor += pAET->bres.m1; pAET-> bres.d += pAET->bres.incr1; } else { pAET->bres.minor += pAET->bres.m; pAET->bres.d += pAET->bres.incr2; } } else { if (pAET->bres.d >= 0) { pAET->bres.minor += pAET->bres.m1; pAET->bres.d += pAET->bres.incr1; } else { pAET->bres.minor += pAET->bres.m; pAET->bres.d += pAET->bres.incr2; } } }; pPrevAET = pAET; pAET = pAET-> next; } }; | |||||
| 593 | EVALUATEEDGEEVENODD(pAET, pPrevAET, y){ if (pAET->ymax == y) { pPrevAET->next = pAET->next ; pAET = pPrevAET->next; if (pAET) pAET->back = pPrevAET ; } else { { if (pAET->bres.m1 > 0) { if (pAET->bres .d > 0) { pAET->bres.minor += pAET->bres.m1; pAET-> bres.d += pAET->bres.incr1; } else { pAET->bres.minor += pAET->bres.m; pAET->bres.d += pAET->bres.incr2; } } else { if (pAET->bres.d >= 0) { pAET->bres.minor += pAET->bres.m1; pAET->bres.d += pAET->bres.incr1; } else { pAET->bres.minor += pAET->bres.m; pAET->bres.d += pAET->bres.incr2; } } }; pPrevAET = pAET; pAET = pAET-> next; } }; | |||||
| 594 | } | |||||
| 595 | miInsertionSort(&AET); | |||||
| 596 | } | |||||
| 597 | } | |||||
| 598 | else { /* default to WindingNumber */ | |||||
| 599 | ||||||
| 600 | /* | |||||
| 601 | * for each scanline | |||||
| 602 | */ | |||||
| 603 | for (y = ET.ymin; y < ET.ymax; y++) { | |||||
| 604 | /* | |||||
| 605 | * Add a new edge to the active edge table when we | |||||
| 606 | * get to the next edge. | |||||
| 607 | */ | |||||
| 608 | if (pSLL && y == pSLL->scanline) { | |||||
| 609 | miloadAET(&AET, pSLL->edgelist); | |||||
| 610 | micomputeWAET(&AET); | |||||
| 611 | pSLL = pSLL->next; | |||||
| 612 | } | |||||
| 613 | pPrevAET = &AET; | |||||
| 614 | pAET = AET.next; | |||||
| 615 | pWETE = pAET; | |||||
| 616 | ||||||
| 617 | /* | |||||
| 618 | * for each active edge | |||||
| 619 | */ | |||||
| 620 | while (pAET) { | |||||
| 621 | /* | |||||
| 622 | * if the next edge in the active edge table is | |||||
| 623 | * also the next edge in the winding active edge | |||||
| 624 | * table. | |||||
| 625 | */ | |||||
| 626 | if (pWETE == pAET) { | |||||
| 627 | ptsOut->x = pAET->bres.minor; | |||||
| 628 | ptsOut++->y = y; | |||||
| 629 | *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor; | |||||
| 630 | nPts++; | |||||
| 631 | ||||||
| 632 | /* | |||||
| 633 | * send out the buffer | |||||
| 634 | */ | |||||
| 635 | if (nPts == NUMPTSTOBUFFER200) { | |||||
| 636 | (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, | |||||
| 637 | FirstWidth, 1); | |||||
| 638 | ptsOut = FirstPoint; | |||||
| 639 | width = FirstWidth; | |||||
| 640 | nPts = 0; | |||||
| 641 | } | |||||
| 642 | ||||||
| 643 | pWETE = pWETE->nextWETE; | |||||
| 644 | while (pWETE != pAET) | |||||
| 645 | EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET){ if (pAET->ymax == y) { pPrevAET->next = pAET->next ; pAET = pPrevAET->next; fixWAET = 1; if (pAET) pAET->back = pPrevAET; } else { { if (pAET->bres.m1 > 0) { if (pAET ->bres.d > 0) { pAET->bres.minor += pAET->bres.m1 ; pAET->bres.d += pAET->bres.incr1; } else { pAET->bres .minor += pAET->bres.m; pAET->bres.d += pAET->bres.incr2 ; } } else { if (pAET->bres.d >= 0) { pAET->bres.minor += pAET->bres.m1; pAET->bres.d += pAET->bres.incr1; } else { pAET->bres.minor += pAET->bres.m; pAET->bres .d += pAET->bres.incr2; } } }; pPrevAET = pAET; pAET = pAET ->next; } }; | |||||
| ||||||
| 646 | pWETE = pWETE->nextWETE; | |||||
| 647 | } | |||||
| 648 | EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET){ if (pAET->ymax == y) { pPrevAET->next = pAET->next ; pAET = pPrevAET->next; fixWAET = 1; if (pAET) pAET->back = pPrevAET; } else { { if (pAET->bres.m1 > 0) { if (pAET ->bres.d > 0) { pAET->bres.minor += pAET->bres.m1 ; pAET->bres.d += pAET->bres.incr1; } else { pAET->bres .minor += pAET->bres.m; pAET->bres.d += pAET->bres.incr2 ; } } else { if (pAET->bres.d >= 0) { pAET->bres.minor += pAET->bres.m1; pAET->bres.d += pAET->bres.incr1; } else { pAET->bres.minor += pAET->bres.m; pAET->bres .d += pAET->bres.incr2; } } }; pPrevAET = pAET; pAET = pAET ->next; } }; | |||||
| 649 | } | |||||
| 650 | ||||||
| 651 | /* | |||||
| 652 | * reevaluate the Winding active edge table if we | |||||
| 653 | * just had to resort it or if we just exited an edge. | |||||
| 654 | */ | |||||
| 655 | if (miInsertionSort(&AET) || fixWAET) { | |||||
| 656 | micomputeWAET(&AET); | |||||
| 657 | fixWAET = 0; | |||||
| 658 | } | |||||
| 659 | } | |||||
| 660 | } | |||||
| 661 | ||||||
| 662 | /* | |||||
| 663 | * Get any spans that we missed by buffering | |||||
| 664 | */ | |||||
| 665 | (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, FirstWidth, 1); | |||||
| 666 | free(pETEs); | |||||
| 667 | miFreeStorage(SLLBlock.next); | |||||
| 668 | return TRUE1; | |||||
| 669 | } | |||||
| 670 | ||||||
| 671 | /* | |||||
| 672 | * Draw polygons. This routine translates the point by the origin if | |||||
| 673 | * pGC->miTranslate is non-zero, and calls to the appropriate routine to | |||||
| 674 | * actually scan convert the polygon. | |||||
| 675 | */ | |||||
| 676 | void | |||||
| 677 | miFillPolygon(DrawablePtr dst, GCPtr pgc, | |||||
| 678 | int shape, int mode, int count, DDXPointPtr pPts) | |||||
| 679 | { | |||||
| 680 | int i; | |||||
| 681 | int xorg, yorg; | |||||
| 682 | DDXPointPtr ppt; | |||||
| 683 | ||||||
| 684 | if (count == 0) | |||||
| 685 | return; | |||||
| 686 | ||||||
| 687 | ppt = pPts; | |||||
| 688 | if (pgc->miTranslate) { | |||||
| 689 | xorg = dst->x; | |||||
| 690 | yorg = dst->y; | |||||
| 691 | ||||||
| 692 | if (mode == CoordModeOrigin0) { | |||||
| 693 | for (i = 0; i < count; i++) { | |||||
| 694 | ppt->x += xorg; | |||||
| 695 | ppt++->y += yorg; | |||||
| 696 | } | |||||
| 697 | } | |||||
| 698 | else { | |||||
| 699 | ppt->x += xorg; | |||||
| 700 | ppt++->y += yorg; | |||||
| 701 | for (i = 1; i < count; i++) { | |||||
| 702 | ppt->x += (ppt - 1)->x; | |||||
| 703 | ppt->y += (ppt - 1)->y; | |||||
| 704 | ppt++; | |||||
| 705 | } | |||||
| 706 | } | |||||
| 707 | } | |||||
| 708 | else { | |||||
| 709 | if (mode == CoordModePrevious1) { | |||||
| 710 | ppt++; | |||||
| 711 | for (i = 1; i < count; i++) { | |||||
| 712 | ppt->x += (ppt - 1)->x; | |||||
| 713 | ppt->y += (ppt - 1)->y; | |||||
| 714 | ppt++; | |||||
| 715 | } | |||||
| 716 | } | |||||
| 717 | } | |||||
| 718 | if (shape == Convex2) | |||||
| 719 | miFillConvexPoly(dst, pgc, count, pPts); | |||||
| 720 | else | |||||
| 721 | miFillGeneralPoly(dst, pgc, count, pPts); | |||||
| 722 | } |