Jump to content
  • Advertisement
Sign in to follow this  
Waaayoff

Picking terrain with mouse for editing?

This topic is 2514 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

In my terrain editor, i use ray-triangle intersection to figure out which triangle the mouse is picking. The problem is that it's way too slow for large terrains. How can i reduce the number of intersection tests? Or better yet, is there a faster test?

Share this post


Link to post
Share on other sites
Advertisement
Is your terrain mesh broken down into zones or something similar? If so, you could calculate a rough bounding box for the zone and do an initial intersection test against the zone first, then test each triangle in the zone.

I assume you're already using Frustrum culling or something similar to ignore everything outside of the field of view?

Share this post


Link to post
Share on other sites
No. I still haven't done any rendering optimizations. But that sounds good. Calculating the bounding boxes is trivial since i'm using heightmaps.

I'm still interested in other tests though. For example, this is one i found online:

"[color=#666666]Code for accurate ray vs. height map collision detection. The algorithm traces the ray across the height map to find out which quads the ray could potentially touch. If the ray goes below the highest vertex in a crossed quad, a ray-plane intersection test against each of the quad's two triangles is done to find out if the ray hit the height map and if so, where exactly."

The problem is that i can't view the code and so i don't know what the algorithm is..

Share this post


Link to post
Share on other sites
I was pondering about the same problem in my engine just now. I realized that since the terrain is being rendered and I'm interested in intersection of ray with the things that appear in the screen, then why not use the z-buffer? Assume we are using OpenGL. Read the value from the depth buffer corresponding to the position of the mouse to variable 'depth'. If depth is less than 1, we assume that the mouse is over terrain. Then unproject the mouse position:


gluUnProject(mousex, mousey, depth, model,
proj, view, &x, &y, &z);

Now if your terrain is a rectangle with width w and length l, you can find the relative position as (x/w,y/l) and use this to sample your heightmap. Just remember to perform this test right after rendering the terrain, so you won't get a point projected on something else.

Share this post


Link to post
Share on other sites
A possible solution is to flatten (project) the problem into 2D, and trace the projected ray through a 2D grid, visiting each integer cell along the way that the ray passes through. Then, for each cell, intersect it against the two heightmap triangles of that cell (this can even be optimized from the general ray-triangle intersection case).

For a good picture and some pseudo, see this page http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html , but beware, the code is buggy in corner cases (see the comments for corrections).

The above approach is nice that it does not require any preprocessing (and does not incur added latency like using a GPU-based solution which was proposed). If it is still too slow, you could consider preprocessing the terrain into a quadtree, store the min+max heights for each quadtree node, and perform the same grid walking in the quadtree, which enables you to skip over more cells, since you know the height extents across a larger range.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!