Orbiter 2016 - RC.2

[SolarLiner]

I can understand it more or less, so I guess it's very dumbed down :lol:

One thing I didn't understand though, with plsplit64. It is restricted to splitting an entire planet at once or can it split local imagery as well?

Also a more theoretical question about the first 3 levels: are they all covering entire planets regardless of their radius? Why 3 levels at different texture sizes?

 

[martins]

One thing I didn't understand though, with plsplit64. It is restricted to splitting an entire planet at once or can it split local imagery as well?

No, you can split smaller areas as well. During operation, plsplit64 asks for the latitude and longitude bounds of the bitmap you provide. Even so, the source bitmap has to be at the correct resolution for the desired level. plsplit64 only splits the bitmap, but doesn't do any interpolation. For example, for generating level-4 tiles, the source bitmap must be at resolution 360/1024 degrees per pixel.

Also a more theoretical question about the first 3 levels: are they all covering entire planets regardless of their radius? Why 3 levels at different texture sizes?

A matter of resource management. At very small apparent radius in the render window, it is unnecessary to cover the planet with a 512 x 512 bitmap and a high-resolution mesh. It's essentially just a continuation of the quad-tree LOD theme.

 

[Enjo]

Wine compatible

RC 2 works flawlessly on my Debian Stable with DX9 for RC2. DX7 client exposes some MFD drawing problems, but I think it should be every Linux guy's standard attitude to complain only when every other solution has failed.
The only thing that bothers me is that my own addons don't work (sic!) due to unsatisfied dependencies, but I can resolve this later.

 

[Face]

I have now drafted a document describing the new texture format, including a section on converting base tiles. It probably needs a bit more work, but let me know if this is useful, or if anything is unclear or missing.

I miss the details of the archive format. How is the TOC composed, what compression format is used, etc.

EDIT: From a quick glance that seems to be ZLIB default compression, because the magic header 78 9C is present. Is that correct?

EDITEDIT:

Looks like it works like this:

Byte-Offset|Bit-Length|Type|Description
0|16|String|"TX"
2|16|ushort|Version? 0x1const
4|32|uint|Node list start address 48const
8|32|uint|Another Version? 0x1const
12|32|uint|Archive start address
16|64|ulong|Archive length
24|32|uint|Node count
28|32|uint|Node index for level 1 (or 0xFFFF if gap)
32|32|uint|Node index for level 2 (or 0xFFFF if gap)
36|32|uint|Node index for level 3 (or 0xFFFF if gap)
40|32|uint|Node index for level 4 first root (or 0xFFFF if gap)
44|32|uint|Node index for level 4 second root (or 0xFFFF if gap)
48|32*8|block|Start of node list (k=index*32+48)
k+0|64|ulong|Start of node archive (address=archive_start+value)
k+8|32|uint|Uncompressed length
k+12|32|uint|Next node index quad tree quadrant 1
k+16|32|uint|Next node index quad tree quadrant 2
k+20|32|uint|Next node index quad tree quadrant 3
k+24|32|uint|Next node index quad tree quadrant 4
k+28|32|uint|reserved space filled with garbage?

P.S.: It seems like due to the nature of the quadtree, dummy nodes are produced if there is a gap between the various layers (e.g. base tiles). These nodes point to the same archive entry as the higher resolution tile that caused them, but with zero uncompressed length.

 

[martins]

I miss the details of the archive format. How is the TOC composed, what compression format is used, etc.

EDIT: From a quick glance that seems to be ZLIB default compression, because the magic header 78 9C is present. Is that correct?

EDITEDIT:

Looks like it works like this:

Byte-Offset|Bit-Length|Type|Description
0|16|String|"TX"
2|16|ushort|Version? 0x1const
4|32|uint|Node list start address 48const
8|32|uint|Another Version? 0x1const
12|32|uint|Archive start address
16|64|ulong|Archive length
24|32|uint|Node count
28|32|uint|Node index for level 1 (or 0xFFFF if gap)
32|32|uint|Node index for level 2 (or 0xFFFF if gap)
36|32|uint|Node index for level 3 (or 0xFFFF if gap)
40|32|uint|Node index for level 4 first root (or 0xFFFF if gap)
44|32|uint|Node index for level 4 second root (or 0xFFFF if gap)
48|32*8|block|Start of node list (k=index*32+48)
k+0|64|ulong|Start of node archive (address=archive_start+value)
k+8|32|uint|Uncompressed length
k+12|32|uint|Next node index quad tree quadrant 1
k+16|32|uint|Next node index quad tree quadrant 2
k+20|32|uint|Next node index quad tree quadrant 3
k+24|32|uint|Next node index quad tree quadrant 4
k+28|32|uint|reserved space filled with garbage?

P.S.: It seems like due to the nature of the quadtree, dummy nodes are produced if there is a gap between the various layers (e.g. base tiles). These nodes point to the same archive entry as the higher resolution tile that caused them, but with zero uncompressed length.

Nice reverse engineering :thumbup: I think you are pretty much correct on all points (except byte offs 8, which is a 4-byte bit flag mostly reserved for future use. At the moment, only bit 0 is used which signifies that the contents are compressed). In any case, I'll put more details on the archive format into the next revision of the paper.

 

[Face]

I think you are pretty much correct on all points (except byte offs 8, which is a 4-byte bit flag mostly reserved for future use. At the moment, only bit 0 is used which signifies that the contents are compressed). In any case, I'll put more details on the archive format into the next revision of the paper.

Thanks for the info. I'm currently working on a commandline tool to manage tree archives, called "treeman". ATM it has the same syntax as texpack (except for the flags) and lists the TOC: View attachment treeman.zip

I'm planning to give it regex filtering and extract/update capability. For the update thing: did you implement the reader in Orbiter with some optimization assumptions in mind? E.g. a certain node sorting, placing higher nodes in a branch always behind lower nodes, every node in the list must be reachable, archive in the same order as nodes, and so on...

I'm asking because I don't want tree manipulation to irritate the runtime extraction mechanism.

 

[martins]

Thanks for the info. I'm currently working on a commandline tool to manage tree archives, called "treeman". ATM it has the same syntax as texpack (except for the flags) and lists the TOC: View attachment 14692

I'm planning to give it regex filtering and extract/update capability. For the update thing: did you implement the reader in Orbiter with some optimization assumptions in mind? E.g. a certain node sorting, placing higher nodes in a branch always behind lower nodes, every node in the list must be reachable, archive in the same order as nodes, and so on...

I'm asking because I don't want tree manipulation to irritate the runtime extraction mechanism.

Sounds good. I should mention that the next version of texpack will have an extract function to unpack the entire archive. Essentially the inverse of the packing operation. This was necessary to make the tileedit utility functional. But it sounds like your tool will be much more capable. An update/merge and selective filter option would definitely be useful.

As to your questions:

• The archive _must_ be in the same order as the TOC nodes, since this is used to calculate the compressed size of each data block (compressed size = node[i+1].blockpos - node.blockpos)
  [*]All nodes must be reachable. The only way for Orbiter to find the level/latidx/lngidx designation of a node is by traversing the quadtree. This is the reason why even nodes without data block have a TOC entry, if they bridge the gap to higher-level nodes, as you noted above.
  [*]The order of the nodes in the list is given by recursively stepping through the quadtree. I thought that this would provide a natural order that groups related nodes close together, but I didn't do any rigorous performance tests on it. If your tool will support different ordering strategies, maybe we can do more tests on this. In any case, currently it is true that higher nodes in a branch are always after lower ones, and that the 4 branches emanating from a node are stored consecutively.
  

Edit: another thing: the 4-byte field at position 28 of each TOC entry is currently unused (in fact, the TOC entry size is 28 Byte, but is padded to 32). I was thinking of using those 4 bytes for a timestamp of some sort, so that archives could be selectively updated with new tiles.

 

[Face]

Sounds good. I should mention that the next version of texpack will have an extract function to unpack the entire archive. Essentially the inverse of the packing operation. This was necessary to make the tileedit utility functional. But it sounds like your tool will be much more capable. An update/merge and selective filter option would definitely be useful.

I think it is important to provide a filter option for developers, because always packing/extracting the whole tree gets cumbersome quickly. I'm aware of the cache/files overloading, but I think having it inside the tree might still be an option (advanced) users want.

"Merge" is an interesting idea, though. Do you think people will come up with whole tree archives bundled in addons? Originally I just thought about filtered extraction, then editing the tiles, then filtered updating.

• The archive _must_ be in the same order as the TOC nodes, since this is used to calculate the compressed size of each data block (compressed size = node[i+1].blockpos - node.blockpos)
  

I've already anticipated that. The only other option would be to unpack until the uncompressed length was reached, which would perhaps need a customized inflate algorithm. Thanks for the clarification.

• All nodes must be reachable. The only way for Orbiter to find the level/latidx/lngidx designation of a node is by traversing the quadtree. This is the reason why even nodes without data block have a TOC entry, if they bridge the gap to higher-level nodes, as you noted above.

Reachability was more meant in the sense of superfluous nodes. I.e. if you want to delete some tiles that make up a sub-tree "leaf", and the corresponding nodes are in the middle of the list, you could just cut it off by setting the root to -1. The nodes in question would then be orphaned, not reachable anymore, but still inside the node list. Is this a problem?

• The order of the nodes in the list is given by recursively stepping through the quadtree. I thought that this would provide a natural order that groups related nodes close together, but I didn't do any rigorous performance tests on it. If your tool will support different ordering strategies, maybe we can do more tests on this. In any case, currently it is true that higher nodes in a branch are always after lower ones, and that the 4 branches emanating from a node are stored consecutively.

The idea here was to add new tiles to the tree by means of appending to the list and archive. I.e. even if a node would be in the middle of the list due to its level/lat/lon order, the entry would be added at the end of the list, with the index in the appropriate root updated from -1 to whatever that n+1 is. The tile data would then also be added at the end of the file.

OTOH, having the index and the archive in one file, the append-only strategy is not a huge win, anyway.

Your idea about alternative pack-strategies is interesting, though.

---------- Post added at 13:43 ---------- Previous post was at 13:24 ----------

Edit: another thing: the 4-byte field at position 44 of each TOC entry is currently unused (in fact, the TOC entry size is 44 Byte, but is padded to 48). I was thinking of using those 4 bytes for a timestamp of some sort, so that archives could be selectively updated with new tiles.

That's another good idea! As long as you don't use that for Orbiter's loading mechanism, I could add a function to convert trees to this new format by means of setting e.g. Bit1 of the flag block and put a current date timestamp in it (whatever resolution that could be). Another function/option could then update the tiles automatically, if the file system tile has a newer date than the TOC entry.

 

[martins]

Reachability was more meant in the sense of superfluous nodes. I.e. if you want to delete some tiles that make up a sub-tree "leaf", and the corresponding nodes are in the middle of the list, you could just cut it off by setting the root to -1. The nodes in question would then be orphaned, not reachable anymore, but still inside the node list. Is this a problem?

Not really a problem - just an efficiency issue, since Orbiter loads the entire TOC into memory. If there are too many dead branches, this will start eating up precious memory.

"Merge" is an interesting idea, though. Do you think people will come up with whole tree archives bundled in addons? Originally I just thought about filtered extraction, then editing the tiles, then filtered updating.

Yes, I could imagine that local trees archives might become the standard format for distributing local texture updates via addons, as long as users have a way of merging it into their main archives. Another idea I had was to keep these sub-archives separate and have Orbiter merge them on the fly, but this is further down the road. At the moment I can't see how to make this efficient, since you might have to search multiple archives for a file.

 

[Face]

Yes, I could imagine that local trees archives might become the standard format for distributing local texture updates via addons, as long as users have a way of merging it into their main archives. Another idea I had was to keep these sub-archives separate and have Orbiter merge them on the fly, but this is further down the road. At the moment I can't see how to make this efficient, since you might have to search multiple archives for a file.

I see. So a reliable tool that does just that would actually help here, right?

This is the current progress on treeman: View attachment treeman.zip

It has now regex filtering, 4 verbosity levels (0-3) and a summary command that shows some statistics.

 

[DaveS]

Martin any comments on this: http://www.orbiter-forum.com/showthread.php?p=533013&postcount=201

 

[martins]

=== Please continue the discussion in the RC.3 thread ===

 

[dbeachy1]

Thread closed since RC.3 is now out. :thumbup: