Closest Point Between 2 Rays

SourLemon100000 · October 5, 2024, 10:58pm

I have come across the need to find the closest point between 2 lines, sort of like Geogebra’s own function:

How would I go about achieving the same thing in Roblox Studio?

hotpocket285 · October 6, 2024, 1:37am

there probably is a way to do it mathematically but i had a similar situation that can be brute forced with for i loops, if you have the construct of the ray, you can just iterate along the two and sample small points along the ray looking for the closest possible two points.

skyblox7862 · October 6, 2024, 2:13am

closest point as in point of intersection???

knightmb1 · October 6, 2024, 2:16am

How many dimensions? Assuming 3d by the picture?

SourLemon100000 · October 6, 2024, 5:15am

I actually found a video on the math for it and am trying to wrap my head around it. I’d rather not brute force with loops as you’ve done because it’ll be running in a while loop that will be active quite often. Even if that doesn’t lead to performance issues, I feel like the math method would be a lot more elegant anyway.

Not necessarily. The 2 rays won’t always be intersecting each other. In fact, one of them is a camera ray from the player’s cursor, so I think it’d be safe to assume they’ll almost never intersect each other. Unless I somehow draw in a player with infinite accuracy…

Yes, I’m trying to do 3D. If it were 2D, it’d be so much simpler.

hotpocket285 · October 6, 2024, 5:25am

i watched the video and i can grasp it, my biggest problem is trying to convert it to code, i’m not really well versed in doing something like that. you can definitely get the (x, y, z) rate of change as if you have the vector constructs you already know the equation. i don’t think it’s too bad to brute force it, for my hockey game i do this on every single shot taken on the goalie to find the most optimal save position and animation. it’s not too bad but if you do find a way to convert the math into code i’d be interested in the solution

skyblox7862 · October 6, 2024, 1:44pm

function doMath(Origin_1, Direction_1, Origin_2 Direction_1)
    local PositionDifference = Origin_1 - Origin_2
    local DirectionDifference = Direction_1 - Direction_2
    
    local T = math.max(0,-PositionDifference :Dot(DirectionDifference ) / v_diff:Dot(DirectionDifference ))
    
    local point1 = Origin_1 * Direction_1 * T
    local point2 = Origin_2 * Direction_2 * T
    return point1 , point2 
end

try this?

DevSynaptix · October 6, 2024, 3:00pm

Optimisations to be done for this, and I would make sure you thoroughly test all edge cases, but maybe something like:

local function approximately(a, b, epsilon)
	epsilon = epsilon or 1e-6
	return a == b or math.abs(a - b) <= epsilon
end

local function sqrMagnitude(vec)
	return vec.X*vec.X + vec.Y*vec.Y + vec.Z*vec.Z
end

local function closestPointSegmentSegment(r0, r1, r2, r3)
	local v0 = r1 - r0
	local l0 = sqrMagnitude(v0)
	if approximately(l0, 0) then
		return false, nil, nil
	end
	v0 *= (1/math.sqrt(math.abs(l0)))

	local v1 = r3 - r2
	local l1 = sqrMagnitude(v1)
	if approximately(l1, 0) then
		return false, nil, nil
	end
	v1 *= (1/math.sqrt(math.abs(l1)))

	local r01 = r0 - r2
	local d0 = v1:Dot(v0)
	local d1 = v1:Dot(v1)
	local d2 = v0:Dot(v0)

	local d = d2*d1 - d0*d0
	if approximately(d, 0) then
		return true, 0, 0
	end

	local d3 = r01:Dot(v1)
	local d4 = r01:Dot(v0)
	d = (d3*d0 - d4*d1) / d

	return true, d, (d3 + d * d0) / d1
end

local function closestPointOnRay(r0, u, p)
	local d = math.max((p - r0):Dot(u), 0)
	return r0 + u*d
end

local function closestPointRayRay(r0, r1)
	local r0v = r0.Direction
	local r1v = r1.Direction

	local r0u = r0v.Unit
	local r1u = r1v.Unit

	local r0a = r0.Origin
	local r0b = r0a + r0v

	local r1a = r1.Origin
	local r1b = r1a + r1v

	local valid, d0, d1 = closestPointSegmentSegment(r0a, r0b, r1a, r1b)
	if not valid then
		return r0a
	end

	if d0 < 0 and d1 < 0 then
		local p0 = closestPointOnRay(r0a, r0u, r1a)
		local p1 = closestPointOnRay(r1a, r1u, r0a)
		if sqrMagnitude(p0 - r1a) <= sqrMagnitude(p1 - r0a) then
			return p0
		end

		return p1
	elseif d0 < 0 then
		return r0a
	elseif d1 < 0 then
		return closestPointOnRay(r1a, r1u, r0a)
	end

	return r0a + r0u*d0
end

Iogician · October 6, 2024, 9:39pm

i just tested and this seems to get within 0.00004% error (or basically 99.99996% accuracy) of the actual intersection point (if applicable) so i think this kind of works, but i’m surprised there isn’t a solidified mathematical way to find the exact intersection point. this will very much work as an approximation, though.

print(
    closestPointRayRay(
        Ray.new(Vector3.new(0,1,0), Vector3.new(2,1,0)), 
        Ray.new(Vector3.new(0,-1,0), Vector3.new(1,1,0))
    )
)

4.000001907348633, 3.0000009536743164, 0

SourLemon100000 · October 7, 2024, 2:55am

I think this might be the most plausible way to get what I want, so while I’m attempting to implement it, could you explain to me what each function does? So far, I’ve got:

approximately checks if 2 values are equal or if it’s less than or equal to a 3rd value or 0.000001
sqrMagnitude squares a vector (any reason you didn’t just use vec * vec for that?)
closestPointOnRay gets the point on the ray
closestPointRayRay runs all the functions after gathering some values

I’ve yet to figure out what closestPointSegmentSegment is supposed to do. Or, rather, I understand what it does, but not why you’ve wrote it, so I think it’d be helpful if you explained what it’s supposed to do.

I also don’t understand some parts of closestPointRayRay, specifically for the r0b and r1b variables. Why are you adding the origin and direction of the rays there? I’m also yet to figure out why any of the cases are the way they are (ie. I don’t understand why it returns closestPointOnRay(r1a, r1u, r0a) when d1 < 0).

All in all, could you tell me if I’m wrong about any of my assumptions on what the functions are supposed to do, explain what closestPointSegmentSegment is supposed to do, and explain why closestPointRayRay returns what it returns? Thanks!

LE4FBUG · October 7, 2024, 4:38am

There is a lot of linear algebra you need to do to solve this problem mathematically; however, I found a solution on the Math Stack Exchange that derives an equation that can be implemented in studio quite nicely by using cross and dot products of vectors.

First, you need to come up with a mathematical description for your rays which the most easiest way to do is to make them parametric; this means by using t as a seperate variable instead of x, y, or z. The good thing about this is you can define your ray solely based on vectors. The direction vector can be written as v (its a vector with a direction of 1 usually of where your ray is heading towards) and the start position of your ray can be written as a vector p. In code, calculating a position on your ray would look something like this:

local function calculatePointOnRay(t)
	local v = -- Write your direction here
	local p = -- Write your ray origin here
	return v * t + p
end

You could wrap this in a table to define v and p easier but implementing this form of a ray is up to you. With this form, we open ourselves to vector operations: the dot and cross product. In short, the dot product returns a scalar that describes how much of a vector, legth-wise, can be projected on another vector, and the cross product returns another vector which is perpedicular to both vectors you give it. In 3D space, there will always be this vector as long as the vectors are not parallel or antiparallel to each other (the cross product would be 0 in this case). Anyway, there are videos and other posts on the DevForum explaining these operations already and better than I can, and its not too essential to understand what these do when using the final equation. Its just important to know that you can’t multiply and divide vectors with other vectors like you can with normal numbers, but you can use these operations instead. They also have equality properties like multiplication and division (what you do on one side has to be done on the to other to not change the equation).

With this, the post on the stack exchange might make a bit more sense. Really what they are doing is using hacky linear algebra techniques to get a t value that can be used to find the closest point on ray 1. The same thing can also be done on ray 2 by swapping the values subscripted with 1 with 2 (this will make sense with the equation below). The most important part of this is the end equation which is quite elegant and very easy to implement since the Vector3 library includes the cross and dot products as their own methods that can be accessed inside each vector you create. Other solutions might be faster; however, they require solving systems of multiple linear equations which takes time to program and implement a full equation for. Here is the end equation for reference:

When they put 1 or 2 in the subscript it just means the p or v or t value belonging to a ray matching the same number, and the x and the dots are the cross and dot products, respectively. Also, I found step 3 a little confusing, but I think what they meant by “turning the equation into real numbers” is that they need t1 to be a scalar and not a vector.; the dot product is able to do turn the vectors into scalars. Overall, the code form of this equation boils down to this:

local p1 = -- Insert origin of ray 1 here
local p2 = -- Insert origin of ray 2 here
local v1 = -- Insert direction of ray 1 here
local v2 = -- Insert direction of ray 2 here
local function findClosestPointOnRay(p1, p2, v1, v2)
	local v1CrossV2 = v1:Cross(v2)
	local t1 = ((p2 - p1):Cross(v2)):Dot(v1CrossV2) / (v1CrossV2.Magnitude) ^ 2
	return t1 * v1 + p1
end

local closestPointOnRay1 = findClosestPointOnRay(p1, p2, v1, v2)
local closestPointOnRay2 = findClosestPointOnRay(p2, p1, v2, v1)

The code is pretty simple, and you can origanize it a bit better by grouping ray 1 values and ray 2 values in tables with methods. Additionally, if you find that you get negative t values, it means that the closest point of the ray is actually before the origin (this means that the ray can act as a line that continues infinitely in both directions). If you don’t want to get points that are backwards from where the ray is pointing, you can just clamp negative t-values to 0 which would bring the closest point back to the origin.

I hope I explained this fairly enough, its a tough topic to understand. Good luck with implementing this!

Edit: I’ve realized you can use the Ray object in Roblox to represent your ray values. If you end up using those, you can make v = ray.Direction and p = ray.Origin.

DevSynaptix · October 7, 2024, 1:16pm

Sure, here’s a breakdown of the functions:

approximation() - compares two numeric values to check equality/similarity such that:
- Resolves to true if a == b OR if the absolute difference between the two values is less than some threshold (in this case, 1e-6), we will consider them approximately equal and resolve to true.
- The epsilon parameter is used to define the threshold; in this case, however, the epsilon parameter is being used as a machine epsilon to account for approximation error
sqrMagnitude() - computes the square magnitude of a vector
- This calculates the magnitude of the vector in a similar manner to the Vector3().Magnitude property but doesn’t perform the square root operation
- As such, simply computing the squared magnitude of a vector is faster than additionally computing its square root - see an old blog by Ozzypig discussing this here, and you’ll find many more benchmarks and discussions relating to this online
closestPointOnRay() - computes the closest point along a ray:
- What we’re essentially doing here is treating the starting point of the ray as the origin of a Plane and then calculating the “point to plane distance”; this is used to compute a point along the normalised direction of the ray (or from the perspective of a plane, its normal)
- However, unlike computing the distance from a point to a plane, we only want a position along the ray’s direction, which is why we’re using math.max to clamp it to a positive value
closestPointSegmentSegment() - computes the closest point pair on two lines:
- The parameters describe the following lines:
  - Line 1 → r0 describes the start position, and r1 describes the end position
  - Line 2 → r2 describes the start position, and r3 describes the end position
- It should be noted that instead of returning the actual point here we’re actually computing the normalised distance of the points along both of the lines
  - The first return value, a boolean, describes whether we’re able to compute the point pairs. This function assumes that the direction vector of the each segment have a non-zero length (i.e. that both points of a single line aren’t collinear)
  - The second return value, a number, describes the normalised distance of the closest point along the first line (described by r0 and r1)
  - The third return value, a number, describes the normalised distance of the closest point along the second line (describes by r2 and r3)
- How the values are computed:
  - In a similar fashion to the previous closestPointOnRay() function, we’re actually looking at the lines from the perspective of a plane - see here for more details
  - Note that, when the lines are parallel, the denominator (defined as local d) will be zero so we return true, 0, 0
closestPointRayRay() - computes the closest point between two rays:
- Note that this function could be simplified to return two points, or skipped entirely by simply using the closestPointSegmentSegment() function; but from your original post, it sounded like you wanted a single point
- As such, this function computes the closest point between two rays by:
  1. Deriving the start and end positions of the ray when treated as a line segment by adding its Direction property to the Ray’s Origin
  2. Computing the normalised distance of the closest points on each line segment via closestPointSegmentSegment()
    - If invalid → i.e. one of the Ray objects have a zero magnitude direction, so we early exit and return the first line’s start position
    - If valid → continue
  3. We check the sign of the normalised distances for each of the return values, how we do that is described below in response to your other question

In Roblox, a Ray’s direction vector isn’t usually normalised unless you either (a) provide it with a normalised direction vector, or (b) if you derive a Ray object with a normalised direction by accessing its Unit property.

As such, the Direction property of a Ray defines both the length of the ray (its magnitude) AND its direction - see Euclidean vector for more information.

So, to confirm, the variables defined as r0a and r0b describe the start and end points of the first ray, whilst r1a and r1b describe the start and end points of the second ray.

From a perspective outside game development this might seem odd because a ray is usually defined as some infinite geometry but this is idealised, both in the real world & game development; it’s often the case that you’ll treat a ray as some finite line segment.

To do this, we take the Origin (its starting position, defined as some Vector3) of each Ray and add its Direction (defined as some Vector3 with a non-zero magnitude); this gives us both the start & end positions of a line segment which we can use as parameters for the closestPointSegmentSegment function.

Here are the cases:

If d0 and d1 are negative → the closest point is the shortest point along each ray since the lines are nearly parallel
If d0 is negative → the closest point from the perspective of Line 2 is some intersection behind Line 1; we early exit and return the start position of Line 1 since that would be the closest (though, depending on your use case, it may be better to treat it in the same way as below - feel free to change this behaviour)
If d1 is negative → the closest point from the perspective of Line 1 is some intersection behind Line 2 which means Line 1 is somewhere in front of Line 2’s direction vector; so we get the closest point of Line 1’s start position along Line 2
If d0 and d1 are positive → the rays are either parallel or are intersecting along their direction so the closest point is d0 (you could also consider selecting the greatest of d0 or d1 here - again, depends on the behaviour you want)

Also, for this: Vector3() * Vector3() returns a Vector3 but I needed a scalar value. If you wanted to use a built in function instead then you would need to use Vector3:Dot() - see Dot product for more info.

system · October 21, 2024, 1:17pm

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.