Determine the cut sections of a polygonal mesh

I have a polygonal mesh, defined by vertices $V$, edges $E$ and face $F$. One can view this as a real life 3D terrain.

I want to obtain cut sections of this terrain, defined by vertical cut planes. What are the algorithms I can use to determine the cut sections of the terrain in an efficient manner? The cut section here is just a polyline that are the intersection lines between the cut section vertical plan and the polygonal mesh.

Edit: Since my elevation map is a mesh, this means that I know every information associated to a vertex, face and edge, e.g, which faces are connected to which edge.Is it possible to leverage this information in order to speed up the cut section further?

• Is your terrain only an elevation map, or is it more complex? In other words, do all the face normals have z strictly positive? Dec 9, 2011 at 15:42
• @SamHocevar, it's only an elevation map Dec 9, 2011 at 15:46
• Thanks, I think you should specify that fact in your question unless you really want a more generic answer, because it can help find proper algorithms. Another question: do the xy coordinates have any kind of regularity, like a square or hexagonal pattern? Dec 9, 2011 at 15:52
• Nope, no such regularity. Dec 10, 2011 at 1:55

Since you have just an elevation map you can start by projecting everything on a 2D plane. So your elevation map will become 2D net and the cutting planes will become cutting lines. After finding all the intersecting points in 2D you can unproject them back to 3D points. This will dramatically simplify the algorithms and the processing time.

• To project in 2D plane you can just ignore the Z component
• You can use a line segment intersection algorithm to find the points.
• You can first make a fast check if both vertices of a given edge are on the same side of a cutting line then the edge doesn't have a cutting point.
• If your cutting planes/lines create a concave shape/polygon then you need to extend this previous early out check to and make sure that at least one vertex is on the "inside" side of each line.
• If your cutting planes/lines don't create concave shape/polygon then you should first split them to segments and do only segment/segment intersection checks.
• Once you have all the intersected edges and their intersection points to find your polyline you should traverse the faces by following the shared edges. (be careful if the faces can be convex, in such case they can have more then 2 intersected edges).
• Unproject the polyline in 3D. To unproject a point you can use the ratio of the distances to the two vertices of the line segment that the point belongs to. In 2D and 3D the ratio should be the same.
• This looks good to me. I suggest unprojecting on the fly rather than doing it in a separate step: when you compute the intersection point, you get the Z coordinate for free at step 2. Dec 10, 2011 at 11:40
• @SamHocevar You are absolutely right Sam and I bet there are more optimizations you can do especially if we knew what the elevation map is or what the planes are. If the elevation map is really large maybe some spacial partitioning is appropriate. Or maybe we are talking about 20 faces mesh and it doesn't matter. Dec 11, 2011 at 8:07
• @Aleks, thank you for your idea. But since my elevation map is a mesh, this means that I know every information associated to a vertex, face and edge, e.g, which faces are connected to which edge. My question is, is it possible to leverage this information in order to speed up the cut section further? Dec 15, 2011 at 2:37
• @Graviton, can you share what the cutting faces are? Are they something specific like view frustum? Are they creating concave hull? One thing you can do is create quad-tree (no need of oct-tree since we will do all processing in 2D) then partition your elevation mesh in it. Project the cutting shape in that tree to find the nodes of interest. This will allow you to work with subset of your mesh. Dec 15, 2011 at 18:41
• Actually, a cut is just the 2D line of the terrain in vertical view Dec 16, 2011 at 2:39