Sign in to follow this  

Place a player onto the 3D-surface

This topic is 389 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi! Sorry for duplicating thread, but it looks like that it was previously created in a wrong place (In "For Beginners" section).
 
I have a 3D-surface that consists of triangles. I want to place a player onto this surface, i.e. I have to count a Z-coord using X and Y coords of triangles. Many advices say I have to cast a ray from the player standing point vertically and thus find a crossing with a triangle plane. But actually that mean check crossing with every triangle forming our 3D-surface, moving from one triangle to another in vertex buffer, cause we don't have access to those triangles through coords - but only through their numbers in a vertex buffer. That way doesn't look very optimal. Optimization looks kinda simple: split surface onto sections, which may be accessed through the coords. But that's only my assumptions.
So, how exectly that problem is usually solved in a modern games? I think there are some standard algorithms.

Share this post


Link to post
Share on other sites

I got confused there because it looks like this thread was moved while I was writing a reply to it and was locked out of posting my reply. Fortunately, I saved a copy of it and didn't lose it. So here's what I replied:

 

It sounds like you are trying to make a terrain and that you are trying to figure out terrain collision.

 

For that, you start with a couple assumptions. One is that the triangles of the grid are all arranged into squares of equally spaced vertices. So, the X and Z (horizontal) coordinates are always the same and evenly spaced apart. The only possible change is the Y value which is the height of each vertex. You draw triangles to shade in the terrain, but in order to make it solid you have to have collision detection.

 

One way to do that is interpolation. You don't start with the height of any position in the square, just the height of the vertices at the corners of each square which are typically stored in an array of vertex heights. So, you have to calculate the height of any position within any given grid square. The first problem you encounter is that it's actually two triangles and this situation allows for the two triangles to face their own directions. And there are two ways the triangles can split the square. Fortunately, you are the one that determines that and so you can know which way the split occurs.

 

You can basically ignore this problem and merely interpolate the x coordinate for an x height and then interpolate the y coordinate for a y height. So, you LERP, or do a weighted average, between the Y heights based off the distance from them and then take that and weight into a weighted average of the X height. This will likely result in a very jittery terrain collision that is not entirely accurate, but it is a little easier and it basically works. Plus the next solution, and more accurate one, is basically the same thing except you interpolate the heights of the 3 vertices of the triangle rather than the 4 vertices of the square.

 

Because you created this, you know where the dividing line is across the square for the two triangles. Set the triangles up so that the dividing line is from 1,0 to 0,1 for the X coordinate offsets within a given triangle. That should be X=1,Z=0 and X=0,Z=1. Now you can do a little math trick here: if the sum of X and Z here is 1 then we know the position is on the hypotenuse line dividing the square(also called a quad for quadrilateral). If the sum of the values is less than 1 then the given position is in one triangle and if they sum up to more than 1 the position is in the other triangle. That's how you know which triangle your position is standing in.

 

So, at this point, we've worked out exactly which triangle the given position is standing over out of the entire grid. Keep in mind that your grid may not start at 0,0 and only be in the positive range. You're probably going to want to center the grid at 0,0 and have it extend equally into all four quadrants. So, you'll have to do the math for that offset which is usually just to divide the grid width in half. Also, we're assuming each grid quad is 1 unit by 1 unit. You can do some math to make them larger or smaller if you like and then you have to take that into account. But regardless, you need to work out which quad the position is in and reduce it down to positions between 1,0 and 0,1.

 

And at this point you know exactly which triangle the position is in and you need to know the height at that point within the one triangle. So, you have the three height values for the triangle's vertices in the height array. Grab those and interpolate between the three values. Your code is going to be slightly different depending on which of the two triangles it is, but we've already figured that out.

 

For one it will be something like:

TerrainHeight = QuadUpperLeftHeight + (XPositionInQuad * (QuadUpperRightHeight - QuadUpperLeftHeight)) + (ZPositionInQuad * (QuadLowerLeftHeight - QuadUpperLeftHeight));

And for the other triangle it would be something like:

TerrainHeight = QuadLowerRightHeight + ((1-XPositionInQuad) * (QuadLowerLeftHeight - QuadLowerRightHeight)) + ((1-ZPositionInQuad) * (QuadUpperRightHeight - QuadLowerRightHeight));

It's basically just a weighted average between the 3 heights of the triangle. You can probably use a LERP function for this; so you may see it implemented with LERP.

 

Anyway, that's how you can determine the height within a grid triangle that is 100% accurate assuming the triangle is planar. Once you know the height of that position on the grid you add a standard camera height to it to make the camera follow the terrain at "eye" level. Or you can use it for collision detection against that spot on the terrain.

 

Here's actual code for terrain height that I wrote in C# for MonoGame. Should be reasonably easy to convert to any framework as most of it is just math:

 public float TerrainHeightBelowPoint(Vector2 PositionTested)
        //==========================================================================================================
        //  TerrainHeightBelowPoint()
        //
        //  Purpose: To return the height of the terrain at any given point on the terrain.
        //
        //  Parameters:
        //      PositionTested - The X,Z position that a height should be retrived for.
        //
        //  Notes:
        //      The first thing to note is that this algorithm is totally different from the terrain collision algorithm
        //  we used before. This one is far more accurate. The reason is that the other one looked at the position
        //  within the entire quad. This one looks at the position over a single triangle in the quad. So, the previous
        //  algorithm could produce a slightly incorrect height diagonally within a given quad. It's usually not a huge
        //  problem unless the quad changes altitude drastically between the corners. However, this method looks at only
        //  the triangle the position is over and interpolates the altitude over that triangle.
        //
        //      It does this based on the rule we are setting that the center line between the two triangles MUST go from
        //  the 0,1 corner to the 1,0 and NEVER from the 0,0 corner to the 1,1 corner. This rule allows us to easily
        //  determine which triangle the position is over within the quad. Notice that if you sum the x and z coordinates
        //  when the center line goes from 0,1 to 1,0 then, the sum is ALWAYS exactly 1. Even 0.4, 0.6 will be on that line
        //  between them because the sum equals exactly 1. This will not work if we draw our centerline from 0,0 to 1,0.
        //  (I believe I said the exact opposite and was therefore wrong in the first terrain tutorial part. I had to do
        //  a correction to the code here once I figured out that I had that backwards and that's part of the reason that
        //  I had to do the backface culling the opposite of the normal direction. Just set the backface culling back to
        //  the proper direction for any other models/meshes drawn.) Anyway, if the sum of x and z are < or > 1 then you
        //  know which side of the center line they are on and thus which triangle the point is in.
        //
        //      Probably the most complicated part of understanding this code is the conversions going on. In order to
        //  do all the math and such, we need the grid quad(square) that we are testing to act like it is 0,0 to 1,1. In
        //  other words, we need it to be a unit square with all sides equalling 1. We can throw away the actual position
        //  once we get the heights at the four corners. Then we just want to know where within THIS quad the position
        //  being tested is at.
        //
        //      So, a tested position of -100.6, 10.3 is shifted by half the size of the grid to "undo" the grid centering
        //  that centered the grid at 0,0. The height map is an array that cannot have negative positions, but our shifted
        //  grid has negative positions. So, we have to "un-center" the position tested to line back up with the height map
        //  array rather than lining up with the drawn grid.
        //
        //      Then we have to undo the scaling of the grid. QuadSize multiplies the size of the grid by this value and
        //  we want to undo that so that every quad (grid square) is 1 unit on every side in order to make the math work
        //  out nicely.
        //
        //      By that point, -100.6, 10.3 is probably looking more like 155.4, 266.3 (if the QuadSize was 1 starting out).
        //  So you can then drop the non-fractional part of the coordinates to get the position within THIS quad. And
        //  so 155.4, 266.3 become 0.4,0.3.
        //
        //      Because 0.4 and 0.3 do not add up to exactly 1, we know the point is not on the center line between 0,1 and
        //  1,0. And because it is less than 1, we know that it is over the upper triangle. We can then take a weighted
        //  average of the position above that triangle based on the percentage position between the 3 triangle corners.
        //
        //==========================================================================================================
        {
            float HeightOfTerrain = 0.0f;   //Altitude of the terrain at the given position.
            float QuadUpperLeft;    //0,0
            float QuadLowerLeft;    //1,0
            float QuadUpperRight;   //0,1
            float QuadLowerRight;   //1,1
            float XInQuad = 0.0f;   //The x position within THIS quad as a percentage of left to right.
            float ZInQuad = 0.0f;   //The z (y if you think in 2D) position within THIS quad as a percentage of top to bottom.
            float x;    //Position coordinate uncentered and unscaled to be 1 by 1 grid square sized.
            float z;    //Position coordinate uncentered and unscaled to be 1 by 1 grid square sized.
            int X = 0;  //Non fractional part of x.
            int Z = 0;  //Non fractional part of z.
            bool PointIsAboveUpperTriangle = false; //Determine which triangle the position is over within the quad.


            //Correct for the fact that the grid is centered but the heightmap can never be as well as quad size so that the quad will be 1 unit for our calculations.
            x = (PositionTested.X / QuadSize) + GridSize / 2;
            z = (PositionTested.Y / QuadSize) + GridSize / 2;
            
            //If the position is off of the grid, then return a height value of zero, and return immediately, rather than crashing with invalid numbers.
            if ((x < 1) || (z < 1) || (x > GridSize) || (z > GridSize))
            {
                HeightOfTerrain = 0;    //Zero is as good a height as any when we are not on the grid.
            }
            else
            {
                //Set X,Y to the Upper Left corner of the quad.
                //Floor will take away the decimal part of the number.
                X = (int)Math.Floor(x);    //Set X to be the value in the upper left corner normalized to an integer and QuadSize of one.
                Z = (int)Math.Floor(z);    //Set Y to be the value in the upper left corner normalized to an integer and QuadSize of one.

                XInQuad = x - X;   //X position within THIS quad. Only the fractional part of the coordinate is kept since the position is between 0 and 1.
                ZInQuad = z - Z;   //Z position within THIS quad. Only the fractional part of the coordinate is kept since the position is between 0 and 1.

                //Get the height at every corner of the quad (square). The center line must run between QuadLowerLeft(0,1) and QuadUpperRight(1,0) for this algorithm to work.
                QuadUpperLeft = HeightMap[X, Z];
                QuadLowerLeft = HeightMap[X, Z + 1];
                QuadUpperRight = HeightMap[X + 1, Z];
                QuadLowerRight = HeightMap[X + 1, Z + 1];

                //If the sum of x and z = 1 it is on the center line. Assuming the center line goes from 1,0 to 0,1.
                //If the sum is less than 1 then it is within the upper triangle.
                PointIsAboveUpperTriangle = XInQuad + ZInQuad < 1;  
                if (PointIsAboveUpperTriangle)
                {
                    HeightOfTerrain = QuadUpperLeft;    //We start with this height and add the weighted averages of the height differences of the other two points of the triangle based on position within this triangle.
                    HeightOfTerrain += XInQuad * (QuadUpperRight - QuadUpperLeft);  //Percentage from 0 to 1 across the quad horizontally, applied to the difference between the two corner heights.
                    HeightOfTerrain += ZInQuad * (QuadLowerLeft - QuadUpperLeft);   //Percentage from 0 to 1 across the quad vertically, applied to the difference between the two corner heights.
                }
                else
                {
                    HeightOfTerrain = QuadLowerRight;
                    HeightOfTerrain += (1f - XInQuad) * (QuadLowerLeft - QuadLowerRight);   //Use the inverse percentage across the quad for the lower triangle because we are drawing in the opposite direction from 1 to 0. 40% becomes 60% for example.
                    HeightOfTerrain += (1f - ZInQuad) * (QuadUpperRight - QuadLowerRight);
                }
            }

            return HeightOfTerrain;
        }
        //==========================================================================================================
 
Edited by BBeck

Share this post


Link to post
Share on other sites

BBeck, thanks for you detailed answer. Well, you mean a terrain should consist of many little squares, so if we look onto this from above (or, the same thing, make an ortho projection into a plane) we see a square grid (halfed by triangles), just like a chess desk. The thing I'm aware of, as I mentioned above, is an access to the specified triangle by its coordinates. Suppose we ortho-projected our grid onto a plane, (or, what is the same, just cut off a Z-coord (height)). Suppose then we're standing at the point with given coords. So how to find a triangle in a vertex buffer, a triangle that contains this given point on our plane? Since a triangle accessed by its number in a vertex buffer, not by its coords.

Well, if I understood right, as we have an exactly square segmentation, we can access a specified square using an offsets in a vertex buffer, so we don't even need to find a square\triangle, we can access it directly. Like this: suppose W is a width of our whole grid in a square-dimension-units, so x of our vertex buffer will be like x = x-point * W, and y will be like y = x-point * W + y-point. Am I right?

Edited by Kobaktan

Share this post


Link to post
Share on other sites

I'm a little worried about the term "vertex buffer" here. You would generally be working from an array of floating points height values. The horizontal positions of the vertices are always the same and evenly spaced.

 

You would still build your vertex buffer using the data from the height array, but you probably would never go retrieve data from your vertex buffer once you built it. All of this is a mathematical concept and doesn't have to be drawn on screen to work. The visual and the collision detection are completely separate. Both are based of the height array.

 

You're right about the math on rows and columns.

 

But maybe the part I didn't explain well enough is how to get the position values inside the square to be between 0 and 1. That's this code here:

 

                //Set X,Y to the Upper Left corner of the quad.
                //Floor will take away the decimal part of the number.
                X = (int)Math.Floor(x);    //Set X to be the value in the upper left corner normalized to an integer and QuadSize of one.
                Z = (int)Math.Floor(z);    //Set Y to be the value in the upper left corner normalized to an integer and QuadSize of one.

                XInQuad = x - X;   //X position within THIS quad. Only the fractional part of the coordinate is kept since the position is between 0 and 1.
                ZInQuad = z- Z;   //Z position within THIS quad. Only the fractional part of the coordinate is kept since the position is between 0 and 1.

 

There you round down and then subtract the floating point X and Z value from the rounded version. That leaves just the remainder of X and the remainder of Y which are values between 0 and 1 and the position within the square.

 

Then you use this code to pull the height data for each vertex of the square:

       QuadUpperLeft = HeightMap[X, Z];
                QuadLowerLeft = HeightMap[X, Z + 1];
                QuadUpperRight = HeightMap[X + 1, Z];
                QuadLowerRight = HeightMap[X + 1, Z + 1];
 

 

Assuming you don't have to correct for squares that are different size than 1 unit and that the grid is from 0,0 and all positive (not centered), just rounding down will give you the positions within the height map/array. Add 1 to get the next vertex.

 

You'll build your mesh out of these values as well. The vertices you load into the vertex buffer will be all evenly spaced and so your X and Z values should basically match your height map. Then use the height value stored in the height map for the Y value when building your vertex buffer.

 

So, you don't look at the vertices. The height map is used both for collision detection and for building the vertex buffer data. So, you don't go to the vertex buffer for answers; you go to the height map that built the vertex buffer. Once you build a vertex buffer you ship it to the graphics card and it's (generally) best not to mess with it after that. Most of the time you don't want to pull data off the graphics card back to the CPU and especially for this. Consider the vertex data inaccessible. But you have the height map it was built from which is more efficient to search anyway. Vertex buffers can be very large as a vertex may consist of a dozen or more floating point values where as a spot in the height map is only 1 float.

Share this post


Link to post
Share on other sites

I'm a little worried about the term "vertex buffer" here

Well I just meant a source, where a real Vertex Buffer gets data from. Actually that source is .3ds file containing a terraing mesh. I was wondering is it possible to reach out a specific square\triangle of the surface explicitly, to gain maximum speed of finding a player height. Well I found that it's possible and it's very simple, so I can now load every .3ds landscape (which is split into squares) in my engine, then I just access needed square with one request. The rest part of that algorithm (i. e. finding an accurate collision point of the player and a triangle inside a specific square) is quite simple. So thanks for your answers)

Share this post


Link to post
Share on other sites

One thing that you may want to consider, if you are not doing it already, is to turn your 3ds model into a gray scale photograph. Each vertex in the model becomes a gray scale value representing height. So, 0 - or black - would be the lowest level on the model and 256 - or white - would be the highest value on the map. Then you can use the photo to load a height array that you can then use to build the actual in game model from as well as consult for terrain height. Something like this is what I have in mind:

 

https://www.youtube.com/watch?v=EnrrsVzkqnc

 

Once you have a gray scale image/texture, there are quite a few tutorials related to loading it into a height map array.

Share this post


Link to post
Share on other sites

This topic is 389 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this