hex_marchingcubes.html

<!DOCTYPE html><html lang="en"><head><meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title></title></head><body>
<script type="module">

// #region IMPORTS
import Starter, { THREE }           from './lib/starter.js';
import Util                         from './lib/Util.js';
import DynLineMesh                  from './lib/DynLineMesh.js';
import ShapePointsMesh              from './lib/ShapePointsMesh.js';
import IrregularHexGrid             from './grid/IrregularHexGrid.js';

import { UtilGltf2, Gltf2 }         from './lib/UtilGltf2.js';

import { Ray, Bvh, nearPoint, from3JSScreenProjection }
                                    from './bvh/index.js';

import MarchingCubes                from './mc/MarchingCubes.js';
import TileDictionary               from './mc/TileDictionary.js';

import { vec3_distance, vec3_add, vec3_scale, vec3_sub } from './lib/Maths.js';
import op_GetVertFaces              from './halfedge/ops/op_GetVertFaces.js';
import op_FaceCentroid              from './halfedge/ops/op_FaceCentroid.js';
import op_FacePoints                from './halfedge/ops/op_FacePoints.js';
import op_FaceVertices              from './halfedge/ops/op_FaceVertices.js';

import TrilinearLattice             from './trilinear/TrilinearLattice.js';
import TrilinearLatticeMaterial     from './trilinear/TrilinearLatticeMaterial.js';
// #endregion

// #region MAIN
let App;
let Debug   = {};
let Ref     = {};

window.addEventListener( "load", async _=>{
    App = new Starter( { webgl2:true, grid:true } );
    App.setCamera( 0, 40, 12, [0,0.0,0] );

    App.add( ( Debug.ln   = new DynLineMesh() ) );
    App.add( ( Debug.pnt  = new ShapePointsMesh().disableDepth() ) );
    App.add( ( Debug.grid = new DynLineMesh() ) );

    Debug.grid.position.y = 0.005;
    Debug.pnt.position.y = 0.005;

    // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    // SIMPLE GRID FOR TESTING
    const grid   = IrregularHexGrid.build( 5, 3, 50, 0.4, 110, 0 );
    const irGrid = new IRGrid().fromTopology( grid, 1, 3 );

    // Initialize all the cells with some userData
    irGrid.cells.forEach( (v,i,ary)=>{ ary[i].userData = { bitValue:0, mesh:null }; });

    debugFaces( grid );
    debugMesh( grid );

    Ref.irGrid = irGrid;
    //irGrid.togglePointByIdx( 0 );
    //irGrid.togglePointByIdx( 5 );

    // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    // Setup what we need to do ray intersection on Grid Points
    const bvh = new Bvh();
    bvh.maxItemsPerNode = 20;
    bvh.getItemPosition = ( data, idx )=>{ return data[ idx ].pos; };
    bvh.setData( irGrid.points );
    Ref.bvh = bvh;

    // debugBVH();
    
    // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    const gltf  = await Gltf2.fetch( './res/mc_tiles.gltf' );
    Ref.dic     = new TileDictionary();
    tileLoading( gltf, Ref.dic );

    // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    // MAKE CUBE TILE FIT IRREGULAR GRID CELL
    const lattice = new TrilinearLattice();
    lattice.setBounds( [-1,-1,-1], [1,1,1] );
    Ref.lattice        = lattice;
    Ref.latticeDefCube = lattice.cube.slice( 0 );

    // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    rebuild();
    App.render();
});
//#endregion

// #region DEBUG
function setRadius( grid, radius ){
    for( let v of grid.vertices ) vec3_norm_scale( v.pos, v.pos, radius );
}

function debugVertices( grid ){
    for( const e of grid.vertices ) Debug.pnt.add( e.pos, 0x00ff00, 2 );
}

function debugEdges( grid ){
    for( const e of grid.iterEdges() ) Debug.ln.add( e.a, e.b, 0x707070 );
}

function debugFaces( grid ){
    for( const f of grid.faces ){
        let edg = grid.halfEdges[ f.halfEdges[0] ];
        let len = f.halfEdges.length;
        for( let i=1; i <= len; i++ ){
            let ii  = i % len;
            let nex = grid.halfEdges[ f.halfEdges[ ii ] ];
            Debug.grid.add( grid.getVertPos( edg.vertex ), grid.getVertPos( nex.vertex ), 0x707070 );
            edg = nex;
        }
    }
}

function debugMesh( grid ){
    const verts = grid.flattenVertices();
    const ind   = grid.flattenIndices();
    const mesh  = toMesh( verts, ind );
    mesh.position.y = 0.001;
    App.add( mesh  );
}

function toMesh( verts, idx ){
    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    const bGeo = new THREE.BufferGeometry();
    bGeo.setAttribute( "position",  new THREE.BufferAttribute( new Float32Array( verts ), 3 ) );
    if( idx && idx.length > 0 )   bGeo.setIndex( idx );

    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    const mat  = new THREE.MeshPhongMaterial( { color:0x009999 } ); // ,side:THREE.DoubleSide
    const mesh = new THREE.Mesh( bGeo, mat );

    return mesh;
} 

function debugLattice( lattice ){
    for( let v of lattice.iterPoints() ){
        Debug.pnt.add( v, 0xffff00, 4 );
    }
}

function debugFaceOrder( grid, fIdx ){
    const color = [ 0xF7716A, 0x81D773, 0x6DA9EA, 0xffffff, 0x00ff00, 0x00ffff, 0xffff00 ];        
    const pnts  = op_FacePoints( grid, fIdx );

    for( let i=0; i < pnts.length; i++ ){
        Debug.pnt.add( pnts[i], color[i], 10 );
    }
}

function debugCell( cell ){
    //const color = [ 0xF7716A, 0x81D773, 0x6DA9EA, 0xffffff, 0x00ff00, 0x00ffff, 0xffff00, 0xff0000 ];
    const color = [ 0xffffff, 0xF7716A, 0x81D773, 0x6DA9EA, 0xffffff, 0xF7716A, 0x81D773, 0x6DA9EA ];
    for( let i=0; i < cell.points.length; i++ ){
        Debug.pnt.add( cell.points[i].pos, color[i], 6 );
    }
}

function debugBVH(){
    const bvh   = Ref.bvh;
    const color = [ 0x81D773, 0x6DA9EA, 0xF7716A, 0x00ff00, 0x00ffff, 0xffff00 ];
    let n, c = 0;
    for( let i=0; i < bvh.nodes.length; i++ ){
        n = bvh.nodes[ i ];
        if( n.isLeaf ){
            Debug.ln.box( n.minBound, n.maxBound, color[c] );

            for( let i=0; i < n.sliceLength; i++ ){
                Debug.pnt.add( bvh.getItemPosition( bvh.data, bvh.partitioned[ i+n.sliceIndex ] ), color[c], 2 );
            }

            c++;
        }else{
            Debug.ln.box( n.minBound, n.maxBound, 0x707070 );
        }
    }
}
// #endregion


// #region BVH INTERSECTION
window.addEventListener( "pointerdown", e=>{
    if( e.button != 2 ) return;

    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    // Compute the Ray and visually draw a line
    const ray = from3JSScreenProjection( new Ray(), e.layerX, e.layerY, App );
    ray.forAABB();

    //Debug.ln.add( ray.posStart, ray.posEnd, 0x00ffff );

    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Ref.bvh.rayIntersect( ray, onIntersect );
} );

function onIntersect( ray, slice ){
    const RNG  = 0.2;
    let min    = Infinity;
    let iMin   = -1;
    let t;

    // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    for( let i of slice ){
        // Loop all the points in the slice & test which
        // one is the closest to the ray
        t = nearPoint( ray,  Ref.bvh.data[ i ].pos, RNG );
        if( t !== null && t < min ){
            min  = t;
            iMin = i;
        }
    }

    // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    // Point interesected
    if( iMin != -1 ){
        Ref.irGrid.togglePointByIdx( iMin );  // Toggle it's state
        rebuild();                            // Rebuild Mesh
        return true;
    }

    return false;
}
// #endregion


// #region BUILDING / RENDERING
function tileLoading( gltf, dic ){
    const mCnt = gltf.json.meshes.length;
    let m, geo, bits;

    for( let i=0; i < mCnt; i++ ){
        if( !gltf.json.meshes[ i ].name.startsWith( 'cliff' ) ) continue;

        m    = gltf.getMesh( i );
        geo  = UtilGltf2.primitiveGeo( m.primitives[ 0 ] );
        bits = TileDictionary.parseBits( m.name );
        dic.addUniqueTile( m.name, bits, geo );
    }
}

function rebuild(){
    Debug.ln.reset();

    // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    let bValue;
    let tiles, tile, uTile;
    let pos = [0,0,0];
    for( let cell of Ref.irGrid.cells ){
        // ------------------------------------
        // If cell value hasn't changed, then skip
        bValue = cell.getBitValue();
        if( cell.userData.bitValue === bValue ) continue;

        cell.userData.bitValue = bValue;

        // ------------------------------------
        // If setting empty space, then hide mesh
        if( bValue === 0 || bValue === 255 ){
            if( cell.userData.mesh ) cell.userData.mesh.visible = false;
            continue;
        }

        // ------------------------------------
        // If tile doesn't exist, then hide any mesh with an error message.
        tiles = Ref.dic.tiles[ bValue ];
        if( !tiles ){
            console.log( 'no tiles found for: ', bValue );
            if( cell.userData.mesh ) cell.userData.mesh.visible = false;
            renderCellframe( cell );
            continue;
        }

        // ------------------------------------
        // Generate mesh tile or replace geometry
        tile  = tiles[ 0 ];
        uTile = Ref.dic.uniqueTiles[ tile.tileId ];
        
        if( cell.userData.mesh ){
            cell.userData.mesh.geometry = uTile.geo;
        }else{
            cell.userData.mat  = new TrilinearLatticeMaterial();
            cell.userData.mat.userData.minBound = Ref.lattice.minBound;
            cell.userData.mat.userData.maxBound = Ref.lattice.maxBound;
            cell.userData.mat.userData.cube     = Ref.latticeDefCube;

            cell.userData.mesh = new THREE.Mesh( uTile.geo, cell.userData.mat );
            cell.userData.mesh.position.fromArray( cell.pos );
            App.add( cell.userData.mesh );
        }

        
        cell.userData.mesh.visible = true;
        cell.userData.mat.userData.setQuat( tile.rotation );
        
        Ref.lattice.fromMarchingCube( cell.localPoints );
        cell.userData.mat.userData.setCube( Ref.lattice.cube.slice( 0 ) );

        //debugCell( cell );
        //debugLattice( Ref.lattice );
    }

    // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    renderPoints();
}

function renderPoints(){
    Debug.pnt.reset();
    for( let p of Ref.irGrid.points ){
        Debug.pnt.add( p.pos, (!p.enabled)?0x707070:0x00ff00, 3 );
    }
}

function renderCellframe( cell ){
    const p = cell.points;
    const col = 0xff0000;

    Debug.ln.add( p[0].pos, p[1].pos, col );
    Debug.ln.add( p[1].pos, p[2].pos, col );
    Debug.ln.add( p[2].pos, p[3].pos, col );
    Debug.ln.add( p[3].pos, p[0].pos, col );

    Debug.ln.add( p[4].pos, p[5].pos, col );
    Debug.ln.add( p[5].pos, p[6].pos, col );
    Debug.ln.add( p[6].pos, p[7].pos, col );
    Debug.ln.add( p[7].pos, p[4].pos, col );

    Debug.ln.add( p[0].pos, p[4].pos, col );
    Debug.ln.add( p[1].pos, p[5].pos, col );
    Debug.ln.add( p[2].pos, p[6].pos, col );
    Debug.ln.add( p[3].pos, p[7].pos, col );
}
// #endregion


// #region Marching Cubes for Irregular Grid
class Point{
    constructor( idx, vIdx, pos ){
        this.idx     = idx;
        this.vertIdx = vIdx;
        this.pos     = pos;
        this.enabled = false;
    }
}

class Cell{
    constructor( idx, fIdx, pos ){
        this.idx         = idx;
        this.faceIdx     = fIdx;   // Ref back to HalfEdge Face
        this.pos         = pos;    // Cell Centroid
        this.points      = null;   // 8 Corners, Needed to compute Bit Value
        this.localPoints = null;   // Local space with centroid as origin, needed for lattice transformation
        this.userData    = {};
    }

    setPoints( ary ){
        this.points      = ary;
        this.localPoints = [];
        for( let p of this.points ){
            this.localPoints.push( vec3_sub( [0,0,0], p.pos, this.pos ) );
        }
    }

    getBitValue(){
        let i   = 0;
        let rtn = 0;
        for( let p of this.points ){
            if( p.enabled ) rtn += MarchingCubes.cornerBit[ i ];
            i++;
        }
        return rtn;
    }

    // getCubePositions(){
    //     return [
    //         this.points[0].pos,
    //         this.points[1].pos,
    //         this.points[2].pos,
    //         this.points[3].pos,
    //         this.points[4].pos,
    //         this.points[5].pos,
    //         this.points[6].pos,
    //         this.points[7].pos,
    //     ];
    // }
}

class IRGrid{
    cells    = [];
    points   = [];
    topology = null;
    constructor(){}

    fromTopology( top, hStep=1.0, cellCnt=3 ){
        let idx       = 0;
        this.topology = top;

        // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        // Build Points
        let o, p, i, pnt;
        for( o of top.vertices ){
            o.userData = [];
            for( i=0; i <= cellCnt; i++ ){
                p       = o.pos.slice( 0 );             // Clone position
                p[ 1 ] += i * hStep;                    // Compute new height position
                pnt     = new Point( idx++, o.idx, p ); // Create Point

                this.points.push( pnt );    // Main Save
                o.userData.push( pnt );     // Temp Save to reference in cell creation
            }
        }

        // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        // Build Cellslet
        const halfStep = hStep * 0.5;
        let cell, pnts, center=[0,0,0];
        
        idx = 0;
        for( o of top.faces ){
            // Get all vertices of the face 
            pnts = op_FaceVertices( top, o.idx );

            // Compute centroid of face
            vec3_add( center, pnts[0].pos, pnts[1].pos );
            vec3_add( center, center, pnts[2].pos );
            vec3_add( center, center, pnts[3].pos );
            vec3_scale( center, center, 0.25 );

            // Build the grid
            for( i=0; i < cellCnt; i++ ){
                pnt       = center.slice( 0 );
                pnt[ 1 ] += halfStep + i * hStep;
                cell      = new Cell( idx++, o.idx, pnt );

                // Point are in CCW, for MC need to order then in CW order
                cell.setPoints([
                    pnts[ 0 ].userData[ i ],    // Bottom face
                    pnts[ 3 ].userData[ i ],
                    pnts[ 2 ].userData[ i ],
                    pnts[ 1 ].userData[ i ],
                    
                    pnts[ 0 ].userData[ i+1 ],  // Top Face
                    pnts[ 3 ].userData[ i+1 ],
                    pnts[ 2 ].userData[ i+1 ],
                    pnts[ 1 ].userData[ i+1 ],
                ]);

                this.cells.push( cell );
                
                // Debug.pnt.add( pnt, 0x00ff00, 4 );
                // for( pnt of cell.points ) Debug.pnt.add( pnt.pos, 0x00ffff, 3 );
            }
        }

        // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        // Cleanup
        for( o of top.vertices ) o.userData = null;

        // for( pnt of this.points ){
        //     Debug.pnt.add( pnt.pos, 0x00ffff, 2 );
        // }

        return this;
    }

    togglePointByIdx( idx ){
        this.points[ idx ].enabled = !this.points[ idx ].enabled;
        return this;
    }
}
// #endregion

</script>
<div style="position:fixed; top:0px; left:0px; padding:5px; background-color:#ffffff20">
    Right click to select or deselect a point on the grid.
 </div>
</body></html>