Search

We introduce here the concept of discrete level sets (DLS) that can be constructed on a voxelized surface with the assurance of certain topological properties. This eventually aids in construction of discrete geodesic Reeb graph (DGRG) on a voxelized object, for topological analysis. Under various transformations like rotation and topology-constrained anisotropic deformation, a DGRG remains invariant to typical topological features like loops or cycles, which eventually helps in identifying ‘handles’ in the underlying object. Experiments on different datasets show promising results on the practical usefulness of DLS and DGRG towards extraction of high-level topological features of arbitrary voxel sets.

Segmentation of the articulated components of digital objects by a fast and efficient algorithm is presented in this paper. Given a 3D object in the form of a triangulated mesh, the approach involves representation of the mesh in a topological space and relating quotient spaces, containing the topologically invariant sections of the object, to weighted Reeb graphs along each of yz-, zx-, and xy-planes. It is followed by segmentation of the Reeb graphs where the concept of exponential averaging for dynamic thresholding ensures natural segmentation with a relatively high degree of accuracy. The segmented quotient spaces corresponding to the three Reeb graphs are subsequently related to each other and transformed topologically to report the segmented object in an appropriate topological space. The segmentation is carried out in a framework of 3D grid so as to exploit the topological relation between the triangulated object and its tight isothetic cover, and hence involves efficient computation and storage. The accuracy of segmentation at different grid resolutions, its robustness w.r.t. rotation, and pose-invariance for a reasonable range of postures are demonstrated by experimental results on a variety of objects.

Recently, plenty of deep learning methods have been proposed to handle point clouds. Almost all of them input the entire point cloud and ignore the information redundancy lying in point clouds. This paper addresses this problem by extracting the Reeb graph from point clouds, which is a much more informative and compact representation of point clouds, and then filter the graph with deep graph convolution. To be able to classify or segment point clouds well, we propose (1) Graph Normalization to transform various graphs into a canonical graph space; (2) Normalized Similarity Distance to better identify the graph structure;(3) Reeb Graph Guided Node Pooling in order to aggregate high-level features from kNN graphs. Besides, our method naturally fits into the problem of classifying point clouds with unknown orientations. In the results, we show that our method gives a competitive performance to the state-of-the-art methods and outperforms previous methods by a large margin on handling point clouds with unknown orientations.

We propose a new method to detect water trap regions in voids of oriented polygonal models that approximate the geometry of mechanical parts. Since water traps decrease cleaning and draining efficiency, accurately predicting such regions allows re-orienting parts to reduce manufacturing time and cost. We construct a directed graph that captures the flow of water in voids of a 3D input model, based on a fast orientation-dependent volume segmentation approach. We can quickly find the water trap regions by analyzing the directed graph. Since we take a purely geometric approach to solve this problem without employing any physical simulation, even if the geometry of the voids is complicated, we can calculate water traps quickly.

Reeb graphs are topological graphs originating in Morse theory, which represent the topological structure of a manifold by contracting the level set components of a scalar-valued function defined on it. The generalization to several functions leads to Reeb spaces, which are thus able to capture more features of an object. We introduce the layered Reeb graph as a discrete representation for Reeb spaces of 3D solids (embedded three-dimensional manifolds with boundary) with respect to two scalar-valued functions. After that we present an efficient algorithm for computing the layered Reeb graph, which uses only a boundary representation of the underlying three-dimensional manifold. This leads to substantial computational advantages if the manifold is given in a boundary representation, since no volumetric representation has to be constructed. However, this algorithm is applicable only if the defining functions satisfy certain conditions. Graphical abstractDisplay Omitted HighlightsWe consider the Reeb space of a 3D solid with respect to two scalar functions.We introduce the layered Reeb graph as an abstract representation of the Reeb space.As an input, we use triangulated 3D solids in boundary representation.We present an efficient, boundary based construction algorithm.We identify restrictions on the functions that make the construction applicable.

A well known result in the analysis of finite metric spaces due to Gromov says that given any $(X,d_X)$ there exists a \emph{tree metric} $t_X$ on $X$ such that $\|d_X-t_X\|_\infty$ is bounded above by twice $\mathrm{hyp}(X)\cdot \log(2\,|X|)$. Here $\mathrm{hyp}(X)$ is the \emph{hyperbolicity} of $X$, a quantity that measures the \emph{treeness} of $4$-tuples of points in $X$. This bound is known to be asymptotically tight. We improve this bound by restricting ourselves to metric spaces arising from filtered posets. By doing so we are able to replace the cardinality appearing in Gromov's bound by a certain poset theoretic invariant (the maximum length of fences in the poset) which can be much smaller thus significantly improving the approximation bound. The setting of metric spaces arising from posets is rich: For example, save for the possible addition of new vertices, every finite metric graph can be induced from a filtered poset. Since every finite metric space can be isometrically embedded into a finite metric graph, our ideas are applicable to finite metric spaces as well. At the core of our results lies the adaptation of the Reeb graph and Reeb tree constructions and the concept of hyperbolicity to the setting of posets, which we use to formulate and prove a tree approximation result for any filtered poset., Comment: 18 pages, 2 figures

Given a virtual garment model on a reference human model, we propose an automated 3D garment fitting system that fits the garment model to a target human model. The proposed method can transfer garment models between human models without any user guidance even when the reference and target human models have different poses. Our goal is not to resize or deform the original garment model according to the target human model but to yield realistic fitting results of the given garment on the target human models. Using pose-independent segmentation and cloth simulation, we achieve realistic and automatic fitting results in reasonable running time. Our method can replace the time-consuming manual fitting process that is necessary for many applications that use virtual garments, such as games, animations, CAD tools and online clothing stores.

Liquid–liquid extraction is a typical multi-fluid problem in chemical engineering where two types of immiscible fluids are mixed together. Mixing of two-phase fluids results in a time-varying fluid density distribution, quantitatively indicating the presence of liquid phases. For engineers who design extraction devices, it is crucial to understand the density distribution of each fluid, particularly flow regions that have a high concentration of the dispersed phase. The propagation of regions of high density can be studied by examining the topology of isosurfaces of the density data. We present a topology-based approach to track the splitting and merging events of these regions using the Reeb graphs. Time is used as the third dimension in addition to two-dimensional (2D) point-based simulation data. Due to low time resolution of the input data set, a physics-based interpolation scheme is required in order to improve the accuracy of the proposed topology tracking method. The model used for interpolation produces a smooth time-dependent density field by applying Lagrangian-based advection to the given simulated point cloud data, conforming to the physical laws of flow evolution. Using the Reeb graph, the spatial and temporal locations of bifurcation and merging events can be readily identified supporting in-depth analysis of the extraction process.

In dip-coating processes a three-dimensional object, e.g. an entire car body, is dipped into a liquid bath. In order to simulate such processes, the space surrounding the object is decomposed into the so-called flow volumes, for which each intersection with a horizontal plane is connected. At any time the liquid's surface then has a unique level within such a flow volume, which greatly simplifies the simulation of the liquid. The decomposition into flow volumes corresponds to the Reeb graph of the object's exterior (considered as 3-manifold with boundary) with respect to the height function. This article presents an algorithm which computes this decomposition for an object represented as oriented triangular boundary mesh. First critical vertices of the surface are identified, which include the upper and lower ends of flow volumes. Using local information about horizontal intersection planes near the critical points, a sweep plane algorithm then constructs the volume decomposition in a second step. It is shown that the method can deal with realistic data.

This paper presents a method of shape chartification suitable for surface approximation. The innovation of this approach lies on the definition of an iterative refinement of the shape into a set of patches that are automatically tiled and used to approximate the original shape up to a prescribed error. The coding of the patches is supported by the Reeb graph and contains the rules to properly tile, stitch them, and reconstruct the original shape while preserving its topology, using a technique which is also exploited for reconstructing an object from non-planar contours. The method is geometry-aware by definition, as the nodes of the Reeb graph are representative of the main shape features, which belong to the approximated shape already at the initial iteration steps. The points of the reconstructed shape belong to the original surface, their total number is highly reduced, and the original connectivity is replaced by a set of patches that preserves the global topology of the input shape.

This paper proposes the use of the surface-based Laplace-Beltrami and the volumetric Laplace eigenvalues and eigenfunctions as shape descriptors for the comparison and analysis of shapes. These spectral measures are isometry invariant and therefore allow for shape comparisons with minimal shape pre-processing. In particular, no registration, mapping, or remeshing is necessary. The discriminatory power of the 2D surface and 3D solid methods is demonstrated on a population of female caudate nuclei (a subcortical gray matter structure of the brain, involved in memory function, emotion processing, and learning) of normal control subjects and of subjects with schizotypal personality disorder. The behavior and properties of the Laplace-Beltrami eigenvalues and eigenfunctions are discussed extensively for both the Dirichlet and Neumann boundary condition showing advantages of the Neumann vs. the Dirichlet spectra in 3D. Furthermore, topological analyses employing the Morse-Smale complex (on the surfaces) and the Reeb graph (in the solids) are performed on selected eigenfunctions, yielding shape descriptors, that are capable of localizing geometric properties and detecting shape differences by indirectly registering topological features such as critical points, level sets and integral lines of the gradient field across subjects. The use of these topological features of the Laplace-Beltrami eigenfunctions in 2D and 3D for statistical shape analysis is novel.

Decomposition of complex 3D objects into simpler sub-parts is a challenging research subject with relevant outcomes for several application contexts. In this paper, an approach is proposed for decomposition of 3D objects based on Reeb graphs. The approach is motivated by perceptual principles and supports identification of salient object protrusions. Experimental results are presented to demonstrate the effectiveness of the proposed approach with respect to different solutions appeared in the literature, and with reference to ground-truth data obtained by manual decomposition of 3D objects.

This paper presents a method to extract skeletons using examples. Our method is based on the observation that many deformations in real-world applications are isometric or near isometric. By taking advantage of the intrinsic property of harmonic 1-form, i.e., it is determined by the metric and independent of the resolution and embedding, our method can easily find a consistent mapping between the reference and example poses which can be in different resolutions and triangulations. We first construct the skeleton-like Reeb graph of a harmonic function defined on the given poses. Then by examining the changes of mean curvatures, we identify the initial locations of joints. Finally we refine the joint locations by solving a constrained optimization problem. We demonstrate the efficacy of the proposed framework by pose space deformation, skeleton transfer, shape segmentation and pose-invariant shape signature.

The Reeb graph is a useful tool in visualizing real-valued data obtained from computational simulations of physical processes. We characterize the evolution of the Reeb graph of a time-varying continuous function defined in three-dimensional space. We show how to maintain the Reeb graph over time and compress the entire sequence of Reeb graphs into a single, partially persistent data structure, and augment this data structure with Betti numbers to describe the topology of level sets and with path seeds to assist in the fast extraction of level sets for visualization.

Given a triangulated surface M with arbitrary genus, the set of its cut-graphs depends on the underlying topology and the selection of a specific one should be guided by the surface geometry and targeted applications. Most of the previous work on this topic uses mesh traversal techniques for the evaluation of the geodesic metric, and therefore the cut-graphs are influenced by the mesh connectivity. Our solution is to build up the cut-graph on the iso-contours of a function f:M->R, that cut the topological handles of M, and on the completion of the cut-graph on the planar domain. In the planar domain, geodesic curves are defined by line segments whose counterparts on M, with respect to a diffeomorphism \phi:M->R2, are smooth approximations of geodesic paths. Our method defines a family of cut-graphs of M which can target different applications, such as global parameterization with respect to different criteria (e.g., minimal length, minimization of the parameterization distortion, or interpolation of points as required by remeshing and texture mapping) or the calculation of polygonal schemes for surface classification. The proposed approach finds a cut-graph of an arbitrary triangle mesh M with n vertices and b boundary components in O((b-1)n) time if M has 0-genus, and O(n(log(n)+2g+b-1)) time if g>=1. The associated polygonal schema is reduced if g=0, and it has a constant number of redundant edges otherwise.

The shape data of many complex objects, such as anatomical structures, are available in the form of contour slices. To visualize these complex shapes, most existing methods focus on resolving the contours connectivities and generating surface models. These methods do not offer any way of abstracting characteristic features from these complex shapes. To address this problem, Morse theory has previously been proposed as a topological abstraction tool, and a Morse theory-based surface coding system has been developed to code complex shapes as a sequence of basic operators. The topological structure of the coded surface is, however, implicitly stored in the operators. Topological information is thus not readily available without evaluating the operators. This paper proposes a more versatile representation by incorporating a contour containment relation into the earlier representation. With the explicit topological information, non-sequential construction and modifications can be performed without violating topological integrity. Editing operators similar to the Euler operators are also proposed.

The interference of the motion paths of objects has been an important theme of research. Previous works concentrate on detecting collisions and finding colliding points, and little has been done on characterizing the contact of two objects considering the structures of the space between the objects. This paper proposes a novel method to characterize the interference of objects. Our method is based on the analysis of the structures of the complementary space of three-dimensional objects. The topological structures are analyzed using the coding method based on the Morse theory and the Reeb graph. The method is applied to actual dental articulations to validate the model.

There are kinds of picture that are drawn with multiple viewpoints. Mountain guide maps, cubism pictures and medical-diagnosis drawings are examples of such pictures. So far, however, they have been drawn intuitively by hand. Implementing a CAD system for such pictures requires clear modelling of their drawing processes. As a case study, the paper presents mountain guide-map modelling using manifolds, and the implementation of multiple-viewpoint CAD based on the model. A local land surface is designed using critical points such as peaks, pits and passes. The local surfaces are then pasted together to form the manifold representing the whole surface. Surface shapes in the overlapping areas are blended using a partition of unity. Projecting a land surface as seen from multiple viewpoints is conducted interactively using the CAD system. Then, the mountain guide map is generated automatically.