Jump to content
  • Advertisement
Sign in to follow this  
KulSeran

Spatial Partitions?

This topic is 4620 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
I hope I understand what you are trying to do...

// find the bounding box/cube that will enclose all the spheres in the group
vector 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/cube




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)

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 collided
AAA CCCC
BBBB




3.) there are others Octtree is one of them.

Share this post


Link to post
Share on other sites
Thanks for the response,
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!