[vtk-developers] vtkPointCloud remote module

Tue Mar 1 06:12:21 EST 2016

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/8b3e53a6/attachment-0001.html>