Live data from Hacker News

Functional Quadtrees

lbjgruppen.com

21–30 of 52 posts

Re: Functional Quadtrees

#21
post #12

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.

That is why I like harmonic app, there is an invite button separating the upvote and downvote. Never going to have this kind of issue

Re: Functional Quadtrees

#23

I 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.

> positions are encoded as strings over the alphabet on 2 bits

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

#24
post #13

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.

I'd love to see that. Could you link me to an implementation or explain this in more detail please?

I would like to know about this more, too. Is there a code anywhere, ideally with comments? But I am fine without comments, too, I would just like to see the code and possibly with an example usage.

Re: Functional Quadtrees

#25

A 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…

In 3D this has to be dealt with in the form of polygons and I think it was common when people were using acceleration grids and kd-trees to split the polygons so they fit neatly.

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

#27
post #12

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.

I just implemented an HN UI. This is good feedback as I'm aiming to have a mobile friendly web version.

https://proc0.github.io/HackerZen (it's also open source)

Re: Functional Quadtrees

#28

I 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…

Dammit why these books have to be $60

Re: Functional Quadtrees

#29

We just did a whole visual identity around the quadtree concept. Take a scroll on this one! https://trace.systems/

That is a cool visualization of a quad tree. I use quadtrees in geospatial applications (to partition lat longs) but this is the time I’ve seen it used to render a photo.

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

#30

A 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…

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

Post reply on HN