Out-of-core simplification

Name

Out-of-core simplification -- objects for simplification based on vertex clustering.

Synopsis


#include <gts.h>


#define     GTS_CLUSTER_CLASS               (klass)
#define     GTS_CLUSTER                     (obj)
#define     GTS_IS_CLUSTER                  (obj)
struct      GtsClusterClass;
struct      GtsCluster;
struct      GtsClusterId;

GtsClusterClass* gts_cluster_class          (void);
GtsCluster* gts_cluster_new                 (GtsClusterClass *klass,
                                             GtsClusterId id,
                                             GtsVertexClass *vklass);
void        gts_cluster_add                 (GtsCluster *c,
                                             GtsPoint *p,
                                             gpointer data);
void        gts_cluster_update              (GtsCluster *c);

#define     GTS_CLUSTER_GRID_CLASS          (klass)
#define     GTS_CLUSTER_GRID                (obj)
#define     GTS_IS_CLUSTER_GRID             (obj)
struct      GtsClusterGridClass;
struct      GtsClusterGrid;

GtsClusterGridClass* gts_cluster_grid_class (void);
GtsClusterGrid* gts_cluster_grid_new        (GtsClusterGridClass *klass,
                                             GtsClusterClass *cluster_class,
                                             GtsSurface *s,
                                             GtsBBox *bbox,
                                             gdouble delta);
void        gts_cluster_grid_add_triangle   (GtsClusterGrid *cluster_grid,
                                             GtsPoint *p1,
                                             GtsPoint *p2,
                                             GtsPoint *p3,
                                             gpointer data);
GtsRange    gts_cluster_grid_update         (GtsClusterGrid *cluster_grid);

Description

Using vertex clusters and vertex cluster grids it is easy to design out-of-core algorithms for surface simplification. This approach has been detailed in a recent paper by Lindstrom and Turk ("Out-of-core simplification of large polygonal models", 2000).

Vertex clusters are just groups of vertices collapsed into a single vertex. The position of this single representative vertex can be derived with different techniques. The default GTS implementation GtsCluster just takes the average of the positions of the vertices in a given cluster as the representative position. Clusters are created using gts_cluster_new(). The cluster is initially empty and the position of the representative vertex is set to the origin. Vertices are added using gts_cluster_add() which calls the add() virtual method of GtsClusterClass. Once all the vertices have been added gts_cluster_update() computes the position of the representative vertex.

Clusters are grouped using the GtsClusterGrid object which is just an implementation of the hash-table based regular grid of Lindstrom and Turk. This regular grid is created using gts_cluster_grid_new(). Once created triangles of the surface to be simplified can be added using gts_cluster_grid_add_triangle() which adds the vertices of the triangle to the GtsCluster they belong to and adds the corresponding faces to the simplified surface. After all the triangles of the original surface have been added the position of the representative vertex of all the vertex clusters is computed using gts_cluster_grid_update(). The simplified surface is then complete and the cluster grid can be destroyed using gts_object_destroy().

Details

GTS_CLUSTER_CLASS()

#define     GTS_CLUSTER_CLASS(klass)

Casts klass to GtsClusterClass.

klass :

a descendant of GtsClusterClass.


GTS_CLUSTER()

#define     GTS_CLUSTER(obj)

Casts obj to GtsCluster.

obj :

a descendant of GtsCluster.


GTS_IS_CLUSTER()

#define     GTS_IS_CLUSTER(obj)

Evaluates to TRUE if obj is a GtsCluster, FALSE otherwise.

obj :

a pointer to test.


struct GtsClusterClass

struct GtsClusterClass {

  GtsObjectClass parent_class;

  void (* add) (GtsCluster * c, GtsPoint * p, gpointer data);
  void (* update) (GtsCluster * c);
};

The cluster class derived from GtsClusterClass. Virtual function add adds point p to the cluster while passing user-data data. Virtual function update computes the position of the representative vertex.


struct GtsCluster

struct GtsCluster {

  GtsObject parent;

  GtsClusterId id;
  GtsVertex * v;
  guint n;
};

The cluster object.

GtsObject parent

The parent object.

GtsClusterId id

Unique identifier.

GtsVertex *v

GtsVertex representative of all the vertices in the cluster.

guint n

Number of vertices added to the cluster.


struct GtsClusterId

struct GtsClusterId {

  guint x, y, z;
};


gts_cluster_class ()

GtsClusterClass* gts_cluster_class          (void);

Returns :

the GtsClusterClass.


gts_cluster_new ()

GtsCluster* gts_cluster_new                 (GtsClusterClass *klass,
                                             GtsClusterId id,
                                             GtsVertexClass *vklass);

klass :

a GtsClusterClass.

id :

the id of the new cluster.

vklass :

a GtsVertexClass for the representative vertex of the cluster.

Returns :

a new GtsCluster.


gts_cluster_add ()

void        gts_cluster_add                 (GtsCluster *c,
                                             GtsPoint *p,
                                             gpointer data);

Adds point p to cluster c.

c :

a GtsCluster.

p :

a GtsPoint.

data :

data to pass to the add() virtual method of GtsClusterClass.


gts_cluster_update ()

void        gts_cluster_update              (GtsCluster *c);

Updates the position of the vertex representative of all the vertices added to c.

c :

a GtsCluster.


GTS_CLUSTER_GRID_CLASS()

#define     GTS_CLUSTER_GRID_CLASS(klass)

Casts klass to GtsClusterGridClass.

klass :

a descendant of GtsClusterGridClass.


GTS_CLUSTER_GRID()

#define     GTS_CLUSTER_GRID(obj)

Casts obj to GtsCluster.

obj :

a descendant of GtsCluster.


GTS_IS_CLUSTER_GRID()

#define     GTS_IS_CLUSTER_GRID(obj)

Evaluates to TRUE if obj is a GtsCluster, FALSE otherwise.

obj :

a pointer to test.


struct GtsClusterGridClass

struct GtsClusterGridClass {

  GtsObjectClass parent_class;
};

The cluster grid class derived from GtsObjectClass.


struct GtsClusterGrid

struct GtsClusterGrid {

  GtsObject parent;

  GtsSurface * surface;
  GtsBBox * bbox;
  GtsVector size;

  GtsClusterClass * cluster_class;
  GHashTable * clusters;
};

The cluster grid object.

GtsObject parent

The parent object.

GtsSurface *surface

Surface being simplified.

GtsBBox *bbox

Bounding box of the original surface.

GtsVector size

Size of the simplification grid.

GtsClusterClass *cluster_class

Private.

GHashTable *clusters

Private.


gts_cluster_grid_class ()

GtsClusterGridClass* gts_cluster_grid_class (void);

Returns :

the GtsClusterGridClass.


gts_cluster_grid_new ()

GtsClusterGrid* gts_cluster_grid_new        (GtsClusterGridClass *klass,
                                             GtsClusterClass *cluster_class,
                                             GtsSurface *s,
                                             GtsBBox *bbox,
                                             gdouble delta);

klass :

a GtsClusterGridClass.

cluster_class :

the klass to be used for the vertex clusters.

s :

the simplified surface.

bbox :

bounding box of the surface to be simplified.

delta :

the size of one grid cell of the simplification grid.

Returns :

a new GtsClusterGrid.


gts_cluster_grid_add_triangle ()

void        gts_cluster_grid_add_triangle   (GtsClusterGrid *cluster_grid,
                                             GtsPoint *p1,
                                             GtsPoint *p2,
                                             GtsPoint *p3,
                                             gpointer data);

Adds the triangle defined by p1, p2 and p3 to the respective clusters of cluster_grid.

cluster_grid :

a GtsClusterGrid.

p1 :

a GtsPoint.

p2 :

a GtsPoint.

p3 :

a GtsPoint.

data :

user data to pass to the cluster add() method.


gts_cluster_grid_update ()

GtsRange    gts_cluster_grid_update         (GtsClusterGrid *cluster_grid);

Updates the representative vertices of all the clusters of cluster_grid.

cluster_grid :

a GtsClusterGrid.

Returns :

a GtsRange describing the statistics for the number of vertices added to each cluster of cluster_grid.