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 Saeran Vasanthakumar on June 1, 2014 at 1:25pm

This is an excellent component Dieter. So useful.

Can you clarify the output for me: the leaves of the tree contain all the voxels, and depth = recursion level? Is that right?

Permalink Reply by Dieter Toews on June 1, 2014 at 3:41pm

Hey Saeran,

yes exactly,

I think, however, that i should change it so that each voxel has a position in the tree based on it's z-order.Thus:

Level 1

0;i

Level 2

0;0;i

0;1;i

0;2;i

0;3;i

0;4;i

0;5;i

0;6;i

0;7;i

Level 3 (shown sparse)

0;0;0;i

0;0;1;i

...

0;3;0;i

0;3;1;i

...

0;7;6;i

0;7;7;i

etc...

This will encode the parent-child relationship right into the tree.

Also, if i switch to using individual mesh faces for mesh clash detection then i'll be sorting them as i go (classic space partitioning sort) so i can add an output with a sorted tree for those too.

Also, I would be interesting to output them in Arend's voxel tool data format.

Also, I will add the voxels status to another output - outside is never incuded in the tree (nulls will be placed) but "on boundary" and "inside" will be represented.

Also, the bigger projects requires that the voxels know about their topology - I'll probably include that in this little test but i have to think about the best way to represent it.

Also, I was just looking at David's oct-tree component and hoping that i haven't replicated that function. It will have to wait for tomorrow since the machine i'm writing this on doesn't have rhino on it. The project is still useful for me as it is the data structure that i'm after but as a general component it might be a tad redundant.

Also, right now it accepts a list of meshes but the only uses the first one. I need to fix this.

Permalink Reply by Saeran Vasanthakumar on June 2, 2014 at 6:28pm

Hmm, lost me there.

By z-order do you mean z-axis, or the overlapping voxels based on pov?

And what is i in your example?

Permalink Reply by Dieter Toews on June 4, 2014 at 7:55pm

http://en.wikipedia.org/wiki/Z-order_curve, it is a type of fractal curve and a way of collapsing the dimension of something.

0;0... is the path - 'i' corresponds to the 0 to n elements in the list, 'i' is, i think, the convention in grasshopper. :-)

Becuase, for example, 0 is a different path than 0;0 multiple recursion levels can be represented in the same tree. (at least that is my understanding)

Permalink Reply by Arend on June 12, 2014 at 11:26am

Hi dieter,

I tested it in the voxelstools, it took 10 seconds to test 2.8 mln voxels - 700.000 filled.

Keep in mind that it's not really the search strategy that's becoming the bottleneck - it the output data. A mesh box is about 800 bytes, that means that you'll have about 800mb of data (memory) for a grid of 100x100x100, and 6.4GB of ram to for a grid of 200x200x200. This combined with GH's feature of copying all objects - you'll be out of luck pretty soon.

In the voxeltools one voxel is represented by one bit, meaning that a grid of a 100x100x100 is not only one object, it's also much lighter: about 150kb in memory footprint for a 100x100x100 grid, and about 1MB for a 200x200x200 grid.

Attachments:

meshbox5-voxelgrid.gh, 1.5 MB

Permalink Reply by Dieter Toews on July 9, 2014 at 4:10pm

Yes i see. The heaviness of the rhino bounding box object and the Copying object behavior of grasshopper is most problematic. I take it there no way to pass objects by ref in grasshopper? Maybe I'll Ask David Rutten this in a separate thread.

In the mean time I've redone my space-partitioning/recursive algorithm and got a factor 12.5x speed up so far. I still have a lot more optimization i can do. It now works with bounding boxes for as long much as possible before switching to intersection tests. This approach works best when the target mesh is high poly and not recursed below the size of individual triangles (like I've been doing for the Stanford bunny).

At this point the formatting of the voxles for grasshopper is taking (at recursion 4) 3x as long as voxlezing the bunny in the first place. Output (at recursion 4) is 1x of voxelization time. I see the delema more clearly now - thank you.

In any case here is an update to the .GHA i posted - it works with the .gh that i previously posted. I still intend to see if i can use your voxel tools framework as the representational/display system for my class. I'll have a poke around in VS and see what happens in the next couple of days.

Attachments: