Point location in tetrahedron meshes

Question

Are there any proven data structures for point location in tetrahedron meshes where the tetrahedra are all disjoint but are "touching" each other? I.e. most faces are faces of exactly two tetrahedra.

By locationI mean that I want to find out in which of the tetrahedrons a given point is located, or if it is not located in any.

So far, I have tried:

1. A simple KD-Tree. This was way too slow for my needs, as the average tree depth was very high and I still had a lot of individual tetrahedrons to test in each leaf.

2. A grid which contained all the intersecting tetrahedra for each cell. This seems to work a lot better, but was still not fast enough. First, the grid contained a lot of empty cells because my overall mesh is not very "boxy". Second, most cells that actually did contain tetrahedra, did contain a lot of them (10+). I suppose this is because a lot of tetrahedra share every vertex, and as soon as a vertex is in a cell, all its adjacent tetrahedra are too.

Some further information on the input data: The mesh is usually not convex and may have holes or inclusions. Though the last two are somewhat unlikely, i have to deal with them, which makes "walking" impossible without (expensive and complicated?) preprocessing.

Answer 1

If you are dealing with a 3D triangulation composed of tetrahedrons with adjacency information, you can just use walking. This is a standard technique for point location and uses 3D orientation tests.

For more information see the paper Walking in a triangulation by Olivier Devillers et al. (Google it and you will find a PDF of it.)

Answer 2

Some quick thoughts: an octree will be similar to your grid approach, but allow you to quickly ignore empty grids, and to subdivide grids which are too full.

Also, you don't mention how you're testing if a point lies inside of a tetrahedron. It's been a while since I've looked at it, but perhaps barycentric coordinates could speed up your point-in-tetrahedron tests? Or a sweep-line algorithm to quickly exclude tetrahedra based on tetrahedron vertices which are clearly on the wrong side of the sweep line to contain the point.