oxiphysics_collision/recast/
mod.rs

1// Copyright 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3
4//! Recast-equivalent navmesh construction from triangle soup.
5//!
6//! Pipeline: rasterize → filter walkable → compact → regions → contours → polymesh → NavMesh
7//!
8//! **v0.1 limitations:** no detail mesh, no tile partitioning, no off-mesh connections.
9//! Long narrow corridors (width < 2*cell_size) may produce empty regions (known limitation).
10
11pub mod compact;
12pub mod contour;
13pub mod polymesh;
14pub mod rasterize;
15pub mod region;
16pub mod walkable;
17
18use crate::recast::polymesh::PolyMesh;
19
20/// Configuration for the Recast pipeline.
21#[derive(Debug, Clone)]
22pub struct RecastConfig {
23    /// Voxel size in world units (XZ dimensions). Default: 0.3
24    pub cell_size: f64,
25    /// Voxel height in world units (Y dimension). Default: 0.2
26    pub cell_height: f64,
27    /// Agent height (minimum clearance above walkable surface). Default: 2.0
28    pub agent_height: f64,
29    /// Agent radius. Default: 0.6
30    pub agent_radius: f64,
31    /// Maximum height step an agent can climb. Default: 0.9
32    pub agent_max_climb: f64,
33    /// Maximum slope angle (degrees) walkable surfaces can have. Default: 45.0
34    pub agent_max_slope: f64,
35    /// Minimum number of cells per region. Default: 8
36    pub region_min_size: usize,
37    /// Size threshold for region merging. Default: 20
38    pub region_merge_size: usize,
39    /// Maximum contour edge length. Default: 12.0
40    pub edge_max_len: f64,
41    /// Maximum contour simplification error. Default: 1.3
42    pub edge_max_error: f64,
43    /// Maximum vertices per polygon. Default: 6
44    pub max_verts_per_poly: usize,
45}
46
47impl Default for RecastConfig {
48    fn default() -> Self {
49        Self {
50            cell_size: 0.3,
51            cell_height: 0.2,
52            agent_height: 2.0,
53            agent_radius: 0.6,
54            agent_max_climb: 0.9,
55            agent_max_slope: 45.0,
56            region_min_size: 8,
57            region_merge_size: 20,
58            edge_max_len: 12.0,
59            edge_max_error: 1.3,
60            max_verts_per_poly: 6,
61        }
62    }
63}
64
65/// Error type for Recast pipeline.
66#[derive(Debug)]
67pub enum RecastError {
68    EmptyInput,
69    RasterizationFailed(String),
70    RegionBuildFailed(String),
71    ContourBuildFailed(String),
72    PolyMeshBuildFailed(String),
73}
74
75impl std::fmt::Display for RecastError {
76    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
77        match self {
78            RecastError::EmptyInput => write!(f, "input triangle soup is empty"),
79            RecastError::RasterizationFailed(s) => write!(f, "rasterization failed: {s}"),
80            RecastError::RegionBuildFailed(s) => write!(f, "region build failed: {s}"),
81            RecastError::ContourBuildFailed(s) => write!(f, "contour build failed: {s}"),
82            RecastError::PolyMeshBuildFailed(s) => write!(f, "poly mesh build failed: {s}"),
83        }
84    }
85}
86
87impl std::error::Error for RecastError {}
88
89/// The main navmesh builder.
90pub struct RecastBuilder {
91    pub config: RecastConfig,
92}
93
94impl RecastBuilder {
95    pub fn new(config: RecastConfig) -> Self {
96        Self { config }
97    }
98
99    pub fn with_default_config() -> Self {
100        Self::new(RecastConfig::default())
101    }
102
103    /// Run the full pipeline and return a `PolyMesh`.
104    ///
105    /// The caller is responsible for converting `PolyMesh` to the application's
106    /// `NavMesh` type using `polymesh::poly_mesh_to_nav_mesh_primitives`.
107    pub fn build(&self, tris: &[[f64; 9]]) -> Result<PolyMesh, RecastError> {
108        if tris.is_empty() {
109            return Err(RecastError::EmptyInput);
110        }
111
112        // Stage 1: Rasterize into heightfield
113        let mut hf = rasterize::rasterize_triangles(tris, &self.config)
114            .map_err(RecastError::RasterizationFailed)?;
115
116        // Stage 2: Filter walkable spans
117        walkable::filter_low_hanging_obstacles(&mut hf, &self.config);
118        walkable::filter_ledge_spans(&mut hf, &self.config);
119        walkable::filter_walkable_low_height(&mut hf, &self.config);
120
121        // Stage 3: Compact heightfield
122        let chf = compact::build_compact_heightfield(&hf, &self.config);
123
124        // Stage 4: Build regions
125        let rhf =
126            region::build_regions(&chf, &self.config).map_err(RecastError::RegionBuildFailed)?;
127
128        // Stage 5: Build contours
129        let cs = contour::build_contours(&rhf, &chf, &self.config)
130            .map_err(RecastError::ContourBuildFailed)?;
131
132        // Stage 6: Build polygon mesh
133        let pm = polymesh::build_poly_mesh(&cs, &self.config)
134            .map_err(RecastError::PolyMeshBuildFailed)?;
135
136        Ok(pm)
137    }
138}
oxiphysics_collision/recast/mod.rs

oxiphysics_collision/recast/
mod.rs
