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

[Jeff Phillips]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20110220/00f13be4/attachment.htm>