[vtk-developers] vtkPointCloud remote module

Wed Feb 3 11:30:49 EST 2016

Bill-

I added a couple of methods to point locator and need to push them. I'll do
that shortly, sorry for the hassle. It'll be later today,

W

On Wed, Feb 3, 2016 at 11:22 AM, Bill Lorensen <bill.lorensen at gmail.com>
wrote:

> 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
>

-- 
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/1f2c4b03/attachment-0001.html>