2D 遮挡剔除的最佳解决方案
在我的 2D 游戏中，我有静态和动态对象。可以有多个摄像机。我的问题：确定与当前相机视图矩形相交的对象。
目前，我只是迭代所有现有对象（不关心动态还是静态），并对它们上的相机视图矩形进行 AABB 检查。这对于非常动态的对象来说似乎是可以接受的，但对于静态对象来说就不行了，因为静态对象可能有数以万计（静态关卡几何体分散在整个场景中）。
我研究了可以解决我的问题的多种数据结构：
- 四叉树
这是我考虑的第一件事，但问题是它会迫使我的场景具有固定大小。 （对于静态对象可接受，但对于动态对象不可接受）
- 动态 AABB 树
看起来不错，但重新平衡的开销对于许多动态对象来说似乎太大了。
- 空间哈希
对我来说，这里的主要问题是，如果你用相机缩小很多，则必须查询大量几乎不存在的空间哈希桶，从而导致性能低下。
总的来说，我对这个问题的良好解决方案的标准是：
动态尺寸：解决方案不得导致场景尺寸受到限制，或者需要大量重新计算来调整尺寸
良好的查询性能（对于相机）
良好的支持动态对象：处理对象所需的计算位置不断变化应该很好：
我的游戏中一次动态对象的最大合理数量可能是 5000考虑一下他们每一帧都会改变自己的位置。考虑到频繁的插入和删除，是否有一种数据结构比每帧比较对象与相机的 AABB 更快？
In my 2D game, I have static and dynamic objects. There can be multiple cameras. My problem: Determine objects that intersect with the current camera's view rectangle.
Currently, I simply iterate over all existing objects (not caring wheter dynamic or static) and do an AABB check with the cameras view rect on them. This seems acceptable for very dynamic objects, but not for static objects, where there can be tens of thousands of them (static level geometry scattered over the whole scene).
I have looked into multiple data structures which could solve my problem:
- Quadtree
This was the first thing I considered, however the problem is that it would force my scenes to be of fixed size. (Acceptable for static, but not for dynamic objects)
- Dynamic AABB tree
Seems good, but the overhead for rebalancing it seems just too great for many dynamic objects.
- Spatial hash
The main problem here for me was that if you zoom out with the camera a lot, a huge number of mostly non-existing spatial hash buckets had to be queried, causing low performance.
In general, my criterias for a good solution of this problem are:
Dynamic size: The solution must not cause the scene size to be limited, or require heavy recomputation for resizing
Good query performance (for the camera)
Good support of very dynamic objects: The computations needed to handle objects with constantly changing position should be good:
The maximum sane number of dynamic objects in my game at one time probably is at 5000. Consider they all change their position every frame. Is there even a data structure which can be faster, considering the frequent insertions and deletions, than comparing the AABBs of the objects with the camera every frame?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
不要试图寻找灵丹妙药。只需将场景分为动态和静态部分，并为它们使用不同的算法。
四叉树显然适合具有固定的静态几何结构
边界。
空间哈希非常适合大小相似的对象集
（例如粒子系统）。
据我所知，动态 AABB 树很少用于遮挡剔除，它们的
主要目的是碰撞检测的广泛阶段。
正如您所注意到的，暴力剔除对于动态对象来说是正常的
如果它们的数量不是很大。
如果您的场景高度稀疏，您可以将其划分为多个岛屿，即创建一个“密度良好”的场景部分列表。
Don't try to find the silver bullet. Just split your scene into dynamic and static parts and use different algorithms for them.
Quad trees are obviously suitable for static geometry with fixed
bounds.
Spatial hashes are ideal for sets of objects with similar sizes
(particle systems, for example).
AFAIK dynamic AABB trees are rarely used for occlusion culling, their
main purpose is the broad phase of collision detection.
And as you noticed, bruteforce culling is normal for dynamic objects
if the number of them is not really big.
If your scene is highly-sparse, you can divide it into islands, i.e. create a list of scene parts with "good density".