Dynamic Sampling and Rendering of Algebraic Point Set Surfaces

Algebraic Point Set Surfaces (APSS) define a smooth surface from a set of points using local moving least‐squares (MLS) fitting of algebraic spheres. In this paper we first revisit the spherical fitting problem and provide a new, more generic solution that includes intuitive parameters for curvature control of the fitted spheres. As a second contribution we present a novel real‐time rendering system of such surfaces using a dynamic up‐sampling strategy combined with a conventional splatting algorithm for high quality rendering. Our approach also includes a new view dependent geometric error tailored to efficient and adaptive up‐sampling of the surface. One of the key features of our system is its high degree of flexibility that enables us to achieve high performance even for highly dynamic data or complex models by exploiting temporal coherence at the primitive level. We also address the issue of efficient spatial search data structures with respect to construction, access and GPU friendliness. Finally, we present an efficient parallel GPU implementation of the algorithms and search structures.     

点模型曲面的调和映射参数化

利用调和映射的平面和球面中值性质,提出了确定点模型曲面参数化映射中有关权因子的两种新方法,设计了能够达到内在变形较小的相应参数化方法,并将参数化方法应用于点模型曲面上的纹理映射．实验和统计结果表明,文中方法是比较有效的点模型曲面的参数化方法．     

Smoothing of Partition of Unity Implicit Surfaces for Noise Robust Surface Reconstruction

We propose a novel method for smoothing partition of unity (PU) implicit surfaces consisting of sets of non-conforming linear functions with spherical supports. We derive new discrete differential operators and Laplacian smoothing using a spherical covering of PU as a grid-like data structure. These new differential operators are applied to the smoothing of PU implicit surfaces. First, Laplacian smoothing is performed for the vector field defined by the gradient of the PU implicit surface, which is then updated to reflect the smoothing of the gradient field. This process achieves a method for noise robust surface reconstruction from scattered points.     

Level Set Equations on Surfaces via the Closest Point Method

Level set methods have been used in a great number of applications in ?² and ?³ and it is natural to consider extending some of these methods to problems defined on surfaces embedded in ?³ or higher dimensions. In this paper we consider the treatment of level set equations on surfaces via a recent technique for solving partial differential equations (PDEs) on surfaces, the Closest Point Method (Ruuth and Merriman, J. Comput. Phys. 227(3):1943–1961, [2008]). Our main modification is to introduce a Weighted Essentially Non-Oscillatory (WENO) interpolation step into the Closest Point Method. This, in combination with standard WENO for Hamilton–Jacobi equations, gives high-order results (up to fifth-order) on a variety of smooth test problems including passive transport, normal flow and redistancing. The algorithms we propose are straightforward modifications of standard codes, are carried out in the embedding space in a well-defined band around the surface and retain the robustness of the level set method with respect to the self-intersection of interfaces. Numerous examples are provided to illustrate the flexibility of the method with respect to geometry.     

Feature Preserving Point Set Surfaces based on Non-Linear Kernel Regression

Moving least squares (MLS) is a very attractive tool to design effective meshless surface representations. However, as long as approximations are performed in a least square sense, the resulting definitions remain sensitive to outliers, and smooth-out small or sharp features. In this paper, we address these major issues, and present a novel point based surface definition combining the simplicity of implicit MLS surfaces [ SOS04 , Kol05 ] with the strength of robust statistics. To reach this new definition, we review MLS surfaces in terms of local kernel regression, opening the doors to a vast and well established literature from which we utilize robust kernel regression. Our novel representation can handle sparse sampling, generates a continuous surface better preserving fine details, and can naturally handle any kind of sharp features with controllable sharpness. Finally, it combines ease of implementation with performance competing with other non-robust approaches.     

多色点集直线划分的复杂性及其近似算法

多色点集划分研究如何将含有不同颜色点的平面划分为各个区域,每个区域中只包含一种颜色的点。这是计算几何中的一种组合优化问题。但是现有的多边形划分方式性能较差。为此,提出用直线来划分平面。针对平面上多色点集的直线划分,将其离散化,证明其可以被非确定性图灵机在多项式时间内判定。并将Max2SAT问题在多项式时间内归约到组合优化问题,证明多色点集直线划分为NP难,从而证明其是NP完全的。利用最优化版本的特有性质,运用贪心方法构造出多项式时间的近似算法,并L归约到Setcover问题,以此证明算法的近似比为O( lgn)。     

基于多重分割结构上的矩阵分割算法

文章在虚共享存储并行系统上建立了矩阵分割的多重结构,提出了一个基于此结构上的矩阵分割算法,能有效避免多处理机间的访存冲突问题,并基本实现分配的负载平衡。文章中所建立的这种多重结构,通用性较强,如用于矩阵乘和矩阵求逆操作。另外还给出了能嵌入矩阵操作之前的程序流程图,并给出了实验数据。     

三角网格上的代数曲面重建

提出一种用分片代数曲面构造三角曲面片的方法,利用具有公共边的2个三角形区域的4个顶点的函数值以及公共边2个端点的外法向量来构造一个二次曲面V(g)和一个截面V(h),其交V(g,h)即为2个三角曲面片的公共边界曲线.对每个已确定了边界条件的三角片内部进一步划分成3部分,每部分各自定义一个三次代数曲面.这3个三次代数曲面不仅在其交线处光滑拼接,而且分别沿三角形的边界与V(g)光滑拼接,从而构成一个具有GC1连续性的分片代数曲面.对于只属于一个三角片的边界留有一个自由度,可对曲面形状加以控制.     

Recognising Algebraic Surfaces from Two Outlines

Photographic outlines of 3 dimensional solids are robust and rich in information useful for surface reconstruction. This paper studies algebraic surfaces viewed from 2 cameras with known intrinsic and extrinsic parameters. It has been known for some time that for a degree d=2 (quadric) algebraic surface there is a 1-parameter family of surfaces that reproduce the outlines. When the algebraic surface has degree d>2, we prove a new result: that with known camera geometry it is possible to completely reconstruct an algebraic surface from 2 outlines i.e. the coefficients of its defining polynomial can be determined in a known coordinate frame. The proof exploits the existence of frontier points, which are calculable from the outlines. Examples and experiments are presented to demonstrate the theory and possible applications.

Multiresolution for Algebraic Curves and Surfaces using Wavelets

This paper describes a multiresolution method for implicit curves and surfaces. The method is based on wavelets, and is able to simplify the topology. The implicit curves and surfaces are defined as the zero-valued piece-wise algebraic isosurface of a tensor-product uniform cubic B-spline. A wavelet multiresolution method that deals with uniform cubic B-splines on bounded domains is proposed. In order to handle arbitrary domains the proposed algorithm dynamically adds appropriate control points and deletes them in the synthesis phase.     

Ray Casting Algebraic Surfaces using the Frustum Form

We propose an algorithm for interactive ray‐casting of algebraic surfaces of high degree. A key point of our approach is a polynomial form adapted to the view frustum. This so called frustum form yields simple expressions for the Bernstein form of the ray equations, which can be computed efficiently using matrix products and pre‐computed quantities. Numerical root‐finding is performed using B‐spline and Bézier techniques, and we compare the performances of recent and classical algorithms. Furthermore, we propose a simple and fairly efficient anti‐aliasing scheme, based on a combination of screen space and object space techniques. We show how our algorithms can be implemented on streaming architectures with single precision, and demonstrate interactive frame‐rates for degrees up to 16.     

Stable Algebraic Surfaces for 3D Object Representation

Linear fitting techniques by implicit algebraic models usually suffer from global stability problems. Ridge regression regularization can be used to improve the stability of algebraic surface fits. In this paper a Euclidean Invariant 3D ridge regression matrix is developed and applied to a particular linear algebraic surface fitting method. Utilization of such a regularization in fitting process makes it possible to globally stabilize 3D object fits with surfaces of any degree. Robustness to noise and moderate levels of occlusion has also been enhanced significantly. Experimental results are presented to verify the improvements in global stability and robustness of the resulting fits.

点集的多IFS编码

文中首先论述了分形编码方法的发展概况,简单介绍了迭代函数系统(IFS)的理论,然后提出了点集的多IFS的思想,定义了多IFS中仿射变换伴随集的概念并给出了求伴随集的两种方法,在此基础上提出了构造点集的多IFS的算法,最后给出了算法的一维实验结果。     

构造代数Blending曲面的Grobner基方法

利用代数几何中关于理想的Groebner基的理论,结合CAGD中的研究方法,对代数Blending曲面做了较为细致的研究,给出了用Groebner基构造代数Blending曲面的新方法,该方法能够求出所有满足要求的代数Blending曲面,并能给出其中次数最低的曲面,文中还讨论了如何利用代数曲面插值,最小平方逼近的方法来选取合适的自由参数,以达到对代数Blending曲面进行形状控制的目的,最后给出了一个茶壶表面造型示例,以说明方法的有效性。     

A Partition of Unity Method with Penalty for Fourth Order Problems

A partition of unity method for fourth order problems is proposed. As a model problem, we focus on the biharmonic problem with either clamped or simply supported boundary conditions when the domain is a bounded polygon. The algorithm is presented, error estimates are made, and numerical results are shown to verify the error estimates.     

Point Set pattern matching ind-dimensions

In this paper we apply computational geometry techniques to obtain an efficient algorithm for the following point set pattern matching problem. Given a setS ofn points and a setP ofk points in thed-dimensional Euclidean space, determine whetherP matches anyk-subset ofS, where a match can be any similarity, i.e., the setP is allowed to undergo translation, rotation, reflection, and global scaling. Motivated by the need to traverse the sets in an orderly fashion to shun exponential complexity, we circumvent the lack of a total order for points in high-dimensional spaces by using an extension of one-dimensional sorting to higher dimensions (which we call circular sorting). This mechanism enables us to achieve the orderly traversal we sought. An optimal algorithm (in time and space) is described for performing circular sorting in arbitrary dimensions. The time complexity of the resulting algorithm for point set pattern matching is O(n logn+kn) for dimension one and O(kn^d) for dimensiond2.Supported in part by CNPq-Conselho Nacional de Desenvolvimento Cientifico e Tecnológico (Brazil) under Grants 200331/79, 300157/90-8, and 500787/91-3.Supported in part by the National Science Foundation under Grant CCR 8901815.     

Riemann Surfaces, Plane Algebraic Curves and Their Period Matrices

The aim of this paper is to present theoretical basis for computing a representation of a compact Riemann surface as an algebraic plane curve and to compute a numerical approximation for its period matrix. We will describe a program C ars (Semmler et al., 1996) that can be used to define Riemann surfaces for computations. C ars allows one also to perform the Fenchel–Nielsen twist and other deformations on Riemann surfaces.Almost all theoretical results presented here are well known in classical complex analysis and algebraic geometry. The contribution of the present paper is the design of an algorithm which is based on the classical results and computes first an approximation of a polynomial representing a given compact Riemann surface as a plane algebraic curve and further computes an approximation for a period matrix of this curve. This algorithm thus solves an important problem in the general case. This problem was first solved, in the case of symmetric Riemann surfaces, in Seppälä (1994).     

构造代数Blending曲面的Gr bner基方法

利用代数几何中关于理想的 Gr bner基的理论 ,结合 CAGD中的研究方法 ,对代数 Blending曲面做了较为细致的研究 ,给出了用 Gr bner基构造代数 Blending曲面的新方法 .该方法能够求出所有满足要求的代数Blending曲面 ,并能给出其中次数最低的曲面 .文中还讨论了如何利用代数曲面插值、最小平方逼近的方法来选取合适的自由参数 ,以达到对代数 Blending曲面进行形状控制的目的 .最后给出了一个茶壶表面造型示例 ,以说明方法的有效性     

点到隐式曲面的正交投影计算

针对点到隐式曲面的正交投影问题,提出一种稳定的几何迭代算法.首先构造初始点处的一条特殊的法截线,并给出沿着该法截线追踪投影点的二阶泰勒迭代方法;然后将给定点向初始点处的法截线的曲率圆作投影,提出基于曲率的步长控制策略,在此基础上给出了基于梯度的迭代误差矫正方法.仿真结果表明,该算法具有良好的收敛性、鲁棒性以及精确性.