• Advertisement

Archived

This topic is now archived and is closed to further replies.

Collision Detection for a Newbie

This topic is 5932 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

This probably isn''t the best place to post this but here goes. I was just getting into doing Open GL, and over time I learned how to do a number of things in Open GL. Lately, I decided to try and make a simple game with it. Shortly into the process, I remembered a very important problem with 3D development. I needed a method for collision detection! I have been searching high and low for a method that would actually help me, but everything was the same. They all talked about using bounding boxes and such, but they left out one VERY important thing. What about the environment? You can''t place a bounding box around a large complex landscape without lots of problems! The only solution I can think of is to make the maps broken down into thousands of pieces and place bounding boxes around them, but that would HURT the speed alot. So here''s my question, how do you do collision detection with landscapes!?!?!?!

Share this post


Link to post
Share on other sites
Advertisement
If by ''landscapes'' you mean ''terrain''...

That should be easy. Since terrains are heightmapped, you can just look up the terrain height at the XZ position you are testing (test all corners of the bounding boxes) to see if they are (or will be) below the terrain height. That should be your collision test. If you plan to bounce or slide your objects on the terrain, use the vertex normal (easy) or calculate a specific normal for your bounce vector.

As for non-heightmapped environments, games commonly use inverse bounding boxes, i.e. the collision test checks if objects will leave the box (space) they''re in.

Share this post


Link to post
Share on other sites

From what I understand, the secret of collision detection is working out which objects to test against other objects

Your code needs some way of working out which surfaces will potentially collide, so that you can avoid the exponential blowout you will get by testing everything against everything else.

A common method to do this is to use some sort of spatial partitioning alorithm to divide your scene into manageable regions, where each region will contain a sub set of the total surfaces in the scene. You can then work out which region to test against, and only test the relevant surfaces.

(the simplest way of doing this is to divide your scene into a grid, and test against squares on the grid. This isfine for height maps but doesn''t work well for 3D scenes).

One of of doing this is to use a hierarchical tree structure to store your scene. For instance, an octree works by splitting the scene at the x/y/z axis into 8 equal boxes. Each of these boxes is in turn split into 8 boxes, which are in turn split etc etc until the nodes of the tree are small enough to contain only a few surfaces.

You allocate your surfaces to the smallest node of the octree that they wil fit into. When collision testing you can then traverse the octree from the root to find the node that contains the surface you want to test against. Once you have found this node, you can work your way back up the octree testing as you go. You can stop testing when you reach some handy limit (like 2 time the size of the node your surface fits into).

The octree is reasonable efficient as you can cull large regions of your scene with a single test.

Hope this helps!

Keef









Share this post


Link to post
Share on other sites
THANK YOU! To start off with, I was intending on making the maps in Milkshape, but I guess that I could just make features like rocks and trees in Milkshape and use a heightmap for the map. Thanks, I owe you guys.

Share this post


Link to post
Share on other sites
I tell you, I am full of problems.

Can anyone point me towards a hieghtmapping tutorial that uses grayscale bitmaps? The NeHe tutorial uses .Raw files. What in the name of George Washington is a .raw file!? I can''t make no sense out of it, and no programs I know of can read or write them! So, can ya guys help me one more time?

Share this post


Link to post
Share on other sites
I tell you, I am full of problems.

Can anyone point me towards a hieghtmapping tutorial that uses grayscale bitmaps? The NeHe tutorial uses .Raw files. What in the name of George Washington is a .raw file!? I can''t make no sense out of it, and no programs I know of can read or write them! So, can ya guys help me one more time?

Share this post


Link to post
Share on other sites
A raw file is just a raw dump of binary data. In the case of images, it is just the pixel data dumped directly to a file. There is no header information or anything, so you will need to know the size dimensions and colour depth before opening it.

Share this post


Link to post
Share on other sites
I''ve managed to make a heightmap engine myself. I also used raw file. I''ve wrote my own program BMP2RAW which used blue value of bmp (0..256) for height and red (0..256) for texture. Easy. My raw was like this. long xsize, long ysize, char[xsize*ysize] blue heights, char[xsize*ysize] red textures. Very simple. I would send you the source but a week ago on a sunday morning computer wouldn''t wake up. Then I found out all the partitions were gone. AAAAAAAAAAAAAAAAAAARRRRRRRRRRRRRGGGGGGGHHHHHHHHHHHH!!!!!!!!!!!!!
Now I''m writing a full game instead of just the graphics engine and I''m tellin'' ya there''s a lot to do. And I won''t tell you what is my game about ''cos you''ll steal my idea.
Right now I''m strugling to make terrain normals to work.

Share this post


Link to post
Share on other sites

  • Advertisement