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样条曲面多步拟合算法进行了实验验证。     

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.