[vtk-developers] bug in vtkPointSet::FindCell

Berk Geveci berk.geveci at kitware.com
Thu Nov 19 09:19:43 EST 2015 

Guys,

Please make sure that you are running some good performance tests while
making any changes there. Slow-down in FindCell would have a huge impact on
VTK's performance. It could be faster as it is...

-berk

On Thu, Nov 19, 2015 at 8:00 AM, Will Schroeder <will.schroeder at kitware.com>
wrote:

> Yes I was thinking along similar lines. I also checked into the
> implementations of a few cells like vtkTriangle::EvaluatePosition().
> Tolerancing does not seem to be used in the few EvaluatePosition() methods
> I checked so I think using the tolerance is reasonable. However as I'm sure
> you well know, a tolerance effectively defines a fuzzy boundary region
> where a point could lie in more than one cell. In this situation you could
> conceivably keep track of the minimal dist2 and return the corresponding
> cell, but I'm guessing that this would complicate the code and affect
> performance.
>
> W
>
> On Thu, Nov 19, 2015 at 8:49 AM, Mathieu Westphal <
> mathieu.westphal at kitware.com> wrote:
>
>> Well i supose that's what the tolerance (tol2 param) is for, is it not ?
>> at least that is why i have reimplemented it the way i did.
>>
>> Mathieu
>>
>>
>>
>> Mathieu Westphal
>>
>> On Thu, Nov 19, 2015 at 2:45 PM, Will Schroeder <
>> will.schroeder at kitware.com> wrote:
>>
>>> I'm thinking there are two basic use cases. First, find the cell that
>>> contains the point (x must be in the cell); and second, find a cell very
>>> close to the point from which to launch additional searches or other local
>>> operations. I'm wondering if we can adjust the design / API / etc. to
>>> explicitly control for this.
>>>
>>> Thoughts?
>>>
>>> W
>>>
>>> On Thu, Nov 19, 2015 at 8:19 AM, Mathieu Westphal <
>>> mathieu.westphal at kitware.com> wrote:
>>>
>>>> Hi
>>>>
>>>> I have seen no notable difference of performance with the algorithm i
>>>> was working on. But it will find more cell , especially in certain cases,
>>>> so the results of algorithms dependent of FindCell will be different. we
>>>> need to determine which one is right and which one is wrong.
>>>>
>>>> Mathieu
>>>>
>>>> Mathieu Westphal
>>>>
>>>> On Thu, Nov 19, 2015 at 2:13 PM, Will Schroeder <
>>>> will.schroeder at kitware.com> wrote:
>>>>
>>>>> It was a long weekend :-)
>>>>>
>>>>> So the key section of code is:
>>>>>
>>>>>   int ret = cell->EvaluatePosition(x, closestPoint, subId, pcoords,
>>>>> dist2, weights);
>>>>>   if (ret == 1 || ( ret == 0 && dist2 <= tol2))
>>>>>
>>>>> I'm guessing that the if clause (ret == 0 && dist2 <= tol2) is
>>>>> basically identifying a cell in which to begin further searching, despite
>>>>> the fact that point x is not actually in the cell. So there is more
>>>>> likelihood of finding the containing cell. Does this affect performance
>>>>> significantly?
>>>>>
>>>>> W
>>>>>
>>>>>
>>>>> On Thu, Nov 19, 2015 at 4:33 AM, Joachim Pouderoux <
>>>>> joachim.pouderoux at kitware.com> wrote:
>>>>>
>>>>>> Will-
>>>>>>
>>>>>> I am pretty sure the weekend is over now ;)
>>>>>> Do you think Mathieu's patch make sense?
>>>>>> So far it breaks some tests and we need to analyze if the some of the
>>>>>> new results are more appropriate or just incorrect...
>>>>>>
>>>>>> Best,
>>>>>> Joachim
>>>>>>
>>>>>>
>>>>>> *Joachim Pouderoux*
>>>>>>
>>>>>> *PhD, Technical Expert*
>>>>>> *Kitware SAS <http://www.kitware.fr>*
>>>>>>
>>>>>>
>>>>>> 2015-07-15 14:16 GMT+02:00 Mathieu Westphal <
>>>>>> mathieu.westphal at kitware.com>:
>>>>>>
>>>>>>> Hello
>>>>>>>
>>>>>>> I've created a fix for FindCell :
>>>>>>> https://gitlab.kitware.com/vtk/vtk/merge_requests/399
>>>>>>>
>>>>>>> But they are a dozen of bugs, can I have your advice about my fix
>>>>>>> and what would be the correct way to do it ?
>>>>>>>
>>>>>>>
>>>>>>> Mathieu Westphal
>>>>>>>
>>>>>>> On Thu, Jul 9, 2015 at 5:03 PM, Mathieu Westphal <
>>>>>>> mathieu.westphal at kitware.com> wrote:
>>>>>>>
>>>>>>>> I have no better solution for topological cracks that what is
>>>>>>>> currently implemented with the radius.
>>>>>>>> Actually i've looking at it too fast, there is no design problem in
>>>>>>>> the current implementation, and I understand complettelly why we need to
>>>>>>>> limit the walk.
>>>>>>>>
>>>>>>>> However there is a typo !
>>>>>>>>     if(cell->EvaluatePosition(x, closestPoint, subId,
>>>>>>>>                                      pcoords, dist2, weights) == 1
>>>>>>>>         && (dist2 <= tol2))
>>>>>>>>       {
>>>>>>>>       return cellId;
>>>>>>>>       }
>>>>>>>>
>>>>>>>> Should be :
>>>>>>>>
>>>>>>>>     int ret = cell->EvaluatePosition(x, closestPoint, subId,
>>>>>>>>                                      pcoords, dist2, weights);
>>>>>>>>     if (ret == 1 || ( ret == 0 && dist2 <= tol2))
>>>>>>>>       {
>>>>>>>>       return cellId;
>>>>>>>>       }
>>>>>>>>
>>>>>>>> Doesn't it ?
>>>>>>>>
>>>>>>>>
>>>>>>>> Mathieu Westphal
>>>>>>>>
>>>>>>>> On Thu, Jul 9, 2015 at 4:15 PM, Will Schroeder <
>>>>>>>> will.schroeder at kitware.com> wrote:
>>>>>>>>
>>>>>>>>> Mathieu-
>>>>>>>>>
>>>>>>>>> I am going to look this over on the weekend. There are several
>>>>>>>>> known issues due to a variety of complex reasons; and if I remember right
>>>>>>>>> there are pathological cases with what you propose (walking across
>>>>>>>>> neighbors) because if there is topological separation/cracks between
>>>>>>>>> neighboring cells it's possible to fail too.
>>>>>>>>>
>>>>>>>>> Anyway I'll have a chance to look this weekend and we'll talk
>>>>>>>>> soon. I think the bottom line is that to 100% guarantee to find the
>>>>>>>>> containing cell a cell locator is needed, but for performance/memory
>>>>>>>>> reasons a point locator has been used in the past (unfortunately a
>>>>>>>>> performance tradeoff that comes back to bite us repeatedly). There may be
>>>>>>>>> more intelligent ways to consider the N closest points from FindPoint which
>>>>>>>>> may produce better results and don't cost too much in performance/memory.
>>>>>>>>>
>>>>>>>>> W
>>>>>>>>>
>>>>>>>>> On Thu, Jul 9, 2015 at 6:10 AM, Mathieu Westphal <
>>>>>>>>> mathieu.westphal at kitware.com> wrote:
>>>>>>>>>
>>>>>>>>>> There is a bug in vtkPointCell::FindCell
>>>>>>>>>>
>>>>>>>>>> I copy here my mantis bug and associated notes:
>>>>>>>>>> http://www.vtk.org/Bug/view.php?id=15573
>>>>>>>>>>
>>>>>>>>>> The current implementation of FindCell/ FindCellWalk is just
>>>>>>>>>> wrong and not working in some case :
>>>>>>>>>>
>>>>>>>>>> See atached image.
>>>>>>>>>> In the current implementation there is three pass :
>>>>>>>>>>
>>>>>>>>>> 1 : FindPoint, Check CellPoint
>>>>>>>>>> 2 : Check first neighbor
>>>>>>>>>> 3 : Check CellPoint within tolerance
>>>>>>>>>>
>>>>>>>>>> In the associated image, one can see the the first pass will find
>>>>>>>>>> red star and only check Cell 1
>>>>>>>>>> the second pass will only check cell 2
>>>>>>>>>> the third pass will not check anything more
>>>>>>>>>>
>>>>>>>>>> Cell 3 will never be found.
>>>>>>>>>>
>>>>>>>>>> I propose a solution based on vtkStreamTracer surface
>>>>>>>>>> implementation, which walk among neighbors more smartly using pcoords and
>>>>>>>>>> cell boundary.
>>>>>>>>>>
>>>>>>>>>> See :
>>>>>>>>>>
>>>>>>>>>> https://gitlab.kitware.com/vtk/vtk/blob/master/Filters/FlowPaths/vtkAbstractInterpolatedVelocityField.cxx#L289
>>>>>>>>>> [^
>>>>>>>>>> <https://gitlab.kitware.com/vtk/vtk/blob/master/Filters/FlowPaths/vtkAbstractInterpolatedVelocityField.cxx#L289>
>>>>>>>>>> ]
>>>>>>>>>>
>>>>>>>>>> What do you think ?
>>>>>>>>>>
>>>>>>>>>> Mathieu Westphal
>>>>>>>>>>
>>>>>>>>>> _______________________________________________
>>>>>>>>>> Powered by www.kitware.com
>>>>>>>>>>
>>>>>>>>>> Visit other Kitware open-source projects at
>>>>>>>>>> http://www.kitware.com/opensource/opensource.html
>>>>>>>>>>
>>>>>>>>>> Search the list archives at:
>>>>>>>>>> http://markmail.org/search/?q=vtk-developers
>>>>>>>>>>
>>>>>>>>>> Follow this link to subscribe/unsubscribe:
>>>>>>>>>> http://public.kitware.com/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) 881-4902
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> Powered by www.kitware.com
>>>>>>>
>>>>>>> Visit other Kitware open-source projects at
>>>>>>> http://www.kitware.com/opensource/opensource.html
>>>>>>>
>>>>>>> Search the list archives at:
>>>>>>> http://markmail.org/search/?q=vtk-developers
>>>>>>>
>>>>>>> Follow this link to subscribe/unsubscribe:
>>>>>>> http://public.kitware.com/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) 881-4902
>>>>>
>>>>
>>>>
>>>
>>>
>>> --
>>> William J. Schroeder, PhD
>>> Kitware, Inc.
>>> 28 Corporate Drive
>>> Clifton Park, NY 12065
>>> will.schroeder at kitware.com
>>> http://www.kitware.com
>>> (518) 881-4902
>>>
>>
>>
>
>
> --
> William J. Schroeder, PhD
> Kitware, Inc.
> 28 Corporate Drive
> Clifton Park, NY 12065
> will.schroeder at kitware.com
> http://www.kitware.com
> (518) 881-4902
>
> _______________________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Search the list archives at: http://markmail.org/search/?q=vtk-developers
>
> Follow this link to subscribe/unsubscribe:
> http://public.kitware.com/mailman/listinfo/vtk-developers
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20151119/ea894880/attachment-0001.html>

More information about the vtk-developers mailing list