cgyurgyik / fast-voxel-traversal-algorithm Goto Github PK

Code like this, seems to set the index to a minimum of 1 ? Why do that ? Does this code assume the voxel grid starts at index 1,1,1 ?

size_t current_X_index = MAX(1, std::ceil(ray_start.x() - grid.minBound().x() / grid.voxelSizeX()));
const size_t end_X_index = MAX(1, std::ceil(ray_end.x() - grid.minBound().x() / grid.voxelSizeX()));

The link for 'safer' implementation is invalid. Don't you think that this resource is valid, for that task: https://www.pbr-book.org/3ed-2018/Shapes/Basic_Shape_Interface or this https://www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-box-intersection.html#:~:text=time%3A%2010%20mins.-,Ray%2DBox%20Intersection,1%20and%20b%3D%2D1.

Ray direction is not computed by the code/algorithm, I noticed this while trying to apply the code.

Fortunately it does not seem to complex, though it could get a bit tricky with overflow potential.

It's likely that a user of this code will want to setup the ray based on a start coordinate and end coordinate.

To compute ray direction I think the correct code would be something like:

Ray.Direction = Ray.End - Ray.Start;
Ray.Direction = Ray.Direction * Ray.Direction // trying to compute delta x, delta y, delta z, no sure if this code is correct.

Also then I notice another problem/short coming, where the overlow potential begins, ray length must also be computed
Not sure how to express this with the ray class.

Ray.Length = std::sqrt( Ray.Direction )

Finally the direction must be normalized.

Ray.Direction = Ray.Direction / Ray.Length

Computing ray direction can become a bit tricky.

To prevent overflow might be save to write:
RayLength = DX * DX
RayLength += DY * DY
RayLength += DZ * DZ

RayLength = std:sqrt(RayLength)

So compute it in steps... to prevent any big multiplication overflows, maybe in this case it don't matter ;)

Also it's possible that the ray length or ray direction is already normalized, it depends on the user :) but some additional code or methods to do all of this would be appreciated and takes away any doubts.

while (current_X_index != end_X_index || current_Y_index != end_Y_index || current_Z_index != end_Z_index)

if for whatever reason these indexes never happen the loop will hang forever. I am not yet sure why these indexes never happen, it might be because there are off by 1 or perhaps floating errors make them go off by 1.

It might be saver to check for tMaxX, tMaxY, tMaxZ to be smaller than the (real space) line length.

And then the code should go from t0 to t1.

while (tMaxX < RayLength) or (tMaxY < RayLength) or (tMaxZ < RayLength)

This could and would most probably make the code a lot saver.

I'm trying to understand the suggestion on how to compute tMax which is describes as below

// grid.minBound.x is the lower left corner of the grid.
// current_X_index is the current X index where the ray begins. If it starts outside, this is 1.
// ray_origin.x is the x-coordinate of where the ray originates.
// ray.direction.x is the x-direction of the ray’s travel path.
tMax = (grid.minBound.x + current_X_index - ray_origin.x) / ray.direction.x);

I think this implies that the direction of travel is always up right. If the travel direction is to the right then I believe it should be:

tMax = (grid.minBound.x + current_X_index - 1 + ray_origin.x) / ray.direction.x);