Fun with 4D Meshes

   Over summer break I wrote a fun bit of code in Unity. It's a component for displaying a three dimensional mesh representation of a four-dimensional shape.

   How did I go about doing this? The first thing I needed to do was create a data structure for describing a “4D Mesh.” The key thing to understand about meshes, of any dimensionality, is that they describe shells, not actual shapes. A 3D mesh is a collection of 2D faces arranged in 3D space. Similarly, my 4D mesh asset is simply a collection of 3D tetrahedrons arranged in 4D space. Its data structure works on exactly the same principles; an array of Vector4s describing vertices positioned in 4D space, and an array of integers describing tetrahedrons by referencing sequences of four vertices.

4DShape.gif

   The second piece of necessary script is a process for translating a cross-section of a 4D mesh into a 3D mesh that can be read by Unity’s mesh renderer component. To do this, I need need the two key elements of a 3D mesh: an array of verts, and an array of triangles. The 3D verts need to be calculated based on the viewer’s current w-position since they describe points along the edges that connect 4D verts. These verts are added to a list, and their indices are also stored in a two-dimensional array. This is so that when I translate the tetrahedrons into triangles, I can use the indices of two 4D verts in a tetrahedron to find the index of the 3D vert that represents the edge between them.

   I plan to post the code on Github eventually, once I’ve done a little more cleanup and optimization. Currently the script makes an effort to cull unused vertices from the mesh it outputs to the mesh renderer, but I suspect that it’s faster and less memory intensive to simply process all the verts since it saves me the trouble of reconstructing a 3D vert index list whenever the mesh needs to be updated. I’m also looking into Unity’s new job system since it could allow me to do much of the calculations on a separate processor.

   The biggest roadblock in the experiment right now is actually the difficulty of inputting the data for a 4D mesh. So far I’ve been doing it by hand. For the shape in the gif above, I needed to input 16 Vector4s (64 values), and 32 tetrahedrons (a sequence of 128 integers). Now that ProBuilder is available for free in Unity 2018, I’m thinking about writing an extension that would allow me to better model and visualize a 4D shape.

A Bit of Bitmask Evangelism

   Friend, have you heard the good word about bitmasks? I’ve found them to be an extremely useful tool, one that I’ve used several times to make my code far more readable and efficient.

   First, let me give a (relatively) vernacular explanation of bitmasks. Computers store data as sequences of ones and zeroes. Normally these sequences are interpreted as binary representations of numbers, numbers that can then be interpreted as other things like text or enumerated types.

   A bitmask is simply a variable that is thought of as an array of booleans instead of a binary number. Bitmasks are useful for describing a subsets of sets. A good example of this is the layer system used by Unity and other game engines. Each layer is associated with a power of two, which means that each layer corresponds to its own bit in the sequence: Layer_A = 1, Layer_B = 2, Layer_C = 4, Layer_D = 8, and so on…

   I’ve linked a more indepth explanation of bitmasks and bitwise operations here. A good post about writing enumerations as bitmasks in Unity is here and below I’ve pasted the code for a custom property drawer for Unity that applies the built-in Layermask drawer to your own mask enumerations.

//Remember to place this class in a folder named Editor
using UnityEngine;
using UnityEditor;
[CustomPropertyDrawer(typeof(MaskFieldAttribute))]
public class MaskFieldDrawer : PropertyDrawer {
    public override void OnGUI(Rect _position, SerializedProperty _property, GUIContent _label)
    {
        EditorGUI.showMixedValue = _property.hasMultipleDifferentValues; //This was a safety line suggested in the forum for multi-object editing scenarios.
        _property.intValue = EditorGUI.MaskField( _position, _label, _property.intValue, _property.enumNames );
    }
}

Custom Property Drawer

//Remember to place this class in a folder named Editor using UnityEngine; using UnityEditor; [CustomPropertyDrawer(typeof(MaskFieldAttribute))] public class MaskFieldDrawer : PropertyDrawer { public override void OnGUI(Rect _position, SerializedProperty _property, GUIContent _label) { EditorGUI.showMixedValue = _property.hasMultipleDifferentValues;//This was a safety line suggested in the forum for multi-object editing scenarios. _property.intValue = EditorGUI.MaskField( _position, _label, _property.intValue, _property.enumNames ); } }

   Bitmasks have made my life easier on multiple occasions. I used them to write my own tag masks for unit behavior logic in Orbit Project. Tablecraft’s code was very quick and dirty, but now that it has become a larger project this semester, I’ve suggested to the new programming team that they ditch my messy loops-within-loops and use bitmasks to compare sets of element cubes.

   The example I really want to talk about is the puzzle-agnostic state-graph builder I wrote for my tech design final last semester. The project really warrants its own post, but I’ll describe it briefly here. The graph builder receives a puzzle class object (all puzzle classes adhere to the same interface). Using the initial state of the puzzle as its starting state, the builder gives the puzzle class a state and asks for all the states that lead from that state. In this way the builder performs a breadth-first search of the puzzle’s state graph. The plan is to eventually write tools that can use this information to assess the properties and overall quality of a puzzle.

   Where do the bitmasks come in? Not in the builder itself. Bitmasks came up because I chose a mobile puzzler named Kami 2 as my test subject. In Kami, the player uses a “paintbucket” mechanic to deconstruct a pattern of colored patches. The goal is to paint the canvas all one color in the minimum number of moves.

   Each given state of a Kami puzzle consists of a set of colored areas, with each area being adjacent to some of the other areas. When a player fills in an area, it combines with adjacent areas of the same color to become a super area.

   Bitmasks made this logic extraordinarily easy. Each initial color patch in the puzzle is given a layer in the bitmask, as well as a mask listing all the other patches that border it. When two areas merge, I simply use a bitwise OR operation to combine both their area mask and their adjacency mask. To check if two areas are adjacent, I use a bitwise AND to check for overlap between the area mask of one patch and the adjacency mask of another.

   Because the same super area can show up many different puzzle states, I ended memoizing area-to-adjacency relationships by storing them in a dictionary (int bitmasks serve as their own hashcode). These little optimizations add up, because even a simple Kami puzzle can have tens-of-thousands of states.