Procedural Image Generation Using Markov Wave Function Collapse

Wave Function Collapse (WFC) is an iterative constraint solving algorithm that performs texture synthesis on input samples to generate procedural outputs. The two commonly used WFC implementations are the Overlapping WFC (OWFC) and Tiling WFC (TWFC) implementations. OWFC incurs a performance cost in identifying constraints whereas TWFC receives pre-determined constraints in the form of meta-data. Pre-determining the meta-data, however, is a non-trivial process and requires substantial design time before the execution of the algorithm. The proposed Markov WFC (MkWFC) implementation aims to reduce the time involved during the meta-data design stage while maintaining the performance benefits of the TWFC implementation. This is achieved by using Markov random fields to determine constraints from a set of input samples and introduces a pre-processing step to the TWFC implementation. By automating constraint identification, the MkWFC implementation reduces both the meta-data generation time as well as the scope for human error. This paper compares TWFC against MkWFC on a set of 6 different procedural image generation problems using 3 sizes for inputs and outputs in a total of 720 trials. When comparing the MkWFC implementation against TWFC, there is an increase in the number of identified and used constraints from input and output respectively, which increases with image size. The performance of TWFC and MkWFC was compared by measuring their respective execution times for all trials. MkWFC was able to identify over 1.5 times more constraints for a 5 × 5 tiled image in 1.03 ± 0.09 ms(α = 0.05) and almost 3 times more constraints in 25 × 25 tiled image in 28.19 ± 2.58 ms(α = 0.05). This is substantially faster than the TWFC methodology where these constraints have to be manually identified and entered into the meta-data file. The automated meta-data generation and nominal increase in execution time allows for MkWFC to scale where TWFC cannot.