Thursday, January 31, 2008

Algo-Gen

I may be fighting a pointless and unwinnable linguistic battle, but I have to try. People very often refer to the default city buildings in X-Plane as "auto-gen" but by any reasonable definition of "auto-gen" they are not really auto-gen at all.

Now these are all made up computer terms, so we can't really check the dictionary. But "autogen" scenery (short for automatically generated) usually refers to scenery that is created by a flight simulator itself, usually while you fly, and usually by placing 3-d detail in places that match the base terrain. This exists in FSX, and existed in X-Plane up to version 7.63.

X-Plane 8 doesn't have autogen!!!!!!! X-Plane 8 has scenery that is generated by computer programs, but X-Plane is not the computer program that is doing it. When you see a ton of buildings piled up in New York City, that is not becaues X-Plane looked at the New York city base terrain and said "hrm - some buildings would be nice."

What actually happens is we analyze New York City when we create the global scenery (before we ever burn the DVD masters) and the DSF generator places all of those buildings in New York City. X-Plane simply gets a huge list of buildings from the DSF and draws them.

I am going to try to coin the term "algogen" (algorithmically generated) to describe these buildings that (like autogen) come from a computer generating semi-random buildings from input data, but unlike autogen, algogen is a process that runs once before the scenery is made.

So how is algogen and autogen different?
  • You can't change the pattern of algogen building placement by editing files in the sim. The algorithm has already been run! You can replace the buildings using an overlay (that excludes the base) or by using a library of models to substitute models.
  • We are trading data size for computation. The DSF is bigger because it lists the location of every building in New York, even if they were just algogen buildings, but the job of placing those buildings is less difficult because X-Plane does not have to check each building against each road. That has been done in advance.
  • Changing the scenery via an overlay doesn't change the algogen! Add an airport via an add-on and you have to exclude the buildings. (But if you send that airport to Robin, the next global render will include it and the algogen will skip the airport automatically.)
Note one of the interesting results of algo-gen: X-Plane can't tell the difference between an alg-gen building and a hand-placed one! They're all just objects in a DSF. The fact that algo-gen buildings disappear with lower settings is because the sim/require_object property in the DSF header tells the sim which objects are important, and our generator always signals the buildings based on obstacle data as important. But algogen as a process is not visible to X-Plane!

And that's why I'm spending so many words on trying to distinguish between "algogen" and "autogen" - because the processes are fundamentally different, they're very different for scenery authors to work with. As a result, authors coming from X-Plane 7 or FSX will be very surprised if they try to understand X-Plane in terms of autogen....they won't be able to find the autogen config files, and the autogen buildings won't react to other scenery changes, because they're not actually autogen at all!

Algogen is a classic pattern of "precompute" vs. "compute-while-fly". Generally precomputing gives authors more flexibility (in our case, we have an obj engine that can handle a lot of objects, so authors can make their own objects of the same density as algo-gen with the objects placed anywhere) at the expense of making it more complex to edit the existing scenery (edit the mesh and the algogen doesn't change).

When we started the v8 scenery, two things pushed me toward precomputation:
  • In the past, changes in X-Plane's rendering engine had broken third party add-ons. So a precomputation strategy (by getting the scenery code out of the sim) means that the sim is doing less "interpretation" and thus the interpretation of scenery is less likely to change.
  • We wanted to focus on performance, which means getting computation out of the sim whenever we could.
Now that last point isn't quite as important as it used to be...when we were doing the design (during mid X-Plane 7), dual core for everyone wasn't on the radar, so the penalty for complex computation while flying is lower (and thus we have more expensive in-flight computation, like forests and completely draped bezier curve-based polygonal pavement).

But I think precomputation is still useful. Even with dual core, the algorithm that places X-Plane's algo-gen bulidings can take one to two minutes for a 1x1 DSF tile on a very fast computer. That's still a load time that's out of the question for us; even on the second core, the DSF wouldn't be "ready" in time for you to fly it. So one use of precomputation is to run algorithms that are more expensive than you can have in real-time. (That algorithm to pack objects inside an irregularly shaped polygon made by roads and land features is not fast.)

More importantly, precomputing does give us a nice advantage in the use of storage data. We ship about 50-60 GB of final scenery, but the source data is well over 100 GB. When we run the algogen algorithm, we have access to the full set of source data: coastlines, elevation, and land use before any simplification is done and any data is thrown out. So we have the potential not only to do a more complex analysis, but to do the analysis on a larger data set.

The down-side of precomputing is that if integration of all data is saved until sim time, there is the potential for third parties to contribute separate data to the sim via add-ons and still have the integration of those data sets work well. This doesn't always work out - see complaints in online magazine reviews about combining orthophotos and new road grids in FS2K4...they don't integrate because neither of those types of resources can be integrated to match the other in real time. But autogen still does a much better job than algogen at this; algogen basically has to be recut when other data changes. (And that is our intention - if you change the road grid, exclude and replace the objects too!)

4 comments:

Anonymous said...

Great post Ben! It's extremely clear what the differences are, and how they work.

Maybe you should be running for president vs. the current crop. LOL!

aMaLaHaMa said...

Haha, it's curious, in spanish, 'algo' means 'something,a few', so, when I saw the title, "Algo-gen", I understood this like "a few-gen", it's funny :D

Regards!!

alpilotx said...

Ben, I would rather have called it Pre-Gen ;-) As it is what you are doing : pre-generate scenery ... Algo-Gen sounds like some medicine ;-) But never mind ...

Benjamin Supnik said...

Hrm, AlpilotX, Pre-Gen sounds like a drug to me too..heck everything sounds like a pill in America because practically everything is. :-)

Fortunately they are working on a new prescription that will help software engineers come up with better names for their technology. Side effects include dry mouth, vommiting, nausea, and the pill should not be taken while using heavy machinery or C++.

Austin did have a plan to call the 25% increase in mesh scenery "trans-mega hyper mesh technology" but I think he was only suggesting that to make me grumpy. :-)