Jump to content
  • Advertisement
Sign in to follow this  
timmaxw

Collision checking with basic shapes vs. vertex checking

This topic is 4079 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
Advertisement
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
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.

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!