STL to SDF evaluation

[Megidd]

Reproduce the bug of #72.

[Megidd]

Pinpoint

The code at which the wrong value is introduced is found:

// Point:
p v3.Vec
{X: -0.8164382918936324, Y: 2.542909114087213, Z: 5.006102143191411}

// A sample triangle among 20 closest neighbors (AABB based)
triangle := neighbor.(*stlTriangle).Triangle3
{X: -1.3557049036026,    Y: 3.3538689613342285, Z: 6.5562238693237305}
{X: -0.9175547361373901, Y: 3.503408193588257,  Z: 6.5562238693237305}
{X: -1.1925894021987915, Y: 3.4095396995544434, Z: 6.5562238693237305}

triNormal := triangle.Normal()
{X: 0, Y: 0, Z: -1}

// Among 3 triangle vertices, the 1st one is picked as a test.
testPointToTriangle := p.Sub(triangle.V[0])
{X: 0.5392666117089677, Y: -0.8109598472470156, Z: -1.5501217261323195}

// This value must be negative, but due to the normal vector and the picked test point,
// it becomes positive.
signedDistanceToTriPlane := triNormal.Dot(testPointToTriangle)
1.5501217261323195

distToTri, _ := stlPointToTriangleDistSq(p, triangle)
3.337441955783935

[Megidd]

Note

Picking any of the triangle vertices as the test, the result is the same:

pointToTri1st := p.Sub(triangle.V[0])
{X: 0.5392666117089677, Y: -0.8109598472470156, Z: -1.5501217261323195}

// The result is wrongly positive.
signedDistanceToTriPlane1st := triNormal.Dot(pointToTri1st)
1.5501217261323195

pointToTri2nd := p.Sub(triangle.V[1])
{X: 0.10111644424375776, Y: -0.960499079501044, Z: -1.5501217261323195}

// The result is wrongly positive.
signedDistanceToTriPlane2nd := triNormal.Dot(pointToTri2nd)
1.5501217261323195

pointToTri3rd := p.Sub(triangle.V[2])
{X: 0.37615111030515913, Y: -0.8666305854672305, Z: -1.5501217261323195}

// The result is wrongly positive.
signedDistanceToTriPlane3rd := triNormal.Dot(pointToTri3rd)
1.5501217261323195

[Megidd]

Test

Looks like the workaround implemented by commits here might fix the bug :thinking: Now, the artifact is not observed:

[deadsy]

I didn't write the stl to sdf conversion code and I'm wary of it. The fix smells like a hack. If it's a good mesh then we should be able to get an unambiguous result. Is it a floating point accuracy thing? I've been reading the paper. Thinking of doing this for 2d (which would be a nice optimisation on the existsing code) and then doing it for 3d.

[Megidd]

If it's a good mesh then we should be able to get an unambiguous result.

I'm observing this bug even for simple STL files like a simple pipe: https://github.com/deadsy/sdfx/pull/68#issuecomment-1626907610

Is it a floating point accuracy thing?

I'm not quite sure. I feel like the cause might be the special cases of the arrangement of triangles :roll_eyes: Anyways, I'm observing this bug with a noticeable frequency.

I've been reading the paper. Thinking of doing this for 2d (which would be a nice optimisation on the existsing code) and then doing it for 3d.

That's a great idea :+1: Looking forward to the implementation of the paper.

[deadsy]

I have a pretty low confidence that an r-tree is going to deliver the right triangle set to test the distance against for all cases. You might try tweaking with numNeighbors and see what happens, but in general I don't like that correctness whould be a function of a tuning parameter.

// WARNING: Setting a low numNeighbors will consider many fewer triangles for each evaluated point, greatly speeding up // the algorithm. However, if the count of triangles is too low artifacts will appear on the surface (triangle // continuations). Setting this value to MaxInt is extremely slow but will provide correct results, so choose a value // that works for your model.

[Megidd]

... but in general I don't like that correctness would be a function of a tuning parameter.

Right, I feel the same :heavy_check_mark:

You might try tweaking with numNeighbors and see what happens ... choose a value that works for your model.

Sure :+1: Let's see...

[Megidd]

The neighbor count is set to the number of triangles, i.e. the max possible. Still, the signed distance value is 1.5501217261323195 which is still a positive one. Still not expected.