[vtk-developers] vtkCell::IntersectWithLine issues

[Will Schroeder]

Whenever you are dealing with intersections you are dealing with tolerances.
And when you deal with tolerances things get tricky. It is not unusual for a
ray very close to an edge to indicate a hit when arriving from one
direction, and indicate a miss when arriving from another, despite the fact
that they pass through the same point closest to the edge. This is why
commercial geometric modelers typically have additional logic to bring
topological information to bear on problems like this. In your case for
example, you could enforce two hits (assuming that you are working with 3D
cells), or just one hit in the cases where it hits an edge or vertex.

The code in VTK handles near misses through a tolerancing mechanism. Since
it is not a geometric modeler, it is not as thorough as it could be. Of
course, there is always the possibility that there is a bug, and its not as
complex as I am making it out to be.

In situations like this it's a good idea to construct more robust, fault
tolerant algorithms. Anticipating failure due to precision issues in
geometric computation is generally very desireable, and yields better
results. For example, rather than intersecting, you could try sampling a
sequence of points along the line, and then logicially build all the cells
along the line using a combination of geometric and tolopological
relationships.

W



On Wed, Jul 2, 2008 at 6:03 AM, Kaushik . <shekhar.kaushik at gmail.com> wrote:

>
>
> On Wed, Jul 2, 2008 at 3:01 PM, Will Schroeder <will.schroeder at kitware.com>
> wrote:
>
>> "From these faces I choose the one that is nearer to the
>> end point of the ray and the next cell to search is the cell adjacent to
>> the chosen face."
>>
>> What does it mean to have a face nearer to an end point? How are you
>> determining this? This is not as straight frward as it sounds and could be
>> an issue.
>
>
> I find the intersection point of each face with the line segment (
> representing the viewing ray in world coordinates ).
> From those faces that intersect the line , i choose the one whose
> intersection point is closest to the farther point of the
> viewing ray. And I need only those cells that intersect the viewing ray .
> Only these cell will contribute to the color value
> at the corresponding pixel.
>
> I find some peculiar outputs from the intersection calculations. When I
> find the intersections with the faces of a cell, I get
> cases where the line intersects only one face. This does not make sense as
> I have confirmed the ray for sure does not end within the cell
>
> Upon looking into the code (vtkQuad.cxx) , I found that the intersection is
> done by splitting the quad along one of the
> diagonal into two triangles. What happens when the line passes exactly
> through the diagonal of the quad ? Does the
> triangle intersection handle this ?
>
> shekhar
>
>
>>
>> W
>>
>> 2008/7/1 Kaushik . <shekhar.kaushik at gmail.com>:
>>
>>>  Hi
>>>
>>> I am trying to implement the following algorithm and I am stuck. I need
>>> to cast rays
>>> from each pixel into a dataset. Along each ray , I need to find the first
>>> cell that satisfies
>>> some characteristics. I go about implementing it as follows :
>>> Using the vtkCellLocator::IntersectWithLine() , i find the first cell the
>>> ray intersects in the dataset.
>>> If this cell satisfies the conditions , we exit.
>>> else we continue searching cells along the ray until one such cell is
>>> found , or until we eventually reach
>>> the boundary of the dataset.
>>> Now this searching cell along a ray is causing me trouble. Given the
>>> first cell that the ray intersected,
>>> I find the faces of the cell that the ray intersects. From these faces I
>>> choose the one that is nearer to the
>>> end point of the ray and the next cell to search is the cell adjacent to
>>> the chosen face.
>>> The algorithm seems to be correct logically atleast.
>>>
>>> The vtkCell::IntersectWithLine() functions however seem to be giving
>>> inconsistent results ! Are there
>>> any known issues with these functions ? Please advise.
>>>
>>> Also can you please comment on the algorithm above ? Is there any other
>>> way( better ? ) to do the same ?
>>>
>>> --
>>> shekhar
>>> _______________________________________________
>>> vtk-developers mailing list
>>> vtk-developers at vtk.org
>>> http://www.vtk.org/mailman/listinfo/vtk-developers
>>>
>>>
>>
>>
>> --
>> William J. Schroeder, PhD
>> Kitware, Inc.
>> 28 Corporate Drive
>> Clifton Park, NY 12065
>> will.schroeder at kitware.com
>> http://www.kitware.com
>> 518-371-3971 (phone and fax)
>
>
>
>
>


-- 
William J. Schroeder, PhD
Kitware, Inc.
28 Corporate Drive
Clifton Park, NY 12065
will.schroeder at kitware.com
http://www.kitware.com
518-371-3971 (phone and fax)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20080702/b5c2b626/attachment.html>