Loop subdivision surfaces interpolating -spline curves

This paper presents a novel method for defining a Loop subdivision surface interpolating a set of popularly-used cubic B-spline curves. Although any curve on a Loop surface corresponding to a regular edge path is usually a piecewise quartic polynomial curve, it is found that the curve can be reduced to a single cubic B-spline curve under certain constraints of the local control vertices. Given a set of cubic B-spline curves, it is therefore possible to define a Loop surface interpolating the input curves by enforcing the interpolation constraints. In order to produce a surface of local or global fair effect, an energy-based optimization scheme is used to update the control vertices of the Loop surface subjecting to curve interpolation constraints, and the resulting surface will exactly interpolate the given curves. In addition to curve interpolation, other linear constraints can also be conveniently incorporated. Because both Loop subdivision surfaces and cubic B-spline curves are popularly used in engineering applications, the curve interpolation method proposed in this paper offers an attractive and essential modeling tool for computer-aided design.     

插值细分曲面三角剖分研究

把三维参数化曲面的离散化算法应用到三角网格表示的离散曲面上。用一种可生成C1阶连续曲面的插值分割技术——改进蝶形算法,重新构造极限面。用推进波前法在物理空间直接离散化,所以不需要进行参数化。     

Polynomial regression under arbitrary product distributions

In recent work, Kalai, Klivans, Mansour, and Servedio (2005) studied a variant of the “Low-Degree (Fourier) Algorithm” for learning under the uniform probability distribution on {0,1} ⁿ . They showed that the L ₁ polynomial regression algorithm yields agnostic (tolerant to arbitrary noise) learning algorithms with respect to the class of threshold functions—under certain restricted instance distributions, including uniform on {0,1} ⁿ and Gaussian on ? ⁿ . In this work we show how all learning results based on the Low-Degree Algorithm can be generalized to give almost identical agnostic guarantees under arbitrary product distributions on instance spaces X ₁×???×X _n . We also extend these results to learning under mixtures of product distributions. The main technical innovation is the use of (Hoeffding) orthogonal decomposition and the extension of the “noise sensitivity method” to arbitrary product spaces. In particular, we give a very simple proof that threshold functions over arbitrary product spaces have δ-noise sensitivity $O(\sqrt{\delta})$ , resolving an open problem suggested by Peres (2004).     

Polygonal mesh regularization for subdivision surfaces interpolating meshes of curves

Published online: 14 February 2003     

基于块的任意曲面上的纹理合成

一种新的曲面纹理合成技术被提出,它采用求最小割集来解决块拼接时的礁缝走样问题。算法在预处理期对模型的三维网格进行了重建,使其规则并且建立网格点与参数化栅格采样后的图像点一一对应的关系,无论对合成的速度和质量都有很大的提高。提出了在曲面上进行纹理粘贴的算法,对于渲染存在不完整性的自然物体取得了较好的效果。     

Hexagonal global parameterization of arbitrary surfaces

We introduce hexagonal global parameterization, a new type of surface parameterization in which parameter lines respect sixfold rotational symmetries (6-RoSy). Such parameterizations enable the tiling of surfaces with nearly regular hexagonal or triangular patterns, and can be used for triangular remeshing. Our framework to construct a hexagonal parameterization, referred to as HEXCOVER, extends the QUADCOVER algorithm and formulates necessary conditions for hexagonal parameterization. We also provide an algorithm to automatically generate a 6-RoSy field that respects directional and singularity features in the surface. We demonstrate the usefulness of our geometry-aware global parameterization with applications such as surface tiling with nearly regular textures and geometry patterns, as well as triangular and hexagonal remeshing.     

Graphics processing unit‐based triangulations of Blinn molecular surfaces

Computing the surface of a molecule (e.g., a protein) plays an important role in the analysis of its geometric structure as needed in the study of interactions between proteins, protein folding, protein docking, and so forth. There are a number of algorithms for the computation of molecular surfaces and their triangulations, but only a few take advantage of graphics processing unit computing. This paper describes a graphics processing unit‐based marching cubes algorithm to triangulate molecular surfaces. In the end of the paper, a performance analysis of three implementations (i.e., serial CPU, CUDA, and OpenCL) of the marching cubes‐based triangulation algorithm takes place as a way to realize beforehand how molecular surfaces can be rendered in real‐time in the future. Copyright © 2011 John Wiley & Sons, Ltd.     

任意散乱点集的B-样条曲面重建

为了解决工业设计中复杂形体的曲面造型问题,提出了一种张量积型的低阶B-样条曲面重建算法。先将采集到的任意拓扑形状的散乱数据点进行三次不同的参数化得到四边形控制网格,然后再采用张量积型的双二次、双三次B-样条进行拟合,在拟合的过程中采用距离函数来控制拟合误差,得到光滑的曲面。运用该方法,直接对初始散乱点集进行重建,方法简单易实施,重建效率高并且重建后的样条曲面自然满足切平面连续。与以往的方法相比,该方法在逆向工程中可以在保证连续性的情况下,得到精准的结果曲面,提高了曲面造型的质量和效率。     

插值给定对角曲线的能量极小Bézier曲面造型

目的 曲面造型是计算机辅助几何设计中的重要研究内容,张量积类型曲面的对角曲线是衡量曲面性质的重要度量,与曲面的几何形状密切相关。基于输入对角曲线的曲面设计方法在实际应用中具有一定的价值,因此提出一种插值给定对角曲线的能量极小Bézier曲面造型的方法。方法 给定一条对角曲线时,修正用户输入的对角曲线及边界曲线的几何信息,然后运用拉格朗日乘数法,结合曲面内部能量函数,求解待定的内部控制顶点,构造曲面。给定两条对角曲线时,在上述内容基础上加入了两条对角曲线必有交点的考量,增加对对角曲线控制顶点的修正。结果 增加了对角曲线这一约束条件,从对比实验曲线图可以看出,随着横坐标曲面阶数升高,纵坐标修正曲线和用户曲线间的差值越来越小,结果表明曲面阶数越高,修正曲线与用户曲线偏差越小,造型效果越好。结论 该曲面造型方法简单,基于修正后的对角曲线和边界曲线构造的曲面具有极小内部能量,可满足曲面造型方面的相关需求。     

Recursively generated B-spline surfaces on arbitrary topological meshes

This paper describes a method for recursively generating surfaces that approximate points lying-on a mesh of arbitrary topology. The method is presented as a generalization of a recursive bicubic B-spline patch subdivision algorithm. For rectangular control-point meshes, the method generates a standard B-spline surface. For non-rectangular meshes, it generates surfaces that are shown to reduce to a standard B-spline surface except at a small number of points, called extraordinary points. Therefore, everywhere except at these points the surface is continuous in tangent and curvature. At the extraordinary points, the pictures of the surface indicate that the surface is at least continuous in tangent, but no proof of continuity is given. A similar algorithm for biquadratic B-splines is also presented.     

Thin film flow on surfaces containing arbitrary occlusions

The flow of a continuous liquid film, only several microns in thickness, on a plane surface containing occlusions, is modelled using lubrication theory. The resultant time-dependent non-linear equation set is discretised using both finite difference and finite element analogues; the former is solved using a very efficient full approximation storage (FAS) multigrid algorithm employing both automatic spatial and temporal adaptivity, the latter exploits the COMSOL suite of software to solve a weak form of the governing equations. The efficiencies and accuracies of both approaches are compared and a variety of problems, of increasing complexity, explored. Although the adaptive multigrid approach is clearly the most efficient, with the two sets of solutions indistinguishable, COMSOL offers an attractive alternative to the non-specialist user. The results, the first of their kind, further demonstrate: (i) the power of using adaptive multigriding, in time as well as space, for the simultaneous control of both spatial and temporal errors; (ii) the significant reduction in memory requirements and CPU time that can be achieved. It is revealed that occlusions lead to many of the features inherent in the flow of thin liquid films over fully submerged micro-scale topographic features; namely, the presence of capillary ridges linked to “bow-wave” plus “comet-tail” free-surface disturbances.     

Interpolation of arbitrary spaced points by closed surfaces

A procedure using spherical coordinates is devised to interploate points in two (resp. three) dimensional spaces by closed smooth curves (resp. surfaces). It can be applied to any of the existing methods for interpolating points. In this article, the Shepard and Maude methods are considered. The interpolation depends upon the choice of a “pole”, therefore, is not unique and, thus, can be controlled at will up to some extent.     

Method of direct texture synthesis on arbitrary surfaces

A direct texture synthesis method on arbitrary surfaces is proposed in this paper. The idea is to recursively map triangles on surface to texture space until the surface is completely mapped. First, the surface is simplified and a tangential vector field is created over the simplified mesh. Then, mapping process searches for the most optimal texture coordinates in texture sample for each triangle, and the textures of neighboring triangles are blended on the mesh. All synthesized texture triangles are compressed to an atlas. Finally, the simplified mesh is subdivided to approach the initial surface. The algorithm has several advantages over former methods: it synthesizes texture on surface without local parameterization; it does not need partitioning surface to patches; and it does not need a particular texture sample. The results demonstrate that the new algorithm is applicable to a wide variety of texture samples and any triangulated surfaces.     

Globally optimal surface mapping for surfaces with arbitrary topology

Computing smooth and optimal one-to-one maps between surfaces of same topology is a fundamental problem in computer graphics and such a method provides us a ubiquitous tool for geometric modeling and data visualization. Its vast variety of applications includes shape registration/matching, shape blending, material/data transfer, data fusion, information reuse, etc. The mapping quality is typically measured in terms of angular distortions among different shapes. This paper proposes and develops a novel quasi-conformal surface mapping framework to globally minimize the stretching energy inevitably introduced between two different shapes. The existing state-of-the-art inter-surface mapping techniques only afford local optimization either on surface patches via boundary cutting or on the simplified base domain, lacking rigorous mathematical foundation and analysis. We design and articulate an automatic variational algorithm that can reach the global distortion minimum for surface mapping between shapes of arbitrary topology, and our algorithm is sorely founded upon the intrinsic geometry structure of surfaces. To our best knowledge, this is the first attempt towards numerically computing globally optimal maps. Consequently, our mapping framework offers a powerful computational tool for graphics and visualization tasks such as data and texture transfer, shape morphing, and shape matching.     

Generation of high order surfaces over arbitrary polyhedral meshes

A new algorithm for generating high order surfaces over arbitrary meshes will be discussed in this paper. This technique offers more freedom to the designer for controlling the shape of free-form objects in order to meet the various constraints. It also has the advantage of being compatible with B-spline surfaces over rectangular grids of points.     

Graham triangulations and triangulations with a center are hamiltonean

Let P be a point set with n elements in general position. A triangulation T of P is a set of triangles with disjoint interiors such that their union is the convex hull of P, no triangle contains an element of P in its interior, and the vertices of the triangles of T are points of P. Given T we define a graph G(T) whose vertices are the triangles of T, two of which are adjacent if they share an edge. We say that T is hamiltonean if G(T) has a hamiltonean path. We prove that the triangulations produced by Graham's Scan are hamiltonean. Furthermore we prove that any triangulation T of a point set which has a point adjacent to all the points in P (a center of T) is hamiltonean.