Hi, after experimenting with processing it becomes increasingly clear that there is a need for some kind of space management when dealing with particles and their collisions. I’m currently partitioning the canvas using an object and checking the particles position against the partition grid. Dan has a video on quadtrees, which I’m still trying to wrap my head around, However what I want to know is, is there any advantage with using a quadtree, or would spacial partitioning be sufficient for most problems?
I assume by spacial partitioning (SP) you mean simply break the world space into smaller squares, bit like a chessboard.
One problem that any system has to overcome is how to identify and process objects that straddle a border into two or more partitions. In the data structure used by QT, these objects are easily identified and handled. In SP they are not differentiated in the data structure and you must do that in the update algorithm.
In both systems you want the savings in collision detection to out-way the additional work in maintaining the data structures. In both cases there are many variables that affect the outcome some of which are -
- number of particles
- size of particles
- size of partition
- depth of QT (not applicable to SP)
So QT has the advantage over SP when it deals with borderline particles but has the disadvantage of being more complex to implement.
3 Likes
For those interested, that QuadTree class and example sketch is available here:
…and an interesting quadtree visualizer demo:
Thank-you everyone for all your input, I shall try to implement the quadtree properly later. I have attempted a spacial partitioning model, and I’m assuming Ive made a mistake somewhere because there is little to no difference when compared to running a collision detection on a whole array of particles.
My program, creates a grid with x+y*width as its id. Then the particles take their x & y coordinates and again using the same equation identify which square they would belong to. When it finds its corresponding grid square it updates that square with itself (after checking its not already present) and uses the child array for that grid space to compute collisions.
It has a current id and a previous id. The previous id is used to remove itself from the last grid space to make sure that each grid space only contains current particles.
I’ve ran this with 2000 particles and can see no difference.
An alternative I was thinking would have been to do the check using the partition object rather that the particle array but I’m not too sure if this would add any efficiency.
Also please note I haven’t accounted for boundary straddling yet.
https://www.openprocessing.org/sketch/750558
Any input would be much appreciated.
Update. So it does seem to provide some performance improvements, at least on open processing. The grid[i].c1() function (which uses the entirety of the grid array), performs at 9 framerates per second versus the 50 - 55 framerates for the c2() (which uses the partitions of the grid array) function. Again no boundary checking yet but clearly an improvement.
Forgot to mention that you need to click the canvas to get the particles to move. Not sure why I dont see the same improvements on the desktop processing app, but I also know that processing is limited to around %30 percent cpu utilization on my pc, still unsure why and still dont know what the fix is for this.