PCL Developers blog

All blog posts for Stephen D. Fox

Back on track
Wednesday, June 06, 2012

After a busy couple of weeks, I am back to work on the out of core library. Justin, Julius, Jacob, Radu, and I have been discussing some pending changes to get outofcore performing at the appropriate level. Julius has provided some excellent feedback, and I think we will have some good demos soon.

Summarizing the OOC interface as it currently stands, remaining tasks on the OOC side fall into the following categories:

  1. OOC Interface (octree_base/octree_base_node) Responsible for recrusively traversing the top level in-memory octree
    1. point/region insertion methods
      • addDataToLeaf
      • addPointCloud
      • addDataToLeaf_and_genLOD
      • addPointCloud_and_genLOD
      • TODO: Need some tools for building point clouds from directory of PCDs
      • TODO: Input support for PointCloud2
      • TODO: Improve the speed of tree-building (slow with zlib compression)
    2. frustrum/box/region requests
      • queryBBIntersects
      • queryBBIncludes
      • queryBBIncludesSubsample
      • TODO: add PointCloud2 query support (almost done)
    3. Parameterization
      • container type
      • downsampling
      • compression (lossy, lossless)
      • depth/BB resolution
      • TODO: work out the interface for controlling these parameters; cross compatibility, etc...
  2. Encoding and Decoding of compressed data (Lossy/Lossless)
    • I have already added zlib compression into PCD containers
    • TODO: look into lossy compression based on the PCL Octree compression
    • TODO: Delay write for faster construction
  3. File I/O
    • Added some additional debug output to the PCDReader methods

Roadmap for the next few days:

  • Finish adding support for PointCloud2 Queries
  • Add support for PointCloud2 as input

Roadmap for the next couple of weeks:

  • Finish improvements to OOC construction (support of containers/point types, PointCloud2, caching, etc...)
  • Work with Julius on adding lossy-compression features
  • Clean up templating of interface class
  • Clean up construction of octree for speed
  • Abstract the hierarchy for easier modification of parameters
  • Make tools for OOC tree construction more flexible
Out of core node data to PCD
Monday, April 16, 2012

For the past week, I have finished the change from dump binary C-struct to PCD file at each node. This should help with debugging, and will make manipulating the data, at each node and pre-rendering, easier. I need to clean up the code a bit more before I commit to the repository.

In addition to cleaning up before committing, a few things that remain outstanding in this change are:

  • block reading of point cloud files
  • efficient appending to PCD files
  • a more detailed consideration of how to take advantage of compression methods
  • tending to the insertion and query methods of the octree_ram container class for use with PCD files
Changes in the outofcore code
Monday, April 09, 2012

I was able to fix the issue reported by Justin in his March 22nd posting about construction of large out-of-core trees. There was an issue in construction of octrees from inputs that were too large (the TRCS point sets were too large). However, if the clouds are broken up into pieces, or come initially from a set of smaller point clouds, there doesn’t seem to be any issue. For now, I refactored some of the reading/writing constants used, and that seems to have fixed it.

Justin and I have been discussing modifying the PCD reader to iterate through PCD files out-of-core to avoid loading the cloud entirely into memory. This goes for both reading and writing PCD files. I think this is a good idea, especially since this software may be running on a busy server at Urban Robotics, in addition to encoding/decoding the octree data. I’m almost done with the change from C-struct dumped binary data files (ending in ”.oct_dat”) at each node to a PCD file. This will provide a lot of convenience for debugging, as well as a simple way to save in binary compressed (lmz) format, and give us access to PCL algorithms at the leaves.

Radu, Julius and I have been chatting about compression within the out-of-core point cloud. As Radu pointed out to me, the chief issue here that we need to be wary of is I/O speed, particularly in reading and decoding the compressed data from disk, since this is supposed to speed up rendering/visualization of enormous data sets. Speed of writing to disk isn’t currently a primary concern for optimization, though it has its place. Construction of the out-of-core tree is usually an off-line pre-processing step. Julius is going to help us determine how we could use the compression from the existing octree for fast decoding at variable densities.

As a final note, I’ve added the abstract parent class for the disk and ram container classes. This is another step toward refactoring the code base and standardizing the interface throughout.

Outofcore Octree Update
Wednesday, March 28, 2012

Recently I’ve been investigating the issues with the outofcore octree reported by Justin. I have not been able to track down the reason that we cannot yet handle insertion of very large pcd files.

I have also been re-implementing the outofcore containers (ram and disk) to inherit a common abstract interface class. While I am working on this, I am cleaning up the binary serialization code, and plan to transition the binary point data at each node to PCL’s binary format. This will also allow us easy access to the lmzCompression of the point data.

As we go along, I have been adding unit tests to monitor bugs/features. These still are not being run by the build server, but I hope to see the outofcore code base sufficiently stable to enable by default soon.

Chats about Outofcore Octrees
Wednesday, March 14, 2012

Justin, Radu, Julius, Jacob and I have been discussing outofcore octrees. Some particularly interesting points of note arose in the conversation regarding the method of serialization. The UR constructs the octree in a depth-first manner, storing the point data in the leafs of the tree. If the LODs are generated, the folders (which contain internal node data) can be read (and rendered) in a breadth first manner, providing a successively more detailed octree as deeper nodes are read (see Justin’s blog).

Julius encodes his outofcore octree using a method similar to the Nested Octrees in the Scheiblauer and Wimmer paper [2]. Each file serialized is itself a sub-octree.

Currently, I am investigating appraoches to serialization for octrees. I’m studying two papers in particular that I’ve found useful:

[2]Claus Scheiblauer and Michael Wimmer, “Out-of-Core Selection and Editing of Huge Point Clouds.” Computers and Graphics, April 2011.
PCL’s Point Clouds in Outofcore Octrees
Wednesday, February 29, 2012

Over the weekend I committed a lot more refactoring and documentation for the outofcore octree code. It is now wrapped in the pcl::outofcore namespace, and I added support for a member function to the pcl::outofcore::octree_base class to copy data from a point cloud to an outofcore octree.

The outofcore library contains four classes:

  • octree_base
  • octree_base_node
  • octree_disk_container
  • octree_ram_container

Users interact with the outofcore octree entirely through the public interface of the octree_base class, which is templated by type of tree (disk v. ram) and the Point Type, and manages the nodes of the octree. The header files for the outofcore files are:

#include <pcl/outofcore/outofcore.h>
 #include <pcl/outofcore/outofcore_impl.h>

For an out-of-core octree, use the octree_disk_container, which will create a root directory for the tree, and up to eight directories, labeled 0-7 within each subsequent directory. Using the octree_ram_container constructs or loads an octree entirely in main memory, which is similar to the Octree already in PCL.

Each directory represents a node of the octree, a cubic axis-aligned region of space whose dimensions are specified by a “bounding box”. All nodes at the same depth, but in different branches, represent disjoint regions of 3D space. On disk, each node is a folder containing:

  • a JSON metadata file
  • up to eight child-node directories labeled 0-7
  • an optional data file of points subsampled from its children. However, if the node is a leaf, then it contains the highest “Level of Detail,” i.e. all the points falling within that bounding box, whether or not the intermediate LOD point sets were computed.

The bounding box of the root node must be specified upon the first creation of the octree. This represents the region of 3D space which contains the entire out-of-core point cloud. Resizing an octree dynamically upon insertion of a point, or set of points, that do not fall within this bounding box is an expensive task, though not impossible (cf. Scheiblauer and Wimmer’s strategy in [1] ). However, it currently is not implemented, meaning any point that is inserted that does not fall within the root’s bounding box will be discarded.

For building up octrees, I’ve added support for the addition of an arbitrary number of PointCloud::Ptr inputs via octree_base’s public member function:

addPointCloud(PointCloudConstPtr cloud)

Justin has written a command line tool for constructing an out-of-core octree from a PCD file. Once this tool has been used to create an out-of-core octree stored entirely on disk, the following code sample can be used to load and manipulate the out-of-core data.

At this point, Justin and I are looking forward to focusing on analysis of query, insertion, scalability and addition of features/algorithms for the outofcore data octree. I will also be adding examples to the trunk later this week.

[1]Claus Scheiblauer and Michael Wimmer, “Out-of-Core Selection and Editing of Huge Point Clouds.” Computers and Graphics, April 2011.
Preliminary conversion from UR’s point type to PCL’s PointT
Thursday, February 16, 2012

I’ve started to make the change to PCL’s templated point type. It required minimal refactoring since the code is already templated, and very few operations are done on the point itself except accessing the fields (which are fortunately mostly the same as pcl’s). To accommodate the Urban Robotics point data structure, we’ll need to use the PointXYZRGBNormal data type, but for the time being, I jettisoned three additional fields (error, cameraCount and traidID) and have been testing with PointXYZ. The extra fields are currently just payload (within the library), and are never used within. We may need to develop some custom point types for the additional payload fields in the long run.

Once I made the change, I had to rewrite some of the unit tests, as they relied on the operator== in the URCS point struct. This was a minor change, but now I can construct and query octrees out of core with the pcl::PointXYZ. I’d still like to benchmark HDD performance for queries, since performance seems to deteriorate quite quickly on my slow hard drive. I’m also planning to use the concepts in the existing octree unit tests as a basis to do a more exhaustive test of the out-of-core octree interface.

[==========] Running 6 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 6 tests from PCL
[ RUN      ] PCL.Outofcore_Octree_Pointcloud_Test
[       OK ] PCL.Outofcore_Octree_Pointcloud_Test (3448 ms)
[ RUN      ] PCL.Bounding_Box
[       OK ] PCL.Bounding_Box (0 ms)
[ RUN      ] PCL.Point_Query
[       OK ] PCL.Point_Query (215 ms)
[ RUN      ] PCL.Octree_Build
[       OK ] PCL.Octree_Build (700 ms)
[ RUN      ] PCL.Octree_Build_LOD
[       OK ] PCL.Octree_Build_LOD (56 ms)
[ RUN      ] PCL.Ram_Tree
[       OK ] PCL.Ram_Tree (42 ms)
[----------] 6 tests from PCL (4461 ms total)

[----------] Global test environment tear-down
[==========] 6 tests from 1 test case ran. (4461 ms total)
[  PASSED  ] 6 tests.

Tonight and tomorrow I hope to start working on changing the container type to PointCloud pointers. Justin and I have also been discussing ways to remove the JSON dependency. Once the basic port is done, I’ll be focusing on improving the interface, improving features and improving overall performance of the out-of-core octree. Finally, I hope to help develop supporting algorithms for Justin’s out-of-core octree visualization tools.

Diving into the UR Out-of-core Octree Code
Wednesday, February 15, 2012

Thanks to Justin Rosen, the Urban Robotics out-of-core octree code is now in the trunk, cleaned up quite a bit from its original state, and compiling in the PCL framework (but we haven’t changed the data structures to PCL’s yet). I have been studying the code and starting to determine what else will need to be done as far as integration goes. I have to thank Justin and Radu for their warm welcome, and for getting me up to speed over the weekend.

So far, I have run the unit tests that Justin converted from Boost to Google unit testing framework, and experimented with the limitations of the code. Currently, I’m working on a combination of two things. I’m working on refactoring the code to work with PCL’s templating and allow point clouds, rather than vector<PointT> as inputs. The transition is going smoothly so far. I can still build the octrees on disk with the unit tests, but there are some issues with querying the points / bounding boxes that I’m still looking into. I’ll have a more detailed update as soon as I get it straightened out.

For tracking down bugs in the PCL in general, I’ve set up a double-buffered installation of PCL trunk and whatever revision I’m interested in, and set up a build environment for test programs to build and run against the different versions. Now that I’m getting settled in, I’m hoping to establish a more specific roadmap by the end of the week, and add some literature review for out-of-core and octree background reading.

Going Live with the PCL-URCS Developer Blog
Saturday, February 11, 2012

Greetings to the PCL community. My name is Stephen Fox, and I am the new developer who has just come aboard for the Urban Robotics Code Sprint. Stay tuned for updates on the project as we move forward with the integration of Urban Robotics’s out-of-core octree implementation!