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.

 

About Ben Supnik

Ben is a software engineer who works on X-Plane; he spends most of his days drinking coffee and swearing at the computer -- sometimes at the same time.

25 comments on “The Reports of My Death Are Greatly Exaggerated

  1. first off, we here in canada are glad to hear you have not been abducted by aliens. we take our aliens abductions bout as seriously as our hockey, which is why they tend to stay south of the border. ( which is why i too was worried, eh? )

    secondly, fantastic job on the mip mapping of the dust texture – under the keys of the MK-4902. super realistic. is it auto gen?

    1. That’s actually a “detail” shader – when we get X-Plane 10 out in public there will be docs on it, but the basic tech is that a second high-res texture runs on top of the lower res one showing stuff that can repeat from afar but needs to be super-detailed up close. Typically you set up your detail with only high frequency information so that it “mips out” before anyone sees the repeats. (Yes, it’s the same 4 inches of dust on all of my equipment! 😉

      One exception: the stereo receiver, as it turns out, is covered with cat fur, not dust…the younger cat likes to sleep on it in the winter for warmth.

  2. the alien thing distracted me from reading the rest of the post, because i could not stop laughing 😀

  3. A lot of truth between the line … for those who understand what they are reading about here 🙂 (maybe not everybody will get the point).

  4. Nice to see you have a balanced & healthy life… Special K in the morning… Budweisser at night.
    P.S.: listen to your body…forget the K’s !!!

    P.S.2: in futures reports… should be fine to know a little about how weather-model developement goes… or something like that.

  5. “wicked” problems are all very well but my primary concern arising out of that post is that your diet appears to be based on case loads of Budweiser, Sam Adams Summer Ale and Special K.

    Loose the Budweiser!

    1. Uh oh, let me clarify: all of the boxes we used for moving we got for free from groceries and supermarkets. I do not drink Budweiser…I am a “beer snob”. I do drink a fair amount of Sam’s Summer though…

      1. A “beer snob” … oh my … then you should really visit me, and we would change that within a few days (we have the highest brewery density on the planet – and I mean real, different breweries!)

  6. wished you would use OSM data for these seperations and a way to update this data into the sim. i dont get why the genre with the biggest usage of growing global datasets is not using them properly. is it a matter of server infrastructure or licensing deals?

    1. I think you have several different ideas here packed together.
      – We don’t use OSM to split our terrain changes because OSM doesn’t have that data – it’s a graphic effect, not a real world phenomenon.
      – If we split the terrain at every block, the impact on framerate is too great, and it’s frankly not necessary for a realistic rendering of global scenery.
      – We are using OSM heavily in version 10.
      – Updating the scenery is an entirely different problem from creating it. We are adopting OSM because (among other things) it gives users a way to edit the _input_ data to the scenery.
      I can’t comment on updating the scenery now because it’s way too early to have any ideas on what our plans are.

      We are definitely NOT committing to providing free updates of the global scenery with a purchase of X-Plane 10; since we don’t have that in place we cannot promise it. We cannot and should not promise things that we don’t have figured out.

  7. I now know how much I am anticipating the v10 release when there was this extremely long gap in posts on the blog. It would make me sad to see no new posts.

  8. Jeremy that is + 1 from here…
    Check in every day to see if there is news here…
    Pic, video more….
    Really looking forward to XP10

    Henrik
    (Denmark)

  9. agreed Jeremy, the wait for v-10 from august of last year is a real bummer, let alone adding 5-6 months from now until it is in hands I was told that by fall/ oct-nov we should be seeing videos and pix of the sim coming together, great. but still SOO LONG

  10. …so its not like x-plane v9, we dont get anymore free updates? well i guess i have to be stuck in v10.00 after the release. or even, maybe ill just keep on using v9…

    1. No, he wasn’t talking about the main program or nav database, just the global scenery…read first, think after…

    2. I believe Ben’s talking specifically about global scenery updates to XP10 based on OSM data after the initial release.

      Though it hasn’t been explicitly stated, I’d be extremely surprised if normal feature/bugfix updates to XP10 aren’t free.

    3. waiting for v10 so long sucks. Especially if thats true in which no free updates during the run of v10. Ugggg

  11. the wait sucks, even if it’s a great product. sooo long, delays after delay….

    who said theres no free updates/patches , pretty sure there will be

  12. More frequent blog posts please! really excited on v-10 , 5day to week(s) break not so fun 🙁

Comments are closed.