+
+ //----------------------------------------------------------------------------
+ // internal function
+ void ComputeBoundsParam( double theBounds[6],
+ double theDirection[3],
+ double theMinPnt[3],
+ double& theMaxBoundPrj,
+ double& theMinBoundPrj )
+ {
+ //Enlarge bounds in order to avoid conflicts of precision
+ for(int i = 0; i < 6; i += 2){
+ static double EPS = 1.0E-3;
+ double aDelta = (theBounds[i+1] - theBounds[i])*EPS;
+ theBounds[i] -= aDelta;
+ theBounds[i+1] += aDelta;
+ }
+
+ double aBoundPoints[8][3] = { {theBounds[0],theBounds[2],theBounds[4]},
+ {theBounds[1],theBounds[2],theBounds[4]},
+ {theBounds[0],theBounds[3],theBounds[4]},
+ {theBounds[1],theBounds[3],theBounds[4]},
+ {theBounds[0],theBounds[2],theBounds[5]},
+ {theBounds[1],theBounds[2],theBounds[5]},
+ {theBounds[0],theBounds[3],theBounds[5]},
+ {theBounds[1],theBounds[3],theBounds[5]}};
+
+ int aMaxId = 0;
+ theMaxBoundPrj = vtkMath::Dot(theDirection,aBoundPoints[aMaxId]);
+ theMinBoundPrj = theMaxBoundPrj;
+ for(int i = 1; i < 8; i++){
+ double aTmp = vtkMath::Dot(theDirection,aBoundPoints[i]);
+ if(theMaxBoundPrj < aTmp){
+ theMaxBoundPrj = aTmp;
+ aMaxId = i;
+ }
+ if(theMinBoundPrj > aTmp){
+ theMinBoundPrj = aTmp;
+ }
+ }
+ double *aMinPnt = aBoundPoints[aMaxId];
+ theMinPnt[0] = aMinPnt[0];
+ theMinPnt[1] = aMinPnt[1];
+ theMinPnt[2] = aMinPnt[2];
+ }
+
+ // internal function
+ void DistanceToPosition( double theBounds[6],
+ double theDirection[3],
+ double theDist,
+ double thePos[3] )
+ {
+ double aMaxBoundPrj, aMinBoundPrj, aMinPnt[3];
+ ComputeBoundsParam(theBounds,theDirection,aMinPnt,aMaxBoundPrj,aMinBoundPrj);
+ double aLength = (aMaxBoundPrj-aMinBoundPrj)*theDist;
+ thePos[0] = aMinPnt[0]-theDirection[0]*aLength;
+ thePos[1] = aMinPnt[1]-theDirection[1]*aLength;
+ thePos[2] = aMinPnt[2]-theDirection[2]*aLength;
+ }
+
+ // internal function (currently unused, left just in case)
+ void PositionToDistance( double theBounds[6],
+ double theDirection[3],
+ double thePos[3],
+ double& theDist )
+ {
+ double aMaxBoundPrj, aMinBoundPrj, aMinPnt[3];
+ ComputeBoundsParam(theBounds,theDirection,aMinPnt,aMaxBoundPrj,aMinBoundPrj);
+ double aPrj = vtkMath::Dot(theDirection,thePos);
+ theDist = (aPrj-aMinBoundPrj)/(aMaxBoundPrj-aMinBoundPrj);
+ }
+
+ bool ComputeClippingPlaneParameters( std::list<vtkActor*> theActorList,
+ double theNormal[3],
+ double theDist,
+ double theBounds[6],
+ double theOrigin[3] )
+ {
+ bool anIsOk = false;
+ anIsOk = ComputeBounds( theActorList, theBounds );
+
+
+ if( !anIsOk )
+ return false;
+
+ DistanceToPosition( theBounds, theNormal, theDist, theOrigin );
+ return true;
+ }
+ bool CreatePlaneOnThreePoints( const gp_Pnt& thePoint1,
+ const gp_Pnt& thePoint2,
+ const gp_Pnt& thePoint3,
+ gp_Pln& thePlane )
+ {
+ gp_Vec aVec1, aVec2;
+ aVec1 = gp_Vec( thePoint1, thePoint2 );
+ aVec2 = gp_Vec( thePoint1, thePoint3 );
+ double anAngle = aVec1.Angle( aVec2 );
+ bool isOnStraight = ( anAngle != 0 && anAngle != M_PI );
+ if ( isOnStraight ) {
+ gce_MakePln aMakePln (thePoint1, thePoint2, thePoint3);
+ if ( aMakePln.IsDone() ) {
+ thePlane = aMakePln.Value();
+ }
+ }
+ return isOnStraight;
+ }
+
+ void FindNbLowestPoint( std::list<gp_Pnt2d> theList, gp_Pnt2d& theNode )
+ {
+ std::list<gp_Pnt2d>::iterator anIter = theList.begin();
+ gp_Pnt2d aNode = gp_Pnt2d ( (*anIter).X(), (*anIter).Y());
+ for( ; anIter != theList.end(); anIter++ ) {
+ if ( (*anIter).Y() < aNode.Y() || ( (*anIter).Y() == aNode.Y() && (*anIter).X() < aNode.X() ) )
+ aNode = *anIter;
+ }
+ theNode = aNode;
+ }
+
+ static bool CompareNodeOfAngleAndDist (const TNodeOfAngleAndDist& first, const TNodeOfAngleAndDist& second )
+ {
+ if ( first.second.second == 0 )
+ return true;
+ if ( second.second.second == 0 )
+ return false;
+ if ( first.second.first == 0 && second.second.first == 0 )
+ if ( first.second.second > second.second.second )
+ return false;
+ else
+ return true;
+ if ( first.second.first < second.second.first ||
+ ( first.second.first == second.second.first && first.second.second >= second.second.second ) )
+ return true;
+ return false;
+ }
+
+ static bool CompareNodeOfDist (const TNodeOfAngleAndDist& first, const TNodeOfAngleAndDist& second )
+ {
+ if ( first.second.second < second.second.second )
+ return true;
+ return false;
+ }
+
+ static bool CompareDistOfPlane ( const TNodeOfDistToPlaneAndDist& first, const TNodeOfDistToPlaneAndDist& second )
+ {
+ if ( first.second.first == 0 && second.second.first != 0 )
+ return true;
+ if ( first.second.first != 0 && second.second.first == 0 )
+ return false;
+ if ( first.second.first < second.second.first ||
+ ( first.second.first != 0 && second.second.first != 0 &&
+ first.second.first == second.second.first && first.second.second > second.second.second ) )
+ return true;
+ return false;
+ }
+
+ static bool CompareDistOfPlaneById ( const TIdOfDistToPlaneAndDist& first, const TIdOfDistToPlaneAndDist& second )
+ {
+ if ( first.second.first == 0 && second.second.first != 0 )
+ return true;
+ if ( first.second.first != 0 && second.second.first == 0 )
+ return false;
+ if ( first.second.first < second.second.first ||
+ ( first.second.first != 0 && second.second.first != 0 &&
+ first.second.first == second.second.first && first.second.second > second.second.second ) )
+ return true;
+ return false;
+ }
+
+ static bool CompareDistForCorrectPlane ( const TNodeOfDist& first, const TNodeOfDist& second )
+ {
+ if ( first.second < second.second ) return true;
+ return false;
+ }
+
+ bool IsNotPlaneIntersection( std::vector<SMESH_TNodeXYZ>& theVector, const gp_Pln& thePlane )
+ {
+ double A, B, C, D, aCur;
+ thePlane.Coefficients(A, B, C, D);
+ int aPlus = -1;
+ for ( int i = 0 ; i < (int)theVector.size(); ++i ) {
+ aCur = A * theVector[i]._xyz[0] + B * theVector[i]._xyz[1] + C * theVector[i]._xyz[2] + D;
+ if ( aCur == 0 )
+ continue;
+ if ( aPlus == -1 && aCur != 0 )
+ aPlus = ( aCur < 0 ) ? 0 : 1;
+ if ( aPlus > -1 && aPlus != ( aCur < 0 ) ? 0 : 1 )
+ return false;
+ }
+ return true;
+ }
+
+ bool GetNextCombination ( std::vector<int>& theVector1, std::vector<int>& theVector2, int theNbPoint )
+ {
+ int aSize = (int)theVector1.size();
+ for ( int i = aSize - 1; i >= 0; --i ) {
+ if ( theVector1[i] < theNbPoint - aSize + i ) {
+ ++theVector1[i];
+ for ( int j = i + 1; j < aSize; ++j )
+ theVector1[j] = theVector1[j-1] + 1;
+ int it = 0;
+ int it2 = 0;
+ bool isVec;
+ for ( int k = 0; k < theNbPoint; ++k ) {
+ isVec = false;
+ if( it < aSize ) {
+ if( k == theVector1[it] ) {
+ isVec = true;
+ ++it;
+ }
+ }
+ if ( isVec )
+ continue;
+ theVector2[it2] = k;
+ it2++;
+ if ( it2 == (int)theVector2.size() )
+ break;
+ }
+ return true;
+ }
+ }
+ return false;
+ }
+
+ bool Get2BasePlane( std::vector<SMESH_TNodeXYZ>& theVector,
+ std::vector<SMESH_TNodeXYZ>& thePlane1,
+ std::vector<SMESH_TNodeXYZ>& thePlane2 )
+ {
+ int aSize = (int)theVector.size() / 2;
+ if ( aSize < 3 || (int)theVector.size() % 2 != 0 )
+ return false;
+ int anArr1[3];
+ int anArr2[2 * aSize - 3];
+ for (int i = 0; i < 3 ; i++) {
+ anArr1[i] = i;
+ }
+ for (int i = 0; i < 2 * aSize - 3 ; i++) {
+ anArr2[i] = i + 3;
+ }
+ int aNbSwapFirstPoint = 0;
+ while ( thePlane1.empty() && thePlane2.empty() && aNbSwapFirstPoint < aSize * 2 ) {
+ std::vector<int> anIndexPlane1( anArr1, anArr1 + 3 );
+ std::vector<int> anIndexPlane2( anArr2, anArr2 + 2 * aSize - 3);
+ int aNbCombination = 0;
+ double aMax = 0;
+ double aSumMin = -1;
+ int aMaxCombination = 0;
+ thePlane1.clear();
+ thePlane2.clear();
+ for (int i = 1; i < 2 * aSize - 1; i++ ) {
+ aMaxCombination += i;
+ }
+ while ( aNbCombination < aMaxCombination ) {
+ gp_Pln aPlane;
+ double aSumMinDist1 = 0;
+ double aSumMinDist2 = 0;
+ std::vector<SMESH_TNodeXYZ> aVectorOfPoint;
+ for(int i = 0; i < 2 * aSize - 3; i++) {
+ aVectorOfPoint.push_back(theVector[anIndexPlane2[i]]);
+ }
+ bool isCorrectPlane = false;
+ bool isCreatePlane = CreatePlaneOnThreePoints( gp_Pnt(theVector[anIndexPlane1[0]]._xyz[0], theVector[anIndexPlane1[0]]._xyz[1], theVector[anIndexPlane1[0]]._xyz[2]),
+ gp_Pnt(theVector[anIndexPlane1[1]]._xyz[0], theVector[anIndexPlane1[1]]._xyz[1], theVector[anIndexPlane1[1]]._xyz[2]),
+ gp_Pnt(theVector[anIndexPlane1[2]]._xyz[0], theVector[anIndexPlane1[2]]._xyz[1], theVector[anIndexPlane1[2]]._xyz[2]),
+ aPlane );
+ if ( isCreatePlane ) {
+ isCorrectPlane = IsNotPlaneIntersection( aVectorOfPoint, aPlane );
+ }
+ if ( !isCorrectPlane ) {
+ GetNextCombination( anIndexPlane1, anIndexPlane2, 2*aSize );
+ aNbCombination++;
+ continue;
+ }
+ std::vector<int> anIndexCorrectPlane1;
+ std::vector<int> anIndexCorrectPlane2;
+ if ( aSize == 3 ) {
+ for (int i = 0; i < aSize ; i++) {
+ anIndexCorrectPlane1.push_back( anIndexPlane1[i] );
+ anIndexCorrectPlane2.push_back( anIndexPlane2[i] );
+ }
+ }
+ if ( aSize >= 4 ) {
+ std::list<TIdOfDistToPlaneAndDist> aListBaseOfPoint;
+ TIdOfDistToPlaneAndDist aCurDistOfPlane;
+ for (int i = 0; i < 2 * aSize - 3; i++ ) {
+ aCurDistOfPlane.second.first = aPlane.Distance( gp_Pnt( theVector[anIndexPlane2[i]]._xyz[0], theVector[anIndexPlane2[i]]._xyz[1], theVector[anIndexPlane2[i]]._xyz[2] ));
+ if ( aCurDistOfPlane.second.first == 0 )
+ aCurDistOfPlane.second.second = 0;
+ else {
+ double aCurDist = 0;
+ for (int j = 0; j < 3; j++) {
+ aCurDist += pow( theVector[anIndexPlane1[j]]._xyz[0] - theVector[anIndexPlane2[i]]._xyz[0], 2.0 ) +
+ pow( theVector[anIndexPlane1[j]]._xyz[1] - theVector[anIndexPlane2[i]]._xyz[1], 2.0 ) +
+ pow( theVector[anIndexPlane1[j]]._xyz[2] - theVector[anIndexPlane2[i]]._xyz[2], 2.0 );
+ }
+ aCurDistOfPlane.second.second = aCurDist;
+ }
+ aCurDistOfPlane.first = anIndexPlane2[i];
+ aListBaseOfPoint.push_back( aCurDistOfPlane );
+ }
+ aListBaseOfPoint.sort( CompareDistOfPlaneById );
+ std::list<TIdOfDistToPlaneAndDist>::iterator anIterDist = aListBaseOfPoint.begin();
+ for (int i = 0; i < 3; i++) {
+ anIndexCorrectPlane1.push_back( anIndexPlane1[i] );
+ }
+ for (int i = 0; i < aSize - 3; i++, anIterDist++) {
+ anIndexCorrectPlane1.push_back((*anIterDist).first);
+ }
+ for (int i = 0; i < 2 * aSize - 3 ; i++) {
+ anIterDist = aListBaseOfPoint.begin();
+ bool isFinded = false;
+ for (int j = 0; j < aSize - 3; j++, anIterDist++) {
+ if ( anIndexPlane2[i] == (*anIterDist).first ) {
+ isFinded = true;
+ break;
+ }
+ }
+ if ( !isFinded )
+ anIndexCorrectPlane2.push_back( anIndexPlane2[i] );
+ }
+ }
+ double aCurDist1, aCurDist2, aMinDist1, aMinDist2, aSumDist1, aSumDist2, aSumDistBase1, aSumDistBase2;
+ bool isCorrect2Base = true;
+ aSumDist1 = aSumDistBase1 = aSumDist2 = aSumDistBase2 = 0;
+ for( int i = 0 ; i < aSize ; i++ ) {
+ aMinDist1 = 0;
+ aMinDist2 = 0;
+ for(int j = 0 ; j < aSize ; j++ ) {
+ aCurDist1 = pow( theVector[anIndexCorrectPlane1[i]]._xyz[0] - theVector[anIndexCorrectPlane2[j]]._xyz[0], 2.0 ) +
+ pow( theVector[anIndexCorrectPlane1[i]]._xyz[1] - theVector[anIndexCorrectPlane2[j]]._xyz[1], 2.0 ) +
+ pow( theVector[anIndexCorrectPlane1[i]]._xyz[2] - theVector[anIndexCorrectPlane2[j]]._xyz[2], 2.0 );
+ aCurDist2 = pow( theVector[anIndexCorrectPlane1[j]]._xyz[0] - theVector[anIndexCorrectPlane2[i]]._xyz[0], 2.0 ) +
+ pow( theVector[anIndexCorrectPlane1[j]]._xyz[1] - theVector[anIndexCorrectPlane2[i]]._xyz[1], 2.0 ) +
+ pow( theVector[anIndexCorrectPlane1[j]]._xyz[2] - theVector[anIndexCorrectPlane2[i]]._xyz[2], 2.0 );
+ aSumDistBase1 += pow( theVector[anIndexCorrectPlane1[i]]._xyz[0] - theVector[anIndexCorrectPlane1[j]]._xyz[0], 2.0 ) +
+ pow( theVector[anIndexCorrectPlane1[i]]._xyz[1] - theVector[anIndexCorrectPlane1[j]]._xyz[1], 2.0 ) +
+ pow( theVector[anIndexCorrectPlane1[i]]._xyz[2] - theVector[anIndexCorrectPlane1[j]]._xyz[2], 2.0 );
+ aSumDistBase2 += pow( theVector[anIndexCorrectPlane2[i]]._xyz[0] - theVector[anIndexCorrectPlane2[j]]._xyz[0], 2.0 ) +
+ pow( theVector[anIndexCorrectPlane2[i]]._xyz[1] - theVector[anIndexCorrectPlane2[j]]._xyz[1], 2.0 ) +
+ pow( theVector[anIndexCorrectPlane2[i]]._xyz[2] - theVector[anIndexCorrectPlane2[j]]._xyz[2], 2.0 );
+ if ( aCurDist1 < aMinDist1 || aMinDist1 == 0)
+ aMinDist1 = aCurDist1;
+ if ( aCurDist2 < aMinDist2 || aMinDist2 == 0)
+ aMinDist2 = aCurDist2;
+ aSumDist1 += aCurDist1;
+ aSumDist2 += aCurDist2;
+ }
+ aSumMinDist1 += aMinDist1;
+ aSumDist1 -= aMinDist1;
+ aSumMinDist2 += aMinDist2;
+ aSumDist2 -= aMinDist2;
+ }
+ isCorrect2Base = ( aSumDistBase1 + aSumDistBase2 <= aSumDist1 + aSumDist2 );
+ if ( isCorrect2Base && ( aSumMinDist1 == aSumMinDist2 || ( aSumMinDist1 + aSumMinDist2 ) > aMax || aMax == 0 ||
+ ( (aSumMinDist1 + aSumMinDist2 ) == aMax && ( (aSumDist1 + aSumDist2 - aSumDistBase1 - aSumDistBase2) < aSumMin || aSumMin == -1 ) ) ) ) {
+ aMax = aSumMinDist1 + aSumMinDist2;
+ aSumMin = aSumDist1 + aSumDist2 - aSumDistBase1 - aSumDistBase2;
+ thePlane1.clear();
+ thePlane2.clear();
+ for(int i = 0; i < aSize; i++) {
+ thePlane1.push_back(theVector[anIndexCorrectPlane1[i]]);
+ thePlane2.push_back(theVector[anIndexCorrectPlane2[i]]);
+ }
+ }
+ if ( aSumMinDist1 == aSumMinDist2 )
+ break;
+ if ( !GetNextCombination( anIndexPlane1, anIndexPlane2, 2 * aSize) )
+ break;
+ aNbCombination++;
+ }
+ if ( thePlane1.empty() && thePlane2.empty() ) {
+ aNbSwapFirstPoint++;
+ SMESH_TNodeXYZ aPoint;
+ aPoint = theVector[0];
+ theVector[0] = theVector[aNbSwapFirstPoint];
+ theVector[aNbSwapFirstPoint] = aPoint;
+ }
+ }
+ if ( thePlane1.empty() && thePlane2.empty() )
+ return false;
+ return true;
+ }
+
+ bool GetCorrectSequenceOfId( std::vector<SMESH_TNodeXYZ>& theVector )
+ {
+ std::list<gp_Pnt2d> aListProjection;
+ gp_Pnt2d aCurPoint;
+ int aSize = (int)theVector.size();
+ if ( aSize < 3 )
+ return false;
+ gp_Pln aPlane;
+ bool isCreatePlane = false;
+ for (int i = 0; i < aSize - 1; i++ ) {
+ isCreatePlane = CreatePlaneOnThreePoints( gp_Pnt( theVector[i]._xyz[0], theVector[i]._xyz[1], theVector[i]._xyz[2] ),
+ gp_Pnt( theVector[i+1]._xyz[0], theVector[i+1]._xyz[1], theVector[i+1]._xyz[2] ),
+ gp_Pnt( theVector[i+2]._xyz[0], theVector[i+2]._xyz[1], theVector[i+2]._xyz[2] ), aPlane );
+ if ( isCreatePlane)
+ break;
+ }
+ if ( !isCreatePlane )
+ return false;
+ for ( int i = 0; i < aSize; i++) {
+ aCurPoint = ProjLib::Project( aPlane, gp_Pnt( theVector[i]._xyz[0], theVector[i]._xyz[1], theVector[i]._xyz[2] ));
+ aListProjection.push_back( aCurPoint );
+ }
+ std::list<TNodeOfAngleAndDist> aListIdOfAngleAndDist;
+ TNodeOfAngleAndDist aCurIdOfAngleAndDist;
+ FindNbLowestPoint( aListProjection, aCurPoint);
+ std::list<gp_Pnt2d>::iterator anIter2d = aListProjection.begin();
+ gp_Vec2d aCurVec;
+ gp_Vec2d aAxisVec = gp_Vec2d( 1, 0 );
+ for( int i = 0 ; anIter2d != aListProjection.end(); anIter2d++, i++) {
+ aCurVec = gp_Vec2d( (*anIter2d).X() - aCurPoint.X(), (*anIter2d).Y() - aCurPoint.Y() );
+ aCurIdOfAngleAndDist.first = theVector[i];
+ if ( (*anIter2d).X() == aCurPoint.X() && (*anIter2d).Y() == aCurPoint.Y() )
+ aCurIdOfAngleAndDist.second.first = 0;
+ else {
+ double anAngle = aAxisVec.Angle( aCurVec );
+ double anRoundAngle = anAngle * 100000;
+ int anIntAngle = anRoundAngle + 0.5;
+ anRoundAngle = (double) anIntAngle / 100000;
+ aCurIdOfAngleAndDist.second.first = anRoundAngle;
+ }
+ aCurIdOfAngleAndDist.second.second = pow( (*anIter2d).X() - aCurPoint.X(), 2.0 ) +
+ pow( (*anIter2d).Y() - aCurPoint.Y(), 2.0 ) +
+ pow( aPlane.Distance( gp_Pnt( theVector[i]._xyz[0], theVector[i]._xyz[1], theVector[i]._xyz[2] )), 2.0 );
+ aListIdOfAngleAndDist.push_back( aCurIdOfAngleAndDist );
+ }
+ aListIdOfAngleAndDist.sort( CompareNodeOfAngleAndDist );
+ std::list<TNodeOfAngleAndDist>::iterator anIter = aListIdOfAngleAndDist.begin();
+ std::list<TNodeOfAngleAndDist> aListResult;
+ double anAngle = 0;
+ bool isSort = true;
+ for(int i = 0 ; anIter != aListIdOfAngleAndDist.end(); anIter++, i++) {
+ if ( anAngle == (*anIter).second.first && anAngle != 0 ) {
+ isSort = false;
+ break;
+ }
+ if ( ( anAngle > (*anIter).second.first && anAngle != 0 ) || i > 1)
+ break;
+ if ( (*anIter).second.first > 0 )
+ anAngle = (*anIter).second.first;
+ }
+ if ( !isSort ) {
+ anIter = aListIdOfAngleAndDist.begin();
+ for( ; anIter != aListIdOfAngleAndDist.end(); anIter++) {
+ if ( anAngle == (*anIter).second.first)
+ aListResult.push_back( *anIter );
+ else if ( anAngle < (*anIter).second.first)
+ break;
+ }
+ }
+ else
+ anAngle = 0;
+ aListResult.sort(CompareNodeOfDist);
+ anIter = aListIdOfAngleAndDist.begin();
+ theVector.clear();
+ for( ; anIter != aListIdOfAngleAndDist.end(); anIter++) {
+ if ( !isSort && anAngle == (*anIter).second.first ){
+ for( std::list<TNodeOfAngleAndDist>::iterator anIter2 = aListResult.begin() ; anIter2 != aListResult.end(); anIter2++) {
+ theVector.push_back((*anIter2).first);
+ }
+ isSort = true;
+ }
+ if ( isSort && anAngle != 0 && anAngle == (*anIter).second.first )
+ continue;
+ theVector.push_back((*anIter).first);
+ }
+
+ return true;