Data structure and algorithm for clipping triangulation with leaf nodes of an octree

Question

I have an application in which I am using an octree to store a volume mesh of axis-aligned bounding boxes (AABBs).

Given a water-tight manifold triangle mesh, I need to:

• find if an AABB is intersected by or completely inside/outside of the surface mesh,

• clip the surface mesh with the intersected AABBs to generate triangles that completely lie within each AABB.

The triangulation and the octree containing the AABBs are both dynamic. The number of leaf nodes in the octree is huge. The number of triangles in the surface mesh is much smaller (O(10^9 - 10^13) octree nodes, vs O(10^6) triangles).

Which data-structures and algorithm are suitable for my problem?

Right now I:

• store the triangles in the same octree as the volume mesh,
• store each triangle in the smallest octree node that contains it,
• clip the triangle mesh with a single AABB by traversing from that AABB to both the root node and its leafs clipping each triangle contained in the nodes with the AABB.

The triangles in the nodes until the leafs are fully contained within the AABB and don't need any "clipping" (the AABB just contains those triangles), while the ones contained in the nodes from the AABB to the root need clipping. However:

• due to the way I am storing the triangles (in the smallest octree node that fully contains them) I don't have an upper bound in the maximum number of triangles that can be stored within each single octree node, so I don't have an upper bound in the number of triangles that have to be tested against a single AABB.

• if I just want to test if an AABB is intersected by the triangle mesh, I have to test all triangles between that AABB and the root node which might be expensive. Ideally I would like to have a very fast way to test, and then clip the mesh if the test is true.

• currently I have no fast way of determining if a node is inside/outside/intersected by the mesh. I could construct a signed distance field (which is expensive), or perform some ray casting (which is also expensive), maybe there is a better solution or maybe I just need to precompute something to speed this up every time I move the triangle mesh.

• moving the triangle mesh requires manipulating the octree (I don't know if this can be avoided). Ideally I would like to generate an octree for the triangle mesh once, and then just move the mesh using a single transformation matrix. However, then I would need to have some sort of mapping between "the octree containing the triangle mesh" and "the octree of my volume mesh". Maybe this mapping is trivial but I haven't figured it out yet. This would save me from manipulating the octree when I move the mesh and maybe the coordinate transformations that would be required are negligible with the cost of clipping.

Answer 1

Rather than making one spatial subdivision structure do double duty in representing both the voxels and the triangles, I would suggest creating a separate BVH for the mesh. You can find many articles and papers about BVH-building algorithms on the web. It's likely to be a more efficiently queryable representation of the mesh than the octree would be.

Given the BVH, it's easy to determine whether a given voxel might intersect the mesh by starting at the BVH root and traversing to child nodes that intersect the voxel box. Depending on the quality of the BVH, i.e. how tightly it fits the mesh, many voxels (or even higher-level octree nodes) may be able to be eliminated with only a few checks. For voxels that do intersect the mesh surface, the BVH traversal will reach down to the leaves, where you can accumulate the triangles into a list for clipping.

If the BVH is built in the mesh's local space, the mesh can easily be moved or transformed without needing to update the octree. (If translation is the only transform needed, then the BVH nodes will always be axis-aligned relative to the voxels, which simplifies the intersection test to an AABB overlap test; if more general transforms are needed, you'd have to use a more general OBB vs OBB test.)

However, note that a BVH doesn't lend itself that well to determining whether a things are inside versus outside a watertight mesh. If that's important to you (it wasn't clear to me whether it is), then you might want to look into using a BSP tree instead of a BVH. A BSP tree can be used for intersection testing similarly to a BVH, but additionally can represent the exact boundary of the mesh so that it can be used to determine whether a point (or voxel) is inside or outside. This property of BSP trees is widely used for collision detection.

An alternate approach to determining inside/outsideness is to use raycasting and count the number of intersections with the mesh (even = outside, odd = inside). The raycasting can be accelerated by the BVH as well.