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