Dx11 adjacent coordinates with compute shader

simple question:
i have a buffer filled with points in 3d space. for each point i want to get all adjacent points within a certain range.

has anyone ideas how to achieve that without going through all points and testing if it is a neighbor? im thinking of a clever way to sort the buffer …

thanks for any input!

There’s no “simple” way to do that.

Basically there are several ways to do it, either use a sort, there’s some examples in cuda/directx sdk.

You can also build a grid data structure, either do a linked list (fast to build, slow to lookup), or a histopyramid (bit slower to build, but much faster to lookup, specially since you can sample larger cells in one go).

Explains histopyramid principles. In your case it’s a bit different but it show the concept.

Depending of what you need to do with neighbour, each technique can have advantages.

For simple forms of “connect all” (with a rather low radius) linked list will do just fine.

If you need a lot of neighbour lookup (swarms/sph), histopyramid will give you a better tradeoff despite the slower build.

here i have a example for the marching Tetrahedrons Algorithm.
It’s not realy clean, it’s just work in progress.

Maybe i will release later as contribution or add to dx11 girlpower.

here is the discripion of the Algorithm.

http://friesboury.be/documents/Geometry%20Shader%20-%20Metaballs.pdf

marching Tetrahedrons Metaballs Algorithm (251.9 kB)