thimni 0.2.2

efficient SDF collision without discretizatio, neural nets, or interval arithmetic
Documentation

thimni

a crate for SDF collision detection that does not use polygon soup, voxelization, et cetra. only SDFs and gradients

performance

benchmarked on i7-7700HQ

benchmark average speed
1000 random spheres colliding 5 milliseconds
100 random menger sponges colliding 100 milliseconds

algorithm 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.

this devlog contains more information on how the algorithm works and properties of this implementation

DEMO

this devlog contains a link to a demo i made for this algorithm, consisting of a destructable fractal and a capsule representing the player.