Search Results

Now showing 1 - 10 of 205
  • Item
    Efficient and Robust Computation of an Approximated Medial Axis
    (The Eurographics Association, 2004) Yang, Y.; Brock, O.; Moll, R. N.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
    The medial axis can be viewed as a compact representation for an arbitrary model; it is an essential geometric structure in many applications. A number of practical algorithms for its computation have been aimed at speeding up its computation and at addressing its instabilities. In this paper we propose a new algorithm to compute the medial axis with arbitrary precision. It exhibits several desirable properties not previously combined in a practical and ef cient algorithm. First, it allows for a tradeoff between computation time and accuracy, making it well-suited for applications in which an approximation of the medial axis suf ces, but computational ef ciency is of particular concern. Second, it is output sensitive: the computation complexity of the algorithm does not depend on the size of the representation of a model, but on the size of the representation of the resulting medial axis. Third, the densities of the approximated medial axis points in different areas are adaptive to local free space volumes, based on the assumption that a coarser approximation in wide open area can still suf ce the requirements of the applications. We present theoretical results, bounding the error introduced by the approximation process. The algorithm has been implemented and experimental results are presented that illustrate its computational ef ciency and robustness.
  • Item
    Patch-Collaborative Spectral Point-Cloud Denoising
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Rosman, G.; Dubrovina, A.; Kimmel, R.; Holly Rushmeier and Oliver Deussen
    We present a new framework for point cloud denoising by patch-collaborative spectral analysis. A collaborative generalization of each surface patch is defined, combining similar patches from the denoised surface. The Laplace–Beltrami operator of the collaborative patch is then used to selectively smooth the surface in a robust manner that can gracefully handle high levels of noise, yet preserves sharp surface features. The resulting denoising algorithm competes favourably with state‐of‐the‐art approaches, and extends patch‐based algorithms from the image processing domain to point clouds of arbitrary sampling. We demonstrate the accuracy and noise‐robustness of the proposed algorithm on standard benchmark models as well as range scans, and compare it to existing methods for point cloud denoising.We present a new framework for point cloud denoising by patch‐collaborative spectral analysis. A collaborative generalization of each surface patch is defined, combining similar patches from the denoised surface. The Laplace‐Beltrami operator of the collaborative patch is then used to selectively smooth the surface in a robust manner that can gracefully handle high levels of noise, yet preserves sharp surface features.
  • Item
    Managing Temporal Change of Cities with CityGML
    (The Eurographics Association, 2014) Morel, Maxime; Gesquière, Gilles; Gonzalo Besuievsky and Vincent Tourre
    An increasing number of cities are developing digital models. It becomes thus necessary to take into account changes over time. Interoperability and thus the use of standards is also recommended. In this paper, we propose a new method, based on CityGML to take into account changes in the objects which compose the city. This method is efficient for any kind of changes of the city objects (semantic, geometry, topology or appearance). We then propose an extension of our method in order to consider more frequent changes as it is the case with sensors data that can be linked with part of city objects.
  • Item
    Vega: Non-Linear FEM Deformable Object Simulator
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Sin, F. S.; Schroeder, D.; Barbic, J.; Holly Rushmeier and Oliver Deussen
    This practice and experience paper describes a robust C++ implementation of several non-linear solid three-dimensional deformable object strategies commonly employed in computer graphics, named the Vega finite element method (FEM) simulation library. Deformable models supported include co-rotational linear FEM elasticity, Saint-Venant Kirchhoff FEM model, mass-spring system and invertible FEM models: neo-Hookean, Saint-Venant Kirchhoff and Mooney-Rivlin. We provide several timestepping schemes, including implicit Newmark and backward Euler integrators, and explicit central differences. The implementation of material models is separated from integration, which makes it possible to employ our code not only for simulation, but also for deformable object control and shape modelling. We extensively compare the different material models and timestepping schemes. We provide practical experience and insight gained while using our code in several computer animation and simulation research projects.This practice and experience paper describes a robust C++ implementation of several nonlinear solid 3D deformable object strategies commonly employed in computer graphics, named the Vega FEM simulation library. Deformable models supported include co-rotational linear FEM elasticity, Saint-Venant Kirchhoff FEM model, mass-spring system, and invertible FEM models: neo-Hookean, Saint-Venant Kirchhoff, and Mooney-Rivlin. We provide several timestepping schemes, including implicit Newmark and backward Euler integrators, and explicit central differences. The implementation of material models is separated from integration, which makes it possible to employ our code not only for simulation, but also for deformable object control and shape modeling. We extensively compare the different material models and timestepping schemes. We provide practical experience and insight gained while using our code in several computer animation and simulation research projects.
  • Item
    Sketch-based Image-independent Editing of 3D Tumor Segmentations using Variational Interpolation
    (The Eurographics Association, 2012) Heckel, Frank; Braunewell, Stefan; Soza, Grzegorz; Tietjen, Christian; Hahn, Horst K.; Timo Ropinski and Anders Ynnerman and Charl Botha and Jos Roerdink
    In the past years sophisticated automatic segmentation algorithms for various medical image segmentation problems have been developed. However, there are always cases where automatic algorithms fail to provide an acceptable segmentation. In these cases the user needs efficient segmentation correction tools, a problem which has not received much attention in research. Cases to be manually corrected are often particularly difficult and the image does often not provide enough information for segmentation, so we present an image-independent method for intuitive sketch-based editing of 3D tumor segmentations. It is based on an object reconstruction using variational interpolation and can be used in any 3D modality, such as CT or MRI. We also discuss sketch-based editing in 2D as well as a hole-correction approach for variational interpolation. Our manual correction algorithm has been evaluated on 89 segmentations of tumors in CT by 2 technical experts with 6+ years of experience in tumor segmentation and assessment. The experts rated the quality of our correction tool as acceptable or better in 92.1% of the cases. They needed a median number of 4 correction steps with one step taking 0.4s on average.
  • Item
    Automatic Building of Structured Geological Models
    (The Eurographics Association, 2004) Brandel, S.; Schneider, S.; Perrin, M.; Guiard, N.; Rainaud, J. F.; Lienhardt, P.; Bertrand, Y.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
    The present article proposes a method to signi cantly improve the construction and updating of 3D geological models used for oil and gas exploration. The proposed method takes advantage of the speci c structures which characterize geological objects. We present a prototype of a geological pilot which enables monitoring the automatic building of a 3D model topologically and geologically consistent, starting from a set of unsegmented surfaces. The geological pilot uses a Geological Evolution Scheme (GES) which records all the interpretation elements that the exploration geologist, who is the end user, wishes to introduce into the model. The model building is performed by reading instructions deduced from the GES. Topology is dealt with step by step by using a 3D Generalized Maps (3-G-Maps) data model enriched to enable the manipulation of objects having speci c geological attributes. The result is a correct 3D model on which geological links between objects can easily be visualized. This model can automatically be revised in case of changes in the geometric data or in the interpretation. In its nal version, the created modular tool will be plugged in 3D modelers currently used in exploration geology in order to improve their performance.
  • Item
    Sparse Iterative Closest Point
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Bouaziz, Sofien; Tagliasacchi, Andrea; Pauly, Mark; Yaron Lipman and Hao Zhang
    Rigid registration of two geometric data sets is essential in many applications, including robot navigation, surface reconstruction, and shape matching. Most commonly, variants of the Iterative Closest Point (ICP) algorithm are employed for this task. These methods alternate between closest point computations to establish correspondences between two data sets, and solving for the optimal transformation that brings these correspondences into alignment. A major difficulty for this approach is the sensitivity to outliers and missing data often observed in 3D scans. Most practical implementations of the ICP algorithm address this issue with a number of heuristics to prune or reweight correspondences. However, these heuristics can be unreliable and difficult to tune, which often requires substantial manual assistance. We propose a new formulation of the ICP algorithm that avoids these difficulties by formulating the registration optimization using sparsity inducing norms. Our new algorithm retains the simple structure of the ICP algorithm, while achieving superior registration results when dealing with outliers and incomplete data. The complete source code of our implementation is provided at http://lgg.epfl.ch/sparseicp.
  • Item
    Non-rigid 3D Shape Retrieval via Sparse Representation
    (The Eurographics Association, 2013) Wan, Lili; Li, Shuai; Miao, Zhenjiang J.; Cen, Yigang G.; Bruno Levy and Xin Tong and KangKang Yin
    Shape descriptor design is an important but challenging problem for non-rigid 3D shape retrieval. Recently, bagof- words based methods are widely used to integrate a model's local shape descriptors into a global histogram. In this paper, we present a new method to pool the local shape descriptors into a global shape descriptor by means of sparse representation. Firstly, we employ heat kernel signature (HKS) to depict the multi-scale local shape. Then, for each model in the training dataset, we take the HKSs corresponding to its mesh vertices to serve as training signals, and thus an over-complete dictionary can be learned from them. Finally, the HKSs of each 3D model are sparsely coded based on the learned dictionary, and such sparse representations can be further integrated to form an object-level shape descriptor. Moreover, we conduct extensive experiments on the state-of-the-art benchmarks, wherein comprehensive evaluations state our method can achieve better performance than other bag-of-words based approaches.
  • Item
    Linear-Time Smoke Animation with Vortex Sheet Meshes
    (The Eurographics Association, 2012) Brochu, Tyson; Keeler, Todd; Bridson, Robert; Jehee Lee and Paul Kry
    We present the first quality physics-based smoke animation method which runs in time approximately linear in the size of the rendered two-dimensional visual detail. Our fundamental representation is a closed triangle mesh surface dividing space between clear air and a uniformly smoky region, on which we compute vortex sheet dynamics to accurately solve inviscid buoyant flow. We handle arbitrary moving no-stick solid boundaries and by default handle an infinite domain. The simulation itself runs in time linear to the number of triangles thanks to the use of a well-conditioned integral equation treatment together with a Fast Multipole Method for linear-time summations, providing excellent performance. Basic zero-albedo smoke rendering, with embedded solids, is easy to implement for interactive rates, and the mesh output can also serve as an extremely compact and detailed input to more sophisticated volume rendering.
  • Item
    Smoke Sheets for Graph-Structured Vortex Filaments
    (The Eurographics Association, 2012) Barnat, Alfred; Pollard, Nancy S.; Jehee Lee and Paul Kry
    Smoke is one of the core phenomena which fluid simulation techniques in computer graphics have attempted to capture. It is both well understood mathematically and important in lending realism to computer generated effects. In an attempt to overcome the diffusion inherent to Eulerian grid-based simulators, a technique has recently been developed which represents velocity using a sparse set of vortex filaments. This has the advantage of providing an easily understandable and controllable model for fluid velocity, but is computationally expensive because each filament affects the fluid velocity over an unbounded region of the simulation space. We present an alternative to existing techniques which merge adjacent filament rings, instead allowing filaments to form arbitrary structures, and we develop a new set of reconnection criteria to take advantage of this filament graph. To complement this technique, we also introduce a method for smoke surface tracking and rendering designed to minimize the number of sample points without introducing excessive diffusion or blurring. Though this representation lends itself to straightforward real-time rendering, we also present a method which renders the thin sheets and curls of smoke as diffuse volumes using any GPU capable of supporting geometry shaders.