OpenGL

OpenGL

Several months ago I decided to teach myself a little OpenGL. Eventually, other interests and obligations began to compete for my time. During the course of learning, I naturally wrote a bunch of code to try things out. In particular, I wrote this "test engine" which contains a whole bunch of stuff.

The code is rather poorly written and perhaps a bit unstable. Again, it was only my testbed for learning and trying stuff, not an attempt to make a useful or well written program. Many places would benefit from documenation, optimization or just cleaner coding. Some sections may be adapted from OpenGL documenation or tutorials (in particular, NeHe Productions' tutorials were espescially helpful). I'd like to thank that site, and others whom I don't recall for providing such useful information.

While I initally never intended to make this code public, I eventually decided it might be useful to someone, such as a person trying to teach themselves OpenGL. There are a couple of interesting bits that I think are unique (which I describe below), and I hope somebody does something with them.

You can download the code here: opengl_test-0.5.tar.bz2.

It is a bzip2 tarball, suitable for compilation under linux. Just 'make', and run opengl_test from the source directory. It has several keyboard commands you can use to see some different things. Take a look at the source to see what they all are. M changes the model being displayed, T changes the texture being used, L toggles lighting, C changes colors. B toggles blending, P turns on pseudo-blending, with blending on (or pseudo-blending), E can be used to cyle though the "electron microscope" modes, AKA jellyfish modes. Try those with the light green or blue colors and no texture or the wood texture. X turns on cell shading mode, O turns on shell shading outlines. B changes the background color I think. Anyhow, you can learn more by looking at the source, so do that. :-)

You'll need OpenGL libraries, SDL and libpng to compile it. I haven't yet killed all the warnings, but they are harmless

I ask that you not redistribute the code at this time. Eventually I intend to write documenation, clean the code up, at which point I'll release it under the GPL or maybe a X11 style license. I decided to release this version now in case I never get around to fixing it. Feel free to look at the code and get ideas from it though.

The interesting features:

It has a cell shading technique, which is modified from the one on NeHe's site.

It has an "electron microscope" mode which I think is cool looking. One of the variations also has a fake focal blur, which looks even cooler. It would be better implemented using per-vertex or per-fragment programs supported by newer video cards, and could benefit from some cleaning up, but the basic algorithm is in there.

It has some interesting shapes (most of which are proceduraly generated). It includes some neat looking knots, and some generalized code for turning 3d parametric equations into opengl models.

The most interesting bit is some real-time isosurface code (blobs). It is based very roughly on the standard marching tetrahedra algorithm, which is based on the well known (and patented) marching cubes algorithm.

A couple of things are interesting about it:

  1. It is substantially faster than marching cubes or marching tetrahedra.
  2. It has a kinda slick way of generating the triangles.
  3. It has lots of headroom for improvment and further optimization.
  4. Is is different enough (and improved) from marching cubes that I doubt it's affected by the patent.

I don't know for sure that I thought of it first, but if so, I'm going to dub it "creeping tetrahedra".

It works as follows:

  1. Find at least one cube that lies on the surface of your blob (if there is more than one manifold, you need to find at least one for each). The the case of a spherical blobs, I just start by looking at the center cube in each sphere and move up one by one until I hit the edge (this is very quick and simple, though it probably could be made quicker, but this is just once per blob per frame, so it's not going to be a big benefit).
  2. Push those couple cubes onto a queue, and mark a lookup table to indicate that these cubes have been pushed.
  3. Calculate the "field strength" of each corner of the first cube on the queue. Use a big array to cache the results so you don't need to redo them when calculating adjacent cubes. Caching the results is very important for speed. Don't waste time calculating the values for all the cells in the universe - you won't need them all.
  4. Break the cube into 6 tetrahedra.
  5. For each of those, if there are some vertices inside and some outside of the object, then that tetrahedra intersects the surface. Interpolate to appoximate where the surface intersects each edge (for those that cross the surface).
  6. Optionally, recalculate the field strength at the approximate intersection point to reapproximate more closely (which results in a somewhat smoother more accurate surface at the expense of speed). You can repeat this a fixed number of times, or until it reaches some particular threshold of accuracy. I think this is Newton's method if I remember my math classes correctly.
  7. Draw 0, 1 or 2 triangles depending on how many intersections you have.
  8. Cache interpolated midpoints for use by other tetrahedra in this cube as well as adjacent cubes (this is pretty important if your isosurface formula is complicated (lots of blobs), and makes a large speed difference).
  9. For each adjacent cube that shares a side, check the following:
    1. Has it been put on the queue previously? (obviously, use a lookup table for this, don't make a linear search of the queue!)
    2. Is it within the rendering region? (i.e. bounds checking)
    3. For each shared edge, do any intersect the surface? (one vertex inside, one vertex outside - or check for the existance of the midpoints we previously calculated, whichever is easier)
    If a is false, and b and c are true, then we know that that adjacent cube also lies on the surface and needs to be analysed. If so, we should push this cube onto the end of the queue.
  10. If there are any cubes on the queue, move the queue head forward and jump back to step 3.

It's that simple. The great part is, you don't need to calculate field strength for any points not near the surface, and you only do work on cubes, edges, etc. that lie on the surface. Normally, computation time for marching cubes is a function of the volume of the rendered region, but here it's a function of the surface area of the blobs. With a length, width and height of N, the volume is N^3, but unless you have a very space filling surface, the surface area is something closer to O(N^2). That lets you use a finer grid, and as the grid gets finer, the benefits over traditional marching cubes increases. At the same time, it's almost as simple to implement.

Of course, it can use some optimization still, and there's room for it. One way is to improve cache locality by improving the order in which it does cubes, and by making lookup tables smaller and more sensible. Also, it could be improved visually and maybe performancewise (well, I'd have to try it) by remvoing pairs of triangles that have a very short shared edge. This algorithm is discussed in lots of places on the web, so I won't go into it here, but it would require storing all the polygons in a structure of some sort and then modifying that before displaying it, rather than doing it on the fly as it does now (that would also be required to make the "outline" technique work with the blobs in addition to the other models).

I know people have been finding this page when searching the web for things like "marching cubes opengl" so please let me know if any of this has been helpful for you.