Highest points along a path on a heightmap

Troubleshooting General Help
1

Hi,



I’m trying to get (as efficiently as possible), the highest point along a path on a heightmap. More precisely, if there’s a line linking two distincts points on the map, I would like to know what are the highest points along the line. For example, if there are two “mountains” between the two points, I want to get two vectors corresponding to the highest points. Is there any efficient way to do so, apart from searching in a TerrainPatch ?



Thanks in advance

2

Considering you mention a heightmap, I’d suggest trying a Grid Traversal algorithm, which works great for situations with either 3D voxels or 2D pixels. What you define as a mountain is a bit hard, I’d start collecting all the points along the line and then select those points that are the highest x% of the set, and post process the resulting set of points by removing every point that has a heigher point right next to it, as well as throwing out all leftover points that are too close to a higher neighbouring peak, which again, has to be specified by a parameter or % to your liking. During this, keep the positions of those points as well (on the heightmap) so you can calculate the 3d position of this point later on.



Just my thoughts :wink:

1 Like
3

Thanks for your answer. I was considering such an algorithm. I don’t need extreme precision, just to get a point (x, y, z) which is roughly the highest along the path.

4

The “not funny part at all” is that I can’t allow myself to use computationally intensive algorithms, whereas the problem implies computationally intensive stuff, and that I would need to do that for n obstacles along the path between two points.

5

I’m curious, how long can the line be and what kind of thing are you doing with the information?



How “rough” can it be?

6

The processing has nothing to do with the graphics (as you may have suspected). I just wan’t to do simple computations using the heights. Actually I’m a student, and I’m working on a little project which implies radio wave propagation “prediction”. It’s a small project, nothing fancy, but maybe it’ll be a basis (in the way that I would have already encountered a few issues) for some stuff I may do in the future…



I haven’t got the time now, but I should begin working on ray tracing in a few weeks. Then I should have much more time to work on something much better

7

Funny… the reason I asked is because when I needed something like this years ago it was for microwave path profiling. :slight_smile: We used a similar grid traversal approach, bilinearly interpolated basically from GIS elevation data… but I only had to find one path.



I can’t offer much more help but you probably recognize that any results are an approximation since it’s really impossible to accurately reconstruct terrain from discrete height values. Given that, simply picking a step resolution and doing bilinear interpolation of the points may be fast enough and accurate enough.

1 Like
8

:slight_smile:



The only reason of my post is that I’m totally new to jME (I began only a few days ago). So I feel compelled to ask, just in case there’s something implemented I didn’t notice which could help me in some way. My little project does not involve only propagation prediction, but other stuff too, some of which require a lot of CPU resources. That’s why I’m like “ewwaaaaaaaah” when I’m thinking about that stuff. Anyway, the goal is not to have an accurate path prediction (would be really stupid to think otherwise), but more an idea according to a model. I’ll try to have something decent when I’ll have time.



I’m currently planning on working (in 2 months or so) on a project dedicated to path prediction. I won’t have any of the additional annoying constraints that I must deal with now. The whole thing should be more interesting.



Thanks for your input