<div dir="ltr"><div>Well i supose that's what the tolerance (tol2 param) is for, is it not ? at least that is why i have reimplemented it the way i did.<br><br></div>Mathieu<br><div><br><br></div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature"><div dir="ltr">Mathieu Westphal<br></div></div></div>
<br><div class="gmail_quote">On Thu, Nov 19, 2015 at 2:45 PM, Will Schroeder <span dir="ltr"><<a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I'm thinking there are two basic use cases. First, find the cell that contains the point (x must be in the cell); and second, find a cell very close to the point from which to launch additional searches or other local operations. I'm wondering if we can adjust the design / API / etc. to explicitly control for this.<div><br></div><div>Thoughts?</div><span class="HOEnZb"><font color="#888888"><div><br>W</div></font></span></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Nov 19, 2015 at 8:19 AM, Mathieu Westphal <span dir="ltr"><<a href="mailto:mathieu.westphal@kitware.com" target="_blank">mathieu.westphal@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Hi<br><br>I have seen no notable difference of performance with the algorithm i was working on. But it will find more cell , especially in certain cases, so the results of algorithms dependent of FindCell will be different. we need to determine which one is right and which one is wrong.<br><br></div>Mathieu<span><font color="#888888"><br></font></span></div><div class="gmail_extra"><span><font color="#888888"><br clear="all"><div><div><div dir="ltr">Mathieu Westphal<br></div></div></div></font></span><div><div>
<br><div class="gmail_quote">On Thu, Nov 19, 2015 at 2:13 PM, Will Schroeder <span dir="ltr"><<a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">It was a long weekend :-)<div><br></div><div>So the key section of code is:</div><span><div><br></div><div><div>  int ret = cell->EvaluatePosition(x, closestPoint, subId, pcoords, dist2, weights);</div><div>  if (ret == 1 || ( ret == 0 && dist2 <= tol2))</div></div><div><br></div></span><div>I'm guessing that the if clause (ret == 0 && dist2 <= tol2) is basically identifying a cell in which to begin further searching, despite the fact that point x is not actually in the cell. So there is more likelihood of finding the containing cell. Does this affect performance significantly?</div><span><font color="#888888"><div><br>W</div></font></span><div><div><div><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Nov 19, 2015 at 4:33 AM, Joachim Pouderoux <span dir="ltr"><<a href="mailto:joachim.pouderoux@kitware.com" target="_blank">joachim.pouderoux@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div><div><div>Will-<br><br></div>I am pretty sure the weekend is over now ;)<br>Do you think Mathieu's patch make sense?<br></div>So far it breaks some tests and we need to analyze if the some of the new results are more appropriate or just incorrect...<br><br></div>Best,<br></div>Joachim<br><div><div><br></div></div></div><div class="gmail_extra"><br clear="all"><div><div><div dir="ltr"><b>Joachim Pouderoux</b><br><blockquote style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><font size="1"><i>PhD, Technical Expert</i></font><br><b><font size="1"><a href="http://www.kitware.fr" target="_blank">Kitware SAS</a></font></b><br></blockquote>
</div></div></div><div><div>
<br><div class="gmail_quote">2015-07-15 14:16 GMT+02:00 Mathieu Westphal <span dir="ltr"><<a href="mailto:mathieu.westphal@kitware.com" target="_blank">mathieu.westphal@kitware.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div>Hello<br><br></div>I've created a fix for FindCell :<br><a href="https://gitlab.kitware.com/vtk/vtk/merge_requests/399" target="_blank">https://gitlab.kitware.com/vtk/vtk/merge_requests/399</a><br><br></div>But they are a dozen of bugs, can I have your advice about my fix and what would be the correct way to do it ?<span><font color="#888888"><br><br></font></span></div><div class="gmail_extra"><span><font color="#888888"><br clear="all"><div><div><div dir="ltr">Mathieu Westphal<br></div></div></div></font></span><div><div>
<br><div class="gmail_quote">On Thu, Jul 9, 2015 at 5:03 PM, Mathieu Westphal <span dir="ltr"><<a href="mailto:mathieu.westphal@kitware.com" target="_blank">mathieu.westphal@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div><div><div>I have no better solution for topological cracks that what is currently implemented with the radius.<br></div></div>Actually i've looking at it too fast, there is no design problem in the current implementation, and I understand complettelly why we need to limit the walk.<br><br></div>However there is a typo !<br>    if(cell->EvaluatePosition(x, closestPoint, subId,<br>                                     pcoords, dist2, weights) == 1<br>        && (dist2 <= tol2))<br>      {   <br>      return cellId;<br>      }   <br><br></div><div>Should be :<br></div><br><div><div><div><div>    int ret = cell->EvaluatePosition(x, closestPoint, subId,<br>                                     pcoords, dist2, weights);<br>    if (ret == 1 || ( ret == 0 && dist2 <= tol2))<br>      {   <br>      return cellId;<br>      }   <br><br></div><div>Doesn't it ?<span><font color="#888888"><br></font></span></div><span><font color="#888888"><div><br></div></font></span></div></div></div></div><div class="gmail_extra"><span><font color="#888888"><br clear="all"><div><div><div dir="ltr">Mathieu Westphal<br></div></div></div></font></span><div><div>
<br><div class="gmail_quote">On Thu, Jul 9, 2015 at 4:15 PM, Will Schroeder <span dir="ltr"><<a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Mathieu-<div><br></div><div>I am going to look this over on the weekend. There are several known issues due to a variety of complex reasons; and if I remember right there are pathological cases with what you propose (walking across neighbors) because if there is topological separation/cracks between neighboring cells it's possible to fail too.</div><div><br></div><div>Anyway I'll have a chance to look this weekend and we'll talk soon. I think the bottom line is that to 100% guarantee to find the containing cell a cell locator is needed, but for performance/memory reasons a point locator has been used in the past (unfortunately a performance tradeoff that comes back to bite us repeatedly). There may be more intelligent ways to consider the N closest points from FindPoint which may produce better results and don't cost too much in performance/memory.</div><div><br></div><div>W</div></div><div class="gmail_extra"><br><div class="gmail_quote"><div><div>On Thu, Jul 9, 2015 at 6:10 AM, Mathieu Westphal <span dir="ltr"><<a href="mailto:mathieu.westphal@kitware.com" target="_blank">mathieu.westphal@kitware.com</a>></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div><div dir="ltr"><div><div>There is a bug in vtkPointCell::FindCell<br><br></div>I copy here my mantis bug and associated notes:<br><a href="http://www.vtk.org/Bug/view.php?id=15573" target="_blank">http://www.vtk.org/Bug/view.php?id=15573</a><br><br>The current implementation of FindCell/ FindCellWalk is just wrong and not working in some case :<br>
<br>
See atached image.<br>
In the current implementation there is three pass :<br>
<br>
1 : FindPoint, Check CellPoint<br>
2 : Check first neighbor<br>
3 : Check CellPoint within tolerance<br>
<br>
In the associated image, one can see the the first pass will find red star and only check Cell 1<br>
the second pass will only check cell 2<br>
the third pass will not check anything more<br>
<br>
Cell 3 will never be found.<br><br><a name="1511ffe27758e620_1511fe622144128b_1511fe19571a7ab5_1511fda65f5b5909_1511fda44208158f_1511f17f77f5fbb3_14e91a4d2b7b59b2_14e73575aa288e28_14e732c80e2e5630_14e724b6ec8e85d8_bugnotes">I propose a solution based on 
vtkStreamTracer surface implementation, which walk among neighbors more 
smartly using pcoords and cell boundary.<br>
<br>
See :<br>
</a><a href="https://gitlab.kitware.com/vtk/vtk/blob/master/Filters/FlowPaths/vtkAbstractInterpolatedVelocityField.cxx#L289" target="_blank">https://gitlab.kitware.com/vtk/vtk/blob/master/Filters/FlowPaths/vtkAbstractInterpolatedVelocityField.cxx#L289</a> [<a href="https://gitlab.kitware.com/vtk/vtk/blob/master/Filters/FlowPaths/vtkAbstractInterpolatedVelocityField.cxx#L289" target="_blank">^</a>]<br><br></div>What do you think ?<span><font color="#888888"><br><div><br clear="all"><div><div><div><div><div dir="ltr">Mathieu Westphal<br></div></div></div>
</div></div></div></font></span></div>
<br></div></div>_______________________________________________<br>
Powered by <a href="http://www.kitware.com" rel="noreferrer" target="_blank">www.kitware.com</a><br>
<br>
Visit other Kitware open-source projects at <a href="http://www.kitware.com/opensource/opensource.html" rel="noreferrer" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
<br>
Search the list archives at: <a href="http://markmail.org/search/?q=vtk-developers" rel="noreferrer" target="_blank">http://markmail.org/search/?q=vtk-developers</a><br>
<br>
Follow this link to subscribe/unsubscribe:<br>
<a href="http://public.kitware.com/mailman/listinfo/vtk-developers" rel="noreferrer" target="_blank">http://public.kitware.com/mailman/listinfo/vtk-developers</a><br>
<br>
<br></blockquote></div><span><font color="#888888"><br><br clear="all"><div><br></div>-- <br><div>William J. Schroeder, PhD<br>Kitware, Inc.<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a><br><a href="http://www.kitware.com" target="_blank">http://www.kitware.com</a><br><a href="tel:%28518%29%20881-4902" value="+15188814902" target="_blank">(518) 881-4902</a></div>
</font></span></div>
</blockquote></div><br></div></div></div>
</blockquote></div><br></div></div></div>
<br>_______________________________________________<br>
Powered by <a href="http://www.kitware.com" rel="noreferrer" target="_blank">www.kitware.com</a><br>
<br>
Visit other Kitware open-source projects at <a href="http://www.kitware.com/opensource/opensource.html" rel="noreferrer" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
<br>
Search the list archives at: <a href="http://markmail.org/search/?q=vtk-developers" rel="noreferrer" target="_blank">http://markmail.org/search/?q=vtk-developers</a><br>
<br>
Follow this link to subscribe/unsubscribe:<br>
<a href="http://public.kitware.com/mailman/listinfo/vtk-developers" rel="noreferrer" target="_blank">http://public.kitware.com/mailman/listinfo/vtk-developers</a><br>
<br>
<br></blockquote></div><br></div></div></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div>William J. Schroeder, PhD<br>Kitware, Inc.<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a><br><a href="http://www.kitware.com" target="_blank">http://www.kitware.com</a><br><a href="tel:%28518%29%20881-4902" value="+15188814902" target="_blank">(518) 881-4902</a></div>
</div></div></div></div>
</blockquote></div><br></div></div></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div>William J. Schroeder, PhD<br>Kitware, Inc.<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a><br><a href="http://www.kitware.com" target="_blank">http://www.kitware.com</a><br><a href="tel:%28518%29%20881-4902" value="+15188814902" target="_blank">(518) 881-4902</a></div>
</div>
</div></div></blockquote></div><br></div>