- Home /
Finding a point that is "visible" to two objects
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.
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!
Answer by Bunny83 · Nov 27, 2017 at 09:53 PM
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.
Here's an Example Image that shows two 2d edge cases.
A trivial example of when this is impossible is when one of the points is on the inside of a spherical shell and the other is outside it
Answer by MaxGuernseyIII · Nov 27, 2017 at 10:07 PM
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.
Hmm, as much as i love neural networks i don't really see how you would use one in this case. An ANN requires input to produce it's output. What would you use as input? How do you input the environment? Just the two positons would be pretty pointless.
Also note that while the 2d case would be more or less trivial for a human, the 3d case is much more difficult, even for a human. We still don't know the exact application. For example for an FPS game where most of the game happens more or less in the same plane the problem could be reduced to a 2d problem.
Though it would be interesting what exactly you have in $$anonymous$$d with the ANN approach. Btw i've created an ANN in my answer over here. Though it's only ment as generational ANN so no backpropagation just random mutation. Though it might be a starting point. Of course there are other ready to use solutions out there.
I mean...we know a neural network can solve a lot of these problems because that's how you and I do it. We just have far superior hardware.
They have to evolved to the point where you can feed them variable-sized inputs. How would they process things like images, sound, and video? Run an FFT, super-complex hash, or other "fingerprint-generating" algorithm first and then feed the output of that into the neural net or something? That seems like you lose too much information when you do that.
Now it may be possible that you would need too big a network and it would be too slow for it to work. If you have a small number of shapes you are using, you could probably just feed it the relevant locations, orientations, and type of shape, then train it to "know" how each type of shape behaves.
You could also have the inputs be raycast-hit-depth maps for a radial pattern distributed over a cone pointed away from each of the two objects. If you want to get fancy, you could have the outputs be guesses as to viable answers as well as guesses as to other codes to sample. Then you punish it if any of the answers are right or any of the suggested grids increase your chances of an answer thereafter. That would cost a lot to train because I think you'd need a person to make the second judgment call.
There's also no way an effective one could be as fast as an heuristic such as you describe but the training-cost-to-effectiveness ratio might make it worth doing anyway.