🔒 Locked

Formula Needed

Started by CsharpNewbie Jul 10, 2006 at 1:35 PM 6 replies 850+ views

Original Post

Jul 10, 2006 at 1:35 PM

Hello Everyone, Hopefully this is a simple question, I am looking for a formula that will take 5 vertices (4 are points on a terrain, 1 is the object) and spit out what height the object should be at. For example, lets say I have the following points on my terrain: (1,1,1), (2,1,1), (1,2,3), and (2,2,2). If the object is at point (1.2,1.3,1) I need the height to be adjusted correctly. Any suggestions?

deathkrush

Jul 10, 2006 at 1:42 PM

You really want to have 3 vertices for the terrain and 1 for the object. Calculate the triangle's normal and use this formula. Then you can move the object down by that distance.

EDIT: I suggest keeping two sets of normals, one set is per-vertex normals used for rendering and another set is per-face normals used for calculations. That way you don't need to waste CPU cycles calculating normals all the time.

CsharpNewbie

Author

CsharpNewbie

Jul 10, 2006 at 1:49 PM

So instead of finding the 4 closest vertices to my object, just find the closest 3? Also, I'm not familar with "normals", any suggestions on good reading material?

deathkrush

Jul 10, 2006 at 3:01 PM

The reason why you want 3 vertices is because they are always guaranteed to form a plane. With 4 vertices you never know. A normal is basically a vector perpendicular to a plane. It could be easily found by using the vector cross product.

If we have 3 points A, B and C, use point-point subtraction to find vectors u and v:

u = B-A
v = C-A

Then, the normal vector to the plane ABC can be calculated as:

n = u * v (cross product)

EDIT: Wikipedia Article, MSDN article

EDIT: This of course doesn't take into account the fact that there is gravity.

CsharpNewbie

Author

CsharpNewbie

Jul 11, 2006 at 9:45 AM

Okay, so should this code work then?

Close is an array of the 3 closest points, boxpos is the position of the box that is moving.

u = close[1].Position - close[2].Position ;
v = close[2].Position - close[0].Position ;
plane = Vector3.Cross(u, v);
boxpos.Z = Vector3.Dot(close[0].Position , plane);

I'm not sure if using close[0].Position is acceptable as being on the plane, since its one of the points that make up the plane, do I need to use a point that is actually on the plane instead of one of the vertices that make it up?

haegarr

271

haegarr

Jul 11, 2006 at 10:24 AM

The following code snippet is a solution:

/**results in the triangularly interpolated height at \a dx \a dz. The integerparts of the location are used as indices to the tile of the height field,while the fractional parts are used to denote the relative location inside thetile. The triangulation of the tile is done by using a diagonale from theupper-left corner to the lower-right corner.\param dx the x axis related component of the position.\param dz the z axis related component of the position.*/float interpolated(float dx,float dz) const {	float y;	// isolating the integral parts used as indices into the height map	const uint32_t ix = int(dx);	const uint32_t iz = int(dz);	// isolating the fractional parts used as relative location on the tile	dx -= ix;	dz -= iz;	// the (diagonale) corners that are used for both tris	const float ha = _height[ix][iz+1];	const float hd = _height[ix+1][iz];	// if on the lower-left tri ... else on the upper-right tri ...	if(dx+dz<1) {		const float hc = _height[ix][iz];		y = ha*dz + hc*(1.0f-dx-dz) + hd*dx;	} else {		const float hb = _height[ix+1][iz+1];		y = ha*(1.0f-dx) + hb*(dx+dz-1.0f) + hd*(1.0f-dz);	}	// done	return y;}

It assumes a height field (your terrain uses such a thing, as it seems) in x-z directions stored in _height[][]. dx and dz are the position co-ordinates on the height field, ranging from 0 to W+1 (if W is the count of tiles in x direction) and from 0 to H+1 (if H is the count of tiles in z direction), resp. y is the resulting interpolated height. The tiles are assumed to be build by 2 tris, so that the tearrain looks like build of tri strips.

deathkrush

Jul 11, 2006 at 11:54 AM

Quote:
Original post by CsharpNewbie
Okay, so should this code work then?

Close is an array of the 3 closest points, boxpos is the position of the box that is moving.

u = close[1].Position - close[2].Position ;
v = close[2].Position - close[0].Position ;
plane = Vector3.Cross(u, v);
boxpos.Z = Vector3.Dot(close[0].Position , plane);

I'm not sure if using close[0].Position is acceptable as being on the plane, since its one of the points that make up the plane, do I need to use a point that is actually on the plane instead of one of the vertices that make it up?

u = close[1].Position - close[2].Position ;
v = close[2].Position - close[0].Position ;
normal = Vector3.Cross(u, v);
normal = normal / normal.Length(); //normalize
distance = Vector3.Dot(boxpos - close[0].Position, normal); //find the distance from the box to the plane
boxpos = boxpos - normal * distance; //move the box along the normal towards the plane

close[0].Position is on the plane because it's one of the points that define the plane.

This is just a general solution that I got from the top of my head, haegarr's solution will work better if your terrain is organized like a height field. If you want the real solution, look into ray-casting gravity vectors from a point onto the terrain polygons to find the closest intersection and then instead of using the normal, move the point along the gravity vector.

SuperNerd

Jul 11, 2006 at 5:23 PM

This is what I came up with.

A Equation For a Plane
Ax + By + Cz + D = 0

Convert three points in the triangle to a plane.
normal = Cross(Point1 - Point2, Point1 - Point3)
A = normal.x
B = normal.y
C = normal.z
D = -(A(Point1.x) plus B(Point1.y) plus C(Point1.z))
(I can't seem to get the plus sign to show up)

Find the Y position of the object on the plane
Object.y = (A(Object.x) plus C(Object.z) plus D) / -B

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.