2D Visibility Polygons Using Matter.js Vertices

Calculating a 2D line-of-sight visibility polygon around Matter.js obstacles involves extracting absolute world vertices from physics bodies, casting angular rays toward those vertices, finding the closest ray-edge intersections, and sorting the intersection points radially to construct a closed polygon. This technique allows developers to create dynamic field-of-view (FOV), lighting, and stealth mechanics directly synchronized with the Matter.js physics simulation.

1. Extracting Line Segments from Matter.js Bodies

Matter.js stores the world-space coordinates of a rigid body inside its vertices array. If your simulation contains compound bodies, you should iterate through body.parts (skipping the parent body at index 0 if parts exist) to collect accurate geometric boundaries.

To build the visibility obstacle set, extract every edge as a line segment defined by two endpoints \((A, B)\):

function getObstacleSegments(bodies, mapBounds) {
  const segments = [];

  // Add bounding box boundaries of the map/screen
  segments.push(
    { a: { x: mapBounds.minX, y: mapBounds.minY }, b: { x: mapBounds.maxX, y: mapBounds.minY } },
    { a: { x: mapBounds.maxX, y: mapBounds.minY }, b: { x: mapBounds.maxX, y: mapBounds.maxY } },
    { a: { x: mapBounds.maxX, y: mapBounds.maxY }, b: { x: mapBounds.minX, y: mapBounds.maxY } },
    { a: { x: mapBounds.minX, y: mapBounds.maxY }, b: { x: mapBounds.minX, y: mapBounds.minY } }
  );

  for (const body of bodies) {
    // Skip sensors or non-colliding visual bodies if desired
    if (body.isSensor) continue;

    const parts = body.parts.length > 1 ? body.parts.slice(1) : [body];

    for (const part of parts) {
      const vertices = part.vertices;
      for (let i = 0; i < vertices.length; i++) {
        const nextIndex = (i + 1) % vertices.length;
        segments.push({
          a: { x: vertices[i].x, y: vertices[i].y },
          b: { x: vertices[nextIndex].x, y: vertices[nextIndex].y }
        });
      }
    }
  }

  return segments;
}

2. Generating Ray Angles Toward Vertices

Visibility changes state primarily at the silhouette corners of obstacles. To capture light passing past corners without artifacts, collect every unique vertex coordinate, determine its angle relative to the source, and cast three rays: one directly at the vertex, and two offset by a minute angle (\(\pm 0.0001\) radians).

function getRayAngles(source, segments) {
  const angles = [];

  for (const seg of segments) {
    for (const point of [seg.a, seg.b]) {
      const angle = Math.atan2(point.y - source.y, point.x - source.x);
      // Cast rays directly at the corner and slightly around it
      angles.push(angle - 0.0001, angle, angle + 0.0001);
    }
  }

  return angles;
}

3. Calculating Ray-Segment Intersections

For each angle, project a ray from the light source and find the nearest intersection among all segments. Use the 2D parametric intersection between a ray starting at point \(P\) along direction \(D = (\cos\theta, \sin\theta)\) and a segment between \(A\) and \(B\):

function getRayIntersection(rayOrigin, rayDir, segment) {
  const r_px = rayOrigin.x;
  const r_py = rayOrigin.y;
  const r_dx = rayDir.x;
  const r_dy = rayDir.y;

  const s_px = segment.a.x;
  const s_py = segment.a.y;
  const s_dx = segment.b.x - segment.a.x;
  const s_dy = segment.b.y - segment.a.y;

  const r_mag = Math.sqrt(r_dx * r_dx + r_dy * r_dy);
  const s_mag = Math.sqrt(s_dx * s_dx + s_dy * s_dy);

  if (r_dx / r_mag === s_dx / s_mag && r_dy / r_mag === s_dy / s_mag) {
    return null; // Parallel
  }

  const denominator = s_dx * r_dy - s_dy * r_dx;
  if (denominator === 0) return null;

  const T2 = (r_dx * (s_py - r_py) + r_dy * (r_px - s_px)) / denominator;
  const T1 = (s_px + s_dx * T2 - r_px) / r_dx;

  // T1 is the ray distance, T2 is the segment fraction
  if (T1 > 0 && T2 >= 0 && T2 <= 1) {
    return {
      x: r_px + r_dx * T1,
      y: r_py + r_dy * T1,
      distance: T1
    };
  }

  return null;
}

4. Constructing the Visibility Polygon

To build the final shape:

  1. Iterate through all generated angles.
  2. Intersect the ray with every obstacle segment to locate the closest collision point.
  3. Store the closest hit points with their corresponding angles.
  4. Sort the hit points in ascending order based on their angle (\(-\pi\) to \(\pi\)).
  5. Connect the sorted points sequentially into a closed polygon.
function computeVisibilityPolygon(source, bodies, mapBounds) {
  const segments = getObstacleSegments(bodies, mapBounds);
  const angles = getRayAngles(source, segments);
  const visibilityPoints = [];

  for (const angle of angles) {
    const rayDir = { x: Math.cos(angle), y: Math.sin(angle) };
    let closestIntersection = null;

    for (const segment of segments) {
      const hit = getRayIntersection(source, rayDir, segment);
      if (hit) {
        if (!closestIntersection || hit.distance < closestIntersection.distance) {
          closestIntersection = { x: hit.x, y: hit.y, angle: angle, distance: hit.distance };
        }
      }
    }

    if (closestIntersection) {
      visibilityPoints.push(closestIntersection);
    }
  }

  // Sort counter-clockwise to form a valid polygon
  visibilityPoints.sort((a, b) => a.angle - b.angle);

  return visibilityPoints;
}

5. Rendering the Result

The output array of points can be drawn using standard HTML5 Canvas 2D methods:

function renderVisibilityPolygon(ctx, points) {
  if (points.length === 0) return;

  ctx.beginPath();
  ctx.moveTo(points[0].x, points[0].y);

  for (let i = 1; i < points.length; i++) {
    ctx.lineTo(points[i].x, points[i].y);
  }

  ctx.closePath();
  ctx.fillStyle = "rgba(255, 255, 200, 0.4)";
  ctx.fill();
}

Performance Optimization

The basic approach operates at \(\mathcal{O}(N^2)\) complexity, where \(N\) is the total vertex count. When scaling up: