Real-Time Ray Tracing of Animated Sparse Voxel Octrees on FPGA

Abstract

Ray tracing—eller strålesporing—er en teknikk benyttet i datagrafikk med det mål å tegne en virtuell verden bestående av tredimensjonale volumetriske modeller. Disse modellene kan være uttrykt som geometriske objekter, eller som abstrakte datastrukturer slik som den optimaliserte voxel-baserte modelltypen kalt sparse voxel octree (SVO). En av hovedbegrensningene forbundet med strålesporing av slike SVO-modeller i dag er at datastrukturen i utgangspunktet ikke har noen støtte for animasjon. I prosjektoppgaven ble det utviklet en generell metode for animering av slike SVO-modeller.

I denne masteroppgaven blir en hardwareakselerator for strålesporing av animerte SVO-modeller spesifisert, utviklet og, i stor grad, implementert. Implementasjonen kjøres på en FPGA, og spesifikasjonen benytter metoden utviklet i prosjektoppgaven for å legge til rette for animasjon. Som grunnlag benyttes ytterligere to etablerte algoritmer: en effektiv metode for traversering av octree-strukturer, og en minne-effektiv datastruktur for lagring av SVO-data.

I første omgang utføres en analyse av systemets krav, og en spesifikasjon av den ønskede løsningen presenteres. Systemets utforming utledes deretter, hvor dets funksjonalitet og interne moduler diskuteres og bestemmes. Til slutt presenteres en implementasjon av dette systemet. Visse deler av systemets implementasjon ble ikke ferdigstilt grunnet tidsbegrensninger, inkludert deler av funksjonaliteten knyttet til animasjon. Resultatet er en komplett spesifikasjon og utforming av et system for hardwareakselerert strålesporing av animerte SVO-modeller i sanntid, og en delvis implementasjon av denne spesifikasjonen.

En rekke ulike konfigurasjoner av implementasjonen testes. Ved en klokkefrekvens på 100 MHz og med 16 kjerner for SVO-traversering, viser systemet seg i stand til å tegne statiske SVO-modeller med en bildefrekvens på 26.91 Hz og en oppløsning på 1280 × 720. Dersom et tilstrekkelig antall kjerner for SVO-traversering implementeres, blir det demonstrert at systemet begrenses av eksterne faktorer—nemlig ytelsen forbundet med IO på utviklingskortet. Det konkluderes at sanntidsytelse under tegning av animerte SVO-modeller er oppnåelig.

Ray tracing is a technique used in computer graphics to render virtual scenes consisting of three-dimensional volumetric models. These volumetric models may be formulated as geometric primitives, or as data structures such as the optimised voxel-based model known as the sparse voxel octree (SVO). One of the main limitations today when using ray tracing to render SVOs is that the octree data structure is inherently static. In other words, efficient animation of a scene to be rendered is challenging to achieve. In the project thesis, a general method for animation of such SVO models was derived.

In this master’s thesis, a hardware accelerator for ray tracing of animated sparse voxel octrees is designed and largely implemented. The hardware implementation runs on an FPGA, and its design employs the method from the project thesis in in order to facilitate animation. The proposed solution also makes use of two additional established algorithms as foundation: an efficient method for traversal of octrees, and a memory-efficient data structure scheme for storing SVO data.

Initially, an analysis of requirements is conducted and a specification of the desired system is introduced. The system design is then derived, in which the functionality of the system and its constituent modules are determined and discussed. Ultimately, an implementation of this design is presented and examined. Certain parts of the design were not fully implemented due to time constraints, such as the modules that provide the arithmetic operations necessary for animation. The overall result is the system design of a fully-fledged hardware accelerator for real-time ray tracing of animated SVO models, and a partial implementation of this design.

A number of implementation configurations are tested. Running at 100 MHz with 16 SVO traversal cores, the implementation is shown to be capable of rendering static SVO models with a frame rate of 26.91 Hz at 1280×720 resolution. With a sufficient number of traversal cores, the implementation appears to be limited by external factors—namely the IO performance of the development board. It is concluded that real-time performance rendering animated SVO models is achievable.