6

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:

boxes fitted to points with normals

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:

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

Epic Wink
  • 796
  • 13
  • 18
  • 1
    Hi, can you clarify a bit more, e.g. for the example you present: Is the number of shapes fixed? Is the relative position of the two fixed? Is it size, orientation or both that you want to optimize? In the given example a third rectangle in the lower right would make the 'outliers' perfectly valid. – mikuszefski Mar 20 '19 at 07:44
  • 1
    I would go with different approach ... first identify contours so create a polylines going through all of your points in other words reorder/group your points first. then find edge and cross/joint points on the polylines , which will divide your set to groups after that just decide if a group is line or curve ... fit it and at last detect your shapes on the fitted lines and curves ... as you can see this sort of things might be too much for single SO answer ... – Spektre Mar 20 '19 at 08:47
  • after that determining simple shapes is easy (and even faster) for example rectangle is set of 4 connected lines with 90 degrees angle where the two pairs of line are the same length... so you can match that +/- some margin error ... see [Unordered cloud point of polygon contour to polygon](https://stackoverflow.com/a/29644460/2521214) and [Given n points on a 2D plane, find the maximum number of points that lie on the same straight line](https://stackoverflow.com/a/20888844/2521214) and [Approximating data with a multi segment cubic bezier curve](https://stackoverflow.com/a/22582447/2521214) – Spektre Mar 20 '19 at 08:54
  • As you mentioned you aim for 3D but what shapes planar or with volume like spheres, boxes, etc ... ? Also where does your dataset come from ... if already processed its possible that in raw data is still some information that can ease up your task – Spektre Mar 20 '19 at 08:56
  • Thank you @Spektre, I've updated the question with more information. Do you think I should edit the question to remove all 2D? It may make the problem much more difficult to process – Epic Wink Mar 21 '19 at 10:37
  • @EpicWink I compose my response in form of an answer ... as comments it was unreadable ... – Spektre Mar 21 '19 at 12:12

1 Answers1

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:

    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:

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

Spektre
  • 49,595
  • 11
  • 110
  • 380