Mesh Bounding Box Clash Detection

Hi all,

I've been wrestling with the correct approach for determining the status of many small, world aligned, static (but recalculated at intervals), regularly spaced, bounding boxes (voxels) in relation to a large arbitrarily shaped mesh. I would like to know if a given bounding box is outside, on the boarder, or inside of the mesh (i want to fill a mesh with ever smaller voxels recursively).

In looking though rhinocommon and other libraries i see:

MeshMeshAccurate/MeshMeshFast intersections
The MeshClash class
Something like DigitalRune Geometry for .NET and XNA or a similar library.

In one and two I'll need to translate my bounding boxes into meshes (no big deal). A bigger problem is that it looks like neither 1 nor 2 will provide all three pieces of info that i would like. The problem i see with 3 is that I'll have to translate the format of meshes back and fourth. It is also not clear that game libraries like digitalRune's will provide all three pieces of info.

Does anyone out there have any experience with the rhinocommon classes above or my problem in general?

Replies to This Discussion

Permalink Reply by Dieter Toews on May 2, 2014 at 3:20pm

I should add that for 2 i think I can combine MeshClash with isPointInside on the centroid of the bounding box to know which of the three possibilities the box is living in.

Permalink Reply by Dieter Toews on May 2, 2014 at 11:10pm

wait - that is clearly not true.... what was i thinking. hmm.

Permalink Reply by djordje on May 2, 2014 at 3:22pm

Hi Dieter,

Check the attached file.
It only checks whether your boxes are outside of the mesh (cylinder in the photo bellow), inside of it, or they intersect with the mesh:

I took the voxel vertices and checked whether or not they are inside of a mesh (mesh.IsPointInside() method).
A shorter (but not sure if quicker too) way would be not to check the vertices of voxels which intersect with mesh, and take in account only those that do not. But that would require meshing each of your voxels which might take some time.

Not sure how would you determine whether you voxel is on the border of the mesh or not (I assume it's the outer border of the mesh?)
Maybe you could check if voxel is outside of the mesh first. Then find the distance between its vertices and the mesh (meshCP = mesh.ClosestMeshPoint()), measure the distance between that closest point on the mesh and your vertex (vertex.DistanceTo(meshCP)), and if the distance is less then some tolerance value, it means one of your voxel vertices almost touches the mesh. But vertex touching a mesh and a voxel on the border of the mesh is not the same or is it?

Attachments:

mesh_inclusion.gh, 8 KB
mesh_inclusion.3dm, 43 KB

Permalink Reply by Dieter Toews on May 2, 2014 at 11:07pm

I did a thought experiment which, i think, eliminates the possibility of using a vertex based approach (see sketch) at an arbitrary level of recursion i might run into the situation that a splinter of a mesh pierces a voxel in such a way that no vertices are enveloped by the mesh. For the rest of what i am planning this would need to be considered "on the boarder".

Permalink Reply by Dieter Toews on May 3, 2014 at 2:32pm

ok, i think i have a way of re-conceptualizing it which is helpful. I will rename my categories "voxel ... :

... not intersecting mesh."
... partially intersecting mesh."
... fully intersecting mesh."

Here is a dumb algorithm but i think it will cover all cases:

I can intersect the voxel and the mesh and measure the volume of the result. If the volume of the intersection is equal to the volume of the voxel it is inside the mesh. if it is zero is it outside . otherwise it is on the boundary or "partially intersecting mesh."

I suspect that this is grossly inefficient compared with what might be possible by operating at a lower level.

Goggling "mesh-bounding box intersection" and "mesh-bounding box collision test" does not yield very encouraging results. I will try typing of a test of the above idea to see if it will work...

Permalink Reply by Arend on May 5, 2014 at 3:49am

could you provide some metrics: How big? (How many elements?), Perhaps an example of the geometry you're playing with? How much geometry? How big is the boundingbox in relation to the voxel?

Sounds like a perfect case for the RTree geometry in Grasshopper. (See attached)

Otherwise, you may also experiment with the voxel tools, a plugin for grasshopper I've written over the last two years, but not yet got around to publishing it.

Attachments:

RTree - experiment.gh, 11 KB

Permalink Reply by Dieter Toews on May 5, 2014 at 9:11am

The voxels are to be by 'floor levels' and by quad tree on arbitrary meshes... so scale-less. We want to build the tree structure ourselves because we want to operate on it. the 1st recursion will divide a floor level into quarters, the next will divide a given quarter into quarters, and so on until max recursion depth in reached. You can imagine the flat pancake being progressively subdivided into tons of tiny columns...

Permalink Reply by Dieter Toews on May 5, 2014 at 2:15pm

So i coded this cartoon up:

private void RunScript(Mesh testVoxel, Mesh testMesh, ref object A)
{
    Rhino.Geometry.Intersect.MeshClash[] clashresult = Rhino.Geometry.Intersect.MeshClash.Search(testVoxel, testMesh, 0.0001, 256);

    //bool inout =
    if (clashresult.Length > 0)
    {
      A = "On Boundary";
    }
    else
    {
      VolumeMassProperties voxelMassProp = VolumeMassProperties.Compute(testVoxel);
      if (testMesh.IsPointInside(voxelMassProp.Centroid, 0.00001, true))
      {
        A = "Inside";
      }
      else
      {
        A = "Outside";
      }
    }
}

It seems to work - see example

Attachments:

mesh-box.gh, 21 KB

Permalink Reply by Dieter Toews on May 5, 2014 at 7:12pm

So, Thinking about it more, Its a bit inelegant but i think it functions. Tomorrow I'll try it with a very heavy "testMesh" that i have and see how it fairs. Even knowing that i don't have to run this check on children of inside voxels (and outside voxels are dead) it may still mean 100's or 1000's on a 4th or 5th level voxel recursion.

Permalink Reply by Dieter Toews on May 6, 2014 at 3:54pm

So here is a new version (see attached gh file with embedded Stanford bunny),

Roughly 1000 boxes are compared against the Stanford bunny. Grasshopper says execution took 1.4 minutes. :-(

I tried it with and without VolumeMassProperties (importing the center-points vs recalculating them) and it didn't seem to affect the speed.

Does anyone know if you can recycle a MeshClash instance so that only one of the meshes changes / does anyone have any other suggestions for speed-ups?

Permalink Reply by Dieter Toews on May 12, 2014 at 11:59am

Sorry - the original Stanford bunny is not watertight. I found the none of the points were resolving to being inside. I was puzzled by this until i found this problem.

I re-embedded an new version that was shrink-wrapped by Christopher Batty and it all works now.

... including a check to see if the test mesh is manifold would resolve the issue by allowing me to create an error for meshes that won't work. In any case here is an updated version of my test gh ->

Attachments:

mesh-box.gh, 21 KB

Permalink Reply by Dieter Toews on May 5, 2014 at 7:32pm

"could you provide some metrics: How big? (How many elements?),"

From building scale to urban scale - 5m to 5000m with maybe 0.5m voxels. so 4^7 = 16384, on 5000m that equals 0.305m grid squares thus 7th level recursion should handle all ridiculous cases although you might need an nearly infinitely fast computer and 1000's of GB of ram if a lot of floor levels also exist.

My hope is to be able to support any mesh complexity that grasshopper/rhino can support.

I searched the forum but can't find your voxel tools - i'd love to play with them if they are about somewhere.