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.
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:
Suzanne Monkey (3508 Triangles) on a cubic grid at resolutions 64, 128, 196, 256, 320, and 384
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
Resolution
Voxels
Accurate SDF (s)
Approx. SDF (s)
Speedup
Error %
64
282 k
9
0.27
33x
0.24%
128
2 M
77
0.83
93x
0.34%
196
7.5 M
233
2.2
106x
0.43%
256
16.8 M
556
5.0
111x
0.54%
320
32.8 M
1054
9.6
110x
0.64%
384
56.6 M
1757
16.2
108x
0.73%
Stanford Bunny Results
Resolution
Voxels
Accurate SDF (s)
Approx. SDF (s)
Speedup
Error %
64
282 k
18
0.31
58x
0.66%
128
2 M
131
0.89
147x
0.64%
196
7.5 M
467
2.5
187x
0.66%
256
16.8 M
1057
5.2
203x
0.75%
320
32.8 M
2117
9.8
216x
0.81%
384
56.6 M
3490
16.6
210x
0.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.
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:
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:
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
Stanford Bunny Results
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:
[gfycat data_id="shamelessrespectfulinsect"] [gfycat data_id="soggyaggravatinggossamerwingedbutterfly"]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.