Mat*_*Mat 7 intersection acceleration
我正在寻找适当的加速结构来进行射线球交叉测试(在游戏中).以下条件适用:
- 每帧有100个球体和100个射线相互测试
- 球体在每一帧中移动,射线也是如此
- 可以在每个帧中添加/删除光线/球体(但是它们中的大部分在两个帧之间是相同的,只是略微移动)
- 全是3D的东西
一个KD-Tree非常适合Ray交叉测试,但是由于球体移动,我必须在每个帧中重建KD树,这是昂贵的
Oct-tree更易于维护,但对于光线交叉测试非常无效.
对100个球体的100条射线似乎并不多,但我在非常低的资源上编码,所以我正在寻找一些加速度
有人可以给我一些提示吗？
100x100=10k，优化的蛮力看起来并不矛盾，特别是射线/球体相交测试仅涉及加法/乘法。您始终可以在主循环之前预先计算所有归一化光线矢量。
如果你假设你生活在一个有界的宇宙中，并且球体和射线的空间密度相对均匀，你可以使用固定的空间网格（固定八叉树）——类似于 16x16x16 单元网格，或更多—— ， 和：
这样你就不必在任何树中存储任何光线，只需存储球体。这种方法的效率取决于细胞大小/球体大小的比率，如果球体大小没有太多分散，这可能是一个很好的提示。
如果球体不相互交叉并且球体大小有最小值，您甚至可以将球体列表绑定到单元格列表中（适当的数字留给读者作为练习......）
华泰