# Finding Z given X & Y coordinates on terrain?

I need to know the most efficient way of finding Z given X & Y coordinates on terrain. My terrain is set up as a grid, each grid block consisting of two triangles which may be flipped in any direction. I want to move game objects smoothly along the floor of the terrain without "stepping." I'm currently using the following method with unexpected results:

double mapClass::getZ(double x, double y)
{
int vertexIndex = ((floor(y))*width*2)+((floor(x))*2);

vec3ray ray = {glm::vec3(x, y, 2), glm::vec3(x, y, 0)};

vec3triangle tri1 = {   glmFrom(vertices[vertexIndex].v1),
glmFrom(vertices[vertexIndex].v2),
glmFrom(vertices[vertexIndex].v3)   };

vec3triangle tri2 = {   glmFrom(vertices[vertexIndex+1].v1),
glmFrom(vertices[vertexIndex+1].v2),
glmFrom(vertices[vertexIndex+1].v3) };

glm::vec3 intersect;

if (!intersectRayTriangle(tri1, ray, intersect))
{
intersectRayTriangle(tri2, ray, intersect);
}

return intersect.z;
}


intersectRayTriangle() and glmFrom() are as follows:

bool intersectRayTriangle(vec3triangle tri, vec3ray ray, glm::vec3 &worldIntersect)
{
glm::vec3 barycentricIntersect;

if (glm::intersectLineTriangle(ray.origin, ray.direction, tri.p0, tri.p1, tri.p2, barycentricIntersect))
{
// Convert barycentric to world coordinates
double u, v, w;
u = barycentricIntersect.x;
v = barycentricIntersect.y;
w = 1 - (u+v);

worldIntersect.x = (u * tri.p0.x + v * tri.p1.x + w * tri.p2.x);
worldIntersect.y = (u * tri.p0.y + v * tri.p1.y + w * tri.p2.y);
worldIntersect.z = (u * tri.p0.z + v * tri.p1.z + w * tri.p2.z);
return true;
}
else
{
return false;
}
}

glm::vec3 glmFrom(s_point3f point)
{
return glm::vec3(point.x, point.y, point.z);
}


My convenience structures are defined as:

struct s_point3f { GLfloat x, y, z; };
struct s_triangle3f { s_point3f v1, v2, v3; };
struct vec3ray { glm::vec3 origin, direction; };
struct vec3triangle { glm::vec3 p0, p1, p2; };


vertices is defined as:

std::vector<s_triangle3f> vertices;


Basically, I'm trying to get the intersect of a ray (which is positioned at the x, and y coordinates specified facing pointing downwards toward the terrain) and one of the two triangles on the grid. getZ() rarely returns anything but 0. Other times, the numbers it generates seem to be completely off. Am I taking the wrong approach? Can anyone see a problem with my code? Any help or critique is appreciated!

EDIT: After considering what David Cummins has suggested, I can confirm that the ray and the triangle should always be intersecting. I added some debugging code to visualize the data. The area shaded red contains the two triangles, and the blue line is the line/ray being checked for intersection. Depth has been disabled when drawing the line.

Here is an example of data being passed to glm::intersectLineTriangle():

triangle #1:
v1={x=19.0000000 y=34.0000000 z=2.70000005},
v2={x=19.0000000 y=33.0000000 z=2.70000005},
v3={x=18.0000000 y=33.0000000 z=2.70000005}

triangle #2:
v1={x=18.0000000 y=33.0000000 z=2.70000005},
v2={x=18.0000000 y=34.0000000 z=2.70000005},
v3={x=19.0000000 y=34.0000000 z=2.70000005}

ray origin:
{x=18.5000000 y=33.1871414 z=10.0000000}

ray direction:
{x=18.5000000 y=33.1871414 z=-10.0000000}


Despite passing seemingly reasonable arguments, it always returns false. Leaving barycentricIntersect as {x=0.0 y=0.0 z=0.0}. Am I misusing the function? Are the values I am passing invalid, and I'm just blind to it?

EDIT 2: I've written a quick SSCCE. I would be extremely grateful if someone could help me debug this issue.

• Possibly the ray you define isn't guaranteed to intersect with the triangles (e.g. origin is too high/low), or you are experiencing floating point issues with the edges of the triangles. – David Cummins Nov 12 '13 at 0:13
• Try normalizing your dir vector before passing it in. Functions like this almost always expect a normalized vector, and anything else could cause problems. – Evan Nov 13 '13 at 19:49
• Ray origin and direction have the same coordinates. Shouldn't the z coordinate be negative in direction vector for a ray to point down? – Helbreder Nov 14 '13 at 8:30
• The only thing I can think of are those ray direction coordinates. I don't know how exactly =glm::intersectLineTiangle= works internally, but thinkng about a ray direction vector, coordinates should be in a form of a (0, 0, -x) for it to point exactly down from a origin point. – Helbreder Nov 14 '13 at 17:11
• I stepped over a SSCCE couple of times to understand how it works and these are the clues I found: * there's a typo in tri2 definition - first two vertices have the same coordinates. I've changed second one to (18.0000000, 34.0000000, 2.70000005) for testing purposes. * given vertices form triangles with clockwise windings. This states, by default, that both triangles are turned away from a ray's direction. I've reversed ray's direction so the ray shoots up from below triangles. * I think only dir vector should be normalized in normalizedIntersectRayTriangle function call. – Helbreder Nov 14 '13 at 22:00

There are two things to take care of:

1. Direction of a ray vector in accordance to triangle windings
2. Actual representation of a ray vector

Seems like gml::intersectLineTriangle() function needs a ray vector to point to a front face of a CCW triangle to work.

This is not the case in Your code and You can do two things to fix it: originate a ray vector "below" floor triangles in Your scene (pointing up) or slightly change order of vertices when preparing data for gml::intersectLineTriangle() function.

As for the second solution, swapping any two vertice coordinates when preparing data for Your intersectRayTriangle() function should do the trick, something like this:

vec3triangle tri1 = {   glmFrom(vertices[vertexIndex].v1),
glmFrom(vertices[vertexIndex].v3),
glmFrom(vertices[vertexIndex].v2)   };

vec3triangle tri2 = {   glmFrom(vertices[vertexIndex+1].v1),
glmFrom(vertices[vertexIndex+1].v3),
glmFrom(vertices[vertexIndex+1].v2) };


Ray direction vector should be a vector originating in (0, 0, 0) as we're interested in actual direction information. I'm not sure if it should be normalized or not, but tests I've conducted over a normalized version yelded valid results.

When constructing parameters for a ray, try this:

vec3ray ray = {glm::vec3(x, y, 10), glm::vec3(0, 0, -1)};


(applied along with a second solution to ad. 1) or this:

vec3ray ray = {glm::vec3(x, y, 0), glm::vec3(0, 0, 1)};


(when not).