Occlusion Culling – Solving the Visibility Problem

All Posts

Nothing is more visible than things hidden
-Confucius

Sometimes it’s good to stop for a while, smell the procedural vegetation and think about where you’ve come. Let’s do that now – I’ll review the core problem Umbra’s known for solving and what’s required from a good solution.


A pentimento in The Arnolfini Portrait by Jan van Eyck.

When an infra-red reflectogram reveals how an old master has painted over a work, art history calls that a pentimento – an exercise in repenting. Some see modern, urban pentimenti in old advertisements peering under new ones. In computer graphics though, we’d like to avoid any unnecessary regrets. Drawing things that end up being hidden behind other things consumes valuable processing power, and what’s worse, no art historian so far has taken interest in our beautiful forgotten work. Figuring out the set of visible things for a 3D view is called the visibility problem, and it’s a difficult one to solve properly.

There’s an early and simple solution to the visibility problem aptly called the painter’s algorithm. Like an old renaissance master, the painter’s algorithm has you drawing everything in back-to-front order. While the result looks correct, it causes pentimenti – overdraw that wastes computing cycles. Computer scientists knew how to solve the visibility problem in the 70s like the artists did in the 1700s. The challenge is in solving it in a fast and practical fashion. The art of doing so is called occlusion culling, and we’ve thought about it quite a bit here at Umbra.

Modern rendering uses z-buffers – sort of the same thing as painter’s algorithm but for each point instead of each surface. While that does solve the problem, it does that very late in the rendering pipeline. By the time we get around rejecting anything, we’ve wasted a lot of time processing things hiding behind walls. A good visibility solution should know what the hidden objects are very early on, so that we can avoid even sending them for rendering. Avoiding spending time on hidden objects allows for more budget with visible ones.

Of course you could solve visibility by doing manual work. And indeed, many occlusion culling systems are based on hand tuning portals or occluders. Less manual work means better workflow for anyone creating content for the system. The bad end of automation spectrum would require tagging all visibility manually, a huge task that will quickly become impractical. An ideal solution would be in the other end – not require manual work and also not place restrictions on content.

OcclusionCulling
Wireframe visualization of a view with and without occlusion culling. The end result is the same, only amount of occluded detail changes.

It’s worth mentioning a couple obvious things. A visibility solution should also produce correct results. No visible object should be reported hidden. To guarantee visually correct result, any inaccuracy should be on the conservative side: reporting hidden objects visible. It should also be fast: too slow occlusion culling would negate the benefits.

One big practical issue with visibility is that it is a global problem that involves everything – a small change in visibility can affect the other side of a 3D world. This must somehow be reflected in the computation we perform to solve it. Reducing something into a local problem would allow to divide and conquer: easy parallelization and reuse of partial results. A generic visibility solution doesn’t really lend itself to this. This also means amount of work performed by the algorithm is at least relative to visible volume. We can compute some parts beforehand offline however and some parts at runtime. This is a choice we do get to make, and it allows us to find some extent of localization.

I’ve listed all you’d want from a visibility system, but will leave for another post how exactly does Umbra solve this all. There’s more still to Umbra: shadow culling, spatial connectivity, raycasts. We’re really in the business of separating a new medium from its limitations. The ultimate goal is a piece of technology that allows for beauty with ugliness, innocence with corruption and new discoveries with missteps along the way. And to shoot more demons. Or anything you might desire.

More from the Umbra blog

Bring your passion to us!

Elina Nygård / August 10, 2017
We are seeking seasoned veterans, propeller hat scientists and enthusiastic students to join us and…
Read more

Overview on Popular Occlusion Culling Techniques

Umbra / December 15, 2016
This article was featured in gamesindustry.biz   The occlusion culling experts at Umbra share…
Read more

Getting It Just Right – Benchmarking On HoloLens

Karlos Zafra / October 21, 2016
"Ahhh, this porridge is just right," – Goldilocks Finding the exact balance in any recipe is…
Read more
Tags

Popular Posts