← Back to branch summary

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

« back to all changes in this revision

Viewing changes to xs/src/admesh/connect.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/connect.c
 
1
/*  ADMesh -- process triangulated solid meshes
 
2
 *  Copyright (C) 1995  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
 
 
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);
 
58
 
 
59
 
 
60
void
 
61
stl_check_facets_exact(stl_file *stl)
 
62
{
 
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.
 
66
 */
 
67
 
 
68
  stl_hash_edge  edge;
 
69
  stl_facet      facet;
 
70
  int            i;
 
71
  int            j;
 
72
 
 
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;
 
77
 
 
78
  stl_initialize_facet_check_exact(stl);
 
79
 
 
80
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
81
    {
 
82
      facet = stl->facet_start[i];
 
83
 
 
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], 
 
86
                    sizeof(stl_vertex))
 
87
         || !memcmp(&facet.vertex[1], &facet.vertex[2], 
 
88
                    sizeof(stl_vertex))
 
89
         || !memcmp(&facet.vertex[0], &facet.vertex[2], 
 
90
                    sizeof(stl_vertex)))
 
91
        {
 
92
          stl->stats.degenerate_facets += 1;
 
93
          stl_remove_facet(stl, i);
 
94
          i--;
 
95
          continue;
 
96
 
 
97
        }
 
98
      for(j = 0; j < 3; j++)
 
99
        {
 
100
          edge.facet_number = i;
 
101
          edge.which_edge = j;
 
102
          stl_load_edge_exact(stl, &edge, &facet.vertex[j],
 
103
                              &facet.vertex[(j + 1) % 3]);
 
104
          
 
105
          insert_hash_edge(stl, edge, stl_match_neighbors_exact);
 
106
        }
 
107
    }
 
108
  stl_free_edges(stl);
 
109
}
 
110
 
 
111
static void
 
112
stl_load_edge_exact(stl_file *stl, stl_hash_edge *edge,
 
113
                    stl_vertex *a, stl_vertex *b)
 
114
{
 
115
 
 
116
  float diff_x;
 
117
  float diff_y;
 
118
  float diff_z;
 
119
  float max_diff;
 
120
  
 
121
  
 
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);
 
128
 
 
129
  if(diff_x == max_diff)
 
130
    {
 
131
      if(a->x > b->x)
 
132
        {
 
133
          memcpy(&edge->key[0], a, sizeof(stl_vertex));
 
134
          memcpy(&edge->key[3], b, sizeof(stl_vertex));
 
135
        }
 
136
      else
 
137
        {
 
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 */
 
141
        }
 
142
    }
 
143
  else if(diff_y == max_diff)
 
144
    {
 
145
      if(a->y > b->y)
 
146
        {
 
147
          memcpy(&edge->key[0], a, sizeof(stl_vertex));
 
148
          memcpy(&edge->key[3], b, sizeof(stl_vertex));
 
149
        }
 
150
      else
 
151
        {
 
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 */
 
155
        }
 
156
    }
 
157
  else
 
158
    {
 
159
      if(a->z > b->z)
 
160
        {
 
161
          memcpy(&edge->key[0], a, sizeof(stl_vertex));
 
162
          memcpy(&edge->key[3], b, sizeof(stl_vertex));
 
163
        }
 
164
      else
 
165
        {
 
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 */
 
169
        }
 
170
    }
 
171
}
 
172
 
 
173
static void
 
174
stl_initialize_facet_check_exact(stl_file *stl)
 
175
{
 
176
  int i;
 
177
 
 
178
  stl->stats.malloced = 0;
 
179
  stl->stats.freed = 0;
 
180
  stl->stats.collisions = 0;
 
181
 
 
182
 
 
183
  stl->M = 81397;
 
184
 
 
185
  for(i = 0; i < stl->stats.number_of_facets ; i++)
 
186
    {
 
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;
 
191
    }
 
192
 
 
193
  stl->heads = (stl_hash_edge**)calloc(stl->M, sizeof(*stl->heads));
 
194
  if(stl->heads == NULL) perror("stl_initialize_facet_check_exact");
 
195
 
 
196
  stl->tail = (stl_hash_edge*)malloc(sizeof(stl_hash_edge));
 
197
  if(stl->tail == NULL) perror("stl_initialize_facet_check_exact");
 
198
 
 
199
  stl->tail->next = stl->tail;
 
200
 
 
201
  for(i = 0; i < stl->M; i++)
 
202
    {
 
203
      stl->heads[i] = stl->tail;
 
204
    }
 
205
}
 
206
 
 
207
static void
 
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))
 
211
{
 
212
  stl_hash_edge *link;
 
213
  stl_hash_edge *new_edge;
 
214
  stl_hash_edge *temp;
 
215
  int            chain_number;
 
216
 
 
217
  chain_number = stl_get_hash_for_edge(stl->M, &edge);
 
218
 
 
219
  link = stl->heads[chain_number];
 
220
 
 
221
  if(link == stl->tail)
 
222
    {
 
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++;
 
227
      *new_edge = edge;
 
228
      new_edge->next = stl->tail;
 
229
      stl->heads[chain_number] = new_edge;
 
230
      return;
 
231
    }      
 
232
  else  if(!stl_compare_function(&edge, link))
 
233
    {
 
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;
 
238
      free(link);
 
239
      stl->stats.freed++;
 
240
      return;
 
241
    }
 
242
  else
 
243
    {                           /* Continue through the rest of the list */
 
244
      for(;;)
 
245
        {
 
246
          if(link->next == stl->tail)
 
247
            {
 
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++;
 
252
              *new_edge = edge;
 
253
              new_edge->next = stl->tail;
 
254
              link->next = new_edge;
 
255
              stl->stats.collisions++;
 
256
              return;
 
257
            }
 
258
          else  if(!stl_compare_function(&edge, link->next))
 
259
            {
 
260
              /* This is a match.  Record result in neighbors list. */
 
261
              match_neighbors(stl, &edge, link->next);
 
262
              
 
263
              /* Delete the matched edge from the list. */
 
264
              temp = link->next;
 
265
              link->next = link->next->next;
 
266
              free(temp);
 
267
              stl->stats.freed++;
 
268
              return;
 
269
            }
 
270
          else
 
271
            {
 
272
              /* This is not a match.  Go to the next link */
 
273
              link = link->next;
 
274
              stl->stats.collisions++;
 
275
            }
 
276
        }
 
277
    }
 
278
}
 
279
 
 
280
 
 
281
static int
 
282
stl_get_hash_for_edge(int M, stl_hash_edge *edge)
 
283
{
 
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);
 
286
}
 
287
 
 
288
static int
 
289
stl_compare_function(stl_hash_edge *edge_a, stl_hash_edge *edge_b)
 
290
{
 
291
  if(edge_a->facet_number == edge_b->facet_number)
 
292
    {
 
293
      return 1;                 /* Don't match edges of the same facet */
 
294
    }
 
295
  else
 
296
    {
 
297
      return memcmp(edge_a, edge_b, SIZEOF_EDGE_SORT);
 
298
    }
 
299
}
 
300
 
 
301
void
 
302
stl_check_facets_nearby(stl_file *stl, float tolerance)
 
303
{
 
304
  stl_hash_edge  edge[3];
 
305
  stl_facet      facet;
 
306
  int            i;
 
307
  int            j;
 
308
 
 
309
 
 
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))
 
313
    {
 
314
      /* No need to check any further.  All facets are connected */
 
315
      return;
 
316
    }
 
317
 
 
318
  stl_initialize_facet_check_nearby(stl);
 
319
 
 
320
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
321
    {
 
322
      facet = stl->facet_start[i];
 
323
      for(j = 0; j < 3; j++)
 
324
        {
 
325
          if(stl->neighbors_start[i].neighbor[j] == -1)
 
326
            {
 
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],
 
331
                                      tolerance))
 
332
                {
 
333
                  /* only insert edges that have different keys */
 
334
                  insert_hash_edge(stl, edge[j], stl_match_neighbors_nearby);
 
335
                }
 
336
            }
 
337
        }
 
338
    }
 
339
 
 
340
  stl_free_edges(stl);
 
341
}
 
342
 
 
343
static int
 
344
stl_load_edge_nearby(stl_file *stl, stl_hash_edge *edge,
 
345
                     stl_vertex *a, stl_vertex *b, float tolerance)
 
346
{
 
347
  float diff_x;
 
348
  float diff_y;
 
349
  float diff_z;
 
350
  float max_diff;
 
351
  unsigned vertex1[3];
 
352
  unsigned vertex2[3];
 
353
 
 
354
 
 
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);
 
360
 
 
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);
 
367
  
 
368
  if(   (vertex1[0] == vertex2[0])
 
369
     && (vertex1[1] == vertex2[1])
 
370
     && (vertex1[2] == vertex2[2]))
 
371
    {
 
372
      /* Both vertices hash to the same value */
 
373
      return 0;
 
374
    }
 
375
 
 
376
  if(diff_x == max_diff)
 
377
    {
 
378
      if(a->x > b->x)
 
379
        {
 
380
          memcpy(&edge->key[0], vertex1, sizeof(stl_vertex));
 
381
          memcpy(&edge->key[3], vertex2, sizeof(stl_vertex));
 
382
        }
 
383
      else
 
384
        {
 
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 */
 
388
        }
 
389
    }
 
390
  else if(diff_y == max_diff)
 
391
    {
 
392
      if(a->y > b->y)
 
393
        {
 
394
          memcpy(&edge->key[0], vertex1, sizeof(stl_vertex));
 
395
          memcpy(&edge->key[3], vertex2, sizeof(stl_vertex));
 
396
        }
 
397
      else
 
398
        {
 
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 */
 
402
        }
 
403
    }
 
404
  else
 
405
    {
 
406
      if(a->z > b->z)
 
407
        {
 
408
          memcpy(&edge->key[0], vertex1, sizeof(stl_vertex));
 
409
          memcpy(&edge->key[3], vertex2, sizeof(stl_vertex));
 
410
        }
 
411
      else
 
412
        {
 
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 */
 
416
        }
 
417
    }
 
418
  return 1;
 
419
}
 
420
 
 
421
static void
 
422
stl_free_edges(stl_file *stl)
 
423
{
 
424
  int i;
 
425
  stl_hash_edge *temp;
 
426
  
 
427
  if(stl->stats.malloced != stl->stats.freed)
 
428
    {
 
429
      for(i = 0; i < stl->M; i++)
 
430
        {
 
431
          for(temp = stl->heads[i]; stl->heads[i] != stl->tail;
 
432
              temp = stl->heads[i])
 
433
            {
 
434
              stl->heads[i] = stl->heads[i]->next;
 
435
              free(temp);
 
436
              stl->stats.freed++;
 
437
            }
 
438
        }
 
439
    }
 
440
  free(stl->heads);
 
441
  free(stl->tail);
 
442
}
 
443
              
 
444
static void
 
445
stl_initialize_facet_check_nearby(stl_file *stl)
 
446
{
 
447
  int i;
 
448
 
 
449
  stl->stats.malloced = 0;
 
450
  stl->stats.freed = 0;
 
451
  stl->stats.collisions = 0;
 
452
 
 
453
  /*  tolerance = STL_MAX(stl->stats.shortest_edge, tolerance);*/
 
454
  /*  tolerance = STL_MAX((stl->stats.bounding_diameter / 500000.0), tolerance);*/
 
455
  /*  tolerance *= 0.5;*/
 
456
 
 
457
  stl->M = 81397;
 
458
 
 
459
  stl->heads = (stl_hash_edge**)calloc(stl->M, sizeof(*stl->heads));
 
460
  if(stl->heads == NULL) perror("stl_initialize_facet_check_nearby");
 
461
 
 
462
  stl->tail = (stl_hash_edge*)malloc(sizeof(stl_hash_edge));
 
463
  if(stl->tail == NULL) perror("stl_initialize_facet_check_nearby");
 
464
 
 
465
  stl->tail->next = stl->tail;
 
466
 
 
467
  for(i = 0; i < stl->M; i++)
 
468
    {
 
469
      stl->heads[i] = stl->tail;
 
470
    }
 
471
}
 
472
 
 
473
 
 
474
 
 
475
static void
 
476
stl_record_neighbors(stl_file *stl,
 
477
                               stl_hash_edge *edge_a, stl_hash_edge *edge_b)
 
478
{
 
479
  int i;
 
480
  int j;
 
481
 
 
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 */
 
485
  
 
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 */
 
489
  
 
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 */
 
493
  
 
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 */
 
497
  
 
498
  if(   ((edge_a->which_edge < 3) && (edge_b->which_edge < 3))
 
499
     || ((edge_a->which_edge > 2) && (edge_b->which_edge > 2)))
 
500
    {
 
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;
 
507
    }
 
508
      
 
509
 
 
510
  /* Count successful connects */
 
511
  /* Total 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));
 
520
  if(i == 2)
 
521
    {
 
522
      stl->stats.connected_facets_1_edge +=1;
 
523
    }
 
524
  else if(i == 1)
 
525
    {
 
526
      stl->stats.connected_facets_2_edge +=1;
 
527
    }
 
528
  else
 
529
    {
 
530
      stl->stats.connected_facets_3_edge +=1;
 
531
    }
 
532
  if(j == 2)
 
533
    {
 
534
      stl->stats.connected_facets_1_edge +=1;
 
535
    }
 
536
  else if(j == 1)
 
537
    {
 
538
      stl->stats.connected_facets_2_edge +=1;
 
539
    }
 
540
  else
 
541
    {
 
542
      stl->stats.connected_facets_3_edge +=1;
 
543
    }
 
544
}
 
545
 
 
546
static void
 
547
stl_match_neighbors_exact(stl_file *stl,
 
548
                               stl_hash_edge *edge_a, stl_hash_edge *edge_b)
 
549
{
 
550
  stl_record_neighbors(stl, edge_a, edge_b);
 
551
}
 
552
 
 
553
static void
 
554
stl_match_neighbors_nearby(stl_file *stl,
 
555
                               stl_hash_edge *edge_a, stl_hash_edge *edge_b)
 
556
{
 
557
  int facet1;
 
558
  int facet2;
 
559
  int vertex1;
 
560
  int vertex2;
 
561
  int vnot1;
 
562
  int vnot2;
 
563
  stl_vertex new_vertex1;
 
564
  stl_vertex new_vertex2;
 
565
 
 
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);
 
569
  if(facet1 != -1)
 
570
    {
 
571
      if(facet1 == edge_a->facet_number)
 
572
        {
 
573
          vnot1 = (edge_a->which_edge + 2) % 3;
 
574
        }
 
575
      else
 
576
        {
 
577
          vnot1 = (edge_b->which_edge + 2) % 3;
 
578
        }
 
579
      if(((vnot1 + 2) % 3) == vertex1)
 
580
        {
 
581
          vnot1 += 3;
 
582
        }
 
583
      stl_change_vertices(stl, facet1, vnot1, new_vertex1);
 
584
    }
 
585
  if(facet2 != -1)
 
586
    {
 
587
      if(facet2 == edge_a->facet_number)
 
588
        {
 
589
          vnot2 = (edge_a->which_edge + 2) % 3;
 
590
        }
 
591
      else
 
592
        {
 
593
          vnot2 = (edge_b->which_edge + 2) % 3;
 
594
        }
 
595
      if(((vnot2 + 2) % 3) == vertex2)
 
596
        {
 
597
          vnot2 += 3;
 
598
        }
 
599
      stl_change_vertices(stl, facet2, vnot2, new_vertex2);
 
600
    }
 
601
  stl->stats.edges_fixed += 2;
 
602
}
 
603
 
 
604
 
 
605
static void
 
606
stl_change_vertices(stl_file *stl, int facet_num, int vnot,
 
607
                         stl_vertex new_vertex)
 
608
{
 
609
  int first_facet;
 
610
  int direction;
 
611
  int next_edge;
 
612
  int pivot_vertex;
 
613
 
 
614
  first_facet = facet_num;
 
615
  direction = 0;
 
616
 
 
617
  for(;;)
 
618
    {
 
619
      if(vnot > 2)
 
620
        {
 
621
          if(direction == 0)
 
622
            {
 
623
              pivot_vertex = (vnot + 2) % 3;
 
624
              next_edge = pivot_vertex;
 
625
              direction = 1;
 
626
            }
 
627
          else
 
628
            {
 
629
              pivot_vertex = (vnot + 1) % 3;
 
630
              next_edge = vnot % 3;
 
631
              direction = 0;
 
632
            }
 
633
        }
 
634
      else
 
635
        {
 
636
          if(direction == 0)
 
637
            {
 
638
              pivot_vertex = (vnot + 1) % 3;
 
639
              next_edge = vnot;
 
640
            }
 
641
          else
 
642
            {
 
643
              pivot_vertex = (vnot + 2) % 3;
 
644
              next_edge = pivot_vertex;
 
645
            }
 
646
        }
 
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];
 
650
        
 
651
      if(facet_num == -1)
 
652
        {
 
653
          break;
 
654
        }
 
655
 
 
656
      if(facet_num == first_facet)
 
657
        {
 
658
          /* back to the beginning */
 
659
          /*printf("\
 
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");
 
663
          return;
 
664
          exit(1);
 
665
          break;
 
666
        }
 
667
    }
 
668
}
 
669
 
 
670
 
 
671
static void
 
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)
 
676
{
 
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 */
 
681
 
 
682
 
 
683
  /* Find first pair */
 
684
  if(edge_a->which_edge < 3)
 
685
    {
 
686
      v1a = edge_a->which_edge;
 
687
      v2a = (edge_a->which_edge + 1) % 3;
 
688
    }
 
689
  else
 
690
    {
 
691
      v2a = edge_a->which_edge % 3;
 
692
      v1a = (edge_a->which_edge + 1) % 3;
 
693
    }      
 
694
  if(edge_b->which_edge < 3)
 
695
    {
 
696
      v1b = edge_b->which_edge;
 
697
      v2b = (edge_b->which_edge + 1) % 3;
 
698
    }
 
699
  else
 
700
    {
 
701
      v2b = edge_b->which_edge % 3;
 
702
      v1b = (edge_b->which_edge + 1) % 3;
 
703
    }
 
704
 
 
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], 
 
708
             sizeof(stl_vertex)))
 
709
    {
 
710
      /* These facets are already equal.  No need to change. */
 
711
      *facet1 = -1;
 
712
    }
 
713
  else
 
714
    {
 
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))
 
718
        {
 
719
          /* This vertex has no neighbors.  This is a good one to change */
 
720
          *facet1 = edge_a->facet_number;
 
721
          *vertex1 = v1a;
 
722
          *new_vertex1 = stl->facet_start[edge_b->facet_number].vertex[v1b];
 
723
        }
 
724
      else
 
725
        {
 
726
          *facet1 = edge_b->facet_number;
 
727
          *vertex1 = v1b;
 
728
          *new_vertex1 = stl->facet_start[edge_a->facet_number].vertex[v1a];
 
729
        }
 
730
    }
 
731
 
 
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],
 
735
             sizeof(stl_vertex)))
 
736
    {
 
737
      /* These facets are already equal.  No need to change. */
 
738
      *facet2 = -1;
 
739
    }
 
740
  else
 
741
    {
 
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))
 
745
        {
 
746
          /* This vertex has no neighbors.  This is a good one to change */
 
747
          *facet2 = edge_a->facet_number;
 
748
          *vertex2 = v2a;
 
749
          *new_vertex2 = stl->facet_start[edge_b->facet_number].vertex[v2b];
 
750
        }
 
751
      else
 
752
        {
 
753
          *facet2 = edge_b->facet_number;
 
754
          *vertex2 = v2b;
 
755
          *new_vertex2 = stl->facet_start[edge_a->facet_number].vertex[v2a];
 
756
        }
 
757
    }
 
758
}
 
759
 
 
760
static void
 
761
stl_remove_facet(stl_file *stl, int facet_number)
 
762
{
 
763
  int neighbor[3];
 
764
  int vnot[3];
 
765
  int i;
 
766
  int j;
 
767
 
 
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));
 
773
  if(j == 2)
 
774
    {
 
775
      stl->stats.connected_facets_1_edge -= 1;
 
776
    }
 
777
  else if(j == 1)
 
778
    {
 
779
      stl->stats.connected_facets_2_edge -= 1;
 
780
      stl->stats.connected_facets_1_edge -= 1;
 
781
    }
 
782
  else if(j == 0)
 
783
    {
 
784
      stl->stats.connected_facets_3_edge -= 1;
 
785
      stl->stats.connected_facets_2_edge -= 1;
 
786
      stl->stats.connected_facets_1_edge -= 1;
 
787
    }  
 
788
  
 
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;
 
795
  
 
796
  for(i = 0; i < 3; i++)
 
797
    {
 
798
      neighbor[i] = stl->neighbors_start[facet_number].neighbor[i];
 
799
      vnot[i] = stl->neighbors_start[facet_number].which_vertex_not[i];
 
800
    }
 
801
  
 
802
  for(i = 0; i < 3; i++)
 
803
    {
 
804
      if(neighbor[i] != -1)
 
805
        {
 
806
          if(stl->neighbors_start[neighbor[i]].neighbor[(vnot[i] + 1)% 3] != 
 
807
             stl->stats.number_of_facets) 
 
808
            {
 
809
              printf("\
 
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);
 
813
              exit(1);
 
814
            }
 
815
          stl->neighbors_start[neighbor[i]].neighbor[(vnot[i] + 1)% 3]
 
816
            = facet_number;
 
817
        }
 
818
    }
 
819
}
 
820
 
 
821
void
 
822
stl_remove_unconnected_facets(stl_file *stl)
 
823
{
 
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(). */
 
829
 
 
830
  int i;
 
831
  
 
832
  /* remove degenerate facets */
 
833
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
834
    {
 
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)))
 
841
        {
 
842
          stl_remove_degenerate(stl, i);
 
843
          i--;
 
844
        }
 
845
    }
 
846
 
 
847
  if(stl->stats.connected_facets_1_edge < stl->stats.number_of_facets)
 
848
    {
 
849
      /* remove completely unconnected facets */
 
850
      for(i = 0; i < stl->stats.number_of_facets; i++)
 
851
        {
 
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))
 
855
            {
 
856
              /* This facet is completely unconnected.  Remove it. */
 
857
              stl_remove_facet(stl, i);
 
858
              i--;
 
859
            }
 
860
        }
 
861
    }
 
862
}
 
863
 
 
864
static void
 
865
stl_remove_degenerate(stl_file *stl, int facet)
 
866
{
 
867
  int edge1;
 
868
  int edge2;
 
869
  int edge3;
 
870
  int neighbor1;
 
871
  int neighbor2;
 
872
  int neighbor3;
 
873
  int vnot1;
 
874
  int vnot2;
 
875
  int vnot3;
 
876
 
 
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)))
 
881
    {
 
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");
 
885
 
 
886
      stl_remove_facet(stl, facet);
 
887
      return;
 
888
    }
 
889
  
 
890
  if(!memcmp(&stl->facet_start[facet].vertex[0], 
 
891
             &stl->facet_start[facet].vertex[1], sizeof(stl_vertex)))
 
892
    {
 
893
      edge1 = 1;
 
894
      edge2 = 2;
 
895
      edge3 = 0;
 
896
    }
 
897
  else if(!memcmp(&stl->facet_start[facet].vertex[1], 
 
898
                  &stl->facet_start[facet].vertex[2], sizeof(stl_vertex)))
 
899
    {
 
900
      edge1 = 0;
 
901
      edge2 = 2;
 
902
      edge3 = 1;
 
903
    }
 
904
  else if(!memcmp(&stl->facet_start[facet].vertex[2], 
 
905
                  &stl->facet_start[facet].vertex[0], sizeof(stl_vertex)))
 
906
    {
 
907
      edge1 = 0;
 
908
      edge2 = 1;
 
909
      edge3 = 2;
 
910
    }
 
911
  else
 
912
    {
 
913
      /* No degenerate. Function shouldn't have been called. */
 
914
      return;
 
915
    }
 
916
  neighbor1 = stl->neighbors_start[facet].neighbor[edge1];
 
917
  neighbor2 = stl->neighbors_start[facet].neighbor[edge2];
 
918
 
 
919
  if(neighbor1 == -1)
 
920
    {
 
921
      stl_update_connects_remove_1(stl, neighbor2);
 
922
    }
 
923
  if(neighbor2 == -1)
 
924
    {
 
925
      stl_update_connects_remove_1(stl, neighbor1);
 
926
    }
 
927
  
 
928
  
 
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];
 
933
 
 
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;
 
938
  
 
939
  stl_remove_facet(stl, facet);
 
940
  
 
941
  if(neighbor3 != -1)
 
942
    {
 
943
      stl_update_connects_remove_1(stl, neighbor3);
 
944
      stl->neighbors_start[neighbor3].neighbor[(vnot3 + 1) % 3] = -1;
 
945
    }
 
946
}
 
947
 
 
948
void
 
949
stl_update_connects_remove_1(stl_file *stl, int facet_num)
 
950
{
 
951
  int j;
 
952
  
 
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 */
 
958
    {
 
959
      stl->stats.connected_facets_3_edge -= 1;
 
960
    }
 
961
  else if(j == 1)                      /* Facet has 2 neighbors */
 
962
    {
 
963
      stl->stats.connected_facets_2_edge -= 1;
 
964
    }
 
965
  else if(j == 2)                      /* Facet has 1 neighbor  */
 
966
    {
 
967
      stl->stats.connected_facets_1_edge -= 1;
 
968
    }      
 
969
}
 
970
 
 
971
void
 
972
stl_fill_holes(stl_file *stl)
 
973
{
 
974
  stl_facet facet;
 
975
  stl_facet new_facet;
 
976
  int neighbors_initial[3];
 
977
  stl_hash_edge edge;
 
978
  int first_facet;
 
979
  int direction;
 
980
  int facet_num;
 
981
  int vnot;
 
982
  int next_edge;
 
983
  int pivot_vertex;
 
984
  int next_facet;
 
985
  int i;
 
986
  int j;
 
987
  int k;
 
988
 
 
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++)
 
992
    {
 
993
      facet = stl->facet_start[i];
 
994
      for(j = 0; j < 3; j++)
 
995
        {
 
996
          if(stl->neighbors_start[i].neighbor[j] != -1) continue;
 
997
          edge.facet_number = i;
 
998
          edge.which_edge = j;
 
999
          stl_load_edge_exact(stl, &edge, &facet.vertex[j],
 
1000
                              &facet.vertex[(j + 1) % 3]);
 
1001
          
 
1002
          insert_hash_edge(stl, edge, stl_match_neighbors_exact);
 
1003
        }
 
1004
    }
 
1005
 
 
1006
  for(i = 0; i < stl->stats.number_of_facets; i++)
 
1007
    {
 
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];
 
1012
      first_facet = i;
 
1013
      for(j = 0; j < 3; j++)
 
1014
        {
 
1015
          if(stl->neighbors_start[i].neighbor[j] != -1) continue;
 
1016
          
 
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)
 
1020
            {
 
1021
              direction = 1;
 
1022
            }
 
1023
          else
 
1024
            {
 
1025
              direction = 0;
 
1026
            }
 
1027
 
 
1028
          facet_num = i;
 
1029
          vnot = (j + 2) % 3;
 
1030
          
 
1031
          for(;;)
 
1032
            {
 
1033
              if(vnot > 2)
 
1034
                {
 
1035
                  if(direction == 0)
 
1036
                    {
 
1037
                      pivot_vertex = (vnot + 2) % 3;
 
1038
                      next_edge = pivot_vertex;
 
1039
                      direction = 1;
 
1040
                    }
 
1041
                  else
 
1042
                    {
 
1043
                      pivot_vertex = (vnot + 1) % 3;
 
1044
                      next_edge = vnot % 3;
 
1045
                      direction = 0;
 
1046
                    }
 
1047
                }
 
1048
              else
 
1049
                {
 
1050
                  if(direction == 0)
 
1051
                    {
 
1052
                      pivot_vertex = (vnot + 1) % 3;
 
1053
                      next_edge = vnot;
 
1054
                    }
 
1055
                  else
 
1056
                    {
 
1057
                      pivot_vertex = (vnot + 2) % 3;
 
1058
                      next_edge = pivot_vertex;
 
1059
                    }
 
1060
                }
 
1061
              next_facet = stl->neighbors_start[facet_num].neighbor[next_edge];
 
1062
              
 
1063
              if(next_facet == -1)
 
1064
                {
 
1065
                  new_facet.vertex[2] = stl->facet_start[facet_num].
 
1066
                    vertex[vnot % 3];
 
1067
                  stl_add_facet(stl, &new_facet);
 
1068
                  for(k = 0; k < 3; k++)
 
1069
                    {
 
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]);
 
1074
                      
 
1075
                      insert_hash_edge(stl, edge, stl_match_neighbors_exact);
 
1076
                    }
 
1077
                  break;
 
1078
                }
 
1079
              else
 
1080
                {
 
1081
                  vnot = stl->neighbors_start[facet_num].
 
1082
                    which_vertex_not[next_edge];
 
1083
                  facet_num = next_facet;
 
1084
                }
 
1085
              
 
1086
              if(facet_num == first_facet)
 
1087
                {
 
1088
                  /* back to the beginning */
 
1089
                  /* printf("\
 
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");
 
1093
          return;
 
1094
                  exit(1);
 
1095
                  break;
 
1096
                }
 
1097
            }
 
1098
        }
 
1099
    }
 
1100
}
 
1101
 
 
1102
void
 
1103
stl_add_facet(stl_file *stl, stl_facet *new_facet)
 
1104
{
 
1105
  stl->stats.facets_added += 1;
 
1106
  if(stl->stats.facets_malloced < stl->stats.number_of_facets + 1)
 
1107
    {
 
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;
 
1115
    }
 
1116
  stl->facet_start[stl->stats.number_of_facets] = *new_facet;
 
1117
 
 
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;
 
1122
                       
 
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;
 
1127
}