[vtk-developers] bug in vtkPointSet::FindCell

Will Schroeder will.schroeder at kitware.com
Thu Nov 19 09:37:11 EST 2015 

...at some point I'm thinking we step back and rethink this whole
algorithm. For example, there's no reason we couldn't parallelize the
inside cell checks / EvaluatePosition() and then compare/composite the
results. And there may be better spatial search structures to look at....

On Thu, Nov 19, 2015 at 9:19 AM, Berk Geveci <berk.geveci at kitware.com>
wrote:

> 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
>>
>>
>>
>


-- 
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/31310cc0/attachment-0001.html>

More information about the vtk-developers mailing list