Fast 3D sphere to triangle collision demo

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

very nice.

It would be great to choose what geometry is added for collision detection here during your broad phase. Most of the collision in that level could be achieved with simple top down 2d collision. Leaving only the triangle slopes for processing. Then again, if your broad phase is very efficient it might be better to let it determine collisions automatically to avoid processing two types of collision systems.

The point here is making it scalable :)

again, very nice.

Cheers mr malee, but to be honest that would be significantly less efficient and kind of messy, having two collision routines.

I've worked on getting this running insanely fast, if you have nothing else running, check the CPU usage. It uses about 9 to 12% of my CPU, and the collision detection counts for about 1%, the rest of it is transformation/rendering.

Also in this particular example, when colliding with the floors/walls, you're generally colliding with an average of 2 polygons at a time, with the majority of the polygons per node being quickly culled, due to being backfacing, or having too large a facing value etc. So only a handful are processed, and generally only a couple of them are actually colliding.

Even if the broadphase determined which polys could use a 2D algorithm, the speed saving would be non existant, even with a fair few objects running on the system. With a 2D algorithm, you'd still have to sort surfaces, you'd still have to check edges, and you'd still have to process the velocity in the same way, and restart the process with your new displacement etc.

You'd only notice a slight difference in speed if around 2000+ polygons were processed, which of course is unrealistic, because in the average low poly level, there is only around 20/30 polygons per node, with most of those being quickly culled anyway.

And of course it would introduce an overhead in processing a large level, having to determine which parts of the geometry could be processed in 2D. Which although in this demo is a decent amount, in the average 3D level (racing game, outdoor shooter, platform game etc) it's only going to be a very small percentage compared to angled surfaces.

So although I'm generally all for optimising everything, I think this particular example would actually be less efficient.

I agree...now just pop everything into a nice octree and collide check against the tris in the vicinity of your dreamcast (nice choice of hero btw lol) :D

Hey RipX, as I said in the opening post, I'm using a uniform grid as a broadphase, which narrows the amount of polys to check down to a very low amount, but with much less overhead than an octree ;)

Hey Rumble...

Must have missed that... this seems like a different and interesting approach for a flash engine to adopt, I see most of the flash engines adhering to perhaps a scenegraph approach coupled with a bsp, kd-tree and/or an octree. I see that you're using a physics approach... I guess the uniform grid would force a game tailored to this engine in many senses and I get the impression that for this reason this would be a good engine for a limited selection of games. Good luck though, looking forward to seeing your game :D

RipX

Funnily enough it's actually not an interesting or new approach in regards to 3D game development, a lot of commercial 3D games apparently do use a uniform grid as a broadphase. It's fast and efficient, if it's implemented well.

For Flash engines especially, with super low polycounts, I think BSP trees/octrees etc are a bit OTT. Especially with a decent amount of moving objects, BSP is really, really slow, plus you have a lot of extra polygons from the cuts you make on the splitting planes etc.

They are good for narrowing down collisions, and great as a means of depth sorting and determining visibility, but their bottleneck is moving objects.

Overall a uniform grid is much faster as a collision broadphase, even if it is a bit quicky and dirty in comparison.

By the way, surely you didn't think I was looping through all 54,000 polys in the level? If I was checking all of them for collision, it would run ridiculously slow, probably 15fps tops ;)

Also the uniform grid has absolutely no influence on level design. It's not like things have to be constructed in modular fashion, or aligned to the grid etc, it's nothing like that.

I just specify a node size and do grid.collectPolygons() and it runs through every polygon in the level, and if it's flagged for per poly collision detection, it gets added to whatever node(s) it resides in. It doesn't matter how the level is constructed, the polys just get added to whatever nodes they occupy, and then in game, the moving object just loops through the polys of whatever node(s) it's currently in, and there you go, that's your broadphase ;)

My first game is a racing game by the way.

Absolutly didn't say it was a new 3D concept, I said it was a new angle on flash 3D engines!

Agree with you about moving objects since the tree needs to reinsert data that has moved but how does you're engine avoid the same thing? Isn't this like an octree where you've simply assigned the size of the uniform cube area? Although....I can see that the collisions are somewhat inverse compared to usual applications. So each face is pushed to a kind of collision tree (if flagged for collisions)... Is this the key point to the implementation? ( please humour my ignorance )

I assume your talking about angled modular algorythms such as those used heavily with ray tracing, again, I'm not sure how you're implementing this if things aren't uniform but I agree this is faster but a general ray-bound intersection algorythm isn't that much slower tbh albeit slightly more complex to implement. ( again, this is a point based on something I'm not understanding fully (Can I do that? lol.. probably not), not a critisism ).

No I didn't think you were looping 54,000 polys per frame... you're better than that!! I've seen earlier example of what you've been doing for a while ;D

This one I now understand, I had assumed you were building your level in blocks, but now I see you are just dividing it uniformally. :)

Good luck with the racing game... However... How many things will we be racing against since you point this out as a major motivation for your engine... I hope there's loads of stuff going on... it'll be cool, can't wait :D

Keep going man, I'm really interested in your engine and good luck with it!!!

RipX

Yep, you got it, I'm just dividing any geometry into a uniform grid. And it's dividing in a conceptual sense, there's no splitting of geometry etc, there's just a reference stored of each poly that intersects a grid node in the node at hand.

Oh by the way it's funny you should say that, because ironically my racing game is actually going to be a touge style game, one on one racing around Japanese mountain tracks etc, so actually only 2 cars :D

That's just a style choice as I love touge/drift racing, and I really like Initial D etc too.

However I guarantee the tracks are going to be big with a fair amount going on, as much as is possible with the small poly budget per frame.

Came back to dust off my account, and first thing I see is a nice, rumblesushi 3d demo!

Awesome stuff with the engine, really! I was amazed seeing it run at a smooth 60 fps, no hesitations, no hiccups. Think of the stuff you could do at 30 fps!

About the uniform broadphase, does that mean you sometimes of one polygon belong to several nodes at once? I'm doing something similar for a 2d project I'm working on, and it would be good to know of any optimizations!

Good good stuff! When's the engine gonna be available to us? :P

P.