Spam My Wiki, Please

User Rs2Play is now the first user to be banned from the X-Plane Wiki.  WikiMedia has some automatic features, like banning all associated IP addresses with a banned user, so if you find yourself kicked from the Wiki in error, email me and I will fix it.  (This would only happen if you were in the same shared IP pool as the user in question.)  Thanks to the users who immediately removed the spam while I was out of the office.

(If we have more spam, I can promote a few users to admin status to ban spammers faster, but so far we have had only one case.)

Unfortunately the situation with the X-Plane SDK Wiki is not as good.  The problem is that the SDK Wiki does not use MediaWiki - it uses phpwiki, so we do not have the rich set of user admin tools that MediaWiki comes with out of the box.  There is currently a user who is (for some reason) attacking the user database by registering fake email addresses over and over.  I do not know what the user hopes to accomplish, other than wasting my time.

The unfortunate side effect is to leave the SDK Wiki user database in a state of chaos.  When I have time, I will be adding some new features to the user signup code and trying to clean out the user base.

Why are we not using MediaWiki for the SDK?  Well, besides history (we used what we found at the time), the SDK Wiki's code is customized to integrate the SDK development tools with the Wiki itself.  This is how you get the latest documentation and user generated content on one page when you look up an XPLM function.

There is no scenery system Wiki - something I have debated a bit.  At this point though I am more concerned with getting the scenery tools out than with updating the documentation; once we have a more complete tool set, then I can ask the question "can users figure out how to use these tools."

(More) Triangle Optimizations

Yesterday I described how triangles and meshes can be optimized and hypothesized that building OBJs carefully could improve vertex throughput.  Having looked at some numbers today, I think the potential for framerate improvement isn't that great...an improvement would come from cache utilization (post vertex shader), and our cache usage seems to be pretty good already.

Simulating a FIFO vertex cache with 16 vertices (an average number - very old hardware might have 8 or 12, and newer hardware has at least 24 slots) I found that we miss the cache preventably around 15% of the time (using a random set of OBJs from LOWI to test) - sometimes we really missed bad (20-25%) but a lot of the time the miss rate might be as low as 5%.  

What these numbers mean is that at the very best, index optimizations in OBJs to improve vertex throughput might only improve vertex processing by about 15% (with the FPS improvement being less, since vertex throughput isn't the only thing that slows us down).

In other words, if I solve the cache problem perfectly (which may be impossible) we get at best 15%.

So this could be a nice optimization (every 5% win counts, and they matter if you can improve fps by 5% over and over) but cache utilization isn't going to change the nature of what you can model with an OBJ, because our cache utilization is already pretty good.

Have a Happy Thanksgiving!

Triangle Optimizations

I've been looking a bit at triangle optimization - first some terminology:

• Indexed triangles means that the vertices in a mesh are referred to by index numbers.  This is the scheme OBJ8 uses.  The advantage of indexing is that if a single vertex is used by many triangles (that share a corner) you only have to include the vertex data once, and then use that data many times by index.  (The savings from indexing depend on how often vertices are shared.)
  
• Triangle strips are strips of triangles sharing common edges.  Because triangles in strips share so many common vertices, they can be stored in a compact form, for a savings of almost 3x.

Back in the old days, triangle strips were critical for performance (hence the presence of strips in the OBJ2 and OBJ7 formats).  However with modern hardware, indexing is more efficient - the slight increase in data size (due to the index) isn't as expensive as the cost of specifying "we're done with one strip, start the next one".  (Consider that if we use indexed triangles, we can submit all triangles in one batch - with strips, we need one batch per strip.)  Thus OBJ8 uses indexing and doesn't provide any strip primitives.

There is one other concept to be aware of: cache utilization.  Graphics cards remember the last few vertices they processed, so if a mesh repeats a vertex shortly after using it, the graphics card can save work.  Triangle strips naturally use a cache somewhat well because vertices occur in close succession.

Strips and DSF

DSF allows for triangle strips (and triangle fans) as a space-saving measure.  Even with indexing, the indices can be compressed if strips and fans are used, and with DSF, file size was a very high priority.

When the DSF file is loaded, the data is rebuilt into indexed triangles (and reindexed - the DSF internal structures don't provide as good indexing as the DSF loader can create) - in version 803 we first started using indexed triangles and found it to be a big win.

MeshTool will generate triangle fans (as a space saving measure) - if you build a DSF by hand (using DSF2Text), use strips/fans to compress file size.

Because DSF focuses on file size, the quality of mesh output is a function of the DSF loader, which has to run while flying.  So while I can imagine some improvements in future performance, I don't expect to be able to get huge wins because the very best mesh optimizing algorithms are much too slow for real-time use.

The DSF loader already produces full indexing and preserves cache utilization from strips and fans - the next logical optimization would be to reorder non-strip, non-fan triangles for better cache use on load; the order in the DSF file may be optimized for file size and not cache utilization.

Optimizing OBJs

Where I believe there could be real improvement is in OBJ8 generation.  The OBJ loader currently loads the indexed OBJ triangles exactly as specified in the file - build a smarter file and we can get faster framerate.  There are two possible ways to win:

• Cache utilization - by ordering vertices for cache use, we can get better throughput.
• Hidden surface removal - by putting the exterior triangle earlier in the OBJ, we can draw them first, occluding the interior of an object, which cuts down fill rate.  (In an airplane, you would want the exterior fuselage first in the OBJ, before the seats inside, so that only the pixels visible through the window are drawn.)

This second form of optimization may be of limited utility in that an OBJ8 optimizer has to respect authoring decisions about translucency, attributes, etc.

I am investigating OBJ optimization now - my hope would be to put optimization into a new version of the ac3d exporter and ObjConverter.

Strips and the iphone

There is one place that triangle strips do matter: the iphone.  It turns out that the iphone will process triangles a lot faster if they are presented in a strip-like order.  So the iphone DSFs are the first to use triangle strips (instead of fans), and the OBJ exporter for the iphone optimizes the OBJ mesh into triangle strip order.

My tests indicate that strip order makes no difference on modern ATI and nVidia GPUs, so there is no point in releasing these optimizations in the main X-Plane tools.  In the long term, I expect our OBJ tools will have two optimization paths - a strip-based path for the iphone and a cache utilization-based path for the desktop.

Why Animating Cars Doesn't Always Work Right

I saw a post about this on X-Plane.org...authors sometimes try to make a vehicle (a car, truck, etc) modeled via an OBJ "drive around" using animation translate commands.  The problem is that sometimes the objects disappear.  Here's what is going on:

X-Plane uses a bounding sphere to decide whether to draw an object.  The bounding sphere is the smallest sphere X-Plane can fit around the entire object; if the sphere is on screen, the object is drawn (even if the object itself isn't on screen).  We do this because we can test whether the sphere is on screen very quickly.

But what if the object has animation?  X-Plane attempts to guess how animation might affect the sphere by looking at animation commands and making the sphere a bit bigger where animation might move the object outside the sphere.  This process works, well, rather poorly. In particular, X-Plane doesn't know exactly how your datarefs will change.  This results in two error cases:

• If X-Plane assumes the animation is more drastic than it really is, we make the sphere too big.  The object will then be drawn even when it is not on screen (because the sphere is on screen because it is too big).  This case hurts fps but does not cause objects to disappear.
• If X-Plane assumes the animation is less drastic than it really is, we do not make the sphere big enough, and sometimes the object "disappears" because the object is on screen but the (too small) sphere is not.

Now let's apply this to objects that are driving around.  Usually this is done via a translate animation command where datarefs feed the object's position.

X-Plane estimates the effects of a translate animation using the largest and smallest key frame values.  But the animation engine will extrapolate beyond these key frames.  So consider these three cases:

• As your dataref goes from -1 to 1, you translate by +/- 1 meter.  In this case, the bounding sphere will be increased in radius by one meter.
• As your dataref goes from -25 to 25, you translate by +/- 25 meters.  In this case, the bounding sphere is increased in radius by twenty five meters.
• As your dataref goes from -1000 to 1000, you translate +/- 1 kilometer.  In this case, the bounding sphere is increased in radius by 1000 meters.

Note that in all three of these cases, the animation works exactly the same!  But by using different dataref and value extremes, X-Plane's estimate of the effects of the animation (and its change to the boundign sphere) can be quite different.

So...if you animate an object and it disappears, it is probably because the bounding sphere has not been increased, perhaps because a translation animation is being sent values outside its minimum and maximum values.

The problem is of course that to have an object "roam" over a large area, it must have a very large bounding sphere, which means it is being drawn a lot more than necessary.

Back From India

I am back from India -- I seem to have done a particularly lousy job of telling anyone I was going off the grid this time, so if you were wondering where I was, well, now you know. I am sorting through about 700 emails now, so it'll be a few days before I can respond to even just the "really time critical" stuff.

Fact or Fiction

More ranting on the question of whether a file format is based on factual information or not. For the sake of taxonomy, let's call this:

• Factual. The file format aims to capture "real world" information. The file spec is thus written against real world norms. Example: a runway is described by the location of its centerline at its threshholds, the type of aproach lighting fixtures, and the material it is built out of. This is all fact that can be verified by going to the runway and measuring it (while trying to avoid 747s).
• Artistic. The file format gives authors a creative platform to create "stuff", e.g. an image, a model; the file format dictates how client applications might interpret that "stuff". Example: OBJs are artistic - it describes what affect on drawing the various bits of the OBJ file have.

Apt.dat is actually a hybrid format - most of it is factual, with one glaring exception: pavement surface areas.

Pavement surface areas are simply an overlapping pile of bezier polygons with holes. There are multiple ways to create a given layout, and you couldn't make an argument that one is "more factually correct" than the other.

Artistic file formats give us a way to be open-ended, and so they are particularly useful for problems that we cannot solve in a practical manner using factual file formats. When we worked on the apt.dat 850 format, I clung to a 100% factual approach for as long as I could, hoping to be able to truly describe "ground truth" about airport pavement. What I found in the end was that real world instances of airport pavement are so varying and weird in real life that almost any factual approach would fail to correctly model important real-world airports. So we punted and simply said "put pavement wherever you want, make it look nice."

The result of going artistic instead of factual is two-fold:

1. The taxiway data in the apt.dat file is less broadly useful to a wide range of client applications; you might be able to infer some aspects of the real taxiways from the data, but the taxiway shape has very little structure to it.
2. You can model just about anything you can dream of - there really aren't any limits.

That taxiways are "artistic" will probably always bug me a little bit from a theoretical viewpoint, but I think there is no question that this was the only practical standpoint.

Final thought: factual file formats are usually not precomputed - that is, if we have a list of runways described by their real-world properties (and not modeled as a collection of textured triangles) then there is probably work that still needs to be done to make the file useful for X-Plane. (That work is done by X-Plane's file loading code.)

Okay - I'm OOTO for a while - see you before thanksgiving!

/ben

Americans: Go Vote!

Lines are a bit long here in Maryland, and we're not even a swing state. Doesn't matter! Go vote!

You Can't Copyright a Fact

Previously I have blogged about a key choice in file format and scenery system design: will the file format be "specification based" or "reality based".

Specification based: the format has an exact interpretation of the data. OBJ is an example of this...the format describes triangles and there is only one interpretation of what that triangle could be.

Reality based: the format models real-world concepts; the correct interpretation is "as close to the real world as possible." The nav.dat file is like that.

I have been reading the OpenStreetMap Wiki and hit upon something I didn't realize: you can't use copyright to protect a derived work from a file that simply contains a list of facts!

Now I am a programmer - I am used to writing code, slapping a copyright notice up top, and assuming that it's now mine...heck, I'm the one getting carpel tunnel from typing it out. But consider the nav.dat file; it contains a giant list of frequencies for navaids. It's a fact that the BOS VOR is 112.7. Is my mentioning of that fact in this blog a derived work of the nav.dat file? Of course not, and it's a good thing too because otherwise we wouldn't be able to state facts without IP conflicts.

The OSM guys believe that they need to change their license to something weirder than the CC-BY-SA license they have now because the CC license uses copyright, you can't copyright facts, and OpenStreetMap is really just a huge collection of facts.

Now at this point I've written six paragraphs too many without the obligatory "I am not a lawyer." I am not one. And I must admit, my biggest concern with all of this is that it gets confusing and hard to interpret, and I'd be perfectly happy if there were only 3 or 4 licenses out there for everyone, you'd pick your favorite flavor, and everyone would know what it means.

Suffice it to say, it never occurred to me that a criteria of a file format might be "protectability" - that is, does the file format allow an author to specify something other than facts, so that it is elligible for copyright protection?

If you are an author, the good news is: pretty much all of our file formats would meet that criteria:

• OBJ and DSF are essentially 3-d modeling containers (DSF is just a damned wierd one).
• Images are copyrightable, so that takes care of your textures.
• Plugins are code, clearly copyrightable.
• ACF files contain, among other things, 3-d models, see the first point.
  
• Apt.dat would be the format most at risk of "factualization", but I think you could argue that the arrangement of bezier curves and attributes is more of an artistic 3-d model than a statement of fact.

But who knows, I am not a lawyer.

(Oh yeah, this whole article is written from an entirely US-centric viewpoint...I am even less qualified to speak of such things outside the US than I am here at home.)

Out of the Office

Starting Wednesday I will be out of the office - Lori and I are going on a 2+ week trip to India!

So first, the obvious: your comments to the blog won't show up until I get back and can moderate them. Similarly, I will be even less on email than I am now. I am trying to dig out my tech support emails as much as possible before I go!

I will announce this before I go: I finally got an end-to-end render of a global scenery tile using CGAL 3.3.1. Andrew did the original work on this, modifying parts of the scenery generation code to handle his NZ scenery. I've been working on the rest of the algorithms and finished it today.

This doesn't mean very much immediately, but it...

• Will fix the instability bugs in MeshTool.
• Will address missing antennas and obstacles in the global scenery.
• Provides a solid basis for building scenery out of just about any kind of data.
• Provides a bunch of nice tools for writing better algorithms, which means nicer looking scenery.

The next steps will probably be to create a new release of the tool set, including perhaps a bug-fixed Mesh Tool, etc.

What Does the Airport Boundary Do

The apt.dat 850 file format defines a polygonal "airport boundary". But what exactly does it do? It does different things when creating DSFs and when rendering them.

Inside X-Plane it has relatively little effect:

• It is one of many elements that counts toward the land area that will be flattened. (Runways and taxiways are also used.)
• We do not actually render any special terrain or fences.

The airport boundary has more of an effect during scenery creation.

• If an airport has an airport boundary, we do not calculate the airport's boundary ourselves - instead f we use the specified boundary.
• All land intersecting the airport boundary is turned to airport terrain.
• The DEM is flattened within the airport boundary to reduce the slope of high frequency bumps.

There is one aspect of airport creation that the airport boundary is not involved in: filling in water to make land under runways. When we create an airport, we actually calculate three boundary polygons:

• The inner ring is closest to runways and taxiways (very close) with very little simplification. It is filled in with land if it is wet.
• A second ring slightly farther from runways and taxiways is also filled in with land if it is wet.
• The outermost ring is a lot farther out, but does not fill in Water. This is the ring that the airport boundary can replace.

Why do we need two inner rings? Well, if an airport is next to the water but not at sea level, we need to induce two sets of mesh points, the outer ones which drop down to sea level and the inner ones which are at airport level. You can see the importance of this at KLGA, where one of the runways dropped to sea level at its midpoint in version 8, but not version 9.

Since the airport boundary polygon provides only one ring, it cannot be used for this purpose. At some point in the future, we might use the airport boundary for rings 2 and 3, or use a smaller version of the airport polygon for rings 1 and 2.

For now, my recommendation is: the airport boundary should trace out the entire airport premesis, not including water.