BIG SUCCESS,
This code below was first translated to Delphi, then tested, then slighty adjusted and I can confirm it works flawlessly, one problems remains, no clipping yet.
This C code was then integrated into the OpenXCom game, tested a few times, made some changes until it works, pretty cool !
(Perhaps if the swapping of xy is not done and such it might be even more accurate, that's kinda the feeling I got first time I did it, but I am going to keep this swapping in there for now
)
(Later I will examine the original code, to see how accurate that one was):
Here is original algorithm, slightly modified to process first and last voxel too,
This code expects the coordinates to be scaled down to grid space, it may be floating points, the game already does that, but in case people want to use this code for other purposes then you know how to use it, divide x,y,z coordinates by cell width, height, depth and such.
Code has been integrated into game in this branch:
https://github.com/SkybuckFlying/OpenXcom/tree/FastVoxelTraversalAttempt2The one that worked for me in 3D for both positive and negative directions (in CUDA C):
#define SIGN(x) (x > 0 ? 1 : (x < 0 ? -1 : 0))
#define FRAC0(x) (x - floorf(x))
#define FRAC1(x) (1 - x + floorf(x))
float tMaxX, tMaxY, tMaxZ, tDeltaX, tDeltaY, tDeltaZ;
int3 voxel;
float x1, y1, z1; // start point
float x2, y2, z2; // end point
int dx = SIGN(x2 - x1);
if (dx != 0) tDeltaX = fmin(dx / (x2 - x1), 10000000.0f); else tDeltaX = 10000000.0f;
if (dx > 0) tMaxX = tDeltaX * FRAC1(x1); else tMaxX = tDeltaX * FRAC0(x1);
voxel.x = (int) x1;
int dy = SIGN(y2 - y1);
if (dy != 0) tDeltaY = fmin(dy / (y2 - y1), 10000000.0f); else tDeltaY = 10000000.0f;
if (dy > 0) tMaxY = tDeltaY * FRAC1(y1); else tMaxY = tDeltaY * FRAC0(y1);
voxel.y = (int) y1;
int dz = SIGN(z2 - z1);
if (dz != 0) tDeltaZ = fmin(dz / (z2 - z1), 10000000.0f); else tDeltaZ = 10000000.0f;
if (dz > 0) tMaxZ = tDeltaZ * FRAC1(z1); else tMaxZ = tDeltaZ * FRAC0(z1);
voxel.z = (int) z1;
while (true) {
// process first and subsequent voxels here
if (tMaxX < tMaxY) {
if (tMaxX < tMaxZ) {
voxel.x += dx;
tMaxX += tDeltaX;
} else {
voxel.z += dz;
tMaxZ += tDeltaZ;
}
} else {
if (tMaxY < tMaxZ) {
voxel.y += dy;
tMaxY += tDeltaY;
} else {
voxel.z += dz;
tMaxZ += tDeltaZ;
}
}
if (tMaxX > 1 && tMaxY > 1 && tMaxZ > 1)
{
// process last voxel here
break;
}
}
