I am creating a terrain engine, and have come across a problem when representing a height of a cell within the map using 4 floating values. I.e. the values could be: 100 ----------- 90 | | | 20 ------------ 10 to represent the heights of each corner of the tile. So far so good. But I really want to know what the values are at a runtime defined point within the square too. Passing in a value from 0.0f to 1.0f for vertical and horizontal fraction parts for the location in the sqaure I want to find the value at that point. I.e. 100 ----------- 90 | | .x | 20 ------------ 10 (.x) where x is at point 0.3 by 0.2 within the box. How do I calculate the number of x !!! Sorry im not great at maths, not on this problem anyway #ifndef _DIRECTX PostQuitMessage(0); #endif [edited by - MatthewEva on October 23, 2002 7:27:39 AM]

Well, in this case the points are all coplaner, i.e. (20-100)=(10-90) and (90-100)=(10-20). So dz.horz=(90-100)*u and dz.vert=((20+dz.horz)-(100+dz.horz))*v. The height of the point (u,v) is 100+dz.horz+dz.vert. That is assuming (0,0) is the top left corner and (1,1) is the bottom right. If the points are not coplaner it still works the same. You have to split the square into two triangles. You have two choices depending upon which way the diagonal runs. You then have to determine which triangle the point lies in by comparing the u and v values to each other. Then your dz.horz and dz.vert are calculated from the horzontal and vertical edges of the triangle the point is in. Also you have to go relative to a point in the triangle.

That was a needlessly complicated way to calculate dz.vert since ((20+dz.horz)-(100+dz.horz))=20-100

[edited by - LilBudyWizer on October 23, 2002 3:49:26 PM]

Many thanks for your very timely reply. I appreciate it. I have understood now that I need to virtualy split the square in half to make two triangles.

so we could use the values that are non coplanar:

20------0
| /
| /
|/
50------100

Say I use a diagonal from bottom left to top right if I make up two arbitrary points in that square, say u=0.4 and v=0.3 I can easily distinguish on paper where this point is, however if I apply the calculation you mentioned we have:

(Previous Post)
{
dz.horz=(90-100)*u and dz.vert=((20+dz.horz)-(100+dz.horz))*v)
}

changes in this exampe to:

dz.horz = (0-20)*u abd dz.vert = ((50+dz.horz)-(20+dz.horz)

which means :

dz.horz = -8
dz.vert = 30

I stopped here, because I realized I am making a funtamental mistake, not taking into consideration the triangles. Sorry for sounding silly. Am I right in assuming that the value for location u=0.4 and v=0.3 in the above example is the sum of the calculations. ie. dz.horz+dz.vert = 22 !!


#ifndef _DIRECTX
PostQuitMessage(0);
#endif

[edited by - MatthewEva on October 23, 2002 4:33:00 PM]

No, dz.vert is the change in z as you from from v=0 to v=1. You are only going to .3 so it is (50-20)*.3=30*.3=9. The calculation I gave for dz.vert was needlessly complicated since the dz.horz cancels out, i.e. dz.horz-dz.horz=0. So you go down by 8 as you move from (0,0) to (.3,0) then rise by 9 as you go from (.3,0) to (.3,.4) giving a total change of 1 as you go from (0,0) to (.3,.4). That is 1 higher than (0,0) which is 20 so (.3,.4) is at a height of 21.

If you are familar with vectors then what you are doing is taking a linear combination of vectors. One vector is v1=(1,0,0)-(0,0,20)=(1,0,-20) and the other is v2=(0,1,50)-(0,0,20)=(0,1,30). Your point of interest is then (0,0,20)+u*v1+v*v2=(0,0,20)+.4*(1,0,-20)+.3*(0,1,30)=(0,0,20)+(.4,0,-8)+(0,.3,9)=(.4,.3,21). Any point in a plane can be found by a point in a plane plus multiples of two independant vectors within that plane. That is basically how you plot a point on a grid. The point (x,y) is (0,0)+x*(1,0)+y*(0,1).

That seems to work for me fine when im using the square above. I have written a program using the following grid:

10 --------- 50
|
|
|
|
|
30 -------- 200

and when interrogating the points within the grid at every 0.25 I get:

10.000000 20.000000 30.000000 40.000000 50.000000
15.000000 25.000000 35.000000 45.000000 55.000000
20.000000 30.000000 40.000000 50.000000 60.000000
25.000000 35.000000 45.000000 55.000000 65.000000
30.000000 40.000000 50.000000 60.000000 200.000000

as the results. It seems at a glance that the points at topleft,topright and bottomleft are working great, however, the calculation does not use the bottomright value to weight the points at that position.

[edited by - MatthewEva on October 24, 2002 3:32:59 AM]

My function is below where m_fTL,m_fTR,m_fBL and m_fBR are the topleft, topright, bottomleft and bottomright weights of the grid.

FLOAT CCoordinate::GetCoordinates(FLOAT fx,FLOAT fy)
{
// Validate Coordinate
if (fx > 1.0f) fx = 1.0f;
if (fy > 1.0f) fy = 1.0f;

// Return If On Border
if (fx == 0.0f && fy == 0.0f) return m_fTL;
if (fx == 1.0f && fy == 0.0f) return m_fTR;
if (fx == 0.0f && fy == 1.0f) return m_fBL;
if (fx == 1.0f && fy == 1.0f) return m_fBR;

// Perform Calculation
FLOAT fVert = (m_fBL-m_fTL)*fy;
FLOAT fHorz = (m_fTR-m_fTL)*fx;

return m_fTL + (fVert+fHorz);
}

[edited by - MatthewEva on October 24, 2002 3:35:24 AM]

Looks right to me. All that is left is splitting it into two triangles. I don''t think there is a way to decide way is best considering just one grid square in isolation. Rather you are deforming the terrain in some manner so if z is the height then you have some function z(x,y) with step sizes dx and dy. Your corner heights are then z(x,y), z(x+dx,y), z(x,y+dy), z(x+dx,y+dy). Depending upon which way the split runs the center points height will be (z(x,y)+z(x+dx,y+dy))/2 or (z(x+dx,y)+z(x,y+dy))/2. You can evaluate what it should actually be with z(x+dx/2,y+dy/2) and use that to decide which direction for the split will make the calculated height closest to the actual height. The in the editor you let the user change the split if they want. No matter how you do it there will be cases where you wished it went the other way.

Also one thing to consider is a bitmap representation of a height field. Basically you just use the color to represent the height. You take a bitmap that represents a top down view of your grid. You then calculate the height for each pixel and then convert it to a color. The easiest is if your heights just range from 0 to 255 and you compose a 24 bit color with red=green=blue=height. It makes a nice way to get a visual representation of the terrain before you put the actual 3D render in place. It also works well for a view to use while sculpting the terrain. As you get further into you will most likely have to scale the color, i.e. not limit the height to 0 to 255, you may need to use multiple color scales for differant ranges and let the user select the minimum and maximum heights that are mapped. As an example the mapping for a mountain range doesn''t work as well for a rolling plane.