How to get the 2D mesh of only visible surfaces when projecting a 3D triangular mesh onto a plane

Question

If I had a triangular mesh surface, it could be rendered according to whatever computer graphics does to render it, and done properly only the front most triangles would be visible.

What I am interested in is something similar to the rendering problem in concept, but I don't want a bitmap image. What i want is the list of 2D polygons that results when projecting a 3D triangular mesh onto a plane, and what I need are the actual vertices and edges of the resulting 2D mesh.

In addition to projecting triangles that are completely visible onto a plane which is trivial, it would also mean not including triangles that are completely covered, but also clipping triangles that are partly covered, possibly into polygons with >3 edges.

In a naive sense, I could simply project every triangle into the plane, tracking the z-value of each one, and then compare every triangle to every other polygon for overlap and then do clipping and ignoring as necessary. But then this would go as N^2 and I have to do this procedure many times and would be concerned about computational cost.

While I have found many things about operations on triangular meshes such as rendering, simplifying, performing booleans, etc. I haven't seen this exactly. If there is a library for doing this, or a reference that discusses how to do it, I would be grateful for a reference.

Answer 1

There are two ways of doing this.

A. Using OpenGL/GPU (Computationally faster) (This logic is also used for selection implementations)

You'll have to follow following steps (I'm assuming you are aware of rendering pipeline and aware of OpenGL/WebGL)

1. Place your camera on the plane you want to project your geometry to, set the proper type of projects and other camera parameters
2. Get the list of all the triangles you have.
3. Assign every triangle a unique color. Following would be an easy way to assign the unique color based on index of the triangle in the list.

    int i = // Index of the triangle 
    // We've added 1 to the index because 0 index is translated to black color 
    // And our background is also rendered as black so we skip will that color.
    int r = (i + 1 & 0x000000FF) >> 0;
    int g = (i + 1 & 0x0000FF00) >> 8;
    int b = (i + 1 & 0x00FF0000) >> 16;
    glm::vec4 unique_color = glm::vec4(r / 255.0f, g / 255.0f, b / 255.0f, 1.0);

4. Setup the OpenGL flags the way your want to get the result, like Turn on back face culling, Enable depth test and set proper depth function etc so that you now cut all the triangles facing away from the camera/plane, and depth test will filter only visible triangles out of all front-facing triangles based on their depths.

    glEnable(GL_CULL_FACE);
    glCullFace(GL_BACK); // This is the default value so you may skip
    glFrontFace(GL_CCW); // Define winding of front-facing triangle.(default is GL_CCW)

5. Create a frame-buffer and render all the triangles with their uniquely assigned colors.
6. When the rendering is complete, you now can traverse all the pixels and get the list of unique colors from the image.
7. Decode the colors into indices of triangles back like given below. (This is exactly revers of what we've done in step 3)

    int triangle_index =
        color.r +
        color.g * 256 +
        color.b * 256 * 256;

8. With all these triangle indices you can take out the triangles list of triangles we had prepared in the step 2.
9. So you now have all the all the triangles which are visible from the defined plane.
10. You can project now all these triangles(triangle points) on the plane and you have projected points, lines and triangles on the given plane.
11. You can read more about this technique here, this technique is used for selection and picking in this example, http://www.opengl-tutorial.org/miscellaneous/clicking-on-objects/picking-with-an-opengl-hack/

B. Using CPU renderers or writing custom algorithm.

In this case you can use CPU rendering libraries for the same or you can write following algorithm

1. Calculate the normal of the plane on which we want to project the visible triangles let's call it projection_normal
2. Discard all the triangle whose noramls makes more than 90 deg angle with projection_normal. In this step you're basically doing back face culling.
3. Now project all the remaining triangles on the projection plane.
4. Identify overlapping projected triangles and keep only the one whose distance from the plane is smallest(depth) and discard rest of the overlapping triangles.
5. Here you'll have to play with more computational geometry math in above step to find the overlaps and there could be different results based on how you calculate depth of the tilted triangles.

I would always recommend OpenGL approach as it has an advantage of faster processing as we use GPU for rendering. And it does most of the work for you, you can control the results based on how you set the depth functions, face culling flags etc.