Spatial Partitions?
Author
I've been trying to get my particle system working recently.
One thing I wanted to do was let the particles interact with eachother. In the simplest case, they collide.
The problem is you can't just loop through everything O(N^2), so an octree
or the like would work, but I was thinking about the conditions where a particle
can interact over a range of distances. But, i have a few questions.
Each particle has a sphere of influence.
Node Spheres are generated to encapsulate every set of previous level spheres that happen to touch/encapsulate. ( where is the forum faq on how to post a picture of my idea?)
Then there are large spheres for visibility testing on the system, and there are set spheres that let you pick a particle, go up one level, then back down a level to all particles that are within influence range.
But, how do you come up with a center and radius for a sphere that encapsulates X other spheres?
[Edited by - KulSeran on October 9, 2005 7:33:21 PM]
I hope I understand what you are trying to do...
However, there is one problem with this. The bounding sphere will be bigger than what you really want if your other smaller bounding spheres are lined up along each of the X,Y, and Z axis. If this is too big of a radius you can scan each of the smaller bounding spheres and locate the sphere that is the furthest away using dist between centers and adding the smaller spheres radius.
Depending on how many spheres there are you could mark each of the bounding spheres that influenced the bounding box/cube and scan those again.
Solving your O(N^2) problem
Looping through everything is O(N^2) but do you really need to
1.) If A colided with B, do I really need to check if B colided with A, which would be less than the O(N^2)
2.) sort your space based on objects bounding spheres (center.x-radius) coordinates.
Scan the list and if the radius +/- the center is overlaping in the X check the other Y and Z coordinates to see if a deeper collision test will need to be done.
3.) there are others Octtree is one of them.
// find the bounding box/cube that will enclose all the spheres in the groupvector min, max;foreach (sphere in group){ if (sphere.x-sphere.radius > min.x){ min.x = sphere.x-sphere.radius; } if (sphere.y-sphere.radius > min.y){ min.y = sphere.y-sphere.radius; } if (sphere.z-sphere.radius > min.z){ min.z = sphere.z-sphere.radius; } if (sphere.x+sphere.radius > max.x){ max.x = sphere.x+sphere.radius; } if (sphere.y+sphere.radius > max.y){ max.y = sphere.y+sphere.radius; } if (sphere.z+sphere.radius > max.z){ max.z = sphere.z+sphere.radius; }}// make a bounding sphere out of that box/cube// center of box/cubeis the center of the sphere// find the distance between the center of box/cube to any corner of the box/cubeHowever, there is one problem with this. The bounding sphere will be bigger than what you really want if your other smaller bounding spheres are lined up along each of the X,Y, and Z axis. If this is too big of a radius you can scan each of the smaller bounding spheres and locate the sphere that is the furthest away using dist between centers and adding the smaller spheres radius.
Depending on how many spheres there are you could mark each of the bounding spheres that influenced the bounding box/cube and scan those again.
Solving your O(N^2) problem
Looping through everything is O(N^2) but do you really need to
1.) If A colided with B, do I really need to check if B colided with A, which would be less than the O(N^2)
for(i = 1 to N){ for (j = i+1 to N){ // check for collision }}2.) sort your space based on objects bounding spheres (center.x-radius) coordinates.
Scan the list and if the radius +/- the center is overlaping in the X check the other Y and Z coordinates to see if a deeper collision test will need to be done.
// object C and B may have collidedAAA CCCC BBBB 3.) there are others Octtree is one of them.
Author
Thanks for the response,
Now that I have an idea of how to make the bounding sphere I will try to work it out.
This is true, but an Octtree takes a specific area like (-10,-10,-10) to (10,10,10)
and seperates it into smaller sections based on objects within that area. And if i want to check if 2 objects are colliding, I would have to check first the current grid, then find the ajacent grids and check them.
I was hopinh to make something that seperates things in space, but just gives me a list of groupings A is next to B and C, but C is next to A,B and D. So that when I check distance constraints on A I have 2 points to constrain, and from C i know i have 3 points to constrain, and there are no extranious checks between A and D, where an octree would probably tell me that there is a posibility that a check needs to be done.
Now that I have an idea of how to make the bounding sphere I will try to work it out.
Quote:
3.) there are others Octtree is one of them.
This is true, but an Octtree takes a specific area like (-10,-10,-10) to (10,10,10)
and seperates it into smaller sections based on objects within that area. And if i want to check if 2 objects are colliding, I would have to check first the current grid, then find the ajacent grids and check them.
I was hopinh to make something that seperates things in space, but just gives me a list of groupings A is next to B and C, but C is next to A,B and D. So that when I check distance constraints on A I have 2 points to constrain, and from C i know i have 3 points to constrain, and there are no extranious checks between A and D, where an octree would probably tell me that there is a posibility that a check needs to be done.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
