1 /* Copyright (C) 2001-2012 Artifex Software, Inc. 2 All Rights Reserved. 3 4 This software is provided AS-IS with no warranty, either express or 5 implied. 6 7 This software is distributed under license and may not be copied, 8 modified or distributed except as expressly authorized under the terms 9 of the license contained in the file LICENSE in this distribution. 10 11 Refer to licensing information at http://www.artifex.com or contact 12 Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134, San Rafael, 13 CA 94903, U.S.A., +1(415)492-9861, for further information. 14 */ 15 16 17 /* Definitions for DDAs */ 18 /* Requires gxfixed.h */ 19 20 #ifndef gxdda_INCLUDED 21 # define gxdda_INCLUDED 22 23 /* We use the familiar Bresenham DDA algorithm for several purposes: 24 * - tracking the edges when filling trapezoids; 25 * - tracking the current pixel corner coordinates when rasterizing 26 * skewed or rotated images; 27 * - converting curves to sequences of lines (this is a 3rd-order 28 * DDA, the others are 1st-order); 29 * - perhaps someday for drawing single-pixel lines. 30 * In the case of trapezoids, lines, and curves, we need to use 31 * the DDA to find the integer X values at integer+0.5 values of Y; 32 * in the case of images, we use DDAs to compute the (fixed) 33 * X and Y values at (integer) source pixel corners. 34 * 35 * The purpose of the DDA is to compute the exact values Q(i) = floor(i*D/N) 36 * for increasing integers i, 0 <= i <= N. D is considered to be an 37 * integer, although it may actually be a fixed. 38 * 39 * In the original formulation of the algorithm, we maintained i*D/N as 40 * Q + (N-R)/N where Q and R are integers, where 0 < R <= N, with the 41 * following auxiliary values: 42 * dQ = floor(D/N) 43 * dR = D mod N (0 <= dR < N) 44 * NdR = N - dR 45 * And at each iteration the code did: 46 * Q += dQ; 47 * if ( R > dR ) R -= dR; else ++Q, R += NdR; 48 * 49 * In the new formulation here, we hold i*D/N as Q + (N-1-R)/N where Q and R 50 * are integers, 0 <= R < N. 51 * Q += dQ; 52 * R -= dR 53 * if ( R < 0) R += N, ++Q; 54 * These formulas work regardless of the sign of D, and never let R go 55 * out of range. 56 * 57 * Why is the new formulation better? Well, it's simpler for one thing - the 58 * values stored in the structure are the obvious ones, without the strange 59 * NdR one. Also, in the original we test R > dR, which takes as long as 60 * doing R-=dR in the first place; in the new code we test R against 0, which 61 * we get for free on most architectures. 62 * 63 * In architectures that use branches for alternation, the first (should) 64 * compiles to something like (excuse the pseudo code): 65 * 66 * Q += dQ 67 * if (R > dR) 68 * goto A 69 * R -= dR 70 * goto B 71 * A: 72 * Q += 1 73 * R += NdR 74 * B: 75 * 76 * So 7 'instructions', 5 on each possible route through the code, including 77 * 1 branch regardless of the values. 78 * 79 * In the new form, it compiles to: 80 * 81 * R -= dR 82 * if (R >= 0) <- this instruction for free due to preceeding one 83 * goto A: 84 * R += N 85 * Q++ 86 * A: 87 * Q += dQ 88 * 89 * So 5 'instructions', 3 on the no step case, 5 on the step case, including 90 * 1 branch on the no-step case. 91 * 92 * If the compiler is smart enough to use the carry flag, it becomes: 93 * 94 * R -= dR 95 * if (R >= 0) <- this instruction for free due to preceeding one 96 * goto A: 97 * R += N 98 * A: 99 * Q += dQ + C <- Add with carry 100 * 101 * 4 instructions total, 3 on the no step case, 4 on the step case, including 102 * 1 branch on the no-step case. 103 * 104 * This is an even better win on architectures (like ARM) where alternation 105 * can be done without branches: 106 * 107 * ADD Q, Q, dQ 108 * CMP R, dR 109 * SUBGT R, R, dR 110 * ADDLE Q, Q, #1 111 * ADDLE R, R, nDR 112 * 113 * in the original (assuming all values in registers) becomes: 114 * 115 * SUBS R, R, dR 116 * ADDLT R, R, N 117 * ADDLT Q, Q, #1 118 * ADD Q, Q, dQ 119 * 120 * If the compiler is smart enough to use the carry flag, we can do even 121 * better: 122 * 123 * SUBS R, R, dR 124 * ADDLT R, R, N 125 * ADC Q, Q, dQ 126 * 127 * (Actually looking at the compilation given by MSVC 2005 confirms a 1 128 * instruction (and once branch) win for the above results. Sadly compilers 129 * don't look to be smart enough to exploit carry flag tricks.) 130 */ 131 #ifdef USE_OLD_DDA_FORMULATION 132 133 /* In the following structure definitions, ntype must be an unsigned type. */ 134 #define dda_state_struct(sname, dtype, ntype)\ 135 struct sname { dtype Q; ntype R; } 136 #define dda_step_struct(sname, dtype, ntype)\ 137 struct sname { dtype dQ; ntype dR, NdR; } 138 139 /* DDA with int Q and uint N */ 140 typedef struct gx_dda_int_s { 141 dda_state_struct(ia_, int, uint) state; 142 dda_step_struct(ie_, int, uint) step; 143 } gx_dda_int_t; 144 145 /* DDA with fixed Q and (unsigned) integer N */ 146 typedef 147 dda_state_struct(_a, fixed, uint) gx_dda_state_fixed; 148 typedef dda_step_struct(_e, fixed, uint) gx_dda_step_fixed; 149 typedef struct gx_dda_fixed_s { 150 gx_dda_state_fixed state; 151 gx_dda_step_fixed step; 152 } gx_dda_fixed; 153 /* 154 * Define a pair of DDAs for iterating along an arbitrary line. 155 */ 156 typedef struct gx_dda_fixed_point_s { 157 gx_dda_fixed x, y; 158 } gx_dda_fixed_point; 159 /* 160 * Initialize a DDA. The sign test is needed only because C doesn't 161 * provide reliable definitions of / and % for integers (!!!). 162 */ 163 #define dda_init_state(dstate, init, N)\ 164 (dstate).Q = (init), (dstate).R = (N) 165 #define dda_init_step(dstep, D, N)\ 166 if ( (N) == 0 )\ 167 (dstep).dQ = 0, (dstep).dR = 0;\ 168 else if ( (D) < 0 )\ 169 { (dstep).dQ = -(int)((uint)-(D) / (N));\ 170 if ( ((dstep).dR = -(D) % (N)) != 0 )\ 171 --(dstep).dQ, (dstep).dR = (N) - (dstep).dR;\ 172 }\ 173 else\ 174 { (dstep).dQ = (D) / (N); (dstep).dR = (D) % (N); }\ 175 (dstep).NdR = (N) - (dstep).dR 176 #define dda_init(dda, init, D, N)\ 177 dda_init_state((dda).state, init, N);\ 178 dda_init_step((dda).step, D, N) 179 /* 180 * Compute the sum of two DDA steps with the same D and N. 181 * Note that since dR + NdR = N, this quantity must be the same in both 182 * fromstep and tostep. 183 */ 184 #define dda_step_add(tostep, fromstep)\ 185 (tostep).dQ +=\ 186 ((tostep).dR < (fromstep).NdR ?\ 187 ((tostep).dR += (fromstep).dR, (tostep).NdR -= (fromstep).dR,\ 188 (fromstep).dQ) :\ 189 ((tostep).dR -= (fromstep).NdR, (tostep).NdR += (fromstep).NdR,\ 190 (fromstep).dQ + 1)) 191 /* 192 * Return the current value in a DDA. 193 */ 194 #define dda_state_current(dstate) (dstate).Q 195 #define dda_current(dda) dda_state_current((dda).state) 196 #define dda_current_fixed2int(dda)\ 197 fixed2int_var(dda_state_current((dda).state)) 198 /* 199 * Increment a DDA to the next point. 200 * Returns the updated current value. 201 */ 202 #define dda_state_next(dstate, dstep)\ 203 (dstate).Q +=\ 204 ((dstate).R > (dstep).dR ?\ 205 ((dstate).R -= (dstep).dR, (dstep).dQ) :\ 206 ((dstate).R += (dstep).NdR, (dstep).dQ + 1)) 207 #define dda_next(dda) dda_state_next((dda).state, (dda).step) 208 #define dda_next_assign(dda,v) \ 209 do { dda_next(dda);(v)=(dda).state.Q; } while (0) 210 /* 211 * Back up a DDA to the previous point. 212 * Returns the updated current value. 213 */ 214 #define dda_state_previous(dstate, dstep)\ 215 (dstate).Q -=\ 216 ((dstate).R <= (dstep).NdR ?\ 217 ((dstate).R += (dstep).dR, (dstep).dQ) :\ 218 ((dstate).R -= (dstep).NdR, (dstep).dQ + 1)) 219 #define dda_previous(dda) dda_state_previous((dda).state, (dda).step) 220 #define dda_previous_assign(dda,v) \ 221 do { dda_previous(dda);v =(dda).state.Q; } while (0) 222 /* 223 * Advance a DDA by an arbitrary number of steps. 224 * This implementation is very inefficient; we'll improve it if needed. 225 */ 226 #define dda_state_advance(dstate, dstep, nsteps)\ 227 BEGIN\ 228 uint n_ = (nsteps);\ 229 (dstate).Q += (dstep).dQ * (nsteps);\ 230 while ( n_-- )\ 231 if ( (dstate).R > (dstep).dR ) (dstate).R -= (dstep).dR;\ 232 else (dstate).R += (dstep).NdR, (dstate).Q++;\ 233 END 234 #define dda_advance(dda, nsteps)\ 235 dda_state_advance((dda).state, (dda).step, nsteps) 236 /* 237 * Translate the position of a DDA by a given amount. 238 */ 239 #define dda_state_translate(dstate, delta)\ 240 ((dstate).Q += (delta)) 241 #define dda_translate(dda, delta)\ 242 dda_state_translate((dda).state, delta) 243 244 #else /* New Version! */ 245 246 /* In the following structure definitions, ntype must be an unsigned type. */ 247 #define dda_state_struct(sname, dtype, ntype)\ 248 struct sname { dtype Q; ntype R; } 249 #define dda_step_struct(sname, dtype, ntype)\ 250 struct sname { dtype dQ; ntype dR, N; } 251 252 /* DDA with int Q and uint N */ 253 typedef struct gx_dda_int_s { 254 dda_state_struct(ia_, int, uint) state; 255 dda_step_struct(ie_, int, uint) step; 256 } gx_dda_int_t; 257 258 /* DDA with fixed Q and (unsigned) integer N */ 259 typedef 260 dda_state_struct(_a, fixed, uint) gx_dda_state_fixed; 261 typedef dda_step_struct(_e, fixed, uint) gx_dda_step_fixed; 262 typedef struct gx_dda_fixed_s { 263 gx_dda_state_fixed state; 264 gx_dda_step_fixed step; 265 } gx_dda_fixed; 266 /* 267 * Define a pair of DDAs for iterating along an arbitrary line. 268 */ 269 typedef struct gx_dda_fixed_point_s { 270 gx_dda_fixed x, y; 271 } gx_dda_fixed_point; 272 /* 273 * Initialize a DDA. The sign test is needed only because C doesn't 274 * provide reliable definitions of / and % for integers (!!!). 275 */ 276 #define dda_init_state(dstate, init, N_)\ 277 (dstate).Q = (init), (dstate).R = ((N_)-1) 278 #define dda_init_step(dstep, D, N_)\ 279 do {\ 280 if ( (N_) == 0 )\ 281 (dstep).dQ = 0, (dstep).dR = 0;\ 282 else if ( (D) < 0 )\ 283 { (dstep).dQ = -(int)((uint)-(D) / (N_));\ 284 if ( ((dstep).dR = -(D) % (N_)) != 0 )\ 285 --(dstep).dQ, (dstep).dR = (N_) - (dstep).dR;\ 286 }\ 287 else\ 288 { (dstep).dQ = (D) / (N_); (dstep).dR = (D) % (N_); }\ 289 (dstep).N = (N_);\ 290 } while (0) 291 #define dda_init(dda, init, D, N)\ 292 dda_init_state((dda).state, init, N);\ 293 dda_init_step((dda).step, D, N) 294 /* 295 * Compute the sum of two DDA steps with the same D and N. 296 * Note that since dR + NdR = N, this quantity must be the same in both 297 * fromstep and tostep. 298 */ 299 #define dda_step_add(tostep, fromstep)\ 300 BEGIN\ 301 (tostep).dR += (fromstep).dR;\ 302 if ((tostep).dR >= (tostep).N) {\ 303 (tostep).dQ ++;\ 304 (tostep).dR -= (tostep).N;\ 305 }\ 306 (tostep).dQ += (fromstep).dQ;\ 307 END 308 /* 309 * Return the current value in a DDA. 310 */ 311 #define dda_state_current(dstate) (dstate).Q 312 #define dda_current(dda) dda_state_current((dda).state) 313 #define dda_current_fixed2int(dda)\ 314 fixed2int_var(dda_state_current((dda).state)) 315 /* 316 * Increment a DDA to the next point. 317 * Returns the updated current value. 318 */ 319 #define dda_state_next(dstate, dstep)\ 320 do {\ 321 (dstate).R -= (dstep).dR;\ 322 if ((signed)(dstate).R < 0) {\ 323 (dstate).Q++;\ 324 (dstate).R += (dstep).N;\ 325 };\ 326 (dstate).Q += (dstep).dQ;\ 327 } while (0) 328 #define dda_next(dda) dda_state_next((dda).state, (dda).step) 329 #define dda_next_assign(dda,v) BEGIN dda_next(dda);(v)=(dda).state.Q; END 330 331 /* 332 * Back up a DDA to the previous point. 333 * Returns the updated current value. 334 */ 335 #define dda_state_previous(dstate, dstep)\ 336 BEGIN\ 337 (dstate).R += (dstep).dR;\ 338 if ((dstate).R >= (dstep).N) {\ 339 (dstate).Q--;\ 340 (dstate).R -= (dstep).N;\ 341 }\ 342 (dstate).Q -= (dstep).dQ;\ 343 END 344 #define dda_previous(dda) dda_state_previous((dda).state, (dda).step) 345 #define dda_previous_assign(dda,v) BEGIN dda_previous(dda);(v)=(dda).state.Q;END 346 /* 347 * Advance a DDA by an arbitrary number of steps. 348 * This implementation is very inefficient; we'll improve it if needed. 349 */ 350 #define dda_state_advance(dstate, dstep, nsteps)\ 351 BEGIN\ 352 uint n_ = (nsteps);\ 353 (dstate).Q += (dstep).dQ * (nsteps);\ 354 while ( n_-- ) {\ 355 (dstate).R -= (dstep).dR;\ 356 if ((signed int)(dstate).R < 0) {\ 357 (dstate).Q ++;\ 358 (dstate).R += (dstep).N;\ 359 }\ 360 }\ 361 END 362 #define dda_advance(dda, nsteps)\ 363 dda_state_advance((dda).state, (dda).step, nsteps) 364 /* 365 * Translate the position of a DDA by a given amount. 366 */ 367 #define dda_state_translate(dstate, delta)\ 368 ((dstate).Q += (delta)) 369 #define dda_translate(dda, delta)\ 370 dda_state_translate((dda).state, delta) 371 372 #endif 373 374 #endif /* gxdda_INCLUDED */ 375