I'm trying to get something similar to the Nearest Neightbor Problem, except I only want neighbors with radius overlapping a radius, and all of them.
I'll explain my problem before explaining what I think I need. I have entities made out of voxels, where i want complete collision between all voxels. I'll do this by only doing collision checks for other entities within the maximum radius of the 'this' entity plus its velocity magnitude, including the radii of those other entities. That is a whole other problem in itself, but something that I can handle. What I need right now is a way of populating the list of collisions 'this' needs to check.
Take a set of entities with arbitrary size/radius, make lines/circles/spheres out of their radii; given one of those spheres, get a list of all other spheres which overlap it. Cubes would also work instead of spheres if its somewhy substantially faster.
Ofcourse I could just iterate over all entities, but that would be n^2 time, and I would like to have thousands of entities. I could perhaps bruteforce it with a compute shader, but I'd like to avoid that.
Sofar I've been thinking have a k-tree store all entity positions, then have each entity make a sort of footprint on the nodes as one step, in the next step, check for nodes belonging to this which also have the footprint of another entity. So how do I make a quadtree in a way which I can set and get footprints from in a way that isnt hideous? Or is there a completely different better way?
edit: found this paper but its quite over my head
