[vtk-developers] bug in vtkPointSet::FindCell

Will Schroeder will.schroeder at kitware.com
Thu Nov 19 08:45:06 EST 2015 

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

More information about the vtk-developers mailing list