Original Post
Referring to my first topic on this board about a collision detection for a huge number of spheres with different radius:
http://www.gamedev.net/community/forums/topic.asp?topic_id=507622
I've been working on that problem on and off during the past few years.
I've considered reduction of the problem to 2 dimensions, but this isn't practical due to high clustering of spheres around the origin that my application will have.
I've considered problem division into each dimension and then comparing the results, but it turned out to be too expensive if you have a huge space to deal with, too.
Finally, I came back to my initial approach. I divide the space into fixed size cubes (sections) and only spheres inside a section are tested against each other. For each tick, I have to check when a sphere enters and leaves a new section, but I do this on each coordinate separately , so the problem division comes into play after all. Of course, whenever a sphere is in 2 sections, it will be included in both computations. In order to allow for completely fair collisions, it would be preferable to just treat both these sections like they were a single one. This means that the sections shouldn't be too big if you don't want clustering of sections too become too expensive. As the spheres get bigger, though, you also need bigger sections to avoid too much clustering. I guess the key lies in finding the right section size, so I will probably start experimenting with variable size sections (probably with an octree approach) for fine-tuning. Additionally, I can put another check into each section, for instance by reducing the problem to 2D inside each section, which might make section clustering have less of an impact on performance.
Anyway, any kind of advice or additional inspiration is more than welcome. I will keep you updated on the final approach.
As it currently looks, it's reasonable to assume that the number of separate entities will be somewhere around 100,000 as a maximum, so I will definitely be able to realize my goal.
http://www.gamedev.net/community/forums/topic.asp?topic_id=507622
I've been working on that problem on and off during the past few years.
I've considered reduction of the problem to 2 dimensions, but this isn't practical due to high clustering of spheres around the origin that my application will have.
I've considered problem division into each dimension and then comparing the results, but it turned out to be too expensive if you have a huge space to deal with, too.
Finally, I came back to my initial approach. I divide the space into fixed size cubes (sections) and only spheres inside a section are tested against each other. For each tick, I have to check when a sphere enters and leaves a new section, but I do this on each coordinate separately , so the problem division comes into play after all. Of course, whenever a sphere is in 2 sections, it will be included in both computations. In order to allow for completely fair collisions, it would be preferable to just treat both these sections like they were a single one. This means that the sections shouldn't be too big if you don't want clustering of sections too become too expensive. As the spheres get bigger, though, you also need bigger sections to avoid too much clustering. I guess the key lies in finding the right section size, so I will probably start experimenting with variable size sections (probably with an octree approach) for fine-tuning. Additionally, I can put another check into each section, for instance by reducing the problem to 2D inside each section, which might make section clustering have less of an impact on performance.
Anyway, any kind of advice or additional inspiration is more than welcome. I will keep you updated on the final approach.
As it currently looks, it's reasonable to assume that the number of separate entities will be somewhere around 100,000 as a maximum, so I will definitely be able to realize my goal.
