3e:null 3f:["$","title",null,{"children":"Spatial data structures: Octrees, BSP, and k-d trees | Tim Henning | Observable"}] 45:T576,md` ## Octrees Octrees are perhaps the simplest of the data structures addressed here. Octrees are a tree data structure where each internal node has eight children. When used to represent spatial data, each node can be thought of as a cubic region in space. Any child nodes of that node divide the space up into eight smaller cubes. If each node stores no extra data, it can be assumed that each region is divided evenly. However, if uneven division is desired, a point can be stored at each node. In this case, the stored point represents the center of the divisions of the parent node. Octrees can be adaptively subdivided to represent a shape, providing the ability to control the resolution. When representing a surface or point cloud, lower subdivisions can be used in areas where there is no data present, and higher subdivisions can be used where data is present up to a desired resolution. This enables a sparse voxelization of the dataset, and reduces the amount of data that needs to be stored. Below is a visualization of an adaptive octree used to store the point set from the Stanford Bunny. Each visualized cube represents a level of the octree that contains a nonzero number of points. The boxes are color coded by their depth in the tree. The tree stores no data in the regions that have no points, which is much more efficient than storing a dense octree up to maximum depth. `46:T6d7,function genOctree(ptlist,min,max,depth){ if(ptlist.length < 5){ return; } if(depth > 10) { return; } var boxes = [[[],[]],[[],[]]]; var ptslists = [[[[],[]],[[],[]]],[[[],[]],[[],[]]]]; var iSplit = (max.x + min.x)/2; var iSZ = (max.x - min.x)/2; var jSplit = (max.y + min.y)/2; var jSZ = (max.y - min.y)/2; var kSplit = (max.z + min.z)/2; var kSZ = (max.z - min.z)/2; for(var i = 0; i < 2; i=i+1){ var iMin = min.x + (i*iSZ); var iMax = iMin + iSZ; for(var j = 0; j < 2; j++){ var jMin = min.y + (j*jSZ); var jMax = jMin + jSZ; for(var k = 0; k < 2; k++){ var kMin = min.z + (k*kSZ); var kMax = kMin + kSZ; var minvec = new THREE.Vector3(iMin,jMin,kMin); var maxvec = new THREE.Vector3(iMax,jMax,kMax); var bx = new THREE.Box3(minvec, maxvec); boxes[i][j].push( bx); } } } if(depth == 0){ scenestate["box"] = boxes; } for( var idx in ptlist){ var pt = ptlist[idx]; var i = (pt.x < iSplit ? 0 : 1); var j = (pt.y < jSplit ? 0 : 1); var k = (pt.z < kSplit ? 0 : 1); ptslists[i][j][k].push(pt); } for(var i = 0; i < 2; i++){ for(var j = 0; j < 2; j++){ for(var k = 0; k < 2; k++){ if(ptslists[i][j][k].length > 0){ var boxcolor; switch(depth % 3){ case 0: boxcolor = 0xff0000; break; case 1: boxcolor = 0x00ff00; break; case 2: boxcolor = 0x0000ff; } scene.add( new THREE.Box3Helper(boxes[i][j][k],boxcolor) ); } genOctree(ptslists[i][j][k],boxes[i][j][k].min,boxes[i][j][k].max,depth+1); } } } }47:[] 43:{"id":"c1bd3dfd7158b30d","slug":"spatial-data-structures-octrees-bsp-and-k-d-trees","title":"Spatial data structures: Octrees, BSP, and k-d trees","thumbnail":"97e09fef4f9fab4aedc76a4076339ecf16112cab123c0d4043bdba99adf10c46","access_level":"public","create_time":"$D2018-10-03T18:32:26.253Z","update_time":"$D2018-10-04T15:02:46.088Z","view_time":null,"first_public_time":"$D2018-12-07T03:21:42.464Z","has_unpublished_edits":null,"fork":false,"stars":7,"starred":false,"owner":{"type":"team","id":"87a3845f24186372","login":"2talltim","name":"Tim Henning","avatar_url":"https://avatars-next.observableusercontent.com/8964efd53fa9def0b85fc46a61a9e09e500d3b7eb2d4da34deb9cc6cc524e398","tier":"starter_2024","bio":""},"version":169,"publish_version":169,"role":null,"authored":false,"authors":[{"type":"individual","id":"8ed5bea0fbd58bf6","login":"2talltim","name":"Tim Henning","avatar_url":"https://avatars-next.observableusercontent.com/8964efd53fa9def0b85fc46a61a9e09e500d3b7eb2d4da34deb9cc6cc524e398","tier":null,"bio":""}],"members":[{"type":"individual","id":"8ed5bea0fbd58bf6","login":"2talltim","name":"Tim Henning","avatar_url":"https://avatars-next.observableusercontent.com/8964efd53fa9def0b85fc46a61a9e09e500d3b7eb2d4da34deb9cc6cc524e398","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":4,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Spatial data structures: Octrees, BSP, and k-d trees","cells":[{"id":0,"value":"md`# Spatial data structures: Octrees, BSP, and k-d trees\n\nOctrees, BSPs, and k-d trees are all ways of organizing 3D data, each with different advantages and disadvantages. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"$45","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"md`\n## k-d Trees\n\nLike Octrees, k-d trees partition space and enable efficient queries on points. The key difference is that each node in a k-d tree partitons space across one plane per level of depth, leading to a binary tree. Each level generates two half spaces that contain its child nodes, which are recursively subdivided. The levels cycle through the axes, e.g. the first level partitions along the x axis, the second along y, etc. The partition is encoded by one of the points in the data set, and is selected by the median of the points in that subpartition. This guarantees a balanced k-d tree. In many cases, this median accounts for a large portion of the runtime of the build. This can be improved by using a median approximation, such as taking the median of a fixed subset of the points, or using a median-of-medians approach. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"visualization_1 = {\n const renderer = new THREE.WebGLRenderer({antialias: true});\n const controls = new THREE.OrbitControls(camera, renderer.domElement);\n renderer.setSize(width, height);\n renderer.setPixelRatio(devicePixelRatio);\n invalidation.then(() => (controls.dispose(), renderer.dispose()));\n controls.addEventListener(\"change\", () => renderer.render(scene, camera));\n while (true){\n renderer.render(scene, camera);\n yield renderer.domElement;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"scene = {\n const scene = new THREE.Scene();\n \n scene.background = new THREE.Color(0xFFFFFF);\n var bunnyGeometry = new THREE.Geometry();\n for( var i in bunny ){\n var clist = bunny[i];\n var pt = new THREE.Vector3(clist[0],clist[1],clist[2]);\n bunnyGeometry.vertices.push( pt );\n }\n var pointsMaterial = new THREE.PointsMaterial( { color: 0x000000, size: 0.03});\n var bunnyPoints = new THREE.Points( bunnyGeometry, pointsMaterial);\n scene.add(bunnyPoints);\n scenestate[\"bunnyPoints\"] = bunnyPoints;\n return scene;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"scenestate = ({})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"octree = {\n var otreeGeo = new THREE.Geometry();\n var base = new THREE.Box3();\n base.expandByObject(scenestate.bunnyPoints);\n base.expandByScalar(0.1);\n scene.add(new THREE.Box3Helper(base));\n genOctree(scenestate.bunnyPoints.geometry.vertices,base.min,base.max,0);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"bunny = (await fetch(\"https://gist.githubusercontent.com/2TallTim/342fb3ab84cadb234326e14948e6263e/raw/87eb1ff4adb4c36f781bf555af0c258c59c068f5/bunny.obj\")).json()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"camera = {\n const fov = 45;\n const aspect = width / height;\n const near = 0.1;\n const far = 1000;\n const camera = new THREE.PerspectiveCamera(fov, aspect, near, far);\n camera.position.set(2, 2, -2)\n camera.lookAt(new THREE.Vector3(0, 0, 0));\n return camera;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"THREE = {\n const THREE = window.THREE = await require(\"three@0.96/build/three.min.js\");\n await require(\"three@0.96/examples/js/controls/OrbitControls.js\").catch(() => {}); //loaders/LoaderSupport.js\n \n await require(\"three@0.96/examples/js/loaders/LoaderSupport.js\").catch(() => {});\n await require(\"three@0.96/examples/js/loaders/OBJLoader2.js\").catch(() => {});\n return THREE;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W47","stdlib":"1"}} 44:"$43:body"