Skip to content

Instantly share code, notes, and snippets.

@ehaliewicz

ehaliewicz/barycentric.html

Created November 12, 2024 21:40
Show Gist options
  • Save ehaliewicz/fcce24a7f2b6dfca2c29e93b27364aa0 to your computer and use it in GitHub Desktop.
Save ehaliewicz/fcce24a7f2b6dfca2c29e93b27364aa0 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ehaliewicz created this gist Nov 12, 2024.
    394 changes: 394 additions & 0 deletions barycentric.html
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,394 @@
    <!DOCTYPE html>
    <html>
    <head></head>
    <body>

    <canvas id="canvas-id" style="image-rendering:pixelated;"></canvas>

    <script type="text/javascript">

    // triangles are
    // [[x,y,z],[x,y,z],[x,y,z]]

    (function() {

    const getDeterminant = function(ax, ay, bx, by, cx, cy) {
    //const ab = new Vector(b);
    //ab.sub(a);
    const abx = bx - ax;
    const aby = by - ay;


    const acx = cx - ax;
    const acy = cy - ay;
    //const ac = new Vector(c);
    //ac.sub(a);

    //return ab[1] * ac[0] - ab[0] * ac[1];
    return aby * acx - abx * acy;
    }

    const isTopLeft = function(start, end) {
    const edgex = end[0] - start[0];
    const edgey = end[1] - start[1];

    const isLeftEdge = edgey > 0;
    const isTopEdge = edgey == 0 && edgex < 0;
    return isLeftEdge || isTopEdge;
    }


    const canvas = document.getElementById("canvas-id");
    console.log("canvas: ", canvas);

    const devicePixelRatio = 0.5;

    const bufWidth = window.innerWidth * devicePixelRatio;
    const bufHeight = window.innerHeight * devicePixelRatio;

    canvas.width = bufWidth;
    canvas.height = bufHeight;


    canvas.style.width = window.innerWidth + "px";
    canvas.style.height = window.innerHeight + "px";


    const ctx = canvas.getContext("2d");

    const screenBuffer = ctx.createImageData(window.innerWidth * devicePixelRatio, window.innerHeight * devicePixelRatio);


    const blocksize = 8;

    var canvasWBlocks = Math.floor((screenBuffer.Width + blocksize-1) / blocksize);
    var canvasHBlocks = Math.floor((screenBuffer.Height + blocksize-1) / blocksize);
    var block_full = new Uint8Array(canvasWBlocks * canvasHBlocks);

    let pixels = 0;

    function drawTriangle( x1, y1, x2, y2, x3, y3, col32, data, width, height) {

    // http://devmaster.net/forums/topic/1145-advanced-rasterization/

    // 28.4 fixed-point coordinates

    var x1 = Math.round( 16 * x1 );
    var x2 = Math.round( 16 * x2 );
    var x3 = Math.round( 16 * x3 );

    var y1 = Math.round( 16 * y1 );
    var y2 = Math.round( 16 * y2 );
    var y3 = Math.round( 16 * y3 );

    // Deltas

    var dx12 = x1 - x2, dy12 = y2 - y1;
    var dx23 = x2 - x3, dy23 = y3 - y2;
    var dx31 = x3 - x1, dy31 = y1 - y3;

    // Bounding rectangle

    var minx = Math.max( ( Math.min( x1, x2, x3 ) + 0xf ) >> 4, 0 );
    var maxx = Math.min( ( Math.max( x1, x2, x3 ) + 0xf ) >> 4, width );
    var miny = Math.max( ( Math.min( y1, y2, y3 ) + 0xf ) >> 4, 0 );
    var maxy = Math.min( ( Math.max( y1, y2, y3 ) + 0xf ) >> 4, height );

    // Block size, standard 8x8 (must be power of two)

    var q = blocksize;

    // Start in corner of 8x8 block

    minx &= ~(q - 1);
    miny &= ~(q - 1);

    // Constant part of half-edge functions

    var c1 = dy12 * ((minx << 4) - x1) + dx12 * ((miny << 4) - y1);
    var c2 = dy23 * ((minx << 4) - x2) + dx23 * ((miny << 4) - y2);
    var c3 = dy31 * ((minx << 4) - x3) + dx31 * ((miny << 4) - y3);

    // Correct for fill convention

    if ( dy12 > 0 || ( dy12 == 0 && dx12 > 0 ) ) c1 ++;
    if ( dy23 > 0 || ( dy23 == 0 && dx23 > 0 ) ) c2 ++;
    if ( dy31 > 0 || ( dy31 == 0 && dx31 > 0 ) ) c3 ++;

    // Note this doesn't kill subpixel precision, but only because we test for >=0 (not >0).
    // It's a bit subtle.
    c1 = (c1 - 1) >> 4;
    c2 = (c2 - 1) >> 4;
    c3 = (c3 - 1) >> 4;

    // Set up min/max corners
    var qm1 = q - 1; // for convenience
    var nmin1 = 0, nmax1 = 0;
    var nmin2 = 0, nmax2 = 0;
    var nmin3 = 0, nmax3 = 0;
    if (dx12 >= 0) nmax1 -= qm1*dx12; else nmin1 -= qm1*dx12;
    if (dy12 >= 0) nmax1 -= qm1*dy12; else nmin1 -= qm1*dy12;
    if (dx23 >= 0) nmax2 -= qm1*dx23; else nmin2 -= qm1*dx23;
    if (dy23 >= 0) nmax2 -= qm1*dy23; else nmin2 -= qm1*dy23;
    if (dx31 >= 0) nmax3 -= qm1*dx31; else nmin3 -= qm1*dx31;
    if (dy31 >= 0) nmax3 -= qm1*dy31; else nmin3 -= qm1*dy31;

    // Loop through blocks
    var linestep = (width - q);// * 4;
    var scale = 255.0 / (c1 + c2 + c3);

    var cb1 = c1;
    var cb2 = c2;
    var cb3 = c3;
    var qstep = -q;
    var e1x = qstep * dy12;
    var e2x = qstep * dy23;
    var e3x = qstep * dy31;
    var x0 = minx;

    for (var y0 = miny; y0 < maxy; y0 += q) {
    // New block line - keep hunting for tri outer edge in old block line dir
    while (x0 >= minx && x0 < maxx && cb1 >= nmax1 && cb2 >= nmax2 && cb3 >= nmax3) {
    x0 += qstep;
    cb1 += e1x;
    cb2 += e2x;
    cb3 += e3x;
    }

    // Okay, we're now in a block we know is outside. Reverse direction and go into main loop.
    qstep = -qstep;
    e1x = -e1x;
    e2x = -e2x;
    e3x = -e3x;
    while (1) {
    // Step everything
    x0 += qstep;
    cb1 += e1x;
    cb2 += e2x;
    cb3 += e3x;

    // We're done with this block line when at least one edge completely out
    // If an edge function is too small and decreasing in the current traversal
    // dir, we're done with this line.
    if (x0 < minx || x0 >= maxx) break;
    if (cb1 < nmax1) if (e1x < 0) break; else continue;
    if (cb2 < nmax2) if (e2x < 0) break; else continue;
    if (cb3 < nmax3) if (e3x < 0) break; else continue;

    // We can skip this block if its already fully covered
    var blockX = (x0 / q) | 0;
    var blockY = (y0 / q) | 0;
    var blockInd = blockX + blockY * canvasWBlocks;
    if (block_full[blockInd]) continue;

    // Offset at top-left corner
    var offset = (x0 + y0 * width);

    // Accept whole block when fully covered
    if (cb1 >= nmin1 && cb2 >= nmin2 && cb3 >= nmin3) {
    var cy1 = cb1;
    var cy2 = cb2;

    for ( var iy = 0; iy < q; iy ++ ) {
    //var cx1 = cy1;
    //var cx2 = cy2;

    for ( var ix = 0; ix < q; ix ++ ) {
    //var u = cx1 * scale; // 0-255!
    //var v = cx2 * scale; // 0-255!
    data[offset] = col32;
    //pixels++;
    //data[offset] = (u<<24)|(v<<16)|0xFF;

    //cx1 += dy12;
    //cx2 += dy23;
    offset++;
    }

    pixels += (q*q);
    //cy1 += dx12;
    //cy2 += dx23;
    offset += linestep;
    }

    block_full[blockInd] = 1;

    } else { // Partially covered block
    var cy1 = cb1;
    var cy2 = cb2;
    var cy3 = cb3;

    for ( var iy = 0; iy < q; iy ++ ) {
    var cx1 = cy1;
    var cx2 = cy2;
    var cx3 = cy3;

    for ( var ix = 0; ix < q; ix ++ ) {
    if ( (cx1 | cx2 | cx3) >= 0) {
    //var u = cx1 * scale; // 0-255!
    //var v = cx2 * scale; // 0-255!
    data[offset] = col32;
    //data[offset] = (u<<24)|(v<<16)|0xFF;
    pixels++;
    }

    cx1 += dy12;
    cx2 += dy23;
    cx3 += dy31;
    offset++;
    }

    cy1 += dx12;
    cy2 += dx23;
    cy3 += dx31;
    offset += linestep;
    }

    }

    }

    // Advance to next row of blocks
    cb1 += q*dx12;
    cb2 += q*dx23;
    cb3 += q*dx31;
    }

    }

    const drawTris = function(numTris, tris, verts, buffer, bufWidth, bufHeight) {
    for(let i = 0; i < numTris; i += 4) {
    const vai = tris[i+0];
    const vbi = tris[i+1];
    const vci = tris[i+2];
    const col = tris[i+3];
    const vax = verts[vai*3+0];
    const vay = verts[vai*3+1];
    //const vax = verts[vai*3+0];
    const vbx = verts[vbi*3+0];
    const vby = verts[vbi*3+1];

    const vcx = verts[vci*3+0];
    const vcy = verts[vci*3+1];

    drawTriangle( vax, vay, vbx, vby, vcx, vcy, col, buffer, bufWidth, bufHeight);

    }
    }


    const buf = new ArrayBuffer(screenBuffer.data.length);
    const buf8 = new Uint8ClampedArray(buf);
    const data = new Uint32Array(buf);

    const vertices = new Uint32Array(3*10000);


    let numTris = 0;
    let numVerts = 0;
    let vertIdx = 0;
    let triIdx = 0;

    vertices[vertIdx++] = 140;
    vertices[vertIdx++] = 100;
    vertices[vertIdx++] = 0;
    vertices[vertIdx++] = 140;
    vertices[vertIdx++] = 40;
    vertices[vertIdx++] = 0;
    vertices[vertIdx++] = 80;
    vertices[vertIdx++] = 40;
    vertices[vertIdx++] = 0;
    vertices[vertIdx++] = 50;
    vertices[vertIdx++] = 90;
    vertices[vertIdx++] = 0;

    numVerts = 4;

    const tris = new Uint32Array(4*10000);
    //[
    0,1,2, ((0xFF<<24)|(120<<16)|(240<<8)|100), // vertex indexes, plus color attributes
    0,2,3, ((0xFF<<24)|(100<<16)|(180<<8)|240)
    //];
    tris[triIdx++] = 0;
    tris[triIdx++] = 1;
    tris[triIdx++] = 2;
    tris[triIdx++] = ((0xFF<<24)|(120<<16)|(240<<8)|100);
    tris[triIdx++] = 0;
    tris[triIdx++] = 2;
    tris[triIdx++] = 3;
    tris[triIdx++] = ((0xFF<<24)|(100<<16)|(180<<8)|240);

    numTris = 2;

    for(let i = 0; i < 998; i++) {
    // last slot is angle, not used yet
    const v1 = [Math.floor(Math.random() * bufWidth), Math.floor(Math.random() * bufHeight), 0];
    const v2 = [Math.floor(Math.random() * bufWidth), Math.floor(Math.random() * bufHeight), 0];
    const v3 = [Math.floor(Math.random() * bufWidth), Math.floor(Math.random() * bufHeight), 0];

    const points = [v1,v2,v3];

    const center = points.reduce((acc, [ x, y ]) => {
    acc[0] += x / points.length;
    acc[1] += y / points.length;
    return acc;
    }, [ 0, 0 ]);

    const angles = points.map(([ x, y ]) => {
    return [ x, y, Math.atan2(y - center[1], x - center[0]) * 180 / Math.PI ];
    });

    const pointsSorted = angles.sort((a, b) => b[2] - a[2]);

    //const ccwPoints = points.reverse();
    //ccwPoints.unshift(ccwPoints.pop());

    const r = Math.floor(Math.random() * 255);
    const g = Math.floor(Math.random() * 255);
    const b = Math.floor(Math.random() * 255);
    tris[triIdx++] = numVerts++;
    tris[triIdx++] = numVerts++;
    tris[triIdx++] = numVerts++;
    tris[triIdx++] = ((0xFF<<24)|(r<<16)|(g<<8)|b);
    vertices[vertIdx++] = pointsSorted[0][0];
    vertices[vertIdx++] = pointsSorted[0][1];
    vertices[vertIdx++] = pointsSorted[0][2];
    vertices[vertIdx++] = pointsSorted[1][0];
    vertices[vertIdx++] = pointsSorted[1][1];
    vertices[vertIdx++] = pointsSorted[1][2];
    vertices[vertIdx++] = pointsSorted[2][0];
    vertices[vertIdx++] = pointsSorted[2][1];
    vertices[vertIdx++] = pointsSorted[2][2];
    numTris++;

    }


    console.log(numTris);
    console.log(numVerts);

    console.log(tris);
    console.log(vertices);
    const startTime = performance.now();
    drawTris(numTris, tris, vertices, data, screenBuffer.width, screenBuffer.height);

    //screenBuffer.data.set(data);
    screenBuffer.data.set(buf8);
    const endTime = performance.now();
    console.log("pixels filled: ", pixels);

    console.log("" + endTime-startTime, "ms");

    const fps = 1000 / (endTime-startTime);
    const pixPerSec = pixels * fps;
    console.log("" + Math.round(pixPerSec/1000000) + "MPix per second");

    ctx.putImageData(screenBuffer, 0, 0);

    })();
    </script>
    </body>



    </html>