Line data Source code
1 : /**
2 : * @file test_TraverseAABB.cpp
3 : *
4 : * @brief Test for TraverseAABB class
5 : *
6 : * @author David Frank - initial code
7 : * @author Maximilian Hornung - modularization, fixes
8 : * @author Tobias Lasser - minor fixes
9 : */
10 :
11 : #include "doctest/doctest.h"
12 :
13 : #include "TraverseAABB.h"
14 : #include "Intersection.h"
15 :
16 : using namespace elsa;
17 : using namespace doctest;
18 :
19 : using Ray = Eigen::ParametrizedLine<real_t, Eigen::Dynamic>;
20 :
21 1691 : bool intersect(const RealVector_t& voxel, const Ray& r)
22 : {
23 : // pre-check parallel rays
24 4689 : for (index_t i = 0; i < r.dim(); ++i) {
25 3254 : real_t tmp = std::abs(r.origin()(i) - voxel(i));
26 :
27 3254 : if (std::abs(r.direction()(i)) < 0.0000001 && tmp >= 0.0 && tmp < 1.0)
28 256 : return true;
29 : }
30 :
31 : // check if ray intersects pixel
32 2870 : IndexVector_t ones(voxel.size());
33 1435 : ones.setOnes();
34 1435 : BoundingBox bb(ones);
35 1435 : bb._min += voxel;
36 1435 : bb._max += voxel;
37 :
38 1435 : return Intersection::withRay(bb, r).operator bool();
39 : }
40 :
41 28 : TEST_CASE("TraverseAABB: Construction of a 2D traversal object")
42 : {
43 : // setup
44 28 : size_t dim = 2;
45 28 : index_t x = 3;
46 28 : index_t y = 3;
47 56 : IndexVector_t volumeDims(dim);
48 28 : volumeDims << x, y;
49 :
50 56 : RealVector_t spacing(dim);
51 :
52 56 : RealVector_t ro(dim);
53 56 : RealVector_t rd(dim);
54 :
55 56 : GIVEN("A 3x3 aabb with standard spacing")
56 : {
57 56 : BoundingBox aabb(volumeDims);
58 :
59 : //================================
60 : // intersection from straight rays from the bottom
61 : //================================
62 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (0.5, "
63 : "-0.5) and direction (0, 1)")
64 : {
65 1 : ro << 0.5, -0.5;
66 1 : rd << 0.0, 1.0;
67 2 : Ray r(ro, rd);
68 :
69 2 : TraverseAABB traverse(aabb, r);
70 1 : CHECK_UNARY(traverse.isInBoundingBox());
71 2 : THEN("The ray intersects the aabb at the bottom left pixel")
72 : {
73 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
74 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
75 : }
76 : }
77 :
78 29 : WHEN("A ray with origin = (1.0, -0.5) and direction (0, 1), hits the boundary between 2 "
79 : "voxels")
80 : {
81 1 : ro << 1.0, -0.5;
82 1 : rd << 0.0, 1.0;
83 2 : Ray r(ro, rd);
84 :
85 2 : TraverseAABB traverse(aabb, r);
86 1 : CHECK_UNARY(traverse.isInBoundingBox());
87 2 : THEN("The ray intersects the aabb at the bottom left pixel")
88 : {
89 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 1);
90 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
91 : }
92 : }
93 :
94 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (1.5, "
95 : "-0.5) and direction (0, 1)")
96 : {
97 1 : ro << 1.5, -0.5;
98 1 : rd << 0.0, 1.0;
99 2 : Ray r(ro, rd);
100 :
101 2 : TraverseAABB traverse(aabb, r);
102 1 : CHECK_UNARY(traverse.isInBoundingBox());
103 2 : THEN("The ray intersects the aabb at the bottom left pixel")
104 : {
105 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 1);
106 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
107 : }
108 : }
109 :
110 29 : WHEN("A ray with origin = (2.0, -0.5) and direction (0, 1), hits the boundary between 2 "
111 : "voxels")
112 : {
113 1 : ro << 2.0, -0.5;
114 1 : rd << 0.0, 1.0;
115 2 : Ray r(ro, rd);
116 :
117 2 : TraverseAABB traverse(aabb, r);
118 1 : CHECK_UNARY(traverse.isInBoundingBox());
119 2 : THEN("The ray intersects the aabb at the bottom left pixel")
120 : {
121 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 2);
122 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
123 : }
124 : }
125 :
126 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (2.5, "
127 : "-0.5) and direction (0, 1)")
128 : {
129 1 : ro << 2.5, -0.5;
130 1 : rd << 0.0, 1.0;
131 2 : Ray r(ro, rd);
132 :
133 2 : TraverseAABB traverse(aabb, r);
134 1 : CHECK_UNARY(traverse.isInBoundingBox());
135 2 : THEN("The ray intersects the aabb at the bottom left pixel")
136 : {
137 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 2);
138 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
139 : }
140 : }
141 :
142 : //================================
143 : // intersection from straight rays from the left
144 : //================================
145 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (-0.5, "
146 : "0.5) and direction (1, 0)")
147 : {
148 1 : ro << -0.5, 0.5;
149 1 : rd << 1.0, 0.0;
150 2 : Ray r(ro, rd);
151 :
152 2 : TraverseAABB traverse(aabb, r);
153 1 : CHECK_UNARY(traverse.isInBoundingBox());
154 2 : THEN("The ray intersects the aabb at the bottom left pixel")
155 : {
156 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
157 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
158 : }
159 : }
160 :
161 29 : WHEN("A ray with origin = (1.0, -0.5) and direction (0, 1), hits the boundary between 2 "
162 : "voxels")
163 : {
164 1 : ro << -0.5, 1.0;
165 1 : rd << 1.0, 0.0;
166 2 : Ray r(ro, rd);
167 :
168 2 : TraverseAABB traverse(aabb, r);
169 1 : CHECK_UNARY(traverse.isInBoundingBox());
170 2 : THEN("The ray intersects the aabb at the bottom left pixel")
171 : {
172 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
173 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 1);
174 : }
175 : }
176 :
177 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (-0.5, "
178 : "1.5) and direction (1, 0)")
179 : {
180 1 : ro << -0.5, 1.5;
181 1 : rd << 1.0, 0.0;
182 2 : Ray r(ro, rd);
183 :
184 2 : TraverseAABB traverse(aabb, r);
185 1 : CHECK_UNARY(traverse.isInBoundingBox());
186 2 : THEN("The ray intersects the aabb at the bottom left pixel")
187 : {
188 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
189 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 1);
190 : }
191 : }
192 :
193 29 : WHEN("A ray with origin = (2.0, -0.5) and direction (0, 1), hits the boundary between 2 "
194 : "voxels")
195 : {
196 1 : ro << -0.5, 2.0;
197 1 : rd << 1.0, 0.0;
198 2 : Ray r(ro, rd);
199 :
200 2 : TraverseAABB traverse(aabb, r);
201 1 : CHECK_UNARY(traverse.isInBoundingBox());
202 2 : THEN("The ray intersects the aabb at the bottom left pixel")
203 : {
204 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
205 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 2);
206 : }
207 : }
208 :
209 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (-0.5, "
210 : "2.5) and direction (1, 0)")
211 : {
212 1 : ro << -0.5, 2.5;
213 1 : rd << 1.0, 0.0;
214 2 : Ray r(ro, rd);
215 :
216 2 : TraverseAABB traverse(aabb, r);
217 1 : CHECK_UNARY(traverse.isInBoundingBox());
218 2 : THEN("The ray intersects the aabb at the bottom left pixel")
219 : {
220 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
221 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 2);
222 : }
223 : }
224 :
225 : //================================
226 : // intersection from straight rays from the right
227 : //================================
228 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (3.5, "
229 : "0.5) and direction (-1, 0)")
230 : {
231 1 : ro << 3.5, 0.5;
232 1 : rd << -1.0, 0.0;
233 2 : Ray r(ro, rd);
234 :
235 2 : TraverseAABB traverse(aabb, r);
236 1 : CHECK_UNARY(traverse.isInBoundingBox());
237 2 : THEN("The ray intersects the aabb at the bottom left pixel")
238 : {
239 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 2);
240 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
241 : }
242 : }
243 :
244 29 : WHEN("A ray with origin = (3.5, 1.0) and direction (-1, 0), hits the boundary between 2 "
245 : "voxels")
246 : {
247 1 : ro << 3.5, 1.0;
248 1 : rd << -1.0, 0.0;
249 2 : Ray r(ro, rd);
250 :
251 2 : TraverseAABB traverse(aabb, r);
252 1 : CHECK_UNARY(traverse.isInBoundingBox());
253 2 : THEN("The ray intersects the aabb at the bottom left pixel")
254 : {
255 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 2);
256 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 1);
257 : }
258 : }
259 :
260 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (3.5, "
261 : "1.5) and direction (-1, 0)")
262 : {
263 1 : ro << 3.5, 1.5;
264 1 : rd << -1.0, 0.0;
265 2 : Ray r(ro, rd);
266 :
267 2 : TraverseAABB traverse(aabb, r);
268 1 : CHECK_UNARY(traverse.isInBoundingBox());
269 2 : THEN("The ray intersects the aabb at the bottom left pixel")
270 : {
271 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 2);
272 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 1);
273 : }
274 : }
275 :
276 29 : WHEN("A ray with origin = (3.5, 2.0) and direction (-1, 0), hits the boundary between 2 "
277 : "voxels")
278 : {
279 1 : ro << 3.5, 2.0;
280 1 : rd << -1.0, 0.0;
281 2 : Ray r(ro, rd);
282 :
283 2 : TraverseAABB traverse(aabb, r);
284 1 : CHECK_UNARY(traverse.isInBoundingBox());
285 2 : THEN("The ray intersects the aabb at the bottom left pixel")
286 : {
287 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 2);
288 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 2);
289 : }
290 : }
291 :
292 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (3.5, "
293 : "2.5) and direction (-1, 0)")
294 : {
295 1 : ro << 3.5, 2.5;
296 1 : rd << -1.0, 0.0;
297 2 : Ray r(ro, rd);
298 :
299 2 : TraverseAABB traverse(aabb, r);
300 1 : CHECK_UNARY(traverse.isInBoundingBox());
301 2 : THEN("The ray intersects the aabb at the bottom left pixel")
302 : {
303 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 2);
304 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 2);
305 : }
306 : }
307 :
308 : //================================
309 : // intersection from straight rays from the top
310 : //================================
311 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (0.5, "
312 : "3.5) and direction (0, -1)")
313 : {
314 1 : ro << 0.5, 3.5;
315 1 : rd << 0.0, -1.0;
316 2 : Ray r(ro, rd);
317 :
318 2 : TraverseAABB traverse(aabb, r);
319 1 : CHECK_UNARY(traverse.isInBoundingBox());
320 2 : THEN("The ray intersects the aabb at the bottom left pixel")
321 : {
322 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
323 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 2);
324 : }
325 : }
326 :
327 29 : WHEN("A ray with origin = (1.0, 3.5) and direction (-1, 0), hits the boundary between 2 "
328 : "voxels")
329 : {
330 1 : ro << 1.0, 3.5;
331 1 : rd << 0.0, -1.0;
332 2 : Ray r(ro, rd);
333 :
334 2 : TraverseAABB traverse(aabb, r);
335 1 : CHECK_UNARY(traverse.isInBoundingBox());
336 2 : THEN("The ray intersects the aabb at the bottom left pixel")
337 : {
338 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 1);
339 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 2);
340 : }
341 : }
342 :
343 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (1.5, "
344 : "3.5) and direction (0, -1)")
345 : {
346 1 : ro << 1.5, 3.5;
347 1 : rd << 0.0, -1.0;
348 2 : Ray r(ro, rd);
349 :
350 2 : TraverseAABB traverse(aabb, r);
351 1 : CHECK_UNARY(traverse.isInBoundingBox());
352 2 : THEN("The ray intersects the aabb at the bottom left pixel")
353 : {
354 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 1);
355 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 2);
356 : }
357 : }
358 :
359 29 : WHEN("A ray with origin = (2.0, 3.5) and direction (-1, 0), hits the boundary between 2 "
360 : "voxels")
361 : {
362 1 : ro << 2.0, 3.5;
363 1 : rd << 0.0, -1.0;
364 2 : Ray r(ro, rd);
365 :
366 2 : TraverseAABB traverse(aabb, r);
367 1 : CHECK_UNARY(traverse.isInBoundingBox());
368 2 : THEN("The ray intersects the aabb at the bottom left pixel")
369 : {
370 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 2);
371 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 2);
372 : }
373 : }
374 :
375 29 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (2.5, "
376 : "3.5) and direction (0, -1)")
377 : {
378 1 : ro << 2.5, 3.5;
379 1 : rd << 0.0, -1.0;
380 2 : Ray r(ro, rd);
381 :
382 2 : TraverseAABB traverse(aabb, r);
383 1 : CHECK_UNARY(traverse.isInBoundingBox());
384 2 : THEN("The ray intersects the aabb at the bottom left pixel")
385 : {
386 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 2);
387 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 2);
388 : }
389 : }
390 :
391 : //
392 : // Some edge cases
393 : //
394 29 : WHEN("A ray with origin = (-0.5, 0.0) and direction (1, 0) hits the left edge of aabb")
395 : {
396 1 : ro << -0.5, 0.0;
397 1 : rd << 1.0, 0.0;
398 2 : Ray r(ro, rd);
399 :
400 2 : TraverseAABB traverse(aabb, r);
401 1 : CHECK_UNARY(traverse.isInBoundingBox());
402 2 : THEN("The ray intersects the aabb at the bottom left pixel")
403 : {
404 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
405 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
406 : }
407 : }
408 :
409 29 : WHEN("A ray with origin = (3.5, 0.0) and direction (-1, 0) hits the left edge of aabb")
410 : {
411 1 : ro << 3.5, 0.0;
412 1 : rd << -1.0, 0.0;
413 2 : Ray r(ro, rd);
414 :
415 2 : TraverseAABB traverse(aabb, r);
416 1 : CHECK_UNARY(traverse.isInBoundingBox());
417 2 : THEN("The ray intersects the aabb at the top left pixel")
418 : {
419 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 2);
420 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
421 : }
422 : }
423 :
424 29 : WHEN("A ray with origin = (-0.5, 3.0) and direction (1, 0) hits the top edge of aabb")
425 : {
426 1 : ro << -0.5, 3.0;
427 1 : rd << 1.0, 0.0;
428 2 : Ray r(ro, rd);
429 :
430 2 : TraverseAABB traverse(aabb, r);
431 :
432 1 : THEN("the the aabb is not hit") { REQUIRE_UNARY_FALSE(traverse.isInBoundingBox()); }
433 : }
434 :
435 29 : WHEN("A ray with origin = (3.5, 3.0) and direction (-1, 0) hits the top edge of aabb")
436 : {
437 1 : ro << 3.5, 3.0;
438 1 : rd << -1.0, 0.0;
439 2 : Ray r(ro, rd);
440 :
441 2 : TraverseAABB traverse(aabb, r);
442 :
443 1 : THEN("the the aabb is not hit") { REQUIRE_UNARY_FALSE(traverse.isInBoundingBox()); }
444 : }
445 :
446 29 : WHEN("A ray with origin = (0.0, -0.5) and direction (0, 1) hits the bottom edge of aabb)")
447 : {
448 1 : ro << 0.0, -0.5;
449 1 : rd << 0.0, 1.0;
450 2 : Ray r(ro, rd);
451 :
452 2 : TraverseAABB traverse(aabb, r);
453 1 : CHECK_UNARY(traverse.isInBoundingBox());
454 2 : THEN("The ray intersects the aabb at the bottom left pixel")
455 : {
456 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
457 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
458 : }
459 : }
460 :
461 29 : WHEN("A ray with origin = (0.0, 3.5) and direction (0, -1) hits the top edge of aabb)")
462 : {
463 1 : ro << 0.0, 3.5;
464 1 : rd << 0.0, -1.0;
465 2 : Ray r(ro, rd);
466 :
467 2 : TraverseAABB traverse(aabb, r);
468 1 : CHECK_UNARY(traverse.isInBoundingBox());
469 2 : THEN("The ray intersects the aabb at the top left pixel")
470 : {
471 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
472 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 2);
473 : }
474 : }
475 :
476 29 : WHEN("A ray with origin = (3.0, -0.5) and direction (0, 1) hits the right edge of aabb)")
477 : {
478 1 : ro << 3.0, -0.5;
479 1 : rd << 0.0, 1.0;
480 2 : Ray r(ro, rd);
481 :
482 2 : TraverseAABB traverse(aabb, r);
483 :
484 1 : THEN("the the aabb is not hit") { REQUIRE_UNARY_FALSE(traverse.isInBoundingBox()); }
485 : }
486 :
487 29 : WHEN("A ray with origin = (3.0, 3.5) and direction (0, -1) hits the top edge of aabb)")
488 : {
489 1 : ro << 3.0, 3.5;
490 1 : rd << 0.0, -1.0;
491 2 : Ray r(ro, rd);
492 :
493 2 : TraverseAABB traverse(aabb, r);
494 :
495 1 : THEN("the the aabb is not hit") { REQUIRE_UNARY_FALSE(traverse.isInBoundingBox()); }
496 : }
497 : }
498 28 : }
499 :
500 1 : TEST_CASE("TraverseAABB: Construction of a 3D traversal object")
501 : {
502 : // setup
503 1 : size_t dim = 3;
504 2 : IndexVector_t volumeDims(dim);
505 1 : volumeDims << 3, 3, 3;
506 :
507 2 : RealVector_t spacing(dim);
508 :
509 2 : RealVector_t ro(dim);
510 2 : RealVector_t rd(dim);
511 :
512 2 : GIVEN("a 3x3x3 aabb with standard spacing")
513 : {
514 2 : BoundingBox aabb(volumeDims);
515 :
516 2 : WHEN("A traversal algorithms is initialised with the aabb and a ray with origin = (0.5, "
517 : "-0.5, 0.5) and direction = (0, 1, 0)")
518 : {
519 1 : ro << 0.5, -0.5, 0.5;
520 1 : rd << 0.0, 1.0, 0.0;
521 2 : Ray r(ro, rd);
522 :
523 2 : TraverseAABB traverse(aabb, r);
524 1 : CHECK_UNARY(traverse.isInBoundingBox());
525 :
526 2 : THEN("The ray intersects the aabb at the voxel (0, 0, 0)")
527 : {
528 1 : REQUIRE_UNARY(traverse.isInBoundingBox());
529 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
530 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
531 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(2), 0);
532 : }
533 : }
534 : }
535 1 : }
536 :
537 1 : TEST_CASE("TraverseAABB: Traverse a minimal 3D volume of size 1x1x1")
538 : {
539 : // setup
540 1 : size_t dim = 3;
541 1 : index_t x = 1;
542 1 : index_t y = 1;
543 1 : index_t z = 1;
544 2 : IndexVector_t volumeDims(dim);
545 1 : volumeDims << x, y, z;
546 :
547 2 : RealVector_t spacing(dim);
548 2 : RealVector_t ro(dim);
549 2 : RealVector_t rd(dim);
550 :
551 2 : GIVEN("A 1x1x1 volume with uniform scaling")
552 : {
553 2 : BoundingBox aabb(volumeDims);
554 1 : spacing << 1.0, 1.0, 1.0;
555 :
556 2 : WHEN("The volume is traversed with a ray with origin = (-0.5, 0.5, 0.5) and a direction = "
557 : "(0, 1, 0)")
558 : {
559 1 : ro << 0.5, -0.5, 0.5;
560 1 : rd << 0.0, 1.0, 0.0;
561 :
562 2 : Ray r(ro, rd);
563 2 : TraverseAABB traverse(aabb, r);
564 1 : CHECK_UNARY(traverse.isInBoundingBox());
565 :
566 1 : traverse.updateTraverse();
567 :
568 2 : THEN("The algorithms left the volume and the voxel it left the box is (0, 1, 0)")
569 : {
570 1 : REQUIRE_UNARY_FALSE(traverse.isInBoundingBox());
571 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
572 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 1);
573 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(2), 0);
574 : }
575 : }
576 : }
577 1 : }
578 :
579 1 : TEST_CASE("TraverseAABB: Traverse a 2D volume and only check that the endpoint is correct")
580 : {
581 : // setup
582 1 : size_t dim = 2;
583 1 : index_t x = 10;
584 1 : index_t y = 10;
585 2 : IndexVector_t volumeDims(dim);
586 1 : volumeDims << x, y;
587 :
588 2 : RealVector_t spacing(dim);
589 2 : RealVector_t ro(dim);
590 2 : RealVector_t rd(dim);
591 :
592 2 : GIVEN("A 10x10 volume with uniform scaling")
593 : {
594 2 : BoundingBox aabb(volumeDims);
595 :
596 2 : WHEN("The volume is traversed with a ray with origin = (-0.5, 0.5, 0.5) and a direction = "
597 : "(0, 1, 0)")
598 : {
599 1 : ro << -1, 4.5;
600 1 : rd << 1.0, 0;
601 :
602 2 : Ray r(ro, rd);
603 2 : TraverseAABB traverse(aabb, r);
604 1 : CHECK_UNARY(traverse.isInBoundingBox());
605 :
606 11 : while (traverse.isInBoundingBox())
607 10 : traverse.updateTraverse();
608 :
609 2 : THEN("The endpoint should be (10,4)")
610 : {
611 1 : REQUIRE_UNARY_FALSE(traverse.isInBoundingBox());
612 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 10);
613 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 4);
614 : }
615 : }
616 : }
617 1 : }
618 :
619 2 : TEST_CASE("TraverseAABB: Traverse a 3D Volume diagonally")
620 : {
621 : // TODO: run through all 4 diagonals
622 : // TODO: make a non cube volume and run through all 4 diagonals
623 : // TODO: make non uniform scaling and run through all 4 diagonals
624 :
625 2 : size_t dim = 3;
626 4 : IndexVector_t volumeDims(dim);
627 2 : volumeDims << 10, 10, 10;
628 :
629 4 : RealVector_t spacing(dim);
630 4 : RealVector_t ro(dim);
631 4 : RealVector_t rd(dim);
632 :
633 4 : GIVEN("A 10x10 volume with uniform scaling")
634 : {
635 4 : BoundingBox aabb(volumeDims);
636 4 : WHEN("Start at (-1, -1, -1) (so bottom left front) and run to (10, 10, 10) (so top right "
637 : "back)")
638 : {
639 2 : ro << -1.0, -1.0, -1.0;
640 2 : rd << 1.0, 1.0, 1.0;
641 2 : rd.normalize();
642 :
643 4 : Ray r(ro, rd);
644 :
645 4 : TraverseAABB traverse(aabb, r);
646 2 : CHECK_UNARY(traverse.isInBoundingBox());
647 :
648 3 : THEN("You entered at (0, 0, 0)")
649 : {
650 1 : CHECK_EQ(traverse.getCurrentVoxel()(0), 0);
651 1 : CHECK_EQ(traverse.getCurrentVoxel()(1), 0);
652 1 : CHECK_EQ(traverse.getCurrentVoxel()(2), 0);
653 : }
654 58 : while (traverse.isInBoundingBox())
655 56 : traverse.updateTraverse();
656 :
657 3 : THEN("You leave the volume at (10, 9, 9)")
658 : {
659 1 : REQUIRE_UNARY_FALSE(traverse.isInBoundingBox());
660 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 10);
661 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 9);
662 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(2), 9);
663 : }
664 : }
665 : }
666 2 : }
667 :
668 4 : TEST_CASE("TraverseAABB: Check that the first step into the 2D Volume is correct")
669 : {
670 4 : size_t dim = 2;
671 4 : index_t x = 5;
672 4 : index_t y = 5;
673 8 : IndexVector_t volumeDims(dim);
674 4 : volumeDims << x, y;
675 :
676 8 : RealVector_t ro(dim);
677 8 : RealVector_t rd(dim);
678 :
679 8 : GIVEN("A 5x5 volume with uniform scaling")
680 : {
681 8 : BoundingBox aabb(volumeDims);
682 :
683 6 : WHEN("The ray direction has the biggest value on the y axis")
684 : {
685 2 : ro << 0, 0;
686 2 : rd << 0.5f, 0.7f;
687 2 : rd.normalize();
688 :
689 4 : Ray r(ro, rd);
690 4 : TraverseAABB traverse(aabb, r);
691 2 : CHECK_UNARY(traverse.isInBoundingBox());
692 :
693 3 : THEN("The traversal is initially at (0, 0)")
694 : {
695 1 : auto voxel = traverse.getCurrentVoxel();
696 1 : CHECK_EQ(voxel(0), 0);
697 1 : CHECK_EQ(voxel(1), 0);
698 : }
699 :
700 2 : traverse.updateTraverse();
701 :
702 3 : THEN("The first step is in y direction")
703 : {
704 1 : REQUIRE_UNARY(traverse.isInBoundingBox());
705 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 0);
706 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 1);
707 : }
708 : }
709 :
710 6 : WHEN("The ray direction has the biggest value on the x axis")
711 : {
712 2 : ro << 0, 0;
713 2 : rd << 0.7f, 0.5f;
714 2 : rd.normalize();
715 :
716 4 : Ray r(ro, rd);
717 4 : TraverseAABB traverse(aabb, r);
718 2 : CHECK_UNARY(traverse.isInBoundingBox());
719 :
720 3 : THEN("The traversal is initially at (0, 0)")
721 : {
722 1 : auto voxel = traverse.getCurrentVoxel();
723 1 : CHECK_EQ(voxel(0), 0);
724 1 : CHECK_EQ(voxel(1), 0);
725 : }
726 :
727 2 : traverse.updateTraverse();
728 :
729 3 : THEN("The first step is in y direction")
730 : {
731 1 : REQUIRE_UNARY(traverse.isInBoundingBox());
732 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(0), 1);
733 1 : REQUIRE_EQ(traverse.getCurrentVoxel()(1), 0);
734 : }
735 : }
736 : }
737 4 : }
738 :
739 1 : TEST_CASE("TraverseAABB: Traverse_Volume_2D_EachPointIsTested")
740 : {
741 : // setup
742 1 : size_t dim = 2;
743 1 : index_t x = 128;
744 1 : index_t y = 128;
745 2 : IndexVector_t volumeDims(dim);
746 1 : volumeDims << x, y;
747 2 : BoundingBox aabb(volumeDims);
748 :
749 2 : RealVector_t ro(dim);
750 1 : ro << -168.274f, -143.397f;
751 2 : RealVector_t rd(dim);
752 1 : rd << 0.761124909f, 0.648605406f;
753 1 : rd.normalize();
754 2 : Ray r(ro, rd);
755 :
756 2 : TraverseAABB traverse(aabb, r);
757 1 : CHECK_UNARY(traverse.isInBoundingBox());
758 :
759 1 : size_t iter = 0;
760 238 : while (traverse.isInBoundingBox()) {
761 474 : RealVector_t voxel = traverse.getCurrentVoxel().template cast<real_t>();
762 237 : INFO("Current Voxel: (" << voxel(0) << ", " << voxel(1) << ") in iter: " << iter);
763 :
764 237 : REQUIRE_UNARY(intersect(voxel, r));
765 237 : traverse.updateTraverse();
766 237 : iter++;
767 : }
768 1 : }
769 :
770 8 : TEST_CASE("TraverseAABB: Traversal through 2D volume should be equal to a ray voxel intersection "
771 : "for every voxel along the way")
772 : {
773 : // TODO make this a stronger test, for first some "easy" direction (parallel ones)
774 : // TODO Then make some harder ones
775 : // setup
776 8 : size_t dim = 2;
777 8 : index_t x = 128;
778 8 : index_t y = 128;
779 16 : IndexVector_t volumeDims(dim);
780 8 : volumeDims << x, y;
781 16 : BoundingBox aabb(volumeDims);
782 :
783 16 : RealVector_t ro(dim);
784 16 : RealVector_t rd(dim);
785 :
786 9 : GIVEN("a point at the bottom left of the volume and a ray with leading dimension x")
787 : {
788 1 : ro << -168.274f, -143.397f;
789 :
790 1 : rd << 0.761124909f, 0.648605406f;
791 1 : rd.normalize();
792 :
793 2 : Ray r(ro, rd);
794 :
795 2 : THEN("Then all points the traversal visits are also hit by the intersection algorithm")
796 : {
797 2 : TraverseAABB traverse(aabb, r);
798 1 : CHECK_UNARY(traverse.isInBoundingBox());
799 :
800 1 : size_t iter = 0;
801 238 : while (traverse.isInBoundingBox()) {
802 474 : RealVector_t voxel = traverse.getCurrentVoxel().template cast<real_t>();
803 237 : INFO("Current Voxel: (" << voxel(0) << ", " << voxel(1) << ") in iter: " << iter);
804 :
805 237 : REQUIRE_UNARY(intersect(voxel, r));
806 237 : traverse.updateTraverse();
807 237 : iter++;
808 : }
809 : }
810 : }
811 :
812 9 : GIVEN("a point at the bottom left of the volume and a ray with leading dimension y")
813 : {
814 1 : ro << 0, 0;
815 :
816 1 : rd << 0.648605406f, 0.761124909f;
817 1 : rd.normalize();
818 :
819 2 : Ray r(ro, rd);
820 :
821 2 : THEN("Then all points the traversal visits are also hit by the intersection algorithm")
822 : {
823 2 : TraverseAABB traverse(aabb, r);
824 1 : CHECK_UNARY(traverse.isInBoundingBox());
825 :
826 1 : size_t iter = 0;
827 238 : while (traverse.isInBoundingBox()) {
828 474 : RealVector_t voxel = traverse.getCurrentVoxel().template cast<real_t>();
829 237 : INFO("Current Voxel: (" << voxel(0) << ", " << voxel(1) << ") in iter: " << iter);
830 :
831 237 : REQUIRE_UNARY(intersect(voxel, r));
832 237 : traverse.updateTraverse();
833 237 : iter++;
834 : }
835 : }
836 : }
837 :
838 9 : GIVEN("a ray going through the border of voxel column 0 and 1")
839 : {
840 1 : ro << 1, -0.5f;
841 :
842 1 : rd << 0, 1;
843 1 : rd.normalize();
844 :
845 2 : Ray r(ro, rd);
846 :
847 2 : THEN("Then all points the traversal visits are also hit by the intersection algorithm")
848 : {
849 2 : TraverseAABB traverse(aabb, r);
850 1 : CHECK_UNARY(traverse.isInBoundingBox());
851 :
852 1 : size_t iter = 0;
853 129 : while (traverse.isInBoundingBox()) {
854 256 : RealVector_t voxel = traverse.getCurrentVoxel().template cast<real_t>();
855 128 : INFO("Current Voxel: (" << voxel(0) << ", " << voxel(1) << ") in iter: " << iter);
856 :
857 128 : REQUIRE_UNARY(intersect(voxel, r));
858 128 : traverse.updateTraverse();
859 128 : iter++;
860 : }
861 : }
862 : }
863 :
864 9 : GIVEN("a ray going through the border of voxel row 0 and 1")
865 : {
866 1 : ro << -0.5f, 1;
867 :
868 1 : rd << 1, 0;
869 1 : rd.normalize();
870 :
871 2 : Ray r(ro, rd);
872 :
873 2 : THEN("Then all points the traversal visits are also hit by the intersection algorithm")
874 : {
875 2 : TraverseAABB traverse(aabb, r);
876 1 : CHECK_UNARY(traverse.isInBoundingBox());
877 :
878 1 : size_t iter = 0;
879 129 : while (traverse.isInBoundingBox()) {
880 256 : RealVector_t voxel = traverse.getCurrentVoxel().template cast<real_t>();
881 128 : INFO("Current Voxel: (" << voxel(0) << ", " << voxel(1) << ") in iter: " << iter);
882 :
883 128 : REQUIRE_UNARY(intersect(voxel, r));
884 128 : traverse.updateTraverse();
885 128 : iter++;
886 : }
887 : }
888 : }
889 :
890 9 : GIVEN("A ray going diagonally through the volume")
891 : {
892 1 : ro << -0.5f, -0.5f;
893 :
894 1 : rd << 1, 1;
895 1 : rd.normalize();
896 :
897 2 : Ray r(ro, rd);
898 :
899 2 : THEN("Then all points the traversal visits are also hit by the intersection algorithm")
900 : {
901 2 : TraverseAABB traverse(aabb, r);
902 1 : CHECK_UNARY(traverse.isInBoundingBox());
903 :
904 1 : size_t iter = 0;
905 256 : while (traverse.isInBoundingBox()) {
906 510 : RealVector_t voxel = traverse.getCurrentVoxel().template cast<real_t>();
907 255 : INFO("Current Voxel: (" << voxel(0) << ", " << voxel(1) << ") in iter: " << iter);
908 :
909 255 : REQUIRE_UNARY(intersect(voxel, r));
910 255 : traverse.updateTraverse();
911 255 : iter++;
912 : }
913 : }
914 : }
915 :
916 9 : GIVEN("A ray going diagonally through the volume")
917 : {
918 1 : ro << -0.5f, 32;
919 :
920 1 : rd << 1, 1;
921 1 : rd.normalize();
922 :
923 2 : Ray r(ro, rd);
924 :
925 2 : THEN("Then all points the traversal visits are also hit by the intersection algorithm")
926 : {
927 2 : TraverseAABB traverse(aabb, r);
928 1 : CHECK_UNARY(traverse.isInBoundingBox());
929 :
930 1 : size_t iter = 0;
931 192 : while (traverse.isInBoundingBox()) {
932 382 : RealVector_t voxel = traverse.getCurrentVoxel().template cast<real_t>();
933 191 : INFO("Current Voxel: (" << voxel(0) << ", " << voxel(1) << ") in iter: " << iter);
934 :
935 191 : REQUIRE_UNARY(intersect(voxel, r));
936 191 : traverse.updateTraverse();
937 191 : iter++;
938 : }
939 : }
940 : }
941 :
942 9 : GIVEN("A ray going diagonally through the volume")
943 : {
944 1 : ro << -0.5f, -0.5f;
945 :
946 1 : rd << 0.699428f, 0.472203f;
947 1 : rd.normalize();
948 :
949 2 : Ray r(ro, rd);
950 :
951 2 : THEN("Then all points the traversal visits are also hit by the intersection algorithm")
952 : {
953 2 : TraverseAABB traverse(aabb, r);
954 1 : CHECK_UNARY(traverse.isInBoundingBox());
955 :
956 1 : size_t iter = 0;
957 215 : while (traverse.isInBoundingBox()) {
958 428 : RealVector_t voxel = traverse.getCurrentVoxel().template cast<real_t>();
959 214 : INFO("Current Voxel: (" << voxel(0) << ", " << voxel(1) << ") in iter: " << iter);
960 :
961 214 : REQUIRE_UNARY(intersect(voxel, r));
962 214 : traverse.updateTraverse();
963 214 : iter++;
964 : }
965 : }
966 : }
967 :
968 9 : GIVEN("A ray going diagonally through the volume")
969 : {
970 1 : volumeDims << 64, 64;
971 2 : BoundingBox aabb(volumeDims);
972 :
973 1 : ro << 32.0002823f, 3232;
974 :
975 1 : rd << -0.000723466626f, -0.999999762f;
976 1 : rd.normalize();
977 :
978 2 : Ray r(ro, rd);
979 :
980 2 : THEN("Then all points the traversal visits are also hit by the intersection algorithm")
981 : {
982 2 : TraverseAABB traverse(aabb, r);
983 1 : traverse.isInBoundingBox();
984 :
985 1 : size_t iter = 0;
986 65 : while (traverse.isInBoundingBox()) {
987 128 : RealVector_t voxel = traverse.getCurrentVoxel().template cast<real_t>();
988 64 : INFO("Current Voxel: (" << voxel(0) << ", " << voxel(1) << ") in iter: " << iter);
989 :
990 64 : REQUIRE_UNARY(intersect(voxel, r));
991 64 : traverse.updateTraverse();
992 64 : iter++;
993 : }
994 : }
995 : }
996 8 : }
|