2D outline algorithm for projected 3D mesh

Question

Given: A 3D mesh defined with a set of vertices and triangles building up the mesh with these points.

Problem: Find the 2d outline of the projected arbitrarily rotated mesh on an arbitrary plane.

The projection is easy. The challenge lies in finding the "hull" of the projected triangle edges in the plane. I need some help with input/pointers on researching this algorithm. For simplicity, we can assume the 3D edges are projected straight down onto the xy plane.

Answer 1

• Start with the rightmost point (the point with the biggest x coordinate)
• Get all edges from this point
• Follow the edge with the smallest angle to the positive x-axis, and also add it to the solution set
• From the point reached, follow and add the edge with the smallest angle to the edge you came from
• Repeat until you reach the original point

Answer 2

I only see answers for convex solutions, so here is mine for non-convex. (It was a little confusing what was the intention.)

Take all edges from your 2D-triangles and group them. If two edges share both endpoints, they are in the same group. All groups, with only one edge, is then a part of the shell.

Finally you can combine the shell-edges to one ring, by joining them together.

Answer 3

The alpha shapes technique mentioned in this question handles a general set of points where the vertex connections are not known:

Is there an efficient algorithm to generate a 2D concave hull?

However, since you already know "face" information which can be preserved through the projection, it is probably not the best approach.

A brute force algorithm might feasible, especially if spatial sorting structures where used. eg for each facet:

1. Project facet on to the plane
2. Check if projected facet is completely enclosed by existing geometry, if yes: done (no need to expand projected silhouette)
3. If points fall outside the existing geometry, do triangle-triangle intersections to determine which portions fall outside, build an arbitrary n-gon (possibly concave) to fill the missing space, then chop the n-gon in to triangles

Another idea, depending on the fidelity you require, is just shoot a bunch of rays normal from your projection plane to your original geometry. Create a 2d hit/miss and use that to determine your extents.

Answer 4

The 2D outline of the mesh projection is a subset of the projection of its edges.

Using this observation, one can determine the 2D outline using the following method:

• the projection of every edge belonging to only one face is part of the 2D outline,
• for other edges, determine the normal vector of its adjacent faces
• calculate the dot products of those normals with the normal of the plane of projection
• the projection of this edge belongs to the 2D outline if all the signs of the dot products not the same (which means, one face is pointing towards the projection plane while at least one other doesn't, which identifies the edge as part of the outline).

Note that this method will report all the edges that are orthogonal to the projection plane, even those which are not visible from the projection plane's point of view. For example, with a torus, it will find the interior and the exterior outlines, even when the torus is rotated in such a way that its interior hole isn't visible from the projection plane's point of view. To sort out which edges are visible, you will need some sort of visibility test. If the intended use is for user display, you can use a depth buffer computed with an orthogonal projection matrix to render the geometry from the projection plane's point-of-view and do some z-testing to determine which edges are visible from the plane. If you need precision, you will need to perform ray/triangle intersection to determine visibility.