Techniques For Shape Modeling From Large Scale Point Clouds

3D geometry is becoming increasingly popular as a new form of digital media following sound, image and video. Point cloud model, a geometric model taking point as a primitive, is a fairly nature representatioin of 3D geometry. Point cloud model has a simple structure, and it is very compact in space. This makes point cloud model very efficient in representing large scale geometry models with rich details. With the rapid development of digital scanner, point cloud models are ubiquitous. Point Based Graphics (PBG) is gaining popularity in Computer Graphics. It focuses on point cloud preprocessing, model representation, and rendering. Recently, many research papers on PBG have been published in the Computer Graphics community. Most of the researches are concentrated on point cloud preprocess, rendering and representation. These researches form a strong fundation for future researches and application of point cloud model. Editing and deformation of geometric models are crutial for the application of geometric models. Currently, there are relatively few researches on shape modeling from point cloud models.This thesis focuses on representation, feature analysis and geometric modeling of large scale point cloud models. The content of this thesis covers key topics for building a shape modeling system from point cloud models. Contributions of this thesis include:1) Preprocessing of point cloud modelsWe propose a new simplification algorithm for large scale point cloud models. The algorithm is consisting of two steps. In the first step, the point cloud model is segmented into several approximated flat regions. In the second step, these regions are hierarchically partitioned. Coupling point cloud segmentation, our algorithm can reduce the geometric errors resulted from simplification without slowing down the performance in hierarchical partition.2) Decomposition of point clouds and extraction of skeletons3D geometry segmentation is a foundmental research topic of Computer Graphics. We proprose a multi-resolution hierarchical decomposition method to decompose large scale point cloud models. Firstly, a representation with link topology is constructed for low resolution point cloud model. Based on this representation, we extend mesh decomposition algorithms to point cloud segmentation with some modifications. For large scale point cloud models, we first decompose the model into several parts at lower resolution, then construct a higher resolution model for each part, and perform further decomposition on this higher resolution point cloud model.We propose a new controlled skeleton extraction method for large scale point cloud models. We first construct a simplified and no-mainfold represention for the point cloud model. Based on this representation, after constructing a Morse function, the kernel point and feature points of model are identified. Connect kernel point with each feature points by geodisc line, we get the surface skeletons. Pushing the surface skeletons inside point cloud model by visual repulsive force and then smoothing them, we get the controlled skeletons. Our skeleton extraction method can be directly applied to large scale point cloud models and is both robust and efficient.3) Shape modeling on point cloud modelsAn interactive blending prototype system for point cloud models is developed. Using our blending method, user can do blending by dragging-and-drop one point cloud model onto another to get a new point cloud model; or by cutting two sub-models to glue them into a new point cloud model. The transition blending region is construced by a natural and smooth implicit surface based on radial basic function. The fact that it lacks link topology makes blending on point cloud models seems more nature than on mesh models.Skeleton-driven skin deformation is a very important 3D geometry deformation method. We propose an elastastic deformation mixed with rigid deformation method for skeleton-driven skin deformation analysis. The deformation of skin is divided into rigid regions and elastastic regions. Rigid deformation can be calculated by rigid rotation of skeletons. Elastastic deformation is performed using a modal warping analysis technique, the modal warping problem is solved based a mesh free method. Our skeleton-driven skin deformation method is very efficient. It gives very realistic results. A new method is developed to assign the influence of skeletons on skin.