在我的 OpenGL 应用程序中，我有很多球体（超过 100.000 个），我愿意实现一种高效的光线拾取算法。
到目前为止，我的方法是幼稚的：
计算与鼠标指针对应的射线（在对象空间中），然后将我拥有的每个球体与射线相交。虽然这种方法对于我的应用程序来说可能足够快（球体的实际渲染可能比用射线拾取它们要慢......），但我想知道哪种方法是这种情况下最好的方法。
我特别担心这些球体可能具有任意半径这一事实，我不知道如何在八叉树等空间分区结构中考虑到这一点。
你有什么建议吗？
我将添加更多细节：
有问题的应用程序是一个分子查看器，其中原子表示为球体，如下图所示：
球体可以部分或完全重叠。场景可以是动态的（您可以进行分子模拟），但您通常不想在动画期间选择任何东西。
理想情况下，我想找到一个将来也可以扩展到气缸的解决方案。
有趣的问题！
射线与球体碰撞测试是最简单的测试之一，这也是为什么球体经常用于确定 PVS（潜在可见集）的原因。
基本上你用更大的球体包围球体。首先，您测试与巨大球体的射线碰撞，如果失败，您可以确定这个大体积内的任何其他球体也不会与射线发生碰撞。如果射线发生碰撞，则只需在体积内移动并测试组中的下一个球体……该层次结构将节省大量计算时间。
从O(N)（测试每个球体），您可以达到O(Log N)（如二叉树或四叉树/八叉树）。
一个问题是当您的层次结构是动态的时，您将不得不重建球体。您可以重建整个树 -可能是O(n Log n)，或者聪明地只重建层次结构的移动部分。如果 K 个球体正在移动，那么重建时间可以减少到O(K Log N)左右（例如移除特定球体然后再次插入）
这是有关拾取的教程的链接和有关边界球体的 wiki
好吧，如果您允许将球体附加到八叉树的内部节点，那么超大的球体可能只是在不会破坏它们的任何级别。
编辑：为了进一步讨论，了解球体是否允许重叠以及它们是静态的还是动态的也是有用的。