Automatic Procedural Modeling of Tree Structures in Point Clouds Using Wavelets

We present a method for discovering the structure of trees in 3D point clouds by linking wavelets with shape grammars. Given a range scan of a tree we find a grammar that can reproduce that tree, and others like it, with sub-voxel accuracy. The grammar inferred is stochastic, allowing us to generate many permutations of related trees. The method of multi-resolution analysis, employed by the discrete wavelet transform, gives great insight into tree structure. Trees are self-similar and exhibit similar branching patterns at different resolutions. The wavelets make these patterns explicit by decomposing the tree into different levels of detail. The multi-resolution structure of the wavelet transform also allows us to infer an L-System grammar. The productions in the grammar are derived from the progressive levels of refinement in the wavelet transform. Each production maps a vector in the low resolution image to a set of vectors in the higher resolution image. Our method utilizes the Fast Wavelet Transform opening the door to real-time inference of procedural models. The grammar inferred is concise and generative, allowing for compression and graphics applications of our algorithm. We demonstrate novel applications of the grammar for shape completion, scan enhancement and geometry propagation.