1
/***************************************************************************
2
* Copyright (c) 2005 Imetric 3D GmbH *
4
* This file is part of the FreeCAD CAx development system. *
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. *
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. *
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 *
21
***************************************************************************/
24
#ifndef MESH_TOPOALGORITHM_H
25
#define MESH_TOPOALGORITHM_H
30
#include "Definitions.h"
32
#include "MeshKernel.h"
35
#include "Algorithm.h"
37
#include <Base/Vector3D.h>
38
#include <Base/Sequencer.h>
41
class AbstractPolygonTriangulator;
44
* The MeshTopoAlgorithm class provides several algorithms to manipulate a mesh.
45
* It supports various mesh operations like inserting a new vertex, swapping the
46
* common edge of two adjacent facets, split a facet, ...
47
* @author Werner Mayer
49
class MeshExport MeshTopoAlgorithm
52
// construction/destruction
53
MeshTopoAlgorithm (MeshKernel &rclM);
54
virtual ~MeshTopoAlgorithm (void);
58
* Inserts a new vertex in the given triangle so that is splitted into three
59
* triangles. The given point must lie inside the triangle not outside or on
62
bool InsertVertex(unsigned long ulFacetPos, const Base::Vector3f& rclPoint);
64
* Creates a new triangle with neighbour facet \a ulFacetPos and the vertex
65
* \a rclPoint whereat it must lie outside the given facet.
66
* @note The vertex \a rclPoint doesn't necessarily need to be a new vertex
67
* it can already be part of another triangle but the client programmer must
68
* make sure that no overlaps are created.
69
* @note This operation might be useful to close gaps in a mesh.
71
bool SnapVertex(unsigned long ulFacetPos, const Base::Vector3f& rP);
73
* Tries to make a more beautiful mesh by swapping the common edge of two
74
* adjacent facets where needed.
75
* \a fMaxAngle is the maximum allowed angle between the normals of two
76
* adjacent facets to allow swapping the common edge. A too high value might
77
* result into folds on the surface.
78
* @note This is a high-level operation and tries to optimze the mesh as a whole.
80
void OptimizeTopology(float fMaxAngle);
82
* Tries to make a more beautiful mesh by swapping the common edge of two
83
* adjacent facets where needed. A swap is needed where to adjacent facets
84
* don't fulfill the Delaunay condition.
86
void DelaunayFlip(float fMaxAngle);
88
* Tries to adjust the edges to the curvature direction with the minimum
89
* absolute value of maximum and minimum curvature.
90
* @note This is a high-level operation and tries to optimze the mesh as a
93
void AdjustEdgesToCurvatureDirection();
95
* This method is provided for convenience. It inserts a new vertex to the
96
* mesh and tries to swap the common edges of the newly created facets with
98
* Just inserting a new vertex leads to very acute-angled triangles which
99
* might be problematic for some algorithms. This method tries to swap the
100
* edges to build more well-formed triangles.
101
* @see InsertVertex(), ShouldSwapEdge(), SwapEdge().
103
bool InsertVertexAndSwapEdge(unsigned long ulFacetPos, const Base::Vector3f& rclPoint,
106
* Checks whether a swap edge operation is legel that is fulfilled if the
107
* two adjacent facets builds a convex polygon. If this operation is legal
108
* true is returned, false is returned if this operation is illegal or if
109
* \a ulFacetPos and \a ulNeighbour are not adjacent facets.
111
bool IsSwapEdgeLegal(unsigned long ulFacetPos, unsigned long ulNeighbour) const;
113
* Checks whether the swap edge operation is legal and whether it makes
114
* sense. This operation only makes sense if the maximum angle of both
115
* facets is decreased and if the angle between the facet normals does
116
* not exceed \a fMaxAngle.
118
bool ShouldSwapEdge(unsigned long ulFacetPos, unsigned long ulNeighbour,
119
float fMaxAngle) const;
121
* Swaps the common edge of two adjacent facets even if the operation might
122
* be illegal. To be sure that this operation is legal check either with
123
* IsSwapEdgeLegal() or ShouldSwapEdge() before.
124
* An illegel swap edge operation can produce non-manifolds, degenrated
125
* facets or it might create a fold on the surface, i.e. geometric overlaps
126
* of several triangles.
128
void SwapEdge(unsigned long ulFacetPos, unsigned long ulNeighbour);
130
* Splits the common edge of the two adjacent facets with index \a ulFacetPos
131
* and \a ulNeighbour. The point \a rP must lie inside of one the given facets
132
* are on the common edge. The two facets get broken into four facets, i.e.
133
* that two new facets get created. If \a rP is coincident with a corner point
136
bool SplitEdge(unsigned long ulFacetPos, unsigned long ulNeighbour,
137
const Base::Vector3f& rP);
139
* Splits the facet with index \a ulFacetPos on the edge side \a uSide into
140
* two facets. This side must be an open edge otherwise nothing is done. The
141
* point \a rP must be near to this edge and must not be coincident with any
142
* corner vertices of the facet.
144
void SplitOpenEdge(unsigned long ulFacetPos, unsigned short uSide,
145
const Base::Vector3f& rP);
147
* Collapses the common edge of two adjacent facets. This operation removes
148
* one common point of the collapsed edge and the facets \a ulFacetPos and
149
* \a ulNeighbour from the data structure.
150
* @note If \a ulNeighbour is the neighbour facet on the i-th side then the
151
* i-th point is removed whereat i is 0, 1 or 2. If the other common point
152
* should be removed then CollapseEdge() should be invoked with transposed
153
* arguments of \a ulFacetPos and \a ulNeighbour, i.e. CollapseEdge
154
* ( \a ulNeighbour, \a ulFacetPos ).
156
* @note The client programmer must make sure that this is a legal operation.
158
* @note This method marks the facets and the point as 'invalid' but does not
159
* remove them from the mesh structure, i.e. the mesh structure gets into an
160
* inconsistent stage. To make the structure consistent again Cleanup() should
162
* The reason why this cannot be done automatically is that it would become
163
* quite slow if a lot of edges should be collapsed.
165
* @note While the mesh structure has invalid elements the client programmer
166
* must take care not to use such elements.
168
bool CollapseEdge(unsigned long ulFacetPos, unsigned long ulNeighbour);
170
* Removes the facet with index \a ulFacetPos and all its neighbour facets.
171
* The three vertices that are referenced by this facet are replaced by its
174
* @note The client programmer must make sure that this is a legal operation.
176
* @note This method marks the facets and the point as 'invalid' but does not
177
* remove them from the mesh structure, i.e. the mesh structure gets into an
178
* inconsistent stage. To make the structure consistent again Cleanup() should
180
* The reason why this cannot be done automatically is that it would become
181
* quite slow if a lot of edges should be collapsed.
183
* @note While the mesh structure has invalid elements the client programmer
184
* must take care not to use such elements.
186
bool CollapseFacet(unsigned long ulFacetPos);
188
* Removes all invalid marked elements from the mesh structure.
192
* Splits the facet with index \a ulFacetPos into up to three facets. The points
193
* \a rP1 and \a rP2 should lie on two different edges of the facet. This method
194
* splits up the both neighbour facets as well.
195
* If either \a rP1 or \a rP2 (probably due to a previous call of SplitFacet())
196
* is coincident with a corner point then the facet is splitted into two facets.
197
* If both points are coincident with corner points of this facet nothing is done.
199
void SplitFacet(unsigned long ulFacetPos, const Base::Vector3f& rP1,
200
const Base::Vector3f& rP2);
202
* Removes the degenerated facet at position \a index from the mesh structure.
203
* A facet is degenerated if its corner points are collinear.
205
void RemoveDegeneratedFacet(unsigned long index);
207
* Removes the corrupted facet at position \a index from the mesh structure.
208
* A facet is corrupted if the indices of its corner points are not all different.
210
void RemoveCorruptedFacet(unsigned long index);
212
* Fills up holes with maximum \a length vertices. In contrast to the first
213
* algorithm this method uses an algorithm to create a constrained Delaunay
214
* triangulation (CDT) where high quality triangles with a maximum area of
215
* \a fMaxArea are created. This may introduce new vertices into the mesh.
217
* To get a z value for the newly inserted vertices a polynomial fit is
218
* computed which uses the boundary points and the points of \a level
219
* rings around the boundary.
220
* If the polynomial fit fails, poosibly due to too less points the average
221
* plane is used, instead.
223
void FillupHoles(unsigned long length, int level, AbstractPolygonTriangulator&);
225
* This is an overloaded method provided for convenience. It takes as first argument
226
* the boundaries which must be filled up.
228
void FillupHoles(const std::list<std::vector<unsigned long> >& aBorders,
229
int level, AbstractPolygonTriangulator&);
231
* Find topologic independent components with maximum \a count facets
232
* and returns an array of the indices.
234
void FindComponents(unsigned long count, std::vector<unsigned long>& aInds);
236
* Removes topologic independent components with maximum \a count facets.
238
void RemoveComponents(unsigned long count);
240
* Harmonizes the normals.
242
void HarmonizeNormals (void);
246
void FlipNormals (void);
255
* Splits the neighbour facet of \a ulFacetPos on side \a uSide.
257
void SplitNeighbourFacet(unsigned long ulFacetPos, unsigned short uSide,
258
const Base::Vector3f rPoint);
260
* Returns all facets that references the point index \a uPointPos. \a uFacetPos
261
* is a facet that must reference this point and is added to the list as well.
263
std::vector<unsigned long> GetFacetsToPoint(unsigned long uFacetPos,
264
unsigned long uPointPos) const;
266
unsigned long GetOrAddIndex (const MeshPoint &rclPoint);
269
MeshKernel& _rclMesh;
272
struct Vertex_Less : public std::binary_function<const Base::Vector3f&,
273
const Base::Vector3f&, bool>
275
bool operator()(const Base::Vector3f& x, const Base::Vector3f& y) const;
279
typedef std::map<Base::Vector3f,unsigned long,Vertex_Less> tCache;
284
* The MeshComponents class searches for topologic independent segments of the
285
* given mesh structure.
287
* @author Werner Mayer
289
class MeshExport MeshComponents
292
enum TMode {OverEdge, OverPoint};
294
MeshComponents( const MeshKernel& rclMesh );
298
* Searches for 'isles' of the mesh. If \a tMode is \a OverEdge then facets
299
* sharing the same edge are regarded as connected, if \a tMode is \a OverPoint
300
* then facets sharing a common point are regarded as connected.
302
void SearchForComponents(TMode tMode, std::vector<std::vector<unsigned long> >& aclT) const;
305
* Does basically the same as the method above escept that only the faces in
306
* \a aSegment are regarded.
308
void SearchForComponents(TMode tMode, const std::vector<unsigned long>& aSegment,
309
std::vector<std::vector<unsigned long> >& aclT) const;
312
// for sorting of elements
313
struct CNofFacetsCompare : public std::binary_function<const std::vector<unsigned long>&,
314
const std::vector<unsigned long>&, bool>
316
bool operator () (const std::vector<unsigned long> &rclC1,
317
const std::vector<unsigned long> &rclC2)
319
return rclC1.size() > rclC2.size();
323
const MeshKernel& _rclMesh;
326
} // namespace MeshCore
328
#endif // MESH_TOPOALGORITHM_H
added
removed
src/Mod/Mesh/App/Core/TopoAlgorithm.h
