<div dir="ltr">Guys,<div><br></div><div>Please make sure that you are running some good performance tests while making any changes there. Slow-down in FindCell would have a huge impact on VTK's performance. It could be faster as it is...</div><div><br></div><div>-berk</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Nov 19, 2015 at 8:00 AM, 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">Yes I was thinking along similar lines. I also checked into the implementations of a few cells like vtkTriangle::EvaluatePosition(). Tolerancing does not seem to be used in the few EvaluatePosition() methods I checked so I think using the tolerance is reasonable. However as I'm sure you well know, a tolerance effectively defines a fuzzy boundary region where a point could lie in more than one cell. In this situation you could conceivably keep track of the minimal dist2 and return the corresponding cell, but I'm guessing that this would complicate the code and affect performance.<span class="HOEnZb"><font color="#888888"><div><br></div><div>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:49 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>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<span><font color="#888888"><br><div><br><br></div></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: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><font color="#888888"><div><br>W</div></font></span></div><div><div><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="151200bd6199787d_1512001d385fa68f_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></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><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>