Newbie - Collision Process

This is a massive subject. It can be very simple to do but in modern games you often need a quite sophiticated algorithm to deal with all the possible kinds of collisions, objects and outcomes using the minimum amount of processor time and memory.

I find this page

http://www.ams.sunysb.edu/~jklosow/quickcd/QCD_resources.html

useful as a starting point for finding information on collision detection: it has links to a number of different algorithms and to pages of people who work with them, many of them the leading people in the field. It does not tell you which is best for you, as that depends on your game.

Thanks for that site, However it hasn''t helped too much,
I do not particularly want packages to acheive collision detection. And i know some of them have source code but Can I just have like a basic overview of how it works?

ie, I have heard things about testing points to see if they are on a triangle, things that i would like to know is like:
What triangle do you test on (all of them??)
What point do you test?
How do you get these values?
and What will it acheive?

Things like that. I know how to do the maths, but not the theory

Thanks
--Josh

Well, it depends on what kind of collision detection you want. If you want an ellipsoid for your character and check against all the polygons in your world, then http://www.peroxide.dk/tutorials/tut10/pxdtut10.html is an excellent article. basically the way it works is you scale the world according to the vectors of your ellipsoid, so as that a unit sphere (a sphere with a radius of 1.0) is to the new world as the elipsoid is to the original, unscaled world. Checking collisions with a unit sphere is about as fast as you can get, so it works very well.
Of course, you''ll have to do an ellipsoid-ellipsoid check for other chaarcters, which the article doesn''t cover, but you can worry about that after getting the world collisions working. Actually, you could use the same technique so you only have to do a unit sphere-ellipsoid test^^ I don''t know how to do either though, so I don''t know what the speed difference would be.

Also, using a quadtree or octree would most likely make a very large improvement on the speed of the algorithm in that article.

Good luck!

---

-Deku-chan

DK Art (my site, which has little programming-related stuff on it, but you should go anyway^_^)

Thanks for that, The article is very helpful
So, for an elipsoid, Would it be correct to say that I am testing to see if the elipse intersects the plane that the triangle is in, and if it does intersect it, Do the points that it intersects at lie inside the triangle?
If so, then i have a collision
Is this the way i should be thinking of it?

It is beginning to make more sense now I think!

--Josh

I keep hearing about quadtrees or octrees Could you please explain them to me?

quote:

---

Original post by JoshG
I keep hearing about quadtrees or octrees Could you please explain them to me?

---

It took me five seconds to get to the Gamedev page of graphics articles:

http://www.gamedev.net/reference/list.asp?categoryid=40

which includes articles on quadtrees and octrees.

The articles and resources section of GameDev is very comprehensive and covers a wide range of topics in game development, so before posting it''s worth checking there to see if your question has already been answered.

John

Sorry about that,
I have always assumed that the "Graphics" section of the Resources was to do with 2D graphics. Seeing as OpenGL and DirectX are covered in other places.

Thanks for pointing me to these things, I guess i assumed wrong! Sorry

--Josh

I just incorporated the tutorial at http://www.peroxide.dk/tutorials/tut10/pxdtut10.html into my 3d game, and one of the functions he uses, CheckPointInTriangle(), didnt work right, so i remade that function and it doesnt use acos() anymore and now the CD works properly. If you try using that and need a lil hand, feel free to email me..

Hi...

I also tried the peroxide tutorial but haven''t got it to work successfully.. It works when the collision occurs inside the triangle, but when the collision is on an edge (like a boxedge) and velocity is towards and along the edge, then you can pass through (no collsion occurs).

rgirard413 I''ve tried to mail you but your mailaddress seems to be wrong!. It would be interesting to see how you made it work!

Here is an image of the problem: