Archived

This topic is now archived and is closed to further replies.

Collision Detecting

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

Recommended Posts

I read the NeHe tutorial on collision detecting. But I don''t understand what he''s saying. Could someone please explain it or is there a web page where I can go to get a better understanding? I just want to do basic detection for planes and spheres.

Share on other sites
if you have simple planes like x = 0 or y = 0 or z = 0 then to find the distance between a point and the plane is very simple. For example, if your plane is x = 0, then the distance from a point to it is simply the absolute value of the x coordinate of that point. eg (4, 1.5, 9) is 4 units away from the plane x = 0.

however, if you have a plane at arbitrary angles, the math is a bit more complex. Assuming that the plane has the equation
Ax + By + Cz + D = 0, and your point is (Xo, Yo, Zo), the distance between the two is
abs((A*Xo + B*Yo + C*Zo - D)/sqrt(A^2 + B^2 + C^2))

you can arrive at that formula with some vector analysis, ask me if you want me to explain it.

I hope this helps, sorry if it came out confusing.

/riley

Share on other sites
Yup.. there''s a math geometry page at: http://www.swin.edu.au/astronomy/pbourke/geometry/

It deals with alot of intersections with planes and lines etc.

-- wav

Share on other sites
Forgive my ignorance, but isn''t it easier and faster to calculate the distance between a point and a plane using the plane''s normal, one point on the plane, and a dotproduct?
www.mr-gamemaker.com ''s tutorial on the dotproduct covers this and is IMHO a very good read for beginners in the collision detection area. You can find it here: http://64.33.37.114/math_rot3.html

Share on other sites
"but isn''t it easier and faster to calculate the distance between a point and a plane using the plane''s normal, one point on the plane, and a dotproduct?"

abs((A*Xo + B*Yo + C*Zo - D)/sqrt(A^2 + B^2 + C^2)) is what you end up with when you do that. The sqrt comes in when you normalize the, err, normal (scale it down so its length is one). The point on the plane you were talking about gets sucked into D. If the point were (Xp, Yp, Zp) then you would end up with A*Xp + B*Yp + C*Zp. From the equation of the plane you know that A*x + B*y + C*z + D = 0, so A*Xp + B*Yp + C*Zp = D.

I love that stuff =)

/riley

Share on other sites
rileyriley,
I would like it if you would explain it a little bit better. To draw my planes I am using GL_QUADS and four vertices.

Share on other sites
Running_Wolf: Okay, you have a quad''s verticies labeled P1,P2,P3 & P4.

Firstly, you need to find the normal vector (a vector which is perpendicular to the actual quad). Let N represent the normal vector.

N.x = P1.y*(P2.z - P3.z) + P2.y*(P3.z - P1.z) + P3.y*(P1.z - P2.z)
N.y = P1.z*(P2.x - P3.x) + P2.z*(P3.x - P1.x) + P3.z*(P1.x - P2.x)
N.z = P1.x*(P2.y - P3.y) + P2.x*(P3.y - P1.y) + P3.x*(P1.y - P2.y)

Then you should normalize this vector to make it easier for openGL to digest:

Mag = Sqrt((N.x*N.x)+(N.y*N.y)+(N.z*N.z)) // Length of Vector
N.x = N.x / Mag // Normalize Vector
N.y = N.y / Mag
N.z = N.z / Mag
-------------------------------------------------------------
Next, the equation of a plane.. Ax + By + Cz + D = 0
(where A, B & C represent the plane''s normal)

You then need to find the constant term, D, and you do this by substituting any point on your quad for x,y & z.
D = -(N.x*P1.x + N.y*P1.y + N.z*P1.z)

With the new found value for D, you now can write your plane equation as:

N.x(x) + N.y(y) + N.z(z) + D = 0
--------------------------------------------------------------
So how do you find the distance between a point and the plane on which your quad lies? Substitute a point in for x,y, & z.

Want to find out the distance between the point (0,1,6.5) and your quad''s plane? do this:

Distance = N.x(0) + N.y(1) + N.z(6.5) + D

which, in turn, simplifies to:
Distance = N.y + N.z(6.5) + D

-- Wav

Share on other sites
Thanks wavarian,
I have just one question. The normals that you calculated and set for the quads. Is it applicable to normals when I try to do lights or do I have to do a seperate normal calculation for each of my quads?

Share on other sites
The normals specified may be used for lighting as well. As for your other question, it depends. If you intend to draw exactly the same quad, but only rotate it a certain degree about the y-axis, or translate it, then yes you can use the same normal for the rest of your rotated/translated quads, just as long as you do to the normal just as you do to the quad. eg.

glNormal3f(0,0,1)

glPushMatrix
glRotatef(45,0,1,0) // This line would rotate the Normal AND the quad at the same time.
glNormal3f(0,0,1)
glPopMatrix

--wav

Share on other sites
Okay, I got it to tell me when the distance i zero but I have a couple more problems. When I reach 0.5 from the quad I have a bool moveforward or movebackward that is turned to false. But when this happens I get stuck. I can''t go anywhere. How is the best way to make it so that when the player is close to a quad or sphere that they can''t go forward or backward as the case may be but can still go in the other directions. Also, right now I have to check with every single quad or sphere I have. How can I tell where the player is going and what objects are in that direction and just check them? Did that make sense to anyone?

Share on other sites
Yup, the easiest way to do this, is to find exactly where the player is moving before he moves there.

A basic example on how to do this:

Temp_Cam.x = Camera.x + 0.4
if CheckCollision(Temp_Cam.x) then DontDoNextLine
..else Camera.x = camera.x + 0.4

Temp_Cam.y = Camera.y + 0.4
if CheckCollision(Temp_Cam.y) then DontDoNextLine
..else Camera.y = camera.y + 0.4

Temp_Cam.z = Camera.z + 0.4
if CheckCollision(Temp_Cam.z) then DontDoNextLine
..else Camera.x = camera.z + 0.4

Sorry, i have limited time on my hands, if you want a more detailed example, i''d be more than happy to post it here.

Share on other sites
wavarian,
Could you post a more detailed example? I understand what you mean I just can''t implement it right. Meaning I get weird things like no matter what I do I can''t move forward and stuff like that. If you want to see the code please e-mail me.

Share on other sites
I got it working!!! There is just one small problem. It seems that the formula that you gave me is for infinite planes. My plane is not infinite. I wish to be able to walk around it. How do I do that?

Share on other sites
test if the point where the plane intersection occurs is inside the polygon. theres heaps of info on the web on how to calculate this

http://members.xoom.com/myBollux

Share on other sites
zedeek,
Where can I find some of this info?

Share on other sites
wavarian:
Sorry, I don''t quite understand what you did. Is what you just said and extension to the equation you gave me earlier or does it replace it? In short, I''m just not quite sure how it all relates to each other. Sorry if I am being a little annoying or stupid. I have a hard time grasping some things.

Share on other sites
>>zedeek,
Where can I find some of this info?<<

and type ''point inside polygon''

http://members.xoom.com/myBollux

Share on other sites
A simple way of determining if a point P is inside a polygon is to:

1. Draw a line from P to each vertex of the polygon
2. Add up all the P angles of each triangle thus formed
3. If the angles add up to 360, the point is inside the polygon
4. If the angles add up to less than 360, the point is outside the polygon.

Cheers

Share on other sites
wavarian: I don''t think that I am implementing it right yet? It doesn''t seem to work. Here is what I am doing. If you want all my code just ask.

I create a quad of:
p1: 0.0, 2.0, 3.0
p2: 0.0, 2.0, 0.0
p3: 0.0, 0.0, 0.0
p4: 0.0, 0.0, 3.0

at creation(in the InitGL function for testing but will be part of the constructor in the final class)

float nx, ny, nz, mag, d
nx = p1.y*(p2.z - p3.z) + p2.y*(p3.z - p1.z) + p3.y*(p1.z - p2.z)
ny = p1.z*(p2.x - p3.x) + p2.z*(p3.x - p1.x) + p3.z*(p1.x - p2.x)
nz = p1.x*(p2.y - p3.y) + p2.x*(p3.y - p1.y) + p3.x*(p1.y - p2.y)
mag = sqrt((nx*nx) + (ny*ny) + (nz*nz))
nx = nx / mag
ny = ny / mag
nz = nz / mag
d = -(nx*p1.x + ny*p1.y + nz*p1.z)

In the Main Function:
float dv1, dv2, dv3
float distance, d2
float x1, x2, x3

Every time through the loop:
dv1 = x - x2
dv2 = y - y2
dv3 = z - z2
(x,y,z being the place to move to and x2, y2, z2 being current position)

d2 = (-d - nx*x2 - ny*y2 - nz*z2) / (nx*dv1 + ny*dv2 + nz*dv3)
x1 = x2 + (d2*dv1)
y1 = y2 + (d2*dv2)
z1 = z2 + (d2*dv3)

if ((x1 > 0.0) && (x1 < 0.0))
if ((y1 > 0.0) && (y1 < 2.0))
if ((z1 > 0.0) && (z1 < 3.0)) {
distance = x1*x2 + y1*y2 + z1*z2 + d
if ((distance < 0.5) && (distance > -0.5))
movef = FALSE;
else
movef = TRUE;
}
Draw Scene

What am I doing wrong?

Share on other sites
Well firstly, from quick glances at your code, i see that you have:

if ((x1 > 0.0) && (x1 < 0.0))

This is saying that x1 must not be equal to 0.0, try doing it something like this:

if ((x1 >= 0.0) && (x1 <= 0.0)) // Not sure how c++ works with this

so that the point is ''allowed'' to be sitting on the x-axis.

-- Wav

Share on other sites
wavarian: The line that says, "if ((x1 > 0.0) && (x1 < 0.0))" is part of my code to see if the point is in my quad. It still stands to reason that I need to make them equal to. I just wanted to make sure that we were talking about the saem thing.

Share on other sites
I wrote a simple collision for wall 90 degree from the floors
quad walls can be angled but 90 degrees to floor.

I send the code for testing, if i get a reply.

BGCJR

Share on other sites
BGCJR: I would like to see that code to compare it to what I have already. Thanks a lot.

wAVaRiaN: I got it working a bit better. Now it almost works. I can get caught on either side of the quad and when I am not ''looking'' straight at the quad I can move. But I get caught and can''t move whenever I ''look'' at the quad no matter what my distance is. I put the code into a class and made some other files that I use. If you want to see the code just tell me and I will e-mail you a ZIP file containing my project. It is in VC++ 6.0 Service Pack 2. Thanks a lot.

Share on other sites
Whats the point in putting if((x1<=0.0)&&(x1>=0.0)) why don''t you just put if(x1==0.0)

Share on other sites
Its fine doing it like that in that example anon, but when the values change, it is required.

Running_Wolf: Unfortunately i don''t program in c++, guessing is my way through that language, and i doubt i would understand anything else written in it.. :/

There are other ways of determining whether or not a point is in the polygon''s space, and they were mentioned before. You should try those, they''re not only more accurate but also quite easy to implement.

-- Wav