You can have a look at my XNA code that does this. You start off with having a GetHeightAtLoc(float x, float y) method like this:


public float GetHeightAtLoc(float x, float y)
{
if (x >= 0 && x < size && y >= 0 && y < size)
{
if (x >= size - 1)
{
if (y >= size - 1)
{
return heights[(int)x + ((int)y * size)];
}
float modY = y % 1;
int cX = (int)x;
int cY = (int)y;
return MathHelper.Lerp(heights[cX + (cY * size)], heights[cX + ((cY + 1) * size)], modY);
}
else if (y >= size - 1)
{
float modX = x % 1;
int cX = (int)x;
int cY = (int)y;
return MathHelper.Lerp(heights[cX + (cY * size)], heights[(cX + 1) + (cY * size)], modX);
}
else
{
float modX = x % 1;
float modY = y % 1;
int cX = (int)x;
int cY = (int)y;
float TopLin = MathHelper.Lerp(heights[cX + (cY * size)], heights[(cX + 1) + (cY * size)], modX);
float BotLin = MathHelper.Lerp(heights[cX + ((cY + 1) * size)], heights[(cX + 1) + ((cY + 1) * size)], modX);
return MathHelper.Lerp(TopLin, BotLin, modY);
}
}
else
{
return 0;
}
}


Then you have a method that takes a ray and intersects it with the terrain return a Vector3 point:


public Vector3 GetRayCollisionPoint(Ray ray)
{
ray = ClipRay(ray, boundingBox.Max.Y, boundingBox.Min.Y);
ray = LinearSearch(ray);
Vector3 collisionPoint = BinarySearch(ray);
if (Calc.Contains(collisionPoint, boundingBox))
{
return collisionPoint;
}
else
{
Calc.MapBounds(ref collisionPoint, boundingBox);
collisionPoint.Y = GetHeightAtLoc(collisionPoint.X, collisionPoint.Z);
return collisionPoint;
}
}


That method uses a Linear search along the ray until the ray goes under the terrain, it then performs a Binary search backwards until it reaches a close enough approximation, in this instance within 0.01f of the terrain height. This results in fast accurate results that are hard to break. A Linear only approach would not be accurate enough due to the large stepping size, decreasing the stepping size would drastically increase computation time. A Binary only approach is prone to breaking if for instance you are looking through one hill, out the other side of it above the terrain again and then into another hill, you might well get the intersection point with the second hill. If no intersection point is found then an intersection with the map bounds is performed and the height at that point used, so if you're looking at the map wall or roof it will give you the point just below it on the terrain.

Here are the Linear and Binary search methods:


private Ray LinearSearch(Ray ray)
{
ray.Direction /= 50.0f;
Vector3 nextPoint = ray.Position + ray.Direction;
float heightAtNextPoint = GetHeightAtLoc(nextPoint.X, nextPoint.Z);
while (heightAtNextPoint < nextPoint.Y)
{
ray.Position = nextPoint;
nextPoint = ray.Position + ray.Direction;
heightAtNextPoint = GetHeightAtLoc(nextPoint.X, nextPoint.Z);
}
return ray;
}
private Vector3 BinarySearch(Ray ray)
{
float accuracy = 0.01f;
float heightAtStartingPoint = GetHeightAtLoc(ray.Position.X, ray.Position.Z);
float currentError = ray.Position.Y - heightAtStartingPoint;
int counter = 0;
while (currentError > accuracy)
{
ray.Direction /= 2.0f;
Vector3 nextPoint = ray.Position + ray.Direction;
float heightAtNextPoint = GetHeightAtLoc(nextPoint.X, nextPoint.Z);
if (nextPoint.Y > heightAtNextPoint)
{
ray.Position = nextPoint;
currentError = ray.Position.Y - heightAtNextPoint;
}
if (counter++ == 1000) break;
}
return ray.Position;
}


Let me know if you have any questions!