CGAL users discussion list

[Olivier Devillers <>]

On 21/03/2014 14:45, Per Zetterlund wrote:
> > > Hi all,
> > >
> > > What is the best way to find which cells (or facets) of
> > > a 3D triangulation that intersects a given line segment?
> > >
> > > Interate through all cells (facets) and check for
> > > intersection (how?) or trace the segment from the
> > > start by going from heighbor to neighbor?

It depends of what do you mean by the best way.

The easiest to code is the former

The most efficient is the latter (as Andreas said):
if your points are random you get only n^(1/3) tetrahedra intersected by 
the line.
However, programming such a walk is painful in 3D, especially if you want to
code correctly all degeneracies.
If your line is defined by pq, when you enter a new tetrahedron abcd 
from face abc,
you can compute the orientations of qpad, pqbd, and pqcd to decide
by which face you exit the tetrahedron (and treat properly all cases 
where you intersect an edge)
Infinite tehtrahedron should not be a problem, you just stop walking.