How to handle objects at the edges of spatial partition cells?

Question

A lot of games store object positions as floats and have a closed ball for the game area (eg. a rectangle and objects are allowed to have position coordinates on all 4 edges).

However, this becomes problematic when partitioning the game area (eg. gridding/quadtrees). The edge cases would have to be added in so that 2 edges of the game area are included in rectangles that touch them or objects on 2 edges would have to be missed out in the partition.

---

Is there another solution to this or do games (and other programs this applies to) usually go with one of the above 2?

(One solution is to use integer coordinates, but what if using floats is unavoidable?)

Answer 1

The simple answer would be to add the object's pointer to both cells. As it exists in both cells, to not include it in both cells would be to circumvent the purpose of having the tree to begin with.

The more complicated answer would be to reexamine the purpose for which you're using the spatial partitioning. If this is for graphics and culling, the answer could go both ways. If you don't cull the object, it's not that big of a deal. If this is for broadphase collision detection, obviously not including the object in both cells will almost certainly produce missed collisions.

The best answer would be to use something like a dynamic AABB tree such as an R-tree or R*-tree in which the cells are not limited to simple volume-based binary subdivision.

---

I run my school's physics club, and I recently spoke with Erin Catto when he came to give his 2019 GDC presentation on dynamic bounding-volume hierarchies to our club. The main takeaway is that the data structure you use and the heuristics employed will be dependent on the scale and purpose of the implementation. I suggest visiting the GDC vault and watching his presentation as he delivers excellent anecdotal information that you may be able to relate to your current problem.

Answer 2

Another way to slice this is to modify your collision checks so you check each object against everything after it in its own cell and also everything in the cells bellow or to the left but not above. (This pattern ensures that each pair is still checked only once: for the remaining neighbouring cells we didn't check, this current cell will be one of their checked neighbours)

Handling it this way, each object can "belong" to only one cell, even if it touches or straddles the border between two cells. You can make your cells smaller to keep the overall number of pairs checked similar, as long as the largest single object is less than two cells wide (so its center can be just on the edge of one cell, without reaching past its immediate neighbouring cell).