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 534

1-Lipschitz Neural Distance Fields
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Coiffier, Guillaume; Béthune, Louis; Hu, Ruizhen; Lefebvre, Sylvain
Neural implicit surfaces are a promising tool for geometry processing that represent a solid object as the zero level set of a neural network. Usually trained to approximate a signed distance function of the considered object, these methods exhibit great visual fidelity and quality near the surface, yet their properties tend to degrade with distance, making geometrical queries hard to perform without the help of complex range analysis techniques. Based on recent advancements in Lipschitz neural networks, we introduce a new method for approximating the signed distance function of a given object. As our neural function is made 1- Lipschitz by construction, it cannot overestimate the distance, which guarantees robustness even far from the surface. Moreover, the 1-Lipschitz constraint allows us to use a different loss function, called the hinge-Kantorovitch-Rubinstein loss, which pushes the gradient as close to unit-norm as possible, thus reducing computation costs in iterative queries. As this loss function only needs a rough estimate of occupancy to be optimized, this means that the true distance function need not to be known. We are therefore able to compute neural implicit representations of even bad quality geometry such as noisy point clouds or triangle soups. We demonstrate that our methods is able to approximate the distance function of any closed or open surfaces or curves in the plane or in space, while still allowing sphere tracing or closest point projections to be performed robustly.
3D Keypoint Estimation Using Implicit Representation Learning
(The Eurographics Association and John Wiley & Sons Ltd., 2023) Zhu, Xiangyu; Du, Dong; Huang, Haibin; Ma, Chongyang; Han, Xiaoguang; Memari, Pooran; Solomon, Justin
In this paper, we tackle the challenging problem of 3D keypoint estimation of general objects using a novel implicit representation. Previous works have demonstrated promising results for keypoint prediction through direct coordinate regression or heatmap-based inference. However, these methods are commonly studied for specific subjects, such as human bodies and faces, which possess fixed keypoint structures. They also suffer in several practical scenarios where explicit or complete geometry is not given, including images and partial point clouds. Inspired by the recent success of advanced implicit representation in reconstruction tasks, we explore the idea of using an implicit field to represent keypoints. Specifically, our key idea is employing spheres to represent 3D keypoints, thereby enabling the learnability of the corresponding signed distance field. Explicit keypoints can be extracted subsequently by our algorithm based on the Hough transform. Quantitative and qualitative evaluations also show the superiority of our representation in terms of prediction accuracy.
3D Motion Completion in Crowded Scenes
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Gafni, Niv; Sharf, Andrei; Thomas Funkhouser and Shi-Min Hu
Crowded motions refer to multiple objects moving around and interacting such as crowds, pedestrians and etc. We capture crowded scenes using a depth scanner at video frame rates. Thus, our input is a set of depth frames which sample the scene over time. Processing such data is challenging as it is highly unorganized, with large spatiotemporal holes due to many occlusions. As no correspondence is given, locally tracking 3D points across frames is hard due to noise and missing regions. Furthermore global segmentation and motion completion in presence of large occlusions is ambiguous and hard to predict. Our algorithm utilizes Gestalt principles of common fate and good continuity to compute motion tracking and completion respectively. Our technique does not assume any pregiven markers or motion template priors. Our key-idea is to reduce the motion completion problem to a 1D curve fitting and matching problem which can be solved efficiently using a global optimization scheme. We demonstrate our segmentation and completion method on a variety of synthetic and real world crowded scanned scenes.
3D Reconstruction Using Labeled Image Regions
(The Eurographics Association, 2003) Ziegler, Remo; Matusik, Wojciech; Pfister, Hanspeter; McMillan, Leonard; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
In this paper we present a novel algorithm for reconstructing 3D scenes from a set of images. The user defines a set of polygonal regions with corresponding labels in each image using familiar 2D photo-editing tools. Our reconstruction algorithm computes the 3D model with maximum volume that is consistent with the set of regions in the input images. The algorithm is fast, uses only 2D intersection operations, and directly computes a polygonal model. We implemented a user-assisted system for 3D scene reconstruction and show results on scenes that are difficult or impossible to reconstruct with other methods.
3D Shape Segmentation and Labeling via Extreme Learning Machine
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Xie, Zhige; Xu, Kai; Liu, Ligang; Xiong, Yueshan; Thomas Funkhouser and Shi-Min Hu
We propose a fast method for 3D shape segmentation and labeling via Extreme Learning Machine (ELM). Given a set of example shapes with labeled segmentation, we train an ELM classifier and use it to produce initial segmentation for test shapes. Based on the initial segmentation, we compute the final smooth segmentation through a graph-cut optimization constrained by the super-face boundaries obtained by over-segmentation and the active contours computed from ELM segmentation. Experimental results show that our method achieves comparable results against the state-of-the-arts, but reduces the training time by approximately two orders of magnitude, both for face-level and super-face-level, making it scale well for large datasets. Based on such notable improvement, we demonstrate the application of our method for fast online sequential learning for 3D shape segmentation at face level, as well as realtime sequential learning at super-face level.
Adaptive Block Coordinate Descent for Distortion Minimization
(The Eurographics Association, 2019) Naitsat, Alexander; Zeevi, Yehoshua Y.; Bommes, David and Huang, Hui
We present a new unified algorithm for optimizing geometric energies and computing positively oriented simplicial mappings. Its major improvements over the state-of-the-art are: adaptive partition of vertices into coordinate blocks with the blended local-global strategy, introduction of new distortion energies for repairing inverted and degenerated simplices, modification of standard rotation-invariant measures, introduction of displacement norm for improving convergence criteria and for controlling the proposed local-global blending. Together these improvements form the basis for Adaptive Block Coordinate Descent (ABCD) algorithm aimed at robust geometric optimization. Our algorithm achieves state-of-the-art results in distortion minimization, even with highly distorted invalid initializations that contain thousands of inverted and degenerated elements. We show over a wide range of 2D and 3D problems that ABCD is more robust than existing techniques in locally injective mappings.
An Adaptive MLS Surface for Reconstruction with Guarantees
(The Eurographics Association, 2005) Dey, Tamal K.; Sun, Jian; Mathieu Desbrun and Helmut Pottmann
Recent work have shown that moving least squares (MLS) surfaces can be used effectively to reconstruct surfaces from possibly noisy point cloud data. Several variants of MLS surfaces have been suggested, some of which have been analyzed theoretically for guarantees. These analyses, so far, have assumed uniform sampling density. We propose a new variant of the MLS surface that, for the first time, incorporates local feature sizes in its formulation, and we analyze it for reconstruction guarantees using a non-uniform sampling density. The proposed variant of the MLS surface has several computational advantages over existing MLS methods.
Adjoint Map Representation for Shape Analysis and Matching
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Huang, Ruqi; Ovsjanikov, Maks; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
In this paper, we propose to consider the adjoint operators of functional maps, and demonstrate their utility in several tasks in geometry processing. Unlike a functional map, which represents a correspondence simply using the pull-back of function values, the adjoint operator reflects both the map and its distortion with respect to given inner products. We argue that this property of adjoint operators and especially their relation to the map inverse under the choice of different inner products, can be useful in applications including bi-directional shape matching, shape exploration, and pointwise map recovery among others. In particular, in this paper, we show that the adjoint operators can be used within the cycle-consistency framework to encode and reveal the presence or lack of consistency between distortions in a collection, in a way that is complementary to the previously used purely map-based consistency measures.We also show how the adjoint can be used for matching pairs of shapes, by accounting for maps in both directions, can help in recovering point-to-point maps from their functional counterparts, and describe how it can shed light on the role of functional basis selection.
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.
An Algorithm for Triangulating Multiple 3D Polygons
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Zou, Ming; Ju, Tao; Carr, Nathan; Yaron Lipman and Hao Zhang
We present an algorithm for obtaining a triangulation of multiple, non-planar 3D polygons. The output minimizes additive weights, such as the total triangle areas or the total dihedral angles between adjacent triangles. Our algorithm generalizes a classical method for optimally triangulating a single polygon. The key novelty is a mechanism for avoiding non-manifold outputs for two and more input polygons without compromising optimality. For better performance on real-world data, we also propose an approximate solution by feeding the algorithm with a reduced set of triangles. In particular, we demonstrate experimentally that the triangles in the Delaunay tetrahedralization of the polygon vertices offer a reasonable trade off between performance and optimality.
All-Hex Mesh Generation via Volumetric PolyCube Deformation
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Gregson, James; Sheffer, Alla; Zhang, Eugene; Mario Botsch and Scott Schaefer
While hexahedral mesh elements are preferred by a variety of simulation techniques, constructing quality all-hex meshes of general shapes remains a challenge. An attractive hex-meshing approach, often referred to as submapping, uses a low distortion mapping between the input model and a PolyCube (a solid formed from a union of cubes), to transfer a regular hex grid from the PolyCube to the input model. Unfortunately, the construction of suitable PolyCubes and corresponding volumetric maps for arbitrary shapes remains an open problem. Our work introduces a new method for computing low-distortion volumetric PolyCube deformations of general shapes and for subsequent all-hex remeshing. For a given input model, our method simultaneously generates an appropriate PolyCube structure and mapping between the input model and the PolyCube. From these we automatically generate good quality all-hex meshes of complex natural and man-made shapes.
Analysis and Synthesis of 3D Shape Families via Deep-learned Generative Models of Surfaces
(The Eurographics Association and John Wiley & Sons Ltd., 2015) Huang, Haibin; Kalogerakis, Evangelos; Marlin, Benjamin; Mirela Ben-Chen and Ligang Liu
We present a method for joint analysis and synthesis of geometrically diverse 3D shape families. Our method first learns part-based templates such that an optimal set of fuzzy point and part correspondences is computed between the shapes of an input collection based on a probabilistic deformation model. In contrast to previous template-based approaches, the geometry and deformation parameters of our part-based templates are learned from scratch. Based on the estimated shape correspondence, our method also learns a probabilistic generative model that hierarchically captures statistical relationships of corresponding surface point positions and parts as well as their existence in the input shapes. A deep learning procedure is used to capture these hierarchical relationships. The resulting generative model is used to produce control point arrangements that drive shape synthesis by combining and deforming parts from the input collection. The generative model also yields compact shape descriptors that are used to perform fine-grained classification. Finally, it can be also coupled with the probabilistic deformation model to further improve shape correspondence. We provide qualitative and quantitative evaluations of our method for shape correspondence, segmentation, fine-grained classification and synthesis. Our experiments demonstrate superior correspondence and segmentation results than previous state-of-the-art approaches.
Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting
(The Eurographics Association and John Wiley & Sons Ltd., 2020) Ouyang, Wenqing; Peng, Yue; Yao, Yuxin; Zhang, Juyong; Deng, Bailin; Jacobson, Alec and Huang, Qixing
The alternating direction multiplier method (ADMM) is widely used in computer graphics for solving optimization problems that can be nonsmooth and nonconvex. It converges quickly to an approximate solution, but can take a long time to converge to a solution of high-accuracy. Previously, Anderson acceleration has been applied to ADMM, by treating it as a fixed-point iteration for the concatenation of the dual variables and a subset of the primal variables. In this paper, we note that the equivalence between ADMM and Douglas-Rachford splitting reveals that ADMM is in fact a fixed-point iteration in a lower-dimensional space. By applying Anderson acceleration to such lower-dimensional fixed-point iteration, we obtain a more effective approach for accelerating ADMM. We analyze the convergence of the proposed acceleration method on nonconvex problems, and verify its effectiveness on a variety of computer graphics including geometry processing and physical simulation.
Animation-Aware Quadrangulation
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Marcias, Giorgio; Pietroni, Nico; Panozzo, Daniele; Puppo, Enrico; Sorkine-Hornung, Olga; Yaron Lipman and Hao Zhang
Geometric meshes that model animated characters must be designed while taking into account the deformations that the shape will undergo during animation. We analyze an input sequence of meshes with point-to-point correspondence, and we automatically produce a quadrangular mesh that fits well the input animation. We first analyze the local deformation that the surface undergoes at each point, and we initialize a cross field that remains as aligned as possible to the principal directions of deformation throughout the sequence. We then smooth this cross field based on an energy that uses a weighted combination of the initial field and the local amount of stretch. Finally, we compute a field-aligned quadrangulation with an off-the-shelf method. Our technique is fast and very simple to implement, and it significantly improves the quality of the output quad mesh and its suitability for character animation, compared to creating the quad mesh based on a single pose. We present experimental results and comparisons with a state-of-the-art quadrangulation method, on both sequences from 3D scanning and synthetic sequences obtained by a rough animation of a triangulated model.
Anisotropy and Cross Fields
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Simons, Lance; Amenta, Nina; Hu, Ruizhen; Lefebvre, Sylvain
We consider a cross field, possibly with singular points of valence 3 or 5, in which all streamlines are finite, and either end on the boundary or form cycles. We show that we can always assign lengths to the two cross field directions to produce an anisotropic orthogonal frame field. There is a one-dimensional family of such length functions, and we optimize within this family so that the two lengths are everywhere as similar as possible. This gives a numerical bound on the minimal anisotropy of any quad mesh exactly following the input cross field. We also show how to remove some limit cycles.
Approximate Implicitization Via Curve Fitting
(The Eurographics Association, 2003) Wurm, E.; Jüttler, B.; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
We discuss methods for fitting implicitly defined (e.g. piecewise algebraic) curves to scattered data, which may contain problematic regions, such as edges, cusps or vertices. As the main idea, we construct a bivariate function, whose zero contour approximates a given set of points, and whose gradient field simultaneously approximates an estimated normal field. The coefficients of the implicit representation are found by solving a system of linear equations. In order to allow for problematic input data, we introduce a criterion for detecting points close to possible singularities. Using this criterion we split the data into segments and develop methods for propagating the orientation of the normals globally. Furthermore we present a simple fallback strategy, that can be used when the process of orientation propagation fails. The method has been shown to work successfully
Approximating and Intersecting Surfaces from Points
(The Eurographics Association, 2003) Adamson, Anders; Alexa, Marc; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
Point sets become an increasingly popular shape representation. Most shape processing and rendering tasks require the approximation of a continuous surface from the point data. We present a surface approximation that is motivated by an efficient iterative ray intersection computation. On each point on a ray, a local normal direction is estimated as the direction of smallest weighted co-variances of the points. The normal direction is used to build a local polynomial approximation to the surface, which is then intersected with the ray. The distance to the polynomials essentially defines a distance field, whose zero-set is computed by repeated ray intersection. Requiring the distance field to be smooth leads to an intuitive and natural sampling criterion, namely, that normals derived from the weighted co-variances are well defined in a tubular neighborhood of the surface. For certain, well-chosen weight functions we can show that well-sampled surfaces lead to smooth distance fields with non-zero gradients and, thus, the surface is a continuously differentiable manifold. We detail spatial data structures and efficient algorithms to compute ray-surface intersections for fast ray casting and ray tracing of the surface.
Approximating Functions on a Mesh with Restricted Voronoï Diagrams
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Nivoliers, Vincent; Lévy, Bruno; Yaron Lipman and Hao Zhang
We propose a method that computes a piecewise constant approximation of a function defined on a mesh. The approximation is associated with the cells of a restricted Voronoï diagram. Our method optimizes an objective function measuring the quality of the approximation. This objective function depends on the placement of the samples that define the restricted Voronoï diagram and their associated function values. We study the continuity of the objective function, derive the closed-form expression of its derivatives and use them to design a numerical solution mechanism. The method can be applied to a function that has discontinuities, and the result aligns the boundaries of the Voronoï cells with the discontinuities. Some examples are shown, suggesting potential applications in image vectorization and compact representation of lighting.
Approximating Gradients for Meshes and Point Clouds via Diffusion Metric
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Luo, Chuanjiang; Safa, Issam; Wang, Yusu
The gradient of a function defined on a manifold is perhaps one of the most important differential objects in data analysis. Most often in practice, the input function is available only at discrete points sampled from the underlying manifold, and the manifold is approximated by either a mesh or simply a point cloud. While many methods exist for computing gradients of a function defined over a mesh, computing and simplifying gradients and related quantities such as critical points, of a function from a point cloud is non-trivial.In this paper, we initiate the investigation of computing gradients under a different metric on the manifold from the original natural metric induced from the ambient space. Specifically, we map the input manifold to the eigenspace spanned by its Laplacian eigenfunctions, and consider the so-called diffusion distance metric associated with it. We show the relation of gradient under this metric with that under the original metric. It turns out that once the Laplace operator is constructed, it is easier to approximate gradients in the eigenspace for discrete inputs (especially point clouds) and it is robust to noises in the input function and in the underlying manifold. More importantly, we can easily smooth the gradient field at different scales within this eigenspace framework. We demonstrate the use of our new eigen-gradients with two applications: approximating / simplifying the critical points of a function, and the Jacobi sets of two input functions (which describe the correlation between these two functions), from point clouds data.
Approximating Isosurfaces by Guaranteed-quality Triangular Meshes
(The Eurographics Association and John Wiley & Sons Ltd., 2020) Hass, Joel; Trnkova, Maria; Jacobson, Alec and Huang, Qixing
We describe a new method for approximating an implicit surface F by a piecewise-flat triangulated surface whose triangles are as close as possible to equilateral. The main advantage is improved mesh quality which is guaranteed for smooth surfaces. The GradNormal algorithm generates a triangular mesh that gives a piecewise-differentiable approximation of F, with angles between 35.2 and 101.5 degrees. As the mesh size approaches 0, the mesh converges to F through surfaces that are isotopic to F.

Browse

Browsing SGP: Eurographics Symposium on Geometry Processing by Title

Results Per Page

Sort Options