Is it possible to get all parts intersecting a Ray?

Help and Feedback Scripting Support
9

I have a GJK distance and intersection implementation. That should work until a c++ implementation is made. I ran into issues like this years ago (particularly when working on my navigation mesh pathfinder).

Below is pretty much all the code you need. You could remove the spherical check, since the maximum number of parts FindPartsInRegion3 returns is relatively small. I’d recommend replacing FindPartsInRegion3 with my AABB structure if the parts wont be moving around too much.


--< BEWARE >--
-- untested code ahead --

local GJK = require 'GJK'

local min = math.min
local max = math.max

local function rejectionVector(point, start, dir)
	local vStartToPoint = point - start
	return vStartToPoint - vStartToPoint:Dot(dir) * dir
end

local function rejectionMagnitudeSquared(point, start, dir)
	local vStartToPoint = point - start
	local projectionMagnitude = vStartToPoint:Dot(dir)
	return vStartToPoint:Dot(vStartPoint) - projectionMagnitude * projectionMagnitude
end

local pPos, pI, pJ, pK
local function supportPart(dir)
	return pPos
		+ pI:Dot(dir) > 0 and pI or -pI
		+ pJ:Dot(dir) > 0 and pJ or -pJ
		+ pK:Dot(dir) > 0 and pK or -pK
end

local rayStart, rayFinish
local function supportRay(dir)
	if rayStart:Dot(dir) > rayFinish:Dot(dir) then
		return rayStart
	else
		return rayFinish
	end
end

local function findPartsOnRay(start, dir, maxDist)
	finish = start + dir * maxDist
	-- Alternatively you could provide your own data structure
	-- to minimize the number of tested parts. I have a AABB spatial
	-- structure here: https://github.com/TylerRHoyer/AABB-Octree

	-- Also alternatively, you could provide your own set of parts to test
	-- if you only want to test a couple parts.

	-- To optimize this, you could do more, smaller region checks
	-- closer to the ray.
	local minP = 
	local maxP = 
	local parts = workspace:FindPartsInRegion3(
		Region3.new(
			Vector3.new(
				min(start.x, finish.x),
				min(start.y, finish.y),
				min(start.z, finish.z)
			), 
			Vector3.new(
				max(start.x, finish.x),
				max(start.y, finish.y),
				max(start.z, finish.z)
			)
		),
		nil,
		100 -- I'm not sure what the largest maximum number of parts returned is
	)

	-- This check is optional, but may reduce the number of parts that
	-- go into the next more expensive operation.
	for i, part in next, parts do
		if rejectionMagnitudeSquared(part.Position, start, dir) <= part.Size:Dot(part.Size) then
			parts[i] = nil
		end
	end

	-- You can combine this loop with the above, but I seperated to show
	-- the distinction between the operations.
	rayStart = start
	rayFinish = finish
	for i, part in next, parts do
		local cf = part.CFrame
		cf = cf - cf.p
		local s = part.Size * 0.5

		pPos = part.Position
		pI = cf.RightVector * s.X
		pJ = cf.UpVector * s.Y
		pK = cf.LookVector * s.Z
		if not GJK.intersection(
			supportPart,
			supportRay,
			rejectionVector(pPos, start, dir)
		) then
			parts[i] = nil
		end
	end

	return parts
end

Basically the core of the code is the call to GJK.intersection. It sets two callbacks, which when called with a vector return the point in the set they represent furthest in that direction. (As a side note, to represent a sphere you wouldn’t need a large number of points, just the center and radius. You’d return the center plus the direction times the radius. Now THAT is slick!) The third parameter is the starting search direction. It returns true if intersecting, and false if not.

Edit: Did I just necro this? Huh… my filters were set onto ‘latest’…

9 Likes