[vtk-developers] bug in vtkPointSet::FindCell

Will Schroeder will.schroeder at kitware.com
Thu Nov 19 09:00:01 EST 2015 

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20151119/3ea5a86f/attachment-0001.html>

More information about the vtk-developers mailing list