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
Memory Efficient Methods for Eulerian Free Surface Fluid Animation
Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
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: urn:nbn:se:liu:diva-60852ISBN: 978-91-7393-295-0 (print)OAI: oai:DiVA.org:liu-60852DiVA: diva2:359805
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
List of papers
1. 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
2. A Spatially Adaptive Morphological Filter For Dual-Resolution Interface Tracking Of Fluids
Open this publication in new window or tab >>A Spatially Adaptive Morphological Filter For Dual-Resolution Interface Tracking Of Fluids
2010 (English)Conference paper, Published paper (Refereed)
Abstract [en]

We present a novel surface-tracking technique for free-surface fluid animations. Unlike the semi-implicit Particle Level Set method (PLS) our interface-tracking approach is purely implicit and hence avoids some of the well-known issues like surface noise and inflated memory footprints. Where PLS augments the interface with Lagrangian tracker-particles, we instead employ a higher resolution level set represented as a DT-Grid. The synchronization of our dual-resolution level sets is facilitated by a novel Spatially Adaptive Morphological (SAM) filter that attempts to preserve fine details while still avoiding spurious topology changes and boundary violations. We demonstrate that our approach can achieve comparative results to the PLS, but with a fraction of the memory footprint. We also show how our technique can be used to effectively enhance thin interface sheets at the cost of volume gain.

Place, publisher, year, edition, pages
Norrköping, Sweden: Eurographics Association, 2010
Series
EG 2010 - Short papers, ISSN 1017-4656
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-60851 (URN)
Conference
31st Annual Confererence of the European Association for Computer Graphics, 3-7 May, Norrköping, Sweden
Available from: 2010-10-28 Created: 2010-10-28 Last updated: 2010-11-16
3. A PML Based Non-Reflective Boundary for Free Surface Fluid Animation
Open this publication in new window or tab >>A PML Based Non-Reflective Boundary for Free Surface Fluid Animation
2010 (English)In: ACM Transactions on Graphics, ISSN 0730-0301, E-ISSN 1557-7368, Vol. 29, no 5, 136- p.Article in journal (Refereed) Published
Abstract [en]

This article presents a novel non-reflective boundary condition for the free surface incompressible Euler and Navier-Stokes equations. Boundaries of this type are very useful when, for example, simulating water flow around a ship moving over a wide ocean. Normally waves generated by the ship will reflect off of the boundaries of the simulation domain and as these reflected waves returns towards the ship they will cause undesired interference patterns.By employing a Perfectly Matched Layer (PML) approach we have derived a boundary condition that absorbs incoming waves and thus efficiently prevents these undesired wave reflections. To solve the resulting boundary equations we present a fast and stable algorithm based on the Stable Fluids approach. Through numerical experiments we then show that our boundaries are significantly more effective than simpler reflection preventing techniques. We also provide a thorough analysis of the parameters involved in our boundary formulation and show how they effect wave absorption efficiency.

Place, publisher, year, edition, pages
New York, NY, USA: ACM, 2010
Keyword
Computational fluid dynamics, Free surface, Stable Fluids, Euler equations, Navier-Stokes equations, Non-reflecting boundary condition, Perfectly matched layer
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-60850 (URN)10.1145/1857907.1857912 (DOI)000284285600005 ()
Available from: 2010-10-28 Created: 2010-10-28 Last updated: 2017-12-12

Open Access in DiVA

Memory Efficient Methods for Eulerian Free Surface Fluid Animation(2694 kB)2469 downloads
File information
File name FULLTEXT01.pdfFile size 2694 kBChecksum
Type fulltextMimetype application/pdf
Cover(207 kB)73 downloads
File information
File name COVER01.pdfFile size 207 kBChecksum
Type coverMimetype application/pdf

Authority records BETA

Söderström, Andreas

Search in DiVA

By author/editor
Söderström, Andreas
By organisation
Department of Science and TechnologyThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 2469 downloads
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: 1926 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