<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Collision Detection — Guide</title>
<link rel="stylesheet" href="style.css">
</head>
<body>
<nav class="sidebar">
<ul>
<li style="margin-bottom: 0.8rem"><a href="https://gitlab.com/porky11/collision-detection" style="opacity: 1">GitLab Repository</a></li>
<li><a href="#overview">Overview</a></li>
<li><a href="#ecosystem">Ecosystem</a></li>
<li><a href="#getting-started">Getting Started</a></li>
<li><a href="#shapes">Shapes</a></li>
<li style="padding-left: 0.8rem; font-size: 0.75rem"><a href="#sphere">Sphere</a></li>
<li style="padding-left: 0.8rem; font-size: 0.75rem"><a href="#capsule">Capsule</a></li>
<li style="padding-left: 0.8rem; font-size: 0.75rem"><a href="#convex">Convex</a></li>
<li style="padding-left: 0.8rem; font-size: 0.75rem"><a href="#ray">Ray</a></li>
<li><a href="#collision-manager">Collision Manager</a></li>
<li><a href="#layers">Layers</a></li>
<li><a href="#algorithms">Algorithms</a></li>
<li style="padding-left: 0.8rem; font-size: 0.75rem"><a href="#brute-force">Brute Force</a></li>
<li style="padding-left: 0.8rem; font-size: 0.75rem"><a href="#spatial">Spatial Partitioning</a></li>
<li style="padding-left: 0.8rem; font-size: 0.75rem"><a href="#bvh">BVH</a></li>
<li><a href="#wrappers">Wrappers</a></li>
<li style="padding-left: 0.8rem; font-size: 0.75rem"><a href="#bounded-collider">BoundedCollider</a></li>
<li style="padding-left: 0.8rem; font-size: 0.75rem"><a href="#transformed">Transformed</a></li>
<li><a href="#custom-collider">Custom Collider</a></li>
<li><a href="#design">Design Principles</a></li>
</ul>
</nav>
<div class="content">
<h1>Collision Detection</h1>
<p class="subtitle">A dimension-generic collision detection ecosystem for Rust</p>
<h2 id="overview">Overview</h2>
<p>This ecosystem provides collision detection that works in any dimension (2D, 3D, N-D) with any vector type. It consists of a core trait crate, shape implementations, and a collision manager with multiple algorithm tiers.</p>
<p>The central idea: implement the <code>Collider</code> trait for your shapes, put them in a <code>CollisionManager</code>, and pick the algorithm that fits your scene.</p>
<h2 id="ecosystem">Ecosystem</h2>
<table>
<tr><th>Crate</th><th>Purpose</th></tr>
<tr><td><a href="https://crates.io/crates/collide"><code>collide</code></a></td><td>Core traits: <code>Collider</code>, <code>BoundingVolume</code>, <code>Bounded</code>, <code>Transformable</code>, <code>SpatialPartition</code></td></tr>
<tr><td><a href="https://crates.io/crates/collide-sphere"><code>collide-sphere</code></a></td><td>Sphere — center + radius. Simplest, most efficient collider</td></tr>
<tr><td><a href="https://crates.io/crates/collide-capsule"><code>collide-capsule</code></a></td><td>Capsule — two endpoints + radius. Good for elongated shapes</td></tr>
<tr><td><a href="https://crates.io/crates/collide-convex"><code>collide-convex</code></a></td><td>Convex hull — N points + radius. Arbitrary shapes via GJK/EPA</td></tr>
<tr><td><a href="https://crates.io/crates/collide-ray"><code>collide-ray</code></a></td><td>Ray — origin + direction. Shape crates implement <code>Collider<Ray></code> via feature flags</td></tr>
<tr><td><a href="https://crates.io/crates/collision-detection"><code>collision-detection</code></a></td><td>Collision manager with brute force, spatial partitioning, and BVH</td></tr>
</table>
<h2 id="getting-started">Getting Started</h2>
<p>Add the crates you need:</p>
<pre>cargo add collision-detection collide collide-sphere</pre>
<p>Create a manager, insert colliders, compute collisions:</p>
<pre>use collision_detection::CollisionManager;
use collide_sphere::Sphere;
let mut manager = CollisionManager::<Sphere<Vec3>, u32>::new();
let player = manager.insert_collider(Sphere::new(player_pos, 0.5), PLAYER_ID);
let enemy = manager.insert_collider(Sphere::new(enemy_pos, 0.5), ENEMY_ID);
let collisions = manager.compute_inner_collisions();
for (collider_index, hits) in &collisions {
for hit in hits {
let other_id = hit.index;
let push_vector = hit.info.vector;
}
}</pre>
<h2 id="shapes">Shapes</h2>
<p>All shapes are generic over the vector type <code>V</code>. They work in 2D, 3D, or any dimension as long as <code>V</code> implements <code>InnerSpace</code>.</p>
<h3 id="sphere">Sphere</h3>
<p>Center + radius. The cheapest collider — collision is a single distance check. Use sphere-only layers when you need maximum throughput.</p>
<pre>use collide_sphere::Sphere;
let sphere = Sphere::new(center, 1.0);
let point = Sphere::point(position); // radius = 0</pre>
<p><code>Sphere</code> also implements <code>BoundingVolume</code>, so it can be used directly as bounding volume for the BVH algorithm.</p>
<h3 id="capsule">Capsule</h3>
<p>Two endpoints + radius. The convex hull of two spheres. Also represents spheres (<code>start == end</code>), lines (<code>radius == 0</code>), and points.</p>
<pre>use collide_capsule::Capsule;
let capsule = Capsule::new(0.5, start, end);
let sphere = Capsule::sphere(center, 1.0);
let line = Capsule::line(start, end);</pre>
<h3 id="convex">Convex</h3>
<p>N points + radius. The Minkowski sum of a convex hull and a sphere. Uses GJK for distance and EPA for penetration. Handles triangles, boxes, arbitrary polytopes.</p>
<pre>use collide_convex::Convex;
let triangle = Convex::new(0.1, vec![p1, p2, p3].into());
let box_shape = Convex::new(0.0, vec![
// 8 corner points of a box
].into());</pre>
<div class="note">Convex uses heap allocation (<code>Box<[V]></code>) and is <code>Clone</code> but not <code>Copy</code>. For performance-critical paths, prefer Sphere or Capsule when possible.</div>
<h3 id="ray">Ray</h3>
<p>Origin + direction. Not a collider against itself, but shape crates implement <code>Collider<Ray></code> via the <code>ray</code> feature flag:</p>
<pre># Cargo.toml
collide-sphere = { version = "...", features = ["ray"] }
collide-capsule = { version = "...", features = ["ray"] }
collide-convex = { version = "...", features = ["ray"] }</pre>
<pre>use collide::Collider;
use collide_ray::Ray;
use collide_sphere::Sphere;
let ray = Ray::new(origin, direction);
let sphere = Sphere::new(center, 1.0);
if let Some(info) = sphere.collision_info(&ray) {
let hit_distance = info.vector.magnitude();
}</pre>
<h2 id="collision-manager">Collision Manager</h2>
<p>The <code>CollisionManager<C, I></code> holds colliders of type <code>C</code> indexed by user IDs of type <code>I</code>. It provides stable indices (via <code>slab</code>), so inserting and removing colliders doesn't invalidate other indices.</p>
<pre>let mut manager = CollisionManager::<Sphere<Vec3>, u32>::new();
// Insert returns an internal index (usize) for future reference
let idx = manager.insert_collider(sphere, MY_OBJECT_ID);
// Update position by replacing the collider
manager.replace_collider(idx, new_sphere);
// Remove when the object is destroyed
manager.remove_collider(idx);
// Query methods
manager.check_collision(&probe); // bool
manager.find_collision(&probe); // Option<I>
manager.find_collisions(&probe); // Iterator<Item = I>
// Batch computation
manager.compute_inner_collisions(); // all pairs within this manager
manager.compute_collisions_with(&other); // all pairs with another manager</pre>
<h2 id="layers">Layers</h2>
<p>There is no built-in layer/mask system. Instead, use <strong>separate <code>CollisionManager</code> instances</strong> as layers:</p>
<pre>// Layer 1: static world geometry
let mut static_layer = CollisionManager::<Sphere<Vec3>, u32>::new();
static_layer.insert_collider(wall, WALL_ID);
static_layer.insert_collider(floor, FLOOR_ID);
// Layer 2: dynamic objects
let mut dynamic_layer = CollisionManager::<Sphere<Vec3>, u32>::new();
dynamic_layer.insert_collider(player, PLAYER_ID);
dynamic_layer.insert_collider(enemy, ENEMY_ID);
// Dynamic objects collide with each other
let mutual = dynamic_layer.compute_inner_collisions();
// Dynamic objects collide with static world
// (no compute_inner_collisions on static — they never move)
let world = dynamic_layer.compute_collisions_with(&static_layer);</pre>
<p>This naturally gives you the "static vs dynamic" optimization. Each layer uses one collider type for maximum efficiency. If you need mixed shapes in one layer, use an enum:</p>
<pre>enum Shape {
Sphere(Sphere<Vec3>),
Capsule(Capsule<Vec3>),
}
impl Collider for Shape {
type Vector = Vec3;
fn collision_info(&self, other: &Self) -> Option<CollisionInfo<Vec3>> {
// dispatch based on variant combination
}
}</pre>
<h2 id="algorithms">Algorithms</h2>
<p>Every manager supports three algorithm variants with the same return type. Start with brute force, add trait implementations to unlock faster algorithms as your scene grows:</p>
<table>
<tr><th>Method</th><th>Complexity</th><th>Required Traits</th></tr>
<tr><td><code>compute_inner_collisions()</code></td><td>O(n²)</td><td><code>Collider</code></td></tr>
<tr><td><code>compute_inner_collisions_spatial()</code></td><td>O(n×k)</td><td><code>Collider + SpatialPartition</code></td></tr>
<tr><td><code>compute_inner_collisions_bvh::<V>()</code></td><td>O(n log n)</td><td><code>Collider + Bounded<V></code></td></tr>
</table>
<p>Same three variants exist for <code>compute_collisions_with</code>.</p>
<h3 id="brute-force">Brute Force</h3>
<p>Tests all pairs. No additional traits needed. Fine for small scenes (<100 objects).</p>
<h3 id="spatial">Spatial Partitioning</h3>
<p>Implement <code>SpatialPartition</code> to map your collider to grid cells. The manager builds a <code>HashMap<Cell, Vec<index>></code> and only checks pairs sharing a cell. Best for uniformly distributed objects of similar size.</p>
<pre>impl SpatialPartition for MyCollider {
type Cell = [i32; 3];
fn cells(&self) -> impl Iterator<Item = [i32; 3]> {
// return all grid cells this collider overlaps
}
}</pre>
<h3 id="bvh">BVH (Bounding Volume Hierarchy)</h3>
<p>Implement <code>Bounded<V></code> to provide a bounding volume. The type parameter <code>V</code> selects which bounding volume to use — <code>Sphere</code> already implements <code>BoundingVolume</code>, so it works out of the box as bounding volume.</p>
<pre>use collide::Bounded;
use collide_sphere::Sphere;
impl Bounded<Sphere<Vec3>> for MyCollider {
fn bounding_volume(&self) -> Sphere<Vec3> {
Sphere::new(self.center(), self.max_radius())
}
}
// Then use:
manager.compute_inner_collisions_bvh::<Sphere<Vec3>>();</pre>
<p><code>Bounded<B></code> is generic, so you can provide multiple bounding volume types and pick the best one per scene.</p>
<h2 id="wrappers">Composable Wrappers</h2>
<h3 id="bounded-collider">BoundedCollider<B, C></h3>
<p>Wraps a collider with a bounding volume for automatic pre-checks. The bounding volume's <code>check_collision</code> runs first — only if it passes, the inner collider is tested. Nestable for cascading broad-to-narrow:</p>
<pre>use collide::BoundedCollider;
// Cheap sphere check before expensive convex GJK
type FastConvex = BoundedCollider<Sphere<Vec3>, Convex<Vec3>>;
let collider = FastConvex::new(my_convex); // sphere computed automatically</pre>
<h3 id="transformed">Transformed<C, T></h3>
<p>Wraps a collider with a transform. The shape must implement <code>Transformable<T></code>, and the transform must implement <code>Transform<V></code> (from <code>vector-space</code>).</p>
<pre>use collide::{Transformed, Transformable};
let world_collider = Transformed::new(local_shape, my_transform);</pre>
<p>Both shapes are materialized in world space before collision testing. For <code>Copy</code> types (Sphere, Capsule) this is free. For <code>Convex</code> it involves heap allocation.</p>
<h2 id="custom-collider">Writing a Custom Collider</h2>
<p>Implement the <code>Collider</code> trait:</p>
<pre>use collide::{Collider, CollisionInfo};
struct MyShape<V> { /* your fields */ }
impl<V> Collider for MyShape<V> {
type Vector = V;
fn check_collision(&self, other: &Self) -> bool {
// Optional: cheap broad-phase test
// Default calls collision_info().is_some()
}
fn collision_info(&self, other: &Self) -> Option<CollisionInfo<V>> {
// Return contact points and separation vector,
// or None if no collision
}
}</pre>
<p>All algorithms call <code>check_collision</code> before <code>collision_info</code>. Override <code>check_collision</code> with a cheap test (bounding sphere distance) to skip expensive narrow-phase math for non-colliding pairs.</p>
<h2 id="design">Design Principles</h2>
<ul>
<li><strong>Dimension-generic</strong>: All traits work in 2D, 3D, N-D. No dimension-specific assumptions anywhere.</li>
<li><strong>No math library lock-in</strong>: Works with any vector type that implements <code>VectorSpace</code> / <code>InnerSpace</code>.</li>
<li><strong>Composable</strong>: Wrappers (<code>BoundedCollider</code>, <code>Transformed</code>) compose freely with any collider.</li>
<li><strong>Progressive complexity</strong>: Start with brute force, add trait impls to unlock faster algorithms without changing existing code.</li>
</ul>
<p>This project is designed for use with AI coding assistants. Consistent API across all algorithm variants (same return type, same collision info structure), composable wrapper types, and uniform naming conventions.</p>
</div>
</body>
</html>