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 // Boost pool: Don't use mutexes to synchronize memory allocation.
29 #define BOOST_POOL_NO_MT
30 #include <boost/pool/object_pool.hpp>
31
32 #include "stl.h"
33
reverse_facet(stl_file * stl,int facet_num)34 static void reverse_facet(stl_file *stl, int facet_num)
35 {
36 ++ stl->stats.facets_reversed;
37
38 int neighbor[3] = { stl->neighbors_start[facet_num].neighbor[0], stl->neighbors_start[facet_num].neighbor[1], stl->neighbors_start[facet_num].neighbor[2] };
39 int vnot[3] = { stl->neighbors_start[facet_num].which_vertex_not[0], stl->neighbors_start[facet_num].which_vertex_not[1], stl->neighbors_start[facet_num].which_vertex_not[2] };
40
41 // reverse the facet
42 stl_vertex tmp_vertex = stl->facet_start[facet_num].vertex[0];
43 stl->facet_start[facet_num].vertex[0] = stl->facet_start[facet_num].vertex[1];
44 stl->facet_start[facet_num].vertex[1] = tmp_vertex;
45
46 // fix the vnots of the neighboring facets
47 if (neighbor[0] != -1)
48 stl->neighbors_start[neighbor[0]].which_vertex_not[(vnot[0] + 1) % 3] = (stl->neighbors_start[neighbor[0]].which_vertex_not[(vnot[0] + 1) % 3] + 3) % 6;
49 if (neighbor[1] != -1)
50 stl->neighbors_start[neighbor[1]].which_vertex_not[(vnot[1] + 1) % 3] = (stl->neighbors_start[neighbor[1]].which_vertex_not[(vnot[1] + 1) % 3] + 4) % 6;
51 if (neighbor[2] != -1)
52 stl->neighbors_start[neighbor[2]].which_vertex_not[(vnot[2] + 1) % 3] = (stl->neighbors_start[neighbor[2]].which_vertex_not[(vnot[2] + 1) % 3] + 2) % 6;
53
54 // swap the neighbors of the facet that is being reversed
55 stl->neighbors_start[facet_num].neighbor[1] = neighbor[2];
56 stl->neighbors_start[facet_num].neighbor[2] = neighbor[1];
57
58 // swap the vnots of the facet that is being reversed
59 stl->neighbors_start[facet_num].which_vertex_not[1] = vnot[2];
60 stl->neighbors_start[facet_num].which_vertex_not[2] = vnot[1];
61
62 // reverse the values of the vnots of the facet that is being reversed
63 stl->neighbors_start[facet_num].which_vertex_not[0] = (stl->neighbors_start[facet_num].which_vertex_not[0] + 3) % 6;
64 stl->neighbors_start[facet_num].which_vertex_not[1] = (stl->neighbors_start[facet_num].which_vertex_not[1] + 3) % 6;
65 stl->neighbors_start[facet_num].which_vertex_not[2] = (stl->neighbors_start[facet_num].which_vertex_not[2] + 3) % 6;
66 }
67
68 // Returns true if the normal was flipped.
check_normal_vector(stl_file * stl,int facet_num,int normal_fix_flag)69 static bool check_normal_vector(stl_file *stl, int facet_num, int normal_fix_flag)
70 {
71 stl_facet *facet = &stl->facet_start[facet_num];
72
73 stl_normal normal;
74 stl_calculate_normal(normal, facet);
75 stl_normalize_vector(normal);
76 stl_normal normal_dif = (normal - facet->normal).cwiseAbs();
77
78 const float eps = 0.001f;
79 if (normal_dif(0) < eps && normal_dif(1) < eps && normal_dif(2) < eps) {
80 // Normal is within tolerance. It is not really necessary to change the values here, but just for consistency, I will.
81 facet->normal = normal;
82 return false;
83 }
84
85 stl_normal test_norm = facet->normal;
86 stl_normalize_vector(test_norm);
87 normal_dif = (normal - test_norm).cwiseAbs();
88 if (normal_dif(0) < eps && normal_dif(1) < eps && normal_dif(2) < eps) {
89 // The normal is not within tolerance, but direction is OK.
90 if (normal_fix_flag) {
91 facet->normal = normal;
92 ++ stl->stats.normals_fixed;
93 }
94 return false;
95 }
96
97 test_norm *= -1.f;
98 normal_dif = (normal - test_norm).cwiseAbs();
99 if (normal_dif(0) < eps && normal_dif(1) < eps && normal_dif(2) < eps) {
100 // The normal is not within tolerance and backwards.
101 if (normal_fix_flag) {
102 facet->normal = normal;
103 ++ stl->stats.normals_fixed;
104 }
105 return true;
106 }
107 if (normal_fix_flag) {
108 facet->normal = normal;
109 ++ stl->stats.normals_fixed;
110 }
111 // Status is unknown.
112 return false;
113 }
114
stl_fix_normal_directions(stl_file * stl)115 void stl_fix_normal_directions(stl_file *stl)
116 {
117 // This may happen for malformed models, see: https://github.com/prusa3d/PrusaSlicer/issues/2209
118 if (stl->stats.number_of_facets == 0)
119 return;
120
121 struct stl_normal {
122 int facet_num;
123 stl_normal *next;
124 };
125
126 // Initialize linked list.
127 boost::object_pool<stl_normal> pool;
128 stl_normal *head = pool.construct();
129 stl_normal *tail = pool.construct();
130 head->next = tail;
131 tail->next = tail;
132
133 // Initialize list that keeps track of already fixed facets.
134 std::vector<char> norm_sw(stl->stats.number_of_facets, 0);
135 // Initialize list that keeps track of reversed facets.
136 std::vector<int> reversed_ids;
137 reversed_ids.reserve(stl->stats.number_of_facets);
138
139 int facet_num = 0;
140 // If normal vector is not within tolerance and backwards:
141 // Arbitrarily starts at face 0. If this one is wrong, we're screwed. Thankfully, the chances
142 // of it being wrong randomly are low if most of the triangles are right:
143 if (check_normal_vector(stl, 0, 0)) {
144 reverse_facet(stl, 0);
145 reversed_ids.emplace_back(0);
146 }
147
148 // Say that we've fixed this facet:
149 norm_sw[facet_num] = 1;
150 int checked = 1;
151
152 for (;;) {
153 // Add neighbors_to_list. Add unconnected neighbors to the list.
154 bool force_exit = false;
155 for (int j = 0; j < 3; ++ j) {
156 // Reverse the neighboring facets if necessary.
157 if (stl->neighbors_start[facet_num].which_vertex_not[j] > 2) {
158 // If the facet has a neighbor that is -1, it means that edge isn't shared by another facet
159 if (stl->neighbors_start[facet_num].neighbor[j] != -1) {
160 if (norm_sw[stl->neighbors_start[facet_num].neighbor[j]] == 1) {
161 // trying to modify a facet already marked as fixed, revert all changes made until now and exit (fixes: #716, #574, #413, #269, #262, #259, #230, #228, #206)
162 for (int id = int(reversed_ids.size()) - 1; id >= 0; -- id)
163 reverse_facet(stl, reversed_ids[id]);
164 force_exit = true;
165 break;
166 }
167 reverse_facet(stl, stl->neighbors_start[facet_num].neighbor[j]);
168 reversed_ids.emplace_back(stl->neighbors_start[facet_num].neighbor[j]);
169 }
170 }
171 // If this edge of the facet is connected:
172 if (stl->neighbors_start[facet_num].neighbor[j] != -1) {
173 // If we haven't fixed this facet yet, add it to the list:
174 if (norm_sw[stl->neighbors_start[facet_num].neighbor[j]] != 1) {
175 // Add node to beginning of list.
176 stl_normal *newn = pool.construct();
177 newn->facet_num = stl->neighbors_start[facet_num].neighbor[j];
178 newn->next = head->next;
179 head->next = newn;
180 }
181 }
182 }
183
184 // an error occourred, quit the for loop and exit
185 if (force_exit)
186 break;
187
188 // Get next facet to fix from top of list.
189 if (head->next != tail) {
190 facet_num = head->next->facet_num;
191 assert(facet_num < stl->stats.number_of_facets);
192 if (norm_sw[facet_num] != 1) { // If facet is in list mutiple times
193 norm_sw[facet_num] = 1; // Record this one as being fixed.
194 ++ checked;
195 }
196 stl_normal *temp = head->next; // Delete this facet from the list.
197 head->next = head->next->next;
198 // pool.destroy(temp);
199 } else { // If we ran out of facets to fix: All of the facets in this part have been fixed.
200 ++ stl->stats.number_of_parts;
201 if (checked >= stl->stats.number_of_facets)
202 // All of the facets have been checked. Bail out.
203 break;
204 // There is another part here. Find it and continue.
205 for (uint32_t i = 0; i < stl->stats.number_of_facets; ++ i)
206 if (norm_sw[i] == 0) {
207 // This is the first facet of the next part.
208 facet_num = i;
209 if (check_normal_vector(stl, i, 0)) {
210 reverse_facet(stl, i);
211 reversed_ids.emplace_back(i);
212 }
213 norm_sw[facet_num] = 1;
214 ++ checked;
215 break;
216 }
217 }
218 }
219
220 // pool.destroy(head);
221 // pool.destroy(tail);
222 }
223
stl_fix_normal_values(stl_file * stl)224 void stl_fix_normal_values(stl_file *stl)
225 {
226 for (uint32_t i = 0; i < stl->stats.number_of_facets; ++ i)
227 check_normal_vector(stl, i, 1);
228 }
229
stl_reverse_all_facets(stl_file * stl)230 void stl_reverse_all_facets(stl_file *stl)
231 {
232 stl_normal normal;
233 for (uint32_t i = 0; i < stl->stats.number_of_facets; ++ i) {
234 reverse_facet(stl, i);
235 stl_calculate_normal(normal, &stl->facet_start[i]);
236 stl_normalize_vector(normal);
237 stl->facet_start[i].normal = normal;
238 }
239 }
240