home // text // multi-media // misc // info

[ video-games computer-science science game-design red-rover ]

Mars, MEGDR, and Proper Signage

I previously hinted at my current project—Red Rover—and while I’m not about show my whole hand just yet, I just felt like sharing the solution to a problem that had been bugging me for a few days.

The game requires, among other assets, Mars heightmap data (which, along with the game’s title, should give you some clues as to the game’s subject). Now, not having visited Mars recently, nor being even a semi-competent 3D visual artist, I was in a bit of a bind. However, I soon found a link to NASA’s Mars Global Surveyor (MGS) mission, which had been circling Mars from late 1997 to approximately January 2007 (for all we know, it could be circling still). MGS contained onboard the Mars Orbital Laser Altimeter (MOLA), which produced exactly what I was looking for: the Mission Experiment Gridded Data Records (MEGDR) (acronyms!), or, in the parlance of our times, a heightmap. Furthermore, being the cosmic badasses that they are, NASA made all this data available for exactly free dollars. My nerd sensors were buzzing. This was the perfect solution to my problem: using actual data from space.

As you can see on the MEGDR page, the data is available in a number of resolutions, and in a number of “flavours,” actual topography being only one of the latter (I still haven’t wrapped my head around the idea of an “areoid”). As a simple sanity check, I wanted to import the MEGDR data (at the lowest resolution), and print it out to a greyscale bitmap, for the purpose of dazzling friends and bewildering enemies. And herein lay the problem.

MEGDR data is raw data. A given MEGDR “image” (example) is a flat file with no headers—there are only “pixels.” Each pixel is a signed, 16-bit big-endian value representing a single height measurement on Mars—thus each pixel can take a value from -32,768 to +32767. Since Martian topography varies from roughly -8200m to 23100m (see this, under “Filter by altitude”), this gives an approximate height resolution of (23100+8200)/65535 = 0.477607385m. Which is pretty darned accurate.

So off I went, naively trying to read this data and then convert it to a greyscale image using SDL. Now, bitmaps rely on red/green/blue values, with each colour being allotted 8 bits ([edit]that is, in SDL each is 8-bit; in many formats, RGB colour is encoded in 16 bits, with the colours getting 5/6/5 bits, respectively[/edit]), so the 16- to 8-bit down-conversion clearly loses a ton of resolution (vertical resolution now being (23100+8200)/256 = 122.265625m). Regardless, I figured that for a greyscale image, I’d still get a good representation. My code was roughly as follows (with some parts, such as the actual image creation, omitted):

short buffer;
for(int i=0; i < mapHeight; ++i) {
  for(int j=0; j < mapWidth; ++j) {
    // Read in two bytes
    marsData.read((char*)&buffer, 2);  

    short val = (buffer << 8) | (buffer >> 8);  

    // Convert 16-bit data to an 8-bit greyscale value
    Uint8 c = 255.0f * ((((float)val) + 32768.0f) / 65535.0f);  

    // The actual colour
    Uint32 clr = SDL_MapRGB(outsfc->format, c, c, c);

The most important part is the endian swap. MEGDR data is stored as big-endian values, while most of my working computers (i.e., x86’s) are little-endian. So, for instance, a height value of 6699 would be stored in the MEGDR data set in hexadecimal as [1A][2B] (in two contiguous bytes), whereas it would be stored in my computer’s memory as [2B][1A]. A simple problem with a simple fix; I won’t go through boolean arithmetic here, suffice it to say that my code, as I intended it to be, would in this case assign to the short “val” the value “[2B][00] OR [00][1A] = [2B][1A].”

This is the result of reading the MEGDR data thus, and spitting it out as a greyscale image. Some strange intuition told me that it was wrong. Well, that much is obvious—I think even from Earth we’d be able to see such contrasting stripes and, from a closer examination, such incredible noise in Mars’ terrain.

I grew more and more frustrated over the next few days—the theory behind the code was solid, and honestly it was such a trivial operation that I was furious at not getting the smooth, natural results I was expecting. Clearly, something was wrong either with NASA’s data, or with my algorithm. I tended to think the rocket scientists were probably not at fault.

To cut a long story less-long, I dove through various fora and specifications for a few days, until finally coming across the mention of logical vs. arithmetic bit shifts (which I should have recalled from my early System Hardware courses, but, well, forgive an old man his forgetfulness). It became clear that, since the variable “buffer” in the above code snippet was a signed variable (as I had declared it, given that the MEGDR data was signed), C++ will actually perform an arithmetic bit shift, preserving the sign of the value.

This, in a word, is bad. Consider a MEGDR value of -254, or [FF][01] in hexadecimal. What I hoped to achieve with the above code was to assign to the short “val” the value of “[00][FF] OR [01][00] = [01][FF]”. But—and here’s the most important point—since “buffer” was a signed short value, an arithmetic shift was used instead of a straight logical shift, preserving the sign bit. As a result, “val” received the value “[FF][FF] OR [01][00] = [FF][FF],” or -32,768. Again, this is bad.

And so we get to the solution. As is so often the case, it is the most trivial matter. See where I declared “buffer” in the above code? I changed it to the following:

unsigned short buffer;

…and with that horribly unassuming specifier, my problems disappeared. “buffer,” as an unsigned short value, was shifted using a logical shift, preserving the hex values as I’d intended. Observe… Mars in all her cylindrically-projected, low-resolution splendour. She may not look like much, but she’s got it where it counts (i.e., actual realism).

So let that be a lesson to you all. Sometimes you may make assumptions about trivial operations. But sometimes those assumptions can turn out to be, shall we say, a bit shifted!

Hahahahaha… oh, my. Let’s have some international coffee.