Qian-Yi Zhou's Homepage

2.5D Dual Contouring

Introduction

We present a robust approach to creating 2.5D building models from aerial LiDAR point clouds. The method is guaranteed to produce crack-free models composed of complex roofs and vertical walls connecting them. By extending classic dual contouring into a 2.5D method, we achieve a simultaneous optimization over the three dimensional surfaces and the two dimensional boundaries of roof layers. Thus, our method can generate building models with arbitrarily shaped roofs while keeping the verticality of connecting walls. An adaptive grid is introduced to simplify model geometry in an accurate manner. Sharp features are detected and preserved by a novel and efficient algorithm.

Pipeline

Given a building point cloud as input, our modeling process executes four steps as illustrated in the following figure:

Scan conversion: We embed the point cloud in a uniform 2D grid. Surface Hermite data samples (gold arrows) are generated at grid points and boundary Hermite data samples (red arrows) are estimated on grid edges connecting different roof layers. This 2D grid is also regarded as the finest level of our supporting quadtree.
Adaptive creation of geometry: In each quadtree cell, we compute a hyper-point by minimizing a 2.5D QEF. Geometry simplification is achieved in an adaptive manner by collapsing subtrees and adding QEFs associated with leaf cells.
Polygon generation: We reconstruct a watertight mesh model by connecting hyper-points with surface polygons (turquoise triangles) and boundary polygons (purple triangles), which form building roofs and vertical walls, respectively.
Post processing: The roof boundaries are refined to follow the principal directions.

Software

We publish the source code of a 2.5D dual contouring program here. The program reads point clouds, applies the 2.5D dual contouring modeling algorithm, and produces 3D models in "obj" format.

This program contains most of the algorithm except the post-processing part. For a fully functional program, visit our urban modeling project page.

The program, test models, and the source code are for research purpose only. For other purposes, contact Qian-Yi Zhou (qianyizh@usc.edu) and Ulrich Neumann (uneumann@graphics.usc.edu).

(Current Version : 1.01, Updated : 10/5/2010)

Source code (74KB), compile with Microsoft Visual Studio 2008.
Windows executable files (40KB) and test models (29,134KB)
All-in-one package (29,246KB)

Publications

2.5D Dual Contouring: A Robust Approach to Creating Building Models from Aerial LiDAR Point Clouds
ECCV 2010 (oral paper), Qian-Yi Zhou and Ulrich Neumann
Links: Paper, Video, Slides, Poster