Campus Event Calendar: Piotr Danilewski (07/14/2009 in E1 4/024)

Campus Event Calendar

Campus Event Calendar:
- All Upcoming:
  - only for D1
  - only for D2
  - only for INET
  - only for D4
  - only for D5
  - only for D6
  - only for RG1
  - Mailing Lists
  - by Speaker
  - by Type
  - by Category
  - by Title
  - Calendar
  - RSS Feed
- History of Events:

Event Entry

What and Who

Binned SAH kd-tree construction on GPU

Piotr Danilewski

Fachrichtung Informatik - Saarbrücken

PhD Application talk

IMPRS Master Student

AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI

Public Audience

English

Note: We use this to send email in the morning.

Date, Time and Location

Tuesday, 14 July 2009

09:00

240 Minutes

E1 4

024

Saarbrücken

Abstract

In order to generate realistically-looking images and animation we are interested in fast ray-tracing which mimics light movement and simulates most of visual effects we can encounter in reality. A basic problem in raytracing is to answer where is the first intersection between given ray and model. Instead of checking each triangle if it is hit by a ray, we construct acceleration structures. One of them in particular - kd-tree speeds up raytracing considerably but is hard to build.

This very costly process may be performed on GPUs which provide huge compute power for reasonable price. However GPUs are special cases of a parallel machines and require new kind of algorithms. There are good serial algorithms for kd-tree construction, usually using Surface Area Heuristic (SAH), or sampled (binned) version of SAH. In case of parallel algorithms, as far as I know, there are no binned builders developed so far. Therefore - as stated in the title - I present a new GPU algorithm for binned SAH kd-tree construction.

The algorithm works in steps - one per each level of the tree with all tree nodes of given level computed in parallel. During my work I observed that various solutions have different efficiency depending on the number of primitives in a node. In order to reach maximum speed, kd-tree construction is divided into 3 stages: big, medium and small. Each of them differs on how counting is resolved and how work is distributed on GPU.

My current program constructs the tree faster than any other known to me algorithm but still have competing quality compared to serial algorithms. Also, tests have shown that execution time scales down well in respect to power of GPU which gives reasons to believe it will continue doing so with future releases of the hardware.

Contact

IMPRS Office Team

0681 9325 225

--email hidden

System used:

Meeting URL:

Meeting ID:

Passcode:

passcode not visible

Code Visible for:

logged in users only

Stephanie Jörg, 07/08/2009 12:51 -- Created document.

Imprint / Impressum | Data Protection / Datenschutzhinweis