Information about http://webstaff.itn.liu.se/~olani/papers/Virtually%20infinite%20resolution%20deformable%20surfaces.pdf
Virtually Infinite Resolution…
Tags: avail, core data, current state, data management, data structures, disk space, geometry, grid topology, grids, infinite resolution, main memory, novel framework, ola, resolution level, rle, sentation, simulations, tations, transparent layers, virtual memory,Pages: 1
Language: english
Created: Mon May 15 13:05:23 2006
Display cached document
Page 1
Virtually Infinite Resolution Deformable Surfaces
Michael B. Nielsen1 , Ola Nilsson2 , Andreas S¨ derstr¨ m2 , and Ken Museth1,2
o o
1 University °
of Arhus 2 Link¨ ping
o University
1 Introduction and previous work
We present a novel framework that allows for level set simulations
at virtually infinite resolutions - the only limitation being the avail-
able disk space. The key components are transparent layers that
combine fast out-of-core data management with efficient compres-
sion. For out-of-core simulations our framework is significantly
faster than OS-based virtual memory schemes. In addition, exten-
sive tests have shown our framework to sustain throughputs that are
about 65% of current state-of-the-art for in-core simulations.
A level set is essentially a time-dependent implicit geometry repre-
sentation and has proven very popular for deforming surface prob-
lems. Several data structures for high resolution level sets and flu-
ids have recently been proposed (e.g. DT-Grid[Nielsen and Museth
2006] and H-RLE[Houston et al. 2006]). However, all of these ap-
proaches are effectively restricted by the main memory available -
typically a few GB. Common to these state-of-the-art grid represen-
tations is that they separately encode grid topology and values. Our
framework can transparently be integrated with any of these grids,
thus requiring minimal transition overhead in an existing pipeline.
In addition it utilizes the virtually infinite size of today's disks or ar-
rays, as well as reduces disk space and memory footprints by means
of efficient compression. Many important graphics applications can
directly benefit from our work. We present several examples, in-
cluding a level set of resolution 300003 which we believe to be Figure 2: Fluid animation using our out-of-core framework.
an order of magnitude larger than ever demonstrated before.
for maximal flexibility for a particular application.
2 Out-of-core and compression framework
3 Applications
¡ ¢ ¡ £ ¡ ¤ ¥
Component
Fluid Animations: The out-of-core framework allows us to sig-
Model Grid Slice Cache Memory
¦ § £ ¨ ©
Codec
nificantly increase the resolutions of fluid animations beyond the
memory available. In our current implementation particles, sur-
Storage
Handler
Or Storage Cache Disk face velocities and DT-Grid based level set surfaces and boundaries
are stored out-of-core. Fluid velocities and pressure are kept un-
Figure 1: Our framework for out-of-core and compressed level sets and fluids. compressed in-core. Fig. 2 shows a fountain simulation using a
statue with an effective resolution of 5123 as the boundary. The
An overview of our framework is illustrated in figure 1. From left peak memory footprint for this out-of-core simulation was 711 MB
to right: The level set or fluid is represented on a sparse 3D com- compared to an estimated 3.7GB if run in-core. Using a standard
putational Grid. The Slice Cache temporarily buffers 2D slices of ATA harddrive the throughput of the out-of-core simulation was
this grid needed to compute finite differences during simulations. about half of the throughput of an in-core simulation.
The rest of the grid is stored compressed in-core or out-of-core.
Surface Deformations: We have created a detailed level set CSG
The Slice Cache provides both efficient sequential and random ac-
bunny (1.62GB) modeled as an out-of-core CSG intersection of a
cess to grid points in a local stencil. As the simulation computations
20483 bunny (304MB) with a tiling of 203 smaller bunnies each at
progress through the grid, the slices are replaced and streamed, pos-
resolution 1283 (7.47GB). Sizes are in uncompressed DT-Grid for-
sibly compressed, to and from memory and disk. The staggered
mat. An out-of-core morph between the bunny and the CSG bunny
boxes shown on the right illustrate that the Topology and numer-
that required close to 5GB of storage was run on a PC with 1GB
ical Values of the grid are processed separately. This can for in-
memory and is shown in the supplementary video. The throughput
stance be utilized for ray-tracing where the topology can be kept
was equal to 65% of the DT-Grid throughput for in-core simula-
in-core and numerical values stored out-of-core. The Component
tions. Using an efficient out-of-core scan converter we have gener-
Codecs take advantage of application specific knowledge to obtain
ated level sets of resolution 300003 and requiring 24GB storage.
good compression. The topology is compressed using statistical en-
coding with local predictions based on Lagrange polynomials and PDEs on Surfaces: We have run several simulations directly on
planar approximations. Context-based encoding further increases the level set manifold. In the video we show the wave equation on
the compression. The numerical values of the grid are compressed models of sizes above 10243 requiring several GB of memory.
using multi-dimensional differential encodings which we show to References
out-perform existing high-preformance codecs. A Storage Handler
H OUSTON , B., N IELSEN , M., BATTY, C., N ILSSON , O., AND M USETH , K. 2006.
stores the grid components in memory or on disk, and a Storage
Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Repre-
Cache efficiently implements our out-of-core scheme by combin- sentation. ACM Transactions on Graphics 25, 1, 124.
ing novel prefetching and page-replacement techniques optimized N IELSEN , M. B., AND M USETH , K. 2006. Dynamic Tubular Grid: An efficient
for the access patterns of level set and fluid simulations. The com- data structure and algorithms for high resolution level sets. Journal of Scientific
ponents of our framework can be combined arbitrarily which allows Computing ISSN: 0885-7474.