local function E(R,U,A)if R:IsA("\066\097\115\101\080\097\114\116")then R.CFrame=U*(R.CFrame-A)+A end local J=R:GetChildren()for R=1,#J,1 do E(J[R],U,A)end end local function R(R,U)local A=CFrame.Angles(0,U,0)local J=(R:GetModelCFrame()).p E(R,A,J)end local function U(E,R,A,J)if E:IsA("\066\097\115\101\080\097\114\116")then R[#R+1]=E elseif E:IsA("\083\099\114\105\112\116")then A[#A+1]=E elseif E:IsA("\068\101\099\097\108")then J[#J+1]=E end for E,g in pairs(E:GetChildren())do U(g,R,A,J)end end local function A(E,R)local U=(game:GetService("\087\111\114\107\115\112\097\099\101")):FindFirstChild("\084\101\114\114\097\105\110")local A=U:WorldToCell(E)local J=U:WorldToCell(R)local g=A.X local q=A.Y local a=A.Z local l=J.X local T=J.Y local w=J.Z if g<U.MaxExtents.Min.X then g=U.MaxExtents.Min.X end if q<U.MaxExtents.Min.Y then q=U.MaxExtents.Min.Y end if a<U.MaxExtents.Min.Z then a=U.MaxExtents.Min.Z end if l>U.MaxExtents.Max.X then l=U.MaxExtents.Max.X end if T>U.MaxExtents.Max.Y then T=U.MaxExtents.Max.Y end if w>U.MaxExtents.Max.Z then w=U.MaxExtents.Max.Z end for E=g,l,1 do for R=q,T,1 do for A=a,w,1 do if(U:GetCell(E,R,A)).Value>0 then return true end end end end return false end local function J(E,R)if not E then return end if E.className=="\083\101\097\116"or E.className=="\086\101\104\105\099\108\101\083\101\097\116"then table.insert(R,E)end local U=E:GetChildren()for E=1,#U,1 do J(U[E],R)end end local function g(E,R)local U={}J(E,U)if R then for E=1,#U,1 do local R=U[E]:FindFirstChild("\083\101\097\116\087\101\108\100")while R do R:Remove()R=U[E]:FindFirstChild("\083\101\097\116\087\101\108\100")end end else for E=1,#U,1 do local R=Instance.new("\087\101\108\100")R.Name="\083\101\097\116\087\101\108\100"R.Parent=U[E]end end end local function q(E)local R=E:FindFirstChild("\065\117\116\111\065\108\105\103\110\084\111\070\097\099\101")if R then return R.Value else return false end end local function a(E)local R=Vector3.new(1,0,0)local U=Vector3.new(0,1,0)local A=Vector3.new(0,0,1)local J=(E.x*R.x+E.y*R.y)+E.z*R.z local g=(E.x*U.x+E.y*U.y)+E.z*U.z local q=(E.x*A.x+E.y*A.y)+E.z*A.z if math.abs(J)>math.abs(g)and math.abs(J)>math.abs(q)then if J>0 then return 0 else return 3 end elseif math.abs(g)>math.abs(J)and math.abs(g)>math.abs(q)then if g>0 then return 1 else return 4 end else if q>0 then return 2 else return 5 end end end local function l(E,R)local U=nil if not R then return R end if R and(R:IsA("\077\111\100\101\108")or R:IsA("\084\111\111\108"))then U=R:GetModelCFrame()R:TranslateBy(E.p-U.p)else R.CFrame=E end return R end local function T(E,R,U)if math.abs(R)<.01 then return 0 end return(U-E)/R end local function w(E,R,U)if not E then return 0 end local A=nil local J=nil if E:IsA("\077\111\100\101\108")then A=E:GetModelCFrame()J=E:GetModelSize()else A=E.CFrame J=E.Size end local g=A:pointToObjectSpace(R)local q=A:pointToObjectSpace(U)local a=q-g local l=1 local w=1 local x=1 if a.X>0 then l=-1 end if a.Y>0 then w=-1 end if a.Z>0 then x=-1 end local D=T(g.X,a.X,(J.X/2)*l)local S=T(g.Y,a.Y,(J.Y/2)*w)local j=T(g.Z,a.Z,(J.Z/2)*x)local c=0 if D>S then if D>j then c=1*l else c=3*x end else if S>j then c=2*w else c=3*x end end return c end local function x(E)local R=Vector3.new(math.huge,math.huge,math.huge)local U=Vector3.new(-math.huge,-math.huge,-math.huge)if E:IsA("\084\101\114\114\097\105\110")then R=Vector3.new(-2,-2,-2)U=Vector3.new(2,2,2)elseif E:IsA("\066\097\115\101\080\097\114\116")then R=-0.5*E.Size U=-R else U=E:GetModelSize()*.5 R=-U end local A=E:FindFirstChild("\074\117\115\116\105\102\105\099\097\116\105\111\110")if A~=nil then local E=A.Value local J=Vector3.new(2,2,2)local g=(U-R)-Vector3.new(.01,.01,.01)local q=Vector3.new(4*math.ceil(g.x/4),4*math.ceil(g.y/4),4*math.ceil(g.z/4))local a=q-g R=R-(.5*a)*E U=U+(.5*a)*(J-E)end return R,U end local function D(E)local R=Vector3.new(math.huge,math.huge,math.huge)local U=Vector3.new(-math.huge,-math.huge,-math.huge)if E:IsA("\066\097\115\101\080\097\114\116")and not E:IsA("\084\101\114\114\097\105\110")then local A=E.CFrame:pointToWorldSpace(-0.5*E.Size)local J=E.CFrame:pointToWorldSpace(.5*E.Size)R=Vector3.new(math.min(A.X,J.X),math.min(A.Y,J.Y),math.min(A.Z,J.Z))U=Vector3.new(math.max(A.X,J.X),math.max(A.Y,J.Y),math.max(A.Z,J.Z))elseif E:IsA("\084\101\114\114\097\105\110")then else local A=(E:GetModelCFrame()):pointToWorldSpace(-0.5*E:GetModelSize())local J=(E:GetModelCFrame()):pointToWorldSpace(.5*E:GetModelSize())R=Vector3.new(math.min(A.X,J.X),math.min(A.Y,J.Y),math.min(A.Z,J.Z))U=Vector3.new(math.max(A.X,J.X),math.max(A.Y,J.Y),math.max(A.Z,J.Z))end return R,U end local function S(E)if E.Parent:FindFirstChild("\082\111\098\108\111\120\077\111\100\101\108")~=nil then return x(E.Parent)else return x(E)end end local function j(E)if E.Parent:FindFirstChild("\082\111\098\108\111\120\077\111\100\101\108")~=nil then if E.Parent:IsA("\084\111\111\108")then return E.Parent.Handle.CFrame else return E.Parent:GetModelCFrame()end else return E.CFrame end end local function c(E)if not E then return false end if not E.Parent then return false end if E:FindFirstChild("\072\117\109\097\110\111\105\100")then return false end if E:FindFirstChild("\082\111\098\108\111\120\083\116\097\109\112\101\114")or E:FindFirstChild("\082\111\098\108\111\120\077\111\100\101\108")then return true end if E:IsA("\080\097\114\116")and not E.CanCollide then return false end if E==game:GetService("\076\105\103\104\116\105\110\103")then return false end return c(E.Parent)end

local function rotatePartAndChildren(part, rotCF, offsetFromOrigin)
	-- rotate this thing, if it's a part
	if part:IsA("BasePart") then
		part.CFrame = (rotCF * (part.CFrame - offsetFromOrigin)) + offsetFromOrigin
	end

	-- recursively do the same to all children
	local partChildren = part:GetChildren()
	for c = 1, #partChildren do rotatePartAndChildren(partChildren[c], rotCF, offsetFromOrigin) end
end

local function modelRotate(model, yAngle)
	local rotCF = CFrame.Angles(0, yAngle, 0)
	local offsetFromOrigin = model:GetModelCFrame().p

	rotatePartAndChildren(model, rotCF, offsetFromOrigin)
end


local function collectParts(object, baseParts, scripts, decals)
	if object:IsA("BasePart") then
		baseParts[#baseParts+1] = object
	elseif object:IsA("Script") then
		scripts[#scripts+1] = object
	elseif object:IsA("Decal") then
		decals[#decals+1] = object
	end

	for index,child in pairs(object:GetChildren()) do
		collectParts(child, baseParts, scripts, decals)
	end
end

local function clusterPartsInRegion(startVector, endVector)
	local cluster = game:GetService("Workspace"):FindFirstChild("Terrain")

	local startCell = cluster:WorldToCell(startVector)
	local endCell = cluster:WorldToCell(endVector)

	local startX = startCell.X
	local startY = startCell.Y
	local startZ = startCell.Z

	local endX = endCell.X
	local endY = endCell.Y
	local endZ = endCell.Z

	if startX < cluster.MaxExtents.Min.X then startX = cluster.MaxExtents.Min.X end
	if startY < cluster.MaxExtents.Min.Y then startY = cluster.MaxExtents.Min.Y end
	if startZ < cluster.MaxExtents.Min.Z then startZ = cluster.MaxExtents.Min.Z end

	if endX > cluster.MaxExtents.Max.X then endX = cluster.MaxExtents.Max.X end
	if endY > cluster.MaxExtents.Max.Y then endY = cluster.MaxExtents.Max.Y end
	if endZ > cluster.MaxExtents.Max.Z then endZ = cluster.MaxExtents.Max.Z end

	for x = startX, endX do
		for y = startY, endY do
			for z = startZ, endZ do
				if (cluster:GetCell(x, y, z).Value) > 0 then return true end
			end
		end
	end

	return false
end

local function findSeatsInModel(parent, seatTable)
	if not parent then return end

	if parent.className == "Seat" or parent.className == "VehicleSeat" then
		table.insert(seatTable, parent)
	end
	local myChildren = parent:GetChildren()
	for j = 1, #myChildren do
		findSeatsInModel(myChildren[j], seatTable)
	end
end

local function setSeatEnabledStatus(model, isEnabled)
	local seatList = {}
	findSeatsInModel(model, seatList)

	if isEnabled then
		-- remove any welds called "SeatWeld" in seats
		for i = 1, #seatList do
			local nextSeat = seatList[i]:FindFirstChild("SeatWeld")
			while nextSeat do nextSeat:Remove() nextSeat = seatList[i]:FindFirstChild("SeatWeld") end
		end
	else
		-- put a weld called "SeatWeld" in every seat
		--   this tricks it into thinking there's already someone sitting there, and it won't make you sit XD
		for i = 1, #seatList do
			local fakeWeld = Instance.new("Weld")
			fakeWeld.Name = "SeatWeld"
			fakeWeld.Parent = seatList[i]
		end
	end
end

local function autoAlignToFace(parts)
	local aatf = parts:FindFirstChild("AutoAlignToFace")
	if aatf then return aatf.Value else return false end
end

local function getClosestAlignedWorldDirection(aVector3InWorld)
	local xDir = Vector3.new(1,0,0)
	local yDir = Vector3.new(0,1,0)
	local zDir = Vector3.new(0,0,1)
	local xDot = aVector3InWorld.x * xDir.x + aVector3InWorld.y * xDir.y + aVector3InWorld.z * xDir.z
	local yDot = aVector3InWorld.x * yDir.x + aVector3InWorld.y * yDir.y + aVector3InWorld.z * yDir.z
	local zDot = aVector3InWorld.x * zDir.x + aVector3InWorld.y * zDir.y + aVector3InWorld.z * zDir.z

	if math.abs(xDot) > math.abs(yDot) and math.abs(xDot) > math.abs(zDot) then
		if xDot > 0 then
			return 0
		else
			return 3
		end
	elseif math.abs(yDot) > math.abs(xDot) and math.abs(yDot) > math.abs(zDot) then
		if yDot > 0 then
			return 1
		else
			return 4
		end
	else
		if zDot > 0 then
			return 2
		else
			return 5
		end
	end
end

local function positionPartsAtCFrame3(aCFrame, currentParts)
	local insertCFrame = nil
	if not currentParts then return currentParts end
	if currentParts and (currentParts:IsA("Model") or currentParts:IsA("Tool")) then
		insertCFrame = currentParts:GetModelCFrame()
		currentParts:TranslateBy(aCFrame.p - insertCFrame.p)
	else
		currentParts.CFrame = aCFrame
	end
	return currentParts
end

local function calcRayHitTime(rayStart, raySlope, intersectionPlane)
	if math.abs(raySlope) < .01 then return 0 end -- 0 slope -->  we just say intersection time is 0, and sidestep this dimension
	return (intersectionPlane - rayStart) / raySlope
end

local function modelTargetSurface(partOrModel, rayStart, rayEnd)
	if not partOrModel then
		return 0
	end

	local modelCFrame = nil
	local modelSize = nil
	if partOrModel:IsA("Model") then
		modelCFrame = partOrModel:GetModelCFrame()
		modelSize = partOrModel:GetModelSize()
	else
		modelCFrame = partOrModel.CFrame
		modelSize = partOrModel.Size
	end

	local mouseRayStart = modelCFrame:pointToObjectSpace(rayStart)
	local mouseRayEnd = modelCFrame:pointToObjectSpace(rayEnd)
	local mouseSlope = mouseRayEnd - mouseRayStart

	local xPositive = 1
	local yPositive = 1
	local zPositive = 1
	if mouseSlope.X > 0 then xPositive = -1 end
	if mouseSlope.Y > 0 then yPositive = -1 end
	if mouseSlope.Z > 0 then zPositive = -1 end

	-- find which surface the transformed mouse ray hits (using modelSize):
	local xHitTime = calcRayHitTime(mouseRayStart.X, mouseSlope.X, modelSize.X/2 * xPositive)
	local yHitTime = calcRayHitTime(mouseRayStart.Y, mouseSlope.Y, modelSize.Y/2 * yPositive)
	local zHitTime = calcRayHitTime(mouseRayStart.Z, mouseSlope.Z, modelSize.Z/2 * zPositive)

	local hitFace = 0

	--if xHitTime >= 0 and yHitTime >= 0 and zHitTime >= 0 then
	if xHitTime > yHitTime then
		if xHitTime > zHitTime then
			-- xFace is hit
			hitFace = 1*xPositive
		else
			-- zFace is hit
			hitFace = 3*zPositive
		end
	else
		if yHitTime > zHitTime then
			-- yFace is hit
			hitFace = 2*yPositive
		else
			-- zFace is hit
			hitFace = 3*zPositive
		end
	end

	return hitFace
end

local function getBoundingBox2(partOrModel)

	-- for models, the bounding box is defined as the minimum and maximum individual part bounding boxes
	-- relative to the first part's coordinate frame.
	local minVec = Vector3.new(math.huge, math.huge, math.huge)
	local maxVec = Vector3.new(-math.huge, -math.huge, -math.huge)

	if partOrModel:IsA("Terrain") then
		minVec = Vector3.new(-2, -2, -2)
		maxVec = Vector3.new(2, 2, 2)
	elseif partOrModel:IsA("BasePart") then
		minVec = -0.5 * partOrModel.Size
		maxVec = -minVec
	else
		maxVec = partOrModel:GetModelSize()*0.5
		minVec = -maxVec
	end

	-- Adjust bounding box to reflect what the model or part author wants in  terms of justification
	local justifyValue = partOrModel:FindFirstChild("Justification")
	if justifyValue ~= nil then
		-- find the multiple of 4 that contains the model
		local justify = justifyValue.Value
		local two = Vector3.new(2, 2, 2)
		local actualBox = maxVec - minVec - Vector3.new(0.01, 0.01, 0.01)
		local containingGridBox = Vector3.new(4 * math.ceil(actualBox.x/4), 4 * math.ceil(actualBox.y/4), 4 * math.ceil(actualBox.z/4))
		local adjustment = containingGridBox - actualBox
		minVec = minVec - 0.5 * adjustment * justify
		maxVec = maxVec + 0.5 * adjustment * (two - justify)
	end

	return minVec, maxVec
end

local function getBoundingBoxInWorldCoordinates(partOrModel)
	local minVec = Vector3.new(math.huge, math.huge, math.huge)
	local maxVec = Vector3.new(-math.huge, -math.huge, -math.huge)

	if partOrModel:IsA("BasePart") and not partOrModel:IsA("Terrain") then
		local vec1 = partOrModel.CFrame:pointToWorldSpace(-0.5 * partOrModel.Size)
		local vec2 = partOrModel.CFrame:pointToWorldSpace(0.5 * partOrModel.Size)
		minVec = Vector3.new(math.min(vec1.X, vec2.X), math.min(vec1.Y, vec2.Y), math.min(vec1.Z, vec2.Z))
		maxVec = Vector3.new(math.max(vec1.X, vec2.X), math.max(vec1.Y, vec2.Y), math.max(vec1.Z, vec2.Z))
	elseif partOrModel:IsA("Terrain") then
		-- we shouldn't have to deal with this case
		--minVec = Vector3.new(-2, -2, -2)
		--maxVec = Vector3.new(2, 2, 2)
	else
		local vec1 = partOrModel:GetModelCFrame():pointToWorldSpace(-0.5 * partOrModel:GetModelSize())
		local vec2 = partOrModel:GetModelCFrame():pointToWorldSpace(0.5 * partOrModel:GetModelSize())
		minVec = Vector3.new(math.min(vec1.X, vec2.X), math.min(vec1.Y, vec2.Y), math.min(vec1.Z, vec2.Z))
		maxVec = Vector3.new(math.max(vec1.X, vec2.X), math.max(vec1.Y, vec2.Y), math.max(vec1.Z, vec2.Z))
	end

	return minVec, maxVec
end

local function getTargetPartBoundingBox(targetPart)
	if targetPart.Parent:FindFirstChild("RobloxModel") ~= nil then
		return getBoundingBox2(targetPart.Parent)
	else
		return getBoundingBox2(targetPart)
	end
end

local function getMouseTargetCFrame(targetPart)
	if targetPart.Parent:FindFirstChild("RobloxModel") ~= nil then
		if targetPart.Parent:IsA("Tool") then return targetPart.Parent.Handle.CFrame
		else return targetPart.Parent:GetModelCFrame() end
	else
		return targetPart.CFrame
	end
end

local function isBlocker(part) -- returns whether or not we want to cancel the stamp because we're blocked by this part
	if not part then return false end
	if not part.Parent then return false end
	if part:FindFirstChild("Humanoid") then return false end
	if part:FindFirstChild("RobloxStamper") or part:FindFirstChild("RobloxModel") then return true end
	if part:IsA("Part") and not part.CanCollide then return false end
	if part == game:GetService("Lighting") then return false end
	return isBlocker(part.Parent)
end
