【作者】 朱晓强；

【导师】 金小刚；

【作者基本信息】 浙江大学 ， 计算机科学与技术， 2013， 博士

【摘要】 三维建模是计算机图形学领域的重要分枝,根据不同的应用和表示方法已经发展有诸多细分主题,例如适于快速绘制的网格模型、表示复杂拓扑改变的隐式曲面、多分辨率表示的细分曲面、可高效编辑的骨架模型等。在解决实际建模过程中,往往需要结合若干种不同的方法,以便充分利用它们各自的优点来生成更好的模型。视频游戏、电影等应用中的模型如树、卡通人物和动物；以及数字教学中的动物器官如血管、支气管等,它们都具有光滑的表面,且可抽象为分枝结构的骨架表示。为满足该类模型应用的需求,已有不少领域(如建模、动画、医学可视化等)都对其进行了研究。本文首先阐述了与分枝结构建模相关的研究现状；其次,在总结现有算法优缺点的基础上,对光滑分枝结构建模几个关键问题进行分析,并提出解决方案内容主要包括卷积曲面解析解及其在Sketch建模中的应用、基于树干的卷积曲面高效多边形化、基于合成的卷积曲面树干建模、基于骨架的树形分枝结构建模四个部分。具体工作可分为如下几个方面：·卷积曲面可生成复杂拓扑变化的模型,因此是一种颇受欢迎的建模工具。针对有限和无限支撑核函数,根据格林定理将平面多边形区域的双重积分转换为沿多边形边界的单重积分；在此基础上给出了新的基于平面多边形骨架的卷积计算解析解,这样不仅减少了计算量且积分过程更加适合并行计算。而对有限支撑核函数,给出了一种计算有效骨架的裁剪算法。本文将所推导的解析解成功应用于基于GPU (Graphics Processing Unit)的Sketch建模系统中,该建模系统支持点、折线段和平面多边形骨架,可交互式生成复杂拓扑结构的模型,并采用光线投射法可生成高质量的卷积曲面。·对基于线骨架卷积曲面创建的树干模型,给出了一种高效的等值面多边形化方法。首先,沿树干骨架方向创建一个以四边形为主的非凸包围多面体,将其四面体化并细分到预定的分辨率；其次,在每个四面体内根据Marching Tetrahedra规则提取等值面多边形,且生成的多边形边长可根据树干的半径自适应调整；最后,由于四面体细分、势能值计算和等值面提取过程都具有较高的并行度,故又提出一种高效基于CUDA的并行化策略。·提供一个基于样例的树建模系统,可创建由高质量四边形表示的树结构单网格模型。由于基于骨架合成、卷积曲面和GPU三者的优点,该树建模系统交互简单高效且生成网格质量较高。首先,采用拉普拉斯算子从给定网格树模型中提取线段骨架信息；其次,将线骨架表示的整棵树自动细分生成子树,再利用所生成的子树合成新的树模型,并采用卷积曲面来局部逼近骨架模型；最后,通过简单的骨架编辑,可生成基于卷积曲面表示的树干,再将其细分为沿骨架方向有良好边流效果的.四边形网格。在整个过程中最耗时的细分、卷积曲面逼近采用基于CUDA的GPU并行算法处理。利用该建模系统,通过交互式编辑骨架,即可方便快捷地创建各种新的树模型。·提出一种可高效生成四边形网格的新的建模树形物体的方法。首先,从输入网格中提取线骨架,并沿骨架生成包围多面体;其次,以该多面体为控制网格执行Catmull-Clark细分过程,通过逆向求解控制顶点位置,且细分后的极曲面能够较好地逼近原始数据。由于选用GPU加速的细分策略,使得过程相当高效。该方法提供了一个建模树形分枝结构的紧致表示方式,可应用于树枝、动物躯干和脉管等树形分枝结构中。对以上所有问题提出的解决方案,文中都做了实验对比,以验证本文方法的正确性。文章最后系统总结了本文所做的工作,分析了本文研究成果的不足之处,并展望未来的研究方向。更多还原

【Abstract】 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.更多还原