KiCad PCB EDA Suite
cbvh_pbrt.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015-2016 Mario Luzeiro <mrluzeiro@ua.pt>
5  * Copyright (C) 1992-2016 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
69 #include "cbvh_pbrt.h"
70 #include "../../../3d_fastmath.h"
71 #include <macros.h>
72 
73 #include <boost/range/algorithm/nth_element.hpp>
74 #include <boost/range/algorithm/partition.hpp>
75 #include <cstdlib>
76 #include <vector>
77 
78 #include <stack>
79 #include <wx/debug.h>
80 
81 #ifdef PRINT_STATISTICS_3D_VIEWER
82 #include <stdio.h>
83 #endif
84 
85 // BVHAccel Local Declarations
87 {
89  {
90  primitiveNumber = 0;
91  bounds.Reset();
92  centroid = SFVEC3F( 0.0f );
93  }
94 
95  BVHPrimitiveInfo( int aPrimitiveNumber, const CBBOX &aBounds ) :
96  primitiveNumber( aPrimitiveNumber ),
97  bounds( aBounds ),
98  centroid( .5f * aBounds.Min() + .5f * aBounds.Max() ) {}
99 
103 };
104 
105 
107 {
108  // BVHBuildNode Public Methods
109  void InitLeaf( int first, int n, const CBBOX &b)
110  {
111  firstPrimOffset = first;
112  nPrimitives = n;
113  bounds = b;
114  children[0] = children[1] = NULL;
115  }
116 
117  void InitInterior( int axis, BVHBuildNode *c0, BVHBuildNode *c1 )
118  {
119  children[0] = c0;
120  children[1] = c1;
121  bounds.Set( c0->bounds );
122  bounds.Union( c1->bounds );
123  splitAxis = axis;
124  nPrimitives = 0;
125  }
126 
130 };
131 
132 
134 {
136  uint32_t mortonCode;
137 };
138 
139 
141 {
144 };
145 
146 
147 // BVHAccel Utility Functions
148 inline uint32_t LeftShift3( uint32_t x )
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 }
166 
167 
168 inline uint32_t EncodeMorton3( const SFVEC3F &v )
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 }
176 
177 
178 static void RadixSort( std::vector<MortonPrimitive> *v )
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 }
233 
234 
235 CBVH_PBRT::CBVH_PBRT( const CGENERICCONTAINER &aObjectContainer,
236  int aMaxPrimsInNode,
237  SPLITMETHOD aSplitMethod ) :
238  m_maxPrimsInNode( std::min( 255, aMaxPrimsInNode ) ),
239  m_splitMethod( aSplitMethod )
240 {
241  if( aObjectContainer.GetList().empty() )
242  {
243  m_nodes = NULL;
244 
245  return;
246  }
247 
248  // Initialize the indexes of ray packet for partition traversal
249  for( unsigned int i = 0; i < RAYPACKET_RAYS_PER_PACKET; ++i )
250  {
251  m_I[i] = i;
252  }
253 
254  // Convert the objects list to vector of objects
255  // /////////////////////////////////////////////////////////////////////////
256  aObjectContainer.ConvertTo( m_primitives );
257 
258  wxASSERT( aObjectContainer.GetList().size() == m_primitives.size() );
259 
260  // Initialize _primitiveInfo_ array for primitives
261  // /////////////////////////////////////////////////////////////////////////
262  std::vector<BVHPrimitiveInfo> primitiveInfo( m_primitives.size() );
263 
264  for( size_t i = 0; i < m_primitives.size(); ++i )
265  {
266  wxASSERT( m_primitives[i]->GetBBox().IsInitialized() );
267 
268  primitiveInfo[i] = BVHPrimitiveInfo( i, m_primitives[i]->GetBBox() );
269  }
270 
271  // Build BVH tree for primitives using _primitiveInfo_
272  int totalNodes = 0;
273 
274  CONST_VECTOR_OBJECT orderedPrims;
275  orderedPrims.clear();
276  orderedPrims.reserve( m_primitives.size() );
277 
278  BVHBuildNode *root;
279 
281  root = HLBVHBuild( primitiveInfo, &totalNodes, orderedPrims);
282  else
283  root = recursiveBuild( primitiveInfo, 0, m_primitives.size(),
284  &totalNodes, orderedPrims);
285 
286  wxASSERT( m_primitives.size() == orderedPrims.size() );
287 
288  m_primitives.swap( orderedPrims );
289 
290  // Compute representation of depth-first traversal of BVH tree
291  m_nodes = static_cast<LinearBVHNode *>( malloc( sizeof( LinearBVHNode ) *
292  totalNodes ) );
294 
295  for( int i = 0; i < totalNodes; ++i )
296  {
297  m_nodes[i].bounds.Reset();
298  m_nodes[i].primitivesOffset = 0;
299  m_nodes[i].nPrimitives = 0;
300  m_nodes[i].axis = 0;
301  }
302 
303  uint32_t offset = 0;
304 
305  flattenBVHTree( root, &offset );
306 
307  wxASSERT( offset == (unsigned int)totalNodes );
308 
309 #ifdef PRINT_STATISTICS_3D_VIEWER
310  uint32_t treeBytes = totalNodes * sizeof( LinearBVHNode ) + sizeof( *this ) +
311  m_primitives.size() * sizeof( m_primitives[0] ) +
312  m_addresses_pointer_to_mm_free.size() * sizeof( void * );
313 
314  printf( "////////////////////////////////////////////////////////////////////////////////\n" );
315  printf( "Creating a CBVH_PBRT from %u objects ", (unsigned int)m_primitives.size() );
316 
317  switch( m_splitMethod )
318  {
319  case SPLITMETHOD::MIDDLE:
320  printf( "using SPLITMETHOD::MIDDLE\n" );
321  break;
323  printf( "using SPLITMETHOD::EQUALCOUNTS\n" );
324  break;
325  case SPLITMETHOD::SAH:
326  printf( "using SPLITMETHOD::SAH\n" );
327  break;
328  case SPLITMETHOD::HLBVH:
329  printf( "using SPLITMETHOD::HLBVH\n" );
330  break;
331  }
332 
333  printf( " BVH created with %d nodes (%.2f MB)\n",
334  totalNodes, float(treeBytes) / (1024.f * 1024.f) );
335  printf( "////////////////////////////////////////////////////////////////////////////////\n\n" );
336 #endif
337 }
338 
339 
341 {
342  if( !m_addresses_pointer_to_mm_free.empty() )
343  {
344  for( std::list<void *>::iterator ii = m_addresses_pointer_to_mm_free.begin();
345  ii != m_addresses_pointer_to_mm_free.end();
346  ++ii )
347  {
348  free( *ii );
349  *ii = NULL;
350  }
351  }
352 
354 }
355 
356 
358 {
359  explicit ComparePoints(int d) { dim = d; }
360 
361  int dim;
362 
363  bool operator()( const BVHPrimitiveInfo &a,
364  const BVHPrimitiveInfo &b ) const
365  {
366  return a.centroid[dim] < b.centroid[dim];
367  }
368 };
369 
370 
372 {
373  explicit CompareToMid( int d, float m ) { dim = d; mid = m; }
374 
375  int dim;
376  float mid;
377 
378  bool operator()( const BVHPrimitiveInfo &a ) const
379  {
380  return a.centroid[dim] < mid;
381  }
382 };
383 
384 
386 {
387  CompareToBucket( int split, int num, int d, const CBBOX &b )
388  : centroidBounds(b)
389  { splitBucket = split; nBuckets = num; dim = d; }
390 
391  bool operator()(const BVHPrimitiveInfo &p) const;
392 
394 
396 };
397 
398 
400 {
401  const float centroid = p.centroid[dim];
402 
403  int b = nBuckets *
404  // Computes the offset (0.0 - 1.0) for one axis
405  ( ( centroid - centroidBounds.Min()[dim] ) /
406  ( centroidBounds.Max()[dim] - centroidBounds.Min()[dim] ) );
407 
408  if( b == nBuckets )
409  b = nBuckets - 1;
410 
411  wxASSERT( (b >= 0) && (b < nBuckets) );
412 
413  return b <= splitBucket;
414 }
415 
416 
418 {
419  HLBVH_SAH_Evaluator( int split, int num, int d, const CBBOX &b )
420  : centroidBounds(b)
421  { minCostSplitBucket = split; nBuckets = num; dim = d; }
422 
423  bool operator()(const BVHBuildNode *node) const;
424 
427 };
428 
429 
431 {
432  const float centroid = node->bounds.GetCenter( dim );
433 
434  int b = nBuckets *
435  // Computes the offset (0.0 - 1.0) for one axis
436  ( ( centroid - centroidBounds.Min()[dim] ) /
437  ( centroidBounds.Max()[dim] - centroidBounds.Min()[dim] ) );
438 
439  if( b == nBuckets )
440  b = nBuckets - 1;
441 
442  wxASSERT( b >= 0 && b < nBuckets );
443 
444  return b <= minCostSplitBucket;
445 }
446 
447 
449 {
450  int count;
452 };
453 
454 
455 BVHBuildNode *CBVH_PBRT::recursiveBuild ( std::vector<BVHPrimitiveInfo> &primitiveInfo,
456  int start,
457  int end,
458  int *totalNodes,
459  CONST_VECTOR_OBJECT &orderedPrims )
460 {
461  wxASSERT( totalNodes != NULL );
462  wxASSERT( start >= 0 );
463  wxASSERT( end >= 0 );
464  wxASSERT( start != end );
465  wxASSERT( start < end );
466  wxASSERT( start <= (int)primitiveInfo.size() );
467  wxASSERT( end <= (int)primitiveInfo.size() );
468 
469  (*totalNodes)++;
470 
471  // !TODO: implement an memory Arena
472  BVHBuildNode *node = static_cast<BVHBuildNode *>( malloc( sizeof( BVHBuildNode ) ) );
473  m_addresses_pointer_to_mm_free.push_back( node );
474 
475  node->bounds.Reset();
476  node->firstPrimOffset = 0;
477  node->nPrimitives = 0;
478  node->splitAxis = 0;
479  node->children[0] = NULL;
480  node->children[1] = NULL;
481 
482  // Compute bounds of all primitives in BVH node
483  CBBOX bounds;
484  bounds.Reset();
485 
486  for( int i = start; i < end; ++i )
487  bounds.Union( primitiveInfo[i].bounds );
488 
489  int nPrimitives = end - start;
490 
491  if( nPrimitives == 1 )
492  {
493  // Create leaf _BVHBuildNode_
494  int firstPrimOffset = orderedPrims.size();
495 
496  for( int i = start; i < end; ++i )
497  {
498  int primitiveNr = primitiveInfo[i].primitiveNumber;
499  wxASSERT( primitiveNr < (int)m_primitives.size() );
500  orderedPrims.push_back( m_primitives[ primitiveNr ] );
501  }
502 
503  node->InitLeaf( firstPrimOffset, nPrimitives, bounds );
504  }
505  else
506  {
507  // Compute bound of primitive centroids, choose split dimension _dim_
508  CBBOX centroidBounds;
509  centroidBounds.Reset();
510 
511  for( int i = start; i < end; ++i )
512  centroidBounds.Union( primitiveInfo[i].centroid );
513 
514  const int dim = centroidBounds.MaxDimension();
515 
516  // Partition primitives into two sets and build children
517  int mid = (start + end) / 2;
518 
519  if( fabs( centroidBounds.Max()[dim] -
520  centroidBounds.Min()[dim] ) < (FLT_EPSILON + FLT_EPSILON) )
521  {
522  // Create leaf _BVHBuildNode_
523  const int firstPrimOffset = orderedPrims.size();
524 
525  for( int i = start; i < end; ++i )
526  {
527  int primitiveNr = primitiveInfo[i].primitiveNumber;
528 
529  wxASSERT( (primitiveNr >= 0) &&
530  (primitiveNr < (int)m_primitives.size()) );
531 
532  const COBJECT *obj = static_cast<const COBJECT *>( m_primitives[ primitiveNr ] );
533 
534  wxASSERT( obj != NULL );
535 
536  orderedPrims.push_back( obj );
537  }
538 
539  node->InitLeaf( firstPrimOffset, nPrimitives, bounds );
540  }
541  else
542  {
543  // Partition primitives based on _splitMethod_
544  switch( m_splitMethod )
545  {
546  case SPLITMETHOD::MIDDLE:
547  {
548  // Partition primitives through node's midpoint
549  float pmid = centroidBounds.GetCenter( dim );
550 
551  BVHPrimitiveInfo *midPtr = std::partition( &primitiveInfo[start],
552  &primitiveInfo[end - 1] + 1,
553  CompareToMid( dim, pmid ) );
554  mid = midPtr - &primitiveInfo[0];
555 
556  wxASSERT( (mid >= start) &&
557  (mid <= end) );
558 
559  if( (mid != start) && (mid != end) )
560  break;
561  }
562 
563  // Intentionally fall through to SPLITMETHOD::EQUAL_COUNTS since prims
564  // with large overlapping bounding boxes may fail to partition
566 
568  {
569  // Partition primitives into equally-sized subsets
570  mid = (start + end) / 2;
571 
572  std::nth_element( &primitiveInfo[start],
573  &primitiveInfo[mid],
574  &primitiveInfo[end - 1] + 1,
575  ComparePoints( dim ) );
576 
577  break;
578  }
579 
580  case SPLITMETHOD::SAH:
581  default:
582  {
583  // Partition primitives using approximate SAH
584  if( nPrimitives <= 2 )
585  {
586  // Partition primitives into equally-sized subsets
587  mid = (start + end) / 2;
588 
589  std::nth_element( &primitiveInfo[start],
590  &primitiveInfo[mid],
591  &primitiveInfo[end - 1] + 1,
592  ComparePoints( dim ) );
593  }
594  else
595  {
596  // Allocate _BucketInfo_ for SAH partition buckets
597  const int nBuckets = 12;
598 
599  BucketInfo buckets[nBuckets];
600 
601  for( int i = 0; i < nBuckets; ++i )
602  {
603  buckets[i].count = 0;
604  buckets[i].bounds.Reset();
605  }
606 
607  // Initialize _BucketInfo_ for SAH partition buckets
608  for( int i = start; i < end; ++i )
609  {
610  int b = nBuckets *
611  centroidBounds.Offset( primitiveInfo[i].centroid )[dim];
612 
613  if( b == nBuckets )
614  b = nBuckets - 1;
615 
616  wxASSERT( b >= 0 && b < nBuckets );
617 
618  buckets[b].count++;
619  buckets[b].bounds.Union( primitiveInfo[i].bounds );
620  }
621 
622  // Compute costs for splitting after each bucket
623  float cost[nBuckets - 1];
624 
625  for( int i = 0; i < (nBuckets - 1); ++i )
626  {
627  CBBOX b0, b1;
628 
629  b0.Reset();
630  b1.Reset();
631 
632  int count0 = 0;
633  int count1 = 0;
634 
635  for( int j = 0; j <= i; ++j )
636  {
637  if( buckets[j].count )
638  {
639  count0 += buckets[j].count;
640  b0.Union( buckets[j].bounds );
641  }
642  }
643 
644  for( int j = i + 1; j < nBuckets; ++j )
645  {
646  if( buckets[j].count )
647  {
648  count1 += buckets[j].count;
649  b1.Union( buckets[j].bounds );
650  }
651  }
652 
653  cost[i] = 1.0f +
654  ( count0 * b0.SurfaceArea() +
655  count1 * b1.SurfaceArea() ) /
656  bounds.SurfaceArea();
657  }
658 
659  // Find bucket to split at that minimizes SAH metric
660  float minCost = cost[0];
661  int minCostSplitBucket = 0;
662 
663  for( int i = 1; i < (nBuckets - 1); ++i )
664  {
665  if( cost[i] < minCost )
666  {
667  minCost = cost[i];
668  minCostSplitBucket = i;
669  }
670  }
671 
672  // Either create leaf or split primitives at selected SAH
673  // bucket
674  if( (nPrimitives > m_maxPrimsInNode) ||
675  (minCost < (float)nPrimitives) )
676  {
677  BVHPrimitiveInfo *pmid =
678  std::partition( &primitiveInfo[start],
679  &primitiveInfo[end - 1] + 1,
680  CompareToBucket( minCostSplitBucket,
681  nBuckets,
682  dim,
683  centroidBounds ) );
684  mid = pmid - &primitiveInfo[0];
685 
686  wxASSERT( (mid >= start) &&
687  (mid <= end) );
688  }
689  else
690  {
691  // Create leaf _BVHBuildNode_
692  const int firstPrimOffset = orderedPrims.size();
693 
694  for( int i = start; i < end; ++i )
695  {
696  const int primitiveNr = primitiveInfo[i].primitiveNumber;
697 
698  wxASSERT( primitiveNr < (int)m_primitives.size() );
699 
700  orderedPrims.push_back( m_primitives[ primitiveNr ] );
701  }
702 
703  node->InitLeaf( firstPrimOffset, nPrimitives, bounds );
704 
705  return node;
706  }
707  }
708  break;
709  }
710  }
711 
712  node->InitInterior( dim,
713  recursiveBuild( primitiveInfo,
714  start,
715  mid,
716  totalNodes,
717  orderedPrims ),
718  recursiveBuild( primitiveInfo,
719  mid,
720  end,
721  totalNodes,
722  orderedPrims) );
723  }
724  }
725 
726  return node;
727 }
728 
729 
730 BVHBuildNode *CBVH_PBRT::HLBVHBuild( const std::vector<BVHPrimitiveInfo> &primitiveInfo,
731  int *totalNodes,
732  CONST_VECTOR_OBJECT &orderedPrims )
733 {
734  // Compute bounding box of all primitive centroids
735  CBBOX bounds;
736  bounds.Reset();
737 
738  for( unsigned int i = 0; i < primitiveInfo.size(); ++i )
739  bounds.Union( primitiveInfo[i].centroid );
740 
741  // Compute Morton indices of primitives
742  std::vector<MortonPrimitive> mortonPrims( primitiveInfo.size() );
743 
744  for( int i = 0; i < (int)primitiveInfo.size(); ++i )
745  {
746  // Initialize _mortonPrims[i]_ for _i_th primitive
747  const int mortonBits = 10;
748  const int mortonScale = 1 << mortonBits;
749 
750  wxASSERT( primitiveInfo[i].primitiveNumber < (int)primitiveInfo.size() );
751 
752  mortonPrims[i].primitiveIndex = primitiveInfo[i].primitiveNumber;
753 
754  const SFVEC3F centroidOffset = bounds.Offset( primitiveInfo[i].centroid );
755 
756  wxASSERT( (centroidOffset.x >= 0.0f) && (centroidOffset.x <= 1.0f) );
757  wxASSERT( (centroidOffset.y >= 0.0f) && (centroidOffset.y <= 1.0f) );
758  wxASSERT( (centroidOffset.z >= 0.0f) && (centroidOffset.z <= 1.0f) );
759 
760  mortonPrims[i].mortonCode = EncodeMorton3( centroidOffset *
761  SFVEC3F( (float)mortonScale ) );
762  }
763 
764  // Radix sort primitive Morton indices
765  RadixSort( &mortonPrims );
766 
767  // Create LBVH treelets at bottom of BVH
768 
769  // Find intervals of primitives for each treelet
770  std::vector<LBVHTreelet> treeletsToBuild;
771 
772  for( int start = 0, end = 1; end <= (int)mortonPrims.size(); ++end )
773  {
774  const uint32_t mask = 0b00111111111111000000000000000000;
775 
776  if( (end == (int)mortonPrims.size()) ||
777  ( (mortonPrims[start].mortonCode & mask) !=
778  (mortonPrims[end].mortonCode & mask) ) )
779  {
780  // Add entry to _treeletsToBuild_ for this treelet
781  const int numPrimitives = end - start;
782  const int maxBVHNodes = 2 * numPrimitives;
783 
784  // !TODO: implement a memory arena
785  BVHBuildNode *nodes = static_cast<BVHBuildNode *>( malloc( maxBVHNodes *
786  sizeof( BVHBuildNode ) ) );
787 
788  m_addresses_pointer_to_mm_free.push_back( nodes );
789 
790  for( int i = 0; i < maxBVHNodes; ++i )
791  {
792  nodes[i].bounds.Reset();
793  nodes[i].firstPrimOffset = 0;
794  nodes[i].nPrimitives = 0;
795  nodes[i].splitAxis = 0;
796  nodes[i].children[0] = NULL;
797  nodes[i].children[1] = NULL;
798  }
799 
800  LBVHTreelet tmpTreelet;
801 
802  tmpTreelet.startIndex = start;
803  tmpTreelet.numPrimitives = numPrimitives;
804  tmpTreelet.buildNodes = nodes;
805 
806  treeletsToBuild.push_back( tmpTreelet );
807 
808  start = end;
809  }
810  }
811 
812  // Create LBVHs for treelets in parallel
813  int atomicTotal = 0;
814  int orderedPrimsOffset = 0;
815 
816  orderedPrims.resize( m_primitives.size() );
817 
818  for( int index = 0; index < (int)treeletsToBuild.size(); ++index )
819  {
820  // Generate _index_th LBVH treelet
821  int nodesCreated = 0;
822  const int firstBit = 29 - 12;
823 
824  LBVHTreelet &tr = treeletsToBuild[index];
825 
826  wxASSERT( tr.startIndex < (int)mortonPrims.size() );
827 
828  tr.buildNodes = emitLBVH( tr.buildNodes,
829  primitiveInfo,
830  &mortonPrims[tr.startIndex],
831  tr.numPrimitives,
832  &nodesCreated,
833  orderedPrims,
834  &orderedPrimsOffset,
835  firstBit );
836 
837  atomicTotal += nodesCreated;
838  }
839 
840  *totalNodes = atomicTotal;
841 
842  // Initialize _finishedTreelets_ with treelet root node pointers
843  std::vector<BVHBuildNode *> finishedTreelets;
844  finishedTreelets.reserve( treeletsToBuild.size() );
845 
846  for( int index = 0; index < (int)treeletsToBuild.size(); ++index )
847  finishedTreelets.push_back( treeletsToBuild[index].buildNodes );
848 
849  // Create and return SAH BVH from LBVH treelets
850  return buildUpperSAH( finishedTreelets,
851  0,
852  finishedTreelets.size(),
853  totalNodes );
854 }
855 
856 
858  BVHBuildNode *&buildNodes,
859  const std::vector<BVHPrimitiveInfo> &primitiveInfo,
860  MortonPrimitive *mortonPrims, int nPrimitives, int *totalNodes,
861  CONST_VECTOR_OBJECT &orderedPrims,
862  int *orderedPrimsOffset, int bit)
863 {
864  wxASSERT( nPrimitives > 0 );
865  wxASSERT( totalNodes != NULL );
866  wxASSERT( orderedPrimsOffset != NULL );
867  wxASSERT( nPrimitives > 0 );
868  wxASSERT( mortonPrims != NULL );
869 
870  if( (bit == -1) || (nPrimitives < m_maxPrimsInNode) )
871  {
872  // Create and return leaf node of LBVH treelet
873  (*totalNodes)++;
874 
875  BVHBuildNode *node = buildNodes++;
876  CBBOX bounds;
877  bounds.Reset();
878 
879  int firstPrimOffset = *orderedPrimsOffset;
880  *orderedPrimsOffset += nPrimitives;
881 
882  wxASSERT( (firstPrimOffset + (nPrimitives - 1)) < (int)orderedPrims.size() );
883 
884  for( int i = 0; i < nPrimitives; ++i )
885  {
886  const int primitiveIndex = mortonPrims[i].primitiveIndex;
887 
888  wxASSERT( primitiveIndex < (int)m_primitives.size() );
889 
890  orderedPrims[firstPrimOffset + i] = m_primitives[primitiveIndex];
891  bounds.Union( primitiveInfo[primitiveIndex].bounds );
892  }
893 
894  node->InitLeaf( firstPrimOffset, nPrimitives, bounds );
895 
896  return node;
897  }
898  else
899  {
900  int mask = 1 << bit;
901 
902  // Advance to next subtree level if there's no LBVH split for this bit
903  if( (mortonPrims[0].mortonCode & mask) ==
904  (mortonPrims[nPrimitives - 1].mortonCode & mask) )
905  return emitLBVH( buildNodes, primitiveInfo, mortonPrims, nPrimitives,
906  totalNodes, orderedPrims, orderedPrimsOffset,
907  bit - 1 );
908 
909  // Find LBVH split point for this dimension
910  int searchStart = 0;
911  int searchEnd = nPrimitives - 1;
912 
913  while( searchStart + 1 != searchEnd )
914  {
915  wxASSERT(searchStart != searchEnd);
916 
917  const int mid = (searchStart + searchEnd) / 2;
918 
919  if( (mortonPrims[searchStart].mortonCode & mask) ==
920  (mortonPrims[mid].mortonCode & mask) )
921  searchStart = mid;
922  else
923  {
924  wxASSERT( (mortonPrims[mid].mortonCode & mask) ==
925  (mortonPrims[searchEnd].mortonCode & mask) );
926  searchEnd = mid;
927  }
928  }
929 
930  const int splitOffset = searchEnd;
931 
932  wxASSERT( splitOffset <= (nPrimitives - 1) );
933  wxASSERT( (mortonPrims[splitOffset - 1].mortonCode & mask) !=
934  (mortonPrims[splitOffset].mortonCode & mask) );
935 
936  // Create and return interior LBVH node
937  (*totalNodes)++;
938 
939  BVHBuildNode *node = buildNodes++;
940  BVHBuildNode *lbvh[2];
941 
942  lbvh[0] = emitLBVH( buildNodes, primitiveInfo, mortonPrims, splitOffset,
943  totalNodes, orderedPrims, orderedPrimsOffset, bit - 1 );
944 
945  lbvh[1] = emitLBVH( buildNodes, primitiveInfo, &mortonPrims[splitOffset],
946  nPrimitives - splitOffset, totalNodes, orderedPrims,
947  orderedPrimsOffset, bit - 1 );
948 
949  const int axis = bit % 3;
950 
951  node->InitInterior( axis, lbvh[0], lbvh[1] );
952 
953  return node;
954  }
955 }
956 
957 
959  std::vector<BVHBuildNode *> &treeletRoots,
960  int start, int end,
961  int *totalNodes )
962 {
963  wxASSERT( totalNodes != NULL );
964  wxASSERT( start < end );
965  wxASSERT( end <= (int)treeletRoots.size() );
966 
967  int nNodes = end - start;
968 
969  if( nNodes == 1 )
970  return treeletRoots[start];
971 
972 
973  (*totalNodes)++;
974 
975  BVHBuildNode *node = static_cast<BVHBuildNode *>( malloc( sizeof( BVHBuildNode ) ) );
976 
977  m_addresses_pointer_to_mm_free.push_back( node );
978 
979  node->bounds.Reset();
980  node->firstPrimOffset = 0;
981  node->nPrimitives = 0;
982  node->splitAxis = 0;
983  node->children[0] = NULL;
984  node->children[1] = NULL;
985 
986  // Compute bounds of all nodes under this HLBVH node
987  CBBOX bounds;
988  bounds.Reset();
989 
990  for( int i = start; i < end; ++i )
991  bounds.Union( treeletRoots[i]->bounds );
992 
993  // Compute bound of HLBVH node centroids, choose split dimension _dim_
994  CBBOX centroidBounds;
995  centroidBounds.Reset();
996 
997  for( int i = start; i < end; ++i )
998  {
999  SFVEC3F centroid =
1000  (treeletRoots[i]->bounds.Min() + treeletRoots[i]->bounds.Max()) *
1001  0.5f;
1002 
1003  centroidBounds.Union(centroid);
1004  }
1005 
1006  const int dim = centroidBounds.MaxDimension();
1007 
1008  // FIXME: if this hits, what do we need to do?
1009  // Make sure the SAH split below does something... ?
1010  wxASSERT( centroidBounds.Max()[dim] != centroidBounds.Min()[dim] );
1011 
1012  // Allocate _BucketInfo_ for SAH partition buckets
1013  const int nBuckets = 12;
1014 
1015  BucketInfo buckets[nBuckets];
1016 
1017  for( int i = 0; i < nBuckets; ++i )
1018  {
1019  buckets[i].count = 0;
1020  buckets[i].bounds.Reset();
1021  }
1022 
1023  // Initialize _BucketInfo_ for HLBVH SAH partition buckets
1024  for( int i = start; i < end; ++i )
1025  {
1026  const float centroid = ( treeletRoots[i]->bounds.Min()[dim] +
1027  treeletRoots[i]->bounds.Max()[dim] ) *
1028  0.5f;
1029  int b =
1030  nBuckets * ( (centroid - centroidBounds.Min()[dim] ) /
1031  (centroidBounds.Max()[dim] - centroidBounds.Min()[dim] ) );
1032 
1033  if( b == nBuckets )
1034  b = nBuckets - 1;
1035 
1036  wxASSERT( (b >= 0) && (b < nBuckets) );
1037 
1038  buckets[b].count++;
1039  buckets[b].bounds.Union( treeletRoots[i]->bounds );
1040  }
1041 
1042  // Compute costs for splitting after each bucket
1043  float cost[nBuckets - 1];
1044 
1045  for( int i = 0; i < nBuckets - 1; ++i )
1046  {
1047  CBBOX b0, b1;
1048  b0.Reset();
1049  b1.Reset();
1050 
1051  int count0 = 0, count1 = 0;
1052 
1053  for( int j = 0; j <= i; ++j )
1054  {
1055  if( buckets[j].count )
1056  {
1057  count0 += buckets[j].count;
1058  b0.Union( buckets[j].bounds );
1059  }
1060  }
1061 
1062  for( int j = i + 1; j < nBuckets; ++j )
1063  {
1064  if( buckets[j].count )
1065  {
1066  count1 += buckets[j].count;
1067  b1.Union( buckets[j].bounds );
1068  }
1069  }
1070 
1071  cost[i] = .125f +
1072  ( count0 * b0.SurfaceArea() + count1 * b1.SurfaceArea() ) /
1073  bounds.SurfaceArea();
1074  }
1075 
1076  // Find bucket to split at that minimizes SAH metric
1077  float minCost = cost[0];
1078  int minCostSplitBucket = 0;
1079 
1080  for( int i = 1; i < nBuckets - 1; ++i )
1081  {
1082  if( cost[i] < minCost )
1083  {
1084  minCost = cost[i];
1085  minCostSplitBucket = i;
1086  }
1087  }
1088 
1089  // Split nodes and create interior HLBVH SAH node
1090  BVHBuildNode **pmid = std::partition( &treeletRoots[start],
1091  &treeletRoots[end - 1] + 1,
1092  HLBVH_SAH_Evaluator( minCostSplitBucket,
1093  nBuckets,
1094  dim,
1095  centroidBounds ) );
1096 
1097  const int mid = pmid - &treeletRoots[0];
1098 
1099  wxASSERT( (mid > start) && (mid < end) );
1100 
1101  node->InitInterior( dim,
1102  buildUpperSAH( treeletRoots, start, mid, totalNodes ),
1103  buildUpperSAH( treeletRoots, mid, end, totalNodes ) );
1104 
1105  return node;
1106 }
1107 
1108 
1109 int CBVH_PBRT::flattenBVHTree( BVHBuildNode *node, uint32_t *offset )
1110 {
1111  LinearBVHNode *linearNode = &m_nodes[*offset];
1112 
1113  linearNode->bounds = node->bounds;
1114 
1115  int myOffset = (*offset)++;
1116 
1117  if( node->nPrimitives > 0 )
1118  {
1119  wxASSERT( (!node->children[0]) && (!node->children[1]) );
1120  wxASSERT( node->nPrimitives < 65536 );
1121 
1122  linearNode->primitivesOffset = node->firstPrimOffset;
1123  linearNode->nPrimitives = node->nPrimitives;
1124  }
1125  else
1126  {
1127  // Creater interior flattened BVH node
1128  linearNode->axis = node->splitAxis;
1129  linearNode->nPrimitives = 0;
1130  flattenBVHTree( node->children[0], offset );
1131  linearNode->secondChildOffset = flattenBVHTree( node->children[1], offset );
1132  }
1133 
1134  return myOffset;
1135 }
1136 
1137 
1138 #define MAX_TODOS 64
1139 
1140 bool CBVH_PBRT::Intersect( const RAY &aRay, HITINFO &aHitInfo ) const
1141 {
1142  if( !m_nodes )
1143  return false;
1144 
1145  bool hit = false;
1146 
1147  // Follow ray through BVH nodes to find primitive intersections
1148  int todoOffset = 0, nodeNum = 0;
1149  int todo[MAX_TODOS];
1150 
1151  while( true )
1152  {
1153  const LinearBVHNode *node = &m_nodes[nodeNum];
1154 
1155  wxASSERT( todoOffset < MAX_TODOS );
1156 
1157  // Check ray against BVH node
1158  float hitBox = 0.0f;
1159 
1160  const bool hitted = node->bounds.Intersect( aRay, &hitBox );
1161 
1162  if( hitted && (hitBox < aHitInfo.m_tHit) )
1163  {
1164  if( node->nPrimitives > 0 )
1165  {
1166  // Intersect ray with primitives in leaf BVH node
1167  for( int i = 0; i < node->nPrimitives; ++i )
1168  {
1169  if( m_primitives[node->primitivesOffset + i]->Intersect( aRay,
1170  aHitInfo ) )
1171  {
1172  aHitInfo.m_acc_node_info = nodeNum;
1173  hit = true;
1174  }
1175  }
1176  }
1177  else
1178  {
1179  // Put far BVH node on _todo_ stack, advance to near node
1180  if( aRay.m_dirIsNeg[node->axis] )
1181  {
1182  todo[todoOffset++] = nodeNum + 1;
1183  nodeNum = node->secondChildOffset;
1184  }
1185  else
1186  {
1187  todo[todoOffset++] = node->secondChildOffset;
1188  nodeNum = nodeNum + 1;
1189  }
1190 
1191  continue;
1192  }
1193  }
1194 
1195  if( todoOffset == 0 )
1196  break;
1197 
1198  nodeNum = todo[--todoOffset];
1199  }
1200 
1201  return hit;
1202 }
1203 
1204 // !TODO: this may be optimized
1205 bool CBVH_PBRT::Intersect( const RAY &aRay,
1206  HITINFO &aHitInfo,
1207  unsigned int aAccNodeInfo ) const
1208 {
1209  if( !m_nodes )
1210  return false;
1211 
1212  bool hit = false;
1213 
1214  // Follow ray through BVH nodes to find primitive intersections
1215  int todoOffset = 0, nodeNum = aAccNodeInfo;
1216  int todo[MAX_TODOS];
1217 
1218  while( true )
1219  {
1220  const LinearBVHNode *node = &m_nodes[nodeNum];
1221 
1222  wxASSERT( todoOffset < MAX_TODOS );
1223 
1224  // Check ray against BVH node
1225  float hitBox = 0.0f;
1226 
1227  const bool hitted = node->bounds.Intersect( aRay, &hitBox );
1228 
1229  if( hitted && (hitBox < aHitInfo.m_tHit) )
1230  {
1231  if( node->nPrimitives > 0 )
1232  {
1233  // Intersect ray with primitives in leaf BVH node
1234  for( int i = 0; i < node->nPrimitives; ++i )
1235  {
1236  if( m_primitives[node->primitivesOffset + i]->Intersect( aRay,
1237  aHitInfo ) )
1238  {
1239  //aHitInfo.m_acc_node_info = nodeNum;
1240  hit = true;
1241  }
1242  }
1243  }
1244  else
1245  {
1246  // Put far BVH node on _todo_ stack, advance to near node
1247  if( aRay.m_dirIsNeg[node->axis] )
1248  {
1249  todo[todoOffset++] = nodeNum + 1;
1250  nodeNum = node->secondChildOffset;
1251  }
1252  else
1253  {
1254  todo[todoOffset++] = node->secondChildOffset;
1255  nodeNum = nodeNum + 1;
1256  }
1257 
1258  continue;
1259  }
1260  }
1261 
1262  if( todoOffset == 0 )
1263  break;
1264 
1265  nodeNum = todo[--todoOffset];
1266  }
1267 
1268  return hit;
1269 }
1270 
1271 
1272 bool CBVH_PBRT::IntersectP( const RAY &aRay, float aMaxDistance ) const
1273 {
1274  if( !m_nodes )
1275  return false;
1276 
1277  // Follow ray through BVH nodes to find primitive intersections
1278  int todoOffset = 0, nodeNum = 0;
1279  int todo[MAX_TODOS];
1280 
1281  while( true )
1282  {
1283  const LinearBVHNode *node = &m_nodes[nodeNum];
1284 
1285  wxASSERT( todoOffset < MAX_TODOS );
1286 
1287  // Check ray against BVH node
1288  float hitBox = 0.0f;
1289 
1290  const bool hitted = node->bounds.Intersect( aRay, &hitBox );
1291 
1292  if( hitted && (hitBox < aMaxDistance) )
1293  {
1294  if( node->nPrimitives > 0 )
1295  {
1296  // Intersect ray with primitives in leaf BVH node
1297  for( int i = 0; i < node->nPrimitives; ++i )
1298  {
1299  const COBJECT *obj = m_primitives[node->primitivesOffset + i];
1300 
1301  if( obj->GetMaterial()->GetCastShadows() )
1302  if( obj->IntersectP( aRay, aMaxDistance ) )
1303  return true;
1304  }
1305  }
1306  else
1307  {
1308  // Put far BVH node on _todo_ stack, advance to near node
1309  if( aRay.m_dirIsNeg[node->axis] )
1310  {
1311  todo[todoOffset++] = nodeNum + 1;
1312  nodeNum = node->secondChildOffset;
1313  }
1314  else
1315  {
1316  todo[todoOffset++] = node->secondChildOffset;
1317  nodeNum = nodeNum + 1;
1318  }
1319 
1320  continue;
1321  }
1322  }
1323 
1324  if( todoOffset == 0 )
1325  break;
1326 
1327  nodeNum = todo[--todoOffset];
1328  }
1329 
1330  return false;
1331 }
uint32_t EncodeMorton3(const SFVEC3F &v)
Definition: cbvh_pbrt.cpp:168
CONST_VECTOR_OBJECT m_primitives
Definition: cbvh_pbrt.h:157
bool operator()(const BVHPrimitiveInfo &a, const BVHPrimitiveInfo &b) const
Definition: cbvh_pbrt.cpp:363
#define KI_FALLTHROUGH
const SFVEC3F & Max() const
Function Max return the maximum vertex pointer.
Definition: cbbox.h:212
int primitivesOffset
leaf
Definition: cbvh_pbrt.h:90
const LIST_OBJECT & GetList() const
Definition: ccontainer.h:63
uint16_t nPrimitives
0 -> interior node
Definition: cbvh_pbrt.h:95
std::vector< const COBJECT * > CONST_VECTOR_OBJECT
Definition: ccontainer.h:39
uint8_t axis
interior node: xyz
Definition: cbvh_pbrt.h:96
SFVEC3F Offset(const SFVEC3F &p) const
Function Offset.
Definition: cbbox.cpp:263
Template specialization to enable wxStrings for certain containers (e.g. unordered_map)
Definition: bitmap.cpp:56
int firstPrimOffset
Definition: cbvh_pbrt.cpp:129
Definition: ray.h:67
CBVH_PBRT(const CGENERICCONTAINER &aObjectContainer, int aMaxPrimsInNode=4, SPLITMETHOD aSplitMethod=SPLITMETHOD::SAH)
Definition: cbvh_pbrt.cpp:235
HLBVH_SAH_Evaluator(int split, int num, int d, const CBBOX &b)
Definition: cbvh_pbrt.cpp:419
bool operator()(const BVHPrimitiveInfo &p) const
Definition: cbvh_pbrt.cpp:399
const int m_maxPrimsInNode
Definition: cbvh_pbrt.h:155
float m_tHit
( 4) distance
Definition: hitinfo.h:43
void InitInterior(int axis, BVHBuildNode *c0, BVHBuildNode *c1)
Definition: cbvh_pbrt.cpp:117
void Set(const SFVEC3F &aPbMin, const SFVEC3F &aPbMax)
Function Set Set bounding box with new parameters.
Definition: cbbox.cpp:67
This file contains miscellaneous commonly used macros and functions.
void Union(const SFVEC3F &aPoint)
Function Union recalculate the bounding box adding a point.
Definition: cbbox.cpp:105
unsigned int MaxDimension() const
Function MaxDimension.
Definition: cbbox.cpp:154
SFVEC3F GetCenter() const
Function GetCenter return the center point of the bounding box.
Definition: cbbox.cpp:135
BVHPrimitiveInfo(int aPrimitiveNumber, const CBBOX &aBounds)
Definition: cbvh_pbrt.cpp:95
CBBOX bounds
Definition: cbvh_pbrt.cpp:451
ComparePoints(int d)
Definition: cbvh_pbrt.cpp:359
bool IntersectP(const RAY &aRay, float aMaxDistance) const override
Definition: cbvh_pbrt.cpp:1272
#define NULL
void InitLeaf(int first, int n, const CBBOX &b)
Definition: cbvh_pbrt.cpp:109
const CMATERIAL * GetMaterial() const
Definition: cobject.h:72
int numPrimitives
Definition: cbvh_pbrt.cpp:142
bool GetCastShadows() const
Definition: cmaterial.h:229
unsigned int m_dirIsNeg[3]
Definition: ray.h:80
BVHBuildNode * buildUpperSAH(std::vector< BVHBuildNode * > &treeletRoots, int start, int end, int *totalNodes)
Definition: cbvh_pbrt.cpp:958
CompareToBucket(int split, int num, int d, const CBBOX &b)
Definition: cbvh_pbrt.cpp:387
BVHBuildNode * children[2]
Definition: cbvh_pbrt.cpp:128
bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const override
Definition: cbvh_pbrt.cpp:1140
virtual bool IntersectP(const RAY &aRay, float aMaxDistance) const =0
Functions Intersect for shadow test.
float SurfaceArea() const
Function SurfaceArea.
Definition: cbbox.cpp:184
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: cbvh_pbrt.cpp:857
BVHBuildNode * recursiveBuild(std::vector< BVHPrimitiveInfo > &primitiveInfo, int start, int end, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims)
Definition: cbvh_pbrt.cpp:455
BVHBuildNode * buildNodes
Definition: cbvh_pbrt.cpp:143
#define MAX_TODOS
Definition: cbvh_pbrt.cpp:1138
const SFVEC3F & Min() const
Function Min return the minimun vertex pointer.
Definition: cbbox.h:205
LinearBVHNode * m_nodes
Definition: cbvh_pbrt.h:158
uint32_t LeftShift3(uint32_t x)
Definition: cbvh_pbrt.cpp:148
static void RadixSort(std::vector< MortonPrimitive > *v)
Definition: cbvh_pbrt.cpp:178
uint32_t mortonCode
Definition: cbvh_pbrt.cpp:136
Stores the hit information of a ray with a point on the surface of a object.
Definition: hitinfo.h:40
#define RAYPACKET_RAYS_PER_PACKET
Definition: raypacket.h:40
CompareToMid(int d, float m)
Definition: cbvh_pbrt.cpp:373
bool Intersect(const RAY &aRay, float *t) const
Function Intersect.
Definition: cbbox_ray.cpp:46
unsigned int m_acc_node_info
( 4) The acc stores here the node that it hits
Definition: hitinfo.h:47
glm::vec3 SFVEC3F
Definition: xv3d_types.h:47
unsigned int m_I[RAYPACKET_RAYS_PER_PACKET]
Definition: cbvh_pbrt.h:163
int flattenBVHTree(BVHBuildNode *node, uint32_t *offset)
Definition: cbvh_pbrt.cpp:1109
void ConvertTo(CONST_VECTOR_OBJECT &aOutVector) const
Definition: ccontainer.cpp:64
BVHBuildNode * HLBVHBuild(const std::vector< BVHPrimitiveInfo > &primitiveInfo, int *totalNodes, CONST_VECTOR_OBJECT &orderedPrims)
Definition: cbvh_pbrt.cpp:730
int secondChildOffset
interior
Definition: cbvh_pbrt.h:91
SPLITMETHOD
Definition: cbvh_pbrt.h:101
CBBOX bounds
Definition: cbvh_pbrt.h:85
bool operator()(const BVHPrimitiveInfo &a) const
Definition: cbvh_pbrt.cpp:378
CBBOX manages a bounding box defined by two SFVEC3F min max points.
Definition: cbbox.h:40
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox.cpp:98
This BVH implementation is based on the source code implementation from the book "Physically Based Re...
bool operator()(const BVHBuildNode *node) const
Definition: cbvh_pbrt.cpp:430
const CBBOX & centroidBounds
Definition: cbvh_pbrt.cpp:395
const CBBOX & centroidBounds
Definition: cbvh_pbrt.cpp:426
std::list< void * > m_addresses_pointer_to_mm_free
Definition: cbvh_pbrt.h:160
SPLITMETHOD m_splitMethod
Definition: cbvh_pbrt.h:156