Month: June 2005

For some odd reason VS.NET doesn’t have the built-in capability to switch between .h and .cpp files from the keyboard. Almost every other programming editor I’ve used has this ability. A lot of people think that it’s just not possible in VS.NET

Well, it is, but it requires some programming and configuration. Fortunately, the program has been written many times by other programmers, so all you need to do is some cut and pasting. Here are the steps:

1) In VS.NET go to Tools -> Macros -> Macros IDE

2) Create a new Macro module under “MyMacros”, call it “Switch”

3) Visit The Code Project and copy the code for the “Switch” module into your new macro you just created.

4) Save changes, close the Macros IDE

5) Verify it works by going to Tools -> Macros -> Macros explorer, finding your new macro, right-clicking it, and selecting “Run”

6) Assign a shortcut to your new macro by going to Tools -> Options -> Environment -> Keyboard and typing “Switch” into the search box.

OK! Now you can get some REAL work done!

Thanks Keith for pointing me at Fluxus, a real-time audio visualization package written (and tweakable) in lisp. It even incorporates some physical simulation features using ODE. Fun!

This just bit me in the ass. I thought flagging a method in a class with the ‘const’ keyword was just that: a flag. It’s not. It’s an entirely new function. For example, these two methods have different signatures:

class thing {
virtual foo();
virtual foo() const;
};

If you have a child class that overrides the parent, you will NOT get a friendly compiler warning if the const’s don’t line up. Boy, did this introduce interesting bugs into my code…

class mything {
virtual foo() const;
};

class myotherthing : public mything {
foo();
};

The parent was getting called instead of the child. Took me half an hour to figure out what was going on. Pesty const! I’ll never use you again! I thought you were my friend…

So…. If you have two functions foo(), and one’s const and the other is not, which one gets used when you make a call to foo()? Ahhhh?!??!

UPDATE: Hey I figured it out, this is actually in Effective C++ by Scott Meyers. When you are working with an object that is const, such as one that you got via a pass-by-const-reference, then the const version of the method will be invoked. Otherwise, the non-const version will be invoked. Assuming they both exist. If neither exist then whichever one does exist is the one that will be used.

I recently received an email from Christophe Delépine about precision issues in geometry clipmaps. I thought this information might be of interest to others so I’m just gonna post my reply here.

Christophe: In Hoppe’s original implementation (without vertex textures), vertex coordinates are stored in VBOs and updated toroidally as the observer moves. If i understand well, this has an important consequence: vertices must have absolute world coordinates. The problem is that you loose precision if coordinates are stored as floats instead of doubles. This makes it impossible to render very large terrains. Do you agree?

It depends upon how you implement things. When I first started writing my USGS terrain renderer I naively rendered everything in global coordinates and I experienced a huge loss in precision whenever I wanted to perform any operations on the terrain. Back in April I wrote:

Robert: I should mention that I encountered some horrible floating point error dealing with UTM coordinates. The coordinates for Corvallis are something like (470187.46959, 4927222.852384). Big numbers. The spacing between heights in the elevation data file are somewhere around 0.00087. Well I can’t just go around adding floating point numbers of such different magnitudes together and expect things to work (I tried, heh), so I got around this by translating everything to the origin and working with the elevation and geotiff data in reference to 0,0 instead of those huge UTM coordinates. Everything is still UTM, it’s just offset by a lot.

The solution to this problem was to move the origin closer to the data I was rendering and then store the data as offsets from the new origin. If you want to render a very, very large terrain I’d imagine your implementation would need to segment the terrain into smaller chunks and then store these chunks as offsets from their respective origins. Maybe a technique that combines quadtrees and geometry clipmaps?

I’m not sure what you would do near the edges of the quad patches.. Maybe your GPU clipmap code would need to be smart enough to pick which dataset to sample from and recalculate the offsets accordingly. I can imagine a shader program that would take 9 different sets of heightmaps, one for each of the possible quad patches it could hit. Maybe it could take only 4 and the CPU program would be smart enough to know the other 5 that it’s not likely to hit because it’s not near those edges.

Christophe: In Hoppe’s second implementation (GPU-based), VBOs are never updated and (x,y) coordinates remain constant. The floating point precision problem disappears but the grid is still flat and does not follow the earth curvature

I don’t know what they are off the top of my head, but there are transformations that can take a UTM coordinate (x,y and height) and put it into a spherical coordinate that is consistent with the earth. It’s probably a trivial manner to do this on the GPU.

I think you might have a floating point precision issue however. If you’re working with full UTM coordinates on the GPU then a transformation that projects them into a spherical space will probably suffer from a large loss of precision. The solution? I’m not sure. If you store the data as offsets from a moving origin then your spherical coordinate transformation will need to take that into account. I’m not sure how that would work, but it could probably be figured out.

Christophe: Another difficult problem which is somewhat related is the mapping of clipmapping texture onto the terrain geometry. Let suppose i have a huge clipmap texture that i want to map on the terrain. My current clipmapping implementation assumes that UV coordinates in the texture are proportional to latitude & longitude.

Again, if you store the terrain data as offsets from a moving origin then this makes the texture mapping problem easier. Terrain data at the origin is u,v = 0,0 and terrain data at the next origin is 1,0 or 0,1.. you get the idea. This would only work if your texture was very large, because you’re going to want to do geometry clipmapping within each of these large patches. Yeah.. things will get tricky if you have a high-resolution texture that you’re trying to map, but there’s probably a way to split things up.

Christophe: Now, if terrain is represented as a grid where points have constants x,y coordinates, then i would have to find the corresponding latitude/longitude for each point to get the correct UV coordinates. This does not seem trivial to me.

First you translate the constant x,y coordinates to world/patch space on the GPU, then you find their UV coordinates:

U = (x – xoffset) / xpatchwidth
V = (y – yoffset) / ypatchheight

Bush 4 Life

House republicans proposed a bill in February that would repeal constitutional amendment 22, which limits presidents to only two terms in office.

I found this amusing because the first thing that came to mind when I read this was the cheesiest line from the latest Star Wars movie: “And so this is how democracy is lost… with great applause.” LOL…

I also find it amusing that republicans think they can only win the next election by putting up Bush again. Come on. Bush isn’t a rarity. There’s got to be plenty of other people that could replace him. All you need to do is find someone that’s graduated from Yale and then send them to the Rove-Rice College of Acting Presidential. Living in Texas I think would be a plus, but I don’t think it’s necessary. Teach them to coin new words on the fly “accidentally” so that they appear to be “from the people.” Most of all, make sure they’re VERY anti-abortion.

Speaking of Condoleeza Rice, why not put her up? Get her in the news more over the next year and you just might have something there.

I love DotA Allstars

I’m going to go out on a limb here: DotA Allstars (doh-tah) has got to be the best non-mmo multiplayer game I’ve ever played. If I were a big-shot game reviewer I would declare it the best multiplayer game ever. Prior to DotA, I felt that Counter Strike Beta 6 (before the cheaters), NeverWinter Nights (lan party or persistent worlds) and Star “who needs some gas” Craft had a three-way tie for the best multiplayer game ever made. It’s hard to compare apples to oranges, but dota brings elements of all three of these games to the table and blows each of them out of the water. If I had to pick one game and throw all others away, I would spare Defense of the Ancients Allstars.

If you haven’t played dota, please allow me to clue you in. Dota isn’t a commercial game. Dota is a custom map for Warcraft 3. To play it, you need to buy a copy of the “Warcraft Battle Chest” which includes the Frozen Throne expansion for WC3. To get a game going, download the map (link above), open WC3, go to BattleNet and click on Custom Games. You’ll notice that more than half of the custom game action on BattleNet is Dota.

Dota is one part real-time strategy, one part team strategy and one part roleplaying. Unlike regular real-time strategy games, you only control one character, your hero. You pick this hero at the beginning of the game and you have to stick with it the entire game. Dota has about 50 heros to choose from, each with their own level track and special abilities. To help your hero you can buy items and recipes that combine items to make new items. The possibilities for item/hero combos are endless.

Dota is played with two teams, up to five players each. Typical games are 3v3, 4v4 or 5v5. Each team has a base in opposite corners of the map connected by three main arteries and a few offshoots to help you get between them. Each team auto-spawns creeps that run down the arteries and meet eachother somewhere in the middle. The goal of the game is to slowly tilt the balance of the creep fights closer and closer to the other team’s base, eventually bringing the creeps into thier base and hopefully destroying it.

My favorite feature of dota is the play time. Dota fixes a major problem I had with StarCraft: if both teams were good, the games could end in a stalemate. I once played a StarCraft game that went on for 5 hours and the only reason it ended was because someone had to go to the bathroom. Dota is set up perfectly so that the games rarely go past an hour, typically games end within 45 minutes. This happens for a number of reasons, but mainly because the creeps and heros get so strong that eventually one team can’t handle it. Sometimes the balance of power shifts so much that all seems to be lost, but this is what makes for exciting dota: the big comeback. Some of the most exciting dota games I’ve played are ones where a few teammates dropped out because they thought all was lost, so the other team gets cocky and starts slipping up, then we make a huge comeback. Good times.

Dota isn’t without problems. I think if dota were it’s own stand-alone game it wouldn’t sell millions of copies until a few problems are fixed.

The first major problem is leavers. Some people don’t like losing, so they leave the game at the first sight of getting pwned. Although the rest of the team can loot their items, if they were a total noob that doesn’t buy them much. Here, there’s not much dota can do because the game is at the mercy of the WC3 game engine, but if I were to make dota a stand-alone game I would allow people to join games in progress. If someone leaves, another should be allowed to take their place, much like Counter Strike and other team FPS games. A lurker/observer mode would help facilitate this–you could tag in/out with lurkers if you’re about to leave.

The second major problem is lag. RTS games completely freeze when one person is experiencing lag. Here, dota could take a lesson from FPS games again and just NOT completely freeze the game. Since dota is pretty much single-character it doesn’t matter much. Just lag the person, let the other people pwn them, and then they’ll leave. Since you’d be able to join a game in progress this wouldn’t be such a big deal. I really hate that WC3 doesn’t have a built-in latency checker when joining a game. Stand-alone dota would definitely need one.

That’s about it. The only problems with dota are things dota can’t do anything about.

In a previous post I thought the Intel-Apple talks were over XScale processors. I was wrong. As announced at WWDC this week, Apple is indeed going to be using Intel chips in their upcoming computers.

I think this is a bad move. Not because they’re using Intel chips, but because they’re using the wrong Intel chips. x86/IA32 is a dead-end road. Intel even admits that x86 is not the future. x86 is a 20 year old instruction set archiecture. No one respects it.

Going with Itanium/IA64 would have been a bit smarter. Intel could probably even produce a special line of Itanium chips that does microcode emulation of PowerPC, much like the line HP made that did dual IA64 and PA-RISC. I think that would have been much smarter.

I was also incredibly wrong when I wrote previously that developers would throw fits if Apple changed things up again. I forgot that MacOS X apps are compiled with gcc. Switching targets would just mean setting some compiler flags. -ppc vs. -x86. Since Apple evolved the magnificent Bundle format for OS X making applications “dual platform” would also be a snap.

The big unknown that’s left in my mind is: will the rumored “OS X 10.4.1 x86 Preview Edition” run on standard PC hardware, or will it require the “Developer Transition Kit?” If I could run OS X on cheap-o hardware I definitely would. I guess we’ll have to wait two weeks to find out, since that’s when it’s scheduled for release.

Actually, will Apple make OS X available for x86 on non-Apple hardware at all? Darwin x86 has been available for a long time. I predict Apple will probably do one of two things: a) build in some special hardware that OS X can use to identify the system as an Apple or b) write in some insane operating system copy protection much like Microsoft’s. Apple would be basically be killing off their hardware division if they released OS X for x86 without any kind of protection… or maybe that’s the plan… ?

Link

In a previous post I wrote about some optimizations I was trying to make to geometry climaps. I’ve summarized my work and posted it at the link above. There’s also a video!

I think the real contribution here is the normal blending technique that I came up with. It uses 1/4 the memory of the previous geometry clipmap work and doesn’t look 1/2 bad. 🙂

I’ve been working on recreating the research of Losasso, Asirvatham, and Hoppe on GPU-based Geometry Clipmaps. One of their articles on the subject appears in GPU Gems 2. Geometry Clipmaps are a simple approach to rendering large terrains. The basic idea is you create fixed donut rings of varying LOD and then displace these rings using a heightmap in the GPU’s vertex shader. Offloading the displacement into the GPU is a significant performance improvement as it avoids continuous recreation of vertex and index buffers.

This week I implemented two ideas that I thought would be improvements to the Geometry Clipmap algorithm presented in GPU Gems 2. The first I call the “view dependent” approach. In Asirvatham’s paper the clipmaps are oriented along the x,z plane and move only when the camera exceeds some threshold. Every frame, the positions of the clipmaps must be recomputed by the CPU and then passed to the GPU. The “view dependent” approach attempts to skip this step by fixing the clipmap meshes in view space.

Imagine the intersection of the view frustum with the plane of the clip maps. It forms a large trapezoid that extends out to infinity. The view dependent approach fills this trapezoid with triangles that become denser closer to the camera and more spaced out as you move away from the camera. On the GPU, view space is transformed back into world space and then the world space coordinates are used to sample the height map. The advantage of this approach would be the vertex and index buffers would be 100% fixed and no transformations would ever need to take place on the CPU.

I implemented the view dependent approach and ran into some interesting problems that make it apparent why Asirvatham et al choose to orient the clipmaps in the x,z plane. When the view frustum is oriented at an even 0, 90, 180, 270 degree angle everything looks perfect, but as you rotate the camera in between these angles you get a stair-stepping effect in the terrain. This is because the points sampled on the heightmap are no longer “even” sample points, and you get an effect similar to drawing a line without anti-aliasing.

To combat this problem I tried solving it the same way you would if you were doing anti-aliasing: super-sampling. Instead of sampling at the point given by the transformation, I sampled 4 points around that point and averaged the results. This did indeed smooth the stair-stepping effect, but just like even anti-aliasing in a ray tracer, you’re just offloading the problem further back into the scene–the stair-stepping was still there, it just wasn’t as apparent.

Another way to combat the stair-stepping effect that I want to try would be to sample only the floor of the transformed points and move the transformed geometry in the x,z plane to an even interval. This might get funky, but I’d like to try it.

The second optimization I tried with geometry clipmaps was a simpler clipmap. In Asirvatham’s paper he uses a very unusual clipmap pattern so that transitions from one LOD to the next are always half the detail, and so each LOD ring has the same width. There’s no other way to get half detail and fixed width without using an unusual spiraling pattern. (Look at the paper, you’ll see what I mean). A simpler approach I thought would be to have transitions go to one third the detail and three times the width, kind of like an expanding checkerboard. Picture a Pascal’s triangle of Purina dog chow logos. This optimization worked pretty well. I believe I’m using significantly less geometry than Asirvatham’s approach. It doesn’t look quite as good, but it’s definitely functional.

Because the LOD tapers off much faster with this approach heightmap aliasing effects become apparent much faster, and it made me aware of a serious deficiency with geometry clipmaps that you don’t have with other terrain rendering algorithms. If you have a mountain off in the background, and that mountain has two peaks, it might look like just one wide peak depending upon how it’s sampled. Irregular mesh approaches don’t have this problem as they perform mesh optimization based on changes in slope. Geometry clipmaps just sample willy-nilly regardless of the consequences. A geometry clipmap approach that takes into account the silhouette differences of the resulting terrain might yield better results.

Once I get this project wrapped up I’ll post screen shots.