liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Level-set methods and geodesic distance functions
Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The work in this thesis focuses on efficient implementations of level-set methods and geodesic distance functions. The level-set method is a grid based design that inherits many favorable traits from implicit geometry. It is connected to distance functions through its special way of representing geometry: in ìo each point in space stores the closest distance to the surface. To differentiate between the inside and outside of a closed object a signed distance is used. In the discrete form the representation keeps a box around the surface that stores regularly positioned samples of the distance function – i.e. a grid. These samples implicitly encode the surface as the zeroth level-set of the signed distance function, hence the name level-set methods. With this representation of geometry follows a toolbox of operations based on partial differential equations (PDE). The solution to these PDES allows for arbitrary motion and deformation of the surface.

This thesis focuses on two topics: 1) grid storage for level-set methods, and 2) geodesic distance functions and parameterization. These topics are covered in a series of in-depth articles.

Today, level-set methods are becoming widespread in both academia and industry. Data structures and highly accurate methods and numerical schemes are available that allow for efficient handling of topological changes of dynamic curves and surfaces. For some applications, such as the capturing of the air/water interface in free surface fluid simulations, it’s is the only realistic choice. In other areas level-set methods are emerging as a competitive candidate to triangle meshes and other explicit representations.

In particular this work introduces efficient level-set data-structures that allow for extremely detailed simulations and representations. It also presents a parameterization method based on geodesic distance that produces a unique coordinate system, the Riemannian normal coordinates (RNC). Amongst other interesting applications this parameterization can be used for decal compositing, and the translation of vector space algorithms to surfaces. The approximation of the RNC involves one or more distance functions. In this thesis, a method originally presented for triangle meshes is adopted. It is then and extended to compute accurate geodesic distance in anisotropic domains in two and three dimensions. The extension to higher dimensions is also outlined.

To motivate this work several applications based on these novel methods and data structures are presented showing rapid ray-tracing, shape morphing, segmentation, geodesic interpolation, texture mapping, and more.

Place, publisher, year, edition, pages
Linköping: Linköping Universisty Electronic Press , 2009. , 92 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1275
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-54830ISBN: 978-91-7393-524-1 (print)OAI: oai:DiVA.org:liu-54830DiVA: diva2:310622
Public defence
2009-11-19, K3. Kåkenhus, Campus Norrköping, Linköpings universitet, Norrköping, 13:00 (English)
Opponent
Supervisors
Available from: 2010-04-15 Created: 2010-04-15 Last updated: 2010-06-21Bibliographically approved
List of papers
1. Surface Reconstruction Via Contour Metamorphosis: An Eulerian Approach With Lagrangian Particle Tracking
Open this publication in new window or tab >>Surface Reconstruction Via Contour Metamorphosis: An Eulerian Approach With Lagrangian Particle Tracking
2005 (English)In: IEEE Visualization 05,2005, IEEE , 2005, 407-414 p.Conference paper, Published paper (Refereed)
Abstract [en]

We present a robust method for 3D reconstruction of closed surfaces from sparsely sampled parallel contours. A solution to this problem is especially important for medical segmentation, where manual contouring of 2D imaging scans is still extensively used. Our proposed method is based on a morphing process applied to neighboring contours that sweeps out a 3D surface. Our method is guaranteed to produce closed surfaces that exactly pass through the input contours, regardless of the topology of the reconstruction.

Our general approach consecutively morphs between sets of input contours using an Eulerian formulation (i.e. fixed grid) augmented with Lagrangian particles (i.e. interface tracking). This is numerically accomplished by propagating the input contours as 2D level sets with carefully constructed continuous speed functions. Specifically this involves particle advection to estimate distances between the contours, monotonicity constrained spline interpolation to compute continuous speed functions without overshooting, and stateof- the-art numerical techniques for solving the level set equations. We demonstrate the robustness of our method on a variety of medical, topographic and synthetic data sets.

Place, publisher, year, edition, pages
IEEE, 2005
Keyword
3D reconstruction, contours, level sets
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-36950 (URN)33136 (Local ID)0-7803-9462-3 (ISBN)33136 (Archive number)33136 (OAI)
Conference
16th IEEE Visualization 2005 (VIS 2005), October 23-28, Minneapolis, Minnesota, USA
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2010-10-20
2. Hierarchical RLE level set: A compact and versatile deformable surface representation
Open this publication in new window or tab >>Hierarchical RLE level set: A compact and versatile deformable surface representation
Show others...
2006 (English)In: ACM Transactions on Graphics, ISSN 0730-0301, E-ISSN 1557-7368, Vol. 25, no 1, 151-175 p.Article in journal (Refereed) Published
Abstract [en]

This article introduces the Hierarchical Run-Length Encoded (H-RLE) Level Set data structure. This novel data structure combines the best features of the DT-Grid ( of Nielsen and Museth [ 2004]) and the RLE Sparse Level Set ( of Houston et al. [ 2004]) to provide both optimal efficiency and extreme versatility. In brief, the H- RLE level set employs an RLE in a dimensionally recursive fashion. The RLE scheme allows the compact storage of sequential nonnarrowband regions while the dimensionally recursive encoding along each axis efficiently compacts nonnarrowband planes and volumes. Consequently, this new structure can store and process level sets with effective voxel resolutions exceeding 5000 x 3000 x 3000 ( 45 billion voxels) on commodity PCs with only 1 GB of memory. This article, besides introducing the H- RLE level set data structure and its efficient core algorithms, also describes numerous applications that have benefited from our use of this structure: our unified implicit object representation, efficient and robust mesh to level set conversion, rapid ray tracing, level set metamorphosis, collision detection, and fully sparse fluid simulation ( including RLE vector and matrix representations.) Our comparisons of the popular octree level set and Peng level set structures to the H- RLE level set indicate that the latter is superior in both narrowband sequential access speed and overall memory usage.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-48097 (URN)10.1145/1122501.1122508 (DOI)
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-13
3. Out-of-core and compressed level set methods
Open this publication in new window or tab >>Out-of-core and compressed level set methods
2007 (English)In: ACM Transactions on Graphics, ISSN 0730-0301, E-ISSN 1557-7368, Vol. 26, no 4, 16- p.Article in journal (Refereed) Published
Abstract [en]

This article presents a generic framework for the representation and deformation of level set surfaces at extreme resolutions. The framework is composed of two modules that each utilize optimized and application specific algorithms: 1) A fast out-of-core data management scheme that allows for resolutions of the deforming geometry limited only by the available disk space as opposed to memory, and 2) compact and fast compression strategies that reduce both offline storage requirements and online memory footprints during simulation. Out-of-core and compression techniques have been applied to a wide range of computer graphics problems in recent years, but this article is the first to apply it in the context of level set and fluid simulations. Our framework is generic and flexible in the sense that the two modules can transparently be integrated, separately or in any combination, into existing level set and fluid simulation software based on recently proposed narrow band data structures like the DT-Grid of Nielsen and Museth [2006] and the H-RLE of Houston et al. [2006]. The framework can be applied to narrow band signed distances, fluid velocities, scalar fields, particle properties as well as standard graphics attributes like colors, texture coordinates, normals, displacements etc. In fact, our framework is applicable to a large body of computer graphics problems that involve sequential or random access to very large co-dimension one (level set) and zero (e.g. fluid) data sets. We demonstrate this with several applications, including fluid simulations interacting with large boundaries (? 15003), surface deformations (? 20483), the solution of partial differential equations on large surfaces (˜40963) and mesh-to-level set scan conversions of resolutions up to ? 350003 (7 billion voxels in the narrow band). Our out-of-core framework is shown to be several times faster than current state-of-the-art level set data structures relying on OS paging. In particular we show sustained throughput (grid points/sec) for gigabyte sized level sets as high as 65% of state-of-the-art throughput for in-core simulations. We also demonstrate that our compression techniques out-perform state-of-the-art compression algorithms for narrow bands. © 2007 ACM.

Place, publisher, year, edition, pages
ACM, 2007
Keyword
Adaptive distance fields, Compression, Computational fluid dynamics, Deformable surfaces, Geometric modeling, Implicit surfaces, Level set methods, Mesh scan conversion, Morphology, Out-of-core, Shape, Streaming
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-48333 (URN)10.1145/1289603.1289607 (DOI)
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-12Bibliographically approved
4. Computing Riemannian Normal Coordinates on Triangle Meshes
Open this publication in new window or tab >>Computing Riemannian Normal Coordinates on Triangle Meshes
Show others...
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Imagine an ant walking around on the curved surface of a plant, a radio amateur planning to broadcast to a distant location across the globe or a pilot taking o from an airport - all of them are helped by egocentric maps of the world around them that shows directions and distances to various remote places. It is not surprising that this idea has already been used in cartography, where it is known as Azimuthal Equidistant Projection (AEP). If Earth is approximated by a sphere, distances and directions between two places are computed from arcs along great circles. In physics and mathematics, the same idea is known as Riemannian Normal Coordinates (RNC). It has been given a precise and general denition for surfaces (2-D), curved spaces (3-D) and generalized to smooth manifolds (N-D). RNC are the Cartesian coordinates of vectors that index points on the surface (or manifold) through the so called exponential map, which is a well known concept in dierential geometry. They are easily computed for a particular point if the inverse of the exponential map, the logarithm map, is known. Recently, RNC and similar coordinate systems have been used in computer graphics, visualization and related areas of research. In Fig. 1 for instance, RNC are used to produce a texture on the Stanford bunny through decal compositing. Given the growing use of RNC, which is further elaborated on in the next section, it is meaningful to develop accurate and reproducible techniques to compute this parameterization. In this paper, we describe a technique to compute RNC for surfaces represented by triangular meshes, which is the predominant representation of surfaces in computer graphics. The method that we propose has similarities to the Logmap framework, which has previously been developed for dimension reduction of unorganized point clouds in high-dimensional spaces, a.k.a. manifold learning. For this reason we sometimes refer to it as "Logmap for triangular meshes" or simply Logmap.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-54826 (URN)
Available from: 2010-04-15 Created: 2010-04-15 Last updated: 2013-08-28
5. Efficient computations of geodesic distance
Open this publication in new window or tab >>Efficient computations of geodesic distance
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We present a novel way to efficiently compute anisotropic distances over a tessellated domain in two dimensions. The method is based on an integral formulation of distance and entails solving a dynamic programming problem. We also present an intuitive geometric construction that is used to characterize dierent types of boundary conditions and show how they aect the resulting distance function in our and competing work.

The included benchmark study shows that our method provides signicantly better results in anisotropic regions and is faster than a current stat-of-the-art solver. Additionally, our method is straightforward to code; the test implementation is less than 150 lines of C++ code.

Keyword
Distance map, Geodesic distance, Riemannian manifolds
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-54828 (URN)
Available from: 2010-04-15 Created: 2010-04-15 Last updated: 2010-10-20

Open Access in DiVA

Cover(978 kB)79 downloads
File information
File name COVER01.pdfFile size 978 kBChecksum SHA-512
a48bf59672e2077f84646451329c00c95940b6fc4685b793a5aa04d2f8e0d09b023bb001b375bc1ef5d197970ee5e281e5576530dde9ea31f6ee6364886fc47c
Type coverMimetype application/pdf

Authority records BETA

Nilsson, Ola

Search in DiVA

By author/editor
Nilsson, Ola
By organisation
Department of Science and TechnologyThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1415 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf