Polycube Generator in C

A 3D polycube generator based on the Computerphile video and this repository. This version is written in C with some optimizations indicated below.

Compiling

make all

Note the current Makefile was written for Linux with GCC. The only external dependencies are pthreads and zlib. It seems to work in Cygwin or MinGW, though the executable is a bit slower.

Usage

The following returns the number of 3D polycubes of length 5:

./polycube_generator 5

The following returns the number of 3D polycubes of each length up to 8:

./polycube_generator 8 -a

For lengths larger than 9, the "-t" option allows specification of a number of compute threads. The default is 16 threads, shown here with 10 threads.

./polycube_generator 13 -n 10

A cache file can be generated by adding "-o" with the filename:

./polycube_generator 5 -o cubes5.pcube

A PCube cache file can be compressed by adding "-oz" with the filename:

./polycube_generator 5 -oz cubes5.pcube

A cache file can be input for use in computation by adding "-i" with the filename:

./polycube_generator 7 -i cubes5.pcube

Cache files can be generated in a smaller "bitface" format by changing the extension to something besides .pcube:

./polycube_generator 5 -o cubes5.dat

Using the Job Processor

The job_processor.py file is used as a client to a SnowmanPolycubeServer instance. By default, it continuously processes segments of a shared seed file and returns the number of polycubes found.

The only non-standard library used is requests.

Before starting, set the configuration in job_processor.cfg. You need to set up the server name, how many hardware threads are available, the name of the command - such as polycube_generator.exe on Windows, and the name which you want to be called in your contribution:

[Job]
job_server = https://snowman-polycube-server.vercel.app/jobs/n18/job-tickets
job_folder = jobs

[General]
threads = 12
cmd = ./polycube_generator
contributor_name = snowmanam2

Note the job_server must point to the proper job-tickets node of an active job on the server, as configured by the server operator.

Once the configuration is saved (assuming the main executable was built as noted in the "Compiling" section), you can start the processor with:

python job_processor.py

The processor will run continuously until the server runs out of segments to compute. You can kill the process if needed, though all progress on the current ticket will be lost. The server will reallocate the dropped segment after the configured timeout has been reached.

Algorithms

Basics:

• The core of this version uses sorted point lists as the basis of the generated cube "keys". The lowest coordinate is 1 in each direction.
• Before any computation is performed, we compute all relevant rotations of the initial point list, including versions expand the dimensions of the list beyond the original size.
• Rotations are reduced to 4 for any dimension set with a dimension not equal to the other 2 dimensions. All 24 rotations are used otherwise.
• Candidate points are determined on all faces of the initial list of length n-1. We sort the list and compare with the original point list to eliminate overlapping points.

This is "hashtable-less" implementation similar to that described by presseyt. The difference is checking if the removed point from the new polycube is the highest possible index in the polycube point list. When doing this in combination with removing all duplicate polycubes from the current "seed" shape, we are left with a unique set of generated cubes. Specific steps taken:

1. Start with polycube p. Extend by cube a to yield cube q (q = p + a).
2. Repeat step 1 for all possible additions of a.
3. Filter result of step 2 to only have unique values, saving the highest possible of the index of a in each q.
4. For each q, check if there is any possible r at a higher index of q that can be removed while remaining a polycube. Otherwise output q.

The advantage of this method is we don't need to recanonize the combinations. I used a rather lazy implementation of steps 3 and 4:

1. Sort all generated q polycubes. Check the current q with the last q to eliminate duplicates.
2. Use a fast "number of neighbors" check to eliminate the majority of higher duplicate r indexes. Specifically, if a cube in q only has 1 neighbor, it can safely be removed.
3. If the neighbor check doesn't cancel the output, iteratively check all r values of index higher than a. We count the number of cubes that can be reached to make sure it is connected.

Performance

Using a rather dated FX-8350 processor with 16 computing threads on Ubuntu with no cache generation or input, measured cumulatively:

• n=11 in 2 seconds
• n=12 in 9 seconds
• n=13 in 74 seconds
• n=14 in 722 seconds (12 minutes)
• n=15 in 5902 seconds (1 hour 38 minutes)

Cache Files

This program can read or write the basic .pcube format. Compression is supported.

The alternative "bitface" cache file format is structured as follows:

1. (1 byte) Length of the polycube
2. (n * key_size bytes) Polycube data

The encoding is a bit / face scheme. The cubes are described in discovery order based on the +xyz / -xyz faces. We skip the face of each cube on which it was discovered, and we skip the last cube because it will always be zeroes. Each bit represents a discovered cube on the face of the current cube.

Note there will be exactly n-1 bits for a polycube of length n. This unambiguously describes the position of all cubes, making recovering the shape rather simple. It also could lead to further space reduction by noticing this data can only have a certain number of states, though I have yet to figure out a good way to do so.

For reference, the space utilization is 70.7 GB for n=15 with 9 bytes per polycube. Still, I estimate n=18 has 42.1 TB required, but I doubt anybody would want to generate that much data.

Example n=4 (note "." designates the skipped bit):

100000 100.00 100.00
a      b      c      d

(this describes a straight line)
abcd

Example n=4:

100000 110.00 000.00
a      b      c      d

(this is a T shape)
 d
abc

Known Areas for Improvement

• qsort can be slow, and it appears in critical areas (filtering for duplicate removal). Maybe mergesort or other methods could be faster.
• Graph algorithms could probably improve the performance of the full connection check.
• Cross-platform compatibility (maybe use CMake).
• CLI is rather basic.
• Increasing I/O depth and/or moving compression & packing methods to threads might help with cache file write speed.
• The 6 expansion rotation sets might be faster to compute if calculated as offsets relative to the main set or each other.

License

MIT