## 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