# ray/heightmap collision

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

## 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 on other sites
Quote:
 Original post by zedrummerHelloDo 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 youCathy
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 on other sites
Hello Jyk

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

1. 1
2. 2
3. 3
4. 4
Rutin
13
5. 5

• 24
• 10
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633695
• Total Posts
3013373
×