1
2//
3// This source file is part of appleseed.
4// Visit http://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-2017 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// appleseed.foundation headers.
31#include "foundation/core/concepts/noncopyable.h"
32#include "foundation/math/aabb.h"
33#include "foundation/math/bsp.h"
34#include "foundation/math/intersection/rayaabb.h"
35#include "foundation/math/ray.h"
36#include "foundation/math/split.h"
37#include "foundation/math/vector.h"
38#include "foundation/utility/test.h"
39
40// Standard headers.
41#include <algorithm>
42#include <cstddef>
43#include <limits>
44#include <memory>
45#include <vector>
46
47using namespace foundation;
48using namespace std;
49
50TEST_SUITE(Foundation_Math_BSP_Node)
51{
52 typedef bsp::Node<double> NodeType;
53
54 TEST_CASE(TestLeafNode)
55 {
56 NodeType node;
57
58 node.make_leaf();
59 EXPECT_TRUE(node.is_leaf());
60
61 node.set_leaf_index(42);
62 EXPECT_TRUE(node.is_leaf());
63 EXPECT_EQ(42, node.get_leaf_index());
64
65 const size_t LeafIndex = (size_t(1) << 31) - 1;
66 node.set_leaf_index(LeafIndex);
67 EXPECT_TRUE(node.is_leaf());
68 EXPECT_EQ(LeafIndex, node.get_leaf_index());
69 }
70
71 TEST_CASE(TestInteriorNode)
72 {
73 NodeType node;
74
75 node.make_interior();
76 EXPECT_TRUE(node.is_interior());
77
78 node.set_child_node_index(42);
79 EXPECT_TRUE(node.is_interior());
80 EXPECT_EQ(42, node.get_child_node_index());
81
82 const size_t ChildIndex = (size_t(1) << 29) - 1;
83 node.set_child_node_index(ChildIndex);
84 EXPECT_TRUE(node.is_interior());
85 EXPECT_EQ(ChildIndex, node.get_child_node_index());
86
87 node.set_split_dim(1);
88 EXPECT_TRUE(node.is_interior());
89 EXPECT_EQ(ChildIndex, node.get_child_node_index());
90 EXPECT_EQ(1, node.get_split_dim());
91
92 node.set_split_abs(66.0);
93 EXPECT_TRUE(node.is_interior());
94 EXPECT_EQ(ChildIndex, node.get_child_node_index());
95 EXPECT_EQ(1, node.get_split_dim());
96 EXPECT_EQ(66.0, node.get_split_abs());
97
98 node.set_leaf_size(33);
99 EXPECT_TRUE(node.is_interior());
100 EXPECT_EQ(ChildIndex, node.get_child_node_index());
101 EXPECT_EQ(1, node.get_split_dim());
102 EXPECT_EQ(33, node.get_leaf_size());
103 }
104}
105
106TEST_SUITE(Foundation_Math_BSP_Intersector)
107{
108 class Leaf
109 : public NonCopyable
110 {
111 public:
112 void clear()
113 {
114 m_boxes.clear();
115 }
116
117 size_t get_size() const
118 {
119 return m_boxes.size();
120 }
121
122 void insert(const AABB3d& box)
123 {
124 m_boxes.push_back(box);
125 }
126
127 const AABB3d& get_box(const size_t i) const
128 {
129 return m_boxes[i];
130 }
131
132 AABB3d get_bbox() const
133 {
134 AABB3d bbox;
135 bbox.invalidate();
136
137 for (size_t i = 0; i < m_boxes.size(); ++i)
138 bbox.insert(m_boxes[i]);
139
140 return bbox;
141 }
142
143 size_t get_memory_size() const
144 {
145 return 0;
146 }
147
148 private:
149 vector<AABB3d> m_boxes;
150 };
151
152 struct LeafFactory
153 : public NonCopyable
154 {
155 Leaf* create_leaf()
156 {
157 return new Leaf();
158 }
159 };
160
161 struct LeafSplitter
162 : public NonCopyable
163 {
164 typedef bsp::LeafInfo<double, 3> LeafInfoType;
165 typedef Split<double> SplitType;
166
167 bool m_first_leaf;
168
169 LeafSplitter()
170 : m_first_leaf(true)
171 {
172 }
173
174 double get_priority(
175 const Leaf& leaf,
176 const LeafInfoType& leaf_info)
177 {
178 const double priority = m_first_leaf ? 1.0 : 0.0;
179 m_first_leaf = false;
180 return priority;
181 }
182
183 bool split(
184 const Leaf& leaf,
185 const LeafInfoType& leaf_info,
186 SplitType& split)
187 {
188 split.m_dimension = 0;
189 split.m_abscissa = 0.0;
190 return true;
191 }
192
193 void sort(
194 const Leaf& leaf,
195 const LeafInfoType& leaf_info,
196 const SplitType& split,
197 Leaf& left_leaf,
198 const LeafInfoType& left_leaf_info,
199 Leaf& right_leaf,
200 const LeafInfoType& right_leaf_info)
201 {
202 for (size_t i = 0; i < leaf.get_size(); ++i)
203 {
204 const AABB3d& box = leaf.get_box(i);
205
206 if (box.max[split.m_dimension] <= split.m_abscissa)
207 {
208 left_leaf.insert(box);
209 }
210 else if (box.min[split.m_dimension] >= split.m_abscissa)
211 {
212 right_leaf.insert(box);
213 }
214 else
215 {
216 left_leaf.insert(box);
217 right_leaf.insert(box);
218 }
219 }
220 }
221 };
222
223 class LeafVisitor
224 : public NonCopyable
225 {
226 public:
227 LeafVisitor()
228 : m_visited_leaf_count(0)
229 , m_closest_hit(numeric_limits<double>::max())
230 {
231 }
232
233 double visit(
234 const Leaf* leaf, // todo: why not a reference?
235 const Ray3d& ray,
236 const RayInfo3d& ray_info)
237 {
238 ++m_visited_leaf_count;
239
240 for (size_t i = 0; i < leaf->get_size(); ++i)
241 {
242 const AABB3d& box = leaf->get_box(i);
243
244 double distance;
245
246 if (intersect(ray, ray_info, box, distance))
247 m_closest_hit = min(m_closest_hit, distance);
248 }
249
250 return m_closest_hit;
251 }
252
253 size_t get_visited_leaf_count() const
254 {
255 return m_visited_leaf_count;
256 }
257
258 double get_closest_hit() const
259 {
260 return m_closest_hit;
261 }
262
263 private:
264 size_t m_visited_leaf_count;
265 double m_closest_hit;
266 };
267
268 struct Fixture
269 {
270 typedef bsp::Tree<double, 3, Leaf> Tree;
271 typedef bsp::Intersector<double, Tree, LeafVisitor, Ray3d> Intersector;
272
273 Tree m_tree;
274 LeafVisitor m_leaf_visitor; // todo: Visitor or LeafVisitor?
275 Intersector m_intersector;
276 bsp::TraversalStatistics m_traversal_stats;
277
278 Fixture()
279 {
280 auto_ptr<Leaf> root_leaf(new Leaf());
281 root_leaf->insert(AABB3d(Vector3d(-1.0, -0.5, -0.2), Vector3d(0.0, 0.5, 0.2)));
282 root_leaf->insert(AABB3d(Vector3d(0.0, -0.5, -0.7), Vector3d(1.0, 0.5, 0.7)));
283
284 bsp::Builder<Tree, LeafFactory, LeafSplitter> builder;
285 LeafFactory leaf_factory;
286 LeafSplitter leaf_splitter;
287
288 builder.build(m_tree, root_leaf, leaf_factory, leaf_splitter);
289 }
290 };
291
292#ifdef FOUNDATION_BSP_ENABLE_TRAVERSAL_STATS
293#define TRAVERSAL_STATISTICS , m_traversal_stats
294#else
295#define TRAVERSAL_STATISTICS
296#endif
297
298#pragma warning (push)
299#pragma warning (disable : 4723) // potential division by 0
300
301 TEST_CASE_F(Intersect_GivenRayEmbeddedInSplitPlane_VisitsBothLeaves, Fixture)
302 {
303 Ray3d ray(Vector3d(0.0, 0.0, 1.0), Vector3d(0.0, 0.0, -1.0));
304
305 m_intersector.intersect(m_tree, ray, RayInfo3d(ray), m_leaf_visitor TRAVERSAL_STATISTICS);
306
307 EXPECT_EQ(2, m_leaf_visitor.get_visited_leaf_count());
308 EXPECT_FEQ(1.0 - 0.7, m_leaf_visitor.get_closest_hit());
309 }
310
311 TEST_CASE_F(Intersect_GivenRayPiercingLeftNode_VisitsLeftNode, Fixture)
312 {
313 Ray3d ray(Vector3d(-0.5, 0.0, 1.0), Vector3d(0.0, 0.0, -1.0));
314
315 m_intersector.intersect(m_tree, ray, RayInfo3d(ray), m_leaf_visitor TRAVERSAL_STATISTICS);
316
317 EXPECT_EQ(1, m_leaf_visitor.get_visited_leaf_count());
318 EXPECT_FEQ(1.0 - 0.2, m_leaf_visitor.get_closest_hit());
319 }
320
321 TEST_CASE_F(Intersect_GivenRayPiercingRightNode_VisitsRightNode, Fixture)
322 {
323 Ray3d ray(Vector3d(0.5, 0.0, 1.0), Vector3d(0.0, 0.0, -1.0));
324
325 m_intersector.intersect(m_tree, ray, RayInfo3d(ray), m_leaf_visitor TRAVERSAL_STATISTICS);
326
327 EXPECT_EQ(1, m_leaf_visitor.get_visited_leaf_count());
328 EXPECT_FEQ(1.0 - 0.7, m_leaf_visitor.get_closest_hit());
329 }
330
331#pragma warning (pop)
332
333#undef TRAVERSAL_STATISTICS
334}
335