Granular particles update!

Hello again!

I've been fooling around with my granular particles repository these past days before do a real coding into Krita. I'm trying to optimize my simulation through a series of modifications in the code I wrote last week.

My first attempt to run this granular particles simulation was quite a big failure, since it was really slow and full of errors. I correct some small things this past weekend and during this week I implemented a neighborhood restriction to the collision detection between particles.

One of the reasons the code had a slow response was the fact that each particle was doing a collision detection with every other particle in the simulation. I initialized with 2010 particles, so we had a lot time wasted just doing useless calculations, since we only had to  worry about each particle vicinity. So this time I implemented a grid so we could restrict the computation of collision only for neighbors particles. I have yet some other two improvements to test before generate some QImages: try the RK4 integrator instead of the Gear's predictor and corrector, and a more vectorizable grid construction which will be more easily implemented in a GPU.

I'm already writting a more detailed post with all the theory used behind the scenes. But if you already took a look at the code before, this update will be easy to understand. Again, the code is well commented and any questions you can contact me here in the comments or sending me a message to my Gitorious account.

See you all soon! :)

2 comentários:

  1. Just some musing from a non programmer...

    1. Are you calculating all this in 2d or 3d? I'm sure 3d is technically prettier, but would 2d not be enough (and much faster)?

    2. In a similar line of thought, is collision detection really needed at all? What if we just had 2d particles, with location, color and velocity that slowed to a stop over time? I know it would be less physically accurate, but I imagine the speed up (especially with many particles) would be huge. It would also let us have more particles and keeping the calculations much simpler may make it easier to run it through openCL allowing us many more particles again...

    ANyway, you're the programmer, so I'm sure you've already thought about these things. I'm just curious. :)

    1. Hi Bugsbane!

      Yes, it's all in 2d. The way i'm implementing the idea we can extend to
      3d, but I cut it off since it would need much more efforts to make it work in
      due time.

      Maybe you're right. I could try to remove the collision between moving particles. Perhaps the visual result would be satisfatory.

      My problem with that (for now) it's two: we need something to happen when a particle get to the limits of the canvas and deal with the mouse interaction. I don't know how the grains should act when they reach the limits of the canvas: if it should bounce back in a collision or just stop at the border. For the bounce, we have to define a set of unmoving invisible particles in the border since a moving particle would have to collide with it. If the particle just stops, we would have less computations to do, but I don't know
      if would be nice to the visual result.

      The other it's the mouse. The mouse will have two actions: add sand and spread sand. While adding sand in the canvas we don't have any problems, since the particles would appear with initial conditions (position, velocity and acceleration) based on the mouse movements. But after that, if the user wants only to spread it, we should have collisions with an invisible particle in the mouse position. The size of this particle will be the size of the brush. That's why I am so concern with collisions for now.

      Anyway, I think you have a point here. I'll remove the collisions between moving particles and restrict that only to the border and the mouse (when we start to use it). Surely this will give us a huge performance improvement. :)

      Thanks for the feedback!