Skip to main content
Game Development

Return to Answer

Bounty Awarded with 50 reputation awarded by Mark Vaaz
added 1295 characters in body
Source Link
Blindman67
Blindman67
  • 460
  • 2
  • 9

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++;
        }
    }

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++;
        }
    }
Source Link
Blindman67
Blindman67
  • 460
  • 2
  • 9

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.

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>