Sign in to follow this  

Ray to terrain intersection

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Im a little confused at how you can compute a ray to terrain intersection. The method i use is as follows each point in the terrain contains a sphere, i loop through each sphere and cast a ray to see if the mouse intersects the sphere and set that point to be the position im intersecting with. I made this up myself as I wasnt sure of another method but its very slow when your searching the whole of the terrain for a point. How can I convert the on-screen mouse coordinates to terrain coordinates in a way that isnt slow? I was talking to a friend he mentioned casting a ray to terrain intersection but im a noob when it comes to this kinda stuff. Cheers Ash.

Share this post


Link to post
Share on other sites
Your approach is quite interesting, but slow :)
That's what I do:
1. Project your terrain and the ray onto a 2d plane (i.e. x-z plane, set the y-axis[=height] to 0).

Well we reduced your problem to 2d, all we need to do now is to trace your ray:

2. Apply a 2d line-draw algorithm, each 'filled' square need to be tested.

3. To test a square you apply a ray-triangle(2x) or ray-quad-detection algorithm in your original 3d space.

Optimize at will :)

--
Ashaman

Share this post


Link to post
Share on other sites
The "line draw" algorithm you want is called DDA, DO NOT use scan conversion line draw routines such as Bresenham, they don't intersect all cells through which the ray traverses.

If you think about it you should never move diagonally (which Bresenham can do) the chances of your ray being intersecting absolutely spot on the exact corner of a cell, well, it's almost impossible with floating point precision issues.

When I've solved this problem in the past I used a hierarhcy of cells with bounding boxes. Say for example my height field is 256x256 (low I know) I would traverse first at 4x4 and then 16x16 checking if the ray should consider any of the higher resolution by considering the maximum height in each cell.

EDIT: Have a quick look at this to visualise the reason you need a DDA
http://groups.csail.mit.edu/graphics/classes/6.837/F03/lectures/14_line_clip_rasterization.ppt

Share this post


Link to post
Share on other sites
Your describing "ray picking", and "ray triangle intersection". Google can help you with those.

If your using directX, look at the pick example. They have a very fast, and very accurate ray intersect triangle function shown here:

you pass in start position, ray dir, and the 3 vertices of a triangle. It computes t,u,v.

intersection point is startposition + t*raydir
the u,v are the texture coordinates of the intersection point.



bool IntersectTriangle( const D3DXVECTOR3& orig, const D3DXVECTOR3& dir,
D3DXVECTOR3& v0, D3DXVECTOR3& v1, D3DXVECTOR3& v2,
FLOAT* t, FLOAT* u, FLOAT* v )
{
// Find vectors for two edges sharing vert0
D3DXVECTOR3 edge1 = v1 - v0;
D3DXVECTOR3 edge2 = v2 - v0;

// Begin calculating determinant - also used to calculate U parameter
D3DXVECTOR3 pvec;
D3DXVec3Cross( &pvec, &dir, &edge2 );

// If determinant is near zero, ray lies in plane of triangle
FLOAT det = D3DXVec3Dot( &edge1, &pvec );

D3DXVECTOR3 tvec;
if( det > 0 )
{
tvec = orig - v0;
}
else
{
tvec = v0 - orig;
det = -det;
}

if( det < 0.0001f )
return FALSE;

// Calculate U parameter and test bounds
*u = D3DXVec3Dot( &tvec, &pvec );
if( *u < 0.0f || *u > det )
return FALSE;

// Prepare to test V parameter
D3DXVECTOR3 qvec;
D3DXVec3Cross( &qvec, &tvec, &edge1 );

// Calculate V parameter and test bounds
*v = D3DXVec3Dot( &dir, &qvec );
if( *v < 0.0f || *u + *v > det )
return FALSE;

// Calculate t, scale parameters, ray intersects triangle
*t = D3DXVec3Dot( &edge2, &qvec );
FLOAT fInvDet = 1.0f / det;
*t *= fInvDet;
*u *= fInvDet;
*v *= fInvDet;

return TRUE;
}

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

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