1
2 //
3 // This source file is part of appleseed.
4 // Visit https://appleseedhq.net/ for additional information and resources.
5 //
6 // This software is released under the MIT license.
7 //
8 // Copyright (c) 2010-2013 Francois Beaune, Jupiter Jazz Limited
9 // Copyright (c) 2014-2018 Francois Beaune, The appleseedhq Organization
10 //
11 // Permission is hereby granted, free of charge, to any person obtaining a copy
12 // of this software and associated documentation files (the "Software"), to deal
13 // in the Software without restriction, including without limitation the rights
14 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15 // copies of the Software, and to permit persons to whom the Software is
16 // furnished to do so, subject to the following conditions:
17 //
18 // The above copyright notice and this permission notice shall be included in
19 // all copies or substantial portions of the Software.
20 //
21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
27 // THE SOFTWARE.
28 //
29
30 #pragma once
31
32 // appleseed.foundation headers.
33 #include "foundation/platform/compiler.h"
34 #include "foundation/platform/types.h"
35
36 // Standard headers.
37 #include <cassert>
38 #include <cstddef>
39
40 namespace foundation {
41 namespace bvh {
42
43 //
44 // Node (leaf node or interior node) of a BVH.
45 //
46
47 template <typename AABB>
48 class APPLESEED_ALIGN(64) Node
49 {
50 public:
51 typedef AABB AABBType;
52
53 // Set/get the node type.
54 void make_interior();
55 void make_leaf();
56 bool is_interior() const;
57 bool is_leaf() const;
58
59 // Set/get the bounding boxes of the child nodes (interior nodes only, static case).
60 void set_left_bbox(const AABBType& bbox);
61 void set_right_bbox(const AABBType& bbox);
62 AABBType get_left_bbox() const;
63 AABBType get_right_bbox() const;
64
65 // Set/get the bounding boxes of the child nodes (interior nodes only, motion case).
66 void set_left_bbox_index(const size_t index);
67 void set_left_bbox_count(const size_t count);
68 void set_right_bbox_index(const size_t index);
69 void set_right_bbox_count(const size_t count);
70 size_t get_left_bbox_index() const;
71 size_t get_left_bbox_count() const;
72 size_t get_right_bbox_index() const;
73 size_t get_right_bbox_count() const;
74
75 // Access user data (leaf nodes only).
76 static const size_t MaxUserDataSize;
77 template <typename U> void set_user_data(const U& data);
78 template <typename U> const U& get_user_data() const;
79 template <typename U> U& get_user_data();
80
81 // Set/get the index of the first child node (interior nodes only).
82 void set_child_node_index(const size_t index);
83 size_t get_child_node_index() const;
84
85 // Set/get the index of the first item (leaf nodes only).
86 void set_item_index(const size_t index);
87 size_t get_item_index() const;
88
89 // Set/get the item count (leaf nodes only).
90 void set_item_count(const size_t count);
91 size_t get_item_count() const;
92
93 private:
94 template <typename Tree, typename Visitor, typename Ray, size_t StackSize, size_t N>
95 friend class Intersector;
96
97 typedef typename AABBType::ValueType ValueType;
98 static const size_t Dimension = AABBType::Dimension;
99
100 uint32 m_item_count;
101 uint32 m_index;
102 uint32 m_left_bbox_index;
103 uint32 m_left_bbox_count;
104 uint32 m_right_bbox_index;
105 uint32 m_right_bbox_count;
106
107 APPLESEED_SIMD4_ALIGN ValueType m_bbox_data[4 * Dimension];
108 };
109
110
111 //
112 // Node class implementation.
113 //
114
115 template <typename AABB>
make_interior()116 inline void Node<AABB>::make_interior()
117 {
118 m_item_count = ~uint32(0);
119 }
120
121 template <typename AABB>
make_leaf()122 inline void Node<AABB>::make_leaf()
123 {
124 if (m_item_count == ~uint32(0))
125 m_item_count = 0;
126 }
127
128 template <typename AABB>
is_interior()129 inline bool Node<AABB>::is_interior() const
130 {
131 return m_item_count == ~uint32(0);
132 }
133
134 template <typename AABB>
is_leaf()135 inline bool Node<AABB>::is_leaf() const
136 {
137 return m_item_count != ~uint32(0);
138 }
139
140 template <typename AABB>
set_left_bbox(const AABBType & bbox)141 inline void Node<AABB>::set_left_bbox(const AABBType& bbox)
142 {
143 assert(is_interior());
144
145 for (size_t i = 0; i < Dimension; ++i)
146 {
147 m_bbox_data[i * 4 + 0] = bbox.min[i];
148 m_bbox_data[i * 4 + 2] = bbox.max[i];
149 }
150 }
151
152 template <typename AABB>
set_right_bbox(const AABBType & bbox)153 inline void Node<AABB>::set_right_bbox(const AABBType& bbox)
154 {
155 assert(is_interior());
156
157 for (size_t i = 0; i < Dimension; ++i)
158 {
159 m_bbox_data[i * 4 + 1] = bbox.min[i];
160 m_bbox_data[i * 4 + 3] = bbox.max[i];
161 }
162 }
163
164 template <typename AABB>
get_left_bbox()165 inline AABB Node<AABB>::get_left_bbox() const
166 {
167 assert(is_interior());
168
169 AABBType bbox;
170
171 for (size_t i = 0; i < Dimension; ++i)
172 {
173 bbox.min[i] = m_bbox_data[i * 4 + 0];
174 bbox.max[i] = m_bbox_data[i * 4 + 2];
175 }
176
177 return bbox;
178 }
179
180 template <typename AABB>
get_right_bbox()181 inline AABB Node<AABB>::get_right_bbox() const
182 {
183 assert(is_interior());
184
185 AABBType bbox;
186
187 for (size_t i = 0; i < Dimension; ++i)
188 {
189 bbox.min[i] = m_bbox_data[i * 4 + 1];
190 bbox.max[i] = m_bbox_data[i * 4 + 3];
191 }
192
193 return bbox;
194 }
195
196 template <typename AABB>
set_left_bbox_index(const size_t index)197 inline void Node<AABB>::set_left_bbox_index(const size_t index)
198 {
199 assert(is_interior());
200 assert(index <= 0xFFFFFFFFu);
201 m_left_bbox_index = static_cast<uint32>(index);
202 }
203
204 template <typename AABB>
set_left_bbox_count(const size_t count)205 inline void Node<AABB>::set_left_bbox_count(const size_t count)
206 {
207 assert(is_interior());
208 assert(count <= 0xFFFFFFFFu);
209 m_left_bbox_count = static_cast<uint32>(count);
210 }
211
212 template <typename AABB>
set_right_bbox_index(const size_t index)213 inline void Node<AABB>::set_right_bbox_index(const size_t index)
214 {
215 assert(is_interior());
216 assert(index <= 0xFFFFFFFFu);
217 m_right_bbox_index = static_cast<uint32>(index);
218 }
219
220 template <typename AABB>
set_right_bbox_count(const size_t count)221 inline void Node<AABB>::set_right_bbox_count(const size_t count)
222 {
223 assert(is_interior());
224 assert(count <= 0xFFFFFFFFu);
225 m_right_bbox_count = static_cast<uint32>(count);
226 }
227
228 template <typename AABB>
get_left_bbox_index()229 inline size_t Node<AABB>::get_left_bbox_index() const
230 {
231 assert(is_interior());
232 return static_cast<uint32>(m_left_bbox_index);
233 }
234
235 template <typename AABB>
get_left_bbox_count()236 inline size_t Node<AABB>::get_left_bbox_count() const
237 {
238 assert(is_interior());
239 return static_cast<uint32>(m_left_bbox_count);
240 }
241
242 template <typename AABB>
get_right_bbox_index()243 inline size_t Node<AABB>::get_right_bbox_index() const
244 {
245 assert(is_interior());
246 return static_cast<uint32>(m_right_bbox_index);
247 }
248
249 template <typename AABB>
get_right_bbox_count()250 inline size_t Node<AABB>::get_right_bbox_count() const
251 {
252 assert(is_interior());
253 return static_cast<uint32>(m_right_bbox_count);
254 }
255
256 #define MAX_USER_DATA_SIZE (4 * Node<AABB>::Dimension * sizeof(typename AABB::ValueType))
257
258 template <typename AABB>
259 const size_t Node<AABB>::MaxUserDataSize = MAX_USER_DATA_SIZE;
260
261 template <typename AABB>
262 template <typename U>
set_user_data(const U & data)263 inline void Node<AABB>::set_user_data(const U& data)
264 {
265 assert(is_leaf());
266 get_user_data<U>() = data;
267 }
268
269 template <typename AABB>
270 template <typename U>
get_user_data()271 inline const U& Node<AABB>::get_user_data() const
272 {
273 static_assert(sizeof(U) <= MAX_USER_DATA_SIZE, "Not enough space in BVH node for user data");
274 assert(is_leaf());
275 return *reinterpret_cast<const U*>(m_bbox_data);
276 }
277
278 template <typename AABB>
279 template <typename U>
get_user_data()280 inline U& Node<AABB>::get_user_data()
281 {
282 static_assert(sizeof(U) <= MAX_USER_DATA_SIZE, "Not enough space in BVH node for user data");
283 assert(is_leaf());
284 return *reinterpret_cast<U*>(m_bbox_data);
285 }
286
287 #undef MAX_USER_DATA_SIZE
288
289 template <typename AABB>
set_child_node_index(const size_t index)290 inline void Node<AABB>::set_child_node_index(const size_t index)
291 {
292 assert(is_interior());
293 assert(index <= 0xFFFFFFFFu);
294 m_index = static_cast<uint32>(index);
295 }
296
297 template <typename AABB>
get_child_node_index()298 inline size_t Node<AABB>::get_child_node_index() const
299 {
300 assert(is_interior());
301 return static_cast<size_t>(m_index);
302 }
303
304 template <typename AABB>
set_item_index(const size_t index)305 inline void Node<AABB>::set_item_index(const size_t index)
306 {
307 assert(is_leaf());
308 assert(index <= 0xFFFFFFFFu);
309 m_index = static_cast<uint32>(index);
310 }
311
312 template <typename AABB>
get_item_index()313 inline size_t Node<AABB>::get_item_index() const
314 {
315 assert(is_leaf());
316 return static_cast<size_t>(m_index);
317 }
318
319 template <typename AABB>
set_item_count(const size_t count)320 inline void Node<AABB>::set_item_count(const size_t count)
321 {
322 assert(is_leaf());
323 assert(count < 0xFFFFFFFFu);
324 m_item_count = static_cast<uint32>(count);
325 }
326
327 template <typename AABB>
get_item_count()328 inline size_t Node<AABB>::get_item_count() const
329 {
330 assert(is_leaf());
331 return static_cast<size_t>(m_item_count);
332 }
333
334 } // namespace bvh
335 } // namespace foundation
336