![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to lines.cxx 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 lines.cxx CVS log | Up to [WindowsNT SDKs] / ntddk / src / video / displays / s3 |
1.1 root 1: /*************************************************************************\
2: * Module Name: Lines.cxx
3: *
4: * C template for the ASM version of the line DDA calculator.
5: *
6: * Copyright (c) 1990-1993 Microsoft Corporation
7: * Copyright (c) 1992 Digital Equipment Corporation
8: \**************************************************************************/
9:
10: #define __CPLUSPLUS
11: #include "driver.h"
12: #include "lines.h"
13: #include "equad.hxx"
14:
15: #define SWAPL(x,y,t) {t = x; x = y; y = t;} // from wingdip.h
16: #define ROR_BYTE(x) ((((x) >> 1) & 0x7f) | (((x) & 0x01) << 7))
17: #define ROL_BYTE(x) ((((x) << 1) & 0xfe) | (((x) & 0x80) >> 7))
18: #define MIN(a, b) ((a) < (b) ? (a) : (b))
19: #define ABS(a) ((a) < 0 ? -(a) : (a))
20:
21: FLONG gaflRound[] = {
22: FL_H_ROUND_DOWN | FL_V_ROUND_DOWN, // no flips
23: FL_H_ROUND_DOWN | FL_V_ROUND_DOWN, // FL_FLIP_D
24: FL_H_ROUND_DOWN, // FL_FLIP_V
25: FL_V_ROUND_DOWN, // FL_FLIP_V | FL_FLIP_D
26: FL_V_ROUND_DOWN, // FL_FLIP_SLOPE_ONE
27: 0xbaadf00d, // FL_FLIP_SLOPE_ONE | FL_FLIP_D
28: FL_H_ROUND_DOWN, // FL_FLIP_SLOPE_ONE | FL_FLIP_V
29: 0xbaadf00d // FL_FLIP_SLOPE_ONE | FL_FLIP_V
30: | FL_FLIP_D
31: };
32:
33: extern "C"
34: BOOL
35: bIntegerLine (
36: PPDEV ppdev,
37: ULONG X1,
38: ULONG Y1,
39: ULONG X2,
40: ULONG Y2
41: );
42:
43: /******************************Public*Routine******************************\
44: * BOOL bLines(ppdev, pptfxFirst, pptfxBuf, cptfx, pls,
45: * prclClip, apfn[], flStart)
46: *
47: * Computes the DDA for the line and gets ready to draw it. Puts the
48: * pixel data into an array of strips, and calls a strip routine to
49: * do the actual drawing.
50: *
51: * Doing Lines Right
52: * -----------------
53: *
54: * In NT, all lines are given to the device driver in fractional
55: * coordinates, in a 28.4 fixed point format. The lower 4 bits are
56: * fractional for sub-pixel positioning.
57: *
58: * Note that you CANNOT! just round the coordinates to integers
59: * and pass the results to your favorite integer Bresenham routine!!
60: * (Unless, of course, you have such a high resolution device that
61: * nobody will notice -- not likely for a display device.) The
62: * fractions give a more accurate rendering of the line -- this is
63: * important for things like our Bezier curves, which would have 'kinks'
64: * if the points in its polyline approximation were rounded to integers.
65: *
66: * Unfortunately, for fractional lines there is more setup work to do
67: * a DDA than for integer lines. However, the main loop is exactly
68: * the same (and can be done entirely with 32 bit math).
69: *
70: * If You've Got Hardware That Does Bresenham
71: * ------------------------------------------
72: *
73: * A lot of hardware limits DDA error terms to 'n' bits. With fractional
74: * coordinates, 4 bits are given to the fractional part, letting
75: * you draw in hardware only those lines that lie entirely in a 2^(n-4)
76: * by 2^(n-4) pixel space.
77: *
78: * And you still have to correctly draw those lines with coordinates
79: * outside that space! Remember that the screen is only a viewport
80: * onto a 28.4 by 28.4 space -- if any part of the line is visible
81: * you MUST render it precisely, regardless of where the end points lie.
82: * So even if you do it in software, somewhere you'll have to have a
83: * 32 bit DDA routine.
84: *
85: * Our Implementation
86: * ------------------
87: *
88: * We employ a run length slice algorithm: our DDA calculates the
89: * number of pixels that are in each row (or 'strip') of pixels.
90: *
91: * We've separated the running of the DDA and the drawing of pixels:
92: * we run the DDA for several iterations and store the results in
93: * a 'strip' buffer (which are the lengths of consecutive pixel rows of
94: * the line), then we crank up a 'strip drawer' that will draw all the
95: * strips in the buffer.
96: *
97: * We also employ a 'half-flip' to reduce the number of strip
98: * iterations we need to do in the DDA and strip drawing loops: when a
99: * (normalized) line's slope is more than 1/2, we do a final flip
100: * about the line y = (1/2)x. So now, instead of each strip being
101: * consecutive horizontal or vertical pixel rows, each strip is composed
102: * of those pixels aligned in 45 degree rows. So a line like (0, 0) to
103: * (128, 128) would generate only one strip.
104: *
105: * We also always draw only left-to-right.
106: *
107: * Style lines may have arbitrary style patterns. We specially
108: * optimize the default patterns (and call them 'masked' styles).
109: *
110: * The DDA Derivation
111: * ------------------
112: *
113: * Here is how I like to think of the DDA calculation.
114: *
115: * We employ Knuth's "diamond rule": rendering a one-pixel-wide line
116: * can be thought of as dragging a one-pixel-wide by one-pixel-high
117: * diamond along the true line. Pixel centers lie on the integer
118: * coordinates, and so we light any pixel whose center gets covered
119: * by the "drag" region (John D. Hobby, Journal of the Association
120: * for Computing Machinery, Vol. 36, No. 2, April 1989, pp. 209-229).
121: *
122: * We must define which pixel gets lit when the true line falls
123: * exactly half-way between two pixels. In this case, we follow
124: * the rule: when two pels are equidistant, the upper or left pel
125: * is illuminated, unless the slope is exactly one, in which case
126: * the upper or right pel is illuminated. (So we make the edges
127: * of the diamond exclusive, except for the top and left vertices,
128: * which are inclusive, unless we have slope one.)
129: *
130: * This metric decides what pixels should be on any line BEFORE it is
131: * flipped around for our calculation. Having a consistent metric
132: * this way will let our lines blend nicely with our curves. The
133: * metric also dictates that we will never have one pixel turned on
134: * directly above another that's turned on. We will also never have
135: * a gap; i.e., there will be exactly one pixel turned on for each
136: * column between the start and end points. All that remains to be
137: * done is to decide how many pixels should be turned on for each row.
138: *
139: * So lines we draw will consist of varying numbers of pixels on
140: * successive rows, for example:
141: *
142: * ******
143: * *****
144: * ******
145: * *****
146: *
147: * We'll call each set of pixels on a row a "strip".
148: *
149: * (Please remember that our coordinate space has the origin as the
150: * upper left pixel on the screen; postive y is down and positive x
151: * is right.)
152: *
153: * Device coordinates are specified as fixed point 28.4 numbers,
154: * where the first 28 bits are the integer coordinate, and the last
155: * 4 bits are the fraction. So coordinates may be thought of as
156: * having the form (x, y) = (M/F, N/F) where F is the constant scaling
157: * factor F = 2^4 = 16, and M and N are 32 bit integers.
158: *
159: * Consider the line from (M0/F, N0/F) to (M1/F, N1/F) which runs
160: * left-to-right and whose slope is in the first octant, and let
161: * dM = M1 - M0 and dN = N1 - N0. Then dM >= 0, dN >= 0 and dM >= dN.
162: *
163: * Since the slope of the line is less than 1, the edges of the
164: * drag region are created by the top and bottom vertices of the
165: * diamond. At any given pixel row y of the line, we light those
166: * pixels whose centers are between the left and right edges.
167: *
168: * Let mL(n) denote the line representing the left edge of the drag
169: * region. On pixel row j, the column of the first pixel to be
170: * lit is
171: *
172: * iL(j) = ceiling( mL(j * F) / F)
173: *
174: * Since the line's slope is less than one:
175: *
176: * iL(j) = ceiling( mL([j + 1/2] F) / F )
177: *
178: * Recall the formula for our line:
179: *
180: * n(m) = (dN / dM) (m - M0) + N0
181: *
182: * m(n) = (dM / dN) (n - N0) + M0
183: *
184: * Since the line's slope is less than one, the line representing
185: * the left edge of the drag region is the original line offset
186: * by 1/2 pixel in the y direction:
187: *
188: * mL(n) = (dM / dN) (n - F/2 - N0) + M0
189: *
190: * From this we can figure out the column of the first pixel that
191: * will be lit on row j, being careful of rounding (if the left
192: * edge lands exactly on an integer point, the pixel at that
193: * point is not lit because of our rounding convention):
194: *
195: * iL(j) = floor( mL(j F) / F ) + 1
196: *
197: * = floor( ((dM / dN) (j F - F/2 - N0) + M0) / F ) + 1
198: *
199: * = floor( F dM j - F/2 dM - N0 dM + dN M0) / F dN ) + 1
200: *
201: * F dM j - [ dM (N0 + F/2) - dN M0 ]
202: * = floor( ---------------------------------- ) + 1
203: * F dN
204: *
205: * dM j - [ dM (N0 + F/2) - dN M0 ] / F
206: * = floor( ------------------------------------ ) + 1 (1)
207: * dN
208: *
209: * = floor( (dM j + alpha) / dN ) + 1
210: *
211: * where
212: *
213: * alpha = - [ dM (N0 + F/2) - dN M0 ] / F
214: *
215: * We use equation (1) to calculate the DDA: there are iL(j+1) - iL(j)
216: * pixels in row j. Because we are always calculating iL(j) for
217: * integer quantities of j, we note that the only fractional term
218: * is constant, and so we can 'throw away' the fractional bits of
219: * alpha:
220: *
221: * beta = floor( - [ dM (N0 + F/2) - dN M0 ] / F ) (2)
222: *
223: * so
224: *
225: * iL(j) = floor( (dM j + beta) / dN ) + 1 (3)
226: *
227: * for integers j.
228: *
229: * Note if iR(j) is the line's rightmost pixel on row j, that
230: * iR(j) = iL(j + 1) - 1.
231: *
232: * Similarly, rewriting equation (1) as a function of column i,
233: * we can determine, given column i, on which pixel row j is the line
234: * lit:
235: *
236: * dN i + [ dM (N0 + F/2) - dN M0 ] / F
237: * j(i) = ceiling( ------------------------------------ ) - 1
238: * dM
239: *
240: * Floors are easier to compute, so we can rewrite this:
241: *
242: * dN i + [ dM (N0 + F/2) - dN M0 ] / F + dM - 1/F
243: * j(i) = floor( ----------------------------------------------- ) - 1
244: * dM
245: *
246: * dN i + [ dM (N0 + F/2) - dN M0 ] / F + dM - 1/F - dM
247: * = floor( ---------------------------------------------------- )
248: * dM
249: *
250: * dN i + [ dM (N0 + F/2) - dN M0 - 1 ] / F
251: * = floor( ---------------------------------------- )
252: * dM
253: *
254: * We can once again wave our hands and throw away the fractional bits
255: * of the remainder term:
256: *
257: * j(i) = floor( (dN i + gamma) / dM ) (4)
258: *
259: * where
260: *
261: * gamma = floor( [ dM (N0 + F/2) - dN M0 - 1 ] / F ) (5)
262: *
263: * We now note that
264: *
265: * beta = -gamma - 1 = ~gamma (6)
266: *
267: * To draw the pixels of the line, we could evaluate (3) on every scan
268: * line to determine where the strip starts. Of course, we don't want
269: * to do that because that would involve a multiply and divide for every
270: * scan. So we do everything incrementally.
271: *
272: * We would like to easily compute c , the number of pixels on scan j:
273: * j
274: *
275: * c = iL(j + 1) - iL(j)
276: * j
277: *
278: * = floor((dM (j + 1) + beta) / dN) - floor((dM j + beta) / dN) (7)
279: *
280: * This may be rewritten as
281: *
282: * c = floor(i + r / dN) - floor(i + r / dN) (8)
283: * j j+1 j+1 j j
284: *
285: * where i , i are integers and r < dN, r < dN.
286: * j j+1 j j+1
287: *
288: * Rewriting (7) again:
289: *
290: * c = floor(i + r / dN + dM / dN) - floor(i + r / dN)
291: * j j j j j
292: *
293: *
294: * = floor((r + dM) / dN) - floor(r / dN)
295: * j j
296: *
297: * This may be rewritten as
298: *
299: * c = dI + floor((r + dR) / dN) - floor(r / dN)
300: * j j j
301: *
302: * where dI + dR / dN = dM / dN, dI is an integer and dR < dN.
303: *
304: * r is the remainder (or "error") term in the DDA loop: r / dN
305: * j j
306: * is the exact fraction of a pixel at which the strip ends. To go
307: * on to the next scan and compute c we need to know r .
308: * j+1 j+1
309: *
310: * So in the main loop of the DDA:
311: *
312: * c = dI + floor((r + dR) / dN) and r = (r + dR) % dN
313: * j j j+1 j
314: *
315: * and we know r < dN, r < dN, and dR < dN.
316: * j j+1
317: *
318: * We have derived the DDA only for lines in the first octant; to
319: * handle other octants we do the common trick of flipping the line
320: * to the first octant by first making the line left-to-right by
321: * exchanging the end-points, then flipping about the lines y = 0 and
322: * y = x, as necessary. We must record the transformation so we can
323: * undo them later.
324: *
325: * We must also be careful of how the flips affect our rounding. If
326: * to get the line to the first octant we flipped about x = 0, we now
327: * have to be careful to round a y value of 1/2 up instead of down as
328: * we would for a line originally in the first octant (recall that
329: * "In the case where two pels are equidistant, the upper or left
330: * pel is illuminated...").
331: *
332: * To account for this rounding when running the DDA, we shift the line
333: * (or not) in the y direction by the smallest amount possible. That
334: * takes care of rounding for the DDA, but we still have to be careful
335: * about the rounding when determining the first and last pixels to be
336: * lit in the line.
337: *
338: * Determining The First And Last Pixels In The Line
339: * -------------------------------------------------
340: *
341: * Fractional coordinates also make it harder to determine which pixels
342: * will be the first and last ones in the line. We've already taken
343: * the fractional coordinates into account in calculating the DDA, but
344: * the DDA cannot tell us which are the end pixels because it is quite
345: * happy to calculate pixels on the line from minus infinity to positive
346: * infinity.
347: *
348: * The diamond rule determines the start and end pixels. (Recall that
349: * the sides are exclusive except for the left and top vertices.)
350: * This convention can be thought of in another way: there are diamonds
351: * around the pixels, and wherever the true line crosses a diamond,
352: * that pel is illuminated.
353: *
354: * Consider a line where we've done the flips to the first octant, and the
355: * floor of the start coordinates is the origin:
356: *
357: * +-----------------------> +x
358: * |
359: * | 0 1
360: * | 0123456789abcdef
361: * |
362: * | 0 00000000?1111111
363: * | 1 00000000 1111111
364: * | 2 0000000 111111
365: * | 3 000000 11111
366: * | 4 00000 ** 1111
367: * | 5 0000 ****1
368: * | 6 000 1***
369: * | 7 00 1 ****
370: * | 8 ? ***
371: * | 9 22 3 ****
372: * | a 222 33 ***
373: * | b 2222 333 ****
374: * | c 22222 3333 **
375: * | d 222222 33333
376: * | e 2222222 333333
377: * | f 22222222 3333333
378: * |
379: * | 2 3
380: * v
381: * +y
382: *
383: * If the start of the line lands on the diamond around pixel 0 (shown by
384: * the '0' region here), pixel 0 is the first pel in the line. The same
385: * is true for the other pels.
386: *
387: * A little more work has to be done if the line starts in the
388: * 'nether-land' between the diamonds (as illustrated by the '*' line):
389: * the first pel lit is the first diamond crossed by the line (pixel 1 in
390: * our example). This calculation is determined by the DDA or slope of
391: * the line.
392: *
393: * If the line starts exactly half way between two adjacent pixels
394: * (denoted here by the '?' spots), the first pixel is determined by our
395: * round-down convention (and is dependent on the flips done to
396: * normalize the line).
397: *
398: * Last Pel Exclusive
399: * ------------------
400: *
401: * To eliminate repeatedly lit pels between continuous connected lines,
402: * we employ a last-pel exclusive convention: if the line ends exactly on
403: * the diamond around a pel, that pel is not lit. (This eliminates the
404: * checks we had in the old code to see if we were re-lighting pels.)
405: *
406: * The Half Flip
407: * -------------
408: *
409: * To make our run length algorithm more efficient, we employ a "half
410: * flip". If after normalizing to the first octant, the slope is more
411: * than 1/2, we subtract the y coordinate from the x coordinate. This
412: * has the effect of reflecting the coordinates through the line of slope
413: * 1/2. Note that the diagonal gets mapped into the x-axis after a half
414: * flip.
415: *
416: * How Many Bits Do We Need, Anyway?
417: * ---------------------------------
418: *
419: * Note that if the line is visible on your screen, you must light up
420: * exactly the correct pixels, no matter where in the 28.4 x 28.4 device
421: * space the end points of the line lie (meaning you must handle 32 bit
422: * DDAs, you can certainly have optimized cases for lesser DDAs).
423: *
424: * We move the origin to (floor(M0 / F), floor(N0 / F)), so when we
425: * calculate gamma from (5), we know that 0 <= M0, N0 < F. And we
426: * are in the first octant, so dM >= dN. Then we know that gamma can
427: * be in the range [(-1/2)dM, (3/2)dM]. The DDI guarantees us that
428: * valid lines will have dM and dN values at most 31 bits (unsigned)
429: * of significance. So gamma requires 33 bits of significance (we store
430: * this as a 64 bit number for convenience).
431: *
432: * When running through the DDA loop, r + dR can have a value in the
433: * j
434: * range 0 <= r < 2 dN; thus the result must be a 32 bit unsigned value.
435: * j
436: *
437: * Testing Lines
438: * -------------
439: *
440: * To be NT compliant, a display driver must exactly adhere to GIQ,
441: * which means that for any given line, the driver must light exactly
442: * the same pels as does GDI. This can be tested using the Guiman tool
443: * provided elsewhere in the DDK, and 'ZTest', which draws random lines
444: * on the screen and to a bitmap, and compares the results.
445: *
446: * If You've Got Line Hardware
447: * ---------------------------
448: *
449: * If your hardware already adheres to GIQ, you're all set. Otherwise
450: * you'll want to look at the S3 sample code and read the following:
451: *
452: * 1) You'll want to special case integer-only lines, since they require
453: * less processing time and are more common (CAD programs will probably
454: * only ever give integer lines). GDI does not provide a flag saying
455: * that all lines in a path are integer lines; consequently, you will
456: * have to explicitly check every line.
457: *
458: * 2) You are required to correctly draw any line in the 28.4 device
459: * space that intersects the viewport. If you have less than 32 bits
460: * of significance in the hardware for the Bresenham terms, extremely
461: * long lines would overflow the hardware. For such (rare) cases, you
462: * can fall back to strip-drawing code, of which there is a C version in
463: * the S3's lines.cxx (or if your display is a frame buffer, fall back
464: * to the engine).
465: *
466: * 3) If you can explicitly set the Bresenham terms in your hardware, you
467: * can draw non-integer lines using the hardware. If your hardware has
468: * 'n' bits of precision, you can draw GIQ lines that are up to 2^(n-5)
469: * pels long (4 bits are required for the fractional part, and one bit is
470: * used as a sign bit). Note that integer lines don't require the 4
471: * fractional bits, so if you special case them as in 1), you can do
472: * integer lines that are up to 2^(n - 1) pels long. See the S3's
473: * fastline.asm for an example.
474: *
475: \**************************************************************************/
476:
477:
478: BOOL bLines(
479: PPDEV ppdev,
480: POINTFIX* pptfxFirst, // Start of first line
481: POINTFIX* pptfxBuf, // Pointer to buffer of all remaining lines
482: RUN* prun, // Pointer to runs if doing complex clipping
483: ULONG cptfx, // Number of points in pptfxBuf or number of runs
484: // in prun
485: LINESTATE* pls, // Color and style info
486: RECTL* prclClip, // Pointer to clip rectangle if doing simple clipping
487: PFNSTRIP apfn[], // Array of strip functions
488: FLONG flStart) // Flags for each line
489: {
490:
491: ULONG M0;
492: ULONG dM;
493: ULONG N0;
494: ULONG dN;
495: ULONG dN_Original;
496: FLONG fl;
497: LONG x;
498: LONG y;
499: EQUAD eqBeta;
500: EQUAD eqGamma;
501: EQUAD euq;
502: EQUAD eq;
503: ULONG ulDelta;
504:
505: ULONG x0;
506: ULONG y0;
507: ULONG x1;
508: ULONG cStylePels; // Major length of line in pixels for styling
509: ULONG xStart;
510: POINTL ptlStart;
511: STRIP strip;
512: PFNSTRIP pfn;
513: LONG cPels;
514: LONG* plStrip;
515: LONG* plStripEnd;
516: LONG cStripsInNextRun;
517:
518: POINTFIX* pptfxBufEnd = pptfxBuf + cptfx; // Last point in path record
519: STYLEPOS spThis; // Style pos for this line
520:
521:
522: do {
523:
524: /***********************************************************************\
525: * Start the DDA calculations. *
526: \***********************************************************************/
527:
528: M0 = (LONG) pptfxFirst->x;
529: dM = (LONG) pptfxBuf->x;
530:
531: N0 = (LONG) pptfxFirst->y;
532: dN = (LONG) pptfxBuf->y;
533:
534: fl = flStart;
535:
536: // Check for non-clipped, non-styled integer endpoint lines - ECR
537:
538: if ( ( (fl & (FL_CLIP | FL_STYLED)) == 0 ) &&
539: ( ((M0 | dM | N0 | dN) & (F-1)) == 0 ) )
540: {
541: if (bIntegerLine(ppdev, M0, N0, dM, dN))
542: {
543: goto Next_Line;
544: }
545: }
546:
547: if ((LONG) M0 > (LONG) dM)
548: {
549: // Ensure that we run left-to-right:
550:
551: register ULONG ulTmp;
552: SWAPL(M0, dM, ulTmp);
553: SWAPL(N0, dN, ulTmp);
554: fl |= FL_FLIP_H;
555: }
556:
557: // Compute the deltas:
558:
559: dM -= M0;
560: dN -= N0;
561:
562: // We now have a line running left-to-right from (M0, N0) to
563: // (M0 + dM, N0 + dN):
564:
565: if ((LONG) dN < 0)
566: {
567: // Line runs from bottom to top, so flip across y = 0:
568:
569: N0 = -(LONG) N0;
570: dN = -(LONG) dN;
571: fl |= FL_FLIP_V;
572: }
573:
574: if (dN >= dM)
575: {
576: if (dN == dM)
577: {
578: // Have to special case slopes of one:
579:
580: fl |= FL_FLIP_SLOPE_ONE;
581: }
582: else
583: {
584: // Since line has slope greater than 1, flip across x = y:
585:
586: register ULONG ulTmp;
587: SWAPL(dM, dN, ulTmp);
588: SWAPL(M0, N0, ulTmp);
589: fl |= FL_FLIP_D;
590: }
591: }
592:
593: fl |= gaflRound[(fl & FL_ROUND_MASK) >> FL_ROUND_SHIFT];
594:
595: x = LFLOOR((LONG) M0);
596: y = LFLOOR((LONG) N0);
597:
598: M0 = FXFRAC(M0);
599: N0 = FXFRAC(N0);
600:
601: // Calculate the remainder term [ dM * (N0 + F/2) - M0 * dN ]:
602:
603: {
604:
605: eqGamma.vImulInit(dM, N0 + F/2);
606: eq.vImulInit(M0, dN);
607:
608: eqGamma -= eq;
609:
610: if (fl & FL_V_ROUND_DOWN)
611: eqGamma -= 1L; // Adjust so y = 1/2 rounds down
612:
613: eqGamma >>= FLOG2;
614:
615: eqBeta.HighPart = ~eqGamma.HighPart;
616: eqBeta.LowPart = ~eqGamma.LowPart;
617:
618: }
619:
620:
621: /***********************************************************************\
622: * Figure out which pixels are at the ends of the line. *
623: \***********************************************************************/
624:
625: // The toughest part of GIQ is determining the start and end pels.
626: //
627: // Our approach here is to calculate x0 and x1 (the inclusive start
628: // and end columns of the line respectively, relative to our normalized
629: // origin). Then x1 - x0 + 1 is the number of pels in the line. The
630: // start point is easily calculated by plugging x0 into our line equation
631: // (which takes care of whether y = 1/2 rounds up or down in value)
632: // getting y0, and then undoing the normalizing flips to get back
633: // into device space.
634: //
635: // We look at the fractional parts of the coordinates of the start and
636: // end points, and call them (M0, N0) and (M1, N1) respectively, where
637: // 0 <= M0, N0, M1, N1 < 16. We plot (M0, N0) on the following grid
638: // to determine x0:
639: //
640: // +-----------------------> +x
641: // |
642: // | 0 1
643: // | 0123456789abcdef
644: // |
645: // | 0 ........?xxxxxxx
646: // | 1 ..........xxxxxx
647: // | 2 ...........xxxxx
648: // | 3 ............xxxx
649: // | 4 .............xxx
650: // | 5 ..............xx
651: // | 6 ...............x
652: // | 7 ................
653: // | 8 ................
654: // | 9 ......**........
655: // | a ........****...x
656: // | b ............****
657: // | c .............xxx****
658: // | d ............xxxx ****
659: // | e ...........xxxxx ****
660: // | f ..........xxxxxx
661: // |
662: // | 2 3
663: // v
664: //
665: // +y
666: //
667: // This grid accounts for the appropriate rounding of GIQ and last-pel
668: // exclusion. If (M0, N0) lands on an 'x', x0 = 2. If (M0, N0) lands
669: // on a '.', x0 = 1. If (M0, N0) lands on a '?', x0 rounds up or down,
670: // depending on what flips have been done to normalize the line.
671: //
672: // For the end point, if (M1, N1) lands on an 'x', x1 =
673: // floor((M0 + dM) / 16) + 1. If (M1, N1) lands on a '.', x1 =
674: // floor((M0 + dM)). If (M1, N1) lands on a '?', x1 rounds up or down,
675: // depending on what flips have been done to normalize the line.
676: //
677: // Lines of exactly slope one require a special case for both the start
678: // and end. For example, if the line ends such that (M1, N1) is (9, 1),
679: // the line has gone exactly through (8, 0) -- which may be considered
680: // to be part of 'x' because of rounding! So slopes of exactly slope
681: // one going through (8, 0) must also be considered as belonging in 'x'.
682: //
683: // For lines that go left-to-right, we have the following grid:
684: //
685: // +-----------------------> +x
686: // |
687: // | 0 1
688: // | 0123456789abcdef
689: // |
690: // | 0 xxxxxxxx?.......
691: // | 1 xxxxxxx.........
692: // | 2 xxxxxx..........
693: // | 3 xxxxx...........
694: // | 4 xxxx............
695: // | 5 xxx.............
696: // | 6 xx..............
697: // | 7 x...............
698: // | 8 x...............
699: // | 9 x.....**........
700: // | a xx......****....
701: // | b xxx.........****
702: // | c xxxx............****
703: // | d xxxxx........... ****
704: // | e xxxxxx.......... ****
705: // | f xxxxxxx.........
706: // |
707: // | 2 3
708: // v
709: //
710: // +y
711: //
712: // This grid accounts for the appropriate rounding of GIQ and last-pel
713: // exclusion. If (M0, N0) lands on an 'x', x0 = 0. If (M0, N0) lands
714: // on a '.', x0 = 1. If (M0, N0) lands on a '?', x0 rounds up or down,
715: // depending on what flips have been done to normalize the line.
716: //
717: // For the end point, if (M1, N1) lands on an 'x', x1 =
718: // floor((M0 + dM) / 16) - 1. If (M1, N1) lands on a '.', x1 =
719: // floor((M0 + dM)). If (M1, N1) lands on a '?', x1 rounds up or down,
720: // depending on what flips have been done to normalize the line.
721: //
722: // Lines of exactly slope one must be handled similarly to the right-to-
723: // left case.
724:
725: {
726:
727: // Calculate x0, x1
728:
729: ULONG N1 = FXFRAC(N0 + dN);
730: ULONG M1 = FXFRAC(M0 + dM);
731:
732: x1 = LFLOOR(M0 + dM);
733:
734: if (fl & FL_FLIP_H)
735: {
736: // ---------------------------------------------------------------
737: // Line runs right-to-left: <----
738:
739: // Compute x1:
740:
741: if (N1 == 0)
742: {
743: if (LROUND(M1, fl & FL_H_ROUND_DOWN))
744: {
745: x1++;
746: }
747: }
748: else if (ABS((LONG) (N1 - F/2)) + M1 > F)
749: {
750: x1++;
751: }
752:
753: if ((fl & (FL_FLIP_SLOPE_ONE | FL_H_ROUND_DOWN))
754: == (FL_FLIP_SLOPE_ONE))
755: {
756: // Have to special-case diagonal lines going through our
757: // the point exactly equidistant between two horizontal
758: // pixels, if we're supposed to round x=1/2 down:
759:
760: if ((N1 > 0) && (M1 == N1 + 8))
761: x1++;
762:
763: // Don't you love special cases? Is this a rhetorical question?
764:
765: if ((M0 > 0) && (N0 == M0 + 8))
766: {
767: x0 = 2;
768: ulDelta = dN;
769: goto right_to_left_compute_y0;
770: }
771: }
772:
773: // Compute x0:
774:
775: x0 = 1;
776: ulDelta = 0;
777: if (N0 == 0)
778: {
779: if (LROUND(M0, fl & FL_H_ROUND_DOWN))
780: {
781: x0 = 2;
782: ulDelta = dN;
783: }
784: }
785: else if (ABS((LONG) (N0 - F/2)) + M0 > F)
786: {
787: x0 = 2;
788: ulDelta = dN;
789: }
790:
791: // Compute y0:
792:
793: right_to_left_compute_y0:
794:
795: y0 = 0;
796: eq = eqGamma;
797: eq += ulDelta;
798: if (eq.lHigh() >= 0)
799: {
800: if (eq.lHigh() > 0 || eq.ulLow() >= 2 * dM - dN)
801: y0 = 2;
802: else if (eq.ulLow() >= dM - dN)
803: y0 = 1;
804: }
805: }
806: else
807: {
808: // ---------------------------------------------------------------
809: // Line runs left-to-right: ---->
810:
811: // Compute x1:
812:
813: x1--;
814:
815: if (M1 > 0)
816: {
817: if (N1 == 0)
818: {
819: if (LROUND(M1, fl & FL_H_ROUND_DOWN))
820: x1++;
821: }
822: else if (ABS((LONG) (N1 - F/2)) <= (LONG) M1)
823: {
824: x1++;
825: }
826: }
827:
828: if ((fl & (FL_FLIP_SLOPE_ONE | FL_H_ROUND_DOWN))
829: == (FL_FLIP_SLOPE_ONE | FL_H_ROUND_DOWN))
830: {
831: // Have to special-case diagonal lines going through our
832: // the point exactly equidistant between two horizontal
833: // pixels, if we're supposed to round x=1/2 down:
834:
835: if ((N1 > 0) && (M1 == N1 + 8))
836: x1--;
837:
838: if ((M0 > 0) && (N0 == M0 + 8))
839: {
840: x0 = 0;
841: goto left_to_right_compute_y0;
842: }
843: }
844:
845: // Compute x0:
846:
847: x0 = 0;
848: if (M0 > 0)
849: {
850: if (N0 == 0)
851: {
852: if (LROUND(M0, fl & FL_H_ROUND_DOWN))
853: x0 = 1;
854: }
855: else if (ABS((LONG) (N0 - F/2)) <= (LONG) M0)
856: {
857: x0 = 1;
858: }
859: }
860:
861: // Compute y0:
862:
863: left_to_right_compute_y0:
864:
865: y0 = 0;
866: if (eqGamma.lHigh() >= 0 &&
867: eqGamma.ulLow() >= dM - (dN & (-(LONG) x0)))
868: {
869: y0 = 1;
870: }
871: }
872: }
873:
874: cStylePels = x1 - x0 + 1;
875: if ((LONG) cStylePels <= 0)
876: goto Next_Line;
877:
878: xStart = x0;
879:
880: /***********************************************************************\
881: * Complex clipping. *
882: \***********************************************************************/
883: #ifdef SIMPLE_CLIP
884: if (fl & FL_COMPLEX_CLIP)
885: #else
886: if (fl & FL_CLIP)
887: #endif // SIMPLE_CLIP
888: {
889: dN_Original = dN;
890:
891: Continue_Complex_Clipping:
892:
893: if (fl & FL_FLIP_H)
894: {
895: // Line runs right-to-left <-----
896:
897: x0 = xStart + cStylePels - prun->iStop - 1;
898: x1 = xStart + cStylePels - prun->iStart - 1;
899: }
900: else
901: {
902: // Line runs left-to-right ----->
903:
904: x0 = xStart + prun->iStart;
905: x1 = xStart + prun->iStop;
906: }
907:
908: prun++;
909:
910: // Reset some variables we'll nuke a little later:
911:
912: dN = dN_Original;
913: pls->spNext = pls->spComplex;
914:
915: // No overflow since large integer math is used
916:
917: euq.vMulInit(x0, dN);
918: euq += eqGamma;
919:
920: y0 = euq.ulDiv(dM);
921:
922: ASSERTS3((LONG) y0 >= 0, "y0 weird: Goofed up end pel calc?");
923: }
924:
925: /////////////////////////////////////////////////////////////////////////
926: // The following clip code works great -- we simply aren't using it yet.
927: /////////////////////////////////////////////////////////////////////////
928:
929: #ifdef SIMPLE_CLIP
930: /***********************************************************************\
931: * Simple rectangular clipping. *
932: \***********************************************************************/
933:
934: if (fl & FL_SIMPLE_CLIP)
935: {
936: ULONG y1;
937: LONG xRight;
938: LONG xLeft;
939: LONG yBottom;
940: LONG yTop;
941:
942: // Note that y0 and y1 are actually the lower and upper bounds,
943: // respectively, of the y coordinates of the line (the line may
944: // have actually shrunk due to first/last pel clipping).
945: //
946: // Also note that x0, y0 are not necessarily zero.
947:
948: RECTL* prcl = &prclClip[(fl & FL_RECTLCLIP_MASK) >>
949: FL_RECTLCLIP_SHIFT];
950:
951: // Normalize to the same point we've normalized for the DDA
952: // calculations:
953:
954: xRight = prcl->right - x;
955: xLeft = prcl->left - x;
956: yBottom = prcl->bottom - y;
957: yTop = prcl->top - y;
958:
959: if (yBottom <= (LONG) y0 ||
960: xRight <= (LONG) x0 ||
961: xLeft > (LONG) x1)
962: {
963: Totally_Clipped:
964:
965: if (fl & FL_STYLED)
966: {
967: pls->spNext += cStylePels;
968: if (pls->spNext >= pls->spTotal2)
969: pls->spNext %= pls->spTotal2;
970: }
971:
972: goto Next_Line;
973: }
974:
975: if ((LONG) x1 >= xRight)
976: x1 = xRight - 1;
977:
978: // We have to know the correct y1, which we haven't bothered to
979: // calculate up until now. This multiply and divide is quite
980: // expensive; we could replace it with code similar to that which
981: // we used for computing y0.
982: //
983: // The reason why we need the actual value, and not an upper
984: // bounds guess like y1 = LFLOOR(dM) + 2 is that we have to be
985: // careful when calculating x(y) that y0 <= y <= y1, otherwise
986: // we can overflow on the divide (which, needless to say, is very
987: // bad).
988:
989: euq.vMulInit(x1, dN);
990: euq += eqGamma;
991: y1 = euq.ulDiv(dM);
992:
993: if (yTop > (LONG) y1)
994: goto Totally_Clipped;
995:
996: if (yBottom <= (LONG) y1)
997: {
998: y1 = yBottom;
999:
1000: euq.vMulInit(y1, dM);
1001: euq += eqBeta;
1002: x1 = euq.ulDiv(dN);
1003: }
1004:
1005: // At this point, we've taken care of calculating the intercepts
1006: // with the right and bottom edges. Now we work on the left and
1007: // top edges:
1008:
1009: if (xLeft > (LONG) x0)
1010: {
1011: x0 = xLeft;
1012:
1013: euq.vMulInit(x0, dN);
1014: euq += eqGamma;
1015: y0 = euq.ulDiv(dM);
1016:
1017: if (yBottom <= (LONG) y0)
1018: goto Totally_Clipped;
1019: }
1020:
1021: if (yTop > (LONG) y0)
1022: {
1023: y0 = yTop;
1024:
1025: euq.vMulInit(y0, dM);
1026: euq += eqBeta;
1027: x0 = euq.ulDiv(dN) + 1;
1028:
1029: if (xRight <= (LONG) x0)
1030: goto Totally_Clipped;
1031: }
1032:
1033: ASSERTS3(x0 <= x1, "Improper rectangle clip");
1034: }
1035: #endif // SIMPLE_CLIP
1036:
1037: /***********************************************************************\
1038: * Done clipping. Unflip if necessary. *
1039: \***********************************************************************/
1040:
1041: ptlStart.x = x + x0;
1042: ptlStart.y = y + y0;
1043:
1044: if (fl & FL_FLIP_D)
1045: {
1046: register LONG lTmp;
1047: SWAPL(ptlStart.x, ptlStart.y, lTmp);
1048: }
1049:
1050:
1051: if (fl & FL_FLIP_V)
1052: {
1053: ptlStart.y = -ptlStart.y;
1054: }
1055:
1056: cPels = x1 - x0 + 1;
1057:
1058: /***********************************************************************\
1059: * Style calculations. *
1060: \***********************************************************************/
1061:
1062: if (fl & FL_STYLED)
1063: {
1064: STYLEPOS sp;
1065:
1066: spThis = pls->spNext;
1067: pls->spNext += cStylePels;
1068:
1069: #ifdef ALTERNATESTYLED
1070: if (fl & FL_ALTERNATESTYLED)
1071: {
1072: pls->spNext &= 1;
1073: if (fl & FL_FLIP_H)
1074: {
1075: sp = pls->spNext - x0 + xStart + 1;
1076: }
1077: else
1078: {
1079: sp = spThis + x0 - xStart;
1080: }
1081: pls->ulStyleMask = (BYTE) (0x55555555L >>
1082: (ptlStart.x & 0x7) + (sp & 1));
1083:
1084: pls->spRemaining = 1;
1085: }
1086: else
1087: #endif // ALTERNATESTYLED
1088:
1089: {
1090: if (pls->spNext >= pls->spTotal2)
1091: pls->spNext %= pls->spTotal2;
1092:
1093:
1094: if (fl & FL_FLIP_H)
1095: sp = pls->spNext - x0 + xStart;
1096: else
1097: sp = spThis + x0 - xStart;
1098: #ifdef MASKSTYLED
1099: if (fl & FL_MASKSTYLED)
1100: {
1101: ULONG cShifts;
1102: ULONG cRemainder;
1103: ULONG ulStyleMask;
1104:
1105: if (fl & FL_FLIP_H)
1106: {
1107: cShifts = (sp + 2) / STYLE_DENSITY;
1108: cRemainder = (sp + 2) % STYLE_DENSITY;
1109: cShifts &= 7L;
1110: ulStyleMask = (pls->ulStyleMaskRtoL >> cShifts);
1111: pls->spRemaining = cRemainder + 1;
1112: }
1113: else
1114: {
1115: cRemainder = sp % STYLE_DENSITY;
1116: cShifts = sp / STYLE_DENSITY;
1117: cShifts &= 7L;
1118: ulStyleMask = (pls->ulStyleMaskLtoR >>
1119: (8 - cShifts));
1120: pls->spRemaining = STYLE_DENSITY - cRemainder;
1121: }
1122:
1123: pls->ulStyleMask = (BYTE) (ulStyleMask >>
1124: (ptlStart.x & 0x7));
1125: }
1126: else
1127: #endif // MASKSTYLED
1128: {
1129: ASSERTS3(fl & FL_ARBITRARYSTYLED, "Oops");
1130:
1131: // Normalize our target style position:
1132:
1133: if ((sp < 0) || (sp >= pls->spTotal2))
1134: {
1135: sp %= pls->spTotal2;
1136:
1137: // The modulus of a negative number is not well-defined
1138: // in C -- if it's negative we'll adjust it so that it's
1139: // back in the range [0, spTotal2):
1140:
1141: if (sp < 0)
1142: sp += pls->spTotal2;
1143: }
1144:
1145: // Since we always draw the line left-to-right, but styling is
1146: // always done in the direction of the original line, we have
1147: // to figure out where we are in the style array for the left
1148: // edge of this line.
1149:
1150: if (fl & FL_FLIP_H)
1151: {
1152: // Line originally ran right-to-left:
1153:
1154: sp = -sp;
1155: if (sp < 0)
1156: sp += pls->spTotal2;
1157:
1158: pls->ulStyleMask = ~pls->ulStartMask;
1159: pls->pspStart = &pls->aspRtoL[0];
1160: pls->pspEnd = &pls->aspRtoL[pls->cStyle - 1];
1161: }
1162: else
1163: {
1164: // Line originally ran left-to-right:
1165:
1166: pls->ulStyleMask = pls->ulStartMask;
1167: pls->pspStart = &pls->aspLtoR[0];
1168: pls->pspEnd = &pls->aspLtoR[pls->cStyle - 1];
1169: }
1170:
1171: if (sp >= pls->spTotal)
1172: {
1173: sp -= pls->spTotal;
1174: if (pls->cStyle & 1)
1175: pls->ulStyleMask = ~pls->ulStyleMask;
1176: }
1177:
1178: pls->psp = pls->pspStart;
1179: while (sp >= *pls->psp)
1180: sp -= *pls->psp++;
1181:
1182: ASSERTS3(pls->psp <= pls->pspEnd,
1183: "Flew off into NeverNeverLand");
1184:
1185: pls->spRemaining = *pls->psp - sp;
1186: if ((pls->psp - pls->pspStart) & 1)
1187: pls->ulStyleMask = ~pls->ulStyleMask;
1188: }
1189: }
1190: }
1191:
1192: plStrip = &strip.alStrips[0];
1193: plStripEnd = &strip.alStrips[STRIP_MAX]; // Is exclusive
1194: cStripsInNextRun = 0x7fffffff;
1195:
1196: strip.ptlStart = ptlStart;
1197:
1198: if (2 * dN > dM &&
1199: !(fl & FL_STYLED) && // !!! Remove this! [andrewgo]
1200: !(fl & FL_DONT_DO_HALF_FLIP))
1201: {
1202: // Do a half flip! Remember that we may doing this on the
1203: // same line multiple times for complex clipping (meaning the
1204: // affected variables should be reset for every clip run):
1205:
1206: fl |= FL_FLIP_HALF;
1207:
1208: eqBeta = eqGamma;
1209: eqBeta -= dM;
1210:
1211: dN = dM - dN;
1212: y0 = x0 - y0; // Note this may overflow, but that's okay
1213: }
1214:
1215: // Now, run the DDA starting at (ptlStart.x, ptlStart.y)!
1216:
1217: strip.flFlips = fl;
1218: pfn = apfn[(fl & FL_STRIP_MASK) >> FL_STRIP_SHIFT];
1219:
1220: // Now calculate the DDA variables needed to figure out how many pixels
1221: // go in the very first strip:
1222:
1223: {
1224: register LONG i;
1225: register ULONG r;
1226: register ULONG dI;
1227: register ULONG dR;
1228:
1229: if (dN == 0)
1230: i = 0x7fffffff;
1231: else
1232: {
1233: euq.vMulInit(y0 + 1, dM);
1234: euq += eqBeta;
1235:
1236: #ifdef FIREWALLS
1237: if (euq.bNegative())
1238: {
1239: RIP("Oops!");
1240: }
1241: #endif
1242:
1243: i = euq.ulDiv(dN, &r) - x0 + 1;
1244:
1245: dI = dM / dN;
1246: dR = dM % dN; // 0 <= dR < dN
1247:
1248: ASSERTS3(dI > 0, "Weird dI");
1249: }
1250:
1251: ASSERTS3(i > 0 && i <= 0x7fffffff, "Weird initial strip length");
1252: ASSERTS3(cPels > 0, "Zero pel line");
1253:
1254: /***********************************************************************\
1255: * Run the DDA! *
1256: \***********************************************************************/
1257:
1258: while(TRUE)
1259: {
1260: cPels -= i;
1261: if (cPels <= 0)
1262: break;
1263:
1264: *plStrip++ = i;
1265:
1266: if (plStrip == plStripEnd)
1267: {
1268: strip.cStrips = plStrip - &strip.alStrips[0];
1269: (*pfn)(ppdev, &strip, pls);
1270: plStrip = &strip.alStrips[0];
1271: }
1272:
1273: i = dI;
1274: r += dR;
1275:
1276: if (r >= dN)
1277: {
1278: r -= dN;
1279: i++;
1280: }
1281: }
1282:
1283: *plStrip++ = cPels + i;
1284:
1285: strip.cStrips = plStrip - &strip.alStrips[0];
1286: (*pfn)(ppdev, &strip, pls);
1287:
1288:
1289: }
1290:
1291: Next_Line:
1292:
1293: if (fl & FL_COMPLEX_CLIP)
1294: {
1295: cptfx--;
1296: if (cptfx != 0)
1297: goto Continue_Complex_Clipping;
1298:
1299: break;
1300: }
1301: else
1302: {
1303: pptfxFirst = pptfxBuf;
1304: pptfxBuf++;
1305: }
1306:
1307: } while (pptfxBuf < pptfxBufEnd);
1308:
1309: return(TRUE);
1310:
1311: }
1312:
1313: #ifdef HARDWAREGIQ
1314:
1315: /////////////////////////////////////////////////////////////////////////
1316: // The following GIQ code works great -- we simply aren't using it yet.
1317: /////////////////////////////////////////////////////////////////////////
1318:
1319: typedef struct _DDALINE /* dl */
1320: {
1321: LONG iDir;
1322: POINTL ptlStart;
1323: LONG cPels;
1324: LONG dMajor;
1325: LONG dMinor;
1326: LONG lErrorTerm;
1327: } DDALINE;
1328:
1329: #define HW_FLIP_D 0x0001L // Diagonal flip
1330: #define HW_FLIP_V 0x0002L // Vertical flip
1331: #define HW_FLIP_H 0x0004L // Horizontal flip
1332: #define HW_FLIP_SLOPE_ONE 0x0008L // Normalized line has exactly slope one
1333: #define HW_FLIP_MASK (HW_FLIP_D | HW_FLIP_V | HW_FLIP_H)
1334:
1335: #define HW_X_ROUND_DOWN 0x0100L // x = 1/2 rounds down in value
1336: #define HW_Y_ROUND_DOWN 0x0200L // y = 1/2 rounds down in value
1337:
1338: LONG gaiDir[] = { 0, 1, 7, 6, 3, 2, 4, 5 };
1339:
1340: FLONG gaflHardwareRound[] = {
1341: HW_X_ROUND_DOWN | HW_Y_ROUND_DOWN, // | | |
1342: HW_X_ROUND_DOWN | HW_Y_ROUND_DOWN, // | | | FLIP_D
1343: HW_X_ROUND_DOWN, // | | FLIP_V |
1344: HW_Y_ROUND_DOWN, // | | FLIP_V | FLIP_D
1345: HW_Y_ROUND_DOWN, // | FLIP_H | |
1346: HW_X_ROUND_DOWN, // | FLIP_H | | FLIP_D
1347: 0, // | FLIP_H | FLIP_V |
1348: 0, // | FLIP_H | FLIP_V | FLIP_D
1349: HW_Y_ROUND_DOWN, // SLOPE_ONE | | |
1350: 0xffffffff, // SLOPE_ONE | | | FLIP_D
1351: HW_X_ROUND_DOWN, // SLOPE_ONE | | FLIP_V |
1352: 0xffffffff, // SLOPE_ONE | | FLIP_V | FLIP_D
1353: HW_Y_ROUND_DOWN, // SLOPE_ONE | FLIP_H | |
1354: 0xffffffff, // SLOPE_ONE | FLIP_H | | FLIP_D
1355: HW_X_ROUND_DOWN, // SLOPE_ONE | FLIP_H | FLIP_V |
1356: 0xffffffff // SLOPE_ONE | FLIP_H | FLIP_V | FLIP_D
1357: };
1358:
1359: /******************************Public*Routine******************************\
1360: * BOOL bHardwareLine(pptfxStart, pptfxEnd, cBits, pdl)
1361: *
1362: * This routine is useful for folks who have line drawing hardware where
1363: * they can explicitly set the Bresenham terms -- they can use this routine
1364: * to draw fractional coordinate GIQ lines with the hardware.
1365: *
1366: * Fractional coordinate lines require an extra 4 bits of precision in the
1367: * Bresenham terms. For example, if your hardware has 13 bits of precision
1368: * for the terms, you can only draw GIQ lines up to 255 pels long using this
1369: * routine.
1370: *
1371: * Input:
1372: * pptfxStart - Points to GIQ coordinate of start of line
1373: * pptfxEnd - Points to GIQ coordinate of end of line
1374: * cBits - The number of bits of precision your hardware can support.
1375: *
1376: * Output:
1377: * returns - TRUE if the line can be drawn directly using the line
1378: * hardware (in which case pdl contains the Bresenham terms
1379: * for drawing the line).
1380: * FALSE if the line is too long, and the strips code must be
1381: * used.
1382: * pdl - Returns the Bresenham line terms for drawing the line.
1383: *
1384: * DDALINE:
1385: * iDir - Direction of the line, as an octant numbered as follows:
1386: *
1387: * \ 5 | 6 /
1388: * \ | /
1389: * 4 \ | / 7
1390: * \ /
1391: * -----+-----
1392: * /|\
1393: * 3 / | \ 0
1394: * / | \
1395: * / 2 | 1 \
1396: *
1397: * ptlStart - Start pixel of line.
1398: * cPels - # of pels in line. *NOTE* You must check if this is <= 0!
1399: * dMajor - Major axis delta.
1400: * dMinor - Minor axis delta.
1401: * lErrorTerm - Error term.
1402: *
1403: * What you do with the last 3 terms may be a little tricky. They are
1404: * actually the terms for the formula of the normalized line
1405: *
1406: * dMinor * x + (lErrorTerm + dMajor)
1407: * y(x) = floor( ---------------------------------- )
1408: * dMajor
1409: *
1410: * where y(x) is the y coordinate of the pixel to be lit as a function of
1411: * the x-coordinate.
1412: *
1413: * Every time the line advances one in the major direction 'x', dMinor
1414: * gets added to the current error term. If the resulting value is >= 0,
1415: * we know we have to move one pixel in the minor direction 'y', and
1416: * dMajor must be subtracted from the current error term.
1417: *
1418: * If you're trying to figure out what this means for your hardware, you can
1419: * think of the DDALINE terms as having been computed equivalently as
1420: * follows:
1421: *
1422: * pdl->dMinor = 2 * (minor axis delta)
1423: * pdl->dMajor = 2 * (major axis delta)
1424: * pdl->lErrorTerm = - (major axis delta) - fixup
1425: *
1426: * That is, if your documentation tells you that for integer lines, a
1427: * register is supposed to be initialized with the value
1428: * '2 * (minor axis delta)', you'll actually use pdl->dMinor.
1429: *
1430: * Example: Setting up the 8514
1431: *
1432: * AXSTPSIGN is supposed to be the axial step constant register, defined
1433: * as 2 * (minor axis delta). You set:
1434: *
1435: * AXSTPSIGN = pdl->dMinor
1436: *
1437: * DGSTPSIGN is supposed to be the diagonal step constant register,
1438: * defined as 2 * (minor axis delta) - 2 * (major axis delta). You set:
1439: *
1440: * DGSTPSIGN = pdl->dMinor - pdl->dMajor
1441: *
1442: * ERR_TERM is supposed to be the adjusted error term, defined as
1443: * 2 * (minor axis delta) - (major axis delta) - fixup. You set:
1444: *
1445: * ERR_TERM = pdl->lErrorTerm + pdl->dMinor
1446: *
1447: * Implementation:
1448: *
1449: * You'll want to special case integer lines before calling this routine
1450: * (since they're very common, take less time to the computation of line
1451: * terms, and can handle longer lines than this routine because 4 bits
1452: * aren't being given to the fraction).
1453: *
1454: * If a GIQ line is too long to be handled by this routine, you can just
1455: * use the slower strip routines for that line. Note that you cannot
1456: * just fail the call -- you must be able to accurately draw any line
1457: * in the 28.4 device space when it intersects the viewport.
1458: *
1459: * Testing:
1460: *
1461: * Use Guiman, or some other test that draws random fractional coordinate
1462: * lines and compares them to what GDI itself draws to a bitmap.
1463: *
1464: \**************************************************************************/
1465:
1466: BOOL bHardwareLine(
1467: POINTFIX* pptfxStart, // Start of line
1468: POINTFIX* pptfxEnd, // End of line
1469: LONG cBits, // # bits precision in hardware Bresenham terms
1470: DDALINE* pdl) // Returns Bresenham terms for doing line
1471: {
1472: FLONG fl; // Various flags
1473: ULONG M0; // Normalized fractional unit x start coordinate (0 <= M0 < F)
1474: ULONG N0; // Normalized fractional unit y start coordinate (0 <= N0 < F)
1475: ULONG M1; // Normalized fractional unit x end coordinate (0 <= M1 < F)
1476: ULONG N1; // Normalized fractional unit x end coordinate (0 <= N1 < F)
1477: ULONG dM; // Normalized fractional unit x-delta (0 <= dM)
1478: ULONG dN; // Normalized fractional unit y-delta (0 <= dN <= dM)
1479: LONG x; // Normalized x coordinate of origin
1480: LONG y; // Normalized y coordinate of origin
1481: LONG x0; // Normalized x offset from origin to start pixel (inclusive)
1482: LONG y0; // Normalized y offset from origin to start pixel (inclusive)
1483: LONG x1; // Normalized x offset from origin to end pixel (inclusive)
1484: LONG lGamma;// Bresenham error term at origin
1485:
1486: /***********************************************************************\
1487: * Normalize line to the first octant.
1488: \***********************************************************************/
1489:
1490: fl = 0;
1491:
1492: M0 = pptfxStart->x;
1493: dM = pptfxEnd->x;
1494:
1495: if ((LONG) dM < (LONG) M0)
1496: {
1497: // Line runs from right to left, so flip across x = 0:
1498:
1499: M0 = -(LONG) M0;
1500: dM = -(LONG) dM;
1501: fl |= HW_FLIP_H;
1502: }
1503:
1504: // Compute the delta. The DDI says we can never have a valid delta
1505: // with a magnitude more than 2^31 - 1, but the engine never actually
1506: // checks its transforms. To ensure that we'll never puke on our shoes,
1507: // we check for that case and simply refuse to draw the line:
1508:
1509: dM -= M0;
1510: if ((LONG) dM < 0)
1511: return(FALSE);
1512:
1513: N0 = pptfxStart->y;
1514: dN = pptfxEnd->y;
1515:
1516: if ((LONG) dN < (LONG) N0)
1517: {
1518: // Line runs from bottom to top, so flip across y = 0:
1519:
1520: N0 = -(LONG) N0;
1521: dN = -(LONG) dN;
1522: fl |= HW_FLIP_V;
1523: }
1524:
1525: // Compute another delta:
1526:
1527: dN -= N0;
1528: if ((LONG) dN < 0)
1529: return(FALSE);
1530:
1531: if (dN >= dM)
1532: {
1533: if (dN == dM)
1534: {
1535: // Have to special case slopes of one:
1536:
1537: fl |= HW_FLIP_SLOPE_ONE;
1538: }
1539: else
1540: {
1541: // Since line has slope greater than 1, flip across x = y:
1542:
1543: register ULONG ulTmp;
1544: ulTmp = dM; dM = dN; dN = ulTmp;
1545: ulTmp = M0; M0 = N0; N0 = ulTmp;
1546: fl |= HW_FLIP_D;
1547: }
1548: }
1549:
1550: // Figure out if we can do the line in hardware, given that we have a
1551: // limited number of bits of precision for the Bresenham terms.
1552: //
1553: // Remember that one bit has to be kept as a sign bit:
1554:
1555: if ((LONG) dM >= (1L << (cBits - 1)))
1556: return(FALSE);
1557:
1558: fl |= gaflHardwareRound[fl];
1559:
1560: /***********************************************************************\
1561: * Calculate the error term at pixel 0.
1562: \***********************************************************************/
1563:
1564: x = LFLOOR((LONG) M0);
1565: y = LFLOOR((LONG) N0);
1566:
1567: M0 = FXFRAC(M0);
1568: N0 = FXFRAC(N0);
1569:
1570: // NOTE NOTE NOTE: If this routine were to handle any line in the 28.4
1571: // space, it will overflow its math (the following part requires 36 bits
1572: // of precision)! But we get here for lines that the hardware can handle
1573: // (see the expression (dM >= (1L << (cBits - 1))) above?), so if cBits
1574: // is less than 28, we're safe.
1575: //
1576: // If you're going to use this routine to handle all lines in the 28.4
1577: // device space, you will HAVE to make sure the math doesn't overflow,
1578: // otherwise you won't be NT compliant! (See lines.cxx for an example
1579: // how to do that. You don't have to worry about this if you simply
1580: // default to the strips code for long lines, because those routines
1581: // already do the math correctly.)
1582:
1583: // Calculate the remainder term [ dM * (N0 + F/2) - M0 * dN ]. Note
1584: // that M0 and N0 have at most 4 bits of significance (and if the
1585: // arguments are properly ordered, on a 486 each multiply would be no
1586: // more than 13 cycles):
1587:
1588: lGamma = (N0 + F/2) * dM - M0 * dN;
1589:
1590: if (fl & HW_Y_ROUND_DOWN)
1591: lGamma--;
1592:
1593: lGamma >>= FLOG2;
1594:
1595: /***********************************************************************\
1596: * Figure out which pixels are at the ends of the line.
1597: \***********************************************************************/
1598:
1599: // The toughest part of GIQ is determining the start and end pels.
1600: //
1601: // Our approach here is to calculate x0 and x1 (the inclusive start
1602: // and end columns of the line respectively, relative to our normalized
1603: // origin). Then x1 - x0 + 1 is the number of pels in the line. The
1604: // start point is easily calculated by plugging x0 into our line equation
1605: // (which takes care of whether y = 1/2 rounds up or down in value)
1606: // getting y0, and then undoing the normalizing flips to get back
1607: // into device space.
1608: //
1609: // We look at the fractional parts of the coordinates of the start and
1610: // end points, and call them (M0, N0) and (M1, N1) respectively, where
1611: // 0 <= M0, N0, M1, N1 < 16. We plot (M0, N0) on the following grid
1612: // to determine x0:
1613: //
1614: // +-----------------------> +x
1615: // |
1616: // | 0 1
1617: // | 0123456789abcdef
1618: // |
1619: // | 0 ........?xxxxxxx
1620: // | 1 ..........xxxxxx
1621: // | 2 ...........xxxxx
1622: // | 3 ............xxxx
1623: // | 4 .............xxx
1624: // | 5 ..............xx
1625: // | 6 ...............x
1626: // | 7 ................
1627: // | 8 ................
1628: // | 9 ......**........
1629: // | a ........****...x
1630: // | b ............****
1631: // | c .............xxx****
1632: // | d ............xxxx ****
1633: // | e ...........xxxxx ****
1634: // | f ..........xxxxxx
1635: // |
1636: // | 2 3
1637: // v
1638: //
1639: // +y
1640: //
1641: // This grid accounts for the appropriate rounding of GIQ and last-pel
1642: // exclusion. If (M0, N0) lands on an 'x', x0 = 2. If (M0, N0) lands
1643: // on a '.', x0 = 1. If (M0, N0) lands on a '?', x0 rounds up or down,
1644: // depending on what flips have been done to normalize the line.
1645: //
1646: // For the end point, if (M1, N1) lands on an 'x', x1 =
1647: // floor((M0 + dM) / 16) + 1. If (M1, N1) lands on a '.', x1 =
1648: // floor((M0 + dM)). If (M1, N1) lands on a '?', x1 rounds up or down,
1649: // depending on what flips have been done to normalize the line.
1650: //
1651: // Lines of exactly slope one require a special case for both the start
1652: // and end. For example, if the line ends such that (M1, N1) is (9, 1),
1653: // the line has gone exactly through (8, 0) -- which may be considered
1654: // to be part of 'x' because of rounding! So slopes of exactly slope
1655: // one going through (8, 0) must also be considered as belonging in 'x'
1656: // when an x value of 1/2 is supposed to round up in value.
1657:
1658: // Calculate x0, x1:
1659:
1660: N1 = FXFRAC(N0 + dN);
1661: M1 = FXFRAC(M0 + dM);
1662:
1663: x1 = LFLOOR(M0 + dM);
1664:
1665: // Line runs left-to-right:
1666:
1667: // Compute x1:
1668:
1669: x1--;
1670: if (M1 > 0)
1671: {
1672: if (N1 == 0)
1673: {
1674: if (LROUND(M1, fl & HW_X_ROUND_DOWN))
1675: x1++;
1676: }
1677: else if (ABS((LONG) (N1 - F/2)) <= (LONG) M1)
1678: {
1679: x1++;
1680: }
1681: }
1682:
1683: if ((fl & (HW_FLIP_SLOPE_ONE | HW_X_ROUND_DOWN))
1684: == (HW_FLIP_SLOPE_ONE | HW_X_ROUND_DOWN))
1685: {
1686: // Have to special-case diagonal lines going through our
1687: // the point exactly equidistant between two horizontal
1688: // pixels, if we're supposed to round x=1/2 down:
1689:
1690: if ((N1 > 0) && (M1 == N1 + 8))
1691: x1--;
1692:
1693: if ((M0 > 0) && (N0 == M0 + 8))
1694: {
1695: x0 = 0;
1696: goto left_to_right_compute_y0;
1697: }
1698: }
1699:
1700: // Compute x0:
1701:
1702: x0 = 0;
1703: if (M0 > 0)
1704: {
1705: if (N0 == 0)
1706: {
1707: if (LROUND(M0, fl & HW_X_ROUND_DOWN))
1708: x0 = 1;
1709: }
1710: else if (ABS((LONG) (N0 - F/2)) <= (LONG) M0)
1711: {
1712: x0 = 1;
1713: }
1714: }
1715:
1716: left_to_right_compute_y0:
1717:
1718: /***********************************************************************\
1719: * Calculate the start pixel.
1720: \***********************************************************************/
1721:
1722: // We now compute y0 and adjust the error term. We know x0, and we know
1723: // the current formula for the pixels to be lit on the line:
1724: //
1725: // dN * x + lGamma
1726: // y(x) = floor( --------------- )
1727: // dM
1728: //
1729: // The remainder of this expression is the new error term at (x0, y0).
1730: // Since x0 is going to be either 0 or 1, we don't actually have to do a
1731: // multiply or divide to compute y0. Finally, we subtract dM from the
1732: // new error term so that it is in the range [-dM, 0).
1733:
1734: y0 = 0;
1735: lGamma += (dN & (-x0));
1736: lGamma -= dM;
1737: if (lGamma >= 0)
1738: {
1739: y0 = 1;
1740: lGamma -= dM;
1741: }
1742:
1743: // Undo our flips to get the start coordinate:
1744:
1745: x += x0;
1746: y += y0;
1747:
1748: if (fl & HW_FLIP_D)
1749: {
1750: register LONG lTmp;
1751: lTmp = x; x = y; y = lTmp;
1752: }
1753:
1754: if (fl & HW_FLIP_V)
1755: {
1756: y = -y;
1757: }
1758:
1759: if (fl & HW_FLIP_H)
1760: {
1761: x = -x;
1762: }
1763:
1764: /***********************************************************************\
1765: * Return the Bresenham terms:
1766: \***********************************************************************/
1767:
1768: pdl->iDir = gaiDir[fl & HW_FLIP_MASK];
1769: pdl->ptlStart.x = x;
1770: pdl->ptlStart.y = y;
1771: pdl->cPels = x1 - x0 + 1; // NOTE: You'll have to check if cPels <= 0!
1772: pdl->dMajor = dM;
1773: pdl->dMinor = dN;
1774: pdl->lErrorTerm = lGamma;
1775:
1776: return(TRUE);
1777: }
1778:
1779: #endif // HARDWAREGIQ
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.