[vtk-developers] vtkPointCloud remote module

Tue Mar 1 17:28:36 EST 2016

Hi Will,

I was using TBB enabled.  I tried changing the dimensions and number of
points per bucket but it didn't improve much.  I was not using vtkVoxelGrid
yet, just a combination of vtkPolyData and vtkStaticPointLocator to replace
the PCL part.  That's what I meant when I said this performance issue is
not specific to vtkPointCloud.  I could probably use vtkVoxelGrid but it
might need some tweaks to support realtime incoming data without the input
data structure growing indefinitely.  I'm managing that myself at the
moment.

I can't share my exact dataset because it is proprietary but I made an
example for you that I believe replicates a similar scenario.  It uses a
publicly available dataset (one of the PCL demo datasets which is called
bunny).  Take a look:

https://github.com/gpwright/pcl_benchmark

It does 5000 random lookups using PCL and then 5000 using VTK.  When I run
that I get the following output:

PCL did 5000 in 0.082

VTK did 5000 in 4.039

Let me know if you have a chance to try it out, would be curious if there
are any easy fixes.

G

On Tue, Mar 1, 2016 at 6:12 AM Will Schroeder <will.schroeder at kitware.com>
wrote:

> Geoff-
>
> Some additional notes:
> - vtkVoxelGrid does not invoke
> vtkStaticPointLocator::FindClosestPointWithinRadius so something else is
> being tested.
> - The methods in vtkStaticPointLocator do not repeatedly
> allocate/deallocate memory. Initially yes, but then the memory resource is
> reused.
> - As a point of reference, depending on the configuration for
> vtkStaticPointLocator, on my system I see 250,000 probes/sec
> (FindClosestNPoints N=10) about 2x faster than vtkPointLocator (and the
> vtkOctreePointLocator). Although faster when probing, the real significant
> difference is the time to construct and delete the static point locator
> which is orders of magnitude faster than the incremental point locator,
> octree, etc
> - These rough numbers are for randomized point clouds. With locally dense,
> but elsewhere sparse point clouds, there may be some serious performance
> hits (which is why any data, or testing scripts, you might have would be
> helpful).
>
> Best,
> W
>
> On Mon, Feb 29, 2016 at 5:50 PM, Will Schroeder <
> will.schroeder at kitware.com> wrote:
>
>> Geoff-
>>
>> 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?
>>
>> 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.
>>
>> Best,
>> W
>>
>> On Mon, Feb 29, 2016 at 5:25 PM, Geoff Wright <gpwright at gmail.com> wrote:
>>
>>> Hi Will,
>>>
>>> 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.
>>>
>>> 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:
>>> vtkDataArrayTemplate<float>::GetTuple
>>> BucketList<int>::FindClosestPointWithinRadius
>>> vtkStaticPointLocator::FindClosestPointWithinRadius
>>>
>>> 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.
>>>
>>> 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.
>>>
>>> Regards,
>>> Geoff
>>>
>>>
>>>
>>>
>>> On Sat, Feb 27, 2016 at 10:28 AM Will Schroeder <
>>> will.schroeder at kitware.com> wrote:
>>>
>>>> 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).
>>>>
>>>> *Classes now running (in VTK/Remote/vtkPointCloud):*
>>>> vtkEuclideanClusterExtraction.h
>>>> vtkExtractHierarchicalBins.h
>>>> vtkExtractPointCloudPiece.h
>>>> vtkExtractPoints.h
>>>> vtkExtractSurface.h
>>>> vtkFitImplicitFunction.h
>>>> vtkHierarchicalBinningFilter.h
>>>> vtkPCACurvatureEstimation.h
>>>> vtkPCANormalEstimation.h
>>>> vtkPointCloudFilter.h
>>>> vtkRadiusOutlierRemoval.h
>>>> vtkSignedDistance.h
>>>> vtkStatisticalOutlierRemoval.h
>>>> vtkVoxelGrid.h
>>>>
>>>> *Surface extraction (in VTK/Remote/vtkPointCloud):*
>>>> We've build a pipeline of objects that perform rudimentary surface
>>>> extraction from a point cloud. There are three major parts:
>>>> 1. Generating normals - currently use vtkPCANormalEstimation, including
>>>> graph traversal to create consistently oriented normals.
>>>> 2. Compute the TSDF using vtkSignedDistance.
>>>> 3. Extract zero-crossing isocontour to generate surface
>>>> (vtkExtractSurface).
>>>>
>>>> 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 PhD thesis
>>>> <http://www.kitware.com/publications/item/view/1253>) to compute
>>>> better normals. For #2, based loosely on the Curless & Levoy
>>>> <https://graphics.stanford.edu/papers/volrange/volrange.pdf> 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 Flying Edges
>>>> <https://www.researchgate.net/publication/282975362_Flying_Edges_A_High-Performance_Scalable_Isocontouring_Algorithm>
>>>> algorithm so it is very fast :-)
>>>>
>>>> *Point Interpolation (in VTK/Filters/Points)*
>>>> 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.
>>>>
>>>> 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.
>>>>
>>>> Best,
>>>> W
>>>>
>>>>
>>>> On Thu, Jan 28, 2016 at 9:12 AM, Will Schroeder <
>>>> will.schroeder at kitware.com> wrote:
>>>>
>>>>> 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:
>>>>> https://gitlab.kitware.com/vtk/point-cloud.git
>>>>>
>>>>> A couple of notes:
>>>>> + 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.
>>>>> + The classes will process as input any vtkPointSet dataset
>>>>> + 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.
>>>>> + Current filters include vtkRadiusOutlierRemoval,
>>>>> vtkStatisticalOutlierRemoval, vtkExtractPoints (extract points using an
>>>>> implicit function). Some of  these names are inspired by PCL
>>>>> <http://pointclouds.org/> names.
>>>>> + 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.
>>>>> + I'm using vtkPointGaussianMapper in the tests, a class that Ken
>>>>> wrote that is very fast.
>>>>>
>>>>> 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.
>>>>>
>>>>> Best,
>>>>> W
>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> William J. Schroeder, PhD
>>>> Kitware, Inc. - Building the World's Technical Computing Software
>>>> 28 Corporate Drive
>>>> Clifton Park, NY 12065
>>>> will.schroeder at kitware.com
>>>> http://www.kitware.com
>>>> (518) 881-4902
>>>> _______________________________________________
>>>> Powered by www.kitware.com
>>>>
>>>> Visit other Kitware open-source projects at
>>>> http://www.kitware.com/opensource/opensource.html
>>>>
>>>> Search the list archives at:
>>>> http://markmail.org/search/?q=vtk-developers
>>>>
>>>> Follow this link to subscribe/unsubscribe:
>>>> http://public.kitware.com/mailman/listinfo/vtk-developers
>>>>
>>>>
>>
>>
>> --
>> William J. Schroeder, PhD
>> Kitware, Inc. - Building the World's Technical Computing Software
>> 28 Corporate Drive
>> Clifton Park, NY 12065
>> will.schroeder at kitware.com
>> http://www.kitware.com
>> (518) 881-4902
>>
>
>
>
> --
> William J. Schroeder, PhD
> Kitware, Inc. - Building the World's Technical Computing Software
> 28 Corporate Drive
> Clifton Park, NY 12065
> will.schroeder at kitware.com
> http://www.kitware.com
> (518) 881-4902
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20160301/6eb375fb/attachment-0001.html>