Large Scale Shape Reconstruction from Urban Point Clouds

Currently, you can find virtual worlds in many different forms. Computer games usually take place in nicely modeled cities or regions. Architects show their designs in their current environment on billboards. When you're planning a route to an unknown destination, you probably use a navigation system. In many cases, it is desirable that a virtual world is 3D and easily recognizable. Modeling these worlds costs time and effort and automating this process may reduce these burdens. Because virtual worlds are gaining popularity, a lot of research has been done into automatically modeling these worlds. Methods aimed at modeling sculptures try to use mainly smooth surfaces. Methods aimed at modeling urban scenes usually pick candidates from a selection of example buildings. We present a new approach for automatic modeling of urban scenes. This novel approach is based on the observation that urban regions consist mainly of planar surfaces. We use a divide-and-conquer strategy to model a scene effectively and efficiently. We divide the input into separate surfaces and we model each surface largely independently of the others. Finally, we combine the surfaces back into one model. We describe different ways to model individual surfaces. One method limits the modeling process to predetermined shapes, like rectangles. This method is limited to convex shapes, or simply put: shapes without dents. Another method models rectilinear shapes, like L-shapes. This method searches for a shape that best describes the input while only using straight angles. Finally, we present a method that uses neighboring surfaces to guide to modeling process. This method searches a shape that nicely connects with its neighbors. Once the individual surfaces are modeled, we combine them into a complete model. We describe a method that finds a watertight model between the surfaces. A watertight model is like a bottle with a strange shape: once filled with water and closed, it will not leak. Obviously, our novel methods are not the only way to model urban scenes and we end this thesis with a discussion on our methods. Developing these methods has revealed several questions. By trying to answer these questions, we could improve on our work such that we may continue to drive the field of research forward.