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

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.

• Can you be more precise about what your problem is (time, memory, logic)? What is stopping you from "just do it"? May 1, 2016 at 12:16
• Hey @Andreas I've updated the question with how am I doing it right now. The main issues are listed. I was wondering if a "canonical" best way of solving this problem is known. Typically when I cannot find them in google is because i am searching for "the wrong keywords". May 2, 2016 at 9:03