What is an infinite scaleless quadtree called?
Asked Answered
M

2

8

2D spatial indexing question:

What do you call a data structure that is essentially an infinite* quadtree whose nodes contain neither absolute coordinates nor absolute scales -- in which the coordinate system of each node has been normalized to the unit square (0,0)-(1,1), and in which the top-level node is not fixed absolutely?

It's a quadtree, of course -- but what type of quadtree is it? (Is there a common name? I've seen dozens of types of quadtrees named and defined in the literature, but not this particular one.)

To render a scene, you are given some starting node (not necessarily the root), its size in pixels, and its location on the screen. You then draw all objects within the node by scaling their coordinates using a current transformation matrix, which you push on the stack and halve as you go down the tree. The absolute coordinates of the nodes are thus available only though temporary work variables during rendering, and are not contained within the data structure itself.

If an object within a node moves outside of the node (e.g., outside the unit square), you pass it to the parent for reassignment to another node. If an object becomes fragmented (for example, an asteroid hit by a bullet), the smaller portions are passed down to children nodes, who must scale the coordinates appropriately to maintain the unit-square normalization within each node.

The key difference here from traditional quadtree implementations used in spatial indexing is that the coordinates of objects are always relative to the coordinate system of the node within which they are contained. This relativism applies not only to position but also to scale.

* Infinite for the lack of absolute coordinates; even double-precision floating-point coordinates impart limits on position and size when used for absolute positioning.

Mercedes answered 7/2, 2010 at 2:58 Comment(2)
(I know this 12 years old but I'm commenting anyway.) When you go outside the root node, what happens? Does a larger root node get created? I would say there's no real name for this type of quadtree. It's just a regular quadtree, you're just using it a bit differently than most people would (storing relative transforms instead of absolute). Cool idea though. I wonder if a similar thing could be used for positioning objects in a space game without requiring 64-bit numbers.Conveyancing
Exactly, yes. If you go outside the root node, say to expand the universe, then a new root node is created.Mercedes
G
2

Yeah it's a uh.. "wrapped-grid-nested quadtree"? You're only limited to the highest and lowest int32 value if that's what you're using for grid-coords.

Globuliferous answered 24/3, 2011 at 6:50 Comment(0)
M
1

You have a grid of quadtrees from what it sounds like. Between each square of integer coordinates you seem to be constructing a quadtree on that part of the grid.

Metralgia answered 5/7, 2010 at 20:4 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.