by C.G. Sleuth March,
2021

In honor of Spring, here is a new version of an old polygonizer! But . . . first, a little history.
Computer graphics defines
objects with vertices, and one expression for a vertex is implicit,
that is, a vertex at location p satisfies some function f(p)
= 0. Objects defined this way include the quadric surfaces visualized in
the 1970s and the blobby molecules introduced by Jim Blinn in 1982.
Blinn defined a DNA molecule as a sum of functions, each based on
distance to an atom. The resulting surfaces were visually interesting,
smooth and complex. Although Blinn visualized these blobby molecules
with raytracing, contouring methods can be used to produce a vertex
mesh. For example, I used blobby, planar contours to define the trunk of
the Mighty Maple (SIGGRAPH 1985). Hoping to model blobby branches, I
created a 3D extension, called it a polygonizer, and wrote a report
for Xerox (my employer).
Figure
1: Implicitly defined trunk (1985) and threeway branch (1987)
The polygonizer was written in Mesa, a language developed at Xerox. A while later, Xerox researchers asked for help with an inkflow simulation. They had volumetric data but couldn’t extract or render surfaces. With some minor changes, the polygonizer generated an animation for the group. They asked if the source could be translated into Fortran, so, by 1989, I had implemented the same algorithm in two languages.
Figure
2: Simulated ink flow through an inkjet head (1989)
In 1991, Ken Shoemake
helped me develop an implicit model we called convolution surfaces. That
year, he organized a
SIGGRAPH
workshop and asked to include the polygonization software. Xerox
generously gave its approval. Ken asked me to translate the code to C
and, so, a third implementation resulted.
Figure 3: Hand modeled by convolution surfaces (1991)
In
1994, Paul Heckbert asked to publish the C
code in Graphics Gems IV. And, in 2003, Andreas Bærentzen
published a fourth implementation, in C++.
This article describes a fifth implementation, in GLSL. Like all the
others, it is uniquely different.
The polygonizer described
above is a surface
follower.
It surrounds a surface with cubes, approximating the surface within each
cube by triangles. This is similar to the wellknown marching cubes
method (SIGGRAPH 1987), except only those cubes that intersect the
surface are
processed. In comparison, marching
cubes processes all cubes within a regular grid.
This difference affects implementation and performance.
The marching cubes method was implemented on programmable GPUs soon
after their introduction, but, to my knowledge, a surfacefollowing
polygonizer has not previously been programmed for the GPU. The
implementation is facilitated by OpenGL’s introduction (in 20112012) of
the compute shader, atomic operations, and the shader storage buffer
object. The latter two allow the compute shader to write to a vertex
buffer.
With the surfacefollowing polygonizer, one or more seed cubes propagate
new cubes across transecting cube faces. A seed cube is needed for each
potentially disjoint surface (for blobby molecules, these are readily
computed).
The direction and extent of cube propagation is unrestricted, so a
method is needed to prevent cycling. A hash table of linked lists can
serve this purpose, as first used by Wyvill
et al. It is implemented as an OpenGL uimage2D, where a
pixel of the image serves as an index to a linked list and is updated
via an atomic exchange. The linkedlist nodes are stored in an OpenGL
buffer and dispensed via an atomic counter. A similar approach has been
used to implement orderindependent transparency.
A second hash table, for transecting
edges, prevents
redundant vertex calculation. It also enables use of the OpenGL element
array buffer for rendering; thus, for closed objects like blobbies, the
number of vertices stored is half the number of triangles, not three
times.
The additional code to support hash tables and related variables nearly triples the GLSL code needed for marching cubes. Six compute programs 1) set seed cubes, 2) set cube polarities and propagate cubes across transecting faces, 3) build an edge hash table, 4) set vertex locations, 5) triangulate each cube and fill the element buffer, and 6) set vertex normal and color. The programs, each reasonably small, run much faster separately than combined. A separate render program displays the triangles.
To compare techniques,
randomly sized blobby atoms were placed within a 3D domain. Marching
cubes was tested with a 50 X 50 X 50 grid and compared against the
surface follower, whose number of cubes varied. Cube size was the same
for both methods.
Timings were made with the Nvidia GeForce MX150 (384 processors). For simple surfaces, the overhead of the surface follower hash tables keeps marching cubes competitive. But, as the number of blobby atoms increases, marching cubes becomes increasingly slower in comparison.
20 atoms  50 atoms  100 atoms  
Surface Follower  30 fps, 10K cubes  24 fps, 25K cubes  15 fps, 35K cubes 
Marching Cubes  20 fps, 125K cubes  6 fps, 125K cubes  3 fps, 125K cubes 
The original marching cubes method advanced plane by plane through the grid of cubes, caching corner and edge calculations for each plane. The timings above are from code that operates cube by cube, not plane by plane. A test in which corner values were cached did not, however, significantly change performance.
If you have OpenGL4.3+ on a Windows machine, you can give Blobbies a try. The executable and binary shaders are at https://github.com/CGSleuth/Blobbies.
Questions? Comments?
Here’s email to the
author.