`Box` - `Line` intersection in 3D

[prittjam]

trafficstars

using Meshes
l = Meshes.Line((0.0,0.0),(1.0,1.0))
b = Meshes.Box((0.0,0.0),(1.0,1.0))
intersect(l,b)

crashes with

ERROR: StackOverflowError:^C SYSTEM (REPL): showing an error caused an error ERROR: InterruptException: Stacktrace: [1] active_module() @ REPL ~/.julia/juliaup/julia-1.10.5+0.x64.linux.gnu/share/julia/stdlib/v1.10/REPL/src/REPL.jl:514 [2] #invokelatest#2 @ ./essentials.jl:892 [inlined] [3] invokelatest @ ./essentials.jl:889 [inlined] [4] active_module @ ./show.jl:502 [inlined] [5] show_type_name(io::IOContext{IOBuffer}, tn::Core.TypeName) @ Base ./show.jl:1041 [6] _show_type(io::IOContext{IOBuffer}, x::Type) @ Base ./show.jl:956 [7] show(io::IOContext{IOBuffer}, x::Type) @ Base ./show.jl:953 [8] show_typeparams(io::IOContext{IOBuffer}, env::Core.SimpleVector, orig::Core.SimpleVector, wheres::Vector{TypeVar}) @ Base ./show.jl:710 [9] show_datatype(io::IOContext{IOBuffer}, x::DataType, wheres::Vector{TypeVar}) @ Base ./show.jl:1130 [10] show_datatype @ ./show.jl:1077 [inlined] [11] _show_type(io::IOContext{IOBuffer}, x::Type) @ Base ./show.jl:961 [12] show(io::IOContext{IOBuffer}, x::Type) @ Base ./show.jl:953 [13] show_typeparams(io::IOContext{IOBuffer}, env::Core.SimpleVector, orig::Core.SimpleVector, wheres::Vector{TypeVar}) @ Base ./show.jl:710 [14] show_typealias(io::IOContext{IOBuffer}, name::GlobalRef, x::Type, env::Core.SimpleVector, wheres::Vector{TypeVar}) @ Base ./show.jl:743 [15] show_typealias(io::IOContext{IOBuffer}, x::Type) @ Base ./show.jl:796 [16] _show_type(io::IOContext{IOBuffer}, x::Type) @ Base ./show.jl:958 [17] show(io::IOContext{IOBuffer}, x::Type) @ Base ./show.jl:953 [18] show_typeparams(io::IOContext{IOBuffer}, env::Core.SimpleVector, orig::Core.SimpleVector, wheres::Vector{TypeVar}) @ Base ./show.jl:710 [19] show_datatype(io::IOContext{IOBuffer}, x::DataType, wheres::Vector{TypeVar}) @ Base ./show.jl:1130 [20] show_datatype @ ./show.jl:1077 [inlined] [21] _show_type(io::IOContext{IOBuffer}, x::Type) @ Base ./show.jl:961 [22] show(io::IOContext{IOBuffer}, x::Type) @ Base ./show.jl:953 [23] sprint(f::Function, args::Type; context::IOContext{IOBuffer}, sizehint::Int64) @ Base ./strings/io.jl:112 [24] sprint @ ./strings/io.jl:107 [inlined] [25] #print_type_bicolor#564 @ ./show.jl:2672 [inlined] [26] show_tuple_as_call(out::IOBuffer, name::Symbol, sig::Type; demangle::Bool, kwargs::Nothing, argnames::Vector{…}, qualified::Bool, hasfirst::Bool) @ Base ./show.jl:2539 [27] show_tuple_as_call @ ./show.jl:2507 [inlined] [28] show_spec_sig(io::IOBuffer, m::Method, sig::Type) @ Base.StackTraces ./stacktraces.jl:265 [29] show_spec_linfo(io::IOBuffer, frame::Base.StackTraces.StackFrame) @ Base.StackTraces ./stacktraces.jl:232 [30] show(io::IOBuffer, frame::Base.StackTraces.StackFrame) @ Base.StackTraces ./stacktraces.jl:270 [31] sprint(f::Function, args::Base.StackTraces.StackFrame; context::Nothing, sizehint::Int64) @ Base ./strings/io.jl:114 [32] sprint @ ./strings/io.jl:107 [inlined] [33] _collapse_repeated_frames(trace::Vector{Any}) @ Base ./errorshow.jl:863 [34] process_backtrace(t::Vector{Base.StackTraces.StackFrame}, limit::Int64; skipC::Bool) @ Base ./errorshow.jl:961 [35] process_backtrace (repeats 2 times) @ ./errorshow.jl:908 [inlined] [36] show_backtrace(io::IOContext{Base.TTY}, t::Vector{Base.StackTraces.StackFrame}) @ Base ./errorshow.jl:784 [37] showerror(io::IOContext{Base.TTY}, ex::StackOverflowError, bt::Vector{Base.StackTraces.StackFrame}; backtrace::Bool) @ Base ./errorshow.jl:97 [38] show_exception_stack(io::IOContext{Base.TTY}, stack::Base.ExceptionStack) @ Base ./errorshow.jl:975 [39] display_error(io::IOContext{Base.TTY}, stack::Base.ExceptionStack) @ Base ./client.jl:111 [40] #invokelatest#2 @ ./essentials.jl:892 [inlined] [41] invokelatest @ ./essentials.jl:889 [inlined] [42] repl_display_error(errio::IO, errval::Any) @ REPL ~/.julia/juliaup/julia-1.10.5+0.x64.linux.gnu/share/julia/stdlib/v1.10/REPL/src/REPL.jl:293 [43] print_response(errio::IO, response::Any, show_value::Bool, have_color::Bool, specialdisplay::Union{Nothing, AbstractDisplay}) @ REPL ~/.julia/juliaup/julia-1.10.5+0.x64.linux.gnu/share/julia/stdlib/v1.10/REPL/src/REPL.jl:310 [44] (::REPL.var"#57#58"{REPL.LineEditREPL, Pair{Any, Bool}, Bool, Bool})(io::Any) @ REPL ~/.julia/juliaup/julia-1.10.5+0.x64.linux.gnu/share/julia/stdlib/v1.10/REPL/src/REPL.jl:284 [45] with_repl_linfo(f::Any, repl::REPL.LineEditREPL) @ REPL ~/.julia/juliaup/julia-1.10.5+0.x64.linux.gnu/share/julia/stdlib/v1.10/REPL/src/REPL.jl:569 [46] print_response(repl::REPL.AbstractREPL, response::Any, show_value::Bool, have_color::Bool) @ REPL ~/.julia/juliaup/julia-1.10.5+0.x64.linux.gnu/share/julia/stdlib/v1.10/REPL/src/REPL.jl:282 [47] (::REPL.var"#do_respond#80"{…})(s::REPL.LineEdit.MIState, buf::Any, ok::Bool) @ REPL ~/.julia/juliaup/julia-1.10.5+0.x64.linux.gnu/share/julia/stdlib/v1.10/REPL/src/REPL.jl:911 [48] #invokelatest#2 @ ./essentials.jl:892 [inlined] [49] invokelatest @ ./essentials.jl:889 [inlined] [50] run_interface(terminal::REPL.Terminals.TextTerminal, m::REPL.LineEdit.ModalInterface, s::REPL.LineEdit.MIState) @ REPL.LineEdit ~/.julia/juliaup/julia-1.10.5+0.x64.linux.gnu/share/julia/stdlib/v1.10/REPL/src/LineEdit.jl:2656 [51] run_frontend(repl::REPL.LineEditREPL, backend::REPL.REPLBackendRef) @ REPL ~/.julia/juliaup/julia-1.10.5+0.x64.linux.gnu/share/julia/stdlib/v1.10/REPL/src/REPL.jl:1312 Some type information was truncated. Use show(err) to see complete types.

[prittjam]

using Meshes
l = Meshes.Line((0.0,0.0),(1.0,1.0))
b = Meshes.Box((0.0,0.0),(1.0,1.0))
intersects(l,b) 

also crashes with

ERROR: MethodError: no method matching iterate(::Nothing)

Closest candidates are: iterate(::Automa.ActionList) @ Automa ~/.julia/packages/Automa/rbg94/src/action.jl:68 iterate(::Automa.ActionList, ::Any) @ Automa ~/.julia/packages/Automa/rbg94/src/action.jl:68 iterate(::Tables.DictRowTable) @ Tables ~/.julia/packages/Tables/8p03y/src/dicts.jl:122 ...

Stacktrace: [1] iterate(::Base.Generator{Nothing, Meshes.var"#414#415"}) @ Base ./generator.jl:44 [2] iterate(::Base.Generator{Base.Generator{Nothing, Meshes.var"#414#415"}, Meshes.var"#424#425"}) @ Base ./generator.jl:44 [3] iterate(f::Base.Iterators.Flatten{Base.Generator{Base.Generator{Nothing, Meshes.var"#414#415"}, Meshes.var"#424#425"}}, state::Tuple{}) @ Base.Iterators ./iterators.jl:1200 [4] iterate(f::Base.Iterators.Flatten{Base.Generator{Base.Generator{Nothing, Meshes.var"#414#415"}, Meshes.var"#424#425"}}) @ Base.Iterators ./iterators.jl:1196 [5] first(itr::Base.Iterators.Flatten{Base.Generator{Base.Generator{Nothing, Meshes.var"#414#415"}, Meshes.var"#424#425"}}) @ Base ./abstractarray.jl:472 [6] _pboxes(points::Base.Iterators.Flatten{Base.Generator{Base.Generator{Nothing, Meshes.var"#414#415"}, Meshes.var"#424#425"}}) @ Meshes ~/.julia/packages/Meshes/1tCoG/src/boundingboxes.jl:89 [7] _bboxes(boxes::Base.Generator{Nothing, Meshes.var"#414#415"}) @ Meshes ~/.julia/packages/Meshes/1tCoG/src/boundingboxes.jl:87 [8] boundingbox(geoms::Nothing) @ Meshes ~/.julia/packages/Meshes/1tCoG/src/boundingboxes.jl:22 [9] boundingbox(p::Line{𝔼{2}, CoordRefSystems.Cartesian2D{CoordRefSystems.NoDatum, Quantity{Float64, 𝐋, Unitful.FreeUnits{…}}}}) @ Meshes ~/.julia/packages/Meshes/1tCoG/src/boundingboxes.jl:18 [10] intersects(g₁::Line{𝔼{…}, CoordRefSystems.Cartesian2D{…}}, g₂::Meshes.Box{𝔼{…}, CoordRefSystems.Cartesian2D{…}}) @ Meshes ~/.julia/packages/Meshes/1tCoG/src/predicates/intersects.jl:73 [11] top-level scope @ REPL[218]:1 Some type information was truncated. Use show(err) to see complete types.

[juliohm]

That is because we don't have an implementation for the pair Line and Box, and the fallback relies on the symmetry of the intersection:

https://github.com/JuliaGeometry/Meshes.jl/blob/a7802878459f568cb48cd950973e8b86a0c9dd28/src/intersections.jl#L100

The solution requires implementing a method intersection(f, line::Line, box::Box) in this source file:

https://github.com/JuliaGeometry/Meshes.jl/blob/master/src/intersections/lines.jl

[thchr]

There's an implementation for ::Ray, ::Box already, but not one for Line.

A 3D implementation without branches is e.g. (just as scaffold, not in the Meshes.jl style):

function intersects(b::Box, l::Line)
    # branchless line-box intersection following https://tavianator.com/2011/ray_box.html
    b_min, b_max = minimum(b), maximum(b)
    c = l.a
    ax = l.a - l.b
    inv_ax = 1 ./ ax

    tx1 = (b_min[1] - c[1]) * inv_ax[1]
    tx2 = (b_max[1] - c[1]) * inv_ax[1]
    tmin = min(tx1, tx2)
    tmax = max(tx1, tx2)

    ty1 = (b_min[2] - c[2]) * inv_ax[2]
    ty2 = (b_max[2] - c[2]) * inv_ax[2]
    tmin = max(tmin, min(ty1, ty2))
    tmax = min(tmax, max(ty1, ty2))
    
    tz1 = (b_min[3] - c[3]) * inv_ax[3]
    tz2 = (b_max[3] - c[3]) * inv_ax[3]   
    tmin = max(tmin, min(tz1, tz2))
    tmax = min(tmax, max(tz1, tz2))

    return tmax ≥ tmin, tmin, tmax
end

[juliohm]

Thank you @thchr ! Do you think you can prepare a PR with tests? I'd be happy to review.

It is important to cover all branches in the PR. You could use the Ray implementation as a starter.