+GList *_roam_sphere_get_leaves(RoamTriangle *tri, GList *list)
+{
+ if (tri->kids[0] && tri->kids[1]) {
+ list = _roam_sphere_get_leaves(tri->kids[0], list);
+ list = _roam_sphere_get_leaves(tri->kids[1], list);
+ return list;
+ } else {
+ return g_list_append(list, tri);
+ }
+}
+GList *_roam_sphere_get_intersect_rec(RoamTriangle *tri, GList *list,
+ gdouble n, gdouble s, gdouble e, gdouble w)
+{
+ gdouble tn = tri->edge.n;
+ gdouble ts = tri->edge.s;
+ gdouble te = tri->edge.e;
+ gdouble tw = tri->edge.w;
+
+ gboolean debug = FALSE &&
+ n==90 && s==45 && e==-90 && w==-180 &&
+ ts > 44 && ts < 46;
+
+ if (debug)
+ g_message("t=%p: %f < %f || %f > %f || %f < %f || %f > %f",
+ tri, tn, s, ts, n, te, w, tw, e);
+ if (tn < s || ts > n || te < w || tw > e) {
+ /* No intersect */
+ if (debug) g_message("no intersect");
+ return list;
+ } else if (tn < n && ts > s && te < e && tw > w) {
+ /* Triangle is completely contained */
+ if (debug) g_message("contained");
+ return _roam_sphere_get_leaves(tri, list);
+ } else if (tri->kids[0] && tri->kids[1]) {
+ /* Paritial intersect with children */
+ if (debug) g_message("edge w/ child");
+ list = _roam_sphere_get_intersect_rec(tri->kids[0], list, n, s, e, w);
+ list = _roam_sphere_get_intersect_rec(tri->kids[1], list, n, s, e, w);
+ return list;
+ } else {
+ /* This triangle is an edge case */
+ if (debug) g_message("edge");
+ return g_list_append(list, tri);
+ }
+}
+GList *roam_sphere_get_intersect(RoamSphere *self,
+ gdouble n, gdouble s, gdouble e, gdouble w)
+{
+ /* I think this is correct..
+ * i_cost = cost for triangle-rectagnle intersect test
+ * time = n_tiles * 2*tris_per_tile * i_cost
+ * time = 30 * 2*333 * i_cost = 20000 * i_cost */
+ GList *list = NULL;
+ for (int i = 0; i < G_N_ELEMENTS(self->roots); i++)
+ list = _roam_sphere_get_intersect_rec(self->roots[i],
+ list, n, s, e, w);
+ return list;
+}