2d outline algorithm for projected 3d mesh

Answer 1

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

http://stackoverflow.com/questions/83593/is-there-an-efficient-algorithm-to-generate-a-2d-concave-hull/83780#83780

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 2

Is it simply a matter of projecting the xyz points into x'Y' points on the arbitrary plane and then just doing a convex hull in those coordinates?

Answer 3

• 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 4

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.