OT: Collision detection. Does this sound fast enough for 60 FPS??

OpenGL OpenGL: Advanced Coding
1

I was attempting to use “coldet” for a game I am working on. But I find that the Collision Points that are returned arent what Im looking for. I am looking for the point to a depth of penetration within the object.

Here is my idea for my collision workings. Let me know if you think this would be fast enough and reliable.(On a side note: I am working with (deformable) models. So (coldet) wouldnt work for this either.)

Items are set up like this. Most items are very very very low Poly. And each Vert that makes them up is setup in and index, (so duplicates are dropped out compleatly). Also they are surrounded in a bounding sphere (for initial checks).

Now to test against a wall. I would do this. I would first check the distance between the sphere and the wall. If it passed that test. I would then find the distances to the wall for all the verts in the model. And depending on what was one was negative (behind the wall). I have my collision pt. This would work on deformable items, Plane collisions, sphere collisions, and with some redisigning, it could also work for model to model collisions.

My major issue is this. It would require a sqrt for EVERY vert (about 10-30 per object), plus the initial sphere check. Plus the normal multiplying and diving and so on.

Do you think this would be a fast enough method to do at 60fps with everything else that has to happen?

(I ask this because I REALY REALY want this game to have very interactive worlds. Instead of this Yeah its a wall, and another wall) And to have interactive worlds, you must have GREAT Collion Detection, cause I hate it when Things fall through walls.

Let me know what you think, thanks.

2

Why do you need to do sqrt for every part? Is there some reason why you can’t just use the distance^2?

a^2 + b^2 + c^2 = r^2 ~ so just compute r^2 an it should save you doing the square root.

3

Would that be faster? If it is I will PLOTTS. I cant believe I NEVER thought about doing it that way. I bet a simple multiplication is A HELL of alot faster than using sqrts. Thanks a million times over. (although I CANT BELIEVE, how stupid I feel)

EDIT:

That will work great for the distance to the bounding sphere. BUT! You have to use a SQRT when working with plane to point distances. Because you have to take the cos(theta)* the length of the vector AFTER you have taken the sqrt of that vector. If i did it with out taking the sqrt, it will throw off the order of operations, and I will get the wrong value. So that did solve half my battle. BUT my question still remains. Will the remaining SQRTS needed be feasible?? Or does some one else have a faster way to find the shortest distance from point to plane?

[This message has been edited by dabeav (edited 09-10-2002).]

4

What does PLOTTS mean?

5

It means crap myself.

6

How are you computing distance to the plane? Are you using a parametrized line (using the planes normal vector originating at the point you want to test), and testing to see at what value of x, y, and z the parametrized line intersects the plane? If so, you shouldn’t really need to take any sqrt (or do any cosine stuff either, for that matter). Everything should just be arithmetic.

If you don’t know what I’m talking about, I’ll tell you here:

You have a point (your vertex) P at (px, py pz). So:

P = [px, py, pz]

You have a plane with equation:

A(X-x0) + B(Y-y0) + C(Z-z0) = 0

(X Y and Z are variables)

The normal vector to the plane is hence [A,B,C]. This means you can define a line from P:

[px+At, py+Bt, pz+Ct]

t is variable. So you end up with the system of equations by combining the parameteric equations with the planar equation to get the set:

px+At = A(X-x0)
py+Bt = B(Y-y0)
pz+Ct = C(Z-z0)

Solve these for their respective X, Y and Z and you get equations in t.

X = px/A + x0 + t
Y = py/B + y0 + t
Z = pz/C + z0 + t

Substitute these expressions back in for their respective variables in the planar equation and you get the incredibly messy:

A(px/A + x0 + t-x0) + B(py/B + y0 + t-y0) + C(pz/C + z0 + t-z0) = 0

This really gets simple tho, as you can see it’s just

px + At + py + Bt + pz + Ct = 0

which you can solve for t to get:

t = -(px+py+pz)/(A+B+C)

Stuff t back into you parametric line equation, and you have your point on the plane. Let’s call this set of points X’ = [x’, y’, z’].

In order to get distance now, all you have to do is take P - X’ and get X’’, so:

[px, py, pz] - [x’, y’, z’] = [x’’, y’’, z’’]

And just check to see if:

x’’^2 + y’’^2 + z’’^2 is greater than or equal to 0, as well as checking to see if it’s in the same direction as the normal vector for the plane (this will tell you if you’re getting a non-zero distance because you haven’t collided yet or have already gone through).

If anyone spots and error please feel free to tell me.

[This message has been edited by Plato (edited 09-10-2002).]

7

Um… ya, so that’s not very clear I don’t think.

All you have to know is the equation of the plane:

A(X-x0)+B(Y-y0)+C(Z-z0) = 0

(you get A B C from the normal vector, and x0, y0, z0 is just the translation from the origin)

The coordinates of your vertex:

P = [px, py, pz]

And the solved parametric equations, which are:

X = px/A + x0 + t
Y = py/B + y0 + t
Z = pz/C + z0 + t

And that to compute t, all you need is:

t = -(px+py+pz)/(A+B+C)

So you compute t, get your X,Y,Z by computing the solved parameteric equations (which, by the way, can be simplified a tad more ~ just put the expression for t into each equation and simplify it). Which leaves you with 2 vectors from the origin - one to your vertex and the other to the nearest point on the plane. The difference between these two vectors is the distance vector.

8

Ok let me get this strait. Ill do a break down of the way Im currently doing it, and the way you are doing it, let me know if im right.

MY WAY:
Using a (random) point on the plane(PlanePx,PlanePy,PlanePz). Draw a line from my Vertex (Px,Py,Pz) to that Plane point.
This will give me the vector of a (test) vector. Now I get the size of that vector using the length = sqrt(xx+yy+z*z); I HAVE to take the sqrt, because the next section is to take the unit vector of that vector (aka, vector/length) and times it by cos(theta) Theta being the angle formed between the 2 vectors, the new found one, and the planes normal. This is a very simple method, works for ANY plane, even if I dont know the origin distance. But DOES require a sqrt every single check.

YOUR METHOD:
A head of time, I find the point on the plane that is the CLOSEST to the origin. AKA the point that when you draw a line to it from the origin, it forms a perpendicular to the plane. (vector equal but oposit to the normal in direction). Now I draw a line from the origin to the Vertex Im checking for. I find the length(squared) of that line, using the distance equation. Then i find the length(squared) of the other line. Subtract the 2 lines, and I get the squared distance from the plane. Is that right.

9

Well, the way i said it wont work. I must have mis read you in some way. I will go through it again and see if i can get it.

10

Ok what you said dosnt seem to make sense on paper. I worked it out, I made a point p. Then drew a plane. I found the closest point that lies on the plane with respect to the origin. I drew my lines, measured there lenghts. I followed your equation, but it didnt work out. Is something wrong with it? Or am I just not seeing this right?

11

Originally posted by dabeav:
YOUR METHOD:
A head of time, I find the point on the plane that is the CLOSEST to the origin. AKA the point that when you draw a line to it from the origin, it forms a perpendicular to the plane. (vector equal but oposit to the normal in direction). Now I draw a line from the origin to the Vertex Im checking for. I find the length(squared) of that line, using the distance equation. Then i find the length(squared) of the other line. Subtract the 2 lines, and I get the squared distance from the plane. Is that right.

Okay, not quite. This method should be giving you a vector that is perpandicular to the plane AND contains your vertex. You’re actually starting from the vertex and drawing a line straight to the plane and finding the point of intersection there. The point on the plane closest to the origin can be used to get the equation of the plane (the translation part) and maybe the 2 spanning vectors if you need them to find the normal, but that’s all.

All you need is to determine the equation of you plane (including translation). How are you determining the equation of your plane?

You might want to double-check my work though, because I might have made an arithmetic error somewhere…

[This message has been edited by Plato (edited 09-11-2002).]

12

Thanks for your help, but i figured it out.

13

Have you tried both methods to see what the difference in FPS is? It would be really interesting to see…

14

No, I have yet to try that, But i believe my new way, is REALY ALOT faster. The first way took about 6-7 multiplies, 1 sqrt, 8-10 add subtracts, plus a arccos calculation. The NEW way takes about 6 multiplies, 6 add subtracts, and thats it. Removing that sqrt is going to be a HUGE difference. If i remember right sqrt can take upwards of 17-21 Cycles. If i ever get around, to a fps/fps test. I will be sure to post it.

15

I’ll bet the arcos function also takes a good chunk of cycles too - usually sqrt, arcX funcs are done by taylor series expansion to some finite order… I’d imagine it’s at least to O3.

What is your new way btw? Is it what I posted or is it something you’ve come up with?

16

Originally posted by dabeav:
No, I have yet to try that, But i believe my new way, is REALY ALOT faster. The first way took about 6-7 multiplies, 1 sqrt, 8-10 add subtracts, plus a arccos calculation. The NEW way takes about 6 multiplies, 6 add subtracts, and thats it. Removing that sqrt is going to be a HUGE difference. If i remember right sqrt can take upwards of 17-21 Cycles. If i ever get around, to a fps/fps test. I will be sure to post it.

actually, a normal sqrt from the math.h takes with full optimisations and intristics and that more than 60 cycles on the systems we benched it (p3 and athlon)… don’t use it don’t use it don’t use it don’t use it!

and if you don’t intersect with a quartic or quadric or how ever called object (sphere, cylinder and that) you will never need a sqrt… never.

17

More than 60 cycles? Are you using sqrt() or sqrtf()? sqrtf() works on floats and should be much faster. I’ve benched expressions like constant / sqrtf( value from array ) to run in roughly 45 cycles, and the equivalent constant * rsqrtf( value from array ) to run in 16-17 cycles. rsqrtf() is a 1.0f / sqrtf() approximation I have lying around …

18

Through a couple “weeks” of research, I have found a realy nice method to do collision detection. I think it will work well with sphere plane collisions, Ray plane/ ray sphere collision. Along with point line distances, and some other odds and ends. So far i have managed to pull off everything to the point of testing actual to the triangle level collisions without using a SINGLE sqrt. Only when testing for exact triangle collision do 3 sqrts come in. (normalizing 3 internal vectors, to see if we have hit the actual triangle). My method starts off testing sphere to plane, with a bout 6 multiplies, and a hand full of plus minus. Then it tests to the models, point by point, with the wall, down to a single point to triangles check. I think it will be VERY VERY VERY fast, considering, it takes a handfull of multiplies per point, and only at the VERY end is there 3 sqrts per model. I will post some code and functions, once i work the bugs out, and make sure it works the way i want. (I CANT WAITE TO MAKE A GAME WITH REAL COLLISION DETECTION, not this cheap crap of late)