<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 12 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal>Hi vtk-developers<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I have been trying to figure out why vtkDataSet::FindAndGetCell does not find a cell containing a point.<o:p></o:p></p><p class=MsoNormal>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).<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>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.<o:p></o:p></p><p class=MsoNormal>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).<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal style='text-autospace:none'>This parameter is hardcoded in<span style='font-size:9.5pt;font-family:Consolas'> vtkDataSet (<span style='color:blue'>#define</span> VTK_MAX_WALK 12</span>) and cannot be controlled by the user.<o:p></o:p></p><p class=MsoNormal style='text-autospace:none'><o:p> </o:p></p><p class=MsoNormal style='text-autospace:none'>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.<o:p></o:p></p><p class=MsoNormal style='text-autospace:none'><o:p> </o:p></p><p class=MsoNormal style='text-autospace:none'>Thanks<o:p></o:p></p><p class=MsoNormal style='text-autospace:none'>Bryn<o:p></o:p></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p><div><div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in'><p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'> vtkusers-bounces@vtk.org [mailto:vtkusers-bounces@vtk.org] <b>On Behalf Of </b>Bryn Lloyd<br><b>Sent:</b> Thursday, May 05, 2011 8:57 PM<br><b>To:</b> vtkusers@vtk.org<br><b>Subject:</b> [vtkusers] FindAndGetCell does not behave as expected. Tolerance not respected<o:p></o:p></span></p></div></div><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Hi<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>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).<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>It seems to me that the function vtkDataSet::FindAndGetCell does not work as expected!<o:p></o:p></p><p class=MsoNormal>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!<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal style='text-autospace:none'>After digging in the code I see that this function returns a vtkCell if following condition in vtkDataSet::<span style='font-size:9.5pt;font-family:Consolas'>FindCellWalk </span>is fulfilled:<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> <span style='color:blue'>if</span> ( (cell->EvaluatePosition(x, closestPoint, subId,<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> pcoords, dist2, weights) == 1)<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> && (dist2 <= tol2) )<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> {<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> <span style='color:blue'>return</span> cellId;<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> }<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>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:<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> <span style='color:blue'>if</span> ( (cell->EvaluatePosition(x, closestPoint, subId,<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> pcoords, dist2, weights) == 1)<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> || (dist2 <= tol2) )<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> {<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> <span style='color:blue'>return</span> cellId;<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> }<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'>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:<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'>if((pcoords[0] > -tol2) <o:p></o:p></span></p><p class=MsoNormal style='text-indent:.5in;text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'>&& (pcoords[1] > -tol2)<o:p></o:p></span></p><p class=MsoNormal style='text-indent:.5in;text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'>&& (pcoords[2] > -tol2))<o:p></o:p></span></p><p class=MsoNormal style='text-autospace:none'><span style='font-size:9.5pt;font-family:Consolas'> return 1; // i.e. point inside cell<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>