Hi guys, trying my best to work this out but I’m ready to pull my hair out. Basically, I have two objects in 3D space. I need to find a point, any point, that both objects have a path to. I should be able to Raycast from both objects to point (x, y, z) and not have anything obstruct my rays. I’ve looked into sphere casting, overlapping spheres, rays, etc. and I cannot seem to think a way to solve my problem. Eternal gratitude if a kind soul can share some wisdom.
There is no easy solution for this problem. It should be obvious that there can be either no point, theoretically one point or infinitely many points. However there’s no straight forward algorithm to find possible solutions.
Though there are several approaches that might work out. First would be some sort of “voxel” grid from each objects perspective. So you could simply test points around each each object that can be reached from that object. Now you can simply find point which can be reached by both objects. This is basically a trial-an-error approach which can be very slow. Also if you don’t find any point that doesn’t mean there is not a point in between your grid positions.
Another way is a more analytical approach which resembles more a pathfinding algorithm. You simply cast a ray towatds your target object. It you can’t reach it you grab the mesh of the object that you actually hit and searching for the silhouette points as seen from your object. For each “edge” of the silhouette you can create a triangle which you can extend further outwards. This can be done by casting two rays through the two vertices of the silhouette (but of course a bit outward so you don’t hit the same object again). You can do the same from the other object. Now each object has a set of triangles. Now you can simply intersect each triangle from one object with each other triangle from the other object. If you find an intersection a possible point lies on the intersection line.
If none of the triangles intersect you would have to continue with the next object(s) you hit when you raycasted around the first occluder. However this approach also has several problems. If the occluding object surrounds one of your objects (like some sort of interior mesh) you will have problems actually finding proper silhouette points.
Even in 2d this is aleary a tough problem. In 3d things get much more complicated.
Can you be more specific what is your exact application of this test and what kind of environment do we talk about? As i said for a generic environment there’s no easy solution that always works. Keep in mind even the two objects can be very close together a possible point could be infinitely far away.
I can’t decide whether or not this is a tongue-in-cheek suggestion but have you considered trying to train up a neural net to approximate a solution to this problem? If you got one that could produce a bunch of probably right answers in a short time box and then rejected all the answers that were invalid, you would probably get an answer that was close enough to having a human sit there and make a decision that you would be satisfied.
It would probably fail for very complex cases but so would you or I if the case was complex enough.
Appreciate the responses fellas, it appears that it was as I feared and this is going to be a giant pain in my behind. I will study your ideas though and hopefully be able to but together some kind of rudimentary implementation. Thank you!