3D Collision detection

Quenty suggested the name change

[size=5]Hey![/size] I spent some time coming up with a box collision function, and decided to use it to make rotatable region3s! My region module and ROBLOX’s Region3’s have the same functionality, except mine are rotatable, and you can do more. lol. (They’re also a fair bit slower, but then again, what do you expect?) You can grab it there:

Do yourself a favor and don’t read it k?

[size=5]Example usage[/size]

local Region=require(script.Parent.ModuleScript)

--Makes a new Region from Part
local r=Region.FromPart(game.Workspace.Part)

--Gets all parts in the Region except for Part
local Parts=r:Cast(game.Workspace.Part)

for i=1,#Parts do
	print(Parts[i])
end

--Tells you if OtherPart is intersecting Region r
local isPartInRegion=r:CastPart(game.Workspace.OtherPart)
print(isPartInRegion)

[size=5]Documentation[/size]
By AxisAngle, (Trey Reynolds)
Documentation

Region constructors:
Region Region.new(CFrame RegionCFrame, Vector3 RegionSize)
>Returns a new Region object

Region Region.FromPart(Instance Part)
	>Returns a new Region objects

Region methods:
table Region:Cast([Instance or table Ignore])
>Returns all parts in the Region, ignoring the Ignore

bool Region:CastPart(Instance Part)
	>Returns true if Part is within Region, false otherwise

table Region:CastParts(table Parts)
	>Returns a table of all parts within the region

bool Region:CastPoint(Vector3 Point)
	>Returns true if Point intersects Region, false otherwise

bool Region:CastSphere(Vector3 SphereCenter, number SphereRadius)
	>Returns true if Sphere intersects Region, false otherwise

bool Region:CastBox(CFrame BoxCFrame, Vector3 BoxSize)
	>Returns true if Box intersects Region, false otherwise

Region properties: (Regions are mutable)
CFrame CFrame
Vector3 Size
Region3 Region3

Region functions:
Region3 Region.Region3BoundingBox(CFrame BoxCFrame,Vector3 BoxSize)
>Returns the enclosing boundingbox of Box

table Region.FindAllPartsInRegion3(Region3 Region3, [Ignore])
	>Returns all parts within a Region3 of any size

bool Region.BoxPointCollision(CFrame BoxCFrame, Vector3 BoxSize, Vector3 Point)
	>Returns true if the Point is intersecting the Box, false otherwise

bool Region.BoxSphereCollision(CFrame BoxCFrame, Vector3 BoxSize, Vector3 SphereCenter, number SphereRadius)
	>Returns true if the Sphere is intersecting the Box, false otherwise

bool Region.BoxCollision(CFrame Box0CFrame, Vector3 Box0Size, CFrame Box1CFrame, Vector3 Box1Size, [bool AssumeTrue])
	>Returns true if the boxes are intersecting, false otherwise
	If AssumeTrue is left blank, it does the full check to see if Box0 is intersecting Box1
	If AssumeTrue is true, it skips the heavy check and assumes that any part that could possibly be in the Region is
	If AssumeTrue is false, it skips the heavy check and assumes that any part that could possible be outside the Region is
2 Likes

I think people may be more interested if they can learn from it, maybe add a bit of documentation on the code if you can so we can see what you are doing. :slight_smile:

(maybe not all the details, but at least explain your general algorithm or something)

I think people may be more interested if they can learn from it, maybe add a bit of documentation on the code if you can so we can see what you are doing. :slight_smile:

(maybe not all the details, but at least explain your general algorithm or something)[/quote]

What? Documented Trey code? Learning from Trey code? You have much to learn.

[quote] [quote=“AxisAngle” post=149024]
Do yourself a favor and don’t read it k?
[/quote]

I think people may be more interested if they can learn from it, maybe add a bit of documentation on the code if you can so we can see what you are doing. :slight_smile:

(maybe not all the details, but at least explain your general algorithm or something)[/quote]

What? Documented Trey code? Learning from Trey code? You have much to learn.[/quote]

Or maybe they have much to learn :wink:

[quote] [quote=“buildthomas” post=149043][quote=“AxisAngle” post=149024]
Do yourself a favor and don’t read it k?
[/quote]

I think people may be more interested if they can learn from it, maybe add a bit of documentation on the code if you can so we can see what you are doing. :slight_smile:

(maybe not all the details, but at least explain your general algorithm or something)[/quote]

What? Documented Trey code? Learning from Trey code? You have much to learn.[/quote]

Or maybe they have much to learn ;)[/quote]

The only thing that isn’t readable is the box collision function.
“I ran out of local variables so I had to redo everything so that I could reuse the names”
So if I made it readable, then it would literally not work. Also it’s so optimized (though I feel I can do a lot better with some smarter case checking), that the math literally only means “Box collision check” now. It’s not even able to be broken down into its smaller raycast parts anymore. But, then again, that’s the price that you pay for only needing 18 operations max per raycast.

[size=4]If you really want to know, just ask me personally.[/size] It’s really pretty easy, just hard to put together.

1: Get the inner radii of the boxes, min(SizeX,SizeY,SizeZ)/2
2: Get the closest point on Box0 to the center of Box1 and vice versa.
3: If the distance between the closest point on Box0 to the center of Box1 is less than the inner radius of Box1, OR the distance between the closest point on Box1 to the center of Box0 is less than the inner radius of Box0, then you know for certain that they are touching
4: Else, get the outer radii
5: If the distance between the closest point on Box0 to the center of Box1 is greater than the outer radius of Box1, OR the distance between the closest point on Box1 to the center of Box0 is greater than the outer radius of Box0, then you know for certain that they are not touching
6: Else, if one of the corners of Box0 is within Box1, then they are definitely touching.
7: If one of the edges of Box1 intersects a plane of box0, then they are definitely touching.
8: Otherwise, they are definitely not touching.

It’s pretty brute force, but it covers all cases.

[quote]
1: Get the inner radii of the boxes, min(SizeX,SizeY,SizeZ)/2
2: Get the closest point on Box0 to the center of Box1 and vice versa.
3: If the distance between the closest point on Box0 to the center of Box1 is less than the inner radius of Box1, OR the distance between the closest point on Box1 to the center of Box0 is less than the inner radius of Box0, then you know for certain that they are touching
4: Else, get the outer radii
5: If the distance between the closest point on Box0 to the center of Box1 is greater than the outer radius of Box1, OR the distance between the closest point on Box1 to the center of Box0 is greater than the outer radius of Box0, then you know for certain that they are not touching
6: Else, if one of the corners of Box0 is within Box1, then they are definitely touching.
7: If one of the edges of Box1 intersects a plane of box0, then they are definitely touching.
8: Otherwise, they are definitely not touching. [/quote]

Sounds cool, I’m checking the code out more closely later. And that’s all the explanation I meant, just gives a broad overview of your code and makes it easier to get into IMO

More. I expect so much more from you. :frowning:

[size=1]jk obviously[/size]

Anyhow, I’ve added this page to my list of “useful RbxDev code” bookmarks. The folder is swelling :swag:

You can just take the model and have it 4life.

Gonna bump this here.

WAAAAT…?

repeat
	local Parts=...
	...
until #Parts<100;

I tried minifying the code with my minifier… and at first I thought your code was broken. But it turns out that body local declaration lifetimes totally extend into the until clause condition, and it’s my minifier that’s broken!

Never seen anyone do that before even where it would have made sense, and the same thing does not work in C-family languages, so I assumed it would not in Lua. That’s the first thing that I’ve learned about Lua in quite a while.

Did anyone else know that that would work in Lua before reading this code?

EDIT: Yup, there it is, right there. I can’t believe I’ve never seen that before:

This is indeed a sure sign the apocalypse is coming.

Huh. I attempted this almost a year ago, and I had a prototype (only around 80 lines too) in a couple of hours. Unfortunately, it would only work if the parts being checked were not rotated, and it took around 0.06 seconds to check 512 parts (not optimized though). I’m sure there is a way around that, but I don’t really want to revisit it. I can barely remember how I managed to do it, and I’m pretty sure I never fully understood the topic in the first place. It’s apparently based on the Separating Axis Theorem for Oriented Bounding Boxes

Here’s the code I used, if you’re interested in glancing at it.

--[[
Written by RobustPhysics


Create a region by using Region.new(CFrame cframe, Vector3 size)
Get a table of parts inside a region with GetPartsInRegion(Region region, Instance group)


EXAMPLE:
~~~~~~~~~~~~
local p = workspace.Part
p.Transparency = 1
local region = Region.new(p.CFrame,p.Size)
local parts = GetPartsInRegion(region)

for _,v in pairs(parts) do
	v:Destroy()
end
~~~~~~~~~~~~

Extra information: http://www.jkh.me/files/tutorials/Separating%20Axis%20Theorem%20for%20Oriented%20Bounding%20Boxes.pdf
]]


local abs = math.abs
local Region = {}
Region.__index = Region

function Region.new(cframe,size)
	local self = setmetatable({},Region)
	self.CFrame = cframe or CFrame.new()
	self.Size = size or Vector3.new()
	return self
end

--[[
	PartInRegion(Instance part, Region region)
	Returns true if part is inside the defined region.
	Should work just fine if you substitute the second argument for another part.
--]]

function PartInRegion(p1,p2)
	local _,_,_,ax1,ax2,ax3,ay1,ay2,ay3,az1,az2,az3 = p1.CFrame:components()
	local cf2 = p2.CFrame:toObjectSpace(p1.CFrame)
	local _,_,_,bx1,bx2,bx3,by1,by2,by3,bz1,bz2,bz3 = cf2:components()
	local Ax = Vector3.new(ax1,ax2,ax3)
	local Ay = Vector3.new(ay1,ay2,ay3)
	local Az = Vector3.new(az1,az2,az3)
	local Bx = Vector3.new(bx1,bx2,bx3)
	local By = Vector3.new(by1,by2,by3)
	local Bz = Vector3.new(bz1,bz2,bz3)
	local hs1 = p1.Size/2
	local hs2 = p2.Size/2
	local Wa,Ha,Da = hs1.X,hs1.Y,hs1.Z
	local Wb,Hb,Db = hs2.X,hs2.Y,hs2.Z
	local T = p2.CFrame.p-p1.CFrame.p
	local planes = {
		Ax,Ay,Az,
		Bx,By,Bz,
		Ax:Cross(Bx),
		Ax:Cross(By),
		Ax:Cross(Bz),
		Ay:Cross(Bx),
		Ay:Cross(By),
		Ay:Cross(Bz),
		Az:Cross(Bx),
		Az:Cross(By),
		Az:Cross(Bz)
	}
	for _,L in pairs(planes) do
		if abs(T:Dot(L)) > abs((Wa*Ax):Dot(L)) + abs((Ha*Ay):Dot(L)) + abs((Da*Az):Dot(L))+
			abs((Wb*Bx):Dot(L)) + abs((Hb*By):Dot(L)) + abs((Db*Bz):Dot(L)) then
			return false
		end
	end
	return true
end

--[[
	GetParts() will return a table of parts located inside of model.
	It's recursive, and only the first argument is required.
--]]

function GetParts(model,tab) 
	tab = tab or {}
	for _,v in pairs(model:GetChildren()) do
		if v:IsA("BasePart") then
			table.insert(tab,v)
		else
			GetParts(v,tab)
		end
	end
	return tab
end

--[[
	GetPartsInRegion(Region region, Instance model)
	Returns a table value of every part inside of 'model' that is colliding with 'region'
	The first argument can be a part, and it should still work just as fine.
--]]

function GetPartsInRegion(region,model)
	model = model or workspace
	local t1 = tick()
	local parts = GetParts(model)
	print("Time to get parts: "..tick()-t1)
	print("Number of parts: "..#parts)
	local collided = {}
	t1 = tick()
	for _,v in pairs(parts) do
		if PartInRegion(v,region) then
			table.insert(collided,v)
		end
	end
	print("Time to check collisions: "..tick()-t1)
	return collided
end

Also, I noticed a small problem with yours. It’s not perfectly accurate.

The transparent gray part isn’t touching, but it was still made transparent by the script.

Before (2 studs away with 5x5x5 parts):

After:

Send me the place. I did a lot of testing on it and never found any problems with it. It’s based on raycasting, so it should be exact.

Sorry for the delay! Just open the place up and press play.

Yeah, I’ve used it for some things

for _, node in pairs(path) do
	local eta = npcLib.EstimatedPathTime(torso.Position, node.Position, hum.WalkSpeed)
	local timeWalked = 0
	repeat
		walkTo(node.Position)
		rotateTowards(node.Position)
		local act = wait(1/10)
		timeWalked = timeWalked + act
		local newTarget = chooseTarget()
	until (timeWalked > eta) or (newTarget ~= target and newTarget ~= nil)
end