Category: Development

More Algorithm Pics

My previous post went on a massive ramble about “wicked problems” and “knapsack” problems – the short version is that I’m working on DSF generation.  Here are a few more pics from DSFs in drydock.

Not everything is unsovled problems; these pics show an algorithm that “removes noise” from digital land class data – the idea is a riff on this paper.  I’m still not sure where it’s going to fit into the flow of data in scenery generation, but we’re looking for it to consolidate forest types.

What does autogen look like while it’s being born?  It looks like this.  For X-Plane 8 and 9, the autogen is built using bitmap technology – the DSF generator literally builds a bitmap image of a city block and tries to “fit” buildings by drawing them and checking for per-pixel overlaps.  Version 10 changes this completely – autogen is built polygonally.  In this pixture, the blue polygons are strings of houess built around roads; where the terrain is too steep, the polygons are clipped.

Getting polygonal autogen setup to be fast enough for production use has been a battle, but we’re getting there.

Website Outage

The main web server that drives X-Plane.com went down for about an hour this evening.  Well, really, the server was fine, but something went wrong in the colocation facility where it lives.  I’m still waiting to find out what went wrong there, and I suspect we may be shopping for new colocation shortly.

In the meantime we’ve turned down the TTL on our DNS entry and set up a live mirror of the main website.  This means that if the main server is kicked off the air again, we should be able to make the backup live very quickly.  This matters because X-Plane’s updater finds the download servers from the main website.  No main website, no way to update, even if the update servers are fine.  We can also set a DNS fail-over to be automatic, but I think the real answer here is reliable colocation.

Point Clouds Are the Technology of the Future (And Always Will Be)

“Unlimited Detail” is back – you can see the videos and read some criticism here.  I have never seen a really good white paper on the technology, so I’m going to have to speculate a bit about what it is they’ve actually done, and then I’ll use the rest of the post to describe why this isn’t the only way to improve perceived realism in a game (and is not the most likely one to succeed.

But first: some video.  This is Euclideon’s promo video, showing lots of really ugly polygonal models, and some clearly not polygonal models with a lot of repeating things.

And here we have in-game footage from the upcoming Battlefield 3, using the Frostbite 2 engine.

I’m starting with the video because I had the same first reaction that I think a lot of other 3-d graphics developers had: attacking six-sided trees from Crysis 1 is a straw man; the industry has moved beyond that.  Look at BF3: is the problem really that they don’t have enough polygons in their budget?  Do you see anything that looks like a mesh?

What Is Unlimited Detail, Anyway?

Short answer is: I don’t know – the company has been quite vague about specific technical claims.  This is what I think is going on from their promotional material.

Their rendering engine uses point cloud data instead of shaded, mapped, textured “polygonal soup” as the input data to be rendered.  Their algorithm does high performance culling and level of detail on the highest level of point cloud data. (Whether this is done by precomputing lower-res point  clouds for farther views, like we do now for textures and meshes, is not specified.)

Why Are Polygons Limiting?

First, we have to observe the obvious: a 1080p video image contains a bit over 2 million pixels; today’s video cards can easily draw 2 million vertices per frame at 30+ fps (even over theAGP bus!).  So for a modern GPU, polygon count is not the operative limit.  If you add more polygons, you can’t see them because they become smaller than one pixel on the screen.

The limit for polygons is level of detail.  If the polygonal mesh of your model is static, then when you walk away from it, the polygons are (in screen space) too small (and we run out of polygons – if we are drawing more than one vertex per screen pixel, we can exceed budget) and if we move in, the polygons are too big.

In other words, the problem with polygons is scalability, not raw count.

And in this, Euclideon may have a nugget of truth in their claims: if there is a general purpose algorithm to take a high-polygon irregular 3-d triangle mesh and produce a lower LOD in real time, I am not aware of it.  In other words, you can’t tell the graphics card “listen, the airplane has a million vertices, but can you just draw 5,000 vertices to make an approximation.”  Polygons don’t work like that.

Coping With Polygon Limit: Old School Edition

There’s a fairly simple solution to the problem of non-scalable polygons: you simply pre-create multiple versions of your mesh with different polygon counts – usually by letting your authoring system do this for you.*  X-Plane has this with our ATTR_LOD system.  It’s simple, and it works sort of.

The biggest problem with this is simple data storage.  I usually advise authors to store only two LODs of their models because each LOD takes up storage, and you get limited benefit from each one.  Had really smooth LOD on objects been a design priority, we could have easily designed a streaming system to push the LODs of an object out to disk (just like we do for orthophoto textures), which would allow for a large number of stored LOD variants.  Still, even with this system you can see that the scalability is so-so.

There’s another category of old-school solutions: CPU-generated dynamic meshes.  More traditional flight simulators often use an algorithm like ROAM to rebuild meshes on the fly at varying levels of detail.  When the goal is to render a height field (e.g. a DEM), ROAM gives you all of the nice properties that Euclideon claims – unlimited detail in the near view scaled out arbitrarily far in the far view.  But it must be pointed out that ROAM is specific to height fields – for general purpose meshes like rocks and airplanes, we only have “substitution LOD”, and it’s not that good.

Don’t Repeat Yourself

It should be noted that if we only had to have one unique type of house in our world, we could create unlimited detail with polygons.  We’d just build the house at 800 levels of detail, all the way from “crude” to “microscopic” and show the right version.  Polygonal renderers do this well.

What stops us is that the mesh budget would be blown on one house; if we need every house to be different, LOD by brute force isn’t going to work.

That’s why the number of repeating structures in the Euclideon demo videos gives developers a queasy feeling.  There are two possibilities:

1. When they built their demo world, they repeated structures over and over because it was a quick way to make something complex, then saved the huge resulting data set to disk.
2. They stored each repeating part only once and are drawing multiple copies.

If it’s the second case, that’s just not impressive, because games can do this now – it’s called “instancing“, and it’s very high performance.  If it’s the first case, well that was just silly – if their engine can draw that much unique detail, they should have filled their world with unique “stuff” to show the engine off.

Where Does Detail Come From?

Before we go on to how modern games create scalable polygonal meshes, we have to ask an important question: where do these details come from?

The claim of infinite detail is that you would build your world in ridiculously high resolution and let the engine handle the down-sampling for scalability automatically.  I don’t think this is a realistic view of the production process.

For X-Plane, the limit on detail is primarily data size.  We already (for X-Plane 9) ship a 78 GB scenery product.  But it’s the structure of that detail that is more interesting.

The scenery is created by “crossing” data sets at two resolutions to create the illusion of something much more detailed.  We take the mesh data (at 90m or worse resolution) and texture it with “landclass” textures – repeating snippets of terrain texture at about 4 meters per pixel.  The terrain is about 78 GB (with 3-d annotations, uncompressed) and the terrain textures are perhaps 250 MB.  If we were to simply ship 4 meter per pixel orthophotos for the world, I think we’d need about 9.3 trillion pixels of texture data.

I mention this because crossing multiple levels of detail is often both part of an authoring process (I will apply the “scales” bump map to the “demon” mesh, then apply a “skin” shader) and how we achieve good data compression.  If the “crossed” art elements never have to be multiplied out, we can store the demon at low res, and the scales bump map over a short distance.  There can be cases where an author simply wants to create one huge art asset, but a lot of the time, large scale really means multiple scale.

Coping With Polygon Limit: New School Edition

If we understand that art assets often are a mash-up of elements running at different scales, we can see how the latest generation of hardware lets us blow past the polygon limit while keeping our data set on disk small.

• DX11 cards come with hardware tessellation.  If our mesh becomes detailed via a control mesh, curve interpolation (e.g. NURBS or whatever) and some kind of displacement mapping, we can simply put the source art elements no the GPU and let the GPU multiply it out on the fly, with variable polygon resolution based on view angle.  Since this is done per frame, we can get the right number of polygons per frame.**
• Since DX10 we’ve had reasonably good flow control in shaders, which allow for displacement mapping and other convincing promotion of 2-d detail to 3-d.

So we can see a choice for game engine developers:

• Switch to point cloud data and a new way of rendering it.  Use the art tools to generate an absolutely ginormous point cloud and trust the scalability of the engine or
• Switch to DX11, push the sources of the art asset to the GPU, and let the GPU do the data generation in real-time.

The advantages of pushing the problem “down to the GPU” (rather than moving to point clouds) is that it lets you ship the smaller set of “generators” for detail, rather than the complete data set.

Euclideon does mention this toward the end of their YouTube video, when they try to categorize art assets into “fiction” (generated by art tools) and “non-fiction” (generated by super-high-resolution scanners).

I don’t deny that if your goal is “non-fiction” – that is, to simply high-res scan a huge world and have it in total detail, not even clever DX11 tricks are going to help you.  But I question how useful that is for anyone in the games industry.  I expect game worlds to be mostly fiction, because they can be.

If I build a game world and I populate my overpasses with concrete support pylons, which am I going to do?

• Scan hundreds of thousands of pylons all around San Diego so I can have “the actual concrete”? or
• Model about 10 pylons and use them over and over, perhaps with a shader that “dirties them up” a little bit differently every time based on a noise source?

There are industries (I’m thinking GIS and medical imaging) where being able to visualize “the real data set” is absolutely critical – and it may be that Euclideon gains traction there.  But for the game development pipeline, I expect fiction, I expect the crossing of multiple levels of detail, and I expect final storage space to be a real factor.

Final Id Thoughts

Two final notes, both regarding Id software…

John Carmack has come down on the side of “large art assets” as superior to “procedural generation” – that is, between an algorithm that expands data and having the artists “just make more” the later is preferable.  The thrust of my argument (huge data sets aren’t shippable, and the generators of detail are being pushed to the GPU) seems like it goes against that, but I agree with Carmack for the scales he is referring to.  Procedural mountains aren’t a substitute for real DEMs.  I think Carmack’s argument is that we can’t cut down the amount of game content from what currently ships without losing quality.  My argument is we can’t scale it up a ton without hitting distribution problems.

Finally, point clouds aren’t the only way to get scalable non-polygonal rendering; a few years ago everyone got very excited about Sparse Voxel Octrees (SVOs).  A SVO is basically a 3-d texture with transparency for empty space, encoded in a very clever and efficient manner for fast rasterization and high compression.  Will SVOs replace polygons?  I don’t know; I suspect that we can make the same arguments against SVOs that we make against point clouds.  I’m waiting to see a game put them into heavy use.

* E.g. the artist would model using NURBS and a displacement map, then let the 3-d tool “polygonalize” the model with different levels of subdivision.  At high subdivision levels, smooth curves are smooth and the displacement map provides smaller detail.

** The polygon limit also comes from CPU-GPU interaction, so when final mesh generation is moved to the GPU we also just get a lot more polygons.

Algorithmic Mountains (and Flash Crashes)

I don’t usually post random links but Indi sent me this TED talk, and I just thought it was great.  Procedural mountain ranges and rogue stock trading algorithms…what could go wrong? 🙂

http://www.ted.com/talks/kevin_slavin_how_algorithms_shape_our_world.html

DDS and Gamma

Sigh…I think the DDS gamma mess is now fixed.  This mess had two parts:

1. Since X-Plane treated DDS as having a gamma of 1.8, all DDS material had to be gamma corrected.  As it turns out, the error from gamma correcting a DXT-compressed texture is surprisingly small, but it was still silly to use anything other than sRGB given today’s computing environment.
2. In investigating this, I discovered that XGrinder/DDSTool from the scenery tools distro are inconsistent; they write out DDS using a gamma of 1.8 on Mac and 2.2 on Windows, resulting in overly bright DDS for authors using Windows.

This is now all fixed in the new DDSTool/XGrinder:

• A bit in the DDS file is used to specify what gamma the file was written with: 1.8 (v9) or 2.2 (good for v10).
• X-Plane 10 will look at this flag and correct gamma accordingly.
• The choice of gamma is a menu setting, and is selectable on both Mac and Windows.

I’m not sure when we’ll have a binary distribution, but the code is in the public GIT repo if anyone wants it.  The new tool should be better for both authors targeting v9 and v10.

(begin rant)

And for those who want to know why we aren’t communicating more, this is the reason why.  A release is made up of a huge number of small details all of which have to be made right, none of which is particularly sexy, and all of which have to be fixed to create an overall effect that is immersive and beautiful.

The saying in aviation is: “aviate, navigate, communicate”; that seems like a good policy for X-Plane 10 too.  I’m going to try to fix as many of these small issues as possible so we can have a functional beta, then we can talk about it.

(end rant)

X-Plane 9, X-Plane 10, and Free Updates

There was a lot of confusion in the comments from my last post regarding X-Plane and free updates.  Let me try to clarify.

First, here’s how updates have worked historically:

• Users get free patches for the life of a major version run.
• These patches include bug fixes, performance improvements, and sometimes substantial new features.
• No new patches once a major new version is released.
• The old patches are available and hosted indefinitely while the new version is out (at least for versions that use our updater).
• There has never been any kind of guarantee as to what features will be released as patches, or how long a version run will last.  Users who buy X-Plane buy the new version because historically the sum of a major version release plus its patches has been substantial.
• The global scenery doesn’t change for a major version run, and therefore there are no automatic updates to the global scenery.

That’s how version 9 has worked, that’s how version 8 worked more or less, and it is how I expect version 10 to work in the future.

To address specific concerns: yes, the version 10 run will have free updates to the core sim, just like before.

The point of my previous post is this: in the past, we have not done any updating of the global scenery, and I am not committing to anything more now.  OSM gives us a sane way to collect new data, but it’s too soon to talk about distribution.

The Reports of My Death Are Greatly Exaggerated

So the problem with this blog thing is that if I go radio silent for a few daysweeks you all think I’ve been abducted by aliens.  Let me first set the record straight:

• I have not been abducted by aliens.
• Austin has not been abducted by aliens.
• Chris was abducted by aliens, and they may have done some experiments, but he seems about the same as before, so we’re not worrying about it.

So what I have been up to?  Well, first, LR closed down the Westborough office and relocated scenery development to Grafton, MA.  Here’s the new home office, ready for action:

As you can see, the move was orderly and the new office is spacious and uncluttered.

(This post is going to get really nerdy really fast – a lot of what goes into X-Plane isn’t easily observable – a lot of the work I do is engineering that goes in under the hood.  It’s a long post, but coffee will help!)

Besides reassembling my office I have been working on global scenery DSF creation.  In particular, I’ve been trying to kill off the remaining “wicked” problems – that is, the parts of DSF generation that require first-of-their-kind algorithms.

(More technically, a design problem is “wicked” if the only way to learn enough about the problem to solve it is to go through the act of solving it.  This chicken-and-egg problem is usually broken by trying to solve the problem multiple times – the first few times are “learning experiences” – that is to say, the first version of the code often has to be thrown out.)

Stuffing Your Luggage

Most of the problems with global scenery generation turn out to be “knapsack” problems.  The knapsack problem is basically this: let’s say you have one suitcase (or knapsack) and you want to fill it as much as possible with your clothes.  All of your clothing are of different sizes.  What subset of clothing do you take that leaves the minimum wasted space?

Well, it turns out that if you want the best fit, with the minimum wasted space, the only way to answer that question is to try every combination of your clothing.  Yep.  You have to pack and unpack your suitcase approximately a gajllion times and just try every packing to see which one is best.

This matters to computer programmers because often we have to “stuff” a space as optimally as possible (or find some optimal combination within a set of combinations); what we learn from the knapsack problem is that the only way to find the truly optimal solution is to try them all.  The problem is that when you have a lot of things to try packing, it takes too long (even for a fast computer) to try every combination.

Just Shove The Biggest Things In First

I’ve put “best” and “minimum” in bold above because they are key to defining knapsack problems.  If you have to have the truly best fit, you have to try packing your suitcase or knapsack with all combinations of clothing.  But if a “pretty good” fit is okay, you can do something a lot faster.  You pick a heuristic (that is, a rule of thumb) and hope it works out well.

Let’s take a look at packing in action.  When you load an airplane, X-Plane packs all of the tiny instrument overlay textures into a few big textures to optimize frame-rate.  (This is called “texture atlasing” – authors have to do this by hand for scenery.)  Packing small textures into a big texture is a knapsack problem – to find the truly optimal packing we’d have to try every combination of instruments in each texture.  That would be very slow, so X-Plane instead uses a simple rule: we pack the biggest things in first, building rows.  As you can see from these pictures, the packing isn’t very good – a human could do a lot better.  But the packing isn’t bad, and it’s fast enough (a perfect solution would take days to run for each airplane load).

Pretty Heuristics

When we have a knapsack problem, and our solution is a heuristic (that is, rather than find the most optimal solution, we’ll find a pretty good solution) there is another question: are the particular kinds of solutions that we come up with nice looking?  Do we like them?  For panel textures, this is a non-issue; the user never sees the “pack” of the panel texture while flying.

But for global scenery, the look of our heuristics matter.  Global scenery generation is riddled with problems where the ideal setup of data would be too slow to compute, so we want our approximation to look “good”.

Here’s an example from global scenery of a knapsack problem where the look of the heuristic solution matters.  The map on the left is the OSM vector data for San Francisco.  The map on the right shows the same region broken into terrain zones.  Calculating terrain zones is a knapsack problem with a heuristic solution where the look matters.  Let’s break that down and see what that means.

First: what is a terrain zone?  A terrain zone is a set of adjacent city blocks in a DSF that all have the same base terrain.  If you recall Austin’s rantdescription of the way cities are created in version 10, he said some stuff about starting with grass and building cities on top of them.  Well, it turns out that if you build every block up on the same grass, you get something that starts to look like a mini-golf course.

We have a lot of ways to cope with that, but one of them is terrain zones: several city blocks are grouped together with one base terrain – but then, at a road boundary, we change to a different base terrain to “break up” the landscape along road boundaries.  The look is a lot less monotone in the far view – at least we think; the picture on the left is San Diego (terrain only) with the urban terrain zones set to primary colors for easy examination.  (When the real artwork is in place, the terrain will be similar and color, with roads dividing the various zones.)

The packing problem is: which blocks get grouped together, and which are kept separate?  Some groupings produce a more efficient final mesh, which results in better framerates.  Like the knapsack problem, it would take too long to find the best grouping for framerate, so instead we try to come up with a pretty good grouping.

If you look at the groupings the above maps and diagram, you’ll see there is sometimes a “tooth” pattern where the boundary beteween blocks jumps up and back.  That’s not so good looking; the algorithm that produces the groupings sometimes picks ugly block combinations, and we can’t just tell it “don’t do that” because it doesn’t check every combination to find the best one.

What Have We Learned?

Putting it together, you can see why global scenery generation is tricky.

• We want to combine city blocks to make moderate sized areas of similar terrain, preferably in clumps that look nice.
• We can’t just try every combination of block groupings; that would be too slow (it’s a knapsack problem).
• Instead we have a heuristic – a simple strategy to try that produces “pretty good results”.
• That strategy is tricky to develop because it has to come close to optimal results (for fps) and we don’t want the groups of blocks to look silly (which is hard to quantify).
• Therefore, calculating the terrain zones is a “wicked” problem – only by implementing a heuristic do we get to see how it “looks” and decide if it is acceptable.
• My office looks like a bomb went off.