old roblox bvh for a friend

require.lua

local function require(name)
	while not shared[name] do
		wait()
	end

	return shared[name]
end

shared.require = require

RetroBvh.lua

--!nolint

local FLAG_BRANCH = 1
local FLAG_LEAF = 0

local Bvh = {}
Bvh.__index = Bvh

local function safe(x)
	-- safe epsilon
	return math.abs(x) < 1e-3 and (x < 0 and -1e-3 or 1e-3) or x
end

local function encode(a, b, c)
	-- utility to encode the start, finish, and id
	return a * 4294967296 + b * 65536 + c
end

local function decode(a)
	-- utility to decode the start, finish, and id
	return math.floor(a / 4294967296), math.floor((a / 65536) % 65536), a % 65536
end

local function drawBox(node)
	-- creates a box
	local part = Instance.new("Part")
	part.Size = node.max - node.min
	part.CFrame = CFrame.new((node.min + node.max) * 0.5)
	part.Transparency = 0.5
	part.Anchored = true
	part.Parent = workspace
end

local function getMajorAxis(a)
	-- gets the axis with the greatest
	-- direction. assumes a > 0
	if a.x > a.y and a.x > a.z then
		return Vector3.new(1, 0, 0)
	elseif a.y > a.x and a.y > a.z then
		return Vector3.new(0, 1, 0)
	else
		return Vector3.new(0, 0, 1)
	end
end

local function dot(a, b)
	return a.x * b.x + a.y * b.y + a.z * b.z
end

local function minVector(a, b)
	return Vector3.new(math.min(a.x, b.x), math.min(a.y, b.y), math.min(a.z, b.z))
end

local function maxVector(a, b)
	return Vector3.new(math.max(a.x, b.x), math.max(a.y, b.y), math.max(a.z, b.z))
end

local function doesAABBCollideAABB(min0, max0, min1, max1)
	return min0.x <= max1.x and max0.x >= min1.x
		and min0.y <= max1.y and max0.y >= min1.y
		and min0.z <= max1.z and max0.z >= min1.z
end

local function doesAABBCollidePoint(min, max, p)
	return min.x <= p.x and p.x <= max.x
		and min.y <= p.y and p.y <= max.y
		and min.z <= p.z and p.z <= max.z
end

local function doesAABBCollideRay(
	min, max,
	origin, invDir
)
	-- a + d*t = c
	-- t = (c - a) / d
	if doesAABBCollidePoint(min, max, origin) then
		return 0
	end

	local vMax = (max - origin) * invDir
	local vMin = (min - origin) * invDir

	local rMin = minVector(vMax, vMin)
	local rMax = maxVector(vMax, vMin)

	local tMin = math.max(rMin.x, rMin.y, rMin.z)
	local tMax = math.min(rMax.x, rMax.y, rMax.z)

	return 0.0 <= math.min(tMax, tMin)
		and tMin <= 1.0
		and tMin <= tMax
end

local function buildBranches(leaves)
	local queue = { encode(1, #leaves, 1) }
	local count = 1
	
	local branches = {}
	while #queue > 0 do
		local start, finish, id = decode(table.remove(queue))

		local span = finish - start
		if span <= 1 then
			branches[id] = {
				left = start,
				right = start ~= finish and finish or 0,

				max = maxVector(leaves[start].max, leaves[finish].max), 
				min = minVector(leaves[start].min, leaves[finish].min),

				flag = FLAG_LEAF
			}
		else
			local max = leaves[start].max
			local min = leaves[start].min
			
			-- get min and max
			for i = start + 1, finish do
				local leaf = leaves[i]
				max = maxVector(max, leaf.max)
				min = minVector(min, leaf.min)
			end

			local axis = getMajorAxis(max - min)
			local boxCenter = (min + max) * 0.5
			local boxSplit = dot(boxCenter, axis)

			-- partition yay
			local cursor = start
			local aux = { }
			for i = start, finish do
				local leaf = leaves[i]
				local center = (leaf.min + leaf.max) * 0.5
				local w = dot(center, axis)
				
				if w < boxSplit then
					-- put it on the left
					leaves[cursor] = leaf
					cursor = cursor + 1
				else
					-- put it on the right
					table.insert(aux, leaf)
				end
			end

			for i, leaf in ipairs(aux) do
				leaves[cursor + i - 1] = leaf
			end

			if cursor <= start + 1 or finish - 1 <= cursor then
				-- use a center split
				cursor = math.floor((start + finish) * 0.5)
			end

			table.insert(queue, encode(cursor, finish, count + 2))
			table.insert(queue, encode(start, cursor - 1, count + 1))			
			branches[id] = {
				left = count + 1,
				right = count + 2,

				max = max,
				min = min,

				flag = FLAG_BRANCH
			}
			
			count = count + 2
		end
	end

	return branches
end

function Bvh.new(leaves)
	return setmetatable({
		branches = buildBranches(leaves),
		leaves = leaves,
	}, Bvh)
end

function Bvh.query(self, a, b)
	local min = minVector(a, b)
	local max = maxVector(a, b)

	local branches = self.branches
	local leaves = self.leaves
	
	local queue = { 1 }
	local output = {}

	while #queue > 0 do
		local node = branches[table.remove(queue)]
		if node.flag == FLAG_LEAF then
			-- check both the left and right leaves
			local leftLeaf = leaves[node.left]
			local rightLeaf = leaves[node.right]
			
			if doesAABBCollideAABB(
				leftLeaf.min, leftLeaf.max,
				min, max
			) then
				table.insert(output, leftLeaf)
			end

			if rightLeaf and doesAABBCollideAABB(
				rightLeaf.min, rightLeaf.max,
				min, max
			) then
				table.insert(output, rightLeaf)
			end
		else
			local leftBranch = branches[node.left]
			local rightBranch = branches[node.right]
			if doesAABBCollideAABB(
				leftBranch.min, leftBranch.max,
				min, max
			) then
				table.insert(queue, node.left)
			end

			if doesAABBCollideAABB(
				rightBranch.min, rightBranch.max,
				min, max
			) then
				table.insert(queue, node.right)
			end
		end
	end

	return output
end

function Bvh.raycast(self, origin, direction)
	local branches = self.branches
	local leaves = self.leaves

	local invDir = Vector3.new(
		1.0 / safe(direction.x),
		1.0 / safe(direction.y),
		1.0 / safe(direction.z)
	)

	local queue = { 1 }
	local output = {}
	while #queue > 0 do
		local node = branches[table.remove(queue)]
		if node.flag == FLAG_LEAF then
			-- check both the left and right leaves
			local leftLeaf = leaves[node.left]
			local rightLeaf = leaves[node.right]

			if doesAABBCollideRay(
				leftLeaf.min, leftLeaf.max,
				origin, invDir
			) then
				table.insert(output, leftLeaf)
			end

			if rightLeaf and doesAABBCollideRay(
				rightLeaf.min, rightLeaf.max,
				origin, invDir
			) then
				table.insert(output, rightLeaf)
			end
		else
			local leftBranch = branches[node.left]
			local rightBranch = branches[node.right]
			if doesAABBCollideRay(
				leftBranch.min, leftBranch.max,
				origin, invDir
			) then
				table.insert(queue, node.left)
			end

			if doesAABBCollideRay(
				rightBranch.min, rightBranch.max,
				origin, invDir
			) then
				table.insert(queue, node.right)
			end
		end
	end

	return output
end

function Bvh.draw(self)
	local branches = self.branches
	local leaves = self.leaves

	local queue = { 1 }
	while #queue > 0 do
		local node = branches[table.remove(queue)]
		drawBox(node)
		
		if node.flag == FLAG_BRANCH then
			table.insert(queue, node.left)
			table.insert(queue, node.right)
		elseif node.right then
			drawBox(leaves[node.left])
			drawBox(leaves[node.right])
		else
			drawBox(leaves[node.left])
		end
	end
end

shared.Bvh = Bvh

usage.lua

while not shared.require do wait() end

local World = shared.require("World")

print("loaded world tester")

-- construct the world bvh
World.createWorld(workspace.Map)

-- do a raycast query
local hit, position, normal = World.raycast(workspace.A.Position, workspace.B.Position - workspace.A.Position)
if hit then
	hit.Color = Color3.new(1, 0, 0)
	workspace.Hit.CFrame = CFrame.new(position, position + normal)
end

-- do a region query
for i, object in ipairs(World.query(workspace.A.Position, workspace.B.Position)) do
	object.Color = Color3.new(1, 0, 0)
end

World.lua

while not shared.require do wait() end

local WorldBvh = nil
local Bvh = shared.require("Bvh")

local function safe(x)
	-- safe epsilon
	return math.abs(x) < 1e-3 and (x < 0 and -1e-3 or 1e-3) or x
end

local function getDescendants(from)
	local output = { from }
	local cursor = 1

	while output[cursor] do
		local instance = output[cursor]
		for i, child in ipairs(instance:children()) do
			table.insert(output, child)
		end

		cursor = cursor + 1
	end

	return output
end

local function minVector(a, b)
	return Vector3.new(math.min(a.x, b.x), math.min(a.y, b.y), math.min(a.z, b.z))
end

local function maxVector(a, b)
	return Vector3.new(math.max(a.x, b.x), math.max(a.y, b.y), math.max(a.z, b.z))
end

local function getBoundingBox(part)
	local cframe = part.CFrame
	local halfSize = part.Size * 0.5

	local x, y, z, r00, r10, r20, r01, r11, r21, r02, r12, r22 = cframe:components()
	local absMatrix = CFrame.new(
		x, y, z,
		math.abs(r00), math.abs(r10), math.abs(r20),
		math.abs(r01), math.abs(r11), math.abs(r21),
		math.abs(r02), math.abs(r12), math.abs(r22)
	)

	return absMatrix * -halfSize, absMatrix * halfSize
end

local function sign(x)
	return x > 0 and 1.0 or -1.0
end

local function dot(a, b)
	return a.x*b.x + a.y*b.y + a.z*b.z
end

local function unit(v)
	return v / math.sqrt(dot(v,v))
end

local function getRaySphere(
	cframe, size,
	origin, direction
)
	local r = math.max(math.max(size.x, size.y), size.z) * 0.5
	local z = origin - cframe.p

	-- z = a - p
	-- dot(bt + z, bt + z) = R^2
	-- dot(b,b)t^2 + 2dot(b,z)t + dot(z,z) - R^2 = 0
	local a = dot(direction, direction)
	local b = 2 * dot(direction, z)
	local c = dot(z, z) - r*r

	-- check discriminant
	local discriminant = b*b - 4*a*c
	if discriminant < 0 then
		return 1, Vector3.new()
	end

	local root = math.sqrt(discriminant)
	local root1 = (-b - root) / (2 * a)
	local root0 = (-b + root) / (2 * a)
	
	if root0 < 0 and root1 < 0 then
		return 1, Vector3.new()
	elseif root1 < root0 then
		root0 = root1
	end

	return root0, unit((origin + direction * root0) - cframe.p)
end

local function getRayBox(
	cframe, size,
	origin, direction
)
	local rotation = cframe - cframe.p
	direction = rotation:inverse() * direction
	origin = cframe:inverse() * origin

	local invDir = Vector3.new(
		1.0 / safe(direction.x),
		1.0 / safe(direction.y),
		1.0 / safe(direction.z)
	)

	local vMax = (size * 0.5 - origin) * invDir
	local vMin = -(size * 0.5 + origin) * invDir

	local rMin = minVector(vMax, vMin)
	local rMax = maxVector(vMax, vMin)

	local tMin = math.max(math.max(rMin.x, rMin.y), rMin.z)
	local tMax = math.min(math.min(rMax.x, rMax.y), rMax.z)

	if 0.0 <= math.min(tMax, tMin)
		and tMin <= 1.0
		and tMin <= tMax then
		-- hits the box, check which
		-- relative direction hit
		if tMin == rMin.x then
			return rMin.x, rotation * Vector3.new(sign(origin.x), 0, 0)
		elseif tMin == rMin.y then
			return rMin.y, rotation * Vector3.new(0, sign(origin.y), 0)
		else
			return rMin.z, rotation * Vector3.new(0, 0, sign(origin.z))
		end
	else
		return -1.0, Vector3.new()
	end
end

local World = {}

function World.createWorld(world)
	local nodes = {}
	for i, part in ipairs(getDescendants(world)) do
		if part.className == "Part" then
			local min, max = getBoundingBox(part)
			table.insert(nodes, {
				min = min,
				max = max,
				part = part,
			})
		end
	end

	WorldBvh = Bvh.new(nodes)
end

function World.query(a, b)
	-- marshals the bvh query and then gives back
	-- the parts. if you dont want to do this, just make
	-- the query in the bvh return the part instead
	local parts = {}
	for i, part in ipairs(WorldBvh:query(a, b)) do
		table.insert(parts, part.part)
	end

	return parts
end

function World.raycast(origin, direction)
	local tNorm = nil
	local tPart = nil
	local tMin = 1.0

	for i, leaf in ipairs(WorldBvh:raycast(origin, direction)) do
		local part = leaf.part
		if part.Shape == Enum.PartType.Block then
			-- block case
			local t, normal = getRayBox(part.CFrame, part.Size, origin, direction)
			if t < tMin then
				tNorm = normal
				tPart = part
				tMin = t
			end
		else
			-- sphere case
			local t, normal = getRaySphere(part.CFrame, part.Size, origin, direction)
			if t < tMin then
				tNorm = normal
				tPart = part
				tMin = t
			end
		end
	end

	if tPart then
		return tPart, origin + direction * tMin, tNorm
	else
		return nil
	end
end

shared.World = World

MARRY ME