Efficient Modelling Of Smooth Surfaces With Branching Structures

As an important branch of computer graphics,3D modeling can be classified into some sub-topics according to their different applications and representations. The mesh representation is suitable for fast rendering, implicit surface is good for modeling objects with complex varying topology, subdivision surface is excellent for multi-resolution representation, and the skeleton-based modeling is efficient for editing and animation. To solve practical modeling problems, dif-ferent approaches can be combined by making use of their advantages. Trees, characters, and organs have smooth branching surfaces, and they can be abstracted as skeletons with branching structures. For modeling such branching objects, many researches in different fields (modeling, animation, visualization, et al.) have been conducted.In this dissertation, related work about modeling branching structures are presented, and the advantages and disadvantages of existing approaches are discussed. Moreover, several key prob-lems for modeling smooth branching models are analyzed and their solutions are provided. Our results consist of analytical solutions for sketch-based convolution surface modeling on the GPU, efficient polygonization of trunk-based convolution surfaces, composition-based tree modelling us-ing convolution surfaces and skeleton-based modelling with tree-like structures. More specifically, the paper makes the following contributions:· Convolution surfaces are attractive for modeling objects of complex evolving topology. This paper presents some novel analytical convolution solutions for planar polygon skele-tons with both finite-support and infinite-support kernel functions. We convert the double integral over a planar polygon into a simple integral along the contour of the polygon based on Green theorem, which reduces the computational cost and allows for efficient parallel computation on the GPU. For finite support kernel functions, a skeleton clipping algorithm is presented to compute the valid skeletons. The analytical solutions are integrated into a prototype modeling system on the GPU (Graphics Processing Unit). Our modeling sys-tem supports point, polyline and planar polygon skeletons. Complex objects with arbitrary genus can be modeled easily in an interactive way. Resulting convolution surfaces with high quality are rendered with interactive ray casting.· We present an efficient polygonization approach for tree trunks modeled by line-skeleton based convolution surfaces. A quad-dominated non-convex bounding polyhedron is firstly created along the skeleton, which is then tetrahedralized and subdivided into the predefined resolution. After that, the iso-surface within each tetrahedron is extracted using Marching Tetrahedra. Our algorithm can generate polygons with adaptive edge lengths according to the thickness of the trunk. In addition, we present an efficient CUDA-based parallel algorithm utilizing the high parallelism of the tetrahedron subdivision, the potential field calculation, and the iso-surface extraction.· We present an example-based tree modeling system by creating the structure of a tree using a single high-quality quad-only mesh. Through combining the strengths of the skeleton-based composition, convolution surfaces, and GPU, our tree modeling system is user-friendly, highly versatile and efficient, and achieves good mesh quality. Our sys-tem first extracts the line skeletons of given tree models by contracting the meshes with the Laplace operator. Then, the skeleton-based subtrees are generated automatically from the line skeletons, and new tree models are composed from these skeleton-based subtrees. We approximate the original tree mesh with a convolution surface based on the extracted skeletons. Using simple editing operations, newly composed tree trunks represented by convolution surfaces are tessellated into quad-only subdivision surfaces with good edge flow along the skeletal directions. We implemented the most time-consuming subdivision and convolution approximation on the GPU with CUDA. Using the developed system, we can create various new trees easily and quickly by interactively manipulating the skeletons only.· We present a novel approach for efficiently representing tree-like shapes with quad-only meshes. After extracting the line skeleton from the input mesh, we create a bounding poly-hedron along the skeleton. Then, the polyhedron is used as the control mesh to perform the Catmull-Clark subdivision. By reversely calculating the vertices of the control mesh, the limit surface is guaranteed to fit the input mesh as tight as possible. High performance is achieved by utilizing the parallel subdivision scheme on the GPU. Our approach provides a compact representation for modeling tree branches, animal torsos, and vasculatures. For all the proposed solutions, comparative experiments are performed to validate our pre-sented approaches. Finally, we systematically summarized our work, analyzed the limitations of our approaches, and gave the potential future work.