![[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.