Ordering and parameterizing scattered 3D data for B-spline surfaceapproximation

Surface representation is intrinsic to many applications in medical imaging, computer vision, and computer graphics. We present a method that is based on surface modeling by B-spline. The B-spline constructs a smooth surface that best fits a set of scattered unordered 3D range data points obtained from either a structured light system (a range finder), or from point coordinates on the external contours of a set of surface sections, as for example in histological coronal brain sections. B-spline stands as of one the most efficient surface representations. It possesses many properties such as boundedness, continuity, local shape controllability, and invariance to affine transformations that makes it very suitable and attractive for surface representation. Despite its attractive properties, however, B-spline has not been widely applied for representing a 3D scattered nonordered data set. This may be due to the problem in finding an ordering and a choice for the topological parameters of the B-spline that lead to a physically meaningful surface parameterization based on the scattered data set. The parameters needed for the B-spline surface construction, as well as finding the ordering of the data points, are calculated based on the geodesics of the surface extended Gaussian map. The set of control points is analytically calculated by solving a minimum mean square error problem for best surface fitting. For a noise immune modeling, we elect to use an approximating rather than an interpolating B-spline. We also examine ways of making the B-spline fitting technique robust to local deformation and noise     

3D scattered data interpolation and approximation with multilevel compactly supported RBFs

In this paper, we propose a hierarchical approach to 3D scattered data interpolation and approximation with compactly supported radial basis functions. Our numerical experiments suggest that the approach integrates the best aspects of scattered data fitting with locally and globally supported basis functions. Employing locally supported functions leads to an efficient computational procedure, while a coarse-to-fine hierarchy makes our method insensitive to the density of scattered data and allows us to restore large parts of missed data. Given a point cloud distributed over a surface, we first use spatial down sampling to construct a coarse-to-fine hierarchy of point sets. Then we interpolate (approximate) the sets starting from the coarsest level. We interpolate (approximate) a point set of the hierarchy, as an offsetting of the interpolating function computed at the previous level. The resulting fitting procedure is fast, memory efficient, and easy to implement.     

Duplex fitting of zero-level and offset surfaces

Offset surfaces play an important role in various CAD/CAM applications. Given a set of oriented points, we propose a hierarchical method in this paper to fit both the zero-level surface and its offset surface with a single implicit function. The implicit function is formed by compactly supported radial basis functions (CSRBFs). Different from other existing methods in literature, our approach reconstructs an implicit function which interpolates or approximates both the zero-level surface and the offset surface of a given point set, simultaneously. Employing locally supported functions leads to an efficient computational procedure, while the coarse-to-fine hierarchy makes our approach insensitive to the density of scattered data and allows us to reconstruct large parts of missing data. The performance of our method is demonstrated by a number of examples and the application of adaptive slicing hollowed models in rapid prototyping.     

三维散乱数据三角形网格逼近的一种算法

以激光－机器视觉测量方式得到的曲面数据云为基础，对曲面密集３维散乱数据用线性逼近进行三角形网格拟合。根据激光测量方式和３维点群分布的特点，应用八叉树空间分割原理，对密集散乱点群采用空间分区存储，建立八叉树拓扑关系，加快几何建模速度。     

RMAP: a rectangular cuboid approximation framework for 3D environment mapping

This paper presents a rectangular cuboid approximation framework (RMAP) for 3D mapping. The goal of RMAP is to provide computational and memory efficient environment representations for 3D robotic mapping using axis aligned rectangular cuboids (RC). This paper focuses on two aspects of the RMAP framework: (i) An occupancy grid approach and (ii) A RC approximation of 3D environments based on point cloud density. The RMAP occupancy grid is based on the Rtree data structure which is composed of a hierarchy of RC. The proposed approach is capable of generating probabilistic 3D representations with multiresolution capabilities. It reduces the memory complexity in large scale 3D occupancy grids by avoiding explicit modelling of free space. In contrast to point cloud and fixed resolution cell representations based on beam end point observations, an approximation approach using point cloud density is presented. The proposed approach generates variable sized RC approximations that are memory efficient for axis aligned surfaces. Evaluation of the RMAP occupancy grid and approximation approach based on computational and memory complexity on different datasets shows the effectiveness of this framework for 3D mapping.     

基于四阶偏微分方程的光滑曲面重构方法

常用的基于散点的曲面重构方法如克里金插值法、样条曲面拟合法等存在计算量大、重构曲面不光滑或无法插值已知散点等问题。为此,提出一种基于四阶偏微分方程的曲面重构方法。该方法首先选择一个四阶偏微分方程,并对其构建差分格式,进而分析该差分格式的稳定性和收敛性。在稳定性和收敛性条件下,采用演化的思想,通过有限差分法迭代求解偏微分方程的数值解,并将其稳态解作为原始曲面的逼近。以地质勘探中实际测井数据为例,采用偏微分方程曲面造型方法重构地质曲面,结果表明,该方法计算简便,构造的曲面具有自然光顺性且可以插值于已知散点。     

散乱数据点集曲线重构的最短路逼近算法

给出了散乱数据点集曲线重构的最短路逼近算法．算法根据数据点的分布构造带权连通图，通过求解带权连通图的最短路径，将散乱数据点集的曲线重构问题转化为有序数据点集的曲线重构问题．算法可以对单连通、多连通和封闭的数据点集进行重构．重构曲线较好地保持了数据点集的形状和走向，尤其是带尖点的数据点集的形状特征．最后给出不同拓扑结构的数据点集的重构曲线实例．     

Surface Reconstruction from Unorganized Point Data with Quadrics

We present a reverse engineering method for constructing a surface approximation scheme whose input is a set of unorganized noisy points in space and whose output is a set of quadric patches. The local surface properties, necessary for the subsequent segmentation, are estimated directly from the data using a simple and efficient data structure—the neighborhood graph. Our segmentation scheme, based on principal curvatures, constructs initial point subsets, which may be enlarged or further subdivided based on associated approximation error estimates obtained through approximation of the initial segments by quadric surfaces. Our method is highly efficient and produces a high‐quality piecewise quadric surface approximation of engineering objects, which we demonstrate for several simple and complex example data sets.     

密集散乱测量数据点的B样条曲面拟合研究

回顾了密集散乱数量数据点面拟合研究发展情况,针对异形边界自由曲面密集散乱测量数据点,提出一种B样条曲面多步拟合算法,其中涉及边界插值B样条曲面生成、Hardy′s双二次局部插值、规则网格数据点B样条曲面最小二乘拟合等关键技术,通过一个工程实例,对文中提出的B样条曲面多步拟合算法进行了实验验证。     

Efficient selection, storage, and retrieval of irregularly distributed elevation data

The advantages and disadvantages of various digital terrain models are discussed briefly and a new model for triangulating a set of nonuniformly distributed three-dimensional surface observations is described. An algorithm for hierarchical subdivision of a set of data points into nested triangles is proposed. The algorithm selects a subset of the data points which reduce the maximum error between a piecewise linear approximation of the surface using only the selected points and the elevations of the points not selected. The data structure used is such that for any given degree of approximation (in the maximum-error sense) only the necessary points need to be stored. Furthermore, an efficient method is available to approximate the elevation of the surface at any point not included in the original data. The performance of the algorithm is demonstrated experimentally.     

The discrete collocation method for Fredholm–Hammerstein integral equations based on moving least squares method

The purpose of this paper is to investigate the discrete collocation method based on moving least squares (MLS) approximation for Fredholm–Hammerstein integral equations. The scheme utilizes the shape functions of the MLS approximation constructed on scattered points as a basis in the discrete collocation method. The proposed method is meshless, since it does not require any background mesh or domain elements. Error analysis of this method is also investigated. Some numerical examples are provided to illustrate the accuracy and computational efficiency of the method.     

The computation of visible-surface representations

A computational theory of visible-surface representations is developed. The visible-surface reconstruction process that computes these quantitative representations unifies formal solutions to the key problems of: (1) integrating multiscale constraints on surface depth and orientation from multiple-visual sources; (2) interpolating dense, piecewise-smooth surfaces from these constraints; (3) detecting surface depth and orientation discontinuities to apply boundary conditions on interpolation; and (4) structuring large-scale, distributed-surface representations to achieve computational efficiency. Visible-surface reconstruction is an inverse problem. A well-posed variational formulation results from the use of a controlled-continuity surface model. Discontinuity detection amounts to the identification of this generic model's distributed parameters from the data. Finite-element shape primitives yield a local discretization of the variational principle. The result is an efficient algorithm for visible-surface reconstruction     

基于SOM的散乱数据点集的B样条曲面重建

利用自组织映射神经网络(SOM)技术对散乱数据点集进行B样条曲面重建时,往往存在网络学习时间过长和学习效果不理想等问题。提出了一种新的神经元初始化方法和分块学习算法,该算法首先运用主元素分析方法(PCA)对散乱数据进行分块,将拓扑结构为四边形的输出层神经元初始化在每块散乱数据的最小二乘平面上进行网络学习和训练,将分块学习得到的各网格曲面拼接成一个整体;然后对该整体网格曲面的边界和内部单独学习,得到一张逼近待重建曲面的双线性B样条曲面;最后对该B样条曲面误差进行了修正。实例证明,该算法可以明显地减少SOM网络学习时间,并改善网络学习效果。     

Fitting Triangular B-Splines to Functional Scattered Data

Scattered data is, by definition, irregularly spaced. Uniform surface schemes are not well adapted to the locally varying nature of such data. Conversely, Triangular B-Spline surfaces 2 are more flexible in that they can be built over arbitrary triangulations and thus can be adapted to the scattered data. This paper discusses the use of DMS spline surfaces for approximation of scattered data. A method is provided for automatically triangulating the domain containing the points and generating basis functions over this triangulation. A surface approximating the data is then found by a combination of least squares and bending energy minimization. This combination serves both to generate a smooth surface and to accommodate for gaps in the data. Examples are presented which demonstrate the eftectiveness of the technique for mathematical, geographical and other data sets.     

基于能量最小化的网格优化算法

对网格优化的方法进行研究,提出一种基于能量最小化的网格优化算法.给定一定数量的三维散乱点数据和一个初始三角网格,使用能量最小化算法对网格顶点位置进行优化,使网格顶点更好地逼近三维散乱点数据;网格也更加逼近实际曲面.实验结果表明,使用该算法能够获得形状良好的网格.     

Simplification of three-dimensional density maps

We consider scientific data sets that describe density functions over three-dimensional geometric domains. Such data sets are often large and coarsened representations are needed for visualization and analysis. Assuming a tetrahedral mesh representation, we construct such representations with a simplification algorithm that combines three goals: the approximation of the function, the preservation of the mesh topology, and the improvement of the mesh quality. The third goal is achieved with a novel extension of the well-known quadric error metric. We perform a number of computational experiments to understand the effect of mesh quality improvement on the density map approximation. In addition, we study the effect of geometric simplification on the topological features of the function by monitoring its critical points.     

Adaptive detection and approximation of unknown surface discontinuities from scattered data

We consider a method for the detection and approximation of fault lines of a surface, which is known only on a finite number of scattered data. In particular, we present an adaptive approach to detect surface discontinuities, which allows us to give an (accurate) approximation of the detected faults. First, to locate all the fault points, i.e. the nodes on or close to fault lines, we consider a procedure based on a local interpolation scheme involving a cardinal radial basis formula. Second, we find further sets of points generally closer to the faults than the fault points. Finally, after applying a nearest-neighbour searching procedure and a powerful refinement technique, we outline some different approximation methods. Numerical results highlight the efficiency of our approach.     

Multi-Level Partition of Unity Algebraic Point Set Surfaces

We present a multi-level partition of unity algebraic set surfaces (MPU-APSS) for surface reconstruction which can be represented by either a projection or in an implicit form. An algebraic point set surface (APSS) defines a smooth surface from a set of unorganized points using local moving least-squares (MLS) fitting of algebraic spheres. However, due to the local nature, APSS does not work well for geometry editing and modeling. Instead, our method builds an implicit approximation function for the scattered point set based on the partition of unity approach. By using an octree subdivision strategy, we first adaptively construct local algebraic spheres for the point set, and then apply weighting functions to blend together these local shape functions. Finally, we compute an error-controlled approximation of the signed distance function from the surface. In addition, we present an efficient projection operator which makes our representation suitable for point set filtering and dynamic point resampling. We demonstrate the effectiveness of our unified approach for both surface reconstruction and geometry modeling such as surface completion.     

基于Kohonen神经网络的B样条曲面重构

探讨了三维散乱数据点的自由曲面自组织重构方法。建立了基于自组织特征映射神经网络的矩形网格重构模型及其训练算法。所建模型利用神经元对曲面散乱数据点的学习和训练来模拟曲面上点与点之间的内在关系,节点连接权向量集作为对散乱数据点集的工程近似化并重构曲面样本点的内在拓扑关系。通过该方法不仅能够对无规则散乱数据点进行逼近,并且通过该方法得到的曲面也可以作为后继曲面重构的初始曲面。仿真实验表明,所建神经网络模型可实现三维密集无规则数据点的曲面自组织重构集自压缩于一体。