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.<br><br>Jeff<br><br><div class="gmail_quote">On Sun, Feb 20, 2011 at 7:09 PM, David Doria <span dir="ltr"><<a href="mailto:daviddoria@gmail.com">daviddoria@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div></div><div class="h5">On Sun, Feb 20, 2011 at 5:15 PM, Jeff Phillips<br>
<<a href="mailto:jeffrey.s.phillips@gmail.com">jeffrey.s.phillips@gmail.com</a>> wrote:<br>
> Hello VTK users,<br>
> I am looking for an efficient way to find the intersection of a line segment<br>
> (or extension thereof) and the closest of multiple triangular faces in a<br>
> surface mesh. The context is neuroimaging data: the line segments are the<br>
> ending segments of virtual white matter fibers, while the mesh is a cortical<br>
> surface representation (derived from SUMA/FreeSurfer, for those familiar).<br>
> We already have a basic idea of how this could be accomplished, but we<br>
> hoped to poll the VTK user community for knowledge of any potentially useful<br>
> algorithms, before we began to write our own.<br>
> The basic problem is that many of the fiber data (line segments) stop short<br>
> of the target mesh, and we must bridge the gap. The simplest way to do this<br>
> would be to find the nearest node in Euclidean space to the endpoints of the<br>
> fibers. However, the nearest-node method is not adequate: the cortical<br>
> surface is folded in complex and unpredictable ways, and the nearest nodes<br>
> are often not in the direction that the fiber projects, resulting in gross<br>
> misassignment of fiber endpoints to surface locations.<br>
> Our alternative idea is to extend each fiber outwards along the path of its<br>
> final segment and to find its first point of intersection with a face in the<br>
> mesh. (Because of cortical folding patterns, a fiber extension might<br>
> intersect with one face, then cross thin air to intersect a second or third<br>
> face.) However, we are concerned about how to search efficiently, given the<br>
> large number of fibers (in a typical situation, we are trying to find the<br>
> surface projection for several hundred fibers) and the much larger number of<br>
> mesh faces (>200K for the whole brain; perhaps a few hundred likely faces,<br>
> which we might isolate using some heuristic, like taking the 500 nearest<br>
> nodes "as the crow flies").<br>
> As control freaks with inflated senses of our own programming ability, we<br>
> are tempted to dash off and try implementing this in MATLAB, but we realize<br>
> that we could be trying to re-invent the wheel. Do any VTK users know of a<br>
> similar situation with an efficient solution? Any suggestions you can<br>
> provide would be much appreciated,<br>
> Jeff Phillips<br>
<br>
</div></div>Jeff,<br>
<br>
If I understand correctly, you are trying to intersect a ray with a<br>
mesh. This is the best way I've found to do that in VTK:<br>
<br>
<a href="http://www.vtk.org/Wiki/VTK/Examples/Cxx/DataStructures/ModifiedBSPTree_IntersectWithLine" target="_blank">http://www.vtk.org/Wiki/VTK/Examples/Cxx/DataStructures/ModifiedBSPTree_IntersectWithLine</a><br>
<font color="#888888"><br>
David<br>
</font></blockquote></div><br>