Completed thesis projects in computer graphics

Camera Focus Controlled by Face Detection on GPU

There are several applications for fast face detection including surveillance, tracking and numerous other. Detection is however rather computationally heavy and not all devices can be equipped with a dedicated hardware for this purpose. As camera equipped phones are now industry standard there is a huge interest in bringing face detection to these platform at a low cost. GPGPU graphics will soon be available on mobile phones and thus making it possible to utilize the graphics pipeline for computations. In this thesis we have investigated how to implement face detection on a prototype platform with OpenGL|ES 2.0 support. We have also generated the statistics needed for the chosen detection method and implemented a reference application.

Student: Karl Berggren and Pär Gregersson

Supervisor: Jon Hasselgren

Font Rasterization for Mobile Devices

Writing memory efficient and fast vector font rendering software for mobile devices can prove quite a challenge. This is the premise for this thesis. Two widely different vector based rasterizer algorithms were examined, one triangle- and one plane sweep-algorithm. Memory efficiency, speed and rendering quality was measured. To enable these measurements, the rasterizers were implemented in C and compared to each other, as well as to the leading open-source rasterizer found in the font rendering library FreeType. It was found that the triangle rasterizer always used less memory than FreeType [3] for font sizes smaller than 60 pixels. The plane sweep rasterizer, in turn, was about 10-15% faster than FreeType, given the right parameters, when test run on a desktop computer. Depending on specific demands, either of the rasterizers described in this report can be useful for mobile systems, although the triangle rasterizer will probably benefit from the use of new technology such as hardware acceleration on mobile devices in the future.

Student: Magnus Andersson

Supervisor: Tomas Akenine-Möller

Stochastic Depth of Field using Hardware Accellerated Rasterization

Depth of field is a desired, but computationally expensive effect in computer graphics. A number of algorithms exist, each having distinct drawbacks or limitations. Accumulation buffering is readily hardware accelerated but requires much computation time in order to eliminate unnatural artifacts. Post-processing techniques are popular because of their performance but are inaccurate. Stochastic ray tracing gives excellent quality but is computationally intense and not easily accelerated using contemporary graphics hardware.

In this thesis, we implement stochastic rasterization on contemporary GPUs, and it is shown to be as efficient as accumulation buffering with comparable image quality with less obvious artifacts. We show that it is already viable to use stochastic rasterization in real-time applications, although several graphics hardware optimizations are unavailable using this technique. Some of these optimizations can be extended to support stochastic rasterization with only slight hardware modifications, making the proposed method likely to outperform accumulation buffering for depth of field effects.

Students: Robert Toth and Erik Linder

Supervisors: Jacob Munkberg and Jon Hasselgren

Two Hybrid Methods of Volumetric Lighting

This thesis introduces and extends previous work on visualizing light shafts in realtime. Two new methods, based on building a Beam Tree for a coarse representation of the scene, are developed and evaluated. The overreaching goal is to reduce the fill-rate on the GPU by moving some of the computations to the CPU.

Student: Anders Jakob Nilsson

Supervisor: Petrik Clarberg

Particle Effects in Interactive Environments - using Shader Technology

This thesis is about creating particle effects suitable for interactive applications such as computer games. The main goal is to find out good ways of implementing and integrating particle effects for games using shader-technology. Within computer graphics, particle effects are groups of moving objects trying to imitate natural phenomena like smoke, fire, drops of water, explosions, swarms of insects etc. and also supernatural phenomena like energy weapons. Stunning and action-filled particle effects may play a conclusive role when people choose between different games.

The main question to be answered during this thesis is:
How can we create visually appealing particle effects for interactive environments using Shader-technology suitable for a game running on Xbox 360?

Student: Jakob Schyberg

Supervisor: Jon Hasselgren

This project was done in cooperation with Southend Interactive AB.

Real-Time Hair Simulation and Visualisation for Games

This thesis evaluates, improves and develops methods for generating, simulating and rendering hair in real-time. The purpose is finding techniques which make use of recent hardware to present an as good as possible visual result while keeping performance at such a level that integration into a game scene is viable. The Kajiya-Kay and Marschner lighting models for hair are evaluated, including recent resource saving discretizations to the Marschner model. Two shadowing methods are adapted and investigated for the nature of hair and real-time applications, and one new method is presented as a lower quality and faster alternative for translucent occluders. For dynamics, two models are developed and an existing model for simulating trees is adapted. The implementation uses and takes into account the capabilities and limits of modern graphics hardware, including various techniques that greatly reduces the amount of data sent to the graphics card. The implementation also includes a Maya pipeline for modeling hair. The result is a state-of-the-art rendering and simulation of hair which suite both in-game and story driven environments.

Student: Henrik Halén

Supervisor: Tomas Akenine-Möller

This project was done in cooperation with Digital Illusions CE, Stockholm.

Ray-Tracing Time-Continuous Animations using 4D KD-Trees

This thesis extends previous work on 3D kd-trees to include a 4:th dimension describing the movements of objects over time. This enables physically correct rendering of time-dependent effects such as motion blur, where the intensity is evaluated by shooting rays randomly distributed over time.

Student: Jens Olsson

Supervisor: Tomas Akenine-Möller

Efficient event propagation in scene graphs

Scene graph based applications for 3D graphics normally supports event listeners in order to interact with displayed data. Events that eventually change data held in the scene graph need to be processed and handled in a robust manner. If a scene graph contains a complex structure with multiple dependencies between attributes, the event processing mechanism through the scene graph becomes a problem difficult to solve in an optimal way. Problems that seem to occur are multiple and partly inconsistent updates of scene graph data which in the end will affect the rendering performance.

This thesis presents a technique called Visual Value 3D that solves the event propagation problem in a robust and optimal way. Visual Value 3D should mainly be used as a complement framework for scene graphs with demands on complex dependencies. Designing dependencies between scene graph objects and attributes is easily made with Visual Value 3D since the entire scene graph with including dependencies is expressed in xml.

Student: Anders Nilsson

Supervisor: Lennart Ohlsson

Web page: http://graphics.cs.lth.se/theses/projects/vv3d

Compressing Dynamically Generated Textures on the GPU

In the area of computer graphics, texture mapping is often used to enhance the appearance of rendered objects. To fit more data into the graphics cards memory, and to speed up rendering, it is common to compress the images used for texture mapping. The process of compressing an image, with currently available tools, takes several seconds. This makes it impossible to use the benefits of compressed textures if the textures are somehow dynamically generated by the application for immediate use (e.g. dynamic environment maps or hardware accelerated window managers). This thesis presents a method that makes it possible to very rapidly compress textures to the S3TC format. This is achieved by simplifying an available compression algorithm with speed in mind, and then adapting this simplified algorithm to take advantage of the incredible computational power of modern GPUs. The result is a compressor that compresses textures hundreds of times faster than available tools while maintaining comparable image quality.

Students: Christoffer Gurell and Oskar Alexanderson

Supervisor: Tomas Akenine-Möller

Also check out the SIGGRAPH sketch on the same topic.

OpenVG for Mobile Equipment

The purpose of this master thesis is to investigate if a software implementation of OpenVG on a mobile phone can be used for a set of applications, e.g. font rendering and map data visualisation. Further, algorithms to improve the render quality and performance are studied.

A software implementation of OpenVG can be used for the applications mentioned above, under the assumption that the developer is aware of the limitations imposed and does not introduce solutions that expose the weaknesses. Improvements are possible, mostly in the application stage, e.g. grid-fitting and global culling algorithms.

Students: Dan Johansson and Maciej Socha

Supervisor: Jon Hasselgren

Optimizing application drawing with hardware accelerated graphics on mobile platforms

This thesis investigates the impact of new 3D hardware on coming mobile phones. The project focuses on possibilities to enhance User Interfaces and enhance applications like Task Switching and Image Browsing using 3D, taking into account limited texture memory and memory bandwidth. The work is implemented on a device running Symbian/UIQ.

Students: Martin Malek and Anders Matson

Supervisor: Tomas Akenine-Möller

Character animation on mobile platforms

Mobile platforms present new challenges to creating believable computer graphics on limited hardware. The greatest of these being the lack of floating point number support and standard mathematic functions such as square root. This thesis will investigate how fixed point calculations can be used to implement methods such as mesh blending, morph targets, vertex blending (skinning) and inverse kinematics using e.g. quaternions and spherical interpolation. These methods will be implemented on actual mobile platforms.

Student: Carl Loodberg

Supervisor: Tomas Akenine-Möller

GPU-based collision detection

The purpose of this thesis is to investigate how the computational power of today's graphics processors (GPUs) can be used for collision detection algorithms. A GPU is capable of floating point calculations at speeds several times faster than that of the CPU, and an aim of the project is to accomplish some performance challenging effect like collisions with particle system objects such as verlet-based cloth models. An equally important issue will be to investigate how these effects can best be integrated into applications such as game engines.

Web page

Report

Students: Simon Klasén and Markus Malmsten

Supervisor: Calle Lejdfors

A tile-based triangle rasterizer in hardware

The implementation of a triangle rasterizer written in VHDL is described. One of the projects purposes is to document how the triangle rasterizer operates, as little has earlier been written at this detailed level before. The triangle rasterizer is tile-based and uses edge functions and areal coordinates for parameter interpolation. Three subcomponents represents the core, one unit that finds the tiles that the triangle overlaps, one unit that finds pixels inside the triangle in a tile, and one unit that finally calculates the pixels final color. The whole chip is synthesizable on a Virtex-II FPGA at 100 MHz and can render triangles with bilinear filtered perspective correct texture mapping, Gouraud shading and z-buffering.

Student: Fredrik Ehnbom

Supervisor: Tomas Akenine-Möller

Photorealistic Rendering of Scenes with Physically-Based Sky Light

This work presents an application that outputs images of skies that can be used to produce photorealistic renderings of outdoor scenes. The application is divided into two parts, a real-time part and a part where an actual rendering of a light probe is done.

Web page

Students: Andreas Agvard and Fredrik Lanker

Supervisor: Tomas Akenine-Möller

Design and implementation of a Real-time Character Animation Library

This work describes the handling of characters animation using various methods. Many methods of animating the characters is investigated and evaluated. The field of interest is mainly realistic looking human based characters but several techniques can easily be adopted to fit various other purposes. The aim for this report has not been aimed towards any specific platform or application. The goal has been to examine and create valueble methods to include in an adaptable and multi featured open source library.

Web page: http://graphics.cs.lth.se/theses/projects/skeleton

Students: Håkan Almér and Erik Erlandsson

Supervisor: Lennart Ohlsson

Prediction techiques in computer games

Almost every computer game today has support for some kind of multiplayer support over internet. The games tend to allow more and more players to be able to play at the same server at the same time. In realtime games, like for example 3D-shooters, there's a problem to get all players synchronized, so all players have the same picture of the virtual world they are in for the moment. In this master thesis we have looked at the issues that arises and tried to solve the problems. We have evaluated how linear, quadratic, Catmull-Rom and Richardson interpolation and extrapolation methods work in computer games, and shown how the algorithms could be written a generic way. To verify the results and to show how the methods work in practice, a simple game and a simulation tool have been developed.

Web page: http://graphics.cs.lth.se/theses/projects/pticg

Student: Joakim Bech

Supervisor: Lennart Ohlsson

Efficient Sampling of Products of Functions using Wavelets

This thesis presents a novel method for importance sampling the product of two-dimensional functions. The functions are represented as wavelets, which enables rapid computation of the product as well as efficient compression. The sampling is done by computing wavelet coefficients for the product on-the-fly, and hierarchically sampling the wavelet tree. The wavelet multiplication is guided by the sampling distribution. Hence, the proposed method is very efficient as it avoids a full computation of the product. The generated sampling distribution is superior to previous methods, as it exactly matches the probability density of the product of the two functions. As an application, the method is applied to the problem of rendering a virtual scene with realistic measured materials under complex direct illumination provided by a high-dynamic range environment map.

Web page: http://graphics.cs.lth.se/theses/projects/wis

Student: Petrik Clarberg

Supervisor: Tomas Akenine-Möller

Hardware accelerated global illumination

Todays computer graphics hardware, available for professional and consumer use, is very powerful. Just last year, Pixar's Luxo Jr. was rendered in real-time with consumer hardware. Nowadays developers have tremendous access not only to powerful graphics engines themselves but also to their inner workings through vertex and pixel shaders. Even though the images produced, are of very high quality they are not that realtistic. Realistic image synthesis is left to software packages that can run on multiple workstations with multiple processors and takes hours or even days to finish. In my thesis I have investigated if there is any or several parts of these global illumination algorithms (radiosity) that will gain from hardware acceleration and shown how it could be implemented.

Web page: here

Student: Mathias Palmqvist

Supervisor: Jon Hasselgren and Lennart Ohlsson

Evaluation of Java 3D for mobile platforms

This master's thesis primary objective has been to investigate the level of 3D complexity that is possible in games and other applications on a state of the art mobile telephone using the JSR-000184 specification of Java 3D. Further it has investigated how this compares to the usage of Java 3D as it is implemented in the optional package for J2SE. To achieve this objective, a Java 3D game has been implemented for both platforms.

Web page: http://graphics.cs.lth.se/theses/projects/java3d

Students: Jonas Nilsson and Fredrik Nygren

Supervisor: Calle Lejdfors

Real-time crowds in a 3D world

The purpose of this project is to create a system for computer environments that needs to portray large crowds. This will allow a more complete natural gaming experience and possibilities for more evolved worlds. The goal is not a realistic simulation of a crowd, but a crowd that looks realistic to the viewer. Aspects of the project is realistic behaviour, easy control and good level of detail to enable greater crowds. A criteria for a well-designed system is that a user-controlled character should be able to travel and interact with densely populated areas with scripted groups as well as individuals without noticeably distinguishing itself as a controlled agent. The primary purpose is to simulate human crowds, specifically crowds medium to far away from a viewer, i.e the focus is not on realistic micro-behavior such as movement of small joints etc.

Web page: http://graphics.cs.lth.se/theses/projects/crowds

Students: Jens Andersson and Anders Holmquist

Supervisor: Lennart Ohlsson

Generation of smooth non-manifold surfaces from segmented image data

This thesis addresses the smoothing of visualisated medical datasets. In certain cases when a dataset is visaulised in 3-D ridges occour. This is the case when 3 or more materials joins in the same voxel. This is a not desired behaviour for materials that are know to be smooth. This project was done at the Konrad Zuse Zentrum in Berlin and integrated in their visualisation tool AMIRA.

Students: Johan Helgesson and Jon Adolfsson

Supervisor: Lennart Ohlsson

Report: Here

Real-time water rendering

This thesis investigates different methods for using modern (DX9-class) graphics hardware for doing efficient real-time water animation and rendering. An alternative to LOD is examined in which a grid mesh is created to be even-sized, not in world-space which is the traditional way, but in perspective camera-space. This allow fine grained control of rendering time and quality. Offloading animation calculations to the GPU also frees up considerable resources from the host CPU. The particular target application is a system for visualizing simulations of guided missiles for nautical targets written in the open-source engine the Nebula Device. The thesis is written in cooperation with Saab Bofors Dynamics (see this link).

Web page: http://graphics.cs.lth.se/theses/projects/projgrid

Student: Claes Johanson

Supervisor: Calle Lejdfors

Optimizations for Shadows in Interactive Environments

Good lighting and shadowing add realism to computer generated images. Currently high quality lighting is only possible in real time for rather simple scenery and with the most powerful graphics hardware. This thesis presents new optimizations that can be used to extend already existing techniques for lighting and shadows. The algorithms developed for the thesis keep the same high quality of rendered images as traditional approaches but will in most cases reduce the workload of the graphics hardware significantly.

Web page: http://graphics.cs.lth.se/theses/projects/shadows

Student: Jon Hasselgren

Supervisor: Lennart Ohlsson

Scripting language programming of pixel/vertex shaders

Programmable hardware is the focus of computer graphics today. Vertex and pixel shaders enable advanced effects like vertex morphing, cloth simulation, anisotropic lighting, bump mapping and texture generation to be rendered in real-time. NVidia has released a high level graphics language called Cg (C for graphics) which generates assembly-like code for the graphics processor. The aim of the thesis was to use Cg in the scripting language Python.

Web page: http://graphics.cs.lth.se/theses/projects/pycgfx

Student: Jonas Jonsson

Supervisor: Lennart Ohlsson

Procedural cities

In both games and animated movies, models of city environments are often needed. These are often very complex and require a great deal of work, in addition to extensive knowledge of 3D-optimization and city-architecture. This master thesis project created a tool which can create procedural models of entire cities. The model generation is controlled by rules and parameters describing different architectonic styles and ways of expression. The models are created in such a manner that they can be imported into established game engines or animation programs.

Web page: http://graphics.cs.lth.se/theses/projects/procity

Students: Paul W Florczykowski and Johan Hoberg

Supervisor: Lennart Ohlsson

The Architecture of Massive Multiplayer Online Games

Massive Multiplayer Online Games (MMOG) are online games where more than 1,000 players can play in the same game concurrently. In most games, players stay in the game for a long time, typically 6-12 months, interacting with other players all over the world. This thesis has investigated the architecture of Massive Multiplayer Online Games. The game International Football Manager (IFM) was used as a case study, in which some experimental implementation also has been done .

Web page: http://graphics.cs.lth.se/theses/projects/mmogarch

Students: Sladjan Bogojevic and Mohsen Kazemzadeh

Supervisor: Lennart Ohlsson

The project was done in cooperation with the company BKdata AB

Shader-based stereo reconstruction

Modern graphic cards can perform extreme amounts of calculations. In addition, the problem within the field of computer vision is often that the algorithms are very time consuming. The objective of this thesis is to find solutions to the stereo matching problem, employing dense local two-frame stereo matching algorithms and hardware support within modern graphic cards. The performance of the implementations is measured against CPU-algorithms, to test the advantage of the shader approach. The algorithms were examined in Matlab and thereafter written in C++, using the DirectX API. Several different local area-based algorithms were tested and implemented as separate components (filters). The separate design created flexibility and testing became easy. The shader programming was done with standard DirectX assembler, for high control and efficiency. The results clearly indicate the advantage of implementing algorithms from image processing by using commodity shaders instead of the CPU.

Web page: http://graphics.cs.lth.se/theses/projects/shaderstereo

Student: Karl Johnson

Supervisor: Lennart Ohlsson

Realtime effects on high resolution video

The purpose of the master thesis was to implement a simple real-time color correcting tool for video, by using the graphics card to do the calculations instead of using the processor. This is because modern programmable graphics cards can perform very many simultaneous pixel calculations compared to the more general purpose processor. The limitation in using the graphics card today is the bandwidth of the computers, both on the PCI-bus (storage) and on the AGP-bus. The AGP-bus has a high theoretical bandwidth, but are far from reaching its potential when it comes to transferring the data from the graphics card to the processor. This thesis also analyzes these bottlenecks.

Web page: http://graphics.cs.lth.se/theses/projects/videoediting

Student: Klas Skogmar

Supervisor: Lennart Ohlsson

Game engine support for haptic hardware

Ordinary haptic hardware such force feedback joysticks and mice are not yet of sufficient quality to give realistic sensory illusions. Devices which have such capabilities do exist, for example the PHANToM from Sensable, but they are still to expensive to be generally available. A consequence of this situation is that that tools for building haptically accessible worlds and interfaces (GHoST, ReachinAPI, eTouch) are separate modules which are difficult to integrate into more general systems. This project has developed a plugin module for haptic interfaces for the open source game engine Crystal Space. The project has also developed two demo applications which show the capabilities of the system. 

Web page: http://graphics.cs.lth.se/theses/projects/crystalhaptics

Students: Henrik Aamisepp and Daniel Nilsson

Supervisors: Lennart Ohlsson, Computer Science and Charlotte Magnusson, Certec

ChromoWheel - a new spin on chromosome visualization

This project dealt with developing a web service for generating genome maps. The maps are preferably viewed with a web browser, since they contain interactive features. They should however also be able to serve as illustrations in printed reports. Furthermore, the map generating process shall serve as an interface for a collection of genomic research data. Different techniques were discussed and a picture generating process is developed. The image format is SVG.

Student: Sven Ekdahl

Web page: http://chromowheel.cgb.ki.se

Supervisor: Lennart Ohlsson

The project was done in cooperation with Karolinska Institutet.

Character support in Crystal Space

This project has implemented an extension to the game engine Crystal Space that supports humanoid models. The humanoid models can be used either as avatars in multi-user worlds or representing bots that are completely under program control. The project consist of two parts. The first part is a Cal3D plug-in for Crystal Space which can display an Cal3D Avatar in a Crystal Space environment. The second part is a Crystal Space application to demonstrate a third-person view using the Cal3D plug-in.

Student: Arton Grajqevci

Web page: http://graphics.cs.lth.se/theses/projects/crystalcharacter

Supervisor: Lennart Ohlsson

Terrain modelling in Crystal Space

The purpose of this master thesis was to visualize in real time an outdoor terrain environment, using the game engine Crystal Space. This includes a study of different types of techniques, for visualization of a landscape surface and vegetation, which are used today in games and simulations programs. Vegetation is here used with reference to a collection of trees, bushes and grass. Other parts of a terrain engine can be such as, water, mountains and visualization of the sky. But the main purpose will be to study and implement techniques for creation of trees and grass with Crystal Space. The grass will be implemented so that it will bend natural in the wind and also if something touches it. All to give the viewer a feeling of reality.

Students: Mikael Rosberg and Erik Nihlmar

Web page: http://graphics.cs.lth.se/theses/projects/crystalterrain

Supervisor: Lennart Ohlsson