[vtkusers] Infinte recursion in vtkDelaunay2D::FindTriangle

Fri Oct 19 08:53:40 EDT 2012

Hi Federico,

The infinite recursion is through CheckEdge(ptId, x, p3, p2, tri),
I've included the repeating segment of the stack trace below (for my
data, it repeats after 42 recursions).  If you can also fix this, then
vtkDelaunay2D will be stable for the very first time.

#14 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=0) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#15 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=6, tri=17) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#16 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=19) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#17 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=19, tri=18) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#18 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=4, tri=20) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#19 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=13, tri=14) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#20 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=16) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#21 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=6, tri=0) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#22 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=17) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#23 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=19, tri=19) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#24 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=4, tri=18) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#25 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=13, tri=20) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#26 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=14) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#27 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=6, tri=16) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#28 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=0) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#29 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=19, tri=17) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#30 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=4, tri=19) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#31 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=13, tri=18) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#32 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=20) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#33 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=6, tri=14) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#34 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=16) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#35 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=19, tri=0) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#36 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=4, tri=17) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#37 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=13, tri=19) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#38 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=18) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#39 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=6, tri=20) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#40 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=14) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#41 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=19, tri=16) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#42 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=4, tri=0) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#43 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=13, tri=17) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#44 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=19) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#45 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=6, tri=18) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#46 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=20) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#47 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=19, tri=14) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#48 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=4, tri=16) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#49 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=13, tri=0) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#50 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=17) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#51 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=6, tri=19) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#52 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=18) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#53 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=19, tri=20) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#54 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=4, tri=14) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#55 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=13, tri=16) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279
#56 0x0000000102301756 in vtkDelaunay2D::CheckEdge (this=0x103fd5010,
ptId=7, x=0x7fff5fbfebe0, p1=7, p2=12, tri=0) at
/Volumes/Work/Kitware/vtk-master/Filters/Core/vtkDelaunay2D.cxx:279

 - David

On Fri, Oct 19, 2012 at 3:08 AM, Federico Bonelli
<federico.bonelli at moxoff.com> wrote:
> From what I see the infinte recursion in CheckEdge is unlinked with
> what I experienced.
> Altough it might be similar: there are 2 statements of recursion in that method
> 1. this->CheckEdge(ptId, x, p3, p2, tri);
> 2. this->CheckEdge(ptId, x, p1, p3, nei);
>
> In the first we check the same triangle, different points, in the
> second we hop on another triangle.
> Can you tell me which of those statements is involved in your infinite
> recursion?
> If it is the second one, it is similar to my case, and I think I could
> try to fix it.
>
> bye,
> Federico
>
> 2012/10/18 David Gobbi <david.gobbi at gmail.com>:
>> 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
>
>
>
> --
> 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