A topological approach for surface reconstruction from sample points

Most algorithms for surface reconstruction from sample points rely on computationally demanding operations to derive the reconstruction. In this paper we introduce an innovative approach for generating 3D piecewise linear approximations from sample points that relies strongly on topological information, thus reducing the computational cost and numerical instabilities typically associated with geometric computations. Discrete Morse theory provides the basis for a topological framework that supports a robust reconstruction algorithm capable of handling multiple components and has low computational cost. We describe the proposed approach and introduce the reconstruction algorithm, called TSR – topological surface reconstructor. Some reconstruction results are presented and the performance of TSR is compared with that of other reconstruction approaches for some standard point sets.     

Detection and classification of topological evolution for linear metamorphosis

The advantage of functional methods for shape metamorphosis is the automatic generation of intermediate shapes possible between the key shapes of different topology types. However, functional methods have a serious problem: shape interpolation is applied without topological information and thereby the time values of topological changes are not known. Thus, it is difficult to identify the time intervals for key frames of shape metamorphosis animation that faithfully visualize the topological evolution. Moreover, information on the types of topological changes is missing. To overcome the problem, we apply topological analysis to functional linear shape metamorphosis and classify the type of topological evolution by using a Hessian matrix. Our method is based on Morse theory and analyzes how the critical points appear. We classify the detected critical points into maximum point, minimum point, and saddle point types. Using the types of critical points, we can define the topological information for shape metamorphosis. We illustrate these methods using shape metamorphosis in 2D and 3D spaces.     

Shape description by medial surface construction

The medial surface is a skeletal abstraction of a solid that provides useful shape information, which compliments existing model representation schemes. The medial surface and its associated topological entities are defined, and an algorithm for computing the medial surface of a large class of B-rep solids is then presented. The algorithm is based on the domain Delaunay triangulation of a relatively sparse distribution of points, which are generated on the boundary of the object. This strategy is adaptive in that the boundary point set is refined to guarantee a correct topological representation of the medial surface     

Algorithms for Extracting Correct Critical Points and Constructing Topological Graphs from Discrete Geographical Elevation Data

Researchers in the fields of computer graphics and geographical information systems (GISs) have extensively studied the methods of extracting terrain features such as peaks, pits, passes, ridges, and ravines from discrete elevation data. The existing techniques, however, do not guarantee the topological integrity of the extracted features because of their heuristic operations, which results in spurious features. Furthermore, there have been no algorithms for constructing topological graphs such as the surface network and the Reeb graph from the extracted peaks, pits, and passes. This paper presents new algorithms for extracting features and constructing the topological graphs using the features. Our algorithms enable us to extract correct terrain features; i.e., our method extracts the critical points that satisfy the Euler formula, which represents the topological invariant of smooth surfaces. This paper also provides an algorithm that converts the surface network to the Reeb graph for representing contour changes with respect to the height. The discrete elevation data used in this paper is a set of sample points on a terrain surface. Examples are presented to show that the algorithms also appeal to our visual cognition.     

Uniformization and Density Adaptation for Point Cloud Data Via Graph Laplacian

Point cloud data is one of the most common types of input for geometric processing applications. In this paper, we study the point cloud density adaptation problem that underlies many pre‐processing tasks of points data. Specifically, given a (sparse) set of points Q sampling an unknown surface and a target density function, the goal is to adapt Q to match the target distribution. We propose a simple and robust framework that is effective at achieving both local uniformity and precise global density distribution control. Our approach relies on the Gaussian‐weighted graph Laplacian and works purely in the points setting. While it is well known that graph Laplacian is related to mean‐curvature flow and thus has denoising ability, our algorithm uses certain information encoded in the graph Laplacian that is orthogonal to the mean‐curvature flow. Furthermore, by leveraging the natural scale parameter contained in the Gaussian kernel and combining it with a simulated annealing idea, our algorithm moves points in a multi‐scale manner. The resulting algorithm relies much less on the input points to have a good initial distribution (neither uniform nor close to the target density distribution) than many previous refinement‐based methods. We demonstrate the simplicity and effectiveness of our algorithm with point clouds sampled from different underlying surfaces with various geometric and topological properties.     

A new learning algorithm with reference-following variables

A learning algorithm is presented for the learning of neural networks, in which the learning trajectory is convergence without any over-learning by changing of topological construction of the algorithm near any local minimum points of learning error. Became the topological construction is not convergent for some functions by usual BP method near some local minimum points, there is an over-learning phenomenon. To avoid the over-learning phenomenon, reference-foUowing variables are used to change the topological construction of this algorithm. The theoretical analysis and the simulation results indicate that the proposed method is simple and useful.     

Finding and classifying critical points of 2D vector fields: a cell-oriented approach using group theory

We present a novel approach to finding critical points in cell-wise barycentrically or bilinearly interpolated vector fields on surfaces. The Poincaré index of the critical points is determined by investigating the qualitative behavior of 0-level sets of the interpolants of the vector field components in parameter space using precomputed combinatorial results, thus avoiding the computation of the Jacobian of the vector field at the critical points in order to determine its index. The locations of the critical points within a cell are determined analytically to achieve accurate results. This approach leads to a correct treatment of cases with two first-order critical points or one second-order critical point of bilinearly interpolated vector fields within one cell, which would be missed by examining the linearized field only. We show that for the considered interpolation schemes determining the index of a critical point can be seen as a coloring problem of cell edges. A complete classification of all possible colorings in terms of the types and number of critical points yielded by each coloring is given using computational group theory. We present an efficient algorithm that makes use of these precomputed classifications in order to find and classify critical points in a cell-by-cell fashion. Issues of numerical stability, construction of the topological skeleton, topological simplification, and the statistics of the different types of critical points are also discussed.     

组合曲面参数线五坐标加工刀具轨迹的计算

提出了组合曲面间拓扑关系的建立方法．通过对曲面相邻边界及相邻角点拓扑信息查询，完成刀具路径的合理组织；针对目前在给定加工精度时确定参数增量算法存在的不足，提出基于等参数线的走刀步长追踪法，并对曲率半径趋于无穷大的情况及直纹面加工的情况进行单独处理，保证了算法的稳定性和有效性．在此基础上，系统地阐述了组合曲面加工中刀触点、刀位点的计算以及刀具轨迹的合理化组织。     

Uncertain 2D Vector Field Topology

We introduce an approach to visualize stationary 2D vector fields with global uncertainty obtained by considering the transport of local uncertainty in the flow. For this, we extend the concept of vector field topology to uncertain vector fields by considering the vector field as a density distribution function. By generalizing the concepts of stream lines and critical points we obtain a number of density fields representing an uncertain topological segmentation. Their visualization as height surfaces gives insight into both the flow behavior and its uncertainty. We present a Monte Carlo approach where we integrate probabilistic particle paths, which lead to the segmentation of topological features. Moreover, we extend our algorithms to detect saddle points and present efficient implementations. Finally, we apply our technique to a number of real and synthetic test data sets.     

Localized Cocone surface reconstruction

We introduce a surface reconstruction algorithm suitable for large point sets. The algorithm is an octree-based version of the Cocone reconstruction algorithm [4], allowing independent processing of small subsets of the total input point set. When the points are sufficiently sampled from a smooth surface, the global guarantee of topological correctness of the original algorithm is preserved, together with the geometric accuracy guarantees.     

Near‐Isometric Level Set Tracking

Implicit representations of geometry have found applications in shape modeling, simulation, and other graphics pipelines. These representations, however, do not provide information about the paths of individual points as shapes move and undergo deformation. For this reason, we reconsider the problem of tracking points on level set surfaces, with the goal of designing an algorithm that — unlike previous work — can recover rotational motion and nearly isometric deformation. We track points on level sets of a time‐varying function using approximate Killing vector fields (AKVFs), the velocity fields of near‐isometric motions. To this end, we provide suitable theoretical and discrete constructions for computing AKVFs in a narrow band surrounding an animated level set surface. Furthermore, we propose time integrators well‐suited to integrating AKVFs in time to track points. We demonstrate the theoretical and practical advantages of our proposed algorithms on synthetic and practical tasks.     

Efficient computation of Morse-Smale complexes for three-dimensional scalar functions

The Morse-Smale complex is an efficient representation of the gradient behavior of a scalar function, and critical points paired by the complex identify topological features and their importance. We present an algorithm that constructs the Morse-Smale complex in a series of sweeps through the data, identifying various components of the complex in a consistent manner. All components of the complex, both geometric and topological, are computed, providing a complete decomposition of the domain. Efficiency is maintained by representing the geometry of the complex in terms of point sets.     

Topology correction of segmented medical images using a fast marching algorithm

We present here a new method for correcting the topology of objects segmented from medical images. Whereas previous techniques alter a surface obtained from a binary segmentation of the object, our technique can be applied directly to the image intensities of a probabilistic or fuzzy segmentation, thereby propagating the topology for all isosurfaces of the object. From an analysis of topological changes and critical points in implicit surfaces, we derive a topology propagation algorithm that enforces any desired topology using a fast marching technique. The method has been applied successfully to the correction of the cortical gray matter/white matter interface in segmented brain images and is publicly released as a software plug-in for the MIPAV package.     

面向非均匀采样点集的3维表面重建算法

针对非均匀采样点集,提出一种改进的3维表面重建方法。该方法将整个点集进行空间划分,缩小近邻点的搜索范围,减少搜索时间;在确定近邻点时,先计算几何近邻点,然后通过求方向性点并构造最小生成树的方法,确定拓扑近邻点;最后通过将拓扑近邻点投影到局部切平面上,利用约束条件对投影点进行三角剖分,并将剖分得到的顶点连接关系映射到3维空间中,实现3维表面重建。实验结果表明,改进后的算法运行效率高、重建效果好、广泛适用于非均匀采样点集的表面重建。     

无线传感器网络拓扑边界辨识算法

在无线传感器网络（ WSNs）中,网络的拓扑特征对于设计网络应用和网络优化具有十分重要的意义。在拓扑特征中又以拓扑边界最为基础,不仅边界本身具有直接的利用价值,而且 WSNs瓶颈辨识、WSNs近凸分块等算法都需要以获取边界信息为前提。提出了一种不依赖地理信息的分布式算法,通过借鉴自然现象热传导的规律和等温线只在边界中断的固有特点,在WSNs这一人工系统中模拟热传导过程,最终成功地辨识了WSNs的边界。     

基于B-Rep实体模型的IGES转换为STL

提出一种将IGES文件格式转换成STL文件格式的算法.根据IGES文件内容重构几何实体信息及其拓扑关系;将几何实体的三维曲面贴合为二维平面,并将曲面上的轮廓边界转换到平面上,在二维空间中根据封闭轮廓边界裁剪曲面;根据曲面上保留的特征点及轮廓边界上的顶点信息对面进行符合STL模型一致性规则的三角剖分,生成合法的STL文件.该算法的核心是保证面与面接合处的三角化的正确性.最后介绍了该算法的转换实例.     

2D‐D Lifting for Shape Reconstruction

We present an algorithm for shape reconstruction from incomplete 3D scans by fusing together two acquisition modes: 2D photographs and 3D scans. The two modes exhibit complementary characteristics: scans have depth information, but are often sparse and incomplete; photographs, on the other hand, are dense and have high resolution, but lack important depth information. In this work we fuse the two modes, taking advantage of their complementary information, to enhance 3D shape reconstruction from an incomplete scan with a 2D photograph. We compute geometrical and topological shape properties in 2D photographs and use them to reconstruct a shape from an incomplete 3D scan in a principled manner. Our key observation is that shape properties such as boundaries, smooth patches and local connectivity, can be inferred with high confidence from 2D photographs. Thus, we register the 3D scan with the 2D photograph and use scanned points as 3D depth cues for lifting 2D shape structures into 3D. Our contribution is an algorithm which significantly regularizes and enhances the problem of 3D reconstruction from partial scans by lifting 2D shape structures into 3D. We evaluate our algorithm on various shapes which are loosely scanned and photographed from different views, and compare them with state‐of‐the‐art reconstruction methods.     

关键点图对比图像分类方法

深度学习是目前图像分类的主流方法之一,其重视感受野内的局部信息,却忽略了类别的先验拓扑结构信息。本文提出了一种新的图像分类方法,即Key-D-Graph,这是基于关键点的图对比网络方法,在识别图像类别时可以显式地考虑拓扑先验结构。具体地,图像分类需要2个步骤,第一步是基于关键点构建图像的图表达,即采用深度学习方法识别图像中目标类别的可能关键点,并采用关键点坐标生成图像的拓扑图表达;第二步基于关键点的图像图表达建立图对比网络,以估计待识别图与目标类别之间的结构差异,实现类别判断,该步骤利用了物体的拓扑先验结构信息,实现了基于图像全局结构信息的物体识别。特别的,Key-D-Graph的中间输出结果为类别关键点,具有语义可解释性,便于在实际应用中对算法逐步分析调试。实验结果表明,提出的方法可在效率和精度上超过主流方法,且通过消融实验分析验证了拓扑结构在分类中的作用机制和有效性。