KiCad PCB EDA Suite
BVH_PBRT Class Reference

#include <bvh_pbrt.h>

Inheritance diagram for BVH_PBRT:
ACCELERATOR_3D

Public Member Functions

 BVH_PBRT (const CONTAINER_3D_BASE &aObjectContainer, int aMaxPrimsInNode=4, SPLITMETHOD aSplitMethod=SPLITMETHOD::SAH)
 
 ~BVH_PBRT ()
 
bool Intersect (const RAY &aRay, HITINFO &aHitInfo) const override
 
bool Intersect (const RAY &aRay, HITINFO &aHitInfo, unsigned int aAccNodeInfo) const override
 
bool Intersect (const RAYPACKET &aRayPacket, HITINFO_PACKET *aHitInfoPacket) const override
 
bool IntersectP (const RAY &aRay, float aMaxDistance) const override
 

Protected Attributes

BBOX_3D m_bbox
 

Private Member Functions

BVHBuildNoderecursiveBuild (std::vector< BVHPrimitiveInfo > &primitiveInfo, int start, int end, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims)
 
BVHBuildNodeHLBVHBuild (const std::vector< BVHPrimitiveInfo > &primitiveInfo, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims)
 
BVHBuildNodeemitLBVH (BVHBuildNode *&buildNodes, const std::vector< BVHPrimitiveInfo > &primitiveInfo, MortonPrimitive *mortonPrims, int nPrimitives, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims, int *orderedPrimsOffset, int bit)
 TODO: after implement memory arena, put const back to this functions. More...
 
BVHBuildNodebuildUpperSAH (std::vector< BVHBuildNode * > &treeletRoots, int start, int end, int *totalNodes)
 
int flattenBVHTree (BVHBuildNode *node, uint32_t *offset)
 

Private Attributes

const int m_maxPrimsInNode
 
SPLITMETHOD m_splitMethod
 
CONST_VECTOR_OBJECT m_primitives
 
LinearBVHNodem_nodes
 
std::list< void * > m_nodesToFree
 
unsigned int m_I [RAYPACKET_RAYS_PER_PACKET]
 

Detailed Description

Definition at line 110 of file bvh_pbrt.h.

Constructor & Destructor Documentation

◆ BVH_PBRT()

BVH_PBRT::BVH_PBRT ( const CONTAINER_3D_BASE aObjectContainer,
int  aMaxPrimsInNode = 4,
SPLITMETHOD  aSplitMethod = SPLITMETHOD::SAH 
)

Definition at line 235 of file bvh_pbrt.cpp.

236  :
237  m_maxPrimsInNode( std::min( 255, aMaxPrimsInNode ) ),
238  m_splitMethod( aSplitMethod )
239 {
240  if( aObjectContainer.GetList().empty() )
241  {
242  m_nodes = nullptr;
243 
244  return;
245  }
246 
247  // Initialize the indexes of ray packet for partition traversal
248  for( unsigned int i = 0; i < RAYPACKET_RAYS_PER_PACKET; ++i )
249  {
250  m_I[i] = i;
251  }
252 
253  // Convert the objects list to vector of objects
254  aObjectContainer.ConvertTo( m_primitives );
255 
256  wxASSERT( aObjectContainer.GetList().size() == m_primitives.size() );
257 
258  // Initialize _primitiveInfo_ array for primitives
259  std::vector<BVHPrimitiveInfo> primitiveInfo( m_primitives.size() );
260 
261  for( size_t i = 0; i < m_primitives.size(); ++i )
262  {
263  wxASSERT( m_primitives[i]->GetBBox().IsInitialized() );
264 
265  primitiveInfo[i] = BVHPrimitiveInfo( i, m_primitives[i]->GetBBox() );
266  }
267 
268  // Build BVH tree for primitives using _primitiveInfo_
269  int totalNodes = 0;
270 
271  CONST_VECTOR_OBJECT orderedPrims;
272  orderedPrims.clear();
273  orderedPrims.reserve( m_primitives.size() );
274 
275  BVHBuildNode *root;
276 
278  root = HLBVHBuild( primitiveInfo, &totalNodes, orderedPrims );
279  else
280  root = recursiveBuild( primitiveInfo, 0, m_primitives.size(), &totalNodes, orderedPrims );
281 
282  wxASSERT( m_primitives.size() == orderedPrims.size() );
283 
284  m_primitives.swap( orderedPrims );
285 
286  // Compute representation of depth-first traversal of BVH tree
287  m_nodes = static_cast<LinearBVHNode*>( malloc( sizeof( LinearBVHNode ) * totalNodes ) );
288  m_nodesToFree.push_back( m_nodes );
289 
290  for( int i = 0; i < totalNodes; ++i )
291  {
292  m_nodes[i].bounds.Reset();
293  m_nodes[i].primitivesOffset = 0;
294  m_nodes[i].nPrimitives = 0;
295  m_nodes[i].axis = 0;
296  }
297 
298  uint32_t offset = 0;
299 
300  flattenBVHTree( root, &offset );
301 
302  wxASSERT( offset == (unsigned int)totalNodes );
303 }
int primitivesOffset
leaf
Definition: bvh_pbrt.h:90
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
SPLITMETHOD m_splitMethod
Definition: bvh_pbrt.h:143
uint16_t nPrimitives
0 -> interior node
Definition: bvh_pbrt.h:95
BVHBuildNode * recursiveBuild(std::vector< BVHPrimitiveInfo > &primitiveInfo, int start, int end, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims)
Definition: bvh_pbrt.cpp:426
uint8_t axis
interior node: xyz
Definition: bvh_pbrt.h:96
BVHBuildNode * HLBVHBuild(const std::vector< BVHPrimitiveInfo > &primitiveInfo, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims)
Definition: bvh_pbrt.cpp:678
const LIST_OBJECT & GetList() const
Definition: container_3d.h:59
std::vector< const OBJECT_3D * > CONST_VECTOR_OBJECT
Definition: container_3d.h:38
const int m_maxPrimsInNode
Definition: bvh_pbrt.h:142
void ConvertTo(CONST_VECTOR_OBJECT &aOutVector) const
std::list< void * > m_nodesToFree
Definition: bvh_pbrt.h:147
#define RAYPACKET_RAYS_PER_PACKET
Definition: raypacket.h:35
int flattenBVHTree(BVHBuildNode *node, uint32_t *offset)
Definition: bvh_pbrt.cpp:1034
void Reset()
Reset the bounding box to zero and de-initialize it.
Definition: bbox_3d.cpp:95
unsigned int m_I[RAYPACKET_RAYS_PER_PACKET]
Definition: bvh_pbrt.h:150
LinearBVHNode * m_nodes
Definition: bvh_pbrt.h:145
BBOX_3D bounds
Definition: bvh_pbrt.h:85

References LinearBVHNode::axis, LinearBVHNode::bounds, CONTAINER_3D_BASE::ConvertTo(), flattenBVHTree(), CONTAINER_3D_BASE::GetList(), HLBVH, HLBVHBuild(), m_I, m_nodes, m_nodesToFree, m_primitives, m_splitMethod, LinearBVHNode::nPrimitives, LinearBVHNode::primitivesOffset, RAYPACKET_RAYS_PER_PACKET, recursiveBuild(), and BBOX_3D::Reset().

◆ ~BVH_PBRT()

BVH_PBRT::~BVH_PBRT ( )

Definition at line 306 of file bvh_pbrt.cpp.

307 {
308  if( !m_nodesToFree.empty() )
309  {
310  for( std::list<void *>::iterator ii = m_nodesToFree.begin(); ii != m_nodesToFree.end();
311  ++ii )
312  {
313  free( *ii );
314  *ii = nullptr;
315  }
316  }
317 
318  m_nodesToFree.clear();
319 }
std::list< void * > m_nodesToFree
Definition: bvh_pbrt.h:147

References m_nodesToFree.

Member Function Documentation

◆ buildUpperSAH()

BVHBuildNode * BVH_PBRT::buildUpperSAH ( std::vector< BVHBuildNode * > &  treeletRoots,
int  start,
int  end,
int *  totalNodes 
)
private

Definition at line 894 of file bvh_pbrt.cpp.

896 {
897  wxASSERT( totalNodes != nullptr );
898  wxASSERT( start < end );
899  wxASSERT( end <= (int)treeletRoots.size() );
900 
901  int nNodes = end - start;
902 
903  if( nNodes == 1 )
904  return treeletRoots[start];
905 
906  (*totalNodes)++;
907 
908  BVHBuildNode* node = static_cast<BVHBuildNode*>( malloc( sizeof( BVHBuildNode ) ) );
909 
910  m_nodesToFree.push_back( node );
911 
912  node->bounds.Reset();
913  node->firstPrimOffset = 0;
914  node->nPrimitives = 0;
915  node->splitAxis = 0;
916  node->children[0] = nullptr;
917  node->children[1] = nullptr;
918 
919  // Compute bounds of all nodes under this HLBVH node
920  BBOX_3D bounds;
921  bounds.Reset();
922 
923  for( int i = start; i < end; ++i )
924  bounds.Union( treeletRoots[i]->bounds );
925 
926  // Compute bound of HLBVH node centroids, choose split dimension _dim_
927  BBOX_3D centroidBounds;
928  centroidBounds.Reset();
929 
930  for( int i = start; i < end; ++i )
931  {
932  SFVEC3F centroid = ( treeletRoots[i]->bounds.Min() + treeletRoots[i]->bounds.Max() ) * 0.5f;
933 
934  centroidBounds.Union( centroid );
935  }
936 
937  const int dim = centroidBounds.MaxDimension();
938 
939  // FIXME: if this hits, what do we need to do?
940  // Make sure the SAH split below does something... ?
941  wxASSERT( centroidBounds.Max()[dim] != centroidBounds.Min()[dim] );
942 
943  // Allocate _BucketInfo_ for SAH partition buckets
944  const int nBuckets = 12;
945 
946  BucketInfo buckets[nBuckets];
947 
948  for( int i = 0; i < nBuckets; ++i )
949  {
950  buckets[i].count = 0;
951  buckets[i].bounds.Reset();
952  }
953 
954  // Initialize _BucketInfo_ for HLBVH SAH partition buckets
955  for( int i = start; i < end; ++i )
956  {
957  const float centroid = ( treeletRoots[i]->bounds.Min()[dim] +
958  treeletRoots[i]->bounds.Max()[dim] ) * 0.5f;
959  int b = nBuckets * ( ( centroid - centroidBounds.Min()[dim] )
960  / ( centroidBounds.Max()[dim] - centroidBounds.Min()[dim] ) );
961 
962  if( b == nBuckets )
963  b = nBuckets - 1;
964 
965  wxASSERT( ( b >= 0 ) && ( b < nBuckets ) );
966 
967  buckets[b].count++;
968  buckets[b].bounds.Union( treeletRoots[i]->bounds );
969  }
970 
971  // Compute costs for splitting after each bucket
972  float cost[nBuckets - 1];
973 
974  for( int i = 0; i < nBuckets - 1; ++i )
975  {
976  BBOX_3D b0, b1;
977  b0.Reset();
978  b1.Reset();
979 
980  int count0 = 0, count1 = 0;
981 
982  for( int j = 0; j <= i; ++j )
983  {
984  if( buckets[j].count )
985  {
986  count0 += buckets[j].count;
987  b0.Union( buckets[j].bounds );
988  }
989  }
990 
991  for( int j = i + 1; j < nBuckets; ++j )
992  {
993  if( buckets[j].count )
994  {
995  count1 += buckets[j].count;
996  b1.Union( buckets[j].bounds );
997  }
998  }
999 
1000  cost[i] = .125f + ( count0 * b0.SurfaceArea() + count1 * b1.SurfaceArea() ) /
1001  bounds.SurfaceArea();
1002  }
1003 
1004  // Find bucket to split at that minimizes SAH metric
1005  float minCost = cost[0];
1006  int minCostSplitBucket = 0;
1007 
1008  for( int i = 1; i < nBuckets - 1; ++i )
1009  {
1010  if( cost[i] < minCost )
1011  {
1012  minCost = cost[i];
1013  minCostSplitBucket = i;
1014  }
1015  }
1016 
1017  // Split nodes and create interior HLBVH SAH node
1018  BVHBuildNode **pmid = std::partition( &treeletRoots[start], &treeletRoots[end - 1] + 1,
1019  HLBVH_SAH_Evaluator( minCostSplitBucket, nBuckets,
1020  dim, centroidBounds ) );
1021 
1022  const int mid = pmid - &treeletRoots[0];
1023 
1024  wxASSERT( ( mid > start ) && ( mid < end ) );
1025 
1026  node->InitInterior( dim,
1027  buildUpperSAH( treeletRoots, start, mid, totalNodes ),
1028  buildUpperSAH( treeletRoots, mid, end, totalNodes ) );
1029 
1030  return node;
1031 }
unsigned int MaxDimension() const
Definition: bbox_3d.cpp:151
BBOX_3D bounds
Definition: bvh_pbrt.cpp:422
const SFVEC3F & Max() const
Return the maximum vertex pointer.
Definition: bbox_3d.h:198
Manage a bounding box defined by two SFVEC3F min max points.
Definition: bbox_3d.h:41
int firstPrimOffset
Definition: bvh_pbrt.cpp:129
void InitInterior(int axis, BVHBuildNode *c0, BVHBuildNode *c1)
Definition: bvh_pbrt.cpp:117
void Union(const SFVEC3F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_3d.cpp:102
float SurfaceArea() const
Definition: bbox_3d.cpp:174
const SFVEC3F & Min() const
Return the minimum vertex pointer.
Definition: bbox_3d.h:191
BBOX_3D bounds
Definition: bvh_pbrt.cpp:127
BVHBuildNode * buildUpperSAH(std::vector< BVHBuildNode * > &treeletRoots, int start, int end, int *totalNodes)
Definition: bvh_pbrt.cpp:894
BVHBuildNode * children[2]
Definition: bvh_pbrt.cpp:128
std::list< void * > m_nodesToFree
Definition: bvh_pbrt.h:147
glm::vec3 SFVEC3F
Definition: xv3d_types.h:44
void Reset()
Reset the bounding box to zero and de-initialize it.
Definition: bbox_3d.cpp:95

References BVHBuildNode::bounds, BucketInfo::bounds, BVHBuildNode::children, BucketInfo::count, BVHBuildNode::firstPrimOffset, BVHBuildNode::InitInterior(), m_nodesToFree, BBOX_3D::Max(), BBOX_3D::MaxDimension(), BBOX_3D::Min(), BVHBuildNode::nPrimitives, BBOX_3D::Reset(), BVHBuildNode::splitAxis, BBOX_3D::SurfaceArea(), and BBOX_3D::Union().

Referenced by HLBVHBuild().

◆ emitLBVH()

BVHBuildNode * BVH_PBRT::emitLBVH ( BVHBuildNode *&  buildNodes,
const std::vector< BVHPrimitiveInfo > &  primitiveInfo,
MortonPrimitive mortonPrims,
int  nPrimitives,
int *  totalNodes,
CONST_VECTOR_OBJECT orderedPrims,
int *  orderedPrimsOffset,
int  bit 
)
private

TODO: after implement memory arena, put const back to this functions.

Definition at line 795 of file bvh_pbrt.cpp.

800 {
801  wxASSERT( nPrimitives > 0 );
802  wxASSERT( totalNodes != nullptr );
803  wxASSERT( orderedPrimsOffset != nullptr );
804  wxASSERT( nPrimitives > 0 );
805  wxASSERT( mortonPrims != nullptr );
806 
807  if( ( bit == -1 ) || ( nPrimitives < m_maxPrimsInNode ) )
808  {
809  // Create and return leaf node of LBVH treelet
810  (*totalNodes)++;
811 
812  BVHBuildNode *node = buildNodes++;
813  BBOX_3D bounds;
814  bounds.Reset();
815 
816  int firstPrimOffset = *orderedPrimsOffset;
817  *orderedPrimsOffset += nPrimitives;
818 
819  wxASSERT( ( firstPrimOffset + ( nPrimitives - 1 ) ) < (int) orderedPrims.size() );
820 
821  for( int i = 0; i < nPrimitives; ++i )
822  {
823  const int primitiveIndex = mortonPrims[i].primitiveIndex;
824 
825  wxASSERT( primitiveIndex < (int)m_primitives.size() );
826 
827  orderedPrims[firstPrimOffset + i] = m_primitives[primitiveIndex];
828  bounds.Union( primitiveInfo[primitiveIndex].bounds );
829  }
830 
831  node->InitLeaf( firstPrimOffset, nPrimitives, bounds );
832 
833  return node;
834  }
835  else
836  {
837  int mask = 1 << bit;
838 
839  // Advance to next subtree level if there's no LBVH split for this bit
840  if( ( mortonPrims[0].mortonCode & mask ) ==
841  ( mortonPrims[nPrimitives - 1].mortonCode & mask ) )
842  return emitLBVH( buildNodes, primitiveInfo, mortonPrims, nPrimitives, totalNodes,
843  orderedPrims, orderedPrimsOffset, bit - 1 );
844 
845  // Find LBVH split point for this dimension
846  int searchStart = 0;
847  int searchEnd = nPrimitives - 1;
848 
849  while( searchStart + 1 != searchEnd )
850  {
851  wxASSERT(searchStart != searchEnd);
852 
853  const int mid = ( searchStart + searchEnd ) / 2;
854 
855  if( ( mortonPrims[searchStart].mortonCode & mask ) ==
856  ( mortonPrims[mid].mortonCode & mask ) )
857  searchStart = mid;
858  else
859  {
860  wxASSERT( ( mortonPrims[mid].mortonCode & mask ) ==
861  ( mortonPrims[searchEnd].mortonCode & mask ) );
862  searchEnd = mid;
863  }
864  }
865 
866  const int splitOffset = searchEnd;
867 
868  wxASSERT( splitOffset <= ( nPrimitives - 1 ) );
869  wxASSERT( ( mortonPrims[splitOffset - 1].mortonCode & mask )
870  != ( mortonPrims[splitOffset].mortonCode & mask ) );
871 
872  // Create and return interior LBVH node
873  (*totalNodes)++;
874 
875  BVHBuildNode *node = buildNodes++;
876  BVHBuildNode *lbvh[2];
877 
878  lbvh[0] = emitLBVH( buildNodes, primitiveInfo, mortonPrims, splitOffset,
879  totalNodes, orderedPrims, orderedPrimsOffset, bit - 1 );
880 
881  lbvh[1] = emitLBVH( buildNodes, primitiveInfo, &mortonPrims[splitOffset],
882  nPrimitives - splitOffset, totalNodes, orderedPrims,
883  orderedPrimsOffset, bit - 1 );
884 
885  const int axis = bit % 3;
886 
887  node->InitInterior( axis, lbvh[0], lbvh[1] );
888 
889  return node;
890  }
891 }
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
void InitLeaf(int first, int n, const BBOX_3D &b)
Definition: bvh_pbrt.cpp:109
Manage a bounding box defined by two SFVEC3F min max points.
Definition: bbox_3d.h:41
void InitInterior(int axis, BVHBuildNode *c0, BVHBuildNode *c1)
Definition: bvh_pbrt.cpp:117
void Union(const SFVEC3F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_3d.cpp:102
BVHBuildNode * emitLBVH(BVHBuildNode *&buildNodes, const std::vector< BVHPrimitiveInfo > &primitiveInfo, MortonPrimitive *mortonPrims, int nPrimitives, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims, int *orderedPrimsOffset, int bit)
TODO: after implement memory arena, put const back to this functions.
Definition: bvh_pbrt.cpp:795
const int m_maxPrimsInNode
Definition: bvh_pbrt.h:142
uint32_t mortonCode
Definition: bvh_pbrt.cpp:136
void Reset()
Reset the bounding box to zero and de-initialize it.
Definition: bbox_3d.cpp:95

References BVHBuildNode::InitInterior(), BVHBuildNode::InitLeaf(), m_maxPrimsInNode, m_primitives, MortonPrimitive::mortonCode, MortonPrimitive::primitiveIndex, BBOX_3D::Reset(), and BBOX_3D::Union().

Referenced by HLBVHBuild().

◆ flattenBVHTree()

int BVH_PBRT::flattenBVHTree ( BVHBuildNode node,
uint32_t *  offset 
)
private

Definition at line 1034 of file bvh_pbrt.cpp.

1035 {
1036  LinearBVHNode *linearNode = &m_nodes[*offset];
1037 
1038  linearNode->bounds = node->bounds;
1039 
1040  int myOffset = (*offset)++;
1041 
1042  if( node->nPrimitives > 0 )
1043  {
1044  wxASSERT( ( !node->children[0] ) && ( !node->children[1] ) );
1045  wxASSERT( node->nPrimitives < 65536 );
1046 
1047  linearNode->primitivesOffset = node->firstPrimOffset;
1048  linearNode->nPrimitives = node->nPrimitives;
1049  }
1050  else
1051  {
1052  // Create interior flattened BVH node
1053  linearNode->axis = node->splitAxis;
1054  linearNode->nPrimitives = 0;
1055  flattenBVHTree( node->children[0], offset );
1056  linearNode->secondChildOffset = flattenBVHTree( node->children[1], offset );
1057  }
1058 
1059  return myOffset;
1060 }
int primitivesOffset
leaf
Definition: bvh_pbrt.h:90
uint16_t nPrimitives
0 -> interior node
Definition: bvh_pbrt.h:95
uint8_t axis
interior node: xyz
Definition: bvh_pbrt.h:96
int firstPrimOffset
Definition: bvh_pbrt.cpp:129
BBOX_3D bounds
Definition: bvh_pbrt.cpp:127
BVHBuildNode * children[2]
Definition: bvh_pbrt.cpp:128
int flattenBVHTree(BVHBuildNode *node, uint32_t *offset)
Definition: bvh_pbrt.cpp:1034
int secondChildOffset
interior
Definition: bvh_pbrt.h:91
LinearBVHNode * m_nodes
Definition: bvh_pbrt.h:145
BBOX_3D bounds
Definition: bvh_pbrt.h:85

References LinearBVHNode::axis, LinearBVHNode::bounds, BVHBuildNode::bounds, BVHBuildNode::children, BVHBuildNode::firstPrimOffset, m_nodes, LinearBVHNode::nPrimitives, BVHBuildNode::nPrimitives, LinearBVHNode::primitivesOffset, LinearBVHNode::secondChildOffset, and BVHBuildNode::splitAxis.

Referenced by BVH_PBRT().

◆ HLBVHBuild()

BVHBuildNode * BVH_PBRT::HLBVHBuild ( const std::vector< BVHPrimitiveInfo > &  primitiveInfo,
int *  totalNodes,
CONST_VECTOR_OBJECT orderedPrims 
)
private

Definition at line 678 of file bvh_pbrt.cpp.

680 {
681  // Compute bounding box of all primitive centroids
682  BBOX_3D bounds;
683  bounds.Reset();
684 
685  for( unsigned int i = 0; i < primitiveInfo.size(); ++i )
686  bounds.Union( primitiveInfo[i].centroid );
687 
688  // Compute Morton indices of primitives
689  std::vector<MortonPrimitive> mortonPrims( primitiveInfo.size() );
690 
691  for( int i = 0; i < (int)primitiveInfo.size(); ++i )
692  {
693  // Initialize _mortonPrims[i]_ for _i_th primitive
694  const int mortonBits = 10;
695  const int mortonScale = 1 << mortonBits;
696 
697  wxASSERT( primitiveInfo[i].primitiveNumber < (int)primitiveInfo.size() );
698 
699  mortonPrims[i].primitiveIndex = primitiveInfo[i].primitiveNumber;
700 
701  const SFVEC3F centroidOffset = bounds.Offset( primitiveInfo[i].centroid );
702 
703  wxASSERT( ( centroidOffset.x >= 0.0f ) && ( centroidOffset.x <= 1.0f ) );
704  wxASSERT( ( centroidOffset.y >= 0.0f ) && ( centroidOffset.y <= 1.0f ) );
705  wxASSERT( ( centroidOffset.z >= 0.0f ) && ( centroidOffset.z <= 1.0f ) );
706 
707  mortonPrims[i].mortonCode = EncodeMorton3( centroidOffset * SFVEC3F( (float)mortonScale ) );
708  }
709 
710  // Radix sort primitive Morton indices
711  RadixSort( &mortonPrims );
712 
713  // Create LBVH treelets at bottom of BVH
714 
715  // Find intervals of primitives for each treelet
716  std::vector<LBVHTreelet> treeletsToBuild;
717 
718  for( int start = 0, end = 1; end <= (int)mortonPrims.size(); ++end )
719  {
720  const uint32_t mask = 0b00111111111111000000000000000000;
721 
722  if( ( end == (int) mortonPrims.size() )
723  || ( ( mortonPrims[start].mortonCode & mask )
724  != ( mortonPrims[end].mortonCode & mask ) ) )
725  {
726  // Add entry to _treeletsToBuild_ for this treelet
727  const int numPrimitives = end - start;
728  const int maxBVHNodes = 2 * numPrimitives;
729 
730  // !TODO: implement a memory arena
731  BVHBuildNode *nodes = static_cast<BVHBuildNode *>( malloc( maxBVHNodes *
732  sizeof( BVHBuildNode ) ) );
733 
734  m_nodesToFree.push_back( nodes );
735 
736  for( int i = 0; i < maxBVHNodes; ++i )
737  {
738  nodes[i].bounds.Reset();
739  nodes[i].firstPrimOffset = 0;
740  nodes[i].nPrimitives = 0;
741  nodes[i].splitAxis = 0;
742  nodes[i].children[0] = nullptr;
743  nodes[i].children[1] = nullptr;
744  }
745 
746  LBVHTreelet tmpTreelet;
747 
748  tmpTreelet.startIndex = start;
749  tmpTreelet.numPrimitives = numPrimitives;
750  tmpTreelet.buildNodes = nodes;
751 
752  treeletsToBuild.push_back( tmpTreelet );
753 
754  start = end;
755  }
756  }
757 
758  // Create LBVHs for treelets in parallel
759  int atomicTotal = 0;
760  int orderedPrimsOffset = 0;
761 
762  orderedPrims.resize( m_primitives.size() );
763 
764  for( int index = 0; index < (int)treeletsToBuild.size(); ++index )
765  {
766  // Generate _index_th LBVH treelet
767  int nodesCreated = 0;
768  const int firstBit = 29 - 12;
769 
770  LBVHTreelet &tr = treeletsToBuild[index];
771 
772  wxASSERT( tr.startIndex < (int)mortonPrims.size() );
773 
774  tr.buildNodes = emitLBVH( tr.buildNodes, primitiveInfo, &mortonPrims[tr.startIndex],
775  tr.numPrimitives, &nodesCreated, orderedPrims,
776  &orderedPrimsOffset, firstBit );
777 
778  atomicTotal += nodesCreated;
779  }
780 
781  *totalNodes = atomicTotal;
782 
783  // Initialize _finishedTreelets_ with treelet root node pointers
784  std::vector<BVHBuildNode *> finishedTreelets;
785  finishedTreelets.reserve( treeletsToBuild.size() );
786 
787  for( int index = 0; index < (int)treeletsToBuild.size(); ++index )
788  finishedTreelets.push_back( treeletsToBuild[index].buildNodes );
789 
790  // Create and return SAH BVH from LBVH treelets
791  return buildUpperSAH( finishedTreelets, 0, finishedTreelets.size(), totalNodes );
792 }
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
Manage a bounding box defined by two SFVEC3F min max points.
Definition: bbox_3d.h:41
int firstPrimOffset
Definition: bvh_pbrt.cpp:129
SFVEC3F Offset(const SFVEC3F &p) const
Definition: bbox_3d.cpp:251
int startIndex
Definition: bvh_pbrt.cpp:142
void Union(const SFVEC3F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_3d.cpp:102
BVHBuildNode * emitLBVH(BVHBuildNode *&buildNodes, const std::vector< BVHPrimitiveInfo > &primitiveInfo, MortonPrimitive *mortonPrims, int nPrimitives, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims, int *orderedPrimsOffset, int bit)
TODO: after implement memory arena, put const back to this functions.
Definition: bvh_pbrt.cpp:795
static void RadixSort(std::vector< MortonPrimitive > *v)
Definition: bvh_pbrt.cpp:178
BBOX_3D bounds
Definition: bvh_pbrt.cpp:127
BVHBuildNode * buildUpperSAH(std::vector< BVHBuildNode * > &treeletRoots, int start, int end, int *totalNodes)
Definition: bvh_pbrt.cpp:894
int numPrimitives
Definition: bvh_pbrt.cpp:142
BVHBuildNode * children[2]
Definition: bvh_pbrt.cpp:128
BVHBuildNode * buildNodes
Definition: bvh_pbrt.cpp:143
uint32_t EncodeMorton3(const SFVEC3F &v)
Definition: bvh_pbrt.cpp:168
std::list< void * > m_nodesToFree
Definition: bvh_pbrt.h:147
glm::vec3 SFVEC3F
Definition: xv3d_types.h:44
void Reset()
Reset the bounding box to zero and de-initialize it.
Definition: bbox_3d.cpp:95

References BVHBuildNode::bounds, LBVHTreelet::buildNodes, buildUpperSAH(), BVHBuildNode::children, emitLBVH(), EncodeMorton3(), BVHBuildNode::firstPrimOffset, m_nodesToFree, m_primitives, BVHBuildNode::nPrimitives, LBVHTreelet::numPrimitives, BBOX_3D::Offset(), RadixSort(), BBOX_3D::Reset(), BVHBuildNode::splitAxis, LBVHTreelet::startIndex, and BBOX_3D::Union().

Referenced by BVH_PBRT().

◆ Intersect() [1/3]

bool BVH_PBRT::Intersect ( const RAY aRay,
HITINFO aHitInfo 
) const
overridevirtual

Implements ACCELERATOR_3D.

Definition at line 1066 of file bvh_pbrt.cpp.

1067 {
1068  if( !m_nodes )
1069  return false;
1070 
1071  bool hit = false;
1072 
1073  // Follow ray through BVH nodes to find primitive intersections
1074  int todoOffset = 0, nodeNum = 0;
1075  int todo[MAX_TODOS];
1076 
1077  while( true )
1078  {
1079  const LinearBVHNode *node = &m_nodes[nodeNum];
1080 
1081  wxASSERT( todoOffset < MAX_TODOS );
1082 
1083  // Check ray against BVH node
1084  float hitBox = 0.0f;
1085 
1086  const bool hitted = node->bounds.Intersect( aRay, &hitBox );
1087 
1088  if( hitted && ( hitBox < aHitInfo.m_tHit ) )
1089  {
1090  if( node->nPrimitives > 0 )
1091  {
1092  // Intersect ray with primitives in leaf BVH node
1093  for( int i = 0; i < node->nPrimitives; ++i )
1094  {
1095  if( m_primitives[node->primitivesOffset + i]->Intersect( aRay, aHitInfo ) )
1096  {
1097  aHitInfo.m_acc_node_info = nodeNum;
1098  hit = true;
1099  }
1100  }
1101  }
1102  else
1103  {
1104  // Put far BVH node on _todo_ stack, advance to near node
1105  if( aRay.m_dirIsNeg[node->axis] )
1106  {
1107  todo[todoOffset++] = nodeNum + 1;
1108  nodeNum = node->secondChildOffset;
1109  }
1110  else
1111  {
1112  todo[todoOffset++] = node->secondChildOffset;
1113  nodeNum = nodeNum + 1;
1114  }
1115 
1116  continue;
1117  }
1118  }
1119 
1120  if( todoOffset == 0 )
1121  break;
1122 
1123  nodeNum = todo[--todoOffset];
1124  }
1125 
1126  return hit;
1127 }
int primitivesOffset
leaf
Definition: bvh_pbrt.h:90
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
uint16_t nPrimitives
0 -> interior node
Definition: bvh_pbrt.h:95
bool Intersect(const RAY &aRay, float *t) const
Definition: bbox_3d_ray.cpp:46
uint8_t axis
interior node: xyz
Definition: bvh_pbrt.h:96
float m_tHit
( 4) distance
Definition: hitinfo.h:38
unsigned int m_dirIsNeg[3]
Definition: ray.h:75
unsigned int m_acc_node_info
( 4) The acc stores here the node that it hits
Definition: hitinfo.h:42
int secondChildOffset
interior
Definition: bvh_pbrt.h:91
#define MAX_TODOS
Definition: bvh_pbrt.cpp:1063
LinearBVHNode * m_nodes
Definition: bvh_pbrt.h:145
BBOX_3D bounds
Definition: bvh_pbrt.h:85

References LinearBVHNode::axis, LinearBVHNode::bounds, BBOX_3D::Intersect(), HITINFO::m_acc_node_info, RAY::m_dirIsNeg, m_nodes, m_primitives, HITINFO::m_tHit, MAX_TODOS, LinearBVHNode::nPrimitives, LinearBVHNode::primitivesOffset, and LinearBVHNode::secondChildOffset.

◆ Intersect() [2/3]

bool BVH_PBRT::Intersect ( const RAY aRay,
HITINFO aHitInfo,
unsigned int  aAccNodeInfo 
) const
overridevirtual
Todo:
This may be optimized

Implements ACCELERATOR_3D.

Definition at line 1131 of file bvh_pbrt.cpp.

1132 {
1133  if( !m_nodes )
1134  return false;
1135 
1136  bool hit = false;
1137 
1138  // Follow ray through BVH nodes to find primitive intersections
1139  int todoOffset = 0, nodeNum = aAccNodeInfo;
1140  int todo[MAX_TODOS];
1141 
1142  while( true )
1143  {
1144  const LinearBVHNode *node = &m_nodes[nodeNum];
1145 
1146  wxASSERT( todoOffset < MAX_TODOS );
1147 
1148  // Check ray against BVH node
1149  float hitBox = 0.0f;
1150 
1151  const bool hitted = node->bounds.Intersect( aRay, &hitBox );
1152 
1153  if( hitted && ( hitBox < aHitInfo.m_tHit ) )
1154  {
1155  if( node->nPrimitives > 0 )
1156  {
1157  // Intersect ray with primitives in leaf BVH node
1158  for( int i = 0; i < node->nPrimitives; ++i )
1159  {
1160  if( m_primitives[node->primitivesOffset + i]->Intersect( aRay, aHitInfo ) )
1161  {
1162  //aHitInfo.m_acc_node_info = nodeNum;
1163  hit = true;
1164  }
1165  }
1166  }
1167  else
1168  {
1169  // Put far BVH node on _todo_ stack, advance to near node
1170  if( aRay.m_dirIsNeg[node->axis] )
1171  {
1172  todo[todoOffset++] = nodeNum + 1;
1173  nodeNum = node->secondChildOffset;
1174  }
1175  else
1176  {
1177  todo[todoOffset++] = node->secondChildOffset;
1178  nodeNum = nodeNum + 1;
1179  }
1180 
1181  continue;
1182  }
1183  }
1184 
1185  if( todoOffset == 0 )
1186  break;
1187 
1188  nodeNum = todo[--todoOffset];
1189  }
1190 
1191  return hit;
1192 }
int primitivesOffset
leaf
Definition: bvh_pbrt.h:90
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
uint16_t nPrimitives
0 -> interior node
Definition: bvh_pbrt.h:95
bool Intersect(const RAY &aRay, float *t) const
Definition: bbox_3d_ray.cpp:46
uint8_t axis
interior node: xyz
Definition: bvh_pbrt.h:96
float m_tHit
( 4) distance
Definition: hitinfo.h:38
unsigned int m_dirIsNeg[3]
Definition: ray.h:75
int secondChildOffset
interior
Definition: bvh_pbrt.h:91
#define MAX_TODOS
Definition: bvh_pbrt.cpp:1063
LinearBVHNode * m_nodes
Definition: bvh_pbrt.h:145
BBOX_3D bounds
Definition: bvh_pbrt.h:85

References LinearBVHNode::axis, LinearBVHNode::bounds, BBOX_3D::Intersect(), RAY::m_dirIsNeg, m_nodes, m_primitives, HITINFO::m_tHit, MAX_TODOS, LinearBVHNode::nPrimitives, LinearBVHNode::primitivesOffset, and LinearBVHNode::secondChildOffset.

◆ Intersect() [3/3]

bool BVH_PBRT::Intersect ( const RAYPACKET aRayPacket,
HITINFO_PACKET aHitInfoPacket 
) const
overridevirtual

Implements ACCELERATOR_3D.

Definition at line 92 of file bvh_packet_traversal.cpp.

93 {
94  if( m_nodes == nullptr )
95  return false;
96 
97  if( &m_nodes[0] == nullptr )
98  return false;
99 
100  bool anyHit = false;
101  int todoOffset = 0, nodeNum = 0;
102  StackNode todo[MAX_TODOS];
103 
104  unsigned int ia = 0;
105 
106  while( true )
107  {
108  const LinearBVHNode *curCell = &m_nodes[nodeNum];
109 
110  ia = getFirstHit( aRayPacket, curCell->bounds, ia, aHitInfoPacket );
111 
112  if( ia < RAYPACKET_RAYS_PER_PACKET )
113  {
114  if( curCell->nPrimitives == 0 )
115  {
116  StackNode& node = todo[todoOffset++];
117  node.cell = curCell->secondChildOffset;
118  node.ia = ia;
119  nodeNum = nodeNum + 1;
120  continue;
121  }
122  else
123  {
124  const unsigned int ie = getLastHit( aRayPacket, curCell->bounds, ia,
125  aHitInfoPacket );
126 
127  for( int j = 0; j < curCell->nPrimitives; ++j )
128  {
129  const OBJECT_3D* obj = m_primitives[curCell->primitivesOffset + j];
130 
131  if( aRayPacket.m_Frustum.Intersect( obj->GetBBox() ) )
132  {
133  for( unsigned int i = ia; i < ie; ++i )
134  {
135  const bool hit = obj->Intersect( aRayPacket.m_ray[i],
136  aHitInfoPacket[i].m_HitInfo );
137 
138  if( hit )
139  {
140  anyHit |= hit;
141  aHitInfoPacket[i].m_hitresult |= hit;
142  aHitInfoPacket[i].m_HitInfo.m_acc_node_info = nodeNum;
143  }
144  }
145  }
146  }
147  }
148  }
149 
150  if( todoOffset == 0 )
151  break;
152 
153  const StackNode& node = todo[--todoOffset];
154 
155  nodeNum = node.cell;
156  ia = node.ia;
157  }
158 
159  return anyHit;
160 
161 }
static unsigned int getFirstHit(const RAYPACKET &aRayPacket, const BBOX_3D &aBBox, unsigned int ia, HITINFO_PACKET *aHitInfoPacket)
RAY m_ray[RAYPACKET_RAYS_PER_PACKET]
Definition: raypacket.h:54
int primitivesOffset
leaf
Definition: bvh_pbrt.h:90
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
unsigned int ia
uint16_t nPrimitives
0 -> interior node
Definition: bvh_pbrt.h:95
virtual bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const =0
static unsigned int getLastHit(const RAYPACKET &aRayPacket, const BBOX_3D &aBBox, unsigned int ia, HITINFO_PACKET *aHitInfoPacket)
bool Intersect(const BBOX_3D &aBBox) const
Intersect aBBox with this frustum.
Definition: frustum.cpp:58
HITINFO m_HitInfo
Definition: hitinfo.h:58
FRUSTUM m_Frustum
Definition: raypacket.h:53
#define RAYPACKET_RAYS_PER_PACKET
Definition: raypacket.h:35
unsigned int m_acc_node_info
( 4) The acc stores here the node that it hits
Definition: hitinfo.h:42
const BBOX_3D & GetBBox() const
Definition: object_3d.h:92
int secondChildOffset
interior
Definition: bvh_pbrt.h:91
bool m_hitresult
Definition: hitinfo.h:57
#define MAX_TODOS
LinearBVHNode * m_nodes
Definition: bvh_pbrt.h:145
BBOX_3D bounds
Definition: bvh_pbrt.h:85

References LinearBVHNode::bounds, StackNode::cell, OBJECT_3D::GetBBox(), getFirstHit(), getLastHit(), StackNode::ia, FRUSTUM::Intersect(), OBJECT_3D::Intersect(), HITINFO::m_acc_node_info, RAYPACKET::m_Frustum, HITINFO_PACKET::m_HitInfo, HITINFO_PACKET::m_hitresult, m_nodes, m_primitives, RAYPACKET::m_ray, MAX_TODOS, LinearBVHNode::nPrimitives, LinearBVHNode::primitivesOffset, RAYPACKET_RAYS_PER_PACKET, and LinearBVHNode::secondChildOffset.

◆ IntersectP()

bool BVH_PBRT::IntersectP ( const RAY aRay,
float  aMaxDistance 
) const
overridevirtual

Implements ACCELERATOR_3D.

Definition at line 1195 of file bvh_pbrt.cpp.

1196 {
1197  if( !m_nodes )
1198  return false;
1199 
1200  // Follow ray through BVH nodes to find primitive intersections
1201  int todoOffset = 0, nodeNum = 0;
1202  int todo[MAX_TODOS];
1203 
1204  while( true )
1205  {
1206  const LinearBVHNode* node = &m_nodes[nodeNum];
1207 
1208  wxASSERT( todoOffset < MAX_TODOS );
1209 
1210  // Check ray against BVH node
1211  float hitBox = 0.0f;
1212 
1213  const bool hitted = node->bounds.Intersect( aRay, &hitBox );
1214 
1215  if( hitted && ( hitBox < aMaxDistance ) )
1216  {
1217  if( node->nPrimitives > 0 )
1218  {
1219  // Intersect ray with primitives in leaf BVH node
1220  for( int i = 0; i < node->nPrimitives; ++i )
1221  {
1222  const OBJECT_3D* obj = m_primitives[node->primitivesOffset + i];
1223 
1224  if( obj->GetMaterial()->GetCastShadows()
1225  && obj->IntersectP( aRay, aMaxDistance ) )
1226  return true;
1227  }
1228  }
1229  else
1230  {
1231  // Put far BVH node on _todo_ stack, advance to near node
1232  if( aRay.m_dirIsNeg[node->axis] )
1233  {
1234  todo[todoOffset++] = nodeNum + 1;
1235  nodeNum = node->secondChildOffset;
1236  }
1237  else
1238  {
1239  todo[todoOffset++] = node->secondChildOffset;
1240  nodeNum = nodeNum + 1;
1241  }
1242 
1243  continue;
1244  }
1245  }
1246 
1247  if( todoOffset == 0 )
1248  break;
1249 
1250  nodeNum = todo[--todoOffset];
1251  }
1252 
1253  return false;
1254 }
int primitivesOffset
leaf
Definition: bvh_pbrt.h:90
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
uint16_t nPrimitives
0 -> interior node
Definition: bvh_pbrt.h:95
bool Intersect(const RAY &aRay, float *t) const
Definition: bbox_3d_ray.cpp:46
uint8_t axis
interior node: xyz
Definition: bvh_pbrt.h:96
unsigned int m_dirIsNeg[3]
Definition: ray.h:75
virtual bool IntersectP(const RAY &aRay, float aMaxDistance) const =0
int secondChildOffset
interior
Definition: bvh_pbrt.h:91
#define MAX_TODOS
Definition: bvh_pbrt.cpp:1063
bool GetCastShadows() const
Definition: material.h:309
LinearBVHNode * m_nodes
Definition: bvh_pbrt.h:145
const MATERIAL * GetMaterial() const
Definition: object_3d.h:64
BBOX_3D bounds
Definition: bvh_pbrt.h:85

References LinearBVHNode::axis, LinearBVHNode::bounds, MATERIAL::GetCastShadows(), OBJECT_3D::GetMaterial(), BBOX_3D::Intersect(), OBJECT_3D::IntersectP(), RAY::m_dirIsNeg, m_nodes, m_primitives, MAX_TODOS, LinearBVHNode::nPrimitives, LinearBVHNode::primitivesOffset, and LinearBVHNode::secondChildOffset.

◆ recursiveBuild()

BVHBuildNode * BVH_PBRT::recursiveBuild ( std::vector< BVHPrimitiveInfo > &  primitiveInfo,
int  start,
int  end,
int *  totalNodes,
CONST_VECTOR_OBJECT orderedPrims 
)
private

Definition at line 426 of file bvh_pbrt.cpp.

429 {
430  wxASSERT( totalNodes != nullptr );
431  wxASSERT( start >= 0 );
432  wxASSERT( end >= 0 );
433  wxASSERT( start != end );
434  wxASSERT( start < end );
435  wxASSERT( start <= (int)primitiveInfo.size() );
436  wxASSERT( end <= (int)primitiveInfo.size() );
437 
438  (*totalNodes)++;
439 
440  // !TODO: implement an memory Arena
441  BVHBuildNode *node = static_cast<BVHBuildNode *>( malloc( sizeof( BVHBuildNode ) ) );
442  m_nodesToFree.push_back( node );
443 
444  node->bounds.Reset();
445  node->firstPrimOffset = 0;
446  node->nPrimitives = 0;
447  node->splitAxis = 0;
448  node->children[0] = nullptr;
449  node->children[1] = nullptr;
450 
451  // Compute bounds of all primitives in BVH node
452  BBOX_3D bounds;
453  bounds.Reset();
454 
455  for( int i = start; i < end; ++i )
456  bounds.Union( primitiveInfo[i].bounds );
457 
458  int nPrimitives = end - start;
459 
460  if( nPrimitives == 1 )
461  {
462  // Create leaf _BVHBuildNode_
463  int firstPrimOffset = orderedPrims.size();
464 
465  for( int i = start; i < end; ++i )
466  {
467  int primitiveNr = primitiveInfo[i].primitiveNumber;
468  wxASSERT( primitiveNr < (int)m_primitives.size() );
469  orderedPrims.push_back( m_primitives[ primitiveNr ] );
470  }
471 
472  node->InitLeaf( firstPrimOffset, nPrimitives, bounds );
473  }
474  else
475  {
476  // Compute bound of primitive centroids, choose split dimension _dim_
477  BBOX_3D centroidBounds;
478  centroidBounds.Reset();
479 
480  for( int i = start; i < end; ++i )
481  centroidBounds.Union( primitiveInfo[i].centroid );
482 
483  const int dim = centroidBounds.MaxDimension();
484 
485  // Partition primitives into two sets and build children
486  int mid = (start + end) / 2;
487 
488  if( fabs( centroidBounds.Max()[dim] -
489  centroidBounds.Min()[dim] ) < (FLT_EPSILON + FLT_EPSILON) )
490  {
491  // Create leaf _BVHBuildNode_
492  const int firstPrimOffset = orderedPrims.size();
493 
494  for( int i = start; i < end; ++i )
495  {
496  int primitiveNr = primitiveInfo[i].primitiveNumber;
497 
498  wxASSERT( ( primitiveNr >= 0 ) && ( primitiveNr < (int) m_primitives.size() ) );
499 
500  const OBJECT_3D* obj = static_cast<const OBJECT_3D*>( m_primitives[ primitiveNr ] );
501 
502  wxASSERT( obj != nullptr );
503 
504  orderedPrims.push_back( obj );
505  }
506 
507  node->InitLeaf( firstPrimOffset, nPrimitives, bounds );
508  }
509  else
510  {
511  // Partition primitives based on _splitMethod_
512  switch( m_splitMethod )
513  {
514  case SPLITMETHOD::MIDDLE:
515  {
516  // Partition primitives through node's midpoint
517  float pmid = centroidBounds.GetCenter( dim );
518 
519  BVHPrimitiveInfo *midPtr = std::partition( &primitiveInfo[start],
520  &primitiveInfo[end - 1] + 1,
521  CompareToMid( dim, pmid ) );
522  mid = midPtr - &primitiveInfo[0];
523 
524  wxASSERT( ( mid >= start ) && ( mid <= end ) );
525 
526  if( ( mid != start ) && ( mid != end ) )
527  break;
528  }
529 
530  // Intentionally fall through to SPLITMETHOD::EQUAL_COUNTS since prims
531  // with large overlapping bounding boxes may fail to partition
533 
535  {
536  // Partition primitives into equally-sized subsets
537  mid = ( start + end ) / 2;
538 
539  std::nth_element( &primitiveInfo[start], &primitiveInfo[mid],
540  &primitiveInfo[end - 1] + 1, ComparePoints( dim ) );
541 
542  break;
543  }
544 
545  case SPLITMETHOD::SAH:
546  default:
547  {
548  // Partition primitives using approximate SAH
549  if( nPrimitives <= 2 )
550  {
551  // Partition primitives into equally-sized subsets
552  mid = ( start + end ) / 2;
553 
554  std::nth_element( &primitiveInfo[start], &primitiveInfo[mid],
555  &primitiveInfo[end - 1] + 1, ComparePoints( dim ) );
556  }
557  else
558  {
559  // Allocate _BucketInfo_ for SAH partition buckets
560  const int nBuckets = 12;
561 
562  BucketInfo buckets[nBuckets];
563 
564  for( int i = 0; i < nBuckets; ++i )
565  {
566  buckets[i].count = 0;
567  buckets[i].bounds.Reset();
568  }
569 
570  // Initialize _BucketInfo_ for SAH partition buckets
571  for( int i = start; i < end; ++i )
572  {
573  int b = nBuckets *
574  centroidBounds.Offset( primitiveInfo[i].centroid )[dim];
575 
576  if( b == nBuckets )
577  b = nBuckets - 1;
578 
579  wxASSERT( b >= 0 && b < nBuckets );
580 
581  buckets[b].count++;
582  buckets[b].bounds.Union( primitiveInfo[i].bounds );
583  }
584 
585  // Compute costs for splitting after each bucket
586  float cost[nBuckets - 1];
587 
588  for( int i = 0; i < ( nBuckets - 1 ); ++i )
589  {
590  BBOX_3D b0, b1;
591 
592  b0.Reset();
593  b1.Reset();
594 
595  int count0 = 0;
596  int count1 = 0;
597 
598  for( int j = 0; j <= i; ++j )
599  {
600  if( buckets[j].count )
601  {
602  count0 += buckets[j].count;
603  b0.Union( buckets[j].bounds );
604  }
605  }
606 
607  for( int j = i + 1; j < nBuckets; ++j )
608  {
609  if( buckets[j].count )
610  {
611  count1 += buckets[j].count;
612  b1.Union( buckets[j].bounds );
613  }
614  }
615 
616  cost[i] = 1.0f + ( count0 * b0.SurfaceArea() +
617  count1 * b1.SurfaceArea() ) / bounds.SurfaceArea();
618  }
619 
620  // Find bucket to split at that minimizes SAH metric
621  float minCost = cost[0];
622  int minCostSplitBucket = 0;
623 
624  for( int i = 1; i < ( nBuckets - 1 ); ++i )
625  {
626  if( cost[i] < minCost )
627  {
628  minCost = cost[i];
629  minCostSplitBucket = i;
630  }
631  }
632 
633  // Either create leaf or split primitives at selected SAH bucket
634  if( ( nPrimitives > m_maxPrimsInNode ) || ( minCost < (float) nPrimitives ) )
635  {
636  BVHPrimitiveInfo *pmid =
637  std::partition( &primitiveInfo[start], &primitiveInfo[end - 1] + 1,
638  CompareToBucket( minCostSplitBucket, nBuckets,
639  dim, centroidBounds ) );
640  mid = pmid - &primitiveInfo[0];
641 
642  wxASSERT( ( mid >= start ) && ( mid <= end ) );
643  }
644  else
645  {
646  // Create leaf _BVHBuildNode_
647  const int firstPrimOffset = orderedPrims.size();
648 
649  for( int i = start; i < end; ++i )
650  {
651  const int primitiveNr = primitiveInfo[i].primitiveNumber;
652 
653  wxASSERT( primitiveNr < (int)m_primitives.size() );
654 
655  orderedPrims.push_back( m_primitives[ primitiveNr ] );
656  }
657 
658  node->InitLeaf( firstPrimOffset, nPrimitives, bounds );
659 
660  return node;
661  }
662  }
663  break;
664  }
665  }
666 
667  node->InitInterior( dim, recursiveBuild( primitiveInfo, start, mid, totalNodes,
668  orderedPrims ),
669  recursiveBuild( primitiveInfo, mid, end, totalNodes,
670  orderedPrims) );
671  }
672  }
673 
674  return node;
675 }
unsigned int MaxDimension() const
Definition: bbox_3d.cpp:151
BBOX_3D bounds
Definition: bvh_pbrt.cpp:422
const SFVEC3F & Max() const
Return the maximum vertex pointer.
Definition: bbox_3d.h:198
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
void InitLeaf(int first, int n, const BBOX_3D &b)
Definition: bvh_pbrt.cpp:109
SPLITMETHOD m_splitMethod
Definition: bvh_pbrt.h:143
BVHBuildNode * recursiveBuild(std::vector< BVHPrimitiveInfo > &primitiveInfo, int start, int end, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims)
Definition: bvh_pbrt.cpp:426
Manage a bounding box defined by two SFVEC3F min max points.
Definition: bbox_3d.h:41
#define KI_FALLTHROUGH
The KI_FALLTHROUGH macro is to be used when switch statement cases should purposely fallthrough from ...
Definition: macros.h:83
int firstPrimOffset
Definition: bvh_pbrt.cpp:129
SFVEC3F Offset(const SFVEC3F &p) const
Definition: bbox_3d.cpp:251
void InitInterior(int axis, BVHBuildNode *c0, BVHBuildNode *c1)
Definition: bvh_pbrt.cpp:117
void Union(const SFVEC3F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_3d.cpp:102
float SurfaceArea() const
Definition: bbox_3d.cpp:174
const SFVEC3F & Min() const
Return the minimum vertex pointer.
Definition: bbox_3d.h:191
SFVEC3F GetCenter() const
Return the center point of the bounding box.
Definition: bbox_3d.cpp:132
BBOX_3D bounds
Definition: bvh_pbrt.cpp:127
const int m_maxPrimsInNode
Definition: bvh_pbrt.h:142
BVHBuildNode * children[2]
Definition: bvh_pbrt.cpp:128
std::list< void * > m_nodesToFree
Definition: bvh_pbrt.h:147
void Reset()
Reset the bounding box to zero and de-initialize it.
Definition: bbox_3d.cpp:95

References BVHBuildNode::bounds, BucketInfo::bounds, BVHBuildNode::children, BucketInfo::count, EQUALCOUNTS, BVHBuildNode::firstPrimOffset, BBOX_3D::GetCenter(), BVHBuildNode::InitInterior(), BVHBuildNode::InitLeaf(), KI_FALLTHROUGH, m_maxPrimsInNode, m_nodesToFree, m_primitives, m_splitMethod, BBOX_3D::Max(), BBOX_3D::MaxDimension(), MIDDLE, BBOX_3D::Min(), BVHBuildNode::nPrimitives, BBOX_3D::Offset(), BBOX_3D::Reset(), SAH, BVHBuildNode::splitAxis, BBOX_3D::SurfaceArea(), and BBOX_3D::Union().

Referenced by BVH_PBRT().

Member Data Documentation

◆ m_bbox

BBOX_3D ACCELERATOR_3D::m_bbox
protectedinherited

Definition at line 53 of file accelerator_3d.h.

Referenced by ACCELERATOR_3D::ACCELERATOR_3D().

◆ m_I

unsigned int BVH_PBRT::m_I[RAYPACKET_RAYS_PER_PACKET]
private

Definition at line 150 of file bvh_pbrt.h.

Referenced by BVH_PBRT().

◆ m_maxPrimsInNode

const int BVH_PBRT::m_maxPrimsInNode
private

Definition at line 142 of file bvh_pbrt.h.

Referenced by emitLBVH(), and recursiveBuild().

◆ m_nodes

LinearBVHNode* BVH_PBRT::m_nodes
private

Definition at line 145 of file bvh_pbrt.h.

Referenced by BVH_PBRT(), flattenBVHTree(), Intersect(), and IntersectP().

◆ m_nodesToFree

std::list<void*> BVH_PBRT::m_nodesToFree
private

Definition at line 147 of file bvh_pbrt.h.

Referenced by buildUpperSAH(), BVH_PBRT(), HLBVHBuild(), recursiveBuild(), and ~BVH_PBRT().

◆ m_primitives

CONST_VECTOR_OBJECT BVH_PBRT::m_primitives
private

Definition at line 144 of file bvh_pbrt.h.

Referenced by BVH_PBRT(), emitLBVH(), HLBVHBuild(), Intersect(), IntersectP(), and recursiveBuild().

◆ m_splitMethod

SPLITMETHOD BVH_PBRT::m_splitMethod
private

Definition at line 143 of file bvh_pbrt.h.

Referenced by BVH_PBRT(), and recursiveBuild().


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