Use quadtrees to improve efficiency of eignverb collision detection in reverb model

[campreilly]

A quadtree (http://en.wikipedia.org/wiki/Quadtree) is a tree data structure that supports efficient searches in two-dimensional space. Quadtrees are frequently used in game design to improve the efficiency of collision detection in two dimensions. If we were to store our eigenverbs in quadtrees, if might have a significant impact on the efficiency of searching for "impacts" between source and receiver eigenverbs.

This is going to take some serious research and design on our part before we are ready to begin coding?

• Should we try to find and re-use an off-the-shelf implementation that mirrors the structure of other STL containers? What would be the advantages of building our own?
• How should the length, width, and orientation of the eigenverbs effect their placement in the quadtree? By analogy, look at this article (http://gamedevelopment.tutsplus.com/tutorials/make-your-game-pop-with-particle-effects-and-quadtrees--gamedev-2138) for example of organizing simple polygons in a quadtree.

[Tibonium]

Noting here that width/height of eigenverbs are now a function of frequency and so the logic for choosing collisions is more difficult than had they been frequency independent, which they shouldn't but were at the time.

[campreilly]

Perhaps we can use the fact that the widths should always the largest at the lowest frequencies to mitigate this effect. We tried this in the past with intensity thresholds, and that had problems. But the equations for width (wave-queue.cc lines 1068-1087) really do appear to be monotonically increasing with frequency.

[campreilly]

While searching for some guidance on quad_trees, I ran into an interesting discussion of the boost::geometry::index::rtree class as a scheme for storing and querying 2-D data.

Discussion: http://stackoverflow.com/questions/16824386/any-good-range-query-libraryusing-k-d-tree-quad-tree-or-r-tree-in-c

Example: http://www.boost.org/doc/libs/1_54_0/libs/geometry/doc/html/geometry/spatial_indexes/rtree_examples/specializing_index__indexable_function_object___storing_shared_pointers_in_the_rtree.html

[islanderjtn]

Implemented eigenveb collision detection using Boost RTrees. See Pull Request 229.