3e:null 3f:["$","title",null,{"children":"3D Tiles 1.1 - Implicit tiling | Geodan research | Observable"}] 45:T612,Recently the 1.1 version of 3D Tiles was released. One of the new features is 'implicit tiling'. When using this feature the spatial data is divided in a regular pattern (quadtree for 2D or octree for 3D). The advantage of this method is that we no longer have to specify the location and bounds of each tile (in large/multiple tileset.json files). One of the more complex aspects of Implicit Tiling are the 'availability bitstreams'. These bitstreams are used to indicate where content can be found (using bit '1') or where nothing can be found (using bit '0'). A simple availability bitstream could look like '01100' for 2 levels in a quadtree. The first bit (value '0') means there is no content on level 0, so the client should not request anything for tile (0,0,0). The following 4 bits ('1100') means there is content on level 1 for tile (1,0,0) and (1,1,0) but not for (1, 0, 1) and (1,1,1). To transform from a 2D or 3D matrix to a 1 dimensional array the Z-order curve/Morton code is used (see https://en.wikipedia.org/wiki/Z-order_curve). In this notebook we compute the availability bitstream in a real world data scenario. As input data we use a SpatiaLite database with US building footprints (https://wiki.openstreetmap.org/wiki/Microsoft_Building_Footprint_Data), specific the Dover dataset (https://1drv.ms/u/s!AqWv0F0N63JkgQqO6E9e2kI28R16). Javascript library Leaflet is used to visualise the results. For more information about Implicit Tiling see https://github.com/CesiumGS/3d-tiles/tree/draft-1.1/specification/ImplicitTiling 46:T442,async function getTiles(db, tiles, tile){ var buildingsinBbox = await GetFeatureCountInBBox(db, tile.bbox); if(buildingsinBbox == 0){ tile.available = 0; tile.features=buildingsinBbox; tiles.push(tile); } else if (buildingsinBbox > maxFeaturesPerTile){ for (var x = 0; x < 2; x++) { for (var y = 0; y < 2; y++) { var dx = (tile.bbox.max[0] - tile.bbox.min[0]) / 2; var dy = (tile.bbox.max[1] - tile.bbox.min[1]) / 2; var xstart = tile.bbox.min[0] + dx * x; var ystart = tile.bbox.min[1] + dy * y; var xend = xstart + dx; var yend = ystart + dy; var bboxQuad = {min:[xstart,ystart],max:[xend,yend]}; var new_tile = {z:tile.z + 1, x:tile.x * 2 + x, y:tile.y * 2 + y}; new_tile.bbox = bboxQuad; await getTiles(db, tiles, new_tile); } } } else { tile.available=1; tile.features=buildingsinBbox; tiles.push(tile); } return tiles; }47:[] 43:{"id":"45b122f324c4b4a3","slug":"3d-tiles-1-1-implicit-tiling","title":"3D Tiles 1.1 - Implicit tiling","thumbnail":"54941c776c8fc0e11de759af8651f46ec7af62f2530b5d7b701119e1016d5623","access_level":"public","create_time":"$D2022-07-08T09:19:38.479Z","update_time":"$D2022-08-01T08:38:24.052Z","view_time":null,"first_public_time":"$D2022-07-25T16:13:12.312Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"e51ebae4171835c5","login":"geodan","name":"Geodan research","avatar_url":"https://avatars-next.observableusercontent.com/6813a9eccdca19e5c7220422908591478b06a880d6e666b49ba801798927a67f","tier":"pro","bio":"To boldly geo where no-one has geo'd before"},"version":419,"publish_version":419,"role":null,"authored":false,"authors":[{"type":"individual","id":"c52bcd9f9cd3472b","login":"bert","name":"Bert Temme","avatar_url":"https://avatars-next.observableusercontent.com/2ca833054fb8f5092f21ca331ed10bbbb81bb1927069b7c63ccf53fde969ab51","tier":null,"bio":""}],"members":[{"type":"team","id":"e51ebae4171835c5","login":"geodan","name":"Geodan research","avatar_url":"https://avatars-next.observableusercontent.com/6813a9eccdca19e5c7220422908591478b06a880d6e666b49ba801798927a67f","tier":"pro","role":"editor"},{"type":"individual","id":"c52bcd9f9cd3472b","login":"bert","name":"Bert Temme","avatar_url":"https://avatars-next.observableusercontent.com/2ca833054fb8f5092f21ca331ed10bbbb81bb1927069b7c63ccf53fde969ab51","tier":null,"role":"viewer"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"titling":"auto","title":"3D Tiles 1.1 - Implicit tiling","cells":[{"id":0,"value":"# 3D Tiles 1.1 - Implicit tiling","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":349,"value":"$45","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":292,"value":"# Database","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":355,"value":"As test database a SpatiaLite database is used, this is an SQLite database with spatial functions. It's created using GDAL command line tool 'ogr2ogr' from the download shapefile:\n\n$ ogr2ogr -f sqlite -dsco spatialite=yes delaware.sqlite bldg_footprints.shp","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":22,"value":"spatialite_db = \"https://bertt.github.io/spatialite_sample/delaware.sqlite\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":294,"value":"# Data inspection","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":357,"value":"First inspect the data, there is a table ('bldg_footprints') with 22532 building footprints and height attribute.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":73,"value":"buildings = await db.exec('SELECT GEOMETRY from bldg_footprints').get.objs","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"map = {\n const container = html`

`;\n yield container;\n const map = L.map(container);\n L.tileLayer(\"https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png\", {\n attribution: \"© OpenStreetMap contributors\"\n }).addTo(map);\n\n const defaultStyle = { \n color: 'red', \n weight: 5\n };\n\n quadTiles.forEach(tile => \n {\n if(tile.available==1){\n var bbox = tile.bbox;\n var f = {\n \"type\": \"Polygon\",\n \"coordinates\": [[\n [bbox.min[0], bbox.min[1]], \n [bbox.max[0], bbox.min[1]],\n [bbox.max[0], bbox.max[1]],\n [bbox.min[0], bbox.max[1]],\n [bbox.min[0], bbox.min[1]]\n ]]};\n L.geoJSON(f, {style: defaultStyle}).addTo(map);\n }\n });\n\n let envLayer = L.geoJson(env,\n { \n weight: 5, \n color: '#432'\n })\n .addTo(map);\n map.fitBounds(envLayer.getBounds());\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":130,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":299,"value":"# Get Morton indices","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":388,"value":"To calculate the availability bitstream, we loop through all levels and determine the Morton index per level.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":331,"value":"maxZ = Math.max.apply(Math, quadTiles.map(function(o) { return o.z; }))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":209,"value":"width = Math.sqrt(Math.pow(4, maxZ));","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":391,"value":"Summarized per level in a table the Morton index looks like:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":223,"value":"levelData = getSummaryTable(quadTiles);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":233,"value":"Inputs.table(levelData, {align:{z:\"left\", cells:\"left\", available:\"left\", morton: \"left\"}, width: {z:2,cells:2,available:10,morton:180}})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":395,"value":"To get the availability bitstream for all levels we concatenate:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":288,"value":"mortonAllLevels = getMorton(levelData);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":282,"value":"function getMorton(levelData) {\n var morton = \"\";\n levelData.forEach(level => { \n morton = morton + level.morton;\n });\nreturn morton;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":220,"value":"function getSummaryTable(tiles){\n var levels = [];\n var maxZ = Math.max.apply(Math, quadTiles.map(function(o) { return o.z; }));\n\n for(let i=0;i<=maxZ;i++){\n let available = 0;\n var cells = Math.pow(4, i);\n var morton = '0'.repeat(cells);\n quadTiles.forEach(tile => \n {\n if(tile.z==i && tile.available==1) {\n available++;\n var index= getMortonIndex(tile.x,tile.y);\n morton = morton.substring(0, index) + '1' + morton.substring(index + 1);\n }\n });\n var level = {z:i,cells:cells, available: available, morton};\n levels.push(level);\n }\n return levels;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":267,"value":"function getMortonIndex(x,y){\n return (insertOneSpacing(x) | (insertOneSpacing(y) << 1)) >>> 0;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":277,"value":"\n\nfunction insertOneSpacing(v) {\n v = (v ^ (v << 8)) & 0x00ff00ff;\n v = (v ^ (v << 4)) & 0x0f0f0f0f;\n v = (v ^ (v << 2)) & 0x33333333;\n v = (v ^ (v << 1)) & 0x55555555;\n return v;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"async function GetFeatureCountInBBox(database, bbox){\n var sql = 'SELECT count(GEOMETRY) from bldg_footprints where MBRIntersects(BuildMBR(' + bbox.min[0] + ', ' + bbox.min[1] + ',' + bbox.max[0] + ',' + bbox.max[1]+ '), GEOMETRY)';\n var featureCount = await database.exec(sql).get.first;\n return featureCount;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":83,"value":"function toFeature(feature){\n let f= {\"type\": \"Feature\"}\n f.geometry = feature.GEOMETRY\n return f\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":327,"value":"# Conclusion","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":402,"value":"With some computation we can get the availability bitstreams using real word data. The availability bitstream is used in the Implicit Tiling 'subtree' file so a client knows where to find content and where nothing is available.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":14,"value":"# References","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":336,"value":"## SpatiaLite","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":16,"value":"SPL = import(\"https://cdn.skypack.dev/spl.js@0.1.0-beta.3?min\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"spl = SPL.default()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"db = fetch(\n spatialite_db\n)\n .then((response) => response.arrayBuffer())\n .then((d) => spl.db(d))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":334,"value":"## Leaflet","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":42,"value":"L = {\n const L = await require(\"leaflet@1/dist/leaflet.js\");\n if (!L._style) {\n const href = await require.resolve(\"leaflet@1/dist/leaflet.css\");\n document.head.appendChild(L._style = html``);\n }\n return L;\n}\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"