| 3D reconstruction from point clouds is a fundamental problem in both computer vision and computer graphics. As urban modeling is an important reconstruction problem that has various significant applications, this thesis investigates the complex problem of reconstructing 3D urban models from aerial LiDAR (Light Detection And Ranging) point cloud.;In the first part of this thesis, an automatic urban modeling system is proposed which consists of three modules: (1) the classification module classifies input points into trees and buildings; (2) the segmentation module splits building points into different roof patches; (3) the modeling module creates building models, ground, and trees from point patches respectively. In order to support city-scale data sets, this pipeline is extended into an out-of-core streaming framework. By storing data as stream files on hard disks and using main memory as only a temporary storage for ongoing computation, an efficient out-of-core data management is achieved. City-scale urban models are successfully created from billions of points with limited computing resource.;The second part of this thesis explores the 2.5D nature of building structures. The 2.5D characteristic of building models is observed and formally defined as "building structures are always composed of complex roofs and vertical walls". Based on this observation, a 2.5D geometry representation is developed for the building structures, and used to extend a classic volumetric modeling approach into a 2.5D method, named 2.5D dual contouring. This algorithm can generate building models with arbitrarily shaped roofs while keeping the verticality of the walls. The next research studies the topology of 2.5D building structures. 2.5D building topology is formally defined as a set of roof features, wall features, and point features; together with the associations between them. Based on this research, the topology restrictions in 2.5D dual contouring are relaxed. The resulting model contains much less triangles but similar visual quality. To further capture the global regularities that intrinsically exist in building models because of human design and construction, a broad variety of global regularity patterns between 2.5D building elements are explored. An automatic algorithm is proposed to discover and enforce global regularities through a series of alignment steps, resulting in 2.5D building models with high quality in terms of both geometry and human judgement. Finally, the 2.5D characteristic of building structures is adopted to aid 3D reconstruction of residential urban areas: a more powerful classification algorithm is developed which adopts an energy minimization scheme based on the 2.5D characteristic of building structures.;This thesis demonstrates the effectiveness of all the algorithms on a range of urban area scans from different cities; with varying sizes, density, complexity, and details. |
