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