del_geo_core/
tri2_scanline.rs

1pub struct TriangleScanlineIter {
2    v0: [f32; 2],
3    v1: [f32; 2],
4    v2: [f32; 2],
5
6    // 現在の走査線
7    py: i32,
8    y_end: i32,
9
10    // 現在のスキャンライン内の x 範囲
11    cur_x: i32,
12    x_end: i32,
13
14    // 今のスキャンラインが有効か
15    has_span: bool,
16}
17
18impl TriangleScanlineIter {
19    pub fn new(v0: [f32; 2], v1: [f32; 2], v2: [f32; 2]) -> Self {
20        let min_y = v0[1].min(v1[1]).min(v2[1]);
21        let max_y = v0[1].max(v1[1]).max(v2[1]);
22
23        let py_start = (min_y - 0.5).ceil() as i32;
24        let py_end = (max_y - 0.5).floor() as i32;
25
26        Self {
27            v0,
28            v1,
29            v2,
30            py: py_start,
31            y_end: py_end,
32            cur_x: 0,
33            x_end: -1,
34            has_span: false,
35        }
36    }
37
38    fn edge_intersect(p0: [f32; 2], p1: [f32; 2], y: f32) -> Option<f32> {
39        if (p1[1] - p0[1]).abs() < f32::EPSILON {
40            return None;
41        }
42        let ymin = p0[1].min(p1[1]);
43        let ymax = p0[1].max(p1[1]);
44
45        if y < ymin || y >= ymax {
46            return None;
47        }
48
49        let t = (y - p0[1]) / (p1[1] - p0[1]);
50        Some(p0[0] + t * (p1[0] - p0[0]))
51    }
52
53    fn setup_span(&mut self) {
54        self.has_span = false;
55
56        while self.py <= self.y_end {
57            let scan_y = self.py as f32 + 0.5;
58            let mut xs = [0.0f32; 3];
59            let mut count = 0;
60
61            if let Some(x) = Self::edge_intersect(self.v0, self.v1, scan_y) {
62                xs[count] = x;
63                count += 1;
64            }
65            if let Some(x) = Self::edge_intersect(self.v1, self.v2, scan_y) {
66                xs[count] = x;
67                count += 1;
68            }
69            if let Some(x) = Self::edge_intersect(self.v2, self.v0, scan_y) {
70                xs[count] = x;
71                count += 1;
72            }
73
74            if count >= 2 {
75                xs[..count].sort_by(|a, b| a.partial_cmp(b).unwrap());
76
77                let x_left = xs[0];
78                let x_right = xs[count - 1];
79
80                // pixel (ix, iy) is covered if its center (ix+0.5, iy+0.5) is inside the triangle.
81                // A pixel ix is covered on this scanline when ix+0.5 is in [x_left, x_right],
82                // i.e. ix >= ceil(x_left - 0.5) and ix <= floor(x_right - 0.5).
83                // NOTE: f32 edge-intersection rounding can make x_right land just below the
84                // true boundary (e.g. 114.49999 instead of 114.5), silently dropping a boundary
85                // pixel. Add a small epsilon before flooring if that matters to the caller.
86                let x_start = (x_left - 0.5).ceil() as i32;
87                let x_end = (x_right - 0.5).floor() as i32;
88
89                if x_start <= x_end {
90                    self.cur_x = x_start;
91                    self.x_end = x_end;
92                    self.has_span = true;
93                    return;
94                }
95            }
96
97            self.py += 1;
98        }
99    }
100}
101
102impl Iterator for TriangleScanlineIter {
103    type Item = [i32; 2];
104
105    fn next(&mut self) -> Option<Self::Item> {
106        loop {
107            if self.has_span && self.cur_x <= self.x_end {
108                let px = self.cur_x;
109                let py = self.py;
110                self.cur_x += 1;
111                return Some([px, py]);
112            }
113
114            // 次のスキャンラインへ
115            self.py += if self.has_span { 1 } else { 0 };
116            self.setup_span();
117
118            if !self.has_span {
119                return None;
120            }
121        }
122    }
123}
124
125#[test]
126fn test0() {
127    let v0 = [2.0f32, 1.0];
128    let v1 = [8.0f32, 3.0];
129    let v2 = [4.0f32, 7.0];
130
131    use std::collections::HashSet;
132    let sign = crate::tri2::area(&v0, &v1, &v2).signum();
133    let pixels_inside: HashSet<_> = TriangleScanlineIter::new(v0, v1, v2).collect();
134    for p in &pixels_inside {
135        let q = [p[0] as f32 + 0.5, p[1] as f32 + 0.5];
136        assert!(crate::tri2::is_inside(&v0, &v1, &v2, &q, sign).is_some());
137    }
138
139    let pixels_outside: HashSet<[i32; 2]> = pixels_inside
140        .iter()
141        .flat_map(|p| {
142            [
143                [p[0] - 1, p[1]],
144                [p[0] + 1, p[1]],
145                [p[0], p[1] - 1],
146                [p[0], p[1] + 1],
147            ]
148        })
149        .filter(|p| !pixels_inside.contains(p))
150        .collect();
151    for p in &pixels_outside {
152        let q = [p[0] as f32 + 0.5, p[1] as f32 + 0.5];
153        assert!(
154            crate::tri2::is_inside(&v0, &v1, &v2, &q, sign).is_none(),
155            "adjacent pixel ({},{}) is inside the triangle",
156            p[0],
157            p[1]
158        );
159    }
160}
del_geo_core/tri2_scanline.rs

del_geo_core/
tri2_scanline.rs
