/
gbykov
/
FreeCAD
GigaCode
beta
ОбзорЦентр заботыВойти

FreeCAD

Форк
0
Ветки: 15Коммиты: 36666Теги: 26
FreeCAD
/src
/Mod
/Mesh
/App
/Core
/
Tools.cpp 
356 строк · 12.4 Кб
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 "Tools.h"
30


31


32
using namespace MeshCore;
33


34
MeshSearchNeighbours::MeshSearchNeighbours(const MeshKernel& rclM, float fSampleDistance)
35
    : _rclMesh(rclM)
36
    , _rclFAry(rclM.GetFacets())
37
    , _rclPAry(rclM.GetPoints())
38
    , _clPt2Fa(rclM)
39
    , _fSampleDistance(fSampleDistance)
40
{
41
    MeshAlgorithm(_rclMesh).ResetFacetFlag(MeshFacet::MARKED);
42
    MeshAlgorithm(_rclMesh).ResetPointFlag(MeshPoint::MARKED);
43
}
44


45
void MeshSearchNeighbours::Reinit(float fSampleDistance)
46
{
47
    _fSampleDistance = fSampleDistance;
48
    MeshAlgorithm(_rclMesh).ResetFacetFlag(MeshFacet::MARKED);
49
    MeshAlgorithm(_rclMesh).ResetPointFlag(MeshPoint::MARKED);
50
}
51


52
unsigned long
53
MeshSearchNeighbours::NeighboursFromFacet(FacetIndex ulFacetIdx,
54
                                          float fDistance,
55
                                          unsigned long ulMinPoints,
56
                                          std::vector<Base::Vector3f>& raclResultPoints)
57
{
58
    bool bAddPoints = false;
59


60
    _fMaxDistanceP2 = fDistance * fDistance;
61
    _clCenter = _rclMesh.GetFacet(ulFacetIdx).GetGravityPoint();
62


63
    unsigned long ulVisited = 1;
64
    std::vector<MeshFacetArray::_TConstIterator> aclTestedFacet;
65


66
    _aclResult.clear();
67
    _aclOuter.clear();
68


69
    // add start facet
70
    bool bFound = CheckDistToFacet(_rclFAry[ulFacetIdx]);
71
    _rclFAry[ulFacetIdx].SetFlag(MeshFacet::MARKED);
72
    aclTestedFacet.push_back(_rclFAry.begin() + ulFacetIdx);
73


74
    if (!bFound && (_aclResult.size() < ulMinPoints)) {
75
        bAddPoints = true;
76
        bFound = ExpandRadius(ulMinPoints);
77
    }
78


79
    int nCtExpandRadius = 0;
80
    // search neighbours, add not marked facets, test distance, add outer points
81
    MeshFacetArray::_TConstIterator f_beg = _rclFAry.begin();
82
    while (bFound && (nCtExpandRadius < 10)) {
83
        bFound = false;
84


85
        std::set<PointIndex> aclTmp;
86
        aclTmp.swap(_aclOuter);
87
        for (PointIndex pI : aclTmp) {
88
            const std::set<FacetIndex>& rclISet = _clPt2Fa[pI];
89
            // search all facets hanging on this point
90
            for (FacetIndex pJ : rclISet) {
91
                const MeshFacet& rclF = f_beg[pJ];
92


93
                if (!rclF.IsFlag(MeshFacet::MARKED)) {
94
                    bool bLF = CheckDistToFacet(rclF);
95
                    bFound = bFound || bLF;
96
                    rclF.SetFlag(MeshFacet::MARKED);
97
                    aclTestedFacet.push_back(f_beg + pJ);
98
                }
99
            }
100
            ulVisited += rclISet.size();
101
        }
102


103
        // too few points inside radius found -> expand radius
104
        if (!bFound && (_aclResult.size() < ulMinPoints)) {
105
            nCtExpandRadius++;
106
            bAddPoints = true;
107
            bFound = ExpandRadius(ulMinPoints);
108
        }
109
        else {
110
            nCtExpandRadius = 0;
111
        }
112
    }
113


114
    // reset marked facets, points
115
    for (auto& pF : aclTestedFacet) {
116
        pF->ResetFlag(MeshFacet::MARKED);
117
    }
118
    for (PointIndex pR : _aclResult) {
119
        _rclPAry[pR].ResetFlag(MeshPoint::MARKED);
120
    }
121


122


123
    // copy points in result container
124
    raclResultPoints.resize(_aclResult.size());
125
    size_t i = 0;
126
    for (std::set<PointIndex>::iterator pI = _aclResult.begin(); pI != _aclResult.end();
127
         ++pI, i++) {
128
        raclResultPoints[i] = _rclPAry[*pI];
129
    }
130


131
    if (bAddPoints) {
132
        // sort points, remove points lying furthest from center
133
        std::sort(raclResultPoints.begin(), raclResultPoints.end(), CDistRad(_clCenter));
134
        raclResultPoints.erase(raclResultPoints.begin() + ulMinPoints, raclResultPoints.end());
135
    }
136


137
    return ulVisited;
138
}
139


140
void MeshSearchNeighbours::SampleAllFacets()
141
{
142
    if (_aclSampledFacets.size() == _rclMesh.CountFacets()) {
143
        return;  // already sampled, do nothing
144
    }
145


146
    _aclSampledFacets.resize(_rclMesh.CountFacets());
147
    MeshFacetIterator clFIter(_rclMesh);
148
    size_t i = 0;
149
    for (clFIter.Init(); clFIter.More(); clFIter.Next(), i++) {
150
        std::vector<Base::Vector3f> clPoints;
151
        clFIter->SubSample(_fSampleDistance, clPoints);
152
        _aclSampledFacets[i].resize(clPoints.size());
153
        std::copy(clPoints.begin(), clPoints.end(), _aclSampledFacets[i].begin());
154
    }
155
}
156


157
unsigned long
158
MeshSearchNeighbours::NeighboursFromSampledFacets(FacetIndex ulFacetIdx,
159
                                                  float fDistance,
160
                                                  std::vector<Base::Vector3f>& raclResultPoints)
161
{
162
    SampleAllFacets();
163


164
    _fMaxDistanceP2 = fDistance * fDistance;
165
    _clCenter = _rclMesh.GetFacet(ulFacetIdx).GetGravityPoint();
166


167
    _akSphere.Center = Wm4::Vector3<float>(_clCenter.x, _clCenter.y, _clCenter.z);
168
    _akSphere.Radius = fDistance;
169


170
    unsigned long ulVisited = 1;
171
    std::vector<MeshFacetArray::_TConstIterator> aclTestedFacet;
172


173
    _aclResult.clear();
174
    _aclOuter.clear();
175
    _aclPointsResult.clear();
176


177
    // add start facet
178
    bool bFound = AccumulateNeighbours(_rclFAry[ulFacetIdx], ulFacetIdx);
179
    _rclFAry[ulFacetIdx].SetFlag(MeshFacet::MARKED);
180


181
    // search neighbours, add not marked facets, test distance, add outer points
182
    MeshFacetArray::_TConstIterator f_beg = _rclFAry.begin();
183
    while (bFound) {
184
        bFound = false;
185


186
        std::set<PointIndex> aclTmp;
187
        aclTmp.swap(_aclOuter);
188
        for (PointIndex pI : aclTmp) {
189
            const std::set<FacetIndex>& rclISet = _clPt2Fa[pI];
190
            // search all facets hanging on this point
191
            for (FacetIndex pJ : rclISet) {
192
                const MeshFacet& rclF = f_beg[pJ];
193


194
                if (!rclF.IsFlag(MeshFacet::MARKED)) {
195
                    bool bLF = AccumulateNeighbours(rclF, pJ);
196
                    bFound = bFound || bLF;
197
                    rclF.SetFlag(MeshFacet::MARKED);
198
                    aclTestedFacet.push_back(f_beg + pJ);
199
                }
200
            }
201
            ulVisited += rclISet.size();
202
        }
203
    }
204


205
    // reset marked facets
206
    for (auto& pF : aclTestedFacet) {
207
        pF->ResetFlag(MeshFacet::MARKED);
208
    }
209


210
    // copy points in result container
211
    raclResultPoints.resize(_aclPointsResult.size());
212
    std::copy(_aclPointsResult.begin(), _aclPointsResult.end(), raclResultPoints.begin());
213


214
    // facet points
215
    for (PointIndex pI : _aclResult) {
216
        if (InnerPoint(_rclPAry[pI])) {
217
            raclResultPoints.push_back(_rclPAry[pI]);
218
        }
219
    }
220


221
    return ulVisited;
222
}
223


224
bool MeshSearchNeighbours::AccumulateNeighbours(const MeshFacet& rclF, FacetIndex ulFIdx)
225
{
226
    int k = 0;
227


228
    for (PointIndex ulPIdx : rclF._aulPoints) {
229
        _aclOuter.insert(ulPIdx);
230
        _aclResult.insert(ulPIdx);
231


232
        if (Base::DistanceP2(_clCenter, _rclPAry[ulPIdx]) < _fMaxDistanceP2) {
233
            k++;
234
        }
235
    }
236


237
    bool bFound = false;
238
    if (k == 3) {  // add all sample points
239
        _aclPointsResult.insert(_aclPointsResult.end(),
240
                                _aclSampledFacets[ulFIdx].begin(),
241
                                _aclSampledFacets[ulFIdx].end());
242
        bFound = true;
243
    }
244
    else {  // add points inner radius
245
        bFound = TriangleCutsSphere(rclF);
246


247
        if (bFound) {
248
            const std::vector<Base::Vector3f>& rclT = _aclSampledFacets[ulFIdx];
249
            std::vector<Base::Vector3f> clTmp;
250
            clTmp.reserve(rclT.size());
251
            for (const auto& pI : rclT) {
252
                if (InnerPoint(pI)) {
253
                    clTmp.push_back(pI);
254
                }
255
            }
256
            _aclPointsResult.insert(_aclPointsResult.end(), clTmp.begin(), clTmp.end());
257
        }
258
    }
259


260
    return bFound;
261
}
262


263
bool MeshSearchNeighbours::ExpandRadius(unsigned long ulMinPoints)
264
{
265
    // add facets from current level
266
    _aclResult.insert(_aclOuter.begin(), _aclOuter.end());
267
    for (PointIndex pI : _aclOuter) {
268
        _rclPAry[pI].SetFlag(MeshPoint::MARKED);
269
    }
270


271
    if (_aclResult.size() < ulMinPoints) {
272
        _fMaxDistanceP2 *= float(ulMinPoints) / float(_aclResult.size());
273
        return true;
274
    }
275
    else {
276
        return false;
277
    }
278
}
279


280
unsigned long
281
MeshSearchNeighbours::NeighboursFacetFromFacet(FacetIndex ulFacetIdx,
282
                                               float fDistance,
283
                                               std::vector<Base::Vector3f>& raclResultPoints,
284
                                               std::vector<FacetIndex>& raclResultFacets)
285
{
286
    std::set<FacetIndex> aulFacetSet;
287


288
    _fMaxDistanceP2 = fDistance * fDistance;
289
    _clCenter = _rclMesh.GetFacet(ulFacetIdx).GetGravityPoint();
290


291
    unsigned long ulVisited = 1;
292
    std::vector<MeshFacetArray::_TConstIterator> aclTestedFacet;
293


294
    _aclResult.clear();
295
    _aclOuter.clear();
296


297
    // add start facet
298
    bool bFound = CheckDistToFacet(_rclFAry[ulFacetIdx]);
299
    _rclFAry[ulFacetIdx].SetFlag(MeshFacet::MARKED);
300
    aclTestedFacet.push_back(_rclFAry.begin() + ulFacetIdx);
301


302
    aulFacetSet.insert(ulFacetIdx);
303


304
    // search neighbours, add not marked facets, test distance, add outer points
305
    MeshFacetArray::_TConstIterator f_beg = _rclFAry.begin();
306
    while (bFound) {
307
        bFound = false;
308


309
        std::set<PointIndex> aclTmp;
310
        aclTmp.swap(_aclOuter);
311
        for (PointIndex pI : aclTmp) {
312
            const std::set<FacetIndex>& rclISet = _clPt2Fa[pI];
313
            // search all facets hanging on this point
314
            for (FacetIndex pJ : rclISet) {
315
                const MeshFacet& rclF = f_beg[pJ];
316


317
                for (PointIndex ptIndex : rclF._aulPoints) {
318
                    if (Base::DistanceP2(_clCenter, _rclPAry[ptIndex]) < _fMaxDistanceP2) {
319
                        aulFacetSet.insert(pJ);
320
                        break;
321
                    }
322
                }
323


324
                if (!rclF.IsFlag(MeshFacet::MARKED)) {
325
                    bool bLF = CheckDistToFacet(rclF);
326


327
                    bFound = bFound || bLF;
328
                    rclF.SetFlag(MeshFacet::MARKED);
329
                    aclTestedFacet.push_back(f_beg + pJ);
330
                }
331
            }
332
            ulVisited += rclISet.size();
333
        }
334
    }
335


336
    // reset marked facets, points
337
    for (auto& pF : aclTestedFacet) {
338
        pF->ResetFlag(MeshFacet::MARKED);
339
    }
340
    for (PointIndex pR : _aclResult) {
341
        _rclPAry[pR].ResetFlag(MeshPoint::MARKED);
342
    }
343


344
    // copy points in result container
345
    raclResultPoints.resize(_aclResult.size());
346
    size_t i = 0;
347
    for (std::set<PointIndex>::iterator pI = _aclResult.begin(); pI != _aclResult.end();
348
         ++pI, i++) {
349
        raclResultPoints[i] = _rclPAry[*pI];
350
    }
351


352
    // copy facets in result container
353
    raclResultFacets.insert(raclResultFacets.begin(), aulFacetSet.begin(), aulFacetSet.end());
354


355
    return ulVisited;
356
}
357

Использование cookies

Мы используем файлы cookie в соответствии с Политикой конфиденциальности и Политикой использования cookies.

Нажимая кнопку «Принимаю», Вы даете АО «СберТех» согласие на обработку Ваших персональных данных в целях совершенствования нашего веб-сайта и Сервиса GitVerse, а также повышения удобства их использования.

Запретить использование cookies Вы можете самостоятельно в настройках Вашего браузера.