Sign in to follow this  
zedrummer

ray/heightmap collision

Recommended Posts

Hello Do you know if there is a quite efficient algorithm to calculate ray to heightmap collision? I guess that should be quite the same as "mouse cursor" to heightmap collision. If not do you know the way to efficiently do that too? Thank you Cathy

Share this post


Link to post
Share on other sites
Quote:
Original post by zedrummer
Hello
Do you know if there is a quite efficient algorithm to calculate ray to heightmap collision?
I guess that should be quite the same as "mouse cursor" to heightmap collision. If not do you know the way to efficiently do that too?
Thank you
Cathy
You mentioned the mouse cursor - is this for picking? And how big is your terrain?

In any case, this problem can basically be broken into two parts: the narrow phase, and the broad phase.

For the narrow phase, it's pretty easy to find ray-triangle intersection code on the net, so you should be able to get this working pretty easily. If robustness and stability is a concern though, you may want to choose an algorithm that treats triangle edges uniformly from triangle to triangle. This is a little more complicated to implement, but will more or less guarantee that rays don't 'fall through the cracks' between triangles due to floating-point error.

For the broad phase, the most efficient method that comes to mind at the moment is 2D-DDA. With this method, you step through the cells of the 2-D (square) cells that make up the terrain, performing narrow-phase intersection tests as you go. Although I've never implemented this particular algorithm, I'm under the impression that it can be optimized pretty aggressively (which I'm guessing may be important given that you're looking for a 'quite efficient' algorithm).

Share this post


Link to post
Share on other sites
Hello Jyk
First thanks for your answer.

Just to be sure to understand, the idea is to follow the path of the ray over the horizontal 2D grid (x,z) and perform the ray/triangle intersection until it hits something (or not).

Just let me explain you what I am doing:
I am working on my own 3D editor.
One of the things he will do will be editing heightmaps. The editors that can be found like freeworld3D are nice, but you can not edit a whole world made of a grid of heightmaps so when you modify an heightmap on the edge, it modify the one next to it accordingly and the heightmaps at the bottom is next to the one at the top and the one at the left is next to the one at the right (the world wrap).
I already made the displaying part, so I can display a whole wrapping world made of a grid of heightmaps which are loading just when needed when moving on this world. It always has in memory a 3x3 grid of heightmaps (even if the world is just a 1x1 heightmap) for the modifications on the heightmap in the middle to impact the ones next to it.
So now I begin the edit part where the first thing is to see where the mouse is on the heightmap to raise/lower/etc... the heightmap over a disk or square surface around this position on the heightmap. That is the reason of my question and the reason why I want it to be efficient is that I may use it later on in an application that request efficiency like a game. And I want that when the user is moving the cursor over the window of this editing program, he has not to wait even a tenth of a second to show the impacted zone.
For the ray version, it is because I think it is quite the same problem and it may help in any later code.

Thanks again
Cathy

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