Plane To Intersect with Terrain Algorithm

Question

I have a terrain, which is represented by elements and coordinates ( they are just a list of mesh), and I have a plane.

How to find the intersection between the plane and the terrain? Should I just break the plane up into a list of lines, and then use ray casting technique or other technique to compute the list of intersection, and join them up together? Or is there other ways of doing?

This question is a special case of my question here, in which I actually discretized the plane by breaking it into a lot of lines, and find the intersection points in order to get the lines where the plane intersect with the terrain, but I really wonder is there a better method.

Answer 1

1. define the plane using its implicit equation. Find a, b, c, and d so that ax + by + cz + d = 0 for all (x, y, z) on the plane
2. Go through every square that defines a segment of your terrain. Interpret the square as two separate triangles
3. For each vertex v1 = (x1, y1, z1), v2 = (x2, y2, z2), v3 = (x3, y3, z3) of a triangle, determine which side of the plane it lies on:
   • l1 = a*x1 + b*y1 + c*z1 + d
   • l2 = a*x2 + b*y2 + c*z2 + d
   • l3 = a*x3 + b*y3 + c*z3 + d
4. Now there are two options.
   • either l1, l2, l3 are all > 0 or l1, l2, l3 are all < 0 - in that case the plane does not intersect the triangle and you have nothing to do.
   • or two of the l values are positive/negative and the third one is the opposite, e.g. l1>0, l2>0 and l3<0 - then the triangle edges v1-v3 and v2-v3 are being intersected
5. edge-plane intersection is easy to calculate. Assuming the v1-v2 edge is intersected:
   • xi = (x1*l1 - x2*l2)/(l1 - l2)
   • yi = (y1*l1 - y2*l2)/(l1 - l2)
   • zi = (z1*l1 - z2*l2)/(l1 - l2)

This way you will obtain a list of edges that correspond to intersection of the plane with your terrain. It is a slow method, but easy to explain... if you wanted to speed it up, you would need to use octrees or similar data structure to limit the amount of point/plane tests you need to do.