Collision Detection

[Kaz]

Over the summer I created a little openGL program that implemented a camera, and not much else. As the summer came to a close I was in the process of reading about collision detection, but had to stop working on the project because school sucked up all my time. Fortunately, I've been able to pick it up again, and now I have a couple of questions that perhaps some of you could answer:

What is the general process that takes place in Quake 3 for collision detection? Is geometry defined in terms of triangles? What tests are at the heart of a game engine?

I've been searching the internet, reading certain sections in Computer Graphics Principles and Practice, and checked out Graphics Gems IV. I've been able to wrap my head around testing to see whether a point is inside of a triangle or not; I see a bunch of trees but don't know what the forest looks like.

[^misantropia^]

Q3A uses a bounding box for collision testing, not a per-surface test (D3 and Q4 do, though). Collision testing is fairly straightforward: a line is drawn from A to B and the game checks if any objects (read: bounding boxes) are in its path.

Remember how a model in Radiant is non-solid and how you have to put an invisible but solid brush around it? That brush is your bounding box.

[Kaz]

Well, I get that much, I was wondering what the procedure is for testing the players bbox against world (and other) geometry. For example, is there just a huge array of triangles that it runs through and tests each one?

[f0qu4k3]

IIRC it uses different methods for collisions objects. uses planes that define a convex region for brushes. AABB boxes for players. Probably something else for patches.

[^misantropia^]

Kaz, take a look at qcommon/cm_trace.c, most of the relevant code lives in that file.