GPU Volume Voxelization : Exploration of the performance characteristics of different GPU-based implementations

In recent years, voxel-based modelling has seen a reintroduction to computer game development through massive graphics hardware improvements. Never- theless, polygons continue to be the default building block of 3D objects, intro- ducing a need for the transformation of polygon meshes into voxel-based models; this process is known as voxelization. Efficient voxelization algorithms take ad- vantage of the flexibility and control offered by modern, programmable GPU pipelines. However, the variability in possible approaches poses the question of how different GPU-based implementations affect voxelization performance.This thesis explores the impact of GPU-based improvements by comparing four different implementations of a solid voxelization algorithm. The implemen- tations include a naive transition from the CPU to the GPU, a non-branching execution path approach, data pre-processing, and a combination of the two previous approaches. Benchmarking experiments run on four, standard polygo- nal models and three graphics cards (NVIDIA and AMD) provide runtime and memory usage data for each implementation. A comparative analysis is per- formed on the basis of this data to determine the performance impact of the GPU-based adjustments to the voxelization algorithm implementation.Results indicate that the non-branching execution path approach yields clear improvements over the naive implementation, while data pre-processing has in- consistent performance and a large initial performance cost; the combination of the two improvements unsurprisingly leads to combined results. Therefore, the conclusive recommendation is using the non-branching execution path technique for GPU-based improvements.Voxel-baserad modellering har på senare år blivit återintroducerat till datorspelsutveckling tack vare massiva förbättringar i grafikhårdvara. Trots detta fortsätter polygoner att vara standarden för uppbyggnaden av 3D-objekt. Detta gör det nödvändigt att kunna transformera polygonytor till voxel-baserade modeller; denna process kallas för voxelisering. Effektiva voxeliseringsalgoritmer tar vara på den flexibilitet och kontroll som ges av moderna, programmerbara GPU-pipelines. Variationen i möjliga tillvägagångssätt gör det dock intressant att veta hur olika GPU-baserade implementationer påverkar prestandan av voxeliseringen. Denna avhandling undersöker påverkan av GPU-baserade förbättringar genom att jämföra fyra olika implementationer av en solid-voxeliseringsalgoritm. Implementationerna inkluderar en naiv övergång från CPU:n till GPU:n, en metod med en non-branching exekveringsväg, förbehandling av data, och en kombination av det två tidigare metoderna. Benchmarkingexperiment görs på fyra standardpolygonmodeller och tre grafikkort (NVIDIA och AMD) förser data för exekveringstid och minnesåtgång för varje implementation. En jämförande analys görs med detta data som grund för att bestämma den påverkan som de GPU-baserade ändringarna har på prestandan av voxeliseringsalgoritmens implementation. Resultaten indikerar att implementationen med en non-branching exekveringsväg ger klara förbättringar över den naiva implementationen, medans förbehandlingen av data presterar inkonsekvent och har en stor initial prestandakostnad; kombinationen av dem båda ledde, inte överraskande, till blandade resultat. Den slutgiltiga rekommendationen är således att använda tekniken med en non-branching exekveringsväg för GPU-baserade förbättringar