← Back to branch summary

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

« back to all changes in this revision

Viewing changes to xs/src/TriangleMesh.cpp

  • 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/TriangleMesh.cpp
 
1
#include "TriangleMesh.hpp"
 
2
#include "ClipperUtils.hpp"
 
3
#include "Geometry.hpp"
 
4
#include <cmath>
 
5
#include <queue>
 
6
#include <deque>
 
7
#include <set>
 
8
#include <vector>
 
9
#include <map>
 
10
#include <utility>
 
11
#include <algorithm>
 
12
#include <math.h>
 
13
#include <assert.h>
 
14
 
 
15
#ifdef SLIC3R_DEBUG
 
16
#include "SVG.hpp"
 
17
#endif
 
18
 
 
19
namespace Slic3r {
 
20
 
 
21
TriangleMesh::TriangleMesh()
 
22
    : repaired(false)
 
23
{
 
24
    stl_initialize(&this->stl);
 
25
}
 
26
 
 
27
TriangleMesh::TriangleMesh(const TriangleMesh &other)
 
28
    : stl(other.stl), repaired(other.repaired)
 
29
{
 
30
    this->stl.heads = NULL;
 
31
    this->stl.tail  = NULL;
 
32
    if (other.stl.facet_start != NULL) {
 
33
        this->stl.facet_start = (stl_facet*)calloc(other.stl.stats.number_of_facets, sizeof(stl_facet));
 
34
        std::copy(other.stl.facet_start, other.stl.facet_start + other.stl.stats.number_of_facets, this->stl.facet_start);
 
35
    }
 
36
    if (other.stl.neighbors_start != NULL) {
 
37
        this->stl.neighbors_start = (stl_neighbors*)calloc(other.stl.stats.number_of_facets, sizeof(stl_neighbors));
 
38
        std::copy(other.stl.neighbors_start, other.stl.neighbors_start + other.stl.stats.number_of_facets, this->stl.neighbors_start);
 
39
    }
 
40
    if (other.stl.v_indices != NULL) {
 
41
        this->stl.v_indices = (v_indices_struct*)calloc(other.stl.stats.number_of_facets, sizeof(v_indices_struct));
 
42
        std::copy(other.stl.v_indices, other.stl.v_indices + other.stl.stats.number_of_facets, this->stl.v_indices);
 
43
    }
 
44
    if (other.stl.v_shared != NULL) {
 
45
        this->stl.v_shared = (stl_vertex*)calloc(other.stl.stats.shared_vertices, sizeof(stl_vertex));
 
46
        std::copy(other.stl.v_shared, other.stl.v_shared + other.stl.stats.shared_vertices, this->stl.v_shared);
 
47
    }
 
48
}
 
49
 
 
50
TriangleMesh& TriangleMesh::operator= (TriangleMesh other)
 
51
{
 
52
    this->swap(other);
 
53
    return *this;
 
54
}
 
55
 
 
56
void
 
57
TriangleMesh::swap(TriangleMesh &other)
 
58
{
 
59
    std::swap(this->stl,                 other.stl);
 
60
    std::swap(this->repaired,            other.repaired);
 
61
    std::swap(this->stl.facet_start,     other.stl.facet_start);
 
62
    std::swap(this->stl.neighbors_start, other.stl.neighbors_start);
 
63
    std::swap(this->stl.v_indices,       other.stl.v_indices);
 
64
    std::swap(this->stl.v_shared,        other.stl.v_shared);
 
65
}
 
66
 
 
67
TriangleMesh::~TriangleMesh() {
 
68
    stl_close(&this->stl);
 
69
}
 
70
 
 
71
void
 
72
TriangleMesh::ReadSTLFile(char* input_file) {
 
73
    stl_open(&stl, input_file);
 
74
}
 
75
 
 
76
void
 
77
TriangleMesh::write_ascii(char* output_file)
 
78
{
 
79
    stl_write_ascii(&this->stl, output_file, "");
 
80
}
 
81
 
 
82
void
 
83
TriangleMesh::write_binary(char* output_file)
 
84
{
 
85
    stl_write_binary(&this->stl, output_file, "");
 
86
}
 
87
 
 
88
void
 
89
TriangleMesh::repair() {
 
90
    if (this->repaired) return;
 
91
    
 
92
    // admesh fails when repairing empty meshes
 
93
    if (this->stl.stats.number_of_facets == 0) return;
 
94
    
 
95
    // checking exact
 
96
    stl_check_facets_exact(&stl);
 
97
    stl.stats.facets_w_1_bad_edge = (stl.stats.connected_facets_2_edge - stl.stats.connected_facets_3_edge);
 
98
    stl.stats.facets_w_2_bad_edge = (stl.stats.connected_facets_1_edge - stl.stats.connected_facets_2_edge);
 
99
    stl.stats.facets_w_3_bad_edge = (stl.stats.number_of_facets - stl.stats.connected_facets_1_edge);
 
100
    
 
101
    // checking nearby
 
102
    int last_edges_fixed = 0;
 
103
    float tolerance = stl.stats.shortest_edge;
 
104
    float increment = stl.stats.bounding_diameter / 10000.0;
 
105
    int iterations = 2;
 
106
    if (stl.stats.connected_facets_3_edge < stl.stats.number_of_facets) {
 
107
        for (int i = 0; i < iterations; i++) {
 
108
            if (stl.stats.connected_facets_3_edge < stl.stats.number_of_facets) {
 
109
                //printf("Checking nearby. Tolerance= %f Iteration=%d of %d...", tolerance, i + 1, iterations);
 
110
                stl_check_facets_nearby(&stl, tolerance);
 
111
                //printf("  Fixed %d edges.\n", stl.stats.edges_fixed - last_edges_fixed);
 
112
                last_edges_fixed = stl.stats.edges_fixed;
 
113
                tolerance += increment;
 
114
            } else {
 
115
                break;
 
116
            }
 
117
        }
 
118
    }
 
119
    
 
120
    // remove_unconnected
 
121
    if (stl.stats.connected_facets_3_edge <  stl.stats.number_of_facets) {
 
122
        stl_remove_unconnected_facets(&stl);
 
123
    }
 
124
    
 
125
    // fill_holes
 
126
    if (stl.stats.connected_facets_3_edge < stl.stats.number_of_facets) {
 
127
        stl_fill_holes(&stl);
 
128
    }
 
129
    
 
130
    // normal_directions
 
131
    stl_fix_normal_directions(&stl);
 
132
    
 
133
    // normal_values
 
134
    stl_fix_normal_values(&stl);
 
135
    
 
136
    // always calculate the volume and reverse all normals if volume is negative
 
137
    stl_calculate_volume(&stl);
 
138
    
 
139
    // neighbors
 
140
    stl_verify_neighbors(&stl);
 
141
    
 
142
    this->repaired = true;
 
143
}
 
144
 
 
145
void
 
146
TriangleMesh::reset_repair_stats() {
 
147
    this->stl.stats.degenerate_facets   = 0;
 
148
    this->stl.stats.edges_fixed         = 0;
 
149
    this->stl.stats.facets_removed      = 0;
 
150
    this->stl.stats.facets_added        = 0;
 
151
    this->stl.stats.facets_reversed     = 0;
 
152
    this->stl.stats.backwards_edges     = 0;
 
153
    this->stl.stats.normals_fixed       = 0;
 
154
}
 
155
 
 
156
void
 
157
TriangleMesh::WriteOBJFile(char* output_file) {
 
158
    stl_generate_shared_vertices(&stl);
 
159
    stl_write_obj(&stl, output_file);
 
160
}
 
161
 
 
162
void TriangleMesh::scale(float factor)
 
163
{
 
164
    stl_scale(&(this->stl), factor);
 
165
}
 
166
 
 
167
void TriangleMesh::scale(std::vector<double> versor)
 
168
{
 
169
    float fversor[3];
 
170
    fversor[0] = versor[0];
 
171
    fversor[1] = versor[1];
 
172
    fversor[2] = versor[2];
 
173
    stl_scale_versor(&this->stl, fversor);
 
174
}
 
175
 
 
176
void TriangleMesh::translate(float x, float y, float z)
 
177
{
 
178
    stl_translate_relative(&(this->stl), x, y, z);
 
179
}
 
180
 
 
181
void TriangleMesh::rotate_x(float angle)
 
182
{
 
183
    stl_rotate_x(&(this->stl), angle);
 
184
}
 
185
 
 
186
void TriangleMesh::rotate_y(float angle)
 
187
{
 
188
    stl_rotate_y(&(this->stl), angle);
 
189
}
 
190
 
 
191
void TriangleMesh::rotate_z(float angle)
 
192
{
 
193
    stl_rotate_z(&(this->stl), angle);
 
194
}
 
195
 
 
196
void TriangleMesh::align_to_origin()
 
197
{
 
198
    this->translate(
 
199
        -(this->stl.stats.min.x),
 
200
        -(this->stl.stats.min.y),
 
201
        -(this->stl.stats.min.z)
 
202
    );
 
203
}
 
204
 
 
205
void TriangleMesh::rotate(double angle, Point* center)
 
206
{
 
207
    this->translate(-center->x, -center->y, 0);
 
208
    stl_rotate_z(&(this->stl), (float)angle);
 
209
    this->translate(+center->x, +center->y, 0);
 
210
}
 
211
 
 
212
TriangleMeshPtrs
 
213
TriangleMesh::split() const
 
214
{
 
215
    TriangleMeshPtrs meshes;
 
216
    std::set<int> seen_facets;
 
217
    
 
218
    // we need neighbors
 
219
    if (!this->repaired) CONFESS("split() requires repair()");
 
220
    
 
221
    // loop while we have remaining facets
 
222
    while (1) {
 
223
        // get the first facet
 
224
        std::queue<int> facet_queue;
 
225
        std::deque<int> facets;
 
226
        for (int facet_idx = 0; facet_idx < this->stl.stats.number_of_facets; facet_idx++) {
 
227
            if (seen_facets.find(facet_idx) == seen_facets.end()) {
 
228
                // if facet was not seen put it into queue and start searching
 
229
                facet_queue.push(facet_idx);
 
230
                break;
 
231
            }
 
232
        }
 
233
        if (facet_queue.empty()) break;
 
234
        
 
235
        while (!facet_queue.empty()) {
 
236
            int facet_idx = facet_queue.front();
 
237
            facet_queue.pop();
 
238
            if (seen_facets.find(facet_idx) != seen_facets.end()) continue;
 
239
            facets.push_back(facet_idx);
 
240
            for (int j = 0; j <= 2; j++) {
 
241
                facet_queue.push(this->stl.neighbors_start[facet_idx].neighbor[j]);
 
242
            }
 
243
            seen_facets.insert(facet_idx);
 
244
        }
 
245
        
 
246
        TriangleMesh* mesh = new TriangleMesh;
 
247
        meshes.push_back(mesh);
 
248
        mesh->stl.stats.type = inmemory;
 
249
        mesh->stl.stats.number_of_facets = facets.size();
 
250
        mesh->stl.stats.original_num_facets = mesh->stl.stats.number_of_facets;
 
251
        stl_allocate(&mesh->stl);
 
252
        
 
253
        int first = 1;
 
254
        for (std::deque<int>::const_iterator facet = facets.begin(); facet != facets.end(); facet++) {
 
255
            mesh->stl.facet_start[facet - facets.begin()] = this->stl.facet_start[*facet];
 
256
            stl_facet_stats(&mesh->stl, this->stl.facet_start[*facet], first);
 
257
            first = 0;
 
258
        }
 
259
    }
 
260
    
 
261
    return meshes;
 
262
}
 
263
 
 
264
void
 
265
TriangleMesh::merge(const TriangleMesh* mesh)
 
266
{
 
267
    // reset stats and metadata
 
268
    int number_of_facets = this->stl.stats.number_of_facets;
 
269
    stl_invalidate_shared_vertices(&this->stl);
 
270
    this->repaired = false;
 
271
    
 
272
    // update facet count and allocate more memory
 
273
    this->stl.stats.number_of_facets = number_of_facets + mesh->stl.stats.number_of_facets;
 
274
    this->stl.stats.original_num_facets = this->stl.stats.number_of_facets;
 
275
    stl_reallocate(&this->stl);
 
276
    
 
277
    // copy facets
 
278
    for (int i = 0; i < mesh->stl.stats.number_of_facets; i++) {
 
279
        this->stl.facet_start[number_of_facets + i] = mesh->stl.facet_start[i];
 
280
    }
 
281
    
 
282
    // update size
 
283
    stl_get_size(&this->stl);
 
284
}
 
285
 
 
286
/* this will return scaled ExPolygons */
 
287
void
 
288
TriangleMesh::horizontal_projection(ExPolygons &retval) const
 
289
{
 
290
    Polygons pp;
 
291
    pp.reserve(this->stl.stats.number_of_facets);
 
292
    for (int i = 0; i < this->stl.stats.number_of_facets; i++) {
 
293
        stl_facet* facet = &this->stl.facet_start[i];
 
294
        Polygon p;
 
295
        p.points.resize(3);
 
296
        p.points[0] = Point(facet->vertex[0].x / SCALING_FACTOR, facet->vertex[0].y / SCALING_FACTOR);
 
297
        p.points[1] = Point(facet->vertex[1].x / SCALING_FACTOR, facet->vertex[1].y / SCALING_FACTOR);
 
298
        p.points[2] = Point(facet->vertex[2].x / SCALING_FACTOR, facet->vertex[2].y / SCALING_FACTOR);
 
299
        p.make_counter_clockwise();  // do this after scaling, as winding order might change while doing that
 
300
        pp.push_back(p);
 
301
    }
 
302
    
 
303
    // the offset factor was tuned using groovemount.stl
 
304
    offset(pp, pp, 0.01 / SCALING_FACTOR);
 
305
    union_(pp, retval, true);
 
306
}
 
307
 
 
308
void
 
309
TriangleMesh::convex_hull(Polygon* hull)
 
310
{
 
311
    this->require_shared_vertices();
 
312
    Points pp;
 
313
    pp.reserve(this->stl.stats.shared_vertices);
 
314
    for (int i = 0; i < this->stl.stats.shared_vertices; i++) {
 
315
        stl_vertex* v = &this->stl.v_shared[i];
 
316
        pp.push_back(Point(v->x / SCALING_FACTOR, v->y / SCALING_FACTOR));
 
317
    }
 
318
    Slic3r::Geometry::convex_hull(pp, hull);
 
319
}
 
320
 
 
321
void
 
322
TriangleMesh::bounding_box(BoundingBoxf3* bb) const
 
323
{
 
324
    bb->min.x = this->stl.stats.min.x;
 
325
    bb->min.y = this->stl.stats.min.y;
 
326
    bb->min.z = this->stl.stats.min.z;
 
327
    bb->max.x = this->stl.stats.max.x;
 
328
    bb->max.y = this->stl.stats.max.y;
 
329
    bb->max.z = this->stl.stats.max.z;
 
330
}
 
331
 
 
332
void
 
333
TriangleMesh::require_shared_vertices()
 
334
{
 
335
    if (!this->repaired) this->repair();
 
336
    if (this->stl.v_shared == NULL) stl_generate_shared_vertices(&(this->stl));
 
337
}
 
338
 
 
339
#ifdef SLIC3RXS
 
340
 
 
341
REGISTER_CLASS(TriangleMesh, "TriangleMesh");
 
342
 
 
343
SV*
 
344
TriangleMesh::to_SV() {
 
345
    SV* sv = newSV(0);
 
346
    sv_setref_pv( sv, perl_class_name(this), (void*)this );
 
347
    return sv;
 
348
}
 
349
 
 
350
void TriangleMesh::ReadFromPerl(SV* vertices, SV* facets)
 
351
{
 
352
    stl.stats.type = inmemory;
 
353
    
 
354
    // count facets and allocate memory
 
355
    AV* facets_av = (AV*)SvRV(facets);
 
356
    stl.stats.number_of_facets = av_len(facets_av)+1;
 
357
    stl.stats.original_num_facets = stl.stats.number_of_facets;
 
358
    stl_allocate(&stl);
 
359
    
 
360
    // read geometry
 
361
    AV* vertices_av = (AV*)SvRV(vertices);
 
362
    for (unsigned int i = 0; i < stl.stats.number_of_facets; i++) {
 
363
        AV* facet_av = (AV*)SvRV(*av_fetch(facets_av, i, 0));
 
364
        stl_facet facet;
 
365
        facet.normal.x = 0;
 
366
        facet.normal.y = 0;
 
367
        facet.normal.z = 0;
 
368
        for (unsigned int v = 0; v <= 2; v++) {
 
369
            AV* vertex_av = (AV*)SvRV(*av_fetch(vertices_av, SvIV(*av_fetch(facet_av, v, 0)), 0));
 
370
            facet.vertex[v].x = SvNV(*av_fetch(vertex_av, 0, 0));
 
371
            facet.vertex[v].y = SvNV(*av_fetch(vertex_av, 1, 0));
 
372
            facet.vertex[v].z = SvNV(*av_fetch(vertex_av, 2, 0));
 
373
        }
 
374
        facet.extra[0] = 0;
 
375
        facet.extra[1] = 0;
 
376
        
 
377
        stl.facet_start[i] = facet;
 
378
    }
 
379
    
 
380
    stl_get_size(&(this->stl));
 
381
}
 
382
#endif
 
383
 
 
384
void
 
385
TriangleMeshSlicer::slice(const std::vector<float> &z, std::vector<Polygons>* layers)
 
386
{
 
387
    /*
 
388
       This method gets called with a list of unscaled Z coordinates and outputs
 
389
       a vector pointer having the same number of items as the original list.
 
390
       Each item is a vector of polygons created by slicing our mesh at the 
 
391
       given heights.
 
392
       
 
393
       This method should basically combine the behavior of the existing
 
394
       Perl methods defined in lib/Slic3r/TriangleMesh.pm:
 
395
       
 
396
       - analyze(): this creates the 'facets_edges' and the 'edges_facets'
 
397
            tables (we don't need the 'edges' table)
 
398
       
 
399
       - slice_facet(): this has to be done for each facet. It generates 
 
400
            intersection lines with each plane identified by the Z list.
 
401
            The get_layer_range() binary search used to identify the Z range
 
402
            of the facet is already ported to C++ (see Object.xsp)
 
403
       
 
404
       - make_loops(): this has to be done for each layer. It creates polygons
 
405
            from the lines generated by the previous step.
 
406
        
 
407
        At the end, we free the tables generated by analyze() as we don't 
 
408
        need them anymore.
 
409
        FUTURE: parallelize slice_facet() and make_loops()
 
410
        
 
411
        NOTE: this method accepts a vector of floats because the mesh coordinate
 
412
        type is float.
 
413
    */
 
414
    
 
415
    std::vector<IntersectionLines> lines(z.size());
 
416
    
 
417
    for (int facet_idx = 0; facet_idx < this->mesh->stl.stats.number_of_facets; facet_idx++) {
 
418
        stl_facet* facet = &this->mesh->stl.facet_start[facet_idx];
 
419
        
 
420
        // find facet extents
 
421
        float min_z = fminf(facet->vertex[0].z, fminf(facet->vertex[1].z, facet->vertex[2].z));
 
422
        float max_z = fmaxf(facet->vertex[0].z, fmaxf(facet->vertex[1].z, facet->vertex[2].z));
 
423
        
 
424
        #ifdef SLIC3R_DEBUG
 
425
        printf("\n==> FACET %d (%f,%f,%f - %f,%f,%f - %f,%f,%f):\n", facet_idx,
 
426
            facet->vertex[0].x, facet->vertex[0].y, facet->vertex[0].z,
 
427
            facet->vertex[1].x, facet->vertex[1].y, facet->vertex[1].z,
 
428
            facet->vertex[2].x, facet->vertex[2].y, facet->vertex[2].z);
 
429
        printf("z: min = %.2f, max = %.2f\n", min_z, max_z);
 
430
        #endif
 
431
        
 
432
        // find layer extents
 
433
        std::vector<float>::const_iterator min_layer, max_layer;
 
434
        min_layer = std::lower_bound(z.begin(), z.end(), min_z); // first layer whose slice_z is >= min_z
 
435
        max_layer = std::upper_bound(z.begin() + (min_layer - z.begin()), z.end(), max_z) - 1; // last layer whose slice_z is <= max_z
 
436
        #ifdef SLIC3R_DEBUG
 
437
        printf("layers: min = %d, max = %d\n", (int)(min_layer - z.begin()), (int)(max_layer - z.begin()));
 
438
        #endif
 
439
        
 
440
        for (std::vector<float>::const_iterator it = min_layer; it != max_layer + 1; ++it) {
 
441
            std::vector<float>::size_type layer_idx = it - z.begin();
 
442
            this->slice_facet(*it / SCALING_FACTOR, *facet, facet_idx, min_z, max_z, &lines[layer_idx]);
 
443
        }
 
444
    }
 
445
    
 
446
    // v_scaled_shared could be freed here
 
447
    
 
448
    // build loops
 
449
    layers->resize(z.size());
 
450
    for (std::vector<IntersectionLines>::iterator it = lines.begin(); it != lines.end(); ++it) {
 
451
        int layer_idx = it - lines.begin();
 
452
        #ifdef SLIC3R_DEBUG
 
453
        printf("Layer %d:\n", layer_idx);
 
454
        #endif
 
455
        
 
456
        this->make_loops(*it, &(*layers)[layer_idx]);
 
457
    }
 
458
}
 
459
 
 
460
void
 
461
TriangleMeshSlicer::slice(const std::vector<float> &z, std::vector<ExPolygons>* layers)
 
462
{
 
463
    std::vector<Polygons> layers_p;
 
464
    this->slice(z, &layers_p);
 
465
    
 
466
    layers->resize(z.size());
 
467
    for (std::vector<Polygons>::const_iterator loops = layers_p.begin(); loops != layers_p.end(); ++loops) {
 
468
        #ifdef SLIC3R_DEBUG
 
469
        size_t layer_id = loops - layers_p.begin();
 
470
        printf("Layer %zu (slice_z = %.2f): ", layer_id, z[layer_id]);
 
471
        #endif
 
472
        
 
473
        this->make_expolygons(*loops, &(*layers)[ loops - layers_p.begin() ]);
 
474
    }
 
475
}
 
476
 
 
477
void
 
478
TriangleMeshSlicer::slice_facet(float slice_z, const stl_facet &facet, const int &facet_idx, const float &min_z, const float &max_z, std::vector<IntersectionLine>* lines) const
 
479
{
 
480
    std::vector<IntersectionPoint> points;
 
481
    std::vector< std::vector<IntersectionPoint>::size_type > points_on_layer;
 
482
    bool found_horizontal_edge = false;
 
483
    
 
484
    /* reorder vertices so that the first one is the one with lowest Z
 
485
       this is needed to get all intersection lines in a consistent order
 
486
       (external on the right of the line) */
 
487
    int i = 0;
 
488
    if (facet.vertex[1].z == min_z) {
 
489
        // vertex 1 has lowest Z
 
490
        i = 1;
 
491
    } else if (facet.vertex[2].z == min_z) {
 
492
        // vertex 2 has lowest Z
 
493
        i = 2;
 
494
    }
 
495
    for (int j = i; (j-i) < 3; j++) {  // loop through facet edges
 
496
        int edge_id = this->facets_edges[facet_idx][j % 3];
 
497
        int a_id = this->mesh->stl.v_indices[facet_idx].vertex[j % 3];
 
498
        int b_id = this->mesh->stl.v_indices[facet_idx].vertex[(j+1) % 3];
 
499
        stl_vertex* a = &this->v_scaled_shared[a_id];
 
500
        stl_vertex* b = &this->v_scaled_shared[b_id];
 
501
        
 
502
        if (a->z == b->z && a->z == slice_z) {
 
503
            // edge is horizontal and belongs to the current layer
 
504
            
 
505
            /* We assume that this method is never being called for horizontal
 
506
               facets, so no other edge is going to be on this layer. */
 
507
            stl_vertex* v0 = &this->v_scaled_shared[ this->mesh->stl.v_indices[facet_idx].vertex[0] ];
 
508
            stl_vertex* v1 = &this->v_scaled_shared[ this->mesh->stl.v_indices[facet_idx].vertex[1] ];
 
509
            stl_vertex* v2 = &this->v_scaled_shared[ this->mesh->stl.v_indices[facet_idx].vertex[2] ];
 
510
            IntersectionLine line;
 
511
            if (min_z == max_z) {
 
512
                line.edge_type = feHorizontal;
 
513
            } else if (v0->z < slice_z || v1->z < slice_z || v2->z < slice_z) {
 
514
                line.edge_type = feTop;
 
515
                std::swap(a, b);
 
516
                std::swap(a_id, b_id);
 
517
            } else {
 
518
                line.edge_type = feBottom;
 
519
            }
 
520
            line.a.x    = a->x;
 
521
            line.a.y    = a->y;
 
522
            line.b.x    = b->x;
 
523
            line.b.y    = b->y;
 
524
            line.a_id   = a_id;
 
525
            line.b_id   = b_id;
 
526
            lines->push_back(line);
 
527
            
 
528
            found_horizontal_edge = true;
 
529
            
 
530
            // if this is a top or bottom edge, we can stop looping through edges
 
531
            // because we won't find anything interesting
 
532
            
 
533
            if (line.edge_type != feHorizontal) return;
 
534
        } else if (a->z == slice_z) {
 
535
            IntersectionPoint point;
 
536
            point.x         = a->x;
 
537
            point.y         = a->y;
 
538
            point.point_id  = a_id;
 
539
            points.push_back(point);
 
540
            points_on_layer.push_back(points.size()-1);
 
541
        } else if (b->z == slice_z) {
 
542
            IntersectionPoint point;
 
543
            point.x         = b->x;
 
544
            point.y         = b->y;
 
545
            point.point_id  = b_id;
 
546
            points.push_back(point);
 
547
            points_on_layer.push_back(points.size()-1);
 
548
        } else if ((a->z < slice_z && b->z > slice_z) || (b->z < slice_z && a->z > slice_z)) {
 
549
            // edge intersects the current layer; calculate intersection
 
550
            
 
551
            IntersectionPoint point;
 
552
            point.x         = b->x + (a->x - b->x) * (slice_z - b->z) / (a->z - b->z);
 
553
            point.y         = b->y + (a->y - b->y) * (slice_z - b->z) / (a->z - b->z);
 
554
            point.edge_id   = edge_id;
 
555
            points.push_back(point);
 
556
        }
 
557
    }
 
558
    if (found_horizontal_edge) return;
 
559
    
 
560
    if (!points_on_layer.empty()) {
 
561
        // we can't have only one point on layer because each vertex gets detected
 
562
        // twice (once for each edge), and we can't have three points on layer because
 
563
        // we assume this code is not getting called for horizontal facets
 
564
        assert(points_on_layer.size() == 2);
 
565
        assert( points[ points_on_layer[0] ].point_id == points[ points_on_layer[1] ].point_id );
 
566
        if (points.size() < 3) return;  // no intersection point, this is a V-shaped facet tangent to plane
 
567
        points.erase( points.begin() + points_on_layer[1] );
 
568
    }
 
569
    
 
570
    if (!points.empty()) {
 
571
        assert(points.size() == 2); // facets must intersect each plane 0 or 2 times
 
572
        IntersectionLine line;
 
573
        line.a.x        = points[1].x;
 
574
        line.a.y        = points[1].y;
 
575
        line.b.x        = points[0].x;
 
576
        line.b.y        = points[0].y;
 
577
        line.a_id       = points[1].point_id;
 
578
        line.b_id       = points[0].point_id;
 
579
        line.edge_a_id  = points[1].edge_id;
 
580
        line.edge_b_id  = points[0].edge_id;
 
581
        lines->push_back(line);
 
582
        return;
 
583
    }
 
584
}
 
585
 
 
586
void
 
587
TriangleMeshSlicer::make_loops(std::vector<IntersectionLine> &lines, Polygons* loops)
 
588
{
 
589
        
 
590
    /*
 
591
    SVG svg("lines.svg");
 
592
    for (IntersectionLines::iterator line = lines.begin(); line != lines.end(); ++line) {
 
593
            svg.AddLine(*line);
 
594
    }
 
595
    svg.Close();
 
596
    */
 
597
    
 
598
    // remove tangent edges
 
599
    for (IntersectionLines::iterator line = lines.begin(); line != lines.end(); ++line) {
 
600
        if (line->skip || line->edge_type == feNone) continue;
 
601
        
 
602
        /* if the line is a facet edge, find another facet edge
 
603
           having the same endpoints but in reverse order */
 
604
        for (IntersectionLines::iterator line2 = line + 1; line2 != lines.end(); ++line2) {
 
605
            if (line2->skip || line2->edge_type == feNone) continue;
 
606
            
 
607
            // are these facets adjacent? (sharing a common edge on this layer)
 
608
            if (line->a_id == line2->a_id && line->b_id == line2->b_id) {
 
609
                line2->skip = true;
 
610
                
 
611
                /* if they are both oriented upwards or downwards (like a 'V')
 
612
                   then we can remove both edges from this layer since it won't 
 
613
                   affect the sliced shape */
 
614
                /* if one of them is oriented upwards and the other is oriented
 
615
                   downwards, let's only keep one of them (it doesn't matter which
 
616
                   one since all 'top' lines were reversed at slicing) */
 
617
                if (line->edge_type == line2->edge_type) {
 
618
                    line->skip = true;
 
619
                    break;
 
620
                }
 
621
            } else if (line->a_id == line2->b_id && line->b_id == line2->a_id) {
 
622
                /* if this edge joins two horizontal facets, remove both of them */
 
623
                if (line->edge_type == feHorizontal && line2->edge_type == feHorizontal) {
 
624
                    line->skip = true;
 
625
                    line2->skip = true;
 
626
                    break;
 
627
                }
 
628
            }
 
629
        }
 
630
    }
 
631
    
 
632
    // build a map of lines by edge_a_id and a_id
 
633
    std::vector<IntersectionLinePtrs> by_edge_a_id, by_a_id;
 
634
    by_edge_a_id.resize(this->mesh->stl.stats.number_of_facets * 3);
 
635
    by_a_id.resize(this->mesh->stl.stats.shared_vertices);
 
636
    for (IntersectionLines::iterator line = lines.begin(); line != lines.end(); ++line) {
 
637
        if (line->skip) continue;
 
638
        if (line->edge_a_id != -1) by_edge_a_id[line->edge_a_id].push_back(&(*line));
 
639
        if (line->a_id != -1) by_a_id[line->a_id].push_back(&(*line));
 
640
    }
 
641
    
 
642
    CYCLE: while (1) {
 
643
        // take first spare line and start a new loop
 
644
        IntersectionLine* first_line = NULL;
 
645
        for (IntersectionLines::iterator line = lines.begin(); line != lines.end(); ++line) {
 
646
            if (line->skip) continue;
 
647
            first_line = &(*line);
 
648
            break;
 
649
        }
 
650
        if (first_line == NULL) break;
 
651
        first_line->skip = true;
 
652
        IntersectionLinePtrs loop;
 
653
        loop.push_back(first_line);
 
654
        
 
655
        /*
 
656
        printf("first_line edge_a_id = %d, edge_b_id = %d, a_id = %d, b_id = %d, a = %d,%d, b = %d,%d\n", 
 
657
            first_line->edge_a_id, first_line->edge_b_id, first_line->a_id, first_line->b_id,
 
658
            first_line->a.x, first_line->a.y, first_line->b.x, first_line->b.y);
 
659
        */
 
660
        
 
661
        while (1) {
 
662
            // find a line starting where last one finishes
 
663
            IntersectionLine* next_line = NULL;
 
664
            if (loop.back()->edge_b_id != -1) {
 
665
                IntersectionLinePtrs* candidates = &(by_edge_a_id[loop.back()->edge_b_id]);
 
666
                for (IntersectionLinePtrs::iterator lineptr = candidates->begin(); lineptr != candidates->end(); ++lineptr) {
 
667
                    if ((*lineptr)->skip) continue;
 
668
                    next_line = *lineptr;
 
669
                    break;
 
670
                }
 
671
            }
 
672
            if (next_line == NULL && loop.back()->b_id != -1) {
 
673
                IntersectionLinePtrs* candidates = &(by_a_id[loop.back()->b_id]);
 
674
                for (IntersectionLinePtrs::iterator lineptr = candidates->begin(); lineptr != candidates->end(); ++lineptr) {
 
675
                    if ((*lineptr)->skip) continue;
 
676
                    next_line = *lineptr;
 
677
                    break;
 
678
                }
 
679
            }
 
680
            
 
681
            if (next_line == NULL) {
 
682
                // check whether we closed this loop
 
683
                if ((loop.front()->edge_a_id != -1 && loop.front()->edge_a_id == loop.back()->edge_b_id)
 
684
                    || (loop.front()->a_id != -1 && loop.front()->a_id == loop.back()->b_id)) {
 
685
                    // loop is complete
 
686
                    Polygon p;
 
687
                    p.points.reserve(loop.size());
 
688
                    for (IntersectionLinePtrs::iterator lineptr = loop.begin(); lineptr != loop.end(); ++lineptr) {
 
689
                        p.points.push_back((*lineptr)->a);
 
690
                    }
 
691
                    loops->push_back(p);
 
692
                    
 
693
                    #ifdef SLIC3R_DEBUG
 
694
                    printf("  Discovered %s polygon of %d points\n", (p.is_counter_clockwise() ? "ccw" : "cw"), (int)p.points.size());
 
695
                    #endif
 
696
                    
 
697
                    goto CYCLE;
 
698
                }
 
699
                
 
700
                // we can't close this loop!
 
701
                //// push @failed_loops, [@loop];
 
702
                //#ifdef SLIC3R_DEBUG
 
703
                printf("  Unable to close this loop having %d points\n", (int)loop.size());
 
704
                //#endif
 
705
                goto CYCLE;
 
706
            }
 
707
            /*
 
708
            printf("next_line edge_a_id = %d, edge_b_id = %d, a_id = %d, b_id = %d, a = %d,%d, b = %d,%d\n", 
 
709
                next_line->edge_a_id, next_line->edge_b_id, next_line->a_id, next_line->b_id,
 
710
                next_line->a.x, next_line->a.y, next_line->b.x, next_line->b.y);
 
711
            */
 
712
            loop.push_back(next_line);
 
713
            next_line->skip = true;
 
714
        }
 
715
    }
 
716
}
 
717
 
 
718
class _area_comp {
 
719
    public:
 
720
    _area_comp(std::vector<double>* _aa) : abs_area(_aa) {};
 
721
    bool operator() (const size_t &a, const size_t &b) {
 
722
        return (*this->abs_area)[a] > (*this->abs_area)[b];
 
723
    }
 
724
    
 
725
    private:
 
726
    std::vector<double>* abs_area;
 
727
};
 
728
 
 
729
void
 
730
TriangleMeshSlicer::make_expolygons_simple(std::vector<IntersectionLine> &lines, ExPolygons* slices)
 
731
{
 
732
    Polygons loops;
 
733
    this->make_loops(lines, &loops);
 
734
    
 
735
    Polygons cw;
 
736
    for (Polygons::const_iterator loop = loops.begin(); loop != loops.end(); ++loop) {
 
737
        if (loop->area() >= 0) {
 
738
            ExPolygon ex;
 
739
            ex.contour = *loop;
 
740
            slices->push_back(ex);
 
741
        } else {
 
742
            cw.push_back(*loop);
 
743
        }
 
744
    }
 
745
    
 
746
    // assign holes to contours
 
747
    for (Polygons::const_iterator loop = cw.begin(); loop != cw.end(); ++loop) {
 
748
        int slice_idx = -1;
 
749
        double current_contour_area = -1;
 
750
        for (ExPolygons::iterator slice = slices->begin(); slice != slices->end(); ++slice) {
 
751
            if (slice->contour.contains_point(loop->points.front())) {
 
752
                double area = slice->contour.area();
 
753
                if (area < current_contour_area || current_contour_area == -1) {
 
754
                    slice_idx = slice - slices->begin();
 
755
                    current_contour_area = area;
 
756
                }
 
757
            }
 
758
        }
 
759
        (*slices)[slice_idx].holes.push_back(*loop);
 
760
    }
 
761
}
 
762
 
 
763
void
 
764
TriangleMeshSlicer::make_expolygons(const Polygons &loops, ExPolygons* slices)
 
765
{
 
766
    /*
 
767
        Input loops are not suitable for evenodd nor nonzero fill types, as we might get
 
768
        two consecutive concentric loops having the same winding order - and we have to 
 
769
        respect such order. In that case, evenodd would create wrong inversions, and nonzero
 
770
        would ignore holes inside two concentric contours.
 
771
        So we're ordering loops and collapse consecutive concentric loops having the same 
 
772
        winding order.
 
773
        TODO: find a faster algorithm for this, maybe with some sort of binary search.
 
774
        If we computed a "nesting tree" we could also just remove the consecutive loops
 
775
        having the same winding order, and remove the extra one(s) so that we could just
 
776
        supply everything to offset_ex() instead of performing several union/diff calls.
 
777
    
 
778
        we sort by area assuming that the outermost loops have larger area;
 
779
        the previous sorting method, based on $b->contains_point($a->[0]), failed to nest
 
780
        loops correctly in some edge cases when original model had overlapping facets
 
781
    */
 
782
 
 
783
    std::vector<double> area;
 
784
    std::vector<double> abs_area;
 
785
    std::vector<size_t> sorted_area;  // vector of indices
 
786
    for (Polygons::const_iterator loop = loops.begin(); loop != loops.end(); ++loop) {
 
787
        double a = loop->area();
 
788
        area.push_back(a);
 
789
        abs_area.push_back(std::fabs(a));
 
790
        sorted_area.push_back(loop - loops.begin());
 
791
    }
 
792
    
 
793
    std::sort(sorted_area.begin(), sorted_area.end(), _area_comp(&abs_area));  // outer first
 
794
 
 
795
    // we don't perform a safety offset now because it might reverse cw loops
 
796
    Polygons p_slices;
 
797
    for (std::vector<size_t>::const_iterator loop_idx = sorted_area.begin(); loop_idx != sorted_area.end(); ++loop_idx) {
 
798
        /* we rely on the already computed area to determine the winding order
 
799
           of the loops, since the Orientation() function provided by Clipper
 
800
           would do the same, thus repeating the calculation */
 
801
        Polygons::const_iterator loop = loops.begin() + *loop_idx;
 
802
        if (area[*loop_idx] >= 0) {
 
803
            p_slices.push_back(*loop);
 
804
        } else {
 
805
            diff(p_slices, *loop, p_slices);
 
806
        }
 
807
    }
 
808
 
 
809
    // perform a safety offset to merge very close facets (TODO: find test case for this)
 
810
    double safety_offset = scale_(0.0499);
 
811
    ExPolygons ex_slices;
 
812
    offset2_ex(p_slices, ex_slices, +safety_offset, -safety_offset);
 
813
    
 
814
    #ifdef SLIC3R_DEBUG
 
815
    size_t holes_count = 0;
 
816
    for (ExPolygons::const_iterator e = ex_slices.begin(); e != ex_slices.end(); ++e) {
 
817
        holes_count += e->holes.size();
 
818
    }
 
819
    printf("%zu surface(s) having %zu holes detected from %zu polylines\n",
 
820
        ex_slices.size(), holes_count, loops.size());
 
821
    #endif
 
822
    
 
823
    // append to the supplied collection
 
824
    slices->insert(slices->end(), ex_slices.begin(), ex_slices.end());
 
825
}
 
826
 
 
827
void
 
828
TriangleMeshSlicer::make_expolygons(std::vector<IntersectionLine> &lines, ExPolygons* slices)
 
829
{
 
830
    Polygons pp;
 
831
    this->make_loops(lines, &pp);
 
832
    this->make_expolygons(pp, slices);
 
833
}
 
834
 
 
835
void
 
836
TriangleMeshSlicer::cut(float z, TriangleMesh* upper, TriangleMesh* lower)
 
837
{
 
838
    std::vector<IntersectionLine> upper_lines, lower_lines;
 
839
    
 
840
    float scaled_z = scale_(z);
 
841
    for (int facet_idx = 0; facet_idx < this->mesh->stl.stats.number_of_facets; facet_idx++) {
 
842
        stl_facet* facet = &this->mesh->stl.facet_start[facet_idx];
 
843
        
 
844
        // find facet extents
 
845
        float min_z = fminf(facet->vertex[0].z, fminf(facet->vertex[1].z, facet->vertex[2].z));
 
846
        float max_z = fmaxf(facet->vertex[0].z, fmaxf(facet->vertex[1].z, facet->vertex[2].z));
 
847
        
 
848
        // intersect facet with cutting plane
 
849
        std::vector<IntersectionLine> lines;
 
850
        this->slice_facet(scaled_z, *facet, facet_idx, min_z, max_z, &lines);
 
851
        
 
852
        // save intersection lines for generating correct triangulations
 
853
        for (std::vector<IntersectionLine>::iterator it = lines.begin(); it != lines.end(); ++it) {
 
854
            if (it->edge_type == feTop) {
 
855
                lower_lines.push_back(*it);
 
856
            } else if (it->edge_type == feBottom) {
 
857
                upper_lines.push_back(*it);
 
858
            } else if (it->edge_type != feHorizontal) {
 
859
                lower_lines.push_back(*it);
 
860
                upper_lines.push_back(*it);
 
861
            }
 
862
        }
 
863
        
 
864
        if (min_z > z || (min_z == z && max_z > min_z)) {
 
865
            // facet is above the cut plane and does not belong to it
 
866
            if (upper != NULL) stl_add_facet(&upper->stl, facet);
 
867
        } else if (max_z < z || (max_z == z && max_z > min_z)) {
 
868
            // facet is below the cut plane and does not belong to it
 
869
            if (lower != NULL) stl_add_facet(&lower->stl, facet);
 
870
        } else if (min_z < z && max_z > z) {
 
871
            // facet is cut by the slicing plane
 
872
            
 
873
            // look for the vertex on whose side of the slicing plane there are no other vertices
 
874
            int isolated_vertex;
 
875
            if ( (facet->vertex[0].z > z) == (facet->vertex[1].z > z) ) {
 
876
                isolated_vertex = 2;
 
877
            } else if ( (facet->vertex[1].z > z) == (facet->vertex[2].z > z) ) {
 
878
                isolated_vertex = 0;
 
879
            } else {
 
880
                isolated_vertex = 1;
 
881
            }
 
882
            
 
883
            // get vertices starting from the isolated one
 
884
            stl_vertex* v0 = &facet->vertex[isolated_vertex];
 
885
            stl_vertex* v1 = &facet->vertex[(isolated_vertex+1) % 3];
 
886
            stl_vertex* v2 = &facet->vertex[(isolated_vertex+2) % 3];
 
887
            
 
888
            // intersect v0-v1 and v2-v0 with cutting plane and make new vertices
 
889
            stl_vertex v0v1, v2v0;
 
890
            v0v1.x = v1->x + (v0->x - v1->x) * (z - v1->z) / (v0->z - v1->z);
 
891
            v0v1.y = v1->y + (v0->y - v1->y) * (z - v1->z) / (v0->z - v1->z);
 
892
            v0v1.z = z;
 
893
            v2v0.x = v2->x + (v0->x - v2->x) * (z - v2->z) / (v0->z - v2->z);
 
894
            v2v0.y = v2->y + (v0->y - v2->y) * (z - v2->z) / (v0->z - v2->z);
 
895
            v2v0.z = z;
 
896
            
 
897
            // build the triangular facet
 
898
            stl_facet triangle;
 
899
            triangle.normal = facet->normal;
 
900
            triangle.vertex[0] = *v0;
 
901
            triangle.vertex[1] = v0v1;
 
902
            triangle.vertex[2] = v2v0;
 
903
            
 
904
            // build the facets forming a quadrilateral on the other side
 
905
            stl_facet quadrilateral[2];
 
906
            quadrilateral[0].normal = facet->normal;
 
907
            quadrilateral[0].vertex[0] = *v1;
 
908
            quadrilateral[0].vertex[1] = *v2;
 
909
            quadrilateral[0].vertex[2] = v0v1;
 
910
            quadrilateral[1].normal = facet->normal;
 
911
            quadrilateral[1].vertex[0] = *v2;
 
912
            quadrilateral[1].vertex[1] = v2v0;
 
913
            quadrilateral[1].vertex[2] = v0v1;
 
914
            
 
915
            if (v0->z > z) {
 
916
                if (upper != NULL) stl_add_facet(&upper->stl, &triangle);
 
917
                if (lower != NULL) {
 
918
                    stl_add_facet(&lower->stl, &quadrilateral[0]);
 
919
                    stl_add_facet(&lower->stl, &quadrilateral[1]);
 
920
                }
 
921
            } else {
 
922
                if (upper != NULL) {
 
923
                    stl_add_facet(&upper->stl, &quadrilateral[0]);
 
924
                    stl_add_facet(&upper->stl, &quadrilateral[1]);
 
925
                }
 
926
                if (lower != NULL) stl_add_facet(&lower->stl, &triangle);
 
927
            }
 
928
        }
 
929
    }
 
930
    
 
931
    // triangulate holes of upper mesh
 
932
    if (upper != NULL) {
 
933
        // compute shape of section
 
934
        ExPolygons section;
 
935
        this->make_expolygons_simple(upper_lines, &section);
 
936
        
 
937
        // triangulate section
 
938
        Polygons triangles;
 
939
        for (ExPolygons::const_iterator expolygon = section.begin(); expolygon != section.end(); ++expolygon)
 
940
            expolygon->triangulate_p2t(&triangles);
 
941
        
 
942
        // convert triangles to facets and append them to mesh
 
943
        for (Polygons::const_iterator polygon = triangles.begin(); polygon != triangles.end(); ++polygon) {
 
944
            Polygon p = *polygon;
 
945
            p.reverse();
 
946
            stl_facet facet;
 
947
            facet.normal.x = 0;
 
948
            facet.normal.y = 0;
 
949
            facet.normal.z = -1;
 
950
            for (size_t i = 0; i <= 2; ++i) {
 
951
                facet.vertex[i].x = unscale(p.points[i].x);
 
952
                facet.vertex[i].y = unscale(p.points[i].y);
 
953
                facet.vertex[i].z = z;
 
954
            }
 
955
            stl_add_facet(&upper->stl, &facet);
 
956
        }
 
957
    }
 
958
    
 
959
    // triangulate holes of lower mesh
 
960
    if (lower != NULL) {
 
961
        // compute shape of section
 
962
        ExPolygons section;
 
963
        this->make_expolygons_simple(lower_lines, &section);
 
964
        
 
965
        // triangulate section
 
966
        Polygons triangles;
 
967
        for (ExPolygons::const_iterator expolygon = section.begin(); expolygon != section.end(); ++expolygon)
 
968
            expolygon->triangulate_p2t(&triangles);
 
969
        
 
970
        // convert triangles to facets and append them to mesh
 
971
        for (Polygons::const_iterator polygon = triangles.begin(); polygon != triangles.end(); ++polygon) {
 
972
            stl_facet facet;
 
973
            facet.normal.x = 0;
 
974
            facet.normal.y = 0;
 
975
            facet.normal.z = 1;
 
976
            for (size_t i = 0; i <= 2; ++i) {
 
977
                facet.vertex[i].x = unscale(polygon->points[i].x);
 
978
                facet.vertex[i].y = unscale(polygon->points[i].y);
 
979
                facet.vertex[i].z = z;
 
980
            }
 
981
            stl_add_facet(&lower->stl, &facet);
 
982
        }
 
983
    }
 
984
    
 
985
    
 
986
    stl_get_size(&(upper->stl));
 
987
    stl_get_size(&(lower->stl));
 
988
    
 
989
}
 
990
 
 
991
TriangleMeshSlicer::TriangleMeshSlicer(TriangleMesh* _mesh) : mesh(_mesh), v_scaled_shared(NULL)
 
992
{
 
993
    // build a table to map a facet_idx to its three edge indices
 
994
    this->mesh->require_shared_vertices();
 
995
    typedef std::pair<int,int>              t_edge;
 
996
    typedef std::vector<t_edge>             t_edges;  // edge_idx => a_id,b_id
 
997
    typedef std::map<t_edge,int>            t_edges_map;  // a_id,b_id => edge_idx
 
998
    
 
999
    this->facets_edges.resize(this->mesh->stl.stats.number_of_facets);
 
1000
    
 
1001
    {
 
1002
        t_edges edges;
 
1003
        // reserve() instad of resize() because otherwise we couldn't read .size() below to assign edge_idx
 
1004
        edges.reserve(this->mesh->stl.stats.number_of_facets * 3);  // number of edges = number of facets * 3
 
1005
        t_edges_map edges_map;
 
1006
        for (int facet_idx = 0; facet_idx < this->mesh->stl.stats.number_of_facets; facet_idx++) {
 
1007
            this->facets_edges[facet_idx].resize(3);
 
1008
            for (int i = 0; i <= 2; i++) {
 
1009
                int a_id = this->mesh->stl.v_indices[facet_idx].vertex[i];
 
1010
                int b_id = this->mesh->stl.v_indices[facet_idx].vertex[(i+1) % 3];
 
1011
                
 
1012
                int edge_idx;
 
1013
                t_edges_map::const_iterator my_edge = edges_map.find(std::make_pair(b_id,a_id));
 
1014
                if (my_edge != edges_map.end()) {
 
1015
                    edge_idx = my_edge->second;
 
1016
                } else {
 
1017
                    /* admesh can assign the same edge ID to more than two facets (which is 
 
1018
                       still topologically correct), so we have to search for a duplicate of 
 
1019
                       this edge too in case it was already seen in this orientation */
 
1020
                    my_edge = edges_map.find(std::make_pair(a_id,b_id));
 
1021
                    
 
1022
                    if (my_edge != edges_map.end()) {
 
1023
                        edge_idx = my_edge->second;
 
1024
                    } else {
 
1025
                        // edge isn't listed in table, so we insert it
 
1026
                        edge_idx = edges.size();
 
1027
                        edges.push_back(std::make_pair(a_id,b_id));
 
1028
                        edges_map[ edges[edge_idx] ] = edge_idx;
 
1029
                    }
 
1030
                }
 
1031
                this->facets_edges[facet_idx][i] = edge_idx;
 
1032
                
 
1033
                #ifdef SLIC3R_DEBUG
 
1034
                printf("  [facet %d, edge %d] a_id = %d, b_id = %d   --> edge %d\n", facet_idx, i, a_id, b_id, edge_idx);
 
1035
                #endif
 
1036
            }
 
1037
        }
 
1038
    }
 
1039
    
 
1040
    // clone shared vertices coordinates and scale them
 
1041
    this->v_scaled_shared = (stl_vertex*)calloc(this->mesh->stl.stats.shared_vertices, sizeof(stl_vertex));
 
1042
    std::copy(this->mesh->stl.v_shared, this->mesh->stl.v_shared + this->mesh->stl.stats.shared_vertices, this->v_scaled_shared);
 
1043
    for (int i = 0; i < this->mesh->stl.stats.shared_vertices; i++) {
 
1044
        this->v_scaled_shared[i].x /= SCALING_FACTOR;
 
1045
        this->v_scaled_shared[i].y /= SCALING_FACTOR;
 
1046
        this->v_scaled_shared[i].z /= SCALING_FACTOR;
 
1047
    }
 
1048
}
 
1049
 
 
1050
TriangleMeshSlicer::~TriangleMeshSlicer()
 
1051
{
 
1052
    if (this->v_scaled_shared != NULL) free(this->v_scaled_shared);
 
1053
}
 
1054
 
 
1055
}