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 378

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.
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.
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.
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.
As-Conformal-As-Possible Surface Registration
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Yoshiyasu, Yusuke; Ma, Wan-Chun; Yoshida, Eiichi; Kanehiro, Fumio; Thomas Funkhouser and Shi-Min Hu
We present a non-rigid surface registration technique that can align surfaces with sizes and shapes that are different from each other, while avoiding mesh distortions during deformation. The registration is constrained locally as conformal as possible such that the angles of triangle meshes are preserved, yet local scales are allowed to change. Based on our conformal registration technique, we devise an automatic registration and interactive registration technique, which can reduce user interventions during template fitting. We demonstrate the versatility of our technique on a wide range of surfaces.
As-Killing-As-Possible Vector Fields for Planar Deformation
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Solomon, Justin; Ben-Chen, Mirela; Butscher, Adrian; Guibas, Leonidas; Mario Botsch and Scott Schaefer
Cartoon animation, image warping, and several other tasks in two-dimensional computer graphics reduce to the formulation of a reasonable model for planar deformation. A deformation is a map from a given shape to a new one, and its quality is determined by the type of distortion it introduces. In many applications, a desirable map is as isometric as possible. Finding such deformations, however, is a nonlinear problem, and most of the existing solutions approach it by minimizing a nonlinear energy. Such methods are not guaranteed to converge to a global optimum and often suffer from robustness issues. We propose a new approach based on approximate Killing vector fields (AKVFs), first introduced in shape processing. AKVFs generate near-isometric deformations, which can be motivated as direction fields minimizing an as-rigid-as-possible (ARAP) energy to first order. We first solve for an AKVF on the domain given user constraints via a linear optimization problem and then use this AKVF as the initial velocity field of the deformation. In this way, we transfer the inherent nonlinearity of the deformation problem to finding trajectories for each point of the domain having the given initial velocities. We show that a specific class of trajectories - the set of logarithmic spirals - is especially suited for this task both in practice and through its relationship to linear holomorphic vector fields. We demonstrate the effectiveness of our method for planar deformation by comparing it with existing state-of-the-art deformation methods.
As-Rigid-As-Possible Surface Modeling
(The Eurographics Association, 2007) Sorkine, Olga; Alexa, Marc; Alexander Belyaev and Michael Garland
Modeling tasks, such as surface deformation and editing, can be analyzed by observing the local behavior of the surface. We argue that defining a modeling operation by asking for rigidity of the local transformations is useful in various settings. Such formulation leads to a non-linear, yet conceptually simple energy formulation, which is to be minimized by the deformed surface under particular modeling constraints. We devise a simple iterative mesh editing scheme based on this principle, that leads to detail-preserving and intuitive deformations. Our algorithm is effective and notably easy to implement, making it attractive for practical modeling applications.
Atomic Volumes for Mesh Completion
(The Eurographics Association, 2005) Podolak, Joshua; Rusinkiewicz, Szymon; Mathieu Desbrun and Helmut Pottmann
The increased use of scanned geometry for applications in computer graphics and 3D hardcopy output has highlighted the need for general, robust algorithms for reconstruction of watertight 3D models given partial polygonal meshes as input. We present an algorithm for 3D hole filling based on a decomposition of space into atomic volumes, which are each determined to be either completely inside or completely outside the model. By defining the output model as the union of interior atomic volumes we guarantee that the resulting mesh is watertight. Individual volumes are labeled as "inside" or "outside" by computing a minimum-cost cut of a graph representation of the atomic volume structure, patching all the holes simultaneously in a globally sensitive manner. User control is provided to select between multiple topologically distinct, yet still valid, ways of filling holes. Finally, we use an octree decomposition of space to provide output-sensitive computation time. We demonstrate the ability of our algorithm to fill complex, non-planar holes in large meshes obtained from 3D scanning devices.
Automatic and Interactive Mesh to T-Spline Conversion
(The Eurographics Association, 2006) Li, Wan-Chiu; Ray, Nicolas; Lévy, Bruno; Alla Sheffer and Konrad Polthier
In Geometry Processing, and more specifically in surface approximation, one of the most important issues is the automatic generation of a quad-dominant control mesh from an arbitrary shape (e.g. a scanned mesh). One of the first fully automatic solutions was proposed by Eck and Hoppe in 1996. However, in the industry, designers still use manual tools (see e.g. cyslice). The main difference between a control mesh constructed by an automatic method and the one designed by a human user is that in the second case, the control mesh follows the features of the model. More precisely, it is well known from approximation theory that aligning the edges with the principal directions of curvature improves the smoothness of the reconstructed surface, and this is what designers intuitively do. In this paper, our goal is to automatically construct a control mesh driven by the anisotropy of the shape, mimicking the mesh that a designer would create manually. The control mesh generated by our method can be used by a wide variety of representations (splines, subdivision surfaces ...). We demonstrate our method applied to the automatic conversion from a mesh of arbitrary topology into a T-Spline surface. Our method first extracts an initial mesh from a PGP (Periodic Global Parameterization). To facilitate user-interaction, we extend the PGP method to take into account optional user-defined information. This makes it possible to locally tune the orientation and the density of the control mesh. The user can also interactively remove edges or sketch additional ones. Then, from this initial control mesh, our algorithm generates a valid T-Spline control mesh by enforcing some validity constraints. The valid T-Spline control mesh is finally fitted to the original surface, using a classic regularized optimization procedure. To reduce the L-infinite approximation error below a user-defined threshold, we iteratively use the T-Spline adaptive local refinement.
Automatic Registration for Articulated Shapes
(The Eurographics Association and Blackwell Publishing Ltd, 2008) Chang, Will; Zwicker, Matthias
We present an unsupervised algorithm for aligning a pair of shapes in the presence of significant articulated motion and missing data, while assuming no knowledge of a template, user-placed markers, segmentation, or the skeletal structure of the shape. We explicitly sample the motion, which gives a priori the set of possible rigid transformations between parts of the shapes. This transforms the problem into a discrete labeling problem, where the goal is to find an optimal assignment of transformations for aligning the shapes. We then apply graph cuts to optimize a novel cost function, which encodes a preference for a consistent motion assignment from both source to target and target to source. We demonstrate the robustness of our method by aligning several synthetic and real-world datasets.

Browse

Browsing SGP: Eurographics Symposium on Geometry Processing by Title

Results Per Page

Sort Options