Subdivision-based Algorithms for Surface Modeling

细分最初被设想为样条的扩展，以控制任意拓扑的网格。细分算法虽然更加灵活和通用，但保留了样条的一些有用性质。最重要的是，这些算法生成的曲面具有自然的层次结构，并且使用简单的局部规则进行计算。这允许设计高效的分层、局部和自适应算法来渲染、操作、碰撞检测和这些表面的交叉。细分表面正在迅速获得广泛接受的行业。近年来，在了解细分表面的性质，特别是光滑性方面取得了实质性进展。然而，对于样条曲线的细分仍然缺乏充分理解和可靠的算法，并且细分的一些实际重要方面，如边界和奇异特征的细分规则，没有严格的理论基础。除光滑性外，没有详细研究细分曲面的其他性质。同时，常用的平稳细分方案的一些基本局限性也变得明显起来。例如，实际的曲率连续细分曲面必然有一个“平面”。在特殊的顶点附近有斑点，而表面在高价点附近获得波纹。提出的研究有三个主要目标：推进平稳细分理论，以包括所有重要的实际情况，并发展必要的理论来理解细分的公平性、网格质量和近似性质。为常见的几何运算开发健壮的算法，如计算碰撞和细分曲面的相交；探索保留局部性的非平稳细分方案，并确定在不牺牲性能的情况下提高所得表面质量的方法。这三个组成部分由一个共同的目标统一起来：开发支持高效、局部、分层和自适应几何建模算法的表面表示。

Subdivision was initially conceived as an extension of splines to control meshes ofarbitrary topology. Subdivision algorithms, while being more flexible and general,retain a number of useful properties of splines. Most importantly, the surfaces generatedby these algorithms have a natural hierarchical structure and are computedusing simple local rules. This allows the design of efficient hierarchical, local, andadaptive algorithms for rendering, manipulation, collision detection and intersectionof such surfaces. Subdivision surfaces are rapidly gaining wide acceptance inthe industry. In recent years, substantial progress has been made in understandingthe properties of the subdivision surfaces, especially smoothness properties. However,subdivision still lacks the body of well understood and reliable algorithmsavailable for splines and a few practically important aspects of subdivision, suchas subdivision rules for boundaries and singular features, do not have a rigoroustheoretical foundation. Aside from smoothness, no other property of subdivisionsurfaces has been studied in detail. At the same time, some fundamental limitationsof the commonly used stationary subdivision schemes became apparent. For example,practical curvature-continuous subdivision surfaces necessarily have a "flat."spot near extraordinary vertices, and the surfaces acquire ripples near vertices ofhigh valence. The proposed research has three main objectives:Advance the theory of stationary subdivision to include all important practicalcases, and develop the theory necessary to understand fairness, meshquality, and approximation properties of subdivision.Develop robust algorithms for common geometric operations such as com-puttingcollisions and intersections of subdivision surfaces;Explore nonstationary subdivision schemes which retain locality, and identifyways to improve the quality of the resulting surfaces without sacrificingthe performance.The three components are unified by a common goal: the development of asurface representation supporting highly efficient, local, hierarchical and adaptivealgorithms for geometric modeling.