## Archive for May, 2010

### Graphics Trick: MIP size

Thursday, May 27th, 2010

This one is all about MIP mapping. If that’s greek to you, go find another window and look it up. This time, how big is that MIP chain? Turns out there are closed form equations for a lot of the common cases.

Each level of a MIP chain is 1/4 the size of the next level up. So the first step is remembering how to find a closed form equation for an infinite sum. In terms of the original size, the rest MIP chain is about this fraction of the base level:

scale = 1/4 + 1/42 + 1/43 + … = 1/4*(1 + 1/4 + 1/42 + …)
scale = 1/4*(1 + scale)
scale = 1/3

So, the rest of the MIP chain is about 1/3 the original, or the whole thing is about 4/3 the original. Seems I remember learning that in grade school (well maybe not grade school, but a while ago). But what’s with the “about”? Well, this infinite sum overcounts by some fractional pixels after the last level. How many? All of the pseudo-MIP levels below the last level, or 1/3 of the size of the last level. Assuming a nice square texture where the last level is 1 pixel, it over counts by 1/3 pixel. In general, it’s

size = base*4/3 – last*1/3

or if you want something you can use integer math for

size = (4*base – last)/3

For example, for a 1024 x 1024 texture, it’s

size = (4*1024*1024 – 1)/3 = 4,194,303/3 = 1,398,101

All integers. I think that’s pretty cool. You’re welcome to do the sum by hand to be sure:

size = 1024*1024 + 512*512 + 256*256 + 128*128 + 64*64 + 32*32 + 16*16 + 8*8 + 4*4 + 2*2 + 1*1 = 1,398,101

But it gets even more fun. What if you pack all the levels of an X x Y MIP texture into a contiguous block of memory (How big? See the size equation). Where does level N start? Well, if you pack smallest level first, it’s just the size equation for level N-1. But if you pack base level first, it’s the size equation from the base through level N-1

Start(N) = (4*base – last)/3

Or avoiding potential problems for the very first level, you can rewrite it in terms of the size of the base level and the size of level N:

Start(N) = (base − next)*4/3

For that 1024 x 1024 texture, this is where it says the levels start

Start(0) = (1024*1024 – 1024*1024)*4/3 = 0
Start(1) = (1024*1024 – 512*512)*4/3 = 1,048,576 (= 1024*1024)
Start(2) = (1024*1024 – 256*256)*4/3 = 1,310,720 (= 1024*1024 + 512*512)
Start(3) = (1024*1024 – 128*128)*4/3 = 1,376,256 (= 1024*1024 + 512*512 + 256*256)

Just throw in a multiplier to handle different size texels, or cube faces if packed together.

A few caveats though. First, it works great for non-square textures or non-power of two textures if you stop when you hit the last full pixel. So, if your 1024×256 texture stops at 4×1, all is good, but not if you toss in an extra 2×1 level, since the equations think it should be a 2 x 1/2 level. Nobody likes half pixels. Also, textures formats like DXT that round up to 4×4 blocks work only as long as you stick to levels that don’t actually need any padding (powers of 2 down to 4×4 are OK, but 14×18 gets padded to 16×20 with those troublesome extra pixels)

Marc

### Graphics Trick: Normals from Height

Thursday, May 20th, 2010

I’ve seen code floating around that computes a normal map from a height map by estimating tangent vectors and doing a cross product. That includes a bit of unnecessary extra math, so here’s a better way to compute the same thing.

First, let’s write the height field as a function of x & y (ok, it’s a texture, so call them u and v if it makes you feel better). So a height field is basically a texture that defines

z = h(x,y)

The tangent-based code already estimated the partial derivatives of h(x,y) with respect to x and y. Let’s call those hx and hy. There are several ways to do this: forward differences

hx = h(x+1) – h(x)

central differences:

hx = (h(x+1) – h(x-1)) / 2

Sobel filter (no, I’m not going to write that one out), or other derivative of a filter.

The trick comes in rewriting this thing as an implicit function of x,y,z that’s 0 on the surface, negative under the surface and positive outside the surface. That’s actually pretty easy:

f(x,y,z) = z – h(x,y)

So the neat thing is that the normal to an implicit surface like this is just the gradient of the implicit function:

N = (fx, fy, fz) = (-hx, -hy, 1)

That’s it. Much friendlier than cross( (1,0,hx), (0,1,hy) ). You could actually get exactly the same result by expanding out the cross product, but I think it’s much cooler (and more applicable in other situations) to know about the normal to an implicit function trick.

Marc

### Graphics Tricks

Thursday, May 20th, 2010

While on sabbatical at Firaxis games, I started sending out periodic “graphics tricks”, with useful stuff that isn’t often covered in a graphics class. I’m going to start putting some of them up here. Definitely for the hardcore programmer, but if you’re programming for games, what other kind is there? The first one should be up shortly…

### Play Tabula

Tuesday, May 11th, 2010

One night in 480 CE, the Roman Emperor Zeno was winning a game of Tabula.

Then he rolled a 2, 5, and 6, and, because of exactly how his pieces were arranged on the board, he lost.

He was so very annoyed that he wrote down, in complete detail, how he had been wronged.

Thus the game of Tabula was preserved; here is a link to a printable board, with, I hope, full instructions– in English. It’s an ancestor of Backgammon, a child of Senat, but it itself was played all over the Roman Empire for hundreds of years.

### Dr. Voodoo is on the App Store

Wednesday, May 5th, 2010

Congratulations to Jen and Brian! I don’t know whether I’m the first sale or not, but they got my dollar!

### GoeMelee at “Come Out and Play” in Brooklyn

Wednesday, May 5th, 2010

The IRC fellows class that I am teaching has been collaborating with me on “GeoMelee,” a real-time strategy game that uses iPhone GPS to let you play in the real world.

COaP has accepted our game; we’ll be running a few sessions June 4th or 5th up in Brooklyn.

All game pieces have a latitude and longitude; you see them by running the game on your iPhone and looking at a map of your location.

credits page

Ericson Crystal Field

game screenshot

Other than that, it’s a simplified version of StarCraft: there are “crystals” on the map. You build “extractors” to harvest them, which allows you to build more things. To build in a location, you have to stand there with your phone. There is fighting.

The map editor is online at http://userpages.umbc.edu/~brt1/app/map/.

The rest will be on the app store as soon as humanly possible.

### DEC went well

Tuesday, May 4th, 2010

UMBC’s Game Developers’ Club had their annual Digital Entertainment Conference last weekend. The highlight for me was watching UMBC students demoing their games for Tom Fulp, the founder of Newgrounds.com. How I wish I’d taken a picture! Dang.

Katie Hirsch (UMBC ’04) started at 9 –sharp– with her excellent “So You Wanna Get Into Games” presentation. Other presenters included Tom Fulp, Eric Jorden (UMBC ’08, and GDC’s founder), Helen Zhang (UMBC ’09, now at Zynga!), Young Vo, Matt Berner, and Ian Frazier. Tom Truong (’09) was there, he’s at Firaxis Big Huge now– maybe next year, we’ll get him to talk.

Congratulations to Gini Bailey, Jonathan Moriarty, Matt Song, Jon Schubbe, and the other GDC members who helped make the day a success.

### Old Games: Clerk’s Naval Tactics

Tuesday, May 4th, 2010

Plate VI, Part I. p.52, Fig. 3 from Clerk's Essay on Naval Tactics

John Clerk was a Scottish businessman who studied many things, among them, naval warfare. His book, “An Essay on Naval Tactics,” changed how the British Navy fought Napoleon, and contributed to his defeat.

It was written without naval experience, but with a good understanding of how ships can move and damage each other. So: accurate movement restrictions, realistic measurements of giving and taking damage– it’s a game. It changed the world.

Google Books has an original edition of the book, as a PDF, free for download, at : books.google.com/books?id=LsdPpUcYxD4C. This version was printed in 1827.

### “Slug” wins at WV Animation Festival

Monday, May 3rd, 2010

“Slug” is a game being developed in our team-based game class. It just won 2nd place at the 2010 West Virginia Animation Festival.