BVH_BaseTraverse< MetricType > Class Template Reference

The classes implement the traverse of the BVH tree. More...

#include <BVH_Traverse.hxx>

Public Member Functions
Metrics comparison for choosing the best branch
virtual Standard_Boolean	IsMetricBetter (const MetricType &, const MetricType &) const
	Compares the two metrics and chooses the best one. Returns true if the first metric is better than the second, false otherwise.
Rejection of the node by metric
virtual Standard_Boolean	RejectMetric (const MetricType &) const
	Rejects the node by the metric.
Condition to stop the descend
virtual Standard_Boolean	Stop () const
	Returns the flag controlling the tree descend. Returns true if the tree descend should be stopped.

Protected Member Functions
Constructors
	BVH_BaseTraverse ()
	Constructor.
virtual	~BVH_BaseTraverse ()
	Destructor.

Detailed Description

template<class MetricType>
class BVH_BaseTraverse< MetricType >

The classes implement the traverse of the BVH tree.

There are two traverse methods implemented:

• Traverse of the single tree
• Parallel traverse of two trees

To perform Selection of the elements from BVH_Tree using the traverse methods implemented here it is required to define Acceptance/Rejection rules in the following methods:

• RejectNode - Node rejection by its bounding box. It is applied to both inner and outer nodes of the BVH tree. Optionally, the method should compute the metric for the node which will allow performing traverse faster by descending by the best branches.
• Accept - Element acceptance. It takes the index of the element of BVH tree. The access to the element itself should be performed through the set on which BVH is built. The Accept method implements the leaf node operation and usually defines the logic of the whole operation.
• IsMetricBetter - Compares the metrics of the nodes and returns true if the left metric is better than the right one.
• RejectMetric - Node rejection by the metric. It should compare the metric of the node with the global one and return true if the global metric is better than the given one.
• Stop - implements conditions to stop the tree descend if the necessary elements are already found.

The selector of a single tree has an extra method which allows accepting the whole branches without any further checks (e.g. full inclusion test):

• AcceptMetric - basing on the metric of the node decides if the node may be accepted without any further checks.

Two ways of selection are possible:

1. Set the BVH set containing the tree and use the method Select() which allows using common interface for setting the BVH Set for accessing the BVH tree and elements in the Accept method.
2. Keep the BVHSetType void, do not set the BVH set and use the method Select (const BVH_Tree<>&) which allows performing selection on the arbitrary BVH tree.

Here is the example of usage of the traverse to find the point-triangulation minimal distance.

// Structure to contain points of the triangle
struct Triangle
{
  Triangle() {}
  Triangle(const BVH_Vec3d& theNode1, 
           const BVH_Vec3d& theNode2,
           const BVH_Vec3d& theNode3)
    : Node1 (theNode1), Node2 (theNode2), Node3 (theNode3)
  {}
 
  BVH_Vec3d Node1;
  BVH_Vec3d Node2;
  BVH_Vec3d Node3;
};
 
// Selector for min point-triangulation distance
class BVH_PointTriangulationSqDist :
  public BVH_Distance<Standard_Real, 3, BVH_Vec3d, BVH_BoxSet<Standard_Real, 3, Triangle>>
{
public:
 
  // Computes the distance from the point to bounding box 
  virtual Standard_Boolean RejectNode (const BVH_Vec3d& theCMin,
                                       const BVH_Vec3d& theCMax,
                                       Standard_Real& theDistance) const Standard_OVERRIDE
  {
    theDistance = BVH_Tools<Standard_Real, 3>::PointBoxSquareDistance (myObject, theCMin, theCMax);
    return RejectMetric (theDistance);
  }
 
  // Computes the distance from the point to triangle
  virtual Standard_Boolean Accept (const Standard_Integer theIndex,
                                   const Standard_Real&) Standard_OVERRIDE
  {
    const Triangle& aTri = myBVHSet->Element (theIndex);
    Standard_Real aDist = BVH_Tools<Standard_Real, 3>::PointTriangleSquareDistance (myObject, aTri.Node1, aTri.Node2, aTri.Node3);
    if (aDist < myDistance)
    {
      myDistance = aDist;
      return Standard_True;
    }
    return Standard_False;
  }
};
 
// Point to which the distance is required
BVH_Vec3d aPoint = ...;
// BVH Set containing triangulation
opencascade::handle<BVH_BoxSet<Standard_Real, 3, Triangle>> aTriangulationSet = ...;
 
BVH_PointTriangulationSqDist aDistTool;
aDistTool.SetObject (aPoint);
aDistTool.SetBVHSet (aTriangulationSet.get());
aDistTool.ComputeDistance();
if (aDistTool.IsDone())
{
  Standard_Real aPointTriSqDist = aDistTool.Distance();
}

Abstract class implementing the base Traverse interface required for selection of the elements from BVH tree.

Template Parameters

MetricType

Type of metric to perform more optimal tree descend

Constructor & Destructor Documentation

BVH_BaseTraverse()

template<class MetricType >

BVH_BaseTraverse< MetricType >::BVH_BaseTraverse ( )

inlineprotected

Constructor.

~BVH_BaseTraverse()

template<class MetricType >

virtual BVH_BaseTraverse< MetricType >::~BVH_BaseTraverse ( )

inlineprotectedvirtual

Destructor.

Member Function Documentation

IsMetricBetter()

template<class MetricType >

virtual Standard_Boolean BVH_BaseTraverse< MetricType >::IsMetricBetter ( const MetricType & , const MetricType &  ) const

inlinevirtual

Compares the two metrics and chooses the best one. Returns true if the first metric is better than the second, false otherwise.

Reimplemented in BVH_Distance< NumType, Dimension, ObjectType, BVHSetType >, BVH_Distance< Standard_Real, 3, BVH_Vec3d, BRepExtrema_TriangleSet >, and BVH_PairDistance< NumType, Dimension, BVHSetType >.

RejectMetric()

template<class MetricType >

virtual Standard_Boolean BVH_BaseTraverse< MetricType >::RejectMetric ( const MetricType & ) const

inlinevirtual

Rejects the node by the metric.

Reimplemented in BVH_Distance< NumType, Dimension, ObjectType, BVHSetType >, BVH_Distance< Standard_Real, 3, BVH_Vec3d, BRepExtrema_TriangleSet >, and BVH_PairDistance< NumType, Dimension, BVHSetType >.

Stop()

template<class MetricType >

virtual Standard_Boolean BVH_BaseTraverse< MetricType >::Stop ( ) const

inlinevirtual

Returns the flag controlling the tree descend. Returns true if the tree descend should be stopped.

Reimplemented in BVH_Distance< NumType, Dimension, ObjectType, BVHSetType >, BVH_Distance< Standard_Real, 3, BVH_Vec3d, BRepExtrema_TriangleSet >, and BVH_PairDistance< NumType, Dimension, BVHSetType >.

---

The documentation for this class was generated from the following file:

• BVH_Traverse.hxx