[vtk-developers] bug in vtkPointSet::FindCell
Mathieu Westphal
mathieu.westphal at kitware.com
Thu Nov 19 08:19:14 EST 2015
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20151119/c365f4bc/attachment.html>
More information about the vtk-developers
mailing list