7

我正在寻找合适的加速结构来进行射线球相交测试（在游戏中）。适用以下条件：

- 每帧大约有 100 个球体和 100 条光线可以相互测试

- 球体在每一帧中移动，光线也是如此

- 可以在每一帧中添加/删除光线/球体（但它们中的大多数在两帧之间是相同的，只是稍微移动了一点）

-整个东西都是3D的

KD-Tree 非常适合 Ray 相交测试，但是由于球体移动，我必须在每一帧中重建 KD-Tree，这很昂贵

Oct-tree 更容易维护，但对于光线相交测试非常无效。

100 条光线对 100 个球体似乎并不多，但我正在使用非常少的资源进行编码，所以我正在为此寻找一些加速

任何人都可以给我一些提示吗？

4

1 回答 1

2

100x100=10k，优化后的蛮力看起来并没有不连贯，尤其是光线/球体相交测试只涉及相加/相乘。您始终可以在主循环之前预先计算所有归一化的光线矢量。

如果您假设您生活在有界宇宙中并且球体和射线的空间密度相对均匀，则可以使用固定空间网格（固定八叉树）-类似于 16x16x16 单元格网格或更多- ， 和：

  • 预先计算每个球体相交的单元格（易于计算，只涉及很少的添加和比较），在每个单元格中存储相交球体的列表，
  • 对于每条射线，在一个循环中：
    • 计算光线穿过的单元格列表（基于 Bresenham 算法的方法可以解决问题）
    • 对此单元格列表中的所有球体进行交集测试。

这样您就不必在任何树中存储任何光线，只需在球体中存储。这种方法的效率取决于细胞大小/球体大小的比率，如果球体大小没有太大的离散度，这可能是一个很好的提示。

如果球体不相互交叉并且球体大小有最小值，您甚至可以将球体列表绑定到单元格列表中（适当的数字留给读者作为练习......）

高温高压

于 2010-02-23T10:13:14.690 回答