separating-axis-test
Test for the intersection of 2 convex polytopes in 2d or 3d.
If an intersection exists, return the minimum translation vector.
(also called the separating axis theorem or the hyperplane separation theorem)
example
The examples below use axis-aligned boxes, but oriented boxes or any other convex polytope will work too.
The examples below show nested coordinates but flat arrays work too.
2d example
2d example with two axis-aligned boxes:
var sat2d =var A =separatingAxes:0110positions: 01111000var B =separatingAxes:0110positions: -0605040504-05-06-05var out = 00console // [0.4,0]
3d example
var sat3d =var A =separatingAxes: 001010100positions:000010110100001011111101var B =separatingAxes: 001010100positions:-050400504005-060-05-060-050410504105-061-05-061var out = 000console // [0,0.4,0]
separating axes
To calculate the separating axes:
In 2d you can loop over each line segment and calculate the edge normal:
var vec2 =var points = 00080506-02var separatingAxes =for var i = 0; i < pointslength; i++var p0 = pointsivar p1 = pointsi+1%pointslengthvar edge = p11 - p01 p00 - p10vec2separatingAxesconsole
In 3d you can loop over each face and compute the face normal:
var vec3 =var points = 010100-100001 // triangular pyramidvar cells = 012023031123var tmp0 = 000 tmp1 = 000var separatingAxes =for var i = 0; i < cellslength; i++var p0 = pointscellsi0var p1 = pointscellsi1var p2 = pointscellsi2vec3vec3var N = 000vec3vec3separatingAxesconsole
If separating axes are flipped versions of each other you can omit one to spare
some calculations. For example if you have both [1,0]
and [-1,0]
, you can
drop one of them.
api
var sat2d = require('separating-axis-test/2d')
var sat3d = require('separating-axis-test/3d')
var {sat2d,sat3d} = require('separating-axis-test')
sat2d(out, A, B)
Calculate the intersection of convex polygons A
and B
in 2d, storing the
minimum translation vector in out
if the shapes intersect.
Each polygon A
and B
must have these fields:
positions
- an array of coordinates which describe the convex hullseparatingAxes
- an array of (normalized) axis normals to test
Coordinates and normals may be specified as nested ([[x0,y0],[x1,y1],...]
) or
flat ([x0,y0,x1,y1,...]
).
If there is no intersection, this function returns null.
Otherwise, it returns the minimum translation vector out
.
sat3d(out, A, B, epsilon=0.00001)
Calculate the intersection of convex polytopes A
and B
in 3d, storing the
minimum translation vector in out
if the shapes intersect.
Each polytope A
and B
must have these fields:
positions
- an array of coordinates which describe the convex hullseparatingAxes
- an array of (normalized) axis normals to test
Coordinates and normals may be specified as nested
([[x0,y0,z0],[x1,y1,z1],...]
) or flat ([x0,y0,z0,x1,y1,z1,...]
).
If there is no intersection, this function returns null.
Otherwise, it returns the minimum translation vector out
.
install
npm install separating-axis-test
license
bsd