javascript - 创建最大体积的内切 3D 框，适合点数组

Question

我有一个 3D 网格，由一组 3D 点(顶点)和一组面(点之间的连接)组成。

Q1我怎样才能找到适合网格内部的最大(体积)内切框。

[操作]

大家好，感谢我可能收到的任何帮助。我正在使用向量来创建 3 维对象。我需要帮助做的是找到适合该对象的最大盒子。想象我们有一个球体。我怎样才能找到适合球体的最大盒子？另一方面，如果我们有一个 3 维箭头怎么办？我该如何找到适合它的最大盒子？我有用于创建对象的所有向量的数组。我正在寻找一种方法来使用这些数组来找到适合构造对象的最大盒子。

Answer 1

1. 您需要测试通用点是否在网格内部

   这可以通过 hit test 来完成你必须处理你的脸，而不是线条，所以处理它们作为

   • planes defined by 2 basis vectors and 2 parameters (2D plane subset)

   找到转换为二维参数的交集，并检查它们是否在面的有效范围内。

2. 现在找到网格的边界框

   只需找到每个轴的最小值和最大值(从顶点开始)，这就会得出多边形的最大尺寸

3. 对于通用网格，您的任务无法通过代数求解，因此

   您必须使用强力+启发式...例如方法通用和测试，以便生成所有(有效)解决方案并从中获取最大的解决方案。您只能通过尝试所有可能性来找到最佳解决方案，但由于无限数量的可能性，这是不可能的，因此您只能实现近似解决方案。我认为使用体素贴图将大大提高性能。

   启发式意味着你只尝试一些解决方案(基于任务/数据集的知识或利用某些东西)，例如，如果你有对称网格，那么你可以像网格一样以居中和对称的方式启动你的盒子(不需要尝试一些疯狂的未对齐框...)

4. 创建体素图

   你有边界框，所以制作 3D 数组，将你的网格体分割成立方体，将每个体素设置为 0(外部)或 1(内部)网格

5. 创建函数来确定通用框是否位于网格内

   只需为盒子的每个体素运行 3 个嵌套 for，如果所有体素都设置为 1，则盒子位于内部。

6. 创建盒子生成器和测试器

   使用一些网格步骤(例如体素大小)生成所有有效框的可能性 - 对于轴对齐框，每个第一个计算卷上有 6 个嵌套 for ，然后将其与实际找到的解决方案进行比较:

   • 如果它不更大，则跳过它并继续下一个框
   • 如果它更大，则运行项目符号#5中的函数
   • 如果它在里面，请将其作为新的实际解决方案

7. 最后您应该得到近似的解决方案

8. 您可以通过在第 7 号子弹之后增加体素计数(使用较小的体素)来提高准确性

   例如，每个轴使用 2 倍以上的体素。现在尝试仅从找到的解决方案中选择 +/- 1 体素的框。您可以递归地应用它来实现所需的精度

[注释]

如果你的盒子是任意方向的，那么你需要添加 3 个以上的维度( Angular )，但这会导致疯狂的复杂性。您可以尝试旋转网格，使盒子轴对齐。因此，首先找到内切最大的线并旋转网格，使其与 x 轴对齐，然后在 yz 平面中找到另一条线，并按 x 轴旋转网格，使该线成为 y 轴。这样解决方案应该是轴对齐的(但情况并非总是如此!!!)。 初始体素图填充样式决定您找到的解决方案是否触及表面...