Link to Course Page
The course webpage
Overview
PointBased Rendering
Introduction and Motivation
In recent years, point sampled surface representations have emerged as a new paradigm in computer graphics. Current research in pointbased graphics includes a broad range of topics such as the study of geometry and appearance acquisition, point sampled surface processing, editing, and modeling, data structures for point sampled geometry, and, last but not least, rendering point sampled surfaces.
The objective of this project is to gain an overview of the core problem areas involved in rendering point sampled geometry. Each problem area is introduced through exemplary, uptodate research publications in the field. Understanding these contributions ideally leads to the identification of research opportunities and to ideas about how to exploit them.
Problem Areas
Visibility and surface reconstruction: The problem of determining the visiblity of points when projecting them to an image plane and reconstructing a continuous output image has been the focus of the pioneering pointrendering publication by Levoy and Whitted [Levoy:1985:PDP]. Since it is a fundamental issue, it is reconsidered in many of the more recent contributions [Zwicker:01:SSP, Rusinkiewicz:00:QSp, Ren:02:EWA].
Antialiasing: Since digital image synthesis is essentially a sampling process, antialiasing techniques are required to avoid visual artifacts. Antialiasing and reconstruction are closely related, and in [Zwicker:01:SSP] it is shown how to unify them into a single framework using socalled resampling filters.
Data structures and compression: Since pointbased rendering pipelines typically operate on large point clouds with millions of points, they rely on efficient data structures that have a small memory footprint, provide quick access to the point data, and facilitate fast warping of the points. These issues are the focus of the QSplat system [Rusinkiewicz:00:QSp], which was developed for the visualization of scanned data. More recently, a hierarchical structure that features a small memory footprint and efficient warping was introduced in [Botsch:02:EPR].
Global illumination: Only very few work has been done on using point sampled surfaces in global illumination simulations. A good starting point to this field is [Schaufler:00:RTP], however leaving open many of the challenges occurring in global illumination algorithms.
Hardware acceleration: Conventional interactive 3D graphics based on triangle meshes heavily exploits sophisticated special purpose hardware. Such hardware is not available for pointbased representations today, although it has been shown that the increasing flexibility of those processors can be exploited for pointbased rendering [Ren:02:EWA]. With graphics hardware becoming even more powerful, these opportunities will become more and more attractive, too.
Available Files:
Geometric Algorithms on Graphics Hardware
Introduction and Motivation
The high performance and increasing flexibility of 3D graphics hardware have made it an excellent candidate for solving complicated geometric problems, beyond its conventional domain of image synthesis. The set of problems include visibility culling, shadow computations, collision detection, intersection computation etc. Since the control flow of the graphics pipeline has become highly customizable, these sophisticated geometric computations can be expressed in terms of efficient multipass framebuffer operations.
The objective of this project is to gain an overview of the research done in the field of hardwareaccelerated geometric algorithms and to investigate on the capabilities of current graphics hardware. An exemplary list of research publications is given below as startingpoint for this survey.
Available Files:
 Project Abstract
 Interactive Geometric Computations with Graphics Hardware. (Siggraph Course)
 C. Everitt, M. Kilgard: Practical and Robust Stenciled Shadow Volumes for HardwareAccelerated Rendering. (NVIDIA White Paper, March 2002)
 K. Hoff, T. Culver, J. Keyser, M. Lin, and D. Manocha: Fast computation of generalized voronoi diagrams using graphics hardware.
(Proceedings of ACM SIGGRAPH 1999)
 T. J. Purcell, I. Buck, W. R. Mark, P. Hanrahan:
Ray tracing on programmable graphics hardware. (Proceedings of ACM SIGGRAPH 2002)
 K. Hoff, A. Zaferakis, M. Lin, D. Manocha: Fast 3D Geometric Proximity Queries between Rigid and Deformable Models Using Graphics Hardware Acceleration. (Technical Report, February 2002)
 N. Stewart, G. Leach, S. John:
An Improved ZBuffer CSG Rendering Algorithm. (Eurographics/Siggraph Workshop on Graphics Hardware 1998)
Physics Based Flow Simulation
Introduction and Motivation
There are two basic approaches to simulate deforming
objects. While the object related (Lagrangian) approach
is the popular method for animating elastic objects,
fluids and gases are usually simulated on an environment
related grid using an Eulerian approach. The quantities
describing the fluid (typically a scalar density field
and a velocity vector field) are evaluated for discrete
time steps at the center of grid cells or cell faces.
The scalar density field contains enough information to
visualize a gas [1]. For fluids, however, the free fluid
air surface needs to be traced and rendered. Particle
and level set methods have become popular methods to
solve this problem [2] [3]. However, for realtime
applications, these methods are too slow. Simulating
fluids in realtime is still an open research problem.
Available Files:
Physics Based Deformations/Fracture
Introduction and Motivation
Various methods to animate elastic objects have been
proposed in the past two decades such as massspring
networks, implicit surfaces and volumetric meshes in
connection with the Finite Element Method. The graphics
community has come up with new techniques to speed up
FEM such as hierarchical computations based on
hierarchical meshes and hierarchical basis functions
and the warped stiffness method.
For the simulation of fracture a volumetric representation
of an object is needed. In connection with mass spring
networks, fracture can be simulated by removing springs
when they are stretched too much. The finite element
method provides stress measures that can be used to
decide whether a crack needs to be generated. The
orientation of the crack can also be derived from the
stress tensor. One problem of simulating the fracture
process in realtime comes from the fact, that the
propagation speed of a crack tip in a brittle material
is very high. An object can shatter into several pieces
within one time step.
Available Files:
 Project Abstract
 M. Müller, J. Dorsey, L. McMillan, R. Jagnow, B. Cutler: "Stable RealTime Deformations"
 O'Brien, J. F., Bargteil, A. W., Hodgins, J. K.: "Graphical Modeling and Animation of Ductile Fracture"
 O'Brien, J. F., Hodgins, J. K.: "Graphical Modeling and Animation of Brittle Fracture"
 M. Müller, J. Dorsey, L. McMillan: "RealTime Simulation of Deformation and Fracture of Stiff Materials"
 J. Smith, A. Witkin, and D. Baraff: "Fast and controllable simulation of the shattering of brittle objects"
3D Video Compression and MPEG4
Description
As 3D Video, we define a sequence of dynamic visual data which is recorded from a realworld event and which can be visualized while navigating in both space and time, with as few constraints as possible. Apart from "normal" playback, where the sequence is rendered as fast as it was recorded, the user is able to navigate in time, while browsing through the sequence using fastforward or fastreverse, or while visualizing the sequence in slowmotion. Furthermore, the user is able to navigate in space, while choosing his viewpoint during playback.
Thus, a 3D video player should combine the interaction metaphors of both conventional 2D video recorders and 3D graphics viewers. The generation of 3D video data can be based on imagebased methods, or based on a geometric representation of the data. In any case, a huge amount of data is generated during the acquisition and processing stage, and hence the data needs to be efficiently encoded for storage and/or transmission.
Goals
The goal of this project consists in
 Analyzing existing systems, which create 3D video sequences, according to the previous definition.
 Describing to what extent these systems fit into the MPEG4 standard or ongoing MPEG standardization processes.
 Proposing how far existing 3D video systems could exploit the MPEG standard for efficient storage and interoperable handling of 3D video data.
This project is supervised by Prof. Markus Gross (grossm@inf.ethz.ch) and Edouard Lamboray (lamboray@inf.ethz.ch).
Available Files:
 Project Abstract
 S. Moezzi, A. Katkere, D. Y. Kuramura, and R. Jain. "Immersive Video."
 T. Kanade, P. Rander, and P. Narayanan. "Virtualized reality: Constructing virtual worlds from real scenes."
 S. Vedula, S. Baker, and T. Kanade. "SpatioTemporal View Interpolation"
 C. Fehn, P. Kauff, M. Op de Beeck, F. Ernst, W. IJsselsteijn, M. Pollefeys, L. Van Gool, E. Ofek and I. Sexton, "An Evolutionary and Optimised Approach on 3DTV"
 S. Würmlin, E. Lamboray, O. G. Staadt, M. H. Gross: 3D Video Recorder
 Overview of the MPEG4 standard
 Working documents on 3DAV: Draft Requirements for 3DAV, Description of Exploration Experiments in 3DAV, Status of Exploration on 3DAV
Vector field topology for feature definition in two and threedimensional velocity fields
Description
Vector field topology is concerned with structures in vector fields which are invariant
under small perturbations of the data. It is capable of describing some essential features
of a vector field by critical points including their types, by closed orbits, and by
other singularities. Vector field topology was mainly developed for the purpose of
flow visualization, making use of the knowledge provided by the related field of
dynamical systems.
In the twodimensional case, vector field topology is sufficient to characterize the vortices
present in a velocity field. It can even provide in some way a segmentation of the data domain.
While vector field topology extends to three dimensions in a straightforward way, its
application to feature definition is a current research topic. One of the main goals of that
research is to find a topologybased method for extracting vortices from steady or unsteady
velocity fields. Furthermore, by incorporating time as an additional dimension,
it becomes possible to detect bifurcations, i.e. changes in topology over time.
The general purpose of feature extraction in flow visualization is to enhance standard
visualization techniques by setting a focus on the relevant flow structures.
Depending on the type of industrial applications, such structures can be vortices, cavitations,
recirculations, shocks and others. While there are different approaches being pursued by
current research, vector field topology is believed to be one of most promising.
Available Files:
(Editing and) Sampling of Point Models
Introduction and Motivation
The 3d content creation pipeline typically consists of three major stages:
First an object is acquired using a 3d scanning device such as a laserrange scanner.
Then the acquired objects is processed, e.g. filtered, edited, textured, etc. Finally
some rendering technique is employed to display the model surface onto the screen.
Since scanners in the most general form produce a cloud of discrete point samples of
the model surface and pointbased rendering methods can produce highquality
renditions, recent research efforts have been focused on investigating the use of point
primitives for geometric processing. Examples include spectral filtering [Pauly:01:SIG],
texturing and sculpting [Zwicker:02:SIG], simplification [Pauly:02:VIS] and multi
scale modeling [Pauly:02:Tech]. Still there remain many open problems related
to the field of pointbased geometric processing.
Problem Areas
 Sampling:
The basis of pointbased geometry processing should be a rigorous sampling theory
that provides quantitative statements on optimal sampling rates and surface error.
Ideally one could imagine a framework similar to the Fourier theory for discrete
functions. First steps in understanding sampling problems for manifolds have been
taken by Amenta et al. [Amenta:98:SIG], [Amenta:99:DCG]. Work in this area would be
of a more theoretical nature, using concepts from computational geometry such as
Voronoi diagram and medial axis, to define sampling criteria and design algorithms
for surface analysis.
 Modeling
A powerful pointbased modeling system is currently being developed at the computer
graphics laboratory at ETH based on the CGL software Pointshop3D (www.pointshop3d.com)
This system features multiscale modeling functionality,
dynamic resampling for large deformations and a collisions detection algorithm that
can be combined with CSG (constructive solid geometry) operations. In this context,
many practical problems arise, including design of suitable dynamic data structures
for fast spatial queries, optimization algorithms for surface smoothing, design of
freeform deformation methods using discrete tensor fields, etc.
Pointshop3D
Pointshop3D is an interactive system for pointbased surface editing [Zwicker:02:SIG]
that provides a flexible interface for implementing different algorithms in the context
of pointbased surface editing. Examples include texture synthesis [Turk:01:SIG],
texture & geometry filtering and morphing.
Available Files:
