4 ms·

A tangent, but HNers interested in an article on collision detection might know: are there any similar articles that show how to compute the intersection of two

A tangent, but HNers interested in an article on collision detection might know: are there any similar articles that show how to compute the intersection of two capsules (as in the space that that a sphere moving in a straight line in a time step occupies) in 3D? My own hobby 3D game got stuck on that hurdle and I couldn’t find any examples anywhere :(

xeonmc 2y ago
Isn’t it just a matter of checking if two lines’ perigee fall within radius sum, and if so check if the respective segments’ closest points to the perigee are within radius sum?
- deleted 2y ago
  [deleted]
pornel 2y ago
You make one of them have thickness of both, so that the collision detection becomes line vs capsule collision. Another trick is to rotate both so that one of the move directions is axis-aligned, and then the problem looks more like AABB.
qwery 2y ago
Capsule-capsule overlap can be detected by treating the capsules as line segments with radius/thickness. But I think you need something more complicated than capsule-capsule intersection to truly solve the problem (continuous collision detection between dynamic objects). The Rapier project and its documentation[0] might be of interest to you. Rapier has a more sophisticated CCD implementation than most (popular in gamedev) physics engines. > Rapier implements nonlinear CCD, meaning that it takes into account both the angular and translational motion of the rigid-body. [0] https://rapier.rs/docs/user_guides/rust/rigid_bodies#continuous-collision-detection https://rapier.rs/docs/user_guides/rust/rigid_bodies#continu...
- Animats 2y ago
  I haven't worked on collision detection since the 1990s. But convex hull collisions are very fast with GJK. And the space swept by translating a convex hull is itself a convex hull. So continuous collision detection (no fly-through) is possible that way. But that's usually overkill. Objects that move more than their own dimension in one frame time are usually bullets, and those should get special handling.
GistNoesis 2y ago
For fine collision between capsules, you consider the capsules as 3d segments with thickness. And two of those collide if the distance between segments < sum of half-thicknesses. You can check this site with nice animations which explain how to compute the distance between segments : https://zalo.github.io/blog/closest-point-between-segments/ https://zalo.github.io/blog/closest-point-between-segments/ One more generic way to compute the distance between shapes is to view it as a minimization problem. You take a point A inside object 1 and a point B inside object 2, and you minimize the squared distance between the points : ||A-B||^2 while constraining point A to object 1 and point B to object 2. In the case of capsules, this is a "convex" optimization problem : So one way of solving for the points, is to take a minimization (newton) step and then project back each point to its respective convex object (projection is well defined and unique because of the convex property) (It usually need less than 10 iterations). In geometry, we often decompose object into convex unions. One example is sphere-trees, where you cover your object with spheres. This allow you to use fast coarse collision algorithm for spheres to find collision candidates of your capsules : You cover your capsules with spheres (a little bigger than the thickness) so that the capsule is inside the union of the spheres.

xeonmc 2y ago

Isn’t it just a matter of checking if two lines’ perigee fall within radius sum, and if so check if the respective segments’ closest points to the perigee are within radius sum?

deleted 2y ago
[deleted]

pornel 2y ago

You make one of them have thickness of both, so that the collision detection becomes line vs capsule collision. Another trick is to rotate both so that one of the move directions is axis-aligned, and then the problem looks more like AABB.

qwery 2y ago

Capsule-capsule overlap can be detected by treating the capsules as line segments with radius/thickness. But I think you need something more complicated than capsule-capsule intersection to truly solve the problem (continuous collision detection between dynamic objects). The Rapier project and its documentation[0] might be of interest to you. Rapier has a more sophisticated CCD implementation than most (popular in gamedev) physics engines. > Rapier implements nonlinear CCD, meaning that it takes into account both the angular and translational motion of the rigid-body. [0] https://rapier.rs/docs/user_guides/rust/rigid_bodies#continuous-collision-detection https://rapier.rs/docs/user_guides/rust/rigid_bodies#continu...

Animats 2y ago
I haven't worked on collision detection since the 1990s. But convex hull collisions are very fast with GJK. And the space swept by translating a convex hull is itself a convex hull. So continuous collision detection (no fly-through) is possible that way. But that's usually overkill. Objects that move more than their own dimension in one frame time are usually bullets, and those should get special handling.

GistNoesis 2y ago

For fine collision between capsules, you consider the capsules as 3d segments with thickness. And two of those collide if the distance between segments < sum of half-thicknesses. You can check this site with nice animations which explain how to compute the distance between segments : https://zalo.github.io/blog/closest-point-between-segments/ https://zalo.github.io/blog/closest-point-between-segments/ One more generic way to compute the distance between shapes is to view it as a minimization problem. You take a point A inside object 1 and a point B inside object 2, and you minimize the squared distance between the points : ||A-B||^2 while constraining point A to object 1 and point B to object 2. In the case of capsules, this is a "convex" optimization problem : So one way of solving for the points, is to take a minimization (newton) step and then project back each point to its respective convex object (projection is well defined and unique because of the convex property) (It usually need less than 10 iterations). In geometry, we often decompose object into convex unions. One example is sphere-trees, where you cover your object with spheres. This allow you to use fast coarse collision algorithm for spheres to find collision candidates of your capsules : You cover your capsules with spheres (a little bigger than the thickness) so that the capsule is inside the union of the spheres.