logoalt Hacker News

pengarutoday at 6:18 PM0 repliesview on HN

When I made a quadtree for some simple 2d games I handled AABB areas, since it was aimed at broad-phase collision detection of what were essentially sprites just rendered w/GL.

Similar to yours I split the leaf nodes when they became too full, with some simple fixed threshold defining "full". Only leaf nodes contained references to the indexed objects, and all overlapping leaf nodes would reference the objects they overlapped. Search queries were done also using an AABB, and would iteratively invoke a callback for all overlapping object AABBs found in the overlapping leaf nodes. IIRC the object references hanging off the leaf nodes had a fixed number of linked list slots to be put on a results list during a search, to deduplicate the results before iterating that list with the provided candidate-found callback. Since any given indexed object could be on many leaf nodes in the index, if they spanned a large area shared with a high density of other indexed objects for instance.

It was up to the callback to do the narrow-phase collision detection / control the results list iterating stop vs. continue via return value.

I recall one of the annoyances of sticking the search results linked list entry in the object references hanging off the leaf nodes was it set a limit to the number of simultaneous searches one could perform against the index. Basically the game would initialize the index with a fixed maximum concurrent number of searches to handle, and that set the number of results-linked-list slots the object references would be allocated to accommodate. As long as that was never exceeded it worked great.

It's been a while so I may have gotten it wrong, but that sounds right to me.

Not sure what the most common approaches are...

The C source is @ https://git.pengaru.com/cgit/libix2/.git/tree/src/ix2.c