Identifying extreme vertices for shadow effects in 2D game using JavaScript

Question

I'm facing an issue while trying to identify the two most extreme vertices of an object in my 2D game using JavaScript. The goal is to determine where I should create a trapezoid to simulate the shadow casting.

Currently, my approach involves rotating the object's vertices to the same plane as the light and then selecting the vertices with the highest and lowest Y values. However, this isn't working as expected, as I end up consistently selecting the diagonal vertices.

I thought about selecting the vertices with the greatest difference in angles relative to the light to determine which ones are the boundary vertices of the object, but I couldn't get it right.

Github repository: https://github.com/markvaaz/game-engine/tree/Renderer

Here's a snippet of my attempt to create the method within my LightingManager class:

  /**
   * Gets the extremes of the shape in relation to the plane of the angle between the light and the shape
   * @param {Object} shape
   * @param {Object} light
   * @method getVerticesFromExtremes
   */
  getVerticesFromExtremes(shape, light){
    const { position: center, vertices } = shape;
    const { position } = light;
    const angle = new Vector(position).angleBetween(center);
    let minIndex = 0;
    let maxIndex = 0;

    vertices.forEach((vertex, index) => {
      vertex = new Vector(vertex.x, vertex.y);
      vertex.rotate(-angle);

      if(vertex.y < vertices[minIndex].y){
        minIndex = index;
      }

      if(vertex.y > vertices[maxIndex].y){
        maxIndex = index;
      }
    });

    if(minIndex > maxIndex) return {
      min: maxIndex,
      max: minIndex
    }

    return {
      min: minIndex,
      max: maxIndex
    }
  }

Here's an example image illustrating the desired shadow effect achieved by selecting the two most extreme points:

For testing purposes, I'm using the following vertex coordinates for a rectangle:

[ { "x": -32, "y": -41 }, { "x": 32, "y": -41 }, { "x": 32, "y": 41 }, { "x": -32, "y": 41 } ]

Note that the coordinates belong to the shape, and the global position is not included. The shape's global position is indicated by the 'position' property of the shape. The light position is its global position

This is the light object and its properties:

{
  "enabled": true,
  "mode": "lighter",
  "brightness": 1,
  "radius": 250,
  "type": "cone",
  "position": {
    "x": 722.5,
    "y": 413.9
  },
  "steps": [
    {
      "start": 1,
      "color": "rgba(255, 255, 255, 0.8)"
    },
    {
      "start": 0,
      "color": "transparent"
    }
  ],
  "angle": 0.0006666665679014124,
  "distance": 150.0000333333296
}

EDIT: DMGregory's answer works up to a certain distance from the object; however, upon getting closer, it ends up selecting the wrong vertex.

Mark Vaaz · Accepted Answer · 2024-01-15 00:33:40Z

I revamped the method to calculate the angles between the light source and each vertex, and then selecting the vertices with the smallest and largest angles. This way, you get the vertices that are at the extremes in relation to the light, regardless of the angle.

getVerticesFromExtremes(shape, light, shapePosition) {
    // If the shape has no vertices, return false
    if(shape.vertices.length === 0) return false;
    
    // Destructure the vertices from the shape
    const { vertices } = shape;
    // Define the center position of the shape and the position of the light
    const center = shapePosition;
    const position = light.position;

    // Initialize the minimum and maximum angles to extreme values
    let minAngle = Infinity;
    let maxAngle = -Infinity;

    // Initialize the indices of the minimum and maximum angles to -1
    let minIndex = -1;
    let maxIndex = -1;

    for(let index = 0; index < vertices.length; index++){
      // Calculate the position of the current vertex
      const vertex = {
        x: vertices[index].x + center.x,
        y: vertices[index].y + center.y
      };

      // Create vectors from the light source to the vertex and the center of the shape
      const vectorToVertex = new Vector(vertex.x - position.x, vertex.y - position.y);
      const vectorToCenter = new Vector(center.x - position.x, center.y - position.y);

      // Calculate the difference between the angles
      let angle = Math.atan2(vectorToVertex.y, vectorToVertex.x) - Math.atan2(vectorToCenter.y, vectorToCenter.x);

      // Normalize the angle to be within the range [-PI, PI]
      if (angle < -Math.PI) {
        angle += Math.PI * 2;
      }

      if (angle > Math.PI) {
        angle -= Math.PI * 2;
      }

      // Update the minimum and maximum angles and their corresponding indices
      if (angle < minAngle) {
        minAngle = angle;
        minIndex = index;
      }

      if (angle > maxAngle) {
        maxAngle = angle;
        maxIndex = index;
      }
    }

    // Return the indices of the vertices with the minimum and maximum angles
    return { min: minIndex, max: maxIndex }
  }

Mark Vaaz · Accepted Answer · 2024-01-12 19:43:41Z

If your light cone is consistently less than 180 degrees, you can get away with sorting the vertices in the order of the slope of the rays joining them to the light, without any trigonometry:

  getVerticesFromExtremes(shape, light) {
    const { center, vertices } = shape;
    const { position } = light;

    // Construct a vector pointing from the light to the object.
    const axis = new Vector(center.x - position.x, center.y - position.y); 

    // Compute offsets to center the light in this axis-oriented coordinates system.
    const onShift = position.x * axis.x + position.y * axis.y;
    const offShift = position.x * axis.y - position.y * axis.x;

    let minSlope = Infinity;
    let maxSlope = -Infinity;
 
    let minIndex = 0;
    let maxIndex = 0;

    for(let index = 0; index < vertices.length; index++){
      const vertex = {
        x: vertices[index].x + center.x,
        y: vertices[index].y + center.y
      };

      // Add the shape's global position to the vertex

      // Put this vertex into a light-centered coordinate system.
      // First, measuring its (scaled) distance in front of the light:
      const onAxis = vertex.x * axis.x + vertex.y * axis.y - onShift;

      // Skip vertices behind / in the plane of the light.
      if (onAxis <= 0) return;

      // Then measuring its (scaled) offset above or below the line through
      // the center of this object.
      const offAxis = vertex.x * axis.y - vertex.y * axis.x - offShift;

      // Compute the slope of the line from the light to the vertex.
      const slope = offAxis / onAxis;
      
      if (slope < minSlope) {
          minSlope = slope;
          minIndex = index;
      }

      if (slope > maxSlope) {
          maxSlope = slope;
          maxIndex = index;
      }
    }

    if(minIndex > maxIndex) return {
      min: maxIndex,
      max: minIndex
    }

    return {
      min: minIndex,
      max: maxIndex
    }
  }

This gets more complicated if you have a light with a > 180 degree span though, or complex shapes that can wrap around the light, so the object's center is on one side, but some occluding vertices might be on the other.

I forgot to mention that the vertices don't include the global position of the shape. I reviewed your code to make some modifications, and I added the center to the vertex, which solved the problem. — Mark Vaaz
– Mark Vaaz, Commented Jan 12, 2024 at 18:33
I was testing it with various shapes and stumbled upon a bug. I edited my question with more information and added a gif demonstrating the issue. — Mark Vaaz
– Mark Vaaz, Commented Jan 13, 2024 at 4:28
As I mentioned, this approximation only works in a narrow cone. Specifically, for vertices less than 90° from the ray joining the light to the object center. In the new example, you're using an omnidirectional light instead of a cone, allowing some vertices within the light to get more than 90° from the angle to the object center when it's close to the light. — DMGregory
– DMGregory ♦, Commented Jan 14, 2024 at 17:57

Blindman67 · Accepted Answer · 2024-01-18 21:53:16Z

The best solution would need to know more about the objects you are trying to find the extremes for.

Things like,

are the shapes always convex,
is there any symmetry,
do lines intercept self,
and more

Simple convex shape

The simplest solution is to get the vector from each point to the light and then compare the cross product between adjacent vectors.

Calculate the cross product for adjacent clockwise and anticlockwise points.

For cross products < 0 clockwise next point is more extreme, and anticlockwise cross product is > 0 for more extreme (I think that is the right way around, if not just swap the signs)

This only works for convex shapes. To do it for concave shapes you are best off breaking the object into a set of convex shapes.

This only works if the light is outside the shape.

The Function

The function FindExtrema(light) that finds the extremes.

Note there is NO trig required.
Complexity is O(n) where n is number on points defining the shape.

    // this.verts[] set of 2d points for shape
    // light 2D pos of light
    // V2 creates 2D vector
    FindExtrema(light) {     
        const left = V2().set(light).sub(this.pos); // from center to light
        const right = V2().set(left);  // for right edge
        const wV = V2();               // working vector
        this.leftVertIdx = -1;         // left index
        this.rightVertIdx = -1;        // right index
        var i = 0, c;
        for (const tV of this.verts) { // Each point in turn
            wV.set(tV).sub(light);     // vector from light to point  
            c = left.cross(wV);        // cross product with prev left 
            if (c < 0) {               // Is left of prev left   
                this.leftVertIdx = i;  // Yes save idx
                left.set(wV).neg();    // set new left (swap dir)
            }
            c = right.cross(wV);       // same for right extreme
            if (c > 0) {
                this.rightVertIdx = i;
                right.set(wV).neg();
            }
            i++;
        }
    }

Example

The snippet shows this simple method of getting the extrema for a shape.

Move mouse to move shape.

Press the mouse button to get a random shape. You will note that the solution will not work for concave shapes.

The function Shape.FindExtrema(from) finds the left and right extreme points when looking at the object from the 2D vector from.

The points are referenced by their index as Shape.leftVertIdx and Shape.rightVertIdx

The shape transforms the base shape. It is the transformed points that are used to find the left and right edges.

If you have problems ask in the comments.

const ctx = canvas.getContext("2d");
var W = canvas.width, H = canvas.height, resized = false;
const TAU = Math.PI * 2;
const Resize = () => { W = canvas.width = innerWidth; H = canvas.height = innerHeight; resized = true; }
const mouse  = {x : 0, y : 0, button : false}
function mouseEvents(e){
    mouse.x = e.pageX; mouse.y = e.pageY;
    mouse.button = e.type === "mousedown" ? true : e.type === "mouseup" ? false : mouse.button;
}
["mousedown","mouseup","mousemove"].forEach(name => document.addEventListener(name,mouseEvents));

const V2 = (x = 0, y = 0) => ({
    x, y,
    set(v) { this.x = v.x; this.y = v.y; return this; },
    sub(v) { this.x -= v.x; this.y -= v.y; return this; },
    length() { return (this.x * this.x + this.y * this.y) ** 0.5; },
    normalize(len = this.length()) { this.x /= len; this.y /= len; return this; },
    neg() { this.x = -this.x; this.y = -this.y; return this; },
    cross(v) { return this.x * v.y - this.y * v.x; },
    scale(s) {  this.x *= s; this.y *= s; return this; },
});

const Light = {
    pos: V2(),    
    Update() {
        if (resized) {
            resized = false;
            this.pos.x = W * 0.5;
            this.pos.y = H * 0.5;
            this.grd = ctx.createRadialGradient(this.pos.x, this.pos.y, 10, this.pos.x, this.pos.y, 1000);
            this.grd.addColorStop(0, "#FFF");
            this.grd.addColorStop(0.01, "#BA4");
            this.grd.addColorStop(1, "#220");
        }
    },
    Draw() {
        ctx.fillStyle = this.grd;
        ctx.fillRect(0, 0, W, H);
    },
};

const Shape = {
    pos: V2(),
    col: "#034",
    sCol: "#8BD",
    verts: [],
    tVerts: [], // transformed
    leftVertIdx: -1,  // -1 for unknown
    rightVertIdx: -1, // -1 for unknown
    Clear() {
        this.verts.length = 0;
        this.tVerts.length = 0;
        this.leftVertIdx = -1;
        this.rightVertIdx = -1;
    },
    Add(...verts) { 
        this.verts.push(...verts); 
        for (const v of verts) { this.tVerts.push(V2(v.x, v.y)); }
    },
    Update(pos, rot) {  // translate and rotate shape
        i = 0;
        this.pos.set(pos);
        const xAx = Math.cos(rot);
        const xAy = Math.sin(rot);
        for (const v of this.verts) {
            const tV = this.tVerts[i++];
            tV.x = v.x * xAx - v.y * xAy + pos.x;
            tV.y = v.x * xAy + v.y * xAx + pos.y;
        }        
    },
    Draw() {
        ctx.fillStyle = this.col;
        ctx.strokeStyle = this.sCol;
        ctx.beginPath();
        for (const tV of this.tVerts) { ctx.lineTo(tV.x, tV.y); }
        ctx.closePath();
        ctx.fill();
        ctx.stroke();
    },
    DrawExtrema(from) {
        const wV = V2();
        ctx.fillStyle = "#220";
        ctx.beginPath();
        if (this.leftVertIdx > -1) {
            const tV = this.tVerts[this.leftVertIdx];
            wV.set(tV).sub(from).normalize().scale(10000);
            ctx.moveTo(tV.x + wV.x, tV.y + wV.y);
            ctx.lineTo(tV.x, tV.y);
        }
        if (this.rightVertIdx > -1) {
            let i = (this.leftVertIdx + 1) % this.verts.length;
            while (i != this.rightVertIdx) {
                ctx.lineTo(this.tVerts[i].x, this.tVerts[i].y);
                i = (i + 1) % this.verts.length;
            }
            const tV = this.tVerts[this.rightVertIdx];
            wV.set(tV).sub(from).normalize().scale(10000);
            ctx.lineTo(tV.x, tV.y);
            ctx.lineTo(tV.x + wV.x, tV.y + wV.y);
        }
        ctx.fill();
        ctx.fillStyle = "#000";
     },
     DrawLineToLight(light) {
        ctx.strokeStyle = "#FFF";
        ctx.beginPath();
        if (this.leftVertIdx > -1) {
            ctx.moveTo(light.x, light.y);
            ctx.lineTo(this.tVerts[this.leftVertIdx].x, this.tVerts[this.leftVertIdx].y);
        }
        if (this.rightVertIdx > -1) {
            ctx.moveTo(light.x, light.y);
            ctx.lineTo(this.tVerts[this.rightVertIdx].x, this.tVerts[this.rightVertIdx].y);
        }
        ctx.stroke();
    },
    FindExtrema(from) {
        const left = V2().set(from).sub(this.pos).normalize();
        const right = V2().set(from).sub(this.pos).normalize();
        const wV = V2();
        this.leftVertIdx = -1;
        this.rightVertIdx = -1;
        var i = 0, c;
        for (const tV of this.tVerts) { 
            wV.set(tV).sub(from).normalize();
            c = left.cross(wV);
            if (c < 0) {
                this.leftVertIdx = i;
                left.set(wV).neg();
            }
            c = right.cross(wV);
            if (c > 0) {
                this.rightVertIdx = i;
                right.set(wV).neg();
            }
            i++;
        }
    }
};
const RndI = (m) => Math.random() * m | 0;
const Rnd  = (m, M) => Math.random() * (M-m) + m;
function RandomShape() {
   Shape.Clear();
   const vCount = RndI(8) + 4;
   const aStep = TAU / vCount;
   var ang = 0;
   var i = 0;
   while (i < vCount) {
       const a = ang + Rnd(-0.5, 0.5) * aStep;
       const dist = Rnd(50, 100);
       const x = Math.cos(a) * dist;
       const y = Math.sin(a) * dist;
       Shape.Add(V2(x,y));
       ang += aStep;
       i++;
   }
}
Shape.Add(V2(-50, -20), V2(50, -20), V2(50, 20), V2(-50, 20));
requestAnimationFrame(MainLoop);
function MainLoop(time) {
     if (mouse.button) {
        RandomShape();
        mouse.button = false;
     }
     if (canvas.width != innerWidth || canvas.width != innerHeight) { Resize() }
     ctx.clearRect(0, 0, W, H);
     Light.Update();
     Shape.Update(mouse, Math.sin(time * 0.0001) * 0.5);
     Shape.FindExtrema(Light.pos);
     Light.Draw();
     Shape.DrawExtrema(Light.pos);
     Shape.Draw();
     Shape.DrawLineToLight(Light.pos);
     requestAnimationFrame(MainLoop);
}

canvas { position: absolute; left: 0px; top: 0px; }
div { position: absolute; left: 10px; top: 10px; color: #FFF;}

<canvas id="canvas" width="10" height="10"></canvas>
<div id="info">Press mouse button to craete random shape</div>

Stack Exchange Network

Identifying extreme vertices for shadow effects in 2D game using JavaScript

3 Answers 3

Simple convex shape

The Function

Example

You must log in to answer this question.

Hot Network Questions

Identifying extreme vertices for shadow effects in 2D game using JavaScript

3 Answers 3

Simple convex shape

The Function

Example

You must log in to answer this question.

Related

Hot Network Questions