Hi there, So I’m finally at the point where I’m happy with the way my scene is rendering, and now I am interested in adding a limited amount of collision detection. I’ve looked at a few online tutorials such as the one over at NeHe, but I’m not very happy with what I’ve found so far.
I’m looking for techniques that will rapidly help me limit the number of calculations that I need to make. Given that my interaction will likely be quite limited, are there techniques along the same lines as defining a clipping/picking volume that might make the task simpler? I’m going for first person so the only times I will need to make these calculations are for the very limited volume around the coordinates that define perspective and also occasionally when individual objects need to be placed in new locations.
Any ideas?
Thanks
Sam
The simplest and fastest collision detection is bounding spheres. Basically you just need to know the center point of the object and a radius that would surround it, then you simply check if the distance from the player to the center point is less then the radius. Very fast and very easy to do, but it’s also not very accurate.
I figured that something along the lines of bounded spheres would work for basic object collisions, but it doesn’t seem like it could be extended to work with things such as walls. I am perfectly happy to use a combination of techniques, so I’m wondering if anybody has ideas about setting up boundaries for movement within a level? Also, I would be interested in the sorts of experiences people have had with the ray style techniques ( algorithms using dot products, distance formulas etc). If I’m not using a very powerful machine, are these techniques still realistic for every single object in a scene?
The next easy version is bounding rectangles, and in the case of walls it works pretty good. You can combine bounding spheres with bounding rectangles to get a bit more performance. Put a bounding sphere around the object so you can test very fast, if that test passes, then do a bounding box detection.
If your level can get complicated (like most FPS games for example), to avoid checking collisions against everything in the level you are going to need a smarter algorithm , such as a BSP tree or an octree. You will probably want that anyways if the level will require have alot of geometry to render. Using those algorithms you can occlude unecessary rendering as well as unecessary collision detection.
Ok, fair enough, I imagine I can get by with the two techniques combined. For the bounding rectangles function, do i simply calculate the coordinates of the rectangular volumes and then compare the two to see if there is overlap? I know this is a simple problem but I’m having trouble visualizing this for all possible cases. Maybe i should just sit down with a pen and paper.
What you described is pretty much correct for walls that meet on 90 degree angles. It gets more complicated if you allow the walls to have arbitrary angles, in that case you need to take into account the normals of those walls to determine the intersection by the planes the wall forms.
The basic way to see if the player has hit a wall, is by firing a ray out from the player using their orientation. The ray should be fired before the player actually moves, the length of the ray should be the amount the player will move by. If the ray intersects the bounding box then it’s a collision and the player shouldn’t move there.
Just use Odejava…it has all the collision detection stuff for ya already. BoundingBoxes, BoundingSpheres, BoundingCappedCylinder and most important Trimesh collision.
Your level would be a couple of Static TriMeshes and your player be a sphere. Done and dusted. Then when the player moves, make sure you sync ode’s version of the sphere with the player’s location.
Writing your own collision library is a headache, and your only going to reinvent a wheel (yes, another one!). Use whats out there instead of making one your own, otherwise, your moral will go down with every minute you code something boring…
DP
Bahhh!!! Cowards!!! If you don’t build it yourself, what’s the point!?! Are we programming or are we using duplo sets!?! Would an artist start by using the sketch of another artist!?! Would…
Kidding 
He’s right, unless you are doing it to learn, or your building your own API…or your nuts like me and build everything from scratch 8)
Well I certainly wouldn’t have asked the question if I wasn’t interested in doing it myself. I think it’s an interesting question for a number of reason. As a student currently enrolled in linear algebra, I enjoy seeing real applications of the sorts of techniques I have to think about for my homework. And I wouldn’t feel confident in my ability to manipulate OpenGL if I wasn’t able to work through these sorts of problems.
Even so, the API you mention seems useful.
I appreciate all the feedback and I am open to more if possible.
Thanks
Oh, one more thing, you say that the technique with bounding rectangles is really only effective if the walls have 90 degree angles. You mean 90 degrees relative to the ‘floor’, correct? Not merely rectangular rooms?
I mean parallel to the X, Y and Z axis, so ya, kinda rectangular.
Picture a S shaped wall. A rectangle around that would not have acurate collision detection because you could not go into the curves of the S shape. To be able to detect around the curves you need to use the normals that make up the shape to test for intersections of the variously angled planes that it is composed of. This is the trickest form of collision detection, and it is also the most accurate.
To go beyond the description above would require pages of information and diagrams to illustrate the idea, algorithms and formulas involved…the good news is there are such descriptions around on the net.
Hmm, so if you’re going to calculate all the normals of the polygons in relation to each other, it would make the most sense to use triangular primitives in your model on the basis that a normal can be calculated using only 2 vectors, which is also true of a triangle? Interesting…