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

Klagenfurt

Are you talking about any type of 3D-shape, or are there some application or domain specific constraints? – Coppice

So you want pattern recognition on 2D polygons? – Rann

@Andre, Hello, I'M talking about any 2d shape. Since the 3d body is shaped like a tree branch, it will probably be close to an ellipse – Klagenfurt

@Itjax, Hello, I need to partition a set of points (all on the same plane) to groups. Each group represents a 2d shape (usually not a polygon), such that the points which belong to the group define the circumference of this 2d shape. – Klagenfurt

@Ojala. So you know the exact shape of the 3D body... Is the orientation of the plane also fixed? In that case it is perhaps closer to a registration problem: finding the transformation (translation) which puts the most "ellipsoids" on your 3d tree-like body. – Coppice

@Andre, Yes. It's a horn-shaped 3d body, which is represented as a list of vertices and faces. Each face is a triangle represented by 3 vertices. The body is positioned along the Z-axis (height). We make several cuts at certain heights. Each cut (a plane perpendicular to the Z- axis) creates cross-section(s) of the 3d body. I would like to find the shapes of these cross-section(s), when the input is a set of points of the intersection. – Klagenfurt

@Ojala, do you get the connectivity information from the original mesh too? Or just points? What would your desired output look like? Like "this group is an ellipse and that group is a rectangle" or "this group's shape is defined by a polyline [<polyline here>]"? – Rann

@Itjax: I also have the faces. The desired output is "this group's shape is defined by a polyline [<polyline here>]", the group should contain all points inside the shape and on its` circumference. My objective is to determine where the 3d body has split to branches – Klagenfurt

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

Frontier

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.

Costotomy

Answer 3

It looks like you wanted to combine intersection points back into connected figures using some detection or Hough Transform.

Much simpler and more robust way is to immediately get not just intersection points, but contours of 3D body, where the plane cuts it.

To construct contours on the body given by triangular mesh, define the value in each mesh vertex equal to signed distance from the plane (positive on one side of the plane and negative on the other side). The marching squares algorithm for isovalue=0 can be then applied to extract the segments of the contours:

This algorithm works well even when the plane passes through a vertex or an edge of the mesh.

To better understand what is the result of plane section, please take a look at this short video. Following the links there, one can find the implementation as well.

Eloign