From 8e20930b70add7648527beae51eb4e53d85696c4 Mon Sep 17 00:00:00 2001 From: asuraven Date: Wed, 18 Aug 2021 20:23:07 +0300 Subject: [PATCH] 0032539: Modeling Algorithms - Parallelize BRepExtrema_DistShapeShape algorithm --- src/BRepCheck/BRepCheck_Analyzer.cxx | 10 +- .../BRepExtrema_DistShapeShape.cxx | 312 ++++++++++++++---- .../BRepExtrema_DistShapeShape.hxx | 21 +- src/BRepTest/BRepTest_ExtremaCommands.cxx | 31 +- 4 files changed, 298 insertions(+), 76 deletions(-) diff --git a/src/BRepCheck/BRepCheck_Analyzer.cxx b/src/BRepCheck/BRepCheck_Analyzer.cxx index 1e777665ce..3be4b24cfb 100644 --- a/src/BRepCheck/BRepCheck_Analyzer.cxx +++ b/src/BRepCheck/BRepCheck_Analyzer.cxx @@ -434,7 +434,7 @@ void BRepCheck_Analyzer::Perform (Standard_Boolean theIsParallel) aNbTasks = (Standard_Integer)Ceiling ((double)aMapSize / aTaskSize); } - NCollection_Array1< NCollection_Array1 > aArrayOfArray (0, aNbTasks - 1); + NCollection_Array1< NCollection_Array1 > anArrayOfArray (0, aNbTasks - 1); for (Standard_Integer anI = 1; anI <= aMapSize; ++anI) { Standard_Integer aVectIndex = (anI-1) / aTaskSize; @@ -447,13 +447,13 @@ void BRepCheck_Analyzer::Perform (Standard_Boolean theIsParallel) { aVectorSize = aTailSize; } - aArrayOfArray[aVectIndex].Resize (0, aVectorSize - 1, Standard_False); + anArrayOfArray[aVectIndex].Resize (0, aVectorSize - 1, Standard_False); } - aArrayOfArray[aVectIndex][aShapeIndex] = myMap.FindKey (anI); + anArrayOfArray[aVectIndex][aShapeIndex] = myMap.FindKey (anI); } - BRepCheck_ParallelAnalyzer aParallelAnalyzer (aArrayOfArray, myMap); - OSD_Parallel::For (0, aArrayOfArray.Size(), aParallelAnalyzer, !theIsParallel); + BRepCheck_ParallelAnalyzer aParallelAnalyzer (anArrayOfArray, myMap); + OSD_Parallel::For (0, anArrayOfArray.Size(), aParallelAnalyzer, !theIsParallel); } //======================================================================= diff --git a/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx b/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx index b31ea7a783..13245e7c9c 100644 --- a/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx +++ b/src/BRepExtrema/BRepExtrema_DistShapeShape.cxx @@ -36,6 +36,8 @@ #include #include #include +#include +#include #include #include @@ -217,7 +219,8 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape() myIsInitS1 (Standard_False), myIsInitS2 (Standard_False), myFlag (Extrema_ExtFlag_MINMAX), - myAlgo (Extrema_ExtAlgo_Grad) + myAlgo (Extrema_ExtAlgo_Grad), + myIsBreak(Standard_False) { // } @@ -230,7 +233,8 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape const TopoDS_Shape& Shape2, const Extrema_ExtFlag F, const Extrema_ExtAlgo A, - const Message_ProgressRange& theRange) + const Message_ProgressRange& theRange, + const Standard_Boolean theIsMultiThread) : myDistRef (0.0), myIsDone (Standard_False), myInnerSol (Standard_False), @@ -238,11 +242,12 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape myIsInitS1 (Standard_False), myIsInitS2 (Standard_False), myFlag (F), - myAlgo (A) + myAlgo (A), + myIsBreak(Standard_False) { LoadS1(Shape1); LoadS2(Shape2); - Perform(theRange); + Perform(theRange, theIsMultiThread); } //======================================================================= @@ -255,7 +260,8 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape const Standard_Real theDeflection, const Extrema_ExtFlag F, const Extrema_ExtAlgo A, - const Message_ProgressRange& theRange) + const Message_ProgressRange& theRange, + const Standard_Boolean theIsMultiThread) : myDistRef (0.0), myIsDone (Standard_False), myInnerSol (Standard_False), @@ -263,11 +269,12 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape myIsInitS1 (Standard_False), myIsInitS2 (Standard_False), myFlag (F), - myAlgo (A) + myAlgo (A), + myIsBreak(Standard_False) { LoadS1(Shape1); LoadS2(Shape2); - Perform(theRange); + Perform(theRange, theIsMultiThread); } //======================================================================= @@ -295,24 +302,24 @@ void BRepExtrema_DistShapeShape::LoadS2 (const TopoDS_Shape& Shape2) } //======================================================================= -//function : SolidTreatment +//function : SolidTreatmentOne //purpose : //======================================================================= -void BRepExtrema_DistShapeShape::SolidTreatment(const TopoDS_Shape& theShape, - const TopTools_IndexedMapOfShape& theMap, - const Message_ProgressRange& theRange) +void BRepExtrema_DistShapeShape::SolidTreatmentOne(const TopoDS_Shape& theShape, + const TopTools_IndexedMapOfShape& theMap, + const Message_ProgressRange& theRange { BRepClass3d_SolidClassifier aClassifier(theShape); const Standard_Real aTolerance = 0.001; Message_ProgressScope aScope(theRange, NULL, theMap.Extent()); for (Standard_Integer i = 1; i < theMap.Extent(); ++i) { - aScope.Next(); + Message_ProgressRange aRange = aScope.Next(); if (!aScope.More()) { throw StdFail_NotDone(); } - const TopoDS_Vertex& aVertex = TopoDS::Vertex(theMap(i)); + const TopoDS_Vertex& aVertex = TopoDS::Vertex(theVertexMap(i)); const gp_Pnt& aPnt = BRep_Tool::Pnt(aVertex); aClassifier.Perform(aPnt, aTolerance); if (aClassifier.State() == TopAbs_IN) @@ -328,15 +335,194 @@ void BRepExtrema_DistShapeShape::SolidTreatment(const TopoDS_Shape& theShape, } } +//======================================================================= +//struct : TreatmentTask +//purpose : +//======================================================================= +struct TreatmentTask +{ + TreatmentTask(const TopoDS_Shape* theShape, + const NCollection_Array1* theArray, + const Message_ProgressRange theRange, + Standard_Boolean* theIsBreak, + Standard_Boolean* theInnerSol, + Standard_Boolean* theIsDone) +: myShape(theShape), + myArray(theArray), + myRange(theRange), + myIsBreak(theIsBreak), + myInnerSol(theInnerSol), + myIsDone(theIsDone) + { + } + + TreatmentTask() +: myShape(NULL), + myArray(NULL), + myIsBreak(NULL), + myInnerSol(NULL), + myIsDone(NULL) + { + } + + TreatmentTask& TreatmentTask::operator =(const TreatmentTask& theCopy) + { + myShape = theCopy.myShape; + myArray = theCopy.myArray; + myRange = theCopy.myRange; + myIsBreak = theCopy.myIsBreak; + myInnerSol = theCopy.myInnerSol; + myIsDone = theCopy.myIsDone; + return *this; + } + + BRepExtrema_SeqOfSolution mySolutionsShape; + const TopoDS_Shape* myShape; + const NCollection_Array1* myArray; + Message_ProgressRange myRange; + Standard_Boolean* myIsBreak; + Standard_Boolean* myInnerSol; + Standard_Boolean* myIsDone; +}; + +//======================================================================= +//struct : TreatmentFunctor +//purpose : +//======================================================================= +struct TreatmentFunctor +{ + void operator() (TreatmentTask& theTask) const + { + const Standard_Real aTolerance = 0.001; + Message_ProgressScope aScope(theTask.myRange, NULL, theTask.myArray->Size()); + BRepClass3d_SolidClassifier aClassifier(*theTask.myShape); + + for (Standard_Integer i = 0; i < theTask.myArray->Size(); i++) + { + if (!aScope.More()) + { + Standard_Atomic_CompareAndSwap((int*) theTask.myIsBreak, Standard_False, Standard_True); + } + Message_ProgressRange aRange = aScope.Next(); + + if (!theTask.myIsBreak) + { + break; + } + + const TopoDS_Vertex& aVertex = TopoDS::Vertex(theTask.myArray->Value(i)); + const gp_Pnt& aPnt = BRep_Tool::Pnt(aVertex); + aClassifier.Perform(aPnt, aTolerance); + if (aClassifier.State() == TopAbs_IN) + { + Standard_Atomic_CompareAndSwap((int*) theTask.myInnerSol, Standard_False, Standard_True); + Standard_Atomic_CompareAndSwap((int*) theTask.myIsDone, Standard_False, Standard_True); + BRepExtrema_SolutionElem aSolElem(0, aPnt, BRepExtrema_IsVertex, aVertex); + theTask.mySolutionsShape.Append(aSolElem); + break; + } + } + } +}; + +//======================================================================= +//function : SolidTreatmentMulty +//purpose : +//======================================================================= +Standard_Boolean BRepExtrema_DistShapeShape::SolidTreatmentMulty(const TopoDS_Shape& theShape, + const TopTools_IndexedMapOfShape& theVertexMap, + const Message_ProgressRange& theRange) +{ + const Standard_Integer aMapSize = theVertexMap.Extent(); + const Standard_Integer aMinTaskSize = 3; + const Handle(OSD_ThreadPool)& aThreadPool = OSD_ThreadPool::DefaultPool(); + const Standard_Integer aNbThreads = aThreadPool->NbThreads(); + Standard_Integer aNbTasks = aNbThreads * 10; + Standard_Integer aTaskSize = (Standard_Integer) Ceiling((double) aMapSize / aNbTasks); + if (aTaskSize < aMinTaskSize) + { + aTaskSize = aMinTaskSize; + aNbTasks = (Standard_Integer) Ceiling((double) aMapSize / aTaskSize); + } + + NCollection_Array1< NCollection_Array1 > anArrayOfArray(0, aNbTasks - 1); + for (Standard_Integer anI = 1; anI <= aMapSize; ++anI) + { + Standard_Integer aVectIndex = (anI - 1) / aTaskSize; + Standard_Integer aShapeIndex = (anI - 1) % aTaskSize; + if (aShapeIndex == 0) + { + Standard_Integer aVectorSize = aTaskSize; + Standard_Integer aTailSize = aMapSize - aVectIndex * aTaskSize; + if (aTailSize < aTaskSize) + { + aVectorSize = aTailSize; + } + anArrayOfArray[aVectIndex].Resize(0, aVectorSize - 1, Standard_False); + } + anArrayOfArray[aVectIndex][aShapeIndex] = theVertexMap(anI); + } + + NCollection_Array1 aTaskArray(0, aNbTasks - 1); + Message_ProgressScope aRange(theRange, "Solid treatment", aNbTasks); + for (Standard_Integer anI = 0; anI < aTaskArray.Size(); ++anI) + { + TreatmentTask aTask(&theShape, &anArrayOfArray[anI], aRange.Next(), &myIsBreak, &myInnerSol, &myIsDone); + aTaskArray.SetValue(anI, aTask); + } + + OSD_Parallel::ForEach(aTaskArray.begin(), aTaskArray.end(), TreatmentFunctor(), Standard_False); + + if (myIsBreak) + { + return Standard_False; + } + + if (myInnerSol) + { + myDistRef = 0.; + } + + for (Standard_Integer anI = 0; anI < aTaskArray.Size(); ++anI) + { + mySolutionsShape1.Append(aTaskArray[anI].mySolutionsShape); + mySolutionsShape2.Append(aTaskArray[anI].mySolutionsShape); + } + + return Standard_True; +} +//======================================================================= +//function : SolidTreatment +//purpose : +//======================================================================= +Standard_Boolean BRepExtrema_DistShapeShape::SolidTreatment(const TopoDS_Shape& theShape, + const TopTools_IndexedMapOfShape& theVertexMap, + const Message_ProgressRange& theRange, + const Standard_Boolean theIsMultiThread) +{ + if (theIsMultiThread) + { + return SolidTreatmentMulty(theShape, theVertexMap, theRange); + } + else + { + return SolidTreatmentOne(theShape, theVertexMap, theRange); + } +} + + + //======================================================================= //function : Perform //purpose : //======================================================================= -Standard_Boolean BRepExtrema_DistShapeShape::Perform(const Message_ProgressRange& theRange) +Standard_Boolean BRepExtrema_DistShapeShape::Perform(const Message_ProgressRange& theRange, + const Standard_Boolean theIsMultiThread) { - myIsDone=Standard_False; - myInnerSol=Standard_False; + myIsDone = Standard_False; + myInnerSol = Standard_False; + myIsBreak = Standard_False; mySolutionsShape1.Clear(); mySolutionsShape2.Clear(); @@ -356,50 +542,50 @@ Standard_Boolean BRepExtrema_DistShapeShape::Perform(const Message_ProgressRange { if (anIsSolid1) { - SolidTreatment(myShape1, myMapV2, aRootScope.Next()); + SolidTreatment(myShape1, myMapV2, aRootScope.Next(), theIsMultiThread)); } - + if (anIsSolid2 && (!myInnerSol)) - { - SolidTreatment(myShape2, myMapV1, aRootScope.Next()); + { + SolidTreatment(myShape2, myMapV1, aRootScope.Next(), theIsMultiThread)); } - if (!myInnerSol) + if (!myInnerSol) + { + if (!myIsInitS1) // rebuild cached data for 1st shape { - if (!myIsInitS1) // rebuild cached data for 1st shape - { - myBV1.Clear(); - myBE1.Clear(); - myBF1.Clear(); + myBV1.Clear(); + myBE1.Clear(); + myBF1.Clear(); - BoxCalculation (myMapV1, myBV1); - BoxCalculation (myMapE1, myBE1); - BoxCalculation (myMapF1, myBF1); + BoxCalculation (myMapV1, myBV1); + BoxCalculation (myMapE1, myBE1); + BoxCalculation (myMapF1, myBF1); - myIsInitS1 = Standard_True; - } + myIsInitS1 = Standard_True; + } - if (!myIsInitS2) // rebuild cached data for 2nd shape - { - myBV2.Clear(); - myBE2.Clear(); - myBF2.Clear(); + if (!myIsInitS2) // rebuild cached data for 2nd shape + { + myBV2.Clear(); + myBE2.Clear(); + myBF2.Clear(); - BoxCalculation (myMapV2, myBV2); - BoxCalculation (myMapE2, myBE2); - BoxCalculation (myMapF2, myBF2); + BoxCalculation (myMapV2, myBV2); + BoxCalculation (myMapE2, myBE2); + BoxCalculation (myMapF2, myBF2); - myIsInitS2 = Standard_True; - } + myIsInitS2 = Standard_True; + } - if (myMapV1.Extent() && myMapV2.Extent()) - { - TopoDS_Vertex V1 = TopoDS::Vertex(myMapV1(1)); - TopoDS_Vertex V2 = TopoDS::Vertex(myMapV2(1)); - myDistRef = DistanceInitiale(V1, V2); - } - else - myDistRef= 1.e30; //szv:!!! + if (myMapV1.Extent() && myMapV2.Extent()) + { + TopoDS_Vertex V1 = TopoDS::Vertex(myMapV1(1)); + TopoDS_Vertex V2 = TopoDS::Vertex(myMapV2(1)); + myDistRef = DistanceInitiale(V1, V2); + } + else + myDistRef= 1.e30; //szv:!!! DistanceMapMap (myMapV1, myMapV2, myBV1, myBV2, aRootScope.Next()); DistanceMapMap (myMapV1, myMapE2, myBV1, myBE2, aRootScope.Next()); @@ -410,22 +596,22 @@ Standard_Boolean BRepExtrema_DistShapeShape::Perform(const Message_ProgressRange DistanceMapMap (myMapE1, myMapF2, myBE1, myBF2, aRootScope.Next()); DistanceMapMap (myMapF1, myMapE2, myBF1, myBE2, aRootScope.Next()); - if (fabs (myDistRef) > myEps) - { + if (fabs (myDistRef) > myEps) + { DistanceMapMap (myMapF1, myMapF2, myBF1, myBF2, aRootScope.Next()); - } - - // Modified by Sergey KHROMOV - Tue Mar 6 11:55:03 2001 Begin - Standard_Integer i = 1; - for (; i <= mySolutionsShape1.Length(); i++) - if (mySolutionsShape1.Value(i).Dist() > myDistRef + myEps) - { - mySolutionsShape1.Remove(i); - mySolutionsShape2.Remove(i); - } - // Modified by Sergey KHROMOV - Tue Mar 6 11:55:04 2001 End - myIsDone = ( mySolutionsShape1.Length() > 0 ); } + + // Modified by Sergey KHROMOV - Tue Mar 6 11:55:03 2001 Begin + Standard_Integer i = 1; + for (; i <= mySolutionsShape1.Length(); i++) + if (mySolutionsShape1.Value(i).Dist() > myDistRef + myEps) + { + mySolutionsShape1.Remove(i); + mySolutionsShape2.Remove(i); + } + // Modified by Sergey KHROMOV - Tue Mar 6 11:55:04 2001 End + myIsDone = ( mySolutionsShape1.Length() > 0 ); + } } catch (StdFail_NotDone) { diff --git a/src/BRepExtrema/BRepExtrema_DistShapeShape.hxx b/src/BRepExtrema/BRepExtrema_DistShapeShape.hxx index 182ea6adfb..4337b4e934 100644 --- a/src/BRepExtrema/BRepExtrema_DistShapeShape.hxx +++ b/src/BRepExtrema/BRepExtrema_DistShapeShape.hxx @@ -44,14 +44,16 @@ class BRepExtrema_DistShapeShape const TopoDS_Shape& Shape2, const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX, const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad, - const Message_ProgressRange& theRange = Message_ProgressRange()); + const Message_ProgressRange& theRange = Message_ProgressRange(), + const Standard_Boolean theIsMultiThread = Standard_False); //! create tool and load both shapes into it
Standard_EXPORT BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1, const TopoDS_Shape& Shape2, const Standard_Real theDeflection, const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX, const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad, - const Message_ProgressRange& theRange = Message_ProgressRange()); + const Message_ProgressRange& theRange = Message_ProgressRange(), + const Standard_Boolean theIsMultiThread = Standard_False); void SetDeflection(const Standard_Real theDeflection) { @@ -67,7 +69,8 @@ class BRepExtrema_DistShapeShape //! from the minimum one.
//! Returns IsDone status.
//! theProgress - progress indicator of algorithm - Standard_EXPORT Standard_Boolean Perform(const Message_ProgressRange& theRange = Message_ProgressRange()); + Standard_EXPORT Standard_Boolean Perform(const Message_ProgressRange& theRange = Message_ProgressRange(), + const Standard_Boolean theIsMultiThread = Standard_False); //! True if the minimum distance is found.
Standard_Boolean IsDone() const { @@ -156,8 +159,16 @@ private: void SolidTreatment(const TopoDS_Shape& theShape, const TopTools_IndexedMapOfShape& theMap, - const Message_ProgressRange& theRange); + const Message_ProgressRange& theRange, + const Standard_Boolean theIsMultiThread); + Standard_Boolean SolidTreatmentOne(const TopoDS_Shape& theShape, + const TopTools_IndexedMapOfShape& theVertexMap, + const Message_ProgressRange& theRange); + + Standard_Boolean SolidTreatmentMulty(const TopoDS_Shape& theShape, + const TopTools_IndexedMapOfShape& theVertexMap, + const Message_ProgressRange& theRange); private: Standard_Real myDistRef; @@ -184,6 +195,8 @@ private: Bnd_SeqOfBox myBE2; Bnd_SeqOfBox myBF1; Bnd_SeqOfBox myBF2; + + Standard_Boolean myIsBreak; }; #endif diff --git a/src/BRepTest/BRepTest_ExtremaCommands.cxx b/src/BRepTest/BRepTest_ExtremaCommands.cxx index 0fa44321d1..9673bf0255 100644 --- a/src/BRepTest/BRepTest_ExtremaCommands.cxx +++ b/src/BRepTest/BRepTest_ExtremaCommands.cxx @@ -64,19 +64,39 @@ static Standard_Integer distance (Draw_Interpretor& di, static Standard_Integer distmini(Draw_Interpretor& di, Standard_Integer n, const char** a) { - if (n != 4 && n != 5 ) + if (n < 4 || n > 6) + { return 1; + } const char *ns1 = (a[2]), *ns2 = (a[3]), *ns0 = (a[1]); TopoDS_Shape S1(DBRep::Get(ns1)), S2(DBRep::Get(ns2)); Standard_Real aDeflection = Precision::Confusion(); - if (n == 5) + if (n >= 5 && strncmp(a[4], "-", 1)) + { aDeflection = Draw::Atof(a[4]); + } + + Standard_Boolean anIsMultiThread = Standard_False; + for (Standard_Integer anAI = 4; anAI < n; anAI++) + { + TCollection_AsciiString anArg(a[anAI]); + anArg.LowerCase(); + if (anArg == "-parallel") + { + anIsMultiThread = Standard_True; + } + else + { + di << "Syntax error at '" << anArg << "'"; + return 1; + } + } Handle(Draw_ProgressIndicator) aProgress = new Draw_ProgressIndicator(di, 1); BRepExtrema_DistShapeShape dst(S1 ,S2, aDeflection, Extrema_ExtFlag_MINMAX, - Extrema_ExtAlgo_Grad, aProgress->Start()); + Extrema_ExtAlgo_Grad, aProgress->Start(), anIsMultiThread); if (dst.IsDone()) { @@ -412,7 +432,10 @@ void BRepTest::ExtremaCommands (Draw_Interpretor& theCommands) aGroup); theCommands.Add ("distmini", - "distmini name Shape1 Shape2 [deflection]", + "distmini name Shape1 Shape2 [deflection] [-parallel]", + "\n\t\t: Searches minimal distance between two shapes." + "\n\t\t: The option is:" + "\n\t\t: -parallel : calculate distance in multithreaded mode" __FILE__, distmini, aGroup); -- 2.39.5