X-Git-Url: http://pileus.org/git/?p=grits;a=blobdiff_plain;f=src%2Froam.c;h=0f4995e0b56593d7bf3dc03f4d65015afb847e8e;hp=a5fd27232617dc7a7927af4e8449294b44514277;hb=22408daaad6f0c7b4075c2b0a725802b0659cfbe;hpb=bd716715f1d13a8df514fcfa53fd82aebdfda770 diff --git a/src/roam.c b/src/roam.c index a5fd272..0f4995e 100644 --- a/src/roam.c +++ b/src/roam.c @@ -15,17 +15,30 @@ * along with this program. If not, see . */ +/** + * SECTION:roam + * @short_description: Realtime Optimally-Adapting Meshes + * + * A spherical version of the Realtime Optimally-Adapting Meshes (ROAM) + * algorithm is use for drawing the surface of the planet. ROAM provide a + * continuous level-of-detail mesh of the planet which is used by #GisOpenGL + * when drawing surface textures for GisTiles. + * + * This implementation of the ROAM algorithm is based on an octahedron as the + * base model. + */ + #include #include #include -#include "gpqueue.h" #include #include +#include "gpqueue.h" #include "gis-util.h" #include "roam.h" -/** +/* * TODO: * - Optimize for memory consumption * - Profile for computation speed @@ -50,6 +63,16 @@ static gint dia_cmp(RoamDiamond *a, RoamDiamond *b, gpointer data) /************* * RoamPoint * *************/ +/** + * roam_point_new: + * @lat: the latitude for the point + * @lon: the longitude for the point + * @elev: the elevation for the point + * + * Create a new point at the given locaiton + * + * Returns: the new point + */ RoamPoint *roam_point_new(gdouble lat, gdouble lon, gdouble elev) { RoamPoint *point = g_new0(RoamPoint, 1); @@ -60,12 +83,14 @@ RoamPoint *roam_point_new(gdouble lat, gdouble lon, gdouble elev) lle2xyz(lat, lon, elev, &point->x, &point->y, &point->z); return point; } -RoamPoint *roam_point_dup(RoamPoint *point) -{ - RoamPoint *new = g_memdup(point, sizeof(RoamPoint)); - new->tris = 0; - return new; -} + +/** + * roam_point_add_triangle: + * @point: the point + * @triangle: the to add + * + * Associating a triangle with a point and update it's vertex normal. + */ void roam_point_add_triangle(RoamPoint *point, RoamTriangle *triangle) { for (int i = 0; i < 3; i++) { @@ -76,6 +101,14 @@ void roam_point_add_triangle(RoamPoint *point, RoamTriangle *triangle) for (int i = 0; i < 3; i++) point->norm[i] /= point->tris; } + +/** + * roam_point_remove_triangle: + * @point: the point + * @triangle: the to add + * + * Un-associating a triangle with a point and update it's vertex normal. + */ void roam_point_remove_triangle(RoamPoint *point, RoamTriangle *triangle) { for (int i = 0; i < 3; i++) { @@ -87,6 +120,13 @@ void roam_point_remove_triangle(RoamPoint *point, RoamTriangle *triangle) for (int i = 0; i < 3; i++) point->norm[i] /= point->tris; } + +/** + * roam_point_update_height: + * @point: the point + * + * Update the height (elevation) of a point based on the current height function + */ void roam_point_update_height(RoamPoint *point) { if (point->height_func) { @@ -96,22 +136,30 @@ void roam_point_update_height(RoamPoint *point) &point->x, &point->y, &point->z); } } -void roam_point_update_projection(RoamPoint *point, RoamSphere *sphere) + +/** + * roam_point_update_projection: + * @point: the point + * @view: the view to use when projecting the point + * + * Updated the screen-space projection of a point. + */ +void roam_point_update_projection(RoamPoint *point, RoamView *view) { static int count = 0; static int version = 0; - if (version != sphere->view->version) { + if (version != view->version) { g_debug("RoamPoint: Projected %d points", count); count = 0; - version = sphere->view->version; + version = view->version; } - if (point->pversion != sphere->view->version) { + if (point->pversion != view->version) { /* Cache projection */ gluProject(point->x, point->y, point->z, - sphere->view->model, sphere->view->proj, sphere->view->view, + view->model, view->proj, view->view, &point->px, &point->py, &point->pz); - point->pversion = sphere->view->version; + point->pversion = view->version; count++; } } @@ -119,15 +167,27 @@ void roam_point_update_projection(RoamPoint *point, RoamSphere *sphere) /**************** * RoamTriangle * ****************/ -RoamTriangle *roam_triangle_new(RoamPoint *l, RoamPoint *m, RoamPoint *r) +/** + * roam_triangle_new: + * @l: the left point + * @m: the middle point + * @r: the right point + * + * Create a new triangle consisting of three points. + * + * Returns: the new triangle + */ +RoamTriangle *roam_triangle_new(RoamPoint *l, RoamPoint *m, RoamPoint *r, + RoamDiamond *parent) { RoamTriangle *triangle = g_new0(RoamTriangle, 1); - triangle->error = 0; - triangle->p.l = l; - triangle->p.m = m; - triangle->p.r = r; - triangle->split = roam_point_new( + triangle->error = 0; + triangle->p.l = l; + triangle->p.m = m; + triangle->p.r = r; + triangle->parent = parent; + triangle->split = roam_point_new( (l->lat + r->lat)/2, (ABS(l->lat) == 90 ? r->lon : ABS(r->lat) == 90 ? l->lon : @@ -196,12 +256,28 @@ RoamTriangle *roam_triangle_new(RoamPoint *l, RoamPoint *m, RoamPoint *r) return triangle; } +/** + * roam_triangle_free: + * @triangle: the triangle + * + * Free data associated with a triangle + */ void roam_triangle_free(RoamTriangle *triangle) { g_free(triangle->split); g_free(triangle); } +/** + * roam_triangle_add: + * @triangle: the triangle + * @left: the left neighbor + * @base: the base neighbor + * @right: the right neighbor + * @sphere: the sphere to add the triangle to + * + * Add a triangle into the sphere's mesh using the given neighbors. + */ void roam_triangle_add(RoamTriangle *triangle, RoamTriangle *left, RoamTriangle *base, RoamTriangle *right, RoamSphere *sphere) @@ -220,6 +296,13 @@ void roam_triangle_add(RoamTriangle *triangle, triangle->handle = g_pqueue_push(sphere->triangles, triangle); } +/** + * roam_triangle_remove: + * @triangle: the triangle + * @sphere: the sphere to remove the triangle from + * + * Remove a triangle from a sphere's mesh. + */ void roam_triangle_remove(RoamTriangle *triangle, RoamSphere *sphere) { /* Update vertex normals */ @@ -230,44 +313,66 @@ void roam_triangle_remove(RoamTriangle *triangle, RoamSphere *sphere) g_pqueue_remove(sphere->triangles, triangle->handle); } -void roam_triangle_sync_neighbors(RoamTriangle *new, RoamTriangle *old, RoamTriangle *neigh) +/* (neight->t.? == old) = new */ +static void roam_triangle_sync_neighbors(RoamTriangle *neigh, RoamTriangle *old, RoamTriangle *new) { if (neigh->t.l == old) neigh->t.l = new; else if (neigh->t.b == old) neigh->t.b = new; else if (neigh->t.r == old) neigh->t.r = new; - else g_assert_not_reached(); } -gboolean roam_point_visible(RoamPoint *triangle, RoamSphere *sphere) +static gboolean roam_triangle_visible(RoamTriangle *triangle, RoamSphere *sphere) { + RoamPoint *l = triangle->p.l; + RoamPoint *m = triangle->p.m; + RoamPoint *r = triangle->p.r; + gdouble min_x = MIN(MIN(l->px, m->px), r->px); + gdouble max_x = MAX(MAX(l->px, m->px), r->px); + gdouble min_y = MIN(MIN(l->py, m->py), r->py); + gdouble max_y = MAX(MAX(l->py, m->py), r->py); gint *view = sphere->view->view; - return triangle->px > view[0] && triangle->px < view[2] && - triangle->py > view[1] && triangle->py < view[3] && - triangle->pz > 0 && triangle->pz < 1; + return !(max_x < view[0] || min_x > view[2] || + max_y < view[1] || min_y > view[3]) && + l->pz > 0 && m->pz > 0 && r->pz > 0 && + l->pz < 1 && m->pz < 1 && r->pz < 1; } -gboolean roam_triangle_visible(RoamTriangle *triangle, RoamSphere *sphere) + +static gboolean roam_triangle_backface(RoamTriangle *triangle, RoamSphere *sphere) { - /* Do this with a bounding box */ - return roam_point_visible(triangle->p.l, sphere) || - roam_point_visible(triangle->p.m, sphere) || - roam_point_visible(triangle->p.r, sphere); + RoamPoint *l = triangle->p.l; + RoamPoint *m = triangle->p.m; + RoamPoint *r = triangle->p.r; + roam_point_update_projection(l, sphere->view); + roam_point_update_projection(m, sphere->view); + roam_point_update_projection(r, sphere->view); + double size = -( l->px * (m->py - r->py) + + m->px * (r->py - l->py) + + r->px * (l->py - m->py) ) / 2.0; + return size < 0; } +/** + * roam_triangle_update_errors: + * @triangle: the triangle + * @sphere: the sphere to use when updating errors + * + * Update the error value associated with a triangle. Called when the view + * changes. + */ void roam_triangle_update_errors(RoamTriangle *triangle, RoamSphere *sphere) { /* Update points */ - roam_point_update_projection(triangle->p.l, sphere); - roam_point_update_projection(triangle->p.m, sphere); - roam_point_update_projection(triangle->p.r, sphere); + roam_point_update_projection(triangle->p.l, sphere->view); + roam_point_update_projection(triangle->p.m, sphere->view); + roam_point_update_projection(triangle->p.r, sphere->view); - /* Not exactly correct, could be out on both sides (middle in) */ if (!roam_triangle_visible(triangle, sphere)) { triangle->error = -1; } else { - roam_point_update_projection(triangle->split, sphere); - RoamPoint *l = triangle->p.l; - RoamPoint *m = triangle->p.m; - RoamPoint *r = triangle->p.r; + roam_point_update_projection(triangle->split, sphere->view); + RoamPoint *l = triangle->p.l; + RoamPoint *m = triangle->p.m; + RoamPoint *r = triangle->p.r; RoamPoint *split = triangle->split; /* l-r midpoint projected l-r midpoint */ @@ -282,12 +387,24 @@ void roam_triangle_update_errors(RoamTriangle *triangle, RoamSphere *sphere) r->px * (l->py - m->py) ) / 2.0; /* Size < 0 == backface */ - //if (size < 0) - // triangle->error *= -1; triangle->error *= size; + + /* Give some preference to "edge" faces */ + if (roam_triangle_backface(triangle->t.l, sphere) || + roam_triangle_backface(triangle->t.b, sphere) || + roam_triangle_backface(triangle->t.r, sphere)) + triangle->error *= 500; } } +/** + * roam_triangle_split: + * @triangle: the triangle + * @sphere: the sphere + * + * Split a triangle into two child triangles and update the sphere. + * triangle + */ void roam_triangle_split(RoamTriangle *triangle, RoamSphere *sphere) { //g_message("roam_triangle_split: %p, e=%f\n", triangle, triangle->error); @@ -299,38 +416,46 @@ void roam_triangle_split(RoamTriangle *triangle, RoamSphere *sphere) if (triangle != triangle->t.b->t.b) g_assert_not_reached(); - RoamTriangle *base = triangle->t.b; + RoamTriangle *s = triangle; // Self + RoamTriangle *b = triangle->t.b; // Base + + RoamDiamond *dia = roam_diamond_new(s, b); /* Add new triangles */ RoamPoint *mid = triangle->split; - RoamTriangle *sl = triangle->kids[0] = roam_triangle_new(triangle->p.m, mid, triangle->p.l); // triangle Left - RoamTriangle *sr = triangle->kids[1] = roam_triangle_new(triangle->p.r, mid, triangle->p.m); // triangle Right - RoamTriangle *bl = base->kids[0] = roam_triangle_new(base->p.m, mid, base->p.l); // Base Left - RoamTriangle *br = base->kids[1] = roam_triangle_new(base->p.r, mid, base->p.m); // Base Right + RoamTriangle *sl = s->kids[0] = roam_triangle_new(s->p.m, mid, s->p.l, dia); // Self Left + RoamTriangle *sr = s->kids[1] = roam_triangle_new(s->p.r, mid, s->p.m, dia); // Self Right + RoamTriangle *bl = b->kids[0] = roam_triangle_new(b->p.m, mid, b->p.l, dia); // Base Left + RoamTriangle *br = b->kids[1] = roam_triangle_new(b->p.r, mid, b->p.m, dia); // Base Right /* triangle,l, base, r, sphere */ - roam_triangle_add(sl, sr, triangle->t.l, br, sphere); - roam_triangle_add(sr, bl, triangle->t.r, sl, sphere); - roam_triangle_add(bl, br, base->t.l, sr, sphere); - roam_triangle_add(br, sl, base->t.r, bl, sphere); + roam_triangle_add(sl, sr, s->t.l, br, sphere); + roam_triangle_add(sr, bl, s->t.r, sl, sphere); + roam_triangle_add(bl, br, b->t.l, sr, sphere); + roam_triangle_add(br, sl, b->t.r, bl, sphere); - roam_triangle_sync_neighbors(sl, triangle, triangle->t.l); - roam_triangle_sync_neighbors(sr, triangle, triangle->t.r); - roam_triangle_sync_neighbors(bl, base, base->t.l); - roam_triangle_sync_neighbors(br, base, base->t.r); + roam_triangle_sync_neighbors(s->t.l, s, sl); + roam_triangle_sync_neighbors(s->t.r, s, sr); + roam_triangle_sync_neighbors(b->t.l, b, bl); + roam_triangle_sync_neighbors(b->t.r, b, br); /* Remove old triangles */ - roam_triangle_remove(triangle, sphere); - roam_triangle_remove(base, sphere); + roam_triangle_remove(s, sphere); + roam_triangle_remove(b, sphere); /* Add/Remove diamonds */ - RoamDiamond *diamond = roam_diamond_new(triangle, base, sl, sr, bl, br); - roam_diamond_update_errors(diamond, sphere); - roam_diamond_add(diamond, sphere); - roam_diamond_remove(triangle->parent, sphere); - roam_diamond_remove(base->parent, sphere); + roam_diamond_update_errors(dia, sphere); + roam_diamond_add(dia, sphere); + roam_diamond_remove(s->parent, sphere); + roam_diamond_remove(b->parent, sphere); } +/** + * roam_triangle_draw: + * @triangle: the triangle + * + * Draw the triangle. Use for debugging. + */ void roam_triangle_draw(RoamTriangle *triangle) { glBegin(GL_TRIANGLES); @@ -341,6 +466,12 @@ void roam_triangle_draw(RoamTriangle *triangle) return; } +/** + * roam_triangle_draw_normal: + * @triangle: the triangle + * + * Draw a normal vector for the triangle. Used while debugging. + */ void roam_triangle_draw_normal(RoamTriangle *triangle) { double center[] = { @@ -362,34 +493,49 @@ void roam_triangle_draw_normal(RoamTriangle *triangle) /*************** * RoamDiamond * ***************/ -RoamDiamond *roam_diamond_new( - RoamTriangle *parent0, RoamTriangle *parent1, - RoamTriangle *kid0, RoamTriangle *kid1, - RoamTriangle *kid2, RoamTriangle *kid3) +/** + * roam_diamond_new: + * @parent0: a parent triangle + * @parent1: a parent triangle + * @kid0: a child triangle + * @kid1: a child triangle + * @kid2: a child triangle + * @kid3: a child triangle + * + * Create a diamond to store information about two split triangles. + * + * Returns: the new diamond + */ +RoamDiamond *roam_diamond_new(RoamTriangle *parent0, RoamTriangle *parent1) { RoamDiamond *diamond = g_new0(RoamDiamond, 1); - - diamond->kids[0] = kid0; - diamond->kids[1] = kid1; - diamond->kids[2] = kid2; - diamond->kids[3] = kid3; - - kid0->parent = diamond; - kid1->parent = diamond; - kid2->parent = diamond; - kid3->parent = diamond; - diamond->parents[0] = parent0; diamond->parents[1] = parent1; - return diamond; } + +/** + * roam_diamond_add: + * @diamond: the diamond + * @sphere: the sphere to add the diamond to + * + * Add a diamond into the sphere's pool of diamonds. It will be check for + * possible merges. + */ void roam_diamond_add(RoamDiamond *diamond, RoamSphere *sphere) { diamond->active = TRUE; diamond->error = MAX(diamond->parents[0]->error, diamond->parents[1]->error); diamond->handle = g_pqueue_push(sphere->diamonds, diamond); } + +/** + * roam_diamond_remove: + * @diamond: the diamond + * @sphere: the sphere to remove the diamond from + * + * Remove a diamond from the sphere's pool of diamonds. + */ void roam_diamond_remove(RoamDiamond *diamond, RoamSphere *sphere) { if (diamond && diamond->active) { @@ -397,62 +543,89 @@ void roam_diamond_remove(RoamDiamond *diamond, RoamSphere *sphere) g_pqueue_remove(sphere->diamonds, diamond->handle); } } + +/** + * roam_diamond_merge: + * @diamond: the diamond + * @sphere: the sphere + * + * "Merge" a diamond back into two parent triangles. The original two triangles + * are added back into the sphere and the four child triangles as well as the + * diamond are removed. + */ void roam_diamond_merge(RoamDiamond *diamond, RoamSphere *sphere) { //g_message("roam_diamond_merge: %p, e=%f\n", diamond, diamond->error); + /* TODO: pick the best split */ sphere->polys -= 2; - /* TODO: pick the best split */ - RoamTriangle **kids = diamond->kids; + /* Use nicer temp names */ + RoamTriangle *s = diamond->parents[0]; // Self + RoamTriangle *b = diamond->parents[1]; // Base + + RoamTriangle *sl = s->kids[0]; + RoamTriangle *sr = s->kids[1]; + RoamTriangle *bl = b->kids[0]; + RoamTriangle *br = b->kids[1]; - /* Create triangles */ - RoamTriangle *triangle = diamond->parents[0]; - RoamTriangle *base = diamond->parents[1]; + s->kids[0] = s->kids[1] = NULL; + b->kids[0] = b->kids[1] = NULL; - roam_triangle_add(triangle, kids[0]->t.b, base, kids[1]->t.b, sphere); - roam_triangle_add(base, kids[2]->t.b, triangle, kids[3]->t.b, sphere); + /* Add original triangles */ + roam_triangle_sync_neighbors(s->t.l, sl, s); + roam_triangle_sync_neighbors(s->t.r, sr, s); + roam_triangle_sync_neighbors(b->t.l, bl, b); + roam_triangle_sync_neighbors(b->t.r, br, b); - roam_triangle_sync_neighbors(triangle, kids[0], kids[0]->t.b); - roam_triangle_sync_neighbors(triangle, kids[1], kids[1]->t.b); - roam_triangle_sync_neighbors(base, kids[2], kids[2]->t.b); - roam_triangle_sync_neighbors(base, kids[3], kids[3]->t.b); + roam_triangle_add(s, sl->t.b, b, sr->t.b, sphere); + roam_triangle_add(b, bl->t.b, s, br->t.b, sphere); - /* Remove triangles */ - roam_triangle_remove(kids[0], sphere); - roam_triangle_remove(kids[1], sphere); - roam_triangle_remove(kids[2], sphere); - roam_triangle_remove(kids[3], sphere); + roam_triangle_sync_neighbors(sl->t.b, sl, s); + roam_triangle_sync_neighbors(sr->t.b, sr, s); + roam_triangle_sync_neighbors(bl->t.b, bl, b); + roam_triangle_sync_neighbors(br->t.b, br, b); - /* Clear kids */ - triangle->kids[0] = triangle->kids[1] = NULL; - base->kids[0] = base->kids[1] = NULL; + /* Remove child triangles */ + roam_triangle_remove(sl, sphere); + roam_triangle_remove(sr, sphere); + roam_triangle_remove(bl, sphere); + roam_triangle_remove(br, sphere); /* Add/Remove triangles */ - if (triangle->t.l->t.l == triangle->t.r->t.r && - triangle->t.l->t.l != triangle && triangle->parent) { - roam_diamond_update_errors(triangle->parent, sphere); - roam_diamond_add(triangle->parent, sphere); + if (s->t.l->t.l == s->t.r->t.r && + s->t.l->t.l != s && s->parent) { + roam_diamond_update_errors(s->parent, sphere); + roam_diamond_add(s->parent, sphere); } - if (base->t.l->t.l == base->t.r->t.r && - base->t.l->t.l != base && base->parent) { - roam_diamond_update_errors(base->parent, sphere); - roam_diamond_add(base->parent, sphere); + if (b->t.l->t.l == b->t.r->t.r && + b->t.l->t.l != b && b->parent) { + roam_diamond_update_errors(b->parent, sphere); + roam_diamond_add(b->parent, sphere); } /* Remove and free diamond and child triangles */ roam_diamond_remove(diamond, sphere); - g_assert(diamond->kids[0]->p.m == diamond->kids[1]->p.m && - diamond->kids[1]->p.m == diamond->kids[2]->p.m && - diamond->kids[2]->p.m == diamond->kids[3]->p.m); - g_assert(diamond->kids[0]->p.m->tris == 0); - roam_triangle_free(diamond->kids[0]); - roam_triangle_free(diamond->kids[1]); - roam_triangle_free(diamond->kids[2]); - roam_triangle_free(diamond->kids[3]); + g_assert(sl->p.m == sr->p.m && + sr->p.m == bl->p.m && + bl->p.m == br->p.m); + g_assert(sl->p.m->tris == 0); + roam_triangle_free(sl); + roam_triangle_free(sr); + roam_triangle_free(bl); + roam_triangle_free(br); g_free(diamond); } + +/** + * roam_diamond_update_errors: + * @diamond: the diamond + * @sphere: the sphere to use when updating errors + * + * Update the error value associated with a diamond. Called when the view + * changes. + */ void roam_diamond_update_errors(RoamDiamond *diamond, RoamSphere *sphere) { roam_triangle_update_errors(diamond->parents[0], sphere); @@ -463,6 +636,13 @@ void roam_diamond_update_errors(RoamDiamond *diamond, RoamSphere *sphere) /************** * RoamSphere * **************/ +/** + * roam_sphere_new: + * + * Create a new sphere + * + * Returns: the sphere + */ RoamSphere *roam_sphere_new() { RoamSphere *sphere = g_new0(RoamSphere, 1); @@ -496,7 +676,8 @@ RoamSphere *roam_sphere_new() sphere->roots[i] = roam_triangle_new( vertexes[_triangles[i][0][0]], vertexes[_triangles[i][0][1]], - vertexes[_triangles[i][0][2]]); + vertexes[_triangles[i][0][2]], + NULL); for (int i = 0; i < 8; i++) roam_triangle_add(sphere->roots[i], sphere->roots[_triangles[i][1][0]], @@ -512,6 +693,13 @@ RoamSphere *roam_sphere_new() return sphere; } + +/** + * roam_sphere_update_view + * @sphere: the sphere + * + * Recreate the sphere's view matrices based on the current OpenGL state. + */ void roam_sphere_update_view(RoamSphere *sphere) { if (!sphere->view) @@ -521,6 +709,13 @@ void roam_sphere_update_view(RoamSphere *sphere) glGetIntegerv(GL_VIEWPORT, sphere->view->view); sphere->view->version++; } + +/** + * roam_sphere_update_errors + * @sphere: the sphere + * + * Update triangle and diamond errors in the sphere. + */ void roam_sphere_update_errors(RoamSphere *sphere) { g_debug("RoamSphere: update_errors - polys=%d", sphere->polys); @@ -545,18 +740,40 @@ void roam_sphere_update_errors(RoamSphere *sphere) g_ptr_array_free(dias, TRUE); } +/** + * roam_sphere_split_one + * @sphere: the sphere + * + * Split the triangle with the greatest error. + */ void roam_sphere_split_one(RoamSphere *sphere) { RoamTriangle *to_split = g_pqueue_peek(sphere->triangles); if (!to_split) return; roam_triangle_split(to_split, sphere); } + +/** + * roam_sphere_merge_one + * @sphere: the sphere + * + * Merge the diamond with the lowest error. + */ void roam_sphere_merge_one(RoamSphere *sphere) { RoamDiamond *to_merge = g_pqueue_peek(sphere->diamonds); if (!to_merge) return; roam_diamond_merge(to_merge, sphere); } + +/** + * roam_sphere_split_merge + * @sphere: the sphere + * + * Perform a predetermined number split-merge iterations. + * + * Returns: the number splits and merges done + */ gint roam_sphere_split_merge(RoamSphere *sphere) { gint iters = 0, max_iters = 500; @@ -592,16 +809,31 @@ gint roam_sphere_split_merge(RoamSphere *sphere) return iters; } + +/** + * roam_sphere_draw: + * @sphere: the sphere + * + * Draw the sphere. Use for debugging. + */ void roam_sphere_draw(RoamSphere *sphere) { g_debug("RoamSphere: draw"); g_pqueue_foreach(sphere->triangles, (GFunc)roam_triangle_draw, NULL); } + +/** + * roam_sphere_draw_normals + * @sphere: the sphere + * + * Draw all the surface normal vectors for the sphere. Used while debugging. + */ void roam_sphere_draw_normals(RoamSphere *sphere) { g_debug("RoamSphere: draw_normal"); g_pqueue_foreach(sphere->triangles, (GFunc)roam_triangle_draw_normal, NULL); } + static GList *_roam_sphere_get_leaves(RoamTriangle *triangle, GList *list, gboolean all) { if (triangle->kids[0] && triangle->kids[1]) { @@ -613,6 +845,7 @@ static GList *_roam_sphere_get_leaves(RoamTriangle *triangle, GList *list, gbool return g_list_prepend(list, triangle); } } + static GList *_roam_sphere_get_intersect_rec(RoamTriangle *triangle, GList *list, gboolean all, gdouble n, gdouble s, gdouble e, gdouble w) { @@ -628,7 +861,7 @@ static GList *_roam_sphere_get_intersect_rec(RoamTriangle *triangle, GList *list 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) { + if (tn <= s || ts >= n || te <= w || tw >= e) { /* No intersect */ if (debug) g_message("no intersect"); return list; @@ -650,6 +883,20 @@ static GList *_roam_sphere_get_intersect_rec(RoamTriangle *triangle, GList *list return g_list_prepend(list, triangle); } } + +/** + * roam_sphere_get_intersect + * @sphere: the sphere + * @all: TRUE if non-leaf triangle should be returned as well + * @n: the northern edge + * @s: the southern edge + * @e: the eastern edge + * @w: the western edge + * + * Lookup triangles withing the sphere that intersect a given lat-lon box. + * + * Returns: the list of intersecting triangles. + */ /* 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. */ @@ -666,13 +913,21 @@ GList *roam_sphere_get_intersect(RoamSphere *sphere, gboolean all, list, all, n, s, e, w); return list; } -void roam_sphere_free_tri(RoamTriangle *triangle) + +static void roam_sphere_free_tri(RoamTriangle *triangle) { if (--triangle->p.l->tris == 0) g_free(triangle->p.l); if (--triangle->p.m->tris == 0) g_free(triangle->p.m); if (--triangle->p.r->tris == 0) g_free(triangle->p.r); roam_triangle_free(triangle); } + +/** + * roam_sphere_free + * @sphere: the sphere + * + * Free data associated with a sphere + */ void roam_sphere_free(RoamSphere *sphere) { g_debug("RoamSphere: free");