Collision Detection (Point-Polygon)

[MacFiend]

I am rendering a simple triangle


my_object.vertices[0].x = 0.0;
my_object.vertices[0].y = 0.0;
my_object.vertices[0].z = 0.0;

my_object.vertices[1].x = 0.0;
my_object.vertices[1].y = 1.0;
my_object.vertices[1].z = -1.0;

my_object.vertices[2].x = 1.0;
my_object.vertices[2].y = 1.0;
my_object.vertices[2].z = -1.0;


and I want to tell if my camera collides with the triangle. So far, I am able to tell if my camera collides with the triangle's plane, using this code


vertex u,v,n,n_normalized;
float n_length,d,solution;
u.x = my_object.vertices[2].x-my_object.vertices[0].x;
u.y = my_object.vertices[2].y-my_object.vertices[0].y;
u.z = my_object.vertices[2].z-my_object.vertices[0].z;
v.x = my_object.vertices[2].x-my_object.vertices[1].x;
v.y = my_object.vertices[2].y-my_object.vertices[1].y;
v.z = my_object.vertices[2].z-my_object.vertices[1].z;

n.x = u.y*v.z - u.z*v.y;
n.y = u.z*v.x - u.x*v.z;
n.z = u.x*v.y - u.y*v.x;

n_length = sqrt(n.x*n.x + n.y*n.y + n.z*n.z);

n_normalized.x = n.x/n_length;
n_normalized.y = n.y/n_length;
n_normalized.z = n.z/n_length;

d = n_normalized.x*my_object.vertices[0].x + n_normalized.y*my_object.vertices[0].y + n_normalized.z*my_object.vertices[0].z;
solution = (n_normalized.x*camera.position.x + n_normalized.y*camera.position.y + n_normalized.z*camera.position.z)-d;


If anyone understands what I am doing (I hope someone does), if solution is zero (or near zero), then the camera has collided with the plane on which my_object (the triangle) lies. Although this is a step forward, now I need to figure out of the camera actually collides with the polygon itself, and not just the plane on which it lies. Anyone have any clues as to what step I should take next? Thanks in advance.

[OneSadCookie]

You could use the planes through the pairs of vertices of the triangle that are perpendicular to the triangle's plane, and check if the camera is in front of each of those planes to check whether it's within the triangle...

There may be better methods, of course, that's just off the top of my head. I'd try Google :p

[MacFiend]

Seems like it would work. Thanks.

[DoG]

take the vectors between the 3 vertices, V12, V13, V23, and the point and the vertices V1P, V2P, V3P

The point on the plane of the triangle is in the triangle
if V12.V13 > V12.V1P and V12.V1P > 0
and if -V23.V12 > V23.V2P and V23.V2P > 0
and if -V23.V13 > -V13.V2P and -V13.V2P > 0

This should be largely correct, the concept is that the angle of any pair of the edge vectors should be larger than the angle between one of the edge vectors and the vector to the point which originates from the common point of the edge pair in question.

[MacFiend]

i'm not sure if i understand you completely DoooG, but then again, i don't necessarily understand vector math all that well :D.


take the vectors between the 3 vertices, V12, V13, V23, and the point and the vertices V1P, V2P, V3P


how would i get the vectors between the 3 vertices V12, V13, V23?

when you say the point, you are talking about the camera position, correct?

and the vertices V1P, V2P, V3P are the vertices of the triangle, right? ie: my_object.vertices[] (from my code above)

Thanks btw, I feel I am getting really close to finally getting past this.

[inio]

// the following is based on code from http://www.ce.chalmers.se/staff/tomasm/raytri/
// by Tomas Moller, May 2000
// modified by Ian Rickard, July 2002
static bool intersect_triangle(const Point3f &orig, const Point3f &dir,
const Point3f &vert0, const Point3f &vert1, const Point3f &vert2,
bool backface = true, float *t=NULL) {
Point3f edge1, edge2, tvec, pvec, qvec;
float det , inv_det;

// find vectors for two edges sharing vert0
edge1 = vert1 -vert0;
edge2 = vert2 -vert0;

// begin calculating determinant - also used to calculate U parameter
pvec.MakeCross(dir, edge2);

// if determinant is near zero, ray lies in plane of triangle
det = edge1.Dot(pvec);

if (det > 0) { // IFR: don't care about the coplanar case
if (t)
inv_det = 1.0 / det;

// calculate distance from vert0 to ray origin
tvec = orig - vert0;

// calculate U parameter and test bounds
float u = tvec.Dot(pvec);

if (u < 0.0 || u > det)
return false;

// prepare to test V parameter
qvec.MakeCross(tvec, edge1);

// calculate V parameter and test bounds
float v = dir.Dot(qvec);

if (v < 0.0 || u + v > det)
return false;

} else {
if (!backface) return false;

if (t)
inv_det = 1.0 / det;

tvec = orig - vert0;

float u = tvec.Dot(pvec);

if (u > 0.0 || u < det)
return false;

qvec.MakeCross(tvec, edge1);

float v = dir.Dot(qvec);

if (v > 0.0 || u + v < det)
return false;
}

if(t)
*t = edge2.Dot(qvec) * inv_det;

return true;
}

[DoG]

Originally posted by MacFiend
i'm not sure if i understand you completely DoooG, but then again, i don't necessarily understand vector math all that well :D.



how would i get the vectors between the 3 vertices V12, V13, V23?

when you say the point, you are talking about the camera position, correct?

and the vertices V1P, V2P, V3P are the vertices of the triangle, right? ie: my_object.vertices[] (from my code above)

Thanks btw, I feel I am getting really close to finally getting past this.

You can get the vectors between the vertices, assuming they are numbered 1, 2, 3, by taking their coordinates and substracting them, so V12 = V2 - V1, and so on.

P is the camera's position mapped to the triangle and V1P = P - V1, etc.

You can project any point P0 to a plane if you know its normal, N, and a point on the plane, V. Simply project V-P0 onto N, and you get the vector pointing to the closest point on the plane. The procedure in my prev. post comes after this. You should check also that proj(V - P0, N).N is positive, in which case P0 is behind the triangle.

[MacFiend]

You can project any point P0 to a plane if you know its normal, N, and a point on the plane, V. Simply project V-P0 onto N, and you get the vector pointing to the closest point on the plane. The procedure in my prev. post comes after this. You should check also that proj(V - P0, N).N is positive, in which case P0 is behind the triangle


OK, DoooG, so should I be using the code I used in my first post in conjunction with the math in your 1st and 2nd post, or is the math in the quote above supposed to replace my code?

I initially tried your method in your 1st post along with my original code, and it doesn't appear to work. Here is what I am trying...


...code from my first post...

if(solution<0.18)
{
vertex v12, v13, v23;
vertex v1p, v2p, v3p;

v12.x = my_object.vertices[1].x-my_object.vertices[0].x;
v12.y = my_object.vertices[1].y-my_object.vertices[0].y;
v12.z = my_object.vertices[1].z-my_object.vertices[0].z;

v13.x = my_object.vertices[2].x-my_object.vertices[0].x;
v13.y = my_object.vertices[2].y-my_object.vertices[0].y;
v13.z = my_object.vertices[2].z-my_object.vertices[0].z;

v23.x = my_object.vertices[2].x-my_object.vertices[1].x;
v23.y = my_object.vertices[2].y-my_object.vertices[1].y;
v23.z = my_object.vertices[2].z-my_object.vertices[1].z;

v1p.x = camera.position.x-my_object.vertices[0].x;
v1p.y = camera.position.y-my_object.vertices[0].y;
v1p.z = camera.position.z-my_object.vertices[0].z;

v2p.x = camera.position.x-my_object.vertices[1].x;
v2p.y = camera.position.y-my_object.vertices[1].y;
v2p.z = camera.position.z-my_object.vertices[1].z;

v3p.x = camera.position.x-my_object.vertices[2].x;
v3p.y = camera.position.y-my_object.vertices[2].y;
v3p.z = camera.position.z-my_object.vertices[2].z;

float dot_v12_v13, dot_v12_v1p, dot_v23_v12, dot_v23_v2p, dot_v23_v13, dot_v13_v2p;

dot_v12_v13 = (v12.x*v13.x) + (v12.y*v13.y) + (v12.z*v13.z);
dot_v12_v1p = (v12.x*v1p.x) + (v12.y*v1p.y) + (v12.z*v1p.z);
dot_v23_v12 = (v23.x*v12.x) + (v23.y*v12.y) + (v23.z*v12.z);
dot_v23_v2p = (v23.x*v2p.x) + (v23.y*v2p.y) + (v23.z*v2p.z);
dot_v23_v13 = (v23.x*v13.x) + (v23.y*v13.y) + (v23.z*v13.z);
dot_v13_v2p = (v13.x*v2p.x) + (v13.y*v2p.y) + (v13.z*v2p.z);

if(dot_v12_v13>dot_v12_v1p && dot_v12_v1p>0 && -dot_v23_v12>dot_v23_v2p && dot_v23_v2p>0 &&
-dot_v23_v13>-dot_v13_v2p && -dot_v13_v2p>0)
{
NSLog(@"Collision!");
}
}


Oh yea, I'm assuming when you use "V12.V1P", the "." is supposed to represent Dot-Product, right?

It doesn't work possibly because dot_v12_v1p is negative for some reason, but then again, I probably just have something mixed up. Does your method take into account approximations? The way I am doing this doesn't actually place the camera position exactly on the plane of the triangle, just really close to it. Any ideas?

Inio, I am going to try your example once I make sense of all of it :wow: .

OneSadCookie:


You could use the planes through the pairs of vertices of the triangle that are perpendicular to the triangle's plane, and check if the camera is in front of each of those planes to check whether it's within the triangle...


Would I use cross-products to find triangles perpendicular to the plane? Sorry I keep asking all these questions, I failed Math 3 :p .

Thanks everyone.

[inio]

Originally posted by MacFiend
Inio, I am going to try your example once I make sense of all of it :wow: .

Here's the source for Point3f:

struct Point3f {
GLfloat x,y,z;

void set(Float ix, Float iy, Float iz){x=ix;y=iy;z=iz;}
Point3f(){}
Point3f(Float ix, Float iy, Float iz){set(ix,iy,iz);}
Point3f(const Point3f &v){*this = v;}
Point3f operator +(const Point3f &t) const {return Point3f(x+t.x, y+t.y, z+t.z);}
Point3f operator -(const Point3f &t) const {return Point3f(x-t.x, y-t.y, z-t.z);}
Point3f operator +=(const Point3f &t) {return Point3f(x+=t.x, y+=t.y, z+=t.z);}
Point3f operator -=(const Point3f &t) {return Point3f(x-=t.x, y-=t.y, z-=t.z);}
Point3f operator* (Float t) const {return Point3f(x*t, y*t, z*t);}
Point3f operator*= (Float t) {return Point3f(x*=t, y*=t, z*=t);}
Float Dot(const Point3f &t) const {float result = x*t.x+y*t.y+z*t.z; return result;}
void MakeCross(const Point3f &a, const Point3f &b) {x = a.y*b.z-a.z*b.y; y = a.z*b.x-a.x*b.z; z = a.x*b.y-a.y*b.x;}
void Normalize() {float inv = FastSqrtRecip(x*x+y*y+z*z); x*=inv; y*=inv; z*=inv;}
operator GLfloat*() {return &x;}
operator const GLfloat*() const {return &x;}
Float Length() const {return FastSqrt(x*x+y*y+z*z);}
Float Length2() const {return x*x+y*y+z*z;}
Point3f ProjectOntoNorm(const Point3f &onto) {return onto*Dot(onto);}
Point3f ProjectOnto(const Point3f &onto) {return (onto*Dot(onto))*(__fres(onto.Length2()));}
Float& operator[](int index) {return (&x)[index];}
};
inline Float Length(const Point3f &i) {return FastSqrt(i.x*i.x+i.y*i.y+i.z*i.z);}


That should help you understand what it's doing. Also backface is to turn off collision checks against backface (points rotate clockwise around ray).

In general, how you would use this is set the start point to the position of the location of the camera in the previous frame, and the direction to the difference between the previous and current frame. If the value returned in t is in 0..1 (and the function returned true) then the movement of the camera passed through the triangle.

oh, and you probably want to take the "static" off the function, I forgot to delete that. (the codes as pasted is used as part of a larger mangle of bsp collision code, so static is appropriate.)

[DoG]

Well, I am not quite sure with the signs, but if you note, I did put some negative signs in my previous equations.

The pseudocode should be something like this:

if distance from point to plane < min_distance
if the point projected on the plane lies inside the triangle (by the dot product tests)
return true
else return false

I have just noticed I have not implemented this piece of code before, I will do it and test it to make sure, but I am sure the algorithm works, even if I made some sign mistakes.

Another thing is that it does matter which way the normal points. If it points the wrong way, eg. to the back of the tri, the test will obviously not work. And it should work even with an approximate projection to the triangle plane.

[inio]

Originally posted by DoooG
if distance from point to plane < min_distance
if the point projected on the plane lies inside the triangle (by the dot product tests)
return true
else return false
Two problems with that:
1. what if the camera moves more then 2*min_distance units in a single frame?
2. what about convex seams?

[DoG]

Originally posted by inio
Two problems with that:
1. what if the camera moves more then 2*min_distance units in a single frame?
2. what about convex seams?

Convex seams? A triangle? I am lost :blink:

You have to consider the camera's position in the previous frame, draw a line segment to the current pos, find the intersection. If there is any, the camera collided, if there is none, it didn't. Additionally, you can test the end position, too.

[MacFiend]

Do you think you could possibly post an example using this method? I've tried several variations to it, but it doesn't seem to work properly. I can get it to sort of recognize a collision, but it's still not correct.

[inio]

Originally posted by DoooG
Convex seams? A triangle? I am lost :blink:
You aren't testing against a single triangle, you're testing against a mesh of triangles. where two triangles meet is called a seam. each seam can be classified as convex, concave, or planar depending on whether the triangles face away from each other, towards each other, or are coplanar. Your method works OK for situations where they're coplanar or face towards each other, but if the triangles face away from each other there's a sliver between the two triangles where you can get stuck.

[DoG]

Originally posted by inio
You aren't testing against a single triangle, you're testing against a mesh of triangles. where two triangles meet is called a seam. each seam can be classified as convex, concave, or planar depending on whether the triangles face away from each other, towards each other, or are coplanar. Your method works OK for situations where they're coplanar or face towards each other, but if the triangles face away from each other there's a sliver between the two triangles where you can get stuck.

The method works for a single triangle, yes, that was asked, ircc. For a mesh, you obviously have to make some more assumptions, for example that the mesh is regular (a single surface). With a regular mesh, and allowing collisions with multiple triangles at the same time, things should work out just fine, since the proposed algorithm correctly determines collision with each individual triangle. Right? (i think)

[MacFiend]

inio, i just tried implementing your example, and i have a few questions about it. what is BACKFACE for? what is T for?

anyway, what i tried still doesn't work :wacko: . here is the code i am using:


-(BOOL)intersectTriangleOrigin:(vertex)orig Direction:(vertex)dir V0:(vertex)vert0 V1:(vertex)vert1 V2:(vertex)vert2 Backface:(BOOL)backface T:(float)t
{
vertex edge1, edge2, tvec, pvec, qvec;
float det, inv_det;

edge1.x = vert1.x-vert0.x;
edge1.y = vert1.y-vert0.y;
edge1.z = vert1.z-vert0.z;

edge2.x = vert2.x-vert0.x;
edge2.y = vert2.y-vert0.y;
edge2.z = vert2.z-vert0.z;


pvec.x = dir.y*edge2.z - dir.z*edge2.y;
pvec.y = dir.z*edge2.x - dir.x*edge2.z;
pvec.z = dir.x*edge2.y - dir.y*edge2.x;

det = edge1.x*pvec.x + edge1.y*pvec.y + edge1.z*pvec.z;

if(det>0)
{
if(t)
inv_det = 1.0/det;

tvec.x = orig.x-vert0.x;
tvec.y = orig.y-vert0.y;
tvec.z = orig.z-vert0.z;

float u = tvec.x*pvec.x + tvec.y*pvec.y + tvec.z*pvec.z;

if(u<0.0 || u>det)
return FALSE;

qvec.x = tvec.y*edge1.z - tvec.z*edge1.y;
qvec.y = tvec.z*edge1.x - tvec.x*edge1.z;
qvec.z = tvec.x*edge1.y - tvec.y*edge1.x;

float v = dir.x*qvec.x + dir.y*qvec.y + dir.z*qvec.z;

if(v<0.0 || u+v>det)
return FALSE;
}
else
{
if(!backface)
return FALSE;

if(t)
inv_det = 1.0/det;

tvec.x = orig.x-vert0.x;
tvec.y = orig.y-vert0.y;
tvec.z = orig.z-vert0.z;

float u = tvec.x*pvec.x + tvec.y*pvec.y + tvec.z*pvec.z;

if(u<0.0 || u>det)
return FALSE;

qvec.x = tvec.y*edge1.z - tvec.z*edge1.y;
qvec.y = tvec.z*edge1.x - tvec.x*edge1.z;
qvec.z = tvec.x*edge1.y - tvec.y*edge1.x;

float v = dir.x*qvec.x + dir.y*qvec.y + dir.z*qvec.z;

if(v<0.0 || u+v>det)
return FALSE;
}

//if(t)
//t = (edge2.x*qvec.x + edge2.y*qvec.y + edge2.z*qvec.z) * inv_det;

return TRUE;
}


and i am testing for collisions using:


if([self intersectTriangleOrigin:camera.position Direction:camera.orientation V0:my_object.vertices[0] V1:my_object.vertices[1] V2:my_object.vertices[2] Backface:FALSE T:0.0])
{
//COLLISION OCCURRED
}


is there something i am missing? thanks.

[inio]

Originally posted by MacFiend
inio, i just tried implementing your example, and i have a few questions about it. what is BACKFACE for? what is T for?backface: if true, intersectiosn from both directions are found. If false, insersections from the side where the triangle appears to be in clickwise order are found. Useful if you want to short circuit out of some calculations and you have a reliable polygon direction.
t: the number of times that you must move dir from the start point to reach the intersection.

[MacFiend]

OneSadCookie, i think i am going to try your idea of using perpendicular planes to tell if the point is within the triangle. Would you be able to tell me how I would find the plane perpendicular to the triangle-plane using the edges of the triangle?

Also, i think the reason none of the other examples are working for me is that the camera position and the triangle are no coplanar. I have no way (as of now), to make the positions coplanar.

[DoG]

Originally posted by MacFiend
OneSadCookie, i think i am going to try your idea of using perpendicular planes to tell if the point is within the triangle. Would you be able to tell me how I would find the plane perpendicular to the triangle-plane using the edges of the triangle?

Also, i think the reason none of the other examples are working for me is that the camera position and the triangle are no coplanar. I have no way (as of now), to make the positions coplanar.

You can easily make the point on the triangle plane closest to the point you want by projecting the distance vector from the point to any of the triangle's vertices to the triangle's normal, then subtracting this vector from the original point's position. But this has been said before, somewhere.

[MacFiend]

Ahh okay. I'll try that then.

[codemattic]

Originally posted by DoooG
The method works for a single triangle, yes, that was asked, ircc. For a mesh, you obviously have to make some more assumptions, for example that the mesh is regular (a single surface). With a regular mesh, and allowing collisions with multiple triangles at the same time, things should work out just fine, since the proposed algorithm correctly determines collision with each individual triangle. Right? (i think)

Technically yes. But in actuality almost always no. Almost always you dont want to collide a point - but a sphere or cylinder or something. In the case of a camera - the camera isnt a point - it has a near clipping plane. So by the time the camera "point" hits the triangle - the triangle has already been clipped by the near plane. So what you almost always want is to collide a sphere with a triangle. And with that - the nearest point from the center to the triangle's plane may well be outside the triangle - while still parts of the sphere (and clipping plane) my knock in to the edge of the triangle.

Still - getting the code working for the point/triangle is a very good start - so dont give up!

[MacFiend]

Yea i understand that all of this would still require a lot more work to get a full collision detection engine going, i just like playing around with small things like this as to provide a basis for the meat. :D

[David]

In Lugaru I use line/poly collision to find the approximate location of the camera and then use sphere/poly on the nearest few to fix the near clipping plane, seems to work best like that.

If this helps at all my line-triangle functions are

bool LineFacet(XYZ p1,XYZ p2,XYZ pa,XYZ pb,XYZ pc,XYZ *p)
{
static float d;
static float a1,a2,a3;
static float total,denom,mu;
static XYZ n,pa1,pa2,pa3;

//Calculate the parameters for the plane
n.x = (pb.y - pa.y)*(pc.z - pa.z) - (pb.z - pa.z)*(pc.y - pa.y);
n.y = (pb.z - pa.z)*(pc.x - pa.x) - (pb.x - pa.x)*(pc.z - pa.z);
n.z = (pb.x - pa.x)*(pc.y - pa.y) - (pb.y - pa.y)*(pc.x - pa.x);
Normalise(&n);
d = - n.x * pa.x - n.y * pa.y - n.z * pa.z;

//Calculate the position on the line that intersects the plane
denom = n.x * (p2.x - p1.x) + n.y * (p2.y - p1.y) + n.z * (p2.z - p1.z);
if (abs(denom) < 0.0000001) // Line and plane don't intersect
return 0;
mu = - (d + n.x * p1.x + n.y * p1.y + n.z * p1.z) / denom;
p->x = p1.x + mu * (p2.x - p1.x);
p->y = p1.y + mu * (p2.y - p1.y);
p->z = p1.z + mu * (p2.z - p1.z);
if (mu < 0 || mu > 1) // Intersection not along line segment
return 0;

if(!PointInTriangle( p, n, &pa, &pb, &pc)){return 0;}

return 1;
}

bool PointInTriangle(XYZ *p, XYZ normal, XYZ *p1, XYZ *p2, XYZ *p3)
{
static float u0, u1, u2;
static float v0, v1, v2;
static float a, b;
static float max;
static int i, j;
static bool bInter = 0;
static float pointv[3];
static float p1v[3];
static float p2v[3];
static float p3v[3];
static float normalv[3];

bInter=0;

pointv[0]=p->x;
pointv[1]=p->y;
pointv[2]=p->z;


p1v[0]=p1->x;
p1v[1]=p1->y;
p1v[2]=p1->z;

p2v[0]=p2->x;
p2v[1]=p2->y;
p2v[2]=p2->z;

p3v[0]=p3->x;
p3v[1]=p3->y;
p3v[2]=p3->z;

normalv[0]=normal.x;
normalv[1]=normal.y;
normalv[2]=normal.z;

#define ABS(X) (((X)<0.f)?-(X):(X) )
#define MAX(A, B) (((A)<(B))?(B):(A))
max = MAX(MAX(ABS(normalv[0]), ABS(normalv[1])), ABS(normalv[2]));
#undef MAX
if (max == ABS(normalv[0])) {i = 1; j = 2;} // y, z
if (max == ABS(normalv[1])) {i = 0; j = 2;} // x, z
if (max == ABS(normalv[2])) {i = 0; j = 1;} // x, y
#undef ABS

u0 = pointv[i] - p1v[i];
v0 = pointv[j] - p1v[j];
u1 = p2v[i] - p1v[i];
v1 = p2v[j] - p1v[j];
u2 = p3v[i] - p1v[i];
v2 = p3v[j] - p1v[j];

if (u1 > -1.0e-05f && u1 < 1.0e-05f)// == 0.0f)
{
b = u0 / u2;
if (0.0f <= b && b <= 1.0f)
{
a = (v0 - b * v2) / v1;
if ((a >= 0.0f) && (( a + b ) <= 1.0f))
bInter = 1;
}
}
else
{
b = (v0 * u1 - u0 * v1) / (v2 * u1 - u2 * v1);
if (0.0f <= b && b <= 1.0f)
{
a = (u0 - b * u2) / u1;
if ((a >= 0.0f) && (( a + b ) <= 1.0f ))
bInter = 1;
}
}

return bInter;
}

void Normalise(XYZ *vectory) {
static float d;
d = fast_sqrt(vectory->x*vectory->x+vectory->y*vectory->y+vectory->z*vectory->z);
if(d==0){return;}
vectory->x /= d;
vectory->y /= d;
vectory->z /= d;
}

float fast_sqrt (register float arg)
{
// Can replace with slower return std::sqrt(arg);
register float result;

if (arg == 0.0) return 0.0;

asm {
frsqrte result,arg // Calculate Square root
}

// Newton Rhapson iterations.
result = result + 0.5 * result * (1.0 - arg * result * result);
result = result + 0.5 * result * (1.0 - arg * result * result);

return result * arg;
}


Hope this helps.

BTW if anyone finds anything that could be sped up here it would be great, since I have to do a ton of these every frame.

[OneSadCookie]

Originally posted by David

void Normalise(XYZ *vectory) {
static float d;
d = fast_sqrt(vectory->x*vectory->x+vectory->y*vectory->y+vectory->z*vectory->z);
if(d==0){return;}
vectory->x /= d;
vectory->y /= d;
vectory->z /= d;
}

BTW if anyone finds anything that could be sped up here it would be great, since I have to do a ton of these every frame.

OK, I'm just going to pick on this one function. You'll want to move this function to the top of the file (just below fast_sqrt, which should be first and inlined).

inline void Normalise(XYZ *vectory) {
float x = vectory->x;
float y = vectory->y;
float z = vectory->z;
float d = 1.0f / fast_sqrt((x*x) + (y*y) + (z*z));
vectory->x = x * d;
vectory->y = y * d;
vectory->z = z * d;
}

I'm sure you can get similar improvements in other places.

[inio]

Originally posted by David
BTW if anyone finds anything that could be sped up here it would be great, since I have to do a ton of these every frame.
Arrays are inherently slower than regular local variables. Also, on PowerPC there's a fast way to do sqrt:// calculate sqrt(x) with pretty good accuacy
// x is double to prevent frsp generation before call
// return type is float to prevent generation after call
inline float FastSqrt(register double x) {
register float inv;
register float oneHalf = 0.5;
asm {
frsqrte inv,x; // inv = 1/sqrt(x) // inv = 1/sqrt(x)
fmuls x,x,inv; // f*inv
fres inv,inv; // 1/inv
fadds x,x,inv; // 1/inv+f*inv
fmuls x,x,oneHalf; // .5*(1/inv+f*inv)
}
return x;
}
which provides about 3 digits of precision. For inverse square root, the even faster:// calculate 1/sqrt(x) with pretty good accuacy
// x is double to prevent frsp generation before call
// return type is float to prevent generation after call
inline float FastSqrtRecip(register double x) {
register float inv;
register float oneHalf = 0.5;
asm {
frsqrte inv,x; // inv = 1/sqrt(x)
fmuls x,x,inv; // f*inv
fres x,x; // 1/(f*inv)
fadds x,x,inv; // 1/(f*inv)+inv
fmuls x,x,oneHalf; // .5*(1/(f*inv)+inv)
}
return x;
} It seems you're doing a slightly less efficient implementation of the same thing.

[inio]

Originally posted by OneSadCookie
...
float d = 1.0f / fast_sqrt((x*x) + (y*y) + (z*z));
...
That's a prime candidate for fmadds. Wonder if CW/gcc will generate it there. more likely sequence might be:x *= x;
y = y * y + x;
z = z * z + y;
float d = FastSqrtRecip(z);

[OneSadCookie]

... except you can't reassign to the locals because you need them later to avoid an extra load. Still, using an extra register won't be a big deal:

float norm = x * x;
norm += y * y;
norm += z * z;
float d = FastSqrtRecip(norm);

In my experience, though, GCC (at least) is pretty good at generating fmadds instructions, so it's probably unnecessary. Disassemble before trying :)

[MacFiend]

David, i'm trying your example. I found (i think, at least) where you got that from, so i tried implementing that. Here is what i'm basing this on: http://astronomy.swin.edu.au/~pbourke/geometry/linefacet/
Here is the code im using:


-(void)testForCollision
{
vertex intersection;

if([self LineFacetSegmentA:camera.position SegmentB:[self moveVertex:camera.position Direction:camera.orientation Amount:CAMERA_MOVE_SPEED] TriangleA:my_object.vertices[0] TriangleB:my_object.vertices[1] TriangleC:my_object.vertices[2] IntersectionResult:&intersection]==TRUE)
{
//COLLISION
}
}
-(BOOL)LineFacetSegmentA:(vertex)p1 SegmentB:(vertex)p2 TriangleA:(vertex)pa TriangleB:(vertex)pb TriangleC:(vertex)pc IntersectionResult:(vertex*)p
{
float d;
float a1,a2,a3;
float total,denom,mu;
vertex n,pa1,pa2,pa3,p;

n.x = (pb.y - pa.y)*(pc.z - pa.z) - (pb.z - pa.z)*(pc.y - pa.y);
n.y = (pb.z - pa.z)*(pc.x - pa.x) - (pb.x - pa.x)*(pc.z - pa.z);
n.z = (pb.x - pa.x)*(pc.y - pa.y) - (pb.y - pa.y)*(pc.x - pa.x);
n = [self NormalizeVertex:n];

d = -n.x*pa.x - n.y*pa.y - n.z*pa.z;

denom = n.x *(p2.x-p1.x) + n.y*(p2.y-p1.y) + n.z*(p2.z-p1.z);

if(fabsf(denom)<0.0000001)
return FALSE;

mu = -(d + n.x*p1.x + n.y*p1.y + n.z*p1.z)/denom;
p.x = p1.x + mu*(p2.x-p1.x);
p.y = p1.y + mu*(p2.y-p1.y);
p.z = p1.z + mu*(p2.z-p1.z);

if(mu<0 || mu>1)
return FALSE;

pa1.x = pa.x - p->x;
pa1.y = pa.y - p->y;
pa1.z = pa.z - p->z;
pa1 = [self NormalizeVertex:pa1];
pa2.x = pb.x - p->x;
pa2.y = pb.y - p->y;
pa2.z = pb.z - p->z;
pa2 = [self NormalizeVertex:pa2];
pa3.x = pc.x - p->x;
pa3.y = pc.y - p->y;
pa3.z = pc.z - p->z;
pa3 = [self NormalizeVertex:pa3];

a1 = pa1.x*pa2.x + pa1.y*pa2.y + pa1.z*pa2.z;
a2 = pa2.x*pa3.x + pa2.y*pa3.y + pa2.z*pa3.z;
a3 = pa3.x*pa1.x + pa3.y*pa1.y + pa3.z*pa1.z;

total = (acos(a1) + acos(a2) + acos(a3)) * 57.2957795;

if(fabsf(total-360)>0.0000001)
return FALSE;

return TRUE;
}

-(vertex)NormalizeVertex:(vertex)p
{
vertex newV;
float length=sqrt(p.x*p.x + p.y*p.y + p.z*p.z);
newV.x = p.x/length;
newV.y = p.y/length;
newV.z = p.z/length;

return newV;
}

-(vertex)moveVertex:(vertex)vert Direction:(vertex)dir Amount:(float)byAmount
{
double yRot,xMov,yMov,zMov,newX,newY,newZ;
double PI=3.14;
vertex newVert;

yRot = dir.y;
yRot = yRot*(PI/180);
xMov = byAmount*sin(yRot);
yMov = 0.0;
zMov = byAmount*cos(yRot);
newX = vert.x+xMov;
newY = vert.y;
newZ = vert.z+zMov;
newVert.x = newX;
newVert.y = newY;
newVert.z = newZ;

return newVert;
}


Now its not working because fabsf(total-360) (near the end of the LineFacet... function) is always some number like 300+. Even when the camera is directly in front of the triangle i want to collide with.

It shouldn't matter if camera.position is coplanar with the triangle plane, just as long as camera.position and its next position intersects the triangle plane, correct?

I was hoping someone could possibly explain to me why fabsf(total-360) is never less than epsilon (0.0000001). I'd really appreciate it, this is frustrating as h***. Thanks for all your help.

btw, the vertices for my triangle are as follows:

my_object.vertices[0].x = 0.0;
my_object.vertices[0].y = 0.0;
my_object.vertices[0].z = 0.0;

my_object.vertices[1].x = 0.0;
my_object.vertices[1].y = 1.0;
my_object.vertices[1].z = -1.0;

my_object.vertices[2].x = 1.0;
my_object.vertices[2].y = 1.0;
my_object.vertices[2].z = -1.0;

[David]

I know nothing about optimizing, so:

What is fmadds?
Is it slower to have a static float and use it every time the function is called or make a local float?
What does inlining a function do?

[MacFiend]

David, do you think you could give me some values that you would input into your function parameters that would cause it to return true?

[inio]

Originally posted by David
What is fmadds?A PowerPC instruction that multiplies two floating point numbers and adds a third. It's faster than doing a fmuls (multiply) and fadds (add) separately

Is it slower to have a static float and use it every time the function is called or make a local float?In theory a good compiler would do whatever is fastest in both cases. If you are going to use a local, make sure it's const (though a good compiler with auto-const it).

What does inlining a function do? There's non-trivial overhead involved in any function call. Inlining avoids this by "inlining" the code of the function into the caller. It also allows the compiler to make optimizations in the called function specific to the call being replaced (such as replacing variables with constants).

[OneSadCookie]

Originally posted by inio
In theory a good compiler would do whatever is fastest in both cases. If you are going to use a local, make sure it's const (though a good compiler with auto-const it).

In practice, a static variable will (almost?) always be slower, since the compiler will feel compelled to write to memory whatever value the variable has at the end of the function, where the value of a local can just be discarded. Yes, in theory a good compiler could tell whether writing to memory was necessary or not, but since there's an explicit language flag 'static' to do that, I'd guess it's not a common optimization for compilers to perform. GCC certainly generates more code for the static case than the non-static.

[inio]

Originally posted by OneSadCookie
In practice, a static variable will (almost?) always be slower, since the compiler will feel compelled to write to memory whatever value the variable has at the end of the function, where the value of a local can just be discarded. Yes, in theory a good compiler could tell whether writing to memory was necessary or not, but since there's an explicit language flag 'static' to do that, I'd guess it's not a common optimization for compilers to perform. GCC certainly generates more code for the static case than the non-static.

Oops, I misread static as const. And I didn't read his question closely enough

I thought the question was:
const float foo=2.73;
int Thinger(float blah) {
return foo+blah;
}vs.int Thingier(float blah) {
float foo=2.73;
return foo+blah;
}if you use foo multiple times in a function, these will be faster than inlining the value in each statement. However, these should generate equivelant code as all FP constants have to be stored as const globals (vs. small integer constants, which can be stored in the instruction stream).