Sign in to follow this  
QQemka

Intersect ray with heightmap

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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;

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this