[vtkusers] Infinte recursion in vtkDelaunay2D::FindTriangle
David Gobbi
david.gobbi at gmail.com
Fri Oct 19 12:17:31 EDT 2012
It is 2D horizontal data, the Z is constant:
-90.003341675 0.00333850272 111.89606363
-90.003341675 -21.336583193 111.89606363
-90.003341675 -38.497227269 111.89606363
-72.837493003 -21.331378597 111.89606363
-58.884457413 -7.3783430075 111.89606363
-0.00333850272 51.502775903 111.89606363
11.263012442 62.769126848 111.89606363
26.664563058 78.170677464 111.89606363
56.497227269 108.00334167 111.89606363
37.083480239 108.00334167 111.89606363
-0.00333850272 108.00334167 111.89606363
-90.003341675 108.00334167 111.89606363
Images of the original data, and the expected triangulation are
attached. You can see why numerical instabilities in Delaunay might
cause problems with this data. These kinds of datasets pop up all the
time in my application.
I'll try to get a stack trace with radius2, dist2 to you soon.
- David
On Fri, Oct 19, 2012 at 9:12 AM, Federico Bonelli
<federico.bonelli at moxoff.com> wrote:
> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: delaunay1.png
Type: image/png
Size: 7844 bytes
Desc: not available
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20121019/fc4a27a8/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: delaunay2.png
Type: image/png
Size: 8613 bytes
Desc: not available
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20121019/fc4a27a8/attachment-0001.png>
More information about the vtkusers
mailing list