Mapping points of the a solid box to a tetrahedral meshed box

Question

Given a 3d solid box with points in it. Given a box meshed with tetraheda. The dimensions of both boxes are the same.

I need to find an algorithm, that maps points of the solid to respective tetrahedra in the mesh.

I used the next algorithm:

1. Refine solid with an octree
2. Iterate over tetrahedra in the mesh and check if it intersects with a branch or a leave of the octree. (Ratschek & Rockne's algorithm)
3. If it intersects, map the points from the octree to the tetrahedron.

But the algorithm is very slow, moreover I have huge problems checking the intersection between a box and a tetrahedron.

I could still stick with an octree, but I definitely need something reasonable to check the intersections. Any comment will be highly appreciated.

UPDATE: I have 2 million solid points and 200k tetrahedra

UPDATE 2: I am trying to implement Walking in a triangulation

Answer 1

One standard simplification would be to first compute approximate octree-tetrahedron intersections using axis-aligned bounding boxes. The resulting intersection tests are then very simple.

Then, once you've traversed to the leaf level of the tree, you can use an exact test to determine which points are contained within a given tetrahedron.

To summarise:

Form an octree T for your points X

for (all tetrahedrons ti in mesh M)

    Form a minimal axis-aligned bounding-box Bi for tetrahedron ti

    Traverse T from root, accumulating a list Li of all leaf nodes 
    that overlap with box Bi

    for (all leaf nodes li in list L)
        for (all points pi in leaf node li)

            if (point pi is inside tetrahedron ti /*exact test*/ )
                Associate point pi with tetrahedron ti
            endif

        endfor
    endfor

endfor

This algorithm is efficient if: (i) the points X are well distributed within the mesh M, and (ii) the tetrahedrons in M have reasonable aspect ratios.

The key to achieving good performance is to ensure that the tree-traversal step is implemented as efficiently as possible.

A point-in-tetrahedron test can be done by checking whether a given point pi lies on the "inner" side of the 4 faces of a tetrahedron. Given a tetrahedron [i,j,k,l], the point pi is on the "inner" side of the face [i,j,k] if it lies on the same side of the plane [i,j,k] as the "opposing" vertex l.

These orientation tests can be performed robustly using adaptive precision arithmetic. Jonathan Shewchuk offers such an implementation here.

Answer 2

Assuming you know the vertices of the tetrahedrons, you can check if a point is inside a tetrahedron, by checking if it lies to the left or rightside of each of its planes, say left is the side pointed along the normal.

The math for determining if a point is to the left or right of a plane is straight forward.

There's another method I found, but looks like a variant of my answer.

Of course, if a point is inside a tet, it gets mapped to the tet. This method can be implemented as a vertex shader or as a OpenCL/CUDA kernel, and that'll make it highly parallel.