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
cluster_destroy(GtsObject * object)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
cluster_add(GtsCluster * c,GtsPoint * p,gpointer data)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
cluster_update(GtsCluster * c)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
cluster_class_init(GtsClusterClass * klass)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
cluster_init(GtsCluster * c)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 */
gts_cluster_class(void)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 */
gts_cluster_new(GtsClusterClass * klass,GtsClusterId id,GtsVertexClass * vklass)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 */
gts_cluster_add(GtsCluster * c,GtsPoint * p,gpointer data)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 */
gts_cluster_update(GtsCluster * c)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
destroy_cluster(GtsClusterId * id,GtsObject * cluster)155 static void destroy_cluster (GtsClusterId * id, GtsObject * cluster)
156 {
157 gts_object_destroy (cluster);
158 }
159
cluster_grid_destroy(GtsObject * object)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
cluster_grid_class_init(GtsClusterGridClass * klass)172 static void cluster_grid_class_init (GtsClusterGridClass * klass)
173 {
174 GTS_OBJECT_CLASS (klass)->destroy = cluster_grid_destroy;
175 }
176
cluster_id_equal(gconstpointer v1,gconstpointer v2)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
cluster_id_hash(gconstpointer key)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
cluster_grid_init(GtsClusterGrid * cluster_grid)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 */
gts_cluster_grid_class(void)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 */
gts_cluster_grid_new(GtsClusterGridClass * klass,GtsClusterClass * cluster_class,GtsSurface * s,GtsBBox * bbox,gdouble delta)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
cluster_index(GtsPoint * p,GtsBBox * bb,GtsVector n)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
cluster_grid_add_point(GtsClusterGrid * cluster_grid,GtsPoint * p,gpointer data)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 */
gts_cluster_grid_add_triangle(GtsClusterGrid * cluster_grid,GtsPoint * p1,GtsPoint * p2,GtsPoint * p3,gpointer data)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
update_cluster(gint * id,GtsCluster * cluster,GtsRange * stats)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 */
gts_cluster_grid_update(GtsClusterGrid * cluster_grid)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 }
388