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

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.