2D outline algorithm for projected 3D mesh

30
votes

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.

6
math3dgeometryprojection
The blue line doesn't look convex here. – Svante
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 :) – ralphtheninja
@MagnusSkog: I need to do exactly this. What method suited you best in the end? – PeteUK
@PeteUK 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. – ralphtheninja
@MagnusSkog Thanks for your response and the warning about FP issues. I feel more confident about doing this now :) – PeteUK

6 Answers

12
votes
  • 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
3
votes

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.

2
votes

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.

2
votes

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.

2
votes

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.

0
votes
  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.