[vtkusers] Infinte recursion in vtkDelaunay2D::FindTriangle

[David Gobbi]

Hi Federico,

I tried your patch, but I'm still seeing infinite recursion.
For me, the infinite recursion is in the CheckEdge()
method.  A short script and dataset that generates the
crash on my system is attached (in python).  I compiled
VTK with gcc-4.2 and the "-O2" level of optimization
(other compiler/optimization combinations might not
generate the same crash, but for gcc-4.2 I see the same
crash on both Linux and on OS X).

 - David

On Thu, Oct 18, 2012 at 12:44 AM, Federico Bonelli
<federico.bonelli at moxoff.com> wrote:
> Hi David, thank you for your answer.
>
> I felt a bit confident yesterday and I tried to fix the bug.
> During the recursion I assumed we don't wanna check the same triangle
> twice, since it won't help anyway.
> I worked around the problem by keeping a stack of the triangles we've
> tried in the recursion, and give up if we'd happen to try the same
> triangle twice.
> I saw that there already was a check for giving up if we're to test
> the same triangle __twice_in_a_row__, but it didn't work for me,
> because I'm in a 4 triangles loop.
>
> Down here is the patch I propose.
>
> Bye and thanks,
> Federico
>
> 2012/10/17 David Gobbi <david.gobbi at gmail.com>:
>> Hi Federico,
>>
>> I've run into this problem, and other people have as well.
>> It's a bug in vtkDelaunay2D, and it is already listed in the
>> VTK bugtracker: certain inputs will cause vtkDelaunay2D
>> to go into infinite recursion.  I do not know of a solution.
>>
>>  - David
>>
>> On Wed, Oct 17, 2012 at 9:33 AM, Federico Bonelli
>> <federico.bonelli at moxoff.com> wrote:
>>> Hello,
>>>
>>> I'm experiencing issues with the method vtkDelaunay2D::FindTriangle,
>>> because it consistently generates an infinite recursion on a case of
>>> mines.
>>> I'm using the nightly-build out of GIT.
>>> Looking at the call stack I discover that the program loops over 4
>>> triangles, using the same pattern over and over again:
>>> id 1, 4, 9, 8, 1, 4, 9, 8, 1, 4, etc etc...
>>>
>>> I'm a bit lost here, what can I do?
>>>
>>> Federico
>>>
>>>
>>> --
>>> Federico Bonelli
>>>
>>> MOXOFF srl
>>> Spinoff del Politecnico di Milano
>>> Via D'Ovidio Francesco, 3 - 20133 Milano (Italia)
>>> tel (+39) 02 3675 4853
>>> web: <http://www.moxoff.com>
>>> --
>>> Sede legale in Milano,
>>> Viale Vittorio Veneto 2/A - 20124 Milano (Italia)
>>> CF/P.IVA 07015910966
>>> Capitale sociale € 50000,00 i.v.
>>> R.E.A.  N. 1929566 - MI
>
>
>
> --
> Federico Bonelli
>
> MOXOFF srl
> Spinoff del Politecnico di Milano
> Via D'Ovidio Francesco, 3 - 20133 Milano (Italia)
> tel (+39) 02 3675 4853
> web: <http://www.moxoff.com>
> --
> Sede legale in Milano,
> Viale Vittorio Veneto 2/A - 20124 Milano (Italia)
> CF/P.IVA 07015910966
> Capitale sociale € 50000,00 i.v.
> R.E.A.  N. 1929566 - MI
-------------- next part --------------
A non-text attachment was scrubbed...
Name: delaunay.py
Type: application/octet-stream
Size: 1588 bytes
Desc: not available
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20121018/c936c51b/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: delaunay.vtp
Type: application/octet-stream
Size: 2596 bytes
Desc: not available
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20121018/c936c51b/attachment-0001.obj>