1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
use super::sampled_contour::*;
use smallvec::*;
use std::ops::{Range};
///
/// An iterator that finds the edges of a contour by calling the `intercepts_on_line()` function
///
pub struct InterceptScanEdgeIterator<TLineIterator> {
/// The contour that this is tracing the edges of
line_iterator: TLineIterator,
/// Set to true once there are no more lines in the line iterator
finished: bool,
/// The y pos of the current line
ypos: f64,
/// The preceding the current one
previous_line: SmallVec<[Range<usize>; 4]>,
/// The line following the current one
current_line: SmallVec<[Range<usize>; 4]>,
/// Index into the previous line of the current x position
previous_pos: usize,
/// Index into the current line of the current x position
current_pos: usize,
/// The next x position to return
xpos: usize,
}
impl<TLineIterator> InterceptScanEdgeIterator<TLineIterator>
where
TLineIterator: Iterator<Item=SmallVec<[Range<usize>; 4]>>,
{
///
/// Creates a new edge iterator at the top-left corner of a contour
///
/// The line iterator should return the rounded intercepts on each line in the contour
///
pub fn from_iterator(line_iterator: TLineIterator) -> InterceptScanEdgeIterator<TLineIterator> {
// Create an edge iterator in a neutral state
let mut iterator = InterceptScanEdgeIterator {
line_iterator: line_iterator,
finished: false,
ypos: 0.0,
previous_line: smallvec![],
current_line: smallvec![],
previous_pos: 0,
current_pos: 0,
xpos: 0,
};
// Load the first line into the iterator
iterator.load_line(0.0);
iterator
}
///
/// Loads a line ahead of the current line into this contour
///
fn load_line(&mut self, ypos: f64) {
use std::mem;
let mut ypos = ypos;
loop {
// Move the current line into the previous line
mem::swap(&mut self.previous_line, &mut self.current_line);
// Load the next line from the contour
if let Some(line) = self.line_iterator.next() {
self.current_line = line;
} else {
self.finished = true;
self.current_line = smallvec![];
}
// Try to pick an x position to start at (one of the lines must be non-empty)
let mut xpos = None;
if self.previous_line.len() > 0 {
xpos = Some(self.previous_line[0].start);
}
if self.current_line.len() > 0 {
xpos = xpos.map_or(Some(self.current_line[0].start), |xpos| Some(xpos.min(self.current_line[0].start)));
}
if let Some(xpos) = xpos {
// Found the next line
self.previous_pos = 0;
self.current_pos = 0;
self.xpos = xpos;
self.ypos = ypos;
break;
}
// Try the next y position if we didn't find a match
ypos += 1.0;
if self.finished {
// No more lines in this shape
self.previous_pos = 0;
self.current_pos = 0;
self.xpos = 0;
break;
}
}
}
}
impl<TLineIterator> Iterator for InterceptScanEdgeIterator<TLineIterator>
where
TLineIterator: Iterator<Item=SmallVec<[Range<usize>; 4]>>,
{
type Item = (ContourPosition, ContourCell);
fn next(&mut self) -> Option<Self::Item> {
// Outer loop: move lines
loop {
if self.finished && self.previous_line.is_empty() {
// Stop once the ypos leaves the end of the shape and there's no previous line
return None;
}
// Inner loop: move within the current line
loop {
let xpos = self.xpos;
// The previous line specifies whether or not the upper part of the current edge is filled, and the next line specifies whether or not the previous edge is filled
let upper = self.previous_line.get(self.previous_pos);
// Move the previous pos on if the x position has exceeded the current range of filled values
if let Some(upper) = upper {
if xpos > upper.end {
self.previous_pos += 1;
continue;
}
}
let lower = self.current_line.get(self.current_pos);
// Move the current pos on if the x position has exceeded the current range of filled values
if let Some(lower) = lower {
if xpos > lower.end {
self.current_pos += 1;
continue;
}
}
// If both are beyond the end of the range, then we've finished the current edge
if upper.is_none() && lower.is_none() {
// Leaving the inner loop will move to the next line
break;
}
// If both the upper and lower lines are empty, then move to the first filled spot
if upper.map_or(true, |upper| xpos < upper.start) && lower.map_or(true, |lower| xpos < lower.start) {
match (upper, lower) {
(Some(upper), Some(lower)) => { self.xpos = upper.start.min(lower.start); }
(Some(upper), None) => { self.xpos = upper.start; }
(None, Some(lower)) => { self.xpos = lower.start; }
(None, None) => { unreachable!() } // As this case is handled above
}
continue;
}
// If both the upper and lower lines are filled, then move to the earliest end point
if upper.map_or(false, |upper| xpos > upper.start && xpos < upper.end) && lower.map_or(false, |lower| xpos > lower.start && xpos < lower.end) {
match (upper, lower) {
(Some(upper), Some(lower)) => { self.xpos = upper.end.min(lower.end); }
_ => { unreachable!() } // Because we map to 'false' if either is None: hitting the end of the range is the same as the pixel being empty
}
continue;
}
// At least one of the upper or lower lines is transitioning between filled and unfilled at the current xpos
let (tl, tr) = upper.map_or((false, false), |upper| (xpos > upper.start && xpos <= upper.end, xpos >= upper.start && xpos < upper.end));
let (bl, br) = lower.map_or((false, false), |lower| (xpos > lower.start && xpos <= lower.end, xpos >= lower.start && xpos < lower.end));
// Next iteration should look at the next cell along
self.xpos += 1;
// Found a cell to return to the caller
return Some((ContourPosition(xpos as _, self.ypos as _), ContourCell::from_corners(tl, tr, bl, br)));
}
// Read in the next line from the contour
self.load_line(self.ypos + 1.0);
}
}
}
///
/// Iterator that returns the intercepts for each line of a contour
///
pub struct ContourInterceptsIterator<'a, TContour> {
/// The contour to find the intercepts on
contour: &'a TContour,
/// The height of the contour
height: f64,
/// The current y position along the contour
ypos: f64,
}
impl<'a, TContour> ContourInterceptsIterator<'a, TContour>
where
TContour: SampledContour,
{
///
/// Creates a new iterator that will return the intercepts in a contour
///
#[inline]
pub fn new(contour: &'a TContour) -> ContourInterceptsIterator<'a, TContour> {
ContourInterceptsIterator {
contour: contour,
height: contour.contour_size().height() as _,
ypos: 0.0,
}
}
}
impl<'a, TContour> Iterator for ContourInterceptsIterator<'a, TContour>
where
TContour: SampledContour,
{
type Item = SmallVec<[Range<usize>; 4]>;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
if self.ypos >= self.height {
// Finished all the lines in the contour
None
} else {
// Get the current line
let current_line = self.contour.rounded_intercepts_on_line(self.ypos);
// Move to the next line
self.ypos += 1.0;
Some(current_line)
}
}
}