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 | |
47 | using namespace foundation; |
48 | using namespace std; |
49 | |
50 | TEST_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 | |
106 | TEST_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 | |