KiCad PCB EDA Suite
cbvh_pbrt.cpp File Reference

This BVH implementation is based on the source code implementation from the book "Physically Based Rendering" (v2 and v3) More...

#include "cbvh_pbrt.h"
#include "../../../3d_fastmath.h"
#include <vector>
#include <boost/range/algorithm/partition.hpp>
#include <boost/range/algorithm/nth_element.hpp>
#include <stdlib.h>
#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)
 

Detailed Description

This BVH implementation is based on the source code implementation from the book "Physically Based Rendering" (v2 and v3)

Adaptions performed for kicad:

  • Types and class types adapted to KiCad project
  • Convert some source to build in the C++ specification of KiCad
  • Code style to match KiCad
  • Asserts converted
  • Use compare functions/structures for std::partition and std::nth_element

The original source code has the following licence:

"pbrt source code is Copyright(c) 1998-2015 Matt Pharr, Greg Humphreys, and Wenzel Jakob.

This file is part of pbrt.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

  • Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
  • Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE."

Definition in file cbvh_pbrt.cpp.

Macro Definition Documentation

#define MAX_TODOS   64

Definition at line 1127 of file cbvh_pbrt.cpp.

Referenced by CBVH_PBRT::Intersect(), and CBVH_PBRT::IntersectP().

Function Documentation

uint32_t EncodeMorton3 ( const SFVEC3F v)
inline

Definition at line 166 of file cbvh_pbrt.cpp.

References LeftShift3().

Referenced by CBVH_PBRT::HLBVHBuild().

167 {
168  wxASSERT( v.x >= 0 && v.x <= (1 << 10) );
169  wxASSERT( v.y >= 0 && v.y <= (1 << 10) );
170  wxASSERT( v.z >= 0 && v.z <= (1 << 10) );
171 
172  return (LeftShift3(v.z) << 2) | (LeftShift3(v.y) << 1) | LeftShift3(v.x);
173 }
uint32_t LeftShift3(uint32_t x)
Definition: cbvh_pbrt.cpp:146
uint32_t LeftShift3 ( uint32_t  x)
inline

Definition at line 146 of file cbvh_pbrt.cpp.

Referenced by EncodeMorton3().

147 {
148  wxASSERT( x <= (1 << 10) );
149 
150  if( x == (1 << 10) )
151  --x;
152 
153  x = (x | (x << 16)) & 0b00000011000000000000000011111111;
154  // x = ---- --98 ---- ---- ---- ---- 7654 3210
155  x = (x | (x << 8)) & 0b00000011000000001111000000001111;
156  // x = ---- --98 ---- ---- 7654 ---- ---- 3210
157  x = (x | (x << 4)) & 0b00000011000011000011000011000011;
158  // x = ---- --98 ---- 76-- --54 ---- 32-- --10
159  x = (x | (x << 2)) & 0b00001001001001001001001001001001;
160  // x = ---- 9--8 --7- -6-- 5--4 --3- -2-- 1--0
161 
162  return x;
163 }
static void RadixSort ( std::vector< MortonPrimitive > *  v)
static

Definition at line 176 of file cbvh_pbrt.cpp.

References MortonPrimitive::mortonCode.

Referenced by CBVH_PBRT::HLBVHBuild().

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