1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
#pragma once
#include "../Common/Casts.hpp"
#include "../Math/Ray.hpp"
#include "Position.hpp"
namespace MC::World::VoxelTraversal {
struct TraversalResult {
// Whether the ray hit a block.
Bool hit{};
// The block that was hit.
Position::BlockWorld block;
// The vector from the ray origin to where the block that was hit.
Position::WorldOffset approach;
// The normal of the collision.
Position::BlockWorldOffset normal;
};
#define MC_WORLD_VOXEL_TRAVERSAL_MAX_ITERATIONS 500
// Amanatides, John, and Andrew Woo. 1987.
// "A Fast Voxel Traversal Algorithm for Ray Tracing."
// https://doi.org/10.2312/EGTP.19871000.
template <typename P>
TraversalResult traverse(Ray ray, P&& predicate, Real max_distance = 0) {
// Find the voxel grid cell containing the origin of the ray.
Position::BlockWorld block_pos = Position::World(ray.origin).round_to_block();
Position::BlockWorldOffset const step = {
Math::sign(ray.direction.x()),
Math::sign(ray.direction.y()),
Math::sign(ray.direction.z()),
};
Position::WorldOffset t_max = {
(TO(Real, block_pos.x()) + TO(Real, step.x() > 0) - ray.origin.x()) / ray.direction.x(),
(TO(Real, block_pos.y()) + TO(Real, step.y() > 0) - ray.origin.y()) / ray.direction.y(),
(TO(Real, block_pos.z()) + TO(Real, step.z() > 0) - ray.origin.z()) / ray.direction.z()
};
Position::WorldOffset const t_delta = {
TO(Real, step.x()) / ray.direction.x(),
TO(Real, step.y()) / ray.direction.y(),
TO(Real, step.z()) / ray.direction.z()
};
// The original algorithm does not mention calculating the normal of the
// block that was hit. When we increment t_max to a collision on one of the axes
// of the voxel grid, the axis gives us the normal of the current block.
Position::BlockWorldOffset normal = {};
// Also not mentioned in the original algorithm, but we need to keep track of
// how far along we have traversed the voxel grid.
// This just means we add the direction of the ray at the axis we have progressed along.
Position::WorldOffset approach = {};
UInt iterations = 0;
while (!predicate(block_pos)) {
if (iterations++ > MC_WORLD_VOXEL_TRAVERSAL_MAX_ITERATIONS)
return {};
if (max_distance > 0 && approach.magnitude() > max_distance)
return {};
if (t_max.x() < t_max.y()) {
if (t_max.x() < t_max.z()) {
block_pos.x() += step.x();
t_max.x() += t_delta.x();
normal = {-step.x(), 0, 0};
approach.x() += ray.direction.x();
} else {
block_pos.z() += step.z();
t_max.z() += t_delta.z();
normal = {0, 0, -step.z()};
approach.z() += ray.direction.z();
}
} else {
if (t_max.y() < t_max.z()) {
block_pos.y() += step.y();
t_max.y() += t_delta.y();
normal = {0, -step.y(), 0};
approach.y() += ray.direction.y();
} else {
block_pos.z() += step.z();
t_max.z() += t_delta.z();
normal = {0, 0, -step.z()};
approach.z() += ray.direction.z();
}
}
}
return {true, block_pos, approach, normal};
}
}
|
