Ray traversing voxelized cube

General Usage
1

I have a ray, that traverses a voxelized cube. I want to know, which voxels are traversed by the ray and which are not. Here is a picture in 2d:

Is there some julia package that can help?

2

Hi, I remember looking for something similar a while back but to my knowledge there is no hands-on package doing this.

The first step in implementing this would be to code a ray-box intersection algorithm, as described here: A Minimal Ray-Tracer: Rendering Simple Shapes (Sphere, Cube, Disk, Plane, etc.) (Ray-Box Intersection)

Here is a Julia attempt (not tested):

using StaticArrays

const Vec3D = SVector{3,Float64}

struct Ray
    orig::Vec3D
    dir::Vec3D 
    invdir::Vec3D
    sig::SVector{3,Int64}
    function Ray(orig, dir)
        invdir = 1 ./ dir
        sig = SVector{3,Int64}((invdir .< 0) .+ 1)
        new(orig, dir, invdir, sig)
    end
end

struct BBox
    bounds::SVector{2,Vec3D}
    function BBox(vmin, vmax)
        bounds = SVector{2,Vec3D}(vmin, vmax)
        new(bounds)
    end
end


function intersect(r::Ray, box::BBox)

    bounds = box.bounds

    tmin = (bounds[r.sig[1]][1] - r.orig[1]) * r.invdir[1] 
    tmax = (bounds[1-r.sig[1]][1] - r.orig[1]) * r.invdir[1] 
    tymin = (bounds[r.sig[2]][2] - r.orig[2]) * r.invdir[2] 
    tymax = (bounds[1-r.sig[2]][2] - r.orig[2]) * r.invdir[2] 
 
    if ((tmin > tymax) || (tymin > tmax)) 
        return false, 0.0, 0.0
    end
    if (tymin > tmin) 
        tmin = tymin
    end
    if (tymax < tmax) 
        tmax = tymax
    end
 
    tzmin = (bounds[r.sig[3]][3] - r.orig[3]) * r.invdir[3]
    tzmax = (bounds[1-r.sig[3]][3] - r.orig[3]) * r.invdir[3] 
 
    if ((tmin > tzmax) || (tzmin > tmax)) 
        return false, 0.0, 0.0
    end
    if (tzmin > tmin) 
        tmin = tzmin
    end
    if (tzmax < tmax) 
        tmax = tzmax
    end
 
    return true, tmin, tmax
}

You can then build an array containing the voxels as boxes and loop through all of them to test whether there is an intersection between each box and a ray. A more efficient approach would be to find the entry point for the first intersection, and then iteratively go to the neighboring voxel based on the exit point.

3
4

Woh, that was fast! I’m definitely going to use this. I really like your implementation using an iterator, which makes it easy for me to use for my application (simulating a X-ray from a CT scan, which involves an integration of the traversed matter, i.e summing all the voxel intensities traversed by a ray multiplied by the traversal time).
Thanks!

5

Registration is under way have fun! Feedback and PRs are appreciated.