PDA

View Full Version : collision detection



robert
02-15-2001, 07:41 AM
can someone please help me, I need to know how to do line and plane collision detection.

I dont need anything fancy, I just need help!! :P

DFrey
02-15-2001, 08:02 AM
Are you wanting to simply determine if a line intersects a plane? Or where a line segment intersects a plane if it does?

robert
02-15-2001, 09:48 AM
just a line intersecting a plane http://www.opengl.org/discussion_boards/ubb/smile.gif

DFrey
02-15-2001, 10:18 AM
Ok, given a plane with normal N and displacement d, and a line parameterized by r(t)=r(0)+(r(1)-r(0))*t:

Take the dot product of N and r(1)-r(0). If the result is (or is close to) zero then assume no intersection. Otherwise there is a intersection. Do you want to know where that intersection is?

robert
02-15-2001, 10:23 AM
Thanks for your help, how do I get the d? Also, I would like to know where the intersection occurs :P

DFrey
02-15-2001, 10:57 AM
Any plane can be defined by a normal N and displacement d, such that for any point P in the plane, the following must be true:

N P - d = 0

Sometimes people will use +d rather than -d but that doesn't change anything significant (only a sign convention). So you see to get d, you just pick a point in the plane and stick it in that equation and solve for d.

To find where the intersection of the line and plane is, substitute r(t) for P and solve the system of equations for t (see Cramer's rule). Then solve for r(t). If you want to see if r(t) is a point on the line segment between r(0) and r(1), you easily check to see if 0<=t<=1, if so then r(t) is a point on the line segment, and therefore the line segment intersects the plane (this is good to know for collision detection since each frame you can only move a step at a time, the path of which is a line segment).



[This message has been edited by DFrey (edited 02-15-2001).]

Michael Steinberg
02-15-2001, 11:07 AM
I once had nothing to do and solved these equations:

a + r*b + s*c = d + t*e

That results in very LONG terms... http://www.opengl.org/discussion_boards/ubb/smile.gif And it's still longer than any other intersection equation. I wonder why we don't get teached the easiest equations in school.

Michael Steinberg
02-15-2001, 11:11 AM
But, DFrey, I wonder why d is called displacement. Displacement sounds like that the plane is translated in some direction about d units.

I wonder why there are so many representations of planes. How do you come to your representation, DFrey. I somehow remebers me of the normal represenation of a plane. But that again looked differently.

DFrey
02-15-2001, 11:16 AM
It is called displacement because it is a displacement from the origin. See, the shortest line from the origin to the plane will have length |d|. And I'm not doing anything special to come up with these plane definitions either, they are just what I learned in Calculus and Analytical Geometry with all the other first year students.


[This message has been edited by DFrey (edited 02-15-2001).]

Michael Steinberg
02-15-2001, 12:35 PM
I start with the normal representation

(x-q)*n = 0

(x1-q1)*n1 + (x2-q2)*n2 + (x3-q3)*n3 = 0

x1*n1 - q1*n1 + x2*n2 - q2*n2 + x3*n3 - q3*n3 = 0

x1*n1 + x2*n2 + x3*n3 = q1*n1 + q2*n2 + q3*n3

x*n = q*n

where q*n is your N*P So:

q*n - x*n = 0

But x*n is no distance.

Or is your operator another product?

You see, DFrey, my problem is that we don't learn enough here. We always calculate to long with the equations we get. We already stopped with linear algebra. It will come the next time when I study on the university... So I try to follow. I'm sorry if I sound a bit idiotic... http://www.opengl.org/discussion_boards/ubb/smile.gif

Michael Steinberg
02-16-2001, 05:38 PM
Any light on it? Thanks!!!

DFrey
02-16-2001, 07:45 PM
I'm wondering if your computer is not using a font with the dot symbol. That's what I wrote.
(N dot P) - d = 0

N dot P has units of length since N is a unitless vector and the components of P have units of length.

Michael Steinberg
02-17-2001, 02:13 AM
Well, we didn't discuss the dot product in school nor did we discuss the cross product. Are there any articles where I could learn about them? Thanks!
PS: The dot is correct here, just my interpretation isn't... http://www.opengl.org/discussion_boards/ubb/smile.gif

02-17-2001, 03:09 AM
Hi!

Michael and DFrey: I think you guys are talking about the same. I mean n=N: normal vector with unit length, q=P: a point of the plane and x*n=d: the distance of the plane from the origin. Or am I wrong?

dav