70 #include "../../../3d_fastmath.h" 73 #include <boost/range/algorithm/nth_element.hpp> 74 #include <boost/range/algorithm/partition.hpp> 81 #ifdef PRINT_STATISTICS_3D_VIEWER 98 centroid( .5f * aBounds.Min() + .5f * aBounds.Max() ) {}
150 wxASSERT( x <= (1 << 10) );
152 if( x == ( 1 << 10 ) )
155 x = ( x | ( x << 16 ) ) & 0b00000011000000000000000011111111;
157 x = ( x | ( x << 8 ) ) & 0b00000011000000001111000000001111;
159 x = ( x | ( x << 4 ) ) & 0b00000011000011000011000011000011;
161 x = ( x | ( x << 2 ) ) & 0b00001001001001001001001001001001;
170 wxASSERT( v.x >= 0 && v.x <= ( 1 << 10 ) );
171 wxASSERT( v.y >= 0 && v.y <= ( 1 << 10 ) );
172 wxASSERT( v.z >= 0 && v.z <= ( 1 << 10 ) );
178 static void RadixSort( std::vector<MortonPrimitive>* v )
180 std::vector<MortonPrimitive> tempVector( v->size() );
182 const int bitsPerPass = 6;
183 const int nBits = 30;
185 wxASSERT( ( nBits % bitsPerPass ) == 0 );
187 const int nPasses = nBits / bitsPerPass;
189 for(
int pass = 0; pass < nPasses; ++pass )
192 const int lowBit = pass * bitsPerPass;
195 std::vector<MortonPrimitive>& in = ( pass & 1 ) ? tempVector : *v;
196 std::vector<MortonPrimitive>& out = ( pass & 1 ) ? *v : tempVector;
199 const int nBuckets = 1 << bitsPerPass;
200 int bucketCount[nBuckets] = {0};
201 const int bitMask = ( 1 << bitsPerPass ) - 1;
203 for( uint32_t i = 0; i < in.size(); ++i )
206 int bucket = ( mp.
mortonCode >> lowBit ) & bitMask;
208 wxASSERT( ( bucket >= 0 ) && ( bucket < nBuckets ) );
210 ++bucketCount[bucket];
214 int startIndex[nBuckets];
217 for(
int i = 1; i < nBuckets; ++i )
218 startIndex[i] = startIndex[i - 1] + bucketCount[i - 1];
221 for( uint32_t i = 0; i < in.size(); ++i )
224 int bucket = (mp.
mortonCode >> lowBit) & bitMask;
225 out[startIndex[bucket]++] = mp;
231 std::swap( *v, tempVector );
237 m_maxPrimsInNode(
std::min( 255, aMaxPrimsInNode ) ),
238 m_splitMethod( aSplitMethod )
240 if( aObjectContainer.
GetList().empty() )
259 std::vector<BVHPrimitiveInfo> primitiveInfo(
m_primitives.size() );
272 orderedPrims.clear();
278 root =
HLBVHBuild( primitiveInfo, &totalNodes, orderedPrims );
290 for(
int i = 0; i < totalNodes; ++i )
302 wxASSERT( offset == (
unsigned int)totalNodes );
379 wxASSERT( ( b >= 0 ) && ( b <
nBuckets ) );
427 int start,
int end,
int* totalNodes,
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() );
455 for(
int i = start; i < end; ++i )
456 bounds.
Union( primitiveInfo[i].bounds );
458 int nPrimitives = end - start;
460 if( nPrimitives == 1 )
463 int firstPrimOffset = orderedPrims.size();
465 for(
int i = start; i < end; ++i )
467 int primitiveNr = primitiveInfo[i].primitiveNumber;
472 node->
InitLeaf( firstPrimOffset, nPrimitives, bounds );
478 centroidBounds.
Reset();
480 for(
int i = start; i < end; ++i )
481 centroidBounds.
Union( primitiveInfo[i].centroid );
486 int mid = (start + end) / 2;
488 if( fabs( centroidBounds.
Max()[dim] -
489 centroidBounds.
Min()[dim] ) < (FLT_EPSILON + FLT_EPSILON) )
492 const int firstPrimOffset = orderedPrims.size();
494 for(
int i = start; i < end; ++i )
496 int primitiveNr = primitiveInfo[i].primitiveNumber;
498 wxASSERT( ( primitiveNr >= 0 ) && ( primitiveNr < (
int)
m_primitives.size() ) );
502 wxASSERT( obj !=
nullptr );
504 orderedPrims.push_back( obj );
507 node->
InitLeaf( firstPrimOffset, nPrimitives, bounds );
517 float pmid = centroidBounds.
GetCenter( dim );
520 &primitiveInfo[end - 1] + 1,
522 mid = midPtr - &primitiveInfo[0];
524 wxASSERT( ( mid >= start ) && ( mid <= end ) );
526 if( ( mid != start ) && ( mid != end ) )
537 mid = ( start + end ) / 2;
539 std::nth_element( &primitiveInfo[start], &primitiveInfo[mid],
549 if( nPrimitives <= 2 )
552 mid = ( start + end ) / 2;
554 std::nth_element( &primitiveInfo[start], &primitiveInfo[mid],
560 const int nBuckets = 12;
564 for(
int i = 0; i < nBuckets; ++i )
566 buckets[i].
count = 0;
571 for(
int i = start; i < end; ++i )
574 centroidBounds.
Offset( primitiveInfo[i].centroid )[dim];
579 wxASSERT( b >= 0 && b < nBuckets );
582 buckets[b].
bounds.
Union( primitiveInfo[i].bounds );
586 float cost[nBuckets - 1];
588 for(
int i = 0; i < ( nBuckets - 1 ); ++i )
598 for(
int j = 0; j <= i; ++j )
600 if( buckets[j].count )
602 count0 += buckets[j].
count;
603 b0.
Union( buckets[j].bounds );
607 for(
int j = i + 1; j < nBuckets; ++j )
609 if( buckets[j].count )
611 count1 += buckets[j].
count;
612 b1.
Union( buckets[j].bounds );
621 float minCost = cost[0];
622 int minCostSplitBucket = 0;
624 for(
int i = 1; i < ( nBuckets - 1 ); ++i )
626 if( cost[i] < minCost )
629 minCostSplitBucket = i;
634 if( ( nPrimitives >
m_maxPrimsInNode ) || ( minCost < (float) nPrimitives ) )
637 std::partition( &primitiveInfo[start], &primitiveInfo[end - 1] + 1,
639 dim, centroidBounds ) );
640 mid = pmid - &primitiveInfo[0];
642 wxASSERT( ( mid >= start ) && ( mid <= end ) );
647 const int firstPrimOffset = orderedPrims.size();
649 for(
int i = start; i < end; ++i )
651 const int primitiveNr = primitiveInfo[i].primitiveNumber;
658 node->
InitLeaf( firstPrimOffset, nPrimitives, bounds );
685 for(
unsigned int i = 0; i < primitiveInfo.size(); ++i )
686 bounds.
Union( primitiveInfo[i].centroid );
689 std::vector<MortonPrimitive> mortonPrims( primitiveInfo.size() );
691 for(
int i = 0; i < (int)primitiveInfo.size(); ++i )
694 const int mortonBits = 10;
695 const int mortonScale = 1 << mortonBits;
697 wxASSERT( primitiveInfo[i].primitiveNumber < (
int)primitiveInfo.size() );
699 mortonPrims[i].primitiveIndex = primitiveInfo[i].primitiveNumber;
701 const SFVEC3F centroidOffset = bounds.
Offset( primitiveInfo[i].centroid );
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 ) );
716 std::vector<LBVHTreelet> treeletsToBuild;
718 for(
int start = 0, end = 1; end <= (int)mortonPrims.size(); ++end )
720 const uint32_t mask = 0b00111111111111000000000000000000;
722 if( ( end == (
int) mortonPrims.size() )
723 || ( ( mortonPrims[start].mortonCode & mask )
724 != ( mortonPrims[end].mortonCode & mask ) ) )
727 const int numPrimitives = end - start;
728 const int maxBVHNodes = 2 * numPrimitives;
731 BVHBuildNode *nodes = static_cast<BVHBuildNode *>( malloc( maxBVHNodes *
736 for(
int i = 0; i < maxBVHNodes; ++i )
752 treeletsToBuild.push_back( tmpTreelet );
760 int orderedPrimsOffset = 0;
764 for(
int index = 0; index < (int)treeletsToBuild.size(); ++index )
767 int nodesCreated = 0;
768 const int firstBit = 29 - 12;
772 wxASSERT( tr.
startIndex < (
int)mortonPrims.size() );
776 &orderedPrimsOffset, firstBit );
778 atomicTotal += nodesCreated;
781 *totalNodes = atomicTotal;
784 std::vector<BVHBuildNode *> finishedTreelets;
785 finishedTreelets.reserve( treeletsToBuild.size() );
787 for(
int index = 0; index < (int)treeletsToBuild.size(); ++index )
788 finishedTreelets.push_back( treeletsToBuild[index].buildNodes );
791 return buildUpperSAH( finishedTreelets, 0, finishedTreelets.size(), totalNodes );
796 const std::vector<BVHPrimitiveInfo>& primitiveInfo,
801 wxASSERT( nPrimitives > 0 );
802 wxASSERT( totalNodes !=
nullptr );
803 wxASSERT( orderedPrimsOffset !=
nullptr );
804 wxASSERT( nPrimitives > 0 );
805 wxASSERT( mortonPrims !=
nullptr );
816 int firstPrimOffset = *orderedPrimsOffset;
817 *orderedPrimsOffset += nPrimitives;
819 wxASSERT( ( firstPrimOffset + ( nPrimitives - 1 ) ) < (
int) orderedPrims.size() );
821 for(
int i = 0; i < nPrimitives; ++i )
827 orderedPrims[firstPrimOffset + i] =
m_primitives[primitiveIndex];
828 bounds.
Union( primitiveInfo[primitiveIndex].bounds );
831 node->
InitLeaf( firstPrimOffset, nPrimitives, bounds );
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 );
847 int searchEnd = nPrimitives - 1;
849 while( searchStart + 1 != searchEnd )
851 wxASSERT(searchStart != searchEnd);
853 const int mid = ( searchStart + searchEnd ) / 2;
855 if( ( mortonPrims[searchStart].mortonCode & mask ) ==
860 wxASSERT( ( mortonPrims[mid].mortonCode & mask ) ==
861 ( mortonPrims[searchEnd].mortonCode & mask ) );
866 const int splitOffset = searchEnd;
868 wxASSERT( splitOffset <= ( nPrimitives - 1 ) );
869 wxASSERT( ( mortonPrims[splitOffset - 1].mortonCode & mask )
870 != ( mortonPrims[splitOffset].mortonCode & mask ) );
878 lbvh[0] =
emitLBVH( buildNodes, primitiveInfo, mortonPrims, splitOffset,
879 totalNodes, orderedPrims, orderedPrimsOffset, bit - 1 );
881 lbvh[1] =
emitLBVH( buildNodes, primitiveInfo, &mortonPrims[splitOffset],
882 nPrimitives - splitOffset, totalNodes, orderedPrims,
883 orderedPrimsOffset, bit - 1 );
885 const int axis = bit % 3;
895 int end,
int* totalNodes )
897 wxASSERT( totalNodes !=
nullptr );
898 wxASSERT( start < end );
899 wxASSERT( end <= (
int)treeletRoots.size() );
901 int nNodes = end - start;
904 return treeletRoots[start];
923 for(
int i = start; i < end; ++i )
924 bounds.
Union( treeletRoots[i]->bounds );
928 centroidBounds.
Reset();
930 for(
int i = start; i < end; ++i )
932 SFVEC3F centroid = ( treeletRoots[i]->bounds.Min() + treeletRoots[i]->bounds.Max() ) * 0.5f;
934 centroidBounds.
Union( centroid );
941 wxASSERT( centroidBounds.
Max()[dim] != centroidBounds.
Min()[dim] );
944 const int nBuckets = 12;
948 for(
int i = 0; i < nBuckets; ++i )
950 buckets[i].
count = 0;
955 for(
int i = start; i < end; ++i )
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] ) );
965 wxASSERT( ( b >= 0 ) && ( b < nBuckets ) );
968 buckets[b].
bounds.
Union( treeletRoots[i]->bounds );
972 float cost[nBuckets - 1];
974 for(
int i = 0; i < nBuckets - 1; ++i )
980 int count0 = 0, count1 = 0;
982 for(
int j = 0; j <= i; ++j )
984 if( buckets[j].count )
986 count0 += buckets[j].
count;
987 b0.
Union( buckets[j].bounds );
991 for(
int j = i + 1; j < nBuckets; ++j )
993 if( buckets[j].count )
995 count1 += buckets[j].
count;
996 b1.
Union( buckets[j].bounds );
1005 float minCost = cost[0];
1006 int minCostSplitBucket = 0;
1008 for(
int i = 1; i < nBuckets - 1; ++i )
1010 if( cost[i] < minCost )
1013 minCostSplitBucket = i;
1018 BVHBuildNode **pmid = std::partition( &treeletRoots[start], &treeletRoots[end - 1] + 1,
1020 dim, centroidBounds ) );
1022 const int mid = pmid - &treeletRoots[0];
1024 wxASSERT( ( mid > start ) && ( mid < end ) );
1040 int myOffset = (*offset)++;
1063 #define MAX_TODOS 64 1074 int todoOffset = 0, nodeNum = 0;
1084 float hitBox = 0.0f;
1088 if( hitted && ( hitBox < aHitInfo.
m_tHit ) )
1107 todo[todoOffset++] = nodeNum + 1;
1113 nodeNum = nodeNum + 1;
1120 if( todoOffset == 0 )
1123 nodeNum = todo[--todoOffset];
1139 int todoOffset = 0, nodeNum = aAccNodeInfo;
1149 float hitBox = 0.0f;
1153 if( hitted && ( hitBox < aHitInfo.
m_tHit ) )
1172 todo[todoOffset++] = nodeNum + 1;
1178 nodeNum = nodeNum + 1;
1185 if( todoOffset == 0 )
1188 nodeNum = todo[--todoOffset];
1201 int todoOffset = 0, nodeNum = 0;
1211 float hitBox = 0.0f;
1215 if( hitted && ( hitBox < aMaxDistance ) )
1234 todo[todoOffset++] = nodeNum + 1;
1240 nodeNum = nodeNum + 1;
1247 if( todoOffset == 0 )
1250 nodeNum = todo[--todoOffset];
bool operator()(const BVHPrimitiveInfo &a, const BVHPrimitiveInfo &b) const
unsigned int MaxDimension() const
const SFVEC3F & Max() const
Return the maximum vertex pointer.
CONST_VECTOR_OBJECT m_primitives
void InitLeaf(int first, int n, const BBOX_3D &b)
SPLITMETHOD m_splitMethod
uint16_t nPrimitives
0 -> interior node
BVHBuildNode * recursiveBuild(std::vector< BVHPrimitiveInfo > &primitiveInfo, int start, int end, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims)
Manage a bounding box defined by two SFVEC3F min max points.
bool Intersect(const RAY &aRay, float *t) const
uint8_t axis
interior node: xyz
BVHBuildNode * HLBVHBuild(const std::vector< BVHPrimitiveInfo > &primitiveInfo, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims)
const LIST_OBJECT & GetList() const
std::vector< const OBJECT_3D * > CONST_VECTOR_OBJECT
#define KI_FALLTHROUGH
The KI_FALLTHROUGH macro is to be used when switch statement cases should purposely fallthrough from ...
This BVH implementation is based on the source code implementation from the book "Physically Based Re...
SFVEC3F Offset(const SFVEC3F &p) const
bool operator()(const BVHPrimitiveInfo &p) const
float m_tHit
( 4) distance
void InitInterior(int axis, BVHBuildNode *c0, BVHBuildNode *c1)
void Union(const SFVEC3F &aPoint)
Recalculate the bounding box adding a point.
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.
static void RadixSort(std::vector< MortonPrimitive > *v)
float SurfaceArea() const
const SFVEC3F & Min() const
Return the minimum vertex pointer.
This file contains miscellaneous commonly used macros and functions.
SFVEC3F GetCenter() const
Return the center point of the bounding box.
BVHBuildNode * buildUpperSAH(std::vector< BVHBuildNode * > &treeletRoots, int start, int end, int *totalNodes)
const int m_maxPrimsInNode
unsigned int m_dirIsNeg[3]
BVHBuildNode * children[2]
bool IntersectP(const RAY &aRay, float aMaxDistance) const override
void ConvertTo(CONST_VECTOR_OBJECT &aOutVector) const
BVHBuildNode * buildNodes
uint32_t EncodeMorton3(const SFVEC3F &v)
HLBVH_SAH_Evaluator(int split, int num, int d, const BBOX_3D &b)
virtual bool IntersectP(const RAY &aRay, float aMaxDistance) const =0
void Set(const SFVEC3F &aPbMin, const SFVEC3F &aPbMax)
Set bounding box with new parameters.
uint32_t LeftShift3(uint32_t x)
const BBOX_3D & centroidBounds
std::list< void * > m_nodesToFree
BVHPrimitiveInfo(int aPrimitiveNumber, const BBOX_3D &aBounds)
Stores the hit information of a ray with a point on the surface of a object.
#define RAYPACKET_RAYS_PER_PACKET
CompareToMid(int d, float m)
unsigned int m_acc_node_info
( 4) The acc stores here the node that it hits
bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const override
int flattenBVHTree(BVHBuildNode *node, uint32_t *offset)
int secondChildOffset
interior
BVH_PBRT(const CONTAINER_3D_BASE &aObjectContainer, int aMaxPrimsInNode=4, SPLITMETHOD aSplitMethod=SPLITMETHOD::SAH)
bool operator()(const BVHPrimitiveInfo &a) const
CompareToBucket(int split, int num, int d, const BBOX_3D &b)
void Reset()
Reset the bounding box to zero and de-initialize it.
const BBOX_3D & centroidBounds
unsigned int m_I[RAYPACKET_RAYS_PER_PACKET]
bool GetCastShadows() const
bool operator()(const BVHBuildNode *node) const
static std::vector< std::string > split(const std::string &aStr, const std::string &aDelim)
Splits the input string into a vector of output strings.
const MATERIAL * GetMaterial() const