A computer graphics beginner practical
by Robin-Marcel Hanne
Personally, I am very interested in computer graphics, most notably Visual Effects (VFX), and computer animation. As a result I decided to partake in this practical. The goal was to create something that be used outside of uni as well; instead of being a one-time creation that gets discarded after the project is finished. As a result, I decided on developing an addon for Blender.
Very commonly used in video games as the go-to meshing algorithm for procedual terrain sampled out of a noise function.
Metaballs are organic looking isosurfaces, that fuse together when in close proximity into a single, contiguous object. Metaballs are similiar to Z-Brush's Z-Spheres, which are commonly used to approximate shape and volume for organic models before sculpting.
The Marching Cubes algorithm has and still is often used for visualising CT or MRI scans. Sampled density values are used to represent the scalar field values and a user-defined threshold can be used to traverse through the scan.
The Marching Cubes algorithm works by iterating over a scalar field and takes in a threshold [t], also called surface level or "isolevel". The algorithm operates by traversing 8 corner points at a time. For each point we check whether the value of said point exceeds the threshold. If the value exceeds the threshold it is considered 'inside of the shape'. As a result, there are 256 different configurations, out of which 15 are unique. The other configurations are mere symmetries of those 15 base cases. The 15 base cases can be seen below. Whilst the original algorithm as published in the SIGGRAPH paper caused back-culling in OpenGL, newer variations used for video games change the triangulation table slightly so this issue no longer occurs. Another, more sophisticated implementation of this algorithm uses shared vertices. Instead of creating 8 new vertices for each iterated cube, vertices which share the same position are merged together. Another addition that can be made would shift the position of a generated vertex along its corresponding edge to linearly interpolate the values between the sampled points and create a smoother, less blocky result. Since this algorithm can be broken down into cubes, it is easily computed in parallel due to each cube being traversed independently of each other. As a result, it can be implemented on a GPU using a compute shader, NVidias Cuda cores or similiar technology.
Due to the Marching Cubes algorithm being a relatively new invention, and patented at first; multiple alternatives for generating a mesh out of a scalar field have surfaced over recent years. In the following we briefly look over three of the most well-known and sophisticated alternatives for the still widely-used Marching Cubes algorithm that exist today: To avoid legal intervention due to the Marching Cubes algorithm's patents, the Marching Tetrahedra algorithm offered a good alternative to create manifold meshes out of scalar fields. However, in comparison to the Marching Cubes algorithm, it produces larger meshes which can lead to slower render times in real-time rendering pipelines, such as those used in video games. The (Naive) Surface nets are a dual method, which creates non-manifold vertices and generates incredibly small meshes. The resulting meshes are extremely fast to render. However, in order to create more high-quality meshes additional hermite data is required in order for dual contouring to be possible. The VESTA (Volume Enclosing Surface Extraction) algorithm is a cycle-based mesh computation algorithm that creates non-degenerate, fully enclosing, non-self-intersecting meshes at a similar speed to the Marching Cubes algorithm. Whilst it produces much smoother results, it is a very new algorithm, hence; not very popular, and is harder to understand, learn and implement as there are only scientific papers about it at the time of this practical.
Whilst the project was originally intended as a simple addon based on Blenders exposed Python API, that plan had to be scrapped early on as Blender does not offer support for creating custom modifiers using their addon API. As a result, the C / C++ source code had to be modified and the program recompiled. Sadly, Blender's source code documentation was outdated, and in some parts non-existent, leading to a lot of reverse-engineering and traversing poorly documented code to understand how the program worked. Due to this, writing a custom modifier in Blender version 3.2 proved to be a rather difficult task. The source code of the custom Blender build can be found at the bottom of this page and should be documented enough to explain the workings of the various structures and allow people to write their own modifiers easier. One of the main changes that needed to be made was adding the modifier information and data to Blender's DNA and RNA components. These are used to store the program's runtime memory and project on the disk. Blender uses build programs called "makesdna" and "makesrna", which generate code out of strictly declared memory structures in the "source/blender/makesdna/DNA_modifier_types.h" and "source/blender/makesrna/intern/rna_modifier.c" files. More information on this can be found in an outdated blog post on creating custom modifiers for Blender and in their developer documentation. In order to remesh a model using the Marching Cubes algorithm, we first need to voxelise the mesh and create a scalar field filled with density values. After a bit of research I discovered that Blender uses a similar technique to convert Meshes into Volumes, and already provides an implementation of an algorithm to convert a mesh into a scalar field, stored using OpenVDB's FloatGrid structure. Once again, due to poor documentation of the Blender source code, I had to reverse-engineer the provided algorithm to understand why the values in the resulting grid ranged from 0 to a seemingly random maxima. Due to Blender's capabilities to be used as a 3D modelling tool and the support of N-Gons (polygons with n-sides) Blender does not use a simple triangle strip to store meshes in memory. Whilst the OpenGL-based rendering backend ends up converting these structures back into a simple triangle strip to send to the GPU, the mesh data itself needs to be stored in what Blender calls a BMesh. BMeshes are structures that store not only faces, loops, edges and vertices, but also much more metadata about the mesh, such as connectivity cycles that store persistent adjacency information. The same applies to mesh, or faceloops. In order to allow for N-Gons, a face is defined by a loop of vertices of variable length in which each index points towards the subsequent vertex in the face. Because the Marching Cubes algorithm only produces triangles, we can assume our loop length to be 3 for each face and easily fill in the loops afterwards. The implementation of this can be seen in the Marching Cubes algorithm. The modifier structure itself is defined in the "/source/blender/modifiers/intern/MOD_MCube.c" file. All submethods and functions called are documented and placed in the according, best-fitting project source code files to avoid breaking the project's code structure.
My name's Robin-Marcel Hanne and I am a computer scientist student at the Karls-Ruprecht University in Heidelberg. As an aspiring 3D artist and game developer, I spend a lot of time using various 3D packages including (but not limited to) Maya, zBrush and Blender, and I have developed a passion for computer graphics. This project was made as a computer graphics beginners practical supervised by Susanne Krömker.