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

[Jeff Phillips]

Thanks for the suggestion, David--this does look like it will speed things
up for us quite a bit.  We're working on implementing this now.

Jeff

On Sun, Feb 20, 2011 at 7:09 PM, David Doria <daviddoria at gmail.com> wrote:

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