Thursday, September 21, 2006

The road to hell is paved with ATTR_poly_os

I'm note sure I can even explain this...basically "polygon offset" is both the darkest voodoo in OpenGL and NOX for OpenGL programmers...usually it helps you win but sometimes it causes you to go down in flames.

The basic idea of polygon offset is this: normally you see the closer of two objects 'on top of' the farther one. This idea is so obvious to us humans who live in a 3-d world that it's almost hard to explain. Imagine I am a painter. If I draw two mountains, the one I draw second will always appear "on top of" the one I draw first in my painting...thus I must draw the far mountains first and the close mountains second to get a realistic landscape.

OpenGL provides "Z buffering"...basically this lets you draw the mountains in any order and the graphics hardware takes to not draw the pieces of the far mountain that need to appear under the near mountain in order to make the 3-d image look realistic.

So where does polygon offset come in? Well, the problem is that if two pixels we're drawing are very very close to each other in distance from the viewer, OpenGL's ability to decide which one goes on top falls apart. It turns out there are limitations to the math OpenGL can use. In particular, if I have an object with two triangles that are exactly on top of each other...OpenGL will randomly show some pixels from one and some from the other! Yuck! This is called Z-thrash.

This is where we bring in polygon offset. Polygon offset is a trick where you tell OpenGL to handicap the competition between two triangles. You say "listen, I know that the grass and the runway are probably about equal distances from the viewer...but handicap the math by adding 2 to the runway in all cases". What happens? The runway always wins! In other words, polygon offset is a cheat that helps assure that given two pieces of scenery on top of each other, the 'right' one always appears on top.

For more discussion on polygon offset, check out this article from the scenery web site.

Whew. Well that was fun...we use polygon offset on runways (to make sure they never thrash with the ground textures) and it just works great. But when it comes to roadways, things really go to hell.

Polygon offset has two strange quirks that make it tricky to work with:

1. If you cheat and use polygon offset to help a bit of scenery 'win' the distance competition, there is a risk that the cheat could push it through other parts of the scenery. (This mainly happens if you use too much polygon offset.) For example, if we used too much polygon offset on the runways, they would start to appear 'on top of' the airplane! It turns out there are two ways to manage this...we can tell OpenGL to "cheat once and forget about it" or "cheat every time you use this triangle". Both ways have their own problems.

2. The amount that OpenGL cheats and adds some to the calculation about "who is closest" depends on the angle from the viewer to the triangle in question! Take a second to consider that...if you look straight at the runway from the top, OpenGL is only adding 1 or 2 to the calculation - but if you then sit on the runway looking down it, perhaps it's adding 10 or 11! I can't hope to explain this aspect of polygon offset without going into the mathematics of 3-d frustum projections, but I will say this: this property is both necessary (if it didn't work like this, most times polygon offset wouldn't provide a decisive winner between two triangles) and a pain in the ass, because it means that relatively large offsets can be used at certain view angles.

(In fact whenever you move the camera and see one piece of scenery "eat" another, then go away, this is what you're seeing - we've used too much polygon offset and at a steep view angle the amount added to the math is too huge.)

Now I think we know enough to understand how X-Plane's roads became the road to hell.

Generally speaking, any time you put something directly on top of the terrain mesh, you need polygon offset to assure you see it and not the terrain under it. This is true for beaches, runways, and of course roads. (Authors making airports out of OBJs know that their tarmac objects need ATTR_poly_os too!!) So I think we can at least see that we need polygon offset for roads on the ground.

Now consider bridges. They are up above the ground, so technically they don't need polygon offset. But if a bridge segment starts on the ground and climbs up, it will be eaten by the ground. So I decided to polygon offset bridges too, and that was okay.

Then came cars. The problem is: do cars have to be polygon offset? Well, it turns out we lose either way. Recall that there are two ways to handle the 'cheat':

- If we only offset bridges once then they appear above terrain, but one bridge may incorrectly appear above another, because the cheat is not permanent.
- IF we offset bridges "permanently" then they will appear above the cars on top of them.

Okay so let's offset the cars too! It turns out that that doesn't work. Recall that the amount of offset is a function of the view angle of the triangle. Well, 99% of the time roads are horizontal, as is the terrain. So offsetting is okay - everyone gets about the same cheat.

But a car is made up of triangles going in all different directions...the result is that if you offset a car, then the roof offsets more than the doors! This just looks terrible. And even worse, the headlights, for technical reasons, always offset the minimal amount. (Geeks: they are billboards - they are quads that always look straight at you, so they always have zero view angle!) Bottom line is: you can't cheat the cars effectively onto the roads. Up through beta 11 you have seen this awful result..the cars look like they are inside the bridges.

Now since most of our cars drive on the highways, and since the highways (at least in the US) are mostly bridges so they can go over the regular road grid, this artifact is visible just about all the time.

So for the next beta I am backing off to the lesser of two evils: the bridges will not be offset. This means the cars will look great on the bridges. What you will see is a gap, like the one shown here. What this is: right as the bridge starts to "rise" out of the ground, the polygon offset cheat is turned off, and so for a little bit the ground consumes it.

4 comments:

Anonymous said...

That was one helluwa long post - but great! :) Thank you.

StrmRnr said...

I know the math you speak of. It is evil. Woe to those who have to deal with hardware accellerated floating point rounding errors.

Anonymous said...

It seems like your offsetting a lot of objects (runways, roads, bridges, airport scenery). I guess you can't just offset the ground by -1 or -2, eh?

Benjamin Supnik said...

Two problems with offsetting the ground -1 or -2:

The actual effect of the offset is a function of the geometry of the particular triangle - it's not uniform. So the relative depth placement of different triangles with the same non-zero offset is not correct. Only the relative depth of the same triangle with different offsets is predictable.

This brings us to the second issue: you never really want to write non-zero offsets back to the framebuffer, because they aren't consistent across multiple triangles.

So the real issue with roads is not that polygon offset produces artifacts, but that we can't both test against an offset value _and_ write back the original value. If we could do this, we could solve the road problem perfectly.

(Pixel shader? I'm not sure yet...when I last tried to write Z-buffer values with a pixel shader I hit a bunch of weird behavior that I haven't had time to investigate.)