Thread: Finding Camera Y coordinate on a heightmap

  1. #1
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    428

    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.

    https://www.youtube.com/watch?v=qYBTyEkm9e8
    Last edited by Lesshardtofind; 01-05-2013 at 07:26 AM.
    Virtual reality hello world http://www.rodneybrothers.com/vr/vrh...rld/index.html in html and javascript.
    Viewable with dodocase, google cardboard, OR, and other compatible VR gear.

  2. #2
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    428
    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?
    Virtual reality hello world http://www.rodneybrothers.com/vr/vrh...rld/index.html in html and javascript.
    Viewable with dodocase, google cardboard, OR, and other compatible VR gear.

  3. #3
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    428
    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!
    Virtual reality hello world http://www.rodneybrothers.com/vr/vrh...rld/index.html in html and javascript.
    Viewable with dodocase, google cardboard, OR, and other compatible VR gear.

  4. #4
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    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.
    Devoted my life to programming...

  5. #5
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    428
    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).
    Last edited by Lesshardtofind; 01-05-2013 at 10:18 AM.
    Virtual reality hello world http://www.rodneybrothers.com/vr/vrh...rld/index.html in html and javascript.
    Viewable with dodocase, google cardboard, OR, and other compatible VR gear.

  6. #6
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    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
    Last edited by GReaper; 01-05-2013 at 10:43 AM.
    Devoted my life to programming...

  7. #7
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    428
    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.
    Last edited by Lesshardtofind; 01-05-2013 at 12:10 PM.
    Virtual reality hello world http://www.rodneybrothers.com/vr/vrh...rld/index.html in html and javascript.
    Viewable with dodocase, google cardboard, OR, and other compatible VR gear.

  8. #8
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    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.
    Devoted my life to programming...

  9. #9
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Quote Originally Posted by Lesshardtofind View Post
    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
    Devoted my life to programming...

  10. #10
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    428
    Dot product is also known as inner product or scalar product
    Oh lol
    Virtual reality hello world http://www.rodneybrothers.com/vr/vrh...rld/index.html in html and javascript.
    Viewable with dodocase, google cardboard, OR, and other compatible VR gear.

  11. #11
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    428
    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!
    Last edited by Lesshardtofind; 01-06-2013 at 01:01 PM.
    Virtual reality hello world http://www.rodneybrothers.com/vr/vrh...rld/index.html in html and javascript.
    Viewable with dodocase, google cardboard, OR, and other compatible VR gear.

  12. #12
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    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...
    Last edited by GReaper; 01-06-2013 at 02:40 PM.
    Devoted my life to programming...

  13. #13
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    428
    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.
    Last edited by Lesshardtofind; 01-06-2013 at 03:07 PM.
    Virtual reality hello world http://www.rodneybrothers.com/vr/vrh...rld/index.html in html and javascript.
    Viewable with dodocase, google cardboard, OR, and other compatible VR gear.

  14. #14
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    428
    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
    Last edited by Lesshardtofind; 01-06-2013 at 04:38 PM.
    Virtual reality hello world http://www.rodneybrothers.com/vr/vrh...rld/index.html in html and javascript.
    Viewable with dodocase, google cardboard, OR, and other compatible VR gear.

  15. #15
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.
    Last edited by VirtualAce; 01-09-2013 at 10:49 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with finding the shortest coordinate of a maze
    By chickenlittle in forum C++ Programming
    Replies: 10
    Last Post: 10-24-2011, 12:27 PM
  2. Puget sound heightmap discription
    By fleurdelys77 in forum Game Programming
    Replies: 18
    Last Post: 09-15-2011, 05:49 AM
  3. Is it a good method (BMP heightmap to raw) ?
    By fleurdelys77 in forum Game Programming
    Replies: 7
    Last Post: 09-11-2011, 05:17 AM
  4. Displaying a heightmap
    By Dark_Phoenix in forum Game Programming
    Replies: 6
    Last Post: 11-11-2006, 04:24 PM
  5. Finding Y coordinate
    By Extol in forum Windows Programming
    Replies: 3
    Last Post: 04-16-2003, 07:50 PM