# Finding Camera Y coordinate on a heightmap

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 01-05-2013
Lesshardtofind
Finding Camera Y coordinate on a heightmap
Hey!

I have been racking my brain for about a day and a half now. I know the answer has to be something simple, but for the life of me I can't deduce the simple equation/algorithym.

I built a randomly generated heightmap class. I have a working camera class that allows you to walk around in 3d space on this map, but I am having a heck of a time trying to figure out how keep the camera on the terrain at all times. The heightmap is declared as follows.

Code:

```struct Vector3{   Vector3();   Vector3(float x, float y, float z);   float X;   float Y;   float Z; }; struct Triangle{   Vector3 VertexA;   Vector3 VertexB;   Vector3 VertexC; }; class HeightMap{   private:     int Length, Width, MaxHeight, MinHeight, Scale, CollisionIndex;     std::vector <int> Heights;     Triangle CollisionTriangleA;     Triangle CollisionTriangleB;     Vector3 Origin;   public:     HeightMap(int L, int W, int MaxH, int MinH, int scale, Vector3 origin);     void Generate();     void Draw();     float GetHeightOf(int index);     float GetHeight(float x, float z);     Triangle GetColTriA();     Triangle GetColTriB(); };```
And the map is drawn like:
Code:

```void HeightMap::Draw(){   int HeightIndex = 0;   glTranslatef(Origin.X, Origin.Y, Origin.Z);   glBegin(GL_TRIANGLES);   for(int w = 0; w < Width-1; w++){     for(int l = 0; l < Length-1; l++){         if(CollisionIndex == HeightIndex){           glEnd();  // this draws the two triangles as wirefram so that I can see the collision detection is working properly           glPolygonMode(GL_FRONT, GL_LINE);           glPolygonMode(GL_BACK, GL_LINE);           // save the Triangles Coordinates for debugging the collision algorithym           CollisionTriangleA.VertexA = Vector3(float(l*Scale), float(Heights.at(HeightIndex)), float(w*Scale));           CollisionTriangleA.VertexB = Vector3(float((l+1)*Scale), float(Heights.at(HeightIndex+1)), float(w*Scale));           CollisionTriangleA.VertexC = Vector3(float(l*Scale), float(Heights.at(HeightIndex+Width)), float((w+1)*Scale));           CollisionTriangleB.VertexA = Vector3(float(l*Scale), float(Heights.at(HeightIndex+Width)), float((w+1)*Scale));           CollisionTriangleB.VertexB = Vector3(float((l+1)*Scale), float(Heights.at(HeightIndex+1)), float(w*Scale));           CollisionTriangleB.VertexC = Vector3(float((l+1)*Scale), float(Heights.at(HeightIndex+Width+1)), float((w+1)*Scale));           glBegin(GL_TRIANGLES);         }         glTexCoord2f(0.0f, 2.0f); glVertex3f(float(l*Scale), float(Heights.at(HeightIndex)), float(w*Scale));         glTexCoord2f(2.0f, 2.0f); glVertex3f(float((l+1)*Scale), float(Heights.at(HeightIndex+1)), float(w*Scale));         glTexCoord2f(0.0f, 0.0f); glVertex3f(float(l*Scale), float(Heights.at(HeightIndex+Width)), float((w+1)*Scale));           glTexCoord2f(0.0f, 0.0f); glVertex3f(float(l*Scale), float(Heights.at(HeightIndex+Width)), float((w+1)*Scale));         glTexCoord2f(2.0f, 2.0f); glVertex3f(float((l+1)*Scale), float(Heights.at(HeightIndex+1)), float(w*Scale));         glTexCoord2d(2.0f, 0.0f); glVertex3f(float((l+1)*Scale), float(Heights.at(HeightIndex+Width+1)), float((w+1)*Scale));         if(CollisionIndex == HeightIndex){           glEnd();           glPolygonMode(GL_FRONT, GL_FILL);           glPolygonMode(GL_BACK, GL_FILL);           glBegin(GL_TRIANGLES);         }       HeightIndex++;     }     HeightIndex++;   }   glEnd(); }```
The above draws the heigh map based off a int value in a vector called "heights" and the correct triangles that I am "standing" on are drawn in a wire frame.

So at this point I have the value of all the vertices stored in the CollisionTriangleA and CollisionTriangleB and I have the X and Z coordinate of the camera, but I can't figure out how to calculate the Camera Y coordinate based off this.

I hope I explained this clearly enough. If you can drop a link or tip I'd really appreciate it ;o).

Thanks!
- John

Here is a video of it as well you can see the the triangles below the camera are rendered in wireframe and the coordinates are displayed in the debug window to the left. Sorry about the background noise...I recorded it in a cafe.

• 01-05-2013
Lesshardtofind
This could probably be presented as just a math question.

Given triangle PQR, triangle STU, and point A.
Point A rests on a surface of one of the triangles.
What is the equation to solve for A.Y?
• 01-05-2013
Lesshardtofind
Think I got it! First to find the triangle the camera is on I can remove the Y component and us this method.

algorithm - How to determine a point in a triangle? - Stack Overflow

Then once I know the triangle that the camera is on use this for calculation of the height.

MathGem:Height of a Point in a Triangle - GPWiki

Stuck at work for the next 12 hours but I will test it when I get home!
• 01-05-2013
GReaper
Actually, its much simpler than that:
Your heightmap is a rectangle. Assuming that your camera will always be within that map ( e.g. not fall out ), you can find the indices with this simple formula:
Code:

```xIndex = int((cameraPos.X - mapPos.X)/mapWidth); zIndex = int((cameraPos.Z - mapPos.Z)/mapHeight);```
You may want to round to nearest instead of truncate, it's your choice. Or you can even get the 4 points wherein your camera stands, find the average and use that as the appropriate height.

EDIT: Just want to clarify that the given formula won't work if the map was also rotated and/or scaled. You may want to adjust it.
• 01-05-2013
Lesshardtofind
Right that is the equation I use to get the index in the map that has the height value. But remember the values represent corner heights and not the faces in between.

So you still have to use the triangle the camera rests on and its slope to find the camer's correct resting position. Your equation is the one I already use to just brute force the height, but it leaves elevation choppy and still allows you so end up underneath the map on steep inclines.

Edit: it would work if the triangles were small like under 1.0f, but the are 20.0f in size (GL units).
• 01-05-2013
GReaper
Ok then, I get it now that you need precision. Therefore, you need Line-plane intersection
Here's a formula I dug up that returns the intersection point of a ray with a plane:
Code:

```a = N.DotProduct(rayDir); if (a == 0)     return rayPos; return rayPos - rayDir * (DistanceToPlane(rayPos) / a);```
"rayPos" will be your camera's position
"rayDir" will be (0, -1, 0)
"DistanceToPlane" will refer to the plane that is formed by the triangle's points
"N" will be the normal of the desired triangle
• 01-05-2013
Lesshardtofind
Nice that's short. Do you have a suggestion for telling which of the two triangles on the quad the camera is above? Or should I just go off that stack overflow link I found?

One other clarification is
Code:

` a = N.DotProduct(rayDir);`
A function of class N that takes ray direction as a parameter, or just multiplication of two vectors into a scalar number?

Sorry I am pretty new to the 3d math concepts, and not sure if this is meant to return 3 coordinates (vector) or a scalar value.
• 01-05-2013
GReaper
You can take the angles between the three lines that make up each triangle and sum them up. If the result doesn't equal 180 degrees ( with some tolerance ), then the point isn't inside the triangle.
You can also cut the quad in half with a vertical plane ( which will separate the two triangles ) and take the distance of the camera's position from that plane. If the distance is positive, you use the one triangle. If the distance is negative, you use the other.

I don't know which method is better, it's been a while since I did vector-plane math.
• 01-05-2013
GReaper
Quote:

Originally Posted by Lesshardtofind
A function of class N that takes ray direction as a parameter, or just multiplication of two vectors into a scalar number?

Dot product is also known as inner product or scalar product ;)
• 01-05-2013
Lesshardtofind
Quote:

Dot product is also known as inner product or scalar product
Oh lol
• 01-06-2013
Lesshardtofind
Well when I was at work I thought it looked simple. I've almost written all the functions needed to get this equation you posted to work, but I'm having some issues here
Code:

`return rayPos - rayDir * (DistanceToPlane(rayPos) / a);`
1. I am having troubles figuring out how to calculate DistanceToPlane most examples I find use plane equations 2x - y +3z. It seems to know the distance to the plane I would need the Intersection point to subtract from the current camera position and then use pathagorean vector magnitude equation. Seems circular since this equation is trying to get the intersection point. I know i'm missing something.
EDIT: http://www-math.mit.edu/~djk/18_022/...example01.html Think is this right.
Code:

` (DistanceToPlane(rayPos) / a);`
2. I'm worried I'm not thinking about this right. This is two scalar to vector math operations correct? Where I should do.
Code:

```rayPos.X *= DistanceToPlane; rayPos.Y *= DistanceToPlane; rayPos.Z *= DistanceToPlane; rayPos.X /= DistanceToPlane; rayPos.Y /= DistanceToPlane; rayPos.Z /= DistanceToPlane;```
I know I should probably define Vector operators to make this easier, but one step at a time ;o). Thanks for the help thus far and I'll be googling and reading diligently all day, but if you get a free moment to clarify these things I would appreciate it.

Thnx!
• 01-06-2013
GReaper
DistanceToPlane is essentially the scalar product of the plane normal and the point, minus D. Remember the plane equation: Ax + By + Cz - D = 0

I wrote it using the formal way because I had already built classes for these things, vector, plane etc.

I can simplify it for you, here's an explanation: ( All products in this formula are scalar )( A * B = A.x*B.x + A.y*B.y + A.z*B.z )
Code:

```scalar_t a = plane.N * rayDir; if (a == 0)     return rayPos; return rayPos - rayDir * ((plane.N*rayPos - plane.D) / a);```
which is equivalent to:
Code:

```scalar_t a = plane.N.x*rayDir.x + plane.N.y*rayDir.y + plane.N.z*rayDir.z; if (EQUALS(a, 0))     return rayPos; vector result; scalar_t common = ((plane.N.x*rayPos.x + plane.N.y*rayPos.y + plane.N.z*rayPos.z - plane.D) / a); result.x = rayPos.x - rayDir.x * common; result.y = rayPos.y - rayDir.y * common; result.z = rayPos.z - rayDir.z * common; return result;```
I hope I didn't make things even more complicated... :D
• 01-06-2013
Lesshardtofind
Quote:

I hope I didn't make things even more complicated.
Nah I just am being super dense on this one.... Might be that 17.5hr shift yesterday killed some brain cells, but you are loosing me with D. Sorry I never took calculus or physics so some of this stuff should be basic for game programming, but I've had to crash course it with google and wiki. So maybe to clarify I will post my code and hopefully you can tell me where I'm shooting myself in the foot. my method is pretty similar to yours other than it seems over-complicated.

Code:

```Vector3 IntersectionPoint(Triangle ColTri, Vector3 CameraPos){   float a = DotProduct(Normal(ColTri), Vector3(0, -1, 0));   if(a == 0)     return CameraPos; // this was the method I read to calculate distance based on the point any point in the plane and the normal to the plane.   Vector3 Temp;   Temp.X = CameraPos.X - ColTri.VertexA.X;   Temp.Y = CameraPos.Y - ColTri.VertexA.Y;   Temp.Z = CameraPos.Z - ColTri.VertexA.Z;   float X = DotProduct(Normal(ColTri), Temp);   float Mag = Magnitude(Normal(ColTri));   float DistanceToPlane = X/Mag;   Vector3 rayPos = CameraPos;   rayPos.X *= DistanceToPlane;   rayPos.Y *= DistanceToPlane;   rayPos.Z *= DistanceToPlane;   rayPos.X /= a;   rayPos.Y /= a;   rayPos.Z /= a;   Vector3 ToReturn = CrossProduct(Vector3(0, -1, 0), rayPos);   ToReturn.X = CameraPos.X - ToReturn.X;   ToReturn.Y = CameraPos.Y - ToReturn.Y;   ToReturn.Z = CameraPos.Z - ToReturn.Z;   return ToReturn; }```
I use it as
Code:

`Camera.SetCenter(Camara.GetCenter().X, IntersectionPoint(TriangleImStandingOn, CameraPos).Y+2.0f, Camera.GetCenter().Z);`
And this has me luanching successfully higher every pass through the game main loop so there is an issue there I'm missing. I think its the Distance formula I'm using.

Thanks alot for your help so far.
• 01-06-2013
Lesshardtofind
Code:

```Vector3 IntersectionPoint(Triangle ColTri, Vector3 CameraPos){   float a = DotProduct(Normal(ColTri), Vector3(0, -1, 0));   if(a == 0)     return CameraPos;   Vector3 Temp;   Temp.X = CameraPos.X - ColTri.VertexA.X;   Temp.Y = CameraPos.Y - ColTri.VertexA.Y;   Temp.Z = CameraPos.Z - ColTri.VertexA.Z;   float X = DotProduct(Normal(ColTri), Temp);   float Mag = Magnitude(Normal(ColTri));   float DistanceToPlane = X/Mag;   Vector3 ToReturn;   float Multiplier = DistanceToPlane/a;   ToReturn.X = CameraPos.X;   ToReturn.Y = CameraPos.Y+Multiplier;   ToReturn.Z = CameraPos.Z;   return ToReturn; }```
Updated still not working:
I did copy the distance formula into another program and test it on multiple triangles and points and it seems to be working so I didn't change it.

I tried your code and was misinformed from one site that said D was an arbitrary constant and could be any number so I tried 1. That didn't work at all. So more research turned up that D is the distance from origin.

I guess I need to come up with a function that returns the slope-intercept of all directional components so that I may caculate the Distance the plane is from the point of origin. On that note I think I'm going to take ten and have dinner! lol
• 01-08-2013
VirtualAce
This can be done via linear interpolation. Find which triangle the camera is in...upper or lower and linear interpolate between the edges using the x and y coefficients representing the barycentric coordinates of the camera in the triangle. This will give you the height at the camera's positon. Slope can be determined by using the camera look vector and the triangle normal.

EDIT:
A second method is to create a point along the look vector at some distance and sample the height via linear interpolation as described above. The slope can then be computed using good old fashioned trig. This is how most car-based games sample the height - either in 3 places or 4 and compute the roll, yaw, and pitch from those points. This allows the car to follow the shape of the terrain.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last