# heightMap help

I have designed a height mapped terrain, made of triangles. I want to find the exact height of a point on the height map. I want to use this to have an object hug the terrain.

The terrain is built so that two triangles make a square.

I have the code to check which triangle the point falls in but cannot find out how to get the height at the point. My code only returns the height of one corner of the triangle.

Also my code to find the correct triangle could be better.

Can anyone give me any pointers.

Let’s say the actual unit values for your terrain range from x1 to x2 (let’s leave out the z-axis for now) If you have an array, it would range from 0 to n. If you want a point on the map, let’s say x3, first check that it is between x1 and x2. The coordinate of the point would be x3/length, or x3/(x2-x1). Notice that these two expressions are equal: x3/(x2-x1)=p/(n-0), where p is the point you are looking for. To find p, you get: p=n*x3/(x2-x1). Now, do the same for the z-axis and you have:

px = nxx3/(x2-x1)
pz = nz
z3/(z2-z1)

Now, what you do to get the point is:

array[(int)px][(int)pz]

This will give you the height of the triangle closest to it, but it will not give you the exact height in the middle of the triangle. I do not know the formula for this, but I have seen it before and it contains 4 sqrt() calls. You do not want to be calling sqrt() hundreds of times per frame. This way is easy, fast, and effective. If anyone has the formula to find the exact height of a point, please post it! If I have any mistakes in my math, please say so.

Originally posted by Pops:
I have the code to check which triangle the point falls in but cannot find out how to get the height at the point.

If you have found the triangle all your work is done. Just insert the 2d point into the triangle’s plane equation and solve for z.

ax+by+cz+d=0 => z = -(d + ax + by)/c

Thanks both,

Fork, I need to find the exact height of the point of the triangle, otherwise my movable object does not follow the terrain smoothly.

roffe,

Thanks

If you already know the triangle, than you can do a simple Ray/Plane Intersection Test. Here is some code:

bool IntersectionRayWithPlane (const RAY &Ray, const PLANE3Df &Plane, VECTOR3Df *Point, float *time)
{
const float fEpsilon = 0.001f;
float fDenominator = Ray.m_vDirection.Dot (Plane.vNormal);

``````if (ABS (fDenominator) &lt; fEpsilon)//plane and ray are parallel
{
if (Plane.WhereIsPoint (Ray.m_vStartingPoint) == ON_PLANE)
{
if (time != NULL)
*time = 0.0f;
if (Point != NULL)
*Point = Ray.m_vStartingPoint;
return (true);
}

return (false);
}

float t = -(Plane.vNormal.Dot (Ray.m_vStartingPoint) - Plane.fDistance);
t /= fDenominator;

if (t &lt; 0.0f)//ray faces away from plane
return (false);

if (time != NULL)
*time = t;
if (Point != NULL)
*Point = Ray.m_vStartingPoint + ((t) * Ray.m_vDirection);

return (true);
``````

}

RAY is defined as follows:

struct RAY
{
VECTOR3Df m_vStartingPoint;
VECTOR3Df m_vDirection;
};

The test will return a point on the plane. Then you should know how to calculate the distance to that point.

You set the starting point of the ray to be equal with the point you want to let “fall down”. The direction of the ray is simply (0|-1|0).

If you have problems with my code, you can search the web for Ray/Plane or Ray/Triangle or Ray/Polygon Intersection Tests.

Hope it helps you.
Jan.

Originally posted by Pops:
[b]roffe,

[/b]

Oh, I guessed I just assumed you had some knowledge of linear algebra. Unfortunately it doesn’t get more trivial than that. I suggest you look up some basic linear algebra docs.

Plane equation for triangle: ax + by + cz +d = 0

(a,b,c) = triangle’s normal
d - distance(shortest) from origin to plane
(x,y,z) = point in 3d space, on plane

You have (x,y), need z.

I just want to make sure all my things are correct.

Example below.

If I have a triangle which represents flat ground with the coords below

Vertex 1
X = 50, Y = 0, Z = 50
Vertex 2
X = 50, Y = 0, Z = 51
Vertex 3
X = 51, Y = 0, Z = 50

I have identified this as the triangle my object is above and want to get the height (Y) at the X, Z coord of my object which are X = 50.2 Z = 50.5

The normal would point up into space

A = 0, B = 1, C = 0

I’m not sure what d is.

You stated ax+by+cz+d=0 => z = -(d + ax + by)/c

I want Y, so

ax+by+cz+d=0 => y = -(d + ax + cz)/b

Is this correct

Originally posted by Pops:
[b]ax+by+cz+d=0 => y = -(d + ax + cz)/b

Is this correct[/b]

Yes. d can be determined by inserting a point in the plane(known). Pick vertex1 for example.

d = -((a,b,c).(x,y,z))
=> ((0,1,0).(50,0,50)) = 0

y = -(d + ax + cz)/b
=> -(0 + 050.2 + 050.5) = 0

This should come as no surprise since your triangle is coplanar(in the same plane) to the plane y=0.

[This message has been edited by roffe (edited 09-17-2003).]

Does this formula represent matrix multiplication?

d = -((a,b,c).(x,y,z))

I have a class for storing both normals and vertex info

class Vector
{
public:
float z;
float y;
float x;
Vector();
virtual ~Vector();

};

I cant just multiply my normal and vertex (I tried), do I have to use matrix multiplication?

If yes, how?

Originally posted by Pops:
[b]Does this formula represent matrix multiplication?

d = -((a,b,c).(x,y,z))

[/b]

Well technically you could call it a matrix multiplication, but it is more commonly referred to as the dot product.

(a,b,c).(x,y,z) = ax+by+cz

Thanks for your help roffe, thats sorted it. My terrain following looks really good now.