Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
I was looking at some efficient methods for collision detection in a scene with both static and dynamic objects when I came across "distance fields."
I tried to search and understand this concept, but I could only find papers written in very complex language. Can someone explain in easy words what distance fields are and how can they be used for collision detection?
A distance field (or distance transform or distance map) is a gridded structure where each cell in the grid represents the shortest distance from that cell to a cell with some other property. Most often that "other property" is a boundary type of cell, such as a wall that a player cannot pass, or the surface of a mesh.
Distance fields have a lot of applicability. You could imagine, for example, how they might be used to implement movement guidance (by creating distance maps to either dangerous or desirable objects and weighting movement decisions by them).
However, you specifically asked about collision. Using distance fields to perform collision detection between two moving objects can quickly become rather inefficient, as rebuilding distance fields can become very slow as the scope of the field grows (especially in 3D, although methods for improving generation time are an area of research).
Distance field collision is thus used mainly to detect collision of a dynamic object with a static one. Most frequently, I've seen this done for detecting collision of cloth (or other deformable) objects with other, fixed objects in the scene.
Crudely, this is accomplished by using a signed distance field for the static object where one sign (often negative) represents a cell inside the mesh and a the other (obviously often positive) represents a cell outside the mesh. The cloth mesh's particles can be transformed into the local space of the static mesh, and the "before" and "after" positions of a particle during a given cloth simulation step can be checked against the distance field to determine if the sign changed (and thus a collision occurred). This is the method discussed in this 2003 paper on cloth simulation, for example.
Note that I wouldn't suggest using distance fields as your only collision detection method. They can be fairly efficient for what they are good at, but they are not good at everything. The best way to achieve efficient collision detection is frequently to use multiple methods, hierarchically, with increasing precision as you traverse down the hierarchy.
What are distance fields ?
In geometry and computer graphics and also used in image processing, a distance field (in simple words), is a label on each cell (pixel in image processing) with the distance of the nearest polygonal object or a pixel with special properties in image processing.
In other words it's a label for each cell that has a value of a nearest object with special property defined by the map. The object vary depending on the application.
The above image contains a Distance map for boundary pixels. Notice how each pixel contains the distance to the nearest boundary pixel. The distance is calculated using Manhattan distance.
There are different ways to calculate the distance, typical approaches include:
How is it applicable in collision detection ?
By maintaining a distance map for objects in the scene, you can check if two objects are colliding based on there distance. Unfortunately maintaining such map is expensive. And this is usually used in self intersecting objects like cloth simulations were distance maps can be maintained and updated more efficiently because of the nature of the object.
