[vtk-developers] bug in vtkPointSet::FindCell

Mathieu Westphal mathieu.westphal at kitware.com
Thu Nov 19 08:49:28 EST 2015


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


More information about the vtk-developers mailing list