src_engineWebGL.js

/**
 * LittleJS WebGL Interface
 * - All WebGL used by the engine is wrapped up here
 * - Will fall back to 2D canvas rendering if WebGL is not supported
 * - For normal stuff you won't need to see or call anything in this file
 * - For advanced stuff there are helper functions to create shaders, textures, etc
 * - Can be disabled with glEnable to revert to 2D canvas rendering
 * - Batches sprite rendering on GPU for incredibly fast performance
 * - Sprite transform math is done in the shader where possible
 * - Supports shadertoy style post processing shaders via plugin
 * @namespace WebGL
 */

'use strict';

/** The WebGL canvas which appears above the main canvas and below the overlay canvas
 *  @type {HTMLCanvasElement}
 *  @memberof WebGL */
let glCanvas;

/** WebGL2 context for `glCanvas`
 *  @type {WebGL2RenderingContext}
 *  @memberof WebGL */
let glContext;

/** Should WebGL be setup with anti-aliasing? must be set before calling engineInit
 *  @type {boolean}
 *  @memberof WebGL */
let glAntialias = true;

// WebGL internal variables not exposed to documentation
let glShader, glPolyShader, glPolyMode, glAdditive, glBatchAdditive, glActiveTexture, glArrayBuffer, glGeometryBuffer, glPositionData, glColorData, glBatchCount;

// WebGL internal constants
const gl_ARRAY_BUFFER_SIZE = 5e5;
const gl_INDICES_PER_INSTANCE = 11;
const gl_INSTANCE_BYTE_STRIDE = gl_INDICES_PER_INSTANCE * 4;
const gl_MAX_INSTANCES = gl_ARRAY_BUFFER_SIZE / gl_INSTANCE_BYTE_STRIDE | 0;
const gl_INDICES_PER_POLY_VERTEX = 3;
const gl_POLY_VERTEX_BYTE_STRIDE = gl_INDICES_PER_POLY_VERTEX * 4;
const gl_MAX_POLY_VERTEXES = gl_ARRAY_BUFFER_SIZE / gl_POLY_VERTEX_BYTE_STRIDE | 0;

///////////////////////////////////////////////////////////////////////////////

// Initialize WebGL, called automatically by the engine
function glInit()
{
    if (!glEnable || headlessMode) return;

    // create the canvas and textures
    glCanvas = document.createElement('canvas');
    glContext = glCanvas.getContext('webgl2', {antialias:glAntialias});

    if (!glContext)
    {
        console.warn('WebGL2 not supported, falling back to 2D canvas rendering!');
        glCanvas = glContext = undefined;
        glEnable = false;
        return;
    }

    // create the WebGL canvas
    const rootElement = mainCanvas.parentElement;
    rootElement.appendChild(glCanvas);

    // setup instanced rendering shader program
    glShader = glCreateProgram(
        '#version 300 es\n' +     // specify GLSL ES version
        'precision highp float;'+ // use highp for better accuracy
        'uniform mat4 m;'+        // transform matrix
        'in vec2 g;'+             // in: geometry
        'in vec4 p,u,c,a;'+       // in: position/size, uvs, color, additiveColor
        'in float r;'+            // in: rotation
        'out vec2 v;'+            // out: uv
        'out vec4 d,e;'+          // out: color, additiveColor
        'void main(){'+           // shader entry point
        'vec2 s=(g-.5)*p.zw;'+    // get size offset
        'gl_Position=m*vec4(p.xy+s*cos(r)-vec2(-s.y,s)*sin(r),1,1);'+ // transform position
        'v=mix(u.xw,u.zy,g);'+    // pass uv to fragment shader
        'd=c;e=a;'+               // pass colors to fragment shader
        '}'                       // end of shader
        ,
        '#version 300 es\n' +     // specify GLSL ES version
        'precision highp float;'+ // use highp for better accuracy
        'uniform sampler2D s;'+   // texture
        'in vec2 v;'+             // in: uv
        'in vec4 d,e;'+           // in: color, additiveColor
        'out vec4 c;'+            // out: color
        'void main(){'+           // shader entry point
        'c=texture(s,v)*d+e;'+    // modulate texture by color plus additive
        '}'                       // end of shader
    );

    // setup poly rendering shaders
    glPolyShader = glCreateProgram(
        '#version 300 es\n' +     // specify GLSL ES version
        'precision highp float;'+ // use highp for better accuracy
        'uniform mat4 m;'+        // transform matrix
        'in vec2 p;'+             // in: position
        'in vec4 c;'+             // in: color
        'out vec4 d;'+            // out: color
        'void main(){'+           // shader entry point
        'gl_Position=m*vec4(p,1,1);'+ // transform position
        'd=c;'+                   // pass color to fragment shader
        '}'                       // end of shader
        ,
        '#version 300 es\n' +     // specify GLSL ES version
        'precision highp float;'+ // use highp for better accuracy
        'in vec4 d;'+             // in: color
        'out vec4 c;'+            // out: color
        'void main(){'+           // shader entry point
        'c=d;'+                   // set color
        '}'                       // end of shader
    );

    // init buffers
    const glInstanceData = new ArrayBuffer(gl_ARRAY_BUFFER_SIZE);
    glPositionData = new Float32Array(glInstanceData);
    glColorData = new Uint32Array(glInstanceData);
    glArrayBuffer = glContext.createBuffer();
    glGeometryBuffer = glContext.createBuffer();

    // create the geometry buffer, triangle strip square
    const geometry = new Float32Array([glBatchCount=0,0,1,0,0,1,1,1]);
    glContext.bindBuffer(glContext.ARRAY_BUFFER, glGeometryBuffer);
    glContext.bufferData(glContext.ARRAY_BUFFER, geometry, glContext.STATIC_DRAW);
}

function glSetInstancedMode()
{
    if (!glPolyMode)
        return;
    
    // setup instanced mode
    glFlush();
    glPolyMode = false;
    glContext.useProgram(glShader);

    // set vertex attributes
    let offset = 0;
    const initVertexAttribArray = (name, type, typeSize, size)=>
    {
        const location = glContext.getAttribLocation(glShader, name);
        const stride = typeSize && gl_INSTANCE_BYTE_STRIDE; // only if not geometry
        const divisor = typeSize && 1; // only if not geometry
        const normalize = typeSize === 1; // only if color
        glContext.enableVertexAttribArray(location);
        glContext.vertexAttribPointer(location, size, type, normalize, stride, offset);
        glContext.vertexAttribDivisor(location, divisor);
        offset += size*typeSize;
    }
    glContext.bindBuffer(glContext.ARRAY_BUFFER, glGeometryBuffer);
    initVertexAttribArray('g', glContext.FLOAT, 0, 2); // geometry
    glContext.bindBuffer(glContext.ARRAY_BUFFER, glArrayBuffer);
    glContext.bufferData(glContext.ARRAY_BUFFER, gl_ARRAY_BUFFER_SIZE, glContext.DYNAMIC_DRAW);
    initVertexAttribArray('p', glContext.FLOAT, 4, 4); // position & size
    initVertexAttribArray('u', glContext.FLOAT, 4, 4); // texture coords
    initVertexAttribArray('c', glContext.UNSIGNED_BYTE, 1, 4); // color
    initVertexAttribArray('a', glContext.UNSIGNED_BYTE, 1, 4); // additiveColor
    initVertexAttribArray('r', glContext.FLOAT, 4, 1); // rotation
}

function glSetPolyMode()
{
    if (glPolyMode)
        return;
    
    // setup poly mode
    glFlush();
    glPolyMode = true;
    glContext.useProgram(glPolyShader);

    // set vertex attributes
    let offset = 0;
    const initVertexAttribArray = (name, type, typeSize, size)=>
    {
        const location = glContext.getAttribLocation(glPolyShader, name);
        const normalize = typeSize === 1; // only normalize if color
        const stride = gl_POLY_VERTEX_BYTE_STRIDE;
        glContext.enableVertexAttribArray(location);
        glContext.vertexAttribPointer(location, size, type, normalize, stride, offset);
        glContext.vertexAttribDivisor(location, 0);
        offset += size*typeSize;
    }
    glContext.bindBuffer(glContext.ARRAY_BUFFER, glArrayBuffer);
    glContext.bufferData(glContext.ARRAY_BUFFER, gl_ARRAY_BUFFER_SIZE, glContext.DYNAMIC_DRAW);
    initVertexAttribArray('p', glContext.FLOAT, 4, 2);         // position
    initVertexAttribArray('c', glContext.UNSIGNED_BYTE, 1, 4); // color
}

// Setup WebGL render each frame, called automatically by engine
// Also used by tile layer rendering when redrawing tiles
function glPreRender()
{
    if (!glEnable || !glContext) return;

    // clear the canvas
    glClearCanvas();

    // build the transform matrix
    const s = vec2(2*cameraScale).divide(mainCanvasSize);
    const rotatedCam = cameraPos.rotate(-cameraAngle);
    const p = vec2(-1).subtract(rotatedCam.multiply(s));
    const ca = Math.cos(cameraAngle);
    const sa = Math.sin(cameraAngle);
    const transform = [
        s.x  * ca,  s.y * sa, 0, 0,
        -s.x * sa,  s.y * ca, 0, 0,
        1,          1,        1, 0,
        p.x,        p.y,      0, 1];

    // set the same transform matrix for both shaders
    const initUniform = (program, uniform, value) =>
    {
        glContext.useProgram(program);
        const location = glContext.getUniformLocation(program, uniform);
        glContext.uniformMatrix4fv(location, false, value);
    }
    initUniform(glPolyShader, 'm', transform);
    initUniform(glShader, 'm', transform);

    // set the active texture
    glContext.activeTexture(glContext.TEXTURE0);
    if (textureInfos[0])
    {
        glActiveTexture = textureInfos[0].glTexture;
        glContext.bindTexture(glContext.TEXTURE_2D, glActiveTexture);
    }

    // start with additive blending off
    glAdditive = glBatchAdditive = false;

    // force it to enter instanced mode
    glPolyMode = true;
    glSetInstancedMode();
}

/** Clear the canvas and setup the viewport
 *  @memberof WebGL */
function glClearCanvas()
{
    if (!glContext) return;

    // clear and set to same size as main canvas
    glCanvas.width = drawCanvas.width;
    glCanvas.height = drawCanvas.height;
    glContext.viewport(0, 0, glCanvas.width, glCanvas.height);
    glContext.clear(glContext.COLOR_BUFFER_BIT);
}

/** Set the WebGL texture, called automatically if using multiple textures
 *  - This may also flush the gl buffer resulting in more draw calls and worse performance
 *  @param {WebGLTexture} texture
 *  @param {boolean} [wrap] - Should the texture wrap or clamp
 *  @memberof WebGL */
function glSetTexture(texture, wrap=false)
{
    // must flush cache with the old texture to set a new one
    if (!glContext || texture === glActiveTexture)
        return;

    glFlush();
    glActiveTexture = texture;
    glContext.bindTexture(glContext.TEXTURE_2D, glActiveTexture);

    // set wrap mode
    const wrapMode = wrap ? glContext.REPEAT : glContext.CLAMP_TO_EDGE;
    glContext.texParameteri(glContext.TEXTURE_2D, glContext.TEXTURE_WRAP_S, wrapMode);
    glContext.texParameteri(glContext.TEXTURE_2D, glContext.TEXTURE_WRAP_T, wrapMode);
}

/** Compile WebGL shader of the given type, will throw errors if in debug mode
 *  @param {string} source
 *  @param {number} type
 *  @return {WebGLShader}
 *  @memberof WebGL */
function glCompileShader(source, type)
{
    if (!glContext) return;

    // build the shader
    const shader = glContext.createShader(type);
    glContext.shaderSource(shader, source);
    glContext.compileShader(shader);

    // check for errors
    if (debug && !glContext.getShaderParameter(shader, glContext.COMPILE_STATUS))
        throw glContext.getShaderInfoLog(shader);
    return shader;
}

/** Create WebGL program with given shaders
 *  @param {string} vsSource
 *  @param {string} fsSource
 *  @return {WebGLProgram}
 *  @memberof WebGL */
function glCreateProgram(vsSource, fsSource)
{
    if (!glContext) return;

    // build the program
    const program = glContext.createProgram();
    glContext.attachShader(program, glCompileShader(vsSource, glContext.VERTEX_SHADER));
    glContext.attachShader(program, glCompileShader(fsSource, glContext.FRAGMENT_SHADER));
    glContext.linkProgram(program);

    // check for errors
    if (debug && !glContext.getProgramParameter(program, glContext.LINK_STATUS))
        throw glContext.getProgramInfoLog(program);
    return program;
}

/** Create WebGL texture from an image and init the texture settings
 *  Restores the active texture when done
 *  @param {HTMLImageElement|HTMLCanvasElement|OffscreenCanvas} [image]
 *  @return {WebGLTexture}
 *  @memberof WebGL */
function glCreateTexture(image)
{
    if (!glContext) return;

    // build the texture
    const texture = glContext.createTexture();
    let mipMap = false;
    if (image && image.width)
    {
        glSetTextureData(texture, image);
        glContext.bindTexture(glContext.TEXTURE_2D, texture);
        mipMap = !tilesPixelated && isPowerOfTwo(image.width) && isPowerOfTwo(image.height);
    }
    else
    {
        // create a white texture
        const whitePixel = new Uint8Array([255, 255, 255, 255]);
        glContext.bindTexture(glContext.TEXTURE_2D, texture);
        glContext.texImage2D(glContext.TEXTURE_2D, 0, glContext.RGBA, 1, 1, 0, glContext.RGBA, glContext.UNSIGNED_BYTE, whitePixel);
    }

    // set texture filtering
    const magFilter = tilesPixelated ? glContext.NEAREST : glContext.LINEAR;
    const minFilter = mipMap ? glContext.LINEAR_MIPMAP_LINEAR : magFilter;
    glContext.texParameteri(glContext.TEXTURE_2D, glContext.TEXTURE_MAG_FILTER, magFilter);
    glContext.texParameteri(glContext.TEXTURE_2D, glContext.TEXTURE_MIN_FILTER, minFilter);
    if (mipMap)
        glContext.generateMipmap(glContext.TEXTURE_2D);
    glContext.bindTexture(glContext.TEXTURE_2D, glActiveTexture); // rebind active texture
    return texture;
}

/** Deletes a WebGL texture
 *  @param {WebGLTexture} [texture]
 *  @memberof WebGL */
function glDeleteTexture(texture)
{
    if (!glContext) return;
    glContext.deleteTexture(texture);
}

/** Set WebGL texture data from an image, restores the active texture when done
 *  @param {WebGLTexture} texture
 *  @param {HTMLImageElement|HTMLCanvasElement|OffscreenCanvas} image
 *  @memberof WebGL */
function glSetTextureData(texture, image)
{
    if (!glContext) return;

    // build the texture
    ASSERT(!!image && image.width > 0, 'Invalid image data.');
    glContext.bindTexture(glContext.TEXTURE_2D, texture);
    glContext.texImage2D(glContext.TEXTURE_2D, 0, glContext.RGBA, glContext.RGBA, glContext.UNSIGNED_BYTE, image);
    glContext.bindTexture(glContext.TEXTURE_2D, glActiveTexture); // rebind active texture
}

/** Draw all sprites and clear out the buffer, called automatically by the system whenever necessary
 *  @memberof WebGL */
function glFlush()
{
    if (glEnable && glContext && glBatchCount)
    {
        // set bend mode
        const destBlend = glBatchAdditive ? glContext.ONE : glContext.ONE_MINUS_SRC_ALPHA;
        glContext.blendFuncSeparate(glContext.SRC_ALPHA, destBlend, glContext.ONE, destBlend);
        glContext.enable(glContext.BLEND);
        
        const byteLength = glBatchCount * 
            (glPolyMode ? gl_INDICES_PER_POLY_VERTEX : gl_INDICES_PER_INSTANCE);
        glContext.bufferSubData(glContext.ARRAY_BUFFER, 0, glPositionData, 0, byteLength);
        
        // draw the batch
        if (glPolyMode)
            glContext.drawArrays(glContext.TRIANGLE_STRIP, 0, glBatchCount);
        else
            glContext.drawArraysInstanced(glContext.TRIANGLE_STRIP, 0, 4, glBatchCount);
        drawCount += glBatchCount;
        glBatchCount = 0;
    }
    glBatchAdditive = glAdditive;
}

/** Flush any sprites still in the buffer and copy to main canvas
 *  @param {CanvasRenderingContext2D|OffscreenCanvasRenderingContext2D} context
 *  @memberof WebGL */
function glCopyToContext(context)
{
    if (!glEnable || !glContext)
        return;

    glFlush();
    context.drawImage(glCanvas, 0, 0);
}

/** Set anti-aliasing for WebGL canvas
 *  Must be called before engineInit
 *  @param {boolean} [antialias]
 *  @memberof WebGL */
function glSetAntialias(antialias=true)
{
    ASSERT(!glCanvas, 'must be called before engineInit');
    glAntialias = antialias;
}

/** Add a sprite to the gl draw list, used by all gl draw functions
 *  @param {number} x
 *  @param {number} y
 *  @param {number} sizeX
 *  @param {number} sizeY
 *  @param {number} [angle]
 *  @param {number} [uv0X]
 *  @param {number} [uv0Y]
 *  @param {number} [uv1X]
 *  @param {number} [uv1Y]
 *  @param {number} [rgba=-1] - white is -1
 *  @param {number} [rgbaAdditive=0] - black is 0
 *  @memberof WebGL */
function glDraw(x, y, sizeX, sizeY, angle=0, uv0X=0, uv0Y=0, uv1X=1, uv1Y=1, rgba=-1, rgbaAdditive=0)
{
    // flush if there is not enough room or if different blend mode
    if (glBatchCount >= gl_MAX_INSTANCES || glBatchAdditive !== glAdditive)
        glFlush();
    glSetInstancedMode();

    glPolyMode = false;
    let offset = glBatchCount++ * gl_INDICES_PER_INSTANCE;
    glPositionData[offset++] = x;
    glPositionData[offset++] = y;
    glPositionData[offset++] = sizeX;
    glPositionData[offset++] = sizeY;
    glPositionData[offset++] = uv0X;
    glPositionData[offset++] = uv0Y;
    glPositionData[offset++] = uv1X;
    glPositionData[offset++] = uv1Y;
    glColorData[offset++] = rgba;
    glColorData[offset++] = rgbaAdditive;
    glPositionData[offset++] = angle;
}

/** Transform and add a polygon to the gl draw list
 *  @param {Array<Vector2>} points - Array of Vector2 points
 *  @param {number} rgba - Color of the polygon as a 32-bit integer
 *  @param {number} x
 *  @param {number} y
 *  @param {number} sx
 *  @param {number} sy
 *  @param {number} angle
 *  @param {boolean} [tristrip] - should tristrip algorithm be used
 *  @memberof WebGL */
function glDrawPointsTransform(points, rgba, x, y, sx, sy, angle, tristrip=true)
{
    const pointsOut = [];
    for (const p of points)
    {
        // transform the point
        const px = p.x*sx;
        const py = p.y*sy;
        const sa = Math.sin(-angle);
        const ca = Math.cos(-angle);
        pointsOut.push(vec2(x + ca*px - sa*py, y + sa*px + ca*py));
    }
    const drawPoints = tristrip ? glPolyStrip(pointsOut) : pointsOut;
    glDrawPoints(drawPoints, rgba);
}

/** Transform and add a polygon to the gl draw list
 *  @param {Array<Vector2>} points - Array of Vector2 points
 *  @param {number} rgba - Color of the polygon as a 32-bit integer
 *  @param {number} lineWidth - Width of the outline
 *  @param {number} x
 *  @param {number} y
 *  @param {number} sx
 *  @param {number} sy
 *  @param {number} angle
 *  @param {boolean} [wrap] - Should the outline connect the first and last points
 *  @memberof WebGL */
function glDrawOutlineTransform(points, rgba, lineWidth, x, y, sx, sy, angle, wrap=true)
{
    const outlinePoints = glMakeOutline(points, lineWidth, wrap);
    glDrawPointsTransform(outlinePoints, rgba, x, y, sx, sy, angle, false);
}

/** Add a list of points to the gl draw list
 *  @param {Array<Vector2>} points - Array of Vector2 points in tri strip order
 *  @param {number} rgba - Color as a 32-bit integer
 *  @memberof WebGL */
function glDrawPoints(points, rgba)
{
    if (!glEnable || points.length < 3)
        return; // needs at least 3 points to have area
    
    // flush if there is not enough room or if different blend mode
    const vertCount = points.length + 2;
    if (glBatchCount+vertCount >= gl_MAX_POLY_VERTEXES || glBatchAdditive !== glAdditive)
        glFlush();
    glSetPolyMode();
  
    // setup triangle strip with degenerate verts at start and end
    let offset = glBatchCount * gl_INDICES_PER_POLY_VERTEX;
    for (let i = vertCount; i--;)
    {
        const j = clamp(i-1, 0, vertCount-3);
        const point = points[j];
        glPositionData[offset++] = point.x;
        glPositionData[offset++] = point.y;
        glColorData[offset++] = rgba;
    }
    glBatchCount += vertCount;
}

/** Add a list of colored points to the gl draw list
 *  @param {Array<Vector2>} points - Array of Vector2 points in tri strip order
 *  @param {Array<number>} pointColors - Array of 32-bit integer colors
 *  @memberof WebGL */
function glDrawColoredPoints(points, pointColors)
{
    if (!glEnable || points.length < 3)
        return; // needs at least 3 points to have area
    
    // flush if there is not enough room or if different blend mode
    const vertCount = points.length + 2;
    if (glBatchCount+vertCount >= gl_MAX_POLY_VERTEXES || glBatchAdditive !== glAdditive)
        glFlush();
    glSetPolyMode();
  
    // setup triangle strip with degenerate verts at start and end
    let offset = glBatchCount * gl_INDICES_PER_POLY_VERTEX;
    for (let i = vertCount; i--;)
    {
        const j = clamp(i-1, 0, vertCount-3);
        const point = points[j];
        const color = pointColors[j];
        glPositionData[offset++] = point.x;
        glPositionData[offset++] = point.y;
        glColorData[offset++] = color;
    }
    glBatchCount += vertCount;
}

// WebGL internal function to convert polygon to outline triangle strip
function glMakeOutline(points, width, wrap=true)
{
    if (points.length < 2)
        return [];
    
    const halfWidth = width / 2;
    const strip = [];
    const n = points.length;
    const e = 1e-6;
    const miterLimit = width*100;
    for (let i = 0; i < n; i++)
    {
        // for each vertex, calculate normal based on adjacent edges
        const prev = points[wrap ? (i - 1 + n) % n : max(i - 1, 0)];
        const curr = points[i];
        const next = points[wrap ? (i + 1) % n : min(i + 1, n - 1)];
        
        // direction from previous to current
        const dx1 = curr.x - prev.x;
        const dy1 = curr.y - prev.y;
        const len1 = (dx1*dx1 + dy1*dy1)**.5;
        
        // direction from current to next
        const dx2 = next.x - curr.x;
        const dy2 = next.y - curr.y;
        const len2 = (dx2*dx2 + dy2*dy2)**.5;
        
        if (len1 < e && len2 < e)
            continue; // skip degenerate point
        
        // calculate perpendicular normals for each edge
        const nx1 = len1 > e ? -dy1 / len1 : 0;
        const ny1 = len1 > e ?  dx1 / len1 : 0;
        const nx2 = len2 > e ? -dy2 / len2 : 0;
        const ny2 = len2 > e ?  dx2 / len2 : 0;
        
        // average the normals for miter
        let nx = nx1 + nx2;
        let ny = ny1 + ny2;
        const nlen = (nx*nx + ny*ny)**.5;
        if (nlen < e)
        {
            // 180 degree turn - use perpendicular
            nx = nx1;
            ny = ny1;
        }
        else
        {
            // calculate miter length
            nx /= nlen;
            ny /= nlen;
            const dot = nx1 * nx + ny1 * ny;
            if (dot > e)
            {
                // scale normal by miter length, clamped to miterLimit
                const miterLength = min(1 / dot, miterLimit);
                nx *= miterLength;
                ny *= miterLength;
            }
        }
        
        // create inner and outer points along the normal
        const inner = vec2(curr.x - nx * halfWidth, curr.y - ny * halfWidth);
        const outer = vec2(curr.x + nx * halfWidth, curr.y + ny * halfWidth);
        strip.push(inner);
        strip.push(outer);
    }
    if (strip.length > 1 && wrap)
    {
        // close the loop
        strip.push(strip[0]);
        strip.push(strip[1]);
    }
    return strip;
}

// WebGL internal function to convert polys to tri strips
function glPolyStrip(points)
{
    // validate input
    if (points.length < 3)
        return [];
    
    // cross product helper: (b-a) x (c-a)
    const cross = (a,b,c)=> (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);

    // calculate signed area of polygon
    const signedArea = (poly)=>
    {
        let area = 0;
        for (let i = poly.length; i--;)
        {
            const j = (i+1) % poly.length;
            area += poly[i].cross(poly[j]);
        }
        return area;
    }

    // ensure counter-clockwise winding
    if (signedArea(points) < 0)
        points = points.reverse();

    // check if point is inside triangle
    const e = 1e-9;
    const pointInTriangle = (p, a, b, c)=>
    {
        const c1 = cross(a, b, p);
        const c2 = cross(b, c, p);
        const c3 = cross(c, a, p);
        const negative = (c1<-e?1:0) + (c2<-e?1:0) + (c3<-e?1:0);
        const positive = (c1> e?1:0) + (c2> e?1:0) + (c3> e?1:0);
        return !(negative && positive);
    };

    // ear clipping triangulation
    const indices = [];
    for (let i = 0; i < points.length; ++i)
        indices[i] = i;
    const triangles = [];
    let attempts = 0;
    const maxAttempts = points.length ** 2 + 100;
    while (indices.length > 3 && attempts++ < maxAttempts)
    {
        let foundEar = false;
        for (let i = 0; i < indices.length; i++)
        {
            const i0 = indices[(i + indices.length - 1) % indices.length];
            const i1 = indices[i];
            const i2 = indices[(i + 1) % indices.length];
            const a = points[i0], b = points[i1], c = points[i2];

            // check if convex
            if (cross(a, b, c) < e)
                continue;
                
            // check if any other point is inside
            let hasInside = false;
            for (let j = 0; j < indices.length; j++)
            {
                const k = indices[j];
                if (k === i0 || k === i1 || k === i2)
                    continue;
                const p = points[k];
                hasInside = pointInTriangle(p, a, b, c);
                if (hasInside)
                    break;
            }
            if (hasInside)
                continue;

            // found valid ear
            triangles.push([i0, i1, i2]);
            indices.splice(i, 1);
            foundEar = true;
            break;
        }

        // fallback for degenerate cases
        if (!foundEar)
        {
            let worstIndex = -1, worstValue = Infinity;
            for (let i = 0; i < indices.length; i++)
            {
                const i0 = indices[(i + indices.length - 1) % indices.length];
                const i1 = indices[i];
                const i2 = indices[(i + 1) % indices.length];
                const value = abs(cross(points[i0], points[i1], points[i2]));
                if (value < worstValue)
                {
                    worstValue = value;
                    worstIndex = i;
                }
            }
            if (worstIndex < 0)
                break;
            
            const i0 = indices[(worstIndex + indices.length - 1) % indices.length];
            const i1 = indices[worstIndex];
            const i2 = indices[(worstIndex + 1) % indices.length];
            triangles.push([i0, i1, i2]);
            indices.splice(worstIndex, 1);
        }
    }
    
    // add final triangle
    if (indices.length === 3)
        triangles.push([indices[0], indices[1], indices[2]]);
    if (!triangles.length)
        return [];

    // convert triangles to triangle strip with degenerate connectors
    const strip = [];
    let [a0, b0, c0] = triangles[0];
    strip.push(points[a0], points[b0], points[c0]);
    for (let i = 1; i < triangles.length; i++)
    {
        // add degenerate bridge from last vertex to first of new triangle
        const [a, b, c] = triangles[i];
        strip.push(points[c0], points[a]);
        strip.push(points[a], points[b], points[c]);
        c0 = c;
    }
    return strip;
}