1 /* ADMesh -- process triangulated solid meshes
2 * Copyright (C) 1995, 1996 Anthony D. Martin <amartin@engr.csulb.edu>
3 * Copyright (C) 2013, 2014 several contributors, see AUTHORS
4 *
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.
9
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.
14
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Questions, comments, suggestions, etc to
20 * https://github.com/admesh/admesh/issues
21 */
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <math.h>
27
28 #include "stl.h"
29
30 static void stl_reverse_facet(stl_file *stl, int facet_num);
31 static void stl_reverse_vector(float v[]);
32 int stl_check_normal_vector(stl_file *stl, int facet_num, int normal_fix_flag);
33
34 static void
stl_reverse_facet(stl_file * stl,int facet_num)35 stl_reverse_facet(stl_file *stl, int facet_num) {
36 stl_vertex tmp_vertex;
37 /* int tmp_neighbor;*/
38 int neighbor[3];
39 int vnot[3];
40
41 stl->stats.facets_reversed += 1;
42
43 neighbor[0] = stl->neighbors_start[facet_num].neighbor[0];
44 neighbor[1] = stl->neighbors_start[facet_num].neighbor[1];
45 neighbor[2] = stl->neighbors_start[facet_num].neighbor[2];
46 vnot[0] = stl->neighbors_start[facet_num].which_vertex_not[0];
47 vnot[1] = stl->neighbors_start[facet_num].which_vertex_not[1];
48 vnot[2] = stl->neighbors_start[facet_num].which_vertex_not[2];
49
50 /* reverse the facet */
51 tmp_vertex = stl->facet_start[facet_num].vertex[0];
52 stl->facet_start[facet_num].vertex[0] =
53 stl->facet_start[facet_num].vertex[1];
54 stl->facet_start[facet_num].vertex[1] = tmp_vertex;
55
56 /* fix the vnots of the neighboring facets */
57 if(neighbor[0] != -1)
58 stl->neighbors_start[neighbor[0]].which_vertex_not[(vnot[0] + 1) % 3] =
59 (stl->neighbors_start[neighbor[0]].
60 which_vertex_not[(vnot[0] + 1) % 3] + 3) % 6;
61 if(neighbor[1] != -1)
62 stl->neighbors_start[neighbor[1]].which_vertex_not[(vnot[1] + 1) % 3] =
63 (stl->neighbors_start[neighbor[1]].
64 which_vertex_not[(vnot[1] + 1) % 3] + 4) % 6;
65 if(neighbor[2] != -1)
66 stl->neighbors_start[neighbor[2]].which_vertex_not[(vnot[2] + 1) % 3] =
67 (stl->neighbors_start[neighbor[2]].
68 which_vertex_not[(vnot[2] + 1) % 3] + 2) % 6;
69
70 /* swap the neighbors of the facet that is being reversed */
71 stl->neighbors_start[facet_num].neighbor[1] = neighbor[2];
72 stl->neighbors_start[facet_num].neighbor[2] = neighbor[1];
73
74 /* swap the vnots of the facet that is being reversed */
75 stl->neighbors_start[facet_num].which_vertex_not[1] = vnot[2];
76 stl->neighbors_start[facet_num].which_vertex_not[2] = vnot[1];
77
78 /* reverse the values of the vnots of the facet that is being reversed */
79 stl->neighbors_start[facet_num].which_vertex_not[0] =
80 (stl->neighbors_start[facet_num].which_vertex_not[0] + 3) % 6;
81 stl->neighbors_start[facet_num].which_vertex_not[1] =
82 (stl->neighbors_start[facet_num].which_vertex_not[1] + 3) % 6;
83 stl->neighbors_start[facet_num].which_vertex_not[2] =
84 (stl->neighbors_start[facet_num].which_vertex_not[2] + 3) % 6;
85 }
86
87 void
stl_fix_normal_directions(stl_file * stl)88 stl_fix_normal_directions(stl_file *stl) {
89 char *norm_sw;
90 /* int edge_num;*/
91 /* int vnot;*/
92 int checked = 0;
93 int facet_num;
94 /* int next_facet;*/
95 int i;
96 int j;
97 struct stl_normal {
98 int facet_num;
99 struct stl_normal *next;
100 };
101 struct stl_normal *head;
102 struct stl_normal *tail;
103 struct stl_normal *newn;
104 struct stl_normal *temp;
105
106 if (stl->error) return;
107
108 /* Initialize linked list. */
109 head = (struct stl_normal*)malloc(sizeof(struct stl_normal));
110 if(head == NULL) perror("stl_fix_normal_directions");
111 tail = (struct stl_normal*)malloc(sizeof(struct stl_normal));
112 if(tail == NULL) perror("stl_fix_normal_directions");
113 head->next = tail;
114 tail->next = tail;
115
116 /* Initialize list that keeps track of already fixed facets. */
117 norm_sw = (char*)calloc(stl->stats.number_of_facets, sizeof(char));
118 if(norm_sw == NULL) perror("stl_fix_normal_directions");
119
120
121 facet_num = 0;
122 /* If normal vector is not within tolerance and backwards:
123 Arbitrarily starts at face 0. If this one is wrong, we're screwed. Thankfully, the chances
124 of it being wrong randomly are low if most of the triangles are right: */
125 if(stl_check_normal_vector(stl, 0, 0) == 2)
126 stl_reverse_facet(stl, 0);
127
128 /* Say that we've fixed this facet: */
129 norm_sw[facet_num] = 1;
130 checked++;
131
132 for(;;) {
133 /* Add neighbors_to_list.
134 Add unconnected neighbors to the list:a */
135 for(j = 0; j < 3; j++) {
136 /* Reverse the neighboring facets if necessary. */
137 if(stl->neighbors_start[facet_num].which_vertex_not[j] > 2) {
138 /* If the facet has a neighbor that is -1, it means that edge isn't shared by another facet */
139 if(stl->neighbors_start[facet_num].neighbor[j] != -1) {
140 stl_reverse_facet
141 (stl, stl->neighbors_start[facet_num].neighbor[j]);
142 }
143 }
144 /* If this edge of the facet is connected: */
145 if(stl->neighbors_start[facet_num].neighbor[j] != -1) {
146 /* If we haven't fixed this facet yet, add it to the list: */
147 if(norm_sw[stl->neighbors_start[facet_num].neighbor[j]] != 1) {
148 /* Add node to beginning of list. */
149 newn = (struct stl_normal*)malloc(sizeof(struct stl_normal));
150 if(newn == NULL) perror("stl_fix_normal_directions");
151 newn->facet_num = stl->neighbors_start[facet_num].neighbor[j];
152 newn->next = head->next;
153 head->next = newn;
154 }
155 }
156 }
157 /* Get next facet to fix from top of list. */
158 if(head->next != tail) {
159 facet_num = head->next->facet_num;
160 if(norm_sw[facet_num] != 1) { /* If facet is in list mutiple times */
161 norm_sw[facet_num] = 1; /* Record this one as being fixed. */
162 checked++;
163 }
164 temp = head->next; /* Delete this facet from the list. */
165 head->next = head->next->next;
166 free(temp);
167 } else { /* if we ran out of facets to fix: */
168 /* All of the facets in this part have been fixed. */
169 stl->stats.number_of_parts += 1;
170 if(checked >= stl->stats.number_of_facets) {
171 /* All of the facets have been checked. Bail out. */
172 break;
173 } else {
174 /* There is another part here. Find it and continue. */
175 for(i = 0; i < stl->stats.number_of_facets; i++) {
176 if(norm_sw[i] == 0) {
177 /* This is the first facet of the next part. */
178 facet_num = i;
179 if(stl_check_normal_vector(stl, i, 0) == 2) {
180 stl_reverse_facet(stl, i);
181 }
182
183 norm_sw[facet_num] = 1;
184 checked++;
185 break;
186 }
187 }
188 }
189 }
190 }
191 free(head);
192 free(tail);
193 free(norm_sw);
194 }
195
196 int
stl_check_normal_vector(stl_file * stl,int facet_num,int normal_fix_flag)197 stl_check_normal_vector(stl_file *stl, int facet_num, int normal_fix_flag) {
198 /* Returns 0 if the normal is within tolerance */
199 /* Returns 1 if the normal is not within tolerance, but direction is OK */
200 /* Returns 2 if the normal is not within tolerance and backwards */
201 /* Returns 4 if the status is unknown. */
202
203 float normal[3];
204 float test_norm[3];
205 stl_facet *facet;
206
207 facet = &stl->facet_start[facet_num];
208
209 stl_calculate_normal(normal, facet);
210 stl_normalize_vector(normal);
211
212 if( (ABS(normal[0] - facet->normal.x) < 0.001)
213 && (ABS(normal[1] - facet->normal.y) < 0.001)
214 && (ABS(normal[2] - facet->normal.z) < 0.001)) {
215 /* It is not really necessary to change the values here */
216 /* but just for consistency, I will. */
217 facet->normal.x = normal[0];
218 facet->normal.y = normal[1];
219 facet->normal.z = normal[2];
220 return 0;
221 }
222
223 test_norm[0] = facet->normal.x;
224 test_norm[1] = facet->normal.y;
225 test_norm[2] = facet->normal.z;
226
227 stl_normalize_vector(test_norm);
228 if( (ABS(normal[0] - test_norm[0]) < 0.001)
229 && (ABS(normal[1] - test_norm[1]) < 0.001)
230 && (ABS(normal[2] - test_norm[2]) < 0.001)) {
231 if(normal_fix_flag) {
232 facet->normal.x = normal[0];
233 facet->normal.y = normal[1];
234 facet->normal.z = normal[2];
235 stl->stats.normals_fixed += 1;
236 }
237 return 1;
238 }
239
240 stl_reverse_vector(test_norm);
241 if( (ABS(normal[0] - test_norm[0]) < 0.001)
242 && (ABS(normal[1] - test_norm[1]) < 0.001)
243 && (ABS(normal[2] - test_norm[2]) < 0.001)) {
244 /* Facet is backwards. */
245 if(normal_fix_flag) {
246 facet->normal.x = normal[0];
247 facet->normal.y = normal[1];
248 facet->normal.z = normal[2];
249 stl->stats.normals_fixed += 1;
250 }
251 return 2;
252 }
253 if(normal_fix_flag) {
254 facet->normal.x = normal[0];
255 facet->normal.y = normal[1];
256 facet->normal.z = normal[2];
257 stl->stats.normals_fixed += 1;
258 }
259 return 4;
260 }
261
262 static void
stl_reverse_vector(float v[])263 stl_reverse_vector(float v[]) {
264 v[0] *= -1;
265 v[1] *= -1;
266 v[2] *= -1;
267 }
268
269
270 void
stl_calculate_normal(float normal[],stl_facet * facet)271 stl_calculate_normal(float normal[], stl_facet *facet) {
272 float v1[3];
273 float v2[3];
274
275 v1[0] = facet->vertex[1].x - facet->vertex[0].x;
276 v1[1] = facet->vertex[1].y - facet->vertex[0].y;
277 v1[2] = facet->vertex[1].z - facet->vertex[0].z;
278 v2[0] = facet->vertex[2].x - facet->vertex[0].x;
279 v2[1] = facet->vertex[2].y - facet->vertex[0].y;
280 v2[2] = facet->vertex[2].z - facet->vertex[0].z;
281
282 normal[0] = (float)((double)v1[1] * (double)v2[2]) - ((double)v1[2] * (double)v2[1]);
283 normal[1] = (float)((double)v1[2] * (double)v2[0]) - ((double)v1[0] * (double)v2[2]);
284 normal[2] = (float)((double)v1[0] * (double)v2[1]) - ((double)v1[1] * (double)v2[0]);
285 }
286
stl_normalize_vector(float v[])287 void stl_normalize_vector(float v[]) {
288 double length;
289 double factor;
290 float min_normal_length;
291
292 length = sqrt((double)v[0] * (double)v[0] + (double)v[1] * (double)v[1] + (double)v[2] * (double)v[2]);
293 min_normal_length = 0.000000000001;
294 if(length < min_normal_length) {
295 v[0] = 0.0;
296 v[1] = 0.0;
297 v[2] = 0.0;
298 return;
299 }
300 factor = 1.0 / length;
301 v[0] *= factor;
302 v[1] *= factor;
303 v[2] *= factor;
304 }
305
306 void
stl_fix_normal_values(stl_file * stl)307 stl_fix_normal_values(stl_file *stl) {
308 int i;
309
310 if (stl->error) return;
311
312 for(i = 0; i < stl->stats.number_of_facets; i++) {
313 stl_check_normal_vector(stl, i, 1);
314 }
315 }
316
317 void
stl_reverse_all_facets(stl_file * stl)318 stl_reverse_all_facets(stl_file *stl) {
319 int i;
320 float normal[3];
321
322 if (stl->error) return;
323
324 for(i = 0; i < stl->stats.number_of_facets; i++) {
325 stl_reverse_facet(stl, i);
326 stl_calculate_normal(normal, &stl->facet_start[i]);
327 stl_normalize_vector(normal);
328 stl->facet_start[i].normal.x = normal[0];
329 stl->facet_start[i].normal.y = normal[1];
330 stl->facet_start[i].normal.z = normal[2];
331 }
332 }
333
334