<div dir="ltr">Hi Will,<div><br></div><div>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.</div><div><br></div><div>Regards,</div><div>Geoff</div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr">On Tue, Feb 2, 2016 at 4:42 PM Will Schroeder <<a href="mailto:will.schroeder@kitware.com">will.schroeder@kitware.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Geoff-<div><br></div><div>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.</div></div><div dir="ltr"><div><br></div><div>W</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jan 30, 2016 at 8:48 AM, Will Schroeder <span dir="ltr"><<a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">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.<div><br></div><div>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.</div><div><br></div><div>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.)</div><div><br></div><div>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).</div><div><br></div><div>The metadata contains something like (assuming multiple separate files, which of course can be memory mapped, etc):</div><div>NumberOfPoints #npts</div><div>NumberOfLevels #numLevels</div><div>Divisions 2 2 2</div><div>Bounds (xmin,xmax,ymin,ymax,zmin,zmax)</div><div>Points type "points.file"</div><div>Offsets type "offsets.file"</div><div>Array type numComp "scalars.file"</div><div>Array type numComp "vectors.file"</div><div><br></div><div>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).</div><div><br></div><div>Algorithmic approach: (this can easily be threaded):</div><div>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. </div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.)</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>Best,</div><div>W</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote"><span>On Fri, Jan 29, 2016 at 12:15 PM, Ken Martin <span dir="ltr"><<a href="mailto:ken.martin@kitware.com" target="_blank">ken.martin@kitware.com</a>></span> wrote:<br></span><div><div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">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. <span><font color="#888888"><div><br></div><div>Ken</div></font></span></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jan 29, 2016 at 11:08 AM, Will Schroeder <span dir="ltr"><<a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Ken-<div><br></div><div>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.</div><div><br></div><div>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?</div><div><br></div><div>It seems I have a homework assignment for the weekend :-)</div><div><br></div><div>Best,</div><div>W</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jan 29, 2016 at 10:42 AM, Ken Martin <span dir="ltr"><<a href="mailto:ken.martin@kitware.com" target="_blank">ken.martin@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Nice, can I make a specific request Will? :-) Part of what I want to do for large point clouds is something like the following:<div><br></div><div>1) Open a VTK multipiece file and read in the bounding boxes of the pieces (but not the data)</div><div><br></div><div>2) Read in the first piece and use it for rendering</div><div><br></div><div>3) In the background read in more pieces, as they are loaded make them available to the mapper</div><div><br></div><div>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.</div><div><br></div><div>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. </div><div><br></div><div>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.</div><div><br></div><div>I could be totally off base but that was my gut feeling on rendering > 2GB point clouds in a nice zippy manner.</div><div><br></div><div>TLDR: I want someone to write a filter/writer subclass to create a special 73 piece vtk file :-)</div><div><br></div><div>Ken</div><div><br></div><div><br><div><br></div><div><br></div></div></div><div class="gmail_extra"><div><div><br><div class="gmail_quote">On Fri, Jan 29, 2016 at 10:06 AM, Will Schroeder <span dir="ltr"><<a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Geoff-<div><br></div><div>I knocked out a vtkVoxelGrid last night, it seems to work great. It's threaded and seems to be fast.</div><div><br></div><div>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.</div><div><br></div><div>Thoughts?</div><div>W</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 28, 2016 at 10:03 AM, Will Schroeder <span dir="ltr"><<a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Thanks for the feedback. I have some downsampling filters in the works now, I'll let you know when I have something ready. <div><br></div><div>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.</div><div><br></div><div>Best,</div><div>W</div></div><div class="gmail_extra"><div><div><br><div class="gmail_quote">On Thu, Jan 28, 2016 at 9:56 AM, Geoff Wright <span dir="ltr"><<a href="mailto:gpwright@gmail.com" target="_blank">gpwright@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Will,<div><br></div><div>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.  <span style="line-height:1.5">It would be great to eliminate the PCL dependency and use exclusively vtk.  </span><span style="line-height:1.5">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 ( </span><a href="http://docs.pointclouds.org/trunk/classpcl_1_1_voxel_grid.html" style="line-height:1.5" target="_blank">http://docs.pointclouds.org/trunk/classpcl_1_1_voxel_grid.html</a><span style="line-height:1.5"> ) before processing them in vtk.  Would it make sense to add something like this to your library?</span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">Geoff</span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5"><br></span></div><div><br></div><div><br></div><div><br></div><div><br></div></div><br><div class="gmail_quote"><div><div><div dir="ltr">On Thu, Jan 28, 2016 at 9:12 AM Will Schroeder <<a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a>> wrote:<br></div></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div><div dir="ltr"><div>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:</div><div><a href="https://gitlab.kitware.com/vtk/point-cloud.git" target="_blank">https://gitlab.kitware.com/vtk/point-cloud.git</a><br></div><div><br></div><div>A couple of notes:</div><div>+ 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.</div><div>+ The classes will process as input any vtkPointSet dataset</div><div>+ 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.</div><div>+ Current filters include vtkRadiusOutlierRemoval, vtkStatisticalOutlierRemoval, vtkExtractPoints (extract points using an implicit function). Some of  these names are inspired by <a href="http://pointclouds.org/" target="_blank">PCL</a> names.</div><div>+ 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.</div><div>+ I'm using vtkPointGaussianMapper in the tests, a class that Ken wrote that is very fast. </div><div><br></div><div>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.</div><div><br></div><div>Best,<br>W</div><div><br></div><div><br></div>
</div></div></div>
_______________________________________________<br>
Powered by <a href="http://www.kitware.com" rel="noreferrer" target="_blank">www.kitware.com</a><br>
<br>
Visit other Kitware open-source projects at <a href="http://www.kitware.com/opensource/opensource.html" rel="noreferrer" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
<br>
Search the list archives at: <a href="http://markmail.org/search/?q=vtk-developers" rel="noreferrer" target="_blank">http://markmail.org/search/?q=vtk-developers</a><br>
<br>
Follow this link to subscribe/unsubscribe:<br>
<a href="http://public.kitware.com/mailman/listinfo/vtk-developers" rel="noreferrer" target="_blank">http://public.kitware.com/mailman/listinfo/vtk-developers</a><br>
<br>
</blockquote></div>
</blockquote></div><br><br clear="all"><span><font color="#888888"><div><br></div></font></span></div></div><span><font color="#888888"><span><font color="#888888">-- <br><div><div dir="ltr"><div>William J. Schroeder, PhD<br>Kitware, Inc. - Building the World's Technical Computing Software<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a><br><a href="http://www.kitware.com" target="_blank">http://www.kitware.com</a><br><a href="tel:%28518%29%20881-4902" value="+15188814902" target="_blank">(518) 881-4902</a></div></div></div>
</font></span></font></span></div><span><font color="#888888">
</font></span></blockquote></div><span><font color="#888888"><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr"><div>William J. Schroeder, PhD<br>Kitware, Inc. - Building the World's Technical Computing Software<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a><br><a href="http://www.kitware.com" target="_blank">http://www.kitware.com</a><br><a href="tel:%28518%29%20881-4902" value="+15188814902" target="_blank">(518) 881-4902</a></div></div></div>
</font></span></div>
<br>_______________________________________________<br>
Powered by <a href="http://www.kitware.com" rel="noreferrer" target="_blank">www.kitware.com</a><br>
<br>
Visit other Kitware open-source projects at <a href="http://www.kitware.com/opensource/opensource.html" rel="noreferrer" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
<br>
Search the list archives at: <a href="http://markmail.org/search/?q=vtk-developers" rel="noreferrer" target="_blank">http://markmail.org/search/?q=vtk-developers</a><br>
<br>
Follow this link to subscribe/unsubscribe:<br>
<a href="http://public.kitware.com/mailman/listinfo/vtk-developers" rel="noreferrer" target="_blank">http://public.kitware.com/mailman/listinfo/vtk-developers</a><br>
<br>
<br></blockquote></div><br><br clear="all"><span><font color="#888888"><div><br></div>-- <br></font></span></div></div><span><font color="#888888"><div>Ken Martin PhD<div>Chairman & CFO<br>Kitware Inc.<br>28 Corporate Drive<br>Clifton Park NY 12065<br><a href="tel:518%20371%203971" value="+15183713971" target="_blank">518 371 3971</a><div><br></div><div><span style="font-size:10pt;font-family:Tahoma,sans-serif">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.</span></div></div></div>
</font></span></div><span><font color="#888888">
</font></span></blockquote></div><span><font color="#888888"><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr"><div>William J. Schroeder, PhD<br>Kitware, Inc. - Building the World's Technical Computing Software<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a><br><a href="http://www.kitware.com" target="_blank">http://www.kitware.com</a><br><a href="tel:%28518%29%20881-4902" value="+15188814902" target="_blank">(518) 881-4902</a></div></div></div>
</font></span></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div>Ken Martin PhD<div>Chairman & CFO<br>Kitware Inc.<br>28 Corporate Drive<br>Clifton Park NY 12065<br><a href="tel:518%20371%203971" value="+15183713971" target="_blank">518 371 3971</a><div><br></div><div><span style="font-size:10pt;font-family:Tahoma,sans-serif">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.</span></div></div></div>
</div>
</div></div></blockquote></div></div></div><div><div><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr"><div>William J. Schroeder, PhD<br>Kitware, Inc. - Building the World's Technical Computing Software<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a><br><a href="http://www.kitware.com" target="_blank">http://www.kitware.com</a><br><a href="tel:%28518%29%20881-4902" value="+15188814902" target="_blank">(518) 881-4902</a></div></div></div>
</div></div></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr"><div>William J. Schroeder, PhD<br>Kitware, Inc. - Building the World's Technical Computing Software<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a><br><a href="http://www.kitware.com" target="_blank">http://www.kitware.com</a><br>(518) 881-4902</div></div></div>
</div>
</blockquote></div>