1 /* Copyright (C) 1994, 1995, 1996, 1997, 1998 Aladdin Enterprises. All rights reserved. 2 3 This software is provided AS-IS with no warranty, either express or 4 implied. 5 6 This software is distributed under license and may not be copied, 7 modified or distributed except as expressly authorized under the terms 8 of the license contained in the file LICENSE in this distribution. 9 10 For more information about licensing, please refer to 11 http://www.ghostscript.com/licensing/. For information on 12 commercial licensing, go to http://www.artifex.com/licensing/ or 13 contact Artifex Software, Inc., 101 Lucas Valley Road #110, 14 San Rafael, CA 94903, U.S.A., +1(415)492-9861. 15 */ 16 17 /* $Id: gxdda.h,v 1.5 2003/08/26 15:38:50 igor Exp $ */ 18 /* Definitions for DDAs */ 19 /* Requires gxfixed.h */ 20 21 #ifndef gxdda_INCLUDED 22 # define gxdda_INCLUDED 23 24 /* 25 * We use the familiar Bresenham DDA algorithm for several purposes: 26 * - tracking the edges when filling trapezoids; 27 * - tracking the current pixel corner coordinates when rasterizing 28 * skewed or rotated images; 29 * - converting curves to sequences of lines (this is a 3rd-order 30 * DDA, the others are 1st-order); 31 * - perhaps someday for drawing single-pixel lines. 32 * In the case of trapezoids, lines, and curves, we need to use 33 * the DDA to find the integer X values at integer+0.5 values of Y; 34 * in the case of images, we use DDAs to compute the (fixed) 35 * X and Y values at (integer) source pixel corners. 36 * 37 * The purpose of the DDA is to compute the exact values Q(i) = floor(i*D/N) 38 * for increasing integers i, 0 <= i <= N. D is considered to be an 39 * integer, although it may actually be a fixed. For the algorithm, 40 * we maintain i*D/N as Q + (N-R)/N where Q and R are integers, 0 < R <= N, 41 * with the following auxiliary values: 42 * dQ = floor(D/N) 43 * dR = D mod N (0 <= dR < N) 44 * NdR = N - dR 45 * Then at each iteration we do: 46 * Q += dQ; 47 * if ( R > dR ) R -= dR; else ++Q, R += NdR; 48 * These formulas work regardless of the sign of D, and never let R go 49 * out of range. 50 */ 51 /* In the following structure definitions, ntype must be an unsigned type. */ 52 #define dda_state_struct(sname, dtype, ntype)\ 53 struct sname { dtype Q; ntype R; } 54 #define dda_step_struct(sname, dtype, ntype)\ 55 struct sname { dtype dQ; ntype dR, NdR; } 56 /* DDA with fixed Q and (unsigned) integer N */ 57 typedef 58 dda_state_struct(_a, fixed, uint) gx_dda_state_fixed; 59 typedef dda_step_struct(_e, fixed, uint) gx_dda_step_fixed; 60 typedef struct gx_dda_fixed_s { 61 gx_dda_state_fixed state; 62 gx_dda_step_fixed step; 63 } gx_dda_fixed; 64 /* 65 * Define a pair of DDAs for iterating along an arbitrary line. 66 */ 67 typedef struct gx_dda_fixed_point_s { 68 gx_dda_fixed x, y; 69 } gx_dda_fixed_point; 70 /* 71 * Initialize a DDA. The sign test is needed only because C doesn't 72 * provide reliable definitions of / and % for integers (!!!). 73 */ 74 #define dda_init_state(dstate, init, N)\ 75 (dstate).Q = (init), (dstate).R = (N) 76 #define dda_init_step(dstep, D, N)\ 77 if ( (N) == 0 )\ 78 (dstep).dQ = 0, (dstep).dR = 0;\ 79 else if ( (D) < 0 )\ 80 { (dstep).dQ = -(int)((uint)-(D) / (N));\ 81 if ( ((dstep).dR = -(D) % (N)) != 0 )\ 82 --(dstep).dQ, (dstep).dR = (N) - (dstep).dR;\ 83 }\ 84 else\ 85 { (dstep).dQ = (D) / (N); (dstep).dR = (D) % (N); }\ 86 (dstep).NdR = (N) - (dstep).dR 87 #define dda_init(dda, init, D, N)\ 88 dda_init_state((dda).state, init, N);\ 89 dda_init_step((dda).step, D, N) 90 /* 91 * Compute the sum of two DDA steps with the same D and N. 92 * Note that since dR + NdR = N, this quantity must be the same in both 93 * fromstep and tostep. 94 */ 95 #define dda_step_add(tostep, fromstep)\ 96 (tostep).dQ +=\ 97 ((tostep).dR < (fromstep).NdR ?\ 98 ((tostep).dR += (fromstep).dR, (tostep).NdR -= (fromstep).dR,\ 99 (fromstep).dQ) :\ 100 ((tostep).dR -= (fromstep).NdR, (tostep).NdR += (fromstep).NdR,\ 101 (fromstep).dQ + 1)) 102 /* 103 * Return the current value in a DDA. 104 */ 105 #define dda_state_current(dstate) (dstate).Q 106 #define dda_current(dda) dda_state_current((dda).state) 107 #define dda_current_fixed2int(dda)\ 108 fixed2int_var(dda_state_current((dda).state)) 109 /* 110 * Increment a DDA to the next point. 111 * Returns the updated current value. 112 */ 113 #define dda_state_next(dstate, dstep)\ 114 (dstate).Q +=\ 115 ((dstate).R > (dstep).dR ?\ 116 ((dstate).R -= (dstep).dR, (dstep).dQ) :\ 117 ((dstate).R += (dstep).NdR, (dstep).dQ + 1)) 118 #define dda_next(dda) dda_state_next((dda).state, (dda).step) 119 /* 120 * Back up a DDA to the previous point. 121 * Returns the updated current value. 122 */ 123 #define dda_state_previous(dstate, dstep)\ 124 (dstate).Q -=\ 125 ((dstate).R <= (dstep).NdR ?\ 126 ((dstate).R += (dstep).dR, (dstep).dQ) :\ 127 ((dstate).R -= (dstep).NdR, (dstep).dQ + 1)) 128 #define dda_previous(dda) dda_state_previous((dda).state, (dda).step) 129 /* 130 * Advance a DDA by an arbitrary number of steps. 131 * This implementation is very inefficient; we'll improve it if needed. 132 */ 133 #define dda_state_advance(dstate, dstep, nsteps)\ 134 BEGIN\ 135 uint n_ = (nsteps);\ 136 (dstate).Q += (dstep).dQ * (nsteps);\ 137 while ( n_-- )\ 138 if ( (dstate).R > (dstep).dR ) (dstate).R -= (dstep).dR;\ 139 else (dstate).R += (dstep).NdR, (dstate).Q++;\ 140 END 141 #define dda_advance(dda, nsteps)\ 142 dda_state_advance((dda).state, (dda).step, nsteps) 143 /* 144 * Translate the position of a DDA by a given amount. 145 */ 146 #define dda_state_translate(dstate, delta)\ 147 ((dstate).Q += (delta)) 148 #define dda_translate(dda, delta)\ 149 dda_state_translate((dda).state, delta) 150 151 #endif /* gxdda_INCLUDED */ 152