algorithm - 快速球格相交

Question

给定一个 3D 网格，一个 3d 点作为球体中心和一个半径，我想快速计算球体包含或相交的所有单元格。

目前我采用球体的（网格对齐）边界框并计算该边界框的最小和最大点的两个单元格。然后，对于这两个单元格之间的每个单元格，我进行盒球相交测试。

如果有更有效的东西会很棒

谢谢！

Answer 1

有一个用于绘制圆的 Bresenham 算法版本。考虑 z=0 处的二维位置（假设球体现在位于 0,0,0），并仅查看网格点的 xy 平面。从x= R, y=0开始，按照Bresenham算法一直到y = y_R, x=0，除了不画，你只要用结果就知道所有x坐标较低的网格点都在圆内，向下到 x=x_center。将它们列在一个列表中，数一数或以其他方式记下。完成二维问题后，重复使用不同的 z 并使用减小的半径 R(z) = sqrt(R^2-z^2) 代替 R，直到 z=R。

如果球心确实位于一个网格点上，你知道球体右半部内外的每个网格点在左侧都有一个镜像伙伴，顶部/底部也是如此，所以你可以做一半的计数/按维度列出。您还可以节省时间将 Bresenham 仅运行到 45 度线，因为相对于中心的任何 x,y 点都有一个伙伴 y,x。如果球体可以在任何地方，您将必须计算每个八分圆的结果。

Answer 2

无论您计算球体内部或外部的单个单元格的效率如何，您的算法将始终为 O(radius^3)，因为您必须标记那么多单元格。DarenW 对中点（又名 Bresenham）圆算法的建议可以提供一个常数因子加速，就像使用平方半径简单地测试交叉点以避免 sqrt() 调用一样。

如果您想要比 O(r^3) 更好的性能，那么您可以使用八叉树而不是平面网格。树的每个节点都可以标记为完全在球体内、完全在球体外或部分在球体内。对于部分内部节点，您会沿着树递归，直到到达最细粒度的单元格。这仍然需要标记 O(r^2 log r) 节点 [O(r^2) 边界上的节点，O(log r) 遍历树以到达每个节点]，因此可能不值得在您的应用程序中遇到麻烦。