[vtk-developers] vtkPointCloud remote module

Bill Lorensen bill.lorensen at gmail.com
Wed Feb 3 11:22:59 EST 2016 

Will,

When I try to build the latest I get:
/Users/lorensen/ProjectsGIT/VTK/Remote/vtkPointCloud/vtkVoxelGrid.cxx:76:
error: ‘class vtkStaticPointLocator’ has no member named
‘GetBucketIds’

On Wed, Feb 3, 2016 at 8:24 AM, Geoff Wright <gpwright at gmail.com> wrote:
> 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 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
>
>
> _______________________________________________
> 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
>
>



-- 
Unpaid intern in BillsBasement at noware dot com

More information about the vtk-developers mailing list