有没有比单独测试8个角是否在球体内更快的方法来检查轴对齐的立方体是否在球体内部?
我正在穿过一个八叉树,检查它的立方体叶子是否在球体内相交或封闭。我在这里找到了一种相交的方法:立方体-球体相交测试?
我希望能找到一种更有效的方法来测试封闭性。我最终需要的是一个返回三种状态之一的测试:
- 外部球体
- 相交球体
- 球体内部
立方体由两个点定义,球体由其中心点和半径定义。
要确定立方体是否完全在球体内,只需测试一个顶点即可,即距离球体中心最远的顶点。可以通过比较立方体和球体的中心点来确定要测试的顶点。例如,给定一个以(cx,cy,cz)
为中心、边半长为l
的立方体,以及一个位于(sx,sy,sz)
、半径为r
的球体,测试点将是
tx = cx + ( cx > sx ? l : -l );
ty = cy + ( cy > sy ? l : -l );
tz = cz + ( cz > sz ? l : -l );
然而,相对于球体测试立方体的角并不能捕捉到所有相交的情况——考虑从(-5,-5,-5)到(5,5,5)的立方体和半径为2的(0,0,6)的球体。两个体积确实相交,但球体内没有顶点。
我会选择多通道方法:
- 根据立方体检查球体的轴对齐边界框-非常简单的检查,快速拒绝显然没有交叉的情况
- 检查球体中心是否位于立方体内
- 这种可能性可能在您的系统中被排除,但您应该还要对球体所在的情况进行边界框检查完全在立方体内
- 在这一点上,别无选择,只能继续检查球体和立方体面之间的交点
不过,为了遍历八叉树,我很想把球体当作一个轴对齐的边界框,并以较小的假阳性率生活。如果我知道这会比得到绝对正确的交叉结果更快,我一点也不会感到惊讶。
您可以测量从立方体中心到球体中心的距离。再加上立方体对角线的长度和球体的半径,就可以确定立方体是否在球体内。