良好的加速结构，适用于移动球体的射线球测试
我正在寻找合适的加速结构来进行射线球相交测试（在游戏中）。适用以下条件：
- 每帧有大约 100 个球体和 100 条光线进行相互测试
- 球体在每帧中移动，光线也移动
- 每帧中可以添加/删除光线/球体（但大多数情况下）它们在两个帧之间是相同的，只是稍微移动了一点）-
整个事情都是 3D 的，
KD 树非常适合光线相交测试，但由于球体移动，我必须在每个帧中重建 KD 树帧，成本昂贵，
八叉树更容易维护，但对于光线相交测试非常无效。
100 条光线针对 100 个球体似乎并不多，但我正在以非常低的资源进行编码，所以我正在寻找一些加速，
任何人都可以给我一些提示吗？
I'm looking for the proper acceleration structure to do ray-sphere intersection tests (in a game). the following conditions apply:
-there are arround 100 spheres and 100 rays to test against each other per frame
-the spheres move in each frame, so do the rays
-there can be rays/spheres added/removed in each frame (but most of them will be the same in between two frames, just moved slightly)
-whole thing is in 3D
a KD-Tree is very good for Ray intersection tests, but since the spheres move, i'd have to rebuild the KD-Tree in every frame, which is costly
an Oct-tree is easier to maintain, but very ineffective for ray intersection tests.
100 rays against 100 spheres doesn't seem to be much, but i'm coding on very low resources, so i'm looking for some acceleration for that
Anyone can give me some hints on that?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
100x100=10k，优化的蛮力看起来并不矛盾，特别是射线/球体相交测试仅涉及加法/乘法。您始终可以在主循环之前预先计算所有归一化光线矢量。
如果你假设你生活在一个有界的宇宙中，并且球体和射线的空间密度相对均匀，你可以使用固定的空间网格（固定八叉树）——类似于 16x16x16 单元网格，或更多—— ，并且：
这样你就不必在任何树中存储任何光线，只需存储球体。这种方法的效率取决于细胞大小/球体大小的比率，如果球体大小没有太多分散，这可能是一个很好的提示。
如果球体不相互交叉并且球体大小有最小值，您甚至可以将球体列表绑定在单元格列表中（适当的数字留给读者作为练习......）
HTH
100x100=10k, an optimized brute force does not seem incoherent, especially that ray/sphere intersection test involve only add/multiply. You can always precompute all normalized ray vector before the main loop.
If you make the assumption that you live in a bounded universe and the spatial density of spheres and rays is relatively uniform, you could use a fixed spatial grid (fixed oct-tree) --something like a 16x16x16 cells grid, or more--, and:
That way you don't have to store any ray in any tree, only spheres. Efficiency of this method depends on the ratio cell size / sphere size, if you don't have too much dispersion on sphere size it can be a good hint.
If spheres don't cross each other and sphere size have a minimum, you can even bound the sphere list in the cell list (appropriate number is left as an exercice to the reader...)
HTH