SGP: Eurographics Symposium on Geometry Processing

Permanent URI for this community

https://diglib.eg.org/handle/10.2312/434

Browse

Now showing 1 - 20 of 27

Advection-Based Function Matching on Surfaces
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Azencot, Omri; Vantzos, Orestis; Ben-Chen, Mirela; Maks Ovsjanikov and Daniele Panozzo
A tangent vector field on a surface is the generator of a smooth family of maps from the surface to itself, known as the flow. Given a scalar function on the surface, it can be transported, or advected, by composing it with a vector field's flow. Such transport is exhibited by many physical phenomena, e.g., in fluid dynamics. In this paper, we are interested in the inverse problem: given source and target functions, compute a vector field whose flow advects the source to the target. We propose a method for addressing this problem, by minimizing an energy given by the advection constraint together with a regularizing term for the vector field. Our approach is inspired by a similar method in computational anatomy, known as LDDMM, yet leverages the recent framework of functional vector fields for discretizing the advection and the flow as operators on scalar functions. The latter allows us to efficiently generalize LDDMM to curved surfaces, without explicitly computing the flow lines of the vector field we are optimizing for. We show two approaches for the solution: using linear advection with multiple vector fields, and using non-linear advection with a single vector field. We additionally derive an approximated gradient of the corresponding energy, which is based on a novel vector field transport operator. Finally, we demonstrate applications of our machinery to intrinsic symmetry analysis, function interpolation and map improvement.
Can Mean-Curvature Flow be Modified to be Non-singular?
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Kazhdan, Michael; Solomon, Jake; Ben-Chen, Mirela; Eitan Grinspun and Niloy Mitra
This work considers the question of whether mean-curvature flow can be modified to avoid the formation of singularities. We analyze the finite-elements discretization and demonstrate why the original flow can result in numerical instability due to division by zero. We propose a variation on the flow that removes the numerical instability in the discretization and show that this modification results in a simpler expression for both the discretized and continuous formulations. We discuss the properties of the modified flow and present empirical evidence that not only does it define a stable surface evolution for genus-zero surfaces, but that the evolution converges to a conformal parameterization of the surface onto the sphere.
Connectivity Editing for Quad-Dominant Meshes
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Peng, Chi-Han; Wonka, Peter; Yaron Lipman and Hao Zhang
We propose a connectivity editing framework for quad-dominant meshes. In our framework, the user can edit the mesh connectivity to control the location, type, and number of irregular vertices (with more or fewer than four neighbors) and irregular faces (non-quads). We provide a theoretical analysis of the problem, discuss what edits are possible and impossible, and describe how to implement an editing framework that realizes all possible editing operations. In the results, we show example edits and illustrate the advantages and disadvantages of different strategies for quad-dominant mesh design.
Construction of Topologically Correct and Manifold Isosurfaces
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Grosso, Roberto; Maks Ovsjanikov and Daniele Panozzo
We present a simple method to describe the geometry and topologically classify the intersection of level sets of trilinear interpolants with a reference unit cell. The solutions of three quadratic equations are used to correctly triangulate the level set within the cell satisfying the conditions imposed by the asymptotic decider. This way the triangulation of isosurfaces across cells borders is manifold and topologically correct. The algorithm presented is intuitive and easy to implement.
Dense Point-to-Point Correspondences Between Genus-Zero Shapes
(The Eurographics Association and John Wiley & Sons Ltd., 2019) Lee, Sing Chun; Kazhdan, Misha; Bommes, David and Huang, Hui
We describe a novel approach that addresses the problem of establishing correspondences between non-rigidly deformed shapes by performing the registration over the unit sphere. In a pre-processing step, each shape is conformally parametrized over the sphere, centered to remove Möbius inversion ambiguity, and authalically evolved to expand regions that are excessively compressed by the conformal parametrization. Then, for each pair of shapes, we perform fast SO(3) correlation to find the optimal rotational alignment and refine the registration using optical flow. We evaluate our approach on the TOSCA dataset, demonstrating that our approach compares favorably to state-of-the-art methods.
Fast and Exact (Poisson) Solvers on Symmetric Geometries
(The Eurographics Association and John Wiley & Sons Ltd., 2015) Kazhdan, Misha; Mirela Ben-Chen and Ligang Liu
In computer graphics, numerous geometry processing applications reduce to the solution of a Poisson equation. When considering geometries with symmetry, a natural question to consider is whether and how the symmetry can be leveraged to derive an efficient solver for the underlying system of linear equations. In this work we provide a simple representation-theoretic analysis that demonstrates how symmetries of the geometry translate into block diagonalization of the linear operators and we show how this results in efficient linear solvers for surfaces of revolution with and without angular boundaries.
Fast and Robust Approximation of Smallest Enclosing Balls in Arbitrary Dimensions
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Larsson, Thomas; Källberg, Linus; Yaron Lipman and Hao Zhang
In this paper, an algorithm is introduced that computes an arbitrarily fine approximation of the smallest enclosing ball of a point set in any dimension. This operation is important in, for example, classification, clustering, and data mining. The algorithm is very simple to implement, gives reliable results, and gracefully handles large problem instances in low and high dimensions, as confirmed by both theoretical arguments and empirical evaluation. For example, using a CPU with eight cores, it takes less than two seconds to compute a 1:001-approximation of the smallest enclosing ball of one million points uniformly distributed in a hypercube in dimension 200. Furthermore, the presented approach extends to a more general class of input objects, such as ball sets.
Fast Planar Harmonic Deformations with Alternating Tangential Projections
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Hefetz, Eden Fedida; Chien, Edward; Weber, Ofir; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
We present a planar harmonic cage-based deformation method with local injectivity and bounded distortion guarantees, that is significantly faster than state-of-the-art methods with similar guarantees, and allows for real-time interaction. With a convex proxy for a near-convex characterization of the bounded distortion harmonic mapping space from [LW16], we utilize a modified alternating projection method (referred to as ATP) to project to this proxy. ATP draws inspiration from [KABL15] and restricts every other projection to lie in a tangential hyperplane. In contrast to [KABL15], our convex setting allows us to show that ATP is provably convergent (and is locally injective). Compared to the standard alternating projection method, it demonstrates superior convergence in fewer iterations, and it is also embarrassingly parallel, allowing for straightforward GPU implementation. Both of these factors combine to result in unprecedented speed. The convergence proof generalizes to arbitrary pairs of intersecting convex sets, suggesting potential use in other applications. Additional theoretical results sharpen the near-convex characterization that we use and demonstrate that it is homeomorphic to the bounded distortion harmonic mapping space (instead of merely being bijective).
GWCNN: A Metric Alignment Layer for Deep Shape Analysis
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Ezuz, Danielle; Solomon, Justin; Kim, Vladimir G.; Ben-Chen, Mirela; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
Deep neural networks provide a promising tool for incorporating semantic information in geometry processing applications. Unlike image and video processing, however, geometry processing requires handling unstructured geometric data, and thus data representation becomes an important challenge in this framework. Existing approaches tackle this challenge by converting point clouds, meshes, or polygon soups into regular representations using, e.g., multi-view images, volumetric grids or planar parameterizations. In each of these cases, geometric data representation is treated as a fixed pre-process that is largely disconnected from the machine learning tool. In contrast, we propose to optimize for the geometric representation during the network learning process using a novel metric alignment layer. Our approach maps unstructured geometric data to a regular domain by minimizing the metric distortion of the map using the regularized Gromov-Wasserstein objective. This objective is parameterized by the metric of the target domain and is differentiable; thus, it can be easily incorporated into a deep network framework. Furthermore, the objective aims to align the metrics of the input and output domains, promoting consistent output for similar shapes. We show the effectiveness of our layer within a deep network trained for shape classification, demonstrating state-of-the-art performance for nonrigid shapes.
A Hierarchical Grid Based Framework for Fast Collision Detection
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Fan, Wenshan; Wang, Bin; Paul, Jean-Claude; Sun, Jiaguang; Mario Botsch and Scott Schaefer
We present a novel hierarchical grid based method for fast collision detection (CD) for deformable models on GPU architecture. A two-level grid is employed to accommodate the non-uniform distribution of practical scene geometry. A bottom-to-top method is implemented to assign the triangles into the hierarchical grid without any iteration while a deferred scheme is introduced to efficiently update the data structure. To address the issue of load balancing, which greatly influences the performance in SIMD parallelism, a propagation scheme which utilizes a parallel scan and a segmented scan is presented, distributing workloads evenly across all concurrent threads. The proposed method supports both discrete collision detection (DCD) and continuous collision detection (CCD) with self-collision. Some typical benchmarks are tested to verify the effectiveness of our method. The results highlight our speedups over prior algorithms on different commodity GPUs.
Hierarchical Multiview Rigid Registration
(The Eurographics Association and John Wiley & Sons Ltd., 2015) Tang, Yizhi; Feng, Jieqing; Mirela Ben-Chen and Ligang Liu
Registration is a key step in the 3D reconstruction of real-world objects. In this paper, we propose a hierarchical method for the rigid registration of multiple views. The multiview registration problem is solved via hierarchical optimization defined on an undirected graph. Each node or edge in this graph represents a single view or a connection between two overlapped views, respectively. The optimizations are performed hierarchically on the edges, the loops, and the entire graph. First, each overlapped pair of views is locally aligned. Then, a loop-based incremental registration algorithm is introduced to refine the initial pairwise alignments. After a loop is registered, the views in the loop are merged into a metaview in the graph. Finally, global error diffusion is applied to the entire graph to evenly distribute the accumulated errors to all views. In addition, a new objective function is defined to describe the loop closure problem; it improves the accuracy and robustness of registration by simultaneously considering transformation and registration errors. The experimental results show that the proposed hierarchical approach is accurate, efficient and robust for initial view states that are not well posed.
Mesh Statistics for Robust Curvature Estimation
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Váša, Libor; Vaněček, Petr; Prantl, Martin; Skorkovská, Věra; Martínek, Petr; Kolingerová, Ivana; Maks Ovsjanikov and Daniele Panozzo
While it is usually not difficult to compute principal curvatures of a smooth surface of sufficient differentiability, it is a rather difficult task when only a polygonal approximation of the surface is available, because of the inherent ambiguity of such representation. A number of different approaches has been proposed in the past that tackle this problem using various techniques. Most papers tend to focus on a particular method, while an comprehensive comparison of the different approaches is usually missing. We present results of a large experiment, involving both common and recently proposed curvature estimation techniques, applied to triangle meshes of varying properties. It turns out that none of the approaches provides reliable results under all circumstances. Motivated by this observation, we investigate mesh statistics, which can be computed from vertex positions and mesh connectivity information only, and which can help in deciding which estimator will work best for a particular case. Finally, we propose a meta-estimator, which makes a choice between existing algorithms based on the value of the mesh statistics, and we demonstrate that such meta-estimator, despite its simplicity, provides considerably more robust results than any existing approach.
Möbius Registration
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Baden, Alex; Crane, Keenan; Kazhdan, Misha; Ju, Tao and Vaxman, Amir
Conformal parameterizations over the sphere provide high-quality maps between genus zero surfaces, and are essential for applications such as data transfer and comparative shape analysis. However, such maps are not unique: to define correspondence between two surfaces, one must find the Möbius transformation that best aligns two parameterizations-akin to picking a translation and rotation in rigid registration problems. We describe a simple procedure that canonically centers and rotationally aligns two spherical maps. Centering is implemented via elementary operations on triangle meshes in R3, and minimizes area distortion. Alignment is achieved using the FFT over the group of rotations. We examine this procedure in the context of spherical conformal parameterization, orbifold maps, non-rigid symmetry detection, and dense point-to-point surface correspondence.
A Multiscale Approach to Optimal Transport
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Mérigot, Quentin; Mario Botsch and Scott Schaefer
In this paper, we propose an improvement of an algorithm of Aurenhammer, Hoffmann and Aronov to find a least square matching between a probability density and finite set of sites with mass constraints, in the Euclidean plane. Our algorithm exploits the multiscale nature of this optimal transport problem. We iteratively simplify the target using Lloyd's algorithm, and use the solution of the simplified problem as a rough initial solution to the more complex one. This approach allows for fast estimation of distances between measures related to optimal transport (known as Earth-mover or Wasserstein distances). We also discuss the implementation of these algorithms, and compare the original one to its multiscale counterpart.
Near-Isometric Level Set Tracking
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Tao, Michael; Solomon, Justin; Butscher, Adrian; Maks Ovsjanikov and Daniele Panozzo
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.
On the Shape of a Set of Points and Lines in the Plane
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Kreveld, Marc van; Lankveld, Thijs van; Veltkamp, Remco C.; Mario Botsch and Scott Schaefer
Detailed geometric models of the real world are in increasing demand. LiDAR data is appropriate to reconstruct urban models. In urban scenes, the individual surfaces can be reconstructed and connected to form the scene geometry. There are various methods for reconstructing the free-form shape of a point sample on a single surface. However, these methods do not take the context of the surface into account. We present the guided a-shape: an extension of the well known a-shape that uses lines (guides) to indicate preferred locations for the boundary of the shape. The guided a-shape uses (parts of) these lines as boundary where the points suggest that this is appropriate. We prove that the guided a-shape can be constructed in O((n+m) log(n+m)) time, from an input of n points and m guides. We apply guided a-shapes to urban reconstruction from LiDAR, where neighboring surfaces can be connected conveniently along their intersection lines into adjacent surfaces of a 3D model. We analyze guided a-shapes of both synthetic and real data and show they are consistently better than a-shapes for this application.
Packing Irregular Objects in 3D Space via Hybrid Optimization
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Ma, Yuexin; Chen, Zhonggui; Hu, Wenchao; Wang, Wenping; Ju, Tao and Vaxman, Amir
Packing problems arise in a wide variety of practical applications. The basic problem is that of placing as many objects as possible in a non-overlapping configuration within a given container. Problems involving irregular shapes are the most challenging cases. In this paper, we consider the most general forms of irregular shape packing problems in 3D space, where both the containers and the objects can be of any shapes, and free rotations of the objects are allowed. We propose a heuristic method for efficiently packing irregular objects by combining continuous optimization and combinatorial optimization. Starting from an initial placement of an appropriate number of objects, we optimize the positions and orientations of the objects using continuous optimization. In combinatorial optimization, we further reduce the gaps between objects by swapping and replacing the deployed objects and inserting new objects. We demonstrate the efficacy of our method with experiments and comparisons.
A Parallel Approach to Compression and Decompression of Triangle Meshes using the GPU
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Jakob, Johannes; Buchenau, Christoph; Guthe, Michael; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
Most state-of-the-art compression algorithms use complex connectivity traversal and prediction schemes, which are not efficient enough for online compression of large meshes. In this paper we propose a scalable massively parallel approach for compression and decompression of large triangle meshes using the GPU. Our method traverses the input mesh in a parallel breadth-first manner and encodes the connectivity data similarly to the well known cut-border machine. Geometry data is compressed using a local prediction strategy. In contrast to the original cut-border machine, we can additionally handle triangle meshes with inconsistently oriented faces. Our approach is more than one order of magnitude faster than currently used methods and achieves competitive compression rates.
Poisson Surface Reconstruction with Envelope Constraints
(The Eurographics Association and John Wiley & Sons Ltd., 2020) Kazhdan, Misha; Chuang, Ming; Rusinkiewicz, Szymon; Hoppe, Hugues; Jacobson, Alec and Huang, Qixing
Reconstructing surfaces from scanned 3D points has been an important research area for several decades. One common approach that has proven efficient and robust to noise is implicit surface reconstruction, i.e. fitting to the points a 3D scalar function (such as an indicator function or signed-distance field) and then extracting an isosurface. Though many techniques fall within this category, existing methods either impose no boundary constraints or impose Dirichlet/Neumann conditions on the surface of a bounding box containing the scanned data. In this work, we demonstrate the benefit of supporting Dirichlet constraints on a general boundary. To this end, we adapt the Screened Poisson Reconstruction algorithm to input a constraint envelope in addition to the oriented point cloud. We impose Dirichlet boundary conditions, forcing the reconstructed implicit function to be zero outside this constraint surface. Using a visual hull and/or depth hull derived from RGB-D scans to define the constraint envelope, we obtain substantially improved surface reconstructions in regions of missing data.
Polycube Simplification for Coarse Layouts of Surfaces and Volumes
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Cherchi, Gianmarco; Livesu, Marco; Scateni, Riccardo; Maks Ovsjanikov and Daniele Panozzo
Representing digital objects with structured meshes that embed a coarse block decomposition is a relevant problem in applications like computer animation, physically-based simulation and Computer Aided Design (CAD). One of the key ingredients to produce coarse block structures is to achieve a good alignment between the mesh singularities (i.e., the corners of each block). In this paper we improve on the polycube-based meshing pipeline to produce both surface and volumetric coarse block-structured meshes of general shapes. To this aim we add a new step in the pipeline. Our goal is to optimize the positions of the polycube corners to produce as coarse as possible base complexes. We rely on re-mapping the positions of the corners on an integer grid and then using integer numerical programming to reach the optimal. To the best of our knowledge this is the first attempt to solve the singularity misalignment problem directly in polycube space. Previous methods for polycube generation did not specifically address this issue. Our corner optimization strategy is efficient and requires a negligible extra running time for the meshing pipeline. In the paper we show that our optimized polycubes produce coarser block structured surface and volumetric meshes if compared with previous approaches. They also induce higher quality hexahedral meshes and are better suited for spline fitting because they reduce the number of splines necessary to cover the domain, thus improving both the efficiency and the overall level of smoothness throughout the volume.

Browse

Browsing SGP: Eurographics Symposium on Geometry Processing by Subject "and systems"

Results Per Page

Sort Options