SDF Refactor #876
SDF Refactor #876
Conversation
|
Related to #655 - with the SDF getting pre-computed, this would also make it a lot easier to do batch processing for Python, etc. I'm not totally thrilled with the API complexity of it, but we did do it for Warp, so... Also, the batching won't speed up getting a higher precision SDF. Personally, I'd rather these languages figure out how to bind a pure function so it can be invoked in parallel, but alas. @zalo opinions? |
|
@pca006132 Weird, I'm getting vec out of range, but only for Python. Any ideas? |
| @@ -12,7 +12,8 @@ | |||
| "program": "${workspaceFolder}/build/test/manifold_test", | |||
| "args": [ | |||
| "--gtest_break_on_failure", | |||
| "--gtest_filter=Smooth.RefineQuads" | |||
| "--gtest_catch_exceptions=0", | |||
There was a problem hiding this comment.
maybe we should gitignore this later
|
No idea, but I can help to debug this later. It seems pretty consistent. |
|
The memory-poor way of doing it would be to give the client program some minimal amount of data that it could use to compute the sample points for processing in parallel. This seems needlessly complicated, imo. The numpythonic way of doing it would be similar to my old PR: pass the SDF sample grid as an A compromise might be to pass only some of the sample points with each call, to balance memory usage and parallelism, and then to call it many times. This has the added benefit of subsequent binary search queries only needing to sample the points near the surface, vastly improving the speed. |
|
@zalo, agreed - I figure once I make it batched for ourselves, I can use that same system to batch to Python. However, I don't follow this:
Can you explain how the speed is faster near the surface, and also how this relates to the batching? I sort of felt the very nature of binary search would pretty much preclude batching. |
|
My intuition is that, when there's a zero-crossing, you can record the two samples points on either side of that for the binary search later; there's no need to sample the empty volume anymore far from the zero-crossing isosurface... It's not really a batching-specific thing... just that every batched call of the algorithm doesn't need to include all of the points in the box volume. |
|
but in general you have no way of knowing if some volume far away from the zero-crossing is empty unless you sample it? e.g. gyroid. |
|
@pca006132 Are you supposed to binary search between two positive distances? 😅 |
|
I think we have no information about anything outside a sphere with radius r when we get a positive distance r. Binary search can help you find the root when you are already near it (kind of move the points of the evaluation grid when we are near the surface?), but it does not make things faster because we still have to evaluate nearby points according to the base resolution. |
| @@ -216,24 +201,26 @@ struct ComputeVerts { | |||
| neighborIndex += 1; | |||
| neighborIndex.w = 0; | |||
| } | |||
| const float val = BoundedSDF(neighborIndex); | |||
| const float val = | |||
| voxels[EncodeIndex(neighborIndex + glm::ivec4(1, 1, 1, 0), gridPow)]; | |||
There was a problem hiding this comment.
It seems that this neighborIndex + glm::ivec4(1, 1, 1, 0) can exceed the gridSize range. I see neighborIndex = glm::ivec4(31, 32, 1, 0) for grdSize = glm::ivec3(31, 31, 31).
And this line is causing the index out of range error.
|
Also, how should we batch compute the sdf function if we want to do root finding? |
|
@zalo @pca006132 I think you're actually in agreement. Checking the whole volume is necessary as the first step and can be batched. Doing binary search only happens on the output verts, but cannot be batched. You'll see this is how it works in this PR already. |
|
ah, I got it to repro with address sanitizer! Should be able to get to the bottom of it now. |
The root-finding routines would need to enqeue their sample requests and store their state until the batched query can get back to it 😅. |
|
I figured out why I wasn't catching it locally - somehow despite not specifying the |
Fixes #655
The big breaking change here is moving
LevelSetfrom a free function in its own library toMeshGL::LevelSet- I decided this is a better home so that we can deprecateMesh, but also only incur the cost of converting to aManifoldfor those who want to (it can be a lot of work finding the flat faces and collapsing edges).I also changed LevelSet to precalculate the SDF values and reference them - I'm seeing a 50% speedup on larger tests (I added
SDF.Blobsfor this). It requires more memory, but if we want, as a follow-on, it would be fairly easy now to calculate it in blocks of a fixed memory size.I've also updated our bindings to the API changes.