Gradient-Based SDF Collision Detection

Apr 18, 2025 - ⧖ 2 min

I have been toying around with an expiremental algorithm for SDF collision detection and resolution. I have not seen anything like it, but i am still not sure if it is novel. The algorithm seems fairly performant and does not use voxelization, traingulation, or polygonization.

UPDATE: I have formalized (to some degree :D) this algorithm in a paper. It proveides far more detail than the explaination section bellow.

Explaination

The algorithm utilizes a property of monotonically increasing isotropic SDFs (i.e. points and spheres. I am not sure if other ones exist), which is that the exact distance between any isotropic SDF A(x) and any other SDF B(x) can be trivialy calculated. Generally, you can get it by substituting each "expression" in A that follows the form ||j||, where j is an "expression" involving x, to B(j). Then, evaluate this new function at the origin. e.g. for a sphere with center C and radius R, the SDF is A(x) = ||C + x|| - R. So the substitution result will be B(C + x) - R. evaluating at the origin, we get B(C) - R.

Steps

  1. Create a region of space the point of collision is expected to be in. in this case, that region is the intersection of the AABBs of the two colliding shapes

  2. Pack that region with circles, such that atleast K% (i currently use 95%, but i have not experimented with it yet) of it is covered. try to use the least amount of circles possible

  3. remove circles that do not intersect both shapes (i.e. the maximum of the distances to the two shapes minus the radius of the circle is less than or equal to 0)

  4. If beneficial (yet to experiment), sort the remaining circles by radius, from smallest to biggest

  5. For each circle, run a root finding algorithm (currently using gradient descent) that begins at the center of the circle to find a point X such that the sum of the squares of the distances is smaller than some threshold ϵ. Break the loop when a collision point X is found.

My implementation

My implementation of the algorithm uses a SDF trait that has to be implemented for each shape. It must use a vector type that implements the Vector trait. Currently, implementations for glam::Vec2 and glam::Vec3 are provided. The trait should be able to work with any number of dimensions. Unfortunately, the required aabb() function does not have a default implementation, as i am not aware of any algorithms for generating the AABB of an SDF.