Weekly Development Notes #19 – Approximating Signed Distance Fields

Covering the weeks of May 4th – 15th, 2020.

Hey everyone, it has been a few weeks since the last development update! I needed to skip last week’s development update to spend some time healing from a minor wrist injury that had left me with limited typing ability. I now have a comfortable wrist brace that is working fantastic and is helping me recover while being able to work painlessly.

The last two weeks mainly involved testing methods for approximating signed distance fields, and that is what I will cover in today’s post!

Approximating Signed Distance Fields

In the last development update, I discussed what a signed distance field (SDF) is, why we need them, and why it is unreasonable for us to calculate them with 100% accuracy. In short:

  • A SDF is a type of data that helps us represent volumes in the simulator by storing distances to the closest point on a surface. They can also be used to query the closest point on a surface from any point in the grid.
  • For a large part of our force field feature set, we need to compute SDFs efficiently over the entire grid, not just a narrow band near the surface. This is so that we can generate force fields that direct fluid towards or away from an object surface.
  • Computing a SDF can be an intense computation. To compute with 100% accuracy, it could take minutes to an hour+ per frame on a high resolution grid. For this reason, we must compute an approximation of the SDF, which can be fast, but introduces some amount of error into the generated data.
  • For a more detailed overview, see the last development update here: Weekly Development Notes #18.

While testing different methods of approximating a SDF, I think I have settled on a method that will work great for our force field features called a Fast Sweeping Method. It is relatively quick to compute, easy to implement, and introduces just a small amount of error that is acceptable for our use case. For an explanation of the Fast Sweeping Method, you can find a paragraph on page 53 of Robert Bridson’s Fluid Simulation SIGGRAPH 2007 Course Notes.

Fast Sweeping Method Results

In order to test the accuracy of a SDF approximation method, accurate data was needed for a comparison. A brute force computation was run on two object meshes at various resolutions to generate data sets of accurate SDF data:

  1. Suzanne Monkey (3508 Triangles) on a cubic grid at resolutions 64, 128, 196, 256, 320, and 384
  2. Stanford Bunny (6966 Triangles) on a cubic grid at resolutions 64, 128, 196, 256, 320, and 384

Approximate SDF data was generated using an implementation of a fast sweeping method and compared against the accurate data. A percentage of error was calculated based on the difference between the approximate and accurate data. In the results, the percentage error is considered to be the percentage of grid nodes whose distance differs by more than the width of one grid cell.

Suzanne Monkey Results

ResolutionVoxelsAccurate SDF (s)Approx. SDF (s)SpeedupError %
64282 k90.2733x0.24%
1282 M770.8393x0.34%
1967.5 M2332.2106x0.43%
25616.8 M5565.0111x0.54%
32032.8 M10549.6110x0.64%
38456.6 M175716.2108x0.73%

Stanford Bunny Results

ResolutionVoxelsAccurate SDF (s)Approx. SDF (s)SpeedupError %
64282 k180.3158x0.66%
1282 M1310.89147x0.64%
1967.5 M4672.5187x0.66%
25616.8 M10575.2203x0.75%
32032.8 M21179.8216x0.81%
38456.6 M349016.6210x0.92%

Error Visualization

According to the above results, approximating the SDF introduces a small amount of error. Is this amount of error acceptable? What is causing the error? To understand what these errors mean, it can help to visualize the data. In the following visualizations, the dots highlight spatially where these errors occur:

It seems most errors align to concave regions of the mesh where two (or more) points are close to being equal distance from the grid point. For our use case, this type and amount of error is minor, so this is looking promising as a way to speed up some major force field computations!

The next step, and what will be the focus of this week’s development, will be integrating and further optimizing this method for the simulation engine. Further testing will be needed on various mesh shapes to ensure that this is a suitable method, but I am quite confident we can make this method work well in our force field feature.

0 0 vote
Article Rating