For a pathfinder I'm building, I need the ability to test two parts for collision, that do not exist in the workspace yet. Putting them into the Workspace and waiting for a hit event would take to much time, so I rolled my own OBB-OBB collision detection program. But I'm have a problem with it. I used the SAT (Separating Axis Theorem) to test. It works by trying to find a separating plane between the two parts. To do this, you test a few normals. you can tell if two parts cross the plane by seeing if their point's projections onto the normal overlap. To find out more, search google. The code should be commented enough for you to find out the rest. The peps in SH had no idea what SAT was....
My issue is that sometimes parts that are close, but not touching, are reported as touching and rarely parts that are touching are reported at not touching.
There is two functions. part_part_collision is the main function.
local i = Vector3.new(1, 0, 0)
local j = Vector3.new(0, 1, 0)
local k = Vector3.new(0, 0, 1)
local function get_points(part)
--The rotation and position of the part
local rot = part.CFrame
local pos = part.Position
--Positions is in the center, so offset in each
--direction by half of the size.
local size = part.Size * 0.5
--The parts axises
local i = rot:vectorToWorldSpace(i)
local j = rot:vectorToWorldSpace(j)
local k = rot:vectorToWorldSpace(k)
--Scale by size
local x, y, z = size.x, size.y, size.z
--return dem points!
return {
-x*i + -y*j + -z*k + pos,
-x*i + -y*j + z*k + pos,
-x*i + y*j + -z*k + pos,
-x*i + y*j + z*k + pos,
x*i + -y*j + -z*k + pos,
x*i + -y*j + z*k + pos,
x*i + y*j + -z*k + pos,
x*i + y*j + z*k + pos,
}
end
local function part_part_collision(p1, p2)
--A list of the part's points, and their CFrames
local p1_points = get_points(p1)
local p2_points = get_points(p2)
local p1_cf = p1.CFrame
local p2_cf = p2.CFrame
--All the normals that must be tested. 3 axises from
--part1, 3 axises from part2, and the 9 cross products
--of those axises.
local n = {
p1_cf:vectorToObjectSpace(i);
p1_cf:vectorToObjectSpace(j);
p1_cf:vectorToObjectSpace(k);
p2_cf:vectorToObjectSpace(i);
p2_cf:vectorToObjectSpace(j);
p2_cf:vectorToObjectSpace(k);
}
n[7] = n[1]:Cross(n[4])
n[8] = n[1]:Cross(n[5])
n[9] = n[1]:Cross(n[6])
n[10] = n[2]:Cross(n[4])
n[11] = n[2]:Cross(n[5])
n[12] = n[2]:Cross(n[6])
n[13] = n[3]:Cross(n[4])
n[14] = n[3]:Cross(n[5])
n[15] = n[3]:Cross(n[6])
--The projection of a onto the normal is really the
--a:Dot(normal)/normal.magnitude, but sense we are
--only testing for overlap in the numorator, we drop
--the denominator of normal.magnitude for speed.
for _, normal in next, n do
--The range for part1 projections on the normal
local p1_min = p1_points[1]:Dot(normal)
local p1_max = p1_min
for i = 2, #p1_points do
local scalar = p1_points[i]:Dot(normal)
if scalar < p1_min then
p1_min = scalar
elseif scalar > p1_max then
p1_max = scalar
end
end
--The range for part2 projections on the normal
local p2_min = p2_points[2]:Dot(normal)
local p2_max = p2_min
for i = 2, #p2_points do
local scalar = p2_points[i]:Dot(normal)
if scalar < p2_min then
p2_min = scalar
elseif scalar > p2_max then
p2_max = scalar
end
end
--if the ranges don't overlap, then the parts don't intersect.
if p2_max p1_max then
return false
end
end
--There must be a collision, we haven't found a gap.
return true
end |