FreeCAD

1
/***************************************************************************
2
 *   Copyright (c) 2005 Werner Mayer <wmayer[at]users.sourceforge.net>     *
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
#ifndef _PreComp_
25
#include <algorithm>
26
#include <map>
27
#endif
28

29
#include "Grid.h"
30
#include "Iterator.h"
31
#include "MeshKernel.h"
32
#include "Projection.h"
33

34

35
using namespace MeshCore;
36

37
// ------------------------------------------------------------------------
38

39
MeshProjection::MeshProjection(const MeshKernel& mesh)
40
    : kernel(mesh)
41
{}
42

43
bool MeshProjection::bboxInsideRectangle(const Base::BoundBox3f& bbox,
44
                                         const Base::Vector3f& p1,
45
                                         const Base::Vector3f& p2,
46
                                         const Base::Vector3f& view) const
47
{
48
    Base::Vector3f dir(p2 - p1);
49
    Base::Vector3f base(p1), normal(view % dir);
50
    normal.Normalize();
51

52
    if (bbox.IsCutPlane(base, normal)) {
53
        dir.Normalize();
54
        Base::Vector3f cnt(bbox.GetCenter());
55

56
        return (fabs(cnt.DistanceToPlane(p1, dir)) + fabs(cnt.DistanceToPlane(p2, dir)))
57
            <= (bbox.CalcDiagonalLength() + (p2 - p1).Length());
58
    }
59

60
    return false;
61
}
62

63
bool MeshProjection::isPointInsideDistance(const Base::Vector3f& p1,
64
                                           const Base::Vector3f& p2,
65
                                           const Base::Vector3f& pt) const
66
{
67
    // project point on line
68
    Base::Vector3f proj, dir(p2 - p1);
69
    Base::Vector3f move(pt - p1);
70
    proj.ProjectToLine(move, dir);
71
    proj = pt + proj;
72
    return (((p1 - proj) * (p2 - proj)) < 0.0f);
73
}
74

75
bool MeshProjection::connectLines(std::list<std::pair<Base::Vector3f, Base::Vector3f>>& cutLines,
76
                                  const Base::Vector3f& startPoint,
77
                                  const Base::Vector3f& endPoint,
78
                                  std::vector<Base::Vector3f>& polyline) const
79
{
80
    const float fMaxDist = float(sqrt(FLOAT_MAX));  // max. length of a gap
81
    const float fMinEps = 1.0e-4f;
82

83
    polyline.clear();
84
    polyline.push_back(startPoint);
85

86
    Base::Vector3f curr(startPoint);
87
    while ((curr != endPoint) && (!cutLines.empty())) {
88
        std::list<std::pair<Base::Vector3f, Base::Vector3f>>::iterator it, pCurr = cutLines.end();
89

90
        // get nearest line
91
        float fMin = fMaxDist * fMaxDist;
92

93
        bool bPos = false;
94
        for (it = cutLines.begin(); it != cutLines.end(); ++it) {
95
            float fD1 = Base::DistanceP2(curr, it->first);
96
            float fD2 = Base::DistanceP2(curr, it->second);
97
            if (std::min<float>(fD1, fD2) < fMin) {
98
                pCurr = it;
99
                bPos = fD1 < fD2;
100
                fMin = std::min<float>(fD1, fD2);
101
                if (fMin < fMinEps) {  // abort because next line already found
102
                    break;
103
                }
104
            }
105
        }
106

107
        if (pCurr != cutLines.end()) {
108
            if (bPos) {
109
                if (fMin > fMinEps) {  // gap, insert point
110
                    polyline.push_back(pCurr->first);
111
                }
112
                polyline.push_back(pCurr->second);
113
                curr = pCurr->second;
114
            }
115
            else {
116
                if (fMin > fMinEps) {  // gap, insert point
117
                    polyline.push_back(pCurr->second);
118
                }
119
                polyline.push_back(pCurr->first);
120
                curr = pCurr->first;
121
            }
122
        }
123
        else {
124
            return false;  // abort because no line was found
125
        }
126

127
        cutLines.erase(pCurr);
128
    }
129

130
    return true;
131
}
132

133
bool MeshProjection::projectLineOnMesh(const MeshFacetGrid& grid,
134
                                       const Base::Vector3f& v1,
135
                                       FacetIndex f1,
136
                                       const Base::Vector3f& v2,
137
                                       FacetIndex f2,
138
                                       const Base::Vector3f& vd,
139
                                       std::vector<Base::Vector3f>& polyline)
140
{
141
    Base::Vector3f dir(v2 - v1);
142
    Base::Vector3f base(v1), normal(vd % dir);
143
    normal.Normalize();
144
    dir.Normalize();
145

146

147
    std::vector<FacetIndex> facets;
148

149
    // special case: start and endpoint inside same facet
150
    if (f1 == f2) {
151
        polyline.push_back(v1);
152
        polyline.push_back(v2);
153
        return true;
154
    }
155

156
    // cut all facets between the two endpoints
157
    MeshGridIterator gridIter(grid);
158
    for (gridIter.Init(); gridIter.More(); gridIter.Next()) {
159
        // bbox cuts plane
160
        if (bboxInsideRectangle(gridIter.GetBoundBox(), v1, v2, vd)) {
161
            gridIter.GetElements(facets);
162
        }
163
    }
164

165
    std::sort(facets.begin(), facets.end());
166
    facets.erase(std::unique(facets.begin(), facets.end()), facets.end());
167

168
    // cut all facets with plane
169
    std::list<std::pair<Base::Vector3f, Base::Vector3f>> cutLine;
170
    for (FacetIndex facet : facets) {
171
        Base::Vector3f e1, e2;
172
        MeshGeomFacet tria = kernel.GetFacet(facet);
173
        if (bboxInsideRectangle(tria.GetBoundBox(), v1, v2, vd)) {
174
            if (tria.IntersectWithPlane(base, normal, e1, e2)) {
175
                if ((facet != f1) && (facet != f2)) {
176
                    // inside cut line
177
                    if (!isPointInsideDistance(v1, v2, e1) || !isPointInsideDistance(v1, v2, e2)) {
178
                        continue;
179
                    }
180

181
                    cutLine.emplace_back(e1, e2);
182
                }
183
                else {
184
                    if (facet == f1) {  // start facet
185
                        if (((e2 - v1) * dir) > 0.0f) {
186
                            cutLine.emplace_back(v1, e2);
187
                        }
188
                        else {
189
                            cutLine.emplace_back(v1, e1);
190
                        }
191

192
                        // start = it - facets.begin();
193
                    }
194

195
                    if (facet == f2) {  // end facet
196
                        if (((e2 - v2) * -dir) > 0.0f) {
197
                            cutLine.emplace_back(v2, e2);
198
                        }
199
                        else {
200
                            cutLine.emplace_back(v2, e1);
201
                        }
202

203
                        // end = it - facets.begin();
204
                    }
205
                }
206
            }
207
        }
208
    }
209

210
    return connectLines(cutLine, v1, v2, polyline);
211
}
212