Houdini: Wang Tile Set, Wave Function Collapse on non-uniform geometry
What is Wave Function Collapse?
This url holds a great example
The idea comes from Quantum superposition originally. In a nutshell, Quantum superposition is simply the idea our object can be in multiple states simultaneously until measured. The example linked above illustrates this using a Wang Tile set. All clickable tiles have 16 valid states until you start picking tiles. By defining a single tile, its neighboring tiles have their “valid” states reduced.
Why 16 valid states? Optional overview on wang tiles
Wang Tileset
A mathematician named Hao Wang in 1961, described how tiles would fit together with a simple rule. When connecting 4 sided tiles, you must match the edges to tiles with the same color edge. Each tile above has 2 colors, and 4 sides. 2^4 is 16. Therefore 16 valid states in our tile’s quantum superposition.
Hint: If you were to use hexagonal tiles instead of square, you would need (2^6) 64 tiles in your tile-set. Certainly you can get away with less, but Once you get into 16+ tile territory, you’re going to want to get procedural. Procedurally generating tile-sets is a post for another time.
If you were interested in 3 colors with a square tile-set, the total potential tiles changes to (3^4) 81 tiles in the above example.
Lets get started distributing Wang Tiles in houdini
There’s one limiting factor when using Wang Tiles in the way it’s implemented in houdini, the expected input is a grid.
Here I’m using a distorted sphere to affect the tile’s superposition. If a primitive within the grid is also within the sphere, the selected tile is 0 or empty. This sphere is solving our tile’s “state”. Doing so simplifies the Wave function collapse aspect of this problem, so we can focus on solving the Wang Tile distribution.
Wang Tile distribution process only worked on grids due to the mathematical properties of a grid. The key to this 2d Wang Tile decoder algorithm: iterating over each polygon, determining neighbor’s tile value.
int northnum = tile_num + num_of_rows; int southnum = tile_num - num_of_rows; int westnum = tile_num - 1;int eastnum = tile_num + 1;
With our neighbor tiles found, we need to determine if they’re “consumed” or not. To make this simple, we’re going to just check if our neighboring tiles are Red (“consumed”) or Black.
int north; int south; int east; int west;
// If we find a consumed/red tile neighbor north
if (north == 1)
north = 1;
// If we find a consumed/red tile neighbor east
if (east == 1)
east = 2;
// If we find a consumed/red tile neighbor west
if (west == 1)
west = 8;
// If we find a consumed/red tile neighbor south
if (south == 1)
south = 4;
// index = wang tile index
int index = north + east + south + west;Index is our wang tile index, an integer 0-15 in this case.
Lets use Tile # 63 as an example. It’s North and East tiles are “consumed” (red).
north = 2; east = 1;
index_63 = 3;
index tile 3
Wang Tile id 3 selected, since we have North and East “consumed” while South and West are not consumed.
And if we don’t find a tile in a one of the 4 directions, we know we’re an edge. However, this method falls apart when we introduce grid like geometry with only 2 edges.
EG: a tube.
North, South, East logic remain the same, but finding the western tile requires a new option.
// Vex H19.5
// Determine NSEW primitive neighbors on a tube
int cols = max(polyneighbours(0, 0));
int rows = nprimitives(0)/cols;
i[]@adjprims = polyneighbours(0, @primnum);
foreach(int primnum; @adjprims){
if(primnum==@primnum+1)
i@east = primnum;
if(primnum==@primnum-1 || primnum==@primnum-1+cols) // check if we've wrapped around a tube
i@west = primnum;
if(primnum==@primnum-cols)
i@south = primnum;
if(primnum==@primnum+cols)
i@north = primnum;
}Even if we solve for tubes/cylinders, we’re still extremely dependent on the primitives being numbered in the correct order.
Take this geometry for example, The top band of primitives are ordered in along the row, 53, 54, 55
The next row down, counts primitives down the column, 138, 139, ect…
So we need to back up a bit, and find a new way to look up neighbor primitives, and establish North, South, East, West neighbors
This sort of becomes a tangent space problem. We need tangent vectors to define a "compass" orientation per primitive. Then we can try to get the local direction vector based on the relative position of the prim we want to query.
The yellow visualizer represents the tangent vector, aka our compass orientation. With these we have the missing ingredients to TRUELY determine our neighboring prim.
Below I’m using our face normal with our tangent normal to create our rotational matrix. I’m then taking additional steps to convert this 3d direction to a 2d tangent space coordinate vector. I’ll be doing this 4 times per face.
// Vex prim wrangle
i@_north = -1; i@_south = -1; i@_west=-1; i@_east=-1;
vector pos; vector normal; vector tangent;
i[]@adjprims = polyneighbours(0, @primnum);
normal = v@N;
tangent = v@tangentu;
matrix3 m = maketransform(normal, tangent); // rotation matrix3 between two transforms
foreach(int primnum; i[]@adjprims){ // loop over adjacent prims to determine NSEW pos
if(diff.x == -1){
// yellow
v@diff_e = diff;
i@_east = primnum;
}
if(diff.x == 1){
// red
v@diff_w = diff;
i@_west = primnum;
}
if(diff.y == -1){
// blue
v@diff_s = diff;
i@_south = primnum;
}
if(diff.y == 1){
// green
v@diff_n = diff;
i@_north = primnum;
}
}
Visualizing the vectors @diff_* in the lines above
When we first calculate diff, it's in world-space, then the inverted local transform puts it into local space aligned with our UV map (v@tangentu derived from UV map).
We can test if our prim/face neighbor finding solution is working as expected. We’re looking for our vectors to consistently point in the x/y directions to determine if we have faces to the North, South, East and West.
You’ll also notice, I’m rotating the grid to demonstrate, no matter what the orientation of the object, the diff vectors are strictly local space. These vectors are locally pointing North/South/East/West if they have a valid neighbor in that direction.
We now have everything we need to calculate our Wang Tile number, 0-15.
// Vex houdini 19.5
// Wang Tile distribution method using true local space coordinates
i@_north = -1; i@_south = -1; i@_west=-1; i@_east=-1;
vector pos; vector normal; vector tangent; vector cd;
i[]@adjprims = polyneighbours(0, @primnum);
normal = v@N;
tangent = v@tangentu;
matrix3 m = maketransform(normal, tangent);
int east; int west; int south; int north;
foreach(int primnum; i[]@adjprims){
pos = prim(0, "P", primnum);
cd = prim(0, "Cd", primnum);
vector diff = pos-@P;
diff = normalize(diff);
diff *= invert(m);
diff *= {1,1,0};
diff = normalize(diff);
diff = -rint(diff);
v@diff = diff;
if(diff.x == -1.0){
i@_south = primnum;
south = int(cd[0])*4;
}
if(diff.x == 1.0){
i@_north = primnum;
north = int(cd[0])*1;
}
if(diff.y == -1.0){
i@_east = primnum;
east = int(cd[0])*2;
}
if(diff.y == 1.0){
i@_west = primnum;
west = int(cd[0])*8;
}
}
int wang_index = north + east + south + west;
if (rint(v@Cd[0]) == 1)
wang_index = 15;
s@name = itoa(wang_index);We now have our wang tile index recorded on every face on our geometry. Dragging the same sphere controller, we can visualize the wang tile distribution working correctly on our non-uniform capsule.
While our distribution is correctly setup, our tiles will correctly change swap to the appropriate tile index based on the sphere controller.
You may have noticed the tiles don’t really deform well to the shape of our capsule geometry as well as they did with the grid.
In the next blog post. I’ll walk through the steps required to write our own custom lattice node to properly fill in the gaps between tiles. Demonstrated in the video above.