Fast ways to filter out a list of triangles before performing SAT test against AABB

Question

I'm trying to perform an AABB-tringle intersection with the triangles coming from a tria mesh and the AABB being the individual cells from a structured 3D grid/Voxel. Are there any smart ways/ algorithms I could use to filter out and reduce the number of triangles and AABB combinations I would have to perform the SAT test against? As it stands I'm checking every triangle against every cell from the grid which isn't efficient. I was also considering filtering out the triangles based on distance of centroid and maximum triangle size in the tria mesh as a tolerance. But this again would involve looping over all the triangles. I was also considering K-nearest neighbors.

Answer 1

There are a few well known techniques such as:

1. give an AABB to each triangle. So you do AABB vs AABB intersection first. The goal is discarding quicky the non-intersecting triangles.

2. Once you have all triangles inside an AABB, you can do massive inter-AABB's collision detection using algorithms such as I-COLLIDE. You can also create an AABB-tree (also known as Bounding-Volume-Hierarchy or BVH) for the mesh in order to discard massive amount of non-intersecting triangles at once.

Once you have reduced the set of triangles which AABB intersect the AABB of the cell, then you need to perform the actual AABB/triangle test for which you can use the separating axis theorem.