Computer Graphics Laboratory

CGL » Teaching » Former Courses

Combinatorics, Geometry and Computation (SS 03) - Home

Home | Course Notes | Exercises | Schedule
Combinatorics, Geometry and Computation

Link to Course Page

The course webpage

Overview

 Point-Based Rendering

Introduction and Motivation

In recent years, point sampled surface representations have emerged as a new paradigm in computer graphics. Current research in point-based 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, up-to-date 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 point-rendering 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 so-called resampling filters.
Data structures and compression: Since point-based 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 point-based representations today, although it has been shown that the increasing flexibility of those processors can be exploited for point-based 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 multi-pass framebuffer operations.
The objective of this project is to gain an overview of the research done in the field of hardware-accelerated geometric algorithms and to investigate on the capabilities of current graphics hardware. An exemplary list of research publications is given below as starting-point for this survey.

Available Files:

 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 real-time applications, these methods are too slow. Simulating fluids in real-time 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 mass-spring 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 real-time 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:

 3D Video Compression and MPEG-4

Description

As 3D Video, we define a sequence of dynamic visual data which is recorded from a real-world 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 fast-forward or fast-reverse, or while visualizing the sequence in slow-motion. Furthermore, the user is able to navigate in space, while choosing his view-point 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 image-based 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 MPEG-4 standard or on-going 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:

 Vector field topology for feature definition in two- and three-dimensional 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 two-dimensional 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 straight-forward way, its application to feature definition is a current research topic. One of the main goals of that research is to find a topology-based 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 laser-range 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 point-based rendering methods can produce high-quality 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 point-based geometric processing.

Problem Areas

  • Sampling:
    The basis of point-based 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 point-based 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 multi-scale 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 free-form deformation methods using discrete tensor fields, etc.

Pointshop3D


Pointshop3D is an interactive system for point-based surface editing [Zwicker:02:SIG] that provides a flexible interface for implementing different algorithms in the context of point-based surface editing. Examples include texture synthesis [Turk:01:SIG], texture & geometry filtering and morphing.

Available Files:




© 2024 ETH Zurich, Computer Graphics Laboratory