spatialrust_interchange/tiles3d/
builder.rs

1//! Deterministic octree 3D Tiles 1.1 tileset builder for point data.
2//!
3//! The builder splits an input point set into an octree whose nodes become
4//! tiles. Each tile carries a `pnts` payload with a per-tile `RTC_CENTER` so
5//! `f32` precision is retained far from the coordinate origin. Split order is
6//! deterministic (fixed octant bit order) and internal geometric error halves
7//! each level, so the same input and options always produce the same tree.
8
9use std::path::Path;
10
11use crate::tiles3d::pnts::{encode_pnts, PntsFeatureTable};
12use crate::tiles3d::tileset::{
13    serialize_tileset_json, BoundingVolume, Refinement, Tile, TileContent, Tileset,
14};
15use crate::{InterchangeError, InterchangeResult};
16
17const OCTANTS: usize = 8;
18const BITS: [u8; 8] = [0b000, 0b001, 0b010, 0b011, 0b100, 0b101, 0b110, 0b111];
19
20/// Options controlling octree construction.
21#[derive(Clone, Debug)]
22pub struct TilesetBuilderOptions {
23    /// Maximum points materialized per tile before the node splits.
24    pub max_points_per_tile: usize,
25    /// Maximum octree depth; nodes at this depth never split.
26    pub max_depth: u32,
27    /// Root geometric error; defaults to the root bounds diagonal when `None`.
28    pub root_geometric_error: Option<f64>,
29    /// Multiplier applied to the parent geometric error for each child level.
30    pub geometric_error_scale: f64,
31    /// Refinement policy recorded on the root tile.
32    pub refine: Refinement,
33}
34
35impl Default for TilesetBuilderOptions {
36    fn default() -> Self {
37        Self {
38            max_points_per_tile: 100_000,
39            max_depth: 12,
40            root_geometric_error: None,
41            geometric_error_scale: 0.5,
42            refine: Refinement::Replace,
43        }
44    }
45}
46
47impl TilesetBuilderOptions {
48    fn validate(&self) -> InterchangeResult<()> {
49        if self.max_points_per_tile == 0 {
50            return Err(InterchangeError::InvalidConfiguration(
51                "max_points_per_tile must be positive".into(),
52            ));
53        }
54        if let Some(error) = self.root_geometric_error {
55            if !error.is_finite() || error < 0.0 {
56                return Err(InterchangeError::InvalidConfiguration(
57                    "root_geometric_error must be finite and non-negative".into(),
58                ));
59            }
60        }
61        if !self.geometric_error_scale.is_finite()
62            || !(0.0..=1.0).contains(&self.geometric_error_scale)
63        {
64            return Err(InterchangeError::InvalidConfiguration(
65                "geometric_error_scale must be within [0, 1]".into(),
66            ));
67        }
68        Ok(())
69    }
70}
71
72/// One generated tile payload paired with its content URI.
73#[derive(Clone, Debug, PartialEq)]
74pub struct BuiltTile {
75    /// Content URI relative to `tileset.json`.
76    pub uri: String,
77    /// Encoded `pnts` payload.
78    pub pnts: Vec<u8>,
79    /// Points materialized by this tile.
80    pub point_count: usize,
81}
82
83/// A validated tileset plus its `pnts` payloads.
84#[derive(Clone, Debug)]
85pub struct BuiltTileset {
86    /// Serialized tileset document.
87    pub tileset: Tileset,
88    /// Tile payloads in deterministic content order.
89    pub tiles: Vec<BuiltTile>,
90}
91
92/// Builds a deterministic octree tileset from interleaved positions.
93///
94/// `positions` holds `N*3` interleaved `x,y,z` values; `rgb` optionally holds
95/// `N*3` interleaved bytes. Positions must all be finite.
96pub fn build_point_tileset(
97    positions: &[f32],
98    rgb: Option<&[u8]>,
99    options: &TilesetBuilderOptions,
100) -> InterchangeResult<BuiltTileset> {
101    options.validate()?;
102    if positions.is_empty() || positions.len() % 3 != 0 {
103        return Err(InterchangeError::InvalidConfiguration(
104            "point positions must be a non-empty multiple of 3".into(),
105        ));
106    }
107    let point_count = positions.len() / 3;
108    if let Some(rgb) = rgb {
109        if rgb.len() != point_count * 3 {
110            return Err(InterchangeError::InvalidConfiguration(
111                "RGB length must equal three times the point count".into(),
112            ));
113        }
114    }
115    if positions.iter().any(|value| !value.is_finite()) {
116        return Err(InterchangeError::InvalidConfiguration(
117            "point positions must contain finite values".into(),
118        ));
119    }
120
121    let (min, max) = compute_bounds(positions);
122    let mut indices: Vec<u32> = (0..point_count).map(|index| index as u32).collect();
123    let root_error = options.root_geometric_error.unwrap_or_else(|| bounds_diagonal(min, max));
124    let node = build_node(&mut indices, min, max, root_error, options, positions)?;
125
126    let mut tiles = Vec::new();
127    let mut tileset_root = materialize(node, positions, rgb, &mut tiles)?;
128    tileset_root.geometric_error = root_error;
129    tileset_root.refine = Some(options.refine);
130
131    Ok(BuiltTileset { tileset: Tileset { geometric_error: root_error, root: tileset_root }, tiles })
132}
133
134/// Writes a built tileset to `dir` as `tileset.json` plus one `.pnts` file per tile.
135pub fn write_point_tileset(
136    dir: impl AsRef<Path>,
137    built: &BuiltTileset,
138) -> InterchangeResult<TilesetWriteReceipt> {
139    let dir = dir.as_ref();
140    std::fs::create_dir_all(dir).map_err(io_error)?;
141    let document = serialize_tileset_json(&built.tileset)?;
142    std::fs::write(dir.join("tileset.json"), document.as_bytes()).map_err(io_error)?;
143
144    let mut tile_count = 0u64;
145    let mut point_count = 0u64;
146    let mut pnts_bytes = 0u64;
147    for tile in &built.tiles {
148        std::fs::write(dir.join(&tile.uri), &tile.pnts).map_err(io_error)?;
149        tile_count += 1;
150        point_count = point_count
151            .checked_add(tile.point_count as u64)
152            .ok_or_else(|| InterchangeError::InvalidConfiguration("point count overflow".into()))?;
153        pnts_bytes = pnts_bytes.checked_add(tile.pnts.len() as u64).ok_or_else(|| {
154            InterchangeError::InvalidConfiguration("pnts byte count overflow".into())
155        })?;
156    }
157    Ok(TilesetWriteReceipt {
158        tileset_json_bytes: document.len() as u64,
159        tile_count,
160        point_count,
161        pnts_bytes,
162    })
163}
164
165/// Receipt for a written 3D Tiles tileset.
166#[derive(Clone, Copy, Debug, PartialEq, Eq)]
167pub struct TilesetWriteReceipt {
168    /// Bytes written for `tileset.json`.
169    pub tileset_json_bytes: u64,
170    /// Number of `pnts` tile files written.
171    pub tile_count: u64,
172    /// Total points across all tiles.
173    pub point_count: u64,
174    /// Total bytes across all `pnts` payloads.
175    pub pnts_bytes: u64,
176}
177
178struct Node {
179    min: [f64; 3],
180    max: [f64; 3],
181    geometric_error: f64,
182    points: Vec<u32>,
183    children: Vec<Node>,
184}
185
186fn build_node(
187    indices: &mut Vec<u32>,
188    min: [f64; 3],
189    max: [f64; 3],
190    geometric_error: f64,
191    options: &TilesetBuilderOptions,
192    positions: &[f32],
193) -> InterchangeResult<Node> {
194    let leaf = indices.len() <= options.max_points_per_tile;
195    if leaf || indices.is_empty() {
196        return Ok(Node {
197            min,
198            max,
199            geometric_error: 0.0,
200            points: std::mem::take(indices),
201            children: Vec::new(),
202        });
203    }
204
205    let center = [(min[0] + max[0]) * 0.5, (min[1] + max[1]) * 0.5, (min[2] + max[2]) * 0.5];
206
207    let mut buckets: [Vec<u32>; OCTANTS] = std::array::from_fn(|_| Vec::new());
208    for &point in indices.iter() {
209        let index = point as usize;
210        let x = f64::from(positions[index * 3]);
211        let y = f64::from(positions[index * 3 + 1]);
212        let z = f64::from(positions[index * 3 + 2]);
213        let mut octant = 0u8;
214        if x >= center[0] {
215            octant |= 0b100;
216        }
217        if y >= center[1] {
218            octant |= 0b010;
219        }
220        if z >= center[2] {
221            octant |= 0b001;
222        }
223        buckets[octant as usize].push(point);
224    }
225    indices.clear();
226
227    let child_error = geometric_error * options.geometric_error_scale;
228    let mut children = Vec::new();
229    for (octant_index, bucket) in buckets.iter_mut().enumerate() {
230        if bucket.is_empty() {
231            continue;
232        }
233        let bits = BITS[octant_index];
234        let child_min = [
235            if bits & 0b100 != 0 { center[0] } else { min[0] },
236            if bits & 0b010 != 0 { center[1] } else { min[1] },
237            if bits & 0b001 != 0 { center[2] } else { min[2] },
238        ];
239        let child_max = [
240            if bits & 0b100 != 0 { max[0] } else { center[0] },
241            if bits & 0b010 != 0 { max[1] } else { center[1] },
242            if bits & 0b001 != 0 { max[2] } else { center[2] },
243        ];
244        let child = build_node(bucket, child_min, child_max, child_error, options, positions)?;
245        if !child.points.is_empty() || !child.children.is_empty() {
246            children.push(child);
247        }
248    }
249
250    Ok(Node { min, max, geometric_error, points: Vec::new(), children })
251}
252
253fn materialize(
254    node: Node,
255    positions: &[f32],
256    rgb: Option<&[u8]>,
257    tiles: &mut Vec<BuiltTile>,
258) -> InterchangeResult<Tile> {
259    let center = [
260        (node.min[0] + node.max[0]) * 0.5,
261        (node.min[1] + node.max[1]) * 0.5,
262        (node.min[2] + node.max[2]) * 0.5,
263    ];
264
265    let mut content = None;
266    if !node.points.is_empty() {
267        let mut local_positions = Vec::with_capacity(node.points.len() * 3);
268        for &point in &node.points {
269            let index = point as usize;
270            local_positions.push(positions[index * 3] - center[0] as f32);
271            local_positions.push(positions[index * 3 + 1] - center[1] as f32);
272            local_positions.push(positions[index * 3 + 2] - center[2] as f32);
273        }
274        let tile_rgb = rgb.map(|rgb| {
275            node.points
276                .iter()
277                .flat_map(|&point| {
278                    let index = point as usize * 3;
279                    rgb[index..index + 3].to_vec()
280                })
281                .collect::<Vec<u8>>()
282        });
283        let table = PntsFeatureTable {
284            positions: local_positions,
285            rgb: tile_rgb,
286            rtc_center: Some(center),
287        };
288        let pnts = encode_pnts(&table)?;
289        let uri = format!("{}.pnts", tiles.len());
290        let point_count = table.point_count();
291        tiles.push(BuiltTile { uri: uri.clone(), pnts, point_count });
292        content = Some(TileContent { uri });
293    }
294
295    let mut children = Vec::new();
296    for child in node.children {
297        children.push(materialize(child, positions, rgb, tiles)?);
298    }
299
300    let bounding_volume = BoundingVolume::box_from_bounds(node.min, node.max)?;
301    Ok(Tile {
302        bounding_volume,
303        geometric_error: node.geometric_error,
304        refine: None,
305        content,
306        children,
307    })
308}
309
310fn compute_bounds(positions: &[f32]) -> ([f64; 3], [f64; 3]) {
311    let mut min = [f64::INFINITY; 3];
312    let mut max = [f64::NEG_INFINITY; 3];
313    for (index, value) in positions.iter().enumerate() {
314        let axis = index % 3;
315        min[axis] = min[axis].min(f64::from(*value));
316        max[axis] = max[axis].max(f64::from(*value));
317    }
318    for axis in 0..3 {
319        if !(max[axis] - min[axis]).is_normal() {
320            min[axis] -= 1.0e-6;
321            max[axis] += 1.0e-6;
322        }
323    }
324    (min, max)
325}
326
327fn bounds_diagonal(min: [f64; 3], max: [f64; 3]) -> f64 {
328    let dx = max[0] - min[0];
329    let dy = max[1] - min[1];
330    let dz = max[2] - min[2];
331    (dx * dx + dy * dy + dz * dz).sqrt()
332}
333
334fn io_error(error: std::io::Error) -> InterchangeError {
335    InterchangeError::InvalidConfiguration(format!("tileset IO failure: {error}"))
336}
337
338#[cfg(test)]
339mod tests {
340    use super::{build_point_tileset, write_point_tileset, TilesetBuilderOptions};
341    use crate::tiles3d::pnts::decode_pnts;
342
343    fn grid_points(size: usize, step: f32) -> Vec<f32> {
344        let mut out = Vec::new();
345        for x in 0..size {
346            for y in 0..size {
347                for z in 0..size {
348                    out.push(x as f32 * step);
349                    out.push(y as f32 * step);
350                    out.push(z as f32 * step);
351                }
352            }
353        }
354        out
355    }
356
357    #[test]
358    fn splits_into_multiple_tiles() {
359        let positions = grid_points(16, 1.0);
360        let built = build_point_tileset(
361            &positions,
362            None,
363            &TilesetBuilderOptions { max_points_per_tile: 64, ..Default::default() },
364        )
365        .unwrap();
366        assert!(built.tiles.len() > 1);
367        let total: usize = built.tiles.iter().map(|tile| tile.point_count).sum();
368        assert_eq!(total, positions.len() / 3);
369        for tile in &built.tiles {
370            let decoded = decode_pnts(&tile.pnts).unwrap();
371            assert_eq!(decoded.point_count(), tile.point_count);
372            assert!(decoded.rtc_center.is_some());
373        }
374    }
375
376    #[test]
377    fn single_tile_within_budget() {
378        let positions = grid_points(2, 1.0);
379        let built =
380            build_point_tileset(&positions, None, &TilesetBuilderOptions::default()).unwrap();
381        assert_eq!(built.tiles.len(), 1);
382        assert_eq!(built.tiles[0].point_count, 8);
383    }
384
385    #[test]
386    fn preserves_rgb_per_tile() {
387        let positions = grid_points(8, 1.0);
388        let rgb: Vec<u8> = (0..positions.len()).map(|index| (index % 251) as u8).collect();
389        let built = build_point_tileset(
390            &positions,
391            Some(&rgb),
392            &TilesetBuilderOptions { max_points_per_tile: 16, ..Default::default() },
393        )
394        .unwrap();
395        let mut rgb_points = 0usize;
396        for tile in &built.tiles {
397            let decoded = decode_pnts(&tile.pnts).unwrap();
398            assert_eq!(decoded.rgb.as_ref().unwrap().len(), decoded.point_count() * 3);
399            rgb_points += decoded.point_count();
400        }
401        assert_eq!(rgb_points, positions.len() / 3);
402    }
403
404    #[test]
405    fn deterministic_output() {
406        let positions = grid_points(12, 0.5);
407        let options = TilesetBuilderOptions { max_points_per_tile: 32, ..Default::default() };
408        let first = build_point_tileset(&positions, None, &options).unwrap();
409        let second = build_point_tileset(&positions, None, &options).unwrap();
410        assert_eq!(first.tiles, second.tiles);
411        assert_eq!(first.tileset, second.tileset);
412    }
413
414    #[test]
415    fn rejects_invalid_input() {
416        assert!(build_point_tileset(&[0.0, 0.0], None, &TilesetBuilderOptions::default()).is_err());
417        assert!(build_point_tileset(
418            &[f32::NAN, 0.0, 0.0],
419            None,
420            &TilesetBuilderOptions::default()
421        )
422        .is_err());
423        let options = TilesetBuilderOptions { max_points_per_tile: 0, ..Default::default() };
424        assert!(build_point_tileset(&[0.0, 0.0, 0.0], None, &options).is_err());
425    }
426
427    #[test]
428    fn writes_files_and_receipt() {
429        let positions = grid_points(6, 1.0);
430        let built =
431            build_point_tileset(&positions, None, &TilesetBuilderOptions::default()).unwrap();
432        let dir = std::env::temp_dir().join(format!("spatialrust-tiles3d-{}", std::process::id()));
433        let receipt = write_point_tileset(&dir, &built).unwrap();
434        assert_eq!(receipt.tile_count as usize, built.tiles.len());
435        assert_eq!(receipt.point_count, (positions.len() / 3) as u64);
436        assert!(dir.join("tileset.json").exists());
437        assert!(dir.join(&built.tiles[0].uri).exists());
438        let _ = std::fs::remove_dir_all(&dir);
439    }
440}
spatialrust_interchange/tiles3d/builder.rs

spatialrust_interchange/tiles3d/
builder.rs
