FreeCAD

1
/***************************************************************************
2
 *   Copyright (c) 2005 Imetric 3D GmbH                                    *
3
 *                                                                         *
4
 *   This file is part of the FreeCAD CAx development system.              *
5
 *                                                                         *
6
 *   This library is free software; you can redistribute it and/or         *
7
 *   modify it under the terms of the GNU Library General Public           *
8
 *   License as published by the Free Software Foundation; either          *
9
 *   version 2 of the License, or (at your option) any later version.      *
10
 *                                                                         *
11
 *   This library  is distributed in the hope that it will be useful,      *
12
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
13
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
14
 *   GNU Library General Public License for more details.                  *
15
 *                                                                         *
16
 *   You should have received a copy of the GNU Library General Public     *
17
 *   License along with this library; see the file COPYING.LIB. If not,    *
18
 *   write to the Free Software Foundation, Inc., 59 Temple Place,         *
19
 *   Suite 330, Boston, MA  02111-1307, USA                                *
20
 *                                                                         *
21
 ***************************************************************************/
22

23
#include "PreCompiled.h"
24

25
#ifndef _PreComp_
26
#include <algorithm>
27
#endif
28

29
#include <Base/Exception.h>
30
#include <Base/Sequencer.h>
31

32
#include "Builder.h"
33
#include "Functional.h"
34
#include "MeshKernel.h"
35
#include <QVector>
36

37

38
using namespace MeshCore;
39

40

41
MeshBuilder::MeshBuilder(MeshKernel& kernel)
42
    : _meshKernel(kernel)
43
    , _fSaveTolerance {MeshDefinitions::_fMinPointDistanceD1}
44
{}
45

46
MeshBuilder::~MeshBuilder()
47
{
48
    MeshDefinitions::_fMinPointDistanceD1 = _fSaveTolerance;
49
    delete this->_seq;
50
}
51

52
void MeshBuilder::SetTolerance(float fTol)
53
{
54
    MeshDefinitions::_fMinPointDistanceD1 = fTol;
55
}
56

57
void MeshBuilder::Initialize(size_t ctFacets, bool deletion)
58
{
59
    if (deletion) {
60
        // Clear the mesh structure and free all memory
61
        _meshKernel.Clear();
62

63
        // Allocate new memory that is needed later on. If AddFacet() gets called exactly ctFacets
64
        // times there is no wastage of memory otherwise the vector reallocates ~50% of its future
65
        // memory usage. Note: A feature of the std::vector implementation is that it can hold more
66
        // memory (capacity) than it actually needs (size).
67
        //       This usually happens if its elements are added without specifying its final size.
68
        //       Later on it's a bit tricky to free the wasted memory. So we're strived to avoid the
69
        //       wastage of memory.
70
        _meshKernel._aclFacetArray.reserve(ctFacets);
71

72
        // Usually the number of vertices is the half of the number of facets. So we reserve this
73
        // memory with 10% surcharge To save memory we hold an array with iterators that point to
74
        // the right vertex (insertion order) in the set, instead of holding the vertex array twice.
75
        size_t ctPoints = ctFacets / 2;
76
        _pointsIterator.reserve(static_cast<size_t>(float(ctPoints) * 1.10f));
77
        _ptIdx = 0;
78
    }
79
    else {
80
        for (const auto& it1 : _meshKernel._aclPointArray) {
81
            MeshPointIterator pit = _points.insert(it1);
82
            _pointsIterator.push_back(pit);
83
        }
84
        _ptIdx = _points.size();
85

86
        // As we have a copy of our vertices in the set we must clear them from our array now  But
87
        // we can keep its memory as we reuse it later on anyway.
88
        _meshKernel._aclPointArray.clear();
89
        // additional memory
90
        size_t newCtFacets = _meshKernel._aclFacetArray.size() + ctFacets;
91
        _meshKernel._aclFacetArray.reserve(newCtFacets);
92
        size_t ctPoints = newCtFacets / 2;
93
        _pointsIterator.reserve(static_cast<size_t>(float(ctPoints) * 1.10f));
94
    }
95

96
    this->_seq = new Base::SequencerLauncher("create mesh structure...", ctFacets * 2);
97
}
98

99
void MeshBuilder::AddFacet(const MeshGeomFacet& facet, bool takeFlag, bool takeProperty)
100
{
101
    unsigned char flag = 0;
102
    unsigned long prop = 0;
103
    if (takeFlag) {
104
        flag = facet._ucFlag;
105
    }
106
    if (takeProperty) {
107
        prop = facet._ulProp;
108
    }
109

110
    AddFacet(facet._aclPoints[0],
111
             facet._aclPoints[1],
112
             facet._aclPoints[2],
113
             facet.GetNormal(),
114
             flag,
115
             prop);
116
}
117

118
void MeshBuilder::AddFacet(const Base::Vector3f& pt1,
119
                           const Base::Vector3f& pt2,
120
                           const Base::Vector3f& pt3,
121
                           const Base::Vector3f& normal,
122
                           unsigned char flag,
123
                           unsigned long prop)
124
{
125
    Base::Vector3f facetPoints[4] = {pt1, pt2, pt3, normal};
126
    AddFacet(facetPoints, flag, prop);
127
}
128

129
void MeshBuilder::AddFacet(Base::Vector3f* facetPoints, unsigned char flag, unsigned long prop)
130
{
131
    this->_seq->next(true);  // allow to cancel
132

133
    // adjust circulation direction
134
    if ((((facetPoints[1] - facetPoints[0]) % (facetPoints[2] - facetPoints[0])) * facetPoints[3])
135
        < 0.0f) {
136
        std::swap(facetPoints[1], facetPoints[2]);
137
    }
138

139
    MeshFacet mf;
140
    mf._ucFlag = flag;
141
    mf._ulProp = prop;
142

143
    int i = 0;
144
    for (i = 0; i < 3; i++) {
145
        MeshPoint pt(facetPoints[i]);
146
        std::set<MeshPoint>::iterator p = _points.find(pt);
147
        if (p == _points.end()) {
148
            mf._aulPoints[i] = _ptIdx;
149
            pt._ulProp = _ptIdx++;
150
            // keep an iterator to the right vertex
151
            MeshPointIterator it = _points.insert(pt);
152
            _pointsIterator.push_back(it);
153
        }
154
        else {
155
            mf._aulPoints[i] = p->_ulProp;
156
        }
157
    }
158

159
    // check for degenerated facet (one edge has length 0)
160
    if ((mf._aulPoints[0] == mf._aulPoints[1]) || (mf._aulPoints[0] == mf._aulPoints[2])
161
        || (mf._aulPoints[1] == mf._aulPoints[2])) {
162
        return;
163
    }
164

165
    _meshKernel._aclFacetArray.push_back(mf);
166
}
167

168
void MeshBuilder::SetNeighbourhood()
169
{
170
    std::set<Edge> edges;
171
    FacetIndex facetIdx = 0;
172

173
    for (auto& mf : _meshKernel._aclFacetArray) {
174
        this->_seq->next(true);  // allow to cancel
175
        for (int i = 0; i < 3; i++) {
176
            Edge edge(mf._aulPoints[i], mf._aulPoints[(i + 1) % 3], facetIdx);
177
            std::set<Edge>::iterator e = edges.find(edge);
178
            if (e != edges.end()) {  // edge exists, set neighbourhood
179
                MeshFacet& mf1 = _meshKernel._aclFacetArray[e->facetIdx];
180
                if (mf1._aulPoints[0] == edge.pt1) {
181
                    if (mf1._aulPoints[1] == edge.pt2) {
182
                        mf1._aulNeighbours[0] = facetIdx;
183
                    }
184
                    else {
185
                        mf1._aulNeighbours[2] = facetIdx;
186
                    }
187
                }
188
                else if (mf1._aulPoints[0] == edge.pt2) {
189
                    if (mf1._aulPoints[1] == edge.pt1) {
190
                        mf1._aulNeighbours[0] = facetIdx;
191
                    }
192
                    else {
193
                        mf1._aulNeighbours[2] = facetIdx;
194
                    }
195
                }
196
                else {
197
                    mf1._aulNeighbours[1] = facetIdx;
198
                }
199

200
                mf._aulNeighbours[i] = e->facetIdx;
201
            }
202
            else {  // new edge
203
                edges.insert(edge);
204
            }
205
        }
206

207
        facetIdx++;
208
    }
209
}
210

211
void MeshBuilder::RemoveUnreferencedPoints()
212
{
213
    _meshKernel._aclPointArray.SetFlag(MeshPoint::INVALID);
214
    for (const auto& it : _meshKernel._aclFacetArray) {
215
        for (PointIndex point : it._aulPoints) {
216
            _meshKernel._aclPointArray[point].ResetInvalid();
217
        }
218
    }
219

220
    unsigned long uValidPts = std::count_if(_meshKernel._aclPointArray.begin(),
221
                                            _meshKernel._aclPointArray.end(),
222
                                            [](const MeshPoint& p) {
223
                                                return p.IsValid();
224
                                            });
225
    if (uValidPts < _meshKernel.CountPoints()) {
226
        _meshKernel.RemoveInvalids();
227
    }
228
}
229

230
void MeshBuilder::Finish(bool freeMemory)
231
{
232
    // now we can resize the vertex array to the exact size and copy the vertices with their correct
233
    // positions in the array
234
    PointIndex i = 0;
235
    _meshKernel._aclPointArray.resize(_pointsIterator.size());
236
    for (const auto& it : _pointsIterator) {
237
        _meshKernel._aclPointArray[i++] = *(it.first);
238
    }
239

240
    // free all memory of the internal structures
241
    // Note: this scope is needed to free memory immediately
242
#if defined(_MSC_VER) && defined(_DEBUG)
243
    // Just do nothing here as it may take a long time when running the debugger
244
#else
245
    {
246
        std::vector<MeshPointIterator>().swap(_pointsIterator);
247
    }
248
#endif
249
    _points.clear();
250

251
    SetNeighbourhood();
252
    RemoveUnreferencedPoints();
253

254
    // if AddFacet() has been called more often (or even less) as specified in Initialize() we have
255
    // a wastage of memory
256
    if (freeMemory) {
257
        size_t cap = _meshKernel._aclFacetArray.capacity();
258
        size_t siz = _meshKernel._aclFacetArray.size();
259
        // wastage of more than 5%
260
        if (cap > siz + siz / 20) {
261
            try {
262
                FacetIndex i = 0;
263
                MeshFacetArray faces(siz);
264
                for (const auto& it : _meshKernel._aclFacetArray) {
265
                    faces[i++] = it;
266
                }
267
                _meshKernel._aclFacetArray.swap(faces);
268
            }
269
            catch (const Base::MemoryException&) {
270
                // sorry, we cannot reduce the memory
271
            }
272
        }
273
    }
274

275
    _meshKernel.RecalcBoundBox();
276
}
277

278
// ----------------------------------------------------------------------------
279

280
struct MeshFastBuilder::Private
281
{
282
    struct Vertex
283
    {
284
        Vertex()
285
            : x(0)
286
            , y(0)
287
            , z(0)
288
            , i(0)
289
        {}
290
        Vertex(float x, float y, float z)
291
            : x(x)
292
            , y(y)
293
            , z(z)
294
            , i(0)
295
        {}
296

297
        float x, y, z;
298
        size_type i;
299

300
        bool operator!=(const Vertex& rhs) const
301
        {
302
            return x != rhs.x || y != rhs.y || z != rhs.z;
303
        }
304
        bool operator<(const Vertex& rhs) const
305
        {
306
            if (x != rhs.x) {
307
                return x < rhs.x;
308
            }
309
            else if (y != rhs.y) {
310
                return y < rhs.y;
311
            }
312
            else if (z != rhs.z) {
313
                return z < rhs.z;
314
            }
315
            else {
316
                return false;
317
            }
318
        }
319
    };
320

321
    // Hint: Using a QVector instead of std::vector is a bit faster
322
    QVector<Vertex> verts;
323
};
324

325
MeshFastBuilder::MeshFastBuilder(MeshKernel& rclM)
326
    : _meshKernel(rclM)
327
    , p(new Private)
328
{}
329

330
MeshFastBuilder::~MeshFastBuilder()
331
{
332
    delete p;
333
}
334

335
void MeshFastBuilder::Initialize(size_type ctFacets)
336
{
337
    p->verts.reserve(ctFacets * 3);
338
}
339

340
void MeshFastBuilder::AddFacet(const Base::Vector3f* facetPoints)
341
{
342
    Private::Vertex v;
343
    for (int i = 0; i < 3; i++) {
344
        v.x = facetPoints[i].x;
345
        v.y = facetPoints[i].y;
346
        v.z = facetPoints[i].z;
347
        p->verts.push_back(v);
348
    }
349
}
350

351
void MeshFastBuilder::AddFacet(const MeshGeomFacet& facetPoints)
352
{
353
    Private::Vertex v;
354
    for (const auto& pnt : facetPoints._aclPoints) {
355
        v.x = pnt.x;
356
        v.y = pnt.y;
357
        v.z = pnt.z;
358
        p->verts.push_back(v);
359
    }
360
}
361

362
void MeshFastBuilder::Finish()
363
{
364
    using size_type = QVector<Private::Vertex>::size_type;
365
    QVector<Private::Vertex>& verts = p->verts;
366
    size_type ulCtPts = verts.size();
367
    for (size_type i = 0; i < ulCtPts; ++i) {
368
        verts[i].i = i;
369
    }
370

371
    // std::sort(verts.begin(), verts.end());
372
    int threads = int(std::thread::hardware_concurrency());
373
    MeshCore::parallel_sort(verts.begin(), verts.end(), std::less<>(), threads);
374

375
    QVector<FacetIndex> indices(ulCtPts);
376

377
    size_type vertex_count = 0;
378
    for (QVector<Private::Vertex>::iterator v = verts.begin(); v != verts.end(); ++v) {
379
        if (!vertex_count || *v != verts[vertex_count - 1]) {
380
            verts[vertex_count++] = *v;
381
        }
382

383
        indices[v->i] = static_cast<FacetIndex>(vertex_count - 1);
384
    }
385

386
    size_type ulCt = verts.size() / 3;
387
    MeshFacetArray rFacets(static_cast<FacetIndex>(ulCt));
388
    for (size_type i = 0; i < ulCt; ++i) {
389
        rFacets[static_cast<size_t>(i)]._aulPoints[0] = indices[3 * i];
390
        rFacets[static_cast<size_t>(i)]._aulPoints[1] = indices[3 * i + 1];
391
        rFacets[static_cast<size_t>(i)]._aulPoints[2] = indices[3 * i + 2];
392
    }
393

394
    verts.resize(vertex_count);
395

396
    MeshPointArray rPoints;
397
    rPoints.reserve(static_cast<size_t>(vertex_count));
398
    for (const auto& v : verts) {
399
        rPoints.push_back(MeshPoint(v.x, v.y, v.z));
400
    }
401

402
    _meshKernel.Adopt(rPoints, rFacets, true);
403
}
404