javascript – Optimizing Efficiency of Minimal Translation Vector (MTV) Calculation in SAT Collisions

I’ve applied a Collison Supervisor utilizing the Separating Axis Theorem (SAT), and I am in search of ideas to reinforce the efficiency of the Minimal Translation Vector (MTV) calculation. The collider works nicely, however I need to discover potential optimizations, particularly within the MTV calculation course of.

I am notably concerned with optimizing the way in which to get the collision data, which entails projections and loop iterations. Any insights, ideas, or greatest practices to reinforce the efficiency could be tremendously appreciated.

Observe: An optimization that I have never included, however I am attempting to implement, is to separate collisions into pairs to keep away from redundant calculations. For instance, when ObjectA is checking collisions with different objects and collides with ObjectB, I retailer collision data utilizing their IDs. When it is ObjectB‘s flip to verify collisions, it primarily ignores ObjectA as a result of the collision has already been resolved. Nevertheless, for some motive, this launched one other difficulty. As an instance ObjectC “pushes” ObjectB again into ObjectA; this may solely be resolved within the subsequent body or collision iteration, inflicting jittering for unknown causes.

This is the total code: https://github.com/markvaaz/game-engine/blob/Physics/engine/engine-components/sat.js

This is a simplified model of the code:

collisionInformation = {
  collided: false,
  regular: new Vector(),
  overlap: Infinity,
  tangent: new Vector(),
  penetration: new Vector(),
  axis: new Vector(),
  middle: new Vector()
};

Determines collision data between two recreation objects utilizing the Separating Axis Theorem (SAT).

getCollisionInformation(gameObjectA, gameObjectB) {
  if(
    gameObjectA === gameObjectB ||
    gameObjectA.Collider.disabled ||
    gameObjectB.Collider.disabled ||
    // AABB collision verify to keep away from pointless calculations
    !gameObjectA.Form.isWithinBounds(gameObjectB.Form.bounds, 1)
  ) return { collided: false };

  const CI = this.collisionInformation;
  const verticesA = gameObjectA.Form.vertices;
  const verticesB = gameObjectB.Form.vertices;

  // Reset the collision data
  CI.collided = false;
  CI.overlap = Infinity;

  // Get the utmost size of the vertices to keep away from a number of loops. For instance,
  // if the overall vertices from A are 20 and the overall vertices from B are 30,
  // it should loop 30 occasions as an alternative of fifty (the a few of the vertices size).
  // Though the variety of calculations on this state is roughly the identical,
  // it could be useful (or not) relying on the adjustments.
  const lenghtA = verticesA.size;
  const lenghtB = verticesB.size;
  const maxLength = Math.max(lenghtA, lenghtB);

  for(let i = 0; i < maxLength; i++){
    if(i < lenghtA && !this.getMTV(verticesA, verticesB, i))
      return CI;

    if(i < lenghtB && !this.getMTV(verticesB, verticesA, i))
      return CI;
  }

  // Calculate the relative place vector 'middle' from the middle of gameObjectA to gameObjectB,
  // then verify if this vector factors in the wrong way to the collision regular.
  // If that's the case, invert the collision-related vectors within the MTV (Minimal Translation Vector) object
  // to make sure they align appropriately for resolving the collision.
  const middle = CI.middle.set(gameObjectB.Form.centerOfMass).sub(gameObjectA.Form.centerOfMass);

  // Verify if the middle vector aligns with the collision regular (dot product < 0)
  if (middle.dot(CI.regular) < 0) {
    // If the middle vector factors in the wrong way to the collision regular,
    // invert the conventional, tangent, and penetration vectors within the MTV to make sure correct collision decision.
    CI.regular.negate();
    CI.tangent.negate();
    CI.penetration.negate();
  }

  return CI;
}

Calculate the Minimal Translation Vector (MTV) between two units of vertices.

getMTV(verticesA, verticesB, index){
  const vertexA = verticesA[index];
  const vertexB = verticesA[index + 1] ?? verticesA[0];
  const CI = this.collisionInformation;

  // Calculate the axis perpendicular to the present edge.
  const axis = CI.axis.set(-(vertexB.y - vertexA.y), vertexB.x - vertexA.x).normalize();

  // Get the overlap alongside the axis.
  const overlap = this.getOverlap(axis, verticesA, verticesB);

  // If there isn't any overlap, replace the MTV to point no collision.
  if(overlap === 0) return CI.collided = false;

  // If absolutely the overlap is lower than the present minimal overlap within the MTV,
  // replace the MTV with details about the present collision.
  if(Math.abs(overlap) < CI.overlap){
    CI.collided = true;

    CI.overlap = Math.abs(overlap);

    CI.regular.set(axis.x, axis.y);

    CI.tangent.set(-CI.regular.y, CI.regular.x);

    CI.penetration.set(CI.regular.x * overlap, CI.regular.y * overlap);
  }

  return CI.collided;
}

Calculate the overlap between two units of vertices alongside a specified axis by way of projections.

getOverlap(axis, verticesA, verticesB){
  let minA = Infinity;
  let maxA = -Infinity;
  let minB = Infinity;
  let maxB = -Infinity;

  const lenghtA = verticesA.size;
  const lenghtB = verticesB.size;

  const maxLength = Math.max(lenghtA, lenghtB);

  // Loop by way of vertices to calculate projections and discover minimal and most values
  for (let i = 0; i < maxLength; i++) {
    if(i < lenghtA){
      const projection = axis.dot(verticesA[i]);
      minA = Math.min(minA, projection);
      maxA = Math.max(maxA, projection);
    }

    if(i < lenghtB){
      const projection = axis.dot(verticesB[i]);
      minB = Math.min(minB, projection);
      maxB = Math.max(maxB, projection);
    }
  }

  // Verify for separation alongside the axis, return 0 if no overlap
  if (minA > maxB || minB > maxA) return 0;

  // Calculate the overlap between the 2 projections
  return Math.min(maxB - minA, maxA - minB);
}