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.

Patronizing

The blue line doesn't look convex here. – Baynebridge

Yeah you're right. I quickly stole that image from a site and draw some red lines on it to illustrate. I still hope that the idea came through :) – Patronizing

@MagnusSkog: I need to do exactly this. What method suited you best in the end? – Saliferous

@Saliferous It worked very well by selecting e.g. east most node, measure angles and go with the closest one. A word of warning: Be careful with floating point precisions on the angles! I remember I had problems with this and the algorithm took the wrong path in the mesh. – Patronizing

@MagnusSkog Thanks for your response and the warning about FP issues. I feel more confident about doing this now :) – Saliferous

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

Baynebridge

What happens if you project a torus on to the x-y plane? This won't get the interior "hole". – Raine

What if there are two edges both equal to the smallest angle? – Sudd

Hmm... Take the shorter of the two. – Sudd

No, measure the angle only in one direction, e.g. anti-clockwise. – Baynebridge

thanks for the nice solution @Svante. Could you advise how would that work for another projection directions please? – Millais

This solution is only in 2D. How you arrive at a 2D input is completely independent. You can map any plane to the xy plane. – Baynebridge

Answer 2

Just to add: A very intuitive way to find edges in a projection is back face culling! Any edge between a culled and non-culled face should be an outline. If you want to hide interior edges, just use the z-buffer. Back face culling is simply the post projection vertex order and very cheap to compute.

Aenea

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.

Raine

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.

Elenaelenchus

For a closed (water tight) 3D mesh all edges are shared by two triangles, and therefore their 2D projections edges will alsoall have two adjacent triangles. However, if you throw away all triangles whose normal are in the opposite direction of the normal of the plane you are projecting to, what you are left with can be used for the described algorithm. – Binge

Answer 5

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.

Picked

I would recommend doing the orientation test post projection. I am trying to remember why pre-projection does not work. Can't come up with a good math reason though. It was just me transforming normals wrong probably when i did it. – Aenea

Answer 6

1. Find the point whose x is min
2. Find all edges for this point
3. start from this point, imaging you have a stick (green), it rolls clock-wisely to find the first edge that it meets. Let's call it edge-A. edge-A
4. Look for intersections in that edge-A. Find the edge-B that causes the intersection, let's call it inter-A, this inter-A is your second outline point. edge-B
5. Let's then think, between the two points of edge-B, who is the next outline point. Link inter-A and the start point We can then "roll the stick" to find the next outline point. (candidate point 1 is the one) enter image description here
6. repeat above steps until you find points that already exist in your collection.

see a demo of finding outline for a bunny Here is an implementation of the algorithm described above.

Calpac