0

我有一个 3D 空间中的三角形列表和一个用 (x,y,z) 坐标描述的点。我正在编写一种将最近的三角形返回到该点的方法。

我最初编写的简单实现是遍历所有三角形，检查与该点的距离，然后返回距离最小的那个。在大多数情况下，虽然我正在使用的三角形列表包含数千或数万个元素，但我正在寻找优化它的方法。

我一直在尝试使用八叉树结构使其工作，因此我创建了一个八叉树来存储所有三角形。我认为一种可能的方法是通过计算该点与每个单元格中心之间的距离，然后仅与该单元格内的三角形进行比较，从而找到距该点最近的八叉树单元格。

我不确定如何从八叉树中检索最近的单元格（这是我第一次使用八叉树）。这是我到目前为止写的方法：

public Octree getClosestCell(final Vec3D point) {
    if (children != null) {
        float minDist = Float.MAX_VALUE;
        Octree closestCell = null;
        for (int i = 0; i < 8; i++) {
            final float dist = point.distanceTo(children[i].getCentroid());
            if (dist < minDist) {
                minDist = dist;
                closestCell = children[i];
            }
        }
        return closestCell.getClosestCell(point);
    } else {
        return this;
    }
}

所以总结一下，我有2个问题：

  1. 建议的方法听起来像是优化此问题的好方法吗？
  2. 上面的方法看起来是正确的还是有更好的方法来检索最近的单元格？
4

0 回答 0