Hi people,
I’m about to properly start work on my first game, but before I do I’m just posting this demo showcasing a few things. The main thing being 3D sphere to triangle collision detection. Also some basic dynamic lighting and fast culling.
Regarding culling, this pseudo game level has 54,000 polygons, which represents a fairly large level in DS or N64 level polycounts. Because it’s broken up into 75 pieces and only a small amount of polygons are visible at any one time, it runs at 60fps with ease, as models that are completely offscreen are quickly discarded from the transformation/render engine.
Also regarding collison detection, the per poly collisions also use my broadphase uniform grid, so the amounts of polygons needing to be checked are narrowed down to an average of about 60 per frame, with the majority of those being quickly discarded anyway, due to them being too far away or backfacing.
The actual sphere to triangle collision routine is more complex than you imagine though. A simple raycast to the polygon is not enough, you need to first find the intersection point, and if that intersection is seen to be NOT in the current triangle, that doesn’t mean there is definitely no collision.
Why? Because the radius of your object could be touching one of the vertices or edges of the triangle, even if the ray doesn’t intersect the actual face of the triangle. You can probably visualise this, imagine a sphere approaching one triangle from every angle.
And the process for checking collisions with the 3 edges and 3 vertices not only brings the collisions checks per triangle to 7 instead of just 1 ray cast, but the edge/vertex check are more complex than the raycast, and slower.
So once you’ve found your colliding polygon, you can just adjust the velocity and the function right?
No, this is the bit that’ll surprise most people. You have to carry on iterating through the polygons in case you collide with multiple polygon simultaneouslly (which you are, a lot of the time). Not only that, but even after you’ve finished iterating over all the polygons in the current node, you have to do it AGAIN, using the new velocity that exists as a result of the first collision.
So you have to actually run the routine up to 5 times per object per frame, to properly implement “sliding” physics.
As you can imagine, getting the routine to run fast isn’t easy.
I have got mine running very fast as you’ll see, and for those of you that are interested, if you maybe want to develop a 3D engine yourself (especially when Flash gets GPU support), the best references are this paper by Kapser Fauerby - http://www.peroxide.dk/papers/collision/collision.pdf and Ericson’s book “Real Time Collision Detection” which Freshmaker recommended to me, thanks Fresh 
I think these are the best, most concise references out there. Part of the trick to getting 3D collision detection running fast is a FAST arse broadphase, that narrows the possible collisions down with minimal overhead, and the other part is simplifying the actual collision routine as much as possible.
Anyway, here’s the demo. Not only does it run at 60fps, but making sure you have nothing else running in the browser, you should check the CPU usage.
By default you control a Dreamcast in 3D person, using the WASD keys or the arrow keys.
Press Spacebar to shoot weapons, press 1 to swap the Dreamcast with a pixel art style Dreamcast, and press 2 to change to FPS style controls, where WASD is move/strafe, and the mouse rotates/looks. While in FPS mode, you can press V to enable vertical look.
http://rumblesushi.com/dreamcast.html
Cheers,
RumbleSushi
