Awaken
← All posts
#9renderingperformanceculling

Precomputed occlusion: how it works, and why it's an option not a default

I built a precomputed-occlusion system for Awaken, got it most of the way working, and then set it aside. I want to be careful here: this is not "don't do PVS." Precomputed visibility is a great, proven technique - Quake shipped it in 1996. It's more that it's a poor fit for this project's current content, and getting it right is mostly a parameter-tuning problem. So: how it works, where it gets hard, and what Awaken does instead for now.

The problem it solves

Frustum culling - not drawing what's behind the camera - is cheap and Awaken has it. Occlusion culling is the harder one: not drawing what's in front of you but hidden behind a wall. In a castle full of rooms, that's a lot of geometry you pay to transform and shade for zero visible pixels. The classic offline answer is a PVS (Potentially Visible Set): precompute, per region, "from roughly here, what could you possibly see?", bake it in, and at runtime discard everything not in your region's set.

flowchart LR
  A["static geometry"] --> B["voxelise
(solid/empty grid)"]
  B --> C["from each cell, ray-march
to others (visibility)"]
  C --> D["store: sparse rows
(CSR)"]
  D --> E["runtime: camera cell →
drop non-visible cells"]

The pipeline (the genuinely reusable parts)

Voxelise. Overlay a uniform grid and mark solid cells. The instructive bug: marking every voxel a triangle's bounding box touches stamps huge phantom-solid slabs for big diagonal triangles (a terrain slope, a long wall). The fix is a proper triangle–box overlap test - the Akenine-Möller 13-axis Separating Axis Theorem check (box normals, triangle normal, and the 9 edge cross-products). Any separating axis → no overlap. It's a reusable primitive any time you rasterise geometry into a grid.

Ray-march visibility. From each cell, sample points and march rays to candidate cells with Amanatides–Woo voxel traversal (the tidy DDA that steps a ray cell-by-cell without missing any). Reach the target unobstructed → visible. Sample corners and union them, so you stay conservative - you never under-estimate visibility and hide something real.

Store it sparsely. "Which cells see which" is nominally an N×N bit matrix - catastrophic at scale (an early honest attempt asked node for a 4-trillion-entry array). So it's CSR (compressed sparse rows): a rowStart offset array plus a flat, sorted list of visible cell IDs, binary-searched - the same structure sparse matrices and graph adjacency use.

Spend the budget where it pays. Open outdoor cells see hundreds of others and gain little from occlusion, so an enclosure gate only gives a cell a visibility row when it's actually walled in (≥4 of 6 axis rays hit solid nearby). The budget concentrates on interiors, where fine cells are affordable and occlusion actually earns its keep.

Where it gets hard (the honest part)

A PVS is happiest on levels built from watertight geometry and authored portals - sealed rooms, doorways the tool understands as connections. Quake levels are exactly that. What Awaken often loads is imported triangle soup: art packs of thousands of overlapping, non-watertight meshes with gaps and no portals. Ray-sampled visibility over that can be made good, but making it provably hole-free is genuinely hard, and the failure mode is loud: sample a bit too coarsely to fit the budget and you can declare a cell hidden that some viewpoint can see - a chunk of world that blinks out as you walk toward it. A visible hole is a much worse bug than a few wasted draw calls, which sets a high bar.

That's a parameter problem more than a dead end: cell size, sample density, the enclosure threshold, the visibility horizon. Tuned tight for a bounded, mostly-indoor level, a PVS works well. Tuned for a large open imported world on a mobile budget, the safe parameters get expensive fast. So the right home for it in Awaken is an opt-in feature for suitable levels, with auto-tuned defaults and an honest "this scene is too open to occlude reliably - falling back to frustum only" - not something on by default for every scene.

What Awaken does for now

For the current target - large, open, imported, mobile-first - the cheaper, always-correct techniques carry more weight per unit of effort:

  • Size-aware distance culling - stop drawing things too small on screen to matter.
  • Level-of-detail - simpler meshes at range.
  • GPU instancing - repeated meshes in one draw.

None of them can make a wall disappear that shouldn't. That reliability is worth a lot when the alternative's failure mode is a hole in your castle. Precomputed occlusion stays on the roadmap as an option for the levels it suits; it just isn't the default, and I'd rather ship culling that's simple and correct than culling that's clever and occasionally wrong.

If there's a portable takeaway: before optimising the implementation of a technique, check its assumptions against your actual data. A PVS assumes sealed rooms and portals; imported packs are a bag of overlapping triangles. That mismatch is the real work - and sometimes the answer is "great tool, wrong job, keep it in the drawer."

← All posts