* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
+/**
+ * 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 <glib.h>
#include <math.h>
#include <string.h>
#include "gis-util.h"
#include "roam.h"
-/**
+/*
* TODO:
* - Optimize for memory consumption
* - Profile for computation speed
/*************
* 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);
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++) {
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++) {
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) {
}
}
+/**
+ * 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;
/****************
* 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);
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)
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 */
roam_point_visible(triangle->p.r, sphere);
}
+/**
+ * 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_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);
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);
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[] = {
/***************
* 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,
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) {
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);
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);
/**************
* RoamSphere *
**************/
+/**
+ * roam_sphere_new:
+ *
+ * Create a new sphere
+ *
+ * Returns: the sphere
+ */
RoamSphere *roam_sphere_new()
{
RoamSphere *sphere = g_new0(RoamSphere, 1);
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)
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);
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;
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]) {
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)
{
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. */
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");
typedef struct _RoamTriangle RoamTriangle;
typedef struct _RoamDiamond RoamDiamond;
typedef struct _RoamSphere RoamSphere;
+/**
+ * RoamHeightFunc:
+ * @lat: the latitude
+ * @lon: the longitude
+ * @user_data: user data passed to the function
+ *
+ * See #GisHeightFunc
+ *
+ * Returns: the elevation
+ */
typedef gdouble (*RoamHeightFunc)(gdouble lat, gdouble lon, gpointer user_data);
/* Misc */
+/**
+ * RoamView:
+ * @model: model view matrix
+ * @proj: projection matrix
+ * @view: viewport matrix
+ * @version: version
+ *
+ * Stores projection matrices
+ */
struct _RoamView {
gdouble model[16];
gdouble proj[16];
/*************
* RoamPoint *
*************/
+/**
+ * RoamPoint:
+ *
+ * Points are used as vertices for triangles. A single point my be shared among
+ * several triangles in order to conceive space and avoid recalculating
+ * projections. Points also store a lot of cached data. The normal vertex normal
+ * is the averaged surface normal of each associated triangle.
+ */
struct _RoamPoint {
/*< private >*/
gdouble x, y, z; /* Model coordinates */
/****************
* RoamTriangle *
****************/
+/**
+ * RoamTriangle:
+ *
+ * Triangles are one of the key datatypes in ROAM. The surface is made up of
+ * triangles. Each triangle has an associated "error". When the surface is being
+ * updated after the view changes, each triangles error is updated. Afterwards
+ * the triangles with the most error are split int to triangles, each with a
+ * lower error than the original.
+ *
+ * Triangles store a lot of data about their location in the mesh so that they
+ * can be split and merged (unsplit) without having to recreate the mesh.
+ */
struct _RoamTriangle {
/*< private >*/
/* Left, middle and right vertices */
/***************
* RoamDiamond *
***************/
+/**
+ * RoamDiamond:
+ *
+ * When two adjacent triangles are split, they, along with the four new child
+ * triangles, are added to a diamond which keeps track of them.
+ *
+ * Like triangles, diamond have an error associated with it. However, when a
+ * diamonds error is small enough it is "merged". That is, the diamond along
+ * with the child triangles is removed and the original two triangles triangles
+ * are added back into the mesh.
+ */
struct _RoamDiamond {
/*< private >*/
RoamTriangle *kids[4]; /* Child triangles */
/**************
* RoamSphere *
**************/
+/**
+ * RoamSphere:
+ *
+ * The sphere keeps track of the triangles and diamonds in the mesh.
+ *
+ * Originally the sphere consists of only 8 triangles forming a octahedron.
+ * These triangles are quickly split to create a smoother sphere.
+ */
struct _RoamSphere {
/*< private >*/
GPQueue *triangles; /* List of triangles */