35-Issue 5

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 27

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.
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.
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.
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.
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.
Polycube Simplification for Coarse Layouts of Surfaces and Volumes
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Cherchi, Gianmarco; Livesu, Marco; Scateni, Riccardo; Maks Ovsjanikov and Daniele Panozzo
Representing digital objects with structured meshes that embed a coarse block decomposition is a relevant problem in applications like computer animation, physically-based simulation and Computer Aided Design (CAD). One of the key ingredients to produce coarse block structures is to achieve a good alignment between the mesh singularities (i.e., the corners of each block). In this paper we improve on the polycube-based meshing pipeline to produce both surface and volumetric coarse block-structured meshes of general shapes. To this aim we add a new step in the pipeline. Our goal is to optimize the positions of the polycube corners to produce as coarse as possible base complexes. We rely on re-mapping the positions of the corners on an integer grid and then using integer numerical programming to reach the optimal. To the best of our knowledge this is the first attempt to solve the singularity misalignment problem directly in polycube space. Previous methods for polycube generation did not specifically address this issue. Our corner optimization strategy is efficient and requires a negligible extra running time for the meshing pipeline. In the paper we show that our optimized polycubes produce coarser block structured surface and volumetric meshes if compared with previous approaches. They also induce higher quality hexahedral meshes and are better suited for spline fitting because they reduce the number of splines necessary to cover the domain, thus improving both the efficiency and the overall level of smoothness throughout the volume.
SGP 2016: Frontmatter
(The Eurographics Association and John Wiley & Sons Ltd., 2016) Maks Ovsjanikov; Daniele Panozzo
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.
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 Panozzo
In 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.
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.
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.
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 Panozzo
We 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.
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.
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.
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.
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.
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.

Browse

Browsing 35-Issue 5 by Issue Date

Results Per Page

Sort Options