0024307: TKOpenGl - efficient culling of large number of presentations

[occt.git] / src / BVH / BVH_BinnedBuilder.lxx

// Created on: 2013-12-20
// Created by: Denis BOGOLEPOV
// Copyright (c) 2013-2014 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.

// =======================================================================
// function : BVH_BinnedBuilder
// purpose  :
// =======================================================================
template<class T, int N, int Bins>
BVH_BinnedBuilder<T, N, Bins>::BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize,
                                                  const Standard_Integer theMaxTreeDepth)
: BVH_Builder<T, N> (theLeafNodeSize,
                     theMaxTreeDepth)
{
  //
}

// =======================================================================
// function : ~BVH_BinnedBuilder
// purpose  :
// =======================================================================
template<class T, int N, int Bins>
BVH_BinnedBuilder<T, N, Bins>::~BVH_BinnedBuilder()
{
  //
}

// =======================================================================
// function : GetSubVolumes
// purpose  :
// =======================================================================
template<class T, int N, int Bins>
void BVH_BinnedBuilder<T, N, Bins>::GetSubVolumes (BVH_Set<T, N>*         theSet,
                                                   BVH_Tree<T, N>*        theBVH,
                                                   const Standard_Integer theNode,
                                                   BVH_BinVector&         theBins,
                                                   const Standard_Integer theAxis)
{
  const T aMin = BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), theAxis);
  const T aMax = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), theAxis);

  const T anInvStep = static_cast<T> (Bins) / (aMax - aMin);

  for (Standard_Integer anIdx = theBVH->BegPrimitive (theNode); anIdx <= theBVH->EndPrimitive (theNode); ++anIdx)
  {
    typename BVH_Set<T, N>::BVH_BoxNt aBox = theSet->Box (anIdx);

    Standard_Integer aBinIndex = static_cast<Standard_Integer> (std::floor ((theSet->Center (anIdx, theAxis) - aMin) * anInvStep));
    if (aBinIndex < 0)
    {
      aBinIndex = 0;
    }
    else if (aBinIndex >= Bins)
    {
      aBinIndex = Bins - 1;
    }

    theBins[aBinIndex].Count++;
    theBins[aBinIndex].Box.Combine (aBox);
  }
}

namespace BVHTools
{
  // =======================================================================
  // function : SplitPrimitives
  // purpose  :
  // =======================================================================
  template<class T, int N>
  Standard_Integer SplitPrimitives (BVH_Set<T, N>*         theSet,
                                    const BVH_Box<T, N>&   theBox,
                                    const Standard_Integer theBeg,
                                    const Standard_Integer theEnd,
                                    const Standard_Integer theBin,
                                    const Standard_Integer theAxis,
                                    const Standard_Integer theBins)
  {
    const T aMin = BVHTools::VecComp<T, N>::Get (theBox.CornerMin(), theAxis);
    const T aMax = BVHTools::VecComp<T, N>::Get (theBox.CornerMax(), theAxis);

    const T anInvStep = static_cast<T> (theBins) / (aMax - aMin);

    Standard_Integer aLftIdx (theBeg);
    Standard_Integer aRghIdx (theEnd);

    do
    {
      while ((Standard_Integer) std::floor ((theSet->Center (aLftIdx, theAxis) - aMin) * anInvStep) <= theBin && aLftIdx < theEnd)
      {
        ++aLftIdx;
      }
      while ((Standard_Integer) std::floor ((theSet->Center (aRghIdx, theAxis) - aMin) * anInvStep) > theBin && aRghIdx > theBeg)
      {
        --aRghIdx;
      }

      if (aLftIdx <= aRghIdx)
      {
        if (aLftIdx != aRghIdx)
        {
          theSet->Swap (aLftIdx, aRghIdx);
        }

        ++aLftIdx;
        --aRghIdx;
      }
    } while (aLftIdx <= aRghIdx);

    return aLftIdx;
  }
}

#if defined (_WIN32) && defined (max)
  #undef max
#endif

#include <limits>

// =======================================================================
// function : BuildNode
// purpose  :
// =======================================================================
template<class T, int N, int Bins>
void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>*         theSet,
                                               BVH_Tree<T, N>*        theBVH,
                                               const Standard_Integer theNode)
{
  const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
  const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);

  if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
  {
    return; // node does not require partitioning
  }

  const BVH_Box<T, N> anAABB (theBVH->MinPoint (theNode),
                              theBVH->MaxPoint (theNode));

  const typename BVH_Box<T, N>::BVH_VecNt aSize = anAABB.Size();

  // Parameters for storing best split
  Standard_Integer aMinSplitAxis   = -1;
  Standard_Integer aMinSplitIndex  =  0;
  Standard_Integer aMinSplitNumLft =  0;
  Standard_Integer aMinSplitNumRgh =  0;

  BVH_Box<T, N> aMinSplitBoxLft;
  BVH_Box<T, N> aMinSplitBoxRgh;

  Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();

  // Find best split
  for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
  {
    if (BVHTools::VecComp<T, N>::Get (aSize, anAxis) <= THE_NODE_MIN_SIZE)
      continue;

    BVH_BinVector aBins;
    GetSubVolumes (theSet, theBVH, theNode, aBins, anAxis);

    // Choose the best split (with minimum SAH cost)
    for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit)
    {
      Standard_Integer aLftCount = 0;
      Standard_Integer aRghCount = 0;

      BVH_Box<T, N> aLftAABB;
      BVH_Box<T, N> aRghAABB;

      for (Standard_Integer anIndex = 0; anIndex < aSplit; ++anIndex)
      {
        aLftCount += aBins[anIndex].Count;
        aLftAABB.Combine (aBins[anIndex].Box);
      }

      for (Standard_Integer anIndex = aSplit; anIndex < Bins; ++anIndex)
      {
        aRghCount += aBins[anIndex].Count;
        aRghAABB.Combine (aBins[anIndex].Box);
      }

      // Simple SAH evaluation
      Standard_Real aCost = (static_cast<Standard_Real> (aLftAABB.Area()) /* / aNodeArea */) * aLftCount
                          + (static_cast<Standard_Real> (aRghAABB.Area()) /* / aNodeArea */) * aRghCount;

      if (aCost <= aMinSplitCost)
      {
        aMinSplitCost   = aCost;
        aMinSplitAxis   = anAxis;
        aMinSplitIndex  = aSplit;
        aMinSplitBoxLft = aLftAABB;
        aMinSplitBoxRgh = aRghAABB;
        aMinSplitNumLft = aLftCount;
        aMinSplitNumRgh = aRghCount;
      }
    }
  }

  if (aMinSplitAxis == -1)
  {
    return;
  }

  theBVH->SetInner (theNode);

  Standard_Integer aMiddle = -1;

  if (aMinSplitNumLft == 0 || aMinSplitNumRgh == 0) // case of objects with the same center
  {
    aMinSplitBoxLft.Clear();
    aMinSplitBoxRgh.Clear();

    aMiddle = std::max (aNodeBegPrimitive + 1,
      static_cast<Standard_Integer> ((aNodeBegPrimitive + aNodeEndPrimitive) / 2.f));

    aMinSplitNumLft = aMiddle - aNodeBegPrimitive;

    for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMiddle; ++anIndex)
    {
      aMinSplitBoxLft.Combine (theSet->Box (anIndex));
    }

    aMinSplitNumRgh = aNodeEndPrimitive - aMiddle + 1;

    for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMiddle; --anIndex)
    {
      aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
    }
  }
  else
  {
    aMiddle = BVHTools::SplitPrimitives<T, N> (theSet, anAABB,
      aNodeBegPrimitive, aNodeEndPrimitive, aMinSplitIndex - 1, aMinSplitAxis, Bins);
  }

  static const Standard_Integer aLftNode = 1;
  static const Standard_Integer aRghNode = 2;

  // Setting up tasks for child nodes
  for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
  {
    typename BVH_Box<T, N>::BVH_VecNt aMinPoint = (aSide == aLftNode)
                                                ? aMinSplitBoxLft.CornerMin()
                                                : aMinSplitBoxRgh.CornerMin();
    typename BVH_Box<T, N>::BVH_VecNt aMaxPoint = (aSide == aLftNode)
                                                ? aMinSplitBoxLft.CornerMax()
                                                : aMinSplitBoxRgh.CornerMax();

    Standard_Integer aBegPrimitive = (aSide == aLftNode)
                                   ? aNodeBegPrimitive
                                   : aMiddle;
    Standard_Integer aEndPrimitive = (aSide == aLftNode)
                                   ? aMiddle - 1
                                   : aNodeEndPrimitive;

    Standard_Integer aChildIndex = theBVH->AddLeafNode (aMinPoint, aMaxPoint, aBegPrimitive, aEndPrimitive);

    theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;

    // Check to see if child node must be split
    const Standard_Integer aNbPimitives = (aSide == aLftNode)
                                        ? aMinSplitNumLft
                                        : aMinSplitNumRgh;

    if (aSide == aLftNode)
      theBVH->LeftChild  (theNode) = aChildIndex;
    else
      theBVH->RightChild (theNode) = aChildIndex;

    const Standard_Boolean isLeaf = aNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
                                 || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;

    if (!isLeaf)
    {
      BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
    }

    BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex));
  }
}