Fit a shape to points

Question

I am trying to fit known well-defined shapes (eg boxes, cylinders; with configurable positions, rotations and dimensions) to a set of points with normals generated from sampling a 3D mesh. My current method is to define a custom fit function for each shape and pass it to a third-party optimisation function:

fitness = get_fitness(shape_parameters, points)
best_parameters = external.optimise(get_fitness, initial_parameters, points)

(for reference, I'm currently using Python 3 and scipy.optimize.minimize with bounds, but language is irrelevant).

This fitness function for a rectangle would look something like

def get_fitness(parameters, points):
    side_fitnesses = []
    for side in [top, right, bottom, left, back, front]:
        dists = get_side_distances(parameters, points, side)
        ndevs = get_side_normal_deviations(parameters, points, side)
        side_fitnesses.append(combine_dists_and_ndevs(dists, ndevs))
    fitnesses = choose_best_side_for_each_point(side_fitnesses)
    return mean(fitnesses)

However this means I have to determine outliers (with/without caching), and I can only fit one shape at a time.

For example (in 2D), for these points (with normals), I'd like the following result:

Notice that there are multiple shapes returned, and outliers are ignored. In general, there can be many, one or zero shapes in the input data. Post-processing can remove invalid (eg too small) results.

Note: my real problem is in 3D. I have segments of a 3D mesh representation of real-world objects, which means I have more information than just points/normals (such as face areas and connectivity) which are in the example above.

Further reading:

• Not well-defined shape-fitting
• Highly technical n-dimensional fitting
• Primitive shape-fitting thesis
• Unanswered SO question on something similar

PS: I'm not sure if StackOverflow is the best StackExchange site for this question

Answer 1

well so you will have to handle meshes with volume then. That changes things a lot ...

1. segmentate objects

   be selecting all faces enclosing its inside ... So its similar to this:

   • Finding holes in 2d point sets?

   so simply find a point inside yet unused mesh ... and "fill" the volume until you hit all the faces it is composed of. Select those faces as belonging to new object. and set them as used... beware touching objects may lead to usage of faces twice or more ...

   You can do this also on vector math/space so just test if line from some inside point to a face is hitting any other face ... if no you found your surface face ... similar to Hit test

2. process object (optional)

   you can further segmentate the object mesh into "planar" objects that it is composed of by grouping faces belonging to the same plane ... or inside enclosing edge/contour ... then detect what they are

   • triangle
   • rectangle
   • polygon
   • disc

   from count and type of faces you can detect basic objects like:

   cone = 1 disc + 1 curved surface with singular edge point parallel to disc center
   box/cube = 6 rectangles/squares
   cylinder = 2 discs + 1 curved surface with center axis going through discs centers
   

3. compute basic geometric properties of individual objects (optional)

   like BBOX or OBB, surface, volume, geom. center, mass center, ...

   Now just decide what type of object it is. For example ratio between surface area and volume can hint sphere or ellipsoid, if OBB matches sides it hints box, if geom and mass centers are the same it hints symmetrical object ...

4. pass the mesh to possible object type fitting function

   so based on bullets #2,#3 you have an idea which object could be which shapes so just confirm it with your fitting function ...

   to ease up this process you can use properties from #3 for example of this see similar:

   • ellipse matching

   so you can come up with similar techniques for basic 3D shapes...