Fast 3D sphere to triangle collision demo

[rumblesushi]

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

[creatify]

Bad A$S, nice work!

[ayumilove]

uhh cool game?
I don't really like rts games :hitman2:

[lordofduct]

we may not get along to often rumble

but ode to the Dreamcast... total win in my book!

[rumblesushi]

Cheers guys.

LOD, yep I'm a huge Dreamcast fan, probably my favourite all time system. Shenmue 1 and 2, Sonic Adventure 1 and 2, VF3, Daytona, VOOT, etc etc, man, what a system.

And even though this is just a tech demo, why not give it some love and include a Dreamcast ;)

Incidentally I forgot to mention about the weapons, they run on a more simple collision system. They run on the same broadphase, but they just use a simple raycast, if the ray (which is of course the current displacement) hits any triangle, then wham, you can break the loop, calculate the bounce, and that's it for the current frame. So they are not represented as a sphere, just a point/ray, so you don't need to do the more complex checks with the verts/edges etc, and the re-iteration that you need to do with sliding physics.

[Gathan]

That demo gives me help that a 3d on par with N64 might be possible with flash in the near future.
Though making the large outdoor levels found in games like Mario64 are just out of reach without gpu support.
The only reason that performances as well as it does is because of the confined spaces and the small viewing areas.
So sad though, us making a big deal about being able to make a n64 game in flash when such things have been easily done in other languages for a long time.
It's almost like flash is our slow little child that we all refuse to give up on haha.
Impressive none the less making good use of what limited resources flash has.

[rumblesushi]

That demo gives me help that a 3d on par with N64 might be possible with flash in the near future.
Though making the large outdoor levels found in games like Mario64 are just out of reach without gpu support.
The only reason that performances as well as it does is because of the confined spaces and the small viewing areas.
So sad though, us making a big deal about being able to make a n64 game in flash when such things have been easily done in other languages for a long time.
It's almost like flash is our slow little child that we all refuse to give up on haha.
Impressive none the less making good use of what limited resources flash has.

Actually you're wrong there. My engine is almost exactly on par with an N64/DS. It can do 2000 polygons at 60fps, in an in game scenario.

Mario64 has around 3000 per frame at 30fps, and Starfox64 for example only has around 1000 polygons per frame (I'm not sure of the framerate, seems higher than 30 but lower than 60).

My engine can render 3000 polys per frame at around 40fps on a Core 2 Duo, so a game just like Mario64 is feasible 100%. The disadvantages are that it's without bilinear filtering/anti aliasing, but the advantage is that there's more RAM available than an N64, so higher res textures.

[TheCanadian]

Cool stuff but you're not supposed to post the same topic in multiple forums.

modEdit: True. Threads merged.

[rumblesushi]

I know. I posted it in the games forum first, then thought actually this place is empty, so posted it here.

[rumblesushi]

Actually, could one of the mods do me a favour and move this to the games forum? This forum is so busy it'll quickly get pushed to page 2, but for those that don't check the forums frequently, they'll have a chance to see it in the games forum.

Cheers.

Thanks to whoever moved it ;)

[Gathan]

Actually you're wrong there. My engine is almost exactly on par with an N64/DS. It can do 2000 polygons at 60fps, in an in game scenario.

Mario64 has around 3000 per frame at 30fps, and Starfox64 for example only has around 1000 polygons per frame (I'm not sure of the framerate, seems higher than 30 but lower than 60).

My engine can render 3000 polys per frame at around 40fps on a Core 2 Duo, so a game just like Mario64 is feasible 100%. The disadvantages are that it's without bilinear filtering/anti aliasing, but the advantage is that there's more RAM available than an N64, so higher res textures.
I suppose your right about mario, but what about starfox, that type of game has alot more action going on the screen at once.
Even if you can render the basic environment and all with a couple thousand polygons at 30-60 fps, what happens once you get explosions, particles flying around, lets not forget about the solar level either with its dynamically changing environment, thats alot more processing intensive then a few thousand polygons that only really move when the player does.
But don't mind me I just remain cautiously pessimistic about the whole thing really, probably from too many high promises made by "adobe" caugh and much under delivering.

[rumblesushi]

It's interesting you should say that, your point about it being all well and good rendering a static environment but what about moving objects/weapons etc.

Well I take it you haven't seen all my other demos?

I've put a LOT of effort into getting moving objects running as fast as possible, and very fast culling too, which allows big worlds with minimal added overhead, as long as it's split up into multple objects, and the rendered poly count is kept low.

By the way, there's no doubt that Mario64 is a more demanding game than StarFox 64. StarFox 64 might have a few more moving objects, but the amount of rendered polys per frame is lower than Mario 64, like half as much, the figures I gave are total rendered count, so that includes any weapons, enemies etc. As you know, the worlds in Mario 64 are big and open, whereas StarFox being on rails, you only see a fairly confined space at any one time.

Anyway, have a look at this for sheer object count and object collisions. Every object can collide with every other object, which in brute force terms would be half a million collision checks with 1000 ships.

Press S to spawn a ship, press spacebar to zoom out, and press R to change the rendering mode to pure wireframe - http://rumblesushi.com/grid.html

Here's an example of a simple, game esque outdoor environment, with a controllable car. Use the WASD keys or arrow keys to control the car - http://rumblesushi.com/beach.html

Cheers,
RumbleSushi

[offsitenoc]

Good stuff here found thanks for share

[hasanvertex]

really nice game.