Octree Ray Tracing - Aukio 3D

The raster pipeline draws triangles. The renderer/octree package offers a second, independent way to build a scene: a voxel volume. Space is stored as an octree — a tree that recursively subdivides a cube into eight octants — which compresses sparse or repetitive volumes well: empty regions are never allocated, and a solid room wall can stay one large cell until something forces it to split.

On top of that volume, renderer/octree/raytracer implements a real ray tracer: it casts one ray per pixel through the octree, finds the first occupied voxel, and computes lighting by casting shadow rays from the hit point toward every light source. The ray tracer is a rendering curiosity next to the raster pipeline — but it is a complete one, with per-pixel shadows and progressive on-screen refinement.

OctreeVolume stores the whole tree in a flat pool: eight parallel int arrays (cell1 … cell8), and a cell is just an index into them. The packing is economical:

• a solid leaf uses cell1 for its state marker, cell2 for its color and cell3 for its illumination value;
• an internal cell uses all eight arrays as child pointers — breakSolidCell subdivides a leaf by writing eight freshly allocated children into cell1 … cell8, inheriting the parent's color and illumination.

There are no Java objects per cell and no pointers to chase beyond array indexing — the same cache-friendly layout philosophy as the raster pipeline's mesh blocks. Cell zero is the master cell, whose edge length is masterCellSize world units.

Building a volume is incremental:

OctreeVolume volume = new OctreeVolume();
volume.initWorld(poolSize, masterCellSize);

// single voxel:
volume.putCell(x, y, z, color);

// filled box of voxels:
volume.fillRectangle(new IntegerPoint(x1, y1, z1),
                     new IntegerPoint(x2, y2, z2), color);

RayTracer is constructed with a target Texture, the volume, the light list and a RaytracingCamera (which wraps the scene's raster camera plus a magnification factor, and owns the texture the result is painted into). It implements Runnable — the demo runs it on a plain background thread:

RaytracingCamera rtCamera = new RaytracingCamera(viewPanel.getCamera(), magnification);
RayTracer rayTracer = new RayTracer(rtCamera.getTexture(),
                                    octreeVolume, lights, rtCamera, viewPanel);
new Thread(rayTracer).start();

For each pixel, RaytracingCamera generates a Ray; traversal (OctreeVolume.traceCell) descends the hierarchy, testing only the children a ray actually crosses and skipping empty subtrees entirely — empty space is never touched voxel by voxel. The first occupied cell hit yields the surface point and its cell2 color.

Lighting is per-pixel: from the hit point a shadow ray is cast toward every LightSource. If any occupied cell blocks that ray, the point is in shadow for that light; otherwise the light contributes to the pixel.

The render is progressive: the tracer repaints its texture roughly once per second (PROGRESS_UPDATE_FREQUENCY_MILLIS), so a refining image appears immediately and sharpens as more pixels complete — you watch the shadows settle rather than waiting for a final image.

The Octree demo in the aukio-3d-demos project (examples/OctreeDemo.java) builds a voxel scene (spiral, tiled floor, a fractal) into an OctreeVolume, places light sources, and starts a background ray-trace render of the current view. The same scene builds deterministically for the golden-image harness, so the ray-traced output is regression-tested like every other demo.

Back to main documentation