X-Git-Url: http://pileus.org/git/?a=blobdiff_plain;f=src%2Froam.c;h=3de5b5b7258ea938116827bf815ac2a1b5fee66e;hb=40c0e86e4e3b25f840242f02fac6def52b9e9d4c;hp=a5fd27232617dc7a7927af4e8449294b44514277;hpb=bd716715f1d13a8df514fcfa53fd82aebdfda770;p=grits diff --git a/src/roam.c b/src/roam.c index a5fd272..3de5b5b 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,21 @@ 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) + +static 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 +108,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 +127,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 +143,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,6 +174,16 @@ void roam_point_update_projection(RoamPoint *point, RoamSphere *sphere) /**************** * RoamTriangle * ****************/ +/** + * 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) { RoamTriangle *triangle = g_new0(RoamTriangle, 1); @@ -196,12 +261,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 +301,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,7 +318,7 @@ 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) +static void roam_triangle_sync_neighbors(RoamTriangle *new, RoamTriangle *old, RoamTriangle *neigh) { if (neigh->t.l == old) neigh->t.l = new; else if (neigh->t.b == old) neigh->t.b = new; @@ -238,33 +326,41 @@ void roam_triangle_sync_neighbors(RoamTriangle *new, RoamTriangle *old, RoamTria 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; -} -gboolean roam_triangle_visible(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); + 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; } +/** + * 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); + roam_point_update_projection(triangle->split, sphere->view); RoamPoint *l = triangle->p.l; RoamPoint *m = triangle->p.m; RoamPoint *r = triangle->p.r; @@ -288,6 +384,13 @@ void roam_triangle_update_errors(RoamTriangle *triangle, RoamSphere *sphere) } } +/** + * roam_triangle_split: + * @triangle: the triangle + * @sphere: the sphere + * + * Split a triangle into two child triangles and update the sphere. + */ void roam_triangle_split(RoamTriangle *triangle, RoamSphere *sphere) { //g_message("roam_triangle_split: %p, e=%f\n", triangle, triangle->error); @@ -331,6 +434,12 @@ void roam_triangle_split(RoamTriangle *triangle, RoamSphere *sphere) roam_diamond_remove(base->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 +450,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,6 +477,19 @@ void roam_triangle_draw_normal(RoamTriangle *triangle) /*************** * RoamDiamond * ***************/ +/** + * 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, RoamTriangle *kid0, RoamTriangle *kid1, @@ -384,12 +512,29 @@ RoamDiamond *roam_diamond_new( 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,6 +542,16 @@ 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); @@ -453,6 +608,15 @@ void roam_diamond_merge(RoamDiamond *diamond, RoamSphere *sphere) roam_triangle_free(diamond->kids[3]); 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 +627,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); @@ -512,6 +683,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 +699,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 +730,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 +799,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 +835,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 +851,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 +873,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 +903,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");