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
Out-of-core and compressed level set methods
University of Århus, Denmark.
Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
Linköping University, Department of Science and Technology, Digital Media. Linköping University, The Institute of Technology.
Linköping University, Department of Science and Technology, Digital Media. Linköping University, The Institute of Technology.
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. Vol. 26, no 4, 16- p.
Keyword [en]
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: urn:nbn:se:liu:diva-48333DOI: 10.1145/1289603.1289607OAI: oai:DiVA.org:liu-48333DiVA: diva2:269229
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-12Bibliographically approved
In thesis
1. Level-set methods and geodesic distance functions
Open this publication in new window or tab >>Level-set methods and geodesic distance functions
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:nbn:se:liu:diva-54830 (URN)978-91-7393-524-1 (ISBN)
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
2. Memory Efficient Methods for Eulerian Free Surface Fluid Animation
Open this publication in new window or tab >>Memory Efficient Methods for Eulerian Free Surface Fluid Animation
2010 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis focuses on improving and extending the available toolset for Eulerian, i.e. grid based, free surface fluid animation and level set based surface tracking in the context of computer graphics and visual effects. More specifically three novel methods are presented each aimed towards reducing the amount of computer memory required for producing high resolution animations of incompressible free surface fluids. Each method is primarily developed for, but not limited to, the popular Stable Fluids method.

Eulerian free surface fluid animation has historically required a large amount of computer memory, especially when high resolution results are desired. This problem has recently been addressed through the development of dynamic computational grids like the Dynamic Tubular Grid (DT-Grid) for level set computations. However, when animating free surface fluids a large amount of tracker particles are often added to the level set geometry in order to provide more accurate tracking of fluid surfaces. As a result the particle level set (PLS) method typically requires two orders of magnitude more memory than a DT-Grid level set. In order to reduce the gap in memory requirement between the level set and the particles this thesis introduces a fast and efficient compression method for such tracker particles. This compression is optionally combined with a specialized external memory algorithm that allows particle and level set data to be efficiently streamed back and forth between primary memory and secondary storage devices such as hard disk drives. The particle compression scheme is able to reduce the size of a DT-Grid particle level set by more than 65% while only inducing a 5% penalty to performance. If combined with the external memory algorithm particle level sets of virtually any size and resolution can be used in free surface fluid animations. The induced performance penalty of the combined scheme depends on the performance of the external storage device, however when using a traditional hard disk drive a 70% increase in simulation time was measured.

This thesis also presents a purely Eulerian alternative to the PLS method through the introduction of a dual resolution level set representation. The method replaces the tracker particles with a level set of higher resolution, thus significantly increasing surface tracking accuracy compared to the unaided level set. The scheme is able to produce high quality results using up to 94% less memory than a PLS. The core component of the method is the Spatially Adaptive Morphology (SAM) filter which connects the high resolution representation of the level set with the lower resolution fluid, thus providing plausable animation also for small and/or thin surface features. A sheet preserving extension to the SAM filter is also presented that is able to preserve thin sheets of fluid indefinitely if so desired. Although this method adds mass to the simulation it is highly useful for animating phenomena like splashes, fountains and waterfalls.

The final method presented in this thesis concerns the efficient local animation of oceans and other very large free surface fluids.For such scenarios large amounts of memory and computation time can be saved by only computing accurate fluid physics in a local fluid region immediately surrounding a point of interest. The fluid outside this region can then be animated using less accurate but significantly faster and less memory demanding models. However, for this approach to be accurate the local fluid must be contained in such a way that it behaves as if still part of a larger fluid. This thesis enables the local simulation of a larger body of fluid by introducing three different non-reflective boundary conditions for free surface fluid animation using a modified Stable Fluids method. Two simple wave dampening boundaries are presented as well as a significantly more advanced wave absorbing boundary based on the Perfectly Matched Layer (PML) approach. All three boundaries are shown to be effective in preventing wave reflection given large enough boundary regions. However the PML boundary is significantly more efficient, typically absorbing waves at a fraction of the distance required by the other two methods.

Place, publisher, year, edition, pages
Linköping: Linköping Universisty Electronic Press, 2010. 138 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1345
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-60852 (URN)978-91-7393-295-0 (ISBN)
Public defence
2010-12-03, K3, Kåkenhus, Campus Norrköping, Linköpings Universitet, Norrköping, 09:30 (English)
Opponent
Supervisors
Available from: 2010-11-16 Created: 2010-10-28 Last updated: 2016-03-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Nilsson, OlaSöderström, AndreasMuseth, Ken

Search in DiVA

By author/editor
Nilsson, OlaSöderström, AndreasMuseth, Ken
By organisation
Department of Science and TechnologyThe Institute of TechnologyDigital Media
In the same journal
ACM Transactions on Graphics
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 440 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