collective
Browse / github.com/storytold/effectcraft / patch
Face tracker: find polygon crossings once per window row
track: Face tracker: point-in-polygon test per window pixel (about 67 % of tracking time) ## Problem `face.rs:860-867`: `inside_polygon` (48 edges) runs for every non-skin pixel of the window (about 650 k pixels for a 237 px face, about 25 M edge tests per frame). It is about 67 % of classical face-tracking time. Also `to_face` calls `sin_cos` per blob pixel (`face.rs:881`) and `win.px` does a bounds-checked `Image::get` twice per pixel. ## Proposal Per window row compute the 48 edge crossings once with the same expression as `mask::inside_polygon`; a pixel's parity is the count of crossings with `x_cross > px`. Limit the loop to the polygon's bounding box. Hoist `sin_cos` out of
- Status
- open
- Score
- 0.00
- Adopters
- 0 other operators
- Author
- vangel76 (imported from pull request #2334, open)
- Base
991904888a20b7da72b2a4880b21c7d912154736- Size
- +79 −11 in 1 file
- Review
- pending
- Shared
- 2026-10-28
- Id
a76588bca5f5b76de3188d15
How it went
No other operator has reported using it yet.
Diff
raw · crates/track/src/face.rs
@@ -186,9 +186,16 @@ fn to_layer(c: [f64; 2], b: f64, roll_deg: f64, q: [f64; 2]) -> [f64; 2] { /// Layer pixels → face frame. fn to_face(c: [f64; 2], b: f64, roll_deg: f64, p: [f64; 2]) -> [f64; 2] {+ face_mapper(c, b, roll_deg)(p)+}++/// [`to_face`] with the rotation worked out once, for mapping many points.+fn face_mapper(c: [f64; 2], b: f64, roll_deg: f64) -> impl Fn([f64; 2]) -> [f64; 2] { let (sn, cs) = roll_deg.to_radians().sin_cos();- let d = [(p[0] - c[0]) / b, (p[1] - c[1]) / b];- [cs * d[0] + sn * d[1], -sn * d[0] + cs * d[1]]+ move |p| {+ let d = [(p[0] - c[0]) / b, (p[1] - c[1]) / b];+ [cs * d[0] + sn * d[1], -sn * d[0] + cs * d[1]]+ } } /// A synthetic face's landmarks in layer pixels.@@ -578,6 +585,44 @@ impl Window { } } +/// Per pixel of a `w × h` window: not skin and inside `poly` (even-odd rule, same comparisons as+/// [`crate::mask::inside_polygon`] at `layer(i, j)`). A scanline crosses the polygon at the same+/// edges for every pixel of a row, so the crossings are found once per row and each pixel's+/// parity follows from how many lie right of it.+fn non_skin_inside(poly: &[[f64; 2]], skin: &[bool], layer: impl Fn(usize, usize) -> [f64; 2], w: usize, h: usize) -> Vec<bool> {+ let mut feat = vec![false; w * h];+ let n = poly.len();+ if n < 3 {+ return feat;+ }+ let mut xs: Vec<f64> = Vec::with_capacity(n);+ for j in 0..h {+ let y = layer(0, j)[1];+ xs.clear();+ let mut prev = poly[n - 1];+ for &cur in poly {+ let (a, b) = (cur, prev);+ if (a[1] > y) != (b[1] > y) {+ xs.push((b[0] - a[0]) * (y - a[1]) / (b[1] - a[1]) + a[0]);+ }+ prev = cur;+ }+ if xs.is_empty() {+ continue;+ }+ xs.sort_by(f64::total_cmp);+ let mut left = 0;+ for i in 0..w {+ let x = layer(i, j)[0];+ while left < xs.len() && xs[left] <= x {+ left += 1;+ }+ feat[j * w + i] = (xs.len() - left) % 2 == 1 && !skin[j * w + i];+ }+ }+ feat+}+ fn median(v: &mut [f32]) -> f32 { v.sort_by(f32::total_cmp); v[v.len() / 2]@@ -857,18 +902,12 @@ impl FaceTracker { let b = major; // Non-skin components inside the face outline (shrunk a little: anti-aliased edges). let inner: Vec<[f64; 2]> = outline.iter().map(|p| [center[0] + 0.9 * (p[0] - center[0]), center[1] + 0.9 * (p[1] - center[1])]).collect();- let mut feat = vec![false; w * h];- for j in 0..h {- for i in 0..w {- if !skin[j * w + i] && crate::mask::inside_polygon(&inner, win.layer(frame, i, j)) {- feat[j * w + i] = true;- }- }- }+ let feat = non_skin_inside(&inner, &skin, |i, j| win.layer(frame, i, j), w, h); let min_area = (0.0006 * b * b).max(2.0) as usize; let mut seen = vec![false; w * h]; let mut blobs: Vec<Blob> = vec![]; let skin_luma = self.skin.med[0] as f64;+ let to_face = face_mapper(center, b, roll); for j0 in 0..h { for i0 in 0..w { if !feat[j0 * w + i0] || seen[j0 * w + i0] {@@ -878,7 +917,7 @@ impl FaceTracker { seen[j0 * w + i0] = true; let mut pts = vec![]; while let Some((i, j)) = st.pop() {- let q = to_face(center, b, roll, win.layer(frame, i, j));+ let q = to_face(win.layer(frame, i, j)); pts.push((q, skin_luma - luma[j * w + i] as f64)); for dj in -1i64..=1 { for di in -1i64..=1 {@@ -1174,6 +1213,35 @@ mod tests { assert!(err < 0.06 * 50.0, "max error {err}"); } + #[test]+ fn row_crossings_match_the_point_in_polygon_test() {+ let (w, h) = (97, 83);+ let off = [13.0, 7.0];+ let layer = |i: usize, j: usize| [(20 + i) as f64 + 0.5 - off[0] + 0.25, (11 + j) as f64 + 0.5 - off[1]];+ let star: Vec<[f64; 2]> = (0..48)+ .map(|k| {+ let a = k as f64 / 48.0 * std::f64::consts::TAU;+ let r = 30.0 + 9.0 * (5.0 * a).sin() + 3.0 * (k % 3) as f64;+ [50.0 + a.cos() * r, 40.0 + a.sin() * r * 1.3]+ })+ .collect();+ // Vertices on pixel-centre rows and columns exercise the tie cases.+ let tied: Vec<[f64; 2]> = vec![[10.0, 5.0], [70.0, 5.0], [70.0, 60.5], [40.0, 30.5], [10.0, 60.5], [10.0, 5.0]];+ for poly in [star, tied, vec![[1.0, 1.0], [5.0, 5.0]]] {+ let skin: Vec<bool> = (0..w * h).map(|i| (i * 7 + i / w) % 5 == 0).collect();+ let got = non_skin_inside(&poly, &skin, layer, w, h);+ let mut inside = 0;+ for j in 0..h {+ for i in 0..w {+ let want = !skin[j * w + i] && crate::mask::inside_polygon(&poly, layer(i, j));+ assert_eq!(got[j * w + i], want, "({i}, {j})");+ inside += want as usize;+ }+ }+ assert!(inside > 0 || poly.len() < 3);+ }+ }+ #[test] fn tracks_a_moving_rotating_synthetic_face() { let (w, h) = (320, 240);