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