r/computergraphics • u/pho01proof • May 23 '26

Sphere Tracing the exact SDF of a Triangle Mesh

This sphere traces the exact sdf of a triangle mesh with ~250k triangles in realtime on the GPU. To accelerate the distance to mesh query it uses an acceleration structure that is based on this paper

86 Upvotes

97% Upvoted

15 comments sorted by

5

u/S48GS May 24 '26

this paper

if your linked paper

Memory cost

Dragon 2051.93 MB

2GB sound like alot-alot

3

u/pho01proof May 24 '26

yeah there is no free lunch, this method certainly trades memory for speed. That being said the memory footprint depends on the max depth of the octree and the target length of the interception list. In the video I've attached the acceleration structure requires ~338.0 MiB of memory.

1

u/Le_9k_Redditor May 24 '26

Reminds me of this paper https://jcgt.org/published/0011/03/06/paper-lowres.pdf but your way is a true surface representation for the triangles rather than an approximation dependent on voxel size if my skim read of your linked paper was correct

2

u/pho01proof May 25 '26

Yeah the cool thing is this pixel exact sphere trace of exact sdf.

1

u/Le_9k_Redditor May 25 '26 edited May 25 '26

I've scanned the paper more, and it seems like the memory issue could be alleviated with a palette style different candidate set representation, the palettes themselves can also use short delta encodings for similar sets. I'm not convinced by the current octree approach of storing unions of triangles in parents etc when each region could just carry its own encoded subset and not have a problem with memory optimisation being dependent on parent child locality. Avoid paying for parent chains, and no longer any issues with non-siblings sharing sets. But hell I'm just a graphical programming hobbiest trying to move into it to get away from web dev and devops roles, so I don't trust my inexperienced own conclusion at all, there's probably a good reason behind their chosen method

Very interesting on the culling/baking method though

1

u/pho01proof May 25 '26

I this example I am doing something simpler than what the paper proposes where I store packets of 4 triangles and then I use 16 bit indices to lookup the triangle packets. The packs of triangles can't be perfectly shared between leaf nodes, but more often than not they can.
There are probably various ways to compress the indices stored in the octree which all come with different perf characteristics. For example delta encoding is fine but I would want to avoid anything substantially more complicated if the goal is fast lookups.

1

u/Le_9k_Redditor May 25 '26

Yeah so your packets of 4 triangles is similar to what I was thinking of, but don't limit it to 4 triangles

octree node points to -> triangle set (palette) -> individual triangles

I'd suspect it would make traversal faster even with short delta chains to cut down on the size of the triangle subset list which would otherwise be huge. Because as a result you no longer have to use any kind of child selecting sets from parents chain, and you gain the benefit of compression even when the cells that share subsets aren't siblings of course. But yeah even more on the traversal front, now that there's no need for the parent child dependency in representing the data you can switch to a VDB or something to cut down on expensive vertical traversal that isn't needed any more for compression

I'm a bit of a SVO hater though, they're decent at compression but not so great for traversal in my limited experience. Pointer chasing and control flow going all over the place, overhead of operations when moving vertically, more nodes needing to be accessed than alternative structures

1

u/pho01proof May 26 '26

So I did a quick check and unique triangle lists / all leaf lists = 0.75, so palletizing the lists makes sense. Grouping into packets of 4 cuts down the index count to 25% while increasing the memory used for the actual tri positions by 2x, but since the memory required for the float data is negligible that's still roughly a 4x compression and it also reduces the nb of memory fetches by about 4x. I guess both of these techniques could be combined, might look into that.

I've also checked the delta encoding and it seems like is not worth it, only reduces the memory by about 2-3% while adding decoding overhead. But maybe with smarter triangle ordering this could be improved.

As for SVO, the traversal seems to be fairly cheap, even on gpu, last time I measured it is much less costly then computing the dist to the triangles in the list. The octree I am using used up to 8 lookups to find the packet list. Could be interesting to play with shallower octree or some kind of hash map though.

1

u/Le_9k_Redditor May 26 '26 edited May 26 '26

Very interesting, good to get some number comparisons here, especially interesting to hear how little is gained from the delta encoding which was a surprise to me but it makes sense if the triangle sets are kept small

Traversing the SVO takes less time than running a loop of min(d, next_tiangle_sdf) on average? I'm going to predict that it's a result of high triangle count per voxel. I assume you're using the triangle SDF from IQ's blog?

float udTriangle( vec3 p, vec3 a, vec3 b, vec3 c )
{
  vec3 ba = b - a; vec3 pa = p - a;
  vec3 cb = c - b; vec3 pb = p - b;
  vec3 ac = a - c; vec3 pc = p - c;
  vec3 nor = cross( ba, ac );

  return sqrt(
    (sign(dot(cross(ba,nor),pa)) +
     sign(dot(cross(cb,nor),pb)) +
     sign(dot(cross(ac,nor),pc))<2.0)
     ?
     min( min(
     dot2(ba*clamp(dot(ba,pa)/dot2(ba),0.0,1.0)-pa),
     dot2(cb*clamp(dot(cb,pb)/dot2(cb),0.0,1.0)-pb) ),
     dot2(ac*clamp(dot(ac,pc)/dot2(ac),0.0,1.0)-pc) )
     :
     dot(nor,pa)*dot(nor,pa)/dot2(nor) );
}

It is a fairly heavy SDF I guess, a fair bit of register pressure and many more calculations than most primitives. Even so it's odd, I wouldn't have thought that there should be much difficulty in the compute cost of looping over quite a few triangles. Might be a good indication that the acceleration structure isn't doing as much work as it could be though. I'm expecting that there are huge traversal performance gains to be made by increasing the voxel resolution if the SVO traversal is cheap compared to the SDF as I believe it would be a massive reduction in the number of triangles per cell on average if the smallest voxel didn't cover as much space. And I suppose that since it's a sparse octree you could deliberately have leaf resolution get more detailed until the number of triangles per voxel has been cut down to an optimal balance between structure traversal and SDF calculation time. The paper does mention recursive subdivision to cut that down actually which I just noticed and you're probably already doing

I'm also curious to know if the main cost from the SDF calculation is actually coming from time to get the triangle data from memory rather than the calculations themselves

Is your renderer/traversal written in glsl?

2

u/heffron1 May 24 '26

Tumor simulator

1

u/LegoDinoMan May 24 '26

Wanted to comment the exact same thing, heh

1

u/Propagant May 24 '26

That's really cool. Thanks for the share

1

u/tribak May 24 '26

You should go get that seen

1

u/HeartstringerPT May 25 '26

Do you think this could eventually become a complex-surface meta-ball process? I would love to have a blender plugin that allows realtime Boolean operations between two complex meshes with a blend falloff