On a 3D Terrain, Given a 3D Line, Find the Intersection Point Between the Line and the Terrain

Question

I have a grid of 3D terrain, where each of the coordinate (x,y,z) of each grid are known. Now, I have a monotonously increasing/ decreasing line, which its start point is also known. I want to find the point where the terrain and the line meets. What is the algorithm to do it?

What I can think of is to store the coordinate of the 3D terrain in a nxn matrix. And then I would segmentize the line based on the grid in the terrain. I would then start with the grid that is the nearest to the line, and then try to compute whether that plane intersects with the line, if yes, then get the coordinate and exit. If no, then I would proceed to the next segment.

But is my algorithm the best, or the most optimum solution? Or is there any existing libraries that already do this?

Answer 1

Not directly and optimisation, just a few hints:

If your grid is large, it might be worthwhile to build an octree from your terrain in order to quickly reduce the number of grid nodes you have to check your line against. This can be more efficient in a huge grid( like 512*512 ndoes) since only the leafnodes your ray is passing through have to be considered.

Additionally, the Octree can be used as a means to decide wich parts of your grid are visible and therefore have to be drawn, by checking which leave-nodes are in the viewing frustum.

There is a catch, though: building the Octree has to be done in advance, taking some time, and the tree is static. It can not be easyly modified after it has been constructes, since a modification in one node might affect several other nodes, not necessarily adjacent ones.

However, if you do not plan to modify your grid once it is created an octree will be helpful.

UPDATE

Now that i understand how you are planning to store your grid, i believe space partitioning will be an efficent way to find the nearest neighbour of the intersection line.

Finding the nearest Neighbour linearly has a runtime complexity of O(N), while space-partitioning appoaches have an average runtime complexity if O(log N).

Answer 2

If the terrain is not built via a nice function you will have to do a ray trace, i.e. traverse the line step by step in order to find an intersection. This procedure can take some time.

There are several parameters for the procedure. E.g. there is the offset you walk alogn the line in each step. If you take an offset too large, you might leave out some "heights" of your terrain and thus not get the correct intersection. If the offset is to small, it will slow down your procedure.

However, there is a nice trick to save time. It's described here resp. here. It uses some kind of optimization structure for the terrain, i.e. it builds several levels of details the following way: The finest level of detail is just the terrain itself. The next (coarser) level of detail contains just a forth of the number of original "pixels" in the terrain texture and combines 4 pixels into one, taking the maximum. The next level of detail is constructed analoguesly:

     .             .       .    .
    ... .         ...     ..    .
  .......        ....     ..    .
 ........    =>  ....  => .. => .

 01234567        0246     04    0
                 1357     26    4

   fine   =>  =>   =>   =>  =>  coarse

If now the ray cast is performed, first of all, the coarser levels of detail are checked:

   /
  / 
 /.
  .
  .
  .

If the ray already misses the coarse level of detail, no finer level has to be examined. That's just a very rough idea how the optimisation works. But it works quite well. Implementing it is quite a bunch of work, but the paper is a good help.

Answer 3

A different approach would be to triangulate the terrain grid to produce a set of facets and then intersect the line with those.

Obviously you'd need to do some optimisations like only checking those facets that intersect the bounding box of the line. You can do a quite cheap/quick facet bounding box to line bounding box check which will discount most of the triangles in the terrain very quickly.

If you arrange your triangles in to an octree (as @sum1stolemyname suggested but for the points) then this checking can be done from the "top down" and you should be able to discount whole sections of the the terrain with a single calculation.