四叉树中巨大对象的问题
假设我有圆形物体。每个对象的直径为 64 像素。
我的四叉树的单元格是 96x96 像素。
当我检查圆所在的单元格及其所有相邻单元格中的碰撞时，一切都会很好并且运行良好。
但是如果我有一个直径为 512 像素的圆怎么办？它将覆盖许多小区，因此当仅检查相邻小区时这将是一个问题。但每次将更大的对象插入树中时，我无法重新调整四叉树网格的大小......
Let's say I have circular objects. Each object has a diameter of 64 pixels.
The cells of my quad tree are let's say 96x96 pixels.
Everything will be fine and working well when I check collision from the cell a circle is residing in + all it's neighbor cells.
BUT what if I have one circle that has a diameter of 512 pixels? It would cover many cells and thus this would be a problem when checking only the neighbor cells. But I can't re-size my quad-tree-grid every time a much larger object is inserted into the tree...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
相反，将对象放入单个单元格中，然后将它们放入与其发生碰撞的所有单元格中。这样您就可以单独测试每个单元。使用指向对象的指针，这样就不会创建副本。此外，您只需要使用leavenodes 来执行此操作，因此无需将较高节点中包含的数据与较低节点中包含的数据组合起来。
Instead och putting objects into a single cell put them in all cells they collide with. That way you can just test each cell individually. Use pointers to the object so you dont create copies. Also you only need to do this with leavenodes, so no need to combine data contained in higher nodes with lower ones.
这是一个有趣的问题。也许您可以使用树高信息来扩展节点或单元格？如果你有一个更大的对象，那么最小的单元格将它与树的高度嵌套在一起。这就是谷歌或必应地图等地图应用程序的作用。
这里有一个类似解决方案的链接： http:// /www.gamedev.net/topic/588426-2d-quadtree-collision---各种大小。我将屏幕与四叉树混淆了。您可以通过简单的recussion来检查碰撞。
This an interesting problem. Maybe you can extend the node or the cell with a tree height information? If you have an object bigger then the smallest cell nest it with the tree height. That's what map's application like google or bing maps does.
Here a link to a similar solution: http://www.gamedev.net/topic/588426-2d-quadtree-collision---variety-in-size. I was confusing the screen with the quadtree. You can check collision with a simple recusion.
过度搜索
在搜索过程中，首先从最大的对象开始...
针对 QuadTreeNode.Centre.X 测试 Object.Position.X，并
针对 QuadTreeNode.Centre.Y 测试 Object.Position.Y；
...然后，通过取差值的绝对值，只要绝对值不大于对象的半径，就将对象视为位于特定子节点内...
...也就是说，当对象侵入该四边形:)
使用 AABB（轴对齐边界框）也可以完成同样的操作。
这里唯一真正需要注意的是，覆盖大部分屏幕的非常大的对象将强制搜索整个树。在这些情况下，可能需要采取不同的方法。
当然，这仅涉及测试其他所有内容的对象。为了确保世界上所有其他大型物体都被正确识别，您需要稍微改变您的四叉树...
使用多个外观
在四叉树的这个变体中，我们只将物体放置在叶节点中四叉树的，作为指针。较大的对象可能出现在多个叶节点中。
由于某些对象在树中具有多种外观，因此一旦对它们进行了测试，我们就需要一种方法来避免它们。
所以...
一个简单的布尔 WasHit 标志可以避免在命中测试过程中多次测试同一对象...并且可以对所有“命中”对象运行“清理”，以便它们为下一次测试做好准备。
虽然这是有道理的，但如果执行所有对所有的命中测试，这是浪费的。
所以......变得更聪明一点，我们可以通过在场景中的每个对象内部使用指针“ptrLastObjectTestedAgainst”来避免任何清理。这避免了在这次运行中重新测试相同的对象（指针在第一次遇到后设置）
在针对场景测试新对象时不需要重置（新对象有一个与上一个指针值不同）。这避免了像使用简单的 Bool 标志一样重置指针的需要。
我在对象大小差异很大的场景中使用了后一种方法，效果很好。
弹性四叉树
我还使用了“弹性”四叉树。基本上，您对每个四叉树节点中可以理想容纳的项目数量设置一个限制 - 但是，与标准四叉树不同，您允许代码在特定情况下覆盖此限制。
这里最重要的规则是，一个对象不能被放置到一个不能完全容纳它的节点中......顶部节点捕获任何大于屏幕的对象。
因此，小对象将继续“掉落”以形成规则的四叉树，但大对象不会总是一直掉落到叶节点 - 而是会扩展最后适合它们的节点。
将非叶节点视为当对象从树上落下时“筛选”对象
这对于许多场景来说是一个非常有效的选择:)
结论
请记住，这些标准算法是有用的通用工具，但它们不能代替思考您的具体问题。不要陷入“仅仅因为众所周知”而使用特定算法或库的陷阱......您的应用程序是独特的，并且它可能会受益于稍微不同的方法。
因此，不要只是学习应用算法……从这些算法中学习，并以新颖且合适的方式应用这些原理本身。这些不是唯一的工具，也不一定最适合您的应用程序。
希望其中一些想法有所帮助。
Oversearching
During the search, and starting with the largest objects first...
Test Object.Position.X against QuadTreeNode.Centre.X, and also
test Object.Position.Y against QuadTreeNode.Centre.Y;
... Then, by taking the Absolute value of the difference, treat the object as lying within a specific child node whenever the absolute value is NOT more than the radius of the object...
... that is, when some portion of the object intrudes into that quad : )
The same can be done with AABB (Axis Aligned Bounding Boxes)
The only real caveat here is that VERY large objects that cover most of the screen, will force a search of the entire tree. In these cases, a different approach may be called for.
Of course, this only takes care of the object that everything else is being tested against. To ensure that all the other large objects in the world are properly identified, you will need to alter your quadtree slightly...
Use Multiple Appearances
In this variation on the QuadTree we ONLY place objects in the leaf nodes of the QuadTree, as pointers. Larger objects may appear in multiple leaf nodes.
Since some objects have multiple appearances in the tree, we need a way to avoid them once they've already been tested against.
So...
A simple Boolean WasHit flag can avoid testing the same object multiple times in a hit-test pass... and a 'cleanup' can be run on all 'hit' objects so that they are ready for the next test.
Whilst this makes sense, it is wasteful if performing all-vs-all hit-tests
So... Getting a little cleverer, we can avoid having any cleanup at all by using a Pointer 'ptrLastObjectTestedAgainst' inside of each object in the scene. This avoids re-testing the same objects on this run (the pointer is set after the first encounter)
It does not require resetting when testing a new object against the scene (the new object has a different pointer value than the last one). This avoids the need to reset the pointer as you would with a simple Bool flag.
I've used the latter approach in scenes with vastly different object sizes and it worked well.
Elastic QuadTrees
I've also used an 'elastic' QuadTree. Basically, you set a limit on how many items can IDEALLY fit in each QuadTreeNode - But, unlike a standard QuadTree, you allow the code to override this limit in specific cases.
The overriding rule here is that an object may NOT be placed into a Node that cannot hold it ENTIRELY... with the top node catching any objects that are larger than the screen.
Thus, small objects will continue to 'fall through' to form a regular QuadTree but large objects will not always fall all the way through to the leaf node - but will instead expand the node that last fitted them.
Think of the non-leaf nodes as 'sieving' the objects as they fall down the tree
This turns out to be a very efficient choice for many scenarios : )
Conclusion
Remember that these standard algorithms are useful general tools, but they are not a substitute for thinking about your specific problem. Do not fall into the trap of using a specific algorithm or library 'just because it is well known' ... your application is unique, and it may benefit from a slightly different approach.
Therefore, don't just learn to apply algorithms ... learn from those algorithms, and apply the principles themselves in novel and fitting ways. These are NOT the only tools, nor are they necessarily the best fit for your application.
Hope some of those ideas helped.