tiling in 3d


Just wondering what thought (or code) has been put into 3d tiling in Cesium? By this I mean if we think of map tiling as being a 2d quadtree, the 3d extension of this would be an octree. Applications I’m thinking of include LOD based serving of data that has a lot of information vertically e.g.

  • point clouds

  • volumetric data

  • meshes with high detail

Also, what are the standards for this? e.g. Is there a 3d extension of WebMercator?



If we use only one data structure here, it would be a bounding volume hierarchy built with Surface Area Heuristics because it makes few assumptions, e.g., number of children and their densities, and it is efficient for dynamic data. I can dig up some recent papers on it if you are interested. I implemented it in our desktop app a while back.

For strictly static data, a kd-tree, again built with Surface Area Heuristics, would be useful in the general case.

An octree can also be useful and is easier to code, but if we code the BVH and/or kd-tree, that might get us 95% there.

My plan has always been to investigate existing JavaScript spatial data structures libraries before coding them, but I am, of course, very open to contributions in this area. I’m happy to discuss in more detail, but I may be at bit slow to respond while I’m at GDC next week.