什么是无限无量纲四叉树？

Question

二维空间索引问题:

你称之为基本上是无限*四叉树的数据结构,其节点既不包含绝对坐标也不包含绝对尺度 - 其中每个节点的坐标系已经标准化为单位平方(0,0) - (1,1 ),顶级节点绝对没有固定？

当然,这是一个四叉树 - 但它是什么类型的四叉树？(有一个共同的名称吗？我已经看到了文献中命名和定义的几十种类型的四叉树,但不是这个特别的.

要渲染场景,您将获得一些起始节点(不一定是根),其大小(以像素为单位)以及它在屏幕上的位置.然后,您可以通过使用当前变换矩阵缩放其坐标来绘制节点内的所有对象,当您向下移动树时,您可以将其推入堆栈并减半.因此,节点的绝对坐标仅在渲染期间通过临时工作变量可用,并且不包含在数据结构本身内.

如果节点内的对象移动到节点之外(例如,在单位方块外),则将其传递给父节点以重新分配给另一个节点.如果对象变得碎片化(例如,子弹击中小行星),则较小的部分向下传递给子节点,子节点必须适当地缩放坐标以维持每个节点内的单位平方归一化.

与空间索引中使用的传统四叉树实现的关键区别在于,对象的坐标始终相对于包含它们的节点的坐标系.这种相对主义不仅适用于立场,也适用于规模.

*缺乏绝对坐标的无限; 甚至双精度浮点坐标在用于绝对定位时也会限制位置和尺寸.

Answer 1

顾名思义，你有一个四叉树网格。在每个整数坐标方格之间，您似乎在网格的该部分上构建了一个四叉树。