collision-2d

There are many javascript collision routines and libraries for 2d. None satisifed all of these criteria:

• consistent API interface
• doesn't generate memory garbage
• consistent vector/matrix/line representation
• is data-oriented
• is purely functional
• collisions only - no gravity, rigid body handling, or complex solvers
• pure es modules

so here we are!

Note: If you're looking for higher-level 2d collision handling routine for ellipsoids vs line segments, check out https://github.com/mreinstein/collide-and-slide-2d

Testing

All tests are in a folder unsurprisingly named test/. You can invoke any of them like this:

deno run test/<testname>.js

These tests will print nothing and return an exit code of 0 on success, or they'll bitch to stdout when they fail.

available collision checks

aabb-aabb overlap

const collided = aabbAABBOverlap(aabb, aabb2, contact)

aabb-aabb contain

// true when aabb1 fully contains aabb2 (2 is fully inside the bounds of 1)
const contains = aabbAABBContain(aabb1, aabb2)

aabb-aabb sweep 1

const collided = aabbAABBSweep1(aabb, aabb2, delta, contact)

aabb-aabb sweep 2

const collided = aabbAABBSweep2(aabb, delta, aabb2, delta2, contact)

aabb-segment sweep

const collided = aabbSegmentSweep(line, aabb, delta, contact)

aabb-segments sweep-indexed

const collided = aabbSegmentsSweep1Indexed(segments, indices, segmentCount, aabb, delta, contact)

if there is a collision, contact.collider will be an integer indicating the index of which segment in the segments array collided.

aabb-point overlap

const collided = aabbPointOverlap(aabb, point, contact)

aabb-segment overlap

const collided = aabbSegmentOverlap(aabb, pos, delta, paddingX, paddingY, contact)

ray-plane-distance

import plane from 'plane.js'


const p = plane.create()
plane.fromPlane(p, planeOrigin, planeNormal)
const distance = plane.rayDistance(p, rayOrigin, rayVector)

ray-sphere overlap

import raySphereOverlap from 'ray-sphere-overlap.js'


// declare 2 points that lie on an infinite ray
const p1 = [ 100, 100 ]
const p2 = [ 200, 100 ]

const sphereCenter: [ 250, 100 ]
const sphereRadius: 50
const contact = { mu1: NaN, mu2: NaN }
const overlaps = raySphereOverlap(p1, p2, sphereCenter, sphereRadius, contact)

// mu1 and mu2 are the points along the line segment from p1 to p2 where the sphere intersection occurs:
//   intersection1 = p1 + contact.mu1  * (p2 - p1)
//   intersection2 = p1 + contact.mu2  * (p2 - p1)
if (overlaps) {
    console.log('sphere intersection time 1:', contact.mu1)
    console.log('sphere intersection time 2', contact.mu2)
}

segment-sphere overlap

import segmentSphereOverlap from 'segment-sphere-overlap.js'


// declare 2 points that lie on a line segment
const p1 = [ 100, 100 ]
const p2 = [ 200, 100 ]

const sphereCenter: [ 250, 100 ]
const sphereRadius: 50
const contact = { intersectionCount: 0, mu1: NaN, mu2: NaN }
const overlaps = segmentSphereOverlap(p1, p2, sphereCenter, sphereRadius, contact)

// mu1 and mu2 are the points along the line segment from p1 to p2 where the sphere intersection occurs:
//   intersection1 = p1 + contact.mu1  * (p2 - p1)
//   intersection2 = p1 + contact.mu2  * (p2 - p1)
if (overlaps) {
    // the segment interesects the sphere, intersectionCount is 1 or 2
    // either mu1 or mu2 will be NaN if there's not 2 intersections
    console.log('intersection count:', contact.intersectionCount)
    console.log('sphere intersection time 1:', contact.mu1)
    console.log('sphere intersection time 2', contact.mu2)
} else {
    // no overlap, contact.intersectionCount is 0
}

segment-normal

const normal = segmentNormal(vec2.create(), pos1, pos2)

segment-point-overlap

const collided = segmentPointOverlap(p, segPoint0, segPoint1) // true or false

segment-segment-overlap

const intersectionPoint = vec2.create()
if (segmentSegmentOverlap(seg1Point1, seg1Point2, seg2Point1, seg2Point2, intersectionPoint)) {
    // if we get here, intersectionPoint is filled in with where the 2 segments overlap
}

segments-segment-overlap

const collided = segmentsSegmentOverlap(segments, start, delta, contact)

if there is a collision, contact.collider will be an integer indicating the index of which segment in the segments array collided.

segments-segment-overlap-indexed

const segs = [
    [ p0, p1 ],
    [ p2, p3 ],
    [ p4, p5 ]
]
const indices = [ 0, 2 ]  // indices into the segs array

const segmentCount = 2    // numer of indices to include. only run the segmentsSegment intersection tests on [ p0, p1 ] and [ p4, p5]

const collided = segmentsSegmentOverlapIndexed(segments, indices, segmentCount, start, delta, contact)

if there is a collision, contact.collider will be an integer indicating the index of which segment in the segments array collided.

segments-sphere-sweep 1

const collided = segmentsSphereSweep1(segments, position, radius, delta, contact)

if there is a collision, contact.collider will be an integer indicating the index of which segment in the segments array collided.

segments-sphere-sweep-1-indexed

const segs = [
    [ p0, p1 ],
    [ p2, p3 ],
    [ p4, p5 ]
]
const indices = [ 0, 2 ]  // indices into the segs array

const segmentCount = 2    // only run the segmentsSphereSweep tests on [ p0, p1 ] and [ p4, p5 ]

const collided = segmentsSphereSweep1(segments, indices, segmentCount, position, radius, delta, contact)

if there is a collision, contact.collider will be an integer indicating the index of which segment in the segments array collided.

sphere-sphere-overlap

const collided = sphereSphereOverlap(centerA, radiusA, centerB, radiusB, contact) // collided is true or false

if there is a collision, contact.delta is a vector that can be added to sphere A’s position to move them into a non-colliding state. contact.position is the point of contact of these 2 spheres

Note: contact is an optional parameter. if you only want to determine if the 2 spheres overlap, omit contact which will be faster.

sphere-sphere-sweep2

const collided = sphereSphereSweep2(radiusA, A0, A1, radiusB, B0, B1, contact)

• A0 is the previous position of sphere A
• A1 is the new position of sphere A
• B0 is the previous position of sphere B
• B1 is the new position of sphere B

If there is a collision contact.position will contain the point where the collision occurred. contact.time has the normalized time where the collision happened.

cone-point-overlap

const collided = conePointOverlap(conePosition, coneRotation, coneFieldOfView, coneMinDistance, coneMaxDistance, point) // collided is true or false

tri-point-overlap

const collided = triPointOverlap(v0, v1, v2, point) // collided is true or false

entities

The collision routines all use these entity definitions

point

a point is a 2d vector, which is represented as an array with 2 values:

const position = [ 200, 150 ] // x: 200, y: 150

We use the fantastic gl-matrix vec2 for representing these.

aabb

an axially aligned bounding box

const aabb = {
    position: [ 200, 100 ],  // center point of the AABB
    width: 50,
    height: 50
}

segment

a line segment consists of 2 points

const segment = [
    [ 0, 0 ],   // starting point of line
    [ 100, 0 ]  // ending point of line
]

plane

a 2d plane

{
    origin: vec2.create(),
    normal: vec2.create(),
    D: 0,
}

contact

The data structure populated when a collision occurs

{
    // for segments-segment-overlap and segments-sphere-sweep1 this is set to the index
    // in the array of line segments passed into the collision routine
    // for all other routines, collider is a reference to the colliding object itself
    collider : null,

    position : [ 0, 0 ], // the exact position of the collision
    delta    : [ 0, 0 ], // a vector that can be applied to get out of the colliding state
    normal   : [ 0, 0 ], // the collision normal vector
    time     : 0         // the time of the collision, from 0..1
}

conventions

All collision checking functions return a boolean indicating if there was a collision. They also accept an optional contact argument, which gets filled in if there is an actual collision.

"sweep" tests indicate at least 1 of the objects is moving. the number indicates how many objects are moving. e.g., aabb-aabb-sweep2 means we are comparing 2 aabbs, both of which are moving.

"overlap" tests don't take movement into account, and this is a static check to see if the 2 entities overlap.

plural forms imply a collection. e.g., segments-segment-ovelap checks one line segment against a set of line segments. If there is more than one collision, the closest collision is set in the contact argument.

"indexed" tests are the same as their non-indexed forms, except they take in an array of segment indices to use. These are nice in that you can avoid having to build large arrays of line segments every frame, if you have things like dynamic line segments (platforms) or have a spatial culling algorithm that selects line segments to include.

credits

Most of these collision checks were adapted from existing open source modules:

• https://github.com/noonat/intersect
• The diagrams are modified from noonat: https://noonat.github.io/intersect/
• https://github.com/kevzettler/gl-swept-sphere-triangle
• https://gist.github.com/toji/2802287
• segment-point-overlap from https://gist.github.com/mattdesl/47412d930dcd8cd765c871a65532ffac
• segment-segment overlap from https://github.com/tmpvar/segseg
• http://www.gamasutra.com/view/feature/131790/simple_intersection_tests_for_games.php
• http://geomalgorithms.com/a07-_distance.html#dist3D_Segment_to_Segment
• https://observablehq.com/@kelleyvanevert/2d-point-in-triangle-test
• aabb-segment sweep from https://gamedev.stackexchange.com/questions/29479/swept-aabb-vs-line-segment-2d