I've been searching for some way to implement quadtrees in my 2D simulation in order to make the collision detection a whole lot faster, thing is I find the concept quite hard to grasp. The sim works great as it is now its just that once I get past the 160-180 particles it gets very slow since the collision detection is going through absolutely all particles needlessly and is just plain stupid. Right now it's just a bunch or circles colliding with each other all around the screen and I'm able to spawn new ones with new speeds and location by clicking and dragging the mouse.
edit1:
Well I think I was able to create the tree now as you can see in the image
My Quadtree image: https://i.sstatic.net/c4WNz.jpg
So the question now is how do I make it useful for my collision detection...
Do I have to create the whole tree from zero each time I check?
What I'm about to do while I await, hope it's right in some way :P
1_Check if there's a ball in each node and leave that node out if there's none. 2_Keep checking intersections until I hit the leaf level and add those intersecting balls to the leaf node. 3_Collide balls in the leaf node before I keep going??
Here's my QuadTreeNode class:
public class QuadTreeNode {
private QuadTreeNode parent;
private QuadTreeNode[] children;
private int id;
private double x;
private double y;
private double width;
private double height;
public QuadTreeNode(double x, double y, double width, double height, int id, QuadTreeNode parent){
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.children = new QuadTreeNode[4];
this.id = id;
this.parent = parent;
//System.out.println("<x:>"+x+"<y:>"+y+"<w:>"+width+"<h:>"+height);
if (this.width>=1000/12 && this!=null){
nodes+=1;
this.children[0] = new QuadTreeNode(x, y, width/2, height/2, id+1, this);
this.children[1] = new QuadTreeNode(x + width/2, y, width/2, height/2, id+2, this);
this.children[2] = new QuadTreeNode(x, y + height/2, width/2, height/2, id+3, this);
this.children[3] = new QuadTreeNode(x + width/2, y + height/2, width/2, height/2, id+4, this);
}
}
I find the concept quite hard to grasp
Idea:
recursive partition of a cell since:
Start with a bounding-box for the whole scene.
Hint: traversal is relative expensive because of many up and down movements in the hirarchy.
Traversal: - test with axis aligned bounding box of the root (first: whole scene)
Hint: the first hit could not be the nearest.
That's the principle of a quadtree or octree (3D) in short. I have a cg slide here which described it with images but I didnt want to upload them all. I think thats not the full answer on your question but maybe it helps a bit.