![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to fillpath.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [WindowsNT SDKs] / ntddk / src / video / displays / s3|
Return to fillpath.c CVS log | Up to [WindowsNT SDKs] / ntddk / src / video / displays / s3 |
1.1 ! root 1: /******************************Module*Header*******************************\ ! 2: * Module Name: fillpath.c ! 3: * ! 4: * DrvFillPath ! 5: * ! 6: * Copyright (c) 1992-1993 Microsoft Corporation ! 7: \**************************************************************************/ ! 8: ! 9: // LATER identify convex polygons and special-case? ! 10: // LATER identify vertical edges and special-case? ! 11: // LATER move pointed-to variables into automatics in search loops ! 12: ! 13: #include "driver.h" ! 14: ! 15: // TMP_BUFFER_SIZE is the size of the buffer used to hold the edge list ! 16: // and accumulated rectangles. The buffer is simply allocated on the ! 17: // stack; consequently, its size plus the total size of all local variables ! 18: // in DrvFillPath must be less than 4K, or you will run into access ! 19: // violations when growing the stack (because there is only one guard page). ! 20: ! 21: #define TMP_BUFFER_SIZE 3800 // Must be less than 4k! ! 22: ! 23: // MAX_PATH_RECTS is the maximum number of rectangles we'll fill per call ! 24: // to the vS3FillRectangles code. Note that sizeof(RECTL) * MAX_PATH_RECTS ! 25: // must be less than TMP_BUFFER_SIZE, to leave room for some edges. ! 26: ! 27: #define MAX_PATH_RECTS 50 ! 28: ! 29: // Describe a single non-horizontal edge of a path to fill. ! 30: ! 31: typedef struct _EDGE { ! 32: PVOID pNext; ! 33: INT iScansLeft; ! 34: INT X; ! 35: INT Y; ! 36: INT iErrorTerm; ! 37: INT iErrorAdjustUp; ! 38: INT iErrorAdjustDown; ! 39: INT iXWhole; ! 40: INT iXDirection; ! 41: INT iWindingDirection; ! 42: } EDGE, *PEDGE; ! 43: ! 44: //MIX translation table. Translates a mix 1-16, into an old style Rop 0-255. ! 45: extern BYTE gaMix[]; ! 46: ! 47: VOID AdvanceAETEdges(EDGE *pAETHead); ! 48: VOID XSortAETEdges(EDGE *pAETHead); ! 49: VOID MoveNewEdges(EDGE *pGETHead, EDGE *pAETHead, INT iCurrentY); ! 50: EDGE * AddEdgeToGET(EDGE *pGETHead, EDGE *pFreeEdge, POINTFIX *ppfxEdgeStart, ! 51: POINTFIX *ppfxEdgeEnd); ! 52: VOID ConstructGET(EDGE *pGETHead, EDGE *pFreeEdges, PATHOBJ *ppo, ! 53: PATHDATA *pd, BOOL bMore); ! 54: ! 55: /******************************Public*Routine******************************\ ! 56: * vS3FillRectangles ! 57: * ! 58: * Draw the list of rectangles with a solid color. ! 59: * ! 60: * NOTE: This routine modifies data in the prclRects buffer! ! 61: * ! 62: \**************************************************************************/ ! 63: ! 64: VOID vS3FillRectangles ! 65: ( ! 66: PPDEV ppdev, ! 67: ULONG ulNumRects, ! 68: RECTL* prclRects, ! 69: ULONG ulS3Mix, ! 70: ULONG iSolidColor ! 71: ) ! 72: { ! 73: RECTL* prclSave; // For coalescing ! 74: BOOL bWait; // If need to do a FIFO_WAIT first ! 75: LONG lCurrentWidth; // For caching last width set ! 76: ! 77: ASSERTS3(ulNumRects > 0, "Shouldn't get zero rectangles\n"); ! 78: ! 79: lCurrentWidth = -1; ! 80: ! 81: // Since an 'in' is so expensive, and it's more than likely that the ! 82: // FIFO is currently empty, we'll contrive to wait for enough entries ! 83: // to do our initialization as well as for outputting the first ! 84: // rectangle: ! 85: ! 86: bWait = FALSE; ! 87: FIFOWAIT(FIFO_8_EMPTY); ! 88: ! 89: TEST_AND_SET_FRGD_MIX(FOREGROUND_COLOR | (WORD) ulS3Mix); ! 90: TEST_AND_SET_FRGD_COLOR((INT) iSolidColor); ! 91: ! 92: OUTPW (MULTIFUNC_CNTL, (DATA_EXTENSION | ALL_ONES)); ! 93: ! 94: prclSave = prclRects; ! 95: ! 96: while (--ulNumRects) ! 97: { ! 98: prclRects++; ! 99: ! 100: if (prclSave->left == prclRects->left && ! 101: prclSave->right == prclRects->right && ! 102: prclSave->bottom == prclRects->top) ! 103: { ! 104: // Coalesce this rectangle: ! 105: ! 106: prclSave->bottom = prclRects->bottom; ! 107: } ! 108: else if (prclSave->bottom == prclSave->top + 1) ! 109: { ! 110: // Output as a line if a single scan high: ! 111: ! 112: if (bWait) ! 113: FIFOWAIT(FIFO_4_EMPTY); ! 114: ! 115: OUTPW (CUR_X, prclSave->left); ! 116: OUTPW (CUR_Y, prclSave->top); ! 117: ! 118: if (prclSave->right - prclSave->left != lCurrentWidth) ! 119: { ! 120: lCurrentWidth = prclSave->right - prclSave->left; ! 121: OUTPW (LINE_MAX, lCurrentWidth); ! 122: } ! 123: ! 124: OUTPW (CMD, DRAW_LINE | DRAW | ! 125: DIR_TYPE_RADIAL | LAST_PIXEL_OFF | ! 126: MULTIPLE_PIXELS | DRAWING_DIRECTION_0 | ! 127: WRITE); ! 128: ! 129: bWait = TRUE; ! 130: prclSave = prclRects; ! 131: } ! 132: else ! 133: { ! 134: // Output an entire rectangle: ! 135: ! 136: if (bWait) ! 137: FIFOWAIT(FIFO_5_EMPTY); ! 138: ! 139: OUTPW (CUR_X, prclSave->left); ! 140: OUTPW (CUR_Y, prclSave->top); ! 141: OUTPW (RECT_WIDTH, (prclSave->right - prclSave->left - 1)); ! 142: OUTPW (MULTIFUNC_CNTL, (RECT_HEIGHT | ! 143: (prclSave->bottom - prclSave->top - 1))); ! 144: ! 145: OUTPW (CMD, RECTANGLE_FILL | DRAWING_DIR_TBLRXM | ! 146: DRAW | DIR_TYPE_XY | ! 147: LAST_PIXEL_ON | MULTIPLE_PIXELS | ! 148: WRITE); ! 149: ! 150: lCurrentWidth = -1; // Rectangle overwrites width ! 151: bWait = TRUE; ! 152: prclSave = prclRects; ! 153: } ! 154: } ! 155: ! 156: // Output saved rectangle: ! 157: ! 158: if (prclSave->bottom == prclSave->top + 1) ! 159: { ! 160: // Output as a line if a single scan high: ! 161: ! 162: if (bWait) ! 163: FIFOWAIT(FIFO_4_EMPTY); ! 164: ! 165: OUTPW (CUR_X, prclSave->left); ! 166: OUTPW (CUR_Y, prclSave->top); ! 167: ! 168: if (prclSave->right - prclSave->left != lCurrentWidth) ! 169: { ! 170: lCurrentWidth = prclSave->right - prclSave->left; ! 171: OUTPW (LINE_MAX, lCurrentWidth); ! 172: } ! 173: ! 174: OUTPW (CMD, DRAW_LINE | DRAW | ! 175: DIR_TYPE_RADIAL | LAST_PIXEL_OFF | ! 176: MULTIPLE_PIXELS | DRAWING_DIRECTION_0 | ! 177: WRITE); ! 178: } ! 179: else ! 180: { ! 181: // Output an entire rectangle: ! 182: ! 183: if (bWait) ! 184: FIFOWAIT(FIFO_5_EMPTY); ! 185: ! 186: OUTPW (CUR_X, prclSave->left); ! 187: OUTPW (CUR_Y, prclSave->top); ! 188: OUTPW (RECT_WIDTH, (prclSave->right - prclSave->left - 1)); ! 189: OUTPW (MULTIFUNC_CNTL, (RECT_HEIGHT | ! 190: (prclSave->bottom - prclSave->top - 1))); ! 191: ! 192: OUTPW (CMD, RECTANGLE_FILL | DRAWING_DIR_TBLRXM | ! 193: DRAW | DIR_TYPE_XY | ! 194: LAST_PIXEL_ON | MULTIPLE_PIXELS | ! 195: WRITE); ! 196: } ! 197: } ! 198: ! 199: /******************************Public*Routine******************************\ ! 200: * DrvFillPath ! 201: * ! 202: * Fill the specified path with the specified brush and ROP. ! 203: * ! 204: \**************************************************************************/ ! 205: ! 206: BOOL DrvFillPath ! 207: ( ! 208: SURFOBJ *pso, ! 209: PATHOBJ *ppo, ! 210: CLIPOBJ *pco, ! 211: BRUSHOBJ *pbo, ! 212: POINTL *pptlBrush, ! 213: MIX mix, ! 214: FLONG flOptions ! 215: ) ! 216: { ! 217: PPDEV ppdev; ! 218: BYTE jClipping; // clipping type ! 219: EDGE *pCurrentEdge; ! 220: EDGE AETHead; // dummy head/tail node & sentinel for Active Edge Table ! 221: EDGE *pAETHead; // pointer to AETHead ! 222: EDGE GETHead; // dummy head/tail node & sentinel for Global Edge Table ! 223: EDGE *pGETHead; // pointer to GETHead ! 224: EDGE *pFreeEdges; // pointer to memory free for use to store edges ! 225: ULONG ulNumRects; // # of rectangles to draw currently in rectangle list ! 226: RECTL *prclRects; // pointer to start of rectangle draw list ! 227: INT iCurrentY; // scan line for which we're currently scanning out the ! 228: // fill ! 229: ! 230: BOOL bMore; ! 231: PATHDATA pd; ! 232: ULONG ulS3Mix; ! 233: BYTE ajBuffer[TMP_BUFFER_SIZE]; ! 234: ! 235: // We currently handle only solid brushes: ! 236: if (pbo->iSolidColor == (ULONG) -1) ! 237: return(FALSE); ! 238: ! 239: // Is there clipping? We don't handle that ! 240: // LATER handle rectangle clipping ! 241: ! 242: // Set up the clipping type ! 243: if (pco == (CLIPOBJ *) NULL) { ! 244: // No CLIPOBJ provided, so we don't have to worry about clipping ! 245: jClipping = DC_TRIVIAL; ! 246: } else { ! 247: // Use the CLIPOBJ-provided clipping ! 248: jClipping = pco->iDComplexity; ! 249: } ! 250: ! 251: if (jClipping != DC_TRIVIAL) { ! 252: return(FALSE); // there is clipping; let GDI fill the path ! 253: } ! 254: ! 255: // There's nothing to do if there's only one point ! 256: // LATER is this needed? ! 257: if (ppo->cCurves <= 1) { ! 258: return(TRUE); ! 259: } ! 260: ! 261: // Do we have enough memory for all the edges? ! 262: // LATER does cCurves include closure? ! 263: if (ppo->cCurves > ((TMP_BUFFER_SIZE - ! 264: (MAX_PATH_RECTS * (ULONG)sizeof(RECTL))) / sizeof(EDGE))) { ! 265: return(FALSE); // too many edges; let GDI fill the path ! 266: } ! 267: ! 268: // See if we can handle this pattern and ROP ! 269: ! 270: // We don't handle ROP4s ! 271: if ((mix & 0xFF) != ((mix >> 8) & 0xFF)) { ! 272: return(FALSE); // it's a ROP4; let GDI fill the path ! 273: } ! 274: ! 275: // The drawing surface ! 276: ppdev = (PPDEV) pso->dhsurf; ! 277: ! 278: ulS3Mix = Rop2ToS3Rop[(mix & 0xFF)-1]; ! 279: ! 280: /* set up working storage in the temporary buffer */ ! 281: ! 282: prclRects = (RECTL*) &ajBuffer[0]; ! 283: ! 284: /* enumerate path here first time to check for special ! 285: cases (rectangles, single pixel and monotone polygons) */ ! 286: ! 287: /* it is too difficult to determine interaction between ! 288: multiple paths, if there is more than one, skip this */ ! 289: ! 290: if (! (bMore = PATHOBJ_bEnum(ppo, &pd))) { ! 291: RECTL *rectangle; ! 292: INT i = pd.count; ! 293: ! 294: /* if the count is less than three than it is at best a ! 295: line which means nothing gets drawn so get out now */ ! 296: ! 297: if (i < 3) { ! 298: return(TRUE); ! 299: } ! 300: ! 301: /* if the count is four, check to see if the polygon is ! 302: really a rectangle since we can really speed that up */ ! 303: ! 304: if (i == 4) { ! 305: rectangle = prclRects; ! 306: ! 307: /* we have to start somewhere so assume that most ! 308: applications specify the top left point first ! 309: ! 310: we want to check that the first two points are ! 311: either vertically or horizontally aligned. if ! 312: they are then we check that the last point [3] ! 313: is either horizontally or vertically aligned, ! 314: and finally that the 3rd point [2] is aligned ! 315: with both the first point and the last point */ ! 316: ! 317: #define FIX_SHIFT 4L ! 318: #define FIX_MASK (- (1 << FIX_SHIFT)) ! 319: ! 320: rectangle->top = pd.pptfx[0].y - 1 & FIX_MASK; ! 321: rectangle->left = pd.pptfx[0].x - 1 & FIX_MASK; ! 322: rectangle->right = pd.pptfx[1].x - 1 & FIX_MASK; ! 323: ! 324: if (rectangle->left ^ rectangle->right) { ! 325: if (rectangle->top ^ (pd.pptfx[1].y - 1 & FIX_MASK)) ! 326: goto not_rectangle; ! 327: ! 328: if (rectangle->left ^ (pd.pptfx[3].x - 1 & FIX_MASK)) ! 329: goto not_rectangle; ! 330: ! 331: if (rectangle->right ^ (pd.pptfx[2].x - 1 & FIX_MASK)) ! 332: goto not_rectangle; ! 333: ! 334: rectangle->bottom = pd.pptfx[2].y - 1 & FIX_MASK; ! 335: if (rectangle->bottom ^ (pd.pptfx[3].y - 1 & FIX_MASK)) ! 336: goto not_rectangle; ! 337: } ! 338: else { ! 339: if (rectangle->top ^ (pd.pptfx[3].y - 1 & FIX_MASK)) ! 340: goto not_rectangle; ! 341: ! 342: rectangle->bottom = pd.pptfx[1].y - 1 & FIX_MASK; ! 343: if (rectangle->bottom ^ (pd.pptfx[2].y - 1 & FIX_MASK)) ! 344: goto not_rectangle; ! 345: ! 346: rectangle->right = pd.pptfx[2].x - 1 & FIX_MASK; ! 347: if (rectangle->right ^ (pd.pptfx[3].x - 1 & FIX_MASK)) ! 348: goto not_rectangle; ! 349: } ! 350: ! 351: /* if the left is greater than the right then ! 352: swap them so the blt code doesn't wig out */ ! 353: ! 354: if (rectangle->left > rectangle->right) { ! 355: FIX temp; ! 356: ! 357: temp = rectangle->left; ! 358: rectangle->left = rectangle->right; ! 359: rectangle->right = temp; ! 360: } ! 361: else { ! 362: ! 363: /* if left == right there's nothing to draw */ ! 364: ! 365: if (rectangle->left == rectangle->right) { ! 366: return(TRUE); ! 367: } ! 368: } ! 369: ! 370: /* shift the values to get pixel coordinates */ ! 371: ! 372: rectangle->left = (rectangle->left >> FIX_SHIFT) + 1; ! 373: rectangle->right = (rectangle->right >> FIX_SHIFT) + 1; ! 374: ! 375: if (rectangle->top > rectangle->bottom) { ! 376: FIX temp; ! 377: ! 378: temp = rectangle->top; ! 379: rectangle->top = rectangle->bottom; ! 380: rectangle->bottom = temp; ! 381: } ! 382: else { ! 383: if (rectangle->top == rectangle->bottom) { ! 384: return(TRUE); ! 385: } ! 386: } ! 387: ! 388: /* shift the values to get pixel coordinates */ ! 389: ! 390: rectangle->top = (rectangle->top >> FIX_SHIFT) + 1; ! 391: rectangle->bottom = (rectangle->bottom >> FIX_SHIFT) + 1; ! 392: ! 393: /* if we get here then the polygon is a rectangle, ! 394: set count to 1 and goto bottom to draw it */ ! 395: ! 396: ulNumRects = 1; ! 397: goto draw_remaining_rectangles; ! 398: } ! 399: } ! 400: ! 401: ! 402: /* if this is not one of the special cases then we find ! 403: ourselves here and we scan convert by building edges */ ! 404: ! 405: not_rectangle: ! 406: pFreeEdges = (EDGE *) (((BYTE *) prclRects) + ! 407: (MAX_PATH_RECTS * sizeof(RECTL))); // storage for list of edges ! 408: // between which to fill ! 409: ! 410: // Initialize an empty list of rectangles to fill ! 411: ulNumRects = 0; ! 412: ! 413: // Enumerate the path edges and build a Global Edge Table (GET) from them ! 414: // in YX-sorted order. ! 415: pGETHead = &GETHead; ! 416: ConstructGET(pGETHead, pFreeEdges, ppo, &pd, bMore); ! 417: ! 418: // Create an empty AET with the head node also a tail sentinel ! 419: pAETHead = &AETHead; ! 420: AETHead.pNext = pAETHead; // mark that the AET is empty ! 421: AETHead.X = 0x7FFFFFFF; // this is greater than any valid X value, so ! 422: // searches will always terminate ! 423: ! 424: // Top scan of polygon is the top of the first edge we come to ! 425: iCurrentY = ((EDGE *)GETHead.pNext)->Y; ! 426: ! 427: // Loop through all the scans in the polygon, adding edges from the GET to ! 428: // the Active Edge Table (AET) as we come to their starts, and scanning out ! 429: // the AET at each scan into a rectangle list. Each time it fills up, the ! 430: // rectangle list is passed to the filling routine, and then once again at ! 431: // the end if any rectangles remain undrawn. We continue so long as there ! 432: // are edges to be scanned out ! 433: while (1) { ! 434: ! 435: // Advance the edges in the AET one scan, discarding any that have ! 436: // reached the end (if there are any edges in the AET) ! 437: if (AETHead.pNext != pAETHead) { ! 438: AdvanceAETEdges(pAETHead); ! 439: } ! 440: ! 441: // If the AET is empty, done if the GET is empty, else jump ahead to ! 442: // the next edge in the GET; if the AET isn't empty, re-sort the AET ! 443: if (AETHead.pNext == pAETHead) { ! 444: if (GETHead.pNext == pGETHead) { ! 445: // Done if there are no edges in either the AET or the GET ! 446: break; ! 447: } ! 448: // There are no edges in the AET, so jump ahead to the next edge in ! 449: // the GET ! 450: iCurrentY = ((EDGE *)GETHead.pNext)->Y; ! 451: } else { ! 452: // Re-sort the edges in the AET by X coordinate, if there are at ! 453: // least two edges in the AET (there could be one edge if the ! 454: // balancing edge hasn't yet been added from the GET) ! 455: if (((EDGE *)AETHead.pNext)->pNext != pAETHead) { ! 456: XSortAETEdges(pAETHead); ! 457: } ! 458: } ! 459: ! 460: // Move any new edges that start on this scan from the GET to the AET; ! 461: // bother calling only if there's at least one edge to add ! 462: if (((EDGE *)GETHead.pNext)->Y == iCurrentY) { ! 463: MoveNewEdges(pGETHead, pAETHead, iCurrentY); ! 464: } ! 465: ! 466: // Scan the AET into rectangles to fill (there's always at least one ! 467: // edge pair in the AET) ! 468: pCurrentEdge = AETHead.pNext; // point to the first edge ! 469: do { ! 470: ! 471: INT iLeftEdge; ! 472: ! 473: // The left edge of any given edge pair is easy to find; it's just ! 474: // wherever we happen to be currently ! 475: iLeftEdge = pCurrentEdge->X; ! 476: ! 477: // Find the matching right edge according to the current fill rule ! 478: if ((flOptions & FP_WINDINGMODE) != 0) { ! 479: ! 480: INT iWindingCount; ! 481: ! 482: // Do winding fill; scan across until we've found equal numbers ! 483: // of up and down edges ! 484: iWindingCount = pCurrentEdge->iWindingDirection; ! 485: do { ! 486: pCurrentEdge = pCurrentEdge->pNext; ! 487: iWindingCount += pCurrentEdge->iWindingDirection; ! 488: } while (iWindingCount != 0); ! 489: } else { ! 490: // Odd-even fill; the next edge is the matching right edge ! 491: pCurrentEdge = pCurrentEdge->pNext; ! 492: } ! 493: ! 494: // See if the resulting span encompasses at least one pixel, and ! 495: // add it to the list of rectangles to draw if so ! 496: if (iLeftEdge < pCurrentEdge->X) { ! 497: ! 498: // We've got an edge pair to add to the list to be filled; see ! 499: // if there's room for one more rectangle ! 500: if (ulNumRects >= MAX_PATH_RECTS) { ! 501: // No more room; draw the rectangles in the list and reset ! 502: // it to empty ! 503: ! 504: vS3FillRectangles(ppdev, ulNumRects, prclRects, ulS3Mix, ! 505: pbo->iSolidColor); ! 506: ! 507: // Reset the list to empty ! 508: ulNumRects = 0; ! 509: } ! 510: ! 511: // Add the rectangle representing the current edge pair ! 512: // LATER coalesce rectangles ! 513: prclRects[ulNumRects].top = iCurrentY; ! 514: prclRects[ulNumRects].bottom = iCurrentY+1; ! 515: prclRects[ulNumRects].left = iLeftEdge; ! 516: prclRects[ulNumRects].right = pCurrentEdge->X; ! 517: ulNumRects++; ! 518: } ! 519: } while ((pCurrentEdge = pCurrentEdge->pNext) != pAETHead); ! 520: ! 521: iCurrentY++; // next scan ! 522: } ! 523: ! 524: /* draw the remaining rectangles, if there are any */ ! 525: ! 526: draw_remaining_rectangles: ! 527: ! 528: if (ulNumRects > 0) { ! 529: vS3FillRectangles(ppdev, ulNumRects, prclRects, ulS3Mix, pbo->iSolidColor); ! 530: } ! 531: ! 532: return(TRUE); // done successfully ! 533: } ! 534: ! 535: // Advance the edges in the AET to the next scan, dropping any for which we've ! 536: // done all scans. Assumes there is at least one edge in the AET. ! 537: VOID AdvanceAETEdges(EDGE *pAETHead) ! 538: { ! 539: EDGE *pLastEdge, *pCurrentEdge; ! 540: ! 541: pLastEdge = pAETHead; ! 542: pCurrentEdge = pLastEdge->pNext; ! 543: do { ! 544: ! 545: // Count down this edge's remaining scans ! 546: if (--pCurrentEdge->iScansLeft == 0) { ! 547: // We've done all scans for this edge; drop this edge from the AET ! 548: pLastEdge->pNext = pCurrentEdge->pNext; ! 549: } else { ! 550: // Advance the edge's X coordinate for a 1-scan Y advance ! 551: // Advance by the minimum amount ! 552: pCurrentEdge->X += pCurrentEdge->iXWhole; ! 553: // Advance the error term and see if we got one extra pixel this ! 554: // time ! 555: pCurrentEdge->iErrorTerm += pCurrentEdge->iErrorAdjustUp; ! 556: if (pCurrentEdge->iErrorTerm >= 0) { ! 557: // The error term turned over, so adjust the error term and ! 558: // advance the extra pixel ! 559: pCurrentEdge->iErrorTerm -= pCurrentEdge->iErrorAdjustDown; ! 560: pCurrentEdge->X += pCurrentEdge->iXDirection; ! 561: } ! 562: ! 563: pLastEdge = pCurrentEdge; ! 564: } ! 565: } while ((pCurrentEdge = pLastEdge->pNext) != pAETHead); ! 566: } ! 567: ! 568: // X-sort the AET, because the edges may have moved around relative to ! 569: // one another when we advanced them. We'll use a multipass bubble ! 570: // sort, which is actually okay for this application because edges ! 571: // rarely move relative to one another, so we usually do just one pass. ! 572: // Also, this makes it easy to keep just a singly-linked list. Assumes there ! 573: // are at least two edges in the AET. ! 574: VOID XSortAETEdges(EDGE *pAETHead) ! 575: { ! 576: BOOL bEdgesSwapped; ! 577: EDGE *pLastEdge, *pCurrentEdge, *pNextEdge; ! 578: ! 579: do { ! 580: ! 581: bEdgesSwapped = FALSE; ! 582: pLastEdge = pAETHead; ! 583: pCurrentEdge = pLastEdge->pNext; ! 584: pNextEdge = pCurrentEdge->pNext; ! 585: ! 586: do { ! 587: if (pNextEdge->X < pCurrentEdge->X) { ! 588: ! 589: // Next edge is to the left of the current edge; swap them ! 590: pLastEdge->pNext = pNextEdge; ! 591: pCurrentEdge->pNext = pNextEdge->pNext; ! 592: pNextEdge->pNext = pCurrentEdge; ! 593: bEdgesSwapped = TRUE; ! 594: pCurrentEdge = pNextEdge; // continue sorting before the edge ! 595: // we just swapped; it might move ! 596: // farther yet ! 597: } ! 598: pLastEdge = pCurrentEdge; ! 599: pCurrentEdge = pLastEdge->pNext; ! 600: } while ((pNextEdge = pCurrentEdge->pNext) != pAETHead); ! 601: } while (bEdgesSwapped); ! 602: } ! 603: ! 604: // Moves all edges that start on the current scan from the GET to the AET in ! 605: // X-sorted order. Parameters are pointer to head of GET and pointer to dummy ! 606: // edge at head of AET, plus current scan line. Assumes there's at least one ! 607: // edge to be moved. ! 608: VOID MoveNewEdges(EDGE *pGETHead, EDGE *pAETHead, INT iCurrentY) ! 609: { ! 610: EDGE *pCurrentEdge = pAETHead; ! 611: EDGE *pGETNext = pGETHead->pNext; ! 612: ! 613: do { ! 614: ! 615: // Scan through the AET until the X-sorted insertion point for this ! 616: // edge is found. We can continue from where the last search left ! 617: // off because the edges in the GET are in X sorted order, as is ! 618: // the AET. The search always terminates because the AET sentinel ! 619: // is greater than any valid X ! 620: while (pGETNext->X > ((EDGE *)pCurrentEdge->pNext)->X) { ! 621: pCurrentEdge = pCurrentEdge->pNext; ! 622: } ! 623: ! 624: // We've found the insertion point; add the GET edge to the AET, and ! 625: // remove it from the GET ! 626: pGETHead->pNext = pGETNext->pNext; ! 627: pGETNext->pNext = pCurrentEdge->pNext; ! 628: pCurrentEdge->pNext = pGETNext; ! 629: pCurrentEdge = pGETNext; // continue insertion search for the next ! 630: // GET edge after the edge we just added ! 631: pGETNext = pGETHead->pNext; ! 632: ! 633: } while (pGETNext->Y == iCurrentY); ! 634: } ! 635: ! 636: ! 637: ! 638: ! 639: ! 640: // Build the Global Edge Table from the path. There must be enough memory in ! 641: // the free edge area to hold all edges. The GET is constructed in Y-X order, ! 642: // and has a head/tail/sentinel node at pGETHead. ! 643: ! 644: VOID ConstructGET( ! 645: EDGE *pGETHead, ! 646: EDGE *pFreeEdges, ! 647: PATHOBJ *ppo, ! 648: PATHDATA *pd, ! 649: BOOL bMore) ! 650: { ! 651: POINTFIX pfxPathStart; // point that started the current subpath ! 652: POINTFIX pfxPathPrevious; // point before the current point in a subpath; ! 653: // starts the current edge ! 654: ! 655: /* Create an empty GET with the head node also a tail sentinel */ ! 656: ! 657: pGETHead->pNext = pGETHead; // mark that the GET is empty ! 658: pGETHead->Y = 0x7FFFFFFF; // this is greater than any valid Y value, so ! 659: // searches will always terminate ! 660: ! 661: /* PATHOBJ_vEnumStart is implicitly performed by engine ! 662: already and first path is enumerated by the caller */ ! 663: ! 664: next_subpath: ! 665: ! 666: /* Make sure the PATHDATA is not empty (is this necessary) */ ! 667: ! 668: if (pd->count != 0) { ! 669: ! 670: /* If first point starts a subpath, remember it as such ! 671: and go on to the next point, so we can get an edge */ ! 672: ! 673: if (pd->flags & PD_BEGINSUBPATH) { ! 674: ! 675: /* the first point starts the subpath; remember it */ ! 676: ! 677: pfxPathStart = *pd->pptfx; /* the subpath starts here */ ! 678: pfxPathPrevious = *pd->pptfx; /* this points starts the next edge */ ! 679: pd->pptfx++; /* advance to the next point */ ! 680: pd->count--; /* count off this point */ ! 681: } ! 682: ! 683: ! 684: /* add edges in PATHDATA to GET, in Y-X sorted order */ ! 685: ! 686: while (pd->count--) { ! 687: pFreeEdges = ! 688: AddEdgeToGET(pGETHead, pFreeEdges, &pfxPathPrevious, pd->pptfx); ! 689: pfxPathPrevious = *pd->pptfx; /* current point becomes previous */ ! 690: pd->pptfx++; /* advance to the next point */ ! 691: } ! 692: ! 693: ! 694: /* If last point ends the subpath, insert the edge that ! 695: connects to firs t point (is this built in already) */ ! 696: ! 697: if (pd->flags & PD_ENDSUBPATH) { ! 698: pFreeEdges = AddEdgeToGET ! 699: (pGETHead, pFreeEdges, &pfxPathPrevious, &pfxPathStart); ! 700: } ! 701: } ! 702: ! 703: /* the initial loop conditions preclude a do, while or for */ ! 704: ! 705: if (bMore) { ! 706: bMore = PATHOBJ_bEnum(ppo, pd); ! 707: goto next_subpath; ! 708: } ! 709: } ! 710: ! 711: // Adds the edge described by the two passed-in points to the Global Edge ! 712: // Table, if the edge spans at least one pixel vertically. ! 713: EDGE * AddEdgeToGET(EDGE *pGETHead, EDGE *pFreeEdge, ! 714: POINTFIX *ppfxEdgeStart, POINTFIX *ppfxEdgeEnd) ! 715: { ! 716: INT iYStart, iYEnd, iXStart, iXEnd, iYHeight, iXWidth; ! 717: ! 718: // Set the winding-rule direction of the edge, and put the endpoints in ! 719: // top-to-bottom order ! 720: iYHeight = ppfxEdgeEnd->y - ppfxEdgeStart->y; ! 721: if (iYHeight >= 0) { ! 722: iXStart = ppfxEdgeStart->x; ! 723: iYStart = ppfxEdgeStart->y; ! 724: iXEnd = ppfxEdgeEnd->x; ! 725: iYEnd = ppfxEdgeEnd->y; ! 726: pFreeEdge->iWindingDirection = 1; ! 727: } else { ! 728: iYHeight = -iYHeight; ! 729: iXEnd = ppfxEdgeStart->x; ! 730: iYEnd = ppfxEdgeStart->y; ! 731: iXStart = ppfxEdgeEnd->x; ! 732: iYStart = ppfxEdgeEnd->y; ! 733: pFreeEdge->iWindingDirection = -1; ! 734: } ! 735: ! 736: // First pixel scan line (non-fractional GIQ Y coordinate) edge intersects. ! 737: // Dividing by 16 with a shift is okay because Y is always positive ! 738: pFreeEdge->Y = (iYStart + 15) >> 4; ! 739: ! 740: // Calculate the number of pixels spanned by this edge ! 741: pFreeEdge->iScansLeft = ((iYEnd + 15) >> 4) - pFreeEdge->Y; ! 742: if (pFreeEdge->iScansLeft <= 0) { ! 743: return(pFreeEdge); // no pixels at all are spanned, so we can ignore ! 744: // this edge ! 745: } ! 746: ! 747: // Set the error term and adjustment factors, all in GIQ coordinates for ! 748: // now ! 749: iXWidth = iXEnd - iXStart; ! 750: if (iXWidth >= 0) { ! 751: // Left to right, so we change X as soon as we move at all ! 752: pFreeEdge->iXDirection = 1; ! 753: pFreeEdge->iErrorTerm = -1; ! 754: } else { ! 755: // Right to left, so we don't change X until we've moved a full GIQ ! 756: // coordinate ! 757: iXWidth = -iXWidth; ! 758: pFreeEdge->iXDirection = -1; ! 759: pFreeEdge->iErrorTerm = -iYHeight; ! 760: } ! 761: ! 762: if (iXWidth >= iYHeight) { ! 763: // Calculate base run length (minimum distance advanced in X for a 1- ! 764: // scan advance in Y) ! 765: pFreeEdge->iXWhole = iXWidth / iYHeight; ! 766: // Add sign back into base run length if going right to left ! 767: if (pFreeEdge->iXDirection == -1) { ! 768: pFreeEdge->iXWhole = -pFreeEdge->iXWhole; ! 769: } ! 770: pFreeEdge->iErrorAdjustUp = iXWidth % iYHeight; ! 771: } else { ! 772: // Base run length is 0, because line is closer to vertical than ! 773: // horizontal ! 774: pFreeEdge->iXWhole = 0; ! 775: pFreeEdge->iErrorAdjustUp = iXWidth; ! 776: } ! 777: pFreeEdge->iErrorAdjustDown = iYHeight; ! 778: ! 779: // If the edge doesn't start on a pixel scan (that is, it starts at a ! 780: // fractional GIQ coordinate), advance it to the first pixel scan it ! 781: // intersects ! 782: // LATER might be faster to use multiplication and division to jump ahead, ! 783: // rather than looping ! 784: while ((iYStart & 0x0F) != 0) { ! 785: // Starts at a fractional GIQ coordinate, not exactly on a pixel scan ! 786: ! 787: // Advance the edge's GIQ X coordinate for a 1-GIQ-pixel Y advance ! 788: // Advance by the minimum amount ! 789: iXStart += pFreeEdge->iXWhole; ! 790: // Advance the error term and see if we got one extra pixel this time ! 791: pFreeEdge->iErrorTerm += pFreeEdge->iErrorAdjustUp; ! 792: if (pFreeEdge->iErrorTerm >= 0) { ! 793: // The error term turned over, so adjust the error term and ! 794: // advance the extra pixel ! 795: pFreeEdge->iErrorTerm -= pFreeEdge->iErrorAdjustDown; ! 796: iXStart += pFreeEdge->iXDirection; ! 797: } ! 798: iYStart++; // advance to the next GIQ Y coordinate ! 799: } ! 800: ! 801: // Turn the calculations into pixel rather than GIQ calculations ! 802: ! 803: // Move the X coordinate to the nearest pixel, and adjust the error term ! 804: // accordingly ! 805: // Dividing by 16 with a shift is okay because X is always positive ! 806: pFreeEdge->X = (iXStart + 15) >> 4; // convert from GIQ to pixel coordinates ! 807: ! 808: // LATER adjust only if needed (if prestepped above)? ! 809: if (pFreeEdge->iXDirection == 1) { ! 810: // Left to right ! 811: pFreeEdge->iErrorTerm -= pFreeEdge->iErrorAdjustDown * ! 812: (((iXStart + 15) & ~0x0F) - iXStart); ! 813: } else { ! 814: // Right to left ! 815: pFreeEdge->iErrorTerm -= pFreeEdge->iErrorAdjustDown * ! 816: ((iXStart - 1) & 0x0F); ! 817: } ! 818: ! 819: // Scale the error adjusts up by 16 times, to move 16 GIQ pixels at a time. ! 820: // Shifts work to do the multiplying because these values are always ! 821: // non-negative ! 822: pFreeEdge->iErrorAdjustUp <<= 4; ! 823: pFreeEdge->iErrorAdjustDown <<= 4; ! 824: ! 825: // Insert the edge into the GET in YX-sorted order. The search always ends ! 826: // because the GET has a sentinel with a greater-than-possible Y value ! 827: while ((pFreeEdge->Y > ((EDGE *)pGETHead->pNext)->Y) || ! 828: ((pFreeEdge->Y == ((EDGE *)pGETHead->pNext)->Y) && ! 829: (pFreeEdge->X > ((EDGE *)pGETHead->pNext)->X))) { ! 830: pGETHead = pGETHead->pNext; ! 831: } ! 832: ! 833: pFreeEdge->pNext = pGETHead->pNext; // link the edge into the GET ! 834: pGETHead->pNext = pFreeEdge; ! 835: ! 836: return(++pFreeEdge); // point to the next edge storage location for next ! 837: // time ! 838: } ! 839:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.