Hierarchical pcube representation

[JATothrim]

Following is just me thinking about the polycube representation and how an pcube is computed.
(sorry if the grammar is bad/gibberish as I'm not too good writing complex sentences in english... 🥲 )

An tree (hierarchical representation) is an compact way to represent the polycubes:

When an base pcube N is expanded to N+1 etc. we count the index of the permutation:

1. Generate unique list of candidate expansions for the base pcube.
2. Start with single candidate in the permutation list.
   This is the "normal way" N+1 expansion of pcube.
3. Process all unique permutations of the expansion list.
   For N+1 expansion the permutation index is just the candidate's array index.

Whats new is the N+2, N+3, etc. expansion of an base pcube:

• N+2: Generate all unique permutations with two candidates.
  Each unique shuffle increments the permutation index.
• N+3 expansion is all unique permutations with three candidates.
• ...
• The final base pcube expansion is simply using all the candidates.

Above process gives unique "index" value to all possible base pcube expansions:
Since we are computing just N+1 the expansions beyond this are not needed until later.
(Note: if we remember the last permutation state for base pcube N+2,
we can continue the enumeration from where we left it for future N+3 etc.)

Now that base pcube expansions have an well defined "index" encode pcube(s) with following:

• Some kind of reference to the base pcube
• the used permutation index value.
  Note that this value will grow with the count of candidate combinations.
• the rotation's index. (an number of [0, 23] )

This scheme does mean that to get the actual coordinate data we have to (re-)compute it using
the expansion process again:

1. Start with already rotated base pcube.
2. Compute expansion candidate list for this pcube.
3. Expand using the permutation index.
   This an hard problem: If we have to start from zero this would take an long time.
   Better options would be to selectively save the permutation state+index and continue from nearest check point.
4. Rotate the expanded pcube using the rotation index.
5. Repeat until we have pcube of required N

The hierarchical representation can be collapsed this way into the canonical form. (sorted coordinate list)

The reference to the base pcube de-duplicates it for all pcubes derived from it and this forms an tree structure.
The trick for saving memory is that the base pcube(s) should be loaded from the disk cache on demand
so N-1 part of the pcube(s) is kept out of memory.
Draw back is that the disk cache system needs to support finding any particular pcube and we have to store the pcube tree structure on disk.

Does any above idea(s) make sense ?

[nsch0e]

1. Generate unique list of candidate expansions for the base pcube.

This is just the union of all the cubes in the base polycube shifted +/-1 for all axis?
Is this the "expansion list"?

• Start with single candidate in the permutation list.

I think I struggle with the term "permutation".
what is permuted: the base cube or the expansion list?

The final base pcube expansion is simply using all the candidates.

I think we loose the cases where with each expansion the shape is increased.
Example:

base cube:

 ##

expansion list:
 ++
+..+
 ++

missing for N+2:
 ##++
missing for N+3:
 ##+++
...

[JATothrim]

This is just the union of all the cubes in the base polycube shifted +/-1 for all axis?
Is this the "expansion list"?

I'm answering quite late and I'll try give somekind of answer. Shortly: It is.

I think I struggle with the term "permutation".
what is permuted: the base cube or the expansion list?

My bad, I struggled at time what to name this process exactly...
Better wording could be "configuration index of adjacent expansions".
The cubes picked are shuffled such that for "N+2" expansion we pick two cubes from the base pcube expansion list at time. The "permutation" is the placement configuration of those two picked cubes, and the idea is the each such configuration gets an index value (the "permutation index").

 ##
expansion list:
 ++
+..+
 ++
missing for N+2:
 ##++
missing for N+3:
 ##+++

You have a good point here. I didn't think about the process how to get all the cases up to N...
The Answer is that ##++ cannot be made with single expansion with this process. Getting #### from ## requires chaining two expansions. N+2 expansion of ## can only include cubes that are immediately adjacent to the base pcube. The search process would have to minimize the number of chained expansions when trying to get up to N cubes.
I try give some ASCII art examples of the "higher" expansions... (dot is non-picked cube, + is picked)

 ++
.##.  --> permutation "0"
 ..
 .+
.##+  --> permutation "1"
 ..
 ..
.##+  --> permutation "2"
 .+
 ..
.##.  --> permutation "3"
 ++
 ..
+##.  --> permutation "4"
 +.
 +.
+##.  --> permutation "5"
 ..
 +.
.##+  --> permutation "6"
 ..
 .+
.##.  --> permutation "7"
 .+

and the list goes on. The idea is that all adjacent the expansion configurations have an index value associated with them. We then have an function that reproduces that configuration from the base pcube and the index.
N+1 expansions of ## in 2D go only up to 6:

 +.
.##.  --> permutation "0"
 ..
 .+
.##.  --> permutation "1"
 ..
 ..
.##+  --> permutation "2"
 ..
 ..
.##.  --> permutation "3"
 .+
 ..
.##.  --> permutation "4"
 +.
 ..
+##.  --> permutation "5"
 ..

To encode a ### line by expanding from ## is adding either 2 or 5 configuration to it from above list. To make longer line new expansion list is computed again and configuration indexes are picked that make ####. (for lines there are exactly two such expansions) Lines are thus bit hard to compute and require chaining the expansions to get up to the number of cubes we want.
Note that ### has shorter possible chain: N+2 expansion from just #
I might try write an 2D version of this and see what the process would be to enumerate all cases up to N.

[nsch0e]

Ok, I can follow 😊 so each permutation is a subset of the expansion list with k elements for N+k. So there should be (E choose k) permutations and E is size of expansion list.

The whole thing is a representation proposal so we are trying to compress the overall representation of a set of cubes? Or is this the base for a new algorithm which enumerates all cubes?

For the compression side: we should consider how much space is needed for a permutation index and also the reference a base cube.

For a straight line of 16 cubes there are 4 * 16 + 2 = 66 expansions.
So worst case permutation list should have 66 choose 33 entries.
Which is really big but also a N+33 step. I don't know if always all expansion steps should be done. Just trying to add my thoughts.

==> a 64 should be able to represent every subset of the expansion list (for N=16)

For the base cube reference a 64-bit integer should be sufficient?!
So approx. 16 bytes / cube.

Perhaps you have other ideas how to compress this more, but I fear that this will not really compress the representation.

[JATothrim]

This is more an thought experiment than proposal at this point...

I made the orignal post after I tried to make an version of Hashy that de-duplicates portion of Cube from the expanded one.
I now pushed the experiment to: https://github.com/JATothrim/opencubes/tree/feature/baseCubeDeDup/cpp
The base cube is currently lost in the expand process and I wasn't able differentiate it from the expanded cube very well.
The deduplication is not as effective as I would hoped.
End result was saving some memory compared to unsplit CubeSet

If we would be able to split the polycube into basic subfragments the base fragments can be de-duplicated.
The expansions are an only point when there is some hierarchy relationship between the base cube and the expanded cube. This experiment is an bit of obsolete now.

For future I'm thinking that I'll just implement your @nsch0e compression scheme on top of CubeSwapper system once that is published.

The CubeSwapper system can do N=13 with ~2.4Gb of RSS / 1Gb of heap memory by dumpping all XYZ data into disk.
Cubes inserted in the Hashy are just an 64-bit file offset at this point. 😄
I hope I can do N=14 with 16GiB of ram at some point...

[nsch0e]

I think we could also look at how much overhead the unordered set adds. Since we are only adding elements to the set and never removing any (except clear), we could probably do smart things like store xyz directly in a contiguous array/file and the hashset entries only point into that?
Also greedy preallocation of the array could help to avoid rehashing and also reducing probability of collisions of the hash...

I worked on a prototype but it is very rudimentary but tailored more towards compressed cubes.

[JATothrim]

I think we could also look at how much overhead the unordered set adds. Since we are only adding elements to the set and never removing any (except clear), we could probably do smart things like store xyz directly in a contiguous array/file and the hashset entries only point into that? Also greedy preallocation of the array could help to avoid rehashing and also reducing probability of collisions of the hash...

I worked on a prototype but it is very rudimentary but tailored more towards compressed cubes.

With CubeSwapper system Subsubhashy writes the cube set XYZ data contiguously in a file (one file per Subsubhashy at moment) and before the temp file is removed CacheWriter does an file-to-file copy merging the set data into the cache-file as-is.
CacheWriter does not iterate the SubsubHashy Cubes at all and the XYZ data does not go through a memcpy. The OS instead does the data copy in the background.
The CacheWriter::save() is nearly instant now and doesn't have to wait for the file-to-file copys to complete.
If the Cubes are also compressed the unordered_set file storage looks good place to implement it since that data going to be later merged into the cache-file.