agg_rust/
dda_line.rs

1//! DDA (Digital Differential Analyzer) line interpolation algorithms.
2//!
3//! Port of `agg_dda_line.h` — efficient line interpolation using integer
4//! arithmetic for rasterization.
5
6// ============================================================================
7// DDA line interpolator (fixed-point with configurable shift)
8// ============================================================================
9
10/// Fixed-point DDA line interpolator with configurable precision.
11///
12/// Port of C++ `dda_line_interpolator<FractionShift, YShift>`.
13/// Uses bit-shift arithmetic for sub-pixel precision.
14pub struct DdaLineInterpolator<const FRACTION_SHIFT: i32, const Y_SHIFT: i32 = 0> {
15    y: i32,
16    inc: i32,
17    dy: i32,
18}
19
20impl<const FRACTION_SHIFT: i32, const Y_SHIFT: i32> DdaLineInterpolator<FRACTION_SHIFT, Y_SHIFT> {
21    pub fn new(y1: i32, y2: i32, count: u32) -> Self {
22        Self {
23            y: y1,
24            inc: ((y2 - y1) << FRACTION_SHIFT) / count as i32,
25            dy: 0,
26        }
27    }
28
29    /// Step forward one unit.
30    #[inline]
31    pub fn inc(&mut self) {
32        self.dy += self.inc;
33    }
34
35    /// Step backward one unit.
36    #[inline]
37    pub fn dec(&mut self) {
38        self.dy -= self.inc;
39    }
40
41    /// Step forward by `n` units.
42    #[inline]
43    pub fn inc_by(&mut self, n: u32) {
44        self.dy += self.inc * n as i32;
45    }
46
47    /// Step backward by `n` units.
48    #[inline]
49    pub fn dec_by(&mut self, n: u32) {
50        self.dy -= self.inc * n as i32;
51    }
52
53    /// Current Y value (shifted output).
54    #[inline]
55    pub fn y(&self) -> i32 {
56        self.y + (self.dy >> (FRACTION_SHIFT - Y_SHIFT))
57    }
58
59    /// Raw accumulated delta.
60    #[inline]
61    pub fn dy(&self) -> i32 {
62        self.dy
63    }
64}
65
66// ============================================================================
67// DDA2 line interpolator (Bresenham-style integer)
68// ============================================================================
69
70/// Integer DDA line interpolator using Bresenham-style remainder tracking.
71///
72/// Port of C++ `dda2_line_interpolator`.
73/// Distributes rounding error evenly across all steps.
74#[derive(Debug, Clone)]
75pub struct Dda2LineInterpolator {
76    cnt: i32,
77    lft: i32,
78    rem: i32,
79    mod_val: i32,
80    y: i32,
81}
82
83impl Dda2LineInterpolator {
84    /// Forward-adjusted line from y1 to y2 over `count` steps.
85    pub fn new_forward(y1: i32, y2: i32, count: i32) -> Self {
86        let cnt = if count <= 0 { 1 } else { count };
87        let mut lft = (y2 - y1) / cnt;
88        let mut rem = (y2 - y1) % cnt;
89        let mut mod_val = rem;
90
91        if mod_val <= 0 {
92            mod_val += count;
93            rem += count;
94            lft -= 1;
95        }
96        mod_val -= count;
97
98        Self {
99            cnt,
100            lft,
101            rem,
102            mod_val,
103            y: y1,
104        }
105    }
106
107    /// Backward-adjusted line from y1 to y2 over `count` steps.
108    pub fn new_backward(y1: i32, y2: i32, count: i32) -> Self {
109        let cnt = if count <= 0 { 1 } else { count };
110        let mut lft = (y2 - y1) / cnt;
111        let mut rem = (y2 - y1) % cnt;
112        let mut mod_val = rem;
113
114        if mod_val <= 0 {
115            mod_val += count;
116            rem += count;
117            lft -= 1;
118        }
119
120        Self {
121            cnt,
122            lft,
123            rem,
124            mod_val,
125            y: y1,
126        }
127    }
128
129    /// Relative delta over `count` steps (y starting at 0).
130    pub fn new_relative(y: i32, count: i32) -> Self {
131        let cnt = if count <= 0 { 1 } else { count };
132        let mut lft = y / cnt;
133        let mut rem = y % cnt;
134        let mut mod_val = rem;
135
136        if mod_val <= 0 {
137            mod_val += count;
138            rem += count;
139            lft -= 1;
140        }
141
142        Self {
143            cnt,
144            lft,
145            rem,
146            mod_val,
147            y: 0,
148        }
149    }
150
151    /// Save state for later restoration.
152    pub fn save(&self) -> [i32; 2] {
153        [self.mod_val, self.y]
154    }
155
156    /// Load previously saved state.
157    pub fn load(&mut self, data: &[i32; 2]) {
158        self.mod_val = data[0];
159        self.y = data[1];
160    }
161
162    /// Step forward one unit.
163    #[inline]
164    pub fn inc(&mut self) {
165        self.mod_val += self.rem;
166        self.y += self.lft;
167        if self.mod_val > 0 {
168            self.mod_val -= self.cnt;
169            self.y += 1;
170        }
171    }
172
173    /// Step backward one unit.
174    #[inline]
175    pub fn dec(&mut self) {
176        if self.mod_val <= self.rem {
177            self.mod_val += self.cnt;
178            self.y -= 1;
179        }
180        self.mod_val -= self.rem;
181        self.y -= self.lft;
182    }
183
184    /// Adjust forward (shift phase).
185    #[inline]
186    pub fn adjust_forward(&mut self) {
187        self.mod_val -= self.cnt;
188    }
189
190    /// Adjust backward (shift phase).
191    #[inline]
192    pub fn adjust_backward(&mut self) {
193        self.mod_val += self.cnt;
194    }
195
196    #[inline]
197    pub fn mod_val(&self) -> i32 {
198        self.mod_val
199    }
200
201    #[inline]
202    pub fn rem(&self) -> i32 {
203        self.rem
204    }
205
206    #[inline]
207    pub fn lft(&self) -> i32 {
208        self.lft
209    }
210
211    #[inline]
212    pub fn y(&self) -> i32 {
213        self.y
214    }
215}
216
217// ============================================================================
218// Bresenham line interpolator
219// ============================================================================
220
221/// Bresenham line interpolator with subpixel precision.
222///
223/// Port of C++ `line_bresenham_interpolator`.
224/// Uses 8-bit subpixel scale (256x).
225pub struct LineBresenhamInterpolator {
226    x1_lr: i32,
227    y1_lr: i32,
228    #[allow(dead_code)]
229    x2_lr: i32,
230    #[allow(dead_code)]
231    y2_lr: i32,
232    ver: bool,
233    len: u32,
234    inc: i32,
235    interpolator: Dda2LineInterpolator,
236}
237
238/// Subpixel constants for Bresenham interpolator.
239pub const SUBPIXEL_SHIFT: i32 = 8;
240pub const SUBPIXEL_SCALE: i32 = 1 << SUBPIXEL_SHIFT;
241#[allow(dead_code)]
242pub const SUBPIXEL_MASK: i32 = SUBPIXEL_SCALE - 1;
243
244/// Convert from high-resolution (subpixel) to low-resolution (pixel).
245#[inline]
246pub fn line_lr(v: i32) -> i32 {
247    v >> SUBPIXEL_SHIFT
248}
249
250impl LineBresenhamInterpolator {
251    pub fn new(x1: i32, y1: i32, x2: i32, y2: i32) -> Self {
252        let x1_lr = line_lr(x1);
253        let y1_lr = line_lr(y1);
254        let x2_lr = line_lr(x2);
255        let y2_lr = line_lr(y2);
256
257        let ver = (x2_lr - x1_lr).abs() < (y2_lr - y1_lr).abs();
258        let len = if ver {
259            (y2_lr - y1_lr).unsigned_abs()
260        } else {
261            (x2_lr - x1_lr).unsigned_abs()
262        };
263        let inc = if ver {
264            if y2 > y1 {
265                1
266            } else {
267                -1
268            }
269        } else if x2 > x1 {
270            1
271        } else {
272            -1
273        };
274
275        let interpolator = Dda2LineInterpolator::new_forward(
276            if ver { x1 } else { y1 },
277            if ver { x2 } else { y2 },
278            len as i32,
279        );
280
281        Self {
282            x1_lr,
283            y1_lr,
284            x2_lr,
285            y2_lr,
286            ver,
287            len,
288            inc,
289            interpolator,
290        }
291    }
292
293    /// True if the line is vertical-major.
294    #[inline]
295    pub fn is_ver(&self) -> bool {
296        self.ver
297    }
298
299    /// Number of steps in the dominant axis.
300    #[inline]
301    #[allow(clippy::len_without_is_empty)]
302    pub fn len(&self) -> u32 {
303        self.len
304    }
305
306    /// Direction increment (+1 or -1).
307    #[inline]
308    pub fn inc(&self) -> i32 {
309        self.inc
310    }
311
312    /// Step along the horizontal-major axis.
313    #[inline]
314    pub fn hstep(&mut self) {
315        self.interpolator.inc();
316        self.x1_lr += self.inc;
317    }
318
319    /// Step along the vertical-major axis.
320    #[inline]
321    pub fn vstep(&mut self) {
322        self.interpolator.inc();
323        self.y1_lr += self.inc;
324    }
325
326    /// Current x1 in pixel coordinates.
327    #[inline]
328    pub fn x1(&self) -> i32 {
329        self.x1_lr
330    }
331
332    /// Current y1 in pixel coordinates.
333    #[inline]
334    pub fn y1(&self) -> i32 {
335        self.y1_lr
336    }
337
338    /// Current secondary axis value in pixel coordinates.
339    #[inline]
340    pub fn x2(&self) -> i32 {
341        line_lr(self.interpolator.y())
342    }
343
344    /// Current secondary axis value in pixel coordinates.
345    #[inline]
346    pub fn y2(&self) -> i32 {
347        line_lr(self.interpolator.y())
348    }
349
350    /// Current secondary axis value in subpixel coordinates.
351    #[inline]
352    pub fn x2_hr(&self) -> i32 {
353        self.interpolator.y()
354    }
355
356    /// Current secondary axis value in subpixel coordinates.
357    #[inline]
358    pub fn y2_hr(&self) -> i32 {
359        self.interpolator.y()
360    }
361}
362
363// ============================================================================
364// Tests
365// ============================================================================
366
367#[cfg(test)]
368mod tests {
369    use super::*;
370
371    #[test]
372    fn test_dda_line_interpolator_basic() {
373        // Interpolate from 0 to 100 in 10 steps with 8-bit fraction
374        let mut dda = DdaLineInterpolator::<8, 0>::new(0, 100, 10);
375        assert_eq!(dda.y(), 0);
376        for _ in 0..10 {
377            dda.inc();
378        }
379        assert_eq!(dda.y(), 100);
380    }
381
382    #[test]
383    fn test_dda_line_interpolator_midpoint() {
384        let mut dda = DdaLineInterpolator::<8, 0>::new(0, 100, 10);
385        for _ in 0..5 {
386            dda.inc();
387        }
388        assert_eq!(dda.y(), 50);
389    }
390
391    #[test]
392    fn test_dda_line_interpolator_backward() {
393        let mut dda = DdaLineInterpolator::<8, 0>::new(0, 100, 10);
394        dda.inc_by(10);
395        assert_eq!(dda.y(), 100);
396        dda.dec_by(10);
397        assert_eq!(dda.y(), 0);
398    }
399
400    #[test]
401    fn test_dda2_forward() {
402        let mut dda = Dda2LineInterpolator::new_forward(0, 10, 10);
403        for _ in 0..10 {
404            dda.inc();
405        }
406        assert_eq!(dda.y(), 10);
407    }
408
409    #[test]
410    fn test_dda2_forward_negative() {
411        let mut dda = Dda2LineInterpolator::new_forward(10, 0, 10);
412        for _ in 0..10 {
413            dda.inc();
414        }
415        assert_eq!(dda.y(), 0);
416    }
417
418    #[test]
419    fn test_dda2_backward() {
420        let mut dda = Dda2LineInterpolator::new_backward(0, 10, 10);
421        for _ in 0..10 {
422            dda.inc();
423        }
424        assert_eq!(dda.y(), 10);
425    }
426
427    #[test]
428    fn test_dda2_save_load() {
429        let mut dda = Dda2LineInterpolator::new_forward(0, 100, 10);
430        for _ in 0..5 {
431            dda.inc();
432        }
433        let saved = dda.save();
434        let y_at_5 = dda.y();
435
436        for _ in 0..3 {
437            dda.inc();
438        }
439        assert_ne!(dda.y(), y_at_5);
440
441        dda.load(&saved);
442        assert_eq!(dda.y(), y_at_5);
443    }
444
445    #[test]
446    fn test_dda2_dec() {
447        let mut dda = Dda2LineInterpolator::new_forward(0, 10, 10);
448        for _ in 0..10 {
449            dda.inc();
450        }
451        assert_eq!(dda.y(), 10);
452        for _ in 0..10 {
453            dda.dec();
454        }
455        assert_eq!(dda.y(), 0);
456    }
457
458    #[test]
459    fn test_bresenham_horizontal() {
460        let bi = LineBresenhamInterpolator::new(0, 0, 10 * SUBPIXEL_SCALE, 0);
461        assert!(!bi.is_ver());
462        assert_eq!(bi.len(), 10);
463        assert_eq!(bi.inc(), 1);
464    }
465
466    #[test]
467    fn test_bresenham_vertical() {
468        let bi = LineBresenhamInterpolator::new(0, 0, 0, 10 * SUBPIXEL_SCALE);
469        assert!(bi.is_ver());
470        assert_eq!(bi.len(), 10);
471        assert_eq!(bi.inc(), 1);
472    }
473
474    #[test]
475    fn test_bresenham_diagonal() {
476        let mut bi = LineBresenhamInterpolator::new(0, 0, 10 * SUBPIXEL_SCALE, 10 * SUBPIXEL_SCALE);
477        // Diagonal: neither axis dominates, but due to < comparison, horizontal wins
478        assert_eq!(bi.len(), 10);
479        // Step all the way
480        for _ in 0..bi.len() {
481            if bi.is_ver() {
482                bi.vstep();
483            } else {
484                bi.hstep();
485            }
486        }
487    }
488
489    #[test]
490    fn test_bresenham_negative_direction() {
491        let bi = LineBresenhamInterpolator::new(10 * SUBPIXEL_SCALE, 0, 0, 0);
492        assert!(!bi.is_ver());
493        assert_eq!(bi.inc(), -1);
494    }
495}
agg_rust/dda_line.rs

agg_rust/
dda_line.rs
