Publications

Papers

GPU Gems 3 Chapter 'LCP Algorithms for Collision Detection Using CUDA'
P. Kipfer
GPU Gems 3 [BibTex]
[link]
[demo]
In this chapter, we use CUDA to accelerate convex collision detection, and we study a parallel implementation of Lemke's algorithm (also called the complementary pivot algorithm) for the linear complementarity problem (LCP). Important LCP applications are linear and quadratic programming, two-person games, boundary-value problems, and the determination of the convex hull of points in a plane.
Realistic and Interactive Simulation of Rivers
P. Kipfer, R. Westermann
Graphics Interface 2006 [BibTex]
[paper]
[slides]
[demo]
In this paper we present interactive techniques for physics-based simulation and realistic rendering of rivers using Smoothed Particle Hydrodynamics. We describe the design and implementation of a grid-less data structure to efficiently determine particles in close proximity and to resolve particle collisions. Based on this data structure, an efficient method to extract and display the fluid free surface from elongated particle structures as they are generated in particle based fluid simulation is presented. The proposed method is far faster than the Marching Cubes approach, and it constructs an explicit surface representation that is well suited for rendering. The surface extraction can be implemented on the GPU and only takes a fraction of the simulation time step. It is thus amenable to real-time scenarios like computer games and virtual reality environments.
GPU Construction and Transparent Rendering of Iso-Surfaces
P. Kipfer, R. Westermann
Vision, Modelling and Visualization 2005 [BibTex]
[paper]
[color]
[images]
[slides]
[demo]
In this paper, we present a novel edge-based approach that avoids redundant computations of edge-surface intersections. We show how to achieve a significant performance gain by considering intrinsic features of recent GPUs. The iso-surface extraction process is re-formulated in a way that reduces both numerical computations and memory access operations. A span-space data structure allows us to avoid the processing of elements not intersected by the selected surface. Finally, to allow for the rendering of transparent surfaces, a GPU sorting routine is integrated into the rendering pass. Our applications show numerical simulation results, distance volumes and advanced shading effects.
GPU Gems 2 Chapter 'Improved GPU Sorting'
P. Kipfer, R. Westermann
GPU Gems 2 [BibTex]
[link]
[demo]
Sorting is one of the most important algorithmic building blocks in computer science. Being able to efficiently sort large amounts of data is a critical operation. Although implementing sorting algorithms on the CPU is relatively straightforward - mostly a matter of choosing a particular sorting algorithm to use - sorting on the GPU is less easily implemented because the GPU is effectively a highly parallel SIMD architecture. Given that the GPU can outperform the CPU both for memory-bound and compute-bound algorithms, finding ways to sort efficiently on the GPU is important. Furthermore, because reading back data from the GPU to the CPU to perform operations such as sorting is inefficient, sorting the data on the GPU is preferable.
UberFlow: A GPU-Based Particle Engine
P. Kipfer, M. Segal, R. Westermann
Graphics Hardware 2004 [BibTex]
[paper]
[slides]
[demo]
We present a system for real-time animation and rendering of large particle sets using GPU computation and {\it memory objects} in OpenGL. Memory objects can be used both as containers for geometry data stored on the graphics card and as render targets, providing an effective means for the manipulation and rendering of particle data on the GPU. To fully take advantage of this mechanism, efficient GPU realizations of algorithms used to perform particle manipulation are essential. Our system implements a versatile particle engine, including inter-particle collisions and visibility sorting. By combining memory objects with floating-point fragment programs, we have implemented a particle engine that entirely avoids the transfer of particle data at run-time. Our system can be seen as a forerunner of a new class of graphics algorithms, exploiting memory objects or similar concepts on upcoming graphics hardware to avoid bus bandwidth becoming the major performance bottleneck.
Local Exact Particle Tracing on Unstructured Grids
P. Kipfer, F. Reck, G. Greiner
Computer Graphics Forum 2003 [BibTex]
[paper]
For interactive exploration of large data sets, a very efficient and reliable particle tracing method is needed. For data on unstructured grids and data sizes, as they appear in simulations of wind channel experiments or flight simulations, the traditional approach, based on numerical integration methods of ordinary differential equations does not allow sufficiently accurate path calculation at the speed required for interactive use. In this paper we extend the local exact approach of Nielson and Jung in such a way that it can be used for interactive particle tracing in large data sets of steady flow simulation experiments. This will be achieved by sophisticated preprocessing using additional memory. For further visual enhancement of the streamline we construct an implicitly defined smooth Bézier curve that is used for ray tracing.
image GRIDLIB: A Parallel, Object-oriented Framework for Hierarchical-hybrid Grid Structures in Technical Simulation and Scientific Visualization
P. Kipfer, F. Hülsemann, S. Meinlschmidt, B. Bergen, G. Greiner, U. Rüde
High Performance Computing in Science and Engineering
This paper presents the gridlib software framework for integrated simulation and visualization. It provides modern object-oriented programming methods for supercomputer applications. While allowing the reuse of existing simulation codes, it enables writing new applications using advanced programming techniques. In this paper, we also present the concept of hierarchical hybrid grids as an efficient and flexible grid data structure for large scale computations. The resulting enormous amounts of data of nowadays applications can be visualized directly on the supercomputer as an integrated part of the whole simulation cycle, avoiding the typical bottleneck of supercomputers: external communication channels.
Parallel Rendering within the Integrated Simulation and Visualization Framework GRIDLIB
P. Kipfer, G. Greiner
Vision, Modelling and Visualization 2001
[paper]
Over the last years, computational fluid dynamics (CFD) research has developed several advanced numeric methods for simulating fluid transport. The models being used have grown considerably in size and so have the computed results. Computer graphics research has developed efficient methods for visualization and rendering, to create images of the computed result that contain significant information. The whole process of using CFD methods in engineering however involves many iterations through the model-simulation-visualization cycle. When using reasonably detailed models, the whole cycle suffers from delays produced by the necessary data conversion and data transport. We have developed a solution to this problem by designing an object-oriented framework for integrating simulation and visualization. Computation routines are free to use the provided grid management interface or can be integrated on a binary level by specifying the expected memory layout to the framework. Both simulation and visualization algorithms can be run on the parallel computer. The rendering subsystem therefore has access to the full grid resolution to produce images of high visual quality.
Interactive Visualization of Flows using LIC and Video Streaming Techniques
P. Kipfer, G. Greiner
Vision, Modelling and Visualization 2000
[paper]
For the visualization of subtle structures in vector fields, the line integral convolution (LIC) method has proven to be of great value. When trying to display 3D LIC volumes of flow fields, the possibility of comprehensive and convenient interactive exploration of the volume becomes a crucial point, because of the amount of information present in the volume. Previous work has shown how to efficiently make use of 3D texture rendering techniques to enable interactivity. Based on this approach, we present a stream-oriented solution to animated 3D LIC volumes, integrating stationary and non-stationary flow simulations. We further show how particle transport is integrated in order to enhance the spatial understanding and produce animations that also show the absolute value and the sign of velocity in the flow field. Our approach is flexible enough to support multiple implementations and makes efficient use of available hardware. It integrates nicely with other approaches to enhance the visual quality.
Transparent Distributed Processing for Rendering
P. Kipfer, Ph. Slusallek
Parallel Visualization and Graphics 1999
[paper]
Rendering, in particular the computation of global illumination, uses computationally very demanding algorithms. As a consequence many researchers have looked into speeding up the computation by distributing it over a number of computational units. However, in almost all cases did they completely redesign the relevant algorithms in order to achieve high efficiency for the particular distributed or parallel environment. In this paper we present a top-down approach for designing distributed applications based on their existing object-oriented decomposition. Distribution logic, in our case based on the CORBA middleware standard, is introduced transparently to the existing application logic. The design approach is demonstrated using several examples of multi-pass global illumination computation and ray-tracing. The results show that a good speedup can usually be obtained even with minimal intervention into existing applications.

Papers co-authored

A Particle System for Interactive Visualization of 3D Flows
J. Krüger, P. Kipfer, P. Kondratieva, R. Westermann
IEEE Transactions on Visualization and Computer Graphics [BibTex]
[paper]
We present a particle system for interactive visualization of steady 3D flow fields on uniform grids. For the amount of particles we target, particle integration needs to be accelerated and the transfer of these sets for rendering must be avoided. To fulfill these requirements, we exploit features of recent graphics accelerators to advect particles in the graphics processing unit (GPU), saving particle positions in graphics memory, and then sending these positions through the GPU again to obtain images in the frame buffer. This approach allows for interactive streaming and rendering of millions of particles, and it enables virtual exploration of high resolution fields in a way similar to real-world experiments. The ability to display the dynamics of large particle sets using visualization options like shaded points or oriented texture splats provides an effective means for visual flow analysis that is far beyond existing solutions. For each particle, flow quantities like vorticity magnitude and λ2 are computed and displayed. Built upon a previously published GPU implementation of a sorting network, visibility sorting of transparent particles is implemented. To provide additional visual cues, the GPU constructs and displays visualization geometry like particle lines and stream ribbons.
Numerical Simulations on PC Graphics Hardware
J. Krüger, T.Schiwietz, P. Kipfer and R. Westermann
Parsim 2004 [BibTex]
[paper]
On recent PC graphics cards, fully programmable parallel geometry and pixel units are available providing powerful instruction sets to perform arithmetic and logical operations. In addition to computational functionality, pixel (fragment) units also provide an efficient memory interface to local graphics data. In this paper, we will demonstrate the benefits of commodity graphics hardware for the parallel implementation of general techniques of numerical computing.
image Client-Server-Visualisierung zwischen Supercomputer und PC mit GRIDLIB
S. Meinlschmidt, P. Kipfer, U. Labsik, G. Greiner
Simulation und Visualisierung 2003
text
GRIDLIB: Flexible and Efficient Grid Management for Simulation and Visualization
F. Hülsemann, P. Kipfer, U. Rüde, G. Greiner
ICCS 2002
[paper]
This paper describes the gridlib project, a unified grid management framework for simulation and visualization. Both, adaptive PDE-solvers and interactive visualization toolkits, have to manage dynamic grids. The gridlib meets the similar but not identical demands on grid management from the two sides, visualization and simulation. One immediate advantage of working of working on a common grid is the fact that visualization has direct access to the simulation results, which eliminates the need for any form of data conversion. Furthermore, the gridlib provides support for unstructured grids, the re-use of existing solvers, the appropriate use of hardware in the visualization pipeline, grid adaptation and hierarchical hybrid grids. The present paper shows how these features have been included in the gridlib design to combine run-time efficiency with the flexibility necessary to ensure wide applicability. The functionality provided the gridlib helps to speed up program development for simulation and visualization alike.
Progressive Isosurface Extraction from Tetrahedral Meshes
U. Labsik, S. Meinlschmidt, P. Kipfer, G. Greiner
Pacific Graphics 2001
[paper]
In this paper we present techniques for transforming a tetrahedral mesh into a progressive representation based on half edge collapses. This allows the efficient transmission of the mesh from a remote computer where the simulation was computed to a visualization computer. During the transmission the user can start visualizing while the transmission is still in progress. We show a technique for progressively extracting isosurfaces from the progressive mesh. Starting with the base mesh an isosurface for a specific value is computed and will locally be improved where a vertex is inserted to the mesh.

My Theses

Distribution and Parallelization Strategies for Integrated Simulation, Visualization and Rendering Systems
P. Kipfer
PhD Thesis
[paper]
This thesis examines several principal strategies for handling distribution and parallelization. A classication is worked out to demarcate the areas of application. Using these strategies, a library for integrated simulation, visualization and rendering on supercomputers and desktop systems is implemented. It offers a clear separation of functionality by employing several abstraction levels to the programmer. Therefore, this thesis presents a substantial contribution to scientic computing to cope with grandchallenge problems. It supplies the enabling key technology for efcient post-processing for visualization and rendering on the supercomputer.
image Verteilte Beleuchtungssimulation mit CORBA
P. Kipfer
Diplomarbeit: Struktur des verteilten Vision-Systems
text

Talks, Presentations and Technical Reports

An Object Oriented Approach for High Performance Simulation and Visualization on Adaptive Hybrid Grids
First SIAM Conference on Computational Science and Engineering
23.11.2000, Washington
Distributed Lighting and Rendering on Shared-memory Multiprocessor Machines
SCI Institute, School of Computing, University of Utah
12.10.1999
gridlib: Advanced object-oriented programming paradigms
P. Kipfer
report 4/01: for internal use only
gridlib: Numerical Methods
P. Kipfer
report 2/01: for internal use only
Visualizing the Structure and Quality Properties of Tetrahedral Meshes
U. Labsik, P. Kipfer, G. Greiner
report 2/00
gridlib: System Design
P. Kipfer
report 4/00: for internal use only
Distributed Lighting Networks [paper]
P. Kipfer
report 3/99: A case study of application-oriented distribution patterns on the Vision system