Sign in to follow this  

Collision checking with basic shapes vs. vertex checking

This topic is 3862 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm a hobbyist programmer who is trying to make a decent 3D game engine. For collision testing, I'm planning to make every object's collision hull be a combination of one or more basic shapes (rectangular prism w/ vertical walls, ramp, vertical cylinder, cone, sphere, etc.). I figure that if the shapes can be expressed mathematically then collision testing will be faster and easier than testing for face-to-face intersections. Because that system wouldn't work for terrain, I was going to use a heightmap for terrain. Has anybody tried this before? Would it work well? Would it be possible to create good maps just with that collection of basic shapes?

Share this post


Link to post
Share on other sites
When you draw a heightmap, chances are you've already calculated the normals for each face. Collisions between a bounding sphere and a plane is very easy. To see if you've got a collision, take the distance between the center of your sphere and the plane. If it is greater than the sphere's radius, there is no collision. Otherwise you have a collision. The distance from a plane with unit normal n (where n is the vector [normalx,normaly,normalz]) with a distance d from the origin to an arbitrary point p (where p is the vector [x,y,z]) is (n dot p) + d.

Share this post


Link to post
Share on other sites
Quote:
Original post by CrimsonSun
When you draw a heightmap, chances are you've already calculated the normals for each face. Collisions between a bounding sphere and a plane is very easy. To see if you've got a collision, take the distance between the center of your sphere and the plane. If it is greater than the sphere's radius, there is no collision. Otherwise you have a collision. The distance from a plane with unit normal n (where n is the vector [normalx,normaly,normalz]) with a distance d from the origin to an arbitrary point p (where p is the vector [x,y,z]) is (n dot p) + d.


Thanks, that'll help for collisions with the heightmap.

But that wasn't my question.

I'm more interested in the pros and cons of using basic shapes only. I'm trying to cut processor costs by not using vertex checking at all. Is that a good idea? Can I still make good levels with only simple shapes and a heightmap, or do I need a full-blown vertex model for the level to look good?

Share this post


Link to post
Share on other sites
Colliding with simplified geometry is a common trick. Whether that simplified geometry is 3D primitives or just low-poly depends on what you're planning on using it for. One big advantage of face hit testing against a low poly model is that skeletal animation just works. If you need to collide with skinned models like that, the extra hassle of rigging the cylinders along with the rest of the model may be more trouble than it's worth. On the other hand, 3D primitives really works better than faces, though, at physics; it's very difficult to keep face-based collision geometry from getting stuck in walls unless you decompose it into convex subobjects, and at that point you might as well just be using primitives.

Share this post


Link to post
Share on other sites
Quote:
Original post by BlazingClaymore
Well most people have fast processors and crapy graphics cards so I really don't thank you should worry so much about that. just go with meshes it will be better in the end. k.


Actually I think the other posts were more helpful - mesh collision nearlly always has problems with getting caught on things in a lot of situations, especially in the free 3D engines you will be using as a hobbyist.

Also, in my experience, the free 3D engines don't run as fast, so the game bogs down much sooner than a commercial game does - so optimisation is every bit as important for the hobbist even though his/her game will not match the complexity of a commercial game.

Share this post


Link to post
Share on other sites
Quote:
Original post by Domarius
especially in the free 3D engines you will be using as a hobbyist.


Actually I'm trying to write my own. (Which is probably dumb of me.)

Thanks for the replies. I'll go with the simplified shapes.

Share this post


Link to post
Share on other sites
Most collision detection systems use a kind of hierarchy approach. The principle is that you want to rule out as many potential colliders as quickly as possible with quick tests (e.g. bounding sphere) so that you put fewer objects through the more expensive tests later on (e.g. per-poly).

So, the best kind of structure to use really depends on the nature of your dataset. If you're doing a space sim which has objects spread out over a large distance, then an AABB tree of all objects in the game world + per-poly test would probably be sufficient (possibly with a second AABB tree for each really large ship). If you're doing a game which has lots of objects packed into a small space, then you may want to perform oriented-bounding-box tests and just skip the per-poly level. There is no one best configuration for all games.

There are only three primitives I'd really bother implementing if I were you:
* Boxes
* Cylinders
* Capsules

All three kinds should be completely freely orientable, though I'd special-case boxes for when they're axis-aligned; you could also special-case spheres (zero-length capsules).

I'd support per-polygon tests as well, though.

Share this post


Link to post
Share on other sites
Quote:
Original post by superpig
There are only three primitives I'd really bother implementing if I were you:
* Boxes
* Cylinders
* Capsules

All three kinds should be completely freely orientable, though I'd special-case boxes for when they're axis-aligned; you could also special-case spheres (zero-length capsules).

I'd support per-polygon tests as well, though.


This is an RPG, so it'll have a lot of objects close together.

Good idea - I should shorten my object list. And I hardly even thougth of special casing. But I'm inclined not to make things completely freely orientable. Vertical and horizontal should be enough. Why is free orientation useful?

What are capsules useful for?

Share this post


Link to post
Share on other sites
(Best of my knowledge - superpig will know more)

Capsules are useful for humanoids because the rounded tops and bottoms let them slide over little ledges instead of getting stuck on them.

If you don't know why free orientation is useful then you shouldn't bother with it for your game :) Based on what you described, it won't be useful for your game. You probably know that axis aligned checks are much faster.

Share this post


Link to post
Share on other sites
Quote:
Original post by Domarius
Capsules are useful for humanoids because the rounded tops and bottoms let them slide over little ledges instead of getting stuck on them.

True. I was considering ellipses for that, but capsules will work better.
Quote:

If you don't know why free orientation is useful then you shouldn't bother with it for your game :)

Yep.

Thanks!

Share this post


Link to post
Share on other sites
Sorry, I thought you were just trying to write an engine - hadn't realised you were actually building a game. In that case it should definitely be guided by your requirements. I was basing my suggestions on a more general-purpose engine, which would definitely need freely orientable collision meshes.

Are you sure you really need all this, though? You could implement per-poly collision detection now, and then use this stuff later to optimize it once you're sure that it's necessary. (That's all that this stuff is, after all - an optimization technique).

Share this post


Link to post
Share on other sites
Quote:
Original post by superpig
Sorry, I thought you were just trying to write an engine - hadn't realised you were actually building a game. In that case it should definitely be guided by your requirements. I was basing my suggestions on a more general-purpose engine, which would definitely need freely orientable collision meshes.

Are you sure you really need all this, though? You could implement per-poly collision detection now, and then use this stuff later to optimize it once you're sure that it's necessary. (That's all that this stuff is, after all - an optimization technique).


Specialized engine or general game, big difference.

I think it would be a lot easier to write basic shape collision code than it would be to write per-poly collision code. Especially if I want to test for more than just intersection, such as bouncing or sliding. Am I wrong?

Share this post


Link to post
Share on other sites
Quote:
Original post by timmaxw
Specialized engine or general game, big difference.
All you said in your original post was "decent 3D game engine," so I assumed non-specialized engine.

Quote:
I think it would be a lot easier to write basic shape collision code than it would be to write per-poly collision code. Especially if I want to test for more than just intersection, such as bouncing or sliding. Am I wrong?
It's probably easier to write bounding-sphere intersection tests than poly-poly intersection tests, sure. But if you wanted the easy option you wouldn't be writing your own engine :P

Something else to consider is the asset pipeline. If you write per-poly support, then you can just throw your models into the collision detection system immediately. If you only support mathematical primitives, then you'll have to provide a toolchain for setting up those primitives before you'll be able to get the models into the game.

Share this post


Link to post
Share on other sites

This topic is 3862 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this