# Ray traversing voxelized cube

**URL:** <https://discourse.julialang.org/t/ray-traversing-voxelized-cube/33065>\
**Category:** General Usage\
**Created:** [January 7, 2020, 3:22pm UTC](https://discourse.julialang.org/t/ray-traversing-voxelized-cube/33065 "2020-01-07T15:22:53Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [January 7, 2020, 3:22pm UTC](https://discourse.julialang.org/t/ray-traversing-voxelized-cube/33065/1 "2020-01-07T15:22:53Z")

</div>

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:  
 ![](https://global.discourse-cdn.com/julialang/original/3X/1/f/1ff320f5ff77021b085a46aeb5250737f1107313.png)  
Is there some julia package that can help?

---

<div class="post-metadata">

**Author:** ![touste](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/touste/32/10758_2.png) [@touste](https://discourse.julialang.org/u/touste)\
**Post date:** [January 8, 2020, 10:16am UTC](https://discourse.julialang.org/t/ray-traversing-voxelized-cube/33065/2 "2020-01-08T10:16:20Z")

</div>

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)](https://www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-box-intersection)

Here is a Julia attempt (not tested):

```julia
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.

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [January 10, 2020, 4:22pm UTC](https://discourse.julialang.org/t/ray-traversing-voxelized-cube/33065/3 "2020-01-10T16:22:07Z")

</div>

> **[GitHub - jw3126/VoxelRayTracers.jl: CPU ray tracing through voxelized geometry](https://github.com/jw3126/VoxelRayTracers.jl)**
>
> CPU ray tracing through voxelized geometry. Contribute to jw3126/VoxelRayTracers.jl development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![touste](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/touste/32/10758_2.png) [@touste](https://discourse.julialang.org/u/touste)\
**Post date:** [January 10, 2020, 7:55pm UTC](https://discourse.julialang.org/t/ray-traversing-voxelized-cube/33065/4 "2020-01-10T19:55:56Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [January 10, 2020, 8:04pm UTC](https://discourse.julialang.org/t/ray-traversing-voxelized-cube/33065/5 "2020-01-10T20:04:44Z")

</div>

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