🔒 Locked

averaging elevation

Started by polpoint Sep 27, 2009 at 8:00 PM 4 replies 1.4k views

Original Post

Sep 27, 2009 at 8:00 PM

Hey! I have a 2d-grid of squares. Each square contains it's own grid of lets say 11x11 squares. Every square also has an elevation value. I want to average out the elevation of the little squares within one of the larger squares with the surrounding larger squares elevations. Basically I want the middle small square to equal it's large square's elevation and the little squares surrounding that to gradually equal 1/2 the dif between the original big square's elevation and the neighbor big square's elevation while taking into account at least 2 of the other 7 neighboring large square's elevation. What sorts of solutions are available to solve my problem? [Edited by - polpoint on September 28, 2009 6:41:54 PM]

sdndsjnsdkjsdn

Sep 28, 2009 at 1:38 AM

gaussian blurring

Witchcraven

Sep 28, 2009 at 1:55 AM

I may be not understanding you quite right, but what you are describing sounds similar to the the solution to laplace's equation. There is a way to calculate it called the method of relaxation I think, you may be able to adapt it to your needs. There is a lot of math jargon surrounding it, however the actual algorithm is conceptually not too difficult. Tomorrow when I am not tired I can try to describe it if needed.

Hodgman

Sep 28, 2009 at 2:03 AM

So you've got a data set something like this:

+---0,0---+---1,0---+|? ? ? ? ?|? ? ? ? ?|...|? ? ? ? ?|? ? ? ? ?|...|? ? A ? ?|? ? B ? ?|...|? ? ? ? ?|? ? ? ? ?|...|? ? ? ? ?|? ? ? ? ?|...+---0,1---+---1,1---+|? ? ? ? ?|? ? ? ? ?|...|? ? ? ? ?|? ? ? ? ?|...|? ? C ? ?|? ? D ? ?|...|? ? ? ? ?|? ? ? ? ?|...|? ? ? ? ?|? ? ? ? ?|...+---------+---------+|   ...   |   ...   |...

Your problem is that you only know the values A,B,C,D, and want to interpolate these values to figure out what to put in all the '?' squares.

The easiest approach is bilinear interpolation.

For example, lets look at the "?" right above "C".
Find the distances from this cell to the nearest interpolation points (i.e. A,B,C and D).

Dist to A = 4Dist to B = ~6.4 (4 up, 5 across)Dist to C = 1Dist to D = ~5.09 (1 down, 5 across)

Now we can compute the value to put in this cell by performing a weighted average.

We want further away samples to have lower weights, and closer ones to have higher weights - so we inverse the distances (so smaller distances have larger values than bigger distances).

Inverse Dist to A = 1/4Inverse Dist to B = 1/6.4Inverse Dist to C = 1/1Inverse Dist to D = 1/5.09

To convert these into weights to use in a weighted-average, we need to normalise the values (i.e. make it so if we add them all together, we get 1.0).

SumOfDistances = 1/4 + 1/6.4 + 1/1 + 1/5.09 = 1.6Weight for A = 1/4    / 1.6 = 0.156Weight for B = 1/6.4  / 1.6 = 0.098Weight for C = 1/1    / 1.6 = 0.625Weight for D = 1/5.09 / 1.6 = 0.123Interpolated value = A*0.156 + B*0.098 + C*0.625 + D*0.123

polpoint

Sep 28, 2009 at 9:57 AM

Hodgman, that is basically what I was picturing, but it seems so much easier the way you wrote it out than the way I was envisioning it. Thanks!

polpoint

Sep 28, 2009 at 1:11 PM

ok - now I am having trouble with implementation:

	for(int pix = 0; pix < RMAP_X; pix++)	{		for(int piy = 0; piy < RMAP_Y; piy++)		{			quadrant = -1;			if(pix < (halfRMAP_X) && piy <(halfRMAP_Y))			{				quadrant = 0;			}			else if(pix >= (halfRMAP_X) && piy < (halfRMAP_Y))			{				quadrant = 1;			}			else if(pix < (halfRMAP_X) && piy >= (halfRMAP_Y))			{				quadrant = 2;			}			else if(pix >= (halfRMAP_X) && piy >= (halfRMAP_Y))			{				quadrant = 3;			}			//find the percentages !			//now we interpolate between the current square and three of it's neighbors.			if(quadrant == 0)			{				//nw				//get the elevations of the west, north & nw				float wDist = 1 / (linearDist(pix, piy, halfRMAP_X + pix, halfRMAP_Y - piy));				float nDist = 1 / (linearDist(pix, piy, halfRMAP_X - pix, halfRMAP_Y + piy));				float nwDist = 1 / (linearDist(pix, piy, halfRMAP_X + pix, halfRMAP_Y + piy));				float centDist = 1 / (linearDist(pix, piy ,halfRMAP_X - pix, halfRMAP_Y - piy));				float sum = wDist + nDist + nwDist + centDist;				wDist = wDist / sum;				nDist = nDist / sum;				nwDist = nwDist / sum;				centDist = centDist / sum;                                //this is so I can check on the values				ddp.str("");				ddp<<wDist<<","<<nDist<<","<<nwDist<<"["<<centDist<<"]-("<<pix<<","<<piy<<")-"<<sum;				setMess(ddp.str());                                           //set the elvation				world.wMap[wX][wY].area.aMap[aX][aY].region.rMap[pix][piy].elevation = nw*nwDist + n*nDist + w*wDist + world.wMap[wX][wY].area.aMap[aX][aY].region.baseHt*centDist;							}		}	}

float linearDist(float x1,float y1,float x2,float y2){  float dx = x2 - x1;  float dy = y2 - y1;  return sqrt(dx*dx+dy*dy);}

I am getting results like this (in the nw quadrant of square 1,1):
if square 1,1's elevation == 4

+---0,0---+---1,0---+
|? ? ? ? ?|? ? ? ? ?|...
|? ? ? ? ?|? ? ? ? ?|...
|? ? 3 ? ?|? ? 9 ? ?|...
|? ? ? ? ?|? ? ? ? ?|...
|? ? ? ? ?|? ? ? ? ?|...
+---0,1---+---1,1---+
|? ? ? ? ?|2 2 2 ? ?|...
|? ? ? ? ?|2 3 2 ? ?|...
|? ? 5 ? ?|2 2 2 ? ?|...
|? ? ? ? ?|? ? ? ? ?|...
|? ? ? ? ?|? ? ? ? ?|...
+---------+---------+
| ... | ... |...

Topic Locked

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