Hacker News Reader

Comment by mattnewport | Hacker News Reader

Coming from a games background, I've not heard of an R tree before. Quadtrees (or octtrees for 3D) are probably the most common spatial query data structure used in game engines. I'm surprised they weren't mentioned in the article. Gonna have to do some research on what the pros and cons of an R tree are vs a quadtree now.

View on HN

R-trees are relatively slow, particularly if you have a very high mutation rate. Their sole redeeming feature is that they can handle non-point geometries with constant space complexity whereas quad-trees have pathological space complexity for geometries like polygons.

If you are just dealing with points, an R-tree is a poor algorithm choice. Quad-trees are pretty close to ideal in terms of performance for that use case.

I've found octtrees quite useful for geometric primitives. There is the pathological case of long thin objects, but I place those in a large number of small nodes rather than one large node. Insert and delete are generally O(log n).

> quad-trees have pathological space complexity for geometries like polygons

Any idea what is used in the wild for closest point queries against non-point data (triangle meshes or otherwise)?

Quadtrees are fine. Just don't approximate the polygon to the limit of resolution of the space. I wrote a paper many years ago on a related problem. The conclusion was that a very small number of quads would be optimal. Too many is obviously a problem; too few and you have to filter out a lot of false negatives.

The paper was in ACM SIGMOD 89, Redundancy in Spatial Databases.

I imagine that you are working in a domain where it is true that R-Trees are slow and only have the one redeeming quality. Anything that I've done involving things on a screen have performed better with quadtrees for me, so I'm not discounting your experience at all.

In other domains though, R-Trees have many other advantages, and often perform better.

http://www.dpi.inpe.br/livros/bdados/artigos/oracle_r_tree.p...

"For these datasets, R-trees consistently outperformed Quadtrees by 2-3 times" ... "In short, a quadtree could be recommended for update-intensive applications using simple poly-gon geometries, high concurrency update databases, or when specialized masks such as touch are frequently used in queries. However, users have to fine-tune the tiling level to obtain best performance. R-trees, which do not require any such tuning, could be used in all other cases to obtain nearly equivalent or better performance."

Octrees can be used for non-point geometries too. You just have to store some geometries at non-leaf nodes. When inserting, you search the tree for the deepest voxel which encapsulates the entire geometry (or, equivalently, its bounding box). At least that's how I've always done it.

The advantage of R-trees and kd-trees is that you can partition the space more intelligently. With octrees, a voxel is always divided into eight equal children, even if one of the eight children will contain all the points/geometries. It's usually not a big problem, but if you have a few small objects with lots of detail and far from the origin, you might get a poorly-balanced octree with some very deep branches.

As you mention, R-trees and kd-trees have slow insertion, but if you're path tracing a static scene and the rendering is going to take hours, you don't really care about that.

Reply on news.ycombinator.com