[vtk-developers] bug in vtkPointSet::FindCell

[Will Schroeder]

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