snowmanam2
commented
1 year ago Hi Wagyx,
The point_rotations_lut has a few more intricacies to it - especially if you aren't generating all rotations. Looking at the logic of "generator_create_rotations" in generator.c, note how the computed rotations depend on the dimensions of the seed polycube. Still, this is just a guess at the cause in your case because there are a number of other factors. To test if this is the only factor, you can temporarily replace the dimension checking code and directly compute all rotations.
Note each row of the point_rotations_lut should always include each dimensional component in some order - either as the base component (X,Y,Z = 0,1,2 in 3D) or its reflection (X',Y',Z' = 3,4,5 in 3D). The 3D case is ordered such that the first component / reflection corresponds to the chosen computed rotations in "generator_create_rotations". I further narrowed the 3D case with the second component meaning something if all 3 dimensions were different, though I don't recall it helped performance as much.
Assuming base components (X,Y = 0,1 in 2D) and reflections (X',Y' = 2,3 in 2D), I think the point_rotations_lut for the 2D case should be:
{0,1}, // X
{2,3},
{1,2}, // Y
{3,0}My suggestion would be to start debugging back at the "generator_generate" function. Construct the point list key programmatically in a test main.c file and read out the output points of the "rkeys" to see if it matches your expectations. This is where I started when building the project. The result should return duplicate polycubes, but the duplicates should always appear in the same orientation.
Other considerations:
- The point storage format will almost certainly need to change for 4D and onward. I found point comparison to be a critical factor in performance, so a single comparison of integers is better than multiple compares. In the case of 2D, I think you probably want to compute something under N=256 but probably more than the N=30 limit built into the current 3D code. So, probably uint16 for 2D packed as 2 8 bit components, and maybe uint32 or uint64 for higher dimensions?
- The next issue you might find involving the point storage method is in the methods for determining point adjacency in filtering the polycubes for output (key.c neighbor and connected methods). Perhaps there are better ways to do this, but the current code is written using the raw point integers themselves as indices to an array of uint8 positions (the so-called "spacemap"). These positions can then be checked against neighbors by using a lookup table of offsets. For the 2D case, you might want to expand the size of the "spacemap" slightly to cover all possible values of a uint16 (65536). For 4D and above, you might want to find another method. I feared expanding it too much because of memory consumption and the possibility of frequent cache misses when trying to read back the data.
- If you do change the data format beyond the original uint16 bounds, you might need to play around with how to sort the points efficiently. I used sorting networks for the 3D case because I found qsort was slower, but perhaps you could change the data type or change the sorting algorithm. Also, the key_compare method will need to change accordingly to compare the correct number of bytes per point.
- I can only imagine trying to wrap my head around constructing the "point_rotations_lut" for higher dimensions. I reasoned the 3D version and the 2D version above by hand, but I'm not sure how one would approach higher dimensions.
Wagyx
Hello snowmanam2, I have forked your project and started a new branch where I am trying to modify the code so it could generate the 2D polyominoes but I am struggling with something, probably the rotation part. I have changed lut to
const uint8_t point_rotations_lut[][2] = { {0,1}, {0,3}, {2,3}, {2,1} }but the numbers I get do not follow the enumeration from Kevin Gong Could you develop a bit on that. There may be a mistake at another place in the code though. I also wonder what to change to make it work with higher dimensions. Thank you,