enter image description here

Eventually this problem will be 3D, so I would like a solution that works in 3D.

My player is looking forwards. There is an axis-aligned box on the screen (FOV is guaranteed to be 90, so boxes behind the player aren't considered.)

I want to get the coordinates of the point on box that is closest to the player's looking direction.

I.e., if the player turned towards the box, which point of the box would intersect with their line of vision first?

  • \$\begingroup\$ What will the shape be in 3d? A rectangular solid? \$\endgroup\$ – Tim Holt May 24 '19 at 19:15
  • \$\begingroup\$ @TimHolt a cuboid (an "axis-aligned box") so yeah a rectangular solid \$\endgroup\$ – theonlygusti May 24 '19 at 21:59
  • \$\begingroup\$ How does this work in 3d? In 2-d, the 'edge of vision' of the player is two lines and the player sees an (infinitely long) circle sector in between. There are many generalisations of this in 3d, some of which will be much easier to work with than others. \$\endgroup\$ – ScienceSnake May 24 '19 at 23:10
  • \$\begingroup\$ @ScienceSnake idk what you mean \$\endgroup\$ – theonlygusti May 24 '19 at 23:12
  • 1
    \$\begingroup\$ @ScienceSnake yes along a single line, imagine a player with a long pokey nose i want to know what that hits first \$\endgroup\$ – theonlygusti May 25 '19 at 10:22

You could decompose that test into four separate tests:

For each edge AB, BC, CD, DA in the box ABCD, determine the distance to the ray. The closest of all four tests is your solution.

For the edge vs ray test, you could do segment-vs-segment, and just pretend the ray is a really long segment.

I found this 2D segment vs segment test that you can use for this.

Note that if multiple edges have distance 0 to the ray, you need to compute the actual intersections, and pick the one closest to the ray origin.

  • \$\begingroup\$ That's fine for the test, but in a 3d world you would be best to also do a Dot Test to ensure the face of the box is facing the ray as another test. The other test I would perform might be a Ray/plane test post the dot product test to eliminate parrallel rays. The original question talks about closest then mentions intersection, so i assume the ray has to collide and therefore parallel test is required. \$\endgroup\$ – ErnieDingo May 23 '19 at 22:43
  • \$\begingroup\$ If I understand it correctly, the method in the link doesn't work. If the segments don't intersect, but the extension of one into a line does intersect the other segment, then it will give the wrong answer. That's because, in this case, the closest distance is between the edge of one line and the middle of the other. The link provided doesn't appear to check for that. \$\endgroup\$ – ScienceSnake May 24 '19 at 23:07

First thing to note is that you only need to consider corners. The player will almost always see a corner of the box before an edge. In the rare cases where the alignment is just right, the player will see an edge and a corner at the same time (because every edge obviously contains corners). So it's enough to only consider corners.

The problem can be solved with linear algebra easily in 2-D, the generalisation to 3-D needs a bit more maths but nothing particularly advanced. The basic algorithm is:

1) From the position of the player and the angle of the line, create a linear equation y = m*x + c which defines the line.

2) The minimum distance between a point and a line is given by the length of a line segment perpendicular to the original line which reaches the point. So, from y = m*x + c construct a unit vector u perpendicular to it.

3) For each corner of rectangle p, find the value t such that p + tu lies on y = mx + c.

4) If all the t's are the same sign, it means that you are on the same side of all the corners. The distance to the rectangle is therefore min(abs(t)), and the corner you will see first is the one which gave that t. If some of the t's are positive and some negative, that means that you are clockwise of some corners and anticlockwise of others, and are therefore inside the rectangle.

EDIT: I did the maths on the back of an envelope. The value of \$t\$ is $$ t = \cos(\theta) (p_y-y_0) - \sin(\theta)(p_x-x_0) $$

Where \$(x_0, y_0)\$ is the coordinate of the player, \$\theta\$ is the angle from the horizontal \$+x\$ axis (measured by the direction towards the \$+y\$ axis) and \$(p_x, p_y)\$ is the coordinate of a corner. This is a shockingly simple result, if I was you I would redo the maths just to double check, it's only 6 or 7 lines of algebra.

The extension in 3-D depends on how the viewer works. Is the vision of the player a wedge or a cone?

  • \$\begingroup\$ I think in 3 dimensions you won't only see corners anywhere near as commonly \$\endgroup\$ – theonlygusti May 24 '19 at 22:49
  • \$\begingroup\$ No, in 3d the player will always see an edge first. But that's a 1-d object compared to a 2-d surface bounding the player's field of view so essentially the same trick works. \$\endgroup\$ – ScienceSnake May 24 '19 at 23:23

2D Solution

This is pretty easy if you divide this into two cases: line intersects object, and line doesn't intersect.

For the intersect case, as you've shown it's just a matter of finding the intersection closest to the viewer - something I assume won't be that hard to figure out.

And for the case of no intersection, a bit of illustrated rotation can help show how this can be figured out easily...

First, here is the scenario with your image...

enter image description here

Now rotate it so that your view vector is zero degrees and the viewer is at the origin (0,0)...

enter image description here

Now, all you have to do is find the corner with the smallest absolute value Y coordinate, and that is your intersection point.

There is one edge case (literally) where the view vector is parallel to an edge, and two points are equally close. I'm guessing for your requirements, you would choose the furthest from the viewer. Here's an illustration...

enter image description here

3D Solution

The concept is somewhat similar with 3D as follows...

First, if the line intersects the 3D shape, then choose the point of intersection as your answer.

If the line does not intersect, then you must find the point that is closest to your view line. Since you have stated that you are only solving this for rectangular solids (meaning there are only 12 edge vectors), I would probably just brute force calculate the closest distance from each edge vector to the view vector, and choose the smallest one, and the coordinate of that closest point. Rather than explain it here, I'll point to a Mathematics stack post that discusses finding the shortest distance between lines - https://math.stackexchange.com/questions/2213165/find-shortest-distance-between-lines-in-3d. There are probably other solutions online to be found.

  • \$\begingroup\$ Rotating it is quite computationally expensive (sin and cos) and I don't know how rotating it would "work" in 3 dimensions. \$\endgroup\$ – theonlygusti May 24 '19 at 18:54
  • \$\begingroup\$ You might want to reword your question to specifically state you're looking for a solution that works in 2D and 3D. \$\endgroup\$ – Tim Holt May 24 '19 at 19:04
  • 1
    \$\begingroup\$ The last statement in red is not true. The corner furthest away is the one that will be seen first. Just consider the line rotating and you'll see that it hits the furthest corner before the first one. \$\endgroup\$ – ScienceSnake May 24 '19 at 22:47
  • \$\begingroup\$ @theonlygusti both these concerns are lessened if you think of it as not a rotation, but a projection onto the subspace perpendicular to the ray. Then it's at most a couple of normalizations to get your basis vector(s), and then a bunch of dot products. You can apply an approximate arctangent if you want the smallest turn instead of the closest linear offset. \$\endgroup\$ – DMGregory May 24 '19 at 23:21
  • 1
    \$\begingroup\$ @theonlygusti, I want to emphasize that I'm not trying to give you code, or math, or hard exact answers here. I'm trying to give you a way to think about your problem that might lead you to an answer. Real growth as a developer comes from figuring things out sometimes. Keep in mind we don't know if you are an experienced programmer or not, or if you know a lot of math or not. Me? I'm visual. So I give you a visual answer to help you imagine how it could be solved. I will say though that your thinking of cos/sin as computationally intensive is naive - a problem 15-20 years ago, not now. \$\endgroup\$ – Tim Holt May 26 '19 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.