<div dir="ltr">Geoff-<div><br></div><div>This is exactly the feedback I need, thank you for doing this work! Is there any chance I can get my hands on a sample dataset? Also, did you try playing around with the binning dimensions (i.e., Divisions) and number of points per bucket....try setting these to a large number like 500^3 and 1 (there is very little penalty to doing this). Also did you try building this with TBB/threading enabled?</div><div><br></div><div>There is no doubt that in certain situations a hierarchical locator is going to be faster than uniform binning, but so far the vtkStaticPointLocator is much faster than VTK's octree and kdtree in the tests I've used, so I'd like to see a representative workflow and work through the bottlenecks, and maybe implement other threaded locators.</div><div><br></div><div>Best,</div><div>W</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Feb 29, 2016 at 5:25 PM, Geoff Wright <span dir="ltr"><<a href="mailto:gpwright@gmail.com" target="_blank">gpwright@gmail.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">Hi Will,<div><br></div><div>I took a look at the new capabilities in vtkPointCloud, it looks very nice, definitely adding some much needed capabilities. I have a PCL pre-processing step that does a bunch of octree-based filtering prior to populating a vtkImageData and evaluating a subsequent vtk pipeline. Unfortunately I wasn't able to eliminate PCL from my hybrid PCL/vtk setup just yet. The problem is not really specific to vtkPointCloud, but I have found that the vtkStaticPointLocator is just very slow compared to pcl::octree::OctreePointCloudSearch. I have some algorithms that do a lot of octree searching and when I switch them over to use vtkStaticPointLocator an algorithm update takes around 200ms compared with 2ms using the octree from pcl.</div><div><br></div><div>Fyi for my particular use case, I did some profiling and the vtk locator tends to get pretty bogged down in the following call stack:</div><div>vtkDataArrayTemplate<float>::GetTuple</div><div>BucketList<int>::FindClosestPointWithinRadius</div><div>vtkStaticPointLocator::FindClosestPointWithinRadius</div><div><br></div><div>If I were to guess I would suspect that its just busy doing a lot of memory allocation and deallocation. I think the pcl implementation benefits from a more low level API, avoiding memory allocation inside loops, and probably gets a boost from inline / precompiled headers too.</div><div><br></div><div>Like I said, it's not specific to your vtkPointCloud module but the performance hit is very significant so I will stick with PCL for the moment.</div><div><br></div><div>Regards,</div><div>Geoff</div><div><br></div><div><br></div><div><br><br><div class="gmail_quote"><div><div class="h5"><div dir="ltr">On Sat, Feb 27, 2016 at 10:28 AM Will Schroeder <<a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a>> wrote:<br></div></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5"><div dir="ltr">Here's a quick update on point cloud processing in VTK. We've got an initial base of decent capability going now, including (and I am absolutely delighted about this) a surface extraction capability based on TSDF (truncated signed distance functions).<div><br></div><div><b>Classes now running (in VTK/Remote/vtkPointCloud):</b></div><div><div>vtkEuclideanClusterExtraction.h<br></div><div>vtkExtractHierarchicalBins.h</div><div>vtkExtractPointCloudPiece.h</div><div>vtkExtractPoints.h</div><div>vtkExtractSurface.h</div><div>vtkFitImplicitFunction.h</div><div>vtkHierarchicalBinningFilter.h</div><div>vtkPCACurvatureEstimation.h</div><div>vtkPCANormalEstimation.h</div><div>vtkPointCloudFilter.h</div><div>vtkRadiusOutlierRemoval.h</div><div>vtkSignedDistance.h</div><div>vtkStatisticalOutlierRemoval.h</div><div>vtkVoxelGrid.h</div></div><div><br></div><div><b>Surface extraction (in VTK/Remote/vtkPointCloud):</b></div><div>We've build a pipeline of objects that perform rudimentary surface extraction from a point cloud. There are three major parts:</div><div>1. Generating normals - currently use vtkPCANormalEstimation, including graph traversal to create consistently oriented normals.</div><div>2. Compute the TSDF using vtkSignedDistance. </div><div>3. Extract zero-crossing isocontour to generate surface (vtkExtractSurface).</div><div><br></div><div>Note that each of these parts will eventually be expanded by writing new filters, for example I want to use in #1 Brad King's tensor voting (from his <a href="http://www.kitware.com/publications/item/view/1253" target="_blank">PhD thesis</a>) to compute better normals. For #2, based loosely on the <a href="https://graphics.stanford.edu/papers/volrange/volrange.pdf" target="_blank">Curless & Levoy</a> paper, we can do better by using different interpolation kernels (see PointInterpolation framework below) rather than the ad hoc probability weights they use (to be added soon). Also for #2 we need to support incremental updating. Finally, #3 is based on a modified <a href="https://www.researchgate.net/publication/282975362_Flying_Edges_A_High-Performance_Scalable_Isocontouring_Algorithm" target="_blank">Flying Edges</a> algorithm so it is very fast :-)</div><div><br></div><div><b>Point Interpolation (in VTK/Filters/Points)</b></div><div>We just pushed this in, it looks to be a very powerful, quite general framework for performing data interpolation across point samples. It's threaded, uses fast threaded locators, and has an abstraction for a family of interpolation kernels (e.g., linear, gaussian, shepard, voronoi, hopefully SPH) at some point soon, with more on the way.</div><div><br></div><div>As usual any feedback is appreciated. Make sure you update both VTK and the vtkPointCloud remote module. Please don't be shy, this is happening really fast and I want to catch the inevitable stupid stuff as soon as possible.</div><div><br></div><div>Best,</div><div>W</div><div><br></div></div><div class="gmail_extra"></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 28, 2016 at 9:12 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"><div>FYI- I have committed an initial set of filters for performing point cloud processing. Any feedback or suggestions are welcome as this is an initial prototype. The work is currently available as a remote module to VTK (vtkPointCloud) via this repository:</div><div><a href="https://gitlab.kitware.com/vtk/point-cloud.git" target="_blank">https://gitlab.kitware.com/vtk/point-cloud.git</a><br></div><div><br></div><div>A couple of notes:</div><div>+ Right now I am using vtkPolyData to represent the point cloud via a vtkPoints instance. There are no vtkVertex, vtkPolyVertex cells created to save on memory.</div><div>+ The classes will process as input any vtkPointSet dataset</div><div>+ There is a general framework for filtering point clouds via the class vtkPointCloudFilter. Besides their filtered cloud output, these filters also have an optional, second output which contains any points removed from the input.</div><div>+ Current filters include vtkRadiusOutlierRemoval, vtkStatisticalOutlierRemoval, vtkExtractPoints (extract points using an implicit function). Some of these names are inspired by <a href="http://pointclouds.org/" target="_blank">PCL</a> names.</div><div>+ All filters are threaded using vtkSMPTools using a threaded locator (vtkStaticPointLocator) so I believe that this is relatively fast, although I have not done much testing.</div><div>+ I'm using vtkPointGaussianMapper in the tests, a class that Ken wrote that is very fast. </div><div><br></div><div>As usual comments and suggestions are requested. In particular any suggestions for other filters to write are welcome (to round out some of the core functionality). The repository is in flux as I try crazy ideas and try to educate myself, so be forewarned.</div><div><br></div><div>Best,<br>W</div><div><br></div><div><br></div>
</div>
</blockquote></div><br><br clear="all"><div><br></div></div><div class="gmail_extra">-- <br><div><div dir="ltr"><div>William J. Schroeder, PhD<br>Kitware, Inc. - Building the World's Technical Computing Software<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><span><span title="Call with Google Voice"><a href="tel:%28518%29%20881-4902" value="+15188814902" target="_blank">(518) 881-4902</a></span></span></div></div></div>
</div></div></div><span class="">
_______________________________________________<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>
</span></blockquote></div></div></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div>William J. Schroeder, PhD<br>Kitware, Inc. - Building the World's Technical Computing Software<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>(518) 881-4902</div></div></div>
</div>