Michael B. Nielsen
Now researcher
at Weta Digital
Postdoc, PhD
Department of Computer Science, Aarhus
University, Denmark
Funded by the Danish Agency
for Science, Technology and Innovation
Contact
Email: mbnielsen AT acm
DOT org
Phone: +45 29699756
Web: http://www.cs.au.dk/~bang
The Dynamic
Tubular Grid (DT-Grid) was used to create fluid effects in Pirates
of the Caribbean 3.
Source Code
DT-Grid source code is available via Google Code here.
Current release v.0.92 (May 9, 2010).
Relevant papers including my dissertation can be found
below.
Recent Publications
|
|
Abstract: Smoke
animations are hard to art-direct because simple changes in parameters such
as simulation resolution often lead to unpredictable changes in the final
result. Previous work has addressed this problem with a guiding approach
which couples low-resolution simulations – that exhibit the desired flow and behaviour – to the final, high-resolution simulation.
This is done in such a way that the desired low frequency features are to
some extent preserved in the high-resolution simulation. However, the steady
(i.e. constant) guiding used often leads to a lack of sufficiently high
detail, and employing time-dependent guiding is expensive because the matrix
of the resulting set of equations needs to be recomputed at every iteration.
We propose an improved mathematical model for Eulerian-based
simulations which is better suited for dynamic, time-dependent guiding of
smoke animations through a novel variational
coupling of the low- and high-resolution simulations. Our model results in a
matrix that does not require re-computation when the guiding changes over
time, and hence we can employ time-dependent guiding more efficiently both in
terms of storage and computational requirements. We demonstrate that
time-dependent guiding allows for more high frequency detail to develop
without losing correspondence to the low resolution simulation. Furthermore,
we explore various artistic effects made possible by time-dependent guiding. |
|||||||
|
Paper |
||||||||
|
Michael B. Nielsen and Brian B. Christensen |
||||||||
|
Eurographics 2010, to appear |
||||||||
|
Video |
||||||||
|
|
Abstract:
We propose a novel approach to guiding of Eulerian-based
smoke animations through coupling of simulations at different grid
resolutions. Specifically we present a variational
formulation that allows smoke animations to adopt the low-frequency features
from a lower resolution simulation (or non-physical synthesis), while
simultaneously developing higher frequencies. The overall motivation for this
work is to address the fact that art-direction of smoke animations is
notoriously tedious. Particularly a change in grid resolution can result in
dramatic changes in the behavior of smoke
animations, and existing methods for guiding either significantly lack high
frequency detail or may result in undesired features developing over time.
Provided that the bulk movement can be represented satisfactorily at low
resolution, our technique effectively allows artists to
prototype simulations at low resolution (where computations are fast) and
subsequently add extra details without altering the overall “look and
feel”. Our implementation is based on a customized multi-grid solver with
memory-efficient data structures. |
|||||||
|
Paper |
Guiding of Smoke Animations
Through Variational Coupling of Simulations at
Different Resolutions |
|||||||
|
Michael B. Nielsen, Brian B. Christensen, Nafees Bin
Zafar, Doug Roble and Ken Museth |
||||||||
|
ACM
SIGGRAPH/Eurographics Symposium on Computer
Animation, 2009, pp. 217-226. |
||||||||
|
Video |
||||||||
|
|
Abstract: The simulation of physical processes on interfaces
and a variety of applications in geometry processing and geometric modeling are based on the solution of partial
differential equations on curved and evolving surfaces. Frequently, an
implicit level set type representation of these surfaces is the most
effective and computationally advantageous approach. This paper addresses the
computational problem of how to solve partial differential equations on
highly resolved level sets with an underlying very high-resolution discrete
grid. These high-resolution grids are represented in a very efficient Dynamic
Tubular Grid encoding format for a narrow band. A reaction diffusion model on
a fixed surface and surface evolution driven by a nonlinear geometric
diffusion approach, by isotropic, or truly
anisotropic curvature motion are investigated as characteristic model
problems. The proposed methods are based on semi-implicit finite element discretizations directly on these narrow bands, require
only standard numerical quadrature and allow for large time steps. To combine
large time steps with a very thin and thus storage inexpensive narrow band,
suitable transparent boundary conditions on the boundary of the narrow band
and a nested iteration scheme in each time step are investigated. This nested
iteration scheme enables the discrete interfaces to move in a single time
step significantly beyond the domain of the narrow band of the previous time
step. Furthermore, algorithmic tools are provided to assemble finite element
matrices and to apply matrix vector operators via fast, cache-coherent access
to the Dynamic Tubular Grid encoded data structure. The consistency of the
presented approach is evaluated and various numerical examples show its
application potential. |
|||||||
|
Paper |
Finite Element
Methods on Very Large, Dynamic Tubular Grid Encoded Implicit Surfaces |
|||||||
|
Oliver Nemitz, Michael Bang Nielsen, Martin Rumpf and Ross Whitaker |
||||||||
|
SIAM
Journal of Scientific Computing, Vol. 31, No. 3. pp. 2258-2281. |
||||||||
|
|
Abstract:
Physical simulation on surfaces and various applications in geometry
processing are based on partial differential equations on surfaces. The
implicit representation of these eventually evolving surfaces in terms of
level set methods leads to effective and flexible numerical tools. This paper
addresses the computational problem of how to solve partial differential
equations on level sets with an underlying very high-resolution discrete
grid. These high-resolution grids are represented in a very efficient
format, which stores only grid points in a thin narrow band. Reaction
diffusion equations on a fixed surface and the evolution of a surface under
curvature motion are considered as model problems. The proposed methods are
based on a semi implicit finite element discretization directly on these thin
narrow bands and allow for large time steps. To ensure this, suitable
transparent boundary conditions are introduced on the boundary of the narrow
band and the time discretization is based on a nested iteration scheme.
Methods are provided to assemble finite element matrices and to apply matrix
vector operators in a manner that do not incur additional overhead and give
fast, cache-coherent access to very large data sets. |
|||||||
|
Paper |
Narrow Band Methods
for PDEs on Very Large Implicit Surfaces |
|||||||
|
Oliver Nemitz, Michael Bang Nielsen, Martin Rumpf and Ross Whitaker |
||||||||
|
|
Dissertation |
Efficient
and High Resolution Level Set Simulations - Data Structures, Algorithms and
Applications |
||||||
|
|
Abstract: This
paper 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 paper 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 (1500^3), surface deformations (2048^3),
the solution of partial differential equations on large surfaces (4096^3) and
mesh-to-level set scan conversions of resolutions up to 35000^3 (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 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. |
|||||||
|
Paper |
||||||||
|
Michael Bang Nielsen, Ola Nilsson, Andreas Söderström and Ken Museth |
||||||||
|
ACM Transactions on Graphics 26(4) (Presented at SIGGRAPH 2008, Partial Differential Equations paper session), October 2007. (Accepted August 2, 2007. Conditionally accepted November 20, 2006). |
||||||||
|
Technical Sketch |
||||||||
|
Michael Bang Nielsen, Ola Nilsson, Andreas Söderström and Ken Museth |
||||||||
|
ACM SIGGRAPH 2006 (August 1 2006) |
||||||||
|
Video |
||||||||
|
|
Abstract: This
paper 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 non-narrow band regions while the dimensionally recursive encoding
along each axis efficiently compacts non-narrow band 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 1GB of memory. This paper,
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 narrow band sequential access speed and
overall memory usage. |
|||||||
|
Paper |
Hierarchical RLE Level Set: A
Compact and Versatile Deformable Surface Representation |
|||||||
|
Ben Houston Michael Bang Nielsen, Christopher Batty, Ola Nilsson and
Ken Museth |
||||||||
|
ACM Transactions on Graphics 25(1), January 2006. Pages 151-175. (Accepted October 22, 2005. Conditionally accepted for SIGGRAPH, April 4, 2005). |
||||||||
|
Technical sketch |
||||||||
|
Ben Houston, Michael Bang Nielsen, Christopher Batty, Ola Nilsson and
Ken Museth |
||||||||
|
ACM SIGGRAPH 2005.(July 31 2005) |
||||||||
|
Video |
||||||||
|
|
Abstract: Level set methods [Osher88] have proved very
successful for interface tracking in many different areas of computational
science. However, current level set methods are limited by a poor balance
between computational efficiency and storage requirements. Tree-based methods
have relatively slow access times, whereas narrow band schemes lead to very
large memory footprints for high resolution interfaces. In this paper we
present a level set scheme for which both computational complexity and
storage requirements scale with the size of the interface. Our novel level
set data structure and algorithms are fast, cache efficient and allow for a
very low memory footprint when representing high resolution level sets. We
use a time-dependent and interface adapting grid dubbed the ``Dynamic Tubular
Grid'' or DT-Grid. Additionally, it has been optimized for advanced
finite difference schemes currently employed in accurate level set
computations. As a key feature of the DT-Grid the associated interface
propagations are not limited to any computational box and can expand freely.
We present several numerical evaluations, including a level set simulation on
a grid with an effective resolution of 1024^3. |
|||||||
|
Paper
|
Dynamic Tubular Grid: An Efficient
Data Structure and Algorithms for High Resolution Level Sets. |
|||||||
|
Michael Bang Nielsen and Ken Museth |
||||||||
|
Journal of Scientific Computing
26(3). March 2006. Pages 261-299. ISSN: 0885-7474 (Paper) 1573-7691
(Online) (Submitted November 12, 2004. Accepted January 26, 2005. Published
Online January 6, 2006). |
||||||||
|
Video |
||||||||
|
Technical Report
|
Dynamic Tubular Grid: An Efficient Data
Structure and Algorithms for High Resolution Level Sets. |
|||||||
|
Michael Bang Nielsen and Ken Museth |
||||||||
|
Linköping Electronic Articles in Computer and Information Science, Vol. 9(001), 2004, ISSN 1401-9841. (November 11, 2004). |
||||||||
|
Technical sketch |
An Optimized, Grid Independent,
Narrow Band Data Structure for High Resolution Level Sets |
|||||||
|
Michael Bang Nielsen and Ken Museth |
||||||||
|
SIGRAD 2004. (November 24, 2004). |
||||||||
|
|
|
|
|
|
||||
