Java Nearest Intersection

Question

I am making my own implementation of a raycaster in a game I am making, and I have come across a very hard problem. I have a player (the black dot), and I need to find the intersection nearest to the player. In the image below, the arrow is pointing to the intersection point I need.

What I guess I am trying to say is that I need a function something like this:

// Each line would take in 2 map values for it's 2 points
// In turn, the map would have to have an even number of points

public Point getNearestIntersection(int playerX, int playerY, int lineDir, Point[] map) {
    // whatever goes here
}

I am going to have to do this about 50 times every frame, with about 100 lines. I would like to get 40 fps at the least if possible... Even if I divide it up into threads I still feel that it would cause a lot of lag.

Is computing the intersection the problem or which one is nearest? — Fildor, Dec 19 '15 at 21:49
I'd suggest using a library. Jbox2d is pretty good, it supports something called bullet physics which is what I think you're looking for. — bigcodeszzer, Dec 19 '15 at 23:42
It seems you have to add ray direction as function parameter. And about lines - are they really lines or segments? About efficiency - is `map` static for multpile player queries? — MBo, Dec 20 '15 at 07:43

score 2 · Answer 1 · answered Dec 19 '15 at 22:22

2

The class Point has a method called distance which calculates the distance of two points. You then could loop all points to get the nearest. Could be something like this:

Point currentNearestIntersection;
double smallestDistance;

for (Point inter : intersections) {
    double distance = player.distance(inter );
    if (distance < smallestDistance) {
        currentNearestIntersection= inter;
        smallestDistance = distance;
    }
}

answered Dec 19 '15 at 22:22

qwertz

14,614
10
34
46

I need to do this about 50 times every frame it renders, and with 100 lines, I think that this would cause a HUGE amount of lag. Though I fear this may be my only option... – mooncat39 Dec 20 '15 at 07:45
Nevermind, I just added that information to the original question. – mooncat39 Dec 20 '15 at 07:50

score 0 · Answer 2 · edited May 23 '17 at 11:52

axis/line intersection is in reality solving:

p(t)=p0+dp*t
q(u)=q0+(q1-q0)*u
p(t)=q(u)
t=? u=?

where:

p0 is your ray start point (vector)
dp is ray direction (vector)
q0,q1 are line endpoints (vectors)
p(t),q(u) are points on axis,line
t,u are line parameters (scalars)

This is simple system of 2 linear equations (but in vectors) so it lead to N solutions where N is the dimensionality of the problem so choose the one that is not division by zero ... Valid result is if:

t>=0 and u=<0.0,1.0>

if you use unit dp vector for direction of your ray then from computing intersection between axis and line the t parameter is directly distance from the ray start point. So you can directly use that ...

if you need to speed up the intersections computation see

brute force line/line intersection with area subdivision

And instead of remebering all intersections store always the one with smallest but non negative t ...

[Notes]

if you got some lines as a grid then you can compute that even faster exploiting DDA algorithm and use real line/line intersection only for the iregular rest... nice example of this is Wolfenstein pseudo 3D raycaster problem like this

Java Nearest Intersection

2 Answers2