Mitsuba Renderer  0.5.0
sahkdtree2.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
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_SAHKDTREE2_H_)
21 #define __MITSUBA_RENDER_SAHKDTREE2_H_
22
23 #include <mitsuba/core/aabb.h>
24 #include <mitsuba/render/gkdtree.h>
25 #include <mitsuba/core/warp.h>
26
28
29 /**
30  * \brief Implements the 2D surface area heuristic for use
31  * by the \ref GenericKDTree construction algorithm.
32  * \ingroup librender
33  */
35 public:
36  /**
37  * \brief Initialize the surface area heuristic with the bounds of
38  * a parent node
39  *
40  * Precomputes some information so that traversal probabilities
41  * of potential split planes can be evaluated efficiently
42  */
43  inline SurfaceAreaHeuristic2(const AABB2 &aabb) {
44  m_extents = aabb.getExtents();
45  m_normalization = 1.0f / (m_extents.x + m_extents.y);
46  }
47
48  /**
49  * Given a split on axis \a axis that produces children having extents
50  * \a leftWidth and \a rightWidth along \a axis, compute the probability
51  * of traversing the left and right child during a typical query
52  * operation.
53  */
54  inline std::pair<Float, Float> operator()(int axis, Float leftWidth, Float rightWidth) const {
55  return std::pair<Float, Float>(
56  (m_extents[1-axis] + leftWidth) * m_normalization,
57  (m_extents[1-axis] + rightWidth) * m_normalization);
58  }
59
60  /**
61  * Compute the underlying quantity used by the tree construction
62  * heuristic. This is used to compute the final cost of a kd-tree.
63  */
64  inline static Float getQuantity(const AABB2 &aabb) {
65  return aabb.getSurfaceArea();
66  }
67 private:
68  Float m_normalization;
69  Vector2 m_extents;
70 };
71
72 /**
73  * \brief Specializes \ref GenericKDTree to a two-dimensional
74  * tree to be used for flatland ray tracing.
75  *
76  * One additional function call must be implemented by subclasses:
77  * \code
78  * /// Check whether a primitive is intersected by the given ray.
79  * /// Some temporary space is supplied, which can be used to cache
80  * /// information about the intersection
81  * bool intersect(const Ray2 &ray, IndexType idx,
82  * Float mint, Float maxt, Float &t, void *tmp);
83  * \endcode
84  *
85  * This class implements an epsilon-free version of the optimized ray
86  * traversal algorithm (TA^B_{rec}), which is explained in Vlastimil
87  * Havran's PhD thesis "Heuristic Ray Shooting Algorithms".
88  *
89  * \author Wenzel Jakob
90  * \ingroup librender
91  */
92 template <typename Derived>
93  class SAHKDTree2D : public GenericKDTree<AABB2, SurfaceAreaHeuristic2, Derived> {
94 public:
99
100  using Parent::m_nodes;
101  using Parent::m_aabb;
102  using Parent::m_indices;
103
104 protected:
105  void buildInternal() {
106  SizeType primCount = cast()->getPrimitiveCount();
107  KDLog(EInfo, "Constructing a SAH kd-tree (%i primitives) ..", primCount);
109  }
110
111  /// Cast to the derived class
112  inline Derived *cast() {
113  return static_cast<Derived *>(this);
114  }
115
116  /// Cast to the derived class (const version)
117  inline const Derived *cast() const {
118  return static_cast<const Derived *>(this);
119  }
120
121  /// Ray traversal stack entry for Wald-style incoherent ray tracing
122  struct KDStackEntry {
123  const KDNode * __restrict node;
124  Float mint, maxt;
125  };
126
127  /// Ray traversal stack entry for Havran-style incoherent ray tracing
129  /* Pointer to the far child */
130  const KDNode * __restrict node;
131  /* Distance traveled along the ray (entry or exit) */
133  /* Previous stack item */
135  /* Associated point */
137  };
138
139  /**
140  * \brief Ray tracing kd-tree traversal loop (Havran variant)
141  *
142  * This is generally the most robust and fastest traversal routine
143  * of the methods implemented in this class.
144  */
145  FINLINE bool rayIntersectHavran(const Ray2 &ray, Float mint, Float maxt,
146  Float &t, void *temp) const {
148
149  /* Set up the entry point */
150  uint32_t enPt = 0;
151  stack[enPt].t = mint;
152  stack[enPt].p = ray(mint);
153
154  /* Set up the exit point */
155  uint32_t exPt = 1;
156  stack[exPt].t = maxt;
157  stack[exPt].p = ray(maxt);
158  stack[exPt].node = NULL;
159
160  bool foundIntersection = false;
161  const KDNode * __restrict currNode = m_nodes;
162  while (currNode != NULL) {
163  while (EXPECT_TAKEN(!currNode->isLeaf())) {
164  const Float splitVal = (Float) currNode->getSplit();
165  const int axis = currNode->getAxis();
166  const KDNode * __restrict farChild;
167
168  if (stack[enPt].p[axis] <= splitVal) {
169  if (stack[exPt].p[axis] <= splitVal) {
170  /* Cases N1, N2, N3, P5, Z2 and Z3 (see thesis) */
171  currNode = currNode->getLeft();
172  continue;
173  }
174
175  /* Typo in Havran's thesis:
176  (it specifies "stack[exPt].p == splitVal", which
177  is clearly incorrect) */
178  if (stack[enPt].p[axis] == splitVal) {
179  /* Case Z1 */
180  currNode = currNode->getRight();
181  continue;
182  }
183
184  /* Case N4 */
185  currNode = currNode->getLeft();
186  farChild = currNode + 1; // getRight()
187  } else { /* stack[enPt].p[axis] > splitVal */
188  if (splitVal < stack[exPt].p[axis]) {
189  /* Cases P1, P2, P3 and N5 */
190  currNode = currNode->getRight();
191  continue;
192  }
193  /* Case P4 */
194  farChild = currNode->getLeft();
195  currNode = farChild + 1; // getRight()
196  }
197
198  /* Cases P4 and N4 -- calculate the distance to the split plane */
199  Float distToSplit = (splitVal - ray.o[axis]) * ray.dRcp[axis];
200
201  /* Set up a new exit point */
202  const uint32_t tmp = exPt++;
203  if (exPt == enPt) /* Do not overwrite the entry point */
204  ++exPt;
205
206  KDAssert(exPt < MTS_KD_MAXDEPTH);
207  stack[exPt].prev = tmp;
208  stack[exPt].t = distToSplit;
209  stack[exPt].node = farChild;
210
211  /* Intrestingly, this appears to be faster than the
212  original code with the prevAxis & nextAxis table */
213  stack[exPt].p = ray(distToSplit);
214  stack[exPt].p[axis] = splitVal;
215  }
216
217  /* Reached a leaf node */
218  for (IndexType entry=currNode->getPrimStart(),
219  last = currNode->getPrimEnd(); entry != last; entry++) {
220  const IndexType primIdx = m_indices[entry];
221
222  bool result = cast()->intersect(ray, primIdx, mint, maxt, t, temp);
223
224  if (result) {
225  maxt = t;
226  foundIntersection = true;
227  }
228  }
229
230  if (stack[exPt].t > maxt)
231  break;
232
233  /* Pop from the stack and advance to the next node on the interval */
234  enPt = exPt;
235  currNode = stack[exPt].node;
236  exPt = stack[enPt].prev;
237  }
238
239  return foundIntersection;
240  }
241 };
242
244
245 #endif /* __MITSUBA_RENDER_SAHKDTREE2_H_ */
#define KDLog(level, fmt,...)
Definition: gkdtree.h:642
SurfaceAreaHeuristic2(const AABB2 &aabb)
Initialize the surface area heuristic with the bounds of a parent node.
Definition: sahkdtree2.h:43
Derived * cast()
Cast to the derived class.
Definition: sahkdtree2.h:112
KDTreeBase< AABB2 >::SizeType SizeType
Definition: sahkdtree2.h:96
Point2 p
Definition: sahkdtree2.h:136
Float t
Definition: sahkdtree2.h:132
std::pair< Float, Float > operator()(int axis, Float leftWidth, Float rightWidth) const
Definition: sahkdtree2.h:54
#define KDAssert(expr)
Definition: gkdtree.h:56
Base class of all kd-trees.
Definition: gkdtree.h:441
uint32_t prev
Definition: sahkdtree2.h:134
#define MTS_NAMESPACE_BEGIN
Definition: platform.h:137
#define MTS_KD_MAXDEPTH
Activate lots of extra checks.
Definition: gkdtree.h:37
static Float getQuantity(const AABB2 &aabb)
Definition: sahkdtree2.h:64
More relevant debug / information message.
Definition: formatter.h:31
Definition: fwd.h:103
Implements the 2D surface area heuristic for use by the GenericKDTree construction algorithm...
Definition: sahkdtree2.h:34
const KDNode *__restrict node
Definition: sahkdtree2.h:130
KDTreeBase< AABB2 >::IndexType IndexType
Definition: sahkdtree2.h:97
Optimized KD-tree acceleration data structure for n-dimensional (n&lt;=4) shapes and various queries on ...
Definition: gkdtree.h:706
Definition: fwd.h:99
Definition: fwd.h:65
Ray traversal stack entry for Wald-style incoherent ray tracing.
Definition: sahkdtree2.h:122
KDTreeBase< AABB2 >::KDNode KDNode
Definition: sahkdtree2.h:98
Float mint
Definition: sahkdtree2.h:124
GenericKDTree< AABB2, SurfaceAreaHeuristic2, Derived > Parent
Definition: sahkdtree2.h:95
const KDNode *__restrict node
Definition: sahkdtree2.h:123
Specializes GenericKDTree to a two-dimensional tree to be used for flatland ray tracing.
Definition: sahkdtree2.h:93
Definition: fwd.h:95
#define MTS_NAMESPACE_END
Definition: platform.h:138
Ray traversal stack entry for Havran-style incoherent ray tracing.
Definition: sahkdtree2.h:128
const Derived * cast() const
Cast to the derived class (const version)
Definition: sahkdtree2.h:117
FINLINE bool rayIntersectHavran(const Ray2 &ray, Float mint, Float maxt, Float &t, void *temp) const
Ray tracing kd-tree traversal loop (Havran variant)
Definition: sahkdtree2.h:145
void buildInternal()
Definition: sahkdtree2.h:105