Metaballs II
Metaballs II renders "blobby objects" by using the "Marching Cubes" algorithm to extract an isosurface from a scalar field.
Technical Information
The scalar field is defined to cover the entire area in which the metaballs can move. Each metaball has a centre and a "power" and adds value to the scalar field. The influence of a metaball is greatest at its centre and falls off in an inverse-square manner.
Marching Cubes
Marching cubes works by covering the area in which the metaballs move with a grid of cubes. Two stages are involved:
- Calculating the value of the scalar field at each vertex, and
- For each cube, calculating triangles to approximate the isosurface using the values at its vertices
Metaballs II uses multithreading and double buffering to execute these two stages in parallel, thus producing an approximate 2x speedup on a multi-processor computer. Several optimisations are also applied at each stage.
Stage 1
Calculating the value at each vertex is performed using SSE intrinsics to calculate 4 values at a time. The vertex data is stored internally in a structure-of-arrays arrangement in order to reduce the amount of data manipulation required to use SSE.
Redundant calculation of vertices is avoided by the use of a bounding box. The maximum possible extent of the isosurface, given the current metaball centres, is computed and calculation is limited to vertices inside this box.
This step also uses OpenMP's "parallel for" construct to allow vertex calculation to be performed on multiple processors concurrently.
In order to be able to access SSE intrinsics and OpenMP, the code for this calculation is written in native (unmanaged) C++. It is encapsulated in a simple unmanaged DLL exposing a single 'extern "C"' function, which is called from the main C# code using a P/Invoke.
Stage 2
The naive way to calculate the triangles making up the isosurface would be to search every cube defined, or every cube within the metaballs' bounding box. However, Metaballs II employs a more sophisticated algorithm.
For each metaball, the algorithm begins with the cube containing the metaball's centre and then steps out towards the edge of the field, until it comes across a cube containing part of the isosurface. The algorithm then looks recursively at neighbouring cubes until the entire surface is found. A lookup table is used to restrict the neighbouring cubes which are considered to those which are likely to contain the isosurface.
Rendering
Metaballs II renders the scene using Direct3D, through the managed wrappers provided by the SlimDX project. HLSL vertex and pixel shaders perform separate refraction calculations for the red, green and blue components, plus a reflection calculation. A simple Fresnel term approximation is used to interpolate between these and produce the final pixel color.