Finding Z given X & Y coordinates on terrain?

Question

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.

Answer 1

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

ad. 1)

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) };

ad. 2)

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).