The #WaveFunctionCollapse algorithm has been introduced by @ExUtumno as a texture synthesis method and nicely used by @OskSta for procedural generation of 3D buildings. Wait, what, how do those relate? Sounds like totaly different applications!
⬇️ Answers in the thread! 1/18
Discrete pixel values: WFC is different from many other texture synthesis algorithms because it never blends pixel colors. It does not need to know that a little bit of blue and some red creates purple. Others do require this, e.g. hal.inria.fr/hal-01824773/f…
2/18
This is a strength because it makes WFC more general. Pixels don't even need to contain colors. They just contain "stuff" or, more properly said, "abstract symbols". Can be an integer, a letter, a shape, whatever.
3/18
It has some drawbacks though, don't wonder why all original examples are pixelart-ish! The algorithm cannot recognize a pixel color "close to" another one, they are either the very same or totally different to its eyes.
4/18
So, what exact problem does WFC solve? There are two major steps. The first is the extraction (or "learning" but the word is a bit strong) of tiles and adjacency rules from an example image.
5/18
The second step is the constraint solving. For each location - or "slot" - in the new image, we pick a tile that respects the adjacency rules with its neighbors. @OskSta made a nice demo to show it in action: oskarstalberg.com/game/wave/wave…
6/18
There are two variants provided by the original implementation: "tiled model" and "overlapping model". The former simply cuts the input image in NxN patterns (here 3x3) and treat them as "abstract symbols".
7/18
The overlapping model extracts patterns using a sliding window. A tile is then a single pixel together with information about its neighborhood. Adjacency rules are derived from this neighborhood.
8/18
The notion of slot differs depending on the model. But anyways for the solving the output image remains a bunch of slots to fill with abstract symbols.
9/18
The true difference between tiled and overlapping models is the relations between slots. There are much more with overlapping model. With patterns larger than 3x3 there would be even more types of adjacency.
10/18
Overall both #WaveFunctionCollapse models are the same thing, the solving step does not care: it's still all tiles, slots, adjacencies and rules.
11/18
What about 3D then? Once again, it is just a change of adjacencies! There are with tiled model 6 adjacency relations: Left, Right, Forward, Backward, Above and Bellow. Overlapping model can also be applied.
12/18
All right then, the solving does not care? What if it's not a grid? "I still don't care", says the solving.
Examples on spheres by @boris_brave
and @OskSta oskarstalberg.com/game/planet/pl…
13/18
It even works with irregular grids, here on my reproduction of #Townscape. A notable difference is that there is no more symmetry in adjacencies. If slot A is "in front of" slot B, B is NOT necessarily "behind" A.
14/18
Here we are, Gumin's texture synthesis and Stalberg's procedural village use the same Wave Function Collapse algorithm, it's "just" a variation of tiles, adjacency rules and slot topology!
15/18
Pixels don't contain colors. And the image is no longer a grid. We've totally deconstructed the texture sythesis approach. But once again, this is good news! It illustrates the versatility of Wave Function Collapse.
16/18
NB: I don't know exactly how OskSta actually handles connection rules, I can only guess. Here is how I did in my implementation: tile faces are labled to tell which other tiles it can connect to.
17/18
📚Other resources to go further (and see the core algo, not presented here)
@ExUtumno's original implementation github.com/mxgmn/WaveFunc…
@ambrosiussen_p's talk about WFC in Houdini at GDC20
@OskSta's talk about Bad North at EPC18

• • •

Missing some Tweet in this thread? You can try to force a refresh
 

Keep Current with Élie Michel 🍪

Élie Michel 🍪 Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!

PDF

Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @exppad

17 May 20
Having a lot of fun reproducing @OskSta 's #Townscaper in #unity3d, very instructive exercise!
⬇️ Details in the thread bellow 1/10
Townscapper is based on #MarchingCubes, the traditional algorithm for converting voxel data to polygonal mesh (see also #DualContouring) 🧊
⬇️ We will apply it on a less usual grid though 2/10
Non regular grid generation based on hexagonal tiles with randomly removed edges.
Subdividing ensures that faces are all squares
➡️required to apply marching cubes! 3/10
Read 11 tweets

Did Thread Reader help you today?

Support us! We are indie developers!


This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal Become our Patreon

Thank you for your support!

Follow Us on Twitter!