BUG: EDF 2655: Low performance of hexa to tetra splitting

[modules/smesh.git] / src / SMESH / SMESH_MeshEditor.cxx

diff --git a/src/SMESH/SMESH_MeshEditor.cxx b/src/SMESH/SMESH_MeshEditor.cxx
index e0ab142c9a5619faf2dcd70390395500688972a6..1d5698d249bc67e59ed207f38ab86ebc735811ca 100644 (file)
--- a/src/SMESH/SMESH_MeshEditor.cxx
+++ b/src/SMESH/SMESH_MeshEditor.cxx
@@ -1899,6 +1899,20 @@ namespace
   };
 } // namespace
 
   };
 } // namespace
 

+class TElemToDelete
+{
+public:
+  TElemToDelete(const SMDS_MeshElement* theElem, SMESHDS_SubMesh* theSubMesh)
+  {
+    elem = theElem;
+    subMesh = theSubMesh;
+  }
+  const SMDS_MeshElement* Elem() const {return elem;}
+  SMESHDS_SubMesh* Submesh() {return subMesh;}
+  const SMDS_MeshElement* elem;
+  SMESHDS_SubMesh* subMesh;
+};
+

 //=======================================================================
 //function : SplitVolumesIntoTetra
 //purpose  : Split volume elements into tetrahedra.
 //=======================================================================
 //function : SplitVolumesIntoTetra
 //purpose  : Split volume elements into tetrahedra.


@@ -1924,6 +1938,7 @@ void SMESH_MeshEditor::SplitVolumesIntoTetra (const TIDSortedElemSet & theElems,
   double bc[3];
 
   TIDSortedElemSet::const_iterator elem = theElems.begin();
   double bc[3];
 
   TIDSortedElemSet::const_iterator elem = theElems.begin();

+  std::vector<TElemToDelete> elem_to_delete;

   for ( ; elem != theElems.end(); ++elem )
   {
     if ( (*elem)->GetType() != SMDSAbs_Volume )
   for ( ; elem != theElems.end(); ++elem )
   {
     if ( (*elem)->GetType() != SMDSAbs_Volume )


@@ -2087,11 +2102,26 @@ void SMESH_MeshEditor::SplitVolumesIntoTetra (const TIDSortedElemSet & theElems,
         }
         ReplaceElemInGroups( face, triangles, GetMeshDS() );
         GetMeshDS()->RemoveFreeElement( face, fSubMesh, /*fromGroups=*/false );
         }
         ReplaceElemInGroups( face, triangles, GetMeshDS() );
         GetMeshDS()->RemoveFreeElement( face, fSubMesh, /*fromGroups=*/false );

+//         TElemToDelete faceToDelete(face, fSubMesh);
+//         elem_to_delete.push_back(faceToDelete); 

       }
 
     } // loop on volume faces to split them into triangles
 
       }
 
     } // loop on volume faces to split them into triangles
 

-    GetMeshDS()->RemoveFreeElement( *elem, subMesh, /*fromGroups=*/false );
+//     GetMeshDS()->RemoveFreeElement( *elem, subMesh, /*fromGroups=*/false );
+
+    // rnc : don't delete the elem here because it results in a mesh with a free
+    // ID at the beginning of the ID list. The first tetra is then inserted in O(1)
+    // but the second one is inserted in O(n), then the whole procedure has almost a O(n^2)
+    // complexity. If all elements to remove are stored and removed after tetra creation 
+    // we get a O(n) complexity for the whole procedure. 
+    // The memory cost is at worst a 6*n*constant memory occupation (where n is the number of elements) 
+    // before deletion of the hexas and then 5*n*constant instead of a maximum of 5*n*constant.
+    // So there is a transient 1/5*(memory occupation) additional cost.
+
+    // Store the elements to delete
+    TElemToDelete elemToDelete(*elem, subMesh);
+    elem_to_delete.push_back(elemToDelete);

 
     if ( geomType == SMDSEntity_TriQuad_Hexa )
     {
 
     if ( geomType == SMDSEntity_TriQuad_Hexa )
     {


@@ -2102,6 +2132,13 @@ void SMESH_MeshEditor::SplitVolumesIntoTetra (const TIDSortedElemSet & theElems,
     }
   } // loop on volumes to split
 
     }
   } // loop on volumes to split
 

+  // Delete stored elements
+  std::vector<TElemToDelete>::iterator it;
+  for( it = elem_to_delete.begin(); it!= elem_to_delete.end(); it++)
+  {
+    GetMeshDS()->RemoveFreeElement( it->Elem(), it->Submesh(), /*fromGroups=*/false );
+  }
+  

   myLastCreatedNodes = newNodes;
   myLastCreatedElems = newElems;
 }
   myLastCreatedNodes = newNodes;
   myLastCreatedElems = newElems;
 }