Élie Michel 🍪 Profile picture
Jul 30, 2021 7 tweets 5 min read Read on X
The #WaveFunctionCollapse algorithm by @ExUtumno has got really trendy in #ProcGen and game dev communities, but it wasn't the first of its kind!
It was highly based on Paul Merrell's work published almost 10 years earlier.⬇️
1/7 Image
First of all, Gumin's #WFC and Merrell's #ModelSynthesis give very similar results when they use the same tile set.
2/7 Image
But WFC is more often "stuck" and forced to restart, so it takes much longer on large grids. Merrell's approach is more naive but in the end it does not make a visible difference.
3/7 Image
@ExUtumno's main contribution over existing work was actually the overlap mode (see )
But so when @OskSta uses WFC, w/o overlap, it's actually closer to #ModelSynthesis!
4/n Image
Nota Bene: afaik OskSta added a #backtracking method to the original WFC, in order to avoid restarting from sratch when WFC gets stuck, mitigating the performance issue.
5/7
A part of Merrell's algorithm that got lost in the story is a per-block generation, to minimize further the risk of deadlocks. A similar approach is used by [Bian18] hal.inria.fr/hal-01811874/d…
6/7 Image
📚More info on Merrell's comparison page! code, video, etc: paulmerrell.org/model-synthesi… (I bet he got a bit furstrated to see his PhD rebranded under another name😬)
7/7

• • •

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

May 31, 2020
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
Read 18 tweets
May 17, 2020
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

Don't want to be a Premium member but still want to support us?

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

Donate via Paypal

Or Donate anonymously using crypto!

Ethereum

0xfe58350B80634f60Fa6Dc149a72b4DFbc17D341E copy

Bitcoin

3ATGMxNzCUFzxpMCHL5sWSt4DVtS8UqXpi copy

Thank you for your support!

Follow Us!

:(