File size: 16,035 Bytes
985c397 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 | // SPDX-License-Identifier: LGPL-2.1-or-later
/***************************************************************************
* Copyright (c) 2005 Imetric 3D GmbH *
* *
* This file is part of the FreeCAD CAx development system. *
* *
* This library is free software; you can redistribute it and/or *
* modify it under the terms of the GNU Library General Public *
* License as published by the Free Software Foundation; either *
* version 2 of the License, or (at your option) any later version. *
* *
* This library is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU Library General Public License for more details. *
* *
* You should have received a copy of the GNU Library General Public *
* License along with this library; see the file COPYING.LIB. If not, *
* write to the Free Software Foundation, Inc., 59 Temple Place, *
* Suite 330, Boston, MA 02111-1307, USA *
* *
***************************************************************************/
#ifndef MESH_TOPOALGORITHM_H
#define MESH_TOPOALGORITHM_H
#include <map>
#include <vector>
#include "Algorithm.h"
#include "Elements.h"
#include "MeshKernel.h"
namespace MeshCore
{
class AbstractPolygonTriangulator;
struct EdgeCollapse;
/**
* The MeshTopoAlgorithm class provides several algorithms to manipulate a mesh.
* It supports various mesh operations like inserting a new vertex, swapping the
* common edge of two adjacent facets, split a facet, ...
* @author Werner Mayer
*/
class MeshExport MeshTopoAlgorithm
{
public:
// construction/destruction
explicit MeshTopoAlgorithm(MeshKernel& rclM);
~MeshTopoAlgorithm();
MeshTopoAlgorithm(const MeshTopoAlgorithm&) = delete;
MeshTopoAlgorithm(MeshTopoAlgorithm&&) = delete;
MeshTopoAlgorithm& operator=(const MeshTopoAlgorithm&) = delete;
MeshTopoAlgorithm& operator=(MeshTopoAlgorithm&&) = delete;
public:
/** @name Topological Operations */
//@{
/**
* Inserts a new vertex in the given triangle so that is split into three
* triangles. The given point must lie inside the triangle not outside or on
* an edge.
*/
bool InsertVertex(FacetIndex ulFacetPos, const Base::Vector3f& rclPoint);
/**
* This method is provided for convenience. It inserts a new vertex to the
* mesh and tries to swap the common edges of the newly created facets with
* their neighbours.
* Just inserting a new vertex leads to very acute-angled triangles which
* might be problematic for some algorithms. This method tries to swap the
* edges to build more well-formed triangles.
* @see InsertVertex(), ShouldSwapEdge(), SwapEdge().
*/
bool InsertVertexAndSwapEdge(FacetIndex ulFacetPos, const Base::Vector3f& rclPoint, float fMaxAngle);
/**
* Swaps the common edge of two adjacent facets even if the operation might
* be illegal. To be sure that this operation is legal, check either with
* IsSwapEdgeLegal() or ShouldSwapEdge() before.
* An illegal swap edge operation can produce non-manifolds, degenerated
* facets or it might create a fold on the surface, i.e. geometric overlaps
* of several triangles.
*/
void SwapEdge(FacetIndex ulFacetPos, FacetIndex ulNeighbour);
/**
* Splits the common edge of the two adjacent facets with index \a ulFacetPos
* and \a ulNeighbour. The point \a rP must lie inside of one the given facets
* are on the common edge. The two facets get broken into four facets, i.e.
* that two new facets get created. If \a rP is coincident with a corner point
* nothing happens.
*/
bool SplitEdge(FacetIndex ulFacetPos, FacetIndex ulNeighbour, const Base::Vector3f& rP);
/**
* Splits the facet with index \a ulFacetPos on the edge side \a uSide into
* two facets. This side must be an open edge otherwise nothing is done. The
* point \a rP must be near to this edge and must not be coincident with any
* corner vertices of the facet.
*/
bool SplitOpenEdge(FacetIndex ulFacetPos, unsigned short uSide, const Base::Vector3f& rP);
/**
* Splits the facet with index \a ulFacetPos into up to three facets. The points
* \a rP1 and \a rP2 should lie on two different edges of the facet. This method
* splits up the both neighbour facets as well.
* If either \a rP1 or \a rP2 (probably due to a previous call of SplitFacet())
* is coincident with a corner point then the facet is split into two facets.
* If both points are coincident with corner points of this facet nothing is done.
*/
void SplitFacet(FacetIndex ulFacetPos, const Base::Vector3f& rP1, const Base::Vector3f& rP2);
/**
* Collapse a vertex. At the moment only removing inner vertexes referenced
* by three facets is supposrted.
*/
bool CollapseVertex(const VertexCollapse& vc);
/**
* Checks whether a collapse edge operation is legal, that is fulfilled if none of the
* adjacent facets flips its normal. If this operation is legal
* true is returned, false is returned if this operation is illegal.
*/
bool IsCollapseEdgeLegal(const EdgeCollapse& ec) const;
/**
* Collapses the common edge of two adjacent facets. This operation removes
* one common point of the collapsed edge and the facets \a ulFacetPos and
* \a ulNeighbour from the data structure.
* @note If \a ulNeighbour is the neighbour facet on the i-th side of
* \a ulFacetPos then the i-th point is removed whereas i is 0, 1 or 2.
* If the other common point should be removed then CollapseEdge()
* should be invoked with swapped arguments of \a ulFacetPos and
* \a ulNeighbour, i.e. CollapseEdge( \a ulNeighbour, \a ulFacetPos ).
*
* @note The client programmer must make sure that this is a legal operation.
*
* @note This method marks the facets and the point as 'invalid' but does not
* remove them from the mesh structure, i.e. the mesh structure gets into an
* inconsistent stage. To make the structure consistent again Cleanup() should
* be called.
* The reason why this cannot be done automatically is that it would become
* quite slow if a lot of edges should be collapsed.
*
* @note While the mesh structure has invalid elements the client programmer
* must take care not to use such elements.
*/
bool CollapseEdge(FacetIndex ulFacetPos, FacetIndex ulNeighbour);
/**
* Convenience function that passes already all needed information.
*/
bool CollapseEdge(const EdgeCollapse& ec);
/**
* Removes the facet with index \a ulFacetPos and all its neighbour facets.
* The three vertices that are referenced by this facet are replaced by its
* gravity point.
*
* @note The client programmer must make sure that this is a legal operation.
*
* @note This method marks the facets and the point as 'invalid' but does not
* remove them from the mesh structure, i.e. the mesh structure gets into an
* inconsistent stage. To make the structure consistent again Cleanup() should
* be called.
* The reason why this cannot be done automatically is that it would become
* quite slow if a lot of facets should be collapsed.
*
* @note While the mesh structure has invalid elements the client programmer
* must take care not to use such elements.
*/
bool CollapseFacet(FacetIndex ulFacetPos);
//@}
/** @name Topological Optimization */
//@{
/**
* Tries to make a more beautiful mesh by swapping the common edge of two
* adjacent facets where needed.
* \a fMaxAngle is the maximum allowed angle between the normals of two
* adjacent facets to allow swapping the common edge. A too high value might
* result into folds on the surface.
* @note This is a high-level operation and tries to optimize the mesh as a whole.
*/
void OptimizeTopology(float fMaxAngle);
void OptimizeTopology();
/**
* Tries to make a more beautiful mesh by swapping the common edge of two
* adjacent facets where needed. A swap is needed where two adjacent facets
* don't fulfill the Delaunay condition.
*/
void DelaunayFlip(float fMaxAngle);
/**
* Overloaded method DelaunayFlip that doesn't use ShouldSwapEdge to check for
* legal swap edge.
*/
int DelaunayFlip();
/**
* Tries to adjust the edges to the curvature direction with the minimum
* absolute value of maximum and minimum curvature.
* @note This is a high-level operation and tries to optimize the mesh as a
* whole.
*/
void AdjustEdgesToCurvatureDirection();
//@}
/**
* Creates a new triangle with neighbour facet \a ulFacetPos and the vertex
* \a rclPoint whereat it must lie outside the given facet.
* @note The vertex \a rclPoint doesn't necessarily need to be a new vertex
* it can already be part of another triangle but the client programmer must
* make sure that no overlaps are created.
* @note This operation might be useful to close gaps in a mesh.
*/
bool SnapVertex(FacetIndex ulFacetPos, const Base::Vector3f& rP);
/**
* Checks whether a swap edge operation is legal, that is fulfilled if the
* two adjacent facets builds a convex polygon. If this operation is legal
* true is returned, false is returned if this operation is illegal or if
* \a ulFacetPos and \a ulNeighbour are not adjacent facets.
*/
bool IsSwapEdgeLegal(FacetIndex ulFacetPos, FacetIndex ulNeighbour) const;
/**
* Checks whether the swap edge operation is legal and whether it makes
* sense. This operation only makes sense if the maximum angle of both
* facets is decreased and if the angle between the facet normals does
* not exceed \a fMaxAngle.
*/
bool ShouldSwapEdge(FacetIndex ulFacetPos, FacetIndex ulNeighbour, float fMaxAngle) const;
/** Computes a value for the benefit of swapping the edge. */
float SwapEdgeBenefit(FacetIndex f, int e) const;
/**
* Removes all invalid marked elements from the mesh structure.
*/
void Cleanup();
/**
* Removes the degenerated facet at position \a index from the mesh structure.
* A facet is degenerated if its corner points are collinear.
*/
bool RemoveDegeneratedFacet(FacetIndex index);
/**
* Removes the corrupted facet at position \a index from the mesh structure.
* A facet is corrupted if the indices of its corner points are not all different.
*/
bool RemoveCorruptedFacet(FacetIndex index);
/**
* Closes holes in the mesh that consists of up to \a length edges. In case a fit
* needs to be done then the points of the neighbours of \a level rings will be used.
* Holes for which the triangulation failed are returned in \a aFailed.
*/
void FillupHoles(
unsigned long length,
int level,
AbstractPolygonTriangulator&,
std::list<std::vector<PointIndex>>& aFailed
);
/**
* This is an overloaded method provided for convenience. It takes as first argument
* the boundaries which must be filled up.
*/
void FillupHoles(
int level,
AbstractPolygonTriangulator&,
const std::list<std::vector<PointIndex>>& aBorders,
std::list<std::vector<PointIndex>>& aFailed
);
/**
* Find holes which consists of up to \a length edges.
*/
void FindHoles(unsigned long length, std::list<std::vector<PointIndex>>& aBorders) const;
/**
* Find topologic independent components with maximum \a count facets
* and returns an array of the indices.
*/
void FindComponents(unsigned long count, std::vector<FacetIndex>& findIndices);
/**
* Removes topologic independent components with maximum \a count facets.
*/
void RemoveComponents(unsigned long count);
/**
* Harmonizes the normals.
*/
void HarmonizeNormals();
/**
* Flips the normals.
*/
void FlipNormals();
/**
* Caching facility.
*/
void BeginCache();
void EndCache();
private:
/**
* Splits the neighbour facet of \a ulFacetPos on side \a uSide.
*/
void SplitNeighbourFacet(FacetIndex ulFacetPos, unsigned short uFSide, const Base::Vector3f& rPoint);
void SplitFacetOnOneEdge(FacetIndex ulFacetPos, const Base::Vector3f& rP1);
void SplitFacetOnTwoEdges(FacetIndex ulFacetPos, const Base::Vector3f& rP1, const Base::Vector3f& rP2);
void SplitFacet(FacetIndex ulFacetPos, PointIndex P1, PointIndex P2, PointIndex Pn);
void AddFacet(PointIndex P1, PointIndex P2, PointIndex P3);
void AddFacet(PointIndex P1, PointIndex P2, PointIndex P3, FacetIndex N1, FacetIndex N2, FacetIndex N3);
void HarmonizeNeighbours(FacetIndex facet1, FacetIndex facet2);
void HarmonizeNeighbours(const std::vector<FacetIndex>& ulFacets);
/**
* Returns all facets that references the point index \a uPointPos. \a uFacetPos
* is a facet that must reference this point and is added to the list as well.
*/
std::vector<FacetIndex> GetFacetsToPoint(FacetIndex uFacetPos, PointIndex uPointPos) const;
/** \internal */
PointIndex GetOrAddIndex(const MeshPoint& rclPoint);
private:
MeshKernel& _rclMesh;
bool _needsCleanup {false};
struct Vertex_Less
{
bool operator()(const Base::Vector3f& u, const Base::Vector3f& v) const;
};
// cache
using tCache = std::map<Base::Vector3f, PointIndex, Vertex_Less>;
tCache* _cache {nullptr};
};
/**
* The MeshComponents class searches for topologic independent segments of the
* given mesh structure.
*
* @author Werner Mayer
*/
class MeshExport MeshComponents
{
public:
enum TMode
{
OverEdge,
OverPoint
};
explicit MeshComponents(const MeshKernel& rclMesh);
/**
* Searches for 'isles' of the mesh. If \a tMode is \a OverEdge then facets
* sharing the same edge are regarded as connected, if \a tMode is \a OverPoint
* then facets sharing a common point are regarded as connected.
*/
void SearchForComponents(TMode tMode, std::vector<std::vector<FacetIndex>>& aclT) const;
/**
* Does basically the same as the method above escept that only the faces in
* \a aSegment are regarded.
*/
void SearchForComponents(
TMode tMode,
const std::vector<FacetIndex>& aSegment,
std::vector<std::vector<FacetIndex>>& aclT
) const;
protected:
// for sorting of elements
struct CNofFacetsCompare
{
bool operator()(const std::vector<FacetIndex>& rclC1, const std::vector<FacetIndex>& rclC2)
{
return rclC1.size() > rclC2.size();
}
};
private:
const MeshKernel& _rclMesh;
};
} // namespace MeshCore
#endif // MESH_TOPOALGORITHM_H
|