Space partitionning related questions

[Roland_Yonaba]

Hi all,

Well, I am actually working on some 2d physics experiments.
So far, the physics engine is doing well. Actually, I've reached the point where I have to deal with collisions detection/resolution.

First of all, my simulation is only about particles (for now). Assume a particle has:
- velocity, position and acceleration vectors
- a mass,
- a radius (to be drawn as full circles shapes)

All generated particles are listed in a simple array (Simulation.particles).
For each simulation timestep, I am using a kind of timed-controlled update system, inside love.update, as follows: (dt is provided by love.update callback, and is about 0.004 on my computer):

Code: Select all

function Simulation:update(dt)
  if dt <= 0 then return end
  self.__buffer = self.__buffer+dt
  local step = 0
  while (self.__buffer >= self.timestep and step < self.__steps) do
    step = step+1
    self:integrate(dt)
    self.__buffer = self.__buffer - dt
  end
end

Inside Simulation:update(), I am looping through all particles created to apply impulses, update their motion.
Then comes the part where I have to deal with collision/detection and resolution.

What I did first:
The first approach to this was a naïve attempt:

Code: Select all

local particle
  for i = 1,#self.particles do
    particle = self.particles[i]
    -- apply impulses
   -- update particle   
   for j = i+1,#self.particles do
     -- check for collision for the pair i,j
    -- resolve it
    end
  end

I also have to say, at this point, that the collision detection process is quite expensive (IMHO) just because it needs to call functions such as math.sqrt (I am dealing with circle shapes ).
But well, everything went right...for a simulation containing up to 100~300 particles.

But above this limit, I encountered severe framerate drops.
So, I said to myself: "don't bash Löve for that, as your approach may not be the best one."

The second approach:
So i figured out a way to narrow down the number of collision checks.
After making some search, I came accross space partitionning techniques. Well, there are lots of techniques, and making a quick review, it seemed to me spatial hashing was the simplest one.
Implementating won't be a problem (hopefully), but I have some of questions about it, before.

First, it is obvious that spatial hashing works well when the grid cell size parameter is well tuned.Not too high, but not too low.
So does this means I have to impose a maximum radius size to my particles ? So how would be the correct approach to this problem .

Second, maybe some of you have experienced different techniques (quadtrees, octrees, bsp, sweep and prune). Would you really recommend spatial hashing to me, based on your experienced and on what i am aiming to accomplish ?

Third, is it really safe to perform collision detection/resolution while updating particles ?
The alternative would be looping through the particles list, updating each one, and collect particles pairs colliding inside an array.
Then loop trhrough this array to resolve each collision (something that I have to experiment, also).

Okay, there are some others questions left, but i'll stop from now. I may be overthinking on some points, but that mostly due to my lack on experience on the topic. So i'll be happy to have some advises.

Thanks in advance.

[substitute541]

What I did first:
The first approach to this was a naïve attempt:

Code: Select all

local particle
  for i = 1,#self.particles do
    particle = self.particles[i]
    -- apply impulses
   -- update particle   
   for j = i+1,#self.particles do
     -- check for collision for the pair i,j
    -- resolve it
    end
  end

I also have to say, at this point, that the collision detection process is quite expensive (IMHO) just because it needs to call functions such as math.sqrt (I am dealing with circle shapes ).
But well, everything went right...for a simulation containing up to 100~300 particles.

One thing, you are making too many unnecessary collisions in the nested loop. A little bit of optimizing will do the job.

Code: Select all

local particle
  for i=1, #self.particles do
     --update particle
  end

  for i = 1,#self.particles - 1 do
    particle = self.particles[i]
   for j = i+1,#self.particles do
     -- check for collision for the pair i,j
    -- resolve it
    end
  end

And yes you do need to use math.sqrt for detecting collisions.

If you don't know how my nested loop works, here's an example : Say you have 5 sprites. What you were doing before has this.

Code: Select all

sprite1 to sprite2, sprite3, sprite4, sprite5
sprite2 to sprite1, sprite3, sprite4, sprite5
sprite3 to sprite1, sprite2, sprite4, sprite5
sprite4 to sprite1, sprite2, sprite3, sprite5
sprite5 to sprite1, sprite2, sprite3, sprite4

Now you see some repetition. Sprite1 to Sprite2, and Sprite2 to Sprite1 is the same right? Surely Sprite1 and Sprite2 are not colliding, then Sprite2 and Sprite1 are also not colliding! After some optimization you wound up with this :

Code: Select all

sprite1 to sprite2, sprite3, sprite4, sprite5
sprite2 to sprite3, sprite4, sprite5
sprite3 to sprite4, sprite5
sprite4 to sprite5
sprite5 to nothing!

Sprite5 doesn't have to check collisions with anything, since the other sprites are already checking collisions for it! And you wound up with the optimized loop.

[ivan]

Hi Roland!

I also have to say, at this point, that the collision detection process is quite expensive (IMHO) just because it needs to call functions such as math.sqrt (I am dealing with circle shapes ).

I doubt math.sqrt would be a bottleneck in your case.
However, depending on the algorithm that you have, you may be able to avoid using math.sqrt:

Code: Select all

local radii = particle1.radius + particle2.radius
local dx, dy = particle1.x - particle2.x, particle1.y - particle2.y
local distSq = dx*dx + dy*dy
if distSq > radii*radii then
 -- no collision
  return
end

Second, maybe some of you have experienced different techniques (quadtrees, octrees, bsp, sweep and prune). Would you really recommend spatial hashing to me, based on your experienced and on what i am aiming to accomplish ?

Sure, I'd definitely recommend spatial hashing or any type of grid-based partitioning.
Quadtrees are more complicated (often a bit slower) but allow you to partition objects which are extremely varied in size (which is NOT true in your case). Octree is basically a quadtree in 3D.
I've read very little about BSP trees but from what I gather they are mostly used to partition static geometry so when you have a lot of moving objects then BSP might not be the ideal approach.
I don't know much about sweep and prune either but it might be worth investigating since it looks like it might be applicable in your case.

Third, is it really safe to perform collision detection/resolution while updating particles ?
The alternative would be looping through the particles list, updating each one, and collect particles pairs colliding inside an array.
Then loop trhrough this array to resolve each collision (something that I have to experiment, also).

Sure. I personally think it's better to separate the collisions into a separate phase but it's a question of preference really.
Just be careful if you plan on deleting particles during table iterations so that your tables don't get out of sync.
In general, I would advise against creating intermediate tables as much as possible especially during each update frame.

Okay, there are some others questions left, but i'll stop from now. I may be overthinking on some points, but that mostly due to my lack on experience on the topic. So i'll be happy to have some advises.

Yep, the whole partitioning business is just a way to optimize your script. I wouldn't worry about it too much.

[Roland_Yonaba]

Thanks all for the answers.

One thing, you are making too many unnecessary collisions in the nested loop. A little bit of optimizing will do the job.

That's already what i'm doing.

However, depending on the algorithm that you have, you may be able to avoid using math.sqrt

Actually, what i'm doing is not so far from that. here is an excerpt:

Code: Select all

function Collision:apply(p, dt, index)
  if not p.collideable then return end
  for i=index+1,#self.__pool do
    local pI = self.__pool[i]
    if pI.collideable then
      local distSq = self._delta:squaredMagnitude()
      local radii = p.radius+pI.radius
      local radiiSq = radii*radii
      if (distSq <= radiiSq) then
        local interpenetration = (radii - sqrt(distSq))      
      -- etc : collision resolution
      end
    end
  end
end

Sure, I'd definitely recommend spatial hashing or any type of grid-based partitioning.
Quadtrees are more complicated (often a bit slower) but allow you to partition objects which are extremely varied in size (which is NOT true in your case). Octree is basically a quadtree in 3D.
I've read very little about BSP trees but from what I gather they are mostly used to partition static geometry so when you have a lot of moving objects then BSP might not be the ideal approach.
I don't know much about sweep and prune either but it might be worth investigating since it looks like it might be applicable in your case.

Okay thanks for those informations. I'm actually looking at theory beyond spatial grids, but I'll also consider implementing quadtrees and sweep and prune. Dreadkillz made a great work on that, so i'd better take a closer look at that.

[kikito]

Okay thanks for those informations. I'm actually looking at theory beyond spatial grids, but I'll also consider implementing quadtrees and sweep and prune. Dreadkillz made a great work on that, so i'd better take a closer look at that.

I've done both quadrees and spatial grids, and I came to the conclusion that the later are both faster and simpler to implement.

In both cases, the tricky parts for me where:

1- handling the edge cases - in other words, handle things correctly when the borders of one item just "touch" (but don't cross) the borders of one cell/quadtree node. (answer: You choose one direction for each axis; i.e. include the item in the cell if it touches the bottom or left, but not the up or right borders). Testing this kind of stuff was maddening.
2- Moving stuff/multipass: I opted for limiting the max velocity of all my objects just so that I didn't have to deal with this. In theory one should be able to iterate over all objects, see their velocities, and make smaller iterations, but it didn't seem worth it for me. I just let the lib user deal with pass-throughs, recommending moderating item speed.
3- Contiguous objects: Something as simple as walking over a tiled floor can be infuriatingly buggy if you don't sort collisions by some kind of heuristic (closer tiles to the player are evaluated first, and the rest are evaluated only after those have been resolved).

[dreadkillz]

Hello Roland! Any standard broad phase collision pruning method will work. I recommend spatial hash as its the simplest method to use. If your objects are of wildly different sizes, I recommend spatial hash still (It's that good!). But if you're curious, you can try to implement a sweep and prune (or just use mine!) as it works with objects of any sizes.

The only glaring weakness of sweep and prune is that it doesn't deal with many moving objects too well because of sorting per updates. The spatial hash structure + sweep and prune alleviates that problem.

Like Ivan said, the space partitioning is to optimize fps. you can worry about this last once you have your collision resolution method down. You can then implement your broad phase to give you that nice boost in fps.

[Roland_Yonaba]

Thanks all for the replies!

I've done both quadrees and spatial grids, and I came to the conclusion that the later are both faster and simpler to implement.

I shall obey.
Well, I am actually working on a spatial grid implementation, but with a specific a slight different approach. To summup, i've noticed that, in most of spatial grids implementation i've seen , the same object can be stored in more than one bucket (or cell or region) of the spatial grid, especially when the object is larger than the grid cell size. And that's pretty normal.
Actually, I'm going with the assumption that in my spatial grid, the cell size is larger than any object that will be added in this grid.
Therefore, when adding the object into the grid, the object is registered only inside the bucket where its top-leftmost corner goes, so only one bucket.

This way, to get shapes overlapping with a given shape A, i am using the following workflow:

Code: Select all

- check into the bucket where A's top-leftmost corner is
- check into  the bucket right above (north)
- check into the northwest bucket
- check into the bucket on the left (west)

if shapes A overlaps the immediate east border
   - check into the bucket on the right (east)
   - check into the northeast  bucket

if shapes A overlaps the immediate south border 
  - check into the the bucket below (south) 
  - check into the southwest bucket

  (nested) if shape A overlaps the immediate east border
  - check into the southeast bucket

Which makes, in the best case 4 tests, and in the worse one, up to 9 checks.
But, in the opposite, updating the spatial grid (when the shape moves) becomes faster, just 1 remove/ 1 add.

It seems to be a more interesting approach (i didn't make intensive tests yet, so I mabe wrong) that the common one, which is to store the shape in all buckets it overlaps with. in this scenario, checking for collisions requires less checks (1 in the best case, 4 in the worse), but updating the grid when the object moves will require a lot more operations.

Any thoughts about this ?
Apologies if I didn't make my point clear enough, I (do) suck at explaining technical things in english sometimes...

The only glaring weakness of sweep and prune is that it doesn't deal with many moving objects too well because of sorting per updates. The spatial hash structure + sweep and prune alleviates that problem.

I haven't considered yet sweep and prune, but I have a general idea on how it works though. Your job was nice on that, by the way (you keep getting updated, i am watching it on github). That would be a nice starting point for me when i'll come on this topic.

[dreadkillz]

Ah yes. I have a case of the commit itis with that repo. There's always a slight bug that I have to fix or code format that I don't like. I need to have better testing standards. It's bug free now though. Compared to my other repo's, I don't go commit happy cause the other stuff is simple. I'll have to be more rigorous with testing for the next big project of mine.

[Roland_Yonaba]

I tried to implement spatial hashes.
Source here: Broad-Phase-Algorithms
Love demo here: SpatialHashDemo

I'll be happy to have comments/critics about the implementation, by the way.
I tried to include it in my physically-based simulation. Indeed, the gain in terms of fps boost was *awesome*.
Wow. I was like sitting there, incredulous.

Before that, rendering above 300 particles was heavy and laggy...
Now, I can work with up to 1000 particles at a constant framerate.

Well, as I am not in a rush, I plan to take it slow and look at other consideration in broad-phase collisions. Well shaptial hashes seems to be the good answer here, but it won't matter looking at quadtrees, octrees, and SAP.

.

[Codex]

Curious, if you had many objects of different sizes and different rotations/speeds/accelerations, but they were spread out of a very large area would there be any advantage of one collision check over another? Most of the tests I've seen performed happened to be on objects that were squashed in a small area.

ex. You have a space game with planets, ships, asteroids, etc. A ship size can range anywhere from 5-100, asteroids can range in size from 1-200, planets can range in size from 300-600, there are thousands of these different objects. (95% of them are asteroids and planets) And they are scattered over a map size of 100,000. None of the objects are static. Everything is in motion.

I've got a really cool idea for a space game later, but collision detection is something I'm still trying to figure out. (still experimenting with SAT) I haven't been able to look closely at other methods, because collision with rotation is still making my brain go numb trying to figure it out...