The Unchained Blog

An Oldie but Blobby


  
  
  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 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).

Figure 1: Implicitly defined trunk (1985) and three-way branch (1987)

Polylingual Polygonization

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.


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.

Blobbies on the GPU

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 well-known 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 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.

Figure 4: 50 atoms

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.

Performance

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 a Windows machine running OpenGL v4.3+, you can try the demo at https://archive.org/details/Blobbies.

Questions? Comments? You can email the author.