[vtk-developers] vtkPointCloud remote module

Wed Feb 3 08:24:44 EST 2016

Hi Will,

Looks good!  I like the use of SMP.  I'll definitely try it out once the
interpolation is in place, it will be great to eliminate PCL as a
dependency.

Regards,
Geoff

On Tue, Feb 2, 2016 at 4:42 PM Will Schroeder <will.schroeder at kitware.com>
wrote:

> Geoff-
>
> I pushed an in progress version of VoxelGrid. As well as a hierarchical
> points binner. This is a work in progress so be forewarned. In particular,
> VoxelGrid does not yet interpolate its attributes yet. This is because I've
> got another branch in VTK for point interpolation, including interpolation
> kernels, that must ripen and placed in master first. Then the interpolation
> will be easy to add.
>
> W
>
> On Sat, Jan 30, 2016 at 8:48 AM, Will Schroeder <
> will.schroeder at kitware.com> wrote:
>
>> Okay I have a quick and dirty design for "file" format and algorithmic
>> approach that I'll start implementing shortly. We'll clean it up with time.
>> Any feedback is welcome.
>>
>> The data file format has three basic logical parts, which could be
>> written into separate files or one file, whatever. 1) metadata, 2) offsets,
>> and 3) sorted points.
>>
>> The key idea is that the points are in sorted order, beginning with level
>> 0 root node, followed by level 1 bins (8 bins) and their points, and level
>> 2 bins (64 bins) and their points, and so on. The points are just a
>> contiguous array of x-y-z, x-y-z, of type float or double (user specified),
>> etc. Data attributes could be stored in similar fashion (all easily
>> changeable depending on what you prefer). Since the number of points in
>> each bin is variable and may even be zero, this is where the offsets come
>> into play. (Note that points are not repeated, and statistically sampled as
>> you suggest ~1/(total number of bins)*NumberOfPoints points in each bin.)
>>
>> The offsets are integral values that simply refer to a position in the
>> sorted points array corresponding to the beginning of each bin. So (level
>> 0, bin 0), (level 1, bin 0), (1,1), (1,2), (1,3), (1,4), (1,5), (1,6),
>> (1,7), (2,0), (2,1), ... you get the idea. For your example of a 3-level
>> octree, there would be 73 offset values (or T=73 total bins). Note that if
>> offset_i == offset_(i+1) then there are zero points in the bin referred to
>> by offset_i. We can also represent the offsets with different integral
>> types depending on the number of points (to save memory).
>>
>> The metadata contains something like (assuming multiple separate files,
>> which of course can be memory mapped, etc):
>> NumberOfPoints #npts
>> NumberOfLevels #numLevels
>> Divisions 2 2 2
>> Bounds (xmin,xmax,ymin,ymax,zmin,zmax)
>> Points type "points.file"
>> Offsets type "offsets.file"
>> Array type numComp "scalars.file"
>> Array type numComp "vectors.file"
>>
>> Note that the Divisions are variable, the structure does not have to be
>> an octree. This is useful to produce bins that are closer to uniform shape,
>> or even create a 2.5D, sorta flat binning tree (e.g. z-divisions always ==
>> 1).
>>
>> Algorithmic approach: (this can easily be threaded):
>> For every point p_i in the input point cloud, generate a random number r
>> (0<=r<1). Assume that there are T total bins.
>> The probability (assuming an octree) that p_i is in level 0: is 1/T; in
>> level 1: 8/T; in level 2: 64/T and so on. Segment the range [0,1) into
>> proportional subranges that r maps into. Thus r will randomly select which
>> level of the tree a point belongs in.
>>
>> Once p_i is assigned a level, compute a hash index h_i which consists of
>> the (i,j,k) bin index added to T_l, there T_l is the total number of bins
>> at the beginning of level l. This hash index is the key to get the sort in
>> the right order; using the level information is a way to segment the bins
>> from different levels into contiguous runs.
>>
>> Now sort the points based on this hash index. The sort is where most of
>> the work is done and we'll use vtkSMPTools::Sort(). This produces a sorted
>> points list. Next create the offsets array by running through the sorted
>> hash indices, etc. (I've done this before in vtkStaticPointsLocator, it's
>> easy to do, and can even be done in parallel.)
>>
>> From the mapper point of view: knowing the bounds, divisions, current
>> level, and (i,j,k) bin index it is possible to construct a local bounding
>> box for each bin. Then there is direct access to the list of points in each
>> bin (through the offsets). And of course since this is a hierarchy of
>> uniform bins, you can easily perform view culling etc. and choose the
>> appropriate level for LODs.
>>
>> That's it in a nutshell. Unfortunately I've got lots of pointy-haired
>> boss stuff to do so this might take a bit to complete, but I'd really like
>> to get a prototype class written this week
>> (vtkPointCloud/vtkHierarchicalBinningFilter), it's got me revved up :-)
>> Initially I'll have this class build the data structures, with a special
>> back-door method to write the data out. Later on we'll decide if we need to
>> separate this backdoor IO into a separate class, etc.
>>
>> Best,
>> W
>>
>>
>> On Fri, Jan 29, 2016 at 12:15 PM, Ken Martin <ken.martin at kitware.com>
>> wrote:
>>
>>> Thanks Will. I promise I'll write the mapper :-) The PTS reader is a
>>> simple ascii X Y Z R G B type format that I usually immediately convert to
>>> VTK XML format as that is far faster and more compact. So unfortunately PTS
>>> is not it. I am thinking a vtkXMLPolyDataWriter subclass that adds some
>>> bounding box metadata.
>>>
>>> Ken
>>>
>>> On Fri, Jan 29, 2016 at 11:08 AM, Will Schroeder <
>>> will.schroeder at kitware.com> wrote:
>>>
>>>> Ken-
>>>>
>>>> I am totally with you. I am writing some simple stuff at the moment
>>>> like VoxelGrid as sort of a "drop-in" replacements for PCL workflows;
>>>> mostly to get my head around the challenges and serve as a stop gap until
>>>> our better stuff comes along. I really like your idea and I do plan to
>>>> implement this; it's really not too hard to do from what I understand and
>>>> given the pieces available in VTK.
>>>>
>>>> So I'll wrap up this simple VoxelGrid and then take a crack at the
>>>> beast you've envisioned. The two major pieces seems to be 1) create a class
>>>> that builds the hierarchical structure, and 2) write a reader/writer pair
>>>> that can perform associated IO. In an earlier email you mentioned a PTS
>>>> reader that you made improvement to; is this a good exemplar data format or
>>>> do you have a better starting point?
>>>>
>>>> It seems I have a homework assignment for the weekend :-)
>>>>
>>>> Best,
>>>> W
>>>>
>>>> On Fri, Jan 29, 2016 at 10:42 AM, Ken Martin <ken.martin at kitware.com>
>>>> wrote:
>>>>
>>>>> Nice, can I make a specific request Will? :-) Part of what I want to
>>>>> do for large point clouds is something like the following:
>>>>>
>>>>> 1) Open a VTK multipiece file and read in the bounding boxes of the
>>>>> pieces (but not the data)
>>>>>
>>>>> 2) Read in the first piece and use it for rendering
>>>>>
>>>>> 3) In the background read in more pieces, as they are loaded make them
>>>>> available to the mapper
>>>>>
>>>>> 4) The mapper based on the current camera parameters and bounding
>>>>> boxes of the pieces intelligently selects what pieces to render. This
>>>>> provides a happy fast interactive experience leading to world peace.
>>>>>
>>>>> For this to work well my thought was to have the pieces be broken up
>>>>> in a special way sort of like an octree but a spatial hash etc would be
>>>>> just as good as long as it is hierarchical and structured. Think of
>>>>> breaking up the volume into 1 + 8 + 64 pieces. The first piece contains
>>>>> ~1/73 of the data covering the entire bounding box. The next eight pieces
>>>>> also each contain  about 1/73 of the data each constrained by their octant
>>>>> of the bounding box. Same idea for the next 64 boxes, they are just one
>>>>> level further down.  This would work really well for a smart mapper
>>>>> providing fast first render plus fast LOD/subsequent renders. I can
>>>>> implement 1-4 pretty quickly.
>>>>>
>>>>> But .... for it to work I need someone to create the 73 piece file the
>>>>> right way. (it does not have to be 73, and clearly some of those 73 will be
>>>>> empty, it just needs to be hierarchical and structured so that a group of
>>>>> pieces can be represented at a lower level of detail by some other piece)
>>>>> My gut feeling was to have the LOD pieces use actual points of the dataset
>>>>> (not centroids or similar) that way as more pieces are loaded we are just
>>>>> providing more detail, not replacing fake data (centroids) with real data.
>>>>> But really either approach is pretty easy to implement in the mapper. The
>>>>> latter approach just means the entire dataset footprint is larger because
>>>>> some of the points are not part of the full res dataset because you
>>>>> generated them.
>>>>>
>>>>> I could be totally off base but that was my gut feeling on rendering >
>>>>> 2GB point clouds in a nice zippy manner.
>>>>>
>>>>> TLDR: I want someone to write a filter/writer subclass to create a
>>>>> special 73 piece vtk file :-)
>>>>>
>>>>> Ken
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Fri, Jan 29, 2016 at 10:06 AM, Will Schroeder <
>>>>> will.schroeder at kitware.com> wrote:
>>>>>
>>>>>> Geoff-
>>>>>>
>>>>>> I knocked out a vtkVoxelGrid last night, it seems to work great. It's
>>>>>> threaded and seems to be fast.
>>>>>>
>>>>>> Question for you before I push the work to the repository: averaging
>>>>>> points in each bin provides a nice subsampled point position. But what do
>>>>>> you think we should do for attributes (e.g., scalars, vector, etc.)? These
>>>>>> could be averaged too. There are however other options like finding the
>>>>>> closest point to the subsampled point and using those attribute values, or
>>>>>> if you want to get really fancy, using an interpolation kernel to
>>>>>> interpolate to the subsampled point.
>>>>>>
>>>>>> Thoughts?
>>>>>> W
>>>>>>
>>>>>> On Thu, Jan 28, 2016 at 10:03 AM, Will Schroeder <
>>>>>> will.schroeder at kitware.com> wrote:
>>>>>>
>>>>>>> Thanks for the feedback. I have some downsampling filters in the
>>>>>>> works now, I'll let you know when I have something ready.
>>>>>>>
>>>>>>> BTW we are on a similar path. PCL is awesome, but we have some
>>>>>>> common workflows that would be better served with more compact software
>>>>>>> environments, and with minimal IO and/or data transfer. So we're trying to
>>>>>>> knock of a small kernel of capability to achieve this.
>>>>>>>
>>>>>>> Best,
>>>>>>> W
>>>>>>>
>>>>>>> On Thu, Jan 28, 2016 at 9:56 AM, Geoff Wright <gpwright at gmail.com>
>>>>>>> wrote:
>>>>>>>
>>>>>>>> Hi Will,
>>>>>>>>
>>>>>>>> This is good to see.  I'm currently using VTK to generate surfaces
>>>>>>>> from some point cloud data.  I have some initial pre processing steps that
>>>>>>>> I use PCL (point cloud library) for, and then a vtk stage that converts PCL
>>>>>>>> point cloud into vtkPolyData/vtkPoints.  It would be great to
>>>>>>>> eliminate the PCL dependency and use exclusively vtk.  My point
>>>>>>>> cloud data grows very large over time with a lot of redundant points so its
>>>>>>>> very important to downsample them onto uniform spacing (
>>>>>>>> http://docs.pointclouds.org/trunk/classpcl_1_1_voxel_grid.html )
>>>>>>>> before processing them in vtk.  Would it make sense to add something like
>>>>>>>> this to your library?
>>>>>>>>
>>>>>>>> Geoff
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> 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
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> _______________________________________________
>>>>>>>>> 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
>>>>>>
>>>>>> _______________________________________________
>>>>>> 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
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Ken Martin PhD
>>>>> Chairman & CFO
>>>>> Kitware Inc.
>>>>> 28 Corporate Drive
>>>>> Clifton Park NY 12065
>>>>> 518 371 3971
>>>>>
>>>>> This communication, including all attachments, contains confidential
>>>>> and legally privileged information, and it is intended only for the use of
>>>>> the addressee.  Access to this email by anyone else is unauthorized. If you
>>>>> are not the intended recipient, any disclosure, copying, distribution or
>>>>> any action taken in reliance on it is prohibited and may be unlawful. If
>>>>> you received this communication in error please notify us immediately and
>>>>> destroy the original message.  Thank you.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> 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
>>>>
>>>
>>>
>>>
>>> --
>>> Ken Martin PhD
>>> Chairman & CFO
>>> Kitware Inc.
>>> 28 Corporate Drive
>>> Clifton Park NY 12065
>>> 518 371 3971
>>>
>>> This communication, including all attachments, contains confidential and
>>> legally privileged information, and it is intended only for the use of the
>>> addressee.  Access to this email by anyone else is unauthorized. If you are
>>> not the intended recipient, any disclosure, copying, distribution or any
>>> action taken in reliance on it is prohibited and may be unlawful. If you
>>> received this communication in error please notify us immediately and
>>> destroy the original message.  Thank you.
>>>
>>
>>
>>
>> --
>> 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/20160203/afe21eb9/attachment-0001.html>