178 results
Search Results
Now showing 1 - 10 of 178
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 BrunetThe 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 Managing Temporal Change of Cities with CityGML(The Eurographics Association, 2014) Morel, Maxime; Gesquière, Gilles; Gonzalo Besuievsky and Vincent TourreAn 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 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 RoerdinkIn 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 BrunetThe 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 ZhangRigid 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 YinShape 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 Functional Webs for Freeform Architecture(The Eurographics Association and Blackwell Publishing Ltd., 2011) Deng, B.; Pottmann, Helmut; Wallner, Johannes; Mario Botsch and Scott SchaeferRationalization and construction-aware design dominate the issue of realizability of freeform architecture. The former means the decomposition of an intended shape into parts which are sufficiently simple and efficient to manufacture; the latter refers to a design procedure which already incorporates rationalization. Recent contributions to this topic have been concerned mostly with small-scale parts, for instance with planar faces of meshes. The present paper deals with another important aspect, namely long-range parts and supporting structures. It turns out that from the pure geometry viewpoint this means studying families of curves which cover surfaces in certain well-defined ways. Depending on the application one has in mind, different combinatorial arrangements of curves are required. We here restrict ourselves to so-called hexagonal webs which correspond to a triangular or tri-hex decomposition of a surface. The individual curve may have certain special properties, like being planar, being a geodesic, or being part of a circle. Each of these properties is motivated by manufacturability considerations and imposes constraints on the shape of the surface. We investigate the available degrees of freedom, show numerical methods of optimization, and demonstrate the effectivity of our approach and the variability of construction solutions derived from webs by means of actual architectural designs.Item Linear-Time Smoke Animation with Vortex Sheet Meshes(The Eurographics Association, 2012) Brochu, Tyson; Keeler, Todd; Bridson, Robert; Jehee Lee and Paul KryWe 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 KrySmoke 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.Item Modelling of Clouds from a Hemispherical Image(The Eurographics Association, 2014) Alldieck, Thiemo; Lundtoft, Dennis H.; Montanari, Niels; Nikolov, Ivan; Vlaykov, Iskren G.; Madsen, Claus B.; Rita Borgo and Wen TangThis paper presents an image-based method for modelling clouds. Unlike previous image-based approaches, a hemispherical photograph is used as input, enabling to consider an entire sky instead of merely a portion. Our method computes the intensity and opacity of the clouds from the photograph. For this purpose, beforehand, the sun illumination is filtered, the pixels are classified between cloud and sky pixels, and the sky behind the clouds is reconstructed. After having been smoothed, the intensity of the clouds is used to create vertices on a hemisphere, and their radius coordinate is modulated by the intensity value of the corresponding pixel. Finally, the mesh is generated by triangulation of the vertices. Additionally, the use of the opacity of the clouds to simulate their transparency and render them is proposed. The results show that our method can be used to produce a realistic full sky populated with clouds in a very straightforward way for the user.