Circle collision issue

[kefniark]

I tried to use this library and realized some projectile were able to go through wall without triggering any collision (mostly circle collider).

The same issue is reproducible even in the samples.
For example, if we add few extra walls to Stress.mjs:

this.collisions.createPolygon(382.5, 255, [[-62.5, -5], [-62.5, 5], [62.5, 5], [62.5, -5]]);
this.collisions.createPolygon(507.5, 255, [[-62.5, -5], [-62.5, 5], [62.5, 5], [62.5, -5]]);
this.collisions.createPolygon(257.5, 255, [[-62.5, -5], [-62.5, 5], [62.5, 5], [62.5, -5]]);
this.collisions.createPolygon(132.5, 255, [[-62.5, -5], [-62.5, 5], [62.5, 5], [62.5, -5]]);

this.collisions.createPolygon(574.5, 697, [[-5, 62.5], [-5, -62.5], [5, -62.5], [5, 62.5]]);
this.collisions.createPolygon(574.5, 572, [[-5, 62.5], [-5, -62.5], [5, -62.5], [5, 62.5]]);
this.collisions.createPolygon(574.5, 447, [[-5, 62.5], [-5, -62.5], [5, -62.5], [5, 62.5]]);
this.collisions.createPolygon(574.5, 323, [[-5, 62.5], [-5, -62.5], [5, -62.5], [5, 62.5]]);

this.collisions.createPolygon(65, 697, [[-5, 62.5], [-5, -62.5], [5, -62.5], [5, 62.5]]);
this.collisions.createPolygon(65, 572, [[-5, 62.5], [-5, -62.5], [5, -62.5], [5, 62.5]]);
this.collisions.createPolygon(65, 447, [[-5, 62.5], [-5, -62.5], [5, -62.5], [5, 62.5]]);
this.collisions.createPolygon(65, 323, [[-5, 62.5], [-5, -62.5], [5, -62.5], [5, 62.5]]);

this.collisions.createPolygon(382.5, 764.5, [[-62.5, -5], [-62.5, 5], [62.5, 5], [62.5, -5]]);
this.collisions.createPolygon(507.5, 764.5, [[-62.5, -5], [-62.5, 5], [62.5, 5], [62.5, -5]]);
this.collisions.createPolygon(257.5, 764.5, [[-62.5, -5], [-62.5, 5], [62.5, 5], [62.5, -5]]);
this.collisions.createPolygon(132.5, 764.5, [[-62.5, -5], [-62.5, 5], [62.5, 5], [62.5, -5]]);

we can already see circle collider being able to go through some of the walls

[ShimShamSam]

Thanks for reporting this. I'm swamped with work this week. Can it wait until this weekend?

[kefniark]

Yes no problem, take your time.

I found the reason earlier, and it's related to the order of vertices.
It's not specified in the doc or the code, but polygon vertices need to be counter-clockwise for this algorithm to work.

So, I see two solutions:

• Just throwing an error and let the user deal with it (that's the solution used for example by p2.js):

throw new Error("Convex vertices must be given in counter-clockwise winding.");

• Fixing it automatically by sorting vertices in createPolygon

[kefniark]

To be sure vertices are sorted in a counter-clockwise, for the moment I just calculate the area of each polygon.
If the area of a polygon is negative, his vertices are sorted in a clockwise order and need to be reverse():

/**
 * Make sure that vertices are ready to use by the collision library
 *
 * @private
 * @param {number[][]} vertices
 * @returns {number[][]}
 *
 * @memberOf CollisionSystem
 */
private reorderVertices(vertices: number[][]) {
	const area = this.area(vertices);
	if (area < 0) {
		vertices.reverse();
	}
	return vertices;
}

/**
 * Calculate the area of a polygon
 * The area will be negative if the points are not given in counter-clockwise order.
 *
 * @private
 * @param {number[][]} vertices
 * @returns {number}
 */
private area(vertices: number[][]) {
	// find bottom right point
	let brIndex = 0;
	for (let i = 1; i < vertices.length; ++i) {
		const isLower = vertices[i][1] < vertices[brIndex][1];
		const isRight = (vertices[i][1] === vertices[brIndex][1] && vertices[i][0] > vertices[brIndex][0]);
		if (isLower || isRight) {
			brIndex = i;
		}
	}

	// calculate area
	let area = 0;
	for (let i = 0; i < vertices.length; ++i) {
		const a = vertices[(i + brIndex) % vertices.length];
		const b = vertices[(i + 1 + brIndex) % vertices.length];
		const c = vertices[(i + 2 + brIndex) % vertices.length];
		area += (((b[0] - a[0]) * (c[1] - a[1])) - ((c[0] - a[0]) * (b[1] - a[1])));;
	}

	return area / 2;
}

The same method can be used to detect Concave Polygons and throw error (all these triangles should have the same sign for a convex shape).