Tag Archives: spatial hashing

Beam Weapons and Epic Battles

Beam weapons are now fully-implemented (the previous implementation was just a hacky prototype). A nice detail of my current weapon implementation is that turrets on ships actually rotate to track their target. It's pretty cool seeing those massive turrets on capital ships swivel towards an enemy ship, then rip them apart with a huge beam of energy.

I'm doing some stress tests with loads of ships in a free-for-all just to see where the bottlenecks in the engine are located. Not surprisingly, almost all of the time is spent in the code for pulse and beam weapons, performing the necessary scene raycasts in order to make collision work. I've already accelerated this a lot with a spatial hashing structure, enabling fast raymarching for short rays (pulses and beams qualify for this). Then, there's a world space AABB test and, finally, OPCODE does its thing with those AABB-trees.

Apparently I've done a pretty good job of optimizing so far, because I can handle about 50 ships in an all-out, epic war before my fps drops below 60. Still, I'd like to push that number to at least 100. I'm not going to settle for limiting the number of ships that can be in an engagement in this game - if you've got the cash to hire a hundred wingmen, you should be able to use them!

Spatial Signatures: Even Faster Collision Detection?

Yes, I'm quite happy with my collision detection engine. But could it be faster? Probably!

Here's an idea I had today. Obviously, I'm obsessed with spatial hashing. It's probably my favorite thing ever. Well, what about this: take a mesh, create a spatial grid of booleans (which can, of course, be represented super-efficiently as a bit vector), then loop over every triangle in the mesh. For any spatial grid that the triangle intersects, the corresponding hash bucket gets set to true. Once this has been done for all triangles, you are left with an array of bits that represents the spatial buckets with which the mesh collides. Purely for the sake of being able to throw around cool and esoteric terminology, I'll call this array the "spatial signature" of the object.

Now, here's the fun part. In my previous technique, I looped over the vertices of one mesh, checking them against the density function of the second. The most expensive part of this check is, without a doubt, evaluating the density function. Well, instead, we could prune the possibilities by first checking the vertex against the spatial signature of the object! It's quite inexpensive to hash the vertex to a bucket in the same space as the one in which the spatial signature was created. Then, we simply check the corresponding index in the bit array. If the array indicates that no triangles intersect that spatial bucket, then there's absolutely no chance that the vertex could be colliding with the mesh. On the other hand, in the event that the bit is turned on, then we continue as before with the full-blown density check.

This is, of course, a completely untested idea, but it seems to me that the speed with which a bit array could be accessed would significantly cut down on the narrow-phase collision check, especially when dealing with complex density functions.

Full-Blown Collision Detection: Working!

The war is over; the battle has been won. For now.

I merged the previously-discussed narrow-phase collision engine with the broad-phase spatial hashing engine that I wrote a few months ago, and the results couldn't have been more pleasing! Everything works just as I had wanted, and now the whole collision detection system is as simple as adding objects to the engine, then requesting collision reports in the update step. Everything else is handled automatically - and it doesn't require choosing a certain type of collision mesh or pre-building any special data for collision detection! All it requires is the density function that was used to generate the object's mesh. Furthermore, it's fast :D

I also made a minor optimization to the spatial hashing engine that's worth mentioning, as it kicked my framerate back up to 60 when doing collision detection on the large, rotating space station in my demo had taking it down to 10 fps or so. The idea is that, when adding an object to spatial buckets, it's a good idea to 'over-allocate,' so to speak. In other words, scale the bounding box by 150% or so, then add this enlarged box to the spatial buckets. It may waste a few checks in the broad-phase cycle, but it cuts down on the frequency with which you have to change the spatial buckets around, which I found to be a huge bottleneck for really large, moving objects (especially when the spatial grid is kept relatively small).

If you do the aforementioned, then when an object moves, you need only modify the spatial grid if the object's new bounding box isn't contained in the 'over-allocated' one. Now, if you've got a grid size of 1 and a battleship that's 50 x 50 x 50, suffice it to say that it's going to get really expensive, really fast to update the spatial grid every frame if the battleship is moving. So don't!

A celebratory shot of me swooping triumphantly over the station, headed back toward the mothership:

Spatial Hashing

I've been working on a physics engine for XDX (I know, it's excessive, but I want to learn how to make *every* component of a game). Spatial partitioning has been getting me down - in particular, octrees are painful because of all the edge cases that have to be considered - especially when one cannot restrict the system to a given space...because I'd rather my games be able to handle "infinite" space.

Last week, I found the answer to all of my problems: spatial hashing. It's a really beautiful scheme, and since it uses a uniform grid for the partitioning, it's particularly simple to implement. However, the fact that grid cells are hashed to buckets means that the flexibility is unrivaled: not only can one specify the size of a grid cell, but one can also specify how many buckets will be used to attach to grid cells. The system easily handles infinite space (since the hashing function works for any x,y,z triple).

I'm pretty excited about the implementation of this collision detection system, and I can't wait to see what kind of results I get! Physics-enabled space games may not be so far off for XDX!