网格级别，最优遮挡剔除的最高效算法是什么？

Question

我是一名新手，对遮挡剔除并不熟悉。乍一看，大多数遮挡剔除算法都是对象级别的，而不是检查单个网格，这对于游戏渲染来说实用性不高。

我寻找的算法可以剔除在给定视点下被遮挡的单个对象中的所有网格，并且具有较高的准确性。它需要至少 O(n log n) 的时间复杂度，朴素的网格逐个比较（O(n^2)）太慢了。

我注意到 Blender GUI 可以实时为你识别被遮挡的网格，即使你使用 10,000+ 个网格组成的大型对象。请问那里使用的是什么算法？

- Fredriku73

Answer 1

Blender使用Bullet物理库的动态AABB树加速结构来执行视锥体剔除和遮挡剔除。遮挡物和对象通过它们的包围体（轴对齐包围盒）表示。

视锥体剔除只需遍历AABB树，给定相机视锥体。

遮挡剔除基于遮挡缓冲区，这是一种深度缓冲区，使用基本射线跟踪器初始化：使用动态AABB树加速结构。您可以选择遮挡缓冲区的分辨率以权衡精度与效率。

请参阅文档http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.49/Game_Engine#Performance Blender在源代码目录中实现： blender\source\gameengine\Physics\Bullet\CcdPhysicsEnvironment.cpp 方法 bool CcdPhysicsEnvironment::cullingTest(PHY_CullingCallback callback, void* userData, PHY__Vector4 *planes, int nplanes, int occlusionRes)

以及Bullet Physics SDK中有一些C++示例代码，在Bullet/Extras/CDTestFramework中。

- Erwin Coumans

Answer 2

你有没有研究过八叉树之类的东西？

- andygeers

---

四叉树可能已经足够了，因为它只需要在二维空间内查找重叠（而非三维）。 - Edmund

Answer 3

剔除不在网格级别上进行的原因是，网格是一个非常愚蠢的渲染器级别对象，而游戏对象位于场景级别，在那里进行所有的剔除。没有采取网格级别的剔除决策，它们只是一种将具有相似着色器状态的基元批处理的方式，如果它们的对象需要被渲染。

如果您真的需要在网格级别上进行剔除，则可能需要为每个网格创建一个对象，然后创建一个包含网格对象的组对象。请注意，由于在网格级别上进行剔除通常不值得，因此您可能会失去性能；它可能会破坏数据传输到硬件的流程。

- Coincoin

Answer 4

通常你要做的第一件事情是检查网格是否有可能相互遮挡。通常使用简单的包围盒（边界框或边界球）进行处理。如果我没记错的话，八叉树 可以帮助解决这个问题。

- Adam Tegen

Answer 5

我尝试了“天真的方法”，它对我的应用程序实际上已经足够快了。

对于网格中的每个三角形，检查是否被网格中的任何其他三角形遮挡，因此是O(n2)。 （我仅通过检查每个三角形上的中心点是否被遮挡就获得了高精度的结果，但如果准确性很重要，您还应该检查三角形的角顶点）。

在一台Pentium 4机器（c ++）上，一个大约有10,000个三角形的二进制STL对象需要大约1分钟才能完成。

该算法可以通过首先对三角形进行排序来优化高达40％，例如按面积大小或距离视点的距离进行排序（更容易被遮挡，因此可以跳过更多检查）。

下一步优化是将三角形放入八叉树中，这应该极大地减少遮挡检查的数量。

- Fredriku73