OasisGames

Hello, as some of you may know, I'm working on a collision detection system, and thanks to PolygonSoup, I've gotten a lot further allong. In my tests, speed does not seem to be affected at all by my method of going through every triangle in the level if I base my collision on a single sphere, but I have problems with the collision itself. I used a rough (and horribly incorrect) algorithm to detect if my sphere is even remotely close to the triangle.
What I'm looking for is a formula that will tell me the distance between point [X,Y,Z] and triangle [(X,Y,Z),(X,Y,Z),(X,Y,Z)].
After that, I will simply determine if the distance is less than the radius of my sphere.

Thank you.


Re: XNA Game Studio Express Collision Detection Cont.

Darkside

Dont know of any specific algorithms

But have you tried looking through http://gpwiki.org Game programming Wiki, does have a lot of good programming references.

Darkside






Re: XNA Game Studio Express Collision Detection Cont.

Gloei

Hi, you don't have to do it that way. I know of these two possible approaches to determine the intersection point between a sphere and a triangle. These are:

1.
Find the point on the triangle that is closest to your sphere's center. If the distance between the sphere's center and this point is smaller than the radius of your sphere, then this is your intersection point. Otherwise, there is no intersection.

2.
a) Test the distance of the plane of the triangle to the sphere's center. If this distance is larger than the sphere's radius, then there is no intersection.
b) Then project the sphere's center onto the triangle's plane. If this projected point is within the triangle's area (defined by its three edges), then this point is the intersection point.
c) If this point was outside the triangle's area. We need to find, for each edge, a point on the edge closest to the sphere's center. If any of these three points has a distance to the sphere's center that's smaller than the sphere's radius, then that point is our intersection point.

I believe your question is about method 1. In my own collision detection code, I use method 2. AFAIK method 1 involves some optimization algebra. Using barycentric coordinates or something, but I'm not so sure. I've briefly looked into it, but it seemed quite hard to understand for me. Method 2 involves some point/plane distance math.

I'll see if I can post my sphere/triangle intersection detection code here.








Re: XNA Game Studio Express Collision Detection Cont.

Gloei

Here's my implementation of a sphere/triangle intersection test.

It it a simple test to see if a sphere at a certain position with a certain radius intersects with (the front side of) a triangle. It will return the normal of the intersection and the location within the triangle of the intersection.

For myself I have it "enhanced" to handle also ellipsoids and return the penetration depth of the intersection, but both are not working correctly, so this is not in the source.

Anyway, this seems to work okay. Hopefully this will help you guys out. I myself didnt have much fun coding it (found lots of bugs in it ;)), but since there wasnt any off-the-shelf solution for it, I was forced to implement it myself. Maybe someone can make a general purpose collision detection library for XNA That would be quite useful I guess. Something like Opcode, but then in XNA.




Re: XNA Game Studio Express Collision Detection Cont.

OasisGames

Thank you! You're code works perfectly!
I'm going to record a video and put it on youtube for others to see (already did one without collision)