barnes_hut.h (1585B)
1 /* Quadtree implementation to keep track of recursive subdivisions of the 2 * simulation field into rectangular cells. 3 */ 4 5 #ifndef BARNES_HUT_H 6 #define BARNES_HUT_H 7 8 #include <stdbool.h> 9 10 // TODO: Limit tree depth 11 #ifndef THETA 12 #define THETA 0.5f 13 #endif 14 15 struct Star; 16 17 struct Cell 18 { 19 float center_x; 20 float center_y; 21 float distance_x; 22 float distance_y; 23 float mass_total; 24 float mass_center_x; 25 float mass_center_y; 26 float stars_sum_x; 27 float stars_sum_y; 28 // TODO: Make this a void*. 29 struct Star *star; 30 }; 31 32 struct QuadTreeNode 33 { 34 struct Cell *cell; 35 struct QuadTreeNode *ne; 36 struct QuadTreeNode *nw; 37 struct QuadTreeNode *sw; 38 struct QuadTreeNode *se; 39 }; 40 41 struct QuadTree 42 { 43 struct QuadTreeNode *root; 44 }; 45 46 47 struct Cell *cell_init(float center_x, float center_y, float distance_x, float distance_y); 48 void cell_free(struct Cell *c); 49 bool cell_contains_star(struct Cell *c, struct Star *s); 50 bool cell_is_empty(struct Cell *c); 51 52 struct QuadTreeNode *quad_tree_node_init(float center_x, float center_y, float distance_x, float distance_y); 53 void quad_tree_node_free(struct QuadTreeNode *node); 54 bool quad_tree_node_is_leaf(struct QuadTreeNode *node); 55 void quad_tree_node_subdivide(struct QuadTreeNode *node); 56 void quad_tree_node_insert_star(struct QuadTreeNode *node, struct Star *star); 57 58 struct QuadTree *quad_tree_init(void); 59 void quad_tree_free(struct QuadTree *qt); 60 bool node_is_sufficiently_far(struct QuadTreeNode *node, struct Star *star); 61 void quad_tree_calc_force_on_star(struct QuadTreeNode *node, struct Star *star); 62 63 #endif