gts/oocs.c

   1 /* GTS - Library for the manipulation of triangulated surfaces
   2  * Copyright (C) 1999 Stéphane Popinet
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 #include <math.h>
  21 #include "gts.h"
  22
  23 static void cluster_destroy (GtsObject * object)
  24 {
  25   GtsCluster * c = GTS_CLUSTER (object);
  26
  27   if (c->v && gts_vertex_is_unattached (c->v))
  28     gts_object_destroy (GTS_OBJECT (c->v));
  29
  30   /* do not forget to call destroy method of the parent */
  31   (* GTS_OBJECT_CLASS (gts_cluster_class ())->parent_class->destroy) (object);
  32 }
  33
  34 static void cluster_add (GtsCluster * c, GtsPoint * p, gpointer data)
  35 {
  36   GtsPoint * cp;
  37
  38   g_return_if_fail (c != NULL);
  39   g_return_if_fail (c->v != NULL);
  40   g_return_if_fail (p != NULL);
  41
  42   cp = GTS_POINT (c->v);
  43
  44   cp->x += p->x;
  45   cp->y += p->y;
  46   cp->z += p->z;
  47   c->n++;
  48 }
  49
  50 static void cluster_update (GtsCluster * c)
  51 {
  52   GtsPoint * p;
  53
  54   g_return_if_fail (c != NULL);
  55   g_return_if_fail (c->v != NULL);
  56
  57   if (c->n > 1) {
  58     p = GTS_POINT (c->v);
  59     p->x /= c->n;
  60     p->y /= c->n;
  61     p->z /= c->n;
  62   }
  63 }
  64
  65 static void cluster_class_init (GtsClusterClass * klass)
  66 {
  67   klass->add = cluster_add;
  68   klass->update = cluster_update;
  69
  70   GTS_OBJECT_CLASS (klass)->destroy = cluster_destroy;
  71 }
  72
  73 static void cluster_init (GtsCluster * c)
  74 {
  75   c->v = NULL;
  76   c->n = 0;
  77 }
  78
  79 /**
  80  * gts_cluster_class:
  81  *
  82  * Returns: the #GtsClusterClass.
  83  */
  84 GtsClusterClass * gts_cluster_class (void)
  85 {
  86   static GtsClusterClass * klass = NULL;
  87
  88   if (klass == NULL) {
  89     GtsObjectClassInfo cluster_info = {
  90       "GtsCluster",
  91       sizeof (GtsCluster),
  92       sizeof (GtsClusterClass),
  93       (GtsObjectClassInitFunc) cluster_class_init,
  94       (GtsObjectInitFunc) cluster_init,
  95       (GtsArgSetFunc) NULL,
  96       (GtsArgGetFunc) NULL
  97     };
  98     klass = gts_object_class_new (gts_object_class (), &cluster_info);
  99   }
 100
 101   return klass;
 102 }
 103
 104 /**
 105  * gts_cluster_new:
 106  * @klass: a #GtsClusterClass.
 107  * @id: the id of the new cluster.
 108  * @vklass: a #GtsVertexClass for the representative vertex of the cluster.
 109  *
 110  * Returns: a new #GtsCluster.
 111  */
 112 GtsCluster * gts_cluster_new (GtsClusterClass * klass,
 113                               GtsClusterId id,
 114                               GtsVertexClass * vklass)
 115 {
 116   GtsCluster * c;
 117
 118   c = GTS_CLUSTER (gts_object_new (GTS_OBJECT_CLASS (klass)));
 119   c->id = id;
 120   c->v = gts_vertex_new (vklass, 0., 0., 0.);
 121
 122   return c;
 123 }
 124
 125 /**
 126  * gts_cluster_add:
 127  * @c: a #GtsCluster.
 128  * @p: a #GtsPoint.
 129  * @data: data to pass to the add() virtual method of #GtsClusterClass.
 130  *
 131  * Adds point @p to cluster @c.
 132  */
 133 void gts_cluster_add (GtsCluster * c, GtsPoint * p, gpointer data)
 134 {
 135   g_return_if_fail (c != NULL);
 136   g_return_if_fail (p != NULL);
 137
 138   (* GTS_CLUSTER_CLASS (GTS_OBJECT (c)->klass)->add) (c, p, data);
 139 }
 140
 141 /**
 142  * gts_cluster_update:
 143  * @c: a #GtsCluster.
 144  *
 145  * Updates the position of the vertex representative of all the
 146  * vertices added to @c.
 147  */
 148 void gts_cluster_update (GtsCluster * c)
 149 {
 150   g_return_if_fail (c != NULL);
 151
 152   (* GTS_CLUSTER_CLASS (GTS_OBJECT (c)->klass)->update) (c);
 153 }
 154
 155 static void destroy_cluster (GtsClusterId * id, GtsObject * cluster)
 156 {
 157   gts_object_destroy (cluster);
 158 }
 159
 160 static void cluster_grid_destroy (GtsObject * object)
 161 {
 162   GtsClusterGrid * cluster_grid = GTS_CLUSTER_GRID (object);
 163
 164   g_hash_table_foreach (cluster_grid->clusters,
 165                         (GHFunc) destroy_cluster, NULL);
 166   g_hash_table_destroy (cluster_grid->clusters);
 167
 168   (* GTS_OBJECT_CLASS (gts_cluster_grid_class ())->parent_class->destroy)
 169     (object);
 170 }
 171
 172 static void cluster_grid_class_init (GtsClusterGridClass * klass)
 173 {
 174   GTS_OBJECT_CLASS (klass)->destroy = cluster_grid_destroy;
 175 }
 176
 177 static gint cluster_id_equal (gconstpointer v1,
 178                               gconstpointer v2)
 179 {
 180   const GtsClusterId * id1 = (const GtsClusterId *) v1;
 181   const GtsClusterId * id2 = (const GtsClusterId *) v2;
 182   return ((id1->x == id2->x) && (id1->y == id2->y) && (id1->z == id2->z));
 183 }
 184
 185 static guint cluster_id_hash (gconstpointer key)
 186 {
 187   const GtsClusterId * id = (const GtsClusterId *) key;
 188   return id->x + id->y + id->z;
 189 }
 190
 191 static void cluster_grid_init (GtsClusterGrid * cluster_grid)
 192 {
 193   cluster_grid->surface = NULL;
 194   cluster_grid->bbox = NULL;
 195   cluster_grid->cluster_class = gts_cluster_class ();
 196   cluster_grid->clusters = g_hash_table_new (cluster_id_hash,
 197                                               cluster_id_equal);
 198 }
 199
 200 /**
 201  * gts_cluster_grid_class:
 202  *
 203  * Returns: the #GtsClusterGridClass.
 204  */
 205 GtsClusterGridClass * gts_cluster_grid_class (void)
 206 {
 207   static GtsClusterGridClass * klass = NULL;
 208
 209   if (klass == NULL) {
 210     GtsObjectClassInfo cluster_grid_info = {
 211       "GtsClusterGrid",
 212       sizeof (GtsClusterGrid),
 213       sizeof (GtsClusterGridClass),
 214       (GtsObjectClassInitFunc) cluster_grid_class_init,
 215       (GtsObjectInitFunc) cluster_grid_init,
 216       (GtsArgSetFunc) NULL,
 217       (GtsArgGetFunc) NULL
 218     };
 219     klass = gts_object_class_new (gts_object_class (), &cluster_grid_info);
 220   }
 221
 222   return klass;
 223 }
 224
 225 /**
 226  * gts_cluster_grid_new:
 227  * @klass: a #GtsClusterGridClass.
 228  * @cluster_class: the klass to be used for the vertex clusters.
 229  * @s: the simplified surface.
 230  * @bbox: bounding box of the surface to be simplified.
 231  * @delta: the size of one grid cell of the simplification grid.
 232  *
 233  * Returns: a new #GtsClusterGrid.
 234  */
 235 GtsClusterGrid * gts_cluster_grid_new (GtsClusterGridClass * klass,
 236                                        GtsClusterClass * cluster_class,
 237                                        GtsSurface * s,
 238                                        GtsBBox * bbox,
 239                                        gdouble delta)
 240 {
 241   GtsClusterGrid * cluster_grid;
 242   GtsVector size;
 243
 244   g_return_val_if_fail (klass != NULL, NULL);
 245   g_return_val_if_fail (cluster_class != NULL, NULL);
 246   g_return_val_if_fail (s != NULL, NULL);
 247   g_return_val_if_fail (bbox != NULL, NULL);
 248   g_return_val_if_fail (delta > 0., NULL);
 249
 250   size[0] = ceil ((bbox->x2 - bbox->x1)/delta);
 251   size[1] = ceil ((bbox->y2 - bbox->y1)/delta);
 252   size[2] = ceil ((bbox->z2 - bbox->z1)/delta);
 253   g_return_val_if_fail (size[0] <= 2.*G_MAXINT + 2. &&
 254                         size[1] <= 2.*G_MAXINT + 2. &&
 255                         size[2] <= 2.*G_MAXINT + 2., NULL);
 256   cluster_grid =
 257     GTS_CLUSTER_GRID (gts_object_new (GTS_OBJECT_CLASS (klass)));
 258   cluster_grid->cluster_class = cluster_class;
 259   cluster_grid->surface = s;
 260   cluster_grid->bbox = bbox;
 261   cluster_grid->size[0] = size[0];
 262   cluster_grid->size[1] = size[1];
 263   cluster_grid->size[2] = size[2];
 264
 265   return cluster_grid;
 266 }
 267
 268 static GtsClusterId cluster_index (GtsPoint * p,
 269                                    GtsBBox * bb,
 270                                    GtsVector n)
 271 {
 272   GtsClusterId id = {0, 0, 0};
 273
 274   g_return_val_if_fail (p->x >= bb->x1 && p->x <= bb->x2, id);
 275   g_return_val_if_fail (p->y >= bb->y1 && p->y <= bb->y2, id);
 276   g_return_val_if_fail (p->z >= bb->z1 && p->z <= bb->z2, id);
 277
 278   id.x = (guint) (p->x == bb->x2 ? n[0] - 1. : n[0]*(p->x - bb->x1)/(bb->x2 - bb->x1));
 279   id.y = (guint) (p->y == bb->y2 ? n[1] - 1. : n[1]*(p->y - bb->y1)/(bb->y2 - bb->y1));
 280   id.z = (guint) (p->z == bb->z2 ? n[2] - 1. : n[2]*(p->z - bb->z1)/(bb->z2 - bb->z1));
 281
 282   return id;
 283 }
 284
 285 static GtsCluster * cluster_grid_add_point (GtsClusterGrid * cluster_grid,
 286                                             GtsPoint * p,
 287                                             gpointer data)
 288 {
 289   GtsClusterId id = cluster_index (p,
 290                                    cluster_grid->bbox,
 291                                    cluster_grid->size);
 292   GtsCluster * c = g_hash_table_lookup (cluster_grid->clusters, &id);
 293
 294   if (c == NULL) {
 295     c = gts_cluster_new (cluster_grid->cluster_class, id,
 296                          cluster_grid->surface->vertex_class);
 297     g_hash_table_insert (cluster_grid->clusters, &c->id, c);
 298   }
 299
 300   gts_cluster_add (c, p, data);
 301
 302   return c;
 303 }
 304
 305 /**
 306  * gts_cluster_grid_add_triangle:
 307  * @cluster_grid: a #GtsClusterGrid.
 308  * @p1: a #GtsPoint.
 309  * @p2: a #GtsPoint.
 310  * @p3: a #GtsPoint.
 311  * @data: user data to pass to the cluster add() method.
 312  *
 313  * Adds the triangle defined by @p1, @p2 and @p3 to the respective clusters
 314  * of @cluster_grid.
 315  */
 316 void gts_cluster_grid_add_triangle (GtsClusterGrid * cluster_grid,
 317                                     GtsPoint * p1,
 318                                     GtsPoint * p2,
 319                                     GtsPoint * p3,
 320                                     gpointer data)
 321 {
 322   GtsCluster * c1, * c2, * c3;
 323
 324   g_return_if_fail (cluster_grid != NULL);
 325   g_return_if_fail (p1 != NULL);
 326   g_return_if_fail (p2 != NULL);
 327   g_return_if_fail (p3 != NULL);
 328   g_return_if_fail (cluster_grid->surface != NULL);
 329
 330   c1 = cluster_grid_add_point (cluster_grid, p1, data);
 331   c2 = cluster_grid_add_point (cluster_grid, p2, data);
 332   c3 = cluster_grid_add_point (cluster_grid, p3, data);
 333
 334   if (c1 != c2 && c2 != c3 && c3 != c1) {
 335     GtsVertex * v1, * v2, * v3;
 336     GtsEdge * e1, * e2, * e3;
 337     gboolean new_edge = FALSE;
 338
 339     v1 = c1->v; v2 = c2->v; v3 = c3->v;
 340
 341     if ((e1 = GTS_EDGE (gts_vertices_are_connected (v1, v2))) == NULL) {
 342       e1 = gts_edge_new (cluster_grid->surface->edge_class, v1, v2);
 343       new_edge = TRUE;
 344     }
 345     if ((e2 = GTS_EDGE (gts_vertices_are_connected (v2, v3))) == NULL) {
 346       e2 = gts_edge_new (cluster_grid->surface->edge_class, v2, v3);
 347       new_edge = TRUE;
 348     }
 349     if ((e3 = GTS_EDGE (gts_vertices_are_connected (v3, v1))) == NULL) {
 350       e3 = gts_edge_new (cluster_grid->surface->edge_class, v3, v1);
 351       new_edge = TRUE;
 352     }
 353     if (new_edge || !gts_triangle_use_edges (e1, e2, e3))
 354       gts_surface_add_face (cluster_grid->surface,
 355                             gts_face_new (cluster_grid->surface->face_class,
 356                                           e1, e2, e3));
 357   }
 358 }
 359
 360 static void update_cluster (gint * id, GtsCluster * cluster, GtsRange * stats)
 361 {
 362   gts_cluster_update (cluster);
 363   gts_range_add_value (stats, cluster->n);
 364 }
 365
 366 /**
 367  * gts_cluster_grid_update:
 368  * @cluster_grid: a #GtsClusterGrid.
 369  *
 370  * Updates the representative vertices of all the clusters of @cluster_grid.
 371  *
 372  * Returns: a #GtsRange describing the statistics for the number of vertices
 373  * added to each cluster of @cluster_grid.
 374  */
 375 GtsRange gts_cluster_grid_update (GtsClusterGrid * cluster_grid)
 376 {
 377   GtsRange stats;
 378
 379   gts_range_init (&stats);
 380   g_return_val_if_fail (cluster_grid != NULL, stats);
 381
 382   g_hash_table_foreach (cluster_grid->clusters,
 383                         (GHFunc) update_cluster, &stats);
 384   gts_range_update (&stats);
 385
 386   return stats;
 387 }