高阶连续插值型细分方法及其局部算子的创建

Subdivision is a standard modeling tool in computer graphics and geometric design for generating curves and surfaces by iteratively applying local refinement rules to an initial control polygon or mesh. There are two classes of subdivision schemes, namely interpolatory and approximating schemes, depending on whether the limit curve or surface interpolates the initial control vertices or not. For approximating schemes, it is known how to split the refinement rules into sequences of very local operations, resulting in an efficient process for computing new vertices, and yet obtaining limit curves and surfaces with high order of continuity. However, little work has been done on how to factorize interpolatory schemes this way. Up to now, interpolatory schemes with local rules yield only C1 continuous limit curves and surfaces. In this project, we propose to develop new interpolatory subdivision schemes based on simple local refinement operations, similar to those of the Lane-Riesenfeld algorithm for generating uniform B-splines. The continuity of the resulting limit curves and surfaces can be of an arbitrary high order, except at a limited number of extraordinary vertices where C1 continuity is obtained in the surface case. The key aspects of this project include: (1) designing interpolatory subdivision schemes for different types of meshes and topological splitting with higher order continuity at regular vertices; (2) decompose subdivision rules at regular vertices into very local operations; (3) using the Fourier transform and its inverse to extend the construction of local operations to extraordinary vertices; (4) simple methods for analyzing the smoothness of the limit surface at the extraordinary vertices; and (5) incorpotating crease and boundary features on the limit surface with also repeated local operations. Overall, this project proposes to develop simple and efficient algorithms for implementing interpolatory subdivision schemes with highly continuous limit curves and surfaces, and to lay the foundations for applying interpolatory subdivision schemes in both computer graphics and geometric design.

细分方法是计算机图形学中的一个标准造型方法。根据极限曲面是否插值控制顶点，细分方法分为插值型和逼近型。借助于局部算子，即计算新点时仅用其直接邻域信息的算子，诸多文献探讨了如何构造高阶连续的逼近型细分方法。然而，类似的插值型细分方法甚少。而且，目前常用的插值型细分只能达到C1连续。本项目旨在把局部算子引入高阶连续的插值型细分，使极限曲面在规则点处高阶连续，在不规则点处C1连续。其主要内容有：设计各种网格类型和各种拓扑分裂方式所对应的高阶连续插值型细分方法并创建其规则点处基于局部算子的细分模板；借助于傅立叶变换及其逆变换等手段把规则点处基于局部算子的细分模板推广到不规则点、边界点处；证明插值型细分方法在不规则点C1连续的简便方法；证明基于局部算子的插值型细分在不规则点C1连续等。本项目将提出若干算法简单的高阶连续插值型细分方法，为插值型细分方法在计算机图形学及相关领域中的进一步应用打下基础。

本项目旨在把局部算子引入高阶连续的插值型细分，使极限曲面在规则点处高阶连续，在不规则点处C1连续。项目执行4年以来，项目组成员齐心协力，刻苦攻关，在高阶连续的插值型细分方法方面取得了一定的进展，为拓展其在计算机动画和计算机图形学等领域的进一步应用打下了基础。在计算机图形学和计算机辅助设计领域国际重要期刊Computer Graphics Forum, Computer-Aided Design、Computer Aided Geometric Design发表论9篇(含录用1篇)。另在其它期刊或会议发表论文10篇，培养研究生7名。在项目实施期间，主办国际会议1次，项目组成员参加其它国际会议5人次，国内会议6人次。主要成果如下：1. 基于局部算子的伪样条细分方法，建立了介于B样条细分曲面与插值细分曲面之间的一类细分曲面。发表于Computer Graphics Forum。2.曲线曲面拟合的渐进迭代逼近算法，具有可重用性、保形性等优点。发表于Computer Aided Design。3.基于双圆弧插值的空间曲线细分方法，其极限曲线G2连续且较为光顺。发表于Computer Aided Geometric Design。4.基于局部算子的2N点插值细分方法实现方法，提高了计算新点的效率且无需存储系数。发表于Computer Aided Geometric Design。5.具有最小支撑域的对称二元伪样条，把一元伪样条推广到二元四向箱样条。已被Computer Aided Geometric Design录用。6.利用多项式再生阶的插值型细分求值方法，其系数矩阵的规模远小于以往的方法。发表于Journal of Computational and Applied Mathematics。7.四边形上一类广义重心坐标的极限性质及单调性，保证其等值线无局部极值点。发表于Computer Aided Geometric Design。8.插值切向及曲率的内心细分法，仅改变第一步的几何规则即可使内心细分法插值给定切向及曲率。发表于Dolomites Research Notes on Approximation。9.双参数几何细分方法，用有理二次Bezier曲线混合圆构造一系列极限曲线形状可控的细分方法。录用于2017年全国几何设计与计算学术会议报告并推荐到《图学学报》。