0032539: Modeling Algorithms - Parallelize BRepExtrema_DistShapeShape algorithm CR0-WEEK-39 IR-2021-10-01
authorasuraven <asuraven@opencascade.com>
Wed, 18 Aug 2021 17:23:07 +0000 (20:23 +0300)
committersmoskvin <smoskvin@opencascade.com>
Fri, 1 Oct 2021 16:14:13 +0000 (19:14 +0300)
src/BRepExtrema/BRepExtrema_DistShapeShape.cxx
src/BRepExtrema/BRepExtrema_DistShapeShape.hxx
src/BRepExtrema/BRepExtrema_DistanceSS.cxx
src/BRepTest/BRepTest_ExtremaCommands.cxx
tests/perf/modalg/bug32539_1 [new file with mode: 0644]
tests/perf/modalg/bug32539_2 [new file with mode: 0644]

index dcd92f2..1ef68ed 100644 (file)
@@ -36,6 +36,7 @@
 #include <BRep_Tool.hxx>
 #include <BRepClass3d_SolidClassifier.hxx>
 #include <NCollection_Vector.hxx>
+#include <OSD_Parallel.hxx>
 #include <StdFail_NotDone.hxx>
 
 #include <algorithm>
@@ -56,13 +57,13 @@ namespace
   }
 
   static void BoxCalculation(const TopTools_IndexedMapOfShape& Map,
-                             Bnd_SeqOfBox&                     SBox)
+                             Bnd_Array1OfBox&                  SBox)
   {
     for (Standard_Integer i = 1; i <= Map.Extent(); i++)
     {
       Bnd_Box box;
       BRepBndLib::Add(Map(i), box);
-      SBox.Append(box);
+      SBox[i] = box;
     }
   }
 
@@ -105,157 +106,510 @@ namespace
 }
 
 //=======================================================================
-//function : DistanceMapMap
+//struct   : IndexBand
 //purpose  : 
 //=======================================================================
+struct IndexBand
+{
+  IndexBand():
+    First(0),
+    Last(0)
+  {
+  }  
+  
+  IndexBand(Standard_Integer theFirtsIndex,
+            Standard_Integer theLastIndex):
+    First(theFirtsIndex),
+    Last(theLastIndex)
+  {
+  }
+  Standard_Integer First;
+  Standard_Integer Last;
+};
 
-Standard_Boolean BRepExtrema_DistShapeShape::DistanceMapMap (const TopTools_IndexedMapOfShape& theMap1,
-                                                             const TopTools_IndexedMapOfShape& theMap2,
-                                                             const Bnd_SeqOfBox&               theLBox1,
-                                                             const Bnd_SeqOfBox&               theLBox2,
-                                                             const Message_ProgressRange&      theRange)
+//=======================================================================
+//struct   : ThreadSolution
+//purpose  : 
+//=======================================================================
+struct ThreadSolution
 {
-  NCollection_Vector<BRepExtrema_CheckPair> aPairList;
-  const Standard_Integer aCount1 = theMap1.Extent();
-  const Standard_Integer aCount2 = theMap2.Extent();
+  ThreadSolution(Standard_Integer theTaskNum):
+    Shape1(0, theTaskNum-1),
+    Shape2(0, theTaskNum-1),
+    Dist(0, theTaskNum-1)
+  {
+    Dist.Init(DBL_MAX);
+  }
 
-  Message_ProgressScope aTwinScope(theRange, NULL, 1.0);
-  Message_ProgressRange aBoxRange(aTwinScope.Next(0.3));
-  Message_ProgressScope aBoxScope(aBoxRange, NULL, aCount1);
+  NCollection_Array1<BRepExtrema_SeqOfSolution> Shape1;
+  NCollection_Array1<BRepExtrema_SeqOfSolution> Shape2;
+  NCollection_Array1<Standard_Real>             Dist;
+};
 
-  for (Standard_Integer anIdx1 = 1; anIdx1 <= aCount1; ++anIdx1)
+//=======================================================================
+//struct   : VertexFunctor
+//purpose  : 
+//=======================================================================
+struct VertexFunctor
+{
+  VertexFunctor(NCollection_Array1<IndexBand>* theBandArray,
+                const Message_ProgressRange& theRange):
+    BandArray(theBandArray),
+    Solution(theBandArray->Size()),
+    Map1(NULL),
+    Map2(NULL),
+    Scope(theRange, "Vertices distances calculating", theBandArray->Size()),
+    Ranges(0, theBandArray->Size() - 1),
+    Eps(Precision::Confusion()),
+    StartDist(0.0)
   {
-    aBoxScope.Next();
-    if (!aBoxScope.More())
+    for (Standard_Integer i = 0; i < theBandArray->Size(); ++i)
     {
-      return Standard_False;
+      Ranges.SetValue(i, Scope.Next());
     }
-    for (Standard_Integer anIdx2 = 1; anIdx2 <= aCount2; ++anIdx2)
+  }
+
+  void operator() (const Standard_Integer theIndex) const
+  {
+    const Standard_Integer aCount2 = Map2->Extent();
+    const Standard_Integer aFirst = BandArray->Value(theIndex).First;
+    const Standard_Integer aLast  = BandArray->Value(theIndex).Last;
+    Solution.Dist[theIndex] = StartDist;
+
+    Message_ProgressScope aScope(Ranges[theIndex], NULL, (double)aLast - aFirst);
+
+
+    for (Standard_Integer anIdx1 = aFirst; anIdx1 <= aLast; ++anIdx1)
     {
-      const Bnd_Box& aBox1 = theLBox1.Value (anIdx1);
-      const Bnd_Box& aBox2 = theLBox2.Value (anIdx2);
-      if (aBox1.IsVoid()
-       || aBox2.IsVoid())
+      if (!aScope.More())
       {
-        continue;
+        break;
       }
+      aScope.Next();
 
-      const Standard_Real aDist = aBox1.Distance (aBox2);
-      if (aDist < myDistRef - myEps || fabs (aDist - myDistRef) < myEps)
+      const TopoDS_Vertex& aVertex1 = TopoDS::Vertex(Map1->FindKey(anIdx1));
+      const gp_Pnt aPoint1 = BRep_Tool::Pnt(aVertex1);
+      for (Standard_Integer anIdx2 = 1; anIdx2 <= aCount2; ++anIdx2)
       {
-        aPairList.Append (BRepExtrema_CheckPair (anIdx1, anIdx2, aDist));
+        const TopoDS_Vertex& aVertex2 = TopoDS::Vertex(Map2->FindKey(anIdx2));
+        const gp_Pnt aPoint2 = BRep_Tool::Pnt(aVertex2);
+        const Standard_Real aDist = aPoint1.Distance(aPoint2);
+        {
+          if (aDist < Solution.Dist[theIndex] - Eps)
+          { 
+            const BRepExtrema_SolutionElem Sol1(aDist, aPoint1, BRepExtrema_IsVertex, aVertex1);
+            const BRepExtrema_SolutionElem Sol2(aDist, aPoint2, BRepExtrema_IsVertex, aVertex2);
+
+            Solution.Shape1[theIndex].Clear();
+            Solution.Shape2[theIndex].Clear();
+            Solution.Shape1[theIndex].Append(Sol1);
+            Solution.Shape2[theIndex].Append(Sol2);
+            
+            Solution.Dist[theIndex] = aDist;
+          }
+          else if (Abs(aDist - Solution.Dist[theIndex]) < Eps)
+          {
+            const BRepExtrema_SolutionElem Sol1(aDist, aPoint1, BRepExtrema_IsVertex, aVertex1);
+            const BRepExtrema_SolutionElem Sol2(aDist, aPoint2, BRepExtrema_IsVertex, aVertex2);
+            Solution.Shape1[theIndex].Append(Sol1);
+            Solution.Shape2[theIndex].Append(Sol2);
+
+            if (Solution.Dist[theIndex] > aDist)
+            {
+              Solution.Dist[theIndex] = aDist;
+            }
+          }          
+        }
       }
     }
   }
-  std::stable_sort(aPairList.begin(), aPairList.end(), BRepExtrema_CheckPair_Comparator);
-  Message_ProgressRange aDistRange(aTwinScope.Next(0.7));
-  Message_ProgressScope aDistScope(aDistRange, NULL, aPairList.Size());
-  for (NCollection_Vector<BRepExtrema_CheckPair>::Iterator aPairIter (aPairList);
-       aPairIter.More(); aPairIter.Next())
+
+  NCollection_Array1<IndexBand>*            BandArray;
+  mutable ThreadSolution                    Solution;
+  const TopTools_IndexedMapOfShape*         Map1;
+  const TopTools_IndexedMapOfShape*         Map2;
+  Message_ProgressScope                     Scope;
+  NCollection_Array1<Message_ProgressRange> Ranges;
+  Standard_Real                             Eps;
+  Standard_Real                             StartDist;
+};
+
+//=======================================================================
+//function : DistanceVertVert
+//purpose  : 
+//=======================================================================
+Standard_Boolean BRepExtrema_DistShapeShape::DistanceVertVert(const TopTools_IndexedMapOfShape& theMap1,
+                                                              const TopTools_IndexedMapOfShape& theMap2,
+                                                              const Message_ProgressRange& theRange)
+{
+  const Standard_Integer aCount1 = theMap1.Extent();
+  const Standard_Integer aMinTaskSize = aCount1 < 10 ? aCount1 : 10;
+  const Handle(OSD_ThreadPool)& aThreadPool = OSD_ThreadPool::DefaultPool();
+  const Standard_Integer aNbThreads = aThreadPool->NbThreads();
+  Standard_Integer aNbTasks = aNbThreads;
+  Standard_Integer aTaskSize = (Standard_Integer) Ceiling((double) aCount1 / aNbTasks);
+  if (aTaskSize < aMinTaskSize)
   {
-    aDistScope.Next();
-    if (!aDistScope.More())
+    aTaskSize = aMinTaskSize;
+    aNbTasks = (Standard_Integer) Ceiling((double) aCount1 / aTaskSize);
+  }
+
+  Standard_Integer aFirstIndex(1);
+  NCollection_Array1<IndexBand> aBandArray(0, aNbTasks - 1);
+  Message_ProgressScope aDistScope(theRange, NULL, 1);
+
+  for (Standard_Integer anI = 0; anI < aBandArray.Size(); ++anI)
+  {
+    if (aCount1 < aFirstIndex + aTaskSize - 1)
     {
-      return Standard_False;
+      aTaskSize = aCount1 - aFirstIndex + 1;
     }
-    const BRepExtrema_CheckPair& aPair = aPairIter.Value();
-    if (aPair.Distance > myDistRef + myEps)
+    aBandArray.SetValue(anI, IndexBand(aFirstIndex, aFirstIndex + aTaskSize - 1));
+    aFirstIndex += aTaskSize;
+  }
+
+  VertexFunctor aFunctor(&aBandArray, aDistScope.Next());
+  aFunctor.Map1            = &theMap1;
+  aFunctor.Map2            = &theMap2;
+  aFunctor.StartDist       = myDistRef;
+  aFunctor.Eps             = myEps;
+
+  OSD_Parallel::For(0, aNbTasks, aFunctor, !myIsMultiThread);
+  if (!aDistScope.More())
+  {
+    return Standard_False;
+  }    
+  for (Standard_Integer anI = 0; anI < aFunctor.Solution.Dist.Size(); ++anI)
+  {
+    Standard_Real aDist = aFunctor.Solution.Dist[anI];
+    if (aDist < myDistRef - myEps)
     {
-      break; // early search termination
+      mySolutionsShape1.Clear();
+      mySolutionsShape2.Clear();
+      mySolutionsShape1.Append(aFunctor.Solution.Shape1[anI]);
+      mySolutionsShape2.Append(aFunctor.Solution.Shape2[anI]);
+      myDistRef = aDist;
     }
+    else if (Abs(aDist - myDistRef) < myEps)
+    {
+      mySolutionsShape1.Append(aFunctor.Solution.Shape1[anI]);
+      mySolutionsShape2.Append(aFunctor.Solution.Shape2[anI]);
+      myDistRef = aDist;
+    }
+  }
+  return Standard_True;
+}
 
-    const Bnd_Box& aBox1 = theLBox1.Value (aPair.Index1);
-    const Bnd_Box& aBox2 = theLBox2.Value (aPair.Index2);
-
-    const TopoDS_Shape& aShape1 = theMap1 (aPair.Index1);
-    const TopoDS_Shape& aShape2 = theMap2 (aPair.Index2);
+//=======================================================================
+//struct   : DistanceFunctor
+//purpose  : 
+//=======================================================================
+struct DistanceFunctor
+{
+  DistanceFunctor(NCollection_Array1<NCollection_Array1<BRepExtrema_CheckPair> >* theArrayOfArrays,
+                  const Message_ProgressRange& theRange):
+    ArrayOfArrays(theArrayOfArrays), 
+    Solution(ArrayOfArrays->Size()),
+    Map1(NULL),
+    Map2(NULL),
+    LBox1(NULL),
+    LBox2(NULL),
+    Scope(theRange, "Shapes distances calculating", theArrayOfArrays->Size()),
+    Ranges(0, theArrayOfArrays->Size() - 1),
+    Eps(Precision::Confusion()),
+    StartDist(0.0)
+  {
+    for (Standard_Integer i = 0; i < theArrayOfArrays->Size(); ++i)
+    {
+      Ranges.SetValue(i, Scope.Next());
+    }
+  }
 
-    BRepExtrema_DistanceSS aDistTool (aShape1, aShape2, aBox1, aBox2, myDistRef, myEps);
-    if (aDistTool.IsDone())
+  void operator() (const Standard_Integer theIndex) const
+  {
+    Message_ProgressScope aScope(Ranges[theIndex], NULL, ArrayOfArrays->Value(theIndex).Size());
+    Solution.Dist[theIndex] = StartDist;
+    for (Standard_Integer i = 0; i < ArrayOfArrays->Value(theIndex).Size(); i++)
     {
-      if (aDistTool.DistValue() < myDistRef - myEps)
+      if (!aScope.More())
+      {
+        return;
+      }
+      aScope.Next();
+      const BRepExtrema_CheckPair& aPair = ArrayOfArrays->Value(theIndex).Value(i);
+      if (aPair.Distance > Solution.Dist[theIndex] + Eps)
+      {
+        break; // early search termination
+      }
+      const Bnd_Box& aBox1 = LBox1->Value(aPair.Index1);
+      const Bnd_Box& aBox2 = LBox2->Value(aPair.Index2);
+      const TopoDS_Shape& aShape1 = Map1->FindKey(aPair.Index1);
+      const TopoDS_Shape& aShape2 = Map2->FindKey(aPair.Index2);
+      BRepExtrema_DistanceSS aDistTool(aShape1, aShape2, aBox1, aBox2, Solution.Dist[theIndex], Eps);
+      const Standard_Real aDist = aDistTool.DistValue();
+      if (aDistTool.IsDone())
       {
-        mySolutionsShape1.Clear();
-        mySolutionsShape2.Clear();
+        if (aDist < Solution.Dist[theIndex] - Eps)
+        {
+          Solution.Shape1[theIndex].Clear();
+          Solution.Shape2[theIndex].Clear();
 
-        BRepExtrema_SeqOfSolution aSeq1 = aDistTool.Seq1Value();
-        BRepExtrema_SeqOfSolution aSeq2 = aDistTool.Seq2Value();
+          BRepExtrema_SeqOfSolution aSeq1 = aDistTool.Seq1Value();
+          BRepExtrema_SeqOfSolution aSeq2 = aDistTool.Seq2Value();
 
-        mySolutionsShape1.Append (aSeq1);
-        mySolutionsShape2.Append (aSeq2);
+          Solution.Shape1[theIndex].Append(aSeq1);
+          Solution.Shape2[theIndex].Append(aSeq2);
 
-        myDistRef = aDistTool.DistValue();
+          Solution.Dist[theIndex] = aDistTool.DistValue();
+        }
+        else if (Abs(aDist - Solution.Dist[theIndex]) < Eps)
+        {
+          BRepExtrema_SeqOfSolution aSeq1 = aDistTool.Seq1Value();
+          BRepExtrema_SeqOfSolution aSeq2 = aDistTool.Seq2Value();
+
+          Solution.Shape1[theIndex].Append(aSeq1);
+          Solution.Shape2[theIndex].Append(aSeq2);
+          if (Solution.Dist[theIndex] > aDist)
+          {
+            Solution.Dist[theIndex] = aDist;
+          }
+        }
       }
-      else if (fabs (aDistTool.DistValue() - myDistRef) < myEps)
+    }
+  }
+
+  NCollection_Array1<NCollection_Array1<BRepExtrema_CheckPair> >* ArrayOfArrays;
+  mutable ThreadSolution                    Solution;
+  const TopTools_IndexedMapOfShape*         Map1;
+  const TopTools_IndexedMapOfShape*         Map2;
+  const Bnd_Array1OfBox*                    LBox1;
+  const Bnd_Array1OfBox*                    LBox2;
+  Message_ProgressScope                     Scope;
+  NCollection_Array1<Message_ProgressRange> Ranges;
+  Standard_Real                             Eps;
+  Standard_Real                             StartDist;
+};
+
+
+//=======================================================================
+//struct   : DistancePairFunctor
+//purpose  : 
+//=======================================================================
+struct DistancePairFunctor
+{
+  DistancePairFunctor(NCollection_Array1<IndexBand>* theBandArray,
+                      const Message_ProgressRange& theRange):
+    BandArray(theBandArray),
+    PairList(0, theBandArray->Size() - 1),
+    LBox1(NULL),
+    LBox2(NULL),
+    Scope(theRange, "Boxes distances calculating", theBandArray->Size()),
+    Ranges(0, theBandArray->Size() - 1),
+    DistRef(0),
+    Eps(Precision::Confusion())
+  {
+    for (Standard_Integer i = 0; i < theBandArray->Size(); ++i)
+    {
+      Ranges.SetValue(i, Scope.Next());
+    }
+  }
+
+  void operator() (const Standard_Integer theIndex) const
+  {
+    const Standard_Integer aFirst = BandArray->Value(theIndex).First;
+    const Standard_Integer aLast  = BandArray->Value(theIndex).Last;
+
+    Message_ProgressScope aScope(Ranges[theIndex], NULL, (double) aLast - aFirst);
+
+    for (Standard_Integer anIdx1 = aFirst; anIdx1 <= aLast; ++anIdx1)
+    {
+      if (!aScope.More())
       {
-        BRepExtrema_SeqOfSolution aSeq1 = aDistTool.Seq1Value();
-        BRepExtrema_SeqOfSolution aSeq2 = aDistTool.Seq2Value();
+        break;
+      }
+      aScope.Next();
 
-        mySolutionsShape1.Append (aSeq1);
-        mySolutionsShape2.Append (aSeq2);
+      for (Standard_Integer anIdx2 = 1; anIdx2 <= LBox2->Size(); ++anIdx2)
+      {
+        const Bnd_Box& aBox1 = LBox1->Value(anIdx1);
+        const Bnd_Box& aBox2 = LBox2->Value(anIdx2);
+        if (aBox1.IsVoid() || aBox2.IsVoid())
+        {
+          continue;
+        }
 
-        if (myDistRef > aDistTool.DistValue())
+        const Standard_Real aDist = aBox1.Distance(aBox2);       
+        if (aDist - DistRef < Eps)
         {
-          myDistRef = aDistTool.DistValue();
+          PairList[theIndex].Append(BRepExtrema_CheckPair(anIdx1, anIdx2, aDist));
         }
       }
     }
   }
-  return Standard_True;
-}
+
+  Standard_Integer ListSize()
+  {
+    Standard_Integer aSize(0);
+    for (Standard_Integer anI = PairList.Lower(); anI <= PairList.Upper(); ++anI)
+    {
+      aSize += PairList[anI].Size();
+    }
+    return aSize;
+  }
+
+  NCollection_Array1<IndexBand>*             BandArray;
+  mutable NCollection_Array1<NCollection_Vector<BRepExtrema_CheckPair> > PairList;
+  const Bnd_Array1OfBox*                     LBox1;
+  const Bnd_Array1OfBox*                     LBox2;
+  Message_ProgressScope                      Scope;
+  NCollection_Array1<Message_ProgressRange>  Ranges;
+  Standard_Real                              DistRef;
+  Standard_Real                              Eps;
+};
 
 //=======================================================================
-//function : DistanceVertVert
+//function : DistanceMapMap
 //purpose  : 
 //=======================================================================
 
-Standard_Boolean BRepExtrema_DistShapeShape::DistanceVertVert(const TopTools_IndexedMapOfShape& theMap1,
-                                                              const TopTools_IndexedMapOfShape& theMap2,
-                                                              const Message_ProgressRange& theRange)
+Standard_Boolean BRepExtrema_DistShapeShape::DistanceMapMap (const TopTools_IndexedMapOfShape& theMap1,
+                                                             const TopTools_IndexedMapOfShape& theMap2,
+                                                             const Bnd_Array1OfBox&            theLBox1,
+                                                             const Bnd_Array1OfBox&            theLBox2,
+                                                             const Message_ProgressRange&      theRange)
 {
   const Standard_Integer aCount1 = theMap1.Extent();
   const Standard_Integer aCount2 = theMap2.Extent();
 
-  Message_ProgressScope aScope(theRange, NULL, aCount1);
+  if (aCount1 == 0 || aCount2 == 0)
+  {
+    return Standard_True;
+  }
+
+  Message_ProgressScope aTwinScope(theRange, NULL, 1.0);
 
-  for (Standard_Integer anIdx1 = 1; anIdx1 <= aCount1; ++anIdx1)
+  const Handle(OSD_ThreadPool)& aThreadPool = OSD_ThreadPool::DefaultPool();
+  const Standard_Integer aNbThreads = aThreadPool->NbThreads();
+  const Standard_Integer aMinPairTaskSize = aCount1 < 10 ? aCount1 : 10;
+  Standard_Integer aNbPairTasks = aNbThreads;
+  Standard_Integer aPairTaskSize = (Standard_Integer) Ceiling((double) aCount1 / aNbPairTasks);
+  if (aPairTaskSize < aMinPairTaskSize)
   {
-    aScope.Next();
-    if (!aScope.More())
+    aPairTaskSize = aMinPairTaskSize;
+    aNbPairTasks = (Standard_Integer) Ceiling((double) aCount1 / aPairTaskSize);
+  }
+
+  Standard_Integer aFirstIndex(1);
+  NCollection_Array1<IndexBand> aBandArray(0, aNbPairTasks - 1);
+
+  for (Standard_Integer anI = 0; anI < aBandArray.Size(); ++anI)
+  {
+    if (aCount1 < aFirstIndex + aPairTaskSize - 1)
     {
-      return Standard_False;
+      aPairTaskSize = aCount1 - aFirstIndex + 1;
     }
-    const TopoDS_Vertex& aVertex1 = TopoDS::Vertex(theMap1.FindKey(anIdx1));
-    const gp_Pnt aPoint1 = BRep_Tool::Pnt(aVertex1);
-    for (Standard_Integer anIdx2 = 1; anIdx2 <= aCount2; ++anIdx2)
-    {
-      const TopoDS_Vertex& aVertex2 = TopoDS::Vertex(theMap2.FindKey(anIdx2));
-      const gp_Pnt aPoint2 = BRep_Tool::Pnt(aVertex2);
+    aBandArray.SetValue(anI, IndexBand(aFirstIndex, aFirstIndex + aPairTaskSize - 1));
+    aFirstIndex += aPairTaskSize;
+  }
 
-      const Standard_Real aDist = aPoint1.Distance(aPoint2);
-      if (aDist < myDistRef - myEps)
-      {
-        mySolutionsShape1.Clear();
-        mySolutionsShape2.Clear();
+  aTwinScope.Next(0.15);
+  DistancePairFunctor aPairFunctor(&aBandArray, aTwinScope.Next(0.15));
+  aPairFunctor.LBox1 = &theLBox1;
+  aPairFunctor.LBox2 = &theLBox2;
+  aPairFunctor.DistRef = myDistRef;
+  aPairFunctor.Eps = myEps;
 
-        const BRepExtrema_SolutionElem Sol1(aDist, aPoint1, BRepExtrema_IsVertex, aVertex1);
-        const BRepExtrema_SolutionElem Sol2(aDist, aPoint2, BRepExtrema_IsVertex, aVertex2);
-        mySolutionsShape1.Append(Sol1);
-        mySolutionsShape2.Append(Sol2);
+  OSD_Parallel::For(0, aNbPairTasks, aPairFunctor, !myIsMultiThread);
+  if (!aTwinScope.More())
+  {
+    return Standard_False;
+  }
+  Standard_Integer aListSize = aPairFunctor.ListSize();
+  if(aListSize == 0)
+  {
+    return Standard_True;
+  }
+  NCollection_Array1<BRepExtrema_CheckPair> aPairList(0, aListSize-1);
+  Standard_Integer aListIndex(0);
+  for (Standard_Integer anI = 0; anI < aPairFunctor.PairList.Size(); ++anI)
+  {
+    for (Standard_Integer aJ = 0; aJ < aPairFunctor.PairList[anI].Size(); ++aJ)
+    {
+      aPairList[aListIndex] = aPairFunctor.PairList[anI][aJ];
+      ++aListIndex;
+    }
+  }
 
-        myDistRef = aDist;
-      }
-      else if (fabs(aDist - myDistRef) < myEps)
-      {
-        const BRepExtrema_SolutionElem Sol1(aDist, aPoint1, BRepExtrema_IsVertex, aVertex1);
-        const BRepExtrema_SolutionElem Sol2(aDist, aPoint2, BRepExtrema_IsVertex, aVertex2);
-        mySolutionsShape1.Append(Sol1);
-        mySolutionsShape2.Append(Sol2);
+  std::stable_sort(aPairList.begin(), aPairList.end(), BRepExtrema_CheckPair_Comparator);
 
-        if (myDistRef > aDist)
+  const Standard_Integer aMapSize = aPairList.Size();
+  Standard_Integer aNbTasks = aMapSize < aNbThreads ? aMapSize : aNbThreads;
+  Standard_Integer aTaskSize = (Standard_Integer) Ceiling((double) aMapSize / aNbTasks);
+  NCollection_Array1<NCollection_Array1<BRepExtrema_CheckPair> > anArrayOfArray(0, aNbTasks - 1);
+  // Since aPairList is sorted in ascending order of distances between Bnd_Boxes,
+  // BRepExtrema_CheckPair are distributed to tasks one by one from smallest to largest,
+  // and not ranges, as for DistancePairFunctor.
+  // Since aMapSize may not be divisible entirely by the number of tasks,
+  // some tasks should receive one BRepExtrema_CheckPair less than the rest.
+  // aLastRowLimit defines the task number from which to start tasks containing
+  // fewer BRepExtrema_CheckPair
+  Standard_Integer aLastRowLimit = ((aMapSize % aNbTasks) == 0) ? aNbTasks : (aMapSize % aNbTasks);
+  for (Standard_Integer anI = 0; anI < aTaskSize; ++anI)
+  {
+    for (Standard_Integer aJ = 0; aJ < aNbTasks; ++aJ)
+    {
+      if (anI == 0)
+      {
+        Standard_Integer aVectorSize = aTaskSize;
+        if (aJ >= aLastRowLimit)
         {
-          myDistRef = aDist;
+          aVectorSize--;
         }
+        anArrayOfArray[aJ].Resize(0, aVectorSize - 1, Standard_False);
+      }
+      if (anI < anArrayOfArray[aJ].Size())
+      {
+        anArrayOfArray[aJ][anI] = aPairList(anI*aNbTasks + aJ);
+      }
+      else
+      {
+        break;
+      }
+    }
+  }
+  DistanceFunctor aFunctor(&anArrayOfArray, aTwinScope.Next(0.85));
+  aFunctor.Map1 = &theMap1;
+  aFunctor.Map2 = &theMap2;
+  aFunctor.LBox1 = &theLBox1;
+  aFunctor.LBox2 = &theLBox2;
+  aFunctor.Eps = myEps;
+  aFunctor.StartDist = myDistRef;
+
+  OSD_Parallel::For(0, aNbTasks, aFunctor, !myIsMultiThread);
+  if (!aTwinScope.More())
+  {
+    return Standard_False;
+  }
+
+  for (Standard_Integer anI = 0; anI < aFunctor.Solution.Dist.Size(); ++anI)
+  {
+    Standard_Real aDist = aFunctor.Solution.Dist[anI];
+    if (aDist < myDistRef - myEps)
+    {
+      mySolutionsShape1.Clear();
+      mySolutionsShape2.Clear();
+      mySolutionsShape1.Append(aFunctor.Solution.Shape1[anI]);
+      mySolutionsShape2.Append(aFunctor.Solution.Shape2[anI]);
+      myDistRef = aDist;
+    }
+    else if (Abs(aDist - myDistRef) < myEps)
+    {
+      mySolutionsShape1.Append(aFunctor.Solution.Shape1[anI]);
+      mySolutionsShape2.Append(aFunctor.Solution.Shape2[anI]);
+      if (myDistRef > aDist)
+      {
+        myDistRef = aDist;
       }
     }
   }
@@ -275,9 +629,9 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape()
   myIsInitS1 (Standard_False),
   myIsInitS2 (Standard_False),
   myFlag (Extrema_ExtFlag_MINMAX),
-  myAlgo (Extrema_ExtAlgo_Grad)
+  myAlgo (Extrema_ExtAlgo_Grad),
+  myIsMultiThread(Standard_False)
 {
-  //
 }
 
 //=======================================================================
@@ -296,7 +650,8 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape
   myIsInitS1 (Standard_False),
   myIsInitS2 (Standard_False),
   myFlag (F),
-  myAlgo (A)
+  myAlgo (A),
+  myIsMultiThread(Standard_False)
 {
   LoadS1(Shape1);
   LoadS2(Shape2);
@@ -321,7 +676,8 @@ BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape
   myIsInitS1 (Standard_False),
   myIsInitS2 (Standard_False),
   myFlag (F),
-  myAlgo (A)
+  myAlgo (A),
+  myIsMultiThread(Standard_False)
 {
   LoadS1(Shape1);
   LoadS2(Shape2);
@@ -352,37 +708,133 @@ void BRepExtrema_DistShapeShape::LoadS2 (const TopoDS_Shape& Shape2)
   Decomposition (Shape2, myMapV2, myMapE2, myMapF2);
 }
 
+//=======================================================================
+//struct   : TreatmentFunctor
+//purpose  : 
+//=======================================================================
+struct TreatmentFunctor
+{
+  TreatmentFunctor(NCollection_Array1<NCollection_Array1<TopoDS_Shape> >* theArrayOfArrays,
+                   const Message_ProgressRange& theRange):
+  ArrayOfArrays(theArrayOfArrays),
+  SolutionsShape1(NULL),
+  SolutionsShape2(NULL),
+  Scope(theRange, "Search for the inner solid", theArrayOfArrays->Size()),
+  Ranges(0, theArrayOfArrays->Size() - 1),
+  DistRef(0),
+  InnerSol(NULL),
+  IsDone(NULL),
+  Mutex(NULL)
+  {
+    for (Standard_Integer i = 0; i < theArrayOfArrays->Size(); ++i)
+    {
+      Ranges.SetValue(i, Scope.Next());
+    }
+  }
+
+  void operator() (const Standard_Integer theIndex) const
+  {
+    const Standard_Real aTolerance = 0.001;
+    Message_ProgressScope aScope(Ranges[theIndex], NULL, ArrayOfArrays->Value(theIndex).Size());
+    BRepClass3d_SolidClassifier aClassifier(Shape);
+
+    for (Standard_Integer i = 0; i < ArrayOfArrays->Value(theIndex).Size(); i++)
+    {
+      if (!aScope.More())
+      {
+        break;
+      }
+      aScope.Next();
+      if (*IsDone)
+      {
+        break;
+      }
+
+      const TopoDS_Vertex& aVertex = TopoDS::Vertex(ArrayOfArrays->Value(theIndex).Value(i));
+      const gp_Pnt aPnt = BRep_Tool::Pnt(aVertex);
+      aClassifier.Perform(aPnt, aTolerance);
+      if (aClassifier.State() == TopAbs_IN)
+      {
+        Standard_Mutex::Sentry aLock(Mutex.get());
+        *InnerSol = Standard_True;
+        *DistRef  = 0.;
+        *IsDone   = Standard_True;
+        BRepExtrema_SolutionElem aSolElem(0, aPnt, BRepExtrema_IsVertex, aVertex);
+        SolutionsShape1->Append(aSolElem);
+        SolutionsShape2->Append(aSolElem);
+        break;
+      }
+    }
+  }
+
+  NCollection_Array1<NCollection_Array1<TopoDS_Shape> >* ArrayOfArrays;
+  BRepExtrema_SeqOfSolution*                 SolutionsShape1;
+  BRepExtrema_SeqOfSolution*                 SolutionsShape2;
+  TopoDS_Shape                               Shape;
+  Message_ProgressScope                      Scope;
+  NCollection_Array1<Message_ProgressRange>  Ranges;
+  Standard_Real*                             DistRef;
+  volatile Standard_Boolean*                 InnerSol;
+  volatile Standard_Boolean*                 IsDone;
+  Handle(Standard_HMutex)                    Mutex;
+};
+
 //=======================================================================
 //function : SolidTreatment
 //purpose  : 
 //=======================================================================
 Standard_Boolean BRepExtrema_DistShapeShape::SolidTreatment(const TopoDS_Shape& theShape,
-                                                            const TopTools_IndexedMapOfShape& theMap,
+                                                            const TopTools_IndexedMapOfShape& theVertexMap,
                                                             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)
+  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)
   {
-    aScope.Next();
-    if (!aScope.More())
-    {
-      return Standard_False;
-    }
-    const TopoDS_Vertex& aVertex = TopoDS::Vertex(theMap(i));
-    const gp_Pnt& aPnt = BRep_Tool::Pnt(aVertex);
-    aClassifier.Perform(aPnt, aTolerance);
-    if (aClassifier.State() == TopAbs_IN)
+    aTaskSize = aMinTaskSize;
+    aNbTasks = (Standard_Integer) Ceiling((double) aMapSize / aTaskSize);
+  }
+
+  NCollection_Array1< NCollection_Array1<TopoDS_Shape> > 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)
     {
-      myInnerSol = Standard_True;
-      myDistRef = 0.;
-      myIsDone = Standard_True;
-      BRepExtrema_SolutionElem Sol(0, aPnt, BRepExtrema_IsVertex, aVertex);
-      mySolutionsShape1.Append(Sol);
-      mySolutionsShape2.Append(Sol);
-      break;
+      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);
+  }
+
+  Message_ProgressScope aScope(theRange, "Solid treatment", aNbTasks);
+  TreatmentFunctor aFunctor(&anArrayOfArray, aScope.Next());
+  aFunctor.SolutionsShape1 = &mySolutionsShape1;
+  aFunctor.SolutionsShape2 = &mySolutionsShape2;
+  aFunctor.Shape = theShape;
+  aFunctor.DistRef = &myDistRef;
+  aFunctor.InnerSol = &myInnerSol;
+  aFunctor.IsDone = &myIsDone;
+  if (myIsMultiThread)
+  {
+    aFunctor.Mutex.reset(new Standard_HMutex());
+  }
+
+  OSD_Parallel::For(0, aNbTasks, aFunctor, !myIsMultiThread);
+
+  if (!aScope.More())
+  {
+    return Standard_False;
   }
   return Standard_True;
 }
@@ -394,22 +846,22 @@ Standard_Boolean BRepExtrema_DistShapeShape::SolidTreatment(const TopoDS_Shape&
 
 Standard_Boolean BRepExtrema_DistShapeShape::Perform(const Message_ProgressRange& theRange)
 {
-  myIsDone=Standard_False;
-  myInnerSol=Standard_False;
+  myIsDone = Standard_False;
+  myInnerSol = Standard_False;
   mySolutionsShape1.Clear();
   mySolutionsShape2.Clear();
 
-  if ( myShape1.IsNull() || myShape2.IsNull() )
+  if (myShape1.IsNull() || myShape2.IsNull())
     return Standard_False;
 
   // Treatment of solids
   Standard_Boolean anIsSolid1 = (myShape1.ShapeType() == TopAbs_SOLID) ||
-                                (myShape1.ShapeType() == TopAbs_COMPSOLID);
+    (myShape1.ShapeType() == TopAbs_COMPSOLID);
   Standard_Boolean anIsSolid2 = (myShape2.ShapeType() == TopAbs_SOLID) ||
-                                (myShape2.ShapeType() == TopAbs_COMPSOLID);
+    (myShape2.ShapeType() == TopAbs_COMPSOLID);
   Standard_Integer aRootStepsNum = 9; // By num of DistanceMapMap calls
-  aRootStepsNum = anIsSolid1 ? aRootStepsNum+1 : aRootStepsNum;
-  aRootStepsNum = anIsSolid2 ? aRootStepsNum+1 : aRootStepsNum;
+  aRootStepsNum = anIsSolid1 ? aRootStepsNum + 1 : aRootStepsNum;
+  aRootStepsNum = anIsSolid2 ? aRootStepsNum + 1 : aRootStepsNum;
   Message_ProgressScope aRootScope(theRange, "calculating distance", aRootStepsNum);
 
   if (anIsSolid1)
@@ -419,10 +871,10 @@ Standard_Boolean BRepExtrema_DistShapeShape::Perform(const Message_ProgressRange
       return Standard_False;
     }
   }
-  
+
   if (anIsSolid2 && (!myInnerSol))
   {
-    if(!SolidTreatment(myShape2, myMapV1, aRootScope.Next()))
+    if (!SolidTreatment(myShape2, myMapV1, aRootScope.Next()))
     {
       return Standard_False;
     }
@@ -432,9 +884,18 @@ Standard_Boolean BRepExtrema_DistShapeShape::Perform(const Message_ProgressRange
   {
     if (!myIsInitS1) // rebuild cached data for 1st shape
     {
-      myBV1.Clear();
-      myBE1.Clear();
-      myBF1.Clear();
+      if (!myMapV1.IsEmpty())
+      {
+        myBV1.Resize(1, myMapV1.Extent(), Standard_False);
+      }
+      if (!myMapE1.IsEmpty())
+      {
+        myBE1.Resize(1, myMapE1.Extent(), Standard_False);
+      }
+      if (!myMapF1.IsEmpty())
+      {
+        myBF1.Resize(1, myMapF1.Extent(), Standard_False);
+      }
 
       BoxCalculation (myMapV1, myBV1);
       BoxCalculation (myMapE1, myBE1);
@@ -445,9 +906,18 @@ Standard_Boolean BRepExtrema_DistShapeShape::Perform(const Message_ProgressRange
 
     if (!myIsInitS2) // rebuild cached data for 2nd shape
     {
-      myBV2.Clear();
-      myBE2.Clear();
-      myBF2.Clear();
+      if (!myMapV2.IsEmpty())
+      {
+        myBV2.Resize(1, myMapV2.Extent(), Standard_False);
+      }
+      if (!myMapE2.IsEmpty())
+      {
+        myBE2.Resize(1, myMapE2.Extent(), Standard_False);
+      }
+      if (!myMapF2.IsEmpty())
+      {
+        myBF2.Resize(1, myMapF2.Extent(), Standard_False);
+      }
 
       BoxCalculation (myMapV2, myBV2);
       BoxCalculation (myMapE2, myBE2);
@@ -458,54 +928,54 @@ Standard_Boolean BRepExtrema_DistShapeShape::Perform(const Message_ProgressRange
 
     if (myMapV1.Extent() && myMapV2.Extent())
     {
-      TopoDS_Vertex V1 = TopoDS::Vertex(myMapV1(1));
-      TopoDS_Vertex V2 = TopoDS::Vertex(myMapV2(1));
+      const TopoDS_Vertex& V1 = TopoDS::Vertex(myMapV1(1));
+      const TopoDS_Vertex& V2 = TopoDS::Vertex(myMapV2(1));
       myDistRef = DistanceInitiale(V1, V2);
     }
     else
-      myDistRef= 1.e30; //szv:!!!
+      myDistRef = 1.e30; //szv:!!!
 
-    if(!DistanceVertVert(myMapV1, myMapV2, aRootScope.Next()))
+    if (!DistanceVertVert(myMapV1, myMapV2, aRootScope.Next()))
     {
       return Standard_False;
     }
-    if(!DistanceMapMap (myMapV1, myMapE2, myBV1, myBE2, aRootScope.Next()))
+    if (!DistanceMapMap(myMapV1, myMapE2, myBV1, myBE2, aRootScope.Next()))
     {
       return Standard_False;
     }
-    if(!DistanceMapMap (myMapE1, myMapV2, myBE1, myBV2, aRootScope.Next()))
+    if (!DistanceMapMap(myMapE1, myMapV2, myBE1, myBV2, aRootScope.Next()))
     {
       return Standard_False;
     }
-    if(!DistanceMapMap (myMapV1, myMapF2, myBV1, myBF2, aRootScope.Next()))
+    if (!DistanceMapMap(myMapV1, myMapF2, myBV1, myBF2, aRootScope.Next()))
     {
       return Standard_False;
     }
-    if(!DistanceMapMap (myMapF1, myMapV2, myBF1, myBV2, aRootScope.Next()))
+    if (!DistanceMapMap(myMapF1, myMapV2, myBF1, myBV2, aRootScope.Next()))
     {
       return Standard_False;
     }
-    if(!DistanceMapMap (myMapE1, myMapE2, myBE1, myBE2, aRootScope.Next()))
+    if (!DistanceMapMap(myMapE1, myMapE2, myBE1, myBE2, aRootScope.Next()))
     {
       return Standard_False;
     }
-    if(!DistanceMapMap (myMapE1, myMapF2, myBE1, myBF2, aRootScope.Next()))
+    if (!DistanceMapMap(myMapE1, myMapF2, myBE1, myBF2, aRootScope.Next()))
     {
       return Standard_False;
     }
-    if(!DistanceMapMap (myMapF1, myMapE2, myBF1, myBE2, aRootScope.Next()))
+    if (!DistanceMapMap(myMapF1, myMapE2, myBF1, myBE2, aRootScope.Next()))
     {
       return Standard_False;
     }
 
-    if (fabs (myDistRef) > myEps)
+    if (Abs(myDistRef) > myEps)
     {
-      if(!DistanceMapMap (myMapF1, myMapF2, myBF1, myBF2, aRootScope.Next()))
+      if (!DistanceMapMap(myMapF1, myMapF2, myBF1, myBF2, aRootScope.Next()))
       {
         return Standard_False;
       }
     }
-    
+
     //  Modified by Sergey KHROMOV - Tue Mar  6 11:55:03 2001 Begin
     Standard_Integer i = 1;
     for (; i <= mySolutionsShape1.Length(); i++)
@@ -515,7 +985,7 @@ Standard_Boolean BRepExtrema_DistShapeShape::Perform(const Message_ProgressRange
         mySolutionsShape2.Remove(i);
       }
     //  Modified by Sergey KHROMOV - Tue Mar  6 11:55:04 2001 End
-    myIsDone = ( mySolutionsShape1.Length() > 0 );
+    myIsDone = (mySolutionsShape1.Length() > 0);
   }
 
   return myIsDone;
index 8b3450e..67269db 100644 (file)
@@ -14,7 +14,7 @@
 #ifndef _BRepExtrema_DistShapeShape_HeaderFile
 #define _BRepExtrema_DistShapeShape_HeaderFile
 
-#include <Bnd_SeqOfBox.hxx>
+#include <Bnd_Array1OfBox.hxx>
 #include <BRepExtrema_SeqOfSolution.hxx>
 #include <BRepExtrema_SolutionElem.hxx>
 #include <BRepExtrema_SupportType.hxx>
 #include <Standard_DefineAlloc.hxx>
 #include <TopTools_IndexedMapOfShape.hxx>
 
-//! This class  provides tools to compute minimum distance <br>
-//! between two Shapes (Compound,CompSolid, Solid, Shell, Face, Wire, Edge, Vertex). <br>
+//! This class  provides tools to compute minimum distance 
+//! between two Shapes (Compound,CompSolid, Solid, Shell, Face, Wire, Edge, Vertex).
 class BRepExtrema_DistShapeShape
 {
  public:
 
   DEFINE_STANDARD_ALLOC
 
-  //! create empty tool <br>
+  //! create empty tool
   Standard_EXPORT BRepExtrema_DistShapeShape();
-  //! computation of the minimum distance (value and pair of points) using default deflection <br>
-  //! Default value is Precision::Confusion(). <br>
+
+  //! create tool and computation of the minimum distance (value and pair of points) 
+  //! using default deflection in single thread mode. <br>
+  //! Default deflection value is Precision::Confusion(). <br>
+  //! @param Shape1 - the first shape for distance computation
+  //! @param Shape2 - the second shape for distance computation
+  //! @param F and @param A are not used in computation and are obsolete.
+  //! @param theRange - the progress indicator of algorithm
   Standard_EXPORT BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1,
                                              const TopoDS_Shape& Shape2,
                                              const Extrema_ExtFlag F = Extrema_ExtFlag_MINMAX,
                                              const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad,
                                              const Message_ProgressRange& theRange = Message_ProgressRange());
-  //! create tool and load both shapes into it <br>
+  //! create tool and computation of the minimum distance 
+  //! (value and pair of points) in single thread mode. <br>
+  //! Default deflection value is Precision::Confusion(). <br>
+  //! @param Shape1 - the first shape for distance computation
+  //! @param Shape2 - the second shape for distance computation
+  //! @param theDeflection - the presition of distance computation
+  //! @param F and @param A are not used in computation and are obsolete.
+  //! @param theRange - the progress indicator of algorithm
   Standard_EXPORT BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1,
                                              const TopoDS_Shape& Shape2,
                                              const Standard_Real theDeflection,
@@ -53,49 +66,60 @@ class BRepExtrema_DistShapeShape
                                              const Extrema_ExtAlgo A = Extrema_ExtAlgo_Grad,
                                              const Message_ProgressRange& theRange = Message_ProgressRange());
   
+  //! Sets deflection to computation of the minimum distance <br>
   void SetDeflection(const Standard_Real theDeflection)
   {
     myEps = theDeflection;
   }
+
   //! load first shape into extrema <br>
   Standard_EXPORT void LoadS1(const TopoDS_Shape& Shape1);
+
   //! load second shape into extrema <br>
   Standard_EXPORT void LoadS2(const TopoDS_Shape& Shape1);
+
   //! computation of  the minimum  distance  (value  and <br>
   //!          couple  of points). Parameter theDeflection is used <br>
   //!          to specify a maximum deviation of extreme distances <br>
   //!          from the minimum one. <br>
   //!          Returns IsDone status. <br>
-  //! theProgress - progress indicator of algorithm
+  //! theRange - the progress indicator of algorithm
   Standard_EXPORT Standard_Boolean Perform(const Message_ProgressRange& theRange = Message_ProgressRange());
+
   //! True if the minimum distance is found. <br>
   Standard_Boolean IsDone() const
   { 
     return myIsDone;
   }
+
   //! Returns the number of solutions satisfying the minimum distance. <br>
   Standard_Integer NbSolution() const
   { 
     return mySolutionsShape1.Length();
   }
+
   //! Returns the value of the minimum distance. <br>
   Standard_EXPORT Standard_Real Value() const;
+
   //! True if one of the shapes is a solid and the other shape <br>
   //! is completely or partially inside the solid. <br>
   Standard_Boolean InnerSolution() const
   { 
     return myInnerSol;
   }
+
   //! Returns the Point corresponding to the <N>th solution on the first Shape <br>
   const gp_Pnt & PointOnShape1(const Standard_Integer N) const
   { 
     return mySolutionsShape1.Value(N).Point();
   }
+
   //! Returns the Point corresponding to the <N>th solution on the second Shape <br>
   const gp_Pnt & PointOnShape2(const Standard_Integer N) const
   { 
     return mySolutionsShape2.Value(N).Point();
   }
+
   //! gives the type of the support where the Nth solution on the first shape is situated: <br>
   //!   IsVertex => the Nth solution on the first shape is a Vertex <br>
   //!   IsOnEdge => the Nth soluion on the first shape is on a Edge <br>
@@ -105,6 +129,7 @@ class BRepExtrema_DistShapeShape
   { 
     return mySolutionsShape1.Value(N).SupportKind();
   }
+
   //! gives the type of the support where the Nth solution on the second shape is situated: <br>
   //!   IsVertex => the Nth solution on the second shape is a Vertex <br>
   //!   IsOnEdge => the Nth soluion on the secondt shape is on a Edge <br>
@@ -114,44 +139,68 @@ class BRepExtrema_DistShapeShape
   { 
     return mySolutionsShape2.Value(N).SupportKind();
   }
+
   //! gives the support where the Nth solution on the first shape is situated. <br>
   //! This support can be a Vertex, an Edge or a Face. <br>
   Standard_EXPORT TopoDS_Shape SupportOnShape1(const Standard_Integer N) const;
+
   //! gives the support where the Nth solution on the second shape is situated. <br>
   //! This support can be a Vertex, an Edge or a Face. <br>
   Standard_EXPORT TopoDS_Shape SupportOnShape2(const Standard_Integer N) const;
+
   //! gives the corresponding parameter t if the Nth solution <br>
   //! is situated on an Edge of the first shape <br>
   Standard_EXPORT void ParOnEdgeS1(const Standard_Integer N,Standard_Real& t) const;
+
   //! gives the corresponding parameter t if the Nth solution <br>
   //! is situated on an Edge of the first shape <br>
   Standard_EXPORT void ParOnEdgeS2(const Standard_Integer N,Standard_Real& t) const;
+
   //! gives the corresponding parameters (U,V) if the Nth solution <br>
   //! is situated on an face of the first shape <br>
   Standard_EXPORT void ParOnFaceS1(const Standard_Integer N,Standard_Real& u,Standard_Real& v) const;
+
   //! gives the corresponding parameters (U,V) if the Nth solution <br>
   //! is situated on an Face of the second shape <br>
   Standard_EXPORT void ParOnFaceS2(const Standard_Integer N,Standard_Real& u,Standard_Real& v) const;
+
   //! Prints on the stream o information on the current state of the object. <br>
   Standard_EXPORT void Dump(Standard_OStream& o) const;
 
+  //! Sets unused parameter
+  //! Obsolete 
   void SetFlag(const Extrema_ExtFlag F)
   {
     myFlag = F;
   }
 
+  //! Sets unused parameter
+  //! Obsolete 
   void SetAlgo(const Extrema_ExtAlgo A)
   {
     myAlgo = A;
   }
 
+  //! If isMultiThread == Standard_True then computation will be performed in parallel.
+  void SetMultiThread(Standard_Boolean theIsMultiThread)
+  {
+    myIsMultiThread = theIsMultiThread;
+  }
+
+  //! Returns Standard_True then computation will be performed in parallel
+  //! Default value is Standard_False
+  Standard_Boolean IsMultiThread() const
+  {
+    return myIsMultiThread;
+  }
+
 private:
 
   //! computes the minimum distance between two maps of shapes (Face,Edge,Vertex) <br>
   Standard_Boolean DistanceMapMap(const TopTools_IndexedMapOfShape& Map1,
                                   const TopTools_IndexedMapOfShape& Map2,
-                                  const Bnd_SeqOfBox&               LBox1,
-                                  const Bnd_SeqOfBox&               LBox2,
+                                  const Bnd_Array1OfBox&            LBox1,
+                                  const Bnd_Array1OfBox&            LBox2,
                                   const Message_ProgressRange&      theRange);
 
   //! computes the minimum distance between two maps of vertices <br>
@@ -183,12 +232,13 @@ private:
   Standard_Boolean myIsInitS2;
   Extrema_ExtFlag myFlag;
   Extrema_ExtAlgo myAlgo;
-  Bnd_SeqOfBox myBV1;
-  Bnd_SeqOfBox myBV2;
-  Bnd_SeqOfBox myBE1;
-  Bnd_SeqOfBox myBE2;
-  Bnd_SeqOfBox myBF1;
-  Bnd_SeqOfBox myBF2;
+  Bnd_Array1OfBox myBV1;
+  Bnd_Array1OfBox myBV2;
+  Bnd_Array1OfBox myBE1;
+  Bnd_Array1OfBox myBE2;
+  Bnd_Array1OfBox myBF1;
+  Bnd_Array1OfBox myBF2;
+  Standard_Boolean myIsMultiThread;
 };
 
 #endif
index 61773dd..7cbd701 100644 (file)
 //------------------------------------------------------------------------------
 static Standard_Boolean TRI_SOLUTION (const BRepExtrema_SeqOfSolution& SeqSol, const gp_Pnt& Pt)
 {
-  const Standard_Integer Nbsol = SeqSol.Length();
-  for (Standard_Integer i = 1; i <= Nbsol; i++)
+  for (BRepExtrema_SeqOfSolution::iterator anIt = SeqSol.begin(); anIt != SeqSol.end(); anIt++)
   {
-    const Standard_Real dst = SeqSol.Value(i).Point().Distance(Pt);
-    if (dst <= Precision::Confusion()) return Standard_False;
+    const Standard_Real dst = anIt->Point().Distance(Pt);
+    if (dst <= Precision::Confusion())
+    {
+      return Standard_False;
+    }
   }
   return Standard_True;
 }  
@@ -83,15 +85,16 @@ static void MIN_SOLUTION (const BRepExtrema_SeqOfSolution& SeqSol1,
                           BRepExtrema_SeqOfSolution& seqSol1,
                           BRepExtrema_SeqOfSolution& seqSol2)
 {
-  const Standard_Integer nbSol = SeqSol1.Length();
-  for (Standard_Integer i = 1; i <= nbSol; i++)
+  for (BRepExtrema_SeqOfSolution::iterator anIt1 = SeqSol1.begin(), anIt2 = SeqSol2.begin(); 
+       anIt1 != SeqSol1.end(); 
+       anIt1++, anIt2++)
   {
-    const Standard_Real dst1 = SeqSol1.Value(i).Dist();
+    const Standard_Real dst1 = anIt1->Dist();
     if (fabs(dst1 - DstRef) < Eps)
-       {         
-      seqSol1.Append(SeqSol1.Value(i));
-      seqSol2.Append(SeqSol2.Value(i));
-       }
+         {       
+      seqSol1.Append(*anIt1);
+      seqSol2.Append(*anIt2);
+         }
   }
 }
 
index 0fa4432..3be19ae 100644 (file)
@@ -64,19 +64,45 @@ 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)
+  Standard_Integer anIndex = 4;
+  if (n >= 5 && a[4][0] != '-')
+  {
     aDeflection = Draw::Atof(a[4]);
+    anIndex++;
+  }
+
+  Standard_Boolean isMultiThread = Standard_False;
+  for (Standard_Integer anI = anIndex; anI < n; anI++)
+  {
+    TCollection_AsciiString anArg(a[anI]);
+    anArg.LowerCase();
+    if (anArg == "-parallel")
+    {
+      isMultiThread = 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());
+  BRepExtrema_DistShapeShape dst;
+  dst.LoadS1(S1);
+  dst.LoadS2(S2);
+  dst.SetDeflection(aDeflection);
+  dst.SetMultiThread(isMultiThread);
+  dst.Perform(aProgress->Start());
 
   if (dst.IsDone()) 
   { 
@@ -412,7 +438,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);
diff --git a/tests/perf/modalg/bug32539_1 b/tests/perf/modalg/bug32539_1
new file mode 100644 (file)
index 0000000..6c7a433
--- /dev/null
@@ -0,0 +1,61 @@
+puts "=========="
+puts "0032539: Modeling Algorithms - Parallelize BRepExtrema_DistShapeShape algorithm"
+puts "=========="
+puts ""
+
+# prepare
+pload XDE OCAF
+XOpen [locate_data_file bug32539_1.xbf] XB
+XGetShape s1 XB 0:1:1:2
+XGetShape s2 XB 0:1:1:4
+Close XB
+btranslate s1 0 0 60
+brotate s2 0 0 0 0 0 1 90
+
+# multi-thread
+dchrono p reset; dchrono p start;
+set pres [distmini res s1 s2 -parallel]
+dchrono p stop;
+regexp {Elapsed time: +([-0-9.+eE]+) Hours +([-0-9.+eE]+) Minutes +([-0-9.+eE]+) Seconds} [dchrono p show] full p_Hours p_Minutes p_Seconds
+set p_Time [expr ${p_Hours}*60.*60. + ${p_Minutes}*60. + ${p_Seconds} ]
+puts "multithreaded time: $p_Time"
+set pdist [dval res_val]
+
+vclear
+vclose ALL
+vinit v1/v1
+vdisplay -dispMode 1 s1 s2 res res2 res3 res4
+vfit
+checkview -screenshot -3d -path ${imagedir}/${test_image}_multi.png
+
+#single-thread
+dchrono s reset; dchrono s start;
+set cres [distmini res s1 s2]
+dchrono s stop;
+regexp {Elapsed time: +([-0-9.+eE]+) Hours +([-0-9.+eE]+) Minutes +([-0-9.+eE]+) Seconds} [dchrono s show] full s_Hours s_Minutes s_Seconds
+set s_Time [expr ${s_Hours}*60.*60. + ${s_Minutes}*60. + ${s_Seconds} ]
+puts "single-threaded time: $s_Time"  
+
+set sdist [dval res_val]
+
+vclear
+vclose ALL
+vinit v2/v2
+vdisplay -dispMode 1 s1 s2 res res2 res3 res4
+vfit
+checkview -screenshot -3d -path ${imagedir}/${test_image}_single.png
+
+# compare
+set ratio [expr ${s_Time}/${p_Time} ]
+puts "acceleration in multi-threaded work: $ratio" 
+
+if {[string compare $cres $pres] != 0} {
+  puts "Error: different result between single-thread and multi-thread mode"
+}
+
+if {[expr abs(${sdist} - ${pdist})] > 1E-13} {
+  puts "Error: different distance between single-thread and multi-thread mode"
+}
+
+
diff --git a/tests/perf/modalg/bug32539_2 b/tests/perf/modalg/bug32539_2
new file mode 100644 (file)
index 0000000..6d9edaf
--- /dev/null
@@ -0,0 +1,54 @@
+puts "=========="
+puts "0032539: Modeling Algorithms - Parallelize BRepExtrema_DistShapeShape algorithm"
+puts "=========="
+puts ""
+
+# prepare
+restore [locate_data_file 5000-12.brep] s1
+restore [locate_data_file BPLSEITLI.brep] s2
+
+# multi-thread
+dchrono p reset; dchrono p start;
+set pres [distmini res s1 s2 -parallel]
+dchrono p stop;
+regexp {Elapsed time: +([-0-9.+eE]+) Hours +([-0-9.+eE]+) Minutes +([-0-9.+eE]+) Seconds} [dchrono p show] full p_Hours p_Minutes p_Seconds
+set p_Time [expr ${p_Hours}*60.*60. + ${p_Minutes}*60. + ${p_Seconds} ]
+puts "multithreaded time: $p_Time"
+set pdist [dval res_val]
+
+vclear
+vclose ALL
+vinit v1/v1
+vdisplay -dispMode 1 s1 s2 res
+vzoom 2
+checkview -screenshot -3d -path ${imagedir}/${test_image}_multi.png
+
+#single-thread
+dchrono s reset; dchrono s start;
+set cres [distmini res s1 s2]
+dchrono s stop;
+regexp {Elapsed time: +([-0-9.+eE]+) Hours +([-0-9.+eE]+) Minutes +([-0-9.+eE]+) Seconds} [dchrono s show] full s_Hours s_Minutes s_Seconds
+set s_Time [expr ${s_Hours}*60.*60. + ${s_Minutes}*60. + ${s_Seconds} ]
+puts "single-threaded time: $s_Time"  
+
+set sdist [dval res_val]
+
+vclear
+vclose ALL
+vinit v2/v2
+vdisplay -dispMode 1 s1 s2 res
+vzoom 2
+checkview -screenshot -3d -path ${imagedir}/${test_image}_single.png
+
+# compare
+set ratio [expr ${s_Time}/${p_Time} ]
+puts "acceleration in multi-threaded work: $ratio" 
+
+if {[string compare $cres $pres] != 0} {
+  puts "Error: different result between single-thread and multi-thread mode"
+}
+
+if {[expr abs(${sdist} - ${pdist})] > 1E-13} {
+  puts "Error: different distance between single-thread and multi-thread mode"
+}