Model synthesis: Difference between revisions

The algorithm was first described by Paul Merrell, who named it 'model synthesis' in a 2007 PhD thesis, later presented at the 2008 [[SIGGRAPH conference]]. The name 'wave function collapse' later became the popular term for the algorithm, after an implementation by Maxim Gumin was published in 2016 on Github [[Repository (version control)|repository]] bearing that name. Variants of the algorithm have become widely adopted and adapted by technical artists and game developers, especially following Gunim's popularisation of the algorithm.<ref>{{Cite conference |last1=Alaka |first1=Shaad |last2=Bidarra |first2=Rafael |chapter=Hierarchical Semantic Wave Function Collapse |date=2023 |title=Proceedings of the 18th International Conference on the Foundations of Digital Games |chapter-url=https://doi.org/10.1145/3582437.3587209 |journal=Foundations of Digital Games 2023 (FDG 2023) |pages=2 |doi=10.1145/3582437.3587209 |isbn=978-1-4503-9855-8 |quote=In 2016, Maxim Gumin unleashed the WFC algorithm, publishing a repository containing his initial implementation. Since then, WFC has had a profound impact on technical artists and game developers, getting adopted, adapted and used in commercially published and upcoming projects (Caves of Qud, Townscaper, Matrix Awakens).}}</ref>▼

Gunim's initial implementation was inspired by Paul Merrell's dissertation, the ideas of [[quantum mechanics]], and [[convolutional neural network]] style transfer.<ref>{{Cite YouTube |url=https://www.youtube.com/watch?v=FG3LbcOGHqw |title=Procedural Modeling Using Graph Grammars |date=Aug 6, 2023 |last=Merrell |first=Paul |type=Video |language=English |time=3:13}}</ref><ref>{{Cite web |date=2021-03-21 |title=Implementing Wave Function Collapse & Binary Space Partitioning for Procedural Dungeon Generation |url=https://blog.shaankhan.dev/implementing-wave-function-collapse-binary-space-partitioning-for-procedural-dungeon-generation/ |access-date=2024-03-24 |website=Shaan Khan |language=en |quote=In the case of WFC it is inspired off three distinctive but functionally similar algorithms& concepts; Texture Synthesis (Specifically Discrete Synthesis), Markov Chains & Quantum Mechanics. WFC was also additionally inspired by convolution neural network style transfer (CNN Style Transfer).}}</ref> The popular name for the algorithm, 'wave function collapse', comes from an analogy drawn from the concept of [[Superposition principle|superposition]] in [[quantum mechanics]].<ref name=GitHub-Gumin>{{Citation |last=Gumin |first=Maxim |title=Wave Function Collapse Algorithm |date=September 2016 |url=https://github.com/mxgmn/WaveFunctionCollapse |access-date=2024-03-24}}</ref><ref>{{Cite web |title=The Wavefunction Collapse Algorithm explained very clearly |url=https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/ |access-date=2024-03-24 |website=Robert Heaton |language=en}}</ref> Whilst inspired by quantum physics, the algorithm doesn't rely on ideas from that field. One innovation in Gunim's implementation was the use of overlapping patterns of tiles instead of individual tiles, allowing a single image as an input to the algorithm.<ref>{{Citation |last=Gumin |first=Maxim |title=Wave Function Collapse Algorithm |date=2016-09 |url=https://github.com/mxgmn/WaveFunctionCollapse |access-date=2024-03-25}}</ref>▼

Prior to the algorithm's popularisation by Gumin, Merrell & Moncha's implementation didn't catch on in popularity to the same degree. Some have speculated that this may have been due to their implementation's lower accessibility, its 3D focus, or computing constraints at the time.<ref>{{Cite conference |last=Alaka |first=Shaad |chapter=Hierarchical Semantic Wave Function Collapse |date=2023 |title=Proceedings of the 18th International Conference on the Foundations of Digital Games |chapter-url=https://doi.org/10.1145/3582437.3587209 |journal=Foundations of Digital Games 2023 (FDG 2023) |pages=2 |doi=10.1145/3582437.3587209 |isbn=978-1-4503-9855-8 |quote=Years before, Merrel had published the conceptually identical Model Synthesis algorithm, though it did not catch on as much as WFC did, possibly due to its lower accessibility, main 3D focus and computing requirements at the time.}}</ref>▼

One of the differences between Merrell & Gunim's implementation and 'wave function collapse' lies in the decision of which cell to 'collapse' next. Merrell's implementation uses a scanline approach, whereas Gunim's always selects as next cell the one with the with the lowest number of possible outcomes.<ref name=Merrell2021>{{Cite web |last=Merrell |first=Paul |date=28 July 2021 |title=Comparing Model Synthesis and Wave Function Collapse |url=https://paulmerrell.org/wp-content/uploads/2021/07/comparison.pdf |quote=The first difference is in the step where we choose a cell and pick a label. The cells are chosen in a different order. Model synthesis sweeps through the grid in scanline order. WFC chooses the lowest entropy cell.}}</ref>▼