GitCorner

Code

ossartcrafteffectcraft🌐
665bfac0b339
//! The 3D Camera Tracker's analysis: structure from motion on a single clip, clean-room from the
//! textbook pipeline (Hartley & Zisserman, *Multiple View Geometry in Computer Vision*, 2nd ed.,
//! 2004; Triggs et al., "Bundle Adjustment — A Modern Synthesis", 2000):
//!
//! 1. **Feature tracks** ([`features::TrackAnalyzer`]): Shi–Tomasi corners followed through the
//!    clip with pyramidal Lucas–Kanade and a forward–backward check ([`crate::klt`]); lost
//!    features end their track and new ones are detected where the frame has none, so tracks
//!    are as long as possible.
//! 2. **Solve** ([`solve`]): keyframes are selected by parallax; a two-view reconstruction
//!    initialises the scene from either the **essential matrix** (normalised 8-point algorithm
//!    inside RANSAC, H&Z §11.2 and §9.6) or, for mostly flat scenes, a **homography
//!    decomposition** (Ma, Soatto, Košecká & Sastry, *An Invitation to 3-D Vision*, 2004, §5.3);
//!    the other keyframes are added incrementally (**resection** by robust pose refinement,
//!    **triangulation** of new tracks by the linear method of H&Z §12.2); a sparse
//!    **Levenberg–Marquardt bundle adjustment** with the Schur complement over the points
//!    ([`bundle`]) refines everything; the frames between keyframes are resected last. Inlier
//!    thresholds start from the analysis resolution and are re-estimated from the residuals
//!    (median absolute residual) once the keyframes are solved, so features on moving objects,
//!    occlusion edges and screen-locked overlays drop out.
//! 3. **Focal length**: *Specify Angle of View* fixes it; *Fixed Angle of View* searches it
//!    (the reprojection error of the keyframe reconstruction over a log-spaced range of focal
//!    lengths, refined by golden-section search) and then adjusts it in the bundle adjustment
//!    as one shared parameter; *Variable Zoom* starts from the same estimate and adjusts a focal
//!    length per frame, with a weak smoothness prior between neighbouring frames.
//! 4. **Tripod pan** shots (no camera translation) are solved as a pure rotation: frame-to-frame
//!    rotations from the tracked rays (orthogonal Procrustes) refined by the same bundle
//!    adjustment with the camera centres fixed. *Auto Detect* solves both ways and keeps the
//!    tripod solution when it explains the tracks as well as the general one (a quick rotation fit
//!    at the general solution's focal length skips the tripod search when it clearly fails).
//!
//! 5. **Lens distortion** (Solve Lens Distortion, or Detailed Analysis): radial distortion
//!    `p_d = p (1 + k1 ρ² + k2 ρ⁴)` (ρ = distance from the principal point over half the frame
//!    diagonal; Brown's model without the tangential terms) is solved jointly with the cameras
//!    and points in a final bundle adjustment on the raw tracks; the whole solve is then repeated
//!    on tracks undistorted with that estimate (the linear initialisations assume a pinhole
//!    camera) and adjusted jointly again. The solve stores `k1, k2`; the effect can undistort
//!    its output so composited 3D layers line up.
//!
//! The camera model has square pixels and the principal point at the layer centre. Camera space is x right, y down, z forward (After Effects' convention); a camera
//! is `(R, C, f)` with `X_cam = R (X − C)` and pixel `u = f x / z + w / 2`.
//!
//! The solve is stored in a canonical frame: the first solved frame's camera is at the origin
//! looking along +z, scaled so the median depth of the points it sees is 1. [`CameraSolve::world`]
//! maps it into composition space for a camera zoom, optionally re-based on a ground plane.

pub mod bundle;
pub mod features;
pub mod geometry;
pub mod linalg;
mod solver;
#[cfg(test)]
mod tests;

use serde::{Deserialize, Serialize};

pub use features::{AnalyzeOpts, TrackAnalyzer};
use linalg::{M3, Similarity, V3};
pub use solver::{SolveError, solve};

/// One feature track: positions (layer pixels) on consecutive frames from `start`.
#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct Track2D {
    pub id: u32,
    pub start: u32,
    pub pts: Vec<[f32; 2]>,
}

impl Track2D {
    /// Exclusive end frame, saturated when the track exceeds the frame index range.
    pub fn end(&self) -> u32 {
        u32::try_from(self.pts.len()).ok().and_then(|n| self.start.checked_add(n)).unwrap_or(u32::MAX)
    }
    /// Position on frame `k` when the track covers it.
    pub fn at(&self, k: u32) -> Option<[f64; 2]> {
        let i = k.checked_sub(self.start)? as usize;
        self.pts.get(i).map(|p| [p[0] as f64, p[1] as f64])
    }
}

/// The tracked features of a clip (step 1 of the analysis).
#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase", default)]
pub struct CameraTracks {
    pub version: u32,
    /// Layer size (pixels).
    pub size: [f64; 2],
    /// Layer time (seconds) of frame 0, and the frame duration.
    pub start: f64,
    pub frame_duration: f64,
    pub frames: u32,
    /// Analysis downsampling factor (image pixels per analysis pixel): the tracking noise scale.
    pub factor: f64,
    pub detailed: bool,
    pub tracks: Vec<Track2D>,
}

impl CameraTracks {
    pub fn to_json(&self) -> String {
        serde_json::to_string(self).unwrap_or_default()
    }
    pub fn from_json(s: &str) -> Option<CameraTracks> {
        if s.trim().is_empty() {
            return None;
        }
        serde_json::from_str(s).ok()
    }
    pub fn is_empty(&self) -> bool {
        self.frames == 0
    }
    pub fn track(&self, id: u32) -> Option<&Track2D> {
        self.tracks.binary_search_by_key(&id, |t| t.id).ok().map(|i| &self.tracks[i])
    }
}

/// Radial lens distortion around the principal point (see the module docs).
#[derive(Clone, Copy, Debug, Default, PartialEq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase", default)]
pub struct Distortion {
    pub k1: f64,
    pub k2: f64,
    /// Normalisation radius ρ = 1 (pixels): half the frame diagonal; 0 = no distortion.
    pub radius: f64,
}

impl Distortion {
    pub const NONE: Distortion = Distortion { k1: 0.0, k2: 0.0, radius: 0.0 };

    /// No distortion for frames of `size` (the radius set, coefficients zero).
    pub fn for_size(size: [f64; 2]) -> Distortion {
        Distortion { k1: 0.0, k2: 0.0, radius: 0.5 * size[0].hypot(size[1]) }
    }
    pub fn is_none(&self) -> bool {
        self.radius <= 0.0 || (self.k1 == 0.0 && self.k2 == 0.0)
    }
    fn rho2(&self, p: [f64; 2]) -> f64 {
        (p[0] * p[0] + p[1] * p[1]) / (self.radius * self.radius)
    }
    /// Ideal → distorted (pixels relative to the principal point).
    pub fn distort(&self, p: [f64; 2]) -> [f64; 2] {
        if self.radius <= 0.0 {
            return p;
        }
        let r2 = self.rho2(p);
        let d = 1.0 + self.k1 * r2 + self.k2 * r2 * r2;
        [p[0] * d, p[1] * d]
    }
    /// Distorted → ideal (fixed-point iteration).
    pub fn undistort(&self, q: [f64; 2]) -> [f64; 2] {
        if self.is_none() {
            return q;
        }
        let mut p = q;
        for _ in 0..30 {
            let r2 = self.rho2(p);
            let d = 1.0 + self.k1 * r2 + self.k2 * r2 * r2;
            if d.abs() < 1e-6 {
                break;
            }
            p = [q[0] / d, q[1] / d];
        }
        p
    }
    /// `d distort / d p` (2 × 2, row-major) and `d distort / d (k1, k2)` (rows x, y).
    pub fn jacobian(&self, p: [f64; 2]) -> ([[f64; 2]; 2], [[f64; 2]; 2]) {
        if self.radius <= 0.0 {
            return ([[1.0, 0.0], [0.0, 1.0]], [[0.0; 2]; 2]);
        }
        let r2 = self.rho2(p);
        let d = 1.0 + self.k1 * r2 + self.k2 * r2 * r2;
        // d(r2)/dp = 2 p / R².
        let dd = (self.k1 + 2.0 * self.k2 * r2) * 2.0 / (self.radius * self.radius);
        let j = [[d + p[0] * dd * p[0], p[0] * dd * p[1]], [p[1] * dd * p[0], d + p[1] * dd * p[1]]];
        let k = [[p[0] * r2, p[0] * r2 * r2], [p[1] * r2, p[1] * r2 * r2]];
        (j, k)
    }
}

/// 3D Camera Tracker ▸ Shot Type.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub enum ShotType {
    #[default]
    FixedAngle,
    VariableZoom,
    SpecifyAngle,
}

impl ShotType {
    pub const ALL: [ShotType; 3] = [ShotType::FixedAngle, ShotType::VariableZoom, ShotType::SpecifyAngle];
    pub fn label(self) -> &'static str {
        match self {
            ShotType::FixedAngle => "Fixed Angle of View",
            ShotType::VariableZoom => "Variable Zoom",
            ShotType::SpecifyAngle => "Specify Angle of View",
        }
    }
    pub fn from_name(s: &str) -> Option<ShotType> {
        let k = s.to_ascii_lowercase().replace([' ', '-', '_'], "");
        match k.as_str() {
            "fixed" | "fixedangle" | "fixedangleofview" => Some(ShotType::FixedAngle),
            "variable" | "variablezoom" | "zoom" => Some(ShotType::VariableZoom),
            "specify" | "specifyangle" | "specifyangleofview" => Some(ShotType::SpecifyAngle),
            _ => None,
        }
    }
}

/// 3D Camera Tracker ▸ Advanced ▸ Solve Method (and Method Used).
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub enum SolveMethod {
    #[default]
    Auto,
    Typical,
    MostlyFlat,
    TripodPan,
}

impl SolveMethod {
    pub const ALL: [SolveMethod; 4] = [SolveMethod::Auto, SolveMethod::Typical, SolveMethod::MostlyFlat, SolveMethod::TripodPan];
    pub fn label(self) -> &'static str {
        match self {
            SolveMethod::Auto => "Auto Detect",
            SolveMethod::Typical => "Typical",
            SolveMethod::MostlyFlat => "Mostly Flat Scene",
            SolveMethod::TripodPan => "Tripod Pan",
        }
    }
    pub fn from_name(s: &str) -> Option<SolveMethod> {
        let k = s.to_ascii_lowercase().replace([' ', '-', '_'], "");
        match k.as_str() {
            "auto" | "autodetect" => Some(SolveMethod::Auto),
            "typical" => Some(SolveMethod::Typical),
            "flat" | "mostlyflat" | "mostlyflatscene" => Some(SolveMethod::MostlyFlat),
            "tripod" | "tripodpan" => Some(SolveMethod::TripodPan),
            _ => None,
        }
    }
}

/// What a solve is made with.
#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase", default)]
pub struct SolveSettings {
    pub shot: ShotType,
    /// Horizontal angle of view (degrees) for [`ShotType::SpecifyAngle`].
    pub hfov: f64,
    pub method: SolveMethod,
    /// Track ids the user deleted.
    pub deleted: Vec<u32>,
    /// Solve radial lens distortion jointly with the cameras.
    pub lens_distortion: bool,
}

/// The solved camera of one frame.
#[derive(Clone, Copy, Debug, Default, PartialEq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase", default)]
pub struct SolvedFrame {
    /// World → camera rotation (axis-angle).
    pub rot: V3,
    /// Camera centre.
    pub center: V3,
    /// Focal length (layer pixels).
    pub focal: f64,
    pub solved: bool,
}

impl SolvedFrame {
    pub fn r(&self) -> M3 {
        linalg::rodrigues(self.rot)
    }
    /// Camera-space position of a world point.
    pub fn to_cam(&self, x: V3) -> V3 {
        linalg::mv(&self.r(), linalg::sub(x, self.center))
    }
    /// Project a world point to layer pixels (`None` behind the camera).
    pub fn project(&self, size: [f64; 2], x: V3) -> Option<[f64; 2]> {
        let c = self.to_cam(x);
        (c[2] > 1e-9).then(|| [self.focal * c[0] / c[2] + size[0] * 0.5, self.focal * c[1] / c[2] + size[1] * 0.5])
    }
}

/// A solved 3D track point.
#[derive(Clone, Copy, Debug, Default, PartialEq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase", default)]
pub struct SolvedPoint {
    /// The feature track it was made from.
    pub id: u32,
    pub pos: V3,
    /// Average reprojection error (pixels).
    pub error: f32,
    /// Frames `[first, last]` the point was tracked on.
    pub first: u32,
    pub last: u32,
}

/// A ground plane and origin (canonical solve coordinates).
#[derive(Clone, Copy, Debug, Default, PartialEq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase", default)]
pub struct Ground {
    pub origin: V3,
    /// Unit normal on the cameras' side ("up").
    pub normal: V3,
    /// Unit in-plane direction that becomes world +x.
    pub x_axis: V3,
}

/// A plane through solved points: After Effects' target.
#[derive(Clone, Copy, Debug, Default, PartialEq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase", default)]
pub struct Target {
    pub center: V3,
    /// Unit normal facing the camera.
    pub normal: V3,
    /// Diameter in canonical units.
    pub size: f64,
}

/// The camera solve (step 2 of the analysis).
#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase", default)]
pub struct CameraSolve {
    pub version: u32,
    pub size: [f64; 2],
    pub start: f64,
    pub frame_duration: f64,
    pub shot: ShotType,
    /// The model that was used (Auto Detect resolves to one of the others).
    pub method_used: SolveMethod,
    /// Average reprojection error (pixels) over all solved observations.
    pub average_error: f64,
    pub frames: Vec<SolvedFrame>,
    pub points: Vec<SolvedPoint>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub ground: Option<Ground>,
    /// The solved lens distortion (Solve Lens Distortion).
    #[serde(skip_serializing_if = "Option::is_none")]
    pub distortion: Option<Distortion>,
}

impl CameraSolve {
    pub fn to_json(&self) -> String {
        serde_json::to_string(self).unwrap_or_default()
    }
    pub fn from_json(s: &str) -> Option<CameraSolve> {
        if s.trim().is_empty() {
            return None;
        }
        serde_json::from_str(s).ok()
    }
    pub fn is_empty(&self) -> bool {
        self.frames.is_empty()
    }
    /// Frame index at a layer time (held at the ends).
    pub fn frame_at(&self, layer_time: f64) -> Option<usize> {
        if self.frames.is_empty() || self.frame_duration <= 0.0 {
            return None;
        }
        let i = ((layer_time - self.start) / self.frame_duration).round();
        Some(i.clamp(0.0, (self.frames.len() - 1) as f64) as usize)
    }
    pub fn point(&self, id: u32) -> Option<&SolvedPoint> {
        self.points.iter().find(|p| p.id == id)
    }
    /// Points tracked on frame `k`.
    pub fn visible(&self, k: usize) -> impl Iterator<Item = &SolvedPoint> {
        let k = k as u32;
        self.points.iter().filter(move |p| p.first <= k && k <= p.last)
    }
    /// Median focal length of the solved frames (layer pixels).
    pub fn focal(&self) -> f64 {
        let mut f: Vec<f64> = self.frames.iter().filter(|c| c.solved).map(|c| c.focal).collect();
        if f.is_empty() {
            return 0.0;
        }
        f.sort_by(f64::total_cmp);
        f[f.len() / 2]
    }
    /// Horizontal angle of view (degrees) of focal length `f`.
    pub fn hfov(&self, f: f64) -> f64 {
        2.0 * (self.size[0] * 0.5 / f.max(1e-9)).atan().to_degrees()
    }

    /// The plane through points `ids` seen from frame `k` (needs three points; with more the
    /// plane is a least-squares fit).
    pub fn target(&self, ids: &[u32], k: usize) -> Option<Target> {
        let pts: Vec<V3> = ids.iter().filter_map(|i| self.point(*i)).map(|p| p.pos).collect();
        let cam = self.frames.get(k).filter(|c| c.solved).or_else(|| self.frames.iter().find(|c| c.solved))?;
        geometry::fit_plane(&pts).map(|(c, mut n, spread)| {
            if linalg::dot(n, linalg::sub(cam.center, c)) < 0.0 {
                n = linalg::scale(n, -1.0);
            }
            // After Effects sizes the target from the camera distance when the points are close.
            let depth = linalg::norm(linalg::sub(cam.center, c));
            Target { center: c, normal: n, size: (spread * 2.0).max(depth * 0.12) }
        })
    }

    /// A ground plane through `ids` (origin at their centroid, normal towards frame `k`'s
    /// camera, +x along that camera's right vector projected on the plane).
    pub fn ground_from(&self, ids: &[u32], k: usize) -> Option<Ground> {
        let t = self.target(ids, k)?;
        let cam = self.frames.get(k).filter(|c| c.solved).or_else(|| self.frames.iter().find(|c| c.solved))?;
        let right = linalg::mtv(&cam.r(), [1.0, 0.0, 0.0]);
        let mut x = linalg::sub(right, linalg::scale(t.normal, linalg::dot(right, t.normal)));
        if linalg::norm(x) < 1e-6 {
            let fwd = linalg::mtv(&cam.r(), [0.0, 0.0, 1.0]);
            x = linalg::cross(fwd, t.normal);
        }
        Some(Ground { origin: t.center, normal: t.normal, x_axis: linalg::normalize(x) })
    }

    /// Canonical solve coordinates → composition world, for a camera whose zoom on the first
    /// solved frame is `zoom0` (comp pixels) in a `comp` sized composition. Without a ground
    /// plane, the first solved frame's camera becomes After Effects' default camera (at
    /// `(w/2, h/2, −zoom)` looking down +z, so points at the median depth land near z = 0). With
    /// one, the ground plane becomes the X-Z plane through the origin, normal along −y (up).
    pub fn world(&self, comp: [f64; 2], zoom0: f64) -> Similarity {
        match &self.ground {
            Some(g) => {
                // Rows: canonical directions that map to world x, y, z.
                let y = linalg::scale(g.normal, -1.0);
                let x = g.x_axis;
                let z = linalg::cross(x, y);
                let r = [x, y, z];
                let t = linalg::scale(linalg::mv(&r, g.origin), -zoom0);
                Similarity { s: zoom0, r, t }
            }
            None => Similarity { s: zoom0, r: linalg::I3, t: [comp[0] * 0.5, comp[1] * 0.5, -zoom0] },
        }
    }

    /// An ideal (pinhole) image point → where it appears in the footage (layer pixels), through
    /// the solved lens distortion.
    pub fn to_image(&self, p: [f64; 2]) -> [f64; 2] {
        match &self.distortion {
            Some(d) if !d.is_none() => {
                let c = [self.size[0] * 0.5, self.size[1] * 0.5];
                let q = d.distort([p[0] - c[0], p[1] - c[1]]);
                [q[0] + c[0], q[1] + c[1]]
            }
            _ => p,
        }
    }
    /// A footage point → its ideal (undistorted) position.
    pub fn to_ideal(&self, p: [f64; 2]) -> [f64; 2] {
        match &self.distortion {
            Some(d) if !d.is_none() => {
                let c = [self.size[0] * 0.5, self.size[1] * 0.5];
                let q = d.undistort([p[0] - c[0], p[1] - c[1]]);
                [q[0] + c[0], q[1] + c[1]]
            }
            _ => p,
        }
    }
    /// Project world point `x` on frame `k`: through the lens distortion into the footage, or
    /// (`undistorted`) into the undistorted image.
    pub fn project(&self, k: usize, x: V3, undistorted: bool) -> Option<[f64; 2]> {
        let q = self.frames.get(k)?.project(self.size, x)?;
        Some(if undistorted { q } else { self.to_image(q) })
    }

    /// The first solved frame.
    pub fn first_solved(&self) -> Option<usize> {
        self.frames.iter().position(|c| c.solved)
    }
}

/// Deterministic colour of a track point (After Effects draws each target in its own colour).
pub fn point_color(id: u32) -> [f32; 3] {
    let mut h = id.wrapping_mul(0x9E37_79B9) ^ 0x5bd1_e995;
    h ^= h >> 15;
    let hue = (h % 360) as f32 / 60.0;
    let x = 1.0 - (hue % 2.0 - 1.0).abs();
    let (r, g, b) = match hue as u32 {
        0 => (1.0, x, 0.0),
        1 => (x, 1.0, 0.0),
        2 => (0.0, 1.0, x),
        3 => (0.0, x, 1.0),
        4 => (x, 0.0, 1.0),
        _ => (1.0, 0.0, x),
    };
    // Bright, slightly desaturated.
    [0.25 + 0.75 * r, 0.25 + 0.75 * g, 0.25 + 0.75 * b]
}

#[cfg(test)]
mod validation_tests {
    use super::*;

    fn tracks() -> CameraTracks {
        CameraTracks { size: [1920.0, 1080.0], factor: 1.0, frame_duration: 1.0 / 30.0, frames: 3, ..Default::default() }
    }

    #[test]
    fn track_end_saturates_instead_of_wrapping() {
        assert_eq!(Track2D { start: u32::MAX, pts: vec![[0.0; 2]], ..Default::default() }.end(), u32::MAX);
        assert_eq!(Track2D { start: 3, pts: vec![[0.0; 2]; 2], ..Default::default() }.end(), 5);
    }

    #[test]
    fn solve_rejects_large_frame_count_before_allocating() {
        let t = CameraTracks { frames: u32::MAX, ..tracks() };
        let error = solve(&t, &SolveSettings::default(), None).unwrap_err();
        assert!(error.0.contains("frame or track count"));
    }

    #[test]
    fn solve_rejects_overflowing_and_out_of_clip_tracks() {
        for start in [u32::MAX, 2] {
            let t = CameraTracks { tracks: vec![Track2D { start, pts: vec![[0.0; 2]; 3], ..Default::default() }], ..tracks() };
            let error = solve(&t, &SolveSettings::default(), None).unwrap_err();
            assert!(error.0.contains("frame range"));
        }
    }

    #[test]
    fn solve_rejects_non_finite_track_positions() {
        let t = CameraTracks { tracks: vec![Track2D { pts: vec![[f32::NAN, 0.0]; 3], ..Default::default() }], ..tracks() };
        let error = solve(&t, &SolveSettings::default(), None).unwrap_err();
        assert!(error.0.contains("finite"));
    }

    #[test]
    fn solve_rejects_invalid_dimensions_timing_and_scale() {
        for t in [
            CameraTracks { size: [f64::NAN, 1080.0], ..tracks() },
            CameraTracks { frame_duration: 0.0, ..tracks() },
            CameraTracks { factor: f64::INFINITY, ..tracks() },
        ] {
            assert!(solve(&t, &SolveSettings::default(), None).is_err());
        }
    }
}