# what form of geometry do i need for collision detection in 3d?

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

## Recommended Posts

hi. im doing a crowd simylation program in a 3d envrionment. i want to keep it fairly simple, as im not the best at maths. but i will need to study some form of geometry to allow the "charachters" in my simulation to know how far they are from other characthers and also to know when they bump into eachother. what do i need to study to teach me this, and if possible could you recommend some books/sites that keep things simple for me as , like i said, im not the best maths head. im using directX 9 and c# for my project. thanks

##### Share on other sites
spheres and/or ovals are your friend.

plain spheres might not be the most accurate, but theyre simple to work with, fast, need i say more?

##### Share on other sites
you need to know sphere to sphere collision and calculating angles

##### Share on other sites
Ovals are used more common on "characters" than spheres, because human body is more similar to ovals.

I would suggest u read this book: Frank D. Luna's 'Introduction TO 3D GAME Programming with DIRECTX9.0', which is written for beginners. So it's very easy to read. A small section of this book(section 11.3, "Bounding Volumes") illustrates some very basic concepts & practice about collision detection, i guess u may like it;)

##### Share on other sites
ellipsoidal shapes are more difficult to collide with each other. Spheres are simpler. They should give a good enough approximation for a crowd simulation, and it's dead simple to test.

simplest is the radius check on two spheres. distance betwen characters less than the sum of the radii, collison, then push characters away. No need for more complication, since characters move slowly.

A compromise would be to use a cylinder. (do a circle test in the (x, z) plane, and a height test in the Y plane), although for a crowd simulator, you could consider the world as strictly 2D.

http://www.gamedev.net/reference/articles/article1234.asp
http://www.red3d.com/cwr/steer/

##### Share on other sites
You need to know how to do sphere-sphere collision. Once you know how to do it, you'll need to add just a few line of code to do ellipse-ellipse collision (assuming the ellipses cannot rotate, and their axis are along the X,Y and Z axis).

If you world can be assimilated as being 2D (ie the map of your world can be represented in 2D), then all you need is circle-circle collision, which is very simple once you have a vector2D class.

##### Share on other sites
You need to know how to do sphere-sphere collision. Once you know how to do it, you'll need to add just a few line of code to do ellipse-ellipse collision (assuming the ellipses cannot rotate, and their axis are along the X,Y and Z axis).

If you world can be assimilated as being 2D (ie the map of your world can be represented in 2D), then all you need is circle-circle collision, which is very simple once you have a vector2D class.

##### Share on other sites
it has to be a 3d world. i like would most likely be using the 3d version of an elipse ( pardon the simplicity of that statement), rather than a sphere, as it would look better for person representation. i have to make my "charachters" run convincingly. they have to be able to move their arms, and they will have eyes so the user knows which way they are facing. the 3d world will be very simple, with a few 3d rectangles in the charachters way as obstacles, just to make the application more interesting. i hope this is a better explination of what i need to do. thanks for all your help

##### Share on other sites
I would just do a circular cylinder. You would just have to check their distance on the x-z plane and see if their y's are close. It's really simple.

##### Share on other sites
If you need 3D then use ellipsoids. But start with sphere-sphere collision (and represent your people as sphere).

Once this works, you'll be able to change it to ellipsoid, by "scalling" your spheres unevenly on each axis when doing collision detection.
isColliding(sphere1,sphere2){  distance = sq(sphere1.x-sphere2.x);  distance = sq(sphere1.y-sphere2.y);  distance = sq(sphere1.z-sphere2.z);    if(distance <= sq(sphere1.radius+sphere2.radius))    return true;  else    return false;}// Not sure about what I'm writing here.// The idea, is to add the radii of the ellipsoids on each axis// to make a *big* ellipsoid centered on ellipsoid1, then to// scale the world so that the big ellipsoid become a unit sphere,// and then test if the unit sphere is colliding with the scaled// center of ellipsoid2.// I'm assuming that the ellipsoids cannot rotate, but if // radiusX=radiusY, you can have rotation around the Z axis.isColliding(ellipsoid1,ellipsoid2){  Sphere sphere1;  Sphere sphere2;  sphere1.x = ellispoid1.x/(ellipsoid1.radiusX+ellipsoid2.radiusX)  sphere1.y = ellispoid1.x/(ellipsoid1.radiusY+ellipsoid2.radiusY)  sphere1.z = ellispoid1.z/(ellipsoid1.radiusZ+ellipsoid2.radiusZ)  sphere1.radius = 1;  sphere2.x = ellispoid1.x/(ellipsoid2.radiusX+ellipsoid2.radiusX)  sphere2.y = ellispoid1.x/(ellipsoid2.radiusY+ellipsoid2.radiusY)  sphere2.z = ellispoid1.z/(ellipsoid2.radiusZ+ellipsoid2.radiusZ)  sphere2.radius = 0;  return isColliding(sphere1,sphere2);}

So start with spheres, then when you're sure it works, add the scaling to have ellipsoid. You will even be able to simulate overweight/skinny people by changing the scaling.

Don't use cylinders, it's more difficult (although I think it's a nicer representation).

However, the way you describe your program, it seems that your world is a 2D world (although it is represented in 3D). You don't seem to have different floors, stairs, people jumping, etc...

So, you could use a simple 2D circle-circle collision (similar to the sphere-sphere collision), where the radius of the circle is the radius of the area covered by your character. That wouldn't prevent you from displaying your world in 3D.

• 13
• 18
• 29
• 11