3

Given a 3D point and a heightmap (a raster image of elevation data), how can I quickly determine the distance between the heightmap and the point?

enter image description here

The naive approach, measuring the distance to every point on the heightmap, works, but takes far too long.

There are of course a lot of general algorithms to speed up nearest-neighbour searches between a point cloud and a point, such as a k-d tree.

Is there an algorithms that is better suited for the particular case of a heightmap, in terms of performance of each query, or performance of preparing the necessary data structures before the query?

Ideally I am searching for an algorithm that does not require the construction of a tree out of the entire heightmap data. It seems that there should be some way to use the fact that the points are already sorted in X and Y direction within the heightmap.

4
  • Do you need the exact distance, or is it enough to get a quick upper or lower bound? Jul 13, 2014 at 1:04
  • Your height map can't have infinite height resolution. So some parts of it near the point will be closer than others, because they can't be further then distance from the base plane +- height map limits. Also you can use down scaled heightmap to find candidate regions.
    – JAre
    Jul 13, 2014 at 1:07
  • @j_random_hacker Ideally I would want the exact distance and perhaps even the closest point itself. However if there is a better way to get an upper and lower bound, I think I could use that as well, as long as the range between upper and lower bound is adjustable.
    – HugoRune
    Jul 13, 2014 at 1:09
  • Are you trying to find the closest point on the height map to your given 3d point?
    – Steve H
    Jul 13, 2014 at 2:59

1 Answer 1

1

Both ideas below assume that your query point P is "directly above" the heightmap -- that is, that the normal from the plane of the heightmap to P intersects the region that actually contains the heightmap. If it doesn't, then I would suggest measuring the distances to the nearest point on each of the 4 edges of the heightmap, and taking the minimum. I haven't thought through whether the two ideas below will still give exact answers in this (common) case, but they can probably be persuaded to.

First, find the point Q on the plane of the heightmap that is directly beneath P (i.e. a normal from the plane of the heightmap through P intersects the plane at Q). Let the point on the heightmap surface, at height height(Q) above Q, be R. Then an upper bound U on the distance from P to any point in the heightmap is given by the distance between P and R, which is simply distance(P, Q) - height(Q).

In the following I'll call the point in the heightmap plane that lies "under" the "top edge" of some heightmap pixel with co-ords A the base of A. So e.g. Q is the base of R.

When P is close to the heightmap surface

In this case, U will be small, and you can use the fact that any heightmap point closer to P than R cannot have its base in the heightmap plane further than U away from Q. (Think of a ball with radius U centred at P: this just touches R, and any point that is closer to P than R must be inside it.) So when looking for closer points than R, you can restrict yourself to testing just the (2U)x(2U) rectangle of heightmap "pixels" centred at Q. (Or in fact just the radius-U disc of heightmap pixels centred at Q -- but that only saves a modest constant factor of comparisons, and might actually be slower due to the more complicated loop conditions.)

Caveat: This does not consider the 4 "side walls" of each heightmap pixel. E.g. suppose heightmap pixels are 1x1 units in size, R has height 5, P is 3 units above R, there is a heightmap pixel S to the left of R with height 100, and all other heightmap pixels have height 0: then the minimum distance from P to the heightmap could be considered to be 1, because if you started at P and moved directly left 1 unit you would hit the east "wall" supporting S. But the algorithm above will report that the distance is 3, because it only considers the "top edge" of each heightmap pixel, and the top edge of S is far behind P.

When P is far away

In this case, the angle between any heightmap point and P plays less of a role; whether a point is close to P depends more on its height than on the distance between its base and Q in the heightmap plane. Therefore I would suggest keeping a copy of the heightmap points sorted by their height in decreasing order. You can then calculate the distances between P and each point A in this list in decreasing height order, stopping once height(A) < height(Q), since any remaining point B in the list, which necessarily has even lower height, must be at least as far away from P as R is because the line BP is at some nonzero angle.

In fact a slightly more sophisticated stopping criterion is possible: at any time while going throught the list of points, you can abort this process and swap over to examining all the points whose bases in the heightmap plane are closer to Q than the most recently considered point. IOW, suppose you are going through the list of heightmap points in decreasing height order, and come to a point A whose base has some small distance D from Q: then the closest point to P is either the closest point you have found so far, or the closest point whose base in the heightmap plane is at most distance D away from Q. This can be found using a search of the (2D)x(2D) grid of heightmap pixels centred at Q, similar to what happens under "When P is close to the heightmap surface". This is useful in a case where R happens to be quite deep, which would otherwise necessitate examining nearly all other heightmap points in decreasing order. Of course if R is in a wide, deep valley then it will take a long time to find any sufficiently close A, and then every or nearly every point will be tested.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.