[vtkusers] Infinte recursion in vtkDelaunay2D::FindTriangle

[Federico Bonelli]

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

<<<<< diff here >>>>>>>>>>>>
diff --git a/Filters/Core/vtkDelaunay2D.cxx b/Filters/Core/vtkDelaunay2D.cxx
index 49ec06d..440cfa9 100644
--- a/Filters/Core/vtkDelaunay2D.cxx
+++ b/Filters/Core/vtkDelaunay2D.cxx
@@ -113,11 +113,18 @@ int vtkDelaunay2D::InCircle (double x[3], double
x1[3], double x2[3],
 // and nei[2] are the vertices defining the edge.
 vtkIdType vtkDelaunay2D::FindTriangle(double x[3], vtkIdType ptIds[3],
                                       vtkIdType tri, double tol,
-                                      vtkIdType nei[3], vtkIdList *neighbors)
+                                      vtkIdType nei[3], vtkIdList
*neighbors, vtkIdList *tried)
 {
-  int i, j, ir, ic, inside, i2, i3;
+  int i, j, ir, ic, inside, i2, i3, cleanUpTried = 0;
   vtkIdType *pts, npts, newNei;
   double p[3][3], n[2], vp[2], vx[2], dp, minProj;
+
+  if( tried == NULL ){
+      cleanUpTried = 1;
+      tried = vtkIdList::New();
+  }
+
+  tried->InsertNextId(tri);

   // get local triangle info
   this->Mesh->GetCellPoints(tri,npts,pts);
@@ -156,6 +163,7 @@ vtkIdType vtkDelaunay2D::FindTriangle(double x[3],
vtkIdType ptIds[3],
     if ( vtkMath::Normalize2D(vx) <= tol )
       {
       this->NumberOfDuplicatePoints++;
+      if( cleanUpTried ) { tried->Delete(); }
       return -1;
       }

@@ -176,6 +184,7 @@ vtkIdType vtkDelaunay2D::FindTriangle(double x[3],
vtkIdType ptIds[3],
   if ( inside ) // all edges have tested positive
     {
     nei[0] = (-1);
+    if( cleanUpTried ) { tried->Delete(); }
     return tri;
     }

@@ -183,6 +192,7 @@ vtkIdType vtkDelaunay2D::FindTriangle(double x[3],
vtkIdType ptIds[3],
     {
     this->Mesh->GetCellEdgeNeighbors(tri,nei[1],nei[2],neighbors);
     nei[0] = neighbors->GetId(0);
+    if( cleanUpTried ) { tried->Delete(); }
     return tri;
     }

@@ -192,12 +202,19 @@ vtkIdType vtkDelaunay2D::FindTriangle(double
x[3], vtkIdType ptIds[3],
     if ( (newNei=neighbors->GetId(0)) == nei[0] )
       {
       this->NumberOfDegeneracies++;
+      if( cleanUpTried ) { tried->Delete(); }
       return -1;
       }
     else
       {
+        // check if newId was done already
+        for( vtkIdType triedId = 0; triedId <
tried->GetNumberOfIds(); ++triedId){
+            if( newNei == tried->GetId(tried->GetNumberOfIds() - 1 - triedId)){
+                return -1;
+            }
+        }
       nei[0] = tri;
-      return this->FindTriangle(x,ptIds,newNei,tol,nei,neighbors);
+      return this->FindTriangle(x,ptIds,newNei,tol,nei,neighbors, tried);
       }
     }
 }
(END)

diff --git a/Filters/Core/vtkDelaunay2D.h b/Filters/Core/vtkDelaunay2D.h
index b647a15..55ddb87 100644
--- a/Filters/Core/vtkDelaunay2D.h
+++ b/Filters/Core/vtkDelaunay2D.h
@@ -256,7 +256,7 @@ private:

   int InCircle (double x[3], double x1[3], double x2[3], double x3[3]);
   vtkIdType FindTriangle(double x[3], vtkIdType ptIds[3], vtkIdType tri,
-                         double tol, vtkIdType nei[3], vtkIdList *neighbors);
+                         double tol, vtkIdType nei[3], vtkIdList
*neighbors, vtkIdList *tried = NULL);
   void CheckEdge(vtkIdType ptId, double x[3], vtkIdType p1, vtkIdType p2,
                  vtkIdType tri);


<<<<<<<< end diff >>>>>>>>>>>>

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