← Back to branch summary

~ubuntu-branches/ubuntu/utopic/slic3r/utopic

« back to all changes in this revision

Viewing changes to xs/src/admesh/util.c

  • Committer: Package Import Robot
  • Author(s): Chow Loong Jin
  • Date: 2014-06-17 01:27:26 UTC
  • Revision ID: package-import@ubuntu.com-20140617012726-2wrs4zdo251nr4vg
Tags: upstream-1.1.4+dfsg
Import upstream version 1.1.4+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
xs/src/admesh/util.c
 
1
/*  ADMesh -- process triangulated solid meshes
 
2
 *  Copyright (C) 1995, 1996  Anthony D. Martin
 
3
 *
 
4
 *  This program is free software; you can redistribute it and/or modify
 
5
 *  it under the terms of the GNU General Public License as published by
 
6
 *  the Free Software Foundation; either version 2, or (at your option)
 
7
 *  any later version.
 
8
 *
 
9
 *  This program 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
 
12
 *  GNU General Public License for more details.
 
13
 *
 
14
 *  You should have received a copy of the GNU General Public License
 
15
 *  along with this program; if not, write to the Free Software
 
16
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 
17
 *  
 
18
 *  Questions, comments, suggestions, etc to <amartin@engr.csulb.edu>
 
19
 */
 
20
 
 
21
#include <stdio.h>
 
22
#include <stdlib.h>
 
23
#include <string.h>
 
24
#include <math.h>
 
25
 
 
26
#include "stl.h"
 
27
 
 
28
static void stl_rotate(float *x, float *y, float angle);
 
29
static float get_area(stl_facet *facet);
 
30
static float get_volume(stl_file *stl);
 
31
 
 
32
 
 
33
void
 
34
stl_verify_neighbors(stl_file *stl)
 
35
{
 
36
  int i;
 
37
  int j;
 
38
  stl_edge edge_a;
 
39
  stl_edge edge_b;
 
40
  int neighbor;
 
41
  int vnot;
 
42
 
 
43
  stl->stats.backwards_edges = 0;
 
44
 
 
45
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
46
    {
 
47
      for(j = 0; j < 3; j++)
 
48
        {
 
49
          edge_a.p1 = stl->facet_start[i].vertex[j];
 
50
          edge_a.p2 = stl->facet_start[i].vertex[(j + 1) % 3];
 
51
          neighbor = stl->neighbors_start[i].neighbor[j];
 
52
          vnot = stl->neighbors_start[i].which_vertex_not[j];
 
53
          
 
54
          if(neighbor == -1)
 
55
            continue;           /* this edge has no neighbor... Continue. */
 
56
          if(vnot < 3)
 
57
            {
 
58
              edge_b.p1 = stl->facet_start[neighbor].vertex[(vnot + 2) % 3];
 
59
              edge_b.p2 = stl->facet_start[neighbor].vertex[(vnot + 1) % 3];
 
60
            }
 
61
          else
 
62
            {
 
63
              stl->stats.backwards_edges += 1;
 
64
              edge_b.p1 = stl->facet_start[neighbor].vertex[(vnot + 1) % 3];
 
65
              edge_b.p2 = stl->facet_start[neighbor].vertex[(vnot + 2) % 3];
 
66
            }
 
67
          if(memcmp(&edge_a, &edge_b, SIZEOF_EDGE_SORT) != 0)
 
68
            {
 
69
              /* These edges should match but they don't.  Print results. */
 
70
              printf("edge %d of facet %d doesn't match edge %d of facet %d\n",
 
71
                     j, i, vnot + 1, neighbor);
 
72
              stl_write_facet(stl, (char*)"first facet", i);
 
73
              stl_write_facet(stl, (char*)"second facet", neighbor);
 
74
            }
 
75
        }
 
76
    }
 
77
}
 
78
 
 
79
void
 
80
stl_translate_relative(stl_file *stl, float x, float y, float z)
 
81
{
 
82
  int i;
 
83
  int j;
 
84
  
 
85
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
86
    {
 
87
      for(j = 0; j < 3; j++)
 
88
        {
 
89
          stl->facet_start[i].vertex[j].x += x;
 
90
          stl->facet_start[i].vertex[j].y += y;
 
91
          stl->facet_start[i].vertex[j].z += z;
 
92
        }
 
93
    }
 
94
  stl->stats.min.x += x;
 
95
  stl->stats.min.y += y;
 
96
  stl->stats.min.z += z;
 
97
  stl->stats.max.x += x;
 
98
  stl->stats.max.y += y;
 
99
  stl->stats.max.z += z;
 
100
  
 
101
  stl_invalidate_shared_vertices(stl);
 
102
}
 
103
 
 
104
void
 
105
stl_scale_versor(stl_file *stl, float versor[3])
 
106
{
 
107
  int i;
 
108
  int j;
 
109
  
 
110
  // scale extents
 
111
  stl->stats.min.x *= versor[0];
 
112
  stl->stats.min.y *= versor[1];
 
113
  stl->stats.min.z *= versor[2];
 
114
  stl->stats.max.x *= versor[0];
 
115
  stl->stats.max.y *= versor[1];
 
116
  stl->stats.max.z *= versor[2];
 
117
  
 
118
  // scale size
 
119
  stl->stats.size.x *= versor[0];
 
120
  stl->stats.size.y *= versor[1];
 
121
  stl->stats.size.z *= versor[2];
 
122
  
 
123
  // scale volume
 
124
  if (stl->stats.volume > 0.0) {
 
125
    stl->stats.volume *= (versor[0] * versor[1] * versor[2]);
 
126
  }
 
127
  
 
128
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
129
    {
 
130
      for(j = 0; j < 3; j++)
 
131
        {
 
132
          stl->facet_start[i].vertex[j].x *= versor[0];
 
133
          stl->facet_start[i].vertex[j].y *= versor[1];
 
134
          stl->facet_start[i].vertex[j].z *= versor[2];
 
135
        }
 
136
    }
 
137
   
 
138
   stl_invalidate_shared_vertices(stl);
 
139
}
 
140
 
 
141
void
 
142
stl_scale(stl_file *stl, float factor)
 
143
{
 
144
    float versor[3];
 
145
    versor[0] = factor;
 
146
    versor[1] = factor;
 
147
    versor[2] = factor;
 
148
    stl_scale_versor(stl, versor);
 
149
}
 
150
 
 
151
static void calculate_normals(stl_file *stl)
 
152
{
 
153
        long i;
 
154
        float normal[3];
 
155
        
 
156
        for(i = 0; i < stl->stats.number_of_facets; i++){
 
157
                stl_calculate_normal(normal, &stl->facet_start[i]);
 
158
                stl_normalize_vector(normal);
 
159
                stl->facet_start[i].normal.x = normal[0];
 
160
                stl->facet_start[i].normal.y = normal[1];
 
161
                stl->facet_start[i].normal.z = normal[2];
 
162
        }
 
163
}
 
164
 
 
165
void
 
166
stl_rotate_x(stl_file *stl, float angle)
 
167
{
 
168
  int i;
 
169
  int j;
 
170
  
 
171
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
172
    {
 
173
      for(j = 0; j < 3; j++)
 
174
        {
 
175
          stl_rotate(&stl->facet_start[i].vertex[j].y,
 
176
                     &stl->facet_start[i].vertex[j].z, angle);
 
177
        }
 
178
    }
 
179
  stl_get_size(stl);
 
180
        calculate_normals(stl);
 
181
}
 
182
 
 
183
void
 
184
stl_rotate_y(stl_file *stl, float angle)
 
185
{
 
186
  int i;
 
187
  int j;
 
188
  
 
189
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
190
    {
 
191
      for(j = 0; j < 3; j++)
 
192
        {
 
193
          stl_rotate(&stl->facet_start[i].vertex[j].z,
 
194
                     &stl->facet_start[i].vertex[j].x, angle);
 
195
        }
 
196
    }
 
197
  stl_get_size(stl);
 
198
        calculate_normals(stl);
 
199
}
 
200
 
 
201
void
 
202
stl_rotate_z(stl_file *stl, float angle)
 
203
{
 
204
  int i;
 
205
  int j;
 
206
  
 
207
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
208
    {
 
209
      for(j = 0; j < 3; j++)
 
210
        {
 
211
          stl_rotate(&stl->facet_start[i].vertex[j].x,
 
212
                     &stl->facet_start[i].vertex[j].y, angle);
 
213
        }
 
214
    }
 
215
  stl_get_size(stl);
 
216
        calculate_normals(stl);
 
217
}
 
218
 
 
219
                
 
220
 
 
221
static void
 
222
stl_rotate(float *x, float *y, float angle)
 
223
{
 
224
  double r;
 
225
  double theta;
 
226
  double radian_angle;
 
227
  
 
228
  radian_angle = (angle / 180.0) * M_PI;
 
229
  
 
230
  r = sqrt((*x * *x) + (*y * *y));
 
231
  theta = atan2(*y, *x);
 
232
  *x = r * cos(theta + radian_angle);
 
233
  *y = r * sin(theta + radian_angle);
 
234
}
 
235
 
 
236
extern void
 
237
stl_get_size(stl_file *stl)
 
238
{
 
239
    if (stl->stats.number_of_facets == 0) return;
 
240
    
 
241
  int i;
 
242
  int j;
 
243
 
 
244
  stl->stats.min.x = stl->facet_start[0].vertex[0].x;
 
245
  stl->stats.min.y = stl->facet_start[0].vertex[0].y;
 
246
  stl->stats.min.z = stl->facet_start[0].vertex[0].z;
 
247
  stl->stats.max.x = stl->facet_start[0].vertex[0].x;
 
248
  stl->stats.max.y = stl->facet_start[0].vertex[0].y;
 
249
  stl->stats.max.z = stl->facet_start[0].vertex[0].z;
 
250
  
 
251
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
252
    {
 
253
      for(j = 0; j < 3; j++)
 
254
        {
 
255
          stl->stats.min.x = STL_MIN(stl->stats.min.x,
 
256
                                     stl->facet_start[i].vertex[j].x);
 
257
          stl->stats.min.y = STL_MIN(stl->stats.min.y,
 
258
                                     stl->facet_start[i].vertex[j].y);
 
259
          stl->stats.min.z = STL_MIN(stl->stats.min.z,
 
260
                                     stl->facet_start[i].vertex[j].z);
 
261
          stl->stats.max.x = STL_MAX(stl->stats.max.x,
 
262
                                     stl->facet_start[i].vertex[j].x);
 
263
          stl->stats.max.y = STL_MAX(stl->stats.max.y,
 
264
                                     stl->facet_start[i].vertex[j].y);
 
265
          stl->stats.max.z = STL_MAX(stl->stats.max.z,
 
266
                                     stl->facet_start[i].vertex[j].z);
 
267
        }
 
268
    }
 
269
    stl->stats.size.x = stl->stats.max.x - stl->stats.min.x;
 
270
    stl->stats.size.y = stl->stats.max.y - stl->stats.min.y;
 
271
    stl->stats.size.z = stl->stats.max.z - stl->stats.min.z;
 
272
    stl->stats.bounding_diameter = sqrt(
 
273
        stl->stats.size.x * stl->stats.size.x +
 
274
        stl->stats.size.y * stl->stats.size.y +
 
275
        stl->stats.size.z * stl->stats.size.z
 
276
        );
 
277
}
 
278
 
 
279
void
 
280
stl_mirror_xy(stl_file *stl)
 
281
{
 
282
  int i;
 
283
  int j;
 
284
  float temp_size;
 
285
  
 
286
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
287
    {
 
288
      for(j = 0; j < 3; j++)
 
289
        {
 
290
          stl->facet_start[i].vertex[j].z *= -1.0;
 
291
        }
 
292
    }
 
293
  temp_size = stl->stats.min.z;
 
294
  stl->stats.min.z = stl->stats.max.z;
 
295
  stl->stats.max.z = temp_size;
 
296
  stl->stats.min.z *= -1.0;
 
297
  stl->stats.max.z *= -1.0;
 
298
}
 
299
 
 
300
void
 
301
stl_mirror_yz(stl_file *stl)
 
302
{
 
303
  int i;
 
304
  int j;
 
305
  float temp_size;
 
306
  
 
307
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
308
    {
 
309
      for(j = 0; j < 3; j++)
 
310
        {
 
311
          stl->facet_start[i].vertex[j].x *= -1.0;
 
312
        }
 
313
    }
 
314
  temp_size = stl->stats.min.x;
 
315
  stl->stats.min.x = stl->stats.max.x;
 
316
  stl->stats.max.x = temp_size;
 
317
  stl->stats.min.x *= -1.0;
 
318
  stl->stats.max.x *= -1.0;
 
319
}
 
320
 
 
321
void
 
322
stl_mirror_xz(stl_file *stl)
 
323
{
 
324
  int i;
 
325
  int j;
 
326
  float temp_size;
 
327
  
 
328
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
329
    {
 
330
      for(j = 0; j < 3; j++)
 
331
        {
 
332
          stl->facet_start[i].vertex[j].y *= -1.0;
 
333
        }
 
334
    }
 
335
  temp_size = stl->stats.min.y;
 
336
  stl->stats.min.y = stl->stats.max.y;
 
337
  stl->stats.max.y = temp_size;
 
338
  stl->stats.min.y *= -1.0;
 
339
  stl->stats.max.y *= -1.0;
 
340
}
 
341
 
 
342
static float get_volume(stl_file *stl)
 
343
{
 
344
        long i;
 
345
        stl_vertex p0;
 
346
        stl_vertex p;
 
347
        stl_normal n;
 
348
        float height;
 
349
        float area;
 
350
        float volume = 0.0;
 
351
        
 
352
        /* Choose a point, any point as the reference */
 
353
        p0.x = stl->facet_start[0].vertex[0].x;
 
354
        p0.y = stl->facet_start[0].vertex[0].y;
 
355
        p0.z = stl->facet_start[0].vertex[0].z;
 
356
 
 
357
        for(i = 0; i < stl->stats.number_of_facets; i++){
 
358
                p.x = stl->facet_start[i].vertex[0].x - p0.x;
 
359
                p.y = stl->facet_start[i].vertex[0].y - p0.y;
 
360
                p.z = stl->facet_start[i].vertex[0].z - p0.z;
 
361
                /* Do dot product to get distance from point to plane */
 
362
                n = stl->facet_start[i].normal;
 
363
                height = (n.x * p.x) + (n.y * p.y) + (n.z * p.z);
 
364
                area = get_area(&stl->facet_start[i]);
 
365
                volume += (area * height) / 3.0;
 
366
        }
 
367
        return volume;
 
368
}
 
369
 
 
370
void stl_calculate_volume(stl_file *stl)
 
371
{
 
372
        stl->stats.volume = get_volume(stl);
 
373
        if(stl->stats.volume < 0.0){
 
374
                stl_reverse_all_facets(stl);
 
375
                stl->stats.volume = -stl->stats.volume;
 
376
        }
 
377
}
 
378
 
 
379
static float get_area(stl_facet *facet)
 
380
{
 
381
        double cross[3][3];
 
382
        float sum[3];
 
383
        float n[3];
 
384
        float area;
 
385
        int i;
 
386
        
 
387
        // cast to double before calculating cross product because large coordinates
 
388
        // can result in overflowing product
 
389
        // (bad area is responsible for bad volume and bad facets reversal)
 
390
        for(i = 0; i < 3; i++){
 
391
            cross[i][0]=(((double)facet->vertex[i].y * (double)facet->vertex[(i + 1) % 3].z) -
 
392
                         ((double)facet->vertex[i].z * (double)facet->vertex[(i + 1) % 3].y));
 
393
            cross[i][1]=(((double)facet->vertex[i].z * (double)facet->vertex[(i + 1) % 3].x) -
 
394
                         ((double)facet->vertex[i].x * (double)facet->vertex[(i + 1) % 3].z));
 
395
            cross[i][2]=(((double)facet->vertex[i].x * (double)facet->vertex[(i + 1) % 3].y) -
 
396
                         ((double)facet->vertex[i].y * (double)facet->vertex[(i + 1) % 3].x));
 
397
        }
 
398
        
 
399
        sum[0] = cross[0][0] + cross[1][0] + cross[2][0];
 
400
        sum[1] = cross[0][1] + cross[1][1] + cross[2][1];
 
401
        sum[2] = cross[0][2] + cross[1][2] + cross[2][2];
 
402
 
 
403
        /* This should already be done.  But just in case, let's do it again */
 
404
        stl_calculate_normal(n, facet);
 
405
        stl_normalize_vector(n);
 
406
 
 
407
        area = 0.5 * (n[0] * sum[0] + n[1] * sum[1] + n[2] * sum[2]);
 
408
        return area;
 
409
}