Articles by olano

Marc Olano is an Associate Professor in the CSEE department at UMBC and Director of the Computer Science Game Development Track. Dr. Olano’s primary area of research is real-time 3D graphics, with forays into other applications of programmable graphics hardware.

Sometimes you want to uniformly distribute some objects over an area. Maybe they’re trees, maybe just blades of grass, maybe an army of guys. Whatever they are, there are a bunch of ways you could try. Here are a few.

These differ in the distribution of points and ease of generation. For distribution, the important characteristics are whether it’s clumpy or evenly spaced, as well whether it’s regular or more random. Ease of generation depends a lot on how you’re going to use it. If you can precompute positions, the complexity doesn’t matter too much. If computed at load time, the complexity might matter a little. However, sometimes you want to be able to quickly answer questions about the distribution without necessarily knowing the location of all the points. That could be “where is point n” (useful for shader-based instancing), or “are there any points near here” (useful for generating partial layouts, or proximity queries).

Easiest (and ugliest) is the uniform grid. If these were tree positions, they might do for an orchard, but would look really strange for a natural forest. You can easily find point n without placing all of the other points, and just as easily find nearby points by searching the neighboring grid cells.

We could do a little better on the layout with a hexagonal grid, since that’s the natural tightest packing on the plane. The points lie in little equilateral triangles. To keep the spacing even, we need to squish the vertical spacing by the height of an equilateral triangle, sqrt(3/4) ≈ .866. To keep about the same density, it comes out to s=sqrt(sqrt(3/4)) fewer rows in y and 1/s more columns in x. The closest integer layout near 16×16 is 15×17, so we have one fewer point. Since this is basically a skewed grid, it is still easy to find point n independently of the other points, and also not too hard to find nearby points. However, it’s still pretty regular, with all the points in nice neat rows.

The last of the deterministic layouts is a Hammersley sequence, one example of a quasi-random sequence. For Hammersley points, the x is just the point number, and y is the point number with the bits reversed. There are definitely still patterns, but no long rows of points. Once again, it is easy to find the location for point n, but much harder to find nearby points. They’ll be near in sequence to n, which guarantees their x is close, but some of those points will have vastly different y. You can play some bit tricks to reduce the search set, or just sweep through the points nearby in x.

The rest of the examples are all different flavors of random distributions. The first chooses each x and y as independent uniformly distributed random numbers (= calls to random() or rand() or drand48() or whatever your random number generator you happen to be using). Since the points are each independent, in theory point n shouldn’t depend on any of the other points. In practice, random number generators keep some state and return numbers in a sequence. That means for most random number generators, you’ll have to run through points 0 to n-1 before you can get the location of point n. There are stateless random number generators (see our High Performance Graphics paper for example), which let you break that artifical dependence and get the points in any order. Nearby points are hard to find without some auxillary data structure though, since any point in the list may be near point n. Also, the independence introduces some heavy clumping, which is usually not good.

The jittered one avoids some of the clumping by going back to the grid. Each point is placed in a random location within its grid cell, but every grid cell has a point and only one point appears in any grid cell. With a stateless random number generator, you can place point n without dependence on the other points. However, now proximity tests are once again possible by looking at the positions in nearby cells. Since the points may appear anywhere in their cell, you need to look at all cells that intersect the search radius. Jittered grids do have some clumping though, since “anywhere in the grid cell” could include four points all landing near the same corner.

The last example is a Poisson disk distribution. This is a random distribution where each point is no closer than a given radius to any other point. There are gobs of algorithms for generating these, though all that I know of require pre-generating the entire distribution. This particular plot was created with a dart-throwing algorithm, where you choose a random location, toss it out if it is too close to any previously placed points, then try again. Dart throwing is about the least efficient way to generate a Poisson distribution, but it’s easy to find other more efficient algorithms. You usually need to create some spatial data structure to help find nearby points, so if you keep that structure around, proximity queries are not too bad. Actually, jittered grids were first introduced to graphics as an approximation to the Poisson disk distribution, though the real thing is clearly much more evenly distributed.

If you’re curious, all of these were created with a point-placement vertex shader. Random numbers were two iterations of TEA (the Tiny Encryption Algorithm, see the above paper) on the point index. The blue component of the color is the point index, while red and green are randomly chosen based on the index.

Anyone who’s done any 3D graphics knows how to use homogeneous coordinates for translation and perspective, but they’re good for other places where you’d rather put off a division or avoid it entirely.

Basic homogeneous coordinates use four coordinates (I’ll use lower case to keep things straight) to represent a 3D point (here in upper case)

p = [x y z w]
P = [X  Y  Z] = [x/w  y/w  z/w]

Or more compactly, in shader notation

P = p.xyz / p.w

For regular points, we use w=1. If w=1/2, we get a point twice as far out in the p.xyz direction. If it’s 1/3, we get a point three times as far out in the p.xyz direction. In the limit, as w goes to 0, we get a point infinitely far away in the p.xyz direction.There’s no need to worry about a pesky division by 0, as long as we don’t ever actually have to do the division for the evil w’s.

That’s the basic idea behind my homogeneous rasterization paper (sometimes called clipless rasterization), used in quite a few GPUs. You normally compute the intersection between each triangle edge and a clipping plane to throw away the parts behind you where w might be 0 or negative. If you put off the division and keep everything in homogeneous coordinates long enough, eventually you can get all the way to visible pixels on the screen, with w’s guaranteed to be positive, before you actually have to divide.

But that’s not what this graphics trick is about. What else can we do using homogeneous coordinates to avoid division? Let’s say we want to subtract two points

V = Q – P = q.xyz/q.w – p.xyz/p.w

I can avoid dividing by putting that over a common denominator

V = (q.xyz * p.w  –  p.xyz * q.w) / (q.w*p.w)
v.xyz = q.xyz*p.w – p.xyz*q.w;  v.w = q.w*p.w

That lets either p or q be infinitely far away. So if P is a point on a surface, and Q is the location of a light, then V is a vector from the surface to the light (I’d use the traditional L, but lower-case l and number 1 tend to look a bit too similar). This will handle both point and directional lights with the same code. Of course, if you know a particular w is always 1 or always 0, you’d factor that constant into the equation in your code. Assuming p.w=1 to make things a little easier, for point lights (q.w=1), that reduces to a vector subtraction between the surface and light location

v.xyz = q.xyz – p.xyz;  v.w = 1

For directional lights, which are infinitely far away in a given direction (often used to approximate the sun), q.w=0, and we see the exact surface position doesn’t matter

v.xyz = q.xyz;  v.w=0

Also, though less common, you can use the same methods do parallel and perspective projection with the same code.

So that puts off the division and keeps everything in homogeneous coordinates, but in many lighting computations, you want a unit length vector pointing in the given direction

normalize(V) = V/length(V)

When you normalize, any scale factor that affects all three components has no effect on the final direction. If V is twice as long, or three times as long, or infinitely long, it still points the same way. In particular, as long as we avoid negative w’s, the division by v.w doesn’t affect the final direction, even if v.w=0.

normalize(v.xyz/v.w) = normalize(v.xyz) = normalize(q.xyz * p.w  –  p.xyz * q.w)

It’s amazing how far you can get with two simple rules: if the division might blow up, put it off. If a constant scaling won’t affect the result, don’t do it.

Marc

This time, how about polygon area (plus circular loops).

The area of a 2D triangle is easy, it’s just half the magnitude of the cross product of two edges where you assume the z component is 0:

|cross((v1−v0),(v2−v0))|

The sign of the cross product tells you if the triangle is front or back facing (counter clockwise or clockwise). If you multiply out the cross product, it has an interesting repeating pattern if you collect it in terms with pairs of indices i and (i+1)%3

(v1.x−v0.x)*(v2.y−v0.y) − (v1.y−v0.y)*(v2.x−v0.x)
= v0.x*v1.y − v1.x*v0.y  +  v1.x*v2.y − v2.x*v1.y  +  v2.x*v0.y − v0.x*v2.y

As a bonus, for 3D triangles, the cross product points in the direction normal to the triangle, and its length is twice the area of the triangle. What’s more, the cyclical pattern appears again for each component (the order and signs here make more sense if you consider x,y,z to have their own mod cycle as well: x is followed by y is followed by z is followed by x …)

n.x = v0.y*v1.z − v1.y*v0.z  +  v1.y*v2.z − v2.y*v1.z  +  v2.y*v0.z − v0.y*v2.z
n.y = v0.z*v1.x − v1.z*v0.x  +  v1.z*v2.x − v2.z*v1.x  +  v2.z*v0.x − v0.z*v2.x
n.z = v0.x*v1.y − v1.x*v0.y  +  v1.x*v2.y − v2.x*v1.y  +  v2.x*v0.y − v0.x*v2.y

As a loop

n = float3(0,0,0);
for(int i0=0; i0<3; ++i0) {

int i1 = (i0+1)%3;

n.x += v[i0].y*v[i1].z − v[i1].y*v[i0].z;
n.y += v[i0].z*v[i1].x − v[i1].z*v[i0].x;
n.z += v[i0].x*v[i1].y − v[i1].x*v[i0].y;

}

Maybe overkill for a triangle, but the cool thing is that the same basic pattern works to find the area of any planar polygon with non-intersecting edges. It doesn’t even need to be convex. Just change the loop limit and mod from 3 to N. Just like the cross product, the magnitude will be twice the polygon area, and the sign will tell you if it is front or back facing.

Why does it work? It’s a simple application of Green’s theorum (or Stoke’s theorum in 3D). Bet you never thought you’d see that again, huh?

Mods add ugly unnecessary conditionals inside the loop, but if you shift the loop order a little, you can actually get rid of the mod:

for(int i0=N-1, i1=0;  i1<N;  i0=i1, ++i1) {

// loop order
// i0=N-1, i1=0
// i0=0,   i1=1
// i0=1,   i1=2
// …
// i0=N-2, i1=N-1

}

Extra bonus facts: in 3D, the resulting vector points in the direction of the polygon normal with length equal to twice the polygon area (just like the triangle cross product). Also, if you do it for the 1-ring of vertices around a given vertex (the vertices one edge away from a given vertex), you get exactly the triangle-area weighted average normal. Yes, that does mean that the area-weighted vertex normal doesn’t actually depend on the vertex position at all. Wierd, huh?

Marc

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

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

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…

There’s a long interview on Gamasutra with local game designer Brian Reynolds (co-founder of Big Huge Games, now with Zynga) about what it’s like to transition from big strategy games to facebook and social games. Worth the read.

This weekend, I was honored to be a judge for the Imagine Cup National Finals. They have two competitions for students, one for Software Design and a new one this year for Game Design. Of course, I was there as a Game Design judge, as was UMBC grad and adjunct faculty member Katie Hirsch of Firaxis Games. This year’s theme was to create a game reflecting one the UN Millennium Development Goals: hunger and poverty, universal primary education, gender equality, child mortality, maternal health, HIV/AIDS and malaria, environment, and global partnership.

Of the 269 entries, ten games made it to the finals. I was on one of the two judging panels that met on Saturday to select the final four games to advance to the final round on Monday at the Newseum in DC. Monday included a presentation of the final four games, a showcase of all ten finalists, and keynote addresses by director James Cameron, Microsoft Chief Research and Strategy Officer Craig Mundie, DOE Director of Educational Technology Karen Cator. The winners were:

  • Grand prize and $8,000
    Sixth by team “To Be Announced”, a puzzle game in which you play a child in a slum, trying to find drinking water for your family. You find items you can use or trade in your quest and meet people in the slum who can help you along the way. The goal is to educate players about the struggles of the worlds poor.
  • First prize and $4,000
    Alterra by team “Coffee Powered Altruism”, a strategy game ambitiously addressing all of the UN Millennium goals. For each one, you are shown a map of a real country with dots representing population (above and below poverty, educated vs. uneducated, etc.), and you attempt to drag in job training centers or other tools to change the makeup of the population without exhausting your budget.
  • Second prize and $3,000
    RoboRecycler by team “Ifrit Salsa”, a kids game where you are a robot collecting items and getting points for depositing them in the correct recycling bin.
  • Third prize
    Antitoxin Squad by team “LeveL13”, a cooperative two-player game where you plant seeds to defeat the pollution blobs.

Teams ranged from High School students to PhD students, and games from 2D sprites to full 3D FPS. Overall, an excellent set of games and a great experience. I’d certainly encourage some of our students to try next year.

Marc Olano

Brian Reynolds has a long history in Baltimore area game companies, from the beginnings in MicroProse, to Firaxis to co-founder of Big Huge games. These days he’s Chief Designer at Zynga. He’ll be talking at the Baltimore IGDA meeting tomorrow (Thursday, 2/25) at 7pm at the Greystone Grill in Hunt Valley. Check it out.

Well, my intention to have an update of favorites every day clearly didn’t last past the first day. So, of two more days of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, here’s what stood out to me…

Read the rest of this entry »

« Older entries § Newer entries »