I'm writing a small terrain visualization piece as part of a game. I'm well-versed in C++ and I have implemented most of the game. I'm using OpenGL (doesn't matter) and a heightmap (no LOD, just simple stuff for now) to draw my triangles. Because of the way that the game works, it is necessary to map the current mouse's location (click, hover, current position, etc) to a 3D point on the terrain. One thing I like in games is the ability to view the game world from any angle and any distance, so one of the features in the game is a free-camera where there are no limits to where it can go. As a result, the user can see the terrain from 1 unit or 500 units away (as long as the z-range isn't too small). It also allows them to see it from any angle. My problem is that outside a basic top-down mouse->terrain mapping I'm having trouble determining the exact spot where the mouse's ray interesects the terrain. What I currently have is: x = (2.0 * ((double)i / (double)global_width) - 1.0); y = (2.0 * ((double)j / (double)global_height) - 1.0) * -1.0; x = ((4.0 / 3.0) * tz * x) + tx + PHeightmap::SCALE*PHeightmap::COLUMNS/2; y = ((3.0 / 3.0) * tz * y) - ty + PHeightmap::SCALE*PHeightmap::ROWS/2; where x,y starts out as the viewport coordinates and ends up being the x,y coords on the terrain (z is up). The 4/3 and 3/3 is there for the aspect ratio. tz is the distance to (z=0) PHeightmap::SCALE is the xy multiplier on the heightmap's dimentions. tx,ty are the x,y translation along the (z=tz) plane. This of course only works for a terrain where the entire Heightmap is (z=0). The moment that I rotate the camera, the mouse clearly stops being representative of the terrain's surface. Where should I go from here? I've tried getting a ray through (0,0,0)->(x,y,0) where 0<=x,y<=1 and running through each triangle in the Heightmap, but this always fails for me. I realize that at certain angles the ray might intersect the terrain at more than one place (I know how to figure out which triangle is closer). Any suggestions for a short-and-sweet or concise method of determining mouse-ray and terrain intersection to determine the exact spot where it hits?

If I'm understanding what you're after, then you probably want something like the following:

1. Use gluUnproject() to find a 3d point on the near plane corresponding to the mouse coordinates
2. Create a ray with the camera position as origin and passing through this point
3. Intersect the ray with every triangle in the heightmap
4. Take the closest hit (if any) as your result

There are obviously some deteails to be worked out here, so here are a couple more comments. I know there are a couple of tutorials online that will help with step 1 - try googling 'opengl picking' for those. You'll get some hits that describe picking in feedback mode using gluPickMatrix(), but you want the gluUnproject() version. Then you'll need a ray-triangle intersection function. Given that, you can do a brute-force raytrace against the terrain and take the closest result, as described above.

Depending on the size of your heightmap, the brute-force approach may be too slow, in which case there are various methods (3DDDA, quadtrees) for accelerating the raytrace. Depending on what ray-tri algorithm you use, there may also be possible robustness issues, with the ray occasionally 'falling through the cracks' between triangles. This can be addressed by switching to a more robust ray-tri algorithm.

Again, this is assuming I'm understanding what you're after. If so, the above method is very general and will return the exact spot on the terrain under the mouse pointer.

Hrmph.

I've written that before, and I couldn't get it to work properly.

Here's what I've written in the past:

double x1, y1, z1, x2, y2, z2;
double Projection[16];
glGetDoublev(GL_PROJECTION_MATRIX, Projection);
double Modelview[16];
glGetDoublev(GL_MODELVIEW_MATRIX, Modelview);
int Viewport[4];
glGetIntegerv(GL_VIEWPORT, Viewport);

gluUnProject(i, j, 0.0, Modelview, Projection, Viewport, &x1, &y1, &z1);
gluUnProject(i, j, 1.0, Modelview, Projection, Viewport, &x2, &y2, &z2);

double u=x2-x1, v=y2-y1, w=z2-z1;

Point P1 = Point(x1, y1, z1);
Point P2 = Point(x2, y2, z2);

Point P = PHeighmap::GetIntersectPoint(P1, P2);

And:


Point PHeightmap::GetIntersectPoint(Point P1, Point P2)
{
/*
we define a plane that passes through A,B,C (the points of the triangle)
n is normal of normalized CROSS(A-C, B-C)
pL and vL are the points on the line
double t = DOT(n, C-pL) / DOT(n, vL)
intersection point P = pL + t(vL)
*** a, b, and c then become 2D points that you drop the one with the largest absolute value for the plane normal
point denom = cross(a-c, b-c)
point u = cross(p-c, b-c) / denom
point v = cross(a-c, p-c) / denom
we need to check if u+v< 1, 0<u<1, 0<v<1, if so then P is the intersection
we then find the smallest z of all the P's the line intersects
*/
for (int i=0; i<PHeightmap::COLUMNS-1; i++)
for (int j=0; j<PHeightmap::ROWS-1; j++)
{
Point A = Point (i+1, j, Map[i+1][j].z*SCALE_HEIGHT);
Point B = Point (i, j, Map[j].z*SCALE_HEIGHT);
Point C = Point (i+1, j+1, Map[i+1][j+1].z*SCALE_HEIGHT);
Point D = Point (i, j+1, Map[j+1].z*SCALE_HEIGHT);

Point N1 = (A-C) CROSS (B-C);
Point N2 = (B-D) CROSS (C-D);

double T1 = (N1 DOT (C-P1)) / (N1 DOT P2);
double T2 = (N2 DOT (D-P1)) / (N2 DOT P2);

Point IP1 = P1 + T1*P2;
Point IP2 = P1 + T2*P2;

Point U1 = ((IP1-C) CROSS (B-C)) / ();
Point V1 = ((A-C) CROSS (IP1-C)) / ();

Point U2 = ((IP2-D) CROSS (C-D)) / ();
Point V2 = ((B-D) CROSS (IP2-D)) / ();
}
}

But that is as far as I've gotten. How do I finish this off?

Took a quick look over your code - I don't have a complete answer, but I can make a couple of suggestions.

The part where you're unprojecting the points looks correct at first glance, but perhaps you could find a way to test that part independently to make sure it's working. For example, you could just render the returned points directly to see if they're under the mouse. (Or maybe you already know this part is working.)

Next, make sure you're clear on whether the intersection function takes the ray in 'start point and end point' form, or 'start point and direction vector' form. From just glancing at your code (and I may be wrong about this), it looks like you're passing start and end points, but the function expects an origin and direction. So you might double check that.

The next thing I'd do is put the ray-triangle intersection code in a separate function so that it's easier to test. (You might test it by just making a single big triangle and casting random rays against it.) The 'intersect with terrain' function would then call the 'ray-triangle intersection' function, twice for each quad.

As for the ray-tri test itself, there are various ways to do it, and a google for 'ray triangle intersection' should turn up several algorithms. Once you get it working, there may be some efficiency and robustness issues to address, but I'd say the first step is to just get it up and running.

'Hope some of that will be useful in some way...

Thanks for the feedback guys. Jyk, thanks for the suggestions and I'll make the code a tad bit more modular. I know that the projection points are correctly on the front and back planes and they do accurately represend the mouse, I just hadn't noticed that the algorithm wants a point+ray and not two vertices. Thanks.