3

我是挑选新手。乍一看,似乎大多数遮挡剔除算法都是对象级别的,而不是检查单个网格,这对于游戏渲染很实用。

我正在寻找的是一种算法,该算法可以高精度地剔除单个对象内对于给定视点被遮挡的所有网格。它至少需要O(n log n),一个简单的逐个网格比较(O(n^2))太慢了。

我注意到 Blender GUI 会实时为您识别被遮挡的网格,即使您使用超过 10,000 个网格的大型对象也是如此。那里使用什么算法,请告诉我?

4

5 回答 5

3

Blender 基于 Bullet 物理库中的动态 AABB 树加速结构执行视锥体剔除和遮挡剔除。遮挡物和对象由它们的边界体积(轴对齐的边界框)表示。

给定一个相机平截头体,视锥体剔除只是遍历 AABB 树。

遮挡剔除基于遮挡缓冲区,这是一种使用非常简单的软件渲染器初始化的深度缓冲区:使用动态 AABB 树加速结构的基本光线追踪器。您可以选择遮挡缓冲区的分辨率来权衡准确性与效率。

另请参阅文档http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.49/Game_Engine#Performance

Blender 源树中的 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 在 Bullet/Extras/CDTestFramework 中有一些 C++ 示例代码。

于 2010-04-10T23:00:18.060 回答
1

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

于 2008-11-25T15:16:06.570 回答
1

不在网格级别进行剔除的原因是网格是一个非常愚蠢的渲染器级别对象,而游戏对象处于场景级别,所有剔除都发生在场景级别。没有网格级别的剔除决定,如果需要渲染对象,它们只是一种批处理具有相似着色器状态的图元的方法。

如果您确实需要在网格级别进行剔除,那么您可能希望为每个网格创建一个对象,然后创建一个包含网格对象的组对象。请注意,您实际上可能会失去性能,因为在网格级别进行剔除通常是不值得的;它可能会中断向硬件传输的数据流。

于 2008-11-25T18:18:18.433 回答
0

Usually the first thing you do is see if the meshes have any chance of occluding each other. Often times with a simple bounding primitive (bounding boxes or bounding spheres). If I recall correctly, Octrees will help with this.

于 2008-11-25T17:02:53.937 回答
0

我尝试了天真的方法,它实际上对我的应用程序来说足够快。

对于网格中的每个三角形,检查是否被网格中的任何其他三角形遮挡,因此为O(n2)。(我仅通过检查每个三角形的中心点是否被遮挡获得了高精度结果,尽管如果准确性很重要,您至少也应该检查三角形角顶点)。

在奔腾 4 机器 (c++) 上,大约 10,000 个三角形的二进制 STL 对象大约需要 1 分钟才能完成

通过首先对三角形进行排序,例如按面积大小或与视点的距离(更有可能被遮挡,因此您可以跳过更多检查),该算法可以优化高达约 40%。

下一个优化步骤是将三角形放入八叉树中,这将大大减少遮挡检查的次数。

于 2009-06-15T12:26:00.847 回答