[vtkusers] efficient method for finding the closest extension of a line segment to several planes

[David Doria]

On Sun, Feb 20, 2011 at 5:15 PM, Jeff Phillips
<jeffrey.s.phillips at gmail.com> wrote:
> Hello VTK users,
> I am looking for an efficient way to find the intersection of a line segment
> (or extension thereof) and the closest of multiple triangular faces in a
> surface mesh.  The context is neuroimaging data:  the line segments are the
> ending segments of virtual white matter fibers, while the mesh is a cortical
> surface representation (derived from SUMA/FreeSurfer, for those familiar).
>  We already have a basic idea of how this could be accomplished, but we
> hoped to poll the VTK user community for knowledge of any potentially useful
> algorithms, before we began to write our own.
> The basic problem is that many of the fiber data (line segments) stop short
> of the target mesh, and we must bridge the gap.  The simplest way to do this
> would be to find the nearest node in Euclidean space to the endpoints of the
> fibers.  However, the nearest-node method is not adequate: the cortical
> surface is folded in complex and unpredictable ways, and the nearest nodes
> are often not in the direction that the fiber projects, resulting in gross
> misassignment of fiber endpoints to surface locations.
> Our alternative idea is to extend each fiber outwards along the path of its
> final segment and to find its first point of intersection with a face in the
> mesh. (Because of cortical folding patterns, a fiber extension might
> intersect with one face, then cross thin air to intersect a second or third
> face.)  However, we are concerned about how to search efficiently, given the
> large number of fibers (in a typical situation, we are trying to find the
> surface projection for several hundred fibers) and the much larger number of
> mesh faces (>200K for the whole brain; perhaps a few hundred likely faces,
> which we might isolate using some heuristic, like taking the 500 nearest
> nodes "as the crow flies").
> As control freaks with inflated senses of our own programming ability, we
> are tempted to dash off and try implementing this in MATLAB, but we realize
> that we could be trying to re-invent the wheel.  Do any VTK users know of a
> similar situation with an efficient solution?  Any suggestions you can
> provide would be much appreciated,
> Jeff Phillips

Jeff,

If I understand correctly, you are trying to intersect a ray with a
mesh. This is the best way I've found to do that in VTK:

http://www.vtk.org/Wiki/VTK/Examples/Cxx/DataStructures/ModifiedBSPTree_IntersectWithLine

David