1 use {FloatNum, SignedNum, Voxel};
2 use steps::Steps;
3
4 #[inline]
compare<T: SignedNum>(a: T, b: T) -> T5 fn compare<T: SignedNum>(a: T, b: T) -> T {
6 if a > b {
7 T::one()
8 } else if a == b {
9 T::zero()
10 } else {
11 -T::one()
12 }
13 }
14
15 /// Where the center of the voxel is, at the center or a corner.
16 ///
17 /// Generally you want `Center`.
18 pub enum VoxelOrigin {
19 Corner,
20 Center,
21 }
22
23 impl VoxelOrigin {
24 #[inline]
25 /// Round a voxel's position based on the origin.
round<I: FloatNum, O: SignedNum>(&self, voxel: Voxel<I>) -> Voxel<O>26 pub fn round<I: FloatNum, O: SignedNum>(&self, voxel: Voxel<I>) -> Voxel<O> {
27 let (x, y, z) = match *self {
28 VoxelOrigin::Corner => voxel,
29 VoxelOrigin::Center => (voxel.0.round(), voxel.1.round(), voxel.2.round()),
30 };
31
32 (O::cast(x), O::cast(y), O::cast(z))
33 }
34 }
35
36 /// Walk between two voxels, taking orthogonal steps and visiting all voxels in between.
37 ///
38 /// Implemented from [this Stack Overflow answer].
39 /// This algorithm takes floating-point numbers as input and should be symmetrical.
40 ///
41 /// Example:
42 ///
43 /// ```
44 /// extern crate line_drawing;
45 /// use line_drawing::{VoxelOrigin, WalkVoxels};
46 ///
47 /// fn main() {
48 /// let a = (0.0, 0.0, 0.0);
49 /// let b = (5.0, 6.0, 7.0);
50 ///
51 /// for (i, (x, y, z)) in WalkVoxels::<f32, i8>::new(a, b, &VoxelOrigin::Center).enumerate() {
52 /// if i > 0 && i % 5 == 0 {
53 /// println!();
54 /// }
55 /// print!("({}, {}, {}), ", x, y, z);
56 /// }
57 /// }
58 /// ```
59 ///
60 /// ```text
61 /// (0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1), (1, 1, 2),
62 /// (1, 2, 2), (2, 2, 2), (2, 2, 3), (2, 3, 3), (2, 3, 4),
63 /// (3, 3, 4), (3, 4, 4), (3, 4, 5), (4, 4, 5), (4, 5, 5),
64 /// (4, 5, 6), (4, 5, 7), (4, 6, 7), (5, 6, 7),
65 /// ```
66 ///
67 /// [this Stack Overflow answer]: https://stackoverflow.com/a/16507714
68 pub struct WalkVoxels<I, O> {
69 voxel: Voxel<O>,
70 count: O,
71 sign_x: O,
72 sign_y: O,
73 sign_z: O,
74 err_x: I,
75 err_y: I,
76 err_z: I,
77 d_err_x: I,
78 d_err_y: I,
79 d_err_z: I,
80 }
81
82 impl<I: FloatNum, O: SignedNum> WalkVoxels<I, O> {
83 #[inline]
84 /// Create a new `WalkVoxels` iterator, with the origin of the voxels.
new(start: Voxel<I>, end: Voxel<I>, origin: &VoxelOrigin) -> Self85 pub fn new(start: Voxel<I>, end: Voxel<I>, origin: &VoxelOrigin) -> Self {
86 let start_i: Voxel<O> = origin.round(start);
87 let end_i: Voxel<O> = origin.round(end);
88
89 let count =
90 (start_i.0 - end_i.0).abs() + (start_i.1 - end_i.1).abs() + (start_i.2 - end_i.2).abs();
91
92 let sign_x = compare(end_i.0, start_i.0);
93 let sign_y = compare(end_i.1, start_i.1);
94 let sign_z = compare(end_i.2, start_i.2);
95
96 // Planes for each axis that we will next cross
97 let x_plane = start_i.0 + (if end_i.0 > start_i.0 {
98 O::one()
99 } else {
100 O::zero()
101 });
102 let y_plane = start_i.1 + (if end_i.1 > start_i.1 {
103 O::one()
104 } else {
105 O::zero()
106 });
107 let z_plane = start_i.2 + (if end_i.2 > start_i.2 {
108 O::one()
109 } else {
110 O::zero()
111 });
112
113 // Only used for multiplying up the error margins
114 let vx = if start.0 == end.0 {
115 I::one()
116 } else {
117 end.0 - start.0
118 };
119 let vy = if start.1 == end.1 {
120 I::one()
121 } else {
122 end.1 - start.1
123 };
124 let vz = if start.2 == end.2 {
125 I::one()
126 } else {
127 end.2 - start.2
128 };
129
130 // Error is normalized to vx * vy * vz so we only have to multiply up
131 let vxvy = vx * vy;
132 let vxvz = vx * vz;
133 let vyvz = vy * vz;
134
135 Self {
136 sign_x,
137 sign_y,
138 sign_z,
139 count,
140 voxel: start_i,
141 // Error from the next plane accumulators, scaled up by vx * vy * vz
142 // gx0 + vx * rx === gxp
143 // vx * rx === gxp - gx0
144 // rx === (gxp - gx0) / vx
145 err_x: (I::cast(x_plane) - start.0) * vyvz,
146 err_y: (I::cast(y_plane) - start.1) * vxvz,
147 err_z: (I::cast(z_plane) - start.2) * vxvy,
148 d_err_x: I::cast(sign_x) * vyvz,
149 d_err_y: I::cast(sign_y) * vxvz,
150 d_err_z: I::cast(sign_z) * vxvy,
151 }
152 }
153
154 #[inline]
steps(self) -> Steps<Voxel<O>, Self>155 pub fn steps(self) -> Steps<Voxel<O>, Self> {
156 Steps::new(self)
157 }
158 }
159
160 impl<I: FloatNum, O: SignedNum> Iterator for WalkVoxels<I, O> {
161 type Item = Voxel<O>;
162
163 #[inline]
next(&mut self) -> Option<Self::Item>164 fn next(&mut self) -> Option<Self::Item> {
165 if self.count >= O::zero() {
166 self.count -= O::one();
167
168 // Which plane do we cross first?
169 let xr = self.err_x.abs();
170 let yr = self.err_y.abs();
171 let zr = self.err_z.abs();
172
173 let x_zero = self.sign_x == O::zero();
174 let y_zero = self.sign_y == O::zero();
175 let z_zero = self.sign_z == O::zero();
176
177 let voxel = self.voxel;
178
179 if !x_zero && (y_zero || xr < yr) && (z_zero || xr < zr) {
180 self.voxel.0 += self.sign_x;
181 self.err_x += self.d_err_x;
182 } else if !y_zero && (z_zero || yr < zr) {
183 self.voxel.1 += self.sign_y;
184 self.err_y += self.d_err_y;
185 } else if !z_zero {
186 self.voxel.2 += self.sign_z;
187 self.err_z += self.d_err_z;
188 }
189
190 Some(voxel)
191 } else {
192 None
193 }
194 }
195 }
196
197 #[test]
tests()198 fn tests() {
199 assert_eq!(
200 WalkVoxels::new(
201 (0.472, -1.100, 0.179),
202 (1.114, -0.391, 0.927),
203 &VoxelOrigin::Center
204 ).collect::<Vec<_>>(),
205 [(0, -1, 0), (1, -1, 0), (1, -1, 1), (1, 0, 1)]
206 );
207 }
208