loshjawrence
commented
5 years ago @kring @tfili Curious what your thoughts are on this approach if you have the time.
Closed loshjawrence closed 2 years ago
loshjawrence
commented
5 years ago @kring @tfili Curious what your thoughts are on this approach if you have the time.
loshjawrence
commented
5 years ago Some notes on BCRS and CRS Compressed row format(ADD refine), Block compressed row format(REPLACE refine)
BCRS:
CRS: Same as above but 1x1 block
As mentioned above, due to our ability to have full row of 0's (matrices with row of zero's in mathematics means it has no inverse), This means you end up specifying the row and column for every element (repeated index pointer to indicate that row has nothing on it)
loshjawrence
commented
5 years ago The min number of bits on a level should be a byte to make access a little easier. For quad this effects levels 1 and 2, for oct this effects level 1
TODO: add cols for best and worst case compressed. try to compare with binary bounding box best and worst case (and points along the way)
Quadtree
| Subtree Levels | Tiles last level | Subtree bits | UInt8Array length | KB |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0.0001 KB |
| 2 | 4 | 5 | 2 | 0.0006 KB |
| 3 | 16 | 21 | 4 | 0.003 KB |
| 4 | 64 | 85 | 12 | 0.01 KB |
| 5 | 256 | 341 | 44 | 0.04 KB |
| 6 | 1024 | 1365 | 172 | 0.17 KB |
| 7 | 4096 | 5461 | 684 | 0.67 KB |
| 8 | 16384 | 21845 | 2732 | 2.7 KB |
| 9 | 65536 | 87381 | 10924 | 10.7 KB |
| 10 | 262144 | 349525 | 43692 | 42.7 KB |
Octree
| Subtree Levels | Tiles last level | Subtree bits | UInt8Array length | KB |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0.0001 KB |
| 2 | 8 | 9 | 2 | 0.001 KB |
| 3 | 64 | 73 | 10 | 0.009 KB |
| 4 | 512 | 585 | 74 | 0.07 KB |
| 5 | 4096 | 4681 | 586 | 0.57 KB |
| 6 | 32768 | 37449 | 4682 | 4.6 KB |
| 7 | 262144 | 299593 | 37450 | 36.6 KB |
| 8 | 2097152 | 2396745 | 299594 | 292.6 KB |
| 9 | 16777216 | 19173961 | 2396746 | 2340.6 KB |
| 10 | 134217728 | 153391689 | 19173962 | 18724.6 KB |
kring
commented
5 years ago Looking at the layer.json for terrain,it seems it would be pretty expensive (at the very least, unpredictable from tileset to tileset) to check if a range d/x/y index is available in the tree on the deeper levels where there's a ton of bounding box fragmentation.
Have you looked at TileAvailability.js? It exists primarily to do this query quickly. I wrote in the documentation that its runtime is log(n) in the number of availability rectangles. And in the PR I said it took 1.2 seconds to do a million random queries on my system at the time.
Still, that might not be fast enough. Certainly a constant-time lookup would be awesome!
re: BCRS:
NOTE: this is not more efficient than index ranges in terms of size, but it is better in terms of lookup
Are you sure? Using bisection for (i) and (ii) I think you're still looking at logarithmic time in rows+columns, as opposed to the rectangle approach which is logarithmic in the number of rectangles (of which there should be fewer in non-crazy cases). Probably much better memory locality with CRS/BCRS though, because there's a lot of pointer chasing in the approach in TileAvailability.js. So maybe CRS/BCRS would be faster anyway.
I think one big advantage from a spec perspective of moving away from the rectangles is that they're a total PITA to compute (i.e. for inclusion in layer.json). I know when I originally implemented the rectangle computation for terrain, it was both difficult to code and also definitely not the minimal number of rectangles possible. Not sure if you guys ended up finding a better algorithm after I left.
So my gut (without having done a lot of analysis) is that having an extra ~42.7KB in every tile (or would the availability be separate from the tile payload? I guess so) at levels 0, 9, and 18 would not be prohibitive in terms of transfer time or memory on the client. Even with a few hundred of them in memory you're only talking about tens of megabytes. I'm slightly more worried about the server needing to store this extra data for every tile at these levels, but I think even that won't add up to anything crazy. It'd be useful to count the number of tiles at these levels in Cesium World Terrain and see what it adds up to.
In general I think favoring more levels is worthwhile, within reason, because an extra 42.7KB is barely noticeable even on a relatively slow connection, but an extra request/response cycle hurts even on very fast connections. 10 levels feels about right to me for the quadtree, probably more like 7 for an octree. But it's easy enough to experiment with.
I didn't quite understand your point about updates, though, i.e:
With the with exhaustive description of availability (or any method of description of availability), it becomes really expensive as you go down the tree, so 10 levels is a bad idea for this scheme. For example, you can represent 5 levels of availability in only 0.04KB or 341 bits. You would need to update twice as frequently as the 10 level subtree but the size is 1000x smaller. The cost to update the client-side data structures is also really cheap and can be done much faster. So there is likely a goldilocks zone for subtree size (no matter what scheme you use) that balances size of request/number of requests/cost to update client data structures.
So I could be missing something.
kring
commented
5 years ago For tile storage (instead of tree), we could have a corresponding array of 3dtiles array init to undefined and spots that have availability would have an actual tile.
This is a really interesting idea. In general I think terrain and probably 3D Tiles rendering would benefit immensely from a memory data-oriented approach and less pointer chasing. It's quite separate from the availability issue though, right?
loshjawrence
commented
5 years ago pretty expensive
This was more of a relative statement (against array lookup) than an outing of layer.json, sorry for the confusion. It's clear that terrain is already quite fast using 2d index bounding boxes. For crs/bcrs it's implied that things are sorted from the way the algo is specified and there's really only one way the data can turn out. For layer.json, I wasn't sure it sorting/bounding box formation would be in the spec or if you would have to do something client side to clean up a low-quality third party layer.json (bounding boxes aren't as efficient as they could be, box order could be better). So there was an addition layer of concern on the impl side of things.
one big advantage from a spec perspective of moving away from...
After having worked with uber on trying to get a loader up and running, I agree that implementation is really important for a spec as well, so that's definitely part of the motivation to try to get everything in array form, in addition to potential speed-ups existing render / analysis algos.
having an extra ~42.7KB in every tile (or would the availability be separate from the tile payload? I guess so)
The later, yea. The raw bit array mipmap of a subtree would replace the layer.json. The fixed size subtrees only exist where there are places to continue on from the upper subtree, so the whole tree isn't fully specified. Smaller subtrees will give you less waste on the server in terms of storage (a smaller subtree tree terminates sooner in areas vs a larger subtree tree) but you'll have to pull them in more frequently. Though even if they are large, these bit arrays compress down a lot.
By "update" I mean requesting more subtree chunks and then initializing 3dtiles arrays when they come back (calling new in spots that have availability).
an extra request/response cycle hurts even on very fast connections
I'm sure you're 100% correct in that round trip latency is what dominates in terms of updating the view of the tree and you don't want to be doing this sort of thing that often. This was something I wanted to test first hand (since I wasn't totally sure of) by trying different subtree sizes. Smaller subtree sizes would help having a lighter cpu/gpu memory footprint for mobile so it was something I wanted to verify.
It's quite separate from the availability issue though, right?
Yes, this is just client side once you get the subtree array chunk back. Just build a corresponding subtree array chunk of tiles and init in places where they exist.
loshjawrence
commented
5 years ago @kring Also, curious what you think about https://github.com/AnalyticalGraphicsInc/3d-tiles/issues/383 (second comment). It is a separate/less immediate effort but could be really powerful if you could pre-bake analysis measurements during tiling and fold it into this metadata system. Maybe fold time-dynamic features into these metadata/availability ideas.
loshjawrence
commented
5 years ago CWT 10 levels, zipped layer.json 3.4KB subtrees total (1 for each head) 1.61 KB
ptrgags
commented
2 years ago Implicit availability is currently implemented as bitstreams using Morton order, divided into fixed-size "subtrees" (see https://github.com/CesiumGS/3d-tiles/tree/main/extensions/3DTILES_implicit_tiling#subtrees)
I opened https://github.com/CesiumGS/3d-tiles/issues/572 for further discussion on compression schemes so we can close this one.
Availability idea for: https://github.com/AnalyticalGraphicsInc/3d-tiles/issues/92
Currently, availability for the prototype implicit tiling is a direct copy of terrain's availability which is an array holding 2d xy bounding boxes(start and end indices) for all the indices that are available on a certain level. In the common case(worst case being checker pattern of availability), it lets you go pretty deep in the tree before json size becomes too much.
Looking at the layer.json for terrain,it seems it would be pretty expensive (at the very least, unpredictable from tileset to tileset) to check if a range d/x/y index is available in the tree on the deeper levels where there's a ton of bounding box fragmentation.
If you want to get away from trees and deal only with availability, this kind of a check would be a workhorse of all the client side code that would want to deal with the implicit tree (traverse, vis/culling, ray, give me highest LOD tiles in boundingVolume, basically any thing dealing with the structure of the tree, (occlusion culling?)).
If this check could move more towards an array lookup that would be best (fastest lookup, impl is simple (after working with Uber, this is very important for the spec to be able to spread), tilers/loaders don't have to care about optimizing/sorting availability ranges to get a "yes/no" without checking every single one).
Something that could get us there could be something like a megatexture approach where we only pull-in a tiny portion of tiles from the megatexture that we would need at any one time. Megatextures are common in giant open-world games. You have a gigantic image that's all of your data and keep this on disk. This image is split this into tiles. You have another image that is your page table where each pixel of this page table corresponds to a tile in the megatexture. The pixel stores the offset into your physical fixed size cache of tiles that you have active. Not saying this is how we should do it but that's my understanding of how it's typically done.
We can package up availability in subtrees of 10 levels (or whatever range is best). Every subtree of 10 levels could be a bit array mipmap or png mipmap. Could do morton but if we want to keep the impl code as straight forward as possible, I guess we could/should avoid morton. Every cell in the subtree is accounted for in this subtree mipmap. Given that pngs are about 33% of bmps the size of a subtree png mipmap would be around 14.7KB. Maybe zipped bitmaps are fine too (the raw bit array mipmap would be around 42.7KB. It's my understanding that zipped bitmaps get decently compressed.
For comparison, the first layer.json for cesium world terrain is 49KB raw, 3.4KB compressed (if you keep it 10 levels for a fair fight with the above). However, going with 8 level subtrees would allow exhaustive bit array mipmaps to win out over layer.json approach: 2.7KB vs 3.9KB
With the with exhaustive description of availability (or any method of description of availability), it becomes really expensive as you go down the tree, so 10 levels is a bad idea for this scheme. For example, you can represent 5 levels of availability in only 0.04KB or 341 bits. You would need to update twice as frequently as the 10 level subtree but the size is 1000x smaller. The cost to update the client-side data structures is also really cheap and can be done much faster. So there is likely a goldilocks zone for subtree size (no matter what scheme you use) that balances size of request/number of requests/cost to update client data structures.
Airing towards a smaller subtree size is better anyway since you only need a few subtrees of the entire tree at any one time and the subtrees have less waste (ratio of 0's / totalBits).
Comparing sizes of different exhaustive subtree availabilities when represented as bit array mipmaps
Only cells on the last level of the subtree that have a 1 would have another subtree available for requesting, 0 tiles would not have an external availability. the availability uri could be some predictable thing like
external/x/y/zas opposed to the tile uri namespace which isx/y/z(or whatever the axis order ends up being)Checking availability for any cell in the tree, if you want to skip though the tree say at level 30, if you get a 404 it just means that subtree doesn't exist so the cell doesn't exist (obviously check any existing unavailability before skipping through the tree to request for external availability).
Why image (or bit array mip interpreted as image)? Leverage the convenience of textures. likely blocky availability, can leverage lossless image compression. could migrate algos to the gpu, take last frames results. Debugability. Can view the image in f12 network tab, can convert to black white and view, can overlay textures on tiles. use layers of images together to mask results (mask output of operations dealing with the tree structure i.e. just assume full availability to simplify impl and speed then mask the results).
octree's subtree bit array mipmap sizes would be:
For tile storage (instead of tree), we could have a corresponding array of 3dtiles array init to undefined and spots that have availability would have an actual tile. This size of this array for the subtree of 10 levels would be 2.8MB quad, 1,227MB oct while the cost of initializing a 3dtiles subtree of 5 levels is 2.7KB quad, 37KB oct. If the subtree is full then you need all this, otherwise it's could be quite wasteful with larger subtrees. In either case, it's very straightforward and efficient for marching around the tree arbitrarily and doing random access. This could be BCRS or CRS to save some room but it would lose out on impl simplicity (requires multiple indirection lookups) and no longer 1to1 mapping between availability structure and tile storage data structures.