How does Roblox calculate the Bounding Boxes on Models/:GetExtentsSize()?

Hello DevForum! Hopefully you all had good holidays! :slight_smile:

Is there any code on calculating the BoundingBox when clicking on a model in Studio/using the function :GetExtentsSize()

image

How does Roblox create that outlne? Just looking for any code behind this.

2 Likes

Check out Model:GetBoundingBox(). It will return a CFrame and a Size for the bounding box, you can then use that to create an outline.

1 Like

I meant the code behind :GetExtentsSize() / :GetBoundingBox() :stuck_out_tongue:

ROBLOX Source code is private, so no source code for their implementation unless you want to get into some shady forums. GetExtentsSize calculates the object oriented minimum bounding box. There are various algorithms for doing so. Keep in mind calculating the exact bounding box is not cheap so usually when speed is desired approximations are computed instead. It’s not a trivial algorithm to understand, but you can check slides on it at a standford course.

7 Likes

Thanks a lot! Worth a look.

While minimum volume bounding boxes may require complex algorithms, I doubt that’s what roblox tries to compute. I’ve seen some bad bounding boxes, leading me to believe they pick an arbitrary axis and just make an axis aligned bounding box (likely choice: the first child or the primary part of a model).

And an axis aligned bounding box is easy! It is computed in O(n) time, and has easily understood algorithms.

So just keep in mind, @Lord_Superbithia, that the Stanford link does not compute axis aligned bounding boxes, but arbitrarily rotated bounding boxes, which are way more complicated.

4 Likes

Thanks! Maybe I should do some external research on boxes that aren’t given with rotation, could help me out on my current project.

Here’s what I came up with. It returns the CFrame + Size of the bounding box. This uses some code from zeuxcg’s bounding box (Annotated source of fastComputeAABB and fasterComputeAABB with notes for expensive lines · GitHub)

function GetBoundingBox(model, orientation)
	if typeof(model) == "Instance" then
		model = model:GetDescendants()
	end
	if not orientation then
		orientation = CFrame.new()
	end
	local abs = math.abs
	local inf = math.huge

	local minx, miny, minz = inf, inf, inf
	local maxx, maxy, maxz = -inf, -inf, -inf

	for _, obj in pairs(model) do
		if obj:IsA("BasePart") then
			local cf = obj.CFrame
			cf = orientation:toObjectSpace(cf)
			local size = obj.Size
			local sx, sy, sz = size.X, size.Y, size.Z

			local x, y, z, R00, R01, R02, R10, R11, R12, R20, R21, R22 = cf:components()

			local wsx = 0.5 * (abs(R00) * sx + abs(R01) * sy + abs(R02) * sz)
			local wsy = 0.5 * (abs(R10) * sx + abs(R11) * sy + abs(R12) * sz)
			local wsz = 0.5 * (abs(R20) * sx + abs(R21) * sy + abs(R22) * sz)

			if minx > x - wsx then
				minx = x - wsx
			end
			if miny > y - wsy then
				miny = y - wsy
			end
			if minz > z - wsz then
				minz = z - wsz
			end

			if maxx < x + wsx then
				maxx = x + wsx
			end
			if maxy < y + wsy then
				maxy = y + wsy
			end
			if maxz < z + wsz then
				maxz = z + wsz
			end
		end
	end

	local omin, omax = Vector3.new(minx, miny, minz), Vector3.new(maxx, maxy, maxz)
	local omiddle = (omax+omin)/2
	local wCf = orientation - orientation.p + orientation:pointToWorldSpace(omiddle)
	local size = (omax-omin)
	return wCf, size
end

Result (cf, size = GetBoundingBox(model, model.PrimaryPart.CFrame)). The selection box is what roblox calculates.

You can pass any CFrame as the orientation and it will spit out a bounding box that’s aligned to that orientation.

25 Likes

Someone asked me if you could optimize XAXA’s function, so I’ve made this version which is slightly faster (according to my benchmarks, ~1 second when called 10 ^ 7 times), for those interested:

-- It's faster to localize object methods
local Methods = Instance.new('Part')
local IsA = Methods.IsA
local GetDescendants = Methods.GetDescendants

-- Same goes for CFrame methods
local CFMethods = CFrame.new()
local ToObjSpace = CFMethods.toObjectSpace
local GetComponents = CFMethods.GetComponents
local PointToWorldSpace = CFMethods.PointToWorldSpace

local inf = math.huge
local negInf = -inf
function GetBoundingBox(model, orientation)
	-- ternary is faster according to my benchmarks
	model = type(model) ~= 'table' and GetDescendants(model) or model

	orientation = orientation or CFMethods

	local minx, miny, minz = inf, inf, inf
	local maxx, maxy, maxz = negInf, negInf, negInf

	-- next is just my preference, LuaU optimized next and pairs out anyway
	for _, obj in next, model do
		-- localization of IsA method
		if IsA(obj, 'BasePart') then
			local cf = ToObjSpace(orientation, obj.CFrame)
			local size = obj.Size
			local sx, sy, sz = size.X, size.Y, size.Z

			-- Localization of GetComponents
			local x, y, z, R00, R01, R02, R10, R11, R12, R20, R21, R22 = GetComponents(cf)

			-- LuaU optimizes out localization of global table indexing (such as math.abs); 
			-- localization is actually slower in this case!
			local wsx = 0.5 * (math.abs(R00) * sx + math.abs(R01) * sy + math.abs(R02) * sz)
			local wsy = 0.5 * (math.abs(R10) * sx + math.abs(R11) * sy + math.abs(R12) * sz)
			local wsz = 0.5 * (math.abs(R20) * sx + math.abs(R21) * sy + math.abs(R22) * sz)

			-- ternary is faster according to my benchmarks
			minx = minx > x - wsx and x - wsx or minx
			miny = miny > y - wsy and y - wsy or miny
			minz = minz > z - wsz and z - wsz or minz

			maxx = maxx < x + wsx and x + wsx or maxx
			maxy = maxy < y + wsy and y + wsy or maxy
			maxz = maxz < z + wsz and z + wsz or maxz
		end
	end

	-- removed redundant variable definitions that are only used once
	local omin, omax = Vector3.new(minx, miny, minz), Vector3.new(maxx, maxy, maxz)
	-- swapped / 2 to * 0.5, as multiplication is faster. This is nitpicking at this point tho lol
	return orientation - orientation.p + PointToWorldSpace(orientation, (omax + omin) * 0.5), (omax - omin)
end

Unsure why you would need something optimized to this extent, since if you even need to optimize you’re probably doing something wrong, but here you go (sorry to bump btw).

EDIT: Fixed an issue where the results weren’t consistent with @XAXA’s original code… Really sorry about that. Also optimized it out a bit more.

11 Likes

Apparently someone hit a bug with this that wasn’t in my implementation, so use with caution.

I apologize for the message, when testing I was using the function that claimed to optimize your function. Assuming that it had been dutifully optimized it, I tested it, found the issue I mentioned above, and was struggling to find results. I am now realizing that your original function does not have this issue at all and works perfectly fine.

UPDATE: See below, it’s fixed!

3 Likes

Really sorry about that!
I edited the function and fixed the issue, and have verified it by running GetBoundingBox_Optimized(...) == GetBoundingBox_Original(...) on a couple of models that had different positions and sizes. No idea what was going through my head at the time :man_facepalming:

Code used to verify the result:
https://paste.sh/0gSeHPrB#I5s6FPs1JWBoLkaLvaN_TorI

2 Likes

First off, sorry for the bump. I just wanted to share a slightly edited function that can get the bounding box from any instance that has BaseParts as descendants, even if the passes instance is a BasePart itself.

local function GetBoundingBox(instance: Instance, orientation: CFrame?): (CFrame,Vector3)
	local isPart: boolean = instance:IsA("BasePart")
	local descendants: {Instance} = instance:GetDescendants()
	if isPart then table.insert(descendants, instance) end
	
	local orientation: CFrame = if orientation then orientation.Rotation elseif isPart and instance:FindFirstChildWhichIsA("BasePart", true) then (instance:: BasePart).CFrame.Rotation else CFrame.identity

	local inf: number = math.huge
	local negInf: number = -inf

	local minx, miny, minz = inf, inf, inf
	local maxx, maxy, maxz = negInf, negInf, negInf

	local function adjust(part: BasePart): ()
		local size: Vector3 = part.Size
		local sx, sy, sz = size.X, size.Y, size.Z

		local x, y, z, R00, R01, R02, R10, R11, R12, R20, R21, R22 = orientation:ToObjectSpace(part.CFrame):GetComponents()
		local wsx = 0.5 * (math.abs(R00) * sx + math.abs(R01) * sy + math.abs(R02) * sz)
		local wsy = 0.5 * (math.abs(R10) * sx + math.abs(R11) * sy + math.abs(R12) * sz)
		local wsz = 0.5 * (math.abs(R20) * sx + math.abs(R21) * sy + math.abs(R22) * sz)

		minx = if minx > (x - wsx) then x - wsx else minx
		miny = if miny > (y - wsy) then y - wsy else miny
		minz = if minz > (z - wsz) then z - wsz else minz
		
		maxx = if maxx < (x + wsx) then x + wsx else maxx
		maxy = if maxy < (y + wsy) then y + wsy else maxy
		maxz = if maxz < (z + wsz) then z + wsz else maxz
	end
	
	for _, descendant: Instance in pairs(descendants) do
		if descendant:IsA("BasePart") then adjust(descendant) end
	end

	local omin, omax = Vector3.new(minx, miny, minz), Vector3.new(maxx, maxy, maxz)
	return orientation + orientation:PointToWorldSpace((omax + omin) * 0.5), (omax - omin)
end
  • Note: This function does differ a bit. If you pass an Instance to the function without passing an orientation, the orientation will default to the instance CFrame if it is a BasePart and has a descendant which is a BasePart. However, if the Instance isn’t a BasePart or is and doesn’t have a BasePart descendant, then it defaults to the identity CFrame (as the original did).
3 Likes