poly_surge 0.1.0

Somewhat novel, fast incremental polytope surgery in Rust. Add and remove halfspaces, 11x-1200x faster than the standard 'just reconstruct it' approach.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

//! # `poly_surge`
//!
//! **Somewhat novel**, fast incremental polytope surgery in Rust. Add and remove
//! halfspaces, **19x-713x faster** than the standard "just reconstruct it" approach.
//!
//! ## What is this?
//!
//! A convex polytope in 3D is a bounded region defined by the intersection of
//! half-spaces (think of it as a 3D shape carved out by planes). This crate lets
//! you **dynamically add and remove** these half-space constraints while preserving
//! the mesh topology (vertices, edges, faces)—no full reconstruction needed.
//!
//! ## Quick Start
//!
//! ```rust
//! use poly_surge::{IncrementalPolytope, HalfSpace};
//! use glam::DVec3;
//!
//! // Create a polytope and add planes to form a cube
//! let mut polytope = IncrementalPolytope::new();
//!
//! // Six faces of a unit cube centered at origin
//! let planes = [
//!     HalfSpace::new(DVec3::X, 0.5),    // +X face
//!     HalfSpace::new(-DVec3::X, 0.5),   // -X face
//!     HalfSpace::new(DVec3::Y, 0.5),    // +Y face
//!     HalfSpace::new(-DVec3::Y, 0.5),   // -Y face
//!     HalfSpace::new(DVec3::Z, 0.5),    // +Z face
//!     HalfSpace::new(-DVec3::Z, 0.5),   // -Z face
//! ];
//!
//! for plane in planes {
//!     polytope.add_plane(plane);
//! }
//!
//! assert_eq!(polytope.vertex_count(), 8);  // Cube has 8 vertices
//! assert!(polytope.is_bounded());
//!
//! // Remove one face - the cube becomes an infinite prism
//! let plane_to_remove = polytope.planes().next().unwrap().0;
//! polytope.remove_plane(plane_to_remove);
//!
//! assert!(!polytope.is_bounded());  // Now unbounded
//! ```
//!
//! ## Key Features
//!
//! - **Incremental construction**: Add planes one at a time with `O(V + E)` clipping
//! - **Topology-based removal**: Remove planes in ~`O(N)` typical time (vs `O(N log N + V)` rebuild)
//! - **Lazy evaluation**: Edges and face orderings built on-demand
//! - **Unbounded support**: Handles infinite polytopes via homogeneous coordinates
//! - **Lazy boundedness check**: `O(1)` query when cached, `O(N log N)` rebuild when dirty
//!
//! ## When to Use
//!
//! - Dynamic Voronoi diagrams (cell modification)
//! - CSG operations on halfspace-defined solids
//! - Robot motion planning (C-space constraint relaxation)
//! - Interactive geometry editors
//! - Any application where planes are added/removed frequently
//!
//! ## When NOT to Use
//!
//! - N > 10,000 planes (consider specialized data structures)
//! - Exact arithmetic required (we use f64 with epsilon tolerance)
//! - Batch deletion of many planes at once (single rebuild may be faster)
//!
//! ## Algorithm
//!
//! The removal algorithm exploits vertex topology: when a plane is removed, vertices
//! with only 2 remaining incident planes lie on a line. We search along that line to
//! find where it hits other constraints, reconstructing the "unclipped" geometry.
//!
//! See the [research proposal](https://gitlab.com/dryad1/demiurge) for details.

#![warn(clippy::pedantic)]
#![warn(clippy::nursery)]

mod incremental_hull;
mod incremental_polytope;

pub use incremental_polytope::{
    AddPlaneResult, Edge, EdgeIdx, HalfSpace, IncrementalPolytope, PlaneIdx, RemovePlaneResult,
    TopologyError, Vertex, VertexIdx,
};

pub use incremental_hull::IncrementalHull;

/// Re-export glam types for convenience
pub mod math {
    pub use glam::{DMat3, DVec3, DVec4};
}