The implementation of fast, practical routines
for drawing Superquadrics was a primary concern for this
project. The organization of the code, with the help of an
object oriented approach, was an important part of achieving this
goal. In particular, the code needed to be flexible enough that
we could write multiple demonstration programs which all
share the same code base.
This code organization effort had to be balanced with the desire for
fast efficient code. In particular, the
algorithm which does the actual drawing of a superquadric
needed a lot of fine tuning before we started to get good results.
OpenGL
OpenGl was a suitable library for our project, being a popular and
powerful 3D graphics API. We used an OpenGL compatible freeware
library called MESA, but our code is easily adapted to any
platform that supports OpenGL or MESA.
Because the OpenGL library provides low-level primitives
for raytracing, lighting
and other important functions, we were able to concentrate
on the important issues related to superquadrics, instead of
spending a lot of time trying to implement such primitives ourselves.
A Java implementation would have been nice, allowing us
to make our applications available for easy execution on the World
Wide Web. However Java does not have suitable 3D primitives, nor
the performance necessary for these graphically intensive calculations.
C++
OpenGL, like most APIs, provides a C interface.
Although there are some potential advantages of using C as our tool
for adding Superquadric functions, we felt the code organization
provided by an object oriented approach outweighted these advantages.
By using C++ we can take advantage of inheritance and abstraction to
produce a Superquadric class that is easy to incorporate into any
OpenGL program, while still offering enough functionality to produce the
full range of superquadric shapes.
Another option would have been to follow the example of the
quadric primitives (spheres, toroids, etc) that are part of the
OpenGL Auxiliary Library, and to provide our superquadrics as
OpenGL-style primitives with a C interface.
The Superquadric class hierarchy is the most important code in the
program. The SuperQuadric class is an abstract class that contains
the data and code that is common to all of the superquadric types.
The four types of superquadrics are subclasses of this class, each
containing the code and data that is specific to its type. This
organization means that the rest of the code rarely needs to know
the type of superquadric with which it is dealing.
The heart of our project is the actual drawing of the superquadric
object. As described earlier, the surface can be described by a simple
function that varies by two angles, eta and omega. A second function
defines the normal of the surface in terms of the values of eta and
omega. The other values in the function: a1, a2, a3, e1 and e2 are
all properties of a particular superquadric and are held constant
during the rendering calculation.
In general, when drawing a surface,
it is desirable to choose sampling points that are not
uniform, but instead vary in intensity depending on the curvature of the
surface at each position. Fortunately, sampling the surface using steady
increments of eta and omega has this effect naturally, which is a very
useful property of superquadrics.
The following example is two views of a box-like superellipsoid, showing
how the surfaces that are nearly flat are represented with large polygons,
while the areas that are curved are represented by many small polygons.
In our code we produce polygons, each with four vertices, to
approximate the superquadric's surface. In principal the idea behind
drawing a superquadric is very simple,
as shown in the following code snippet:
glBegin (GL_QUADS);
for (n = n_init; n < n_final; n += n_inc)
{
for (w = w_init; w < w_final; w += w_inc)
{
this->GetPoint(p1, n, w);
glVertex3dv(p1.p);
this->GetNormal(p1, n, w);
glNormal3dv(p1.p);
this->GetPoint(p1, n, w + w_inc);
glVertex3dv(p1.p);
this->GetNormal(p1,n, w+w_inc);
glNormal3dv(p1.p);
this->GetPoint(p1, n + n_inc, w + w_inc);
glVertex3dv(p1.p);
this->GetNormal(p1,n + n_inc, w + w_inc);
glNormal3dv(p1.p);
this->GetPoint(p1, n + n_inc, w);
glVertex3dv(p1.p);
this->GetNormal(p1, n + n_inc, w);
glNormal3dv(p1.p);
}
}
glEnd ();
We vary eta and omega (ie n and w) over their correct range and
calculate polygons. The range of values for eta and omega depends
on the Superquadric type (thisinformation is set by the constructor).
Also the value of the position and
normal of a particular point depends on the superquadric type, so
we call the GetPoint() and GetNormal() functions, which are virtual.
The actual algorithm that is used is significantly more efficient because
it makes use of the following techniques:
Efficient Vertex Calculation
Obviously this naive approach is not suitable for the real implementation.
Firstly, the calculation of each point is a fairly complex floating point
calculation; therefore, the above code is being inefficient by calculating
each point four times.
To avoid this we store the data in
a temporary two dimensional array, and then produce the polygons from
this array. An implementation that uses only O(n) memory instead
of O(n*n) memory is possible but would have made our code more
difficult to understand and debug.
Joined Surfaces
In some cases the objects wrap around and
should properly connect to form a complete surface. When working
with extreme values of e1 and e2 the errors from the
the calculation were strong enough to produce visible gaps in
the surface of objects like the superellipsoid which should be
a self enclosed solid. To solve this problem the data is adjusted to
ensure that the sample point values are used for vertices that are
meant to be the same.
Avoided Recalculation
We used OpenGl display lists to store
the polygons that are calculated. Whenever the object is
redisplayed, it makes use of these stored vertices rather than
recalculating all the data.
Therefore the rotation and translation operations can occur very
quickly.
Only when some attribute of the
object itself changes do we need to recalculate it.
Polygon Culling
There
are some OpenGL display issues that are tightly related to our surfaces.
For example, a superellipsoid is self enclosed, so for efficiency we
can enable culling of back-facing polygons and polygons
inside the object should not be drawn. On the other hand,
superhyperboloids are not self enclosed so we must draw both inside
and outside surfaces.
All these efficiency techniques have been implemented and are
used. The resulting code can be found
in the SuperQuadric::Calculate() and SuperQuardric::Show() methods
which are in the superq.cpp file.
As mentioned above, there is a heirarchy of classes representing
the superquadric family. There are also classes encapsulating
OpenGl features we used in our demos. The following is a
list of these classes.
- SuperQuadric
- This is the virtual base class for all the superquadrics types.
It contains all the code that is shared by all the types, including
the all important calculate() function.
- SuperEllipse, SuperHyperboloid1, SuperHyperboloid2, SuperToroid
- These are the four classes that contain the code that
is specific for each superquadric type.
Each class provides its own GetNormal() and GetPosition() function
to use the correct formula for each different object, (as described in
the
section on the mathematical background).
The special case of drawing both sheets of the superhyperboloid with
two sheets is handled easily by overloading the Calculate() function.
- GlobalEnv
- GlobalEnv contains important functions for using OpenGL. It
provides functions to display a superquadrics, create a superquadric,
set up a simple sighting situation.
- Material
- Encapsulates OpenGl material settings. This class allows the user
to easily associate a material with each object, or alternatively to
have a set of materials which can be alternately be applied to one or
many objects.
- LightModel
- Encapsulates OpenGL global lighting functions, such as global ambient
light.
LightSource
Encapsulates OpenGL lighting functions. 8 different lights can
be defined. This class stores the settings for ambient, diffuse, & specular
light, position, etc.
The total code is fairly substantial, being about 3500 lines, including
the 3 demos. It can be found in the code subdirectory of
this project.
The functionality provided by our code is modular enough that
writing more demos is really easy. Our given classes provide a solid
framework for creating and displaying superquadrics such that only code which
pertains to the actual workings of a new demo needs to be written.
For example, classes GlobalEnv, Material, LightSource and LightModel
provide useful functions for placing lights on the
screen or displaying groups of superquadrics; however, you can also
override these functions and provide your own.
Future demos could be more creative, perhaps showing animated superquadric
objects doing various acrobatic actions. Or, they could be part of
a more sophisticated rendered screen with texture mapped surfaces and
better lighting. A third possibility is to
extend our simple interactive demos to create a
a flexible modeling system with a graphical interface.