{"version":3,"sources":["jsdelivr-header.js","/npm/three-octree-vertices@1.0.0/Octree.js"],"names":[],"mappings":"AAAA;AACA;AACA;AACA;AACA;AACA;AACA,UCNY,UAAW,eAEhB,MAAM,OACT,UAAY,IAAI,MAAM,QAEtB,WAAA,CAAY,EAAU,EAAqB,GACnC,aAAoB,MAAM,iBAC1B,EAAW,EAAS,WAAW,SAAS,OAE5C,KAAK,mBAAqB,EAC1B,KAAK,SAAW,EAChB,MAAM,EAAM,EAAS,OAAS,EAG9B,GAFA,KAAK,QAAS,IAAI,MAAM,MAAO,aAAa,GAC5C,KAAK,SAAW,CAAC,CAAE,IAAK,KAAK,OAAQ,SAAU,GAAI,QAAS,KACxD,GAAO,EAEP,YADA,KAAK,SAAS,GAAG,QAAU,MAAM,GAAK,OAAO,KAAI,CAAC,EAAG,IAAM,KAI/D,MAAM,EAAQ,OAAO,SAAS,KAAK,QACnC,IAAK,MAAM,KAAK,EAAO,CACnB,MAAM,EAAI,CAAE,IAAK,EAAG,SAAU,GAAI,QAAS,IAC3C,IAAK,IAAI,EAAI,EAAG,EAAI,IAAO,EACnB,EAAE,cAAc,OAAO,GAAG,UAAU,EAAc,EAAJ,KAC9C,EAAE,QAAQ,KAAK,GAGvB,KAAK,SAAS,GAAG,SAAS,KAAK,EACnC,CAEA,MAAM,EAAQ,KAAK,SAAS,GAAG,SAAS,QACxC,KAAO,EAAM,QAAQ,CACjB,MAAM,EAAO,EAAM,IAAI,GACvB,EAAM,MACF,EAAK,QAAQ,OAAS,IACtB,KAAK,UAAU,GACf,EAAM,QAAQ,EAAK,UAE3B,CACJ,CAEA,SAAA,CAAU,GACN,MAAM,EAAW,KAAK,SAAS,OAAS,EACnC,KAAK,SAAS,OACf,KAAK,SAAW,MAAM,KAAK,KAAK,WAEpC,KAAK,SAAS,KAAK,EAAE,EAAG,EAAE,EAAG,EAAE,GAC/B,IAAI,EAAO,KAAK,SAAS,GAEzB,KAAO,EAAK,SAAS,QACjB,IAAK,MAAM,KAAK,EAAK,SACjB,GAAI,EAAE,IAAI,cAAc,GAAI,CACxB,EAAO,EACP,KACJ,CAGR,EAAK,QAAQ,KAAK,GACd,EAAK,QAAQ,OAAS,KAAK,oBAC3B,KAAK,UAAU,EAEvB,CAEA,MAAA,CAAO,EAAU,GACb,MAAM,EAAU,aAAoB,MAAM,OAAU,EAAW,IAAI,MAAM,OAAO,EAAU,GACpF,EAAM,GACN,EAAQ,KAAK,SAAS,QAC5B,KAAO,EAAM,QAAQ,CACjB,MAAM,EAAO,EAAM,IAAI,GAEvB,GADA,EAAM,MACF,EAAK,IAAI,iBAAiB,GAC1B,GAAI,EAAK,SAAS,OACd,IAAK,MAAM,KAAK,EAAK,SACjB,EAAM,KAAK,QAGf,IAAK,MAAM,KAAK,EAAK,QACb,EAAO,cAAc,OAAO,GAAG,UAAU,KAAK,SAAc,EAAJ,KACxD,EAAI,KAAK,EAK7B,CACA,OAAO,CACX,CAEA,aAAA,CAAc,EAAY,MACtB,MAAM,EAAS,IAAI,MAAM,YAAO,EAAW,GACrC,EAAoB,GAC1B,IAAK,IAAI,EAAI,EAAG,EAAK,KAAK,SAAS,OAAS,EAAG,EAAI,IAAM,EACrD,QAA6B,IAAzB,EAAkB,GAAkB,CACpC,EAAO,OAAO,UAAU,KAAK,SAAc,EAAJ,GACvC,MAAM,EAAQ,KAAK,OAAO,GACpB,EAAW,KAAK,OAAO,GAC7B,EAAM,SAAQ,GAAO,EAAkB,GAAO,GAClD,CAEJ,OAAO,CACX,CAEA,SAAA,CAAU,GACN,MAAM,EAAQ,OAAO,SAAS,EAAK,KACnC,IAAK,MAAM,KAAK,EAAO,CACnB,MAAM,EAAI,CAAE,IAAK,EAAG,SAAU,GAAI,QAAS,IAC3C,IAAK,MAAM,KAAK,EAAK,QACb,EAAE,cAAc,OAAO,GAAG,UAAU,KAAK,SAAc,EAAJ,KACnD,EAAE,QAAQ,KAAK,GAIvB,EAAK,SAAS,KAAK,EACvB,CACA,EAAK,QAAU,EACnB,CAEA,eAAO,CAAS,GACZ,MAAM,EAAQ,GACR,EAAW,EAAI,QAAQ,IAAI,MAAM,SAAW,eAAe,IACjE,IAAK,IAAI,EAAI,EAAG,EAAI,EAAG,IACnB,IAAK,IAAI,EAAI,EAAG,EAAI,EAAG,IACnB,IAAK,IAAI,EAAI,EAAG,EAAI,EAAG,IAAK,CACxB,MAAM,EAAO,IAAI,MAAM,KACvB,EAAK,IAAI,IAAI,EAAG,EAAG,GAAG,SAAS,GAAU,IAAI,EAAI,KACjD,EAAK,IAAI,KAAK,EAAK,KAAK,IAAI,GAC5B,EAAM,KAAK,EACf,CAGR,OAAO,CACX","file":"/npm/three-octree-vertices@1.0.0/Octree.js","sourceRoot":"","sourcesContent":["/**\n * Minified by jsDelivr using Terser v5.37.0.\n * Original file: /npm/three-octree-vertices@1.0.0/Octree.js\n *\n * Do NOT use SRI with dynamically generated files! More information: https://www.jsdelivr.com/using-sri-with-dynamic-files\n */\n","import * as THREE from 'three';\n\nexport class Octree {\n    static _v = new THREE.Vector3();\n\n    constructor(vertices, maxVerticesPerNode = 8) {\n        if (vertices instanceof THREE.BufferGeometry) {\n            vertices = vertices.attributes.position.array;\n        }\n        this.maxVerticesPerNode = maxVerticesPerNode;\n        this.vertices = vertices;\n        const num = vertices.length / 3;\n        this.bounds = new THREE.Box3().setFromArray(vertices);\n        this.subTrees = [{ box: this.bounds, subTrees: [], indices: [] }];\n        if (num <= maxVerticesPerNode) {\n            this.subTrees[0].indices = Array(num).fill().map((_, i) => i);\n            return;\n        }\n\n        const boxes = Octree.boxSplit(this.bounds);\n        for (const b of boxes) {\n            const t = { box: b, subTrees: [], indices: [] };\n            for (let i = 0; i < num; ++i) {\n                if (b.containsPoint(Octree._v.fromArray(vertices, i * 3))) {\n                    t.indices.push(i);\n                }\n            }\n            this.subTrees[0].subTrees.push(t);\n        }\n\n        const trees = this.subTrees[0].subTrees.slice();\n        while (trees.length) {\n            const curr = trees.at(-1);\n            trees.pop();\n            if (curr.indices.length > maxVerticesPerNode) {\n                this.splitCell(curr);\n                trees.push(...curr.subTrees);\n            }\n        }\n    }\n\n    addVertex(v) {\n        const newIndex = this.vertices.length / 3;\n        if (!this.vertices.push){\n            this.vertices = Array.from(this.vertices);\n        }\n        this.vertices.push(v.x, v.y, v.z);\n        let curr = this.subTrees[0];\n        const found = false;\n        while (curr.subTrees.length) {\n            for (const t of curr.subTrees) {\n                if (t.box.containsPoint(v)) {\n                    curr = t;\n                    break;\n                }\n            }\n        }\n        curr.indices.push(newIndex);\n        if (curr.indices.length > this.maxVerticesPerNode) {\n            this.splitCell(curr);\n        }\n    }\n\n    search(position, radius) {\n        const sphere = (position instanceof THREE.Sphere) ? position : new THREE.Sphere(position, radius);\n        const ret = [];\n        const trees = this.subTrees.slice();\n        while (trees.length) {\n            const curr = trees.at(-1);\n            trees.pop();\n            if (curr.box.intersectsSphere(sphere)) {\n                if (curr.subTrees.length) {\n                    for (const t of curr.subTrees) {\n                        trees.push(t);\n                    }\n                } else {\n                    for (const i of curr.indices) {\n                        if (sphere.containsPoint(Octree._v.fromArray(this.vertices, i * 3))) {\n                            ret.push(i);\n                        }\n                    }\n                }\n            }\n        }\n        return ret;\n    }\n\n    mergeVertices(threshold = 1e-4) {\n        const sphere = new THREE.Sphere(undefined, threshold);\n        const verticesToIndices = []\n        for (let i = 0, il = this.vertices.length / 3; i < il; ++i) {\n            if (verticesToIndices[i] === undefined) {\n                sphere.center.fromArray(this.vertices, i * 3);\n                const found = this.search(sphere);\n                const newIndex = Math.min(...found);\n                found.forEach(ind => verticesToIndices[ind] = newIndex);\n            }\n        }\n        return verticesToIndices;\n    }\n\n    splitCell(cell) {\n        const boxes = Octree.boxSplit(cell.box);\n        for (const b of boxes) {\n            const t = { box: b, subTrees: [], indices: [] };\n            for (const i of cell.indices) {\n                if (b.containsPoint(Octree._v.fromArray(this.vertices, i * 3))) {\n                    t.indices.push(i);\n                }\n            }\n\n            cell.subTrees.push(t);\n        }\n        cell.indices = [];\n    }\n\n    static boxSplit(box) {\n        const boxes = [];\n        const halfsize = box.getSize(new THREE.Vector3()).multiplyScalar(0.5);\n        for (let x = 0; x < 2; x++) {\n            for (let y = 0; y < 2; y++) {\n                for (let z = 0; z < 2; z++) {\n                    const curr = new THREE.Box3();\n                    curr.min.set(x, y, z).multiply(halfsize).add(box.min);\n                    curr.max.copy(curr.min).add(halfsize);\n                    boxes.push(curr);\n                }\n            }\n        }\n        return boxes;\n    }\n}\n"]}