I have been struggling with this collision detection for a while now. I have a terrain map, drawn with clockwise triangle strips. Using a formula from the book “Real Time Collision Detection” I am trying to find the height of a triangle at the current position. This is to determine the cameras height above the terrain.

I can calculate my exact position in a particular terrain chunk and retrieve the correct coordinates for the current quad but the method always returns garbage, or returns 0 for failure.

My program is fairly large so I cannot post it all, but here is the collision test function:

``````
int LineQuad(Point p, Point q, Point a, Point b, Point c, Point d, float &r) {
Point pq, pa, pb, pc;

pq.x = q.x - p.x;
pq.y = q.y - p.y;
pq.z = q.z - p.z;

pa.x = a.x - p.x;
pa.y = a.y - p.y;
pa.z = a.z - p.z;

pb.x = b.x - p.x;
pb.y = b.y - p.y;
pb.z = b.z - p.z;

pc.x = c.x - p.x;
pc.y = c.y - p.y;
pc.z = c.z - p.z;

Point m = Cross(pc, pq);
float v = Dot(pa, m);
if (v >= 0.0f) {
printf("Triangle ABC, v=%f", v);
float u = -Dot(pb, m);
printf(", u=%f
", u);
if (u < 0.0f) { printf("Calculation Error: u=%f
", u); return 0; }
float w = -ScalarTriple(pq, pb, pa);
printf(", w=%f
", w);
if (w <= 0.0f) { printf("Calculation Error: w=%f
", w); return 0; }

float denom = 1.0f / (u + v + w);
u *= denom;
v *= denom;
w *= denom;
r = (u*a.x+u*a.y+u*a.z)+(v*b.x+v*b.y+v*b.z)+(w*c.x+w*c.y+w*c.z);
} else {
Point pd;
pd.x = d.x - p.x;
pd.y = d.y - p.y;
pd.z = d.z - p.z;

float u = Dot(pd, m);
printf(", u=%f", u);
if (u < 0.0f) { printf("Calculation Error: u=%f
", u); return 0; }
float w = -ScalarTriple(pq, pa, pd);
printf(", w=%f
", w);
if (w <= 0.0f) { printf("Calculation Error: w=%f
", w); return 0; }
v = -v;

float denom = 1.0f / (u + v + w);
u *= denom;
v *= denom;
w *= denom;
r = (u*a.x+u*a.y+u*a.z)+(v*d.x+v*d.y+v*d.z)+(w*c.x+w*c.y+w*c.z);
}
return 1;
}

``````

Point p is the current camera position.

``````
p.x=xPos2;
p.y=gameVars.transform.yPos;
p.z=zPos2;

``````

Point q is a vector pointing down from the camera:

``````
q.x=xPos2;
q.y=-1;
q.z=zPos2;

``````

Here is the output that I get from one of the quads, in the format x, y, z where y is the height value. Quad ABCD starts in the top-right corner:

``````
a: (-10, 16, 0)
b: (-10, 16, -10)
c: (0, 16, -10)
d: (0, 16, 0)

Triangle ABC, v=1970.000000, u=-950.000000
Calculation Error, u=-950
r:0.000000

``````

Any help would be greatly appreciated, I have been trying to figure out collision detection for a long time now.

Let me ask a somewhat simpler question. Lets say I have clockwise quad ABCD where AC is the shared line of two triangles, and line PQ intersecting the quad. How would I calculate which triangle that line is intersecting?

I understand that only line AC needs to be tested for which side PQ is on to determine which triangle it resides in. Can a Scalar Triple Product be used to determine this?

I have solved this problem for anyone that cares. What I did was strip down the components of different functions to get what I needed. I did not need to calculate IF a collision occurred as I was simply trying to detect height above a changing surface.

So first, I did a Cross and Dot product on the shared triangle line of a quad to determine which side of the half space I was in.

I then used a modification of a ray-triangle intersection test to calculate the barycentric coordinates and return the point on the ray where the intersection occurred which translates into the height.

Here are the functions used:

``````
struct Point {
float x, y, z;
};

Point Cross(Point u, Point v) {
Point i;
i.x=  (u.y * v.z) - (u.z * v.y);
i.y=-((u.x * v.z) - (u.z * v.x));
i.z=  (u.x * v.y) - (u.y * v.x);
return i;
}

float Dot(Point a, Point b) {
float i = (a.x*b.x)+(a.y*b.y)+(a.z*b.z);
return i;
}

float halfSpace(Point p, Point q, Point a, Point c) {
Point pq, pa, pc;

pq.x = q.x - p.x;
pq.y = q.y - p.y;
pq.z = q.z - p.z;

pa.x = a.x - p.x;
pa.y = a.y - p.y;
pa.z = a.z - p.z;

pc.x = c.x - p.x;
pc.y = c.y - p.y;
pc.z = c.z - p.z;

Point m = Cross(pc, pq);
float v = Dot(pa, m);

return v;
}

int IntersectTri(Point p, Point q, Point a, Point b, Point c, float &u, float &v, float &w, float &t) {
Point qp, ab, ac, ap, e;

qp.x = p.x - q.x;
qp.y = p.y - q.y;
qp.z = p.z - q.z;

ab.x = b.x - a.x;
ab.y = b.y - a.y;
ab.z = b.z - a.z;

ac.x = c.x - a.x;
ac.y = c.y - a.y;
ac.z = c.z - a.z;

//Compute Normal
Point n = Cross(ab, ac);

//Compute denominator
float d = Dot(qp, n);
if (d<= 0.0f) return 2;	//Ray is parallel to or points away from triangle

//Compute Ray Intersection
ap.x = p.x - a.x;
ap.y = p.y - a.y;
ap.z = p.z - a.z;

t = Dot(ap, n);
//if (t < 0.0f) return 0
//if (t > d) return 0	//This test for segment only, not ray test

//Compute Barycentric Coordinates, and test bounds
e = Cross(qp, ap);
v = Dot(ac, e);
//if (v < 0.0f || v > d) return 0;
w = -Dot(ab, e);
//if (w < 0.0f || v+w > d) return 0;

//Intersection Valid, compute last coordinate
float ood = 1.0f / d;
t *= ood;
v *= ood;
w *= ood;
u = 1.0f - v - w;
return 1;
}

``````

Calling IntersectTri() modifies the values of u, v, w, and t by reference. t contains the position on the ray in barycentric form:

``````
Point a, b, c, d, q, p;
float u, v, w, t;

a.x=10.0f;
a.y=0.0f;
a.z=0.0f;

b.x=0.0f;
b.y=0.0f;
b.z=0.0f;

c.x=0.0f;
c.y=0.0f;
c.z=10.0f;

d.x=10.0f;
d.y=0.0f;
d.z=10.0f;

p.x=4;
p.y=20;
p.z=4;

q.x=4;
q.y=-20;
q.z=4;

u=0;
v=0;
w=0;
t=0;

v = halfSpace(p, q, a, c);
if (v > 0.0) {
//Inside triangle ABC
triTest=IntersectTri(p, q, a, b, c, u, v, w, t);
}
else {
//Inside triangle ACD
triTest=IntersectTri(p, q, a, c, d, u, v, w, t);
}

if (triTest==0) printf("IntersectTri() FAILED.
");
else if (triTest==2) printf("IntersectTri() computes Parallel/Away.
");
else printf("IntersectTri() Success!
");

``````