I've gone through a plethora of resources on collision detection and response, and as a result I've managed to implement a fairly robust routine for my engine, which currently uses brushes for meshes and spheres for actors. It is modeled after the Quake 2 source code, which has been a treasure trove of a resource to learn from. As a result I love brushes - they're simple, they support any convex shape, can be trivially extended to boxes and k-DOPs and, most importantly, are very cheap to test.

However, there are a few questions that I'm unclear about:

1) I'm guessing brush-based collision either is or is becoming passe in modern engines in favor of a more expensive polygon soup approach, which is woven directly into the physics engine. If nothing else, then one glaring reason for this stems from a fairly subtle point that annoys me more than it perhaps should. Which is corner turning:

[attachment=28567:brushcollisioncorner.png]

Notice the gap between the circle and the rectangle. The circle collided with the rectangle and slid down its east wall as it was trying to move south-west. Hence, due to the direction vector, it wants to go right as soon as possible (or left, depending if you're the circle or the player ). As it approaches the bottom of the rectangle, it should hug the corner, but it can't, because it happens to be stuck behind the rightmost plane of the brush until the circle's top extent clears across the brush's bottommost plane, at which point it is no longer potentially inside the brush and can safely move west. As best I can tell there's no way to overcome this in a brush-based collision system short of adding a bevel to the corner of the collision brush itself. If anyone can suggest a way to around this behavior, I'd love to hear it. The thing is, I don't think this is even noticeable in a 3D game, especially if you're in first person perspective. But in an ortographic world it quickly becomes evident and soon enough fairly annoying.

2) Translating brushes is fairly trivial. However when it comes to rotating them, as best I can tell, it's easier to just rebuild the entire collision brush from scratch. I've yet to find a plane rotation routine that doesn't boil down to recalculating the plane equation. That being said, it's likely still cheaper than rotating a polygon-based collision mesh.

3) I started messing around with a GJK handler for moving objects a while ago and got it to work with two spheres. However, I kind of got stuck extending the code to brushes. At least it wasn't as trivial as I would have hoped (more to the point, support calculation for brushes turned out to be less than trivial, especially with rotation thrown into the mix). Incidentally, GJK wasn't around when Q1 and Q2 were written, so who ever wrote the collision code opted for a fairly "cheap" workaround for the sweep test - essentially the collision brushes are expanded to simulate the Minkowski space, which then allows point-brush collision testing without using anything as fancy as supports. It's pretty nifty in theory, but I don't think it handles brush collision with anything other than a sphere (or a capsule that's squished into a spheroid).

While points 2 and 3 are a matter of time and research to overcome, I'm still unsure what to do about point number 1. I've gone so far as to consider adopting Bullet, but frankly I've put so much time into this and learned so much, that I don't want to throw it all aside...

What is a brush? How is it represented in memory? I'm assuming a tree of planes, but people use the term brush to mean a lot of different things.

What is a brush?

This largely stems from the Quake 2 source code, which has been a treasure trove of a resource to learn from. As a result I love brushes - they're simple, they support any convex shape

Notice the gap between the circle and the rectangle. The circle slid down the east wall of the rectangle and due to the direction vector wants to make a right turn

That direction vector doesn't look like it will hug the corner. If it were between 180° and 185°, then it may do a better job hugging the corner. In which case, I'd do direction vector -> resolve collisions -> normalize to current speed.

I think you misunderstand - ideally the circle should always be moving left, hugging the corner along its circumference as it passes the right edge of the mesh and moves below the bottom edge (hence there should not be any gap). In the image the circle was sliding down along the wall and was always pulling to the left, but the problem is that it won't manage to actually start moving around the corner before its "bounding box" (or rather its top extent) moves beyond the brush's bottom plane. The behavior is always there and really trivial to demonstrate - it just might not be as evident from a still image. I spent some time trying to figure out the cause and as best I can tell it has to do with the way collision works with brushes. Consequently I don't see a way around this behavior. Think of it in another way - if the collision hull was a box, it would hug the corner properly whereas any other shape won't.

Don't get me wrong - I'd love to be proven mistaken, though!

From my understanding (and it has been a long time and I am not sure if I remember correctly!) the brushes were inflated by the sphere radius and exported this way. This is essentially a Minkowski sum and what created the bevel planes in Quake. Then the whole movement code becomes simply point versus plane (which makes it so simple). I can ask how that worked exactly and post here tomorrow, but...

...to be honest (as you expected already yourself) brushes is a totally outdated technique and a total waste of time learning this. I would study AABB trees on triangle meshes, GJK and SAT. This is much more valuable in my opinion, though not as easy as point vs plane.

PhysX has released its source code and it ships with a character controller. A good place to start learning about character controllers.

HTH,

-Dirk

A couple reasons that brushes aren't popular anymore are the technical limitations (requiring beveling for not-very obtuse angles), but more importantly the planes are usually assorted in a binary tree. The binary tree isn't often a very cache-friendly structure, and can take a lot of work to coax the memory layout to something optimal. Instead it is often easier and faster to use AABBs for broadphase, some N^2 loops thrown in (with a reasonable N) that can be multi-threaded/SIMD'd, and arrays that can be batched and sent to various threads.

I'm trying to describe the idea that: binaries trees made a lot of sense before hardware speeds rose, and multi-threaded code was less pervasive.

As for rotating a brush, you can often use a transform to represent the world to local space of a brush. This way you can take live objects in world space and do collision detection the local space of a brush. Conceptually this is like rotating the world around the brush in order to avoid recompiling your plane trees.

A couple reasons that brushes aren't popular anymore are the technical limitations (requiring beveling for not-very obtuse angles), but more importantly the planes are usually assorted in a binary tree. The binary tree isn't often a very cache-friendly structure, and can take a lot of work to coax the memory layout to something optimal. Instead it is often easier and faster to use AABBs for broadphase, some N^2 loops thrown in (with a reasonable N) that can be multi-threaded/SIMD'd, and arrays that can be batched and sent to various threads.

I'm trying to describe the idea that: binaries trees made a lot of sense before hardware speeds rose, and multi-threaded code was less pervasive.

As for rotating a brush, you can often use a transform to represent the world to local space of a brush. This way you can take live objects in world space and do collision detection the local space of a brush. Conceptually this is like rotating the world around the brush in order to avoid recompiling your plane trees.

These are very nice points of interest - thanks!

Just to note - brushes have one additional disadvantage that polysoups don't have to worry about: a valid brush needs to represent a closed mesh, meaning that the smallest potential number of plane tests you have to perform in 3D is 5. Indeed, you can usually rely on early outs, but in a polysoup solution you can just throw a single triangle at the collision code and not have to worry about having to deal with topological correctness.