{"_id":"@brakebein/threeoctree","_rev":"3-054eebe0091c8cc86a05fc800eccbe7c","name":"@brakebein/threeoctree","dist-tags":{"latest":"2.0.1"},"versions":{"2.0.0":{"name":"@brakebein/threeoctree","version":"2.0.0","description":"(sparse + dynamic) 3D spatial representation structure for fast searches in three.js","repository":{"type":"git","url":"git+ssh://git@github.com/Brakebein/threeoctree.git"},"keywords":["three","three.js","octree","3d"],"license":"MIT","bugs":{"url":"https://github.com/Brakebein/threeoctree/issues"},"homepage":"https://github.com/Brakebein/threeoctree#readme","main":"build/threeoctree.js","module":"build/threeoctree.module.js","types":"types/index.d.ts","scripts":{"build":"npx rollup -c && npx tsc -d --emitDeclarationOnly --declarationDir types && npx eslint --fix --quiet --ext .d.ts types"},"devDependencies":{"@rollup/plugin-node-resolve":"^13.0.6","@rollup/plugin-typescript":"^8.3.0","@types/three":"^0.133.1","@typescript-eslint/eslint-plugin":"^5.1.0","@typescript-eslint/parser":"^5.1.0","eslint":"^8.0.1","eslint-plugin-html":"^6.2.0","rollup":"^2.58.0","rollup-plugin-terser":"^7.0.2","three":"^0.133.1","tslib":"^2.3.1","tslint":"^6.1.3","typescript":"^4.4.4"},"peerDependencies":{"three":">=0.130.2"},"gitHead":"c85008ca8ba1c2de3e640ed6e75b1713fa493996","_id":"@brakebein/threeoctree@2.0.0","_nodeVersion":"14.16.1","_npmVersion":"6.14.11","dist":{"integrity":"sha512-KhqkV2wNpdMPSUtXbcl2+Hv6JC300wJ2ldBJj8Y78BG8G6ewzgV/hcd+nWX3AJ+U5Q3FCU2imcAPJ8w7flaGcA==","shasum":"af1cf2b3285915c39bc34f27c4c64d08dc16f291","tarball":"https://registry.npmjs.org/@brakebein/threeoctree/-/threeoctree-2.0.0.tgz","fileCount":14,"unpackedSize":147585,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIDcRBh/hqaUMfmX2eGan/AUU4EhbPB6XzVIpa2Rm0GW3AiEAlE3t62BdQB4HEF5jVd/LcsEqx+eYaS7vZv6ZGQ29uBQ="}]},"_npmUser":{"name":"brakebein","email":"bruschie@hotmail.com"},"directories":{},"maintainers":[{"name":"brakebein","email":"bruschie@hotmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/threeoctree_2.0.0_1634909470694_0.5495303244068479"},"_hasShrinkwrap":false},"2.0.1":{"name":"@brakebein/threeoctree","version":"2.0.1","description":"(sparse + dynamic) 3D spatial representation structure for fast searches in three.js","repository":{"type":"git","url":"git+ssh://git@github.com/Brakebein/threeoctree.git"},"keywords":["three","three.js","octree","3d"],"license":"MIT","bugs":{"url":"https://github.com/Brakebein/threeoctree/issues"},"homepage":"https://github.com/Brakebein/threeoctree#readme","main":"build/threeoctree.js","module":"build/threeoctree.module.js","types":"types/index.d.ts","scripts":{"build":"npx rollup -c && npx tsc -d --emitDeclarationOnly --declarationDir types && npx eslint --fix --quiet --ext .d.ts types"},"devDependencies":{"@rollup/plugin-node-resolve":"^13.0.6","@rollup/plugin-typescript":"^8.3.0","@types/three":"^0.133.1","@typescript-eslint/eslint-plugin":"^5.1.0","@typescript-eslint/parser":"^5.1.0","eslint":"^8.0.1","eslint-plugin-html":"^6.2.0","rollup":"^2.58.0","rollup-plugin-terser":"^7.0.2","three":"^0.133.1","tslib":"^2.3.1","tslint":"^6.1.3","typescript":"^4.4.4"},"peerDependencies":{"three":">=0.130.2"},"gitHead":"53944af3a95b6d7bb4e2568fa8957353046ec087","_id":"@brakebein/threeoctree@2.0.1","_nodeVersion":"14.16.1","_npmVersion":"6.14.11","dist":{"integrity":"sha512-NpjPiWiizuenj5l7ZU+AoXWr3A603Y4t0jD+oiR0V0tvzJnFkJBAO2/4YLYU7TKFM9Zcz4+eoBmzGyokmFsupA==","shasum":"b407f5ab7395c1ab8e1bd5425d0e922069f6344b","tarball":"https://registry.npmjs.org/@brakebein/threeoctree/-/threeoctree-2.0.1.tgz","fileCount":14,"unpackedSize":147535,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.13\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJhzZtmCRA9TVsSAnZWagAAstsP/RPvdb2gFJi5+I3vpR11\nEiTva8L7fMlyaH883mCsglXz8M+zn6boBU4vWMVefbPMfKqglP38+nvzPWCr\nJeASL0zcAnXPrm1FM9bUk/gJy/w6ahG2yALSdjBl0Z2quMF+0VAZqSGPmMMI\nHVwIIGxsvyspHWddT7qYXBoZhQGC/5I2SN1W0okgIxj6l2YTl2igc49H79oh\nthezVl48Z4Kq4h+U+tcRsyx+p3YOpqgH4f+3HG4/31Ih8fCfLxdW3wUN23dL\nAHZAhHzUENJxCHisTYJHfoShkqmliUcexgLFVpCFNvpzVPxccDpES8LxAqeP\nGtwkYzkWCKbVkFoiG6ZtQLy/F5+cBLkw2uW/8bP1V4svfMZx5LC0lEiWt4p3\nk8eAeRZr4OYif1RhmEgHQrhPy8UhfbOuj5NbZoHKKz/z3AH3hcpQoYsI1L0D\nTlauF/3310wC55CrAGyn2lX57G9rPm64sci92IPmIAWnhrZRumjGH45y8Vk0\nnmGeylPBuvq2BZcmHEZoIEx+GF74uOa0PpKypTeDBbfbF2POnjlyIPNmOJze\nkvo316+rS2cxQqDLn2LHgZNU5tlNyRv7/WqwU/eBnkYfZljxuMYghQqxrym2\ndlmfyPCRT7WK+cA38bRr06DfViKOT49YvUfHitlJLlOZ+qclT6plwF5+kUGQ\nsvE2\r\n=mKrj\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDO5pCmNaoOLF7ZALrPQuAfGVjSsAsyYS3wEDj7Vi+HzAIgXPc7VjCOqlak07BYf7P+jB52W5QZge5KZuyaQhVRjQg="}]},"_npmUser":{"name":"brakebein","email":"bruschie@hotmail.com"},"directories":{},"maintainers":[{"name":"brakebein","email":"bruschie@hotmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/threeoctree_2.0.1_1634986219265_0.2524985182404682"},"_hasShrinkwrap":false}},"time":{"created":"2021-10-22T13:31:10.606Z","2.0.0":"2021-10-22T13:31:11.043Z","modified":"2022-04-04T20:21:53.878Z","2.0.1":"2021-10-23T10:50:19.440Z"},"maintainers":[{"name":"brakebein","email":"bruschie@hotmail.com"}],"description":"(sparse + dynamic) 3D spatial representation structure for fast searches in three.js","homepage":"https://github.com/Brakebein/threeoctree#readme","keywords":["three","three.js","octree","3d"],"repository":{"type":"git","url":"git+ssh://git@github.com/Brakebein/threeoctree.git"},"bugs":{"url":"https://github.com/Brakebein/threeoctree/issues"},"license":"MIT","readme":"# threeoctree\r\n\r\n### (sparse + dynamic) 3D spatial representation structure for fast searches\r\n\r\nFully featured search tree for the [three.js WebGL library](https://github.com/mrdoob/three.js).\r\n\r\nSee [demo examples](https://brakebein.github.io/threeoctree)\r\n\r\n### Acknowledgement\r\n\r\nThe original library has been implemented by [Collin Hover](https://github.com/collinhover/threeoctree)\r\nbased on Dynamic Octree by [Piko3D](http://www.piko3d.com/) and Octree by [Marek Pawlowski](pawlowski.it).\r\n\r\nHowever, the original code hasn't been updated for years and has also been [removed from the three.js repo (r100)](https://github.com/mrdoob/three.js/issues/15387#issuecomment-445273451).\r\nThere seems to be [new Octree class](https://github.com/mrdoob/three.js/blob/db7851f4c58cccea0379667af39ac000acf1ae59/examples/jsm/math/Octree.js), which is however not sparse and dynamic and serves only for simple hit tests.\r\n\r\nHence, the aim of this repo is to bring it up-to-date with the latest three.js release (r133).\r\nSupport for `Geometry` was dropped, since it is deprecated and has been [removed from three.js core (r125)](https://github.com/mrdoob/three.js/wiki/Migration-Guide#r124--r125).\r\nInstead, Octree has been updated to only support `BufferGeometry`.\r\nAdditionally, it adds type declarations.\r\n  \r\n## Features\r\n\r\n* handle complete objects ( i.e. 1 center position for entire geometry )\r\n* handle object faces ( i.e. split a complex mesh's geometry into a series of pseudo-objects )\r\n* handle both objects and faces together in a single octree\r\n* overlapping nodes to help sort objects that overlap multiple nodes much more efficiently ( overlap is percentage based )\r\n* split ( 1 larger octree node > up to 8 smaller octree nodes )\r\n* merge ( up to 8 smaller octree nodes > 1 larger octree node )\r\n* expand ( 1 smaller octree node > 1 larger octree node + original smaller octree node + up to 7 other smaller octree nodes ) \r\n* contract ( 1 larger octree node + entire subtree > 1 smaller octree node )\r\n* rebuild ( account for moving objects, trade-off is performance and is not recommended )\r\n* search by position and radius ( i.e. sphere search )\r\n* search by ray using position, direction, and distance/far ( does not include specific collisions, only potential )\r\n* raycast search results using `THREE.OctreeRaycaster`\r\n    \r\n### Needs\r\n\r\n* reworking / optimization of insert and removal ( currently we have to force a transform update in case the object is added before first three update )\r\n* `OctreeRaycaster`: consider backface culling with respect to `material.side` ( `FrontSide | BackSide | DoubleSide` )\r\n\r\n## Usage\r\n\r\nDownload the [latest script](https://github.com/Brakebein/threeoctree/tree/master/build)\r\nand include it in your html after three.js:\r\n\r\n```html\r\n<script src=\"js/three.min.js\"></script>\r\n<script src=\"js/threeoctree.min.js\"></script>\r\n<script>\r\n  const octree = new THREE.Octree();\r\n</script>\r\n```\r\n\r\nUsage with npm and ES modules:\r\n\r\n```\r\nnpm install @brakebein/threeoctree\r\n```\r\n\r\n```javascript\r\nimport { Octree } from '@brakebein/threeoctree';\r\n\r\nconst octree = new Octree();\r\n```\r\n\r\n### Initialize\r\n\r\n```javascript\r\nconst octree = new THREE.Octree({\r\n    undeferred: false, // optional, default = false, octree will defer insertion until you call octree.update();\r\n    depthMax: Infinity, // optional, default = Infinity, infinite depth\r\n    objectsThreshold: 8, // optional, default = 8\r\n    overlapPct: 0.15, // optional, default = 0.15 (15%), this helps sort objects that overlap nodes\r\n    scene: scene // optional, pass scene as parameter only if you wish to visualize octree\r\n});\r\n```\r\n\r\n### Add/Remove Objects\r\n\r\nAdd mesh as single octree object:  \r\n  \r\n```javascript\r\noctree.add( mesh );\r\n```\r\n  \r\nAdd mesh's faces as octree objects:  \r\n  \r\n```javascript\r\noctree.add( mesh, { useFaces: true } );\r\n```\r\n  \r\nAdd mesh's vertices as octree objects:  \r\n  \r\n```javascript\r\noctree.add( mesh, { useVertices: true } );\r\n```\r\n( note that only vertices OR faces can be used, and useVertices overrides useFaces )\r\n\r\nRemove all octree objects associated with a mesh:  \r\n  \r\n```javascript\r\noctree.remove( mesh );\r\n```\r\n\r\n### Update\r\n  \r\nWhen `octree.add( object )` is called and `octree.undeferred !== true`, insertion for that object is deferred until the octree is updated.\r\nUpdate octree to insert all deferred objects **after render cycle** to makes sure object matrices are up-to-date.\r\n\r\n```javascript\r\nrenderer.render( scene, camera );\r\noctree.update();\r\n```\r\n\r\n### Rebuild\r\n\r\nTo account for moving objects within the octree:\r\n\r\n```javascript\r\noctree.rebuild();\r\n```\r\n  \r\n### Search\r\n\r\nSearch octree at a position in all directions for radius distance:  \r\n  \r\n```javascript\r\noctree.search( position, radius );\r\n```\r\n\r\nSearch octree and organize results by object (i.e. all faces/vertices belonging to three object in one list vs a result for each face/vertex):  \r\n  \r\n```javascript\r\noctree.search( position, radius, true );\r\n```\r\n\r\nSearch octree using a ray:  \r\n  \r\n```javascript\r\noctree.search( ray.origin, ray.far, true, ray.direction );\r\n```\r\n\r\n### Intersections\r\n\r\nThe `OctreeRaycaster` extends the `THREE.Raycaster` class by two methods to help use the search results:\r\n`intersectOctreeObjects()` and `intersectOctreeObject()`.\r\nIn most cases you will use only the former:  \r\n  \r\n```javascript\r\nconst octreeResults = octree.search( raycaster.ray.origin, raycaster.ray.far, true, raycaster.ray.direction );\r\nconst intersections = raycaster.intersectOctreeObjects( octreeResults );\r\n```\r\n\r\nIf you wish to get an intersection from a user's mouse click, this is easy enough:\r\n\r\n```javascript\r\nfunction onClick ( event ) {\r\n    \r\n    const mouse = new THREE.Vector2(\r\n        ( event.pageX / window.innerWidth ) * 2 - 1,\r\n        -( event.pageY / window.innerHeight ) * 2 + 1\r\n    );\r\n\r\n    // set raycaster\r\n  \r\n    const raycaster = new THREE.OctreeRaycaster();\r\n    raycaster.setFromCamera( mouse, camera );\r\n\r\n    // now search octree and find intersections using method above\r\n  \r\n    const octreeResults = octree.search( raycaster.ray.origin, raycaster.ray.far, true, raycaster.ray.direction );\r\n    const intersections = raycaster.intersectOctreeObjects( octreeResults );\r\n    \r\n    // ...\r\n    \r\n}\r\n```\r\n\r\n### TypeScript usage\r\n\r\nMake use of generics in TypeScript: \r\n\r\n```typescript\r\nimport { BoxGeometry, MeshBasicMaterial } from 'three';\r\nimport { Octree } from '@brakebein/threeoctree';\r\n\r\nconst octree = new Octree<Mesh<BoxGeometry, MeshBasicMaterial>>();\r\n\r\nconst mesh = new Mesh( new BoxGeometry(), new MeshBasicMaterial() );\r\n\r\noctree.add( mesh );\r\n\r\n// ...\r\n\r\nconst octreeResults = octree.search( position, radius, true );\r\n\r\noctreeResults[0].object // -> Mesh<BoxGeometry, MeshBasicMaterial>\r\n```\r\n","readmeFilename":"README.md"}