Earlier quoted context omitted.
You can even build them with basically one line of code by sorting points using Morton / Z-curve order. It's linear time if you use a counting/radix sort. Edit: lol, downvoted for this post. Never change, HN.
It’s super easy to click the downvote button by accident on mobile when you meant to upvote. And this UI will never be fixed because this is HN after all.
Functional Quadtrees
21–30 of 52 posts
Re: Functional Quadtrees
#22Re: Functional Quadtrees
#23I wish the article had made it clearer that quadtree positions are encoded as strings over the alphabet on 2 bits (similarly, octrees use the alphabet over 3 bits). This makes storing keys and lexicographically comparing them very simple.
This is the most pedantic way of saying "binary 2-tuples" I've ever seen. Also for quadtrees this is inferior to base 4 because you can assume clockwise (or counter) ordering.
Re: Functional Quadtrees
#24Earlier quoted context omitted.
You can even build them with basically one line of code by sorting points using Morton / Z-curve order. It's linear time if you use a counting/radix sort. Edit: lol, downvoted for this post. Never change, HN.
I'd love to see that. Could you link me to an implementation or explain this in more detail please?
Re: Functional Quadtrees
#25A general quadtree implementation question that puzzled me when I was implementing it myself for hobby games was: do you store a rectangle in the smallest node that completely contains it? Most code that I saw that used quadtrees were treating things as points and storing them only at the lowest level. I also made mine auto-divide by counting items that are entirely in a quadrant as they are added to the node, with a…
That being said most ray tracing seems to do bounding volume hierarchies now, so maybe a bvh is the best way to deal with things that have volume.
Re: Functional Quadtrees
#26We just did a whole visual identity around the quadtree concept. Take a scroll on this one! https://trace.systems/
What does that mean?
Re: Functional Quadtrees
#27Earlier quoted context omitted.
You can even build them with basically one line of code by sorting points using Morton / Z-curve order. It's linear time if you use a counting/radix sort. Edit: lol, downvoted for this post. Never change, HN.
It’s super easy to click the downvote button by accident on mobile when you meant to upvote. And this UI will never be fixed because this is HN after all.
https://proc0.github.io/HackerZen (it's also open source)
Re: Functional Quadtrees
#28I like to do data-oriented programming, and was just thinking about how I want to organize (and search through) the primary data structures/concepts for a project I'm working on. Part of that involved thinking about things like what information I might cache and what representations data might take. That lead me to looking into the nuances of things like B-Trees, AVL Trees, Quadtrees, k-d trees and so forth. I've fou…
Re: Functional Quadtrees
#29We just did a whole visual identity around the quadtree concept. Take a scroll on this one! https://trace.systems/
Quad trees are abstract until you see what they look like. It’s a clever method to partition 2D points.
(Kd trees are even better)
Re: Functional Quadtrees
#30A general quadtree implementation question that puzzled me when I was implementing it myself for hobby games was: do you store a rectangle in the smallest node that completely contains it? Most code that I saw that used quadtrees were treating things as points and storing them only at the lowest level. I also made mine auto-divide by counting items that are entirely in a quadrant as they are added to the node, with a…
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