+static GList *_roam_sphere_get_intersect_rec(RoamTriangle *triangle, GList *list,
+ gboolean all, gdouble n, gdouble s, gdouble e, gdouble w)
+{
+ gdouble tn = triangle->edge.n;
+ gdouble ts = triangle->edge.s;
+ gdouble te = triangle->edge.e;
+ gdouble tw = triangle->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",
+ triangle, 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");
+ if (all) list = g_list_prepend(list, triangle);
+ return _roam_sphere_get_leaves(triangle, list, all);
+ } else if (triangle->kids[0] && triangle->kids[1]) {
+ /* Paritial intersect with children */
+ if (debug) g_message("edge w/ child");
+ if (all) list = g_list_prepend(list, triangle);
+ list = _roam_sphere_get_intersect_rec(triangle->kids[0], list, all, n, s, e, w);
+ list = _roam_sphere_get_intersect_rec(triangle->kids[1], list, all, n, s, e, w);
+ return list;
+ } else {
+ /* This triangle is an edge case */
+ if (debug) g_message("edge");
+ return g_list_prepend(list, triangle);
+ }
+}
+/* Warning: This grabs pointers to triangles which can be changed by other
+ * calls, e.g. split_merge. If you use this, you need to do some locking to
+ * prevent the returned list from becomming stale. */
+GList *roam_sphere_get_intersect(RoamSphere *sphere, gboolean all,
+ 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(sphere->roots); i++)
+ list = _roam_sphere_get_intersect_rec(sphere->roots[i],
+ list, all, n, s, e, w);
+ return list;
+}
+
+static void roam_sphere_free_tri(RoamTriangle *triangle)