Author Topic: OBB vs OBB collisions using Separate Axis Theorem  (Read 231 times)

I wrote some code to detect intersections between OBBs. I can think of a couple use cases for this, mainly that triggers in Blockland will always detect objects within it's AABB even if you have set up it's polyhedron attribute correctly, you could use this to get more accuracy. I'm fairly confident it works... though it may not be very intuitive or efficient. Maybe someone with experience in this area can roast my code or make it explode

You can also use this to detect OBB vs Segment/Point/Plane intersections by reducing relevant dimensions of the OBB to 0, but there are probably more efficient ways to do this





Green lines indicate that no overlap was detected when the OBBs were projected onto that axis. Red line indicates an overlap. In order for OBBs to be intersecting, there must be overlap on every axis.

Code: [Select]
$R_SAT_DebugLines = true;

function vectorClosestPoint(%vector, %startPoint, %point)
{
%vN = vectorNormalize(%vector);
%v2 = vectorSub(%point, %startPoint);
%dot = vectorDot(%vN, vectorNormalize(%v2));

%closestPoint = vectorAdd(%startPoint, vectorScale(%vN, %dot * vectorLen(%v2)));
return %closestPoint;
}

function OBBIntersectVector(%center, %vector, %OBBPointsA, %OBBPointsB)
{
%vector = vectorNormalize(%vector);

%minAlongA = "";
%maxAlongA = "";
%minAlongB = "";
%maxAlongB = "";

for(%i = 0; %i < 8; %i++)
{
%a = %i * 3;

%vertex = getWords(%OBBPointsA, %a, %a + 2);
%projected = vectorClosestPoint( %vector, %center, %vertex );
%OBBProjectedA = %OBBProjectedA @ %projected SPC "";

%dot = vectorDot(%vertex, %vector);

if(%minAlongA $= "" || %dot < %minAlongA)
%minAlongA = %dot;

if(%maxAlongA $= "" || %dot > %maxAlongA)
%maxAlongA = %dot;
}


for(%i = 0; %i < 8; %i++)
{
%a = %i * 3;

%vertex = getWords(%OBBPointsB, %a, %a + 2);
%projected = vectorClosestPoint( %vector, %center, %vertex );
%OBBProjectedB = %OBBProjectedB @ %projected SPC "";

%dot = vectorDot(%vertex, %vector);

if(%minAlongB $= "" || %dot < %minAlongB)
%minAlongB = %dot;

if(%maxAlongB $= "" || %dot > %maxAlongB)
%maxAlongB = %dot;
}



%overlapMax = getMax(%minAlongA, %minAlongB);
%overlapMin = getMin(%maxAlongA, %maxAlongB);

if($R_SAT_DebugLines)
{
if(%overlapMax <= %overlapMin)
{
drawLine(%center, vectorAdd(%center, %vector), "1 0 0 1", 0.05);
}
else
{
drawLine(%center, vectorAdd(%center, %vector), "0 1 0 1", 0.05);
}
}

return %overlapMax <= %overlapMin;
}

$obbACenter = "5 5 5";
function OBBIntersectTest()
{
%obbACenter = $obbACenter;

%obbAForward = "1 1 1";
%obbARight = vectorCross(%obbAForward, "0 0 1");
%obbAUp = vectorCross(%obbARight, %obbAForward);

%obbAF = 3;
%obbAR = 5;
%obbAU = 4;
%obbAColor = "1 0 0 1";

%obbBCenter = LocalClientConnection.player.getHackPosition();
%obbBForward = LocalClientConnection.player.getForwardVector();
%obbBRight = vectorCross(%obbBForward, "0 0 1");
%obbBUp = vectorCross(%obbBRight, %obbBForward);
%obbBF = 5 * 0.25;
%obbBR = 5 * 0.25;
%obbBU = 10.6 * 0.25;
%obbBColor = "0 0 1 1";

%pointsA = OBB(%obbACenter, %obbAForward, %obbARight, %obbAUp, %obbAF, %obbAR, %obbAU, %obbAColor);
%pointsB = OBB(%obbBCenter, %obbBForward, %obbBRight, %obbBUp, %obbBF, %obbBR, %obbBU, %obbBColor);

%intersectAU = OBBIntersectVector(%obbACenter, %obbAUp, %pointsA, %pointsB);
%intersectAR = OBBIntersectVector(%obbACenter, %obbARight, %pointsA, %pointsB);
%intersectAF = OBBIntersectVector(%obbACenter, %obbAForward, %pointsA, %pointsB);

%intersectBU = OBBIntersectVector(%obbBCenter, %obbBUp, %pointsA, %pointsB);
%intersectBR = OBBIntersectVector(%obbBCenter, %obbBRight, %pointsA, %pointsB);
%intersectBF = OBBIntersectVector(%obbBCenter, %obbBForward, %pointsA, %pointsB);

return
(
%intersectAU && %intersectAF && %intersectAR &&
%intersectBU && %intersectBF && %intersectBR
);
}

function quadrilateralFromPolyhedron(%polyhedron, %corner, %center, %color)
{
if(%color $= "") %color = getRandom() SPC getRandom() SPC getRandom() SPC 1;

%forwardVector = getWords(%polyhedron, 3, 5);
%rightVector = getWords(%polyhedron, 6, 8);
%upVector = getWords(%polyhedron, 9, 11);

%c0 = %corner; // Backward Bottom Left
%c1 = vectorAdd(%c0, %forwardVector); // Forward Bottom Left
%c2 = vectorAdd(%c0, %rightVector); // Backward Bottom Right
%c3 = vectorAdd(%c2, %forwardVector); // Forward Bottom Right

%c4 = vectorAdd(%c0, %upVector); // Backward Top Left
%c5 = vectorAdd(%c1, %upVector); // Forward Top Left
%c6 = vectorAdd(%c2, %upVector); // Backward Top Right
%c7 = vectorAdd(%c3, %upVector); // Forward Top Right

//for(%i = 0; %i < 8; %i++) drawLine(%c[%i], %c[%i], "1 0 0 1", 0.1);

if($R_SAT_DebugLines)
{
// top rectangle
drawLine(%c4, %c5, %color, 0.05);
drawLine(%c6, %c7, %color, 0.05);
drawLine(%c5, %c7, %color, 0.05);
drawLine(%c4, %c6, %color, 0.05);

// bottom rectangle
drawLine(%c0, %c1, %color, 0.05);
drawLine(%c2, %c3, %color, 0.05);
drawLine(%c0, %c2, %color, 0.05);
drawLine(%c1, %c3, %color, 0.05);

// verticals
drawLine(%c5, %c1, %color, 0.05);
drawLine(%c7, %c3, %color, 0.05);
drawLine(%c6, %c2, %color, 0.05);
drawLine(%c0, %c4, %color, 0.05);
}


%obbPoints = %c0 SPC %c1 SPC %c2 SPC %c3 SPC %c4 SPC %c5 SPC %c6 SPC %c7;
return %obbPoints;
}

function OBB_forward(%center, %forwardVector, %f, %r, %u, %color)
{
%forwardVector = vectorNormalize(%forwardVector);
%rightVector = vectorCross(%forwardVector, "0 0 1");
%upVector = vectorCross(%rightVector, %forwardVector);
return OBB(%center, %forwardVector, %rightVector, %upVector, %f, %r, %u, %color);
}

function OBB(%center, %forwardVector, %rightVector, %upVector, %f, %r, %u, %color)
{
if(%color $= "") %color = getRandom() SPC getRandom() SPC getRandom() SPC 1;

%forwardVector = vectorNormalize(%forwardVector);
%rightVector = vectorNormalize(%rightVector);
%upVector = vectorNormalize(%upVector);

%hf = %f * 0.5;
%hr = %r * 0.5;
%hu = %u * 0.5;

%corner = vectorAdd(%center, vectorScale(%forwardVector, -%hf));
%corner = vectorAdd(%corner, vectorScale(%rightVector, -%hr));
%corner = vectorAdd(%corner, vectorScale(%upVector, -%hu));

return quadrilateralFromPolyhedron("0 0 0" SPC vectorScale(%forwardVector, %f) SPC vectorScale(%rightVector, %r) SPC vectorScale(%upVector, %u), %corner, %center, %color);
}

OBBIntersectTest() will create a rotated OBB near the origin, and a second OBB around the player's bounding box, and will return whether or not the OBBs intersected.
« Last Edit: October 09, 2020, 01:27:41 PM by Crook »

The beats... The bombs...