In this article we will dive deep into Amanatides and Woo's fast voxel traversal algorithm. Designed for, however not limited to, ray tracing voxel grids.Most visual examples in this article will be 2D for convenience however, the concepts are the same for 3D. All code snippets provided will be using C++ 20 and will be for 3D voxel traversal.
Most visual examples in this article will be 2D for convenience however, the concepts are the same for 3D. All code snippets provided will be using C++ 20 and will be for 3D voxel traversal.
You may wonder "What can voxel ray tracing do?". Here's two screenshots taken from my own CPU voxel ray tracer:Ray traced voxels with lighting.Ray traced voxel terrain.
To get started tracing anything, we need some data to traverse ! Let's setup a little VoxelTracer class together:constexpr int GRID_SIDE = 32; class VoxelTracer { /* Grid voxel data. */ unsigned int grid[GRID_SIDE * GRID_SIDE * GRID_SIDE]; /* Grid minimum and maximum point in world space. (x, y, z) */ vec3 grid_min, grid_max; public: VoxelTracer() { grid_min = vec3(0, 0, 0); grid_max = vec3(1, 1, 1); /* TODO: fill `grid` with data */ } /** * @brief Find the nearest intersection with the grid. * @param ro Ray origin * @param rd Ray direction (normalized) * @return `1e30f` if no intersection was found. */ float find_nearest(const vec3& ro, const vec3& rd) const; };
What to fill grid with is up to you. Each voxel in the grid is stored as a color unsigned int, RGBA.For some inspiration: you could fill it with a noise pattern, like Perlin noise.