FreeCAD

1
// SPDX-License-Identifier: LGPL-2.1-or-later
2

3
/***************************************************************************
4
 *   Copyright (c) 2024 Werner Mayer <wmayer[at]users.sourceforge.net>     *
5
 *                                                                         *
6
 *   This file is part of FreeCAD.                                         *
7
 *                                                                         *
8
 *   FreeCAD is free software: you can redistribute it and/or modify it    *
9
 *   under the terms of the GNU Lesser General Public License as           *
10
 *   published by the Free Software Foundation, either version 2.1 of the  *
11
 *   License, or (at your option) any later version.                       *
12
 *                                                                         *
13
 *   FreeCAD is distributed in the hope that it will be useful, but        *
14
 *   WITHOUT ANY WARRANTY; without even the implied warranty of            *
15
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU      *
16
 *   Lesser General Public License for more details.                       *
17
 *                                                                         *
18
 *   You should have received a copy of the GNU Lesser General Public      *
19
 *   License along with FreeCAD. If not, see                               *
20
 *   <https://www.gnu.org/licenses/>.                                      *
21
 *                                                                         *
22
 **************************************************************************/
23

24

25
#include "PreCompiled.h"
26
#ifndef _PreComp_
27
#include <algorithm>
28
#include <Precision.hxx>
29
#endif
30

31
#include "BRepMesh.h"
32
#include <Base/Tools.h>
33

34
using namespace Part;
35

36
namespace {
37
struct MeshVertex
38
{
39
    Base::Vector3d p;
40
    std::size_t i = 0;
41

42
    explicit MeshVertex(const Base::Vector3d& p)
43
        : p(p)
44
    {
45
    }
46

47
    Base::Vector3d toPoint() const
48
    {
49
        return p;
50
    }
51

52
    bool operator < (const MeshVertex &v) const
53
    {
54
        if (p.x != v.p.x) {
55
            return p.x < v.p.x;
56
        }
57
        if (p.y != v.p.y) {
58
            return p.y < v.p.y;
59
        }
60
        if (p.z != v.p.z) {
61
            return p.z < v.p.z;
62
        }
63

64
        // points are equal
65
        return false;
66
    }
67
};
68

69
class MergeVertex
70
{
71
public:
72
    using Facet = BRepMesh::Facet;
73

74
    MergeVertex(std::vector<Base::Vector3d> points,
75
                std::vector<Facet> faces,
76
                double tolerance)
77
        : points{std::move(points)}
78
        , faces{std::move(faces)}
79
        , tolerance{tolerance}
80
    {
81
        setDefaultMap();
82
        check();
83
    }
84

85
    bool hasDuplicatedPoints() const
86
    {
87
        return duplicatedPoints > 0;
88
    }
89

90
    void mergeDuplicatedPoints()
91
    {
92
        if (!hasDuplicatedPoints()) {
93
            return;
94
        }
95

96
        redirectPointIndex();
97
        auto degreeMap = getPointDegrees();
98
        decrementPointIndex(degreeMap);
99
        removeUnusedPoints(degreeMap);
100
        reset();
101
    }
102

103
    std::vector<Base::Vector3d> getPoints() const
104
    {
105
        return points;
106
    }
107

108
    std::vector<Facet> getFacets() const
109
    {
110
        return faces;
111
    }
112

113
private:
114
    void setDefaultMap()
115
    {
116
        // by default map point index to itself
117
        mapPointIndex.resize(points.size());
118
        std::generate(mapPointIndex.begin(),
119
                      mapPointIndex.end(),
120
                      Base::iotaGen<std::size_t>(0));
121
    }
122

123
    void reset()
124
    {
125
        mapPointIndex.clear();
126
        duplicatedPoints = 0;
127
    }
128

129
    void check()
130
    {
131
        using VertexIterator = std::vector<Base::Vector3d>::const_iterator;
132

133
        double tol3d = tolerance;
134
        auto vertexLess = [tol3d](const VertexIterator& v1,
135
                                  const VertexIterator& v2)
136
        {
137
            if (fabs(v1->x - v2->x) >= tol3d) {
138
                return v1->x < v2->x;
139
            }
140
            if (fabs(v1->y - v2->y) >= tol3d) {
141
                return v1->y < v2->y;
142
            }
143
            if (fabs(v1->z - v2->z) >= tol3d) {
144
                return v1->z < v2->z;
145
            }
146
            return false;  // points are considered to be equal
147
        };
148
        auto vertexEqual = [&](const VertexIterator& v1,
149
                               const VertexIterator& v2)
150
        {
151
            if (vertexLess(v1, v2)) {
152
                return false;
153
            }
154
            if (vertexLess(v2, v1)) {
155
                return false;
156
            }
157
            return true;
158
        };
159

160
        std::vector<VertexIterator> vertices;
161
        vertices.reserve(points.size());
162
        for (auto it = points.cbegin(); it != points.cend(); ++it) {
163
            vertices.push_back(it);
164
        }
165

166
        std::sort(vertices.begin(), vertices.end(), vertexLess);
167

168
        auto next = vertices.begin();
169
        while (next != vertices.end()) {
170
            next = std::adjacent_find(next, vertices.end(), vertexEqual);
171
            if (next != vertices.end()) {
172
                auto first = next;
173
                std::size_t first_index = *first - points.begin();
174
                ++next;
175
                while (next != vertices.end() && vertexEqual(*first, *next)) {
176
                    std::size_t next_index = *next - points.begin();
177
                    mapPointIndex[next_index] = first_index;
178
                    ++duplicatedPoints;
179
                    ++next;
180
                }
181
            }
182
        }
183
    }
184

185
    void redirectPointIndex()
186
    {
187
        for (auto& face : faces) {
188
            face.I1 = int(mapPointIndex[face.I1]);
189
            face.I2 = int(mapPointIndex[face.I2]);
190
            face.I3 = int(mapPointIndex[face.I3]);
191
        }
192
    }
193

194
    std::vector<std::size_t> getPointDegrees() const
195
    {
196
        std::vector<std::size_t> degreeMap;
197
        degreeMap.resize(points.size());
198
        for (const auto& face : faces) {
199
            degreeMap[face.I1]++;
200
            degreeMap[face.I2]++;
201
            degreeMap[face.I3]++;
202
        }
203

204
        return degreeMap;
205
    }
206

207
    void decrementPointIndex(const std::vector<std::size_t>& degreeMap)
208
    {
209
        std::vector<std::size_t> decrements;
210
        decrements.resize(points.size());
211

212
        std::size_t decr = 0;
213
        for (std::size_t pos = 0; pos < points.size(); pos++) {
214
            decrements[pos] = decr;
215
            if (degreeMap[pos] == 0) {
216
                decr++;
217
            }
218
        }
219

220
        for (auto& face : faces) {
221
            face.I1 -= int(decrements[face.I1]);
222
            face.I2 -= int(decrements[face.I2]);
223
            face.I3 -= int(decrements[face.I3]);
224
        }
225
    }
226

227
    void removeUnusedPoints(const std::vector<std::size_t>& degreeMap)
228
    {
229
        // remove unreferenced points
230
        std::vector<Base::Vector3d> new_points;
231
        new_points.reserve(points.size() - duplicatedPoints);
232
        for (std::size_t pos = 0; pos < points.size(); ++pos) {
233
            if (degreeMap[pos] > 0) {
234
                new_points.push_back(points[pos]);
235
            }
236
        }
237

238
        points.swap(new_points);
239
    }
240

241
private:
242
    std::vector<Base::Vector3d> points;
243
    std::vector<Facet> faces;
244
    double tolerance = 0.0;
245
    std::size_t duplicatedPoints = 0;
246
    std::vector<std::size_t> mapPointIndex;
247
};
248

249
}
250

251
void BRepMesh::getFacesFromDomains(const std::vector<Domain>& domains,
252
                                   std::vector<Base::Vector3d>& points,
253
                                   std::vector<Facet>& faces)
254
{
255
    std::size_t numFaces = 0;
256
    for (const auto& it : domains) {
257
        numFaces += it.facets.size();
258
    }
259
    faces.reserve(numFaces);
260

261
    std::set<MeshVertex> vertices;
262
    auto addVertex = [&vertices](const Base::Vector3d& pnt, uint32_t& pointIndex) {
263
        MeshVertex vertex(pnt);
264
        vertex.i = vertices.size();
265
        auto it = vertices.insert(vertex);
266
        pointIndex = it.first->i;
267
    };
268

269
    for (const auto & domain : domains) {
270
        std::size_t numDomainFaces = 0;
271
        for (const Facet& df : domain.facets) {
272
            Facet face;
273

274
            // 1st vertex
275
            addVertex(domain.points[df.I1], face.I1);
276

277
            // 2nd vertex
278
            addVertex(domain.points[df.I2], face.I2);
279

280
            // 3rd vertex
281
            addVertex(domain.points[df.I3], face.I3);
282

283
            // make sure that we don't insert invalid facets
284
            if (face.I1 != face.I2 &&
285
                face.I2 != face.I3 &&
286
                face.I3 != face.I1) {
287
                faces.push_back(face);
288
                numDomainFaces++;
289
            }
290
        }
291

292
        domainSizes.push_back(numDomainFaces);
293
    }
294

295
    std::vector<Base::Vector3d> meshPoints;
296
    meshPoints.resize(vertices.size());
297
    for (const auto & vertex : vertices) {
298
        meshPoints[vertex.i] = vertex.toPoint();
299
    }
300
    points.swap(meshPoints);
301

302
    MergeVertex merge(points, faces, Precision::Confusion());
303
    if (merge.hasDuplicatedPoints()) {
304
        merge.mergeDuplicatedPoints();
305
        points = merge.getPoints();
306
        faces = merge.getFacets();
307
    }
308
}
309

310
std::vector<BRepMesh::Segment> BRepMesh::createSegments() const
311
{
312
    std::size_t numMeshFaces = 0;
313
    std::vector<Segment> segm;
314
    for (size_t numDomainFaces : domainSizes) {
315
        Segment segment(numDomainFaces);
316
        std::generate(segment.begin(),
317
                      segment.end(),
318
                      Base::iotaGen<std::size_t>(numMeshFaces));
319
        numMeshFaces += numDomainFaces;
320
        segm.push_back(segment);
321
    }
322

323
    return segm;
324
}
325