#### Archived

This topic is now archived and is closed to further replies.

# Heightmap for Powerful Minds!

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

## Recommended Posts

I have a terrain heightmap generated via a simple plasma algorithm. Now, I need to improve my algorithm for determining the height of a specific point on that grid. For example, if I use triangular polygons to connect the grid points, I may need to calculate the height of a point that is within one of the polygons. I''ve made some progress in a few directions here, but suspect there is some good solution in one of your powerful minds.

##### Share on other sites
Do barrycentric coordinates help me here? I can determine what triangle I''m in by getting the closest point, and the location relative to it. I can then weight my proximity to the various sides, and get a barycentric coordinate. This seems like a weak approach.

Anyone solve this basic math problem cleanly?

##### Share on other sites
Well, I'm not gonna go too much into this, but basicly you need to do two things.. First, getting the four height field values that define the particluar quad in your height field where the test point falls onto, then using these four values to do linear interpolation much like blending colors, but in this case you're blending height values.. you can read up on polygon shading if you wanna figure out how that works.. anyhow, I'm just gonna post the code..

enjoy..

#define HF_SIZE 80float heightField[HF_SIZE][HF_SIZE];float heightFieldNormal[HF_SIZE][HF_SIZE][3];float terrainMin[2], terrainMax[2], terrainSpan[2];  // these are all x, z pairsvoid getHeight(float x, float z, float *height, float *normal) {	int i, j;	float ux, uy, uz, vx, vy, vz;	// check if outside terrain	if ((x < terrainMin[0]) || (x > terrainMax[0]) || (z < terrainMin[1]) || (z > terrainMax[1])) {		*height = 0.0f;		if (normal != NULL) {			normal[0] = 0.0f;			normal[1] = 1.0f;			normal[2] = 0.0f;		}		return;	}	// get x and z into grid quad's coordinates	x -= terrainMin[0];	z -= terrainMin[1];	i = (int) ((float) (HF_SIZE - 1) * x / terrainSpan[0]);	j = (int) ((float) (HF_SIZE - 1) * z / terrainSpan[1]);	x -= (float) i * terrainSpan[0] / (float) (HF_SIZE - 1);	z -= (float) j * terrainSpan[1] / (float) (HF_SIZE - 1);	x /= terrainSpan[0] / (float) (HF_SIZE - 1);	z /= terrainSpan[1] / (float) (HF_SIZE - 1);	// interpolate height	ux = heightField[j][i] + (heightField[j+1][i] - heightField[j][i]) * z;	vx = heightField[j][i+1] + (heightField[j+1][i+1] - heightField[j][i+1]) * z;	*height = ux + (vx - ux) * x;		// interpolate normal	if (normal != NULL) {		ux = heightFieldNormal[j][i][0] + (heightFieldNormal[j+1][i][0] - heightFieldNormal[j][i][0]) * z;		uy = heightFieldNormal[j][i][1] + (heightFieldNormal[j+1][i][1] - heightFieldNormal[j][i][1]) * z;		uz = heightFieldNormal[j][i][2] + (heightFieldNormal[j+1][i][2] - heightFieldNormal[j][i][2]) * z;		vx = heightFieldNormal[j][i+1][0] + (heightFieldNormal[j+1][i+1][0] - heightFieldNormal[j][i+1][0]) * z;		vy = heightFieldNormal[j][i+1][1] + (heightFieldNormal[j+1][i+1][1] - heightFieldNormal[j][i+1][1]) * z;		vz = heightFieldNormal[j][i+1][2] + (heightFieldNormal[j+1][i+1][2] - heightFieldNormal[j][i+1][2]) * z;		normal[0] = ux + (vx - ux) * x;			normal[1] = uy + (vy - uy) * x;			normal[2] = uz + (vz - uz) * x;		}}

Edited by - bpj1138 on December 26, 2001 11:12:47 PM

##### Share on other sites
You should be careful that quad interpolation as bpj1138 has put it forth is ill-defined; it is dependant upon the direction in which you choose to do the interpolation.

If you are rendering your height field as triangles, it is also the case that this interpolation won''t match the thing you are displaying.

You need to decide carefully how you are getting triangles from your height field (usually, each quad is split into 2 triangles, but people differ as to whether you divide them all the same way, or in alternating directions). Once you have that, you just figure out which half of the quad your point is in, get the plane equation for the triangle that makes up that half of the quad, and solve the plane equation using the (x, y) of that point to get z.

-Jonathan.

##### Share on other sites
He''s right, it''s not the most accurate interpolation, and the "direction" he''s talking about is how the two triangles that make up a quad bend..

What this is useful for is two-fold.. if your terrain model is "adaptive", meaning, areas of high complexity are given more polygons and flat areas are modeled with less polygons (bryce does this very well), you don''t need to find which polygon you need to use to get the height measurement, which would be very time consuming "point inside polygon" code with possibly coarse culling done first. The algorithm immediately goes to the height field quad that''s needed with those interger calculations (i, j) in the grid....

Second, your terrain model might be very detailed, but you don''t need so much detail for the height field, also a lot of detail might make the thing walking on it jump up and down (due to too much detail).. generating the height field smooths it out basicly.. you can also vary the number of grid points, so if you''re getting errors, just increase the number of points as there is no performance penalty for doing so, just memory usage..

l8r on..

--bart

##### Share on other sites
Wouldn''t a plane equation be helpful here?

If A*x + B*y + C*z + D = 0.0 and you have x and y, z should be pretty easy to calculate.

I think A, B and C are your normal for your triangle and D is calculated from a known point (say point #1). Store these four values with each triangle and you should be able to calculate your z pretty easily.

But I''m a little foggy on this, so maybe I''m way off. Anybody?

I suppose there''s still difficulty in finding which triangle you''re in...

##### Share on other sites
OK. Thanks - this is super helpful.

My terrain has no LOD code and is not adaptive yet, so the routine for determining which polygon profiles to be almost negligible in time. Also, in my case, each polygon is a flat quad for now, so the component triangles won''t bend (even though it''s actually composed of a triangle strip).

So, I think this makes your advice very good for my case - we''ll see how it goes!

##### Share on other sites
Hey.. no problem.. glad to be of help..

btw, when I posted the message, I realized there are some obvious optimizations, like putting "i + 1" and "j + 1" into some variables, unless the compiler already optimizes that.. i dunno..

also, terrainSpan[0] / (float) (HF_SIZE - 1) is just the quad size so you should compute that along with terrain span..

l8r..

--bart

• 11
• 18
• 12
• 22
• 9
• ### Forum Statistics

• Total Topics
631397
• Total Posts
2999822
×