[vtk-developers] vtkPointCloud remote module

Will Schroeder will.schroeder at kitware.com
Sat Jan 30 08:48:05 EST 2016


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20160130/8318ff54/attachment-0001.html>


More information about the vtk-developers mailing list