SIMULATING GRAVITY EFFICIENTLY WITH QUAD-TREES




The n-body problem is a classic physics problem in which a number of objects interact with each other using gravity in space. The net force acting on a particular body is determined by the sum of gravitational force between that body and every other body in the system

Calculating gravitational attraction is an expensive process. Every unique body within a system exerts an equal and opposite force on one another. This results in a time complexity of O(N^2). The force between two individual points of mass is strongest when the two points are very close to each other and weak when far away from each other. This property is used in the Barnes-Hut algorithm to reduce the time complexity of the problem to O(N log N). Because far away points have little impact on the net force acting on a gravitational body, the Barnes-Hut algorithm groups points sufficiently far away from the one in question and only calculates the force between the point and the group's center of mass.

Groups of bodies are determined recursively using a quad tree. This quad tree is a tree data structure with 4 children. Each child represents 1/4 of the spacial region based on x and y coordinates.


Spacial visualization of the quad-tree
Leaf nodes contain a single body. Each node contains a count of bodies in the subtree,a list of the bodies in the subtree, the spacial region it covers (xmin,xmax,ymin,ymax),the location of the center of mass,the total mass of all of the subtree, and pointers to the child nodes. The structs that I used to construct the tree are shown below.

//the structs used for the quad-tree
typedef struct{
    double x,y,vx,vy,mass,fx,fy;
    unsigned char r,g,b;
} Body;
struct Llnode{
    struct Llnode *next;
    Body  bod;
};
typedef struct Bhnode{
    struct Bhnode *next[4];
	struct Llnode *list;
    long int listsize;
    double cmassx,cmassy,mass;
    double xmin,xmax,ymin,ymax;
} Bhnode;

In order to determine if a group of bodies are sufficiently far away from each other, a value theta is set by the user that acts as a threshold for the ratio between the width of the region (s) and the distance between the body in question and the current node's center of mass (d). If the threshold is met, s/d < theta, then the node is sufficiently far away to consider the whole subtree as a single mass.


Video of Barnes-Hut in action




comments powered by Disqus
>
the random curiosities of derek lomibao ©2014