Jump to content
  • Advertisement
Sign in to follow this  
GameGeazer

Storing Signed Distance Fields

This topic is 753 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello everyone, I was wondering if anyone knows a good way of going about storing signed distance fields in a way that can be parsed well on the gpu.

 

Here's a description of my current implementation:

 

A SignedDistanceFunction consists of:

  1. A transfrom stored as a mat4x4
  2. A signed distance function (i.e. Sphere, Torus, ect)

A SignedDistanceField is a 3D byte array. The stored value indicates the material

 

SignedDistanceFunctions are applied like paint brushes to the SignedDistanceFields in order in parallel on the gpu. There are three different options

  1. Carve - sets the byte index to 0
  2. Place - sets the byte index to a value
  3. Paint - Change the value of non 0 indexes

An Edit is one of the above three operations

 

With this method each SignedDistanceFunction needs to be applied to the SignedDistanceField in an iterative fashion since an index might be written to with one Edit, but deleted in the next. For large numbers of edits this could become a performance issue.

 

I thought that applying the functions backwards( most recent modification first) and marking the changed cells as not needing computations( flag in a byte array) might be a decent solution, but the functions are still being applied iteratively instead of in parallel

 

Does anyone have any thoughts on this? If there is a completely different way of approaching distance fields I'd love to hear!

Edited by GameGeezer

Share this post


Link to post
Share on other sites
Advertisement
  • Do you need to combine elementary distance functions and render their sum, product etc. (for example, "metaballs" composed of several spheres)?
  • Do you really need to keep around SignedDistanceFunction objects, i.e. old brushstrokes? Forgetting them after applying an "edit" once would seem the most efficient course of action.
  • What do you need to store in your voxels, apart from the 1-byte material code?
  • How are you going to render your voxels? Their representation has to be suitable.

Share this post


Link to post
Share on other sites

A SignedDistanceField is a 3D byte array. The stored value indicates the material
SignedDistanceFunctions are applied like paint brushes to the SignedDistanceFields in order in parallel on the gpu. There are three different options

  • Carve - sets the byte index to 0
  • Place - sets the byte index to a value
  • Paint - Change the value of non 0 indexes
An Edit is one of the above three operations

Shouldn't a signed distance field store signed distances, so an "edit" should write signed distances into it? The only time you'd write 0 into it, would be if a 3D cell happens to lie exactly on the surface being defined. What you're describing sounds more like painting voxel values?

With actual SDF data, you then have the operators of:
Union = min(F1,F2)
Subtraction = max(-F1,F2)
Intersection = max(F1,F2)

(and more complex ones, like "smooth union" :))
 
In general, yep, you've got to apply each "edit" one at a time, as a data-parallel, serial list of operations.
However, you can group together some repeated sets of "edits" into sets that can be done in parallel.
e.g. if you have a series of Union "edits", they could be implemented using an atomic-min function, allowing multiple concurrent edits. If they were followed by a Subtraction operator, you'd have to make sure that this union-group was finished before starting the Subtraction edit though.
Likewise if you then had a contiguous group of Intersection edits - the whole contiguous group of intersections could be done in parallel by using an atomic-max function :)

Share this post


Link to post
Share on other sites

 

  • Do you need to combine elementary distance functions and render their sum, product etc. (for example, "metaballs" composed of several spheres)?
  • Do you really need to keep around SignedDistanceFunction objects, i.e. old brushstrokes? Forgetting them after applying an "edit" once would seem the most efficient course of action.
  • What do you need to store in your voxels, apart from the 1-byte material code?
  • How are you going to render your voxels? Their representation has to be suitable.

 

 

  • Yeah, the goal is to use functions to carve and model a more complex function using the primitive shapes
  • I'm keeping them around in order to rebuild the DistanceField at multiple resolutions. The highest resolution I'm extracting at is around 900x900x900 and storing the field as a byte array takes up a rather large amount of memory. But I can't think of a real reason to keep them around during run time once the DistanceField has been built, Thanks! I'll look into nixing them.
  • A material consists of a local position, normal, and roughness compacted into 4 bytes and then another 4 bytes for color.
  • I'm splatting them, one point per voxel

 

 

A SignedDistanceField is a 3D byte array. The stored value indicates the material
SignedDistanceFunctions are applied like paint brushes to the SignedDistanceFields in order in parallel on the gpu. There are three different options

  • Carve - sets the byte index to 0
  • Place - sets the byte index to a value
  • Paint - Change the value of non 0 indexes
An Edit is one of the above three operations

Shouldn't a signed distance field store signed distances, so an "edit" should write signed distances into it? The only time you'd write 0 into it, would be if a 3D cell happens to lie exactly on the surface being defined. What you're describing sounds more like painting voxel values?

With actual SDF data, you then have the operators of:
Union = min(F1,F2)
Subtraction = max(-F1,F2)
Intersection = max(F1,F2)

(and more complex ones, like "smooth union" :))
 
In general, yep, you've got to apply each "edit" one at a time, as a data-parallel, serial list of operations.
However, you can group together some repeated sets of "edits" into sets that can be done in parallel.
e.g. if you have a series of Union "edits", they could be implemented using an atomic-min function, allowing multiple concurrent edits. If they were followed by a Subtraction operator, you'd have to make sure that this union-group was finished before starting the Subtraction edit though.
Likewise if you then had a contiguous group of Intersection edits - the whole contiguous group of intersections could be done in parallel by using an atomic-max function :)

 

 

I guess it really isn't a distance field haha, since I'm not storing well.. distances. The grids I'm using are fairly high resolution(900x900x900) so I was trying to cut on memory consumption by storing only the points that lie close enough to the surface in a KDTree.

 

I just came up with an idea, maybe I could store the (x,y, z) coordinates of points that are close enough to the surface inside in the KDTree and when querying the distance from a point perform a nearest neighbor search on the tree, find the (x, y, z) coordinate close enough to be considered on the surface, and then subtract the point I'm querying from that? There would be a little computational overhead, but memorywise that should be much more efficient than the grid I'm currently using.

 

Thankyou! Batching distance fields and using atomic instructions to pick the highest one sounds like a road worth walking down.

 

If anyone else has thoughts I'd love to hear them.

Share this post


Link to post
Share on other sites

it depends heavily on the data, the use case and goal.

 

data:

- can be real distance fields, which tend to act like a compression if your data is regular e.g. Valve stores 4096 textures in 64 distance fields:

http://www.valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf

- can be spare data, in which case an kdtree (sometimes with "Bricks" as leaves) is the weapon of choice,e.g.: http://s08.idav.ucdavis.edu/olick-current-and-next-generation-parallelism-in-games.pdf

- can be a voxel field of functions that approximate non-orthogonal surfaces rather than increasing detail with by resolution, e.g.: https://mediatech.aalto.fi/~samuli/publications/laine2010i3d_paper.pdf

...

 

use case:

-medical rendering, it's usually done by marching a semi-transparent volume. I've seen people using LZSS or RLE compression per slice, which is on-the-fly decompressed to tiny caches. e.g. http://raycast.org/powerup/publications/FITpaper2007.pdf

-satelite data: it's usually a heightmap, although rendered as voxel, it's stored as 2d images. sometimes this is done as multi-layer image, which is efficient for very spares volumes (look up "depth peeling", this shows the basic concept of it)

-game data, (in the simplest case: minecraft), this is often just a huge grid, containing sub grids/chunks, which are zipped on disc. the amount is very low.

-uniform points? aka unlimited detail technology?

...

 

goal:

-are you running out of disc space? video memory? 

-are you trying to save bandwidth for rendering? are you really bandwidth bound? or fetch bound by TMU?

-are you trying to voxelize in real time? or streaming static data? transcoding involved?

-interactive visualization of scientific data (1-10fps)? pre-visualization of cinematic rendering (<1fps)? cad editor (>10fps)? game(60fps)?

 

in general, 900^3 doesn't sound like that much, I ran 4096^3 with realtime voxelization: http://twitpic.com/3rm2sa on CPU,  Jon Olick ran 16384^3 (if I recall correctly) in 

on an GTX200 or something, and medical data of about 1k^3 ran on some Pentium4. If you get the rendering right, 900^3 should be a piece of cake on modern GPUs. If you just want to accelerate rendering in a cheap way, rather use leap-stepping: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.6582&rep=rep1&type=pdf

if you URGENTLY want to compress data. implement some of the GPU based compression. E.g. don't store R8G8B8A8, but instead BC1 blocks.

Share this post


Link to post
Share on other sites

-are you running out of disc space? video memory? 

 

I'm more concerned by the method then memory at this point.

 

-are you trying to save bandwidth for rendering? are you really bandwidth bound? or fetch bound by TMU?

 

Yeah, bandwidth-wise I can use a 512^3 grid in real-time at around 20 fps using a very naive approach. Now that the poc actually runs, I'm looking for ways to improve.

 

-are you trying to voxelize in real time? or streaming static data? transcoding involved?

 

Yes. As of now, for each edit, I walk over each cell of the grid and (if the cell is close enough) apply the changes. i.e. set the voxel to a material if it's close enough to the surface. I haven't heard of streaming static data or transcoding. Is either approach worth looking into?

 

-interactive visualization of scientific data (1-10fps)? pre-visualization of cinematic rendering (<1fps)? cad editor (>10fps)? game(60fps)?

 

Aiming for real-time game performance.

 

Thanks for the article on SVO's!  I found a great paper from NVIDIA about building tree nodes in parallel. It's taking me some time to transition into GPU programming haha, this stuff is such a crazy different way of thinking.

Edited by GameGeezer

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!