VoxelMeshSDF BAKE_MODE_ACCURATE_PARTITIONED does not accurately bake PrismMesh

[Piratux]

Describe the bug
VoxelMeshSDF'S BAKE_MODE_ACCURATE_PARTITIONED produces big gap between SDF values when baking PrismMesh. This does not happen with BAKE_MODE_ACCURATE_NAIVE.

More specifically, baking a mesh with BAKE_MODE_ACCURATE_PARTITIONED, one can notice "SDF gap" in visualisation between layers 13 and 14.
Switching to BAKE_MODE_ACCURATE_NAIVE and checking visualised SDF between layers 13 and 14 show no "SDF gap".

Additional info:
I've noticed this issue happen with pyramid mesh as well.

See video:

2024-06-12.23-37-10.mp4

To Reproduce
Steps to reproduce the behavior:

1. Add VoxelModifierMesh node to scene.
2. For VoxelModifierMesh create PrismMesh.
3. Select bake mode BAKE_MODE_ACCURATE_PARTITIONED.
4. Click Bake.
5. Check SDF visualised difference between layers 13 and 14.
6. Now repeat steps 3,4,5 but with BAKE_MODE_ACCURATE_NAIVE instead.

Expected behavior
SDF produced values by BAKE_MODE_ACCURATE_PARTITIONED should be very similar to BAKE_MODE_ACCURATE_NAIVE.

Environment

• OS: Windows 10
• Graphics card: GTX 650 Ti
• Godot version: 4.2.2 stable
• Module version: 1.2.0
• Renderer: Forward+

MRP
Test VoxelMeshSDF partitioned pyramid bake issue.zip

[Zylann]

That mode creates a data structure referencing triangles in chunks, and I suspect triangles are missing near the area that has the "gap" you mention.

That mode uses a compute_near_chunks function, which has a performance issue with such simple meshes. You should probably reduce Partition Subdiv to something like 8, which is much faster and also doesn't have the gap issue.

Looking more into it, I think it's simply not working properly when triangles are too big relatively to chunks: i.e if you have a mesh with only a few triangles, but subdivided so much that the AABB of triangles cover a lot of chunks, the tricks compute_near_chunks does will start producing wrong results like you're getting. It's simply not a good algorithm when used with these meshes and that config. Not sure how it would be fixed while remaining relevant. The only quick fix I have in mind is to decrease Partition Subdiv, or use another mode.

What issue is that really causing?

[Piratux]

It's not really causing big noticable issues (it can be noticed using grow_sphere as it relies on accurate SDF, but it's negligible).
Rather just wanted to document the issue.

[Zylann]

Added some info in the docs in cab1b7e

Some ideas to improve the algorithm:

godot_voxel/edition/mesh_sdf.cpp

Lines 423 to 433 in 2972862

	// TODO This creates artifacts when the mesh has few/big triangles and subdivision is high.
	// A diagonal triangle D could have an AABB so large that it intersects many chunks while not
	// relatively being close to them. Yet, 2 chunks away (>sqrt(3)) there could be a chunk intersected by
	// an axis-aligned triangle A that would be closer than D. Yet it won't be detected.
	//
	// To fix this we could:
	// - Increase the margin we use to add more triangles? That might work but reduce efficiency.
	// - Instead of using AABBs to figure if a triangle is in a chunk, we could attempt a box/triangle
	// intersection, or 3D rasterization. Then we could keep using the sqrt(3) margin since we know if
	// a triangle is in a chunk, and if we pick any point on the sides of hat chunk, the distance from
	// that point to the triangle is always closer than the diagonal of that chunk.