src/SMDS/SMDS_ElementFactory.hxx

   1 // Copyright (C) 2007-2020  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   : SMDS_ElementFactory.hxx
  23 //  Module : SMESH
  24 //
  25 #ifndef _SMDS_ElementFactory_HeaderFile
  26 #define _SMDS_ElementFactory_HeaderFile
  27
  28 #include "SMDS_MeshCell.hxx"
  29 #include "SMDS_Position.hxx"
  30
  31 #include <Utils_SALOME_Exception.hxx>
  32
  33 #include <boost/container/flat_set.hpp>
  34 #include <boost/dynamic_bitset.hpp>
  35 #include <boost/make_shared.hpp>
  36 #include <boost/ptr_container/ptr_vector.hpp>
  37 #include <boost/shared_ptr.hpp>
  38
  39 #include <set>
  40
  41 #include <vtkType.h>
  42
  43 class SMDS_ElementChunk;
  44 class SMDS_Mesh;
  45 class SMDS_MeshCell;
  46 class SMDS_MeshNode;
  47
  48 struct _ChunkCompare {
  49   bool operator () (const SMDS_ElementChunk* c1, const SMDS_ElementChunk* c2) const;
  50 };
  51 typedef boost::ptr_vector<SMDS_ElementChunk>       TChunkVector;
  52 typedef std::set<SMDS_ElementChunk*,_ChunkCompare> TChunkPtrSet;
  53
  54 //------------------------------------------------------------------------------------
  55 /*!
  56  * \brief Allocate SMDS_MeshElement's (SMDS_MeshCell's or SMDS_MeshNode's )
  57  *        and bind some attributes to elements:
  58  *        element ID, element VTK ID, sub-mesh ID, position on shape.
  59  *
  60  * Elements are allocated by chunks, so there are used and non-used elements
  61  */
  62 class SMDS_ElementFactory
  63 {
  64 protected:
  65   bool                     myIsNodal;          // what to allocate: nodes or cells
  66   SMDS_Mesh*               myMesh;
  67   TChunkVector             myChunks;           // array of chunks of elements
  68   TChunkPtrSet             myChunksWithUnused; // sorted chunks having unused elements
  69   std::vector< vtkIdType > myVtkIDs;           // myVtkIDs[ smdsID-1 ] == vtkID
  70   std::vector< int >       mySmdsIDs;          // mySmdsIDs[ vtkID ] == smdsID - 1
  71   int                      myNbUsedElements;   // counter of elements
  72
  73   friend class SMDS_ElementChunk;
  74
  75 public:
  76
  77   SMDS_ElementFactory( SMDS_Mesh* mesh, const bool isNodal=false );
  78   virtual ~SMDS_ElementFactory();
  79
  80   //! Return minimal ID of a non-used element
  81   int GetFreeID();
  82
  83   //! Return maximal ID of an used element
  84   int GetMaxID();
  85
  86   //! Return minimal ID of an used element
  87   int GetMinID();
  88
  89   //! Return an element by ID. NULL if the element with the given ID is already used
  90   SMDS_MeshElement* NewElement( const int id );
  91
  92   //! Return a SMDS_MeshCell by ID. NULL if the cell with the given ID is already used
  93   SMDS_MeshCell* NewCell( const int id ) { return static_cast<SMDS_MeshCell*>( NewElement( id )); }
  94
  95   //! Return an used element by ID. NULL if the element with the given ID is not yet used
  96   const SMDS_MeshElement* FindElement( const int id ) const;
  97
  98   //! Return a number of used elements
  99   int NbUsedElements() const { return myNbUsedElements; }
 100
 101   //! Return an iterator on all element filtered using a given filter.
 102   //  nbElemsToReturn is used to optimize by stopping the iteration as soon as
 103   //  all elements satisfying filtering condition encountered.
 104   template< class ElemIterator >
 105   boost::shared_ptr< ElemIterator > GetIterator( SMDS_MeshElement::Filter* filter,
 106                                                  size_t nbElemsToReturn = -1 );
 107
 108   //! Return an iterator on all element assigned to a given shape.
 109   //  nbElemsToReturn is used to optimize by stopping the iteration as soon as
 110   //  all elements assigned to the shape encountered.
 111   //  sm1stElem is used to quickly find the first chunk holding elements of the shape;
 112   //  it must have smallest ID between elements on the shape
 113   template< class ElemIterator >
 114   boost::shared_ptr< ElemIterator > GetShapeIterator( int                     shapeID,
 115                                                       size_t                  nbElemsToReturn,
 116                                                       const SMDS_MeshElement* sm1stElem );
 117
 118   //! Mark the element as non-used
 119   void Free( const SMDS_MeshElement* );
 120
 121   //! Return an SMDS ID by a Vtk one
 122   int FromVtkToSmds( vtkIdType vtkID );
 123
 124   //! De-allocate all elements
 125   virtual void Clear();
 126
 127   //! Remove unused elements located not at the end of the last chunk.
 128   //  Minimize allocated memory
 129   virtual void Compact(std::vector<int>& idCellsOldToNew);
 130
 131   //! Return true if Compact() will change IDs of elements
 132   virtual bool CompactChangePointers();
 133
 134   //! Return a number of elements in a chunk
 135   static int ChunkSize();
 136 };
 137
 138 //------------------------------------------------------------------------------------
 139 /*!
 140  * \brief Allocate SMDS_MeshNode's
 141  */
 142 class SMDS_NodeFactory : public SMDS_ElementFactory
 143 {
 144   std::vector<char> myShapeDim; // dimension of shapes
 145
 146 public:
 147
 148   SMDS_NodeFactory( SMDS_Mesh* mesh );
 149   ~SMDS_NodeFactory();
 150
 151   //! Return a SMDS_MeshNode by ID. NULL if the node with the given ID is already used
 152   SMDS_MeshNode* NewNode( int id ) { return (SMDS_MeshNode*) NewElement(id); }
 153
 154   //! Return an used node by ID. NULL if the node with the given ID is not yet used
 155   const SMDS_MeshNode* FindNode( int id ) { return (const SMDS_MeshNode*) FindElement(id); }
 156
 157   //! Set a total number of sub-shapes in the main shape
 158   void SetNbShapes( size_t nbShapes );
 159
 160   //! Return a dimension of a shape
 161   int  GetShapeDim( int shapeID ) const;
 162
 163   //! Set a dimension of a shape
 164   void SetShapeDim( int shapeID, int dim );
 165
 166   //! De-allocate all nodes
 167   virtual void Clear();
 168
 169   //! Remove unused nodes located not at the end of the last chunk.
 170   //  Minimize allocated memory
 171   virtual void Compact(std::vector<int>& idNodesOldToNew);
 172
 173   //! Return true if Compact() will change IDs of node
 174   virtual bool CompactChangePointers();
 175 };
 176
 177 //------------------------------------------------------------------------------------
 178 /*!
 179  * \brief Range of elements in a chunk having the same attribute value
 180  */
 181 template< typename ATTR>
 182 struct _Range
 183 {
 184   typedef ATTR attr_t;
 185
 186   attr_t myValue; // common attribute value
 187   int    my1st;   // index in the chunk of the 1st element
 188   _Range( int i0 = 0, attr_t v = 0 ): myValue( v ), my1st( i0 ) {}
 189
 190   bool operator < (const _Range& other) const { return my1st < other.my1st; }
 191 };
 192
 193 typedef std::vector< std::pair< int, int > > TIndexRanges;
 194
 195 //------------------------------------------------------------------------------------
 196 /*!
 197  * \brief Sorted set of ranges
 198  */
 199 template< class RANGE >
 200 struct _RangeSet
 201 {
 202   typedef typename RANGE::attr_t              attr_t;
 203   typedef boost::container::flat_set< RANGE > set_t;
 204   typedef typename set_t::const_iterator      set_iterator;
 205
 206   set_t mySet;
 207
 208   _RangeSet() { mySet.insert( RANGE( 0, 0 )); }
 209
 210   /*!
 211    * \brief Return a number of ranges
 212    */
 213   size_t Size() const { return mySet.size(); }
 214
 215   /*!
 216    * \brief Return a mutable _Range::my1st of a range pointed by an iterator
 217    */
 218   int&   First( set_iterator rangePtr ) { return const_cast< int& >( rangePtr->my1st ); }
 219
 220   /*!
 221    * \brief Return a number of elements in a range pointed by an iterator
 222    */
 223   size_t Size( set_iterator rangePtr ) const
 224   {
 225     int next1st =
 226       ( rangePtr + 1 == mySet.end() ) ? SMDS_ElementFactory::ChunkSize() : ( rangePtr + 1 )->my1st;
 227     return next1st - rangePtr->my1st;
 228   }
 229
 230   /*!
 231    * \brief Return ranges of indices (from,to) of elements having a given value
 232    */
 233   bool GetIndices( const attr_t theValue, TIndexRanges & theIndices,
 234                    const attr_t* /*theMinValue*/ = 0, const attr_t* /*theMaxValue*/ = 0) const
 235   {
 236     bool isFound = false;
 237
 238     // if ( sizeof( attr_t ) == sizeof( int ) && theMinValue )
 239     //   if ( theValue < *theMinValue || theValue > *theMaxValue )
 240     //     return isFound;
 241
 242     for ( set_iterator it = mySet.begin(); it < mySet.end(); ++it )
 243     {
 244       if ( it->myValue == theValue )
 245       {
 246         theIndices.push_back( std::make_pair( it->my1st, it->my1st + Size( it )));
 247         isFound = true;
 248         ++it; // the next range value differs from theValue
 249       }
 250     }
 251     return isFound;
 252   }
 253
 254   /*!
 255    * \brief Return value of an element attribute
 256    *  \param [in] theIndex - element index
 257    *  \return attr_t - attribute value
 258    */
 259   attr_t GetValue( int theIndex ) const
 260   {
 261     set_iterator r = mySet.upper_bound( theIndex ) - 1;
 262     return r->myValue;
 263   }
 264
 265   /*!
 266    * \brief Change value of an element attribute
 267    *  \param [in] theIndex - element index
 268    *  \param [in] theValue - attribute value
 269    *  \return attr_t - previous value
 270    */
 271   attr_t SetValue( int theIndex, attr_t theValue )
 272   {
 273     set_iterator rNext = mySet.end(); // case of adding elements
 274     set_iterator     r = rNext - 1;
 275     if ( r->my1st > theIndex )
 276     {
 277       rNext = mySet.upper_bound( theIndex );
 278       r     = rNext - 1;
 279     }
 280     int          rSize = Size( r ); // range size
 281     attr_t      rValue = r->myValue;
 282     if ( rValue == theValue )
 283       return rValue; // it happens while compacting
 284
 285     if ( r->my1st == theIndex ) // theIndex is the first in the range
 286     {
 287       bool joinPrev = // can join theIndex to the previous range
 288         ( r->my1st > 0 && ( r-1 )->myValue == theValue );
 289
 290       if ( rSize == 1 )
 291       {
 292         bool joinNext = // can join to the next range
 293           ( rNext != mySet.end() && rNext->myValue == theValue );
 294
 295         if ( joinPrev )
 296         {
 297           if ( joinNext ) // && joinPrev
 298           {
 299             mySet.erase( r, r + 2 );
 300           }
 301           else // joinPrev && !joinNext
 302           {
 303             mySet.erase( r );
 304           }
 305         }
 306         else
 307         {
 308           if ( joinNext ) // && !joinPrev
 309           {
 310             r = mySet.erase( r ); // then r points to the next range
 311             First( r )--;
 312           }
 313           else // !joinPrev && !joinNext
 314           {
 315             const_cast< attr_t & >( r->myValue ) = theValue;
 316           }
 317         }
 318       }
 319       else // if rSize > 1
 320       {
 321         if ( joinPrev )
 322         {
 323           First( r )++;
 324         }
 325         else
 326         {
 327           r = mySet.insert( r, RANGE( theIndex + 1, rValue )) - 1;
 328           const_cast< attr_t & >( r->myValue ) = theValue;
 329         }
 330       }
 331     }
 332     else if ( r->my1st + rSize - 1 == theIndex ) // theIndex is last in the range
 333     {
 334       if ( rNext != mySet.end() && rNext->myValue == theValue ) // join to the next
 335       {
 336         First( rNext )--;
 337       }
 338       else
 339       {
 340         mySet.insert( r, RANGE( theIndex, theValue ));
 341       }
 342     }
 343     else // theIndex in the middle of the range
 344     {
 345       r = mySet.insert( r, RANGE( theIndex,     theValue ));
 346       r = mySet.insert( r, RANGE( theIndex + 1, rValue ));
 347     }
 348     return rValue;
 349   }
 350 }; // struct _RangeSet
 351
 352
 353 typedef _Range< int >  _ShapeIDRange; // sub-mesh ID range
 354 typedef _Range< bool > _UsedRange;    // range of used elements
 355
 356 typedef _RangeSet< _ShapeIDRange > TSubIDRangeSet;
 357 typedef _RangeSet< _UsedRange >    TUsedRangeSet;
 358 typedef boost::dynamic_bitset<>    TBitSet;
 359 //typedef float                       TParam;
 360 typedef double                     TParam;
 361 //typedef std::unordered_set<int>    TSubIDSet;
 362
 363 //------------------------------------------------------------------------------------
 364 /*!
 365  * \brief Allocate SMDS_MeshElement's (SMDS_MeshCell's or SMDS_MeshNode's )
 366  *        and bind some attributes to elements:
 367  *        element ID, sub-shape ID, isMarked flag, parameters on shape
 368  */
 369 class SMDS_ElementChunk
 370 {
 371   SMDS_ElementFactory* myFactory;     // holder of this chunk
 372   SMDS_MeshElement*    myElements;    // array of elements
 373   int                  my1stID;       // ID of myElements[0]
 374   TBitSet              myMarkedSet;   // mark some elements
 375   TUsedRangeSet        myUsedRanges;  // ranges of used/unused elements
 376   TSubIDRangeSet       mySubIDRanges; // ranges of elements on the same sub-shape
 377   //TSubIDSet*           mySubIDSet;    // set of sub-shape IDs
 378   // int                  myMinSubID;    // min sub-shape ID
 379   // int                  myMaxSubID;    // max sub-shape ID
 380   std::vector<TParam>  myPositions;   // UV parameters on shape: 2*param_t per an element
 381
 382 public:
 383
 384   SMDS_ElementChunk( SMDS_ElementFactory* factory = 0, int id0 = 0 );
 385   ~SMDS_ElementChunk();
 386
 387   //! Return an element by an index [0,ChunkSize()]
 388   SMDS_MeshElement* Element(int index) { return & myElements[index]; }
 389
 390   //! Return an element by an index [0,ChunkSize()]
 391   const SMDS_MeshElement* Element(int index) const { return & myElements[index]; }
 392
 393   //! Return ID of the first non-used element
 394   int  GetUnusedID() const;
 395
 396   //! Mark an element as used
 397   void UseElement( const int index );
 398
 399   //! Mark an element as non-used
 400   void Free( const SMDS_MeshElement* e );
 401
 402   //! Check if a given range holds used or non-used elements
 403   static bool IsUsed( const _UsedRange& r ) { return r.myValue; }
 404
 405   //! Return index of an element in the chunk
 406   int Index( const SMDS_MeshElement* e ) const { return e - myElements; }
 407
 408   //! Return ID of the 1st element in the chunk
 409   int Get1stID() const { return my1stID; }
 410
 411   //! Return pointer to on-shape-parameters of a node
 412   TParam* GetPositionPtr( const SMDS_MeshElement* node, bool allocate=false );
 413
 414   //! Return ranges of used/non-used elements
 415   const TUsedRangeSet&  GetUsedRanges() const { return myUsedRanges; }
 416   const TUsedRangeSet&  GetUsedRangesMinMax( bool& min, bool& max ) const
 417   { min = false; max = true; return myUsedRanges; }
 418
 419   //! Return ranges of elements assigned to sub-shapes and min/max of sub-shape IDs
 420   const TSubIDRangeSet& GetSubIDRangesMinMax( int& /*min*/, int& /*max*/ ) const
 421   { /*min = myMinSubID; max = myMaxSubID;*/ return mySubIDRanges; }
 422
 423   //! Minimize allocated memory
 424   void Compact();
 425
 426   //! Print some data
 427   void Dump() const; // debug
 428
 429
 430   // Methods called by SMDS_MeshElement
 431
 432   int  GetID( const SMDS_MeshElement* e ) const;
 433
 434   int  GetVtkID( const SMDS_MeshElement* e ) const;
 435   void SetVTKID( const SMDS_MeshElement* e, const vtkIdType id );
 436
 437   int  GetShapeID( const SMDS_MeshElement* e ) const;
 438   void SetShapeID( const SMDS_MeshElement* e, int shapeID ) const;
 439
 440   bool IsMarked   ( const SMDS_MeshElement* e ) const;
 441   void SetIsMarked( const SMDS_MeshElement* e, bool is );
 442
 443   SMDS_PositionPtr GetPosition( const SMDS_MeshNode* n ) const;
 444   void SetPosition( const SMDS_MeshNode* n, const SMDS_PositionPtr& pos, int shapeID );
 445
 446   SMDS_Mesh* GetMesh() { return myFactory->myMesh; }
 447 };
 448
 449 //------------------------------------------------------------------------------------
 450 /*!
 451  * \brief Iterator on elements in chunks
 452  */
 453 template< class ELEM_ITERATOR, class RANGE_SET >
 454 struct _ChunkIterator : public ELEM_ITERATOR
 455 {
 456   typedef typename ELEM_ITERATOR::value_type    element_type;
 457   typedef SMDS_MeshElement::Filter*             filter_ptr;
 458   typedef typename RANGE_SET::attr_t            attr_type;
 459   typedef const RANGE_SET& (SMDS_ElementChunk::*get_rangeset_fun)(attr_type&, attr_type&) const;
 460
 461   const SMDS_MeshElement* myElement;
 462   TIndexRanges            myRanges;
 463   int                     myRangeIndex;
 464   const TChunkVector&     myChunks;
 465   int                     myChunkIndex;
 466   get_rangeset_fun        myGetRangeSetFun;
 467   attr_type               myValue;
 468   attr_type               myMinValue;
 469   attr_type               myMaxValue;
 470   filter_ptr              myFilter;
 471   size_t                  myNbElemsToReturn;
 472   size_t                  myNbReturned;
 473
 474   _ChunkIterator( const TChunkVector &      theChunks,
 475                   get_rangeset_fun          theGetRangeSetFun,
 476                   attr_type                 theAttrValue,
 477                   SMDS_MeshElement::Filter* theFilter,
 478                   size_t                    theNbElemsToReturn = -1,
 479                   int                       theChunkIndex = 0):
 480     myElement( 0 ),
 481     myRangeIndex( 0 ),
 482     myChunks( theChunks ),
 483     myChunkIndex( theChunkIndex-1 ),
 484     myGetRangeSetFun( theGetRangeSetFun ),
 485     myValue( theAttrValue ),
 486     myFilter( theFilter ),
 487     myNbElemsToReturn( theNbElemsToReturn ),
 488     myNbReturned( 0 )
 489   {
 490     next();
 491   }
 492   ~_ChunkIterator()
 493   {
 494     delete myFilter;
 495   }
 496
 497   virtual bool more()
 498   {
 499     return myElement;
 500   }
 501
 502   virtual element_type next()
 503   {
 504     element_type result = (element_type) myElement;
 505     myNbReturned += bool( result );
 506
 507     myElement = 0;
 508     if ( myNbReturned < myNbElemsToReturn )
 509       while ( ! nextInRange() )
 510       {
 511         if ( ++myRangeIndex >= (int)myRanges.size() )
 512         {
 513           myRanges.clear();
 514           myRangeIndex = 0;
 515           while ( ++myChunkIndex < (int)myChunks.size() &&
 516                   !getRangeSet().GetIndices( myValue, myRanges, &myMinValue, &myMaxValue ))
 517             ;
 518           if ( myChunkIndex >= (int)myChunks.size() )
 519             break;
 520         }
 521       }
 522     return result;
 523   }
 524
 525   bool nextInRange()
 526   {
 527     if ( myRangeIndex < (int)myRanges.size() )
 528     {
 529       std::pair< int, int > & range = myRanges[ myRangeIndex ];
 530       while ( range.first < range.second && !myElement )
 531       {
 532         myElement = myChunks[ myChunkIndex ].Element( range.first++ );
 533         if ( !(*myFilter)( myElement ))
 534           myElement = 0;
 535       }
 536     }
 537     return myElement;
 538   }
 539
 540   const RANGE_SET& getRangeSet()
 541   {
 542     return ( myChunks[  myChunkIndex ].*myGetRangeSetFun )( myMinValue, myMaxValue );
 543   }
 544 }; // struct _ChunkIterator
 545
 546
 547 template< class ElemIterator >
 548 boost::shared_ptr< ElemIterator >
 549 SMDS_ElementFactory::GetIterator( SMDS_MeshElement::Filter* filter,
 550                                   size_t                    nbElemsToReturn )
 551 {
 552   typedef _ChunkIterator< ElemIterator, TUsedRangeSet > TChuckIterator;
 553   return boost::make_shared< TChuckIterator >( myChunks,
 554                                                & SMDS_ElementChunk::GetUsedRangesMinMax,
 555                                                /*isUsed=*/true,
 556                                                filter,
 557                                                nbElemsToReturn );
 558 }
 559
 560 template< class ElemIterator >
 561 boost::shared_ptr< ElemIterator >
 562 SMDS_ElementFactory::GetShapeIterator( int                     shapeID,
 563                                        size_t                  nbElemsToReturn,
 564                                        const SMDS_MeshElement* sm1stElem )
 565 {
 566   int iChunk = sm1stElem ? (( sm1stElem->GetID() - 1 ) / ChunkSize()) : 0;
 567   typedef _ChunkIterator< ElemIterator, TSubIDRangeSet > TChuckIterator;
 568   return boost::make_shared< TChuckIterator >( myChunks,
 569                                                & SMDS_ElementChunk::GetSubIDRangesMinMax,
 570                                                /*shapeID=*/shapeID,
 571                                                new SMDS_MeshElement::NonNullFilter(),
 572                                                nbElemsToReturn,
 573                                                iChunk );
 574 }
 575
 576 #endif