Fastest way to find if point is inside part bounding box

Help and Feedback Scripting Support
#1

I have a number of train cars and a number of train car sensors. The train cars are particles, and the sensors are rotated 3D rectangles (part bounding boxes). I need to detect when the train cars are within the sensors. I want to do it as fast as possible.

Here’s what I have:

function Update()
	local FreeCars = {}
	for _,car in ipairs (Cars) do
		table.insert(FreeCars,car)
	end
	
	-- for simplicity, car can only occupy 1 sensor at a time
	for _,sensor in ipairs (Sensors) do
		for i = #FreeCars, 1, -1 do
			-- broad phase using spherical approximation
			if (FreeCars[i].CAttachment.WorldPosition - sensor.Position).magnitude < sensor.Radius then -- Radius is part.Size.Magnitude/2
				local SSize = sensor.Size -- Size is actually part.Size/2
				local Offset = sensor.CFrame:pointToObjectSpace(FreeCars[i].CAttachment.WorldPosition)
				-- narrow phase
				if Offset.X*Offset.X <= SSize.X*SSize.X and Offset.Y*Offset.Y <= SSize.Y*SSize.Y and Offset.Z*Offset.Z <= SSize.Z*SSize.Z then
					table.remove(FreeCars,i)
					-- update the car
				end
			end
		end
	end
end

Is this good? Is this bad? Are there obvious improvements? Let me know what you think.

2 Likes
#2

This looks like a great start and you have the right idea. Assuming this works fine then there isn’t necessarily anything wrong with it at all.

If you find that this isn’t as performant as you require then the next step is to improve your broad phase by using a spatial partitioning method, such as a quadtree. (other methods seem beyond the scope of this problem, more information can be found here )

#3

The only potential improvements in your code are situational. In the rare case where your bounding box is very long on one dimension, the distance check you’re doing might become futile and could be replaced with an Axis Alligned Bounding Box check.

Otherwise, if you do not intend on rotating your bounding boxes, you could replace the CFrame object space shifting with a check on an AABB.

Most likely with any of these changes you would see no tangible difference.

If your car count goes over 200 i would suggest you divide the check cycle in 3 or more different updates, repeating one after the other in different frames. You will lose in time precision but the performance will improve greatly.

2 Likes