Before diving into the specifics of the research, I will provide some motivation for this "new" modeling method. The word "new" is singled out here since it is suspected that many higher powered systems, such as those used in the movie industry, make use of a similar method. A few selected products (limited to availability) were examined, in terms of model representation and device interaction.

All commercial and Share-Ware products reviewed during the course of this research deal exclusively with specifying the exterior of three-dimensional models. However, each appears to have its own unique method of dealing with this specification. Some products, such as Pov-Ray or Poly-Ray, require the use of scripts, and are equipped with a variety of shapes ready to go. Shapes such as ellipsoids and 3-D symbols are common. More commercial products, such as Soft F/X Modeler, allow a more interactive method of specifying vertices for lines, polygons, ellipsoids, and other basic shapes.

Some products represent their models exclusively through an exhaustive list of lines, polygons, and other very primitive shapes. This is quite time-consuming, and requires a lot of patience and precision on the part of the user. Others, such as freeware ray-tracers, provide smooth curvatures as their primitive shapes, allowing the user to customize them in a relatively limited manner. The major advantage with the ray-tracer is the ability to specify light sources, textures, and various optical effects with each surface. Since the rendering process is quite lengthy, however, this method can also be very time-consuming.

Putting aside the freeware ray-tracing programs, which offer no interactive interface, interactive modeling programs appear to offer a wide range of interfaces to devices. Traditional programs with the mouse, such as Soft F/X Modeler, provide a triple-view interface (as described later in section 4), where the mouse is used to choose and manipulate each point or primitive object.

More powerful tools, which could unfortunately only be examined through research papers in the SIGGRAPH publications, have been designed and implemented. One particularly interesting idea found in [Conner et al., 1992] describes the use of widgets, 3-D objects which encapsulate interactive behavior. The use of augmented transition networks (often defined as a finite state automaton) in this work allows new interactive transformations to be created by simply adding the network to the program and specifying the results of each state change.

By providing a more dynamic approach to rendering objects, it is hoped that the user will be less overwhelmed by the shear complexity of model representation. While this approach generally means that rendering algorithms are more complex, I believe the skeletal model will not introduce a significant time delay beyond what can be seen with an exhaustive external representation. Also, by using several ideas introduced in various SIGGRAPH publications for device manipulation, I hope to provide similar levels of interactivity as existing commercial and academic approaches to modeling.

There are two major features of the skeletal modeling technique which make it different from other methods. Joints and connections make up the framework, or skeleton, of the model. Each joint is allowed to be connected to as many other joints as desired. An entire 3-D object can therefore easily be defined by a single center joint with all its connected joints, making a "stick figure". Covers are then applied to each joint connection, giving the object a more realistic appearance, and providing features that may be difficult to reproduce with joints alone.

As was already eluded to, a joint is a single point in space to which one or many other joints may be connected. For the purpose of this research, the center joint of a 3-D object is the root of a tree of joints. Therefore, each joint can have at most one parent joint, and zero only if it is the center joint. An extension to this idea might be to allow multiple center joints for each 3-D object (so that transformations applied to one object appear to apply to several disconnected objects). The term connection is used to refer to the line connecting two joints together.

This approach to modeling has potential to provide an easy mechanism for interacting with the object as a whole, and with each individual joint and connection. Imagine a two-dimensional device such as a mouse attempting to indicate which portion of the overall model it is to interact with next. Rather than having to deal with the inherent problems in transforming a 2-D point-and-click to some existing 3-D point on the surface of the model, the device can be used to maneuver through the object directly. Up and down movement will travel down child and parent connections, respectively. Side-to-side movement will allow the device to choose which child to travel to with the next "up" motion. The figure to the right shows how mouse movement might allow this type of travelling through the 3-D object.

In addition to this interaction potential, the user will be presented with fewer points to work with. At the very least, the work will be distributed between specifying the skeletal structure and the individual covers. This is always a major concern when creating relatively complex 3-D objects.

Perhaps more important than interactivity and complexity is the issue of how transformations will affect the 3-D object. Another projected advantage of using joints and connections is the ability to transform an entire sub-tree with respect to the parent. Additionally, the types of transformations which can be applied become more intuitive and perhaps more dynamic (an issue I will discuss later dealing with animation).

The first issue I will deal with is the ability to transform the position of a joint with respect to its parent. By placing a new joint in some initial position, and allowing transformations to occur relative to its parent, it is anticipated that the user should be able to place the joint in its desired position with more ease. This can be illustrated with the simple fact that intuitive transformations such as lengthening, rotation around the parent connection, and extensions all become possible.

The figure to the right shows three joints, where the child is the joint the user wishes to manipulate. The process of lengthening uses the child-parent connection as its basis, and essentially scales the child’s position away from the parent (as if it were the origin). The process of rotation performs a rotation around the parent-grandparent connection. The process of extending performs a rotation around either the X- or Y-axis, as desired by the user. Note that the axes portrayed in this illustration make up the orientation of the child-parent connection. The connection from the parent to the child is therefore the Z-axis. To make an analogy, extending is similar to the way our own joints (in our fingers, at our elbows, and at our knees) allow motion. This final type of transformation indicates an important requirement: each connection must be oriented in some fashion. As will be seen later, this is also necessary for proper representation of covers.

Early on during the research, it was recognized that various different types of joints occur in nature, and should be considered for this project as well. While these individual types are not necessarily implemented differently, there may be other features (such as animation) which would make use of differing types. Classification issues for joints involve flexibility (for example, our elbows as opposed to our wrists), the inherent location within the object (how does one specify the skull, for example), and proximity to connecting joints (consider our spinal column).

Here, I will discuss four possible joint types. Note that these are not currently implemented differently – rather they are a distinction the modeler makes when using the skeletal method. It is also helpful to classify joints for the purpose of terminology that will be used throughout the remainder of this paper. Also note that while I use the human body as a reference, this is not to suggest that this is the only object we can create with the skeletal model!

A central joint consists of perhaps a few or many connected joints in varying directions, and may have a complex cover surrounding it. As an example, the pelvic region or the bottom of the neck may be considered a central joint.

A flexible joint connects two joints together in a linear fashion, such as the knee or elbow joints. These are particularly useful for the extension transformations described earlier.

An end joint is located at the exterior (or at the "leaf" joints) of the object, and therefore has no child connections. These require special attention since the corresponding cover should appear "closed off".

A spinal joint is located within an inflexible, linear collection of joints. This distinction is made as a more complete implementation might consider allowing covers to span multiple connections. When considering our spinal column (and hence the term spinal joint), while many joints make up this region, it would be useful for the modeler to only have to specify a single cover, rather than one cover for every joint.

Covers are a more exhaustive representation of a 3-D model. While it is potentially possible to explore many different types of covers (from single polygonal representations to mathematical equations), this research has restricted itself to collections of polygons in space. The most important features about using covers are their relative simplicity, as compared to the entire 3-D object, and their reusability.

A major decision had to be made as to what exactly covers should surround – the joints themselves, or the connections. This decision resulted from the most prominent problem that arose during the research: how will the modeling program connect adjoining covers together? For simpler joints such as flexible and end joints, covers could potentially surround either the joints or the connections. However, the more complicated central joint would have trouble understanding how its children should connect to itself if the covers surrounded the joints.

For example, consider the figure to the right. The open-ended cube represents the cover for the parent joint. If the two children joints are to have similar covers surrounding them, a decision must be made as to where the three covers should join. It is conceivable that the bottom lines can be divided amongst the two covers, as illustrated by the red arrows. However, this is somewhat confusing, and relies on the fact that the parent’s cover must be precisely specified. As will be seen, a more dynamic and intuitive approach is to surround the connections with the covers.

Now consider the figure to the left. The open-ended cube now represents the cover for the grandparent-parent connection. Again, the decision must be made as to where the children covers should join. Here, if the parent-child connections have a similar cover, then dividing amongst them makes more sense. The parent joint can also adapt to an expanding number of children without worrying about the precise representation of the cover.

This now leads to the problem of connecting children together. The question "do children actually connect together, and if so, how" begs an answer. In fact, I believe the modeling program should allow one of perhaps several choices. First, each child cover may be its own connection (consider a 3-D object representing a collection of pipes). Second, children covers should be connected in an open-ended manner to the next child (consider the individual joints we have in our hands). A third, more complicated option might allow children covers to be connected in a circular open-ended manner, where the final child reconnects back to the first child.

Up to this point, I have only provided a relatively abstract discussion of how adjoining covers connect to one another. Since each connection has its own cover, taken from what it supposed to be a reusable collection, the modeling program itself should be able to determine how to connect them properly. This will free the user from creating covers specific to the connection.

In two dimensions, it is useful to consider the usual problem that printers have connecting two lines together. In the blown-up view of two lines to the right we can see the method printers use to solve this problem. The ends would normally partially intersect (where the angle is less than ninety degrees), and introduce a small gap (where the angle is greater than ninety degrees). The corrected image simply fills in the gap with a smooth circular end.

However, in three dimensions, such a solution is no longer feasible, particularly if the modeling program wishes to show the object in real time while the user works on it. Additional problems can arise in three dimensional covers: endpoints will rarely, if ever, actually meet, and the potential of intersecting polygons is far too great. I have chosen to solve this difficulty by determining the average of the endpoints and connecting them directly. This solution is relatively simple to compute, and has potential to provide a dynamic approach to rendering 3-D objects.

The figure to the right, which shows a cover over a connection, orients the cover in the most predictable manner. An enlightened reader will realize that the cover can be rotated around its connection. In fact, each connection should maintain its own orientation information. This is aided by using the imaginary line between joints as the z-axis, and allowing the user to rotate the x- and y-axes around this as desired.

This orientation problem, easily fixed as just described, would have been far more difficult if the covers surrounded the joints instead. Each time a joint is specified, the orientation of the cover would have to be resolved, and any changes to the orientation may cause problems with connected covers.

By placing the covers around an oriented connection, and directly connecting the endpoint together (as described in section 2.2.2), the modeling program adapts to any change. In fact, the user can also be supplied with a powerful, but easily implemented option of automatically rotating the child joints around the parent while the orientation (of the grandparent-parent connection) is being manipulated. It is important to realize that this should only be an option, since it is somewhat presumptuous to change such a large portion of the object while the user may only be interested in a single connection.

Now that it is established that covers surround connections, and each connection maintains its own orientation, it is essential to consider two additional problems: what orientation does the modeling program give to a new connection, and how transformations will affect the orientation. The first problem can be approached in an arbitrary manner, while the second problem must be dealt with more precisely.

Solving the problem of assigning an appropriate orientation to new connections depends on whether the new joint has any siblings, and whether it has a grandparent. If the new joint has no parent (i.e. it is the first joint the user is plotting), then there is no connection to even worry about. In other cases, while it is possible to simply provide a completely arbitrary orientation, it would be helpful to the user if it "followed" the parent-grandparent connection or any sibling connections. By an arbitrary orientation, I am not implying randomly generated X- and Y-axes. Rather, any X- and Y-axis is allowed within the restriction that all these axes (normalized) dot products sum to zero.

The following algorithm can be used, where C denotes the new joint, P denotes the parent joint of C, G denotes the grandparent joint of C, and S denotes the previous sibling joint of C. Note that the Z-axis of the C-P connection follows the vector joining the two joints together.

• If the new joint has any sibling joints, then find the cross product of vector C-P with the Y-axis of the S-P connection. This produces the new X-axis.
• Else if the new joint has a grandparent joint, then find the cross product of vector C-P with the Y-axis of the P-G connection. This produces the new X-axis.
• Else provide an arbitrary orientation.

The process of finding the new Y-axis is trivial: it is the X-axis crossed by the Z-axis.

Many transformations will either have no effect, or at least a predictable effect, on the orientation of a connection. Lengthening moves the joint along the Z-axis of the connection. This will only have an effect on the orientation if the joint is "lengthened" by a negative factor, where the X- and Y-axes will just flip their direction. Rotation around the parent connection simply becomes the task of rotating the entire orientation. Extensions are just rotations around either the X- or Y-axis, so they too rotate the entire orientation.

However, the normally simple act of translation is not as predictable, as it gives the user much more freedom for manipulation. A similar method that was used to assign orientation to new connections can be used. The new X-axis can be determined by finding the cross product of the new Z-axis with the old Y-axis.

The software created during the course of this research made use of the object-oriented features of C++, whenever possible, on a Windows 95 platform. Since some aspects of this operating system still hold remnants of conventional C callback routines, much of the code dealing with device interaction was done in C. In this section, I will describe the abstract data types developed for use with the skeletal modeling technique.

At an overall level, the modeling program itself keeps track of the current 3-D object it is working with, including the particular joint and connection as well as interactive information. It makes use of a list of scenes (described in section 3.3) to determine which drawing surfaces need to be updated. A list of available 3-D objects is also maintained.

A point, vector, polygon (also called a point list), and polygon list are all primitive classes which make up the more abstract data types. As I am sure any reader can immediately imagine the exact data structure and much of the implementation of these simple classes, I will say relatively little about them. They each have their own constructors and destructors, and a list of intuitive operations. Points and vectors have the usual overloaded operators, as well as functions for rotation around an arbitrary axis, dot products, and cross products.

One special operation is included with polygons. This involves joining together two point lists to create a polygon list. The need for this operation will be revealed later when I describe the implementation details of covers. The algorithm will be described in section 3.7.1.

A drawing surface is a visual two-dimensional surface to which rendering of 3-D objects can take place. An abstract class represents any type of drawing surface, and provides the code which must draw three-dimensional shapes with a common interface. Thus, new types of surfaces (for example, a PostScript file) can be created simply by writing the lower-level code for actual drawing (with the PostScript example, this amounts to developing the proper string and appending it to the file). Each new type of drawing surface requires a subclass of this abstract class.

The abstract class defines the following data items:

• A title, which may be used as the subclass desires (in the title bar of a window, or as the filename, for example). This is specified when the drawing surface is created.
• Scaling and centering information, used to position the objects accordingly. In addition, the eye distance is included for drawing surfaces which have perspective correction.

Drawing to the surface must be surrounding by calls to Start-Draw and Finish-Draw routines. This is to ensure that any type of surface is accommodated. Files, for example, require some special attention for opening and closing operations. Even windows may want to make use of an off-screen in order to prevent flashing artifacts when the object is regenerated.

Abstract functions allow the user code to specify pen color as well as fill color (for the interior of polygons) for all future drawing operations. There are three simple drawing operations available to user code: a point, a line, and a polygon. Two internal operations can be inherited and used by subclasses for projection purposes, each of which return the final X and Y co-ordinates of a given point in space. These include a perspective correction function and an orthographic projection function.

It is worth noting that the drawing surfaces implemented in this project assumes the following orientation: X to the right, Y up, and Z out of the screen. Additionally, no camera manipulation is allowed (a common assumption while a user is working with the object) – but object manipulation is possible.

While not entirely necessary, the scene allows a drawing surface to include multiple three-dimensional objects. Each scene (a C++ class) is associated with a single drawing surface (which may change at run-time of course), and contains a list of 3-D objects which may be manipulated with simple add and remove operations. User code may test for availability of a particular object within the scene, and may indicate that the scene should be rendered.

The 3-D object was actually implemented as an abstract class with no data, and only the transformation and abstract rendering operations at its disposal (I am anticipating future expansion). A skeletal object is a subclass of this which provides a single central joint as its data.

A joint is implemented as a point in space with a pointer back to its parent joint (if it has one), and a list of child connections. The fundamental transformation operations available to the user are available here, including translation, rotation around the parent-grandparent connection, extensions with relation to the orientation of the connection to the parent, and lengthening. Additionally, a rendering operation is provided which renders all child connections (and then calls the child joints’ render operations as well).

Several attachment and detachment capabilities could be made available to the user. An attach-child function generates a new child joint and creates the connection to it (specifying the orientation as described in section 2.3.1. A delete-sub-tree operation removes the joint and its connection to its parent, as well as any child joints. More powerful operations may be included in the future: an attach-object function which makes a copy of an entire object and makes its central joint equivalent to the joint for which the function was called, and a delete-connection function which removes the joint and the connection to its parent but which attaches all of the child joints back onto the parent (rather than deleting them, as in the delete-sub-tree function).

A connection is made up of the child joint, the X- and Y- axis orientation, and the cover which should surround the connection. Additionally, flag information specifying whether the connection should be open-ended to its siblings is provided. In the future, texture information might be included, which would be particularly useful if DirectX or OpenGL drawing surfaces are built (these are graphics libraries available on the PC platform which have built in rendering capabilities for texture mapping).

Aside from internal implementation details, only a rendering function is available to user code. This function determines the exact representation of the cover in terms of polygons, z-buffers them (i.e. sorts them by their depth, or distance from the viewer), and then calls the drawing surface routines available. More details on the overall rendering process is available in section 3.7.2. This particular rendering operation uses its cover and open-ended flag information to determine the exact polygons to generate.

As mentioned earlier in section 2.2, covers for the purpose of this research are restricted to polygonal representations. However, to support future expansion, an abstract cover class was created with no data. It provides subclasses with an operation to translate a point from one co-ordinate system to another, using an algorithm extracted from course notes in the Computer Graphics II course (74.449).

The basic subclass used in this project is the point list cover. This cover makes use of two sets of point lists, one for the parent joint and the other for the child joint. An additional list of point lists (!) can be supplied to provide more definition between the parent and child joints. The points are actually specified with the parent relative to the origin, and the child relative to 0,0,1. This particular implementation may at first seem strange, so I will explain now why it is used. The actual polygons which make up the cover are not the point lists directly specified. If the parent point list is {P0, P1, …, Pn} and the child point list is {C0, C1, …, Cn} and there are no intermediate point lists, then the first polygon is <P0, P1, C1, C0>, the second polygon is <P1, P2, C2, C1>, and so on. The algorithm initially presented in section 3.1 and described in more detail in 3.7.1 handles cases when the number of corresponding points are not equal.

User code is provided with a function which, given the orientation of a connection, produces the list of polygons which actually cover the connection. This list of polygons is still subject to the averaging mechanism described in section 2.2.2 in order to connect adjoining covers together.

Given a two lists of points {P0, P1, …, Pn} and {Q0, Q1, …, Qm}, where "n" and "m" are not necessarily equal, this algorithm determines a list of polygons which connect the two point lists together. It makes use of a "one-dimensional scaler" which jumps along each list of points, perhaps using midpoints between them in order to accommodate differences in "n" and "m", and generates a single polygon at each jump. As the only real way to see how this "scaler" works is to examine the code, I provide it here. The actual code which generates the polygons simply calls the Jump method for each "scaler" until all points are exhausted.

Any interested readers are invited to use this code for a multitude of purposes (with slight modifications depending on the application) – from drawing a line to scaling an image to rendering a texture (I know I use it!).

The rendering of a skeletal model actually takes place at several different levels. The order of render method calls is as follows: the user request – the list of scenes – an individual scene – an object – the joint – and finally, the connection (which also calls the cover to determine the relative locations of each polygon). At the list of scenes, each scenes’ render method is called. At an individual scene, the scene is first queried for an object, and then the object’s render method is called. This in turn calls the central joint’s render method (for a skeletal model; this may be different if future object subclasses are created).

Once the call reaches the joint’s method, things get more complicated. At the object level, we actually must keep track of the depth of each connection and draw them from back to front. This is achieved with a modified merge sort algorithm which also uses an insertion sort for linear connections. The skeleton is traversed depth first, sorting child connections as just described. The following example illustrates the algorithm. Note that we do not know the depth of each joint specified in the diagram below.

1. Begin with an empty list.
2. Insert connection 1-2.
3. Traverse down to joint 3.
1. Begin with an empty list.
2. Insert connection 2-3.
3. Insert connection 3-4.
4. Insert connection 4-5.
4. Merge list 1-2 with 2-3-4-5.
5. Traverse down to joint 6.
1. Begin with an empty list.
2. Insert connection 2-6.
3. Insert connection 6-7.
4. Traverse down to joint 8.
1. Begin with an empty list.
2. Insert connection 7-8.
5. Merge list 2-6-7 with 7-8.
6. Traverse down to joint 9.
1. Begin with an empty list.
2. Insert connection 7-9.
7. Merge list 2-6-7, 7-8 with 7-9
6. Merge list 1-2, 2-3-4-5 with 2-6-7, 7-8, 7-9.

This results in the sorted list of connections to render. At this point, the render method of each connection in the list is called, as was described in section 3.5. It is interesting to note that polygons are only z-buffered at the connection level.

With such a strong tie into the drawing surface abstract class described in section 3.2, it is relatively easy to create a new user interface. Although an actual interface was not created on any platform other than Windows 95, I suspect the code without the particular drawing surface subclasses developed, is portable to both Unix and Macintosh (it compiles fine on the Unix machines!).

The actual user interface consists of a common menu bar with options available to create a new scene, where the type of drawing surface is selectable. Existing objects can be added and removed from the surface as desired. Operations to perform are selected from one menu which allows the user to choose between travelling through the skeletal structure, reorienting the current connection, translating or rotating the entire current object, or performing a transformation operation on the current joint. The operations are affected on the object by holding the mouse button while manipulating with movement.

Here, I will describe two individual drawing surfaces, each encapsulated within a single subclass. As it turns out, the most intuitive interface allows the user to use both types of drawing surfaces – the perspective window provides a good image of what the object actually looks like, while the triple-view window allows better fine tuning.

This interface provides three separate viewing areas, one looking down the X-axis, another looking down the Y-axis, and the other looking down the Z-axis. Each simply extracts the other two co-ordinates from each point and renders accordingly in each viewing area. The user can also tab between each of these three views while performing an operation.

This type of surface shows the user exactly what the object looks like by performing a perspective correction on each point. Each drawing operation occurs in a single viewing area.

There are several ideas which deserve future exploration that result from the use of the skeletal model. In particular, the dynamic nature with which connections are rendered provides a number of possibilities regarding creating and manipulating 3-D objects at run-time. Using an idea known as "degrees of freedom", coupled with the fact that transformations applied to a single joint affect that entire sub-tree of joints, I believe animation is a potential possibility. I will finish off this discussion with some of the limitations found using the skeletal model.

Earlier on in section 3.4, it was mentioned that a potential operation on a joint might copy and connect an existing 3-D object to it. While this in itself could allow a dynamic approach to creating and manipulating objects at run-time, the reverse of this may also be useful. Imagine being able to sever a connection to create an entirely new object. Being a computer game enthusiast, I can think of several uses for this!

Another possible method of run-time manipulation is to replace the cover for a particular connection. Since the render algorithm handles connecting adjoining covers automatically, this replacement is entirely possible, and may provide useful effects.

By re-rendering an object while applying small consecutive transformations to individual joints, the potential for animation with very little added data is very high. One concept dealing with "degrees of freedom" recognizes the requirement to specify limitations on how free the user is to manipulate a particular portion of an object. This can be incorporated into each connection, where a maximum rotation and extension potential might be specified, for example.

Several limitations are incurred by the use of the skeletal modeling technique. The most common limitation for almost any interactive modeling is that objects created are only as good as the artist. The difficulty of precisely specifying a point in space, although somewhat alleviated with the ability to transform joints relative to the parent connection, is still apparent. Additionally, the skeletal technique relies partially on the use of appropriately complex covers, which must be specified in the conventional exhaustive manner.

Another prominent drawback is that skeletal models, with the use of polyhedrons as the covers, do tend to appear somewhat rigid and blocky, particularly with simple covers. Also, with the chosen method of connecting adjoining covers, the final representation of the object is slightly unpredictable. For example, if the angle between two connections becomes too small, the area around the joint will get skinnier.

At such an early stage during the testing and use of the software developed, and considering this project is largely open-ended, it is difficult to predict exactly how effective the skeletal modeling technique is for user interaction. Additionally, as I have been the exclusive user of the software, my own tie to it can only serve to overemphasize its effectiveness. However, I strongly believe that this approach provides a good alternative to an exhaustive external representation of 3-D models, as it requires less raw data to produce comparably more complex objects.