Point location in tetrahedron meshes

8
votes

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.

3
algorithmcomputational-geometry
Have you tries the following (could not find a reference, so I describe it shortly)? Start in an arbitrary tet. Determine a face, relatively to which the point lies outside of the tet (on the opposite side than the fourth tet vertex). Step on the the tet on the other side of the face. Check again. If there is no such face, the point is in the current tet. This algorithm works for convex meshes. Does it fit your needs? – Nico Schertler
Another thought about that. You can combine the two methods. After finding the correct grid cell, you can look for the correct tet with the method above. – Nico Schertler
That sounds neat. Surely, you can make it work for non convex meshes by filling concavities with "void" tetrahedra? – ltjax
Probably, although it could be difficult to fill the holes. But give it a try, if you like. – Nico Schertler
Maybe interval tree, in your case, locates smaller number of tetrahedrons to test. Depth is probably like in KD-Tree. – Ante

3 Answers

6
votes

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.)

1
votes

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.

0
votes

This is admittedly a little brainstormy.

Perhaps a custom of a kdTree that uses face-aligned planes instead of axis-aligned ones.

If a point is on the "correct" side of all four planes of a tetrahedron, then it must be inside the tetrahedron. (Right?) And if you're on the wrong side of any plane, then you can not only rule out the current tet, but also any others on that side of the plane.

It seems you should be able to build a tree where each node is a single plane, and a leaf node means you're in one specific tet (assuming the tets never intersect). The tree may be deep, but since each test is only against a plane (rather than a more expensive triangle test) and since a leaf node gives you exactly one answer, it seems like it should be fast.

Building the tree efficiently may prove difficult.