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