Parallel Voxelization of 3D Surfaces

Bachelor's thesis project at the Facultat d'Informàtica de Barcelona (FIB), Universitat Politècnica de Catalunya (UPC), May 2024.

This project focuses on the development and optimization of a voxelization engine built on top of the Diligent Engine graphics framework. Voxelization is a critical process in computer graphics and simulation: it converts continuous geometric data into discrete volumetric representations known as voxels — the 3D equivalent of pixels.

Motivation

Voxel representations are increasingly relevant in modern real-time graphics. They are used in procedural terrain generation, global illumination (voxel cone tracing), physics simulation, and games like Minecraft. The challenge is that voxelizing complex meshes is computationally expensive. This project investigates how to make that process fast and scalable using parallelism.

Demo

Latency benchmark

Technical approach

The project is structured around two main concerns: how to store voxels efficiently, and how to generate them fast.

Storage models

Four storage strategies were designed and benchmarked:

The Octree-based models provide the best memory efficiency at the cost of access complexity. The cached variant recovers a meaningful fraction of that performance.

Voxelization algorithm

The voxelization algorithm converts triangle meshes into voxel occupancy by testing each triangle against the voxel grid. The parallel version distributes work across CPU cores — each thread processes an independent chunk of the mesh — achieving significant speedup on multi-core hardware.

The parallelization strategy was designed carefully to avoid race conditions during octree insertion, which required a dedicated memory pool approach per thread with a merge step at the end.

Rendering

The engine renders the resulting voxel volumes in real time using an OpenGL-based rendering pipeline built on the Diligent Engine. Vertex attributes are packed tightly for GPU bandwidth efficiency, and the rendering pipeline was designed to handle large voxel counts without bottlenecking on draw calls.

Results

The parallel version achieves near-linear speedup on the tested hardware up to several cores. Speedup and efficiency are measured as:

$$S(p) = \frac{T_1}{T_p}, \qquad E(p) = \frac{S(p)}{p}$$

where $T_1$ is the single-thread time, $T_p$ the time with $p$ threads. Efficiency holds above 70% at 8 threads. Memory usage is dominated by the storage model choice — the Octree with cache offers the best trade-off between speed and memory.

Technologies

• C++
• Diligent Engine (graphics abstraction layer over OpenGL/Vulkan/D3D12)
• OpenGL
• Multithreading (std::thread)