How to check if intersection is empty or not

[Megidd]

I have a code like this, checking the intersection/collision of some SDFs with each other:

    for i, sdfi := range mySDFs {
        for j, sdfj := range mySDFs {
            if i == j {
                continue
            }

            sdfCollision := sdf.Intersect3D(sdfi, sdfj)
            // TODO: How to check if the intersection is empty or not?
        }
    }

I'm not sure how to check if sdfCollision is actually empty or not. I mean, I intend to figure out whether any two 3D models are intersecting with each other.

Sorry if it's not the best question to ask. But for some reason I cannot figure it out.

[deadsy]

It's not so easy to tell from the SDF object itself. Essentially you are asking if the SDF is >0 somewhere and <0 somewhere else. ie- the intersection surface is defined within the bounding volume.

A cheap way of getting a partial answer would be an intersection check on axis aligned bounding volumes. If they don't intersect you know the SDFs don't intersect. If they do intersect the SDFs may intersect.

Getting a more definitive answer for the "may intersect" case would likely take more CPU- and clever methods don't immediately spring to mind. Research needed...

For the packing case you possibly don't need an exact answer. As a practical matter you'd probably want to have a minimum gap between neighboring objects.

[Megidd]

Thanks @deadsy :+1:

It's not so easy to tell from the SDF object itself.

Honestly, I didn't expect that. Implementing tight pack by SDF was based on the assumption that fast collision/intersection detection is possible by SDF.

A cheap way of getting a partial answer would be an intersection check on axis aligned bounding volumes.

That's right. Actually, we have a packing algorithm based on AABBox. But it doesn't pack tightly. That's why I started implementing a tight pack algorithm :slightly_smiling_face:

For the packing case you possibly don't need an exact answer. As a practical matter you'd probably want to have a minimum gap between neighboring objects.

Right. But due to how Simulated Annealing works, I need to be able to detect collisions/intersections. The state of Simulated Annealing is random, so 3D models can be located randomly. Therefore, they might be intersecting.

Question

Referring to the following code, what would be the most practical way to check if sdfi and sdfj are actually intersecting? I guess my question is this: how to know if sdfCollision has any zero values? Is that the right question to ask in my case?

    for i, sdfi := range mySDFs {
        for j, sdfj := range mySDFs {
            if i == j {
                continue
            }

            sdfCollision := sdf.Intersect3D(sdfi, sdfj)
            // TODO: How to check if sdfi and sdfj are actually intersecting?
        }
    }

[deadsy]

Yes - that's the right question. If you search the bounding box and find a +ve value and a -ve value then you can infer that is it zero at some point and therefore contains a surface. To search efficiently you'd probably want to work out a field gradient and then chase that to the zero (or at least until you flipped signs).

But: If you looked for zeroes and didn't find them, does that mean they don't exist? Maybe you were just looking in the wrong place...

[deadsy]

also:

1) what does @fogleman do? 2) There's a TODO on the Intersect3D code that needs to be fixed (better bounding box).

[Megidd]

Yes - that's the right question.

Right, thanks 👍 I didn't test the following approach. I'm curious if it works.

Marching Cubes

for i, sdfi := range mySDFs {
    for j, sdfj := range mySDFs {
        if i == j {
            continue
        }

        sdfCollision := sdf.Intersect3D(sdfi, sdfj)

        // If there is no collision, then the following STL would have no vertices. Maybe.
        render.ToSTL(sdfCollision, "collision.stl", render.NewMarchingCubesUniform(50))

        // Also, I can call my custom wrapper to get triangle mesh from SDF.
        // If there is no collision, then this triangle mesh would have no vertices. Maybe.
        m := wrapper.Mesh(sdfCollision, render.NewMarchingCubesUniform(50))
    }
}

My custom wrapper takes an SDF and a Marching Cubes algorithm and returns the mesh triangles:

func Mesh(s sdf.SDF3, r render.Render3) *Mesh {
    // Wrapper logic...
}

Test

I didn't test the above approach:

• Would it correctly detect whether there is any collision/intersection?
• Is it fast enough? It should be noted that we don't need high precision.

Question

Does the above approach make sense?

[Megidd]

1. what does @fogleman do?

I didn't study his source code thoroughly yet. But I think I have to. I believe he's not using SDF.

[deadsy]

Yes - if you render an intersection object then a "no intersect" will have an empty mesh. That is: no triangles were generated. If the intersection region is smaller than the sampling region then you may fail to detect it. This is the brute force approach to this and is obvious but slow. If you did it you'd just create a special renderer target which tracked if it actually received any triangle, and would conclude as soon as it received one - you don't need to actually create an STL.

Taking a quick look at the @fogleman code it looks like he uses trees of AABB's to speed up intersection checking. You may note that his examples all have the objects axis aligned.