Mitsuba Renderer  0.5.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
sahkdtree3.h
Go to the documentation of this file.
1 /*
2  This file is part of Mitsuba, a physically based rendering system.
3 
4  Copyright (c) 2007-2014 by Wenzel Jakob and others.
5 
6  Mitsuba is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License Version 3
8  as published by the Free Software Foundation.
9 
10  Mitsuba is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18 
19 #pragma once
20 #if !defined(__MITSUBA_RENDER_SAHKDTREE3_H_)
21 #define __MITSUBA_RENDER_SAHKDTREE3_H_
22 
23 #include <mitsuba/render/gkdtree.h>
24 #include <mitsuba/core/warp.h>
25 #include <mitsuba/core/random.h>
26 
28 
29 /// Use a simple hashed 8-entry mailbox per thread
30 #define MTS_KD_MAILBOX_ENABLED 1
31 #define MTS_KD_MAILBOX_SIZE 8
32 #define MTS_KD_MAILBOX_MASK (MTS_KD_MAILBOX_SIZE-1)
33 
34 /**
35  * \brief Implements the 3D surface area heuristic for use
36  * by the \ref GenericKDTree construction algorithm.
37  * \ingroup librender
38  */
40 public:
41  /**
42  * \brief Initialize the surface area heuristic with the bounds of
43  * a parent node
44  *
45  * Precomputes some information so that traversal probabilities
46  * of potential split planes can be evaluated efficiently
47  */
48  inline SurfaceAreaHeuristic3(const AABB &aabb) {
49  const Vector extents(aabb.getExtents());
50  const Float temp = 1.0f / (extents.x * extents.y
51  + extents.y*extents.z + extents.x*extents.z);
52  m_temp0 = Vector(
53  extents[1] * extents[2],
54  extents[0] * extents[2],
55  extents[0] * extents[1]) * temp;
56  m_temp1 = Vector(
57  extents[1] + extents[2],
58  extents[0] + extents[2],
59  extents[0] + extents[1]) * temp;
60  }
61 
62  /**
63  * Given a split on axis \a axis that produces children having extents
64  * \a leftWidth and \a rightWidth along \a axis, compute the probability
65  * of traversing the left and right child during a typical query
66  * operation. In the case of the surface area heuristic, this is simply
67  * the ratio of surface areas.
68  */
69  inline std::pair<Float, Float> operator()(int axis, Float leftWidth, Float rightWidth) const {
70  return std::pair<Float, Float>(
71  m_temp0[axis] + m_temp1[axis] * leftWidth,
72  m_temp0[axis] + m_temp1[axis] * rightWidth);
73  }
74 
75  /**
76  * Compute the underlying quantity used by the tree construction
77  * heuristic. This is used to compute the final cost of a kd-tree.
78  */
79  inline static Float getQuantity(const AABB &aabb) {
80  return aabb.getSurfaceArea();
81  }
82 private:
83  Vector m_temp0, m_temp1;
84 };
85 
86 /**
87  * \brief Specializes \ref GenericKDTree to a three-dimensional
88  * tree to be used for ray tracing.
89  *
90  * One additional function call must be implemented by subclasses:
91  * \code
92  * /// Check whether a primitive is intersected by the given ray.
93  * /// Some temporary space is supplied, which can be used to cache
94  * /// information about the intersection
95  * bool intersect(const Ray &ray, IndexType idx,
96  * Float mint, Float maxt, Float &t, void *tmp);
97  * \endcode
98  *
99  * This class implements an epsilon-free version of the optimized ray
100  * traversal algorithm (TA^B_{rec}), which is explained in Vlastimil
101  * Havran's PhD thesis "Heuristic Ray Shooting Algorithms".
102  *
103  * \author Wenzel Jakob
104  * \ingroup librender
105  */
106 template <typename Derived>
107  class SAHKDTree3D : public GenericKDTree<AABB, SurfaceAreaHeuristic3, Derived> {
108 public:
113 
114  using Parent::m_nodes;
115  using Parent::m_aabb;
116  using Parent::m_indices;
117 
118 protected:
119  void buildInternal() {
120  SizeType primCount = cast()->getPrimitiveCount();
121  KDLog(EInfo, "Constructing a SAH kd-tree (%i primitives) ..", primCount);
123  }
124 
125  /// Cast to the derived class
126  inline Derived *cast() {
127  return static_cast<Derived *>(this);
128  }
129 
130  /// Cast to the derived class (const version)
131  inline const Derived *cast() const {
132  return static_cast<const Derived *>(this);
133  }
134 
135  /**
136  * \brief Hashed mailbox implementation
137  */
138  struct HashedMailbox {
139  inline HashedMailbox() {
140  memset(entries, 0xFF, sizeof(IndexType)*MTS_KD_MAILBOX_SIZE);
141  }
142 
143  inline void put(IndexType primIndex) {
144  entries[primIndex & MTS_KD_MAILBOX_MASK] = primIndex;
145  }
146 
147  inline bool contains(IndexType primIndex) const {
148  return entries[primIndex & MTS_KD_MAILBOX_MASK] == primIndex;
149  }
150 
152  };
153 
154  /// Ray traversal stack entry for Wald-style incoherent ray tracing
155  struct KDStackEntry {
156  const KDNode * __restrict node;
157  Float mint, maxt;
158  };
159 
160  /// Ray traversal stack entry for Havran-style incoherent ray tracing
162  /* Pointer to the far child */
163  const KDNode * __restrict node;
164  /* Distance traveled along the ray (entry or exit) */
166  /* Previous stack item */
168  /* Associated point */
170  };
171 
172  /**
173  * \brief Ray tracing kd-tree traversal loop (Havran variant)
174  *
175  * This is generally the most robust and fastest traversal routine
176  * of the methods implemented in this class.
177  */
178  template<bool shadowRay> FINLINE
179  bool rayIntersectHavran(const Ray &ray, Float mint, Float maxt,
180  Float &t, void *temp) const {
181  KDStackEntryHavran stack[MTS_KD_MAXDEPTH];
182  #if 0
183  static const int prevAxisTable[] = { 2, 0, 1 };
184  static const int nextAxisTable[] = { 1, 2, 0 };
185  #endif
186 
187  #if defined(MTS_KD_MAILBOX_ENABLED)
188  HashedMailbox mailbox;
189  #endif
190 
191  /* Set up the entry point */
192  uint32_t enPt = 0;
193  stack[enPt].t = mint;
194  stack[enPt].p = ray(mint);
195 
196  /* Set up the exit point */
197  uint32_t exPt = 1;
198  stack[exPt].t = maxt;
199  stack[exPt].p = ray(maxt);
200  stack[exPt].node = NULL;
201 
202  bool foundIntersection = false;
203  const KDNode * __restrict currNode = m_nodes;
204  while (currNode != NULL) {
205  while (EXPECT_TAKEN(!currNode->isLeaf())) {
206  const Float splitVal = (Float) currNode->getSplit();
207  const int axis = currNode->getAxis();
208  const KDNode * __restrict farChild;
209 
210  if (stack[enPt].p[axis] <= splitVal) {
211  if (stack[exPt].p[axis] <= splitVal) {
212  /* Cases N1, N2, N3, P5, Z2 and Z3 (see thesis) */
213  currNode = currNode->getLeft();
214  continue;
215  }
216 
217  /* Typo in Havran's thesis:
218  (it specifies "stack[exPt].p == splitVal", which
219  is clearly incorrect) */
220  if (stack[enPt].p[axis] == splitVal) {
221  /* Case Z1 */
222  currNode = currNode->getRight();
223  continue;
224  }
225 
226  /* Case N4 */
227  currNode = currNode->getLeft();
228  farChild = currNode + 1; // getRight()
229  } else { /* stack[enPt].p[axis] > splitVal */
230  if (splitVal < stack[exPt].p[axis]) {
231  /* Cases P1, P2, P3 and N5 */
232  currNode = currNode->getRight();
233  continue;
234  }
235  /* Case P4 */
236  farChild = currNode->getLeft();
237  currNode = farChild + 1; // getRight()
238  }
239 
240  /* Cases P4 and N4 -- calculate the distance to the split plane */
241  Float distToSplit = (splitVal - ray.o[axis]) * ray.dRcp[axis];
242 
243  /* Set up a new exit point */
244  const uint32_t tmp = exPt++;
245  if (exPt == enPt) /* Do not overwrite the entry point */
246  ++exPt;
247 
248  KDAssert(exPt < MTS_KD_MAXDEPTH);
249  stack[exPt].prev = tmp;
250  stack[exPt].t = distToSplit;
251  stack[exPt].node = farChild;
252 
253  #if 1
254  /* Intrestingly, this appears to be faster than the
255  original code with the prevAxis & nextAxis table */
256  stack[exPt].p = ray(distToSplit);
257  stack[exPt].p[axis] = splitVal;
258  #else
259  const int nextAxis = nextAxisTable[axis];
260  const int prevAxis = prevAxisTable[axis];
261  stack[exPt].p[axis] = splitVal;
262  stack[exPt].p[nextAxis] = ray.o[nextAxis]
263  + distToSplit*ray.d[nextAxis];
264  stack[exPt].p[prevAxis] = ray.o[prevAxis]
265  + distToSplit*ray.d[prevAxis];
266  #endif
267 
268  }
269 
270  /* Reached a leaf node */
271  for (IndexType entry=currNode->getPrimStart(),
272  last = currNode->getPrimEnd(); entry != last; entry++) {
273  const IndexType primIdx = m_indices[entry];
274 
275  #if defined(MTS_KD_MAILBOX_ENABLED)
276  if (mailbox.contains(primIdx))
277  continue;
278  #endif
279 
280  bool result;
281  if (!shadowRay)
282  result = cast()->intersect(ray, primIdx, mint, maxt, t, temp);
283  else
284  result = cast()->intersect(ray, primIdx, mint, maxt);
285 
286  if (result) {
287  if (shadowRay)
288  return true;
289  maxt = t;
290  foundIntersection = true;
291  }
292 
293  #if defined(MTS_KD_MAILBOX_ENABLED)
294  mailbox.put(primIdx);
295  #endif
296  }
297 
298  if (stack[exPt].t > maxt)
299  break;
300 
301  /* Pop from the stack and advance to the next node on the interval */
302  enPt = exPt;
303  currNode = stack[exPt].node;
304  exPt = stack[enPt].prev;
305  }
306 
307  return foundIntersection;
308  }
309 
310  struct RayStatistics {
314  uint64_t time;
315 
316  RayStatistics(bool foundIntersection, uint32_t numTraversals,
317  uint32_t numIntersections, uint64_t time) :
318  foundIntersection(foundIntersection), numTraversals(numTraversals),
319  numIntersections(numIntersections), time(time) { }
320  };
321 
322  /**
323  * \brief Internal kd-tree traversal implementation (Havran variant)
324  *
325  * This method is almost identical to \ref rayIntersectHavran, except
326  * that it additionally returns statistics on the number of traversed
327  * nodes, intersected shapes, as well as the time taken to do this
328  * (measured using rtdsc).
329  */
330  FINLINE RayStatistics rayIntersectHavranCollectStatistics(
331  const Ray &ray, Float mint, Float maxt, Float &t, void *temp) const {
332  KDStackEntryHavran stack[MTS_KD_MAXDEPTH];
333 
334  /* Set up the entry point */
335  uint32_t enPt = 0;
336  stack[enPt].t = mint;
337  stack[enPt].p = ray(mint);
338 
339  /* Set up the exit point */
340  uint32_t exPt = 1;
341  stack[exPt].t = maxt;
342  stack[exPt].p = ray(maxt);
343  stack[exPt].node = NULL;
344 
345  uint32_t numTraversals = 0;
346  uint32_t numIntersections = 0;
347  uint64_t timer = rdtsc();
348  bool foundIntersection = false;
349 
350  const KDNode * __restrict currNode = m_nodes;
351  while (currNode != NULL) {
352  while (EXPECT_TAKEN(!currNode->isLeaf())) {
353  const Float splitVal = (Float) currNode->getSplit();
354  const int axis = currNode->getAxis();
355  const KDNode * __restrict farChild;
356 
357  ++numTraversals;
358  if (stack[enPt].p[axis] <= splitVal) {
359  if (stack[exPt].p[axis] <= splitVal) {
360  /* Cases N1, N2, N3, P5, Z2 and Z3 (see thesis) */
361  currNode = currNode->getLeft();
362  continue;
363  }
364 
365  /* Typo in Havran's thesis:
366  (it specifies "stack[exPt].p == splitVal", which
367  is clearly incorrect) */
368  if (stack[enPt].p[axis] == splitVal) {
369  /* Case Z1 */
370  currNode = currNode->getRight();
371  continue;
372  }
373 
374  /* Case N4 */
375  currNode = currNode->getLeft();
376  farChild = currNode + 1; // getRight()
377  } else { /* stack[enPt].p[axis] > splitVal */
378  if (splitVal < stack[exPt].p[axis]) {
379  /* Cases P1, P2, P3 and N5 */
380  currNode = currNode->getRight();
381  continue;
382  }
383  /* Case P4 */
384  farChild = currNode->getLeft();
385  currNode = farChild + 1; // getRight()
386  }
387 
388  /* Cases P4 and N4 -- calculate the distance to the split plane */
389  t = (splitVal - ray.o[axis]) * ray.dRcp[axis];
390 
391  /* Set up a new exit point */
392  const uint32_t tmp = exPt++;
393  if (exPt == enPt) /* Do not overwrite the entry point */
394  ++exPt;
395 
396  KDAssert(exPt < MTS_KD_MAXDEPTH);
397  stack[exPt].prev = tmp;
398  stack[exPt].t = t;
399  stack[exPt].node = farChild;
400  stack[exPt].p = ray(t);
401  stack[exPt].p[axis] = splitVal;
402  }
403 
404  /* Reached a leaf node */
405  for (unsigned int entry=currNode->getPrimStart(),
406  last = currNode->getPrimEnd(); entry != last; entry++) {
407  const IndexType primIdx = m_indices[entry];
408 
409  ++numIntersections;
410  bool result = cast()->intersect(ray, primIdx, mint, maxt, t, temp);
411 
412  if (result) {
413  maxt = t;
414  foundIntersection = true;
415  }
416  }
417 
418  if (stack[exPt].t > maxt)
419  break;
420 
421  /* Pop from the stack and advance to the next node on the interval */
422  enPt = exPt;
423  currNode = stack[exPt].node;
424  exPt = stack[enPt].prev;
425  }
426 
427  return RayStatistics(foundIntersection, numTraversals,
428  numIntersections, rdtsc() - timer);
429  }
430 
431  /**
432  * \brief Ray tracing kd-tree traversal loop (PBRT variant)
433  */
434  template<bool shadowRay> FINLINE bool rayIntersectPBRT(const Ray &ray,
435  Float mint_, Float maxt_, Float &t, void *temp) const {
436  KDStackEntry stack[MTS_KD_MAXDEPTH];
437  int stackPos = 0;
438  Float mint = mint_, maxt=maxt_;
439  const KDNode *node = m_nodes;
440  bool foundIntersection = false;
441 
442  while (node != NULL) {
443  if (maxt_ < mint)
444  break;
445 
446  if (EXPECT_TAKEN(!node->isLeaf())) {
447  const Float split = (Float) node->getSplit();
448  const int axis = node->getAxis();
449  const float tPlane = (split - ray.o[axis]) * ray.dRcp[axis];
450  bool leftOfSplit = (ray.o[axis] < split)
451  || (ray.o[axis] == split && ray.d[axis] <= 0);
452 
453  const KDNode * __restrict left = node->getLeft();
454  const KDNode * __restrict right = left + 1;
455  const KDNode * __restrict first = leftOfSplit ? left : right;
456  const KDNode * __restrict second = leftOfSplit ? right : left;
457 
458  if (tPlane > maxt || tPlane <= 0) {
459  node = first;
460  } else if (tPlane < mint) {
461  node = second;
462  } else {
463  stack[stackPos].node = second;
464  stack[stackPos].mint = tPlane;
465  stack[stackPos].maxt = maxt;
466  ++stackPos;
467  node = first;
468  maxt = tPlane;
469  }
470  } else {
471  for (unsigned int entry=node->getPrimStart(),
472  last = node->getPrimEnd(); entry != last; entry++) {
473  const IndexType primIdx = m_indices[entry];
474 
475  bool result;
476  if (!shadowRay)
477  result = cast()->intersect(ray, primIdx, mint, maxt, t, temp);
478  else
479  result = cast()->intersect(ray, primIdx, mint, maxt);
480 
481  if (result) {
482  if (shadowRay)
483  return true;
484  maxt_ = t;
485  foundIntersection = true;
486  }
487  }
488 
489  if (stackPos > 0) {
490  --stackPos;
491  node = stack[stackPos].node;
492  mint = stack[stackPos].mint;
493  maxt = stack[stackPos].maxt;
494  } else {
495  break;
496  }
497  }
498  }
499  return foundIntersection;
500  }
501 public:
502  /**
503  * \brief Empirically find the best traversal and intersection
504  * cost values
505  *
506  * This is done by running the traversal code on random rays
507  * and fitting the SAH cost model to the collected statistics.
508  */
509  void findCosts(Float &traversalCost, Float &intersectionCost) {
510  ref<Random> random = new Random();
511  uint8_t temp[128];
512  BSphere bsphere = m_aabb.getBSphere();
513  int nRays = 10000000, warmup = nRays/4;
514  Vector *A = new Vector[nRays-warmup];
515  Float *b = new Float[nRays-warmup];
516  int nIntersections = 0, idx = 0;
517 
518  for (int i=0; i<nRays; ++i) {
519  Point2 sample1(random->nextFloat(), random->nextFloat()),
520  sample2(random->nextFloat(), random->nextFloat());
521  Point p1 = bsphere.center + warp::squareToUniformSphere(sample1) * bsphere.radius;
522  Point p2 = bsphere.center + warp::squareToUniformSphere(sample2) * bsphere.radius;
523  Ray ray(p1, normalize(p2-p1), 0.0f);
524  Float mint, maxt, t;
525  if (m_aabb.rayIntersect(ray, mint, maxt)) {
526  if (ray.mint > mint) mint = ray.mint;
527  if (ray.maxt < maxt) maxt = ray.maxt;
528  if (EXPECT_TAKEN(maxt > mint)) {
529  RayStatistics statistics =
530  rayIntersectHavranCollectStatistics(ray, mint, maxt, t, temp);
531  if (statistics.foundIntersection)
532  nIntersections++;
533  if (i > warmup) {
534  A[idx].x = 1;
535  A[idx].y = (Float) statistics.numTraversals;
536  A[idx].z = (Float) statistics.numIntersections;
537  b[idx] = (Float) statistics.time;
538  idx++;
539  }
540  }
541  }
542  }
543 
544  KDLog(EDebug, "Fitting to " SIZE_T_FMT " samples (" SIZE_T_FMT
545  " intersections)", idx, nIntersections);
546 
547  /* Solve using normal equations */
548  Matrix4x4 M(0.0f), Minv;
549  Vector4 rhs(0.0f), x;
550 
551  for (int i=0; i<3; ++i) {
552  for (int j=0; j<3; ++j)
553  for (int k=0; k<idx; ++k)
554  M.m[i][j] += A[k][i]*A[k][j];
555  for (int k=0; k<idx; ++k)
556  rhs[i] += A[k][i]*b[k];
557  }
558  M.m[3][3] = 1.0f;
559  bool success = M.invert(Minv);
560  SAssert(success);
561 
562  Transform(Minv, M)(rhs, x);
563 
564  Float avgRdtsc = 0, avgResidual = 0;
565  for (int i=0; i<idx; ++i) {
566  avgRdtsc += b[i];
567  Float model = x[0] * A[i][0]
568  + x[1] * A[i][1]
569  + x[2] * A[i][2];
570  avgResidual += std::abs(b[i] - model);
571  }
572  avgRdtsc /= idx;
573  avgResidual /= idx;
574 
575  for (int k=0; k<idx; ++k)
576  avgRdtsc += b[k];
577  avgRdtsc /= idx;
578 
579  KDLog(EDebug, "Least squares fit:");
580  KDLog(EDebug, " Constant overhead = %.2f", x[0]);
581  KDLog(EDebug, " Traversal cost = %.2f", x[1]);
582  KDLog(EDebug, " Intersection cost = %.2f", x[2]);
583  KDLog(EDebug, " Average rdtsc value = %.2f", avgRdtsc);
584  KDLog(EDebug, " Avg. residual = %.2f", avgResidual);
585  x *= 10/x[1];
586  KDLog(EDebug, "Re-scaled:");
587  KDLog(EDebug, " Constant overhead = %.2f", x[0]);
588  KDLog(EDebug, " Traversal cost = %.2f", x[1]);
589  KDLog(EDebug, " Intersection cost = %.2f", x[2]);
590 
591  delete[] A;
592  delete[] b;
593  traversalCost = x[1];
594  intersectionCost = x[2];
595  }
596 };
597 
599 
600 #endif /* __MITSUBA_RENDER_SAHKDTREE3_H_ */
RayStatistics(bool foundIntersection, uint32_t numTraversals, uint32_t numIntersections, uint64_t time)
Definition: sahkdtree3.h:316
#define KDLog(level, fmt,...)
Definition: gkdtree.h:642
KDTreeBase< AABB >::SizeType SizeType
Definition: sahkdtree3.h:110
Random number generator based on SIMD-oriented Fast Mersenne Twister
Definition: random.h:88
uint32_t numIntersections
Definition: sahkdtree3.h:313
std::pair< Float, Float > operator()(int axis, Float leftWidth, Float rightWidth) const
Definition: sahkdtree3.h:69
TVector3< Float > Vector
Definition: fwd.h:113
#define KDAssert(expr)
Definition: gkdtree.h:56
Float getSurfaceArea() const
Calculate the surface area of the bounding box.
Definition: aabb.h:464
Bounding sphere data structure in three dimensions.
Definition: bsphere.h:32
Debug message, usually turned off.
Definition: formatter.h:30
Base class of all kd-trees.
Definition: gkdtree.h:441
Normal normalize(const Normal &n)
Definition: normal.h:73
#define MTS_NAMESPACE_BEGIN
Definition: platform.h:137
#define MTS_KD_MAXDEPTH
Activate lots of extra checks.
Definition: gkdtree.h:37
uint32_t numTraversals
Definition: sahkdtree3.h:312
Definition: sahkdtree3.h:310
FINLINE bool rayIntersectPBRT(const Ray &ray, Float mint_, Float maxt_, Float &t, void *temp) const
Ray tracing kd-tree traversal loop (PBRT variant)
Definition: sahkdtree3.h:434
More relevant debug / information message.
Definition: formatter.h:31
Ray traversal stack entry for Wald-style incoherent ray tracing.
Definition: sahkdtree3.h:155
KDTreeBase< AABB >::IndexType IndexType
Definition: sahkdtree3.h:111
void put(IndexType primIndex)
Definition: sahkdtree3.h:143
uint32_t prev
Definition: sahkdtree3.h:167
HashedMailbox()
Definition: sahkdtree3.h:139
Float radius
Definition: bsphere.h:34
uint64_t time
Definition: sahkdtree3.h:314
Axis-aligned bounding box data structure in three dimensions.
Definition: aabb.h:437
Implements the 3D surface area heuristic for use by the GenericKDTree construction algorithm...
Definition: sahkdtree3.h:39
Hashed mailbox implementation.
Definition: sahkdtree3.h:138
Float mint
Definition: sahkdtree3.h:157
FINLINE RayStatistics rayIntersectHavranCollectStatistics(const Ray &ray, Float mint, Float maxt, Float &t, void *temp) const
Internal kd-tree traversal implementation (Havran variant)
Definition: sahkdtree3.h:330
Float t
Definition: sahkdtree3.h:165
#define SAssert(cond)
``Static&#39;&#39; assertion (to be used outside of classes that derive from Object)
Definition: logger.h:79
Optimized KD-tree acceleration data structure for n-dimensional (n&lt;=4) shapes and various queries on ...
Definition: gkdtree.h:706
const Derived * cast() const
Cast to the derived class (const version)
Definition: sahkdtree3.h:131
Definition: fwd.h:99
#define SIZE_T_FMT
Definition: platform.h:92
Reference counting helper.
Definition: ref.h:40
Point p
Definition: sahkdtree3.h:169
Encapsulates a 4x4 linear transformation and its inverse.
Definition: transform.h:33
Definition: fwd.h:65
Definition: fwd.h:96
Vector squareToUniformSphere(const Point2 &sample)
Uniformly sample a vector on the unit sphere with respect to solid angles.
FINLINE bool rayIntersectHavran(const Ray &ray, Float mint, Float maxt, Float &t, void *temp) const
Ray tracing kd-tree traversal loop (Havran variant)
Definition: sahkdtree3.h:179
bool contains(IndexType primIndex) const
Definition: sahkdtree3.h:147
const KDNode *__restrict node
Definition: sahkdtree3.h:156
Basic 4x4 matrix data type.
Definition: matrix.h:656
VectorType getExtents() const
Calculate the bounding box extents.
Definition: aabb.h:292
GenericKDTree< AABB, SurfaceAreaHeuristic3, Derived > Parent
Definition: sahkdtree3.h:109
void buildInternal()
Definition: sahkdtree3.h:119
void findCosts(Float &traversalCost, Float &intersectionCost)
Empirically find the best traversal and intersection cost values.
Definition: sahkdtree3.h:509
#define MTS_KD_MAILBOX_SIZE
Definition: sahkdtree3.h:31
SurfaceAreaHeuristic3(const AABB &aabb)
Initialize the surface area heuristic with the bounds of a parent node.
Definition: sahkdtree3.h:48
Definition: fwd.h:100
KDTreeBase< AABB >::KDNode KDNode
Definition: sahkdtree3.h:112
bool foundIntersection
Definition: sahkdtree3.h:311
const KDNode *__restrict node
Definition: sahkdtree3.h:163
#define MTS_KD_MAILBOX_MASK
Definition: sahkdtree3.h:32
Point center
Definition: bsphere.h:33
Derived * cast()
Cast to the derived class.
Definition: sahkdtree3.h:126
Ray traversal stack entry for Havran-style incoherent ray tracing.
Definition: sahkdtree3.h:161
Definition: fwd.h:97
Specializes GenericKDTree to a three-dimensional tree to be used for ray tracing. ...
Definition: sahkdtree3.h:107
#define MTS_NAMESPACE_END
Definition: platform.h:138
static Float getQuantity(const AABB &aabb)
Definition: sahkdtree3.h:79