四叉树会自动自排序吗？
Do quadtrees automatically self sort?
假设我有一个四叉树。
假设我里面有一个移动的物体。
我知道当你添加和删除节点时四叉树会自动排序，但是当一个节点，比方说在他的更新函数中移动到另一个不相关节点的左边时会发生什么？
或者基本上这个节点传送？
四叉树发生了什么？
我需要重建它吗？
我只是无法理解四叉树是否会在您仅更新节点数据时自动进行自我排序，或者我是否需要在更新节点时重建整棵树。
我见过人们为每帧移动的对象实现四叉树的方法有很多，包括为此目的使用松散的四叉树，其中甚至允许节点具有重叠的 AABB，这些 AABB 作为对象扩展和收缩存储在树叶中移动。
就是说，我发现它足够简单，可以相当便宜地更新非松散版本（虽然不像空间散列或网格那样便宜，但足够便宜以在大量实体移动的情况下保持稳定的帧速率围绕碰撞检测）。
简单的方法是在移动之前从树中删除元素，移动它，然后将它重新插入到树中。删除元素时，请检查它所属的节点。如果它们变为空（没有存储元素，没有子元素），则将它们从父元素中移除。如果父节点变为空（该节点中没有存储子节点，如果您将元素存储在分支中，则该节点中没有元素），然后从祖父节点中删除父节点，然后重复。
加快速度的技巧是避免过多的内存分配。如果您为节点使用空闲列表，它会有所帮助，例如另一种可能加快速度的方法是检测对象何时不会从一个节点移动到另一个节点。
例如，您可以通过时间步长乘以其速度来扩展实体的边界框或球体，并测试扩展的边界 box/sphere 是否与新节点重叠。如果不是，您不需要从树中移除元素、移动它并重新插入。您可以继续并简单地移动它。或者你可以只存储它之前的位置，移动它，然后看看它是否属于不同的节点。如果是这样，删除元素，就好像它有以前的位置，然后重新插入新位置。我还没有真正发现这是必要的，尽管我可以通过索引操作而不是堆来完成大部分这些事情 allocations/deallocations.
假设我有一个四叉树。 假设我里面有一个移动的物体。
我知道当你添加和删除节点时四叉树会自动排序，但是当一个节点，比方说在他的更新函数中移动到另一个不相关节点的左边时会发生什么？ 或者基本上这个节点传送？
四叉树发生了什么？ 我需要重建它吗？
我只是无法理解四叉树是否会在您仅更新节点数据时自动进行自我排序，或者我是否需要在更新节点时重建整棵树。
我见过人们为每帧移动的对象实现四叉树的方法有很多，包括为此目的使用松散的四叉树，其中甚至允许节点具有重叠的 AABB，这些 AABB 作为对象扩展和收缩存储在树叶中移动。
就是说，我发现它足够简单，可以相当便宜地更新非松散版本（虽然不像空间散列或网格那样便宜，但足够便宜以在大量实体移动的情况下保持稳定的帧速率围绕碰撞检测）。
简单的方法是在移动之前从树中删除元素，移动它，然后将它重新插入到树中。删除元素时，请检查它所属的节点。如果它们变为空（没有存储元素，没有子元素），则将它们从父元素中移除。如果父节点变为空（该节点中没有存储子节点，如果您将元素存储在分支中，则该节点中没有元素），然后从祖父节点中删除父节点，然后重复。
加快速度的技巧是避免过多的内存分配。如果您为节点使用空闲列表，它会有所帮助，例如另一种可能加快速度的方法是检测对象何时不会从一个节点移动到另一个节点。
例如，您可以通过时间步长乘以其速度来扩展实体的边界框或球体，并测试扩展的边界 box/sphere 是否与新节点重叠。如果不是，您不需要从树中移除元素、移动它并重新插入。您可以继续并简单地移动它。或者你可以只存储它之前的位置，移动它，然后看看它是否属于不同的节点。如果是这样，删除元素，就好像它有以前的位置，然后重新插入新位置。我还没有真正发现这是必要的，尽管我可以通过索引操作而不是堆来完成大部分这些事情 allocations/deallocations.