Dynamic Tessellation for Ellipsoids

Dynamic Tessellation for Ellipsoids

My most recent work deals with efficient dynamic tessellation for ellipsoids. The basic idea is to parametrize the ellipsoid's surface in spherical coordinates, using 3 orthogonal basis vectors to define its shape. Then, we proceed to determine its silhouette and the point on the ellipsoid's surface where the surface normal is [0,0,1] (i.e. pointing toward the viewer and parallel to the z-axis). We use points lying on the silhouette curve, as well as this point in the interior, to construct a fan of triangles covering the screen projection of the ellipsoid.

In order to do this efficiently, we assume an orthographic projection. We can simulate the more common perspective projection using the following two steps:

  1. We adjust the size of the orthographic projection according to viewing distance, using a simple scaling factor determined by the distance of the ellipsoid's centroid from the viewer.
  2. If the viewer is not looking at the centroid of the ellipsoid, we pretend that he is, and then translate the resulting image accordingly.
This is, of course, only an approximation, but generally works well when the perspective is moderately weak.

The advantage to using an orthographic projection is that the silhouette is easy to determine. It is an ellipse inscribed on the ellipsoid's surface, determined by the following constraint: The z-component of the surface normal (in eye-space) is zero. Finding the appropriate relation between phi and theta (in our spherical coordinate system) requires a bit of math, although it is not too expensive---a few divisions and square roots are all that's needed. All the trig values needed can be stored in a small table. The surface normals are also relatively easy to obtain. Texture-mapping, however, will be more challenging to implement.

A more detailed account of this algorithm will be posted soon. In the meantime, you can play with the Java applet shown below, which illustrates how this dynamic tessellation can significantly reduce the polygon count of an arbitrary ellipsoid, relative to the traditional static tessellation scheme.

Java Applet