src/StdMeshers/StdMeshers_QuadFromMedialAxis_1D2D.cxx

   1 // Copyright (C) 2007-2015  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   5 //
   6 // This library is free software; you can redistribute it and/or
   7 // modify it under the terms of the GNU Lesser General Public
   8 // License as published by the Free Software Foundation; either
   9 // version 2.1 of the License, or (at your option) any later version.
  10 //
  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 GNU
  14 // Lesser General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU Lesser General Public
  17 // License along with this library; if not, write to the Free Software
  18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  19 //
  20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21 //
  22 // File      : StdMeshers_QuadFromMedialAxis_1D2D.cxx
  23 // Created   : Wed Jun  3 17:33:45 2015
  24 // Author    : Edward AGAPOV (eap)
  25
  26 #include "StdMeshers_QuadFromMedialAxis_1D2D.hxx"
  27
  28 #include "SMESH_Block.hxx"
  29 #include "SMESH_Gen.hxx"
  30 #include "SMESH_MAT2d.hxx"
  31 #include "SMESH_Mesh.hxx"
  32 #include "SMESH_MeshEditor.hxx"
  33 #include "SMESH_MesherHelper.hxx"
  34 #include "SMESH_ProxyMesh.hxx"
  35 #include "SMESH_subMesh.hxx"
  36 #include "SMESH_subMeshEventListener.hxx"
  37 #include "StdMeshers_FaceSide.hxx"
  38 #include "StdMeshers_LayerDistribution.hxx"
  39 #include "StdMeshers_NumberOfLayers.hxx"
  40 #include "StdMeshers_Regular_1D.hxx"
  41 #include "StdMeshers_ViscousLayers2D.hxx"
  42
  43 #include <BRepAdaptor_Curve.hxx>
  44 #include <BRepBuilderAPI_MakeEdge.hxx>
  45 #include <BRepTools.hxx>
  46 #include <BRep_Tool.hxx>
  47 #include <GeomAPI_Interpolate.hxx>
  48 #include <Geom_Surface.hxx>
  49 #include <Precision.hxx>
  50 #include <TColgp_HArray1OfPnt.hxx>
  51 #include <TopExp.hxx>
  52 #include <TopExp_Explorer.hxx>
  53 #include <TopLoc_Location.hxx>
  54 #include <TopTools_MapOfShape.hxx>
  55 #include <TopoDS.hxx>
  56 #include <TopoDS_Edge.hxx>
  57 #include <TopoDS_Face.hxx>
  58 #include <TopoDS_Vertex.hxx>
  59 #include <gp_Pnt.hxx>
  60
  61 #include <list>
  62 #include <vector>
  63
  64 //================================================================================
  65 /*!
  66  * \brief 1D algo
  67  */
  68 class StdMeshers_QuadFromMedialAxis_1D2D::Algo1D : public StdMeshers_Regular_1D
  69 {
  70 public:
  71   Algo1D(int studyId, SMESH_Gen* gen):
  72     StdMeshers_Regular_1D( gen->GetANewId(), studyId, gen )
  73   {
  74   }
  75   void SetSegmentLength( double len )
  76   {
  77     SMESH_Algo::_usedHypList.clear();
  78     _value[ BEG_LENGTH_IND ] = len;
  79     _value[ PRECISION_IND  ] = 1e-7;
  80     _hypType = LOCAL_LENGTH;
  81   }
  82   void SetRadialDistribution( const SMESHDS_Hypothesis* hyp )
  83   {
  84     SMESH_Algo::_usedHypList.clear();
  85     if ( !hyp )
  86       return;
  87
  88     if ( const StdMeshers_NumberOfLayers* nl =
  89          dynamic_cast< const StdMeshers_NumberOfLayers* >( hyp ))
  90     {
  91       _ivalue[ NB_SEGMENTS_IND  ] = nl->GetNumberOfLayers();
  92       _ivalue[ DISTR_TYPE_IND ]   = 0;
  93       _hypType = NB_SEGMENTS;
  94     }
  95     if ( const StdMeshers_LayerDistribution* ld =
  96          dynamic_cast< const StdMeshers_LayerDistribution* >( hyp ))
  97     {
  98       if ( SMESH_Hypothesis* h = ld->GetLayerDistribution() )
  99       {
 100         SMESH_Algo::_usedHypList.clear();
 101         SMESH_Algo::_usedHypList.push_back( h );
 102       }
 103     }
 104   }
 105   void ComputeDistribution(SMESH_MesherHelper& theHelper,
 106                            const gp_Pnt&       thePnt1,
 107                            const gp_Pnt&       thePnt2,
 108                            list< double >&     theParams)
 109   {
 110     SMESH_Mesh& mesh = *theHelper.GetMesh();
 111     TopoDS_Edge edge = BRepBuilderAPI_MakeEdge( thePnt1, thePnt2 );
 112
 113     SMESH_Hypothesis::Hypothesis_Status aStatus;
 114     CheckHypothesis( mesh, edge, aStatus );
 115
 116     theParams.clear();
 117     BRepAdaptor_Curve C3D(edge);
 118     double f = C3D.FirstParameter(), l = C3D.LastParameter(), len = thePnt1.Distance( thePnt2 );
 119     if ( !StdMeshers_Regular_1D::computeInternalParameters( mesh, C3D, len, f, l, theParams, false))
 120     {
 121       for ( size_t i = 1; i < 15; ++i )
 122         theParams.push_back( i/15 );
 123     }
 124     else
 125     {
 126       for (list<double>::iterator itU = theParams.begin(); itU != theParams.end(); ++itU )
 127         *itU /= len;
 128     }
 129   }
 130   virtual const list <const SMESHDS_Hypothesis *> &
 131   GetUsedHypothesis(SMESH_Mesh &, const TopoDS_Shape &, const bool)
 132   {
 133     return SMESH_Algo::_usedHypList;
 134   }
 135   virtual bool CheckHypothesis(SMESH_Mesh&                          aMesh,
 136                                const TopoDS_Shape&                  aShape,
 137                                SMESH_Hypothesis::Hypothesis_Status& aStatus)
 138   {
 139     if ( !SMESH_Algo::_usedHypList.empty() )
 140       return StdMeshers_Regular_1D::CheckHypothesis( aMesh, aShape, aStatus );
 141     return true;
 142   }
 143 };
 144
 145 //================================================================================
 146 /*!
 147  * \brief Constructor sets algo features
 148  */
 149 //================================================================================
 150
 151 StdMeshers_QuadFromMedialAxis_1D2D::StdMeshers_QuadFromMedialAxis_1D2D(int        hypId,
 152                                                                        int        studyId,
 153                                                                        SMESH_Gen* gen)
 154   : StdMeshers_Quadrangle_2D(hypId, studyId, gen),
 155     _regular1D( 0 )
 156 {
 157   _name = "QuadFromMedialAxis_1D2D";
 158   _shapeType = (1 << TopAbs_FACE);
 159   _onlyUnaryInput          = true;  // FACE by FACE so far
 160   _requireDiscreteBoundary = false; // make 1D by myself
 161   _supportSubmeshes        = true; // make 1D by myself
 162   _neededLowerHyps[ 1 ]    = true;  // suppress warning on hiding a global 1D algo
 163   _neededLowerHyps[ 2 ]    = true;  // suppress warning on hiding a global 2D algo
 164   _compatibleHypothesis.clear();
 165   _compatibleHypothesis.push_back("ViscousLayers2D");
 166   _compatibleHypothesis.push_back("LayerDistribution2D");
 167   _compatibleHypothesis.push_back("NumberOfLayers2D");
 168 }
 169
 170 //================================================================================
 171 /*!
 172  * \brief Destructor
 173  */
 174 //================================================================================
 175
 176 StdMeshers_QuadFromMedialAxis_1D2D::~StdMeshers_QuadFromMedialAxis_1D2D()
 177 {
 178   delete _regular1D;
 179   _regular1D = 0;
 180 }
 181
 182 //================================================================================
 183 /*!
 184  * \brief Check if needed hypotheses are present
 185  */
 186 //================================================================================
 187
 188 bool StdMeshers_QuadFromMedialAxis_1D2D::CheckHypothesis(SMESH_Mesh&         aMesh,
 189                                                          const TopoDS_Shape& aShape,
 190                                                          Hypothesis_Status&  aStatus)
 191 {
 192   aStatus = HYP_OK;
 193
 194   // get one main optional hypothesis
 195   const list <const SMESHDS_Hypothesis * >& hyps = GetUsedHypothesis(aMesh, aShape);
 196   _hyp2D  = hyps.empty() ? 0 : hyps.front();
 197
 198   return true; // does not require hypothesis
 199 }
 200
 201 namespace
 202 {
 203   typedef map< const SMDS_MeshNode*, list< const SMDS_MeshNode* > > TMergeMap;
 204
 205   //================================================================================
 206   /*!
 207    * \brief Sinuous face
 208    */
 209   struct SinuousFace
 210   {
 211     FaceQuadStruct::Ptr          _quad;
 212     vector< TopoDS_Edge >        _edges;
 213     vector< TopoDS_Edge >        _sinuSide[2], _shortSide[2];
 214     vector< TopoDS_Edge >        _sinuEdges;
 215     vector< Handle(Geom_Curve) > _sinuCurves;
 216     int                          _nbWires;
 217     list< int >                  _nbEdgesInWire;
 218     TMergeMap                    _nodesToMerge;
 219
 220     SinuousFace( const TopoDS_Face& f ): _quad( new FaceQuadStruct )
 221     {
 222       list< TopoDS_Edge > edges;
 223       _nbWires = SMESH_Block::GetOrderedEdges (f, edges, _nbEdgesInWire);
 224       _edges.assign( edges.begin(), edges.end() );
 225
 226       _quad->side.resize( 4 );
 227       _quad->face = f;
 228     }
 229     const TopoDS_Face& Face() const { return _quad->face; }
 230     bool IsRing() const { return _shortSide[0].empty() && !_sinuSide[0].empty(); }
 231   };
 232
 233   //================================================================================
 234   /*!
 235    * \brief Temporary mesh
 236    */
 237   struct TmpMesh : public SMESH_Mesh
 238   {
 239     TmpMesh()
 240     {
 241       _myMeshDS = new SMESHDS_Mesh(/*id=*/0, /*isEmbeddedMode=*/true);
 242     }
 243   };
 244
 245   //================================================================================
 246   /*!
 247    * \brief Event listener which removes mesh from EDGEs when 2D hyps change
 248    */
 249   struct EdgeCleaner : public SMESH_subMeshEventListener
 250   {
 251     int _prevAlgoEvent;
 252     EdgeCleaner():
 253       SMESH_subMeshEventListener( /*isDeletable=*/true,
 254                                   "StdMeshers_QuadFromMedialAxis_1D2D::EdgeCleaner")
 255     {
 256       _prevAlgoEvent = -1;
 257     }
 258     virtual void ProcessEvent(const int                       event,
 259                               const int                       eventType,
 260                               SMESH_subMesh*                  faceSubMesh,
 261                               SMESH_subMeshEventListenerData* data,
 262                               const SMESH_Hypothesis*         hyp)
 263     {
 264       if ( eventType == SMESH_subMesh::ALGO_EVENT )
 265       {
 266         _prevAlgoEvent = event;
 267         return;
 268       }
 269       // SMESH_subMesh::COMPUTE_EVENT
 270       if ( _prevAlgoEvent == SMESH_subMesh::REMOVE_HYP ||
 271            _prevAlgoEvent == SMESH_subMesh::REMOVE_ALGO ||
 272            _prevAlgoEvent == SMESH_subMesh::MODIF_HYP )
 273       {
 274         SMESH_subMeshIteratorPtr smIt = faceSubMesh->getDependsOnIterator(/*includeSelf=*/false);
 275         while ( smIt->more() )
 276           smIt->next()->ComputeStateEngine( SMESH_subMesh::CLEAN );
 277       }
 278       _prevAlgoEvent = -1;
 279     }
 280   };
 281
 282   //================================================================================
 283   /*!
 284    * \brief Return a member of a std::pair
 285    */
 286   //================================================================================
 287
 288   template< typename T >
 289   T& get( std::pair< T, T >& thePair, bool is2nd )
 290   {
 291     return is2nd ? thePair.second : thePair.first;
 292   }
 293
 294   //================================================================================
 295   /*!
 296    * \brief Select two EDGEs from a map, either mapped to least values or to max values
 297    */
 298   //================================================================================
 299
 300   // template< class TVal2EdgesMap >
 301   // void getTwo( bool                 least,
 302   //              TVal2EdgesMap&       map,
 303   //              vector<TopoDS_Edge>& twoEdges,
 304   //              vector<TopoDS_Edge>& otherEdges)
 305   // {
 306   //   twoEdges.clear();
 307   //   otherEdges.clear();
 308   //   if ( least )
 309   //   {
 310   //     TVal2EdgesMap::iterator i = map.begin();
 311   //     twoEdges.push_back( i->second );
 312   //     twoEdges.push_back( ++i->second );
 313   //     for ( ; i != map.end(); ++i )
 314   //       otherEdges.push_back( i->second );
 315   //   }
 316   //   else
 317   //   {
 318   //     TVal2EdgesMap::reverse_iterator i = map.rbegin();
 319   //     twoEdges.push_back( i->second );
 320   //     twoEdges.push_back( ++i->second );
 321   //     for ( ; i != map.rend(); ++i )
 322   //       otherEdges.push_back( i->second );
 323   //   }
 324   //   TopoDS_Vertex v;
 325   //   if ( TopExp::CommonVertex( twoEdges[0], twoEdges[1], v ))
 326   //   {
 327   //     twoEdges.clear(); // two EDGEs must not be connected
 328   //     otherEdges.clear();
 329   //   }
 330   // }
 331
 332   //================================================================================
 333   /*!
 334    * \brief Finds out a minimal segment length given EDGEs will be divided into.
 335    *        This length is further used to discretize the Medial Axis
 336    */
 337   //================================================================================
 338
 339   double getMinSegLen(SMESH_MesherHelper&        theHelper,
 340                       const vector<TopoDS_Edge>& theEdges)
 341   {
 342     TmpMesh tmpMesh;
 343     SMESH_Mesh* mesh = theHelper.GetMesh();
 344
 345     vector< SMESH_Algo* > algos( theEdges.size() );
 346     for ( size_t i = 0; i < theEdges.size(); ++i )
 347     {
 348       SMESH_subMesh* sm = mesh->GetSubMesh( theEdges[i] );
 349       algos[i] = sm->GetAlgo();
 350     }
 351
 352     int nbSegDflt = mesh->GetGen() ? mesh->GetGen()->GetDefaultNbSegments() : 15;
 353     double minSegLen = Precision::Infinite();
 354
 355     for ( size_t i = 0; i < theEdges.size(); ++i )
 356     {
 357       SMESH_subMesh* sm = mesh->GetSubMesh( theEdges[i] );
 358       if ( SMESH_Algo::IsStraight( theEdges[i], /*degenResult=*/true ))
 359         continue;
 360       // get algo
 361       size_t iOpp = ( theEdges.size() == 4 ? (i+2)%4 : i );
 362       SMESH_Algo*  algo = sm->GetAlgo();
 363       if ( !algo ) algo = algos[ iOpp ];
 364       // get hypo
 365       SMESH_Hypothesis::Hypothesis_Status status = SMESH_Hypothesis::HYP_MISSING;
 366       if ( algo )
 367       {
 368         if ( !algo->CheckHypothesis( *mesh, theEdges[i], status ))
 369           algo->CheckHypothesis( *mesh, theEdges[iOpp], status );
 370       }
 371       // compute
 372       if ( status != SMESH_Hypothesis::HYP_OK )
 373       {
 374         minSegLen = Min( minSegLen, SMESH_Algo::EdgeLength( theEdges[i] ) / nbSegDflt );
 375       }
 376       else
 377       {
 378         tmpMesh.Clear();
 379         tmpMesh.ShapeToMesh( TopoDS_Shape());
 380         tmpMesh.ShapeToMesh( theEdges[i] );
 381         try {
 382           if ( !mesh->GetGen() ) continue; // tmp mesh
 383           mesh->GetGen()->Compute( tmpMesh, theEdges[i], true, true ); // make nodes on VERTEXes
 384           if ( !algo->Compute( tmpMesh, theEdges[i] ))
 385             continue;
 386         }
 387         catch (...) {
 388           continue;
 389         }
 390         SMDS_EdgeIteratorPtr segIt = tmpMesh.GetMeshDS()->edgesIterator();
 391         while ( segIt->more() )
 392         {
 393           const SMDS_MeshElement* seg = segIt->next();
 394           double len = SMESH_TNodeXYZ( seg->GetNode(0) ).Distance( seg->GetNode(1) );
 395           minSegLen = Min( minSegLen, len );
 396         }
 397       }
 398     }
 399     if ( Precision::IsInfinite( minSegLen ))
 400       minSegLen = mesh->GetShapeDiagonalSize() / nbSegDflt;
 401
 402     return minSegLen;
 403   }
 404
 405   //================================================================================
 406   /*!
 407    * \brief Returns EDGEs located between two VERTEXes at which given MA branches end
 408    *  \param [in] br1 - one MA branch
 409    *  \param [in] br2 - one more MA branch
 410    *  \param [in] allEdges - all EDGEs of a FACE
 411    *  \param [out] shortEdges - the found EDGEs
 412    *  \return bool - is OK or not
 413    */
 414   //================================================================================
 415
 416   bool getConnectedEdges( const SMESH_MAT2d::Branch* br1,
 417                           const SMESH_MAT2d::Branch* br2,
 418                           const vector<TopoDS_Edge>& allEdges,
 419                           vector<TopoDS_Edge>&       shortEdges)
 420   {
 421     vector< size_t > edgeIDs[4];
 422     br1->getGeomEdges( edgeIDs[0], edgeIDs[1] );
 423     br2->getGeomEdges( edgeIDs[2], edgeIDs[3] );
 424
 425     // EDGEs returned by a Branch form a connected chain with a VERTEX where
 426     // the Branch ends at the chain middle. One of end EDGEs of the chain is common
 427     // with either end EDGE of the chain of the other Branch, or the chains are connected
 428     // at a common VERTEX;
 429
 430     // Get indices of end EDGEs of the branches
 431     bool vAtStart1 = ( br1->getEnd(0)->_type == SMESH_MAT2d::BE_ON_VERTEX );
 432     bool vAtStart2 = ( br2->getEnd(0)->_type == SMESH_MAT2d::BE_ON_VERTEX );
 433     size_t iEnd[4] = {
 434       vAtStart1 ? edgeIDs[0].back() : edgeIDs[0][0],
 435       vAtStart1 ? edgeIDs[1].back() : edgeIDs[1][0],
 436       vAtStart2 ? edgeIDs[2].back() : edgeIDs[2][0],
 437       vAtStart2 ? edgeIDs[3].back() : edgeIDs[3][0]
 438     };
 439
 440     set< size_t > connectedIDs;
 441     TopoDS_Vertex vCommon;
 442     // look for the same EDGEs
 443     for ( int i = 0; i < 2; ++i )
 444       for ( int j = 2; j < 4; ++j )
 445         if ( iEnd[i] == iEnd[j] )
 446         {
 447           connectedIDs.insert( edgeIDs[i].begin(), edgeIDs[i].end() );
 448           connectedIDs.insert( edgeIDs[j].begin(), edgeIDs[j].end() );
 449           i = j = 4;
 450         }
 451     if ( connectedIDs.empty() )
 452       // look for connected EDGEs
 453       for ( int i = 0; i < 2; ++i )
 454         for ( int j = 2; j < 4; ++j )
 455           if ( TopExp::CommonVertex( allEdges[ iEnd[i]], allEdges[ iEnd[j]], vCommon ))
 456           {
 457             connectedIDs.insert( edgeIDs[i].begin(), edgeIDs[i].end() );
 458             connectedIDs.insert( edgeIDs[j].begin(), edgeIDs[j].end() );
 459             i = j = 4;
 460           }
 461     if ( connectedIDs.empty() ||                     // nothing
 462          allEdges.size() - connectedIDs.size() < 2 ) // too many
 463       return false;
 464
 465     // set shortEdges in the order as in allEdges
 466     if ( connectedIDs.count( 0 ) &&
 467          connectedIDs.count( allEdges.size()-1 ))
 468     {
 469       size_t iE = allEdges.size()-1;
 470       while ( connectedIDs.count( iE-1 ))
 471         --iE;
 472       for ( size_t i = 0; i < connectedIDs.size(); ++i )
 473       {
 474         shortEdges.push_back( allEdges[ iE ]);
 475         iE = ( iE + 1 ) % allEdges.size();
 476       }
 477     }
 478     else
 479     {
 480       set< size_t >::iterator i = connectedIDs.begin();
 481       for ( ; i != connectedIDs.end(); ++i )
 482         shortEdges.push_back( allEdges[ *i ]);
 483     }
 484     return true;
 485   }
 486
 487   //================================================================================
 488   /*!
 489    * \brief Find EDGEs to discretize using projection from MA
 490    *  \param [in,out] theSinuFace - the FACE to be meshed
 491    *  \return bool - OK or not
 492    *
 493    * It separates all EDGEs into four sides of a quadrangle connected in the order:
 494    * theSinuEdges[0], theShortEdges[0], theSinuEdges[1], theShortEdges[1]
 495    */
 496   //================================================================================
 497
 498   bool getSinuousEdges( SMESH_MesherHelper& theHelper,
 499                         SinuousFace&        theSinuFace)
 500   {
 501     vector<TopoDS_Edge> * theSinuEdges  = & theSinuFace._sinuSide [0];
 502     vector<TopoDS_Edge> * theShortEdges = & theSinuFace._shortSide[0];
 503     theSinuEdges[0].clear();
 504     theSinuEdges[1].clear();
 505     theShortEdges[0].clear();
 506     theShortEdges[1].clear();
 507
 508     vector<TopoDS_Edge> & allEdges = theSinuFace._edges;
 509     const size_t nbEdges = allEdges.size();
 510     if ( nbEdges < 4 && theSinuFace._nbWires == 1 )
 511       return false;
 512
 513     if ( theSinuFace._nbWires == 2 ) // ring
 514     {
 515       size_t nbOutEdges = theSinuFace._nbEdgesInWire.front();
 516       theSinuEdges[0].assign ( allEdges.begin(), allEdges.begin() + nbOutEdges );
 517       theSinuEdges[1].assign ( allEdges.begin() + nbOutEdges, allEdges.end() );
 518       theSinuFace._sinuEdges = allEdges;
 519       return true;
 520     }
 521     if ( theSinuFace._nbWires > 2 )
 522       return false;
 523
 524     // create MedialAxis to find short edges by analyzing MA branches
 525     double minSegLen = getMinSegLen( theHelper, allEdges );
 526     SMESH_MAT2d::MedialAxis ma( theSinuFace.Face(), allEdges, minSegLen * 3 );
 527
 528     // in an initial request case, theFace represents a part of a river with almost parallel banks
 529     // so there should be two branch points
 530     using SMESH_MAT2d::BranchEnd;
 531     using SMESH_MAT2d::Branch;
 532     const vector< const BranchEnd* >& braPoints = ma.getBranchPoints();
 533     if ( braPoints.size() < 2 )
 534       return false;
 535     TopTools_MapOfShape shortMap;
 536     size_t nbBranchPoints = 0;
 537     for ( size_t i = 0; i < braPoints.size(); ++i )
 538     {
 539       vector< const Branch* > vertBranches; // branches with an end on VERTEX
 540       for ( size_t ib = 0; ib < braPoints[i]->_branches.size(); ++ib )
 541       {
 542         const Branch* branch = braPoints[i]->_branches[ ib ];
 543         if ( branch->hasEndOfType( SMESH_MAT2d::BE_ON_VERTEX ))
 544           vertBranches.push_back( branch );
 545       }
 546       if ( vertBranches.size() != 2 || braPoints[i]->_branches.size() != 3)
 547         continue;
 548
 549       // get common EDGEs of two branches
 550       if ( !getConnectedEdges( vertBranches[0], vertBranches[1],
 551                                allEdges, theShortEdges[ nbBranchPoints > 0 ] ))
 552         return false;
 553
 554       for ( size_t iS = 0; iS < theShortEdges[ nbBranchPoints ].size(); ++iS )
 555         shortMap.Add( theShortEdges[ nbBranchPoints ][ iS ]);
 556
 557       ++nbBranchPoints;
 558     }
 559
 560     if ( nbBranchPoints != 2 )
 561       return false;
 562
 563     // add to theSinuEdges all edges that are not theShortEdges
 564     vector< vector<TopoDS_Edge> > sinuEdges(1);
 565     TopoDS_Vertex vCommon;
 566     for ( size_t i = 0; i < allEdges.size(); ++i )
 567     {
 568       if ( !shortMap.Contains( allEdges[i] ))
 569       {
 570         if ( !sinuEdges.back().empty() )
 571           if ( !TopExp::CommonVertex( sinuEdges.back().back(), allEdges[ i ], vCommon ))
 572             sinuEdges.resize( sinuEdges.size() + 1 );
 573
 574         sinuEdges.back().push_back( allEdges[i] );
 575       }
 576     }
 577     if ( sinuEdges.size() == 3 )
 578     {
 579       if ( !TopExp::CommonVertex( sinuEdges.back().back(), sinuEdges[0][0], vCommon ))
 580         return false;
 581       vector<TopoDS_Edge>& last = sinuEdges.back();
 582       last.insert( last.end(), sinuEdges[0].begin(), sinuEdges[0].end() );
 583       sinuEdges[0].swap( last );
 584       sinuEdges.resize( 2 );
 585     }
 586     if ( sinuEdges.size() != 2 )
 587       return false;
 588
 589     theSinuEdges[0].swap( sinuEdges[0] );
 590     theSinuEdges[1].swap( sinuEdges[1] );
 591
 592     if ( !TopExp::CommonVertex( theSinuEdges[0].back(), theShortEdges[0][0], vCommon ) ||
 593          !vCommon.IsSame( theHelper.IthVertex( 1, theSinuEdges[0].back() )))
 594       theShortEdges[0].swap( theShortEdges[1] );
 595
 596     theSinuFace._sinuEdges = theSinuEdges[0];
 597     theSinuFace._sinuEdges.insert( theSinuFace._sinuEdges.end(),
 598                                    theSinuEdges[1].begin(), theSinuEdges[1].end() );
 599
 600     return ( theShortEdges[0].size() > 0 && theShortEdges[1].size() > 0 &&
 601              theSinuEdges [0].size() > 0 && theSinuEdges [1].size() > 0 );
 602
 603     // the sinuous EDGEs can be composite and C0 continuous,
 604     // therefor we use a complex criterion to find TWO short non-sinuous EDGEs
 605     // and the rest EDGEs will be treated as sinuous.
 606     // A short edge should have the following features:
 607     // a) straight
 608     // b) short
 609     // c) with convex corners at ends
 610     // d) far from the other short EDGE
 611
 612     // vector< double > isStraightEdge( nbEdges, 0 ); // criterion value
 613
 614     // // a0) evaluate continuity
 615     // const double contiWgt = 0.5; // weight of continuity in the criterion
 616     // multimap< int, TopoDS_Edge > continuity;
 617     // for ( size_t i = 0; i < nbEdges; ++I )
 618     // {
 619     //   BRepAdaptor_Curve curve( allEdges[i] );
 620     //   GeomAbs_Shape C = GeomAbs_CN;
 621     //   try:
 622     //     C = curve.Continuity(); // C0, G1, C1, G2, C2, C3, CN
 623     //   catch ( Standard_Failure ) {}
 624     //   continuity.insert( make_pair( C, allEdges[i] ));
 625     //   isStraight[i] += double( C ) / double( CN ) * contiWgt;
 626     // }
 627
 628     // // try to choose by continuity
 629     // int mostStraight = (int) continuity.rbegin()->first;
 630     // int lessStraight = (int) continuity.begin()->first;
 631     // if ( mostStraight != lessStraight )
 632     // {
 633     //   int nbStraight = continuity.count( mostStraight );
 634     //   if ( nbStraight == 2 )
 635     //   {
 636     //     getTwo( /*least=*/false, continuity, theShortEdges, theSinuEdges );
 637     //   }
 638     //   else if ( nbStraight == 3 && nbEdges == 4 )
 639     //   {
 640     //     theSinuEdges.push_back( continuity.begin()->second );
 641     //     vector<TopoDS_Edge>::iterator it =
 642     //       std::find( allEdges.begin(), allEdges.end(), theSinuEdges[0] );
 643     //     int i = std::distance( allEdges.begin(), it );
 644     //     theSinuEdges .push_back( allEdges[( i+2 )%4 ]);
 645     //     theShortEdges.push_back( allEdges[( i+1 )%4 ]);
 646     //     theShortEdges.push_back( allEdges[( i+3 )%4 ]);
 647     //   }
 648     //   if ( theShortEdges.size() == 2 )
 649     //     return true;
 650     // }
 651
 652     // // a) curvature; evaluate aspect ratio
 653     // {
 654     //   const double curvWgt = 0.5;
 655     //   for ( size_t i = 0; i < nbEdges; ++I )
 656     //   {
 657     //     BRepAdaptor_Curve curve( allEdges[i] );
 658     //     double curvature = 1;
 659     //     if ( !curve.IsClosed() )
 660     //     {
 661     //       const double f = curve.FirstParameter(), l = curve.LastParameter();
 662     //       gp_Pnt pf = curve.Value( f ), pl = curve.Value( l );
 663     //       gp_Lin line( pf, pl.XYZ() - pf.XYZ() );
 664     //       double distMax = 0;
 665     //       for ( double u = f; u < l; u += (l-f)/30. )
 666     //         distMax = Max( distMax, line.SquareDistance( curve.Value( u )));
 667     //       curvature = Sqrt( distMax ) / ( pf.Distance( pl ));
 668     //     }
 669     //     isStraight[i] += curvWgt / (              curvature + 1e-20 );
 670     //   }
 671     // }
 672     // // b) length
 673     // {
 674     //   const double lenWgt = 0.5;
 675     //   for ( size_t i = 0; i < nbEdges; ++I )
 676     //   {
 677     //     double length = SMESH_Algo::Length( allEdges[i] );
 678     //     if ( length > 0 )
 679     //       isStraight[i] += lenWgt / length;
 680     //   }
 681     // }
 682     // // c) with convex corners at ends
 683     // {
 684     //   const double cornerWgt = 0.25;
 685     //   for ( size_t i = 0; i < nbEdges; ++I )
 686     //   {
 687     //     double convex = 0;
 688     //     int iPrev = SMESH_MesherHelper::WrapIndex( int(i)-1, nbEdges );
 689     //     int iNext = SMESH_MesherHelper::WrapIndex( int(i)+1, nbEdges );
 690     //     TopoDS_Vertex v = helper.IthVertex( 0, allEdges[i] );
 691     //     double angle = SMESH_MesherHelper::GetAngle( allEdges[iPrev], allEdges[i], theFace, v );
 692     //     if ( angle < M_PI ) // [-PI; PI]
 693     //       convex += ( angle + M_PI ) / M_PI / M_PI;
 694     //     v = helper.IthVertex( 1, allEdges[i] );
 695     //     angle = SMESH_MesherHelper::GetAngle( allEdges[iNext], allEdges[i], theFace, v );
 696     //     if ( angle < M_PI ) // [-PI; PI]
 697     //       convex += ( angle + M_PI ) / M_PI / M_PI;
 698     //     isStraight[i] += cornerWgt * convex;
 699     //   }
 700     // }
 701   }
 702
 703   //================================================================================
 704   /*!
 705    * \brief Creates an EDGE from a sole branch of MA
 706    */
 707   //================================================================================
 708
 709   TopoDS_Edge makeEdgeFromMA( SMESH_MesherHelper&            theHelper,
 710                               const SMESH_MAT2d::MedialAxis& theMA,
 711                               const double                   theMinSegLen)
 712   {
 713     if ( theMA.nbBranches() != 1 )
 714       return TopoDS_Edge();
 715
 716     vector< gp_XY > uv;
 717     theMA.getPoints( theMA.getBranch(0), uv );
 718     if ( uv.size() < 2 )
 719       return TopoDS_Edge();
 720
 721     TopoDS_Face face = TopoDS::Face( theHelper.GetSubShape() );
 722     Handle(Geom_Surface) surface = BRep_Tool::Surface( face );
 723
 724     vector< gp_Pnt > pnt;
 725     pnt.reserve( uv.size() * 2 );
 726     pnt.push_back( surface->Value( uv[0].X(), uv[0].Y() ));
 727     for ( size_t i = 1; i < uv.size(); ++i )
 728     {
 729       gp_Pnt p = surface->Value( uv[i].X(), uv[i].Y() );
 730       int nbDiv = int( p.Distance( pnt.back() ) / theMinSegLen );
 731       for ( int iD = 1; iD < nbDiv; ++iD )
 732       {
 733         double  R = iD / double( nbDiv );
 734         gp_XY uvR = uv[i-1] * (1 - R) + uv[i] * R;
 735         pnt.push_back( surface->Value( uvR.X(), uvR.Y() ));
 736       }
 737       pnt.push_back( p );
 738     }
 739
 740     // cout << "from salome.geom import geomBuilder" << endl;
 741     // cout << "geompy = geomBuilder.New(salome.myStudy)" << endl;
 742     Handle(TColgp_HArray1OfPnt) points = new TColgp_HArray1OfPnt(1, pnt.size());
 743     for ( size_t i = 0; i < pnt.size(); ++i )
 744     {
 745       gp_Pnt& p = pnt[i];
 746       points->SetValue( i+1, p );
 747       // cout << "geompy.MakeVertex( "<< p.X()<<", " << p.Y()<<", " << p.Z()
 748       //      <<" theName = 'p_" << i << "')" << endl;
 749     }
 750
 751     GeomAPI_Interpolate interpol( points, /*isClosed=*/false, gp::Resolution());
 752     interpol.Perform();
 753     if ( !interpol.IsDone())
 754       return TopoDS_Edge();
 755
 756     TopoDS_Edge branchEdge = BRepBuilderAPI_MakeEdge(interpol.Curve());
 757     return branchEdge;
 758   }
 759
 760   //================================================================================
 761   /*!
 762    * \brief Returns a type of shape, to which a hypothesis used to mesh a given edge is assigned
 763    */
 764   //================================================================================
 765
 766   TopAbs_ShapeEnum getHypShape( SMESH_Mesh* mesh, const TopoDS_Shape& edge )
 767   {
 768     TopAbs_ShapeEnum shapeType = TopAbs_SHAPE;
 769
 770     SMESH_subMesh* sm = mesh->GetSubMesh( edge );
 771     SMESH_Algo*  algo = sm->GetAlgo();
 772     if ( !algo ) return shapeType;
 773
 774     const list <const SMESHDS_Hypothesis *> & hyps =
 775       algo->GetUsedHypothesis( *mesh, edge, /*ignoreAuxiliary=*/true );
 776     if ( hyps.empty() ) return shapeType;
 777
 778     TopoDS_Shape shapeOfHyp =
 779       SMESH_MesherHelper::GetShapeOfHypothesis( hyps.front(), edge, mesh);
 780
 781     return SMESH_MesherHelper::GetGroupType( shapeOfHyp, /*woCompound=*/true);
 782   }
 783
 784   //================================================================================
 785   /*!
 786    * \brief Discretize a sole branch of MA an returns parameters of divisions on MA
 787    */
 788   //================================================================================
 789
 790   bool divideMA( SMESH_MesherHelper&            theHelper,
 791                  const SMESH_MAT2d::MedialAxis& theMA,
 792                  const SinuousFace&             theSinuFace,
 793                  SMESH_Algo*                    the1dAlgo,
 794                  const double                   theMinSegLen,
 795                  vector<double>&                theMAParams )
 796   {
 797     // Check if all EDGEs of one size are meshed, then MA discretization is not needed
 798     SMESH_Mesh* mesh = theHelper.GetMesh();
 799     size_t nbComputedEdges[2] = { 0, 0 };
 800     for ( size_t iS = 0; iS < 2; ++iS )
 801       for ( size_t i = 0; i < theSinuFace._sinuSide[iS].size(); ++i )
 802       {
 803         const TopoDS_Edge& sinuEdge = theSinuFace._sinuSide[iS][i];
 804         SMESH_subMesh*           sm = mesh->GetSubMesh( sinuEdge );
 805         bool             isComputed = ( !sm->IsEmpty() );
 806         if ( isComputed )
 807         {
 808           TopAbs_ShapeEnum shape = getHypShape( mesh, sinuEdge );
 809           if ( shape == TopAbs_SHAPE || shape <= TopAbs_FACE )
 810           {
 811             // EDGE computed using global hypothesis -> clear it
 812             bool hasComputedFace = false;
 813             PShapeIteratorPtr faceIt = theHelper.GetAncestors( sinuEdge, *mesh, TopAbs_FACE );
 814             while ( const TopoDS_Shape* face = faceIt->next() )
 815               if (( !face->IsSame( theSinuFace.Face() )) &&
 816                   ( hasComputedFace = !mesh->GetSubMesh( *face )->IsEmpty() ))
 817                 break;
 818             if ( !hasComputedFace )
 819             {
 820               sm->ComputeStateEngine( SMESH_subMesh::CLEAN );
 821               isComputed = false;
 822             }
 823           }
 824         }
 825         nbComputedEdges[ iS ] += isComputed;
 826       }
 827     if ( nbComputedEdges[0] == theSinuFace._sinuSide[0].size() ||
 828          nbComputedEdges[1] == theSinuFace._sinuSide[1].size() )
 829       return true; // discretization is not needed
 830
 831     // Make MA EDGE
 832     TopoDS_Edge branchEdge = makeEdgeFromMA( theHelper, theMA, theMinSegLen );
 833     if ( branchEdge.IsNull() )
 834       return false;
 835
 836     // const char* file = "/misc/dn25/salome/eap/salome/misc/tmp/MAedge.brep";
 837     // BRepTools::Write( branchEdge, file);
 838     // cout << "Write " << file << endl;
 839
 840
 841     // Find 1D algo to mesh branchEdge
 842
 843     // look for a most local 1D hyp assigned to the FACE
 844     int mostSimpleShape = -1, maxShape = TopAbs_EDGE;
 845     TopoDS_Edge edge;
 846     for ( size_t i = 0; i < theSinuFace._sinuEdges.size(); ++i )
 847     {
 848       TopAbs_ShapeEnum shapeType = getHypShape( mesh, theSinuFace._sinuEdges[i] );
 849       if ( mostSimpleShape < shapeType && shapeType < maxShape )
 850       {
 851         edge = theSinuFace._sinuEdges[i];
 852         mostSimpleShape = shapeType;
 853       }
 854     }
 855
 856     SMESH_Algo* algo = the1dAlgo;
 857     if ( mostSimpleShape > -1 )
 858     {
 859       algo = mesh->GetSubMesh( edge )->GetAlgo();
 860       SMESH_Hypothesis::Hypothesis_Status status;
 861       if ( !algo->CheckHypothesis( *mesh, edge, status ))
 862         algo = the1dAlgo;
 863     }
 864
 865     TmpMesh tmpMesh;
 866     tmpMesh.ShapeToMesh( branchEdge );
 867     try {
 868       mesh->GetGen()->Compute( tmpMesh, branchEdge, true, true ); // make nodes on VERTEXes
 869       if ( !algo->Compute( tmpMesh, branchEdge ))
 870         return false;
 871     }
 872     catch (...) {
 873       return false;
 874     }
 875     return SMESH_Algo::GetNodeParamOnEdge( tmpMesh.GetMeshDS(), branchEdge, theMAParams );
 876   }
 877
 878   //================================================================================
 879   /*!
 880    * \brief Select division parameters on MA and make them coincide at ends with
 881    *        projections of VERTEXes to MA for a given pair of opposite EDGEs
 882    *  \param [in] theEdgePairInd - index of the EDGE pair
 883    *  \param [in] theDivPoints - the BranchPoint's dividing MA into parts each
 884    *         corresponding to a unique pair of opposite EDGEs
 885    *  \param [in] theMAParams - the MA division parameters
 886    *  \param [out] theSelectedMAParams - the selected MA parameters
 887    *  \return bool - is OK
 888    */
 889   //================================================================================
 890
 891   bool getParamsForEdgePair( const size_t                              theEdgePairInd,
 892                              const vector< SMESH_MAT2d::BranchPoint >& theDivPoints,
 893                              const vector<double>&                     theMAParams,
 894                              vector<double>&                           theSelectedMAParams)
 895   {
 896     if ( theDivPoints.empty() )
 897     {
 898       theSelectedMAParams = theMAParams;
 899       return true;
 900     }
 901     if ( theEdgePairInd > theDivPoints.size() || theMAParams.empty() )
 902       return false;
 903
 904     // find a range of params to copy
 905
 906     double par1 = 0;
 907     size_t iPar1 = 0;
 908     if ( theEdgePairInd > 0 )
 909     {
 910       const SMESH_MAT2d::BranchPoint& bp = theDivPoints[ theEdgePairInd-1 ];
 911       bp._branch->getParameter( bp, par1 );
 912       while ( theMAParams[ iPar1 ] < par1 ) ++iPar1;
 913       if ( par1 - theMAParams[ iPar1-1 ] < theMAParams[ iPar1 ] - par1 )
 914         --iPar1;
 915     }
 916
 917     double par2 = 1;
 918     size_t iPar2 = theMAParams.size() - 1;
 919     if ( theEdgePairInd < theDivPoints.size() )
 920     {
 921       const SMESH_MAT2d::BranchPoint& bp = theDivPoints[ theEdgePairInd ];
 922       bp._branch->getParameter( bp, par2 );
 923       iPar2 = iPar1;
 924       while ( theMAParams[ iPar2 ] < par2 ) ++iPar2;
 925       if ( par2 - theMAParams[ iPar2-1 ] < theMAParams[ iPar2 ] - par2 )
 926         --iPar2;
 927     }
 928
 929     theSelectedMAParams.assign( theMAParams.begin() + iPar1,
 930                                 theMAParams.begin() + iPar2 + 1 );
 931
 932     // adjust theSelectedMAParams to fit between par1 and par2
 933
 934     double d = par1 - theSelectedMAParams[0];
 935     double f = ( par2 - par1 ) / ( theSelectedMAParams.back() - theSelectedMAParams[0] );
 936
 937     for ( size_t i = 0; i < theSelectedMAParams.size(); ++i )
 938     {
 939       theSelectedMAParams[i] += d;
 940       theSelectedMAParams[i] = par1 + ( theSelectedMAParams[i] - par1 ) * f;
 941     }
 942
 943     return true;
 944   }
 945
 946   //--------------------------------------------------------------------------------
 947   // node or node parameter on EDGE
 948   struct NodePoint
 949   {
 950     const SMDS_MeshNode* _node;
 951     double               _u;
 952     int                  _edgeInd; // index in theSinuEdges vector
 953
 954     NodePoint(): _node(0), _u(0), _edgeInd(-1) {}
 955     NodePoint(const SMDS_MeshNode* n, double u, size_t iEdge ): _node(n), _u(u), _edgeInd(iEdge) {}
 956     NodePoint(double u, size_t iEdge) : _node(0), _u(u), _edgeInd(iEdge) {}
 957     NodePoint(const SMESH_MAT2d::BoundaryPoint& p) : _node(0), _u(p._param), _edgeInd(p._edgeIndex) {}
 958     gp_Pnt Point(const vector< Handle(Geom_Curve) >& curves) const
 959     {
 960       return _node ? SMESH_TNodeXYZ(_node) : curves[ _edgeInd ]->Value( _u );
 961     }
 962   };
 963   typedef multimap< double, pair< NodePoint, NodePoint > > TMAPar2NPoints;
 964
 965   //================================================================================
 966   /*!
 967    * \brief Finds a VERTEX corresponding to a point on EDGE, which is also filled
 968    *        with a node on the VERTEX, present or created
 969    *  \param [in,out] theNodePnt - the node position on the EDGE
 970    *  \param [in] theSinuEdges - the sinuous EDGEs
 971    *  \param [in] theMeshDS - the mesh
 972    *  \return bool - true if the \a theBndPnt is on VERTEX
 973    */
 974   //================================================================================
 975
 976   bool findVertexAndNode( NodePoint&                  theNodePnt,
 977                           const vector<TopoDS_Edge>&  theSinuEdges,
 978                           SMESHDS_Mesh*               theMeshDS = 0,
 979                           size_t                      theEdgeIndPrev = 0,
 980                           size_t                      theEdgeIndNext = 0)
 981   {
 982     if ( theNodePnt._edgeInd >= theSinuEdges.size() )
 983       return false;
 984
 985     double f,l;
 986     BRep_Tool::Range( theSinuEdges[ theNodePnt._edgeInd ], f,l );
 987     const double tol = 1e-3 * ( l - f );
 988
 989     TopoDS_Vertex V;
 990     if      ( Abs( f - theNodePnt._u ) < tol )
 991       V = SMESH_MesherHelper::IthVertex( 0, theSinuEdges[ theNodePnt._edgeInd ], /*CumOri=*/false);
 992     else if ( Abs( l - theNodePnt._u ) < tol )
 993       V = SMESH_MesherHelper::IthVertex( 1, theSinuEdges[ theNodePnt._edgeInd ], /*CumOri=*/false);
 994     else if ( theEdgeIndPrev != theEdgeIndNext )
 995       TopExp::CommonVertex( theSinuEdges[theEdgeIndPrev], theSinuEdges[theEdgeIndNext], V );
 996
 997     if ( !V.IsNull() && theMeshDS )
 998     {
 999       theNodePnt._node = SMESH_Algo::VertexNode( V, theMeshDS );
1000       if ( !theNodePnt._node )
1001       {
1002         gp_Pnt p = BRep_Tool::Pnt( V );
1003         theNodePnt._node = theMeshDS->AddNode( p.X(), p.Y(), p.Z() );
1004         theMeshDS->SetNodeOnVertex( theNodePnt._node, V );
1005       }
1006     }
1007     return !V.IsNull();
1008   }
1009
1010   //================================================================================
1011   /*!
1012    * \brief Add to the map of NodePoint's those on VERTEXes
1013    *  \param [in,out] theHelper - the helper
1014    *  \param [in] theMA - Medial Axis
1015    *  \param [in] theMinSegLen - minimal segment length
1016    *  \param [in] theDivPoints - projections of VERTEXes to MA
1017    *  \param [in] theSinuEdges - the sinuous EDGEs
1018    *  \param [in] theSideEdgeIDs - indices of sinuous EDGEs per side
1019    *  \param [in] theIsEdgeComputed - is sinuous EGDE is meshed
1020    *  \param [in,out] thePointsOnE - the map to fill
1021    *  \param [out] theNodes2Merge - the map of nodes to merge
1022    */
1023   //================================================================================
1024
1025   bool projectVertices( SMESH_MesherHelper&                 theHelper,
1026                         const SMESH_MAT2d::MedialAxis&      theMA,
1027                         vector< SMESH_MAT2d::BranchPoint >& theDivPoints,
1028                         const vector< std::size_t > &       theEdgeIDs1,
1029                         const vector< std::size_t > &       theEdgeIDs2,
1030                         const vector< bool >&               theIsEdgeComputed,
1031                         TMAPar2NPoints &                    thePointsOnE,
1032                         SinuousFace&                        theSinuFace)
1033   {
1034     SMESHDS_Mesh* meshDS = theHelper.GetMeshDS();
1035     const vector< TopoDS_Edge >&     theSinuEdges = theSinuFace._sinuEdges;
1036     const vector< Handle(Geom_Curve) >& theCurves = theSinuFace._sinuCurves;
1037
1038     double uMA;
1039     SMESH_MAT2d::BoundaryPoint bp[2];
1040     const SMESH_MAT2d::Branch& branch = *theMA.getBranch(0);
1041     {
1042       // add to thePointsOnE NodePoint's of ends of theSinuEdges
1043       if ( !branch.getBoundaryPoints( 0., bp[0], bp[1] ) ||
1044            !theMA.getBoundary().moveToClosestEdgeEnd( bp[0] )) return false;
1045       if ( !theSinuFace.IsRing() &&
1046            !theMA.getBoundary().moveToClosestEdgeEnd( bp[1] )) return false;
1047       NodePoint np0( bp[0] ), np1( bp[1] );
1048       findVertexAndNode( np0, theSinuEdges, meshDS );
1049       findVertexAndNode( np1, theSinuEdges, meshDS );
1050       thePointsOnE.insert( make_pair( -0.1, make_pair( np0, np1 )));
1051     }
1052     if ( !theSinuFace.IsRing() )
1053     {
1054       if ( !branch.getBoundaryPoints( 1., bp[0], bp[1] ) ||
1055            !theMA.getBoundary().moveToClosestEdgeEnd( bp[0] ) ||
1056            !theMA.getBoundary().moveToClosestEdgeEnd( bp[1] )) return false;
1057       NodePoint np0( bp[0] ), np1( bp[1] );
1058       findVertexAndNode( np0, theSinuEdges, meshDS );
1059       findVertexAndNode( np1, theSinuEdges, meshDS );
1060       thePointsOnE.insert( make_pair( 1.1, make_pair( np0, np1)));
1061     }
1062
1063     // project theDivPoints
1064
1065     if ( theDivPoints.empty() )
1066       return true;
1067
1068     for ( size_t i = 0; i < theDivPoints.size(); ++i )
1069     {
1070       if ( !branch.getParameter( theDivPoints[i], uMA ))
1071         return false;
1072       if ( !branch.getBoundaryPoints( theDivPoints[i], bp[0], bp[1] ))
1073         return false;
1074
1075       NodePoint  np[2] = {
1076         NodePoint( bp[0] ),
1077         NodePoint( bp[1] )
1078       };
1079       bool isVertex[2] = {
1080         findVertexAndNode( np[0], theSinuEdges, meshDS, theEdgeIDs1[i], theEdgeIDs1[i+1] ),
1081         findVertexAndNode( np[1], theSinuEdges, meshDS, theEdgeIDs2[i], theEdgeIDs2[i+1] )
1082       };
1083
1084       TMAPar2NPoints::iterator u2NP =
1085         thePointsOnE.insert( make_pair( uMA, make_pair( np[0], np[1])));//.first;
1086
1087       if ( !isVertex[0] && !isVertex[1] ) return false; // error
1088       if ( isVertex[0] && isVertex[1] )
1089         continue;
1090       const size_t iVert = isVertex[0] ? 0 : 1;
1091       const size_t iNode = 1 - iVert;
1092
1093       bool isOppComputed = theIsEdgeComputed[ np[ iNode ]._edgeInd ];
1094       if ( !isOppComputed )
1095         continue;
1096
1097       // a VERTEX is projected on a meshed EDGE; there are two options:
1098       // 1) a projected point is joined with a closet node if a strip between this and neighbor
1099       // projection is WIDE enough; joining is done by creating a node coincident with the
1100       //  existing node which will be merged together after all;
1101       // 2) a neighbor projection is merged with this one if it is TOO CLOSE; a node of deleted
1102       // projection is set to the BoundaryPoint of this projection
1103
1104       // evaluate distance to neighbor projections
1105       const double rShort = 0.2;
1106       bool isShortPrev[2], isShortNext[2];
1107       TMAPar2NPoints::iterator u2NPPrev = u2NP, u2NPNext = u2NP;
1108       --u2NPPrev; ++u2NPNext;
1109       // bool hasPrev = ( u2NP     != thePointsOnE.begin() );
1110       // bool hasNext = ( u2NPNext != thePointsOnE.end() );
1111       // if ( !hasPrev ) u2NPPrev = u2NP0;
1112       // if ( !hasNext ) u2NPNext = u2NP1;
1113       for ( int iS = 0; iS < 2; ++iS ) // side with Vertex and side with Nodes
1114       {
1115         NodePoint np     = get( u2NP->second,     iS );
1116         NodePoint npPrev = get( u2NPPrev->second, iS );
1117         NodePoint npNext = get( u2NPNext->second, iS );
1118         gp_Pnt     p     = np    .Point( theCurves );
1119         gp_Pnt     pPrev = npPrev.Point( theCurves );
1120         gp_Pnt     pNext = npNext.Point( theCurves );
1121         double  distPrev = p.Distance( pPrev );
1122         double  distNext = p.Distance( pNext );
1123         double         r = distPrev / ( distPrev + distNext );
1124         isShortPrev[iS] = ( r < rShort );
1125         isShortNext[iS] = (( 1 - r ) > ( 1 - rShort ));
1126       }
1127       // if ( !hasPrev ) isShortPrev[0] = isShortPrev[1] = false;
1128       // if ( !hasNext ) isShortNext[0] = isShortNext[1] = false;
1129
1130       TMAPar2NPoints::iterator u2NPClose;
1131
1132       if (( isShortPrev[0] && isShortPrev[1] ) || // option 2) -> remove a too close projection
1133           ( isShortNext[0] && isShortNext[1] ))
1134       {
1135         u2NPClose = isShortPrev[0] ? u2NPPrev : u2NPNext;
1136         NodePoint& npProj  = get( u2NP->second,      iNode ); // NP of VERTEX projection
1137         NodePoint npCloseN = get( u2NPClose->second, iNode ); // NP close to npProj
1138         NodePoint npCloseV = get( u2NPClose->second, iVert ); // NP close to VERTEX
1139         if ( !npCloseV._node )
1140         {
1141           npProj = npCloseN;
1142           thePointsOnE.erase( isShortPrev[0] ? u2NPPrev : u2NPNext );
1143           continue;
1144         }
1145         else
1146         {
1147           // can't remove the neighbor projection as it is also from VERTEX, -> option 1)
1148         }
1149       }
1150       // else: option 1) - wide enough -> "duplicate" existing node
1151       {
1152         u2NPClose = isShortPrev[ iNode ] ? u2NPPrev : u2NPNext;
1153         NodePoint& npProj   = get( u2NP->second,      iNode ); // NP of VERTEX projection
1154         NodePoint& npCloseN = get( u2NPClose->second, iNode ); // NP close to npProj
1155         npProj = npCloseN;
1156         npProj._node = 0;
1157         //npProj._edgeInd = npCloseN._edgeInd;
1158         // npProj._u       = npCloseN._u + 1e-3 * Abs( get( u2NPPrev->second, iNode )._u -
1159         //                                             get( u2NPNext->second, iNode )._u );
1160         // gp_Pnt        p = npProj.Point( theCurves );
1161         // npProj._node    = meshDS->AddNode( p.X(), p.Y(), p.Z() );
1162         // meshDS->SetNodeOnEdge( npProj._node, theSinuEdges[ npProj._edgeInd ], npProj._u  );
1163
1164         //theNodes2Merge[ npCloseN._node ].push_back( npProj._node );
1165       }
1166     }
1167     return true;
1168   }
1169
1170   double getUOnEdgeByPoint( const size_t     iEdge,
1171                             const NodePoint* point,
1172                             SinuousFace&     sinuFace )
1173   {
1174     if ( point->_edgeInd == iEdge )
1175       return point->_u;
1176
1177     TopoDS_Vertex V0 = TopExp::FirstVertex( sinuFace._sinuEdges[ iEdge ]);
1178     TopoDS_Vertex V1 = TopExp::LastVertex ( sinuFace._sinuEdges[ iEdge ]);
1179     gp_Pnt p0 = BRep_Tool::Pnt( V0 );
1180     gp_Pnt p1 = BRep_Tool::Pnt( V1 );
1181     gp_Pnt  p = point->Point( sinuFace._sinuCurves );
1182
1183     double f,l;
1184     BRep_Tool::Range( sinuFace._sinuEdges[ iEdge ], f,l );
1185     return p.SquareDistance( p0 ) < p.SquareDistance( p1 ) ? f : l;
1186   }
1187
1188   //================================================================================
1189   /*!
1190    * \brief Move coincident nodes to make node params on EDGE unique
1191    *  \param [in] theHelper - the helper
1192    *  \param [in] thePointsOnE - nodes on two opposite river sides
1193    *  \param [in] theSinuFace - the sinuous FACE
1194    *  \param [out] theNodes2Merge - the map of nodes to merge
1195    */
1196   //================================================================================
1197
1198   void separateNodes( SMESH_MesherHelper&            theHelper,
1199                       const SMESH_MAT2d::MedialAxis& theMA,
1200                       TMAPar2NPoints &               thePointsOnE,
1201                       SinuousFace&                   theSinuFace )
1202   {
1203     if ( thePointsOnE.size() < 2 )
1204       return;
1205
1206     SMESHDS_Mesh* meshDS = theHelper.GetMeshDS();
1207     const vector<TopoDS_Edge>&    theSinuEdges = theSinuFace._sinuEdges;
1208     const vector< Handle(Geom_Curve) >& curves = theSinuFace._sinuCurves;
1209
1210     SMESH_MAT2d::BoundaryPoint bp[2];
1211     const SMESH_MAT2d::Branch& branch = *theMA.getBranch(0);
1212
1213     typedef TMAPar2NPoints::iterator TIterator;
1214
1215     for ( int iSide = 0; iSide < 2; ++iSide ) // loop on two sinuous sides
1216     {
1217       // get a tolerance to compare points
1218       double tol = Precision::Confusion();
1219       for ( size_t i = 0; i < theSinuFace._sinuSide[ iSide ].size(); ++i )
1220         tol = Max( tol , BRep_Tool::Tolerance( theSinuFace._sinuSide[ iSide ][ i ]));
1221
1222       // find coincident points
1223       TIterator u2NP = thePointsOnE.begin();
1224       vector< TIterator > sameU2NP( 1, u2NP++ );
1225       while ( u2NP != thePointsOnE.end() )
1226       {
1227         for ( ; u2NP != thePointsOnE.end(); ++u2NP )
1228         {
1229           NodePoint& np1 = get( sameU2NP.back()->second, iSide );
1230           NodePoint& np2 = get( u2NP           ->second, iSide );
1231
1232           if (( !np1._node || !np2._node ) &&
1233               ( np1.Point( curves ).SquareDistance( np2.Point( curves )) < tol*tol ))
1234           {
1235             sameU2NP.push_back( u2NP );
1236           }
1237           else if ( sameU2NP.size() == 1 )
1238           {
1239             sameU2NP[ 0 ] = u2NP;
1240           }
1241           else
1242           {
1243             break;
1244           }
1245         }
1246
1247         if ( sameU2NP.size() > 1 )
1248         {
1249           // find an existing node on VERTEX among sameU2NP and get underlying EDGEs
1250           const SMDS_MeshNode* existingNode = 0;
1251           set< int > edgeInds;
1252           NodePoint* np;
1253           for ( size_t i = 0; i < sameU2NP.size(); ++i )
1254           {
1255             np = &get( sameU2NP[i]->second, iSide );
1256             if ( np->_node )
1257               if ( !existingNode || np->_node->GetPosition()->GetDim() == 0 )
1258                 existingNode = np->_node;
1259             edgeInds.insert( np->_edgeInd );
1260           }
1261           list< const SMDS_MeshNode* >& mergeNodes = theSinuFace._nodesToMerge[ existingNode ];
1262
1263           TIterator u2NPprev = sameU2NP.front();
1264           TIterator u2NPnext = sameU2NP.back() ;
1265           if ( u2NPprev->first > 0. ) --u2NPprev;
1266           if ( u2NPnext->first < 1. ) ++u2NPprev;
1267
1268           set< int >::iterator edgeID = edgeInds.begin();
1269           for ( ; edgeID != edgeInds.end(); ++edgeID )
1270           {
1271             // get U range on iEdge within which the equal points will be distributed
1272             double u0, u1;
1273             np = &get( u2NPprev->second, iSide );
1274             u0 = getUOnEdgeByPoint( *edgeID, np, theSinuFace );
1275
1276             np = &get( u2NPnext->second, iSide );
1277             u1 = getUOnEdgeByPoint( *edgeID, np, theSinuFace );
1278
1279             if ( u0 == u1 )
1280             {
1281               if ( np->_node ) --u2NPprev;
1282               else             ++u2NPnext;
1283               np = &get( u2NPprev->second, iSide );
1284               u0 = getUOnEdgeByPoint( *edgeID, np, theSinuFace );
1285               np = &get( u2NPnext->second, iSide );
1286               u1 = getUOnEdgeByPoint( *edgeID, np, theSinuFace );
1287             }
1288
1289             // distribute points and create nodes
1290             double du = ( u1 - u0 ) / ( sameU2NP.size() + 1 );
1291             double u  = u0 + du;
1292             for ( size_t i = 0; i < sameU2NP.size(); ++i )
1293             {
1294               np = &get( sameU2NP[i]->second, iSide );
1295               if ( !np->_node && *edgeID == np->_edgeInd )
1296               {
1297                 np->_u = u;
1298                 u += du;
1299                 gp_Pnt p = np->Point( curves );
1300                 np->_node = meshDS->AddNode( p.X(), p.Y(), p.Z() );
1301                 meshDS->SetNodeOnEdge( np->_node, theSinuEdges[ *edgeID ], np->_u  );
1302                 //mergeNodes.push_back( np->_node );
1303               }
1304             }
1305           }
1306
1307           sameU2NP.resize( 1 );
1308           u2NP = ++sameU2NP.back();
1309           sameU2NP[ 0 ] = u2NP;
1310
1311         } // if ( sameU2NP.size() > 1 )
1312       } // while ( u2NP != thePointsOnE.end() )
1313     } // for ( int iSide = 0; iSide < 2; ++iSide )
1314
1315     return;
1316   } // separateNodes()
1317
1318   //================================================================================
1319   /*!
1320    * \brief Setup sides of SinuousFace::_quad
1321    *  \param [in] theHelper - helper
1322    *  \param [in] thePointsOnEdges - NodePoint's on sinuous sides
1323    *  \param [in,out] theSinuFace - the FACE
1324    *  \param [in] the1dAlgo - algorithm to use for radial discretization of a ring FACE
1325    *  \return bool - is OK
1326    */
1327   //================================================================================
1328
1329   bool setQuadSides(SMESH_MesherHelper&   theHelper,
1330                     const TMAPar2NPoints& thePointsOnEdges,
1331                     SinuousFace&          theFace,
1332                     SMESH_Algo*           the1dAlgo)
1333   {
1334     SMESH_Mesh*               mesh = theHelper.GetMesh();
1335     const TopoDS_Face&        face = theFace._quad->face;
1336     SMESH_ProxyMesh::Ptr proxyMesh = StdMeshers_ViscousLayers2D::Compute( *mesh, face );
1337     if ( !proxyMesh )
1338       return false;
1339
1340     list< TopoDS_Edge > side[4];
1341     side[0].insert( side[0].end(), theFace._shortSide[0].begin(), theFace._shortSide[0].end() );
1342     side[1].insert( side[1].end(), theFace._sinuSide[1].begin(),  theFace._sinuSide[1].end() );
1343     side[2].insert( side[2].end(), theFace._shortSide[1].begin(), theFace._shortSide[1].end() );
1344     side[3].insert( side[3].end(), theFace._sinuSide[0].begin(),  theFace._sinuSide[0].end() );
1345
1346     for ( int i = 0; i < 4; ++i )
1347     {
1348       theFace._quad->side[i] = StdMeshers_FaceSide::New( face, side[i], mesh, i < QUAD_TOP_SIDE,
1349                                                          /*skipMediumNodes=*/true, proxyMesh );
1350     }
1351
1352     if ( theFace.IsRing() )
1353     {
1354       // --------------------------------------
1355       // Discretize a ring in radial direction
1356       // --------------------------------------
1357
1358       if ( thePointsOnEdges.size() < 4 )
1359         return false;
1360
1361       // find most distant opposite nodes
1362       double maxDist = 0, dist;
1363       TMAPar2NPoints::const_iterator u2NPdist, u2NP = thePointsOnEdges.begin();
1364       for ( ; u2NP != thePointsOnEdges.end(); ++u2NP )
1365       {
1366         SMESH_TNodeXYZ        xyz( u2NP->second.first._node ); // node out
1367         dist = xyz.SquareDistance( u2NP->second.second._node );// node in
1368         if ( dist > maxDist )
1369         {
1370           u2NPdist = u2NP;
1371           maxDist = dist;
1372         }
1373       }
1374       // compute distribution of radial nodes
1375       list< double > params; // normalized params
1376       static_cast< StdMeshers_QuadFromMedialAxis_1D2D::Algo1D* >
1377         ( the1dAlgo )->ComputeDistribution( theHelper,
1378                                             SMESH_TNodeXYZ( u2NPdist->second.first._node ),
1379                                             SMESH_TNodeXYZ( u2NPdist->second.second._node ),
1380                                             params );
1381
1382       // add a radial quad side
1383       u2NP = thePointsOnEdges.begin();
1384       const SMDS_MeshNode* nOut = u2NP->second.first._node;
1385       const SMDS_MeshNode*  nIn = u2NP->second.second._node;
1386       nOut = proxyMesh->GetProxyNode( nOut );
1387       nIn  = proxyMesh->GetProxyNode( nIn );
1388       gp_XY uvOut = theHelper.GetNodeUV( face, nOut );
1389       gp_XY uvIn  = theHelper.GetNodeUV( face, nIn );
1390       Handle(Geom_Surface) surface = BRep_Tool::Surface( face );
1391       UVPtStructVec uvsNew; UVPtStruct uvPt;
1392       uvPt.node = nOut;
1393       uvPt.u    = uvOut.X();
1394       uvPt.v    = uvOut.Y();
1395       uvsNew.push_back( uvPt );
1396       for (list<double>::iterator itU = params.begin(); itU != params.end(); ++itU )
1397       {
1398         gp_XY uv  = ( 1 - *itU ) * uvOut + *itU * uvIn;
1399         gp_Pnt p  = surface->Value( uv.X(), uv.Y() );
1400         uvPt.node = theHelper.AddNode( p.X(), p.Y(), p.Z(), /*id=*/0, uv.X(), uv.Y() );
1401         uvPt.u    = uv.X();
1402         uvPt.v    = uv.Y();
1403         uvsNew.push_back( uvPt );
1404       }
1405       uvPt.node = nIn;
1406       uvPt.u    = uvIn.X();
1407       uvPt.v    = uvIn.Y();
1408       uvsNew.push_back( uvPt );
1409
1410       theFace._quad->side[ 0 ] = StdMeshers_FaceSide::New( uvsNew );
1411       theFace._quad->side[ 2 ] = theFace._quad->side[ 0 ];
1412
1413       // rotate the IN side if opposite nodes of IN and OUT sides don't match
1414       if ( theFace._quad->side[ 1 ].GetUVPtStruct().empty() )
1415         return false;
1416       const SMDS_MeshNode * nIn0 = theFace._quad->side[ 1 ].First().node;
1417       if ( nIn0 != nIn )
1418       {
1419         nIn  = proxyMesh->GetProxyNode( nIn );
1420         const UVPtStructVec& uvsIn = theFace._quad->side[ 1 ].GetUVPtStruct(); // _sinuSide[1]
1421         size_t i; // find UVPtStruct holding nIn
1422         for ( i = 0; i < uvsIn.size(); ++i )
1423           if ( nIn == uvsIn[i].node )
1424             break;
1425         if ( i == uvsIn.size() )
1426           return false;
1427
1428         // create a new IN quad side
1429         uvsNew.clear();
1430         uvsNew.reserve( uvsIn.size() );
1431         uvsNew.insert( uvsNew.end(), uvsIn.begin() + i, uvsIn.end() );
1432         uvsNew.insert( uvsNew.end(), uvsIn.begin() + 1, uvsIn.begin() + i + 1);
1433         theFace._quad->side[ 1 ] = StdMeshers_FaceSide::New( uvsNew );
1434
1435         if ( theFace._quad->side[ 1 ].NbPoints() !=
1436              theFace._quad->side[ 3 ].NbPoints())
1437           return false;
1438       }
1439     } // if ( theShortEdges[0].empty() )
1440
1441     return true;
1442
1443   } // setQuadSides()
1444
1445   //================================================================================
1446   /*!
1447    * \brief Divide the sinuous EDGEs by projecting the division point of Medial
1448    *        Axis to the EGDEs
1449    *  \param [in] theHelper - the helper
1450    *  \param [in] theMinSegLen - minimal segment length
1451    *  \param [in] theMA - the Medial Axis
1452    *  \param [in] theMAParams - parameters of division points of \a theMA
1453    *  \param [in] theSinuEdges - the EDGEs to make nodes on
1454    *  \param [in] theSinuSide0Size - the number of EDGEs in the 1st sinuous side
1455    *  \param [in] the1dAlgo - algorithm to use for radial discretization of a ring FACE
1456    *  \return bool - is OK or not
1457    */
1458   //================================================================================
1459
1460   bool computeSinuEdges( SMESH_MesherHelper&        theHelper,
1461                          double                     /*theMinSegLen*/,
1462                          SMESH_MAT2d::MedialAxis&   theMA,
1463                          vector<double>&            theMAParams,
1464                          SinuousFace&               theSinuFace,
1465                          SMESH_Algo*                the1dAlgo)
1466   {
1467     if ( theMA.nbBranches() != 1 )
1468       return false;
1469
1470     // normalize theMAParams
1471     for ( size_t i = 0; i < theMAParams.size(); ++i )
1472       theMAParams[i] /= theMAParams.back();
1473
1474
1475     SMESH_Mesh*     mesh = theHelper.GetMesh();
1476     SMESHDS_Mesh* meshDS = theHelper.GetMeshDS();
1477     double f,l;
1478
1479     // get data of sinuous EDGEs and remove unnecessary nodes
1480     const vector< TopoDS_Edge >& theSinuEdges = theSinuFace._sinuEdges;
1481     vector< Handle(Geom_Curve) >& curves      = theSinuFace._sinuCurves;
1482     vector< int >                edgeIDs   ( theSinuEdges.size() ); // IDs in the main shape
1483     vector< bool >               isComputed( theSinuEdges.size() );
1484     curves.resize( theSinuEdges.size(), 0 );
1485     for ( size_t i = 0; i < theSinuEdges.size(); ++i )
1486     {
1487       curves[i] = BRep_Tool::Curve( theSinuEdges[i], f,l );
1488       if ( !curves[i] )
1489         return false;
1490       SMESH_subMesh* sm = mesh->GetSubMesh( theSinuEdges[i] );
1491       edgeIDs   [i] = sm->GetId();
1492       isComputed[i] = ( !sm->IsEmpty() );
1493     }
1494
1495     const SMESH_MAT2d::Branch& branch = *theMA.getBranch(0);
1496     SMESH_MAT2d::BoundaryPoint bp[2];
1497
1498     vector< std::size_t > edgeIDs1, edgeIDs2; // indices in theSinuEdges
1499     vector< SMESH_MAT2d::BranchPoint > divPoints;
1500     branch.getOppositeGeomEdges( edgeIDs1, edgeIDs2, divPoints );
1501     for ( size_t i = 0; i < edgeIDs1.size(); ++i )
1502       if ( isComputed[ edgeIDs1[i]] &&
1503            isComputed[ edgeIDs2[i]] )
1504       {
1505         int nbNodes1 = meshDS->MeshElements(edgeIDs[ edgeIDs1[i]] )->NbNodes();
1506         int nbNodes2 = meshDS->MeshElements(edgeIDs[ edgeIDs2[i]] )->NbNodes();
1507         if ( nbNodes1 != nbNodes2 )
1508           return false;
1509         if (( i-1 >= 0 ) &&
1510             ( edgeIDs1[i-1] == edgeIDs1[i] ||
1511               edgeIDs2[i-1] == edgeIDs2[i] ))
1512           return false;
1513         if (( i+1 < edgeIDs1.size() ) &&
1514             ( edgeIDs1[i+1] == edgeIDs1[i] ||
1515               edgeIDs2[i+1] == edgeIDs2[i] ))
1516           return false;
1517       }
1518
1519     // map param on MA to parameters of nodes on a pair of theSinuEdges
1520     TMAPar2NPoints pointsOnE;
1521     vector<double> maParams;
1522
1523     // compute params of nodes on EDGEs by projecting division points from MA
1524
1525     for ( size_t iEdgePair = 0; iEdgePair < edgeIDs1.size(); ++iEdgePair )
1526       // loop on pairs of opposite EDGEs
1527     {
1528       // --------------------------------------------------------------------------------
1529       if ( isComputed[ edgeIDs1[ iEdgePair ]] !=                    // one EDGE is meshed
1530            isComputed[ edgeIDs2[ iEdgePair ]])
1531       {
1532         // "projection" from one side to the other
1533
1534         size_t iEdgeComputed = edgeIDs1[iEdgePair], iSideComputed = 0;
1535         if ( !isComputed[ iEdgeComputed ])
1536           ++iSideComputed, iEdgeComputed = edgeIDs2[iEdgePair];
1537
1538         map< double, const SMDS_MeshNode* > nodeParams; // params of existing nodes
1539         if ( !SMESH_Algo::GetSortedNodesOnEdge( meshDS, theSinuEdges[ iEdgeComputed ], /*skipMedium=*/true, nodeParams ))
1540           return false;
1541
1542         SMESH_MAT2d::BoundaryPoint& bndPnt = bp[ 1-iSideComputed ];
1543         SMESH_MAT2d::BranchPoint brp;
1544         NodePoint npN, npB; // NodePoint's initialized by node and BoundaryPoint
1545         NodePoint& np0 = iSideComputed ? npB : npN;
1546         NodePoint& np1 = iSideComputed ? npN : npB;
1547
1548         double maParam1st, maParamLast, maParam;
1549         if ( !theMA.getBoundary().getBranchPoint( iEdgeComputed, nodeParams.begin()->first, brp ))
1550             return false;
1551         branch.getParameter( brp, maParam1st );
1552         if ( !theMA.getBoundary().getBranchPoint( iEdgeComputed, nodeParams.rbegin()->first, brp ))
1553             return false;
1554         branch.getParameter( brp, maParamLast );
1555
1556         map< double, const SMDS_MeshNode* >::iterator u2n = nodeParams.begin(), u2nEnd = nodeParams.end();
1557         TMAPar2NPoints::iterator end = pointsOnE.end(), pos = end;
1558         TMAPar2NPoints::iterator & hint = (maParamLast > maParam1st) ? end : pos;
1559         for ( ++u2n, --u2nEnd; u2n != u2nEnd; ++u2n )
1560         {
1561           // point on EDGE (u2n) --> MA point (brp)
1562           if ( !theMA.getBoundary().getBranchPoint( iEdgeComputed, u2n->first, brp ))
1563             return false;
1564           // MA point --> points on 2 EDGEs (bp)
1565           if ( !branch.getBoundaryPoints( brp, bp[0], bp[1] ) ||
1566                !branch.getParameter( brp, maParam ))
1567             return false;
1568
1569           npN = NodePoint( u2n->second, u2n->first, iEdgeComputed );
1570           npB = NodePoint( bndPnt );
1571           pos = pointsOnE.insert( hint, make_pair( maParam, make_pair( np0, np1 )));
1572         }
1573
1574         // move iEdgePair forward;
1575         // find divPoints most close to max MA param
1576         if ( edgeIDs1.size() > 1 )
1577         {
1578           maParamLast = pointsOnE.rbegin()->first;
1579           int iClosest;
1580           double minDist = 1.;
1581           for ( ; iEdgePair < edgeIDs1.size()-1; ++iEdgePair )
1582           {
1583             branch.getParameter( divPoints[iEdgePair], maParam );
1584             double d = Abs( maParamLast - maParam );
1585             if ( d < minDist )
1586               minDist = d, iClosest = iEdgePair;
1587             else
1588               break;
1589           }
1590           if ( Abs( maParamLast - 1. ) < minDist )
1591             break; // the last pair treated
1592           else
1593             iEdgePair = iClosest;
1594         }
1595       }
1596       // --------------------------------------------------------------------------------
1597       else if ( !isComputed[ edgeIDs1[ iEdgePair ]] &&         // none of EDGEs is meshed
1598                 !isComputed[ edgeIDs2[ iEdgePair ]])
1599       {
1600         // "projection" from MA
1601         maParams.clear();
1602         if ( !getParamsForEdgePair( iEdgePair, divPoints, theMAParams, maParams ))
1603           return false;
1604
1605         for ( size_t i = 1; i < maParams.size()-1; ++i )
1606         {
1607           if ( !branch.getBoundaryPoints( maParams[i], bp[0], bp[1] ))
1608             return false;
1609
1610           pointsOnE.insert( pointsOnE.end(), make_pair( maParams[i], make_pair( NodePoint(bp[0]),
1611                                                                                 NodePoint(bp[1]))));
1612         }
1613       }
1614       // --------------------------------------------------------------------------------
1615       else if ( isComputed[ edgeIDs1[ iEdgePair ]] &&             // equally meshed EDGES
1616                 isComputed[ edgeIDs2[ iEdgePair ]])
1617       {
1618         // add existing nodes
1619
1620         size_t iE0 = edgeIDs1[ iEdgePair ];
1621         size_t iE1 = edgeIDs2[ iEdgePair ];
1622         map< double, const SMDS_MeshNode* > nodeParams[2]; // params of existing nodes
1623         if ( !SMESH_Algo::GetSortedNodesOnEdge( meshDS, theSinuEdges[ iE0 ],
1624                                                 /*skipMedium=*/false, nodeParams[0] ) ||
1625              !SMESH_Algo::GetSortedNodesOnEdge( meshDS, theSinuEdges[ iE1 ],
1626                                                 /*skipMedium=*/false, nodeParams[1] ) ||
1627              nodeParams[0].size() != nodeParams[1].size() )
1628           return false;
1629
1630         if ( nodeParams[0].size() <= 2 )
1631           continue; // nodes on VERTEXes only
1632
1633         bool reverse = ( theSinuEdges[0].Orientation() == theSinuEdges[1].Orientation() );
1634         double maParam;
1635         SMESH_MAT2d::BranchPoint brp;
1636         std::pair< NodePoint, NodePoint > npPair;
1637
1638         map< double, const SMDS_MeshNode* >::iterator
1639           u2n0F = ++nodeParams[0].begin(),
1640           u2n1F = ++nodeParams[1].begin();
1641         map< double, const SMDS_MeshNode* >::reverse_iterator
1642           u2n1R = ++nodeParams[1].rbegin();
1643         for ( ; u2n0F != nodeParams[0].end(); ++u2n0F )
1644         {
1645           if ( !theMA.getBoundary().getBranchPoint( iE0, u2n0F->first, brp ) ||
1646                !branch.getParameter( brp, maParam ))
1647             return false;
1648
1649           npPair.first = NodePoint( u2n0F->second, u2n0F->first, iE0 );
1650           if ( reverse )
1651           {
1652             npPair.second = NodePoint( u2n1R->second, u2n1R->first, iE1 );
1653             ++u2n1R;
1654           }
1655           else
1656           {
1657             npPair.second = NodePoint( u2n1F->second, u2n1F->first, iE1 );
1658             ++u2n1F;
1659           }
1660           pointsOnE.insert( make_pair( maParam, npPair ));
1661         }
1662       }
1663     }  // loop on pairs of opposite EDGEs
1664
1665     if ( !projectVertices( theHelper, theMA, divPoints, edgeIDs1, edgeIDs2,
1666                            isComputed, pointsOnE, theSinuFace ))
1667       return false;
1668
1669     separateNodes( theHelper, theMA, pointsOnE, theSinuFace );
1670
1671     // create nodes
1672     TMAPar2NPoints::iterator u2np = pointsOnE.begin();
1673     for ( ; u2np != pointsOnE.end(); ++u2np )
1674     {
1675       NodePoint* np[2] = { & u2np->second.first, & u2np->second.second };
1676       for ( int iSide = 0; iSide < 2; ++iSide )
1677       {
1678         if ( np[ iSide ]->_node ) continue;
1679         size_t       iEdge = np[ iSide ]->_edgeInd;
1680         double           u = np[ iSide ]->_u;
1681         gp_Pnt           p = curves[ iEdge ]->Value( u );
1682         np[ iSide ]->_node = meshDS->AddNode( p.X(), p.Y(), p.Z() );
1683         meshDS->SetNodeOnEdge( np[ iSide ]->_node, edgeIDs[ iEdge ], u );
1684       }
1685     }
1686
1687     // create mesh segments on EDGEs
1688     theHelper.SetElementsOnShape( false );
1689     TopoDS_Face face = TopoDS::Face( theHelper.GetSubShape() );
1690     for ( size_t i = 0; i < theSinuEdges.size(); ++i )
1691     {
1692       SMESH_subMesh* sm = mesh->GetSubMesh( theSinuEdges[i] );
1693       if ( sm->GetSubMeshDS() && sm->GetSubMeshDS()->NbElements() > 0 )
1694         continue;
1695
1696       StdMeshers_FaceSide side( face, theSinuEdges[i], mesh,
1697                                 /*isFwd=*/true, /*skipMediumNodes=*/true );
1698       vector<const SMDS_MeshNode*> nodes = side.GetOrderedNodes();
1699       for ( size_t in = 1; in < nodes.size(); ++in )
1700       {
1701         const SMDS_MeshElement* seg = theHelper.AddEdge( nodes[in-1], nodes[in], 0, false );
1702         meshDS->SetMeshElementOnShape( seg, edgeIDs[ i ] );
1703       }
1704     }
1705
1706     // update sub-meshes on VERTEXes
1707     for ( size_t i = 0; i < theSinuEdges.size(); ++i )
1708     {
1709       mesh->GetSubMesh( theHelper.IthVertex( 0, theSinuEdges[i] ))
1710         ->ComputeStateEngine( SMESH_subMesh::CHECK_COMPUTE_STATE );
1711       mesh->GetSubMesh( theHelper.IthVertex( 1, theSinuEdges[i] ))
1712         ->ComputeStateEngine( SMESH_subMesh::CHECK_COMPUTE_STATE );
1713     }
1714
1715     // Setup sides of a quadrangle
1716     if ( !setQuadSides( theHelper, pointsOnE, theSinuFace, the1dAlgo ))
1717       return false;
1718
1719     return true;
1720   }
1721
1722   //================================================================================
1723   /*!
1724    * \brief Mesh short EDGEs
1725    */
1726   //================================================================================
1727
1728   bool computeShortEdges( SMESH_MesherHelper&        theHelper,
1729                           const vector<TopoDS_Edge>& theShortEdges,
1730                           SMESH_Algo*                the1dAlgo,
1731                           const bool                 theHasRadialHyp,
1732                           const bool                 theIs2nd)
1733   {
1734     SMESH_Hypothesis::Hypothesis_Status aStatus;
1735     for ( size_t i = 0; i < theShortEdges.size(); ++i )
1736     {
1737       if ( !theHasRadialHyp )
1738         // use global hyps
1739         theHelper.GetGen()->Compute( *theHelper.GetMesh(), theShortEdges[i], true, true );
1740
1741       SMESH_subMesh* sm = theHelper.GetMesh()->GetSubMesh(theShortEdges[i] );
1742       if ( sm->IsEmpty() )
1743       {
1744         // use 2D hyp or minSegLen
1745         try {
1746           // compute VERTEXes
1747           SMESH_subMeshIteratorPtr smIt = sm->getDependsOnIterator(/*includeSelf=*/false);
1748           while ( smIt->more() )
1749             smIt->next()->ComputeStateEngine( SMESH_subMesh::COMPUTE );
1750
1751           // compute EDGE
1752           the1dAlgo->CheckHypothesis( *theHelper.GetMesh(), theShortEdges[i], aStatus );
1753           if ( !the1dAlgo->Compute( *theHelper.GetMesh(), theShortEdges[i] ))
1754             return false;
1755         }
1756         catch (...) {
1757           return false;
1758         }
1759         sm->ComputeStateEngine( SMESH_subMesh::CHECK_COMPUTE_STATE );
1760         if ( sm->IsEmpty() )
1761           return false;
1762       }
1763     }
1764     return true;
1765   }
1766
1767   inline double area( const UVPtStruct& p1, const UVPtStruct& p2, const UVPtStruct& p3 )
1768   {
1769     gp_XY v1 = p2.UV() - p1.UV();
1770     gp_XY v2 = p3.UV() - p1.UV();
1771     return v2 ^ v1;
1772   }
1773
1774   bool ellipticSmooth( FaceQuadStruct::Ptr quad, int nbLoops )
1775   {
1776     //nbLoops = 10;
1777     if ( quad->uv_grid.empty() )
1778       return true;
1779
1780     int nbhoriz  = quad->iSize;
1781     int nbvertic = quad->jSize;
1782
1783     const double dksi = 0.5, deta = 0.5;
1784     const double  dksi2 = dksi*dksi, deta2 = deta*deta;
1785     double err = 0., g11, g22, g12;
1786     int nbErr = 0;
1787
1788     FaceQuadStruct& q = *quad;
1789     UVPtStruct pNew;
1790
1791     double refArea = area( q.UVPt(0,0), q.UVPt(1,0), q.UVPt(1,1) );
1792
1793     for ( int iLoop = 0; iLoop < nbLoops; ++iLoop )
1794     {
1795       err = 0;
1796       for ( int i = 1; i < nbhoriz - 1; i++ )
1797         for ( int j = 1; j < nbvertic - 1; j++ )
1798         {
1799           g11 = ( (q.U(i,j+1) - q.U(i,j-1))*(q.U(i,j+1) - q.U(i,j-1))/dksi2 +
1800                   (q.V(i,j+1) - q.V(i,j-1))*(q.V(i,j+1) - q.V(i,j-1))/deta2 )/4;
1801
1802           g22 = ( (q.U(i+1,j) - q.U(i-1,j))*(q.U(i+1,j) - q.U(i-1,j))/dksi2 +
1803                   (q.V(i+1,j) - q.V(i-1,j))*(q.V(i+1,j) - q.V(i-1,j))/deta2 )/4;
1804
1805           g12 = ( (q.U(i+1,j) - q.U(i-1,j))*(q.U(i,j+1) - q.U(i,j-1))/dksi2 +
1806                   (q.V(i+1,j) - q.V(i-1,j))*(q.V(i,j+1) - q.V(i,j-1))/deta2 )/(4*dksi*deta);
1807
1808           pNew.u = dksi2/(2*(g11+g22)) * (g11*(q.U(i+1,j) + q.U(i-1,j))/dksi2 +
1809                                           g22*(q.U(i,j+1) + q.U(i,j-1))/dksi2
1810                                           - 0.5*g12*q.U(i+1,j+1) + 0.5*g12*q.U(i-1,j+1) +
1811                                           - 0.5*g12*q.U(i-1,j-1) + 0.5*g12*q.U(i+1,j-1));
1812
1813           pNew.v = deta2/(2*(g11+g22)) * (g11*(q.V(i+1,j) + q.V(i-1,j))/deta2 +
1814                                           g22*(q.V(i,j+1) + q.V(i,j-1))/deta2
1815                                           - 0.5*g12*q.V(i+1,j+1) + 0.5*g12*q.V(i-1,j+1) +
1816                                           - 0.5*g12*q.V(i-1,j-1) + 0.5*g12*q.V(i+1,j-1));
1817
1818           // if (( refArea * area( q.UVPt(i-1,j-1), q.UVPt(i,j-1), pNew ) > 0 ) &&
1819           //     ( refArea * area( q.UVPt(i+1,j-1), q.UVPt(i+1,j), pNew ) > 0 ) &&
1820           //     ( refArea * area( q.UVPt(i+1,j+1), q.UVPt(i,j+1), pNew ) > 0 ) &&
1821           //     ( refArea * area( q.UVPt(i-1,j), q.UVPt(i-1,j-1), pNew ) > 0 ))
1822           {
1823             err += sqrt(( q.U(i,j) - pNew.u ) * ( q.U(i,j) - pNew.u ) +
1824                         ( q.V(i,j) - pNew.v ) * ( q.V(i,j) - pNew.v ));
1825             q.U(i,j) = pNew.u;
1826             q.V(i,j) = pNew.v;
1827           }
1828           // else if ( ++nbErr < 10 )
1829           // {
1830           //   cout << i << ", " << j << endl;
1831           //   cout << "x = ["
1832           //        << "[ " << q.U(i-1,j-1) << ", " <<q.U(i,j-1) << ", " << q.U(i+1,j-1) << " ],"
1833           //        << "[ " << q.U(i-1,j-0) << ", " <<q.U(i,j-0) << ", " << q.U(i+1,j-0) << " ],"
1834           //        << "[ " << q.U(i-1,j+1) << ", " <<q.U(i,j+1) << ", " << q.U(i+1,j+1) << " ]]" << endl;
1835           //   cout << "y = ["
1836           //        << "[ " << q.V(i-1,j-1) << ", " <<q.V(i,j-1) << ", " << q.V(i+1,j-1) << " ],"
1837           //        << "[ " << q.V(i-1,j-0) << ", " <<q.V(i,j-0) << ", " << q.V(i+1,j-0) << " ],"
1838           //        << "[ " << q.V(i-1,j+1) << ", " <<q.V(i,j+1) << ", " << q.V(i+1,j+1) << " ]]" << endl<<endl;
1839           // }
1840         }
1841
1842       if ( err / ( nbhoriz - 2 ) / ( nbvertic - 2 ) < 1e-6 )
1843         break;
1844     }
1845     //cout << " ERR " << err / ( nbhoriz - 2 ) / ( nbvertic - 2 ) << endl;
1846
1847     return true;
1848   }
1849
1850   //================================================================================
1851   /*!
1852    * \brief Remove temporary node
1853    */
1854   //================================================================================
1855
1856   void mergeNodes( SMESH_MesherHelper& theHelper,
1857                    SinuousFace&        theSinuFace )
1858   {
1859     SMESH_MeshEditor editor( theHelper.GetMesh() );
1860     SMESH_MeshEditor::TListOfListOfNodes nodesGroups;
1861
1862     TMergeMap::iterator n2nn = theSinuFace._nodesToMerge.begin();
1863     for ( ; n2nn != theSinuFace._nodesToMerge.end(); ++n2nn )
1864     {
1865       if ( !n2nn->first ) continue;
1866       nodesGroups.push_back( list< const SMDS_MeshNode* >() );
1867       list< const SMDS_MeshNode* > & group = nodesGroups.back();
1868
1869       group.push_back( n2nn->first );
1870       group.splice( group.end(), n2nn->second );
1871     }
1872     editor.MergeNodes( nodesGroups );
1873   }
1874
1875 } // namespace
1876
1877 //================================================================================
1878 /*!
1879  * \brief Sets event listener which removes mesh from EDGEs when 2D hyps change
1880  */
1881 //================================================================================
1882
1883 void StdMeshers_QuadFromMedialAxis_1D2D::SetEventListener(SMESH_subMesh* faceSubMesh)
1884 {
1885   faceSubMesh->SetEventListener( new EdgeCleaner, 0, faceSubMesh );
1886 }
1887
1888 //================================================================================
1889 /*!
1890  * \brief Create quadrangle elements
1891  *  \param [in] theHelper - the helper
1892  *  \param [in] theFace - the face to mesh
1893  *  \param [in] theSinuEdges - the sinuous EDGEs
1894  *  \param [in] theShortEdges - the short EDGEs
1895  *  \return bool - is OK or not
1896  */
1897 //================================================================================
1898
1899 bool StdMeshers_QuadFromMedialAxis_1D2D::computeQuads( SMESH_MesherHelper& theHelper,
1900                                                        FaceQuadStruct::Ptr theQuad)
1901 {
1902   StdMeshers_Quadrangle_2D::myHelper     = &theHelper;
1903   StdMeshers_Quadrangle_2D::myNeedSmooth = false;
1904   StdMeshers_Quadrangle_2D::myCheckOri   = false;
1905   StdMeshers_Quadrangle_2D::myQuadList.clear();
1906
1907   int nbNodesShort0 = theQuad->side[0].NbPoints();
1908   int nbNodesShort1 = theQuad->side[2].NbPoints();
1909
1910   // compute UV of internal points
1911   myQuadList.push_back( theQuad );
1912   if ( !StdMeshers_Quadrangle_2D::setNormalizedGrid( theQuad ))
1913     return false;
1914
1915   // elliptic smooth of internal points to get boundary cell normal to the boundary
1916   bool isRing = theQuad->side[0].grid->Edge(0).IsNull();
1917   if ( !isRing )
1918     ellipticSmooth( theQuad, 1 );
1919
1920   // create quadrangles
1921   bool ok;
1922   theHelper.SetElementsOnShape( true );
1923   if ( nbNodesShort0 == nbNodesShort1 )
1924     ok = StdMeshers_Quadrangle_2D::computeQuadDominant( *theHelper.GetMesh(),
1925                                                         theQuad->face, theQuad );
1926   else
1927     ok = StdMeshers_Quadrangle_2D::computeTriangles( *theHelper.GetMesh(),
1928                                                      theQuad->face, theQuad );
1929
1930   StdMeshers_Quadrangle_2D::myHelper = 0;
1931
1932   return ok;
1933 }
1934
1935 //================================================================================
1936 /*!
1937  * \brief Generate quadrangle mesh
1938  */
1939 //================================================================================
1940
1941 bool StdMeshers_QuadFromMedialAxis_1D2D::Compute(SMESH_Mesh&         theMesh,
1942                                                  const TopoDS_Shape& theShape)
1943 {
1944   SMESH_MesherHelper helper( theMesh );
1945   helper.SetSubShape( theShape );
1946
1947   TopoDS_Face F = TopoDS::Face( theShape );
1948   if ( F.Orientation() >= TopAbs_INTERNAL ) F.Orientation( TopAbs_FORWARD );
1949
1950   SinuousFace sinuFace( F );
1951
1952   _progress = 0.01;
1953
1954   if ( getSinuousEdges( helper, sinuFace ))
1955   {
1956     _progress = 0.4;
1957
1958     double minSegLen = getMinSegLen( helper, sinuFace._sinuEdges );
1959     SMESH_MAT2d::MedialAxis ma( F, sinuFace._sinuEdges, minSegLen, /*ignoreCorners=*/true );
1960
1961     if ( !_regular1D )
1962       _regular1D = new Algo1D( _studyId, _gen );
1963     _regular1D->SetSegmentLength( minSegLen );
1964
1965     vector<double> maParams;
1966     if ( ! divideMA( helper, ma, sinuFace, _regular1D, minSegLen, maParams ))
1967       return error(COMPERR_BAD_SHAPE);
1968
1969     _progress = 0.8;
1970     if ( _hyp2D )
1971       _regular1D->SetRadialDistribution( _hyp2D );
1972
1973     if ( !computeShortEdges( helper, sinuFace._shortSide[0], _regular1D, _hyp2D, 0 ) ||
1974          !computeShortEdges( helper, sinuFace._shortSide[1], _regular1D, _hyp2D, 1 ))
1975       return error("Failed to mesh short edges");
1976
1977     _progress = 0.85;
1978
1979     if ( !computeSinuEdges( helper, minSegLen, ma, maParams, sinuFace, _regular1D ))
1980       return error("Failed to mesh sinuous edges");
1981
1982     _progress = 0.9;
1983
1984     bool ok = computeQuads( helper, sinuFace._quad );
1985
1986     if ( ok )
1987       mergeNodes( helper, sinuFace );
1988
1989     _progress = 1.;
1990
1991     return ok;
1992   }
1993
1994   return error(COMPERR_BAD_SHAPE, "Not implemented so far");
1995 }
1996
1997 //================================================================================
1998 /*!
1999  * \brief Predict nb of elements
2000  */
2001 //================================================================================
2002
2003 bool StdMeshers_QuadFromMedialAxis_1D2D::Evaluate(SMESH_Mesh &         theMesh,
2004                                                   const TopoDS_Shape & theShape,
2005                                                   MapShapeNbElems&     theResMap)
2006 {
2007   return StdMeshers_Quadrangle_2D::Evaluate(theMesh,theShape,theResMap);
2008 }
2009
2010 //================================================================================
2011 /*!
2012  * \brief Return true if the algorithm can mesh this shape
2013  *  \param [in] aShape - shape to check
2014  *  \param [in] toCheckAll - if true, this check returns OK if all shapes are OK,
2015  *              else, returns OK if at least one shape is OK
2016  */
2017 //================================================================================
2018
2019 bool StdMeshers_QuadFromMedialAxis_1D2D::IsApplicable( const TopoDS_Shape & aShape,
2020                                                        bool                 toCheckAll )
2021 {
2022   TmpMesh tmpMesh;
2023   SMESH_MesherHelper helper( tmpMesh );
2024
2025   int nbFoundFaces = 0;
2026   for (TopExp_Explorer exp( aShape, TopAbs_FACE ); exp.More(); exp.Next(), ++nbFoundFaces )
2027   {
2028     const TopoDS_Face& face = TopoDS::Face( exp.Current() );
2029     SinuousFace sinuFace( face );
2030     bool isApplicable = getSinuousEdges( helper, sinuFace );
2031
2032     if ( toCheckAll  && !isApplicable ) return false;
2033     if ( !toCheckAll &&  isApplicable ) return true;
2034   }
2035   return ( toCheckAll && nbFoundFaces != 0 );
2036 }
2037