3D Raycasting
The Digital Differential Analyzer (DDA) algorithm,
adapted to 3D, is exactly the thing one needs to travel along a line (or a ray) through a grid of voxels.
This article is a stub. Perhaps help us expand it?
Implementation
The following implementation was written in GLSL,
but should be simple enough to be ported to any language one may choose...
bool DDATraversal(vec3 origin, vec3 dir, out vec3 o_hitPos, out vec3 o_hitNormal)
{
dir = normalize(dir);
// We don't want to deal with this in the loop...
if (rayDir.x == 0)
rayDir.x = 0.001;
if (rayDir.y == 0)
rayDir.y = 0.001;
if (rayDir.z == 0)
rayDir.z = 0.001;
ivec3 raySign = ivec3(sign(dir));
ivec3 rayPositivity = (1 + raySign) >> 1;
vec3 rayInverse = 1 / dir;
ivec3 gridCoords = ivec3(origin);
vec3 withinVoxelCoords = origin - gridCoords;
while (true)
{
if (!isCoordInBounds(gridCoords))
return false;
if (isVoxelFilled(gridCoords))
{
o_hitPos = gridCoords + withinVoxelCoords;
vec3 normal = vec3(0);
normal[minIdx] = -raySign[minIdx];
o_hitNormal = normal;
return true; // We hit a voxel!
}
// Do a step...
vec3 t = (rayPositivity - withinVoxelCoords) * rayInverse;
int minIdx = t.x < t.y ? (t.x < t.z ? 0 : 2) : (t.y < t.z ? 1 : 2);
gridCoords[minIdx] += raySign[minIdx];
withinVoxelCoords += rayDir * t[minIdx];
withinVoxelCoords[minIdx] = 1 - rayPositivity[minIdx];
}
}