Ask coding questions

← Back to all posts
Polygon Triangulation With Separating Axis Theorem
h
realTronsi (912)

I'm learning the Separated Axis Theorem for 2D collisions and response. I want to support collisions with concave polygons, so I'm triangulating polygons using earcut and testing each triangle against each other.

Unfortunately, it still seems to treat concave polygons as if they were convex, for example, given the coordinates (0, 0), (0, 50), (40, 50), and (10, 40), collisions behave as if the (10, 40) point was not there, effectively making it a triangle. I checked the triangulated coordinates and they appear to be normal: [1, 0, 3, 3, 2, 1] (each number representing the index of the point).

Additionally, my SAT implementation returns false the moment it finds non-overlapping "shadows", but by checking the each of the triangles against each other, individual triangles could be non-overlapping while their parent polygon is colliding. A similar problem is also present in response, where I am grabbing the smallest overlap difference and pushing the collider back, but the smallest overlap with individual triangles might not represent the true overlap amount.

How do I fix both these issues?

Triangulation

triangulate(){
	let pvertices = [];
	for(let v of this.vertices){
		pvertices.push(v.x, v.y);
	}
	this.tpoints = earcut(pvertices); // triangulated vertices
	this.tsub = []; // triangulated polygons for collision
	for(let i = 0; i < this.tpoints.length; i+=3){
		this.tsub.push([this.vertices[this.tpoints[i]], this.vertices[this.tpoints[i+1]], this.vertices[this.tpoints[i+2]]]);
	}
}

Collision detection

let sprite1 = this;
let sprite2 = cand;

for (let sprite = 0; sprite < 2; sprite++) {
	if (sprite == 1) {
		// flip to avoid repetitive code
		sprite1 = cand;
		sprite2 = this;
	}

	for(let s = 0; s < sprite1.tsub.length; s++){
		for (let a = 0; a < sprite1.tsub[s].length; a++) {
			const b = (a + 1) % sprite1.tsub[s].length;

			// normal to sprite edge (axis projection)
			const ap = new Vector(-(sprite1.tsub[s][b].y - sprite1.tsub[s][a].y), sprite1.tsub[s][b].x - sprite1.tsub[s][a].x);

			// find min max for both sprites
			let min1, max1, min2, max2;

			for (let t of sprite1.tsub) {
				for(let p of t){
					let q = ap.dot(p);
					min1 = Math.min(min1 ?? q, q);
					max1 = Math.max(max1 ?? q, q);
					}
			}
			for (let t of sprite2.tsub) {
				for(let p of t){
					let q = ap.dot(p);
					min2 = Math.min(min2 ?? q, q);
					max2 = Math.max(max2 ?? q, q);
				}
			}

			if (!(max2 >= min1 && max1 >= min2))
				return false;
		}
	}
}

return true;
Comments
hotnewtop
Coder100 (17013)

can i give you the function i use

i didn't write it, but i use it.

Coder100 (17013)

@realTronsi

function isInPoly(x, y, poly) {
    let isIn = false;

    for (let i = 0, j = poly.length - 1; i < poly.length; j = i++) {
        let xi = poly[i].x, yi = poly[i].y;
        let xj = poly[j].x, yj = poly[j].y;
        let intersect = yi > y !== yj > y && x < (xj - xi) * (y - yi) / (yj - yi) + xi;
        if (intersect) isIn = !isIn;
    }

    return isIn;
}
 
function isBetween(c, a, b) {
    return (a - c) * (b - c) <= 0;
}
 
function overlap(a, b, c, d) {
    return isBetween(c < d ? c : d, a, b) || isBetween(a < b ? a : b, c, d);
}
 
function polyPolyCol(poly1, poly2) {
    let polys = [
        poly1,
        poly2
    ];

    function project(poly, axis) {
        let mn = Infinity;
        let mx = -Infinity;
        for (let i = 0; i < poly.length; i++) {
            let dot = poly[i].x * axis.x + poly[i].y * axis.y;
            mx = max(mx, dot);
            mn = min(mn, dot);
        }
        return {
            min: mn,
            max: mx
        };
    }

    function getAxes(poly) {
        let axes = [];
        for (let i = 0; i < poly.length; i++) {
            let n = (i + 1) % poly.length;
            axes[i] = {
                y: poly[i].x - poly[n].x,
                x: -(poly[i].y - poly[n].y)
            };
        }
        return axes;
    }

    for (let p = 0; p < polys.length; p++) {
        let axes = getAxes(polys[p]);
        for (let i = 0; i < axes.length; i++) {
            let axis = axes[i];
            let p1 = project(poly1, axis);
            let p2 = project(poly2, axis);
            if (!overlap(p1.min, p1.max, p2.min, p2.max)) {
                return false;
            }
        }
    }

    return true;
}
realTronsi (912)

@Coder100 where is concave handling occurring?

Coder100 (17013)

uh
from what i can tell apparently it doesn't need it let me find the article explaining how it was made @realTronsi

realTronsi (912)

@Coder100 it looks to be using something similar to or is SAT, which only works for convex. The source article would be helpful thanks

realTronsi (912)

@Coder100 could you create a simple demo to show concave collisions with the provided code? The article does not handle concave polygons anywhere in the code