Detecting arbitrary shapes

Question

Greetings,

We have a set of points which represent an intersection of a 3d body and a horizontal plane. We would like to detect the 2D shapes that represent the cross sections of the body. There can be one or more such shapes. We found articles that discuss how to operate on images using Hough Transform, but we may have thousands of such points, so converting to an image is very wasteful. Is there a simpler way to do this?

Thank you

Answer 1

In converting your 3D model to a set of points, you have thrown away the information required to find the intersection shapes. Walk the edge-face connectivity graph of your 3D model to find the edge-plane intersection points in order.

Assuming you have, or can construct, the 3d model topography (some number of vertices, edges between vertices, faces bound by edges):

1. Iterate through the edge list until you find one that intersects the test plane, add it to a list
2. Pick one of the faces that share this edge
3. Iterate through the other edges of that face to find the next intersection, add it to the list
4. Repeat for the other face that shares that edge until you arrive back at the starting edge

You've built an ordered list of edges that intersect the plane - it's trivial to linearly interpolate each edge to find the intersection points, in order, that form the intersection shape. Note that this process assumes that the face polygons are convex, which in your case they are. If your volume is concave you'll have multiple discrete intersection shapes, and so you need to repeat this process until all edges have been examined.

There's some java code that does this here, and a rather nifty test application here.

Controls:

• 1-5 to change the test volume
• q and w to alter the number of query planes
• a, s, and d to alter the scan speed of the query planes
• left-click-drag to rotate the view
• right-click-drag to rotate the query planes

Answer 2

The algorithm / code from the accepted answer does not work for complex special cases, when the plane intersects some vertices of a concave surface. In this case "walking" the edge-face connectivity graph greedily could close some of the polygons before time.

What happens is, that because the plane intersects a vertex, at one point when walking the graph there are two possibilities for the next edge, and it does matter which one is chosen.

A possible solution is to implement a graph traversal algorithm (for instance depth-first search), and choose the longest loop which contains the starting edge.