使形状适合点

Question

我试图将已知的明确定义的形状（例如，盒子，圆柱体；具有可配置的位置，旋转和尺寸）拟合到一组点，这些点具有通过采样3D网格生成的法线。我当前的方法是为每个形状定义自定义拟合函数，并将其传递给第三方优化函数：

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

（作为参考，我目前正在使用Python 3并scipy.optimize.minimize带有边界，但是语言无关紧要）。

矩形的适应度函数看起来像

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)

但是，这意味着我必须确定异常值（有/没有缓存），并且一次只能拟合一个形状。

例如（在2D中），对于这些点（具有法线），我想要以下结果：

请注意，返回了多个形状，并且忽略了异常值。通常，输入数据中可以有许多，一种或零种形状。后处理可以删除无效（例如，太小）的结果。

注意：我真正的问题是3D。我具有真实世界对象的3D网格表示的片段，这意味着我除了上面的示例中的点/法线（例如面部区域和连接性）外，还具有更多信息。

进一步阅读：

• 形状拟合不明确
• 高度技术性的n维拟合
• 原始形状拟合论文
• 关于类似问题的未解决的SO问题

PS：我不确定StackOverflow是否是此问题的最佳StackExchange网站

Answer 1

那么你就必须处理带有体积的网格。这改变了很多事情......

1. 分割对象

   选择包围其内部的所有面...所以它与此类似：

   • 在二维点集中寻找漏洞？

   因此，只需在未使用的网格内找到一个点...并“填充”体积，直到击中其组成的所有面。选择这些面作为属于新对象。并将它们设置为已使用的...小心触摸物体可能会导致使用脸部两次或更多次...

   您也可以在向量数学/空间上执行此操作，因此只需测试从某个内部点到一个面的线是否击中任何其他面...如果没有，您找到您的表面...类似于命中测试

2. 过程对象（可选）

   您可以通过将属于同一平面的面分组...或内部封闭边缘/轮廓...将对象网格进一步分割成由其组成的“平面”对象，然后检测它们是什么

   • 三角形
   • 长方形
   • 多边形
   • 光盘

   根据面部的数量和类型，您可以检测基本物体，例如：

   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. 计算单个对象的基本几何属性（可选）

   像 BBOX 或OBB、表面、体积、几何。中心, 质量中心, ...

   现在只需决定它是什么类型的对象。例如，表面积和体积之间的比率可以暗示球体或椭球体，如果OBB匹配边，则暗示盒子，如果几何和质心相同，则暗示对称物体...

4. 将网格传递给可能的对象类型拟合函数

   因此，根据项目符号#2、#3，您知道哪个对象可能是哪种形状，因此只需使用您的拟合函数进行确认即可...

   为了简化此过程，您可以使用#3中的属性，例如，请参阅类似的内容：

   • 椭圆匹配

   所以你可以为基本的3D形状想出类似的技术......