-// Copyright (C) 2007-2015 CEA/DEN, EDF R&D, OPEN CASCADE
+// Copyright (C) 2007-2020 CEA/DEN, EDF R&D, OPEN CASCADE
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
#include <vector>
#include <NCollection_DataMap.hxx>
+#include <Precision.hxx>
#include <gp_Pnt.hxx>
using namespace SMESH_MeshAlgos;
BNode(const SMDS_MeshNode * node): SMESH_TNodeXYZ( node ) {}
const SMDS_MeshNode * Node() const { return _node; }
- void AddLinked( BEdge* e ) const;
- void AddClose ( const BEdge* e, double u ) const;
+ void AddLinked( BEdge* e ) const;
+ void AddClose ( const BEdge* e, double u ) const;
BEdge* GetCloseEdge( size_t i ) const { return myCloseEdges[i].first; }
double GetCloseU( size_t i ) const { return myCloseEdges[i].second; }
BEdge* GetCloseEdgeOfBorder( int borderID, double * u = 0 ) const;
- bool IsCloseEdge( const BEdge* ) const;
+ bool HasCloseEdgeWithNode( const BNode* n ) const;
+ bool IsCloseEdge( const BEdge*, double * u = 0 ) const;
bool operator<(const BNode& other) const { return Node()->GetID() < other.Node()->GetID(); }
+ double SquareDistance(const BNode& e2) const { return ( e2 - *this ).SquareModulus(); }
};
/*!
* \brief Edge of a free border
myNodes[0] = node1->Node();
myNodes[1] = node2->Node();
myFace = face;
- setId( ID ); // mesh element ID
+ setID( ID ); // mesh element ID
}
bool IsInGroup() const
{
if ( myID < 0 )
{
myID = id;
- if ( myNext )
- myNext->SetID( id + 1 );
+
+ for ( BEdge* be = myNext; be && be->myID < 0; be = be->myNext )
+ {
+ be->myID = ++id;
+ }
}
}
+ //================================================================================
+ /*!
+ * \brief Checks if a point is closer to this BEdge than tol
+ */
+ //================================================================================
+
bool IsOut( const gp_XYZ& point, const double tol, double& u ) const
{
gp_XYZ me = *myBNode2 - *myBNode1;
double dist2 = ( point - proj ).SquareModulus();
return ( dist2 > tol * tol );
}
+ //================================================================================
+ /*!
+ * \brief Checks if two BEdges can be considered as overlapping
+ */
+ //================================================================================
+
bool IsOverlappingProjection( const BEdge* toE, const double u, bool is1st ) const
{
// is1st shows which end of toE is projected on this at u
double u2;
const double eps = 0.1;
- if ( toE == myBNode1->GetCloseEdgeOfBorder( toE->myBorderID, &u2 ) ||
- toE == myBNode2->GetCloseEdgeOfBorder( toE->myBorderID, &u2 ))
+ if ( myBNode1->IsCloseEdge( toE, &u2 ) ||
+ myBNode2->IsCloseEdge( toE, &u2 ))
return (( 0 < u2 && u2 < 1 ) && // u2 is proj param of myBNode's on toE
( Abs( u2 - int( !is1st )) > eps ));
return Abs( u - u2 ) > eps;
return false;
}
+ //================================================================================
+ /*!
+ * \brief Finds all neighbor BEdge's having the same close borders
+ */
+ //================================================================================
+
bool GetRangeOfSameCloseBorders(BEdge* eRange[2], const std::set< int >& bordIDs)
{
if ( this->myCloseBorders != bordIDs )
return false;
- eRange[0] = this;
- while ( eRange[0]->myPrev && eRange[0]->myPrev->myCloseBorders == bordIDs )
+ if ( bordIDs.size() == 1 && bordIDs.count( myBorderID )) // border close to self
{
- if ( eRange[0]->myPrev == this /*|| eRange[0]->myPrev->myInGroup*/ )
- break;
- eRange[0] = eRange[0]->myPrev;
- }
-
- eRange[1] = this;
- if ( eRange[0]->myPrev != this ) // not closed range
- while ( eRange[1]->myNext && eRange[1]->myNext->myCloseBorders == bordIDs )
+ double u;
+ eRange[0] = this;
+ while ( eRange[0]->myBNode1->GetCloseEdgeOfBorder( myBorderID, &u ))
+ {
+ if ( eRange[0]->myPrev == this || u < 0 || u > 1 )
+ break;
+ eRange[0] = eRange[0]->myPrev;
+ }
+ eRange[1] = this;
+ while ( eRange[1]->myBNode2->GetCloseEdgeOfBorder( myBorderID, &u ))
{
- if ( eRange[1]->myNext == this /*|| eRange[1]->myNext->myInGroup*/ )
+ if ( eRange[1]->myNext == this || u < 0 || u > 1 )
break;
eRange[1] = eRange[1]->myNext;
}
+ }
+ else
+ {
+ eRange[0] = this;
+ while ( eRange[0]->myPrev && eRange[0]->myPrev->myCloseBorders == bordIDs )
+ {
+ if ( eRange[0]->myPrev == this )
+ break;
+ eRange[0] = eRange[0]->myPrev;
+ }
+
+ eRange[1] = this;
+ if ( eRange[0]->myPrev != this ) // not closed border
+ while ( eRange[1]->myNext && eRange[1]->myNext->myCloseBorders == bordIDs )
+ {
+ if ( eRange[1]->myNext == this )
+ break;
+ eRange[1] = eRange[1]->myNext;
+ }
+ }
- return ( eRange[0] != eRange[1] );
+ if ( eRange[0] == eRange[1] )
+ {
+ std::set<int>::iterator closeBord = eRange[0]->myCloseBorders.begin();
+ for ( ; closeBord != eRange[0]->myCloseBorders.end(); ++closeBord )
+ {
+ if ( BEdge* be = eRange[0]->myBNode1->GetCloseEdgeOfBorder( *closeBord ))
+ if ( be->myCloseBorders == eRange[0]->myCloseBorders )
+ return true;
+ if ( BEdge* be = eRange[0]->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
+ if ( be->myCloseBorders == eRange[0]->myCloseBorders )
+ return true;
+ }
+ return false;
+ }
+ return true;
}
}; // class BEdge
+ //================================================================================
+ /*!
+ * \brief Checks if all border parts include the whole closed border, and if so
+ * returns \c true and choose starting BEdge's with most coincident nodes
+ */
+ //================================================================================
+
+ bool chooseStartOfClosedBorders( std::vector< BEdge* >& ranges ) // PAL23078#c21002
+ {
+ bool allClosed = true;
+ for ( size_t iR = 1; iR < ranges.size() && allClosed; iR += 2 )
+ allClosed = ( ranges[ iR-1 ]->myPrev == ranges[ iR ] );
+ if ( !allClosed )
+ return allClosed;
+
+ double u, minDiff = Precision::Infinite();
+ std::vector< BEdge* > start( ranges.size() / 2 );
+ BEdge* range0 = start[0] = ranges[0];
+ do
+ {
+ double maxDiffU = 0;
+ double maxDiff = 0;
+ for ( size_t iR = 3; iR < ranges.size(); iR += 2 )
+ {
+ int borderID = ranges[iR]->myBorderID;
+ if ( BEdge* e = start[0]->myBNode1->GetCloseEdgeOfBorder( borderID, & u ))
+ {
+ start[ iR / 2 ] = e;
+ double diffU = Min( Abs( u ), Abs( 1.-u ));
+ double diff = e->myBNode1->SquareDistance( *e->myBNode2 ) * diffU * diffU;
+ maxDiffU = Max( diffU, maxDiffU );
+ maxDiff = Max( diff, maxDiff );
+ }
+ }
+ if ( maxDiff < minDiff )
+ {
+ minDiff = maxDiff;
+ for ( size_t iR = 1; iR < ranges.size(); iR += 2 )
+ {
+ ranges[ iR-1 ] = start[ iR/2 ];
+ ranges[ iR ] = ranges[ iR-1]->myPrev;
+ }
+ }
+ if ( maxDiffU < 1e-6 )
+ break;
+ start[0] = start[0]->myNext;
+ }
+ while ( start[0] != range0 );
+
+ return allClosed;
+ }
+
+ //================================================================================
+ /*!
+ * \brief Tries to include neighbor BEdge's into a border part
+ */
+ //================================================================================
+
void extendPart( BEdge* & e1, BEdge* & e2, const std::set< int >& bordIDs, int groupID )
{
if (( e1->myPrev == e2 ) ||
if ( e1->myPrev )
{
for ( bord = bordIDs.begin(); bord != bordIDs.end(); ++bord )
- if (( *bord != e1->myBorderID ) &&
- (( be = e1->myBNode1->GetCloseEdgeOfBorder( *bord, &u ))) &&
+ if ((( be = e1->myBNode1->GetCloseEdgeOfBorder( *bord, &u ))) &&
( be->myInGroup == groupID ) &&
( 0 < u && u < 1 ) &&
( be->IsOverlappingProjection( e1->myPrev, u, false )))
e1 = e1->myPrev;
break;
}
+ if ( bord == bordIDs.end() && // not extended
+ e1->myBNode1->HasCloseEdgeWithNode( e1->myPrev->myBNode1 ))
+ {
+ e1 = e1->myPrev;
+ }
+ e1->myInGroup = groupID;
}
if ( e2->myNext )
{
for ( bord = bordIDs.begin(); bord != bordIDs.end(); ++bord )
- if (( *bord != e2->myBorderID ) &&
- (( be = e2->myBNode2->GetCloseEdgeOfBorder( *bord, &u ))) &&
+ if ((( be = e2->myBNode2->GetCloseEdgeOfBorder( *bord, &u ))) &&
( be->myInGroup == groupID ) &&
( 0 < u && u < 1 ) &&
( be->IsOverlappingProjection( e2->myNext, u, true )))
e2 = e2->myNext;
break;
}
+ if ( bord == bordIDs.end() && // not extended
+ e2->myBNode2->HasCloseEdgeWithNode( e2->myNext->myBNode2 ))
+ {
+ e2 = e2->myNext;
+ }
+ e2->myInGroup = groupID;
}
}
+ //================================================================================
+ /*!
+ * \brief Connect BEdge's incident at this node
+ */
+ //================================================================================
+
void BNode::AddLinked( BEdge* e ) const
{
myLinkedEdges.reserve(2);
void BNode::AddClose ( const BEdge* e, double u ) const
{
if ( ! e->Contains( this ))
- myCloseEdges.push_back( make_pair( const_cast< BEdge* >( e ), u ));
+ myCloseEdges.push_back( std::make_pair( const_cast< BEdge* >( e ), u ));
}
BEdge* BNode::GetCloseEdgeOfBorder( int borderID, double * uPtr ) const
{
if ( uPtr ) *uPtr = u;
return e;
}
- bool BNode::IsCloseEdge( const BEdge* e ) const
+ bool BNode::HasCloseEdgeWithNode( const BNode* n ) const
+ {
+ for ( size_t i = 0; i < myCloseEdges.size(); ++i )
+ if ( GetCloseEdge( i )->Contains( n ) &&
+ 0 < GetCloseU( i ) && GetCloseU( i ) < 1 )
+ return true;
+ return false;
+ }
+ bool BNode::IsCloseEdge( const BEdge* e, double * uPtr ) const
{
for ( size_t i = 0; i < myCloseEdges.size(); ++i )
if ( e == GetCloseEdge( i ) )
+ {
+ if ( uPtr ) *uPtr = GetCloseU( i );
return true;
+ }
return false;
}
} // namespace
-// struct needed for NCollection_Map
-struct TLinkHasher
-{
- static int HashCode(const SMESH_TLink& link, int aLimit)
- {
- return ::HashCode( link.node1()->GetID() + link.node2()->GetID(), aLimit );
- }
- static Standard_Boolean IsEqual(const SMESH_TLink& l1, const SMESH_TLink& l2)
- {
- return ( l1.node1() == l2.node1() && l1.node2() == l2.node2() );
- }
-};
-
//================================================================================
/*
* Returns groups of TFreeBorder's coincident within the given tolerance.
CoincidentFreeBorders & foundFreeBordes)
{
// find free links
- typedef NCollection_DataMap<SMESH_TLink, const SMDS_MeshElement*, TLinkHasher > TLink2FaceMap;
+ typedef NCollection_DataMap<SMESH_TLink, const SMDS_MeshElement*, SMESH_TLink > TLink2FaceMap;
TLink2FaceMap linkMap;
+ int nbSharedLinks = 0;
SMDS_FaceIteratorPtr faceIt = mesh.facesIterator();
while ( faceIt->more() )
{
{
const SMDS_MeshNode* n1 = nodeIt->next();
SMESH_TLink link( n0, n1 );
- if ( !linkMap.Bind( link, face ))
- linkMap.UnBind( link );
+ if ( const SMDS_MeshElement** faceInMap = linkMap.ChangeSeek( link ))
+ {
+ nbSharedLinks += bool( *faceInMap );
+ *faceInMap = 0;
+ }
+ else
+ {
+ linkMap.Bind( link, face );
+ }
n0 = n1;
}
}
- if ( linkMap.IsEmpty() )
+ if ( linkMap.Extent() == nbSharedLinks )
return;
// form free borders
std::set < BNode > bNodes;
- std::vector< BEdge > bEdges( linkMap.Extent() );
+ std::vector< BEdge > bEdges( linkMap.Extent() - nbSharedLinks );
TLink2FaceMap::Iterator linkIt( linkMap );
- for ( int iEdge = 0; linkIt.More(); linkIt.Next(), ++iEdge )
+ for ( int iEdge = 0; linkIt.More(); linkIt.Next() )
{
+ if ( !linkIt.Value() ) continue;
const SMESH_TLink & link = linkIt.Key();
std::set< BNode >::iterator n1 = bNodes.insert( BNode( link.node1() )).first;
std::set< BNode >::iterator n2 = bNodes.insert( BNode( link.node2() )).first;
bEdges[ iEdge ].Set( &*n1, &*n2, linkIt.Value(), iEdge+1 );
n1->AddLinked( & bEdges[ iEdge ] );
n2->AddLinked( & bEdges[ iEdge ] );
+ ++iEdge;
}
linkMap.Clear();
// form groups of coincident parts of free borders
- TFreeBorderPart part;
- TCoincidentGroup group;
- vector< BEdge* > ranges; // couples of edges delimiting parts
+ TFreeBorderPart part;
+ TCoincidentGroup group;
+ std::vector< BEdge* > ranges; // couples of edges delimiting parts
BEdge* be = 0; // a current edge
int skipGroup = bEdges.size(); // a group ID used to avoid repeating treatment of edges
}
beRange[1]->myInGroup = groupID;
+ // get starting edge of each close border
+ closeEdges.clear();
+ be = beRange[0];
+ if ( be->myCloseBorders.empty() )
+ be = beRange[0]->myNext;
+ std::set<int>::iterator closeBord = be->myCloseBorders.begin();
+ for ( ; closeBord != be->myCloseBorders.end(); ++closeBord )
+ if ( BEdge* e = be->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
+ closeEdges.push_back( e );
+
+ for ( size_t iE = 0; iE < closeEdges.size(); ++iE )
+ if ( be->myCloseBorders != closeEdges[iE]->myCloseBorders )
+ {
+ closeBord = closeEdges[iE]->myCloseBorders.begin();
+ for ( ; closeBord != closeEdges[iE]->myCloseBorders.end(); ++closeBord )
+ if ( !be->myCloseBorders.count( *closeBord ))
+ if ( BEdge* e = closeEdges[iE]->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
+ if ( std::find( closeEdges.begin(), closeEdges.end(), e ) == closeEdges.end() )
+ closeEdges.push_back( e );
+ }
+
// add parts of other borders
BEdge* be1st = beRange[0];
- closeEdges.clear();
- std::set<int>::iterator closeBord = be1st->myCloseBorders.begin();
- for ( ; closeBord != be1st->myCloseBorders.end(); ++closeBord )
- closeEdges.push_back( be1st->myBNode2->GetCloseEdgeOfBorder( *closeBord ));
-
for ( size_t iE = 0; iE < closeEdges.size(); ++iE )
{
be = closeEdges[ iE ];
if ( !be ) continue;
bool ok = be->GetRangeOfSameCloseBorders( beRange, be->myCloseBorders );
- if ( !ok && be->myPrev )
- ok = be->myPrev->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
- if ( !ok && be->myNext )
- ok = be->myNext->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
+ // if ( !ok && be->myPrev )
+ // ok = be->myPrev->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
+ // if ( !ok && be->myNext )
+ // ok = be->myNext->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
if ( !ok )
continue;
be = beRange[0];
- if ( be->myCloseBorders != be1st->myCloseBorders )
- {
- //add missing edges to closeEdges
- closeBord = be->myCloseBorders.begin();
- for ( ; closeBord != be->myCloseBorders.end(); ++closeBord )
- if ( !be1st->myCloseBorders.count( *closeBord ))
- closeEdges.push_back( be->myBNode2->GetCloseEdgeOfBorder( *closeBord ));
- }
ranges.push_back( beRange[0] );
ranges.push_back( beRange[1] );
if ( ranges.size() > 2 )
{
- for ( size_t iR = 1; iR < ranges.size(); iR += 2 )
- extendPart( ranges[ iR-1 ], ranges[ iR ], be1st->myCloseBorders, groupID );
+ if ( !chooseStartOfClosedBorders( ranges ))
+ for ( size_t iR = 1; iR < ranges.size(); iR += 2 )
+ extendPart( ranges[ iR-1 ], ranges[ iR ], be1st->myCloseBorders, groupID );
// fill in a group
beRange[0] = ranges[0];
part._node2 = beRange[0]->myID + 1;
part._nodeLast = beRange[1]->myID + 1;
}
+ // if ( group[0]._node2 != part._node2 )
group.push_back( part );
}
- foundFreeBordes._coincidentGroups.push_back( group );
+ //if ( group.size() > 1 )
+ foundFreeBordes._coincidentGroups.push_back( group );
}
else
{
} // SMESH_MeshAlgos::FindCoincidentFreeBorders()
+//================================================================================
+/*
+ * Returns all TFreeBorder's. Optionally check if the mesh is manifold
+ * and if faces are correctly oriented.
+ */
+//================================================================================
+
+void SMESH_MeshAlgos::FindFreeBorders(SMDS_Mesh& theMesh,
+ TFreeBorderVec & theFoundFreeBordes,
+ const bool theClosedOnly,
+ bool* theIsManifold,
+ bool* theIsGoodOri)
+{
+ bool isManifold = true;
+
+ // find free links
+ typedef NCollection_DataMap<SMESH_TLink, const SMDS_MeshElement*, SMESH_TLink > TLink2FaceMap;
+ TLink2FaceMap linkMap;
+ int nbSharedLinks = 0;
+ SMDS_FaceIteratorPtr faceIt = theMesh.facesIterator();
+ while ( faceIt->more() )
+ {
+ const SMDS_MeshElement* face = faceIt->next();
+ if ( !face ) continue;
+
+ const SMDS_MeshNode* n0 = face->GetNode( face->NbNodes() - 1 );
+ SMDS_NodeIteratorPtr nodeIt = face->interlacedNodesIterator();
+ while ( nodeIt->more() )
+ {
+ const SMDS_MeshNode* n1 = nodeIt->next();
+ SMESH_TLink link( n0, n1 );
+ if ( const SMDS_MeshElement** faceInMap = linkMap.ChangeSeek( link ))
+ {
+ if ( *faceInMap )
+ {
+ if ( theIsGoodOri && *theIsGoodOri && !IsRightOrder( *faceInMap, n1, n0 ))
+ *theIsGoodOri = false;
+ }
+ else
+ {
+ isManifold = false;
+ }
+ nbSharedLinks += bool( *faceInMap );
+ *faceInMap = 0;
+ }
+ else
+ {
+ linkMap.Bind( link, face );
+ }
+ n0 = n1;
+ }
+ }
+ if ( theIsManifold )
+ *theIsManifold = isManifold;
+
+ if ( linkMap.Extent() == nbSharedLinks )
+ return;
+
+ // form free borders
+ std::set < BNode > bNodes;
+ std::vector< BEdge > bEdges( linkMap.Extent() - nbSharedLinks );
+
+ TLink2FaceMap::Iterator linkIt( linkMap );
+ for ( int iEdge = 0; linkIt.More(); linkIt.Next() )
+ {
+ if ( !linkIt.Value() ) continue;
+ const SMESH_TLink & link = linkIt.Key();
+ std::set< BNode >::iterator n1 = bNodes.insert( BNode( link.node1() )).first;
+ std::set< BNode >::iterator n2 = bNodes.insert( BNode( link.node2() )).first;
+ bEdges[ iEdge ].Set( &*n1, &*n2, linkIt.Value(), iEdge+1 );
+ n1->AddLinked( & bEdges[ iEdge ] );
+ n2->AddLinked( & bEdges[ iEdge ] );
+ ++iEdge;
+ }
+ linkMap.Clear();
+
+ // assign IDs to borders
+ std::vector< BEdge* > borders; // 1st of connected (via myPrev and myNext) edges
+ std::set< BNode >::iterator bn = bNodes.begin();
+ for ( ; bn != bNodes.end(); ++bn )
+ {
+ for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
+ {
+ if ( bn->myLinkedEdges[i]->myBorderID < 0 )
+ {
+ BEdge* be = bn->myLinkedEdges[i];
+ int borderID = borders.size();
+ borders.push_back( be );
+ for ( ; be && be->myBorderID < 0; be = be->myNext )
+ {
+ be->myBorderID = borderID;
+ be->Orient();
+ }
+ bool isClosed = ( be == bn->myLinkedEdges[i] );
+ if ( !isClosed && theClosedOnly )
+ {
+ borders.pop_back();
+ continue;
+ }
+ be = bn->myLinkedEdges[i]->myPrev;
+ for ( ; be && be->myBorderID < 0; be = be->myPrev )
+ {
+ be->myBorderID = borderID;
+ be->Orient();
+ }
+ if ( !isClosed )
+ while ( borders.back()->myPrev )
+ borders.back() = borders.back()->myPrev;
+ }
+ }
+ }
+ theFoundFreeBordes.resize( borders.size() );
+ for ( size_t i = 0; i < borders.size(); ++i )
+ {
+ TFreeBorder & bordNodes = theFoundFreeBordes[ i ];
+ BEdge* be = borders[i];
+
+ size_t cnt = 1;
+ for ( be = be->myNext; be && be != borders[i]; be = be->myNext )
+ ++cnt;
+ bordNodes.resize( cnt + 1 );
+
+ BEdge* beLast;
+ for ( be = borders[i], cnt = 0;
+ be && cnt < bordNodes.size()-1;
+ be = be->myNext, ++cnt )
+ {
+ bordNodes[ cnt ] = be->myBNode1->Node();
+ beLast = be;
+ }
+ bordNodes.back() = beLast->myBNode2->Node();
+ }
+}
