2
\$\begingroup\$

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?

Improve this question
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Is your terrain only an elevation map, or is it more complex? In other words, do all the face normals have z strictly positive? \$\endgroup\$ – sam hocevar Dec 9 '11 at 15:42
  • \$\begingroup\$ @SamHocevar, it's only an elevation map \$\endgroup\$ – Graviton Dec 9 '11 at 15:46
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – sam hocevar Dec 9 '11 at 15:52
  • \$\begingroup\$ Nope, no such regularity. \$\endgroup\$ – Graviton Dec 10 '11 at 1:55
1
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$ – sam hocevar Dec 10 '11 at 11:40
  • \$\begingroup\$ @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. \$\endgroup\$ – Aleks Dec 11 '11 at 8:07
  • \$\begingroup\$ @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? \$\endgroup\$ – Graviton Dec 15 '11 at 2:37
  • \$\begingroup\$ @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. \$\endgroup\$ – Aleks Dec 15 '11 at 18:41
  • \$\begingroup\$ Actually, a cut is just the 2D line of the terrain in vertical view \$\endgroup\$ – Graviton Dec 16 '11 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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