From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Thu, 8 Apr 2010 16:45:12 +0000 (+0300)
Subject: planets: Add support for spatial search from quadtree
X-Git-Url: http://git.itanic.dy.fi/?p=sdl-planets;a=commitdiff_plain;h=58fe44a0bda0d30597853670f3e477b001ba2223

planets: Add support for spatial search from quadtree

This can be used to for example draw only visible planets on the
screen.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
---

diff --git a/planet.c b/planet.c
index bdbde37..da83d3a 100644
--- a/planet.c
+++ b/planet.c
@@ -244,3 +244,45 @@ int planet_spatial_compare(struct quadtree *ta, struct quadtree *tb)
 		return 2;
 	return 3;
 }
+
+int planet_search_rectangular(struct quadtree *node,
+			      struct quadtree_iterator *itr)
+{
+	struct planet_search_iterator *it = qt_itr_to_planet_itr(itr);
+	struct planet *p = tree_to_planet(node);
+	int direction = 0, i;
+	int up = 0, left = 0, right = 0, down = 0;
+
+	for (i = 0; i < 2; i++) {
+		if (it->limit[i].x < p->pos.x)
+			left = 1;
+		else
+			right = 1;
+		if (it->limit[i].y < p->pos.y)
+			up = 1;
+		else
+			down = 1;
+	}
+
+	if (left && up)
+		direction |= QUADTREE_UPLEFT;
+	if (right && up)
+		direction |= QUADTREE_UPRIGHT;
+	if (left && down)
+		direction |= QUADTREE_DOWNLEFT;
+	if (right && down)
+		direction |= QUADTREE_DOWNRIGHT;
+	if (direction == (QUADTREE_UPLEFT | QUADTREE_UPRIGHT |
+			  QUADTREE_DOWNLEFT | QUADTREE_DOWNRIGHT))
+		direction |= QUADTREE_SELF;
+
+	return direction;
+}
+
+void planet_draw_iterator(struct quadtree *node, struct quadtree_iterator *it)
+{
+	struct planet *p = tree_to_planet(node);
+	struct planet_search_iterator *i = qt_itr_to_planet_itr(it);
+
+	draw_planet(i->screen, p, i->cam);
+}
diff --git a/planet.h b/planet.h
index 22bfd07..0673c87 100644
--- a/planet.h
+++ b/planet.h
@@ -19,10 +19,20 @@ struct planet {
 	unsigned char r, g, b;
 };
 
+struct planet_search_iterator {
+	struct quadtree_iterator qt_iterator;
+	struct vector limit[2];
+	struct camera *cam;
+	SDL_Surface *screen;
+};
+
 #define list_to_planet(list_head) container_of((list_head), struct planet, list)
 
 #define tree_to_planet(qt) container_of((qt), struct planet, tree)
 
+#define qt_itr_to_planet_itr(qt)					\
+	container_of((qt), struct planet_search_iterator, qt_iterator)
+
 void init_planet(struct planet *p);
 void create_planets(struct planet *p, int num, double total_mass,
 		    double radius);
@@ -33,4 +43,8 @@ struct planet *move_planet(struct planet *p, const double time);
 void print_planet(const struct planet *p);
 
 int planet_spatial_compare(struct quadtree *a, struct quadtree *b);
+int planet_search_rectangular(struct quadtree *node,
+			      struct quadtree_iterator *itr);
+void planet_draw_iterator(struct quadtree *node, struct quadtree_iterator *it);
+
 #endif