search

JuliaGeometry / Meshes.jl

Computational geometry in Julia
https://juliageometry.github.io/MeshesDocs/stable
Other
389 stars 84 forks source link

`Box`-`Triangle` intersection in 3D #809

Open cserteGT3 opened 5 months ago

cserteGT3 commented 5 months ago

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: https://github.com/JuliaGeometry/Meshes.jl/blob/4f1a5d86e23d80465e10c45a183bbd7249e6c7fc/src/predicates/intersects.jl#L96-L104

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 commented 5 months ago

@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 commented 5 months ago

Yes. I'll take a look into it.

juliohm commented 5 months ago

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

MachSilva commented 5 months ago

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 commented 4 months ago

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