🔒 Locked

Collision Detection

Started by Sean Doherty Jul 3, 2004 at 7:23 PM 9 replies 1.9k views

Original Post

Jul 3, 2004 at 7:23 PM

At present, I have been using bounding spheres to check for object colisions. However, is there is easy way given to determine the actual intersection point (in world space coordinates) of an object collision. For example, I am firing a laser at an object; the laser automatically locks onto the object so I know it hits. However, I would like to determine the exact coordinates of the collision so I can initiate a pariicale system for the explossion. Basically, I have: Source Position of the Laser Beam. Target Position of object Laser Beam is striking. Vector between the two (via calculation). The Mesh and World Space Matrix for the object being hit by the Laser. From what I can tell D3DXIntersect does not allow my to plug in the World Space Coordinates of the Object. So I am unsure how the calculate the collion Coordinates? Thanks

paranoia33

Jul 3, 2004 at 7:51 PM

Transform all of your mesh coordinates using D3DXVec3TransformCoord() then if you know the 3 coordinates of the triangle you coolided with then you can use the equation of a plane Ax+By+Cz+D and get the exact location of the hit..

Ill email you my source because its a lot to take in..im sure there is an easier way also that someone else knows but w/e.

Sean Doherty

Author

Sean Doherty

Jul 3, 2004 at 8:31 PM

paranoia33,

That would be great if you could email some source:

Thanks

Sean.Doherty@FreelanceGames.com

Etnu

108

Etnu

Jul 3, 2004 at 9:01 PM

You can test a ray -> triangle intersection this way.

//------------------------------------------	// TriangleIntersect()	// Given a triangle (v1,v2,v3), and a ray with	// origin at vOrigin, extending in vDirection,	// returns true if the ray intersects the triangle	// using Moller's Algorithm.	//------------------------------------------	inline bool TriangleIntersect(const Vec& v0, const Vec& v1, const Vec& v2, const Vec& vOrigin, const Vec& vDirection, Vec& vTUV, bool bTwoSided)	{			// Calculate edges.		Vec vEdge1 = v1 - v0;		Vec vEdge2 = v2 - v0;		// P point.		Vec vT, vP, vQ;			CrossProduct(vP,vDirection,vEdge2);				// Determinate		float fDet = DotProduct(vEdge1, vP);		if(!bTwoSided)		{			// Test for intersection with forward-facing triangles only.			if(fDet < 0.0001f)				return false;						vT = vOrigin - v0;		       			vTUV.y = DotProduct(vT,vP);			if(vTUV.y < 0.0f || vTUV.y > fDet)				return false;			CrossProduct(vQ,vT,vEdge1);						vTUV.z = DotProduct(vDirection,vQ);			if(vTUV.z < 0.0f || vTUV.y + vTUV.z > fDet)				return false;			vTUV.x = DotProduct(vEdge2, vQ);			float fInvDet = 1.0f / fDet;			vTUV *= fInvDet;		}		else		{			// Just test for any intersection			if(fDet > -0.00001f && fDet < 0.00001f)				return false;			float fInvDet = 1.0f / fDet;			vT = vOrigin - v0;			vTUV.y = DotProduct(vT,vP) * fInvDet;			if(vTUV.y < 0.0f || vTUV.y > 1.0f)				return false;			CrossProduct(vQ,vT,vEdge1);						vTUV.z = DotProduct(vDirection,vQ) * fInvDet;			if(vTUV.z < 0.0f || vTUV.z + vTUV.y > 1.0f)				return false;			vTUV.x = DotProduct(vEdge2, vQ) * fInvDet;		}		return true;	}

vTUV:
T = distance along the ray to the intersection.
U / V = Barycentric coordinates of the intersection.

If you start at origin vOrigin, and travel in vDirection for T units, you'll have your point of intersection.

Jojo_the_fluffy_bear

Jul 3, 2004 at 10:12 PM

Do you want to check for a collision against the sphere or the mesh of the object? I'm assuming it's the bounding spehere you want to get the point of collision for.

How I would do it is get the vector from the object that's firing the laser to the object that's being hit, normalize that vector and then multiply it by the radius of the sphere, and finally add it to the position of the object being hit.

                     rP2 ------------> Dv --> P2

Where P1 is the object that's firing, P2 is the center of the object being hit, r is the radius of the bounding sphere and Dv is the vector to the point of the intersection.

(||P1-P2||*r) = Dv
Dv + p2 = point of intersection

(sorry for the shoddy ASCII art... and probably shoddy math, but hay, it's late!)

Now, this assumes that the line goes directly from the object firing to the center of the object being hit. If you want a proper line/ray-sphere intersection test, that'll take me a while to dig up.

Hope this helps.
-Jojo

Sean Doherty

Author

Sean Doherty

Jul 3, 2004 at 11:24 PM

Quote:
Original post by Etnu
You can test a ray -> triangle intersection this way.
*** Source Snippet Removed ***

vTUV:
T = distance along the ray to the intersection.
U / V = Barycentric coordinates of the intersection.

If you start at origin vOrigin, and travel in vDirection for T units, you'll have your point of intersection.

Etnu,

I am not completly folling you? I have a Mesh, do I have to use the function that you provided to test every triangle in the Mesh for an intersection?

If so, I assume that I do this by Transforming all of your mesh coordinates using D3DXVec3TransformCoord()?

Thanks

Sean Doherty

Author

Sean Doherty

Jul 3, 2004 at 11:26 PM

Quote:
Original post by Jojo_the_fluffy_bear
Do you want to check for a collision against the sphere or the mesh of the object? I'm assuming it's the bounding spehere you want to get the point of collision for.

How I would do it is get the vector from the object that's firing the laser to the object that's being hit, normalize that vector and then multiply it by the radius of the sphere, and finally add it to the position of the object being hit.

*** Source Snippet Removed ***

Where P1 is the object that's firing, P2 is the center of the object being hit, r is the radius of the bounding sphere and Dv is the vector to the point of the intersection.

(||P1-P2||*r) = Dv
Dv + p2 = point of intersection

(sorry for the shoddy ASCII art... and probably shoddy math, but hay, it's late!)

Now, this assumes that the line goes directly from the object firing to the center of the object being hit. If you want a proper line/ray-sphere intersection test, that'll take me a while to dig up.

Hope this helps.
-Jojo

Jojo,

I am actually using a varation of a bounding Sphere at present. I was hoping to be able to actually check the exact point of intersection against the Mesh not the bounding sphere?

Thanks

Jojo_the_fluffy_bear

Jul 5, 2004 at 2:38 PM

Okay, then you'll just have to do a standard ray/line-plane intersection test (yep, for every triangle in the mesh) and then convert the coordinates into barycentric space. You could alternatively get the angles between the point of intersection on the plane and each point of the triangle you're testing for intersection(using acos) and then add them up. If the measurement is equal to 360' then the point is inside the triangle, if it's more than that, then the point does not lie inside the triangle.

Using barycentric space can be a bit involved, and using acos, while easier than the aforementioned method, is a pretty costly operation- especially for every single plane with which the line/ray intersects. You might come up with a line intersecting several planes with only one of the intersections lying inside a triangle.

Since Jojo's memory isn't what it used to be, I couldn't really give you the equations for doing any of that stuff offhand. If you'd like I could post some, but not until I have some good solid references in front of me.

However, what Etnu posted is an excellent method.

And to answer your first question: Outside of using bounding speheres (which are by far the simplest to use) to check for object collisions, there aren't any 'easy' ways to check for collisions/intersection as all of the methods I've ever seen are fairly involved with the mathematics.

-Jojo

Etnu

108

Etnu

Jul 5, 2004 at 3:06 PM

Keep in mind you can use point -> sphere collision as a preliminary method, as it's extremely fast (a simple distance calculation), and only have to test triangles when they fail the sphere test.

SoaringTortoise

Jul 5, 2004 at 3:39 PM

Something I'm doing that you may find useful->

Every mesh as a simpler collision mesh (for example, a piller uses a cylinder, a human uses a cylinder and a sphere, wall objects use a cube, etc). This makes the ray-collision test much faster (a human model uses 800+ polys. A cylinder + simplified sphere uses around 120).

My collision goes like this:

1) Test for sphere (fast and dirty)2) If there is a collision   3) Get a ray and a start point (i.e. the gun muzzle and the direction pointing)    4) Transform the ray and start points using the INVERSE matrix of the object. I use the DirectX functions d3dxmatinverse, d3dxVec3TransformNormal and d3dxvec3TransformVertex to do this.    5) Finally I use the d3dx.Intersect method on the low-detail meshes to get an exact collision face (plus distance)

You can easily use the returned distance to project along the ray to get a specific collision point (normalize the ray, scale it to the distance and add it to the starting point).

I've heard it said that the Microsoft supplied d3dx* functions are very slow. However, I'm writing in Visual Basic 6 so I'm pretty certain that they'll be much faster than anything I can do in VB :-p

SoulSpectre

Jul 5, 2004 at 3:54 PM

I wouldn't recommend calculating a collision for every triangle in the mesh, unless you HAD to do it. Some reasons you may need to: calculating deflections, applying effect to triangle. Calculating line/plane tests for large meshes will be costly. If it is just to see if a bullet hit a person then use this approach:

1. A bounding sphere for first test.
2. An assortment of spheres, cylinders, cubes for sub test of collision.
3. repeat step 2 zero or more times for greater detail of the sub objects.
4. (optional) perform sub tri test of tris in this sub node.

The good thing with this approach is that if your mesh is animated, you can attach the nodes to the bones, else if you are just keyframing you will need to keyframe the nodes too.

If the mesh is a static mesh - ie doesn't change its shape, then use a line to bsp tree test but that may be beyond your ability atm so just use the approach I showed above. Unless you need the exact hit position use the bsp or tri test.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.