ADSODA
ArbitraryDimensional Solid Object Display Algorithm
by Greg Ferrar
Introduction
ADSODA is an algorithm for displaying solid objects of arbitary dimension.
It includes ndimensional lighting, ndimensional hidden solid removal,
and ndimensional orthographic projection to n1 dimensions.
Motivation
Traditional highspeed rendering packages use onedimensional and
twodimensional solid objects (line segments and polygons) for their internal
scene representations, even when the scene is of three or more dimensions.
For instance, fast threedimensional renderers generally render objects as
polygons, which are twodimensional, rather than using fully
threedimensional objects like spheres or polyhedra. In three dimensions,
this is not generally a problem, because full realism can be achieved using
polygons. However, in higher dimensions, polygons no longer suffice just
as 0D points 1D line segments are not sufficient to render realistic 3D
scenes into two dimensions, 1D line segments and 2D polygons are not
sufficient to render realistic 4D scenes into three dimensions.
Furthermore, the introduction of fully solid ndimensional objects
brings with it the problem of hidden solid removal; naively drawing the projections of
all solids in a space is insufficient, because the projections of an object
will obscure objects in front if it, if it is drawn in the wrong order.
This problem can be effectively solved in three dimensions using a zbuffer,
or by drawing backtofront. For n dimensions, however, a zbuffer
required extraordinary amounts of memory, and backtofront ordering
works only if rendering is being done immediately after projection into some sort
of a "bitmap", where individual pixels or voxels can overwrite the
voxels behind them. In arbitrary ndimensional rendering, this condition
does not hold. For instance, two projections are required to render a 4dimensional
object on a 2dimensional screen, and the intermediate 3dimensional projection
cannot be a "bitmap"; it must be a mathematical scene representation, so that it
can be used to project to 2D.
A Solution
ADSODA addresses these issues by using an ndimensional representation
for a solid.
which fully describes the ndimensional volume occupied by the solid.
This representation, a simplified form of CSG (constructive solid geometry),
provides some operations, like object intersections, differences, and slicings,
quite efficiently. Using these operations, it implements ndimensional
hidden solid removal (the natural extension of 3dimensional hidden surface
removal) in the source space, clipping out hidden parts of the scene from
the source space before projecting. With this done, drawing can be done in
arbitary order; since there is no overlap of the object projections,
all possible orderings result in the same projected space, and the projected
space objects to not intersect.
To render the ndimensional solid realistically in (n1)space,
ADSODA implements several other basic rendering algorithms. First, it use
a simple lighting model which is highly efficient, due to the inclusion of
normal vectors in the natural representation of solids. Second, it
contains an orthographic projection algorithm for mapping nspaces
to (n1)spaces. Finally, it
contains algorithms for rendering 2dimensional and 3dimensional solids
using OpenGL. These algorithms combine to support the rendering of arbitrary
dimensional solids with lighting effects in all dimensions, and
hidden solid removal in all dimensions.
Due to the relative simplicity of the representation and the algorithms,
ADSODA can render simple animated fourdimensional scenes in real time.
Solid Representation
ADSODA represents solid ndimensional solids as the intersection
of a set of halfspaces. For instance, it would represent the
twodimensional solid in
Figure 1a as the intersection of four halfplanes in
Figure 1b,
Figure 1c,
Figure 1d, and
Figure 1e (Figure 1f).
The halfspaces are
represented by their equations, which can also be thought of as their normal
vectors, plus a constant.
Figure 1a

Figure 1b

Figure 1c

Figure 1d

Figure 1e

Figure 1f

This representation extends naturally into n dimensions.
Operations involving slicing are trivial; to slice a solid along an arbitrary line,
it is necessary only to add another halfspace to its representation
(Figures 2a and 2b).
Figure 2a

Figure 2b

Lighting
The solid representation model makes lighting fast and simple.
The normal vectors of the faces of the solids being lit are built into the
representations of the solids (each face of a solid is represented by its
equation, as described above, and the nonconstant coefficients of the
equation are exactly the components of the normal vector).
ADSODA uses a very simple lighting algorithm; it computes the
dot product of the normalized normal vector with the normalized eye
vector, and uses this as the brightness.
Hidden Solid Removal
Before an ndimensional space can be projected onto (n1)
dimensions for display, hidden solid removal must take place.
This removes all solids in the space which are obscured by other solids,
as seen from the eye point. After hidden solid removal occurs,
all solids in the space can be projected directly onto the lower dimensional space;
hidden solid removal ensures that no "collisions" will occur (that in
the lower dimensional space, no two projected solids will intersect).
In the case of a 3D to 2D projection, for instance, this means that the resulting
twodimensional space can be immediately drawn on a screen without
any regard for the order polygons are drawn in; there will be no overlap,
so the end result of any order or rendering will be the same.
The first step in ADSODA's hidden solid removal algorithm is to compute
the silhouettes of all the solids in the space. The silhouette
of an ndimensional solid is the "outline" of the solid, as seen from
the observer. Figure 3 shows a sample twodimensional space with three solids
(Figure 3a), with the silhouettes of the three solids. The observer in this example is
twodimensional, and is looking from the negative y direction.
The silhouette is an (n1)dimensional
solid, and is represented in the same way all (n1)dimensional
solids are represented in ADSODA (as the intersection of a set of
halfspaces; in Figure 3, each silhouette is represented as the intersection
of two halflines).
Figure 3a

Figure 3b

Figure 3c

Figure 3d

To compute the silhouette of a solid, ADSODA finds every pair of adjacent faces
of the solid for which one face is a frontface (facing towards the viewer)
and the other face is a backface (facing away from the viewer). Frontfaces
and backfaces can be easily determined by checking the sign of the dot product
of viewing vector with the face normal vector. Given two such adjacent
faces, ADSODA finds the intersection between the faces
(which is an (n2)space), and projects it to the
destination space. For instance in Figure 3c, the lower right corner
of the green solid is the intersection of a frontface and a backface,
and is therefore a border of the silhouette; the leftmost point of the green solid
is the intersection of a frontface and a backface, and is therefore also a border of
the silhouette; there are no other adjacent frontface/backface pairs, so there are
no other borders to the silhouette.
For an ndimensional solid, the faces of the solid are
(n1)dimensional solids imbedded in nspace (line segments, in the case of
Figure 3); the boundaries of the silhouette are (n2)spaces
imbedded in the (n1)dimensional projection space (points, in the case of Figure 3).
As another example, consider the case of a cube in 3space (Figure 4).
To find the silhouette of this cube,
ADSODA finds every edge between a frontface and a backface, and projects the
edge (which is a line in 3space) onto the destination plane. The result is a
halfplane, which, combined with other halfplanes found in the same manner
(there are six such halfplanes),
represents the 2dimensional silhouette solid using ADSODA's solid representation method.
Figure 4a

Figure 4b

Figure 4c

Finding which faces are adjacent is nontrivial; this information is not
present in the basic (intersection of halfspaces) representation.
It must be computed in a separate step. ADSODA determines this information
by first finding all corners of the solid, and then using them to
find the adjacent faces. To find corners, ADSODA iterates through every possible
ntuple of faces, and finds their intersection (a point). If the intersection lies
on the boundary of the solid, it is a corner. If it lies outside the solid,
it is not a corner, and it is ignored. For each corner thus found, every face which
contributed to that corner is added to the "adjacent faces" list of every
other face. The corners are also used again later, in rendering.
Once the silhouettes have been computed, they are extruded back into
nspace, parallel to the viewing vector. They are extruded
infinitely into nspace, forming a tube through nspace
which intersects the projection space in the shape of the silhouette, and
is parallel to the viewing vector (Figure 5).
This extrusion is easily represented using ADSODA's normal solid
object representation it is the intersection of the set of halfspaces
in nspace which intersect the destination space at the edges
of the silhouette, and which are perpendicular to the viewing plane.
This is the silhouette tube.
Figure 5a

Figure 5b

Figure 5c

The silhouette tube is then subtracted from
every solid in the space which is behind the silhouetted solid
(a solid S1 is behind another S2 if some corner of S1 is
inside the silhouette tube of S2, and if that corner is behind a backface of S2),
and the rear solid is replaced by the difference.
This difference is exactly that portion of the back solid which is not obscured
by the silhouetted solid.
To compute the difference of two solids (S1  S2),
ADSODA duplicates S1, and the copy is
repeatedly sliced by faces of S2.
Each slice results in another
piece S1 which is outside the volume of S2. The union of all these pieces
is the difference. (Incidentally, the final piece which remains after
all the pieces of the difference have been sliced away is the intersection).
For example, Figure 6 shows the subtraction/intersection process for
two twodimensional solids. Initially, S1 is duplicated, creating the red solid.
In Figure 6b, this red solid sliced against one of the faces of S2,
by adding that face
as a face of the red solid. Since this face does not change the appearance of the red solid
(the red solid already lies entirely in the halfplane described by that face),
this face is discarded automatically by ADSODA, and the process continues.
The next face (Figure 6c) is more interesting; adding this face to
the red solid changes it (cuts off a corner).
The new
red solid is computed by copying the red solid, and adding the face;
the green solid is computed by
copying the previous red solid again, and adding the negative
of the face (the face with its normal negated; the vectors in the diagrams are
the negative normals).
The green solid is added to the difference, and the process continues with
the new sliced red solid.
In this manner, for each face which intersects the red solid,
the red solid is sliced smaller against that face,
and the piece which is sliced off is added to the difference list
(the list of solids which represents the difference). At the end,
the red solid is the intersection, and the green solids are the difference.
Figure 6a

Figure 6b

Figure 6c

Figure 6d

Figure 6e

Figure 6f

When the hidden solid removal algorithm is done, all solids in the space
will have been sliced by the silhouette tubes of all solids in front of them,
and all pieces which lay in the silhouette tubes will have been removed
from the space (Figure 7). This ensures that everything which was obscured in the
original space will be missing in the resulting space,
so projection can safely continue; all projected solids will be distinct.
Figure 7

Projection
The projection algorithm works in much the same way as the silhouette
algorithm. For each frontface, the edges shared with all adjacent faces (not just backfaces)
are computed, and are projected to the destination space
(Figure 8). The combination of all projected edges defines the projected face
as a single solid in the destination space
using the same representation as is used elsewhere (intersection of halfspaces).
Note that in Figure 8, lighting has also
been applied to the projection, as though a white light were coming from negative y;
the faces which face most directly towards negative y are the brightest.
Figure 8

Rendering in 2D
ADSODA uses OpenGL to render solids (polygons) in 2D.
It draws the outline of the polygon by starting at the top
corner (in screen coordinates), connecting the dots down the right side,
and connecting the dots back up the left side. Since there is no
information in the basic representation about the order corners
should be drawn in, it is necessary to explicitly compute this order.
ADSODA does this by sorting corners on their y coordinates,
finding
the top and bottom points (first and last in the sort), using the line segment between them
to find which side of the polygon the other corners lie on,
and then traversing the corners as described above (down the right, up the left).
Rendering in 3D
ADSODA can use OpenGL to render solids in 3D.
It draws each face of the solid as a 3dimensional polygon.
Since there is no information about the order to draw the
vertices in, ADSODA must determine this before it draws.
It does this by arbitrarily choosing two corners, p_{1}
and p_{2}.
For each corner from p_{2} to p_{n},
it determines the angle between
p_{1}p_{2} and
p_{1}p_{n}
using the following formula:
It negates the resulting angle when
the face normal faces away from
p_{1}p_{2} x
p_{2}p_{n}.
This gives an ordering which can be used directly to
order the drawing of the vertices.
Figure 9

It's also possible to render a threedimensional space with ADSODA by
performing the projection to two dimensions using ADSODA's algorithms,
and then rendering it in 2D, but this is slower than taking advantage
of OpenGL's fast rendering algorithms.
Implementation Details
ADSODA is written in C++. It requires the Standard Template Library, and
uses a very limited portion of OpenGL for rendering (polygons, polylines, and colors).
It has been successfully built using both g++, the SGI C++ compiler,
and Microsoft Visual C++.
It implements the following classes:
 Vector: an ndimensional vector
 AMatrix: an nbyn matrix
 Color: a color
 Face: one face of a Solid
 Halfspace: an ndimensional halfspace
 Light: an ndimensional light
 Solid: an ndimensional solid object (a collection of Faces)
 Space: an ndimensional space (a collection of Solids, and a
collection of Lights).
The file demo.cpp implements 2, 3, and 4dimensional demonstrations.
You can download the source code for ADSODA from here.
Credits
Thanks to Antonio Costa, whose implementation of CSG in his rtrace ray tracing program
helped to inspire the CSGstyle solid representation used in ADSODA.
Thanks to the many users of my Macintosh program HyperCuber, whose requests
spurred me to develop a better way of drawing ndimensional objects.
Thanks to Dr. George Francis, whose Math 428 course at The University of Illinois
provided a means for me to invest the time necessary to complete this project,
and who provided invaluable help in creating the OpenGL demonstration.
Thanks to Stuart Levy, who provided additional help in getting the demonstration
up and running, especially in the CAVE at UIUC.
Thanks to Ben Schaeffer, who helped me to develop the algorithm, used for 3D rendering,
which orders the vertices by angle.
Sources
Foley, James D.; van Dam, Andries; Feiner, Steven; Hughes, John F.;
Computer Graphics: Principles and Practice, AddisonWesley Publishing Company, 1987.
Glassner, Andrew S. (Editor), Graphics Gems, Academic Press Professional, 1990.
Schneider, Dennis M., Linear Algebra: A Concrete Introduction, Macmillan Publishin Company,
New York, 1987.
Related Links
JeanFrancois Bigot has written a program called 4DNav,
using the Factor programming language, which uses ADSODA as its algorithm for hidden solid removal.
ADSODA was created by Greg Ferrar.