我正在尝试发现一种更快的算法,用于测试轴对齐的conical surface是否与轴对齐的边界框的体积相交。
我开发的当前算法如下:
谁能想到一个更有效的?这似乎通过计算每个线路交叉点做了很多额外的工作。
编辑:
以上算法很糟糕,例如:
锥体只能与盒子的一个边缘交叉,使得所有轴线交叉点都在一侧,因此除非测试所有边缘或者智能选择要测试的边缘,否则上述算法不起作用(可能是最接近锥体的边缘?)。
编辑编辑:请参阅下面我自己的答案,我后面发现的解决方案对我来说似乎是最优的。
我找到了一个可能的最佳解决方
沿+ -z轴的单位右锥开口的等式是x^2 + y^2 - z^2 = 0
。
使用x^2 + y^2 - z^2
在AABB上找到interval arithmatic的最大值和最小值。提示:对于x^2
,最小值是clamp(0, [xmin, xmax])^2
,最大值是max(xmin^2, xmax^2)
。
看看this table of object/object intersection tests似乎没有众所周知的锥形/ AABB交叉测试。所以你是自己的,我害怕!
你可以从David Eberly的文章“Intersection of a Triangle and a Cone”开始,看看你有多少可以适应你的情况。 (在最坏的情况下,AABB由12个三角形组成,但我希望你能做得更好。)
来自@Gareth Rees的link to the David Eberly article是一个很好的,但如果你把所有东西都分成三角形,你最终会检查多余的顶点和边缘。我认为这样可行:
交换面部和边缘检查的顺序实际上可能更好;我希望面部检查比边缘检查更快,所以你可以提前退出。
SIMD优化可能有一些很好的机会,因为顶点和边的数量都是4的倍数,锥体是轴对齐的,但这超出了这个答案的范围:)
我想出了一个算法来解决任意锥和aabb的一般情况,但它仍然有效地处理你的具体情况。
我在另一个帖子中描述了它:Detect if a cube and a cone intersect each other?