SGP16: Eurographics Symposium on Geometry Processing (CGF 35-5)
Permanent URI for this collection
Parametrization and Volumes
Scale-Invariant Directional Alignment of Surface Parametrizations
[meta data] [files:
Campen, Marcel
;
Ibing, Moritz
;
Ebke, Hans-Christian
;
Zorin, Denis
;
Kobbelt, Leif
Mappings
Complex Transfinite Barycentric Mappings with Similarity Kernels
[meta data] [files:
Chen, Renjie
;
Gotsman, Craig
Parametrization and Volumes
Incorporating Sharp Features in the General Solid Sweep Framework
[meta data] [files:
Adsul, Bharat
;
Machchhar, Jinesh
;
Sohoni, Milind
Parametrization and Volumes
Polycube Simplification for Coarse Layouts of Surfaces and Volumes
[meta data] [files:
Cherchi, Gianmarco
;
Livesu, Marco
;
Scateni, Riccardo
Mappings
Iterative Closest Conformal Maps between Planar Domains
[meta data] [files:
Segall, Aviv
;
Ben-Chen, Mirela
Mappings
Advection-Based Function Matching on Surfaces
[meta data] [files:
Azencot, Omri
;
Vantzos, Orestis
;
Ben-Chen, Mirela
Fitting and Tracking
Near-Isometric Level Set Tracking
[meta data] [files:
Tao, Michael
;
Solomon, Justin
;
Butscher, Adrian
Fitting and Tracking
Mobility Fitting using 4D RANSAC
[meta data] [files:
Li, Hao
;
Wan, Guowei
;
Li, Honghua
;
Sharf, Andrei
;
Xu, Kai
;
Chen, Baoquan
Modeling and Design
CustomCut: On-demand Extraction of Customized 3D Parts with 2D Sketches
[meta data] [files:
Guo, Xuekun
;
Lin, Juncong
;
Xu, Kai
;
Chaudhuri, Siddhartha
;
Jin, Xiaogang
Modeling and Design
Stenciling: Designing Structurally-Sound Surfaces with Decorative Patterns
[meta data] [files:
Schumacher, Christian
;
Thomaszewski, Bernhard
;
Gross, Markus
Functional Correspondence
Stable Region Correspondences Between Non-Isometric Shapes
[meta data] [files:
Ganapathi-Subramanian, Vignesh
;
Thibert, Boris
;
Ovsjanikov, Maks
;
Guibas, Leonidas
Modeling and Design
Splines in the Space of Shells
[meta data] [files:
Heeren, Behrend
;
Rumpf, Martin
;
Schröder, Peter
;
Wardetzky, Max
;
Wirth, Benedikt
Functional Correspondence
Non-Rigid Puzzles
[meta data] [files:
Litany, Or
;
Rodolà, Emanuele
;
Bronstein, Alex M.
;
Bronstein, Michael M.
;
Cremers, Daniel
Fabrication
Interactive Modeling of Mechanical Objects
[meta data] [files:
Ureta, Francisca Gil
;
Tymms, Chelsea
;
Zorin, Denis
Fabrication
Data-Driven Bending Elasticity Design by Shell Thickness
[meta data] [files:
Zhang, Xiaoting
;
Le, Xinyi
;
Wu, Zihao
;
Whiting, Emily
;
Wang, Charlie C. L.
Reconstruction
Curve Reconstruction with Many Fewer Samples
[meta data] [files:
Ohrhallinger, Stefan
;
Mitchell, Scott A.
;
Wimmer, Michael
Reconstruction
Crawl through Neighbors: A Simple Curve Reconstruction Algorithm
[meta data] [files:
Parakkat, Amal Dev
;
Muthuganapathy, Ramanathan
Reconstruction
Construction of Topologically Correct and Manifold Isosurfaces
[meta data] [files:
Grosso, Roberto
Structures
Learning 3D Scene Synthesis from Annotated RGB-D Images
[meta data] [files:
Kermani, Zeinab Sadeghipour
;
Liao, Zicheng
;
Tan, Ping
;
Zhang, Hao (Richard)
Structures
Identifying Style of 3D Shapes using Deep Metric Learning
[meta data] [files:
Lim, Isaak
;
Gehre, Anne
;
Kobbelt, Leif
Structures
Symmetry and Orbit Detection via Lie-Algebra Voting
[meta data] [files:
Shi, Zeyun
;
Alliez, Pierre
;
Desbrun, Mathieu
;
Bao, Hujun
;
Huang, Jin
Voronoi et al.
Planar Minimization Diagrams via Subdivision with Applications to Anisotropic Voronoi Diagrams
[meta data] [files:
Bennett, Huck
;
Papadopoulou, Evanthia
;
Yap, Chee
Voronoi et al.
Disk Density Tuning of a Maximal Random Packing
[meta data] [files:
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.
Voronoi et al.
Exploration of Empty Space among Spherical Obstacles via Additively Weighted Voronoi Diagram
[meta data] [files:
Manak, Martin
Differential Properties
Mesh Statistics for Robust Curvature Estimation
[meta data] [files:
Váša, Libor
;
Vaněček, Petr
;
Prantl, Martin
;
Skorkovská, Věra
;
Martínek, Petr
;
Kolingerová, Ivana
Differential Properties
Deep Learning for Robust Normal Estimation in Unstructured Point Clouds
[meta data] [files:
Boulch, Alexandre
;
Marlet, Renaud
Browse
Recent Submissions
Item SGP 2016: Frontmatter(The Eurographics Association and John Wiley & Sons Ltd., 2016) Maks Ovsjanikov; Daniele PanozzoItem Scale-Invariant Directional Alignment of Surface Parametrizations(The Eurographics Association and John Wiley & Sons Ltd., 2016) Campen, Marcel; Ibing, Moritz; Ebke, Hans-Christian; Zorin, Denis; Kobbelt, Leif; Maks Ovsjanikov and Daniele PanozzoVarious applications of global surface parametrization benefit from the alignment of parametrization isolines with principal curvature directions. This is particularly true for recent parametrization-based meshing approaches, where this directly translates into a shape-aware edge flow, better approximation quality, and reduced meshing artifacts. Existing methods to influence a parametrization based on principal curvature directions suffer from scale-dependence, which implies the necessity of parameter variation, or try to capture complex directional shape features using simple 1D curves. Especially for non-sharp features, such as chamfers, fillets, blends, and even more for organic variants thereof, these abstractions can be unfit. We present a novel approach which respects and exploits the 2D nature of such directional feature regions, detects them based on coherence and homogeneity properties, and controls the parametrization process accordingly. This approach enables us to provide an intuitive, scale-invariant control parameter to the user. It also allows us to consider non-local aspects like the topology of a feature, enabling further improvements. We demonstrate that, compared to previous approaches, global parametrizations of higher quality can be generated without user intervention.Item Complex Transfinite Barycentric Mappings with Similarity Kernels(The Eurographics Association and John Wiley & Sons Ltd., 2016) Chen, Renjie; Gotsman, Craig; Maks Ovsjanikov and Daniele PanozzoTransfinite 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.Item 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 PanozzoThis 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.Item 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 PanozzoRepresenting 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.Item 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 PanozzoConformal 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.Item 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 PanozzoA 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.Item Near-Isometric Level Set Tracking(The Eurographics Association and John Wiley & Sons Ltd., 2016) Tao, Michael; Solomon, Justin; Butscher, Adrian; Maks Ovsjanikov and Daniele PanozzoImplicit 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.Item 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 PanozzoCapturing 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.Item 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 PanozzoSeveral 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.Item Stenciling: Designing Structurally-Sound Surfaces with Decorative Patterns(The Eurographics Association and John Wiley & Sons Ltd., 2016) Schumacher, Christian; Thomaszewski, Bernhard; Gross, Markus; Maks Ovsjanikov and Daniele PanozzoWe present a novel method to design shells with artistic cutouts in a manner that produces a stable final result. The process of stenciling, removing material with a fixed shape, is a particularly appealing way to introduce a decorative pattern into the design of architectural structures, furniture, or household objects. However, removing material can easily weaken an object to the point where its integrity is compromised, while purely functional distributions of cutouts lack the desired aesthetic component. We tackle this problem by combining aesthetics, stability, and material efficiency in an optimization that determines the distribution and scaling of these stencils in a way that complies as much as possible with both pattern and stability objectives. We demonstrate the capabilities of our system on examples from architecture, furniture design, and decorative items, and show how user interaction can be integrated to guide the aesthetics of the final result.Item Stable Region Correspondences Between Non-Isometric Shapes(The Eurographics Association and John Wiley & Sons Ltd., 2016) Ganapathi-Subramanian, Vignesh; Thibert, Boris; Ovsjanikov, Maks; Guibas, Leonidas; Maks Ovsjanikov and Daniele PanozzoWe consider the problem of finding meaningful correspondences between 3D models that are related but not necessarily very similar. When the shapes are quite different, a point-to-point map is not always appropriate, so our focus in this paper is a method to build a set of correspondences between shape regions or parts. The proposed approach exploits a variety of feature functions on the shapes and makes use of the key observation that points in matching parts have similar ranks in the sorting of the corresponding feature values. Our algorithm proceeds in two steps. We first build an affinity matrix between points on the two shapes, based on feature rank similarity over many feature functions. We then define a notion of stability of a pair of regions, with respect to this affinity matrix, obtained as a fixed point of a nonlinear operator. Our method yields a family of corresponding maximally stable regions between the two shapes that can be used to define shape parts. We observe that this is an instance of the biclustering problem and that it is related to solving a constrained maximal eigenvalue problem. We provide an algorithm to solve this problem that mimics the power method. We show the robustness of its output to noisy input features as well its convergence properties. The obtained part correspondences are shown to be almost perfect matches in the isometric case, and also semantically appropriate even in non-isometric cases. We provide numerous examples and applications of this technique, for example to sharpening correspondences in traditional shape matching algorithms.Item Splines in the Space of Shells(The Eurographics Association and John Wiley & Sons Ltd., 2016) Heeren, Behrend; Rumpf, Martin; Schröder, Peter; Wardetzky, Max; Wirth, Benedikt; Maks Ovsjanikov and Daniele PanozzoCubic splines in Euclidean space minimize the mean squared acceleration among all curves interpolating a given set of data points. We extend this observation to the Riemannian manifold of discrete shells in which the associated metric measures both bending and membrane distortion. Our generalization replaces the acceleration with the covariant derivative of the velocity. We introduce an effective time-discretization for this novel paradigm for navigating shell space. Further transferring this concept to the space of triangular surface descriptors-edge lengths, dihedral angles, and triangle areas-results in a simplified interpolation method with high computational efficiency.Item 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 PanozzoShape 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.Item 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 PanozzoObjects 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.Item 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 PanozzoWe 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.Item 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 PanozzoWe 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.Item 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 PanozzoGiven 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.Item Construction of Topologically Correct and Manifold Isosurfaces(The Eurographics Association and John Wiley & Sons Ltd., 2016) Grosso, Roberto; Maks Ovsjanikov and Daniele PanozzoWe 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.Item 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 PanozzoWe 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.Item 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 PanozzoWe 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.Item Symmetry and Orbit Detection via Lie-Algebra Voting(The Eurographics Association and John Wiley & Sons Ltd., 2016) Shi, Zeyun; Alliez, Pierre; Desbrun, Mathieu; Bao, Hujun; Huang, Jin; Maks Ovsjanikov and Daniele PanozzoIn this paper, we formulate an automatic approach to the detection of partial, local, and global symmetries and orbits in arbitrary 3D datasets. We improve upon existing voting-based symmetry detection techniques by leveraging the Lie group structure of geometric transformations. In particular, we introduce a logarithmic mapping that ensures that orbits are mapped to linear subspaces, hence unifying and extending many existing mappings in a single Lie-algebra voting formulation. Compared to previous work, our resulting method offers significantly improved robustness as it guarantees that our symmetry detection of an input model is frame, scale, and reflection invariant. As a consequence, we demonstrate that our approach efficiently and reliably discovers symmetries and orbits of geometric datasets without requiring heavy parameter tuning.Item 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 PanozzoLet 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.Item 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 PanozzoWe 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.Item 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 PanozzoProperties 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.Item 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 PanozzoWhile 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.Item 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 PanozzoNormal 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.