Box-Triangle intersection in 3D

[cserteGT3]

I discovered the following:

t = Triangle((Point(-60.0, -35.0, 55.0), Point(-68.75, -33.43333, 54.90143), Point(-68.75, -35.0, 55.0)))
b = Box((-77.5, -35.0, 54.6073),(-68.75, -31.8914, 55.0))
intersects(b, t)

Running this code causes an infinite loop here:

Meshes.jl/src/predicates/intersects.jl

Lines 96 to 104 in 4f1a5d8

	while true
	P = minkowskipoint(g₁, g₂, d)
	if (P - O) ⋅ d < zero(T)
	return false
	end
	push!(points, P)
	d = gjk!(O, points)
	isnothing(d) && return true

In this particular case changing the argument order solves the issue (running intersects(t,b)), but in general it does not solve the issue.
I tried normalizing my input, but it doesn't help.

s = maximum(sides(boundingbox([t, b])))
tn = Scale(1 / s)(t)
bn = Scale(1 / s)(b)
intersects(bn, tn)

I am not sure why is this the case, on other triangle-box pairs it works fine. Maybe because they have one vertice that is common?

[juliohm]

@MachSilva if I remember correctly, you contributed the GJK algorithm in the 3D case, right? Appreciate if you can take a look to see if this corner case can be fixed.

[MachSilva]

Yes. I'll take a look into it.

[juliohm]

@MachSilva appreciate if you can take a look at it. I will be working on other fronts tomorrow before the next minor release.

[MachSilva]

Sorry for the delay. I've taken a look for some time and I didn't found the cause of the loop yet. I've been looking it in my spare time only. So, I can't tell how much time I'll take to fix it, but I'll still look for a fix.

[juliohm]

Thank you for taking a look into it @MachSilva ❤️