[vtkusers] Infinte recursion in vtkDelaunay2D::FindTriangle
Federico Bonelli
federico.bonelli at moxoff.com
Fri Oct 19 11:12:39 EDT 2012
I investigated a bit further.
Do you have 3D data or 2D data?
All this part of the code accepts 3D data but ignores the 3rd
component, plain and simple.
For horizontal or almost horizontal surfaces it's no big deal, but if
you're trying to triangulate a vertical wall-ish thing, you're gonna
have a bad time.
I wonder if it is working as intended or else.
Federico
2012/10/19 Federico Bonelli <federico.bonelli at moxoff.com>:
> This is interesting, because it seems like the Delaunay flipping
> algorithm is failing to produce Delaunay triangles, which is
> impossible in exact arithmetic.
> This because when the recursion get back to the line
> if ( this->InCircle (x3, x, x1, x2) )
> a second time on the same triangle on a freshly flipped edge, it does
> detect that the flip was unsuccessful.
>
> It'd be interesting if you could give me, along with the stack trace,
> the values of radius2 and dist2 in the ::InCircle method as it keep
> getting called by the CheckEdge method.
>
> I bet that radius2 and dist2 are quite close in your case, and the
> fixed tolerance used in ::InCircle is wrong for you.
> Can you print those info?
>
>
> 2012/10/19 David Gobbi <david.gobbi at gmail.com>:
>> 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
>
>
>
> --
> 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
More information about the vtkusers
mailing list