[vtkusers] FindAndGetCell does not behave as expected. Tolerance not respected

[Bryn Lloyd]

Hi vtk-developers

 

I have been trying to figure out why vtkDataSet::FindAndGetCell does not
find a cell containing a point.

I assumed it might have to do with numerical precision of the inside test,
however, it fails on my data set even when the cell has a good shape (nearly
equilateral triangle).

 

The reason, as I have found, is that if I call the function FindAndGetCell
without an initial cellId (i.e. cellId = -1), then the function starts at
the cells at the closest point and walks to neighboring cells from there.

The walk is stopped after 12 cells. This can be too early depending on the
configuration (see attached screenshot, where FindAndGetCell  could find a
cell for the red points).

 

This parameter is hardcoded in vtkDataSet (#define VTK_MAX_WALK 12) and
cannot be controlled by the user.

 

It seems if the user needs a robust result from FindAndGetCell, then a good
initial guess of cellId should be provided, or vtkCellLocator should be
used.

 

Thanks

Bryn

 

 

 

From: vtkusers-bounces at vtk.org [mailto:vtkusers-bounces at vtk.org] On Behalf
Of Bryn Lloyd
Sent: Thursday, May 05, 2011 8:57 PM
To: vtkusers at vtk.org
Subject: [vtkusers] FindAndGetCell does not behave as expected. Tolerance
not respected

 

Hi

 

I was trying to interpolate values at points by locating the containing cell
and using the parametric coordinates. The cells are 2d triangles (z==0).

 

It seems to me that the function vtkDataSet::FindAndGetCell does not work as
expected!

Sometimes points, which are on the edge of a cell are not classified as
inside. I am aware that due to numerical precision reasons this is not
completely robust, but I would expect that if I increase the Tolerance in
the call to FindAndGelCell then I should get a nearby cell. This does not
always happen!

 

After digging in the code I see that this function returns a vtkCell if
following condition in vtkDataSet::FindCellWalk is fulfilled:

 

    if (   (cell->EvaluatePosition(x, closestPoint, subId,

                                   pcoords, dist2, weights) == 1)

        && (dist2 <= tol2) )

      {

      return cellId;

      }

 

 

 

It often happens that cell->EvaluatePosition returns 0 but, the tolerance
condition is true. Therefore, the tolerance does not have any effect. I
think this should be changed to either:

 

    if (   (cell->EvaluatePosition(x, closestPoint, subId,

                                   pcoords, dist2, weights) == 1)

        || (dist2 <= tol2) )

      {

      return cellId;

      }

 

Or, alternatively the tolerance should be passed on to the cell and used to
evaluate if the point is inside or not. This could for instance be done as
follows:

 

if((pcoords[0] > -tol2) 

&& (pcoords[1] > -tol2)

&& (pcoords[2] > -tol2))

  return 1; // i.e. point inside cell

 

 

 

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20110506/2eceb8fb/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: FindAndGetCell_Failure_WrongInitialCells.png
Type: image/png
Size: 31988 bytes
Desc: not available
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20110506/2eceb8fb/attachment.png>