roam

roam — Realtime Optimally-Adapting Meshes

Synopsis

struct              RoamDiamond;
gdouble             (*RoamHeightFunc)                   (gdouble lat,
                                                         gdouble lon,
                                                         gpointer user_data);
struct              RoamPoint;
struct              RoamSphere;
struct              RoamTriangle;
struct              RoamView;
void                roam_diamond_add                    (RoamDiamond *diamond,
                                                         RoamSphere *sphere);
void                roam_diamond_merge                  (RoamDiamond *diamond,
                                                         RoamSphere *sphere);
RoamDiamond *       roam_diamond_new                    (RoamTriangle *parent0,
                                                         RoamTriangle *parent1);
void                roam_diamond_remove                 (RoamDiamond *diamond,
                                                         RoamSphere *sphere);
void                roam_diamond_update_errors          (RoamDiamond *diamond,
                                                         RoamSphere *sphere);
void                roam_point_add_triangle             (RoamPoint *point,
                                                         RoamTriangle *triangle);
RoamPoint *         roam_point_new                      (double lat,
                                                         double lon,
                                                         double elev);
void                roam_point_remove_triangle          (RoamPoint *point,
                                                         RoamTriangle *triangle);
void                roam_point_update_height            (RoamPoint *point);
void                roam_point_update_projection        (RoamPoint *point,
                                                         RoamView *view);
void                roam_sphere_draw                    (RoamSphere *sphere);
void                roam_sphere_draw_normals            (RoamSphere *sphere);
void                roam_sphere_free                    (RoamSphere *sphere);
GList *             roam_sphere_get_intersect           (RoamSphere *sphere,
                                                         gboolean all,
                                                         gdouble n,
                                                         gdouble s,
                                                         gdouble e,
                                                         gdouble w);
void                roam_sphere_merge_one               (RoamSphere *sphere);
RoamSphere *        roam_sphere_new                     ();
gint                roam_sphere_split_merge             (RoamSphere *sphere);
void                roam_sphere_split_one               (RoamSphere *sphere);
void                roam_sphere_update_errors           (RoamSphere *sphere);
void                roam_sphere_update_view             (RoamSphere *sphere);
void                roam_triangle_add                   (RoamTriangle *triangle,
                                                         RoamTriangle *left,
                                                         RoamTriangle *base,
                                                         RoamTriangle *right,
                                                         RoamSphere *sphere);
void                roam_triangle_draw                  (RoamTriangle *triangle);
void                roam_triangle_draw_normal           (RoamTriangle *triangle);
void                roam_triangle_free                  (RoamTriangle *triangle);
RoamTriangle *      roam_triangle_new                   (RoamPoint *l,
                                                         RoamPoint *m,
                                                         RoamPoint *r,
                                                         RoamDiamond *parent);
void                roam_triangle_remove                (RoamTriangle *triangle,
                                                         RoamSphere *sphere);
void                roam_triangle_split                 (RoamTriangle *triangle,
                                                         RoamSphere *sphere);
void                roam_triangle_update_errors         (RoamTriangle *triangle,
                                                         RoamSphere *sphere);

Description

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 GritsOpenGL when drawing surface textures for GritsTiles.

This implementation of the ROAM algorithm is based on an octahedron as the base model.

Details

struct RoamDiamond

struct 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.


RoamHeightFunc ()

gdouble             (*RoamHeightFunc)                   (gdouble lat,
                                                         gdouble lon,
                                                         gpointer user_data);

See GritsHeightFunc

lat :

the latitude

lon :

the longitude

user_data :

user data passed to the function

Returns :

the elevation

struct RoamPoint

struct 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 RoamSphere

struct 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 RoamTriangle

struct 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 RoamView

struct RoamView {
	gdouble model[16];
	gdouble proj[16];
	gint view[4];
	gint version;
};

Stores projection matrices

gdouble model[16];

model view matrix

gdouble proj[16];

projection matrix

gint view[4];

viewport matrix

gint version;

version

roam_diamond_add ()

void                roam_diamond_add                    (RoamDiamond *diamond,
                                                         RoamSphere *sphere);

Add a diamond into the sphere's pool of diamonds. It will be check for possible merges.

diamond :

the diamond

sphere :

the sphere to add the diamond to

roam_diamond_merge ()

void                roam_diamond_merge                  (RoamDiamond *diamond,
                                                         RoamSphere *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.

diamond :

the diamond

sphere :

the sphere

roam_diamond_new ()

RoamDiamond *       roam_diamond_new                    (RoamTriangle *parent0,
                                                         RoamTriangle *parent1);

Create a diamond to store information about two split triangles.

parent0 :

a parent triangle

parent1 :

a parent triangle

Returns :

the new diamond

roam_diamond_remove ()

void                roam_diamond_remove                 (RoamDiamond *diamond,
                                                         RoamSphere *sphere);

Remove a diamond from the sphere's pool of diamonds.

diamond :

the diamond

sphere :

the sphere to remove the diamond from

roam_diamond_update_errors ()

void                roam_diamond_update_errors          (RoamDiamond *diamond,
                                                         RoamSphere *sphere);

Update the error value associated with a diamond. Called when the view changes.

diamond :

the diamond

sphere :

the sphere to use when updating errors

roam_point_add_triangle ()

void                roam_point_add_triangle             (RoamPoint *point,
                                                         RoamTriangle *triangle);

Associating a triangle with a point and update it's vertex normal.

point :

the point

triangle :

the to add

roam_point_new ()

RoamPoint *         roam_point_new                      (double lat,
                                                         double lon,
                                                         double elev);

Create a new point at the given locaiton

lat :

the latitude for the point

lon :

the longitude for the point

elev :

the elevation for the point

Returns :

the new point

roam_point_remove_triangle ()

void                roam_point_remove_triangle          (RoamPoint *point,
                                                         RoamTriangle *triangle);

Un-associating a triangle with a point and update it's vertex normal.

point :

the point

triangle :

the to add

roam_point_update_height ()

void                roam_point_update_height            (RoamPoint *point);

Update the height (elevation) of a point based on the current height function

point :

the point

roam_point_update_projection ()

void                roam_point_update_projection        (RoamPoint *point,
                                                         RoamView *view);

Updated the screen-space projection of a point.

point :

the point

view :

the view to use when projecting the point

roam_sphere_draw ()

void                roam_sphere_draw                    (RoamSphere *sphere);

Draw the sphere. Use for debugging.

sphere :

the sphere

roam_sphere_draw_normals ()

void                roam_sphere_draw_normals            (RoamSphere *sphere);

Draw all the surface normal vectors for the sphere. Used while debugging.

sphere :

the sphere

roam_sphere_free ()

void                roam_sphere_free                    (RoamSphere *sphere);

Free data associated with a sphere

sphere :

the sphere

roam_sphere_get_intersect ()

GList *             roam_sphere_get_intersect           (RoamSphere *sphere,
                                                         gboolean all,
                                                         gdouble n,
                                                         gdouble s,
                                                         gdouble e,
                                                         gdouble w);

Lookup triangles withing the sphere that intersect a given lat-lon box.

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

Returns :

the list of intersecting triangles.

roam_sphere_merge_one ()

void                roam_sphere_merge_one               (RoamSphere *sphere);

Merge the diamond with the lowest error.

sphere :

the sphere

roam_sphere_new ()

RoamSphere *        roam_sphere_new                     ();

Create a new sphere

Returns :

the sphere

roam_sphere_split_merge ()

gint                roam_sphere_split_merge             (RoamSphere *sphere);

Perform a predetermined number split-merge iterations.

sphere :

the sphere

Returns :

the number splits and merges done

roam_sphere_split_one ()

void                roam_sphere_split_one               (RoamSphere *sphere);

Split the triangle with the greatest error.

sphere :

the sphere

roam_sphere_update_errors ()

void                roam_sphere_update_errors           (RoamSphere *sphere);

Update triangle and diamond errors in the sphere.

sphere :

the sphere

roam_sphere_update_view ()

void                roam_sphere_update_view             (RoamSphere *sphere);

Recreate the sphere's view matrices based on the current OpenGL state.

sphere :

the sphere

roam_triangle_add ()

void                roam_triangle_add                   (RoamTriangle *triangle,
                                                         RoamTriangle *left,
                                                         RoamTriangle *base,
                                                         RoamTriangle *right,
                                                         RoamSphere *sphere);

Add a triangle into the sphere's mesh using the given neighbors.

triangle :

the triangle

left :

the left neighbor

base :

the base neighbor

right :

the right neighbor

sphere :

the sphere to add the triangle to

roam_triangle_draw ()

void                roam_triangle_draw                  (RoamTriangle *triangle);

Draw the triangle. Use for debugging.

triangle :

the triangle

roam_triangle_draw_normal ()

void                roam_triangle_draw_normal           (RoamTriangle *triangle);

Draw a normal vector for the triangle. Used while debugging.

triangle :

the triangle

roam_triangle_free ()

void                roam_triangle_free                  (RoamTriangle *triangle);

Free data associated with a triangle

triangle :

the triangle

roam_triangle_new ()

RoamTriangle *      roam_triangle_new                   (RoamPoint *l,
                                                         RoamPoint *m,
                                                         RoamPoint *r,
                                                         RoamDiamond *parent);

Create a new triangle consisting of three points.

l :

the left point

m :

the middle point

r :

the right point

Returns :

the new triangle

roam_triangle_remove ()

void                roam_triangle_remove                (RoamTriangle *triangle,
                                                         RoamSphere *sphere);

Remove a triangle from a sphere's mesh.

triangle :

the triangle

sphere :

the sphere to remove the triangle from

roam_triangle_split ()

void                roam_triangle_split                 (RoamTriangle *triangle,
                                                         RoamSphere *sphere);

Split a triangle into two child triangles and update the sphere. triangle

triangle :

the triangle

sphere :

the sphere

roam_triangle_update_errors ()

void                roam_triangle_update_errors         (RoamTriangle *triangle,
                                                         RoamSphere *sphere);

Update the error value associated with a triangle. Called when the view changes.

triangle :

the triangle

sphere :

the sphere to use when updating errors