Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeodesicEmbedding (GE): A High-Dimensional Embedding Approach for Fast Geodesic Distance Queries
167
0
0.0
(
0
)
Added by
Bailin Deng
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we develop a novel method for fast geodesic distance queries. The key idea is to embed the mesh into a high-dimensional space, such that the Euclidean distance in the high-dimensional space can induce the geodesic distance in the original manifold surface. However, directly solving the high-dimensional embedding problem is not feasible due to the large number of variables and the fact that the embedding problem is highly nonlinear. We overcome the challenges with two novel ideas. First, instead of taking all vertices as variables, we embed only the saddle vertices, which greatly reduces the problem complexity. We then compute a local embedding for each non-saddle vertex. Second, to reduce the large approximation error resulting from the purely Euclidean embedding, we propose a cascaded optimization approach that repeatedly introduces additional embedding coordinates with a non-Euclidean function to reduce the approximation residual. Using the precomputation data, our approach can determine the geodesic distance between any two vertices in near-constant time. Computational testing results show that our method is more desirable than previous geodesic distance queries methods.
rate research
Read More
In this paper, we propose a parallel and scalable approach for geodesic distance computation on triangle meshes. Our key observation is that the recovery of geodesic distance with the heat method from [Crane et al. 2013] can be reformulated as optimization of its gradients subject to integrability, which can be solved using an efficient first-order method that requires no linear system solving and converges quickly. Afterward, the geodesic distance is efficiently recovered by parallel integration of the optimized gradients in breadth-first order. Moreover, we employ a similar breadth-first strategy to derive a parallel Gauss-Seidel solver for the diffusion step in the heat method. To further lower the memory consumption from gradient optimization on faces, we also propose a formulation that optimizes the projected gradients on edges, which reduces the memory footprint by about 50%. Our approach is trivially parallelizable, with a low memory footprint that grows linearly with respect to the model size. This makes it particularly suitable for handling large models. Experimental results show that it can efficiently compute geodesic distance on meshes with more than 200 million vertices on a desktop PC with 128GB RAM, outperforming the original heat method and other state-of-the-art geodesic distance solvers.
This paper presents a new curved layer volume decomposition method for multi-axis support-free printing of freeform solid parts. Given a solid model to be printed that is represented as a tetrahedral mesh, we first establish a geodesic distance field embedded on the mesh, whose value at any vertex is the geodesic distance to the base of the model. Next, the model is naturally decomposed into curved layers by interpolating a number of iso-geodesic distance surfaces (IGDSs). These IGDSs morph from bottom-up in an intrinsic and smooth way owing to the nature of geodesics, which will be used as the curved printing layers that are friendly to multi-axis printing. In addition, to cater to the collision-free requirement and to improve the printing efficiency, we also propose a printing sequence optimization algorithm for determining the printing order of the IGDSs, which helps reduce the air-move path length. Ample experiments in both computer simulation and physical printing are performed, and the experimental results confirm the advantages of our method.
Numerical computation of shortest paths or geodesics on curved domains, as well as the associated geodesic distance, arises in a broad range of applications across digital geometry processing, scientific computing, computer graphics, and computer vision. Relative to Euclidean distance computation, these tasks are complicated by the influence of curvature on the behavior of shortest paths, as well as the fact that the representation of the domain may itself be approximate. In spite of the difficulty of this problem, recent literature has developed a wide variety of sophisticated methods that enable rapid queries of geodesic information, even on relatively large models. This survey reviews the major categories of approaches to the computation of geodesic paths and distances, highlighting common themes and opportunities for future improvement.
Blue noise sampling has proved useful for many graphics applications, but remains underexplored in high-dimensional spaces due to the difficulty of generating distributions and proving properties about them. We present a blue noise sampling method with good quality and performance across different dimensions. The method, spoke-dart sampling, shoots rays from prior samples and selects samples from these rays. It combines the advantages of two major high-dimensional sampling methods: the locality of advancing front with the dimensionality-reduction of hyperplanes, specifically line sampling. We prove that the output sampling is saturated with high probability, with bounds on distances between pairs of samples and between any domain point and its nearest sample. We demonstrate spoke-dart applications for approximate Delaunay graph construction, global optimization, and robotic motion planning. Both the blue-noise quality of the output distribution and the adaptability of the intermediate processes of our method are useful in these applications.
We present Clusterplot, a multi-class high-dimensional data visualization tool designed to visualize cluster-level information offering an intuitive understanding of the cluster inter-relations. Our unique plots leverage 2D blobs devised to convey the geometrical and topological characteristics of clusters within the high-dimensional data, and their pairwise relations, such that general inter-cluster behavior is easily interpretable in the plot. Class identity supervision is utilized to drive the measuring of relations among clusters in high-dimension, particularly, proximity and overlap, which are then reflected spatially through the 2D blobs. We demonstrate the strength of our clusterplots and their ability to deliver a clear and intuitive informative exploration experience for high-dimensional clusters characterized by complex structure and significant overlap.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
