Take the 2-minute tour ×




Addition of any auxilary data is possible.

share|improve this question
add comment

8 Answers

up vote 7 down vote accepted


See: http://en.wikipedia.org/wiki/Octree



share|improve this answer
add comment


share|improve this answer
add comment


share|improve this answer
add comment




share|improve this answer
add comment





share|improve this answer
add comment


share|improve this answer
add comment


share|improve this answer
add comment

Another possibility, simpler than creating a kd-tree or and octree, is using a neighborhood grid.

I will explain the concept for 2D, but this idea can be trivially extended to 3D.

First place all your points into a 2D square matrix. Then you can run a full or partial spatial sort, so points will became ordered inside the matrix.

Points with small Y could move to the top rows of the matrix, and likewise, points with large Y would go to the bottom rows. The same will happen with points with small X coordinates, that should move to the columns on the left. And symmetrically, points with large X value will go to the right columns.

After you did the spatial sort (there are many ways to achieve this, both by serial or parallel algorithms) you can lookup the nearest points of a given point P by just visiting the adjacent cells where point P is actually stored in the neighborhood matrix.

You can read more details for this idea in the following paper (you will find PDF copies of it online): Supermassive Crowd Simulation on GPU based on Emergent Behavior.

The sorting step gives you interesting choices. You can use just the even-odd transposition sort described in the paper, which is very simple to implement (even in CUDA). If you run just one pass of this, it will give you a partial sort, which can be already useful if your matrix is near-sorted. That is, if your points move slowly, it will save you a lot of computation.

If you need a full sort, you can run such even-odd transposition pass several times (as described in the following Wikipedia page):


Another possibility is to implement the spatial sort alternating X and Y passes and using Shell-sort, to achieve a more efficient full sort:


Personally I think it is a wonderful solution (have implemented it myself), but still almost unknown.

share|improve this answer
add comment

Your Answer


