javascript – Exploring Efficiency Enhancements in Minimal Translation Vector (MTV) Calculation for SAT Collisions

I’m creating a Collision Supervisor utilizing the Separating Axis Theorem (SAT) and asking for options to enhance the efficiency of the Minimal Translation Vector (MTV) calculation. Whereas the collision course of works effectively, I’m excited about exploring doable optimizations, particularly within the MTV.

Specifically, I’m excited about optimizing the retrieval of convergence data, which includes interpolation and loop iteration. We are going to establish any insights, suggestions, or beneficial actions that may additional enhance effectivity.

Moreover, I consider that sharing this data might be a worthwhile addition to Stack Gamedev, serving to all recreation builders dealing with related efficiency challenges of their tasks.

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

Here is a simplified model of the code:

collisionInformation = {
  collided: false,
  regular: new Vector(),
  overlap: Infinity,
  tangent: new Vector(),
  penetration: new Vector(),
  axis: new Vector(),
  heart: 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 examine 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 entire vertices from A are 20 and the entire vertices from B are 30,
  // it should loop 30 occasions as a substitute of fifty (the a number 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 modifications.
  const lengthA = verticesA.size;
  const lengthB = verticesB.size;
  const maxLength = Math.max(lengthA, lengthB);

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

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

  // Calculate the relative place vector 'heart' from the middle of gameObjectA to gameObjectB,
  // then examine if this vector factors in the other 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 accurately for resolving the collision.
  const heart = CI.heart.set(gameObjectB.Form.centerOfMass).sub(gameObjectA.Form.centerOfMass);

  // Examine if the middle vector aligns with the collision regular (dot product < 0)
  if (heart.dot(CI.regular) < 0) {
    // If the middle vector factors in the other 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 is not 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 projections.

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

  const lengthA = verticesA.size;
  const lengthB = verticesB.size;

  const maxLength = Math.max(lengthA, lengthB);

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

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

  // Examine 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);
}