Original Post
In two recent projects, I needed a lean way for points to query a neighborhood around themselves; my problem reduces to the collision detection of a soup of spheres. Since my primitive is so basic, the problem is basically a broad phase algorithm. Furthermore, I can't take advantage of coherence because my points are moving fast. The solution that I have devised and currently testing is as located at http://www.mathgladiator.com/code/QuickNeighborhood.cpp, and I would like feedback as to the potential of using it in games. I only have one big assumption, namely all the spheres are the same size. After I complete my testing, I aim to optimize the algorithm; the current version has... imperfections. My current benchmark is included in the code. I tested 10,000 spheres of radius 0.1 uniformly distributed inside a box with all dimensions 1; it generates 194,593 intersections in 0.254453 seconds.
