From 96d53eab0f1af886f2746733d302752ae178b2cd Mon Sep 17 00:00:00 2001 From: emv Date: Wed, 17 Apr 2019 17:29:02 +0300 Subject: [PATCH] 0030655: Modeling Data - Provide interfaces for selection of the elements from BVH tree Provide the easy to use interfaces for selection of the elements from BVH tree. The selection rules should be implemented in the selector class derived from *BVH_BoxSet<>::Selector* or in *BVH_BoxSet<>::PairSelector* in Reject/Accept methods. The *BVH_BoxSet<>::Selector* is used for selection of the elements from the tree. The *BVH_BoxSet<>::PairSelector* is used for selection of the pairs of elements from two BVH trees. Auxiliary changes: - Two methods BVH_Box::IsOut(OtherBox) and BVH_Box::IsOut(Point) have been added; - Added methods for conversion of Bnd boxes to BVH boxes Test case for the issue. (cherry picked from commit 9175060417729936736392d52444e8f751bcf986) # Conflicts: # src/BVH/BVH_Box.hxx # tests/lowalgos/grids.list --- src/BVH/BVH_Box.hxx | 33 ++++ src/BVH/BVH_BoxSet.hxx | 378 ++++++++++++++++++++++++++++++++++++ src/BVH/FILES | 1 + src/Bnd/Bnd_Tools.hxx | 47 +++++ src/Bnd/FILES | 1 + src/QABugs/FILES | 1 + src/QABugs/QABugs.cxx | 1 + src/QABugs/QABugs.hxx | 1 + src/QABugs/QABugs_BVH.cxx | 297 ++++++++++++++++++++++++++++ tests/lowalgos/bvh/bug30655 | 38 ++++ tests/lowalgos/grids.list | 3 +- 11 files changed, 800 insertions(+), 1 deletion(-) create mode 100644 src/BVH/BVH_BoxSet.hxx create mode 100644 src/Bnd/Bnd_Tools.hxx create mode 100644 src/QABugs/QABugs_BVH.cxx create mode 100644 tests/lowalgos/bvh/bug30655 diff --git a/src/BVH/BVH_Box.hxx b/src/BVH/BVH_Box.hxx index 4e7dfc94e7..0ea93fe9b9 100644 --- a/src/BVH/BVH_Box.hxx +++ b/src/BVH/BVH_Box.hxx @@ -121,6 +121,39 @@ public: //DUMP_VALUES (OS, "CornerMin", BVH::ToString (CornerMax())); } +public: + + //! Checks if the Box is out of the other box. + Standard_Boolean IsOut (const BVH_Box& theOther) const + { + if (!IsValid() || !theOther.IsValid()) + return Standard_True; + + for (int i = 0; i < N; ++i) + { + if (myMinPoint[i] > theOther.myMaxPoint[i] || + myMaxPoint[i] < theOther.myMinPoint[i]) + return Standard_True; + } + return Standard_False; + } + + //! Checks if the Point is out of the box. + Standard_Boolean IsOut (const BVH_VecNt& thePoint) const + { + if (!IsValid()) + return Standard_True; + + for (int i = 0; i < N; ++i) + { + if (thePoint[i] < myMinPoint[i] || + thePoint[i] > myMaxPoint[i]) + return Standard_True; + } + return Standard_False; + } + + protected: BVH_VecNt myMinPoint; //!< Minimum point of bounding box diff --git a/src/BVH/BVH_BoxSet.hxx b/src/BVH/BVH_BoxSet.hxx new file mode 100644 index 0000000000..a929477ecc --- /dev/null +++ b/src/BVH/BVH_BoxSet.hxx @@ -0,0 +1,378 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 17/04/2019 +// Copyright (c) 2019 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#ifndef _BVH_BoxSet_Header +#define _BVH_BoxSet_Header + +#include +#include +#include + +//! Abstract class implementing the set of elements with bounding boxes +//! organized with bounding volume hierarchy (BVH). +//! +//! The elements and their boxes are always synchronized which allows +//! implementing convenient methods for elements selection by tree descend. +//! +//! The selection/rejection rules should be implemented in the derived Selector +//! class in the Accept/Reject methods. +//! The Reject() method is performed on the nodes (both inner and outer) to check +//! and reject the whole branches of the tree. It operates with boxes and usually +//! is simple enough. +//! The Accept() method on the other hand is applied to the leafs only (performs +//! the leaf-node operation). It operates with elements on which boxes are built +//! and implements the logic of the operation. +//! +//! Two selection methods are implemented - single tree descend used for elements selections +//! and parallel descend of two BVH trees for selections of pairs of elements of these trees. +//! +//! Here is the example of usage of the algorithm. +//! It implements the selection of pairs of sub-shapes of two shapes with +//! interfering bounding boxes. It uses the Linear builder for BVH construction: +//! ~~~~ +//! // Selector implementing the Rejection/Selection rules +//! class PairShapesSelector : public BVH_BoxSet ::PairSelector +//! { +//! public: +//! // Constructor +//! PairShapesSelector() {} +//! +//! // Returns the selected pairs +//! const NCollection_List >& Pairs () const { return myPairs; } +//! +//! protected: +//! +//! // Defines the rules for node rejection +//! virtual Standard_Boolean Reject (const BVH_Box & theBox1, +//! const BVH_Box & theBox2) const Standard_OVERRIDE +//! { +//! return theBox1.IsOut (theBox2); +//! } +//! +//! // Defines the rules for leaf acceptance +//! virtual Standard_Boolean Accept (const TopoDS_Shape& theShape1, const TopoDS_Shape& theShape2) Standard_OVERRIDE +//! { +//! myPairs.Append (std::pair (theShape1, theShape2)); +//! return Standard_True; +//! } +//! +//! protected: +//! +//! // Selected pairs +//! NCollection_List > myPairs; +//! }; +//! +//! TopoDS_Shape aShape[2]; +//! aShape[0] = ...; // First shape for BVH construction on its sub-shapes +//! aShape[1] = ...; // Second shape for BVH construction on its sub-shapes +//! +//! // Define BVH Builder +//! opencascade::handle > aLBuilder = new BVH_LinearBuilder (); +//! +//! // Create the ShapeSet +//! opencascade::handle > aShapeBoxSet[2]; +//! +//! for (int i = 0; i < 2; ++i) +//! { +//! aShapeBoxSet[i] = new BVH_BoxSet (aLBuilder); +//! +//! // Add elements with boxes into set +//! TopTools_IndexedMapOfShape aMapShapes; +//! TopExp::MapShapes (aShape[i], TopAbs_VERTEX, aMapShapes); +//! TopExp::MapShapes (aShape[i], TopAbs_EDGE, aMapShapes); +//! TopExp::MapShapes (aShape[i], TopAbs_FACE, aMapShapes); +//! +//! for (Standard_Integer iS = 1; iS <= aMapShapes.Extent (); ++iS) +//! { +//! const TopoDS_Shape& aS = aMapShapes (iS); +//! Bnd_Box aSBox; +//! BRepBndLib::Add (aS, aSBox); +//! aShapeBoxSet[i]->Add (aS, Bnd_Tools::Bnd2BVH (aSBox)); +//! } +//! // Build BVH +//! aShapeBoxSet[i]->Build(); +//! } +//! +//! // Initialize selector +//! PairShapesSelector aSelector; +//! // Select the pairs of elements +//! aShapeBoxSet[0]->Select (aShapeBoxSet[1], aSelector); +//! +//! const NCollection_List >& aPairs = aSelector.Pairs (); +//! ~~~~ +//! \tparam NumType Numeric data type +//! \tparam Dimension Vector dimension +//! \tparam DataType Type of elements on which the boxes are built +template +class BVH_BoxSet : public BVH_PrimitiveSet +{ +public: //! @name Constructors + + //! Empty constructor for use the default BVH_Builder + BVH_BoxSet() + : BVH_PrimitiveSet () + { + } + + //! Constructor for usage the custom BVH builder + BVH_BoxSet (const opencascade::handle >& theBuilder) + : BVH_PrimitiveSet (theBuilder) + { + } + +public: //! @name Adding elements in BVH + + //! Adds the element into BVH + void Add (const DataType& theElement, const BVH_Box& theBox) + { + myElements.Append (theElement); + myBoxes.Append (theBox); + + BVH_Object::myIsDirty = Standard_True; + } + +public: //! @name Clearing the elements + + //! Clears the vectors of elements and boxes + void Clear() + { + myElements.Clear(); + myBoxes.Clear(); + } + +public: //! @name BVH construction + + //! Constructs the BVH + void Build() + { + BVH_PrimitiveSet::Update(); + } + +public: //! @name Necessary overrides for BVH construction + + //! Make inherited method Box() visible to avoid CLang warning + using BVH_PrimitiveSet ::Box; + + //! Returns the bounding box with the given index (starting at 0). + BVH_Box Box (const Standard_Integer theIndex) const Standard_OVERRIDE + { + return myBoxes (theIndex); + } + + //! Returns centroid position along specified axis (starting at 0). + Standard_Real Center (const Standard_Integer theIndex, + const Standard_Integer theAxis) const Standard_OVERRIDE + { + return myBoxes (theIndex).Center().GetData()[theAxis]; + } + + //! Returns the number of boxes. + Standard_Integer Size() const Standard_OVERRIDE + { + return myBoxes.Length(); + } + + //! Swaps indices of two specified boxes. + void Swap (const Standard_Integer theIndex1, + const Standard_Integer theIndex2) Standard_OVERRIDE + { + std::swap (myBoxes (theIndex1), myBoxes (theIndex2)); + std::swap (myElements (theIndex1), myElements (theIndex2)); + } + +public: //! @name Selectors + + //! Abstract Elements Selector. + //! Defines the rules for nodes rejection/acceptance. + class Selector + { + public: //! @name Constructor + + //! Constructor + Selector() {} + + //! Destructor + virtual ~Selector () {} + + public: //! @name Rules for Accept/Reject + + //! Rejection of the node by bounding box + virtual Standard_Boolean Reject (const BVH_Box&) const = 0; + + //! Leaf acceptance + virtual Standard_Boolean Accept (const DataType&) = 0; + }; + + //! Abstract Pair elements Selector. + //! Defines the rules for rejection/acceptance of the pair of nodes of two BVH trees + class PairSelector + { + public: //! @name Constructor + + //! Constructor + PairSelector() {} + + //! Destructor + virtual ~PairSelector () {} + + public: //! @name Rules for Accept/Reject + + //! Rejection of the node by bounding boxes + virtual Standard_Boolean Reject (const BVH_Box& theBox1, + const BVH_Box& theBox2) const = 0; + + //! Leaf acceptance + virtual Standard_Boolean Accept (const DataType&, const DataType&) = 0; + }; + +public: //! @name Selection of the elements by tree descend + + //! Selection of the elements from the BVH tree by the + //! rules defined in Selector. + Standard_Integer Select (Selector& theSelector); + + //! Selection of the pairs of elements of two BVH trees by the + //! rules defined in Selector. + Standard_Integer Select (const opencascade::handle >& theOther, + PairSelector& theSelector); + +protected: //! @name Fields + + NCollection_Vector > myBoxes; //!< Bounding boxes for the elements + NCollection_Vector myElements; //!< Elements +}; + + +//======================================================================= +//function : Select +//purpose : Selection from the tree by tree descend +//======================================================================= +template +Standard_Integer BVH_BoxSet ::Select (Selector& theSelector) +{ + Standard_Integer aNbAccepted = 0; + + const opencascade::handle >& aBVH = this->myBVH; + if (aBVH.IsNull()) + return aNbAccepted; + + const BVH_Array4i& aBVHNodes = aBVH->NodeInfoBuffer(); + + NCollection_List aNodes; + aNodes.Append (0); + + // Starting with the root of the tree descend to the leafs. + for (NCollection_List ::Iterator it (aNodes); it.More(); aNodes.Remove (it)) + { + int iNode = it.Value(); + BVH_Box aBox (aBVH->MinPoint (iNode), aBVH->MaxPoint (iNode)); + if (theSelector.Reject (aBox)) + continue; + + const BVH_Vec4i& aNode = aBVHNodes[iNode]; + if (aNode.x() == 0) + { + // Inner node - add its children for treatment + aNodes.Append (aNode.y()); + aNodes.Append (aNode.z()); + } + else + { + // Outer node - apply the leaf node operation to each element + for (Standard_Integer iN = aNode.y(); iN <= aNode.z(); ++iN) + { + if (!theSelector.Reject (myBoxes (iN)) && theSelector.Accept (myElements (iN))) + ++aNbAccepted; + } + } + } + return aNbAccepted; +} + +//======================================================================= +//function : Select +//purpose : Selection from the tree by parallel tree descend +//======================================================================= +template +Standard_Integer BVH_BoxSet ::Select + (const opencascade::handle >& theOther, + PairSelector& theSelector) +{ + Standard_Integer aNbAccepted = 0; + if (theOther.IsNull()) + return aNbAccepted; + + const opencascade::handle >& aBVH1 = this->myBVH; + const opencascade::handle >& aBVH2 = theOther->myBVH; + if (aBVH1.IsNull() || aBVH2.IsNull()) + return aNbAccepted; + + const BVH_Array4i& aBVHNodes1 = aBVH1->NodeInfoBuffer(); + const BVH_Array4i& aBVHNodes2 = aBVH2->NodeInfoBuffer(); + + NCollection_List > aNodes; + aNodes.Append (std::pair (0, 0)); + + // Starting with the roots of the trees descend to the leafs. + for (NCollection_List >::Iterator it (aNodes); it.More(); aNodes.Remove (it)) + { + std::pair aPair = it.Value(); + + BVH_Box aBox1 (aBVH1->MinPoint (aPair.first), aBVH1->MaxPoint (aPair.first)); + BVH_Box aBox2 (aBVH2->MinPoint (aPair.second), aBVH2->MaxPoint (aPair.second)); + if (theSelector.Reject (aBox1, aBox2)) + continue; + + const BVH_Vec4i& aNode1 = aBVHNodes1[aPair.first]; + const BVH_Vec4i& aNode2 = aBVHNodes2[aPair.second]; + + if (aNode1.x() == 0 && aNode2.x() == 0) + { + // Inner/Inner + aNodes.Append (std::pair (aNode1.y(), aNode2.y())); + aNodes.Append (std::pair (aNode1.y(), aNode2.z())); + aNodes.Append (std::pair (aNode1.z(), aNode2.y())); + aNodes.Append (std::pair (aNode1.z(), aNode2.z())); + } + else if (aNode1.x() == 0) + { + // Inner/Outer + aNodes.Append (std::pair (aNode1.y(), aPair.second)); + aNodes.Append (std::pair (aNode1.z(), aPair.second)); + } + else if (aNode2.x() == 0) + { + // Outer/Inner + aNodes.Append (std::pair (aPair.first, aNode2.y())); + aNodes.Append (std::pair (aPair.first, aNode2.z())); + } + else + { + // Outer/Outer + for (Standard_Integer iN1 = aNode1.y(); iN1 <= aNode1.z(); ++iN1) + { + for (Standard_Integer iN2 = aNode2.y (); iN2 <= aNode2.z (); ++iN2) + { + if (!theSelector.Reject (myBoxes (iN1), theOther->myBoxes (iN2)) && + theSelector.Accept (myElements (iN1), theOther->myElements (iN2))) + ++aNbAccepted; + } + } + } + } + return aNbAccepted; +} + +#endif // _BVH_BoxSet_Header diff --git a/src/BVH/FILES b/src/BVH/FILES index a563d1f113..3d9a1d69e0 100644 --- a/src/BVH/FILES +++ b/src/BVH/FILES @@ -1,6 +1,7 @@ BVH.cxx BVH_BinnedBuilder.hxx BVH_Box.hxx +BVH_BoxSet.hxx BVH_Builder.hxx BVH_BuildQueue.hxx BVH_BuildQueue.cxx diff --git a/src/Bnd/Bnd_Tools.hxx b/src/Bnd/Bnd_Tools.hxx new file mode 100644 index 0000000000..db0b0dfecf --- /dev/null +++ b/src/Bnd/Bnd_Tools.hxx @@ -0,0 +1,47 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 17/04/2019 +// Copyright (c) 2019 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#ifndef _Bnd_Tools_Header +#define _Bnd_Tools_Header + +#include +#include +#include + +//! Defines a set of static methods operating with bounding boxes +class Bnd_Tools +{ +public: //! @name Bnd_Box to BVH_Box conversion + + //! Converts the given Bnd_Box2d to BVH_Box + static BVH_Box Bnd2BVH (const Bnd_Box2d& theBox) + { + Standard_Real aXMin, aYMin, aXMax, aYMax; + theBox.Get (aXMin, aYMin, aXMax, aYMax); + return BVH_Box (BVH_Vec2d (aXMin, aYMin), + BVH_Vec2d (aXMax, aYMax)); + } + + //! Converts the given Bnd_Box to BVH_Box + static BVH_Box Bnd2BVH (const Bnd_Box& theBox) + { + Standard_Real aXMin, aYMin, aZMin, aXMax, aYMax, aZMax; + theBox.Get (aXMin, aYMin, aZMin, aXMax, aYMax, aZMax); + return BVH_Box (BVH_Vec3d (aXMin, aYMin, aZMin), + BVH_Vec3d (aXMax, aYMax, aZMax)); + } +}; + +#endif // _Bnd_Tools_Header diff --git a/src/Bnd/FILES b/src/Bnd/FILES index 1e88fce03d..84d07163db 100644 --- a/src/Bnd/FILES +++ b/src/Bnd/FILES @@ -32,3 +32,4 @@ Bnd_SeqOfBox.hxx Bnd_Sphere.cxx Bnd_Sphere.hxx Bnd_Sphere.lxx +Bnd_Tools.hxx \ No newline at end of file diff --git a/src/QABugs/FILES b/src/QABugs/FILES index 7e13b24803..50403e600f 100644 --- a/src/QABugs/FILES +++ b/src/QABugs/FILES @@ -20,5 +20,6 @@ QABugs_17.cxx QABugs_18.cxx QABugs_19.cxx QABugs_20.cxx +QABugs_BVH.cxx QABugs_PresentableObject.cxx QABugs_PresentableObject.hxx diff --git a/src/QABugs/QABugs.cxx b/src/QABugs/QABugs.cxx index 9449d71000..14b9ad0126 100644 --- a/src/QABugs/QABugs.cxx +++ b/src/QABugs/QABugs.cxx @@ -36,6 +36,7 @@ void QABugs::Commands(Draw_Interpretor& theCommands) { QABugs::Commands_18(theCommands); QABugs::Commands_19(theCommands); QABugs::Commands_20(theCommands); + QABugs::Commands_BVH(theCommands); return; } diff --git a/src/QABugs/QABugs.hxx b/src/QABugs/QABugs.hxx index bfd1a989cb..7b5095f47a 100644 --- a/src/QABugs/QABugs.hxx +++ b/src/QABugs/QABugs.hxx @@ -75,6 +75,7 @@ public: Standard_EXPORT static void Commands_20 (Draw_Interpretor& DI); + Standard_EXPORT static void Commands_BVH (Draw_Interpretor& DI); protected: diff --git a/src/QABugs/QABugs_BVH.cxx b/src/QABugs/QABugs_BVH.cxx new file mode 100644 index 0000000000..589c136ff6 --- /dev/null +++ b/src/QABugs/QABugs_BVH.cxx @@ -0,0 +1,297 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 17/04/2019 +// Copyright (c) 2019 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#include + +#include +#include + +#include + +#include + +#include +#include +#include + +#include + +#include + +#include +#include + +#include + +//======================================================================= +//function : ShapeSelector +//purpose : Implement the simplest shape's selector +//======================================================================= +class ShapeSelector : public BVH_BoxSet ::Selector +{ +public: + //! Constructor + ShapeSelector() {} + + //! Sets the Box for selection + void SetBox (const Bnd_Box& theBox) + { + myBox = Bnd_Tools::Bnd2BVH (theBox); + } + + //! Returns the selected shapes + const NCollection_List& Shapes () const { return myShapes; } + +public: + + //! Defines the rules for node rejection + virtual Standard_Boolean Reject (const BVH_Box & theBox) const Standard_OVERRIDE + { + return myBox.IsOut (theBox); + } + + //! Defines the rules for leaf acceptance + virtual Standard_Boolean Accept (const TopoDS_Shape& theShape) Standard_OVERRIDE + { + myShapes.Append (theShape); + return Standard_True; + } + +protected: + + BVH_Box myBox; //!< Selection box + NCollection_List myShapes; //!< Selected shapes +}; + +//======================================================================= +//function : QABVH_ShapeSelect +//purpose : Test the work of BVH on the simple example of shapes selection +//======================================================================= +static Standard_Integer QABVH_ShapeSelect (Draw_Interpretor& theDI, + Standard_Integer theArgc, + const char** theArgv) +{ + if (theArgc != 4) + { + theDI.PrintHelp (theArgv[0]); + return 1; + } + + // Get the shape to add its sub-shapes into BVH + TopoDS_Shape aShape = DBRep::Get (theArgv [2]); + if (aShape.IsNull()) + { + std::cout << theArgv[2] << " does not exist" << std::endl; + return 1; + } + + // Get the shape to get the Box for selection + TopoDS_Shape aBShape = DBRep::Get (theArgv [3]); + if (aBShape.IsNull()) + { + std::cout << theArgv[3] << " does not exist" << std::endl; + return 1; + } + + // Define BVH Builder + opencascade::handle > aLBuilder = + new BVH_LinearBuilder (); + + // Create the ShapeSet + opencascade::handle > aShapeBoxSet = + new BVH_BoxSet (aLBuilder); + + // Add elements into BVH + + // Map the shape + TopTools_IndexedMapOfShape aMapShapes; + TopExp::MapShapes (aShape, TopAbs_VERTEX, aMapShapes); + TopExp::MapShapes (aShape, TopAbs_EDGE, aMapShapes); + TopExp::MapShapes (aShape, TopAbs_FACE, aMapShapes); + + for (Standard_Integer iS = 1; iS <= aMapShapes.Extent(); ++iS) + { + const TopoDS_Shape& aS = aMapShapes(iS); + + Bnd_Box aSBox; + BRepBndLib::Add (aS, aSBox); + + aShapeBoxSet->Add (aS, Bnd_Tools::Bnd2BVH (aSBox)); + } + + // Build BVH + aShapeBoxSet->Build(); + + // Initialize selector + ShapeSelector aSelector; + Bnd_Box aSelectionBox; + BRepBndLib::Add (aBShape, aSelectionBox); + aSelector.SetBox (aSelectionBox); + + // Select the elements + aShapeBoxSet->Select (aSelector); + const TopTools_ListOfShape& aSelectedShapes = aSelector.Shapes(); + + // Draw the selected shapes + TopoDS_Compound aResult; + BRep_Builder().MakeCompound (aResult); + + for (TopTools_ListOfShape::Iterator it (aSelectedShapes); it.More(); it.Next()) + BRep_Builder().Add (aResult, it.Value()); + + DBRep::Set (theArgv[1], aResult); + return 0; +} + +//======================================================================= +//function : PairShapeSelector +//purpose : Implement the simplest shape's selector +//======================================================================= +class PairShapesSelector : public BVH_BoxSet ::PairSelector +{ +public: + //! Constructor + PairShapesSelector() {} + + //! Returns the selected pairs of shapes + const NCollection_List >& Pairs () const { return myPairs; } + +public: + + //! Defines the rules for node rejection + virtual Standard_Boolean Reject (const BVH_Box & theBox1, + const BVH_Box & theBox2) const Standard_OVERRIDE + { + return theBox1.IsOut (theBox2); + } + + //! Defines the rules for leaf acceptance + virtual Standard_Boolean Accept (const TopoDS_Shape& theShape1, const TopoDS_Shape& theShape2) Standard_OVERRIDE + { + myPairs.Append (std::pair (theShape1, theShape2)); + return Standard_True; + } + +protected: + + NCollection_List > myPairs; //!< Selected pairs +}; + +//======================================================================= +//function : QABVH_PairSelect +//purpose : Test the work of BVH on the simple example of pairs of shapes selection +//======================================================================= +static Standard_Integer QABVH_PairSelect (Draw_Interpretor& theDI, + Standard_Integer theArgc, + const char** theArgv) +{ + if (theArgc != 4) + { + theDI.PrintHelp (theArgv[0]); + return 1; + } + + TopoDS_Shape aShape[2]; + // Get the first shape + aShape[0] = DBRep::Get (theArgv [2]); + if (aShape[0].IsNull()) + { + std::cout << theArgv[2] << " does not exist" << std::endl; + return 1; + } + + // Get the second shape + aShape[1] = DBRep::Get (theArgv [3]); + if (aShape[1].IsNull()) + { + std::cout << theArgv[3] << " does not exist" << std::endl; + return 1; + } + + // Define BVH Builder + opencascade::handle > aLBuilder = + new BVH_LinearBuilder (); + + // Create the ShapeSet + opencascade::handle > aShapeBoxSet[2]; + + for (Standard_Integer i = 0; i < 2; ++i) + { + aShapeBoxSet[i] = new BVH_BoxSet (aLBuilder); + // Add elements into set + TopTools_IndexedMapOfShape aMapShapes; + TopExp::MapShapes (aShape[i], TopAbs_VERTEX, aMapShapes); + TopExp::MapShapes (aShape[i], TopAbs_EDGE, aMapShapes); + TopExp::MapShapes (aShape[i], TopAbs_FACE, aMapShapes); + + for (Standard_Integer iS = 1; iS <= aMapShapes.Extent(); ++iS) + { + const TopoDS_Shape& aS = aMapShapes(iS); + + Bnd_Box aSBox; + BRepBndLib::Add (aS, aSBox); + + aShapeBoxSet[i]->Add (aS, Bnd_Tools::Bnd2BVH (aSBox)); + } + // Build BVH + aShapeBoxSet[i]->Build(); + } + + // Initialize selector + PairShapesSelector aSelector; + // Select the elements + aShapeBoxSet[0]->Select (aShapeBoxSet[1], aSelector); + + const NCollection_List >& aPairs = aSelector.Pairs(); + + // Draw the selected shapes + TopoDS_Compound aResult; + BRep_Builder().MakeCompound (aResult); + + for (NCollection_List >::Iterator it (aPairs); it.More(); it.Next()) + { + TopoDS_Compound aPair; + BRep_Builder().MakeCompound (aPair); + + BRep_Builder().Add (aPair, it.Value().first); + BRep_Builder().Add (aPair, it.Value().second); + + BRep_Builder().Add (aResult, aPair); + } + + DBRep::Set (theArgv[1], aResult); + return 0; +} + +//======================================================================= +//function : Commands_BVH +//purpose : BVH commands +//======================================================================= +void QABugs::Commands_BVH (Draw_Interpretor& theCommands) +{ + const char *group = "QABugs"; + + theCommands.Add("QABVH_ShapeSelect", + "Tests the work of BHV_BoxSet algorithm on the simple example of selection of shapes located which boxes interfere with given box.\n" + "Usage: QABVH_ShapeSelect result shape box (defined as a solid)\n" + "\tResult should contain all sub-shapes of the shape interfering with given box", + __FILE__, QABVH_ShapeSelect, group); + + theCommands.Add("QABVH_PairSelect", + "Tests the work of BHV_BoxSet algorithm on the simple example of selection of pairs of shapes with interfering bounding boxes.\n" + "Usage: QABVH_PairSelect result shape1 shape2\n" + "\tResult should contain all interfering pairs (compound of pairs)", + __FILE__, QABVH_PairSelect, group); +} diff --git a/tests/lowalgos/bvh/bug30655 b/tests/lowalgos/bvh/bug30655 new file mode 100644 index 0000000000..2b50539267 --- /dev/null +++ b/tests/lowalgos/bvh/bug30655 @@ -0,0 +1,38 @@ +puts "=======" +puts "0030655: Modeling Data - Provide interfaces for selection of the elements from BVH tree" +puts "=======" +puts "" + +pload QAcommands + +box b 10 10 10 + +# select elements interfering with each vertex (must be one vertex (itself), three edges and three faces - 7 in total) +foreach v [explode b v] { + QABVH_ShapeSelect r_$v b $v + if { [llength [explode r_$v]] != 7} { + puts "Error: incorrect selection" + } +} + +# select elements interfering with each edge (must be two vertices, five edges and and four faces - 11 in total) +foreach e [explode b e] { + QABVH_ShapeSelect r_$e b $e + if { [llength [explode r_$e]] != 11} { + puts "Error: incorrect selection" + } +} + +# select elements interfering with each face (must be ffour vertices, eight edges and and five faces - 17 in total) +foreach f [explode b f] { + QABVH_ShapeSelect r_$f b $f + if { [llength [explode r_$f]] != 17} { + puts "Error: incorrect selection" + } +} + +# intersect the box with itself - select all interfering pairs (8 * 7 + 12 * 11 + 6 * 17 = 290) +QABVH_PairSelect r b b +if { [llength [explode r]] != 290} { + puts "Error: incorrect selection" +} diff --git a/tests/lowalgos/grids.list b/tests/lowalgos/grids.list index 5d4e4d5ba4..4ceafa0356 100644 --- a/tests/lowalgos/grids.list +++ b/tests/lowalgos/grids.list @@ -3,4 +3,5 @@ 003 extcs 004 extcc 005 2dgcc -006 intss \ No newline at end of file +006 intss +008 bvh -- 2.39.5