用 Houdini 实现 WaveFunctionCollapse
—— 一个名字取得极好的算法

废话

众所周知，取名一直以来是程序猿最大的挑战；名字取得不好，自己难受同事受难；反之只要名字取得好，注释不写关系都不大。然而起名字真的太难了，如果有一天我的头秃了，我相信一定会是想名字想秃的

所以那天机缘巧合下我看到 “WaveFunction Collapse”（WFC）算法的时候完全惊呆了，作者真是个天才！这么简单的算法配上这么帅的名字，直接拔高了1024个层次嘛，而且实际上“波函数塌缩”对于这个算法的行为的确是个不错的比喻，记住名字之后直接连算法本身也忘不掉了！

早想动手玩玩，然而我懒嘛，一直拖下来了，直到昨天来到题图的 WFC（环球金融中心）出差，我知道缘分来了，这下不玩玩 WFC 算法有点对不起这趟折腾

简介

这算法的思路和解数独非常像：把空间分为多个 cell，根据一系列约束条件，每个 cell 能取的值会受到限制； WFC算法就是不断的去找合法取值（波函数）比较少的 cell，把它的值确定（塌缩）下来，确定下来的 cell 又会对周围形成新的约束条件，导致其“塌缩”

说起来简单，但用这个简单的算法确实可以做出些有趣的效果：

wfc-eg

而且，看它这么长出东西的过程，感觉也非常舒服：

anim1

anim2

anim3

开干

不过在正式开干之前，还有点准备工作要做

准备工作

Step 1：弄些图

开始之前，最好准备一堆约束关系明确，易于验证的图；碰巧呢，Wang Tile 研究的正是这“给定相邻边约束条件，能不能用这些图块非重复性地拼满整个平面”的问题，如何证明“非重复性”这个高深的问题就留给数学家吧，我们可以拿点已知可用的 Wangle Tile 集合来用 —— 比如：

// 来源：http://www.cr31.co.uk/stagecast/wang/2edge.html

用 WaveFunction Collapse 解 Wang Tile 约束，简直绝配

Step 2：To Houdini

想在 Houdini 里面直接分析各张图之间的相邻合法关系以及预览下图这样的结果的话，首先还是得把上面那些图给弄到 Houdini 里面去 ——

tiles in houdini

所以新建个 copnet，添加 file 节点，填入对应图片路径：

cop-file

额，可是这太不程序猿了！手动导入这么多图片绝对会出人命的，所以写点代码吧：

for i in range(a,b):
  filenode=copnet.createNode('file', 'img_'+str(i))
  fn = os.path.join(imgdir, str(i)+ext)
  filenode.parm('filename1').set(fn)
  filenode.moveToGoodPosition()

得到：

然后为了能画出来还要给它们各自建个 material，方法类似，不再啰嗦：

matnet

再然后，弄个 objnet 加一堆 geometry，里面这么连 —— 这是为了后面直接把这些grid copytopoint 到目标网格上：

tile-geo

同样写点代码建一堆这样的 geo：

geos

另外，再想办法生成一堆点，代表每个图块记下对应的 coppath 和 soppath：

tileset meta

以上提到的部分我是这么干的：

tiles node

在 load_img_list 节点上把图片路径和参数填好，点一下 Execute 键，copnet, matnet, objnet, add_paths 几个节点都会对应更新好，这是全程唯一的手动操作

Step 3：提取四边颜色

接下来要开始做有技术的事情了，为了能自动推断出每个 tile 每个方向能接另外哪些 tile ，我们首先需要知道 tile 上下左右四个方向的特征颜色

在开始之前为了视野清净先另建一个 geometry

用 objmerge 取出前面用来保存每个 tile 的 cop path / sop path 的 OUT_tileset 节点，取名 tileset

连一个 attribcreate, 创建 px 属性，用来储存每个 tile 四个方向的特征颜色 // 我就是特别不会取名的代表

再连一个 python 节点，用 COPNode 的 getPixelByUV 函数查一下四个方向的像素值，uv 稍留点 margin 没准以后会用带有 border 的图呢，毕竟俗话说得好，做人留一线，日后好相见，然后随手 encode 一下每通道只留6位精度，防止图片有损压缩坑人：

import math
node = hou.pwd()
geo = node.geometry()
margin = node.parm('margin').eval()

def dopt(point):
  coppath = point.attribValue('coppath')
  copnode = hou.node(coppath)
  samplepts = ( (0.5, 1.0-margin), #up
                (1.0-margin, 0.5), #right
                (0.5, margin), #down
                (margin, 0.5) )#left
  samplepxs = []
  for uv in samplepts:
    px = copnode.getPixelByUV('C', uv[0], uv[1])
    r,g,b = map(lambda x: math.floor(x*64), px)
    encoded = int(r*64*64+g*64+b)
    samplepxs.append(encoded)

  point.setAttribValue('px', samplepxs)

for pt in geo.points():
  dopt(pt)

这样就记下了特征颜色：

tile sample px

Step 4：记录邻接关系

接下来，显而易见的是，我们需要记下类似于 tile A 是否可以出现在 tile B 的 D 方向的信息，这个信息很容易可以用三维数组表示：

legal[A][B][D] == 1: OK, legal[A][B][D] == 0: 不OK

可惜 SOP 不方便存这样的信息，我们退而求其次好了，直接建一个 NxNx4 的点云吧：

再接个 python 节点把它们初始化一下：

node = hou.pwd()
geo = node.geometry()
dimension = map(int,
               hou.node('../alloc_rule_cube').
               parmTuple('dimension').eval()
            )
N = dimension[0]

import numpy as np

rules=np.zeros(dimension,dtype=int)

given_geo = node.inputs()[1].geometry()
given=np.zeros((N, 4),dtype=int)
i = 0
for pt in given_geo.points():
  given[i:]=pt.attribValue('px')
  i+=1

for i in range(N):
  for j in range(N):
    rules[i][j][0] = given[i][0] == given[j][2] ## j above i
    rules[i][j][1] = given[i][1] == given[j][3] ## i j
    rules[i][j][2] = given[i][2] == given[j][0] ## j below i
    rules[i][j][3] = given[i][3] == given[j][1] ## j i
    for k in range(4):
      geo.point(i*N*4+j*4+k).setAttribValue('islegal', rules[i][j][k])

// 这里用到的 inputs()[1] 正是前面 Step 3 提取了四边颜色的节点

对于得到的 Geometry ，point(geo, 'islegal', A*N*4 + B*4 + D) 就和前面设想的 legal[A][B][D] 数组访问等价了

把 islegal 属性可视化一下，我们可以看到这个合法空间：