Search Results

Now showing 1 - 10 of 99
  • Item
    A Parallel Approach to Compression and Decompression of Triangle Meshes using the GPU
    (The Eurographics Association and John Wiley & Sons Ltd., 2017) Jakob, Johannes; Buchenau, Christoph; Guthe, Michael; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
    Most state-of-the-art compression algorithms use complex connectivity traversal and prediction schemes, which are not efficient enough for online compression of large meshes. In this paper we propose a scalable massively parallel approach for compression and decompression of large triangle meshes using the GPU. Our method traverses the input mesh in a parallel breadth-first manner and encodes the connectivity data similarly to the well known cut-border machine. Geometry data is compressed using a local prediction strategy. In contrast to the original cut-border machine, we can additionally handle triangle meshes with inconsistently oriented faces. Our approach is more than one order of magnitude faster than currently used methods and achieves competitive compression rates.
  • 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 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.
  • Item
    Rib-reinforced Shell Structure
    (The Eurographics Association and John Wiley & Sons Ltd., 2016) Li, Wei; Zheng, Anzong; You, Lihua; Yang, Xiaosong; Zhang, Jianjun; Liu, Ligang; Jernej Barbic and Wen-Chieh Lin and Olga Sorkine-Hornung
    Shell structures are extensively used in engineering due to their efficient load-carrying capacity relative to material volume. However, large-span shells require additional supporting structures to strengthen fragile regions. The problem of designing optimal stiffeners is therefore becoming a major challenge for shell applications. To address it, we propose a computational framework to design and optimize rib layout on arbitrary shell to improve the overall structural stiffness and mechanical performance. The essential of our method is to place ribs along the principal stress lines which reflect paths of material continuity and indicates trajectories of internal forces. Given a surface and user-specified external loads, we perform a Finite Element Analysis. Using the resulting principal stress field, we generate a quad-mesh whose edges align with this cross field. Then we extract an initial rib network from the quad-mesh. After simplifying rib network by removing ribs with little contribution, we perform a rib flow optimization which allows ribs to swing on surface to further adjust rib distribution. Finally, we optimize rib cross-section to maximally reduce material usage while achieving certain structural stiffness requirements. We demonstrate that our rib-reinforced shell structures achieve good static performances. And experimental results by 3D printed objects show the effectiveness of our method.
  • 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 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.
  • Item
    Spatial Matching of Animated Meshes
    (The Eurographics Association and John Wiley & Sons Ltd., 2016) Seo, Hyewon; Cordier, Frederic; Eitan Grinspun and Bernd Bickel and Yoshinori Dobashi
    This paper presents a new technique which makes use of deformation and motion properties between animated meshes for finding their spatial correspondences. Given a pair of animated meshes exhibiting a semantically similar motion, we compute a sparse set of feature points on each mesh and compute spatial correspondences among them so that points with similar motion behavior are put in correspondence. At the core of our technique is our new, dynamic feature descriptor named AnimHOG, which encodes local deformation characteristics. AnimHOG is ob-tained by computing the gradient of a scalar field inside the spatiotemporal neighborhood of a point of interest, where the scalar values are obtained from the deformation characteristic associated with each vertex and at each frame. The final matching has been formulated as a discreet optimization problem that finds the matching of each feature point on the source mesh so that the descriptor similarity between the corresponding feature pairs as well as compatibility and consistency as measured across the pairs of correspondences are maximized. Consequently, reliable correspondences can be found even among the meshes of very different shape, as long as their motions are similar. We demonstrate the performance of our technique by showing the good quality of matching results we obtained on a number of animated mesh pairs.
  • Item
    Principal Geodesic Analysis in the Space of Discrete Shells
    (The Eurographics Association and John Wiley & Sons Ltd., 2018) Heeren, Behrend; Zhang, Chao; Rumpf, Martin; Smith, William; Ju, Tao and Vaxman, Amir
    Important sources of shape variability, such as articulated motion of body models or soft tissue dynamics, are highly nonlinear and are usually superposed on top of rigid body motion which must be factored out. We propose a novel, nonlinear, rigid body motion invariant Principal Geodesic Analysis (PGA) that allows us to analyse this variability, compress large variations based on statistical shape analysis and fit a model to measurements. For given input shape data sets we show how to compute a low dimensional approximating submanifold on the space of discrete shells, making our approach a hybrid between a physical and statistical model. General discrete shells can be projected onto the submanifold and sparsely represented by a small set of coefficients. We demonstrate two specific applications: model-constrained mesh editing and reconstruction of a dense animated mesh from sparse motion capture markers using the statistical knowledge as a prior.
  • Item
    Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion
    (The Eurographics Association and John Wiley & Sons Ltd., 2017) Herholz, Philipp; Haase, Felix; Alexa, Marc; Loic Barthe and Bedrich Benes
    We define Voronoi cells and centroids based on heat diffusion. These heat cells and heat centroids coincide with the common definitions in Euclidean spaces. On curved surfaces they compare favorably with definitions based on geodesics: they are smooth and can be computed in a stable way with a single linear solve. We analyze the numerics of this approach and can show that diffusion diagrams converge quadratically against the smooth case under mesh refinement, which is better than other common discretization of distance measures in curved spaces. By factorizing the system matrix in a preprocess, computing Voronoi diagrams or centroids amounts to just back-substitution. We show how to localize this operation so that the complexity is linear in the size of the cells and not the underlying mesh. We provide several example applications that show how to benefit from this approach.
  • Item
    Effective Characterization of Relief Patterns
    (The Eurographics Association and John Wiley & Sons Ltd., 2018) Giachetti, Andrea; Ju, Tao and Vaxman, Amir
    In this paper, we address the problem of characterizing relief patterns over surface meshes independently on the underlying shape. We propose to tackle the problem by estimating local invariant features and encoding them using the Improved Fisher Vector technique, testing both features estimated on 3D meshes and local descriptors estimated on raster images created by encoding local surface properties (e.g. mean curvature) over a surface parametrization. We compare the robustness of the obtained descriptors against noise and surface bending and evaluate retrieval performances on a specific benchmark proposed in a track of the Eurographics Shape REtrieval Contest 2017. Results show that, with the proposed framework, it is possible to obtain retrieval results largely improving the state of the art and that the image-based approach is still effective when the underlying surface is heavily deformed.
  • Item
    Kernel Functional Maps
    (The Eurographics Association and John Wiley & Sons Ltd., 2018) Wang, Larry; Gehre, Anne; Bronstein, Michael M.; Solomon, Justin; Ju, Tao and Vaxman, Amir
    Functional maps provide a means of extracting correspondences between surfaces using linear-algebraic machinery. While the functional framework suggests efficient algorithms for map computation, the basic technique does not incorporate the intuition that pointwise modifications of a descriptor function (e.g. composition of a descriptor and a nonlinearity) should be preserved under the mapping; the end result is that the basic functional maps problem can be underdetermined without regularization or additional assumptions on the map. In this paper, we show how this problem can be addressed through kernelization, in which descriptors are lifted to higher-dimensional vectors or even infinite-length sequences of values. The key observation is that optimization problems for functional maps only depend on inner products between descriptors rather than descriptor values themselves. These inner products can be evaluated efficiently through use of kernel functions. In addition to deriving a kernelized version of functional maps including a recent extension in terms of pointwise multiplication operators, we provide an efficient conjugate gradient algorithm for optimizing our generalized problem as well as a strategy for low-rank estimation of kernel matrices through the Nyström approximation.
  • Item
    Object Completion using k-Sparse Optimization
    (The Eurographics Association and John Wiley & Sons Ltd., 2015) Mavridis, Pavlos; Sipiran, Ivan; Andreadis, Anthousis; Papaioannou, Georgios; Stam, Jos and Mitra, Niloy J. and Xu, Kun
    We present a new method for the completion of partial globally-symmetric 3D objects, based on the detection of partial and approximate symmetries in the incomplete input dataset. In our approach, symmetry detection is formulated as a constrained sparsity maximization problem, which is solved efficiently using a robust RANSACbased optimizer. The detected partial symmetries are then reused iteratively, in order to complete the missing parts of the object. A global error relaxation method minimizes the accumulated alignment errors and a nonrigid registration approach applies local deformations in order to properly handle approximate symmetry. Unlike previous approaches, our method does not rely on the computation of features, it uniformly handles translational, rotational and reflectional symmetries and can provide plausible object completion results, even on challenging cases, where more than half of the target object is missing. We demonstrate our algorithm in the completion of 3D scans with varying levels of partiality and we show the applicability of our approach in the repair and completion of heavily eroded or incomplete cultural heritage objects.