MeshCore::MeshTopoAlgorithm Class Reference

The MeshTopoAlgorithm class provides several algorithms to manipulate a mesh. More...

#include <TopoAlgorithm.h>

Public Member Functions

 MeshTopoAlgorithm (MeshKernel &rclM)
 
virtual ~MeshTopoAlgorithm (void)
 
Topological Operations
bool InsertVertex (unsigned long ulFacetPos, const Base::Vector3f &rclPoint)
 Inserts a new vertex in the given triangle so that is split into three triangles. More...
 
bool InsertVertexAndSwapEdge (unsigned long ulFacetPos, const Base::Vector3f &rclPoint, float fMaxAngle)
 This method is provided for convenience. More...
 
void SwapEdge (unsigned long ulFacetPos, unsigned long ulNeighbour)
 Swaps the common edge of two adjacent facets even if the operation might be illegal. More...
 
bool SplitEdge (unsigned long ulFacetPos, unsigned long ulNeighbour, const Base::Vector3f &rP)
 Splits the common edge of the two adjacent facets with index ulFacetPos and ulNeighbour. More...
 
void SplitOpenEdge (unsigned long ulFacetPos, unsigned short uSide, const Base::Vector3f &rP)
 Splits the facet with index ulFacetPos on the edge side uSide into two facets. More...
 
void SplitFacet (unsigned long ulFacetPos, const Base::Vector3f &rP1, const Base::Vector3f &rP2)
 Splits the facet with index ulFacetPos into up to three facets. More...
 
bool CollapseVertex (const VertexCollapse &vc)
 Collapse a vertex. More...
 
bool IsCollapseEdgeLegal (const EdgeCollapse &ec) const
 Checks whether a collapse edge operation is legal, that is fulfilled if none of the adjacent facets flips its normal. More...
 
bool CollapseEdge (unsigned long ulFacetPos, unsigned long ulNeighbour)
 Collapses the common edge of two adjacent facets. More...
 
bool CollapseEdge (const EdgeCollapse &ec)
 Convenience function that passes already all needed information. More...
 
bool CollapseFacet (unsigned long ulFacetPos)
 Removes the facet with index ulFacetPos and all its neighbour facets. More...
 

Topological Optimization

void OptimizeTopology (float fMaxAngle)
 Tries to make a more beautiful mesh by swapping the common edge of two adjacent facets where needed. More...
 
void OptimizeTopology ()
 
void DelaunayFlip (float fMaxAngle)
 Tries to make a more beautiful mesh by swapping the common edge of two adjacent facets where needed. More...
 
int DelaunayFlip ()
 Overloaded method DelaunayFlip that doesn't use ShouldSwapEdge to check for legal swap edge. More...
 
void AdjustEdgesToCurvatureDirection ()
 Tries to adjust the edges to the curvature direction with the minimum absolute value of maximum and minimum curvature. More...
 
bool SnapVertex (unsigned long ulFacetPos, const Base::Vector3f &rP)
 Creates a new triangle with neighbour facet ulFacetPos and the vertex rclPoint whereat it must lie outside the given facet. More...
 
bool IsSwapEdgeLegal (unsigned long ulFacetPos, unsigned long ulNeighbour) const
 Checks whether a swap edge operation is legal, that is fulfilled if the two adjacent facets builds a convex polygon. More...
 
bool ShouldSwapEdge (unsigned long ulFacetPos, unsigned long ulNeighbour, float fMaxAngle) const
 Checks whether the swap edge operation is legal and whether it makes sense. More...
 
float SwapEdgeBenefit (unsigned long f, int e) const
 Computes a value for the benefit of swapping the edge. More...
 
void Cleanup ()
 Removes all invalid marked elements from the mesh structure. More...
 
void RemoveDegeneratedFacet (unsigned long index)
 Removes the degenerated facet at position index from the mesh structure. More...
 
void RemoveCorruptedFacet (unsigned long index)
 Removes the corrupted facet at position index from the mesh structure. More...
 
void FillupHoles (unsigned long length, int level, AbstractPolygonTriangulator &, std::list< std::vector< unsigned long > > &aFailed)
 Closes holes in the mesh that consists of up to length edges. More...
 
void FillupHoles (int level, AbstractPolygonTriangulator &, const std::list< std::vector< unsigned long > > &aBorders, std::list< std::vector< unsigned long > > &aFailed)
 This is an overloaded method provided for convenience. More...
 
void FindHoles (unsigned long length, std::list< std::vector< unsigned long > > &aBorders) const
 Find holes which consists of up to length edges. More...
 
void FindComponents (unsigned long count, std::vector< unsigned long > &aInds)
 Find topologic independent components with maximum count facets and returns an array of the indices. More...
 
void RemoveComponents (unsigned long count)
 Removes topologic independent components with maximum count facets. More...
 
void HarmonizeNormals (void)
 Harmonizes the normals. More...
 
void FlipNormals (void)
 Flips the normals. More...
 
void BeginCache ()
 Caching facility. More...
 
void EndCache ()
 

Detailed Description

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

Constructor & Destructor Documentation

◆ MeshTopoAlgorithm()

MeshTopoAlgorithm::MeshTopoAlgorithm ( MeshKernel rclM)

◆ ~MeshTopoAlgorithm()

MeshTopoAlgorithm::~MeshTopoAlgorithm ( void  )
virtual

References Cleanup(), and EndCache().

Member Function Documentation

◆ AdjustEdgesToCurvatureDirection()

◆ BeginCache()

void MeshTopoAlgorithm::BeginCache ( )

Caching facility.

◆ Cleanup()

void MeshTopoAlgorithm::Cleanup ( )

◆ CollapseEdge() [1/2]

bool MeshTopoAlgorithm::CollapseEdge ( const EdgeCollapse ec)

Convenience function that passes already all needed information.

References DraftVecUtils::find(), MeshCore::MeshFacet::ReplaceNeighbour(), MeshCore::MeshFacet::SetInvalid(), and MeshCore::MeshFacet::Transpose().

◆ CollapseEdge() [2/2]

bool MeshTopoAlgorithm::CollapseEdge ( unsigned long  ulFacetPos,
unsigned long  ulNeighbour 
)

Collapses the common edge of two adjacent facets.

This operation removes one common point of the collapsed edge and the facets ulFacetPos and ulNeighbour from the data structure.

Note
If ulNeighbour is the neighbour facet on the i-th side of 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 ulFacetPos and ulNeighbour, i.e. CollapseEdge( ulNeighbour, ulFacetPos ).
The client programmer must make sure that this is a legal operation.
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.
While the mesh structure has invalid elements the client programmer must take care not to use such elements.

References MeshCore::MeshFacet::IsValid(), MeshCore::MeshFacet::SetInvalid(), MeshCore::MeshFacet::Side(), and MeshCore::MeshFacet::Transpose().

Referenced by Mesh::MeshObject::collapseEdge(), and MeshCore::MeshRemoveNeedles::Fixup().

◆ CollapseFacet()

bool MeshTopoAlgorithm::CollapseFacet ( unsigned long  ulFacetPos)

Removes the facet with index 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.
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.
While the mesh structure has invalid elements the client programmer must take care not to use such elements.

References MeshCore::MeshFacet::IsValid(), MeshCore::MeshFacet::SetInvalid(), MeshCore::MeshFacet::Side(), and MeshCore::MeshFacet::Transpose().

Referenced by Mesh::MeshObject::collapseFacet(), Mesh::MeshObject::collapseFacets(), Mesh::MeshObject::offsetSpecial2(), and MeshPart::MeshAlgos::offsetSpecial2().

◆ CollapseVertex()

bool MeshTopoAlgorithm::CollapseVertex ( const VertexCollapse vc)

Collapse a vertex.

At the moment only removing inner vertexes referenced by three facets is supposrted.

References DraftVecUtils::find(), MeshCore::MeshFacet::HasPoint(), MeshCore::MeshFacet::ReplaceNeighbour(), MeshCore::MeshFacet::SetInvalid(), and MeshCore::MeshFacet::Transpose().

Referenced by MeshCore::MeshFixMergeFacets::Fixup().

◆ DelaunayFlip() [1/2]

int MeshTopoAlgorithm::DelaunayFlip ( )

◆ DelaunayFlip() [2/2]

void MeshTopoAlgorithm::DelaunayFlip ( float  fMaxAngle)

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.

References Base::DistanceP2(), ShouldSwapEdge(), MeshCore::MeshFacet::Side(), and SwapEdge().

◆ EndCache()

void MeshTopoAlgorithm::EndCache ( )

Referenced by ~MeshTopoAlgorithm().

◆ FillupHoles() [1/2]

void MeshTopoAlgorithm::FillupHoles ( int  level,
AbstractPolygonTriangulator cTria,
const std::list< std::vector< unsigned long > > &  aBorders,
std::list< std::vector< unsigned long > > &  aFailed 
)

This is an overloaded method provided for convenience.

It takes as first argument the boundaries which must be filled up.

References Base::Console(), MeshCore::MeshAlgorithm::FillupHole(), Base::ConsoleSingleton::Log(), and MeshCore::AbstractPolygonTriangulator::NeedsReindexing().

◆ FillupHoles() [2/2]

void MeshTopoAlgorithm::FillupHoles ( unsigned long  length,
int  level,
AbstractPolygonTriangulator cTria,
std::list< std::vector< unsigned long > > &  aFailed 
)

Closes holes in the mesh that consists of up to length edges.

In case a fit needs to be done then the points of the neighbours of level rings will be used. Holes for which the triangulation failed are returned in aFailed.

References MeshCore::MeshAlgorithm::GetMeshBorders(), and MeshCore::MeshAlgorithm::SplitBoundaryLoops().

Referenced by Mesh::MeshObject::fillupHoles().

◆ FindComponents()

void MeshTopoAlgorithm::FindComponents ( unsigned long  count,
std::vector< unsigned long > &  aInds 
)

Find topologic independent components with maximum count facets and returns an array of the indices.

References MeshCore::MeshComponents::OverEdge, and MeshCore::MeshComponents::SearchForComponents().

Referenced by RemoveComponents(), and Mesh::MeshObject::removeComponents().

◆ FindHoles()

void MeshTopoAlgorithm::FindHoles ( unsigned long  length,
std::list< std::vector< unsigned long > > &  aBorders 
) const

Find holes which consists of up to length edges.

References MeshCore::MeshAlgorithm::GetMeshBorders().

◆ FlipNormals()

void MeshTopoAlgorithm::FlipNormals ( void  )

Flips the normals.

Referenced by Mesh::MeshObject::flipNormals().

◆ HarmonizeNormals()

void MeshTopoAlgorithm::HarmonizeNormals ( void  )

◆ InsertVertex()

bool MeshTopoAlgorithm::InsertVertex ( unsigned long  ulFacetPos,
const Base::Vector3f rclPoint 
)

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.

References MeshCore::MeshFacet::ReplaceNeighbour().

Referenced by Mesh::MeshObject::insertVertex(), and InsertVertexAndSwapEdge().

◆ InsertVertexAndSwapEdge()

bool MeshTopoAlgorithm::InsertVertexAndSwapEdge ( unsigned long  ulFacetPos,
const Base::Vector3f rclPoint,
float  fMaxAngle 
)

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 also
InsertVertex(), ShouldSwapEdge(), SwapEdge().

References InsertVertex(), ShouldSwapEdge(), and SwapEdge().

Referenced by Mesh::MeshObject::refine().

◆ IsCollapseEdgeLegal()

bool MeshTopoAlgorithm::IsCollapseEdgeLegal ( const EdgeCollapse ec) const

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.

References MeshCore::MeshGeomFacet::GetNormal().

Referenced by MeshCore::MeshRemoveNeedles::Fixup().

◆ IsSwapEdgeLegal()

bool MeshTopoAlgorithm::IsSwapEdgeLegal ( unsigned long  ulFacetPos,
unsigned long  ulNeighbour 
) const

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 ulFacetPos and ulNeighbour are not adjacent facets.

References MeshCore::MeshGeomFacet::IsDegenerated(), and MeshCore::MeshFacet::Side().

Referenced by AdjustEdgesToCurvatureDirection(), and ShouldSwapEdge().

◆ OptimizeTopology() [1/2]

void MeshTopoAlgorithm::OptimizeTopology ( )

◆ OptimizeTopology() [2/2]

void MeshTopoAlgorithm::OptimizeTopology ( float  fMaxAngle)

Tries to make a more beautiful mesh by swapping the common edge of two adjacent facets where needed.

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.

References ShouldSwapEdge(), MeshCore::MeshFacet::Side(), and SwapEdge().

Referenced by Mesh::MeshObject::optimizeTopology().

◆ RemoveComponents()

void MeshTopoAlgorithm::RemoveComponents ( unsigned long  count)

Removes topologic independent components with maximum count facets.

References FindComponents().

◆ RemoveCorruptedFacet()

void MeshTopoAlgorithm::RemoveCorruptedFacet ( unsigned long  index)

Removes the corrupted facet at position index from the mesh structure.

A facet is corrupted if the indices of its corner points are not all different.

References MeshCore::MeshFacet::ReplaceNeighbour().

Referenced by MeshCore::MeshFixCorruptedFacets::Fixup().

◆ RemoveDegeneratedFacet()

void MeshTopoAlgorithm::RemoveDegeneratedFacet ( unsigned long  index)

Removes the degenerated facet at position index from the mesh structure.

A facet is degenerated if its corner points are collinear.

References MeshCore::MeshFacet::ReplaceNeighbour(), and MeshCore::MeshFacet::Side().

Referenced by MeshCore::MeshFixDegeneratedFacets::Fixup().

◆ ShouldSwapEdge()

bool MeshTopoAlgorithm::ShouldSwapEdge ( unsigned long  ulFacetPos,
unsigned long  ulNeighbour,
float  fMaxAngle 
) 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 fMaxAngle.

References Base::Vector3< _Precision >::GetAngle(), MeshCore::MeshGeomFacet::GetNormal(), IsSwapEdgeLegal(), MeshCore::MeshGeomFacet::MaximumAngle(), and MeshCore::MeshFacet::Side().

Referenced by DelaunayFlip(), MeshCore::MeshFixDeformedFacets::Fixup(), InsertVertexAndSwapEdge(), and OptimizeTopology().

◆ SnapVertex()

bool MeshTopoAlgorithm::SnapVertex ( unsigned long  ulFacetPos,
const Base::Vector3f rP 
)

Creates a new triangle with neighbour facet ulFacetPos and the vertex rclPoint whereat it must lie outside the given facet.

Note
The vertex 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.
This operation might be useful to close gaps in a mesh.

References Base::DistanceP2(), MeshCore::MeshFacet::HasOpenEdge(), Base::Vector3< _Precision >::Length(), and SplitOpenEdge().

Referenced by Mesh::MeshObject::snapVertex().

◆ SplitEdge()

bool MeshTopoAlgorithm::SplitEdge ( unsigned long  ulFacetPos,
unsigned long  ulNeighbour,
const Base::Vector3f rP 
)

Splits the common edge of the two adjacent facets with index ulFacetPos and ulNeighbour.

The point 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 rP is coincident with a corner point nothing happens.

References MeshCore::MeshFacet::Side().

Referenced by Mesh::MeshObject::splitEdge(), and Mesh::MeshObject::splitEdges().

◆ SplitFacet()

void MeshTopoAlgorithm::SplitFacet ( unsigned long  ulFacetPos,
const Base::Vector3f rP1,
const Base::Vector3f rP2 
)

Splits the facet with index ulFacetPos into up to three facets.

The points rP1 and rP2 should lie on two different edges of the facet. This method splits up the both neighbour facets as well. If either rP1 or 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.

References Base::Distance().

Referenced by MeshPart::MeshAlgos::cutByCurve(), and Mesh::MeshObject::splitFacet().

◆ SplitOpenEdge()

void MeshTopoAlgorithm::SplitOpenEdge ( unsigned long  ulFacetPos,
unsigned short  uSide,
const Base::Vector3f rP 
)

Splits the facet with index ulFacetPos on the edge side uSide into two facets.

This side must be an open edge otherwise nothing is done. The point rP must be near to this edge and must not be coincident with any corner vertices of the facet.

Referenced by SnapVertex().

◆ SwapEdge()

void MeshTopoAlgorithm::SwapEdge ( unsigned long  ulFacetPos,
unsigned long  ulNeighbour 
)

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.

References MeshCore::MeshFacet::Side().

Referenced by AdjustEdgesToCurvatureDirection(), DelaunayFlip(), MeshCore::MeshFixCaps::Fixup(), MeshCore::MeshFixDeformedFacets::Fixup(), InsertVertexAndSwapEdge(), OptimizeTopology(), and Mesh::MeshObject::swapEdge().

◆ SwapEdgeBenefit()

float MeshTopoAlgorithm::SwapEdgeBenefit ( unsigned long  f,
int  e 
) const

Computes a value for the benefit of swapping the edge.

Referenced by OptimizeTopology().


The documentation for this class was generated from the following files:
  • Sources/FreeCAD/src/Mod/Mesh/App/Core/TopoAlgorithm.h
  • Sources/FreeCAD/src/Mod/Mesh/App/Core/TopoAlgorithm.cpp