Intersecting Line Against Quadrilateral

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 {
		printf("Triangle ADC, v=%f", v);
		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!
");