Hi, I''m using the plane equation to move my player up and down the hills of my terrain. It seems to partly work -- whenever the player encounters a hill, it goes up. The problem is that it suddenly jolts a few feet off the ground at the slightest bump in the terrain and becomes suspended in midair. If I continue to move foward, the player will continue to follow the slope, but its feet will not be on the ground unless the terrain is completely level (0). Here is the code to position the player:

void CPlayer::Update (void)
{
	if (m_bWalking)
	{
		// Move player x units forward in the current direction
		m_vPosition.x += cos (m_fRotation) * m_nSpeed;
		m_vPosition.z += sin (m_fRotation) * m_nSpeed;

		// Place player''s feet on the terrain
		m_vPosition.y = g_World.GetHeightAtPoint (m_vPosition.x, m_vPosition.z);
	}
}
 

And here is the code that returns that height of the terrain:

//////////////////////////////////////////////////////////////////////////
// Returns the height of the terrain at the given world coordinates.
//////////////////////////////////////////////////////////////////////////

float CWorld::GetHeightAtPoint (float x, float z)
{
	CVector2 vTile = GetTileAtPoint (x, z);
	CVector3 vNormal = GetTileNormal (vTile.x, vTile.y);

	// Compute the distance from the origin to the tile plane
	float fDist = Dot (-vNormal, GetTilePos (vTile.x, vTile.y));

	// Use the plane equation to get the y of the point on the tile''s plane
	// Plane equation: Ax + By + Cz + D = 0 (ABC = normal, D = dist from origin)
	float y = (0 - vNormal.x * x - vNormal.z * z - fDist) / vNormal.y;

	return y;
}
 

GetTileAtPoint() converts world coordinates to tile coordinates. GetTilePos() returns the position of the upper left corner of the tile in world coordinates. GetTileNormal() returns the normalized normal of the tile. I am calculating y by using simple algebra to transfer Ax, B, Cz, and D to the right side of the equation: y = (0 - Ax - Cz - D) / B It looks like a scaling problem. I have a feeling that I might be calculating D wrong. I didn''t understand its definition real well (origin of what?) so I just copied the line for a book. Any ideas?

Are tiles slanted? If so, does the height in mid-air to which the player suddenly jumps level with the height of the part of the tile from which you''re calculating the height of the terrain? I''m thinking that maybe you''re walking onto the low part of the tile, but the function returns the height of the high part, so your character jumps up to the highest point of the tile, as opposed to the height where it is actually located. What happens if you walk onto a tile that''s slanted the opposite direction from the other side? I''m guessing this isn''t the case if you''re smoothly following the surface of the tile, but just offset some distance above where you should be...

How did you calculate A, B, C and D? Are you sure you''re getting the height from the right tile, and not the one next to where you should be?

Thanks for the quick reply.

The player is pretty high up, higher than any tiles is the vicinity. When I move from a level tile to a slanted one, the character hops about 5 vitual feet in the air as soon as I touch the new tile. If I climb up the slant, the player goes up very quickly (probably 10x faster than the forward move speed).

I''m getting the tile the player is on by:

x = worldx / TILESIZE
y = worldz / TILESIZE

The world is a heightmap, so x and z is always constant. I''m pretty sure the right tile is being checked because the player follows the incline/declines almost perfectly (although like I said there is the scaling problem... if the land below is 1 virtual foot, the player is probably 5 virtual feet up. If the land is 5 feet high, the player is 25 feet up).

I''m getting the tile normal (ABC) by:

normalize (cross (tile.bottomleft - tile.upperleft, tile.upperright - tile.upperleft))

So I''m always getting the normal of the upper left triangle in the tile... not sure if this would be a problem or not.

I think your problem is here:
float fDist = Dot (-vNormal, GetTilePos (vTile.x, vTile.y));

Try changing it to:

float fDist = Dot (vNormal, GetTilePos (vTile.x, vTile.y));

If this was the wrong way round, I think you would experience symptoms similar to what you describe. Unfortunantly, what you have done seems mathematically sound, so I am having trouble convincing myself that this might work (I originally thought you were the wrong way around).

A few more things...
Are you sure your normals are normalized. That is the only thing I can think of for why you should go up so much faster than the terrain goes down. This is assuming the slanted tile is slanted in one direction only. If not, I suggest you try that and see if the ratio of up to down changes.
Another problem you will experience later is if the tiles are curved (i.e. the normals at different corners are different) then you will get a slightly incorrect answer.

your tile should be made of 2 triangles. What you have is an approximation of a rough plane, and that plane could not possibly go through the 4 points (unless they are on the same plane obviously).

What you have to do, is do it the hard way, and test the intersection with the two triangles on the tile. It is not as complicated as it seems, but be careful if you use triangle strips for rendering, as the tile diagonal segment will 'criss-cross' from one tile to the next tile.

For here, I'll assume all the tiles have the same configuration, with a diagonal going from top-left to bottom-right, and NEVER from bottom-left to top-right.

V0      V1+-------+|\      || \  .(x, z) |  \    ||   \ T1||    \  || T0  \ ||      \|+-------+V2      V3

when getting the vectors, you also have to be careful, as there are 1 more vertex per line than there are tiles (two vectors for one tile).

how to extract the tile vectors...

void GetTileVertices(Vector* V, float x, float z){   // size of the map in world coordinates   float Imin = 0.0f;   float Imin = 0.0f;   float Jmax = (TILESIZE * (NUM_TILES_ON_X + 1));   float Jmax = (TILESIZE * (NUM_TILES_ON_Z + 1));   // how far are we inside the map (as a 'percentage').   float t = (x - Imin) / (Imax - Imin);   float u = (z - Jmin) / (Jmax - Jmin);   // bottom left pixel on heightmap corresponding to the bottom left corner of the tile in 3D coordinates   int   i = (int) (t * TILESIZE);   int   j = (int) (u * TILESIZE);   // the 4 corners of the tile in the 3D   float xmin = t * (float) i;   float zmin = u * (float) j;   float xmax = xmin + TILESIZE;   float zmax = zmin + TILESIZE;   V[0] = Vector(xmin, GetHeightmapHeight(i  , j  ), zmin);   V[1] = Vector(xmax, GetHeightmapHeight(i+1, j  ), zmin);   V[2] = Vector(xmin, GetHeightmapHeight(i  , j+1), zmax);   V[3] = Vector(xmax, GetHeightmapHeight(i+1, j+1), zmax);}

now you have the two triangles making the tile, you need to find the two triangle planes

void CalculateNormal(Vector V0, Vector V1, Vector V2, Vector& N, float &d){    Vector E = V1 - V0;    Vector F = V2 - V1;    N = E.Cross(F);    N.Normalise();    d = V0 * N;}

from there, you need to cast a ray to a plane, from the player position and going down, to find it's position on the surface of the triangle.

// plane normal, plane d-param, ray start pos, ray direction, resultbool RayPlaneIntersect(Vector N, float d, Vector P, Vector D, Vector &Q){    float denom = D * N;    // ray parallel to the plane    if (fabs(D * N) < 0.000001f)    {        Q = P;        return false;    }    float t = (d - (P * N)) / denom;    Vector Q = P + D * t;    return true;}

you need to decide which of the two triangles to test. It depends on wich side of the diagonal line the player is

// tri index, vertices of the tile, pos of player int SelectTileTriangle(Vector* V, Vector Pos){    Vector E = V3  - V0;    Vector D = Pos - V0;    if (fabs(D.z) < 0.000001f)         return 0;    float s = fabs(E.x) / fabs(E.z);    float t = fabs(D.x) / fabs(D.z);    if (t > s)    {        return 1;    }    return 0;}

now, you put everything together

Vector V[4];Vector N;float  d;Vector Q;GetTileVertices(V, PlayerPos.x, PlayerPos.z);int i = SelectTileTriangle(V, PlayerPos);if (i == 0)   CalculateNormal(V0, V3, V1, N, d);else   CalculateNormal(V0, V2, V3, N, d);RayPlaneIntersect(N, d, PlayerPos, Vector(0, -1, 0), Q);PlayerPos.y = Q.y;    

now, I don't know how this works for you, but it seems that you are using heighmaps vertices as tile heights, when they should be tile CORNERS heights. Hence the '+1' when extracting the tile corners, and diagonal malarkey.

also, the only thing you have to change, for when the diagonal is of the other kind (bottom-left to top right), is to swap around vertices 2 and 3 at the end of the first function. Be careful if you use the triangles for other things, as the triangles will have their diagonals inverted (going down instead of up).

If you use strips, in that function, you can detect if a tile is using a top-left/bottom-right diagonal or the other by looking at if the variable 'i' is odd or even. Every even columns should be the same kind, and every odd columns should be of the other kind. Which one? Well, you have to test both and see what works.

[edited by - oliii on June 27, 2003 10:05:58 PM]

I think the problem might have to do with how you''re calculating D. The ''distance from the origin'' is the vertical distance y, of the plane, above the point on the xz plane at point (0,0).

It''s equivalent to b in the equation for a line, y = mx + b. when x = 0, y = b, whereas for the plane, when x = 0 and z = 0, y = D.

I think you''re calculating D = fDist as the distance in the xz plane from the point (0,0) to the tile, which is not correct.

This, I think, would explain the strange height jump.

If this is the case, then equally slanted tile located in different places should cause different height jumps...

To get the correct D, select a corner of your tile and use the x and z positions and the known y and normal vector and solve for D.

oliii- I originally coded collision using a plane test for individual triangles like you showed, but the function I wrote to check if the point was in the triangle was terribly long, and I never managed to get it to work right (it used edge planes, sort of like checking for objects in the frustum). Your version is a lot less complex and it works well. I think my best bet is to use triangle tests instead of quad tests, even though it isn''t as easy I don''t think I could ever get a quad test to work, unless I forced all four points to be on the same plane like you said.

Long story short, my character finally has his feet on the ground. Thanks to all who helped.

np

np