# Intersect ray with heightmap

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

## Recommended Posts

Hello. I got fully working ray picking, which tells me if ray hit an object. But using D3DXBoxBoundProbe tells me "yes" or "no", but does not give the XYZ of intersection point. Now i need to sleect the point on the terrain to make my unit move to given XYZ on right click press.

The only solution for the heightmap which comes to my mind is to take every triangle, then count XYZ of intersection ray - plane (plane which contains the triangle) and then check if the point is inside the triangle. It seems not too optimal for me, are there better solutions?

Greetz

##### Share on other sites

One alternative to a brute force method would be to reduce the set of triangles to possible candidates. Another possibility is to use approximations first and compute more costly methods only if the approximation says so. For example:

A height map has a regular grid of z samples in the x/y plane. When seen from above, it looks like a regular arrangement of quadratic cells. Each cell has 8 neighbors (or less if being placed at an edge of the map). The ray, also seen from above, passes through these cells. So you can handle this as a 2D problem first: Start at the cell which contains the camera, calculate through which of the 4 edges the ray leaves the cell, determine the neighboring cell at that edge, and continue the same from there. In this way yo can iterate those cells that are touched by the ray. Now, before hopping to the next cell, determine whether the ray passes through the ground of the cell. If not, then go to the next cell; otherwise the cell of interest is found.

The ground test can be optimized, too. If you have the minimum and maximum height value of the current cell, and you have the entry and exit heights of the ray, then a first test would be a simple interval overlapping test (like a 1D bounding volume hit). Notice that the entry height of a cell is the same as the exit height of the previously visited cell, so passing this value would be beneficial. Notice that the entry / exit heights again are computed by ray / plane intersections, but the planes are axis aligned and hence the intersections are easier to calculate.

##### Share on other sites

I suppose you could frustum cull the triangles with the frustum built arund the ray as an "elongated box" (6 planes, maybe the Zfar plane can be left out to get an infinite frustum), and then use D3DXIntersectTri() (https://msdn.microsoft.com/en-us/library/windows/desktop/bb172885%28v=vs.85%29.aspx) on the remaining triangles. Probably not the fastest way though, but if it's only for picking I think it should be okay?

Edit: Maybe you can treat the ray as a 2D ray (XZ), collect all close-by triangles along the ray on your grid (they should be easy to locate in your triangle list if you know the 2D coord) and then run D3DXIntersectTri() on the collected list?

Edited by vinterberg

##### Share on other sites

The final result would be movement like starcraft or warcraft3 have. You press right click with selected unit and it moves right there. Those games, i see, are not using heightmaps, because there are vertical terrain walls. Maybe there is alternative to this way of handling terrain, fitting RTS type of game?

Greetz

Edited by QQemka

##### Share on other sites

The way i did terrain picking was to render the terrain to a pick buffer, but render the UV coordinate out of the pixel shader in the R and G channels and output the height in the B channel. Then you simply get the uv coordinates from the pick buffer and transform it back into the world position. you know how big your heightmap is, where your terain is in the world and so on.

This works for any arbitrarily complicated heightmap terrain.

Edited by Dave

##### Share on other sites

Hey there this here works fine for RTS types terrain and cammera views.

.


D3DXVECTOR3 RT = D3DXVECTOR3(0.0f, 0.0f, 0.0f);

// Compute the vector of the pick ray in world space
//D3DXVECTOR3 v;
// Get the inverse view matrix
D3DXMATRIX matView;//= *g_Camera.GetViewMatrix();
gpCamera->getViewMatrix(&matView);

D3D10_VIEWPORT vp;
vp.TopLeftX = 0;
vp.TopLeftY = 0;
vp.Width    = width;
vp.Height   = height;
vp.MinDepth = 0.0f;
vp.MaxDepth = 1.0f;

D3DXMATRIX Identityworld;
D3DXMatrixIdentity( &Identityworld );

// Put mouse coordinates in screen space
D3DXVECTOR3 mnear = D3DXVECTOR3(ptCursor.x, ptCursor.y, 0);
D3DXVECTOR3 mfar = D3DXVECTOR3(ptCursor.x, ptCursor.y, 1);
// Transform points to world space

D3DXVec3Unproject(&mnear,
&mnear,
&vp,
pmproj,
&matView,
&Identityworld);

D3DXVec3Unproject(&mfar,
&mfar,
&vp,
pmproj,
&matView,
&Identityworld);

// near = DX.Vector3.Unproject(near,m_device.Viewport, m_device.Transform.Projection, m_device.Transform.View, DX.Matrix.Identity);
// far = DX.Vector3.Unproject(far,m_device.Viewport, m_device.Transform.Projection, m_device.Transform.View, DX.Matrix.Identity);
// Find Y Intercept
D3DXVECTOR3 direction = mfar - mnear;
if (mfar.y < 0) // if your mouse ray ends below XZ Plane
{
float yFactor = -mnear.y / direction.y;
RT = mnear + direction * yFactor; // zeroWorldPoint.X and zeroWorldPoint.Z contain XZ Plane Intercept
}
else
return RT;//error

//make sure we are not out of bounds
int hw = mWidth * 0.5f;
int hd = mDepth * 0.5f;

if(RT.x < -hw )
RT.x = -hw;
else
if(RT.x > hw)////how big the map is
RT.x = hw;

if(RT.z < -hd )
RT.z = -hd;
else
if(RT.z > hd)////how big the map is
RT.z = hd;

//we will need to trace the rays direction back up to check height values on the height map

float heighmapheight	= 0.0f;
heighmapheight	= getHeight(RT.x, RT.z);

direction = mnear - mfar;//revers the direction so we move towards the ground
//RT.y = heighmapheight;
D3DXVec3Normalize(&direction, &direction);
while(RT.y - heighmapheight < 10)
{
RT += direction * 20;
//float yFactor = -mnear.y / direction.y;
//RT = mnear + direction * yFactor; // zeroWorldPoint.X and zeroWorldPoint.Z contain XZ Plane Intercept
heighmapheight	= getHeight(RT.x, RT.z);
}

return RT;


• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 13
• 12
• 15
• 11
• 12
• ### Forum Statistics

• Total Topics
634152
• Total Posts
3015842
×