by C.G. Sleuth
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 ray-tracing, 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).
1: Implicitly defined trunk (1985) and three-way branch (1987)
The polygonizer was written in Mesa, a language developed at Xerox. A while later, Xerox researchers asked for help with an ink-flow 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.
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
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)
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
It surrounds a surface with cubes, approximating the surface within each
cube by triangles. This is similar to the well-known marching cubes
method (SIGGRAPH 1987), except only those cubes that intersect the
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 surface-following polygonizer has not previously been programmed for the GPU. The implementation is facilitated by OpenGL’s introduction (in 2011-2012) 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 surface-following 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 linked-list nodes are stored in an OpenGL buffer and dispensed via an atomic counter. A similar approach has been used to implement order-independent 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've got OpenGL4.3+ on a Windows machine, you can give Blobbies a try. The executable and binary shaders are at https://github.com/CGSleuth/Blobbies.
Here’s email to the