KiCad PCB EDA Suite
bvh_pbrt.cpp File Reference
#include "bvh_pbrt.h"
#include "../../../3d_fastmath.h"
#include <macros.h>
#include <boost/range/algorithm/nth_element.hpp>
#include <boost/range/algorithm/partition.hpp>
#include <cstdlib>
#include <vector>
#include <stack>
#include <wx/debug.h>

Go to the source code of this file.

Classes

struct  BVHPrimitiveInfo
 
struct  BVHBuildNode
 
struct  MortonPrimitive
 
struct  LBVHTreelet
 
struct  ComparePoints
 
struct  CompareToMid
 
struct  CompareToBucket
 
struct  HLBVH_SAH_Evaluator
 
struct  BucketInfo
 

Macros

#define MAX_TODOS   64
 

Functions

uint32_t LeftShift3 (uint32_t x)
 
uint32_t EncodeMorton3 (const SFVEC3F &v)
 
static void RadixSort (std::vector< MortonPrimitive > *v)
 

Macro Definition Documentation

◆ MAX_TODOS

#define MAX_TODOS   64

Definition at line 1063 of file bvh_pbrt.cpp.

Function Documentation

◆ EncodeMorton3()

uint32_t EncodeMorton3 ( const SFVEC3F v)
inline

Definition at line 168 of file bvh_pbrt.cpp.

169 {
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 ) );
173 
174  return ( LeftShift3( v.z ) << 2 ) | ( LeftShift3( v.y ) << 1 ) | LeftShift3( v.x );
175 }
uint32_t LeftShift3(uint32_t x)
Definition: bvh_pbrt.cpp:148

References LeftShift3().

Referenced by BVH_PBRT::HLBVHBuild().

◆ LeftShift3()

uint32_t LeftShift3 ( uint32_t  x)
inline

Definition at line 148 of file bvh_pbrt.cpp.

149 {
150  wxASSERT( x <= (1 << 10) );
151 
152  if( x == ( 1 << 10 ) )
153  --x;
154 
155  x = ( x | ( x << 16 ) ) & 0b00000011000000000000000011111111;
156  // x = ---- --98 ---- ---- ---- ---- 7654 3210
157  x = ( x | ( x << 8 ) ) & 0b00000011000000001111000000001111;
158  // x = ---- --98 ---- ---- 7654 ---- ---- 3210
159  x = ( x | ( x << 4 ) ) & 0b00000011000011000011000011000011;
160  // x = ---- --98 ---- 76-- --54 ---- 32-- --10
161  x = ( x | ( x << 2 ) ) & 0b00001001001001001001001001001001;
162  // x = ---- 9--8 --7- -6-- 5--4 --3- -2-- 1--0
163 
164  return x;
165 }

Referenced by EncodeMorton3().

◆ RadixSort()

static void RadixSort ( std::vector< MortonPrimitive > *  v)
static

Definition at line 178 of file bvh_pbrt.cpp.

179 {
180  std::vector<MortonPrimitive> tempVector( v->size() );
181 
182  const int bitsPerPass = 6;
183  const int nBits = 30;
184 
185  wxASSERT( ( nBits % bitsPerPass ) == 0 );
186 
187  const int nPasses = nBits / bitsPerPass;
188 
189  for( int pass = 0; pass < nPasses; ++pass )
190  {
191  // Perform one pass of radix sort, sorting _bitsPerPass_ bits
192  const int lowBit = pass * bitsPerPass;
193 
194  // Set in and out vector pointers for radix sort pass
195  std::vector<MortonPrimitive>& in = ( pass & 1 ) ? tempVector : *v;
196  std::vector<MortonPrimitive>& out = ( pass & 1 ) ? *v : tempVector;
197 
198  // Count number of zero bits in array for current radix sort bit
199  const int nBuckets = 1 << bitsPerPass;
200  int bucketCount[nBuckets] = {0};
201  const int bitMask = ( 1 << bitsPerPass ) - 1;
202 
203  for( uint32_t i = 0; i < in.size(); ++i )
204  {
205  const MortonPrimitive &mp = in[i];
206  int bucket = ( mp.mortonCode >> lowBit ) & bitMask;
207 
208  wxASSERT( ( bucket >= 0 ) && ( bucket < nBuckets ) );
209 
210  ++bucketCount[bucket];
211  }
212 
213  // Compute starting index in output array for each bucket
214  int startIndex[nBuckets];
215  startIndex[0] = 0;
216 
217  for( int i = 1; i < nBuckets; ++i )
218  startIndex[i] = startIndex[i - 1] + bucketCount[i - 1];
219 
220  // Store sorted values in output array
221  for( uint32_t i = 0; i < in.size(); ++i )
222  {
223  const MortonPrimitive& mp = in[i];
224  int bucket = (mp.mortonCode >> lowBit) & bitMask;
225  out[startIndex[bucket]++] = mp;
226  }
227  }
228 
229  // Copy final result from _tempVector_, if needed
230  if( nPasses & 1 )
231  std::swap( *v, tempVector );
232 }
uint32_t mortonCode
Definition: bvh_pbrt.cpp:136

References MortonPrimitive::mortonCode.

Referenced by BVH_PBRT::HLBVHBuild().