   Heightmap Intersection
  I have a height map terrain, and I wish to know accurately the height at any point on it.//   x and z both increment by 1 at each step in the height mapfloat GetHeight(float x, float z);I''m having a little difficulty trying to find the height when it is not on the border of a triangle, but within. I am not after some random code, more so a mathematical or talked thru solution.Thanks,Bangz.http://www.bangz.co.uk 
  OK, the mathematical solution. The best way to find out the height at any point on your terrain0 is to take your x and z coords, and create a ray from them, where ray start = (x, fHighestTerrainPoint, z) and ray end = (x, fLowestTerrainPoint, z). Then, you can do a polygon/line intersection test on each triangle in your terrain, to see which triangle is intersected by the ray. Once you've located that triangle, it's a simple matter to find out the exact point at which the ray intersects the triangle. Extract the y component of this, and hey presto, you have the exact height. There's a good polygon/line intersection tutorial at www.gametutorials.com (it's on one of the OpenGL tutorial pages), but if you want, I'll post some of my code for ray-based picking.There are obvious optimizations to this method. You could locate the triangles near to the x and z coords which are likely to be intersected, and only test them, for example.   Windows 95 - 32 bit extensions and a graphical shell for a 16 bit patch to an 8 bit operating system originally coded for a 4 bit microprocessor, written by a 2 bit company that can't stand 1 bit of competition.   [edited by - iNsAn1tY on February 10, 2004 12:05:46 PM];  Sounds like a good idea, I already have code that finds which triangle I am currently in. I was originally trying to do some sort of Trilinear interpolation but it wasn''t working, I think my method was flawed! ;-)Thanks,Bangz. ;  this might be completely silly and overly complicated or wrong, but:let x0,z0 be the corner of your triangle:xdh = height(x1,z0) - height(x0,z0);zdh = height(x0,z1) - height(x0,z0);h = height(x0,z0) + fraction(x)*xdh + fraction(z)*zdh;for every other triangle that would be flipped around.basically the side of the triangle are vectors and scaling them by the fraction of your x,z coords (in this case, as your vertices are 1 unit apart) and adding them should result in a vector from corner to intersection. at least it _looks_ right when i place a few hundred test lines on my terrain. ;  Excellent, I was trying to do something similar to this. I noticed I had a bug somewhere else in my code where I was basically flipping the top and bottom points :-S D''oh!It all works now, here''s the function... For reference to anyone who has this problem in the future!float CTerrain::CalculateYValue(float x, float z){//check rangeif(x<0 || x>this->m_nWidth || z<0 || z>this->m_nHeight)return 0;//Retrieve the points for the current quad we are infloat fTopLeft = m_pData[(int)x + (((int)z+1) * this->m_nWidth)].m_fy;float fTopRight = m_pData[((int)x) + (((int)z+1) * this->m_nWidth) + 1].m_fy;float fBottomLeft = m_pData[((int)x) + (((int)z) * this->m_nWidth)].m_fy;float fBottomRight = m_pData[((int)x) + (((int)z) * this->m_nWidth) + 1].m_fy;float finalHeight = 0;//what we are trying to find//fraction parts of x and zfloat frac_x = x - ((int)x);float frac_z = z - ((int)z);//What triangle are we in? (top right or bottom left)if((frac_x*frac_x + frac_z*frac_z) < ((1-frac_x)*(1-frac_x) + (1-frac_z)*(1-frac_z))){//in bottom left trianglefloat dX = fBottomRight - fBottomLeft;//how the height changes with respect to xfloat dZ = fTopLeft - fBottomLeft;//how the height changes with respect to z//calculate our final heightfinalHeight = dX * frac_x + dZ * frac_z + fBottomLeft;}else{//in top right trianglefloat dX = fTopLeft - fTopRight;//how the height changes with respect to xfloat dZ = fBottomRight - fTopRight;//how the height changes with respect to z//calculate our final heightfinalHeight = dX * (1 - frac_x) + dZ * (1 - frac_z) + fTopRight;}//return our calculated heightreturn ((float)finalHeight);}  Thanks,Bangz.http://www.bangz.co.uk ;  just to say, here is a similar thread on the subjectthis. 