I'm stuck on getting 3D collision working for my GTA type game. I've read every tutorial on collision I could find but I still don't get it. I have two .X file meshes which are loaded. One a car, one a city with building etc. I need to detect when my car hits a building and stop it. Most of the tutorials I've read deal with quake style games. Any help would be very helpful as I've spend one week reading and I understand the basics of vectors and planes.

thanks

P.S. I'm using DirectX8 and Visual C++ 6.

do a search for "colldet" on the web .
Colldet is a library for collision detection . Might help , u can use in comercial products even , but i think no source code available .
I guess the easiest way to test for collision is to put your object in circles(spheres) and if the circles are tangent or intersected , well u have collision .

Your question anyway is to vague

how would I go about doing that? Can you give me some code or a starting point?

how would I go about doing that? Can you give me some code or a starting point?

I read another tutorial on collision and I got an idea from it. Tell me if this will work. My car is a mesh, so I will loop though each vector(vertex) of the car and input into my collision detection function added with another vector showing where the car will move. The function will then loop though each triangle in my city mesh and find its plane then work out if the which side of the triangle plane the car vertex will be if is moved. If the loop ends without collison being TRUE then the car is moved, else the car remains where it is. Here's some pesudo code-

D3DXVECTOR3 pos;
D3DXVECTOR3 movepos;
for(i=0;i<dwNumVerticesCar) {
pos=carVerice[i]+movepos;
collision(pos);
}
if (collision!=TRUE) {
x=movepos.x;
y=movepos.y;
z=movepost.z;
}

VOID collision(D3DXVECTOR3 &pos) {
for (each triangle of city mesh) {
findPlane();
checkWhichSideOfPlanePosIsOn();
if (collision) {
collision = TRUE;
}
}
}


Is there any problems with my idea. If not can someone expand my code more, like show how me code for finding the plane, etc.

Any help will be helpful.

Sory for my bad english ! If someone could corect this , please do it!

Collision detections algorithms are implemented through intersections results between two or more primitives ( the primitives are basic 3D objects : cube , sphere , pyramids ...) or the triangles from the scene and the primitives .

The intersection calculations for primitives are used to get the collision between the objects in the scene (excluding the walls - for a 3dShooter game) .

Objects are situated inside an aproximation primitive (circle ,sphere , rectangle , box) ,because these primitives aproximates the shape of the object .

Those aproximation primitives can be :

- spheres
- AABB(Axis Aligned Bounding Box) . The object is situated inside a box whose faces are paralels with coordinating axis .
- OBB(Oriented Bounding Box) . The object is situated in the smallest box that can be created. It aproximated the object volume at best .

I'll explain the spheres aproches :

Let it be 2 objects . Put these objects in 2 speheres( or circles) .
These Spheres are : S1(center1,radius1) & S2(center2,radius2)
distance = the distance from center1 to center2
if distance is less than radius1+radius2 well u MIGHT have a collision . :) . I repeat U MIGHT have a collision .

if (distance< radius1+radius2) ColisionCouldBePossible();
else ColisionIsNotPossible;

Examples :

  (example1)

     ---------------
    /               \
   /                 \ 
  /                   \
 /                     \ 
|       ********        |
|      * any    *       |  
|      *        *       |
|      * object *       | 
 \      ********       / 
  \                   /  
   \                 /
    \               /
     ---------------   
                                 Collison is not possible
     ---------------
    /               \
   /                 \ 
  /                   \
 /                     \ 
|         -----         |
|       /      \        |  
|     --  a car ---     |
|    |             |    |
 \   ---O--------O--   / 
  \                   /  
   \                 /
    \               /
     ---------------   


  (example2)

     ---------------
    /               \
   /                 \ 
  /                   \
 /                     \ 
|       ********        |
|      * any    *       |  
|      *        *       |
|      * object *       | 
 \      ********       / 
  \  ---------------  /  
   \/               \/
   /\               /\               Colission is still not                                     
  /  ---------------  \                possible
 /                     \       The spheres are intersecting but
|         -----         |       the objects don't
|       /      \        |  
|     --  a car ---     |
|    |             |    |
 \   ---O--------O--   / 
  \                   /  
   \                 /
    \               /
     ---------------   

Now let's take another example , let's say in a 3d Shooter we have to test if a rocket will hit a character(human) , and where . So we put our rocket in a sphere and the human in another one . If the spheres are intersecting we might have a collision , so we test further .
Now we pot the upper part of the human body in a sphere , and the lower part in another one , and test again for a intersection . Let's say the rocket sphere intersect the sphere of the upper part of the body .
No we put the head in a sphere , the chest in a sphere , the shoulders in another 2 spheres , the uper parts of the arms in another 2 spheres and so go on ... we test for intersection again . :)

The fixed parts of the scene (walls , stairs , floor ,etc ) can not be aproximated with primitives . For collision detection u have 3 choiches .
U have to test for intersection between the primitive of the object and :
1) the scene's triangles (this is what are u doing in your example i guess) . This test might be a problem if the scene has many triangles and the quality collision it's not so good .
2)the scene's polygons . U must put the triangles toghether , when u design the level of the game, in convex polygons .The test will be through the primitive and a reduced set of convex polygons .
3)planes wich aproximates geometry . U have to cut the level in collision planes , which aproximate the level geometry . The test are between the primitive and the planes which are closer . This method does not dependend on the numbers of triangles involved in the scene . It's widely used in engines BSP tree based .

Huh ! That's all for now . If u think it's not enough or u don't understand i think i can give u a more detailed explanation (with pictures . I think i can make a web page )

That's all and good luck !

P.S. AABB and OBB cases are somewhat similar with the sphere test but they can provide a better aproximation , and also they might be slow in comparation with the sphere tests .

Sorry, I still don't get it.

What exactly u don't understand ? What part of the collision u don't understand ? Try to be more explicit so i can help u more .



P.S. Do u have some math knowledge ?

:
: Sorry, I still don't get it.
:

Collision detection & what results from the collision can get very tricky. You must try and understand the basics 1st, then work onwards. I can see from your prevoius posts you have the city mesh and the car model already, and so you are very eager to slot this next 'collision bit' in. Unfortunately I think this could hinder you in some way as they are complicated meshes and are not ideal to learn the basics of collision detection. Make yourself a small testbed, and use simple shapes, like cubes. These will be faster to load and easier to debug. write routines to create collision boxes ( or spheres ) around these simple shapes and also to draw the collision are, so you can see if they move with the object and rotate with them. Then, once you have mastered spherical collision, move onto more complicated methods. I think this is what aris is trying to explain.

To help you with spherical collision, you need to know about how to create a vector from one object to another, and how to measure the length of the vector. If the length of the vector is less than the radius of the collision sphere, the objects are touching. Write yourself some nice c++ vector classes to do these individual steps. They will make your life easier in the long run.

Do you know any basic vector maths ?

That's very interesting. Can you e-mail me some URL's where I can find something more about collision detection?
I'd apreciate that 'cause I have to do a collision detection, too but I didn't find any good tutorial.

Thanx in advance.

my e-mail: spooky@centrum.sk

Could you put a car in to s square box?


: Sory for my bad english ! If someone could corect this , please do it!
:
: Collision detections algorithms are implemented through intersections results between two or more primitives ( the primitives are basic 3D objects : cube , sphere , pyramids ...) or the triangles from the scene and the primitives .
:
: The intersection calculations for primitives are used to get the collision between the objects in the scene (excluding the walls - for a 3dShooter game) .
:
: Objects are situated inside an aproximation primitive (circle ,sphere , rectangle , box) ,because these primitives aproximates the shape of the object .
:
: Those aproximation primitives can be :
:
: - spheres
: - AABB(Axis Aligned Bounding Box) . The object is situated inside a box whose faces are paralels with coordinating axis .
: - OBB(Oriented Bounding Box) . The object is situated in the smallest box that can be created. It aproximated the object volume at best .
:
: I'll explain the spheres aproches :
:
: Let it be 2 objects . Put these objects in 2 speheres( or circles) .
: These Spheres are : S1(center1,radius1) & S2(center2,radius2)
: distance = the distance from center1 to center2
: if distance is less than radius1+radius2 well u MIGHT have a collision . :) . I repeat U MIGHT have a collision .
:

: if (distance< radius1+radius2) ColisionCouldBePossible();
: else ColisionIsNotPossible;
: 
: Examples :
: 
:   (example1)
: 
:      ---------------
:     /               \
:    /                 \ 
:   /                   \
:  /                     \ 
: |       ********        |
: |      * any    *       |  
: |      *        *       |
: |      * object *       | 
:  \      ********       / 
:   \                   /  
:    \                 /
:     \               /
:      ---------------   
:                                  Collison is not possible
:      ---------------
:     /               \
:    /                 \ 
:   /                   \
:  /                     \ 
: |         -----         |
: |       /      \        |  
: |     --  a car ---     |
: |    |             |    |
:  \   ---O--------O--   / 
:   \                   /  
:    \                 /
:     \               /
:      ---------------   
: 
: 
:   (example2)
: 
:      ---------------
:     /               \
:    /                 \ 
:   /                   \
:  /                     \ 
: |       ********        |
: |      * any    *       |  
: |      *        *       |
: |      * object *       | 
:  \      ********       / 
:   \  ---------------  /  
:    \/               \/
:    /\               /\               Colission is still not                                     
:   /  ---------------  \                possible
:  /                     \       The spheres are intersecting but
: |         -----         |       the objects don't
: |       /      \        |  
: |     --  a car ---     |
: |    |             |    |
:  \   ---O--------O--   / 
:   \                   /  
:    \                 /
:     \               /
:      ---------------   
: 

:
: Now let's take another example , let's say in a 3d Shooter we have to test if a rocket will hit a character(human) , and where . So we put our rocket in a sphere and the human in another one . If the spheres are intersecting we might have a collision , so we test further .
: Now we pot the upper part of the human body in a sphere , and the lower part in another one , and test again for a intersection . Let's say the rocket sphere intersect the sphere of the upper part of the body .
: No we put the head in a sphere , the chest in a sphere , the shoulders in another 2 spheres , the uper parts of the arms in another 2 spheres and so go on ... we test for intersection again . :)
:
: The fixed parts of the scene (walls , stairs , floor ,etc ) can not be aproximated with primitives . For collision detection u have 3 choiches .
: U have to test for intersection between the primitive of the object and :
: 1) the scene's triangles (this is what are u doing in your example i guess) . This test might be a problem if the scene has many triangles and the quality collision it's not so good .
: 2)the scene's polygons . U must put the triangles toghether , when u design the level of the game, in convex polygons .The test will be through the primitive and a reduced set of convex polygons .
: 3)planes wich aproximates geometry . U have to cut the level in collision planes , which aproximate the level geometry . The test are between the primitive and the planes which are closer . This method does not dependend on the numbers of triangles involved in the scene . It's widely used in engines BSP tree based .
:
: Huh ! That's all for now . If u think it's not enough or u don't understand i think i can give u a more detailed explanation (with pictures . I think i can make a web page )
:
: That's all and good luck !
:
: P.S. AABB and OBB cases are somewhat similar with the sphere test but they can provide a better aproximation , and also they might be slow in comparation with the sphere tests .
: