1
/* ADMesh -- process triangulated solid meshes
2
* Copyright (C) 1995 Anthony D. Martin
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)
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.
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.
18
* Questions, comments, suggestions, etc to <amartin@engr.csulb.edu>
29
static void stl_match_neighbors_exact(stl_file *stl,
30
stl_hash_edge *edge_a, stl_hash_edge *edge_b);
31
static void stl_match_neighbors_nearby(stl_file *stl,
32
stl_hash_edge *edge_a, stl_hash_edge *edge_b);
33
static void stl_record_neighbors(stl_file *stl,
34
stl_hash_edge *edge_a, stl_hash_edge *edge_b);
35
static void stl_initialize_facet_check_exact(stl_file *stl);
36
static void stl_initialize_facet_check_nearby(stl_file *stl);
37
static void stl_load_edge_exact(stl_file *stl, stl_hash_edge *edge,
38
stl_vertex *a, stl_vertex *b);
39
static int stl_load_edge_nearby(stl_file *stl, stl_hash_edge *edge,
40
stl_vertex *a, stl_vertex *b, float tolerance);
41
static void insert_hash_edge(stl_file *stl, stl_hash_edge edge,
42
void (*match_neighbors)(stl_file *stl,
43
stl_hash_edge *edge_a, stl_hash_edge *edge_b));
44
static int stl_get_hash_for_edge(int M, stl_hash_edge *edge);
45
static int stl_compare_function(stl_hash_edge *edge_a, stl_hash_edge *edge_b);
46
static void stl_free_edges(stl_file *stl);
47
static void stl_remove_facet(stl_file *stl, int facet_number);
48
static void stl_change_vertices(stl_file *stl, int facet_num, int vnot,
49
stl_vertex new_vertex);
50
static void stl_which_vertices_to_change(stl_file *stl, stl_hash_edge *edge_a,
51
stl_hash_edge *edge_b, int *facet1, int *vertex1,
52
int *facet2, int *vertex2,
53
stl_vertex *new_vertex1, stl_vertex *new_vertex2);
54
static void stl_remove_degenerate(stl_file *stl, int facet);
55
extern int stl_check_normal_vector(stl_file *stl,
56
int facet_num, int normal_fix_flag);
57
static void stl_update_connects_remove_1(stl_file *stl, int facet_num);
61
stl_check_facets_exact(stl_file *stl)
63
/* This function builds the neighbors list. No modifications are made
64
* to any of the facets. The edges are said to match only if all six
65
* floats of the first edge matches all six floats of the second edge.
73
stl->stats.connected_edges = 0;
74
stl->stats.connected_facets_1_edge = 0;
75
stl->stats.connected_facets_2_edge = 0;
76
stl->stats.connected_facets_3_edge = 0;
78
stl_initialize_facet_check_exact(stl);
80
for(i = 0; i < stl->stats.number_of_facets; i++)
82
facet = stl->facet_start[i];
84
//If any two of the three vertices are found to be exactally the same, call them degenerate and remove the facet.
85
if( !memcmp(&facet.vertex[0], &facet.vertex[1],
87
|| !memcmp(&facet.vertex[1], &facet.vertex[2],
89
|| !memcmp(&facet.vertex[0], &facet.vertex[2],
92
stl->stats.degenerate_facets += 1;
93
stl_remove_facet(stl, i);
98
for(j = 0; j < 3; j++)
100
edge.facet_number = i;
102
stl_load_edge_exact(stl, &edge, &facet.vertex[j],
103
&facet.vertex[(j + 1) % 3]);
105
insert_hash_edge(stl, edge, stl_match_neighbors_exact);
112
stl_load_edge_exact(stl_file *stl, stl_hash_edge *edge,
113
stl_vertex *a, stl_vertex *b)
122
diff_x = ABS(a->x - b->x);
123
diff_y = ABS(a->y - b->y);
124
diff_z = ABS(a->z - b->z);
125
max_diff = STL_MAX(diff_x, diff_y);
126
max_diff = STL_MAX(diff_z, max_diff);
127
stl->stats.shortest_edge = STL_MIN(max_diff, stl->stats.shortest_edge);
129
if(diff_x == max_diff)
133
memcpy(&edge->key[0], a, sizeof(stl_vertex));
134
memcpy(&edge->key[3], b, sizeof(stl_vertex));
138
memcpy(&edge->key[0], b, sizeof(stl_vertex));
139
memcpy(&edge->key[3], a, sizeof(stl_vertex));
140
edge->which_edge += 3; /* this edge is loaded backwards */
143
else if(diff_y == max_diff)
147
memcpy(&edge->key[0], a, sizeof(stl_vertex));
148
memcpy(&edge->key[3], b, sizeof(stl_vertex));
152
memcpy(&edge->key[0], b, sizeof(stl_vertex));
153
memcpy(&edge->key[3], a, sizeof(stl_vertex));
154
edge->which_edge += 3; /* this edge is loaded backwards */
161
memcpy(&edge->key[0], a, sizeof(stl_vertex));
162
memcpy(&edge->key[3], b, sizeof(stl_vertex));
166
memcpy(&edge->key[0], b, sizeof(stl_vertex));
167
memcpy(&edge->key[3], a, sizeof(stl_vertex));
168
edge->which_edge += 3; /* this edge is loaded backwards */
174
stl_initialize_facet_check_exact(stl_file *stl)
178
stl->stats.malloced = 0;
179
stl->stats.freed = 0;
180
stl->stats.collisions = 0;
185
for(i = 0; i < stl->stats.number_of_facets ; i++)
187
/* initialize neighbors list to -1 to mark unconnected edges */
188
stl->neighbors_start[i].neighbor[0] = -1;
189
stl->neighbors_start[i].neighbor[1] = -1;
190
stl->neighbors_start[i].neighbor[2] = -1;
193
stl->heads = (stl_hash_edge**)calloc(stl->M, sizeof(*stl->heads));
194
if(stl->heads == NULL) perror("stl_initialize_facet_check_exact");
196
stl->tail = (stl_hash_edge*)malloc(sizeof(stl_hash_edge));
197
if(stl->tail == NULL) perror("stl_initialize_facet_check_exact");
199
stl->tail->next = stl->tail;
201
for(i = 0; i < stl->M; i++)
203
stl->heads[i] = stl->tail;
208
insert_hash_edge(stl_file *stl, stl_hash_edge edge,
209
void (*match_neighbors)(stl_file *stl,
210
stl_hash_edge *edge_a, stl_hash_edge *edge_b))
213
stl_hash_edge *new_edge;
217
chain_number = stl_get_hash_for_edge(stl->M, &edge);
219
link = stl->heads[chain_number];
221
if(link == stl->tail)
223
/* This list doesn't have any edges currently in it. Add this one. */
224
new_edge = (stl_hash_edge*)malloc(sizeof(stl_hash_edge));
225
if(new_edge == NULL) perror("insert_hash_edge");
226
stl->stats.malloced++;
228
new_edge->next = stl->tail;
229
stl->heads[chain_number] = new_edge;
232
else if(!stl_compare_function(&edge, link))
234
/* This is a match. Record result in neighbors list. */
235
match_neighbors(stl, &edge, link);
236
/* Delete the matched edge from the list. */
237
stl->heads[chain_number] = link->next;
243
{ /* Continue through the rest of the list */
246
if(link->next == stl->tail)
248
/* This is the last item in the list. Insert a new edge. */
249
new_edge = (stl_hash_edge*)malloc(sizeof(stl_hash_edge));
250
if(new_edge == NULL) perror("insert_hash_edge");
251
stl->stats.malloced++;
253
new_edge->next = stl->tail;
254
link->next = new_edge;
255
stl->stats.collisions++;
258
else if(!stl_compare_function(&edge, link->next))
260
/* This is a match. Record result in neighbors list. */
261
match_neighbors(stl, &edge, link->next);
263
/* Delete the matched edge from the list. */
265
link->next = link->next->next;
272
/* This is not a match. Go to the next link */
274
stl->stats.collisions++;
282
stl_get_hash_for_edge(int M, stl_hash_edge *edge)
284
return ((edge->key[0] / 23 + edge->key[1] / 19 + edge->key[2] / 17
285
+ edge->key[3] /13 + edge->key[4] / 11 + edge->key[5] / 7 ) % M);
289
stl_compare_function(stl_hash_edge *edge_a, stl_hash_edge *edge_b)
291
if(edge_a->facet_number == edge_b->facet_number)
293
return 1; /* Don't match edges of the same facet */
297
return memcmp(edge_a, edge_b, SIZEOF_EDGE_SORT);
302
stl_check_facets_nearby(stl_file *stl, float tolerance)
304
stl_hash_edge edge[3];
310
if( (stl->stats.connected_facets_1_edge == stl->stats.number_of_facets)
311
&& (stl->stats.connected_facets_2_edge == stl->stats.number_of_facets)
312
&& (stl->stats.connected_facets_3_edge == stl->stats.number_of_facets))
314
/* No need to check any further. All facets are connected */
318
stl_initialize_facet_check_nearby(stl);
320
for(i = 0; i < stl->stats.number_of_facets; i++)
322
facet = stl->facet_start[i];
323
for(j = 0; j < 3; j++)
325
if(stl->neighbors_start[i].neighbor[j] == -1)
327
edge[j].facet_number = i;
328
edge[j].which_edge = j;
329
if(stl_load_edge_nearby(stl, &edge[j], &facet.vertex[j],
330
&facet.vertex[(j + 1) % 3],
333
/* only insert edges that have different keys */
334
insert_hash_edge(stl, edge[j], stl_match_neighbors_nearby);
344
stl_load_edge_nearby(stl_file *stl, stl_hash_edge *edge,
345
stl_vertex *a, stl_vertex *b, float tolerance)
355
diff_x = ABS(a->x - b->x);
356
diff_y = ABS(a->y - b->y);
357
diff_z = ABS(a->z - b->z);
358
max_diff = STL_MAX(diff_x, diff_y);
359
max_diff = STL_MAX(diff_z, max_diff);
361
vertex1[0] = (unsigned)((a->x - stl->stats.min.x) / tolerance);
362
vertex1[1] = (unsigned)((a->y - stl->stats.min.y) / tolerance);
363
vertex1[2] = (unsigned)((a->z - stl->stats.min.z) / tolerance);
364
vertex2[0] = (unsigned)((b->x - stl->stats.min.x) / tolerance);
365
vertex2[1] = (unsigned)((b->y - stl->stats.min.y) / tolerance);
366
vertex2[2] = (unsigned)((b->z - stl->stats.min.z) / tolerance);
368
if( (vertex1[0] == vertex2[0])
369
&& (vertex1[1] == vertex2[1])
370
&& (vertex1[2] == vertex2[2]))
372
/* Both vertices hash to the same value */
376
if(diff_x == max_diff)
380
memcpy(&edge->key[0], vertex1, sizeof(stl_vertex));
381
memcpy(&edge->key[3], vertex2, sizeof(stl_vertex));
385
memcpy(&edge->key[0], vertex2, sizeof(stl_vertex));
386
memcpy(&edge->key[3], vertex1, sizeof(stl_vertex));
387
edge->which_edge += 3; /* this edge is loaded backwards */
390
else if(diff_y == max_diff)
394
memcpy(&edge->key[0], vertex1, sizeof(stl_vertex));
395
memcpy(&edge->key[3], vertex2, sizeof(stl_vertex));
399
memcpy(&edge->key[0], vertex2, sizeof(stl_vertex));
400
memcpy(&edge->key[3], vertex1, sizeof(stl_vertex));
401
edge->which_edge += 3; /* this edge is loaded backwards */
408
memcpy(&edge->key[0], vertex1, sizeof(stl_vertex));
409
memcpy(&edge->key[3], vertex2, sizeof(stl_vertex));
413
memcpy(&edge->key[0], vertex2, sizeof(stl_vertex));
414
memcpy(&edge->key[3], vertex1, sizeof(stl_vertex));
415
edge->which_edge += 3; /* this edge is loaded backwards */
422
stl_free_edges(stl_file *stl)
427
if(stl->stats.malloced != stl->stats.freed)
429
for(i = 0; i < stl->M; i++)
431
for(temp = stl->heads[i]; stl->heads[i] != stl->tail;
432
temp = stl->heads[i])
434
stl->heads[i] = stl->heads[i]->next;
445
stl_initialize_facet_check_nearby(stl_file *stl)
449
stl->stats.malloced = 0;
450
stl->stats.freed = 0;
451
stl->stats.collisions = 0;
453
/* tolerance = STL_MAX(stl->stats.shortest_edge, tolerance);*/
454
/* tolerance = STL_MAX((stl->stats.bounding_diameter / 500000.0), tolerance);*/
455
/* tolerance *= 0.5;*/
459
stl->heads = (stl_hash_edge**)calloc(stl->M, sizeof(*stl->heads));
460
if(stl->heads == NULL) perror("stl_initialize_facet_check_nearby");
462
stl->tail = (stl_hash_edge*)malloc(sizeof(stl_hash_edge));
463
if(stl->tail == NULL) perror("stl_initialize_facet_check_nearby");
465
stl->tail->next = stl->tail;
467
for(i = 0; i < stl->M; i++)
469
stl->heads[i] = stl->tail;
476
stl_record_neighbors(stl_file *stl,
477
stl_hash_edge *edge_a, stl_hash_edge *edge_b)
482
/* Facet a's neighbor is facet b */
483
stl->neighbors_start[edge_a->facet_number].neighbor[edge_a->which_edge % 3] =
484
edge_b->facet_number; /* sets the .neighbor part */
486
stl->neighbors_start[edge_a->facet_number].
487
which_vertex_not[edge_a->which_edge % 3] =
488
(edge_b->which_edge + 2) % 3; /* sets the .which_vertex_not part */
490
/* Facet b's neighbor is facet a */
491
stl->neighbors_start[edge_b->facet_number].neighbor[edge_b->which_edge % 3] =
492
edge_a->facet_number; /* sets the .neighbor part */
494
stl->neighbors_start[edge_b->facet_number].
495
which_vertex_not[edge_b->which_edge % 3] =
496
(edge_a->which_edge + 2) % 3; /* sets the .which_vertex_not part */
498
if( ((edge_a->which_edge < 3) && (edge_b->which_edge < 3))
499
|| ((edge_a->which_edge > 2) && (edge_b->which_edge > 2)))
501
/* these facets are oriented in opposite directions. */
502
/* their normals are probably messed up. */
503
stl->neighbors_start[edge_a->facet_number].
504
which_vertex_not[edge_a->which_edge % 3] += 3;
505
stl->neighbors_start[edge_b->facet_number].
506
which_vertex_not[edge_b->which_edge % 3] += 3;
510
/* Count successful connects */
512
stl->stats.connected_edges += 2;
513
/* Count individual connects */
514
i = ((stl->neighbors_start[edge_a->facet_number].neighbor[0] == -1) +
515
(stl->neighbors_start[edge_a->facet_number].neighbor[1] == -1) +
516
(stl->neighbors_start[edge_a->facet_number].neighbor[2] == -1));
517
j = ((stl->neighbors_start[edge_b->facet_number].neighbor[0] == -1) +
518
(stl->neighbors_start[edge_b->facet_number].neighbor[1] == -1) +
519
(stl->neighbors_start[edge_b->facet_number].neighbor[2] == -1));
522
stl->stats.connected_facets_1_edge +=1;
526
stl->stats.connected_facets_2_edge +=1;
530
stl->stats.connected_facets_3_edge +=1;
534
stl->stats.connected_facets_1_edge +=1;
538
stl->stats.connected_facets_2_edge +=1;
542
stl->stats.connected_facets_3_edge +=1;
547
stl_match_neighbors_exact(stl_file *stl,
548
stl_hash_edge *edge_a, stl_hash_edge *edge_b)
550
stl_record_neighbors(stl, edge_a, edge_b);
554
stl_match_neighbors_nearby(stl_file *stl,
555
stl_hash_edge *edge_a, stl_hash_edge *edge_b)
563
stl_vertex new_vertex1;
564
stl_vertex new_vertex2;
566
stl_record_neighbors(stl, edge_a, edge_b);
567
stl_which_vertices_to_change(stl, edge_a, edge_b, &facet1, &vertex1,
568
&facet2, &vertex2, &new_vertex1, &new_vertex2);
571
if(facet1 == edge_a->facet_number)
573
vnot1 = (edge_a->which_edge + 2) % 3;
577
vnot1 = (edge_b->which_edge + 2) % 3;
579
if(((vnot1 + 2) % 3) == vertex1)
583
stl_change_vertices(stl, facet1, vnot1, new_vertex1);
587
if(facet2 == edge_a->facet_number)
589
vnot2 = (edge_a->which_edge + 2) % 3;
593
vnot2 = (edge_b->which_edge + 2) % 3;
595
if(((vnot2 + 2) % 3) == vertex2)
599
stl_change_vertices(stl, facet2, vnot2, new_vertex2);
601
stl->stats.edges_fixed += 2;
606
stl_change_vertices(stl_file *stl, int facet_num, int vnot,
607
stl_vertex new_vertex)
614
first_facet = facet_num;
623
pivot_vertex = (vnot + 2) % 3;
624
next_edge = pivot_vertex;
629
pivot_vertex = (vnot + 1) % 3;
630
next_edge = vnot % 3;
638
pivot_vertex = (vnot + 1) % 3;
643
pivot_vertex = (vnot + 2) % 3;
644
next_edge = pivot_vertex;
647
stl->facet_start[facet_num].vertex[pivot_vertex] = new_vertex;
648
vnot = stl->neighbors_start[facet_num].which_vertex_not[next_edge];
649
facet_num = stl->neighbors_start[facet_num].neighbor[next_edge];
656
if(facet_num == first_facet)
658
/* back to the beginning */
660
Back to the first facet changing vertices: probably a mobius part.\n\
661
Try using a smaller tolerance or don't do a nearby check\n");*/
662
printf("Failed to repair mesh (back to the first facet changing vertices: probably a mobius part)\n");
672
stl_which_vertices_to_change(stl_file *stl, stl_hash_edge *edge_a,
673
stl_hash_edge *edge_b, int *facet1, int *vertex1,
674
int *facet2, int *vertex2,
675
stl_vertex *new_vertex1, stl_vertex *new_vertex2)
677
int v1a; /* pair 1, facet a */
678
int v1b; /* pair 1, facet b */
679
int v2a; /* pair 2, facet a */
680
int v2b; /* pair 2, facet b */
683
/* Find first pair */
684
if(edge_a->which_edge < 3)
686
v1a = edge_a->which_edge;
687
v2a = (edge_a->which_edge + 1) % 3;
691
v2a = edge_a->which_edge % 3;
692
v1a = (edge_a->which_edge + 1) % 3;
694
if(edge_b->which_edge < 3)
696
v1b = edge_b->which_edge;
697
v2b = (edge_b->which_edge + 1) % 3;
701
v2b = edge_b->which_edge % 3;
702
v1b = (edge_b->which_edge + 1) % 3;
705
/* Of the first pair, which vertex, if any, should be changed */
706
if(!memcmp(&stl->facet_start[edge_a->facet_number].vertex[v1a],
707
&stl->facet_start[edge_b->facet_number].vertex[v1b],
710
/* These facets are already equal. No need to change. */
715
if( (stl->neighbors_start[edge_a->facet_number].neighbor[v1a] == -1)
716
&& (stl->neighbors_start[edge_a->facet_number].
717
neighbor[(v1a + 2) % 3] == -1))
719
/* This vertex has no neighbors. This is a good one to change */
720
*facet1 = edge_a->facet_number;
722
*new_vertex1 = stl->facet_start[edge_b->facet_number].vertex[v1b];
726
*facet1 = edge_b->facet_number;
728
*new_vertex1 = stl->facet_start[edge_a->facet_number].vertex[v1a];
732
/* Of the second pair, which vertex, if any, should be changed */
733
if(!memcmp(&stl->facet_start[edge_a->facet_number].vertex[v2a],
734
&stl->facet_start[edge_b->facet_number].vertex[v2b],
737
/* These facets are already equal. No need to change. */
742
if( (stl->neighbors_start[edge_a->facet_number].neighbor[v2a] == -1)
743
&& (stl->neighbors_start[edge_a->facet_number].
744
neighbor[(v2a + 2) % 3] == -1))
746
/* This vertex has no neighbors. This is a good one to change */
747
*facet2 = edge_a->facet_number;
749
*new_vertex2 = stl->facet_start[edge_b->facet_number].vertex[v2b];
753
*facet2 = edge_b->facet_number;
755
*new_vertex2 = stl->facet_start[edge_a->facet_number].vertex[v2a];
761
stl_remove_facet(stl_file *stl, int facet_number)
768
stl->stats.facets_removed += 1;
769
/* Update list of connected edges */
770
j = ((stl->neighbors_start[facet_number].neighbor[0] == -1) +
771
(stl->neighbors_start[facet_number].neighbor[1] == -1) +
772
(stl->neighbors_start[facet_number].neighbor[2] == -1));
775
stl->stats.connected_facets_1_edge -= 1;
779
stl->stats.connected_facets_2_edge -= 1;
780
stl->stats.connected_facets_1_edge -= 1;
784
stl->stats.connected_facets_3_edge -= 1;
785
stl->stats.connected_facets_2_edge -= 1;
786
stl->stats.connected_facets_1_edge -= 1;
789
stl->facet_start[facet_number] =
790
stl->facet_start[stl->stats.number_of_facets - 1];
791
/* I could reallocate at this point, but it is not really necessary. */
792
stl->neighbors_start[facet_number] =
793
stl->neighbors_start[stl->stats.number_of_facets - 1];
794
stl->stats.number_of_facets -= 1;
796
for(i = 0; i < 3; i++)
798
neighbor[i] = stl->neighbors_start[facet_number].neighbor[i];
799
vnot[i] = stl->neighbors_start[facet_number].which_vertex_not[i];
802
for(i = 0; i < 3; i++)
804
if(neighbor[i] != -1)
806
if(stl->neighbors_start[neighbor[i]].neighbor[(vnot[i] + 1)% 3] !=
807
stl->stats.number_of_facets)
810
in stl_remove_facet: neighbor = %d numfacets = %d this is wrong\n",
811
stl->neighbors_start[neighbor[i]].neighbor[(vnot[i] + 1)% 3],
812
stl->stats.number_of_facets);
815
stl->neighbors_start[neighbor[i]].neighbor[(vnot[i] + 1)% 3]
822
stl_remove_unconnected_facets(stl_file *stl)
824
/* A couple of things need to be done here. One is to remove any */
825
/* completely unconnected facets (0 edges connected) since these are */
826
/* useless and could be completely wrong. The second thing that needs to */
827
/* be done is to remove any degenerate facets that were created during */
828
/* stl_check_facets_nearby(). */
832
/* remove degenerate facets */
833
for(i = 0; i < stl->stats.number_of_facets; i++)
835
if( !memcmp(&stl->facet_start[i].vertex[0],
836
&stl->facet_start[i].vertex[1], sizeof(stl_vertex))
837
|| !memcmp(&stl->facet_start[i].vertex[1],
838
&stl->facet_start[i].vertex[2], sizeof(stl_vertex))
839
|| !memcmp(&stl->facet_start[i].vertex[0],
840
&stl->facet_start[i].vertex[2], sizeof(stl_vertex)))
842
stl_remove_degenerate(stl, i);
847
if(stl->stats.connected_facets_1_edge < stl->stats.number_of_facets)
849
/* remove completely unconnected facets */
850
for(i = 0; i < stl->stats.number_of_facets; i++)
852
if( (stl->neighbors_start[i].neighbor[0] == -1)
853
&& (stl->neighbors_start[i].neighbor[1] == -1)
854
&& (stl->neighbors_start[i].neighbor[2] == -1))
856
/* This facet is completely unconnected. Remove it. */
857
stl_remove_facet(stl, i);
865
stl_remove_degenerate(stl_file *stl, int facet)
877
if( !memcmp(&stl->facet_start[facet].vertex[0],
878
&stl->facet_start[facet].vertex[1], sizeof(stl_vertex))
879
&& !memcmp(&stl->facet_start[facet].vertex[1],
880
&stl->facet_start[facet].vertex[2], sizeof(stl_vertex)))
882
/* all 3 vertices are equal. Just remove the facet. I don't think*/
883
/* this is really possible, but just in case... */
884
printf("removing a facet in stl_remove_degenerate\n");
886
stl_remove_facet(stl, facet);
890
if(!memcmp(&stl->facet_start[facet].vertex[0],
891
&stl->facet_start[facet].vertex[1], sizeof(stl_vertex)))
897
else if(!memcmp(&stl->facet_start[facet].vertex[1],
898
&stl->facet_start[facet].vertex[2], sizeof(stl_vertex)))
904
else if(!memcmp(&stl->facet_start[facet].vertex[2],
905
&stl->facet_start[facet].vertex[0], sizeof(stl_vertex)))
913
/* No degenerate. Function shouldn't have been called. */
916
neighbor1 = stl->neighbors_start[facet].neighbor[edge1];
917
neighbor2 = stl->neighbors_start[facet].neighbor[edge2];
921
stl_update_connects_remove_1(stl, neighbor2);
925
stl_update_connects_remove_1(stl, neighbor1);
929
neighbor3 = stl->neighbors_start[facet].neighbor[edge3];
930
vnot1 = stl->neighbors_start[facet].which_vertex_not[edge1];
931
vnot2 = stl->neighbors_start[facet].which_vertex_not[edge2];
932
vnot3 = stl->neighbors_start[facet].which_vertex_not[edge3];
934
stl->neighbors_start[neighbor1].neighbor[(vnot1 + 1) % 3] = neighbor2;
935
stl->neighbors_start[neighbor2].neighbor[(vnot2 + 1) % 3] = neighbor1;
936
stl->neighbors_start[neighbor1].which_vertex_not[(vnot1 + 1) % 3] = vnot2;
937
stl->neighbors_start[neighbor2].which_vertex_not[(vnot2 + 1) % 3] = vnot1;
939
stl_remove_facet(stl, facet);
943
stl_update_connects_remove_1(stl, neighbor3);
944
stl->neighbors_start[neighbor3].neighbor[(vnot3 + 1) % 3] = -1;
949
stl_update_connects_remove_1(stl_file *stl, int facet_num)
953
/* Update list of connected edges */
954
j = ((stl->neighbors_start[facet_num].neighbor[0] == -1) +
955
(stl->neighbors_start[facet_num].neighbor[1] == -1) +
956
(stl->neighbors_start[facet_num].neighbor[2] == -1));
957
if(j == 0) /* Facet has 3 neighbors */
959
stl->stats.connected_facets_3_edge -= 1;
961
else if(j == 1) /* Facet has 2 neighbors */
963
stl->stats.connected_facets_2_edge -= 1;
965
else if(j == 2) /* Facet has 1 neighbor */
967
stl->stats.connected_facets_1_edge -= 1;
972
stl_fill_holes(stl_file *stl)
976
int neighbors_initial[3];
989
/* Insert all unconnected edges into hash list */
990
stl_initialize_facet_check_nearby(stl);
991
for(i = 0; i < stl->stats.number_of_facets; i++)
993
facet = stl->facet_start[i];
994
for(j = 0; j < 3; j++)
996
if(stl->neighbors_start[i].neighbor[j] != -1) continue;
997
edge.facet_number = i;
999
stl_load_edge_exact(stl, &edge, &facet.vertex[j],
1000
&facet.vertex[(j + 1) % 3]);
1002
insert_hash_edge(stl, edge, stl_match_neighbors_exact);
1006
for(i = 0; i < stl->stats.number_of_facets; i++)
1008
facet = stl->facet_start[i];
1009
neighbors_initial[0] = stl->neighbors_start[i].neighbor[0];
1010
neighbors_initial[1] = stl->neighbors_start[i].neighbor[1];
1011
neighbors_initial[2] = stl->neighbors_start[i].neighbor[2];
1013
for(j = 0; j < 3; j++)
1015
if(stl->neighbors_start[i].neighbor[j] != -1) continue;
1017
new_facet.vertex[0] = facet.vertex[j];
1018
new_facet.vertex[1] = facet.vertex[(j + 1) % 3];
1019
if(neighbors_initial[(j + 2) % 3] == -1)
1037
pivot_vertex = (vnot + 2) % 3;
1038
next_edge = pivot_vertex;
1043
pivot_vertex = (vnot + 1) % 3;
1044
next_edge = vnot % 3;
1052
pivot_vertex = (vnot + 1) % 3;
1057
pivot_vertex = (vnot + 2) % 3;
1058
next_edge = pivot_vertex;
1061
next_facet = stl->neighbors_start[facet_num].neighbor[next_edge];
1063
if(next_facet == -1)
1065
new_facet.vertex[2] = stl->facet_start[facet_num].
1067
stl_add_facet(stl, &new_facet);
1068
for(k = 0; k < 3; k++)
1070
edge.facet_number = stl->stats.number_of_facets - 1;
1071
edge.which_edge = k;
1072
stl_load_edge_exact(stl, &edge, &new_facet.vertex[k],
1073
&new_facet.vertex[(k + 1) % 3]);
1075
insert_hash_edge(stl, edge, stl_match_neighbors_exact);
1081
vnot = stl->neighbors_start[facet_num].
1082
which_vertex_not[next_edge];
1083
facet_num = next_facet;
1086
if(facet_num == first_facet)
1088
/* back to the beginning */
1090
Back to the first facet filling holes: probably a mobius part.\n\
1091
Try using a smaller tolerance or don't do a nearby check\n"); */
1092
printf("Failed to repair mesh (back to the first facet filling holes: probably a mobius part)\n");
1103
stl_add_facet(stl_file *stl, stl_facet *new_facet)
1105
stl->stats.facets_added += 1;
1106
if(stl->stats.facets_malloced < stl->stats.number_of_facets + 1)
1108
stl->facet_start = (stl_facet*)realloc(stl->facet_start,
1109
(sizeof(stl_facet) * (stl->stats.facets_malloced + 256)));
1110
if(stl->facet_start == NULL) perror("stl_add_facet");
1111
stl->neighbors_start = (stl_neighbors*)realloc(stl->neighbors_start,
1112
(sizeof(stl_neighbors) * (stl->stats.facets_malloced + 256)));
1113
if(stl->neighbors_start == NULL) perror("stl_add_facet");
1114
stl->stats.facets_malloced += 256;
1116
stl->facet_start[stl->stats.number_of_facets] = *new_facet;
1118
/* note that the normal vector is not set here, just initialized to 0 */
1119
stl->facet_start[stl->stats.number_of_facets].normal.x = 0.0;
1120
stl->facet_start[stl->stats.number_of_facets].normal.y = 0.0;
1121
stl->facet_start[stl->stats.number_of_facets].normal.z = 0.0;
1123
stl->neighbors_start[stl->stats.number_of_facets].neighbor[0] = -1;
1124
stl->neighbors_start[stl->stats.number_of_facets].neighbor[1] = -1;
1125
stl->neighbors_start[stl->stats.number_of_facets].neighbor[2] = -1;
1126
stl->stats.number_of_facets += 1;