`Box` - `Line` intersection in 3D

[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))
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:

Meshes.jl/src/intersections.jl

Line 100 in a780287

intersection(f, g₁, g₂) = intersection(f, g₂, g₁)

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.