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)