Return to Answer

Also both a quad-tree and grid don't do a magnificent job if you have a number of large elements that span much of the entire scene, but at least the grid stays flat and doesn't subdivide to the nth degree in those cases. The quad-tree should store elements in branches and not just leaves to reasonably handle such cases or else it will want to subdivide like crazy and degrade in quality extremely rapidly. There are more pathological cases like this you have to take care of with a quad-tree if you want it to handle the widest range of content. The grid has an appeal that it does a decent job, kind of a jack-of-all-trades, against a wide range of inputs, and it takes a very steady and predictable amount of memory no matter what you do (32-bit overhead per cell, 32-bit overhead per element inserted in cell).

Also both a quad-tree and grid don't do a magnificent job if you have a number of large elements that span much of the entire scene, but at least the grid stays flat and doesn't subdivide to the nth degree in those cases. The quad-tree should store elements in branches and not just leaves to reasonably handle such cases or else it will want to subdivide like crazy and degrade in quality extremely rapidly. There are more pathological cases like this you have to take care of with a quad-tree if you want it to handle the widest range of content. For example, another case that can really trip up a quad-tree is if you have a boatload of coincident elements. At that point some people just resort to setting a depth limit for their quad-tree to prevent it from subdividing infinitely. The grid has an appeal that it does a decent job, kind of a jack-of-all-trades, against a wide range of inputs, and it takes a very steady and predictable amount of memory no matter what you do (32-bit overhead per cell, 32-bit overhead per element inserted in cell).

The other one that I find extremely useful is that your classic rasterization algorithms for drawing shapes can be used to do searches into the grid. For example, you can use Bresenham line rasterization to search for elements that intersect a line. Since I work a lot in image processing, it's really nice to be able to use the exact same optimized code I use to plot pixels to an image as I use to detect intersections against moving objects in a grid.

The other one that I find extremely useful is that your classic rasterization algorithms for drawing shapes can be used to do searches into the grid. For example, you can use Bresenham line rasterization to search for elements that intersect a line, scanline rasterization to find what cells intersect a polygon, etc. Since I work a lot in image processing, it's really nice to be able to use the exact same optimized code I use to plot pixels to an image as I use to detect intersections against moving objects in a grid.

Sorry for resurrecting ancient thread but IMHO plain old grids aren't used often enough for these cases. There's lot of advantages to a grid in that cell insertion/removal is dirt cheap. You don't have to bother with freeing a cell since the grid has no aim to optimize for sparse representations.

Sorry for resurrecting ancient thread but IMHO plain old grids aren't used often enough for these cases. There's lot of advantages to a grid in that cell insertion/removal is dirt cheap. You don't have to bother with freeing a cell since the grid has no aim to optimize for sparse representations. I say that having reduced the time to marquee select a bunch of elements in a legacy codebase from over 1200ms down to 20ms by just replacing the quad-tree with a grid. In fairness though, that quad-tree was really poorly implemented, storing a separate dynamic array per leaf node for the elements.