2
* Pure Data Packet module. mesh implementation
3
* Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org>
5
* This program is free software; you can redistribute it and/or modify
6
* it under the terms of the GNU General Public License as published by
7
* the Free Software Foundation; either version 2 of the License, or
8
* (at your option) any later version.
10
* This program is distributed in the hope that it will be useful,
11
* but WITHOUT ANY WARRANTY; without even the implied warranty of
12
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
* GNU General Public License for more details.
15
* You should have received a copy of the GNU General Public License
16
* along with this program; if not, write to the Free Software
17
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21
/* a very naive approach to triangular meshes */
24
// $$TODO: some serious memory corruption in this file our the list implementation
34
void vertex_add_triangle(t_vertex *v, t_triangle *t)
36
pdp_list_add_pointer(v->trilist, t);
38
void vertex_remove_triangle(t_vertex *v, t_triangle *t)
40
pdp_list_remove_pointer(v->trilist, t);
42
void vertex_add_neighbour(t_vertex *v, t_vertex *neighbour)
44
pdp_list_add_pointer_to_set(v->vertlist, neighbour);
48
/* constructor/destructors are "private"
49
they may only be called by the mesh object to ensure
50
the vector list stays sound (i.e. without duplicates) */
51
void _vertex_free(t_vertex *v)
53
if (!v->trilist) post("WARNING: vertex %x has empty trilist", v);
55
pdp_list_free(v->trilist);
58
if (!v->vertlist) post("WARNING: vertex %x has empty vertlist", v);
60
pdp_list_free(v->vertlist);
66
t_vertex *_vertex_new(float *c, float *n)
69
t_vertex *v = (t_vertex *) pdp_alloc(sizeof(t_vertex));
72
v->trilist = pdp_list_new(0);
73
v->vertlist = pdp_list_new(0);
78
void vertex_compute_normal_random(t_vertex *v){int k; I3(k) v->n[k] = _rand();}
79
void vertex_compute_normal_sphere(t_vertex *v){int k; I3(k) v->n[k] = v->c[k];}
80
void vertex_compute_normal_prism(t_vertex *v)
83
float sum[] = {0.0f, 0.0f, 0.0f};
86
t_pdp_list *vl = v->vertlist;
89
PDP_POINTER_IN(vl, i, vtx) {
90
I3(k) sum[k] += vtx->c[k];
94
I3(k) sum[k] *= scale;
95
I3(k) v->n[k] = v->c[k] - sum[k];
97
//post("computed normal (%f, %f, %f) of vertex (%f, %f, %f)", v->n[0], v->n[1], v->n[2], v->c[0], v->c[1], v->c[2]);
99
void vertex_compute_normal_average(t_vertex *v)
101
int triangles = pdp_list_size(v->trilist);
102
float scale = 1.0f / ((float)triangles);
107
I3(k) v->n[k] = 0; //reset normal
108
PDP_POINTER_IN(v->trilist, i, t){
109
I3(k) v->n[k] += t->n[k];
111
_vector3_scale(v->n, scale);
117
float vertex_normalize(t_vertex *v)
119
return _vector3_normalize(v->c);
123
/* TRIANGLE methods */
125
/* create triangle (a connection between 3 vertices):
126
counterclockwize with facing front
127
this method is "private"
128
you can only create triangles as part of a mesh */
129
t_triangle *_triangle_new(t_vertex *v0, t_vertex *v1, t_vertex *v2)
133
t_triangle *t = (t_triangle *)pdp_alloc(sizeof(t_triangle));
135
/* store vertex references */
140
/* reset median vertices */
143
/* connect triangle to vertices */
144
vertex_add_triangle(v0, t);
145
vertex_add_triangle(v1, t);
146
vertex_add_triangle(v2, t);
148
/* connect vertices to vertices */
149
vertex_add_neighbour(v0, v1);
150
vertex_add_neighbour(v0, v2);
151
vertex_add_neighbour(v1, v0);
152
vertex_add_neighbour(v1, v2);
153
vertex_add_neighbour(v2, v0);
154
vertex_add_neighbour(v2, v1);
159
/* delete a triangle, disconnecting the vertices */
160
void _triangle_free(t_triangle *t)
164
/* remove the triangle reference of the vertices */
165
I3(k) vertex_remove_triangle(t->v[k], t);
167
/* set references to zero (bug catcher) */
176
/* get triangle that shares the link between v0 and v1 */
177
t_triangle *triangle_neighbour(t_triangle *t, t_vertex *v0, t_vertex *v1)
181
PDP_POINTER_IN(v1->trilist, it, tri){
182
if (tri != t && pdp_list_contains_pointer(v0->trilist, tri)) return tri;
187
/* add a median vector to a link in a triangle
188
note: vertices must be in triangle, or behaviour is undefined */
189
void triangle_add_median(t_triangle *t, t_vertex *v0, t_vertex *v1, t_vertex *median)
193
if (!((v0 == t->v[2]) || (v1 == t->v[2]))) t->m[0] = median;
196
else if (!((v0 == t->v[0]) || (v1 == t->v[0]))) t->m[1] = median;
199
else t->m[2] = median;
202
void triangle_compute_normal(t_triangle *t)
207
I3(k) v0[k] = t->v[1]->c[k] - t->v[0]->c[k];
208
I3(k) v1[k] = t->v[2]->c[k] - t->v[0]->c[k];
209
_vector3_cross(v0,v1,t->n);
212
void triangle_compute_unit_normal(t_triangle *t)
214
triangle_compute_normal(t);
215
_vector3_normalize(t->n);
220
/* add and remove methods for vertices and triangles */
221
t_vertex *mesh_vertex_add(t_mesh *m, float *c, float *n)
223
t_vertex *v = _vertex_new(c, n);
224
pdp_list_add_pointer(m->vertices, v);
228
void mesh_vertex_remove(t_mesh *m, t_vertex *v)
230
pdp_list_remove_pointer(m->vertices, v);
234
t_triangle *mesh_triangle_add(t_mesh *m, t_vertex *v0, t_vertex *v1, t_vertex *v2)
236
t_triangle *t = _triangle_new(v0,v1,v2);
237
pdp_list_add_pointer(m->triangles, t);
241
void mesh_triangle_remove(t_mesh *m, t_triangle *t)
243
pdp_list_remove_pointer(m->triangles, t);
247
/* calculate normals */
248
void mesh_calculate_normals(t_mesh *m)
252
t_pdp_list *l = m->vertices;
253
t_pdp_list *l_tri = m->triangles;
256
//while (v = pdp_list_getnext_pointer(l, &it)) vertex_compute_normal_sphere(v);
257
switch(m->normal_type){
259
case MESH_NORMAL_SPHERE: PDP_POINTER_IN(l, it, v) vertex_compute_normal_sphere(v); break;
260
case MESH_NORMAL_PRISM: PDP_POINTER_IN(l, it, v) vertex_compute_normal_prism(v); break;
261
case MESH_NORMAL_RANDOM: PDP_POINTER_IN(l, it, v) vertex_compute_normal_random(v); break;
262
case MESH_NORMAL_AVERAGE:
263
PDP_POINTER_IN(l_tri, it_tri, t) triangle_compute_unit_normal(t);
264
PDP_POINTER_IN(l, it, v) vertex_compute_normal_average(v);
269
/* split a triangle in 4, using the intermedia median vertex storage */
270
void mesh_split_four(t_mesh *m, t_triangle *old_t)
275
/* some intermediates */
276
t_triangle *neighbour;
277
t_float newv[] = {0,0,0};
278
t_float nullvect[] = {0,0,0};
281
/* get main vertices */
282
I3(k) v[k] = old_t->v[k];
284
/* get median vertices inserted by neighbouring triangles */
285
I3(k) v[k+3] = old_t->m[k];
287
#define GET_MEDIAN(v, v0, v1) \
289
I3(k) newv[k] = 0.5f * (v0->c[k] + v1->c[k]); \
290
v = mesh_vertex_add(m, newv, nullvect); \
291
/*vertex_normalize(v);*/ \
292
if (neighbour = triangle_neighbour(old_t, v0, v1)){ \
293
triangle_add_median(neighbour, v0, v1, v); \
297
GET_MEDIAN(v[3], v[0], v[1])
298
GET_MEDIAN(v[4], v[1], v[2])
299
GET_MEDIAN(v[5], v[2], v[0])
303
/* remove the old triangle */
304
mesh_triangle_remove(m, old_t);
306
/* create 4 new triangles */
307
mesh_triangle_add(m, v[0], v[3], v[5]);
308
mesh_triangle_add(m, v[1], v[4], v[3]);
309
mesh_triangle_add(m, v[2], v[5], v[4]);
310
mesh_triangle_add(m, v[3], v[4], v[5]);
314
/* split a triangle in 3 */
315
void mesh_split_three(t_mesh *m, t_triangle *old_t)
319
t_float newv[] = {0,0,0};
320
t_float nullvect[] = {0,0,0};
323
I3(k) v[k] = old_t->v[k];
325
/* remove a triangle */
326
mesh_triangle_remove(m, old_t);
328
/* compute new vertex coordinates */
329
I3(k) I3(l) newv[k] += 0.33333f * v[l]->c[k];
331
/* create new vertex */
332
v[3] = mesh_vertex_add(m, newv, nullvect);
333
//vertex_normalize(v[3]);
335
/* create 3 new triangles */
336
mesh_triangle_add(m, v[0], v[1], v[3]);
337
mesh_triangle_add(m, v[1], v[2], v[3]);
338
mesh_triangle_add(m, v[2], v[0], v[3]);
344
void mesh_split_all_four(t_mesh *m)
347
t_pdp_list *l = pdp_list_copy(m->triangles);
349
//post("split_all_four: nb triangles %d", pdp_list_size(m->triangles));
352
t = pdp_list_pop(l).w_pointer;
353
mesh_split_four(m, t);
355
mesh_calculate_normals(m);
360
void mesh_split_all_three(t_mesh *m)
363
t_pdp_list *l = pdp_list_copy(m->triangles);
365
//post("split_all_three: nb triangles %d", pdp_list_size(m->triangles));
368
t = pdp_list_pop(l).w_pointer;
369
mesh_split_three(m, t);
371
mesh_calculate_normals(m);
375
void mesh_split_random_three(t_mesh *m)
377
int size = pdp_list_size(m->triangles);
378
t_triangle *t = pdp_list_index(m->triangles, (random() % size)).w_pointer;
379
mesh_split_three(m, t);
380
mesh_calculate_normals(m);
385
void mesh_free(t_mesh *m)
391
/* delete all triangles */
392
while (m->triangles->elements){
393
t = pdp_list_pop(m->triangles).w_pointer;
394
//post("freeing triangle %x", t);
397
pdp_list_free(m->triangles);
400
/* delete all vertices */
401
while (m->vertices->elements){
402
v = pdp_list_pop(m->vertices).w_pointer;
403
//post("freeing vertex %x", v);
406
pdp_list_free(m->vertices);
414
t_mesh *_mesh_new(void)
416
t_mesh *m = (t_mesh *)pdp_alloc(sizeof(t_mesh));
418
/* create main vertex and triangle lists */
419
m->triangles = pdp_list_new(0);
420
m->vertices = pdp_list_new(0);
422
/* set normal type */
423
m->normal_type = MESH_NORMAL_PRISM;
429
t_mesh *mesh_new_tetra(void)
436
t_mesh *m = _mesh_new();
439
float fv[4][3] = {{2,0,0},{0,2,0},{0,0,2}, {-1,-1,-1}};
442
I4(k) v[k] = mesh_vertex_add(m, &fv[k][0], n);
443
I4(k) vertex_normalize(v[k]);
446
mesh_triangle_add(m, v[0], v[1], v[2]);
447
mesh_triangle_add(m, v[1], v[0], v[3]);
448
mesh_triangle_add(m, v[0], v[2], v[3]);
449
mesh_triangle_add(m, v[1], v[3], v[2]);
452
/* compute normals */
453
mesh_calculate_normals(m);
459
void _mesh_relax_compute_resultant_spring(t_mesh *m, float *center, float d0, float r0)
465
PDP_POINTER_IN(m->vertices, i, v){
469
/* compute contribution of origin link */
470
I3(k) v->n[k] = v->c[k] - center[k];
471
r = _vector3_normalize(v->n);
472
I3(k) v->n[k] *= (r0 - r);
474
PDP_POINTER_IN(v->vertlist, j, w){
479
/* compute force contribution of one link (model: spring with rest length == d0) */
480
I3(k) f[k] = w->c[k] - v->c[k]; // PC: f == distance vector
481
d = _vector3_normalize(f); // PC: d == distance, vector == unit norm
482
I3(k) v->n[k] += (d - d0) * f[k]; // PC: n == n_prev + fource resultant
487
void _mesh_relax_apply_force(t_mesh *m, float k)
492
PDP_POINTER_IN(m->vertices, it, v){
494
/* apply fource vector with step */
495
I3(i) v->c[i] += k * v->n[i];
500
void mesh_compute_center(t_mesh *m, float *c)
508
PDP_POINTER_IN(m->vertices, it, v){
509
I3(k) c[k] += v->c[k];
511
scale = 1.0f / ((float)pdp_list_size(m->vertices));
516
void mesh_translate(t_mesh *m, float *c)
522
PDP_POINTER_IN(m->vertices, it, v){
523
I3(k) v->c[k] += c[k];
527
/* relax a mesh (move toward equal link length) */
528
void mesh_relax(t_mesh *m, float step, float d0, float r0)
532
mesh_compute_center(m, c);
534
mesh_translate(m, c);
536
_mesh_relax_compute_resultant_spring(m, c, d0, r0); /* compute force resultant */
537
_mesh_relax_apply_force(m, step); /* apply "time step towards desired distance" */
538
mesh_calculate_normals(m); /* restore normals */
543
/* print some debug information */
544
void mesh_debug(t_mesh *m)
547
int boundary_edges = 0;
551
post("\tnumber of vertices = %d", pdp_list_size(m->vertices));
552
post("\tnumber of triangles = %d", pdp_list_size(m->triangles));
554
PDP_POINTER_IN(m->triangles, it, t){
555
I3(k) if (!triangle_neighbour(t, t->v[k], t->v[(k+1)%3])) boundary_edges++;
557
post("\tnumber of boundaray edges = %d", boundary_edges);
added
removed
opengl/system/pdp_mesh.c
