Pathfinding through Identified Empty Space in Point Clouds

Indoor point clouds are useful for many applications, such as for pathfinding through empty, collision-free space. Fast-performing methods are required to identify this empty space because the indoor environment changes frequently and often does not follow the architectural design. As part of the Synthesis Project 2015, students of the MSc in Geomatics programme at Delft University of Technology have developed a method to efficiently identify and structure connected empty space in point clouds. Read on to learn more about the project.

(By Tom Broersen, Florian Fichtner and Ivo de Liefde)

During the Geomatics Synthesis Project 2015, themed ‘explorative point cloud processing’, three groups of students spent ten weeks building an application for either indoor, terrestrial or aerial point clouds. The group named ‘Project Pointless’ was to focus on indoor point clouds. For generating models of indoor space, focus lies often on identifying the boundaries of space and the objects inside it. But for indoor pathfinding it is much more logical to focus on the empty, pointless space, which is the space that can actually be used. Therefore, the group developed an algorithm which identifies and structures the empty space in point clouds.

An interior point cloud of the Faculty of Architecture’s bar, the Bouwpub (measuring 9mx15mx5m), was obtained with a ZEB1 mobile laser scanner. A coloured point cloud was used for visual display only, which was obtained using the Leica C10 laser scanner.

Linear octree

A linear octree was used to derive and structure the empty space in the point cloud. An octree recursively subdivides the point cloud into eight equal-sized octants, up to a predefined maximum resolution. Octants are called grey nodes if they themselves contain smaller octants. Octants are called black (containing points) or white (empty) leaf nodes if they do not contain smaller octants. A locational code is generated for every leaf node using bitwise interleaving: a method that combines the x, y, and z coordinates into a single binary string. The entire octree structure is implicitly stored in the resulting set of locational codes.

Empty space

In the above procedure, black leaf nodes are created first. The white leaf nodes which contain the actual empty space can then be reconstructed from the linear octree structure of black leaf nodes. The developed method ensures that black leaf nodes always have the maximum specified resolution, thus the octree always reaches maximum resolution around points in the point cloud. The white leaf nodes are not further subdivided for efficient storage of empty space.

The usability of the empty space has been shown in a pathfinding application. For this purpose, a neighbour-finding algorithm was applied to the white leaf nodes, which retrieves the connected empty spaces. An A* algorithm was implemented that uses this connectivity to find the shortest path in three dimensions.

Speed and scalability

The method was implemented such that an octree of 6cm resolution was generated. The speed of the implementation was evaluated by comparing the processing time required for the generation of octrees with different maximum octree levels. Doubling caused only a small increase in total processing time, indicating that the method scales very well for increasing resolution. The method also scales well when increasing the size of the point cloud; for a four-times-larger point cloud, the required processing time increased only 3.5 times. The entire process, including the acquisition of the data with the ZEB1 laser scanner, can be completed in only a few minutes per room. 

The potential of empty space

Point clouds contain a wealth of potential information about scanned objects and surfaces, but also about the space which can be used to move through. Empty space can be derived and structured swiftly and efficiently from point clouds using the methods presented in this article. Having the empty space can be beneficial for applications such as 3D pathfinding, because it puts the focus on usable space instead of focusing on boundary points or objects. It could also be used for a whole gamut of other possible applications, such as estimating the volume of available storage space and calculating how to fit large objects through narrow spaces. The presented method is currently being further developed for indoor navigation.

Acknowledgements

The authors would like to acknowledge their fellow members of Project Pointless: Olivier Rodenberg and Erik Heeres. Special thanks goes to their supervisor at Delft University of Technology, Edward Verbree, and the rest of the Geomatics Department, as well as to Robert Voûte from CGI Netherlands. They have offered great support.

Further Reading

Broersen, T., Fichtner, F. W., Heeres, E. J., De Liefde, I., Rodenberg, O. B. P. M., Verbree, E. (2015). Project Pointless: Identifying, visualising and pathfinding through empty space in interior point clouds using an octree approach.

Verbree, E. (2015). Insight through explorative point clouds. Connecting indoor and outdoor. Presentation at Nederlands Centrum voor Geodesie en Geo-informatie (NCGeo), Management of Massive Point Cloud Data, Delft, The Netherlands, December 2015.

Biographies of the authors

Tom Broersen is a geomatics master student at TU Delft and holds an MSc in physical geography. He is currently working on his graduation project on automatic identification of water courses from Lidar point clouds.

tombroersen@gmail.com

Florian W. Fichtner is a geomatics student at Delft University of Technology and is currently working on his graduation assignment at CGI. He is fascinated by maps and holds a BSc in geography from Tübingen University, Germany.

fwfichtner@gmail.com

Ivo de Liefde has a broad interest in geosciences and is currently graduating from Delft University of Technology in geomatics. He obtained his BSc in human geography at Utrecht University.  

ivodeliefde@gmail.com        

Figure captions

Figure 1, Drone navigating through the empty space in a point cloud of the Bouwpub.

Figure 2, Identified empty space (transparent octants) with octants containing points in yellow.

Figure 3, Route (blue octants) through the Bouwpub (purple octants) using the identified empty space.

Figure 4, A point cloud of the Project Pointless group: (from left to right) Ivo de Liefde, Florian Fichtner, Erik Heeres, Olivier Rodenberg and Tom Broersen.