SGP16: Eurographics Symposium on Geometry Processing (CGF 35-5)

Permanent URI for this collection

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

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.
Complex Transfinite Barycentric Mappings with Similarity Kernels
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Chen, Renjie; Gotsman, Craig; Maks Ovsjanikov and Daniele Panozzo
Transfinite barycentric kernels are the continuous version of traditional barycentric coordinates and are used to define inter-polants of values given on a smooth planar contour. When the data is two-dimensional, i.e. the boundary of a planar map, these kernels may be conveniently expressed using complex number algebra, simplifying much of the notation and results. In this paper we develop some of the basic complex-valued algebra needed to describe these planar maps, and use it to define similarity kernels, a natural alternative to the usual barycentric kernels. We develop the theory behind similarity kernels, explore their properties, and show that the transfinite versions of the popular three-point barycentric coordinates (Laplace, mean value and Wachspress) have surprisingly simple similarity kernels. We furthermore show how similarity kernels may be used to invert injective transfinite barycentric mappings using an iterative algorithm which converges quite rapidly. This is useful for rendering images deformed by planar barycentric mappings.
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.
Crawl through Neighbors: A Simple Curve Reconstruction Algorithm
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Parakkat, Amal Dev; Muthuganapathy, Ramanathan; Maks Ovsjanikov and Daniele Panozzo
Given a planar point set sampled from an object boundary, the process of approximating the original shape is called curve reconstruction. In this paper, a novel non-parametric curve reconstruction algorithm based on Delaunay triangulation has been proposed and it has been theoretically proved that the proposed method reconstructs the original curve under e-sampling. Starting from an initial Delaunay seed edge, the algorithm proceeds by finding an appropriate neighbouring point and adding an edge between them. Experimental results show that the proposed algorithm is capable of reconstructing curves with different features like sharp corners, outliers, multiple objects, objects with holes, etc. The proposed method also works for open curves. Based on a study by a few users, the paper also discusses an application of the proposed algorithm for reconstructing hand drawn skip stroke sketches, which will be useful in various sketch based interfaces.
Curve Reconstruction with Many Fewer Samples
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Ohrhallinger, Stefan; Mitchell, Scott A.; Wimmer, Michael; Maks Ovsjanikov and Daniele Panozzo
We consider the problem of sampling points from a collection of smooth curves in the plane, such that the CRUST family of proximity-based reconstruction algorithms can rebuild the curves. Reconstruction requires a dense sampling of local features, i.e., parts of the curve that are close in Euclidean distance but far apart geodesically. We show that e < 0:47-sampling is sufficient for our proposed HNN-CRUST variant, improving upon the state-of-the-art requirement of e < 13 -sampling. Thus we may reconstruct curves with many fewer samples. We also present a new sampling scheme that reduces the required density even further than e < 0:47-sampling. We achieve this by better controlling the spacing between geodesically consecutive points. Our novel sampling condition is based on the reach, the minimum local feature size along intervals between samples. This is mathematically closer to the reconstruction density requirements, particularly near sharp-angled features. We prove lower and upper bounds on reach r-sampling density in terms of lfs e-sampling and demonstrate that we typically reduce the required number of samples for reconstruction by more than half.
CustomCut: On-demand Extraction of Customized 3D Parts with 2D Sketches
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Guo, Xuekun; Lin, Juncong; Xu, Kai; Chaudhuri, Siddhartha; Jin, Xiaogang; Maks Ovsjanikov and Daniele Panozzo
Several applications in shape modeling and exploration require identification and extraction of a 3D shape part matching a 2D sketch. We present CustomCut, an on-demand part extraction algorithm. Given a sketched query, CustomCut automatically retrieves partially matching shapes from a database, identifies the region optimally matching the query in each shape, and extracts this region to produce a customized part that can be used in various modeling applications. In contrast to earlier work on sketch-based retrieval of predefined parts, our approach can extract arbitrary parts from input shapes and does not rely on a prior segmentation into semantic components. The method is based on a novel data structure for fast retrieval of partial matches: the randomized compound k-NN graph built on multi-view shape projections. We also employ a coarse-to-fine strategy to progressively refine part boundaries down to the level of individual faces. Experimental results indicate that our approach provides an intuitive and easy means to extract customized parts from a shape database, and significantly expands the design space for the user. We demonstrate several applications of our method to shape design and exploration.
Data-Driven Bending Elasticity Design by Shell Thickness
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Zhang, Xiaoting; Le, Xinyi; Wu, Zihao; Whiting, Emily; Wang, Charlie C. L.; Maks Ovsjanikov and Daniele Panozzo
We present a method to design the deformation behavior of 3D printed models by an interactive tool, where the variation of bending elasticity at different regions of a model is realized by a change in shell thickness. Given a soft material to be used in 3D printing, we propose an experimental setup to acquire the bending behavior of this material on tubes with different diameters and thicknesses. The relationship between shell thickness and bending elasticity is stored in an echo state network using the acquired dataset. With the help of the network, an interactive design tool is developed to generate non-uniformly hollowed models to achieve desired bending behaviors. The effectiveness of this method is verified on models fabricated by different 3D printers by studying whether their physical deformation can match the designed target shape.
Deep Learning for Robust Normal Estimation in Unstructured Point Clouds
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Boulch, Alexandre; Marlet, Renaud; Maks Ovsjanikov and Daniele Panozzo
Normal estimation in point clouds is a crucial first step for numerous algorithms, from surface reconstruction and scene understanding to rendering. A recurrent issue when estimating normals is to make appropriate decisions close to sharp features, not to smooth edges, or when the sampling density is not uniform, to prevent bias. Rather than resorting to manually-designed geometric priors, we propose to learn how to make these decisions, using ground-truth data made from synthetic scenes. For this, we project a discretized Hough space representing normal directions onto a structure amenable to deep learning. The resulting normal estimation method outperforms most of the time the state of the art regarding robustness to outliers, to noise and to point density variation, in the presence of sharp edges, while remaining fast, scaling up to millions of points.
Disk Density Tuning of a Maximal Random Packing
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Ebeida, Mohamed S.; Rushdi, Ahmad A.; Awad, Muhammad A.; Mahmoud, Ahmed H.; Yan, Dong-Ming; English, Shawn A.; Owens, John D.; Bajaj, Chandrajit L.; Mitchell, Scott A.; Maks Ovsjanikov and Daniele Panozzo
We introduce an algorithmic framework for tuning the spatial density of disks in a maximal random packing, without changing the sizing function or radii of disks. Starting from any maximal random packing such as a Maximal Poisson-disk Sampling (MPS), we iteratively relocate, inject (add), or eject (remove) disks, using a set of three successively more-aggressive local operations. We may achieve a user-defined density, either more dense or more sparse, almost up to the theoretical structured limits. The tuned samples are conflict-free, retain coverage maximality, and, except in the extremes, retain the blue noise randomness properties of the input. We change the density of the packing one disk at a time, maintaining the minimum disk separation distance and the maximum domain coverage distance required of any maximal packing. These properties are local, and we can handle spatially-varying sizing functions. Using fewer points to satisfy a sizing function improves the efficiency of some applications. We apply the framework to improve the quality of meshes, removing non-obtuse angles; and to more accurately model fiber reinforced polymers for elastic and failure simulations.
Exploration of Empty Space among Spherical Obstacles via Additively Weighted Voronoi Diagram
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Manak, Martin; Maks Ovsjanikov and Daniele Panozzo
Properties of granular materials or molecular structures are often studied on a simple geometric model - a set of 3D balls. If the balls simultaneously change in size by a constant speed, topological properties of the empty space outside all these balls may also change. Capturing the changes and their subsequent classification may reveal useful information about the model. This has already been solved for balls of the same size, but only an approximate solution has been reported for balls of different sizes. These solutions work on simplicial complexes derived from the dual structure of the ordinary Voronoi diagram of ball centers and use the mathematical concept of simplicial homology groups. If the balls have different radii, it is more appropriate to use the additively weighted Voronoi diagram (also known as the Apollonius diagram) instead of the ordinary diagram, but the dual structure is no longer a simplicial complex, so the previous approaches cannot be used directly. In this paper, a method is proposed to overcome this problem. The method works with Voronoi edges and vertices instead of the dual structure. Additional bridge edges are introduced to overcome disconnected cases. The output is a tree graph of events where cavities are created or merged during a simulated shrinking of the balls. This graph is then reorganized and filtered according to some criteria to get a more concise information about the development of the empty space in the model.
Identifying Style of 3D Shapes using Deep Metric Learning
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Lim, Isaak; Gehre, Anne; Kobbelt, Leif; Maks Ovsjanikov and Daniele Panozzo
We present a method that expands on previous work in learning human perceived style similarity across objects with different structures and functionalities. Unlike previous approaches that tackle this problem with the help of hand-crafted geometric descriptors, we make use of recent advances in metric learning with neural networks (deep metric learning). This allows us to train the similarity metric on a shape collection directly, since any low- or high-level features needed to discriminate between different styles are identified by the neural network automatically. Furthermore, we avoid the issue of finding and comparing sub-elements of the shapes. We represent the shapes as rendered images and show how image tuples can be selected, generated and used efficiently for deep metric learning. We also tackle the problem of training our neural networks on relatively small datasets and show that we achieve style classification accuracy competitive with the state of the art. Finally, to reduce annotation effort we propose a method to incorporate heterogeneous data sources by adding annotated photos found online in order to expand or supplant parts of our training data.
Incorporating Sharp Features in the General Solid Sweep Framework
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Adsul, Bharat; Machchhar, Jinesh; Sohoni, Milind; Maks Ovsjanikov and Daniele Panozzo
This paper extends a recently proposed robust computational framework for constructing the boundary representation (brep) of the volume swept by a given smooth solid moving along a one parameter family h of rigid motions. Our extension allows the input solid to have sharp features, and thus it is a significant and useful generalization of that work. This naturally requires a precise description of the geometry of the surface generated by the sweep of a sharp edge supported by two intersecting smooth faces. We uncover the geometry along with the related issues like parametrization and singularities via a novel mathematical analysis. Correct trimming of such a surface is achieved by an analysis of the interplay between the cone of normals at a sharp point and its trajectory under h. The overall topology is explained by a key lifting theorem which allows us to compute the adjacency relations amongst entities in the swept volume by relating them to corresponding adjacencies in the input solid. Moreover, global issues related to body-check such as orientation, singularities and self-intersections are efficiently resolved. Examples from a pilot implementation illustrate the efficiency and effectiveness of our framework.
Interactive Modeling of Mechanical Objects
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Ureta, Francisca Gil; Tymms, Chelsea; Zorin, Denis; Maks Ovsjanikov and Daniele Panozzo
Objects with various types of mechanical joints are among the most commonly built. Joints implement a vocabulary of simple constrained motions (kinematic pairs) that can be used to build more complex behaviors. Defining physically correct joint geometry is crucial both for realistic appearance of models during motion, as these are typically the only parts of geometry that stay in contact, and for fabrication. Direct design of joint geometry often requires more effort than the design of the rest of the object geometry, as it requires design of components that stay in precise contact, are aligned with other parts, and allow the desired range of motion. We present an interactive system for creating physically realizable joints with user-controlled appearance. Our system minimizes or, in most cases, completely eliminates the need for the user to manipulate low-level geometry of joints. This is achieved by automatically inferring a small number of plausible combinations of joint dimensions, placement and orientation from part geometry, with the user making the final high-level selection based on object semantic. Through user studies, we demonstrate that functional results with a satisfying appearance can be obtained quickly by users with minimal modeling experience, offering a significant improvement in the time required for joint construction, compared to standard modeling approaches.
Iterative Closest Conformal Maps between Planar Domains
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Segall, Aviv; Ben-Chen, Mirela; Maks Ovsjanikov and Daniele Panozzo
Conformal maps between planar domains are an important tool in geometry processing, used for shape deformation and image warping. The Riemann mapping theorem guarantees that there exists a conformal map between any two simply connected planar domains, yet computing this map efficiently remains challenging. In practice, one of the main algorithmic questions is the correspondence between the boundaries of the domains. On the one hand, there exist a number of conformal maps between any two domains, thus many potential boundary correspondences, yet on the other, given full boundary prescription a conformal map might not exist. Furthermore, an approximate boundary fitting can be enough for many applications. We therefore propose an alternating minimization algorithm for finding a boundary-approximating conformal map given only an initial global alignment of the two input domains.We utilize the Cauchy-Green complex barycentric coordinates to parameterize the space of conformal maps from the source domain, and thus compute a continuous map without requiring the discretization of the domain, and without mapping to intermediate domains. This yields a very efficient method which allows to interactively modify additional user-provided constraints, such as point-to-point and stroke-to-stroke correspondences. Furthermore, we show how to easily generalize this setup to quasi-conformal maps, thus enriching the space of mappings and reducing the area distortion. We compare our algorithm to state-of-the-art methods for mapping between planar domains, and demonstrate that we achieve less distorted maps on the same inputs. Finally, we show applications of our approach to stroke based deformation and constrained texture mapping.
Learning 3D Scene Synthesis from Annotated RGB-D Images
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Kermani, Zeinab Sadeghipour; Liao, Zicheng; Tan, Ping; Zhang, Hao (Richard); Maks Ovsjanikov and Daniele Panozzo
We present a data-driven method for synthesizing 3D indoor scenes by inserting objects progressively into an initial, possibly, empty scene. Instead of relying on few hundreds of hand-crafted 3D scenes, we take advantage of existing large-scale annotated RGB-D datasets, in particular, the SUN RGB-D database consisting of 10,000+ depth images of real scenes, to form the prior knowledge for our synthesis task. Our object insertion scheme follows a co-occurrence model and an arrangement model, both learned from the SUN dataset. The former elects a highly probable combination of object categories along with the number of instances per category while a plausible placement is defined by the latter model. Compared to previous works on probabilistic learning for object placement, we make two contributions. First, we learn various classes of higher-order objectobject relations including symmetry, distinct orientation, and proximity from the database. These relations effectively enable considering objects in semantically formed groups rather than by individuals. Second, while our algorithm inserts objects one at a time, it attains holistic plausibility of the whole current scene while offering controllability through progressive synthesis. We conducted several user studies to compare our scene synthesis performance to results obtained by manual synthesis, stateof- the-art object placement schemes, and variations of parameter settings for the arrangement model.
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.
Mobility Fitting using 4D RANSAC
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Li, Hao; Wan, Guowei; Li, Honghua; Sharf, Andrei; Xu, Kai; Chen, Baoquan; Maks Ovsjanikov and Daniele Panozzo
Capturing the dynamics of articulated models is becoming increasingly important. Dynamics, better than geometry, encode the functional information of articulated objects such as humans, robots and mechanics. Acquired dynamic data is noisy, sparse, and temporarily incoherent. The latter property is especially prominent for analysis of dynamics. Thus, processing scanned dynamic data is typically an ill-posed problem. We present an algorithm that robustly computes the joints representing the dynamics of a scanned articulated object. Our key idea is to by-pass the reconstruction of the underlying surface geometry and directly solve for motion joints. To cope with the often-times extremely incoherent scans, we propose a space-time fitting-andvoting approach in the spirit of RANSAC. We assume a restricted set of articulated motions defined by a set of joints which we fit to the 4D dynamic data and measure their fitting quality. Thus, we repeatedly select random subsets and fit with joints, searching for an optimal candidate set of mobility parameters. Without having to reconstruct surfaces as intermediate means, our approach gains the advantage of being robust and efficient. Results demonstrate the ability to reconstruct dynamics of various articulated objects consisting of a wide range of complex and compound motions.
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.
Non-Rigid Puzzles
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Litany, Or; Rodolà, Emanuele; Bronstein, Alex M.; Bronstein, Michael M.; Cremers, Daniel; Maks Ovsjanikov and Daniele Panozzo
Shape correspondence is a fundamental problem in computer graphics and vision, with applications in various problems including animation, texture mapping, robotic vision, medical imaging, archaeology and many more. In settings where the shapes are allowed to undergo non-rigid deformations and only partial views are available, the problem becomes very challenging. To this end, we present a non-rigid multi-part shape matching algorithm. We assume to be given a reference shape and its multiple parts undergoing a non-rigid deformation. Each of these query parts can be additionally contaminated by clutter, may overlap with other parts, and there might be missing parts or redundant ones. Our method simultaneously solves for the segmentation of the reference model, and for a dense correspondence to (subsets of) the parts. Experimental results on synthetic as well as real scans demonstrate the effectiveness of our method in dealing with this challenging matching scenario.
Planar Minimization Diagrams via Subdivision with Applications to Anisotropic Voronoi Diagrams
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Bennett, Huck; Papadopoulou, Evanthia; Yap, Chee; Maks Ovsjanikov and Daniele Panozzo
Let X = {f1, . . ., fn} be a set of scalar functions of the form fi : R2 →R which satisfy some natural properties. We describe a subdivision algorithm for computing a clustered e-isotopic approximation of the minimization diagram of X. By exploiting soft predicates and clustering of Voronoi vertices, our algorithm is the first that can handle arbitrary degeneracies in X, and allow scalar functions which are piecewise smooth, and not necessarily semi-algebraic. We apply these ideas to the computation of anisotropic Voronoi diagram of polygonal sets; this is a natural generalization of anisotropic Voronoi diagrams of point sites, which extends multiplicatively weighted Voronoi diagrams. We implement a prototype of our anisotropic algorithm and provide experimental results.

Browse

Browsing SGP16: Eurographics Symposium on Geometry Processing (CGF 35-5) by Title

Results Per Page

Sort Options