Construction of Surfaces with Parallelism Conditions

In this paper we define the notion of pseudo-parallel parameterized surfaces, extending that of offset surfaces. Then we consider the problem of fitting a set of scattered points with a surface pseudo-parallel to a given reference surface. We propose a method of solution based on a modified version of the classical smoothing D ^m -splines over a bounded domain. The convergence of the method is established and some numerical examples are given.     

基于层次T网格的分片孔斯曲面重构

本文提出一种基于任意层次T网格的多项式(PHT)样条空间$S(3,3,1,1,T)$的一个新的曲面重构算法.该算法由分片插值于层次T网格上每个小矩形单元对应4个顶点的16个参数的孔斯曲面形式给出.对于一个给定的T网格和相应基点处的几何信息(函数值,两个一阶偏导数和混合导数值),可得到与$S(3,3,1,1,T)$的PHT样条曲面相同的结果,且曲面表达形式更简单,同时,在离散数据点的曲面拟合中,我们给出了自适应的曲面加细算法.数值算例显示,该自适应算法能够有效的拟合离散数据点.     

Least-Squares Fitting of Algebraic Spline Surfaces

We present an algorithm for fitting implicitly defined algebraic spline surfaces to given scattered data. By simultaneously approximating points and associated normal vectors, we obtain a method which is computationally simple, as the result is obtained by solving a system of linear equations. In addition, the result is geometrically invariant, as no artificial normalization is introduced. The potential applications of the algorithm include the reconstruction of free-form surfaces in reverse engineering. The paper also addresses the generation of exact error bounds, directly from the coefficients of the implicit representation.     

一种二次保形插值参数曲面

1．引言保形插值是工业设计和制造中经常遇到的问题，有关这方面的研究已有许多文献【‘－u1．设n二Fx；，yi，人，川7一0，1，…；n；j＝0；l，…，。；x；＜x；＋1．l＝0，1，…．n—1；yi＜的十；，J二O，L…，。一卫｝是一给定的数据集，Cadson和［ltsch、Beatson和zejerJ－1985年分别提出的方法只保持被插数据集的轴向单调性；Dodd和Roulier等人于1983和1987年提出的方法只保持被插点集网格线上的轴向凸凹性和单调性；Constantini和FOntanella于1990年提出的方法可保持被插点集在所有于区域的边界及共内部的轴向凸凹性和单调性；…     

Smooth surface reconstruction via natural neighbour interpolation of distance functions

We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and accommodates non-uniform samples. The reconstructed surface interpolates the data points and is implicitly represented as the zero set of some pseudo-distance function. It can be meshed so as to satisfy a user-defined error bound, which makes the method especially relevant for small point sets. Experimental results are presented for surfaces in .     

Existence and uniqueness of solutions of surface reconstruction problem

Surface reconstruction from scattered data is an important problem in such areas as reverse engineering and computer aided design.In solving partial differential equations derived from surface reconstruction problems,level-set method has been successfully used.We present in this paper a theoretical analysis on the existence and uniqueness of the solution of a partial differential equation derived from a model of surface reconstruction using the level-set approach.We give the uniqueness analysis of the cl...     

Numerical control of kohonen neural network for scattered data approximation

Surface reconstruction from scattered data using Kohonen neural network is presented in this paper. The network produces a topologically predefined grid from the unordered data which can be applied as a rough approximation of the input set or as a base surface for further process. The quality and computing time of the approximation can be controlled by numerical parameters. As a further application, ruled surface is produced from a set of unordered lines by the network. AMS subject classification 68U07, 65D17, 68T20     

Adaptive thinning for bivariate scattered data

This paper studies adaptive thinning strategies for approximating a large set of scattered data by piecewise linear functions over triangulated subsets. Our strategies depend on both the locations of the data points in the plane, and the values of the sampled function at these points—adaptive thinning. All our thinning strategies remove data points one by one, so as to minimize an estimate of the error that results by the removal of a point from the current set of points (this estimate is termed “anticipated error”). The thinning process generates subsets of “most significant” points, such that the piecewise linear interpolants over the Delaunay triangulations of these subsets approximate progressively the function values sampled at the original scattered points, and such that the approximation errors are small relative to the number of points in the subsets. We design various methods for computing the anticipated error at reasonable cost, and compare and test the performance of the methods. It is proved that for data sampled from a convex function, with the strategy of convex triangulation, the actual error is minimized by minimizing the best performing measure of anticipated error. It is also shown that for data sampled from certain quadratic polynomials, adaptive thinning is equivalent to thinning which depends only on the locations of the data points—nonadaptive thinning. Based on our numerical tests and comparisons, two practical adaptive thinning algorithms are proposed for thinning large data sets, one which is more accurate and another which is faster.     

Scattered and track data interpolation using an efficient strip searching procedure

A new local algorithm for bivariate interpolation of large sets of scattered and track data is presented. The method, which changes partially depending on the kind of data, is based on the partition of the interpolation domain in a suitable number of parallel strips, and, starting from these, on the construction for any data point of a square neighbourhood containing a convenient number of data points. Then, the well-known modified Shepard’s formula for surface interpolation is applied with some effective improvements. The proposed algorithm is very fast, owing to the optimal nearest neighbour searching, and achieves good accuracy. Computational cost and storage requirements are analyzed. Moreover, the efficiency and reliability of the algorithm are shown by several numerical tests, also performed by Renka’s algorithm for a comparison.     

加密网格点二元局部基插值样条函数

1.简介 由于在理论以及应用两方面的重要性,多元样条引起了许多人的注意([6],[7]),紧支撑光滑分片多项式函数对于曲面的逼近是一个十分有效的工具。由于它们的局部支撑性,它们很容易求值;由于它们的光滑性,它们能被应用到要满足一定光滑条件的情况下;由于它们是紧支撑的,它们的线性包有很大的逼近灵活性,而且用它们构造逼近方法来解决的系统是     

Scattered Data Fitting by Direct Extension of Local Polynomials to Bivariate Splines

We present a new scattered data fitting method, where local approximating polynomials are directly extended to smooth (C ¹ or C ²) splines on a uniform triangulation Δ (the four-directional mesh). The method is based on designing appropriate minimal determining sets consisting of whole triangles of domain points for a uniformly distributed subset of Δ. This construction allows to use discrete polynomial least squares approximations to the local portions of the data directly as parts of the approximating spline. The remaining Bernstein–Bézier coefficients are efficiently computed by extension, i.e., using the smoothness conditions. To obtain high quality local polynomial approximations even for difficult point constellations (e.g., with voids, clusters, tracks), we adaptively choose the polynomial degrees by controlling the smallest singular value of the local collocation matrices. The computational complexity of the method grows linearly with the number of data points, which facilitates its application to large data sets. Numerical tests involving standard benchmarks as well as real world scattered data sets illustrate the approximation power of the method, its efficiency and ability to produce surfaces of high visual quality, to deal with noisy data, and to be used for surface compression.     

Local Lagrange Interpolation with Bivariate Splines of Arbitrary Smoothness

We describe a method which can be used to interpolate function values at a set of scattered points in a planar domain using bivariate polynomial splines of any prescribed smoothness. The method starts with an arbitrary given triangulation of the data points, and involves refining some of the triangles with Clough-Tocher splits. The construction of the interpolating splines requires some additional function values at selected points in the domain, but no derivatives are needed at any point. Given n data points and a corresponding initial triangulation, the interpolating spline can be computed in just O(n) operations. The interpolation method is local and stable, and provides optimal order approximation of smooth functions.     

Scattering of Love waves due to the presence of a rigid barrier of finite depth in the crustal layer of the earth

The problem of scattering of Love waves due to the presence of a rigid barrier of finite depth in the crusfal layer of the earth is studied in the present paper. The barrier is in the slightly dissipative surface layer and the surface of the layer is a free surface. The Wiener-Hopf technique is the method of solution. Evaluation of the integrals along appropriate contours in the complex plane yields the reflected, transmitted and the scattered waves. The scattered waves behave as a decaying cylindrical wave at distant points. Numrical computations for the amplitude of the scattered waves have been made versus the wave number. The amplitude falls off rapidly as the wave number increases very slowly.     

On self-intersections of immersed surfaces

A daisy graph is a union of immersed circles in 3-space which intersect only at the triple points. It is shown that a daisy graph can always be realized as the self-intersection set of an immersed closed surface in 3-space and the surface may be chosen to be orientable if and only if the daisy graph has an even number of edges on each immersed circle.

     

Numerical analyses of the boundary effect of radial basis functions in 3D surface reconstruction

Surface reconstruction is very important for surface characterization and graph processing. Radial basis function has now become a popular method to reconstruct 3D surfaces from scattered data. However, it is relatively inaccurate at the boundary region. To solve this problem, a circle of new centres are added outside the domain of interest. The factors that influence the boundary behaviour are analyzed quantitatively via numerical experiments. It is demonstrated that if the new centres are properly located, the boundary problem can be effectively overcome whilst not reducing the accuracy at the interior area. A modified Graham scan technique is introduced to obtain the boundary points from a scattered point set. These boundary points are extended outside with an appropriate distance, and then uniformized to form the new auxiliary centres.      

Least Squares Solution of Bivariate Surface Fitting Problems Using Tensor Product Splines

The paper treats bivariate surface fitting problems, where the data points lie on lines parallel to one of the axes. The associated bivariate collocation matrix is investigated as a block Kronecker product of univariate collocation matrices. Based on various properties of this block Kronecker product, such scattered data are characterized where the associated interpolation problem using tensor product splines admits a unique solution.     

Global and local optimization using radial basis function response surface models

The focus of this paper is the optimization of complex multi-parameter systems. We consider systems in which the objective function is not known explicitly, and can only be evaluated through computationally intensive numerical simulation or through costly physical experiments. The objective function may also contain many local extrema which may be of interest. Given objective function values at a scattered set of parameter values, we develop a response surface model that can dramatically reduce the required computation time for parameter optimization runs. The response surface model is developed using radial basis functions, producing a model whose objective function values match those of the original system at all sampled data points. Interpolation to any other point is easily accomplished and generates a model which represents the system over the entire parameter space. This paper presents the details of the use of radial basis functions to transform scattered data points, obtained from a complex continuum mechanics simulation of explosive materials, into a response surface model of a function over the given parameter space. Response surface methodology and radial basis functions are discussed in general and are applied to a global optimization problem for an explosive oil well penetrator.     

A general radial quasi-interpolation operator on the sphere

Geodetic and meteorological data, collected via satellites for example, are genuinely scattered and not confined to any special set of points. In order to learn geodetic and meteorological rules, one needs to use these scattered data only to construct an approximant or interpolant. In this paper, we introduce a general distance generated from the scattered data, and, using this, construct a general radial quasi-interpolation operator on the sphere, and we study the convergence rate of this operator. We also show some potential applications of the results obtained here in satellite geodesy.     

Coverage problems and visibility regions on topographic surfaces

The viewshed of a point on an irregular topographic surface is defined as the area visible from the point. The area visible from a set of points is the union of their viewsheds. We consider the problems of locating the minimum number of viewpoints to see the entire surface, and of locating a fixed number of viewpoints to maximize the area visible, and possible extensions. We discuss alternative methods of representing the surface in digital form, and adopt a TIN or triangulated irregular network as the most suitable data structure. The space is tesselated into a network of irregular triangles whose vertices have known elevations and whose edges join vertices which are Thiessen neighbours, and the surface is represented in each one by a plane. Visibility is approximated as a property of each triangle: a triangle is defined as visible from a point if all of its edges are fully visible. We present algorithms for determination of visibility, and thus reduce the problems to variants of the location set covering and maximal set covering problems. We examine the performance of a variety of heuristics.     

基于特征曲线和曲面匹配的弹痕自动比对方案

提出了消除测量误差的两套方案:基于特征曲线提取的方案和基于曲面匹配的方案.建立了中心重合法、近似法矢重合法与多点预定位法相结合的曲面匹配模型;讨论并给出了用于弹痕比对的六个差异度衡量指标;建立了弹痕及弹头相似度模型;给出了方案的有效性评价体系;最后,对一组实际的弹痕数据,进行有效性验证,取得了较高的正确率.