INTRODUCTION
Interactive Graphics significantly enhances our ability to understand data, to perceive trends, and to visualize real or imaginary objects--indeed, to create "virtual worlds" that we can explore from arbitrary points of view [2]. Virtual worlds can be found in applications ranging from computer aided modeling and simulation to entertainment and games. The most obvious way to hold a user’s belief in a virtual world is to make it look like the real world. However it is usually not enough to make a virtual world look realistic. There must be interesting places to go, objects to interact with or seemingly intelligent agents that reside in the world. With the aid of 3D graphics a user is able to navigate in virtual space and explore the world from various points of views. By using some basic animation objects can be given motion and finally by scripting these animations, objects can also be made to “behave”.
Macromedia Director [1] is a software tool that is used for producing multimedia presentations using media such as bitmaps, sounds and text. It provides users with some animation utilities to enable them to create 2D animations. It even includes a sophisticated object oriented scripting language (Lingo) which enables users to “direct” the 2D objects on the screen. Because of the extensible internal design provided by the Macromedia Open Architecture (MOA) , the Director 7 Software Development Kit provides the necessary capabilities for third party developers to create plug-ins called “Xtras” which enhance Director’s features. The MOA model is derived from Microsoft’s Component Object Model (COM) and serves to provide a consistent and modular method to implement the extensions. By default Director has no methods of displaying and manipulating 3D data. The aim of this project therefore is to enhance its capabilities by providing functions to manipulate 3D objects.
CHAPTER 1
THE SCENE GRAPH
1.1
The Problem
OpenGL, SGI’s (Silicon Graphics Inc.) 3D graphics library was to be used to render the 3D objects required. However, using the OpenGL API (Application Programmer Interface) by itself was not enough to satisfy the requirements of building the Xtra. Graphics primitives called through OpenGL under immediate mode are only sent to the rendering hardware and are not stored any where internally within the library. OpenGL does possess a method of storing primitives in a structure known as a display list but once the contents of a display is set, it is non editable unless the entire structure is rebuilt from the start. This would be highly unsuitable for animation since animation requires small changes in an object properties each frame. Thus it was necessary to build an extra layer that sat on top of OpenGL to store and manage 3D information that would otherwise be lost. This layer is the scene graph, and it represents the core of the system implementation.
1.2 What is a Scene Graph?
A scene graph is a hierarchical data structure that is used to describe objects and their attributes. It is used to store data in an efficient and organized manner so that objects can be rendered quickly and efficiently. Data is stored in nodes that are connected together to form a graph-like structure (See Figure 1). Almost every function the system performs can be achieved through proper placement of the appropriate data nodes in the scene graph at the appropriate positions. By doing so the scene graph controls the rendering state and the information passed into the immediate mode API. The scene graph also makes modeling easier because it allows one to construct scene elements based on a hierarchy of objects. (See section 2.3 on Hierarchical modeling)
1.3 Why
use a Scene Graph?
1.3.1 Immediate Mode and Display Lists
Graphics APIs usually present the user with an immediate or a display list model. The immediate model requires that the user describe the scene by passing graphics primitives to the rendering pipeline each time it is to be displayed. If the scene or the viewpoint of the scene changes then it is up to the application to retransmit all the data that is needed to describe the new scene since no data is retained within the graphics system itself. While this means that it is relatively quick and efficient to modify primitives and their attributes, the application must provide code to generate scene data that is acceptable to the graphics system[3]. Also the application must provide functions when rendering involves multiple, specialized passes over the database or special initialization of the environment.
With a display list model the graphics system provides an
internal database that the application can use to store frequently called
primitives. The database will be a list of primitives that the renderer will be
required to draw. Traditional graphic standards such as GKS supported the use
of primitive aggregation in structures called segments. Later standards such as PHIGS supported a multi-level
data structure from which part hierarchies can be constructed and the
manipulation of the structure as a whole or as separate elements were possible.
For a small modification of the scene, an application can usually make use of
editing calls to edit the display list. However if the application needed to
rapidly modify large portions of the scene database for each frame or if the
application was highly interactive then editing the display list may be
inefficient [3]. Kaplan also stated that it might be difficult for the user to
write code that allows the display to track the status of the internal data
representations closely.
1.3.2 Graphics is
Object Oriented
In the development of the Dore Graphics System [3], Kaplan
stated that the key to Dore's architecture were abstractions such as ease of use, flexibility, modularity and
extensibility, advantages that an object oriented system would be able to
provide. Wisskirchen[4] supported the use of object oriented methodologies in
interactive graphics by saying that “Interactive graphics has always been
object-oriented in the sense that what we intuitively consider to be objects
were indeed the central subject of treatment”. The close relationship between
object oriented methods and interactive graphics naturally led to toolkits that
hid away the low level rendering details and described the image through the
idea of objects in a scene. In the scene metaphor there are objects (objects
which exist in the scene), the notion of a camera (an object which will produce
an image) and lights (objects which illuminate the scene)
An example was GROOP, (Graphics using Object-Oriented
Programming) which was developed by the IBM Research Centre and the Georgia
Institute of Technology in 1993[5]. GROOP was an object oriented 3D toolkit for
creating animated 3D computer-generated graphics. GROOP's aim was to simplify
the creation of graphics applications by separating the scene description from
the rendering pipeline. Simple animation could be quickly constructed by
creating objects, adding them to the scene and applying transformations. The
scene information is stored in a hierarchical nesting of GeometricObjects where
materials, transformations and geometric data were localised attributes of a
GeometricObject. GeometricObjects may be aggregated together in containers that
were composite objects. A composite object may be manipulated as a single
object during transformations or when assigned material properties. In
addition, composites could contain other composites, which led to hierarchies
of composed complex objects.
The hierarchical structuring of complex objects evolved into
tree like data structures that would be able to describe the whole scene. Such
structures were called scene graphs and would not only include the hierarchy of
complex objects but also other objects such as lights and cameras. Open
Inventor [6] was a good example of a graphics toolkit with scene graph support
built on top of the OpenGL library.
Nodes on the tree would be used to represent the individual objects. As
well as the nodes which held the geometry of 3D objects, there would be other
nodes which would represent other data required by the scene such as composite
containers, transformations, vertex information, materials and colours. Nodes
could be referenced by more than one parent so Open Inventor's scene graph
could be better described as a directed acyclic graph (DAG) rather than a tree.
It also meant that the data in nodes could be shared by different sections of
the scene graph thus saving on storage space. To perform certain actions on a
scene graph the tree would be traversed and nodes would be visited from top to
bottom, left to right. For example, in order to render the scene a
"draw" message would be sent from the top of the hierarchy. This
message would propagate down the tree and upon receiving the message, each node
would perform different actions depending on what type of node it was e.g. an
SoShape node would draw an object to the display while an SoTransformation node
would concatenate the current transformation matrix with its own. This was a good
example of the object-oriented idea of polymorphism at work.
1.3.3 Primitives Vs Objects
The scene graph approach is usually the one taken by traditional
retained mode graphics packages. Graphics packages like Direct3D Retained Mode
and Open Inventor make use of the scene graph API because it makes it easier to
write 3D graphical programs. With an
immediate mode API the user has to describe the scene using low-level
primitives. With a scene graph the user is able to describe a scene in a manner
that is similar to the way we naturally think about objects in the world. A
scene graph is a higher-level form of 3D graphics programming as it enables
users to describe models instead of
primitives. The scene graph would then be responsible for feeding the
primitives to the immediate mode API.
Sowizral [7] mentions that scene graphs “allow programmers to
forget about controlling the rendering pipeline and instead think about content
and how best to present it.” He predicted that the great majority of 3D
graphics programs would exclusively use scene graphs in the new millennium.
Most current 3D programs already use some form of scene graph technology, which
is usually optimized for their domain, to manage their database. Although the
databases of these programs are not exactly considered as "true"
scene graphs, nevertheless there is still a need to manage data in a consistent
and efficient manner.
1.3.4 Scene Graphs as game engines
Some commercial 3D game engines have already taken the approach
used by traditional scene graph graphics APIs. One example is Numerical
Design's NetImmerse Engine [8]. The graphical database used by NetImmerse is a
scene graph that interfaces to common 3D engine elements. The scene graph is an
integrated data structure that stores the audio emitters, bounding volumes,
transformations and properties as well as the geometric data for the 3D scene.
Functions such as collision detection and geometry updates are handled by
partial traversals of the scene graph.
The hierarchy provided by the structure of the scene graph
played a central role to NetImmerse's internal workings. For example, culling
of invisible objects in NetImmerse was performed by maintaining bounding
spheres at each hierarchy level that are updated as the scene changes. The
advantage of hierarchical culling is that the traversal can bypass whole
subtrees that lie outside the viewing frustum. A less obvious advantage is that
culling tests do not have to be performed on every object if the scene is set
in a hierarchy. If a node's bounding sphere lies completely below the top
clipping plane and completely beyond the near clipping plane then there is
further need to perform the same clipping tests on the node's children. If the
bounding sphere lies completely within the viewing frustum, then the whole sub
tree can be eliminated from the clipping test. Collision detection also
benefits from the hierarchical structure of the database. A simple hierarchical
technique suggested by the author was to check for an intersection between the
bounding spheres of two complex objects. If the bounding spheres intersect then
a collision might have occurred. In this case, the sub trees are recursively
traversed and the bounding spheres of the children objects are tested for
intersections.
CHAPTER 2
SCENE GRAPH IMPLEMENTATION
2.1 The Composite Pattern
The scene graph model is an example of the Composite pattern described in [9]. It enables objects composing into tree structures to form part-whole hierarchies. Each object may be combined to form larger components which may be further grouped together to form even larger components. Although each object might perform a different task, the interface for handling any one of these objects remains the same in view of the client. The Composite pattern is achieved through an abstract base class that represents both leaf and container classes. This abstract base class declares methods that represent the interface for objects in the composition. According to [9], there are four participants that make up the Composite pattern. These are:
1) Component: The class that declares the interface for objects and implements the default behaviour for the interface common to all classes.
2) Leaf: Nodes in the tree structure that terminate a sub-hierarchy and invoke a method unique to the leaf node.
3) Composite: nodes in the tree structure that define the behaviour that enables objects to have children and implement the child-related methods.
4) Client: A class which manipulates the composition through the Component interface
2.2 Class Hierarchy of the Scene Graph
In the scene graph implemented, the analogy to the Component class is an abstract base class called Node. The Node class defines the default behaviour for each of the individual node objects in the scene graph. Almost every function in the Node class has been declared as a virtual function with an implementation that either does nothing or performs a default action. Included in the declaration are the tree management functions such as AddChild( ) and DeleteChild( ) which provide the interface for the construction of the scene graph as well as functions that are common to all nodes such as Draw( ) . The real implementations of these functions are to be found in the Composite and Leaf classes. Node does contain a few methods that are implemented within the class. For example, all nodes contain a label which may be set by the method setLabel( ). The Node class is also responsible for memory management routines (See Section 2.5: Component sharing) so that is also an implemented method within the class. The declaration of class Node may be found listed as Appendix A.1.
The Composite class is one of the most important classes in the class diagram (See… for declaration of class Composite). Composite is the class that enables grouping of the nodes in the scene graph by implementing the behaviour that enables nodes to have children. Although the child management routines might have been declared in the Node class, the Composite class contains the actual implementation of the routines. Included methods of the Composite class are AddChild(Node*) and DeleteChild(Node*) which enable a Composite node to add or delete a node under its hierarchy. There are also node retrieval methods such as GetChild(string) and GetChildAtPosition(int) to help retrieve nodes in a hierarchy. The data structure used to store a Composite’s children is the STL(Standard Template Library) list found in C++. The Draw( ) function of the Composite class, calls the Draw( ) method of each child under the hierarchy. This enables the Draw message to propagate down from the top of the hierarchy to the lower leaf nodes.
The leaf nodes are different from the Composite nodes in that they are incapable of having any child nodes. Also, they do not implement any methods that enable them to do so. The leaf node classes consist of two major base classes that are derived from the class Node. Shape nodes specify geometry that is to be displayed on the screen and implement both the Draw and Prepare functionalities. Nodes of type Shape are usually the ones that call OpenGL’s functions that enable primitives to be sent to the rendering hardware. Shape is a base class with different types of shapes being derived from it. Some of the derived classes include simple geometric objects like cubes and pyramids, quadrics objects such as spheres and cylinders and an indexgeometry class which is used to store polygonal mesh data from models. (See section 2.8.3 Model Loader). The other base class derived from Node is the Attribute class. Attributes are nodes that usually affect the appearance of objects drawn by changing the current rendering state. An example of an attribute node is the Material node, which changes the current material type of an object when its Draw method is executed. Individual transformations such as translate, rotate and scale are also part of the Attribute class as they change the model view matrix by concatenating transformation matrices on to it.
In addition to the individual transformation classes, there is also another class which is a composition of a translate, rotate and scale node. This class has been named Transformation and represents the combined transformation of a translate, rotate and scale. The order of the transformation when OpenGL pops the matrix stack always goes scale, rotate then translate. If a scale or rotate needed to be performed around another point other than the local origin then the Transformation node enables the center point to be changed. The Transformation node is derived from the Composite node so all children of a Transformation node belong in the same local coordinate system.
2.3 Hierarchical Modeling
In the real world, objects are usually made up of a collection of components. For example, a car can be thought of consisting a chassis and four wheels. So when a car is translated, the wheels on the car must also be translated such that they remain in the same position relative to body. When moving the car it is not intuitive to perform separate transformations to each of the individual object parts. To keep track of all the transformations required by a more complicated object would be extremely difficult. Additionally we might also want to the wheels to rotate while the car is translating. Clearly, there is a need to perform transformations to an object as a whole and separately to each individual component.
The car can be represented as a hierarchy as in Figure 1. The car object sits at the top of the hierarchy with the individual chassis and wheel objects beneath it. Each object in the hierarchy has its own local coordinate system and local origin point. When a transformation is applied to the top of the hierarchy, the lower structures of the hierarchy will be transformed along with it. Transformations propagate down the hierarchy to lower level objects such that in our car example, if the car is moved the wheels will also move relative to the car. Since lower level objects have their own coordinate systems, it is possible to manipulate objects individually as well. Returning to our car example, if we wanted a wheel to rotate then it would just be a matter of applying a rotation around a local origin at the center of the wheel. Because transformations propagate downwards a hierarchy, a rotation performed on one wheel will not affect other wheels.
2.4 The Object Node
The Object class represents the concept of hierarchical modeling. Object is a class derived from Transformable (See section 4.3: The Transformable Node) which itself is derived from Transformation (See Figure 7). The Object class inherits methods available to the Transformation class such as translate( ) and rotate( ) as well as Transformable methods such as movestep( ) and rotatestep( ) . This enable object nodes to have the full set of transformation methods available to it. Transformation is derived from the class Composite. Because the Composite class provides the necessary methods to attach child objects under itself, the Object class is also able to do so. Although the system could have relied on just having the basic composite and leaf nodes, it soon became apparent that a higher-level node type was needed in order to hide away the unnecessary details involved in building the scene graph. The Object node is similar to a simplified version of Open Inventor’s Node Kits [6].
With the Object node, the various attribute and shape nodes are already organized correctly so the details of building a complex object sub graph are hidden away. The Object node has a member function, SetPart( ), which is used to create part hierarchies. Each node keeps a pointer to its parent part so that it simplifies moving up the structure and deleting a component when part hierarchies need to be altered.
The Draw( ) member function of an Object node involves calls to push and pop[13] the current rendering state. This ensures that children nodes of an object get transformed within the local coordinate system of its parent. It also ensures that a child node will inherit any material properties acquired by a parent node if the child has not already specified its own material properties.
2.4.1 Composition of the Object Node
Figure 8 is a diagram showing the various nodes present in an Object node after the constructor is called. The Object node keeps a pointer to each of these nodes so that they could be accessed right away, instead of calling the GetChild( ) member function to retrieve the appropriate node. The nodes attributes, appearance, childlist and shape are nodes of type Composite. Placing nodes into these container groups ensures proper organization of the nodes within the hierarchy.
The attribute composite node is where all the geometric data placed. Geometric data such as vertex coordinates are placed into this container. The appearance node is where the material or color properties of an object are to be placed. It determines what an object is going to look like. The childlist node groups together all the children parts of the object and the shape node contains any nodes that specify the geometry of the object. There are also transformation nodes that enable the object to be modeled. There will be times when geometry will not be properly located, oriented or scaled to fit the scene. Transformations need to be applied to these objects at the time they are displayed to create the necessary model [5]. These transformations correspond to transformations performed in modeling space.
2.5 Component sharing
One of the advantages of having a component-based system is that it makes it possible to share components. This is useful because it reduces storage requirements. For example, if a scene contains ten identical cars then the system only needs to store the geometry for one car. Each car can then be referenced by different transformation nodes to produce ten different instantiations of the car. Because each instance now possesses its own Transformation Node, the objects are able to move independent of one another. Another less obvious advantage is that, since all instances share the same geometry node, a change in the original geometry will change the appearance of all instances[10]. This can be useful in situations where there are a lot of similar shaped models in a scene. A diagram of how instancing works is presented below.
Now the scene graph is no longer a tree structure but a directed acyclic graph (DAG). This poses a problem when it comes to removing components from the scene graph. Now it is not possible to just delete a whole sub tree because other nodes may point to leaf nodes at the bottom of the hierarchy. The solution to this problem is to use a reference counting [11] scheme for the nodes.
Each node keeps track of how many pointers are currently pointing to it. The Node class has two member functions that allow rudimentary reference counting. AddRef increments the reference count of a node while UnRef decrements the reference count. The UnRef member function checks to see if the reference count has gone below one every time it is called. If this happens then it will destroy the node by calling its own destructor. The AddChild and DeleteChild member functions automatically add or delete a reference each time they are called. Clients may also call the AddRef function if they wish a node to explicitly remain around but must call UnRef when a node is no longer required for memory to be properly deallocated.
2.5.1 Creating Instances of Objects
The Object node is a collection of nodes that represent an object in the world. This makes copying of Object nodes a little more complicated than merely referencing the Shape node that represents the geometry of the original object. This is because the object could be a complex object made up multiple objects in a part hierarchy. For this reason the Object Node has been given a Copy( ) member function. This function creates a reference to the attribute node of the original object and adds it in as a child. It does the same thing to the shape node. To copy each part that a complex object might have, a new object node is created. Then the new object’s Copy member function is called on an object that is present in the childlist node. The process is repeated for each object in the childlist node.
2.6 The Camera
Every 3D system requires the notion of a camera, which displays the world on the screen. The camera is one of the most important components in the system because it enables us to see the scene. The camera must be able to navigate and orient itself around the world. A basic camera model would be similar to OpenGL’s gluLookAt( ) [13] function where an orientation view matrix is specified given the camera’s position, a view direction position and a view up vector. While this camera model was already included in the OpenGL library routines, a more sophisticated camera model was needed to simulate walking or flying.
In the case of first person perspective, moving forwards and backward, rotating left and right and looking up and down were the minimum requirements. One way of specifying orientation in 3D space involved the use of three Euler angles [14] commonly known as yaw, pitch and roll. The three angles specify rotation angles in the Y, X and Z axis respectively. To implement a basic “walking” camera, information about the camera’s forward and view up vector need to be updated as the orientation variables change. The scene can then be transformed into camera coordinates using the gluLookAt( ) function with the current position, forward direction and up vector of the camera. An implementation of a basic walk camera was taken from [15].
Although this implementation was adequate for walking, it was not suitable for flying through a scene while orienting at arbitrary directions. The problem with representing orientations with Euler angles is a phenomenon known as gimbal lock [14]. Take as an example an arrowhead pointing at the negative z direction. A rotation about the Y axis(yaw) turns the arrowhead left or right. Now suppose the arrowhead started pitching upwards (rotating about the X axis). At the point where the arrowhead is pointing up the Y axis, if we now try to perform a yaw, we find that the arrowhead will instead start to roll. This phenomenon occurs because rotating the arrowhead by ninety degrees on the X axis has rotated the Z axis onto the Y axis. Even worse, it becomes impossible to perform a rotation in the Y axis in this position. This problem occurs because Euler angles assume that the interactions of rolls about the axes are independent when in fact they are not [14].
To prevent gimbal lock on the camera, quaternions [16] were used.to represent the orientations of the camera. A unit quaternion describes a rotation in 3D space. It has the form a + bi + cj + dk where a, b, c and d are real numbers satisfying the equation a2+b2+c2+d2=1. A rotation by the angle θ about the vector [b,c,d] corresponds to the quaternion cos θ /2 +b sin θ/2i +c sin θ /2j+d sin θ/2 k. Multiple rotations can be achieved by multiplying multiple quaternions together [2]. The camera keeps a quaternion to keep track of its current orientation. Since the interface requires that users input the amount in degrees to turn the camera, these angles are first converted into a unit quaternion. Thus for a command such as RotateCamera (30), the quaternion to represent a rotation of 30 degrees in the Y axis is formed. This quaternion is now multiplied to the camera quaternion to produce a new unit quaternion that represents the combined rotations of the camera. When it is time to transform the scene into viewing coordinates, the camera quaternion is transformed into a matrix and concatenated into the modelview matrix under OpenGL.
2.6.1 Camera
Controls
The camera control functions are very similar to the functions that move objects (See section 4.4, Object Control Functions ). There are functions that move the camera forwards and backwards, rotate the camera as well as functions which shift and lift the camera. In addition, the camera also possesses some tracking functionalities that are useful for various purposes. The camera has three tracking modes. The first mode is the relative track mode, where the camera will remain at the same position relative to an object. The second mode is the align-with mode, where the camera will align its forward direction with the forward direction of the object of interest while it is tracking. This mode is useful for a first perspective view if the camera is placed near the origin of the objects local coordinate system. The third mode is the static point-at-object mode, where the camera will remain stationary while continuously pointing at the object specified. This mode is useful for that stationary pan shot as the object moves past.
2.7 View Frustum Culling
Under OpenGL, every coordinate vertex call gets transformed by the modelview and projection matrices before being clipped against the viewing volume. The viewing volume of a perspective projection is the frustum of a pyramid. One advantage that a scene graph has over an immediate mode API is that a scene graph “understands” objects. Because of this fact the scene graph is capable of knowing when an object is visible in the scene or not. In view frustum culling we decide whether an object is visible or not by checking to see if it is totally inside the view frustum. By deciding whether a model is inside the viewing frustum before hand, the scene graph can avoid sending the primitives to OpenGL thus avoiding the unnecessary processing time involved in clipping non-visible geometry.
Because it would be too much work to determine precisely if an object is within the frustum, we make an approximation to the object by using a bounding box around the object. The bounding box of each object is first calculated at the initial construction of the scene graph. Composite and shape nodes are the only node types that possess bounding boxes. The bounding volumes are calculated by starting from the bottom of the hierarchy, moving upwards and then updating the volumes of objects in higher levels. This ensures that the volume of parent objects encompasses the volumes of all of their children. The box of each object is stored as eight vertices in local space. These eight vertices form the corners of the reference bounding box.. The reference box will always be axis aligned meaning that all edges of the box are parallel to the coordinate axis. During each frame update the bounding boxes are updated by transforming the eight vertices with the transformation matrix of the object. The bounding box is then tested against the frustum to see if it lies on the inside. If the bounding box lies completely outside the frustum then we can be sure that the object lies outside as well. The advantage with a scene graph is that not every object needs to be tested against the frustum. If an object’s bounding box fails the visibility test then we can be sure that any child object will also be outside the viewing volume.
The code for calculating the frustum plane equations and checking whether a bounding box is outside the frustum was obtained from [12]. The culling test is performed by testing a bounding box against six plane equations, each describing a face of the viewing frustum. The test checks whether a corner point of the bounding box lie outside the frustum by substituting the corner point into the plane equations and checking the sign of the result. If all eight points are found to lie outside then the object is trivially culled.
2.8 Other Components of the
System
2.8.1 Lights
Scenes may contain multiple lights. Since the OpenGL API will only allow eight light sources in any one scene (without suffering a performance hit), the system has the same limitation. The system provides two types of lights, positional and spotlights. Positional lights may be specified as point or directional light sources. A point light is a source that radiates light equally in all directions. A directional light has the effect of a point source at infinite distance, when the rays reaching the objects are parallel. An example of a real world directional light would be the Sun’s rays reaching Earth. Colors and intensities of lights may also be adjusted by specifying their ambient, diffuse and specular components.
2.8.2 Material Attributes
All Object nodes possess a container for housing nodes that determine the appearance of an object. Material nodes allow the user to specifies material properties such as the ambient, diffuse, specular and shininess parameters. Color nodes only affect the color of an object and will provide a flat shaded look that disregards lighting parameters. Like all attribute nodes, material and color nodes will affect whole sub levels of a scene graph if no other material or color nodes have been specified in any of the lower levels.
2.8.3 Model Loader
The system was not built as a modeling tool. Although, it does provide some basic modeling transformations as well as a few basic geometric shapes, its purpose is to provide the necessary means to create animations using the scripting language of Director. For this reason, the ability to load models from external files would enable the construction of more realistic looking worlds.
The system is able to load 3D models of the OBJ file format [17]. Currently it is able to read coordinate vertices, face indexes and group information from an OBJ file. The model is stored in a normal object node. The coordinate vertices are stored in a Coordinate node and placed in the attributes section of the object hierarchy. The Coordinate node’s Draw( ) behaviour is similar to other attribute nodes. It replaces the current global coordinate pool from which vertex data is referenced. The face information is stored in a shape node of type IndexGeometry. IndexGeometry nodes only store the referencing indices of the vertices. This way multiple IndexGeometry nodes may share vertex information from one Coordinate node. Groups are stored as separate child objects of the parent object.
2.9 Additional Implementation details
One of the first problems encountered was how to interface OpenGL to Director’s “Stage”, the window in the program that will display the objects. The MOA provided interfaces which enabled a developer to have access to the rendering context [18] of the Stage window. The Xtra that was implemented was an OpenGL window that took up the rendering context of a child window [19] of the Stage window. This was to ensure that the OpenGL window did not take up the entire Stage but only remained as an enclosed sprite.
Figure 2.9
Screenshot of Macromedia Director showing the Stage and Cast Window
The system keeps a pointer to the root of the scene graph. In addition, it keeps an array of pointers to the object nodes in the scene graph, an array of pointers to the light nodes in the scene graph and a pointer to the camera object. Methods that initialize OpenGL and construct the scene graph are found in the system class. The scene is described by the user through Lingo commands that interface with the System class. Although there are many different node types used to construct the tree, users only get to manipulate the Object node through the Lingo script. A typical call to CreateSphere( ) in the Lingo script creates a new Sphere node and a new Object node. The Sphere node is then connected to the shape container node in the Object class. The Object Node is then passed into the AddObject( ) method of the System class. Inside this method the Object node is connected to the scene graph and a pointer to the object is stored in an array. The array index number is passed back to the user as the return value of the call to CreateSphere( ). An array of pointers was used to reference the object nodes in the scene graph because it would have been too slow to search the tree for a particular object node every time an object’s properties needed to be changed.
A function that manipulates an object stored in the scene graph would first require the user to pass the index number of the object. For example, a call to RotateObject( ) would involve the user passing the index number of the object which was to be rotated and the parameters required for the rotation. The appropriate object node would then be accessed in the array and the parameters of the rotations passed into the object node.
When a frame needed to be rendered the root of the scene graph is passed as a parameter into the camera’s Display( ) function. The camera will then transform the scene into viewing coordinates before passing a Draw( ) message to the root of the scene graph. This message propagates downwards the scene graph and every node that receives the message will perform its own node specific task. Since each node’s Draw( ) function is encapsulated within the node itself, the scene graph is highly extensible when new functionalities are required. By varying the properties of the data in the appropriate object nodes each frame and redrawing the scene graph, animations can be created.
Figure 2.10: Creation of a sphere object
CHAPTER 3
ANIMATION
“To animate is, literally, to bring to
life.” (From Computer Graphics:
Principles and Practice, Foley et al, 1990)
3.1
Animation Control Techniques
In order to make an artificial virtual world come to life, users
must be able to interact with objects from that world. These objects will then
perform certain actions based on the user's actions. The animation system has
to be able to cater for the range of motions that an author might require when
animating his actors. The following section will briefly look at a few general
computer animation control techniques.
Animation control mechanisms can range from full-explicit
control methods in which the animator describes the position and attributes of
every object in the scene at every frame, to very high-level descriptions that
automatically generated the animation. Full-explicit control mechanisms usually
involve the animator applying transformations such as translations, rotations
and scaling to objects or by using a system which interpolates a sequence of
frames given a few key frames (key framing). Key framing had its origins in
conventional animation where a lead animator would draw the key points in the
animation. People known as “in-betweeners” would then pencil in the frames
between the key frames.
Constraint or rule-based systems force objects to maintain some
relationship to a parameter while in motion. For example, an object can be
constrained to always orient itself towards another object or an object can be
made such that it never passes through walls.
In procedural controlled models, the motion of objects is
controlled through various elements of the model communicating. Procedure
controlled models form a big part of other animation control methods, which
will be discussed below. For example in physically-based systems, the position
of one object may influence the motion of another while in actor based systems,
actors may influence the behaviour of other actors.
Physically based systems are separated into two classes:
Kinematic and Dynamic systems. Kinematics
refers to motion using known positions and velocities. A typical kinematic
description of an animating object might be, "an object positioned
initially at point(0,0,0) to move at a constant velocity in the
direction(1,2,1) for ." On the other hand, dynamics is concerned about finding the movement given the known
laws of physics. In the example of our object, a dynamic description could
be,"An object has mass of 10 grams and a force of 20 Newton is applied to
it in the direction(1,2,1)." Such descriptions are useful for objects that
have to move realistically within the environment. Both kinematics and dynamics
also have their inverted counterparts. Techniques using inverse
kinematics/dynamics have been used to animate hierarchical models, especially
in the area of realistic character animation [2].
Actor/script-based systems are a high-level form of procedural
control. The animation in these systems is usually controlled by giving
behaviour to objects in the scene . Thus, a car in a scene could be given an
instruction such as “move North at speed”. The behaviour of an actor can be
constrained by certain rules or it could depend on the behaviour of other
actors in its surroundings. The disadvantage with actor based systems is that
it is difficult for the animator to visualize the animation just by looking at
the script. An example of one of the first actor/script based system was ASAS
(as described in [2]). ASAS enabled users to select objects as arguments and
then apply transformations on these objects using one of the provided
transformation routines. Typical transformation commands included up, down,
left, right, zoom-in, zoom-out, forward and backward.
Macromedia's Director is another example of an actor/script
based system. Although Director is capable of keyframing animations, it uses a
powerful object oriented scripting language to manipulate its actors. Since the
project was attempting to extend Macromedia's Director capabilities by
introducing 3D actors, it made sense to introduce scripting commands that were
capable of controlling the motion of 3D actors.
3.2
Revelations from other animation systems
3.2.1 OSCAR(Object-oriented SCene AnimatoR)
OSCAR(as described in [22])
was a three-dimensional computer animation system built in 1984 upon the model of traditional manual
animation process. The goal of the graphics animation system was to provide an
automated system for the efficient creation, control and management of
3D-computer animation. Animation control was achieved through keyframing
techniques and/or animation scripts which referenced a library of complex
actions. Animations consisted of scenes, which consisted of components such as
actors, cameras and lights. The problem statement set out by Oscar provided a
good start for what a typical animation system might consist of:
·
The user
input consists of text files that contain animation scripts. Scripts can
reference a library of complex actions, as well as define new actions.
·
The
script controls any participant in the animation including actors, cameras and
lights. Control is provided through lists of actions that were grouped into
cues. A cue is a series of events.
·
Actors:
Participants in the scene that have position, orientation, appearance and
visibility properties. It is useful to group actors together so the system must
provide a mechanism to allow actors to be collected and controlled enmasse.
·
Since
modeling is a complicated and tedious task, the system must be able to use
models that already exist.
·
All
animation is viewed through the camera. Multiple cameras can exist, but only
one is active in a scene at one time. The user can place the camera in the
environment and control its aim and orientation. Different camera movement
effects like panning, zooming and tracking are required.
·
Multiple
lights can be used to illuminate the animation. Lights have geometry and can be
turned on and off and their intensity can be controlled.
·
A
computerized animation system should have a keyframing capability in which the
system interpolates the animation.
OSCAR's scripting language syntax is similar to Smalltalk with
some extensions. Actors, cameras and lights are declared with their initial
properties. Custom animation sequences are achieved by creating new cues and
incrementally adjusting the coordinates of the actors with each time step. Here
is an example of a declaration of a new ball actor and a cue which bounces the
ball taken from [9].
actor new:ball position=(0,0,0)
color=(1,0,0) model=ball_model;
cue new:bounce
start\_time=0 end\_time=6
start actions="scalar new: x; scalar
new: y;"
tick actions=("x=20/6*[bounce
time?];",
"y=30 * [bounce time?] sin!
*10;",
"ball position= [x ?], [y ?],
0);");
Although this is a fine way of specifying animation scripts (and
easy to implement), complex behaviours might be difficult to implement unless
the animator was provided with a library of ready-made behaviours which met his
needs. Thus, if such a system was adopted then some sort of library consisting
of higher level actions would probably have to be provided.
3.2.2 Alice, an interactive toolkit for novices
Alice[23]
was a tool built for describing the time based and interactive behaviour of 3D
objects developed by the University of Virginia and Carnegie Mellon University.
The goal of Alice was to create a control mechanism that would enable novices
to be able to create 3D interactive graphics without much knowledge of graphics
programming. The authoring environment avoided the traditional mathematical
terminology normally found in 3D graphics such as transformation matrices,
vertices or coordinate axes. Instead it used a control method which was based
on LOGO styled object-centric directions such as left/right, up/down and
forwards/backwards. The research team claimed that by removing the notion of
the XYZ coordinates it “relieved the user of the cognitive mapping step which
might occur thousands of times while developing a 3D program”.
Another important feature in Alice's API was the inclusion of
high-level transformations of objects. Instead of the usual translate, rotate
and scale, Alice's command set would include useful functions such as “place”,
which would be used to put an object next to, on top of or behind some other
object; or “alignwith”, which would make one object point in the same direction
as another object. Objects in the scene were controlled through scripts
composed of such commands that could run in parallel or in sequential order.
Another nice feature that Alice provides is that all commands are animated. For
example when an object is issued a move command, the user can specify a
direction, distance as well as the duration of the animation. Their research
indicated that this was a useful debugging feature because it gives the user a
chance to see the animation unfold over time.
Alice was an interesting system to look at because of its focus
on making the process of creating 3D interactive content easier for novices.
One problem in authoring interesting interactive content appears to be the
difficulty of making objects in a scene move as the animator might have visualized.
Although low level transformations may provide the flexibility required to
construct custom animations, it may not be easy for first timers to use them or
even understand them! The inclusion of "specialized" semi-high level
transformations within Alice looks like a step in the right direction to
creating custom behaviours for actors. By using the more intuitive high level
transformations, users did not need to know much graphics programming to begin
creating animated virtual actors.
3.2.3 Open Inventor: The Engine under the Hood
Open Inventor uses classes of objects known as engines. Engines can be connected to
fields in the scene graph and used to animate sections of the scene. Wernecke
describes an engine as, “a black box that receives input values, performs some
operation on them, and then copies the results into one or more outputs.” To
animate an object, the engine would be connected to transformation nodes within
the scene graph. The engine would generate values that would update the value of
the transformations and the scene would move as the transformations occurred.
For example to rotate a wheel, an engine object would be connected to the scene
graph that describes the rotation. The input to the engine could be a real-time
clock. The engine would generate the appropriate output values, which causes an
incremental rotation of the wheel at each time step. Engines could also be
connected to other engines such that the output of one engine became the input
of the next. This would enable movement of one object to have some sort of
relationship with another object, a method of imposing constraints. In
addition, certain types of engines could be programmed with Boolean rules such
that the outputs from these engines causes the objects connected to them to
move in a constrained manner.
Engines provide a means of representing animations as nodes in
the scene graph. Thus the behaviour of objects would then just be a matter of
attaching the appropriate engine to the appropriate section of the scene graph.
Although this concept was exciting the interface from which users interacted
with the system didn’t lend itself too well with the idea of node placement on
specific positions of the scene graph. It was easier to let users manipulate
objects via methods similar to Alice’s object centric commands.
CHAPTER
4
IMPLEMENTATION
OF THE ANIMATION SYSTEM
In its most basic form, animation is simply the gradual change
in an object’s properties over time. Although most people often associate
animation with motion, it covers all changes that produce a visual effect [2].
The simplest approach would involve incrementally changing the properties of an
object after each frame step. Director
already provided built in functionalities that enable the current frame to advance
to the next frame so an interface for allowing users to change an object’s
properties was worked on.
4.1 A
Basic Strategy
The easiest method was to provide low-level transformation
functions as Lingo commands. These functions were direct manipulations of the
data in the transformation nodes through the Lingo script. Controlling the
animation could then be done by “feeding” in the appropriate transformations
values from external sources. An external Lingo animation engine was created in
order to provide a means of controlling the speed and duration of the
animations. The engine was a modification of a code sample taken from [24].
Users were able to specify the number of frames the animation will take, the
frame per second speed of the animation, the playback direction and the whether
the animation loops at the end. The engine was modified such that it outputs
values between zero and one. If there were thirty frames specified in the
animation then the output will be thirty equally spaced values between zero and
one. This parametric output between zero and one enabled the engine to be used
for different interpolating functions.
Already a linear interpolator in Lingo has been constructed using the
engine as a basis.
While providing global transformations and letting external
script engines control the animation was one solution to the problem, an
earlier implementation of the system revealed that it was still not easy to get
3D actors moving in the right direction. The transformations applied by the external
interpolating engines were still only low-level positional changes in the
objects. Although the coordinate positions could be interpolated by the engine,
rotations still had to be visualized manually first in order to orient objects
in the required directions. Once the objects were oriented in the correct
direction, it was difficult to get objects to move in the desired direction
using only a global translate function. Another reason why this method was
abandoned was because it failed to capture the essence of an actor-script based
system. Commands to objects were only 3D transformations with values that were
modified slightly at each frame step in order to create animation. Another
solution had to be found which was simple and worked well within a text based
scripting environment.
4.2
Objects with Direction
The next approach taken to control the 3D objects was influenced
by the Turtle graphics of the LOGO programming language [20]. Objects are given
a direction and a distance to move in. Direction is an important property in
Turtle Geometry because with direction we can bring knowledge about our bodies
and how we move and apply it to the turtle [21]. For a system like this to work the objects must first possess
some intrinsic forward direction. The forward direction for this system was
chosen as the positive Z axis. There was also a need to keep track of the state
of an object. The scene graph was supposed to be a database that held the
information relating to the objects. However there were no nodes that kept
track of the global state of an object. Transformation nodes only held the data
that transformed an object in its own local coordinates. In a part hierarchy a
child object could be motionless in relation to its parent object while the
parent object is moving. A new node type had to be created to track the dynamic
state of an object in the virtual world.
4.3 The
Transformable Node
The Transformable Node was created as a “higher level” type of
transformation node. It is a derived class of Transformation(See Figure 7) and
serves to keep track of the state of an object while providing methods used to
manipulate objects. Some of the variables it updates include information such
as the forward, up and side vectors of an object, the “position” of an object
(where the local origin exists) and the current bounding volume of an object.
There are also methods which help to move an object relative to its current
orientation in space. For example, the movestep(x ) method will move an object
x units in the direction of its current forward vector while the rotatestep(x)
method will rotate an object x degrees in its local Y axis from its current
orientation. In addition, the Transformable is able to “attach” itself to
another Transformable and react based on that object’s position and direction.
Currently, each Transformable holds a pointer to another Transformable object
when the AttachToObject( ) method is called. During the update of the
Transformable’s state, the object will point its forward direction towards the
position of the second object. As a result the orientation of the first
Transformable object is constrained
by the position of the second Transformable object.
Although Figure 7 shows Object being the only derived class from
Transformable, the original idea was to have the Camera, Object and Light
classes all being derived from Transformable. This was because all three
classes had common properties involving position and orientation and thus were transformable. However, due to the time
constraints placed on the project, the design of the class hierarchy was
incomplete and so implementation was less than satisfactory for the Camera and
Light. The final decision saw the removal of the common abstraction from the
Camera and Light classes and treating them as separate classes instead. Because
of this, Camera still bears many similar methods to Transformable though it no
longer inherits from it.
4.4
Object Control Functions
Objects are given commands in Lingo such as MoveObjectForward(myobject, 1) which indicated that the object
known as “myobject” is to be moved one unit forward. By placing this command in
the enterframe or exitframe handler in a Lingo script an object can be made to
animate by moving it one unit forwards per frame. Almost all the functions used
to manipulate objects are performed from the object’s local coordinates. A
similar command, MoveObjectToward
moves the object forward but keeps the object at the same height. This is
useful for objects that need to pitch up or down but must still remain on the
ground. Rotational commands such as TurnObject
will rotate the object along the y axis changing its heading, PitchObject will roll an object forwards
or backwards while RollObject will
turn an object to its side. There is however, one command that breaks the rule
of moving from the object’s point of view. LiftObject
will move an object up or down in world coordinates. This decision was made
because in the real world there is only one up direction possible and the
function has been deliberately made to reflect that.
In addition, there are also a few commands that are useful for
specifying the orientation of an object. One of the simplest commands
implemented is the PointObjectAt(x,y,z)
command. This command basically instructs an object to align its forward
direction towards the position (x,y,z) in world coordinates. Although the PointObjectAt function might be
simplistic, it is can form the basis of higher level behaviour through
scripting. For example, a gun turret in the scene can be made to track an
object merely by commanding the turret to point at the object’s position at
every frame update. (See ObjectTrackObject
below) Another application for the PointObjectAt
command could be the animation of objects along motion paths. It is usually desirable
to have objects oriented tangent to the motion path [10]. This command could be
used to orient objects along that motion path by setting the object to point at
the next point along the path. SetObjectDirection
is similar to PointObjectAt except that
it takes as input a vector to set the forward direction of an object.
ObjectTrackObject
is a command that demonstrates the AttachToObject method of the
Transformable node. When called, the first object will attempt to point at the
position of the second object specified during each frame update. This will
cause the first object to appear to be “tracking” the second object. To
accommodate for objects that are supposed to be unable to pitch up or down, the
mode of ObjectTrackObject can be
selected such that an object will only change its direction heading and not its
angle of elevation as it tracks the second object. This is useful for
situations where ground based objects might be required to track a flying
object but they cannot tilt upwards. To stop the tracking behaviour, the
command ObjectReleaseObject is
called.
Refer to Appendix B User Documentation for a full list of Lingo
commands available.
CHAPTER
5
Results
and Discussion
The Xtra was implemented in C++ using the Director 7 SDK and
ran in Director 7 under Windows 98. Using
the Xtra implemented, a small interactive demo (available at http://www.csse.monash.edu.au/~mwong/)
was created to highlight some of the capabilities of the Xtra. The demo
consisted of two tanks in a forest consisting of approximately 20 trees
(instanced from an original model of a tree) with a model of a spaceship flying
in the air. It showed the spaceship turning to face its opposite direction
before accelerating forwards and finally disappearing into the sky. The green
tank could be controlled via the keyboard while the red tank was to respond to
the player tank by moving toward the green tank if it was too far and moving
away from it if it got too near. This behaviour exhibited by the red tank was
supposed to show the tracking behaviour that could be implemented using the
command set. View frustum culling was turned on.
5.1
Hierarchical Modelling
Each tank was a part hierarchy consisting of a box for the body,
a smaller box for the turret and a cylinder for the cannon. The turret was set as a child of the tank
while the cannon was set as the child of the turret (See Appendix listing A.2)
The tank’s turret could be rotated independently while moving along with the tank’s
chassis because the scene graph maintains the necessary transformations
required on each level of the hierarchy. Because the cannon was set as a child
of the turret, the cannon remained in same position relative to the turret when
it was rotating. Thus a rotation of the
turret also rotated the cannon.
Figure
5.1: Screenshot of the demo showing two tanks
5.2
Scripting Behaviours
The spaceship’s movement was scripted using the new Lingo
commands introduced into the scripting language. It was broken up into two
sections, a rotational section and then a translation section. The rotational
section was described using the TurnObject
command at each frame step until the angle rotated was 180 degrees. Then the
translation of the spaceship was performed by calling the MoveObjectForward command. Although the Xtra had no built in
mechanism for easing in and out [2], it
was noted that the parameter passed into the MoveObjectForward function was a velocity because we were
specifying how far an object is to move forwards per frame step. A linear interpolator was used to vary the
step size per frame resulting in the object accelerating. The result was a
simple animation that could be described using two of the Xtra’s scripting
commands. The Lingo code for the scripted spaceship may be found in Appendix
listing A.3.
Figure 5.2: Model spaceship from point of view of green tank
Using the object relative commands also made it easy to set up
the controls for the player controlled green tank. Commands such as MoveObjectForward and TurnObject could be mapped directly onto
keys on the keyboard with minimum fuss. The missile that the tank fires out of
its cannon was easily directed parallel to the cannon by setting the forward
direction of the missile as the forward direction of the cannon using the
function SetObjectDirection. Finally
with the tracking feature of the Transformable node, the red tank was able
possess simple deterministic behaviour. The red tank’s movement was scripted
using the ObjectTrackObject command,
which caused it to orient itself towards the green tank. At each frame step,
the following algorithm was used to script the red tank. This made the red tank
follow the green tank if it was too far while backing away from the green tank
if it was too near.
if distance between tanks is greater than
60
Move
red tank forwards
else if distance between tanks is less
than 30
Move
red tank backwards
The equivalent algorithm in Lingo using the Xtra’s scripting
language can be found in Appendix listing A.3
5.3
Culling Tests
The frame rate of the demo was tested against an earlier build
without frustum culling. Frame rate was calculated by counting the number of
times the enterframe handler was called in Director and then dividing that
number by the time passed in seconds. The frustum-culled version generally
appeared to be smoother and the average frame rate attained was around 15
frames per second. The version that did not cull geometry outside the frustum
performed poorer, averaging only about 6.5 frames per second.. The table below
shows the test results from 4 runs of the same scene. While frustum culling
certainly improved the performance of the system, a large number of objects
within the frustum will still cause the frame rate to drop dramatically. This
would result in fluctuations in the frame rate when the camera view changes
from an area with little scenery to an area with dense scenery. Also, as the
number of objects in the scene is increased, frame rate will drop. This is
because the system is testing every object against the frustum and for large
numbers of objects the total processing time taken in testing for visibility
could be significantly large.
|
Test Run |
With Frustum Culling |
Without Frustum Culling |
|
1 |
14.58 fps |
6.57 fps |
|
2 |
14.84 fps |
6.49 fps |
|
3 |
15.87 fps |
6.21 fps |
|
4 |
16.10 fps |
6.49 fps |
|
Average |
15.35 fps |
6.44 fps |
Table 5.1:
Frame rate test results comparing a culled scene with a non-culled scene
Currently the system tests every object to see if they lie
within the viewing volume. It was mentioned before that if an object was tested
and found to be outside the frustum then its child objects will not need to be
tested. Perhaps if the spatial relationships between objects were exploited the
system would have less bounding boxes to test for visibility. For example a
scene could be divided up into groups of objects that lie close to one another.
The frustum cull could test the bounding boxes of these groups and if the test
fails then the objects in that group would not need to be tested for
visibility.
CHAPTER
6
Conclusion
The work done in this thesis was primarily motivated by the need
to incorporate 3D graphics and animation functionality into an existing
multimedia authoring tool. The research had focused on a data structure that
can be used to store 3D data as well as being a user model for representing the
objects in the 3D world. This thesis has also shown that by giving objects
directional properties, we can begin describing the movement of objects in an
intuitive manner and that it works well within a scripted animation control
scheme.
The design of the Xtra had required a scene graph to be built in
order to store the 3D data because the graphics library did not possess a
suitable data storage system.
Programming graphics at the scene graph level was found to be more
intuitive than programming at the immediate mode level because the scene graph
is a natural representation of the way we think about objects in the world.
Since the scene graph fed data to the immediate mode API, it is able to make
more efficient use of the rendering pipeline by automatically culling
non-visible objects through view frustum culling. Finally, the scene graph also
showed how data could be stored more efficiently through multiple referencing
of nodes to create new instances of objects.
With the scene graph being the framework of the system, users
could begin to manipulate 3D data as objects instead of graphics primitives.
This was because users did not need to worry about keeping track of the transformations
required to move the various parts in a hierarchical model. Furthermore it was
found that by giving objects direction as well as position the motion of
objects could be more easily described because it resembled the way we
naturally thought about moving in space.
Although the animation system developed is adequate for
specifying motion, it is not a general animation control program. For example,
the Xtra would not be able to create any animations that involved objects
undergoing shape deformations. Also, because the animation is described through
Lingo scripts, complex animations might require a fair amount of programming
skill from the animator.
6.1
Further work
Currently the Xtra is not very good at modeling scenes since the
user has to deal with a text based script to build the world and use numerical
values to specify positions of objects. Although the Xtra was never intended to
be a modeling program, there will always be some aspect of modeling involved in
the creation of scenes. A GUI interface with picking routines for the Xtra
would have relieved the user from visualizing the placement of objects within
the scene and made manipulation of objects as easy as selecting, dragging and
dropping with the mouse. With picking routines, Director presentations created
with the Xtra would become interactive as users interact with objects in the
world through the click of a mouse button.
Another area that the Xtra could improve upon is its visual
effects. Effects such as texture mapping or shadows can help to make objects
appear more realistic. Because the system can be extended by creating new node
types for the scene graph, new features can probably be added in without
affecting the current framework.
The relationship between the class Transformable, the Object
class, the Camera class and the Light class could be investigated more
thoroughly. Currently the Camera and Light classes exist as separate classes
but there was no reason why that should be the case as cameras and lights
exhibit similar properties such as position and direction.
View frustum culling certainly improved the real time
performance of the system. However for applications such as fast moving games,
the performance of the Xtra was still not adequate. That was because the program was testing every object for
visibility before culling. The system could be improved by having it
automatically group objects which are close together and a test for visibility
would involve testing the bounding boxes of these groups first before testing
the objects inside the group. This would reduce the number of visibility tests
performed after each frame update.
APPENDIX A
SOURCE CODE
This appendix
contains the code listings referred to by the thesis. The source code for the entire Xtra is available online at http://www.csse.monash.edu.au/~mwong
A.1 Node.h
Declaration of class Node.
class Node
{
public:
Node(void)
{
countref=0;
cacheflag=false;
}
virtual ~Node(void){};
virtual void Draw(){};
virtual void Prepare(){};
virtual void Update(){};
virtual void AddChild(Node*){};
virtual void PrependChild(Node*){};
virtual int NumChildren()
{
return 0;
}
virtual Node* GetChild(string label)
{
return NULL;
}
virtual Node* GetChildAtPosition(int position)
{
return NULL;
}
virtual void DeleteChild(string label){};
virtual void DeleteChild(Node*){};
virtual void DeleteAllChildren(){};
virtual void GetVolume(BoundingBox& bb)
{};
virtual void SetCache(int)
{};
virtual void createdisplaylist(){};
virtual void CalculateAABB(){};
void AddRef()
{
countref+=1;
}
void UnRef()
{
if(--countref<=0)
{
delete this;
}
}
void setLabel(string name)
{
this->label=name;
}
string getLabel()
{
return this->label;
}
protected:
bool cacheflag;
GLint dlist;
private:
int countref;
string label;
};
A.2 Lingo
code to construct a hierarchical model of a tank
on
new me
--create a new cube
for the body
tank=member(1).CreateCube(10,4,10)
member(1).ScaleObject(tank, 0.5, 0.5, 0.5)
--create a new cube
for the turret
turret=member(1).CreateCube(5,2,5)
member(1).SetObjectPosition(turret,
0, 3, 0)
--create a new
cylinder for the cannon
cannon=member(1).CreateCylinder(0.5,0.5, 10)
member(1).SetRotateObject(cannon, 0,0,0)
--set the cannon as
a child of the turret
member(1).SetPart(turret, cannon)
--set the turret as
a child of the tank
member(1).SetPart(tank,turret)
--set the tank color to green. This will ensure all children
---parts will also be green
member(1).SetDiffuse(tank, 0,0.5,0,1)
missilefired=0
--create a missile but make it invisible
initially
missile=member(1).CreateSphere(0.25)
member(1).TurnOnObject(missile,0)
return me
end
A.3 Lingo code
that animated the spaceship described in section 5.2
on startmoveforward
--turn on the linear interpolator
engineforward.ancestor.StartAnimation(1)
end
on exitframe
--if animation has started start rotating
if
animating=1 then
--turn the spaceship 3 degrees each frame
member(1).TurnObject(objectid, -3)
angle= angle+3
--if reached 180 degrees stop rotating and
move forwards
if
angle=180 then
rotating=0
animating=0
startmoveforward()
end if
end if
--if we have turned on the linear
interpolator engine
if
engineforward.ancestor.CheckAnimating()=TRUE then
--get the velocity from our linear
interpolator
velocity=engineforward.exitframe()
member(1).MoveObjectForward(objectid, velocity)
end if
end
A.3 Lingo
code that animated red tank described in section 5.2
on startmovie
--make the
enemy tank track the player tank
member(1).ObjectTrackObject(redtank,
greentank,1)
end
on exitframe
--get the distance between the tanks
distance=member(1).DistanceBtwObjects(greentank,
redtank)
--if distance is too
far move red tank forward
if(distance
> 60) then
member(1).MoveObjectForward(redtank,1)
--else if distance is too near then move red
tank back
else if(distance
<30) then
member(1).MoveObjectForward(redtank,-1)
end if
end
APPENDIX B
User Documentation
Disclaimer
The Xtra
produced represents an ongoing piece of software for the purposes of this
thesis. Though it is functional, it is
not a fully completed software. It has
not been tested extensively and in its current state the author cannot
guarantee that it will work.
Platform
The Xtra has
been designed to work with Director 7 under Windows98/NT.
Installation
Under the
Macromedia director, there should be a folder labeled “Xtras”. Create a new
folder inside the “Xtras” folder and place the Xtra inside it. The Xtra
filename is Oval.x32 and it may be downloaded at
http://www.csse.monash.edu.au/~mwong/
Using the Xtra
The Xtra has
been built as an Sprite Xtra and works in “Direct to Stage” Window Mode. To
insert the Xtra into a presentation, click on the Insert menu and scroll down
to the Sprite Examples folder. There should be an option titled “MyXtra”. After the Xtra has been selected it will
appear on the cast member window. To
produce a display from the cast member, click and drag the cast member onto the
Stage window. This will create a new sprite on the Stage window.
The world may
be created through the Lingo script inside the startmovie handler. A light
source must be specified for objects to become visible. The camera will be
initially positioned at position(0,0,0) facing the negative z direction. Simple
animations may be produced by varying the properties of objects within the
enterframe or exitframe handler. Here is an example script which will move a
cube 10 small steps and then rotate it continuously.
global cube
global steps
on startmovie
member(1).SetCameraPosition(0,0,10)
member(1).AddPositionalLight(100,100,100,0)
cube=member(1).CreateCube(1,1,1)
steps=0
end
on enterframe
steps=steps+1
if(steps<10) then
member(1).SideObject(cube,0.2)
else
member(1).TurnObject(cube, 1)
end if
end
on stopmovie
member(1).ClearWorld()
end
Functions of
the Xtra
Below are the
list of functions which the Xtra currently provides. If the Xtra is currently
the in the first cast position, then type member(1).function( ) to call a function.
Object
Creation Functions
CreateCube(float
width, float height, float depth) -- Creates a cube with the specified
dimensions. Returns the cube’s index number.
CreateSphere(float
radius) – Creates a sphere with the specified radius. Returns the sphere’s
index number.
CreatePyramid(float
basewidth, float height) – Creates a pyramid with the specified basewidth and
height. Returns the pyramid’s index number.
CreateCylinder(float
topradius, float bottomradius, float height) – Creates a cylinder with the
specified radii and height. Cylinder will be initially positioned with the base
at z=0 and the top at z=height. Returns the cylinder’s index number.
CreateDisc(float
innerRadius, float outerRadius) –
Creates a disc on the z=0 plane, with a radius of outerRadius and a concentric
circular hole with a radius of innerRadius.
Returns the disc’s index number.
LoadModel(string
filename) – Loads an OBJ model from the current working directory. Returns the
model’s index number.
SetObjectDiffuse(int
objectindex, float R, float G, float B, float A) – Sets an object’s material
diffuse component to the specified RGBA intensity.
SetObjectAmbient(int
objectindex, float R, float G, float B, float A) – Sets an object’s material
ambient component to the specified RGBA intensity.
SetObjectSpecular(int
objectindex, float R, float G float B, float A) – Sets an object’s material
specular component to the specified RGBA intensity.
SetObjectShininess(int
objectindex, float intensity) – Sets the size and brightness of an object’s
specular highlights.
SetPart(int objectindex1,
int objectindex2) – Sets the object specified by objectindex2 to become a child
of the object specified by objectindex1
CloneObject(int
objectindex) – Copies the object specified by objectindex and returns the
clone’s index number.
Object Manipulation
Commands
SetObjectPosition(int
objectindex, float x, float y, float z) – Sets an object local coordinate
origin to the point (x,y,z).
RotateObject(int
objectindex, float axisx, float axisy, float axisz, float rotateAngle) –
Rotates an object around the axis (axisx, axisy, axisz) by an an amount
specified in rotateAngle.
ScaleObject(int
objectindex, float factorx, float factory, float factorz) – Scales an object
dimensions by the specified scalling factors.
SetObjectCenter(int
objectindex, float x, float y, float z) – Shifts the object away from the local coordinate origin by the amount
specified in x, y and z. Shifting the object away from the local coordinate
origin affects the rotation and scaling of an object.
SetTranslateObject(int
objectindex, float x, float y, float z) – Sets the initial position of an
object in its local coordinates.
SetRotateObject(int
objectindex, float anglex, float angley, float anglez) – Sets the initial
orientation of an object.
SetScaleObject(int
objectindex, float factorx, float factory, float factorz) – Sets the initial
scaling factors of an object.
MoveObjectForward(int
objectindex, float stepsize) – Moves an object in the direction it is currently
facing by the amount specified by stepsize. A negative stepsize value will move
an object backwards.
MoveObjectToward(int
objectindex, float stepsize) – Moves an object in the direction it is currently
facing by the amount specified by stepsize. Object’s y coordinates will not
change. A negative stepsize value will move an object backwards.
TurnObject(int
objectindex, float angle) – Rotates an object about the local y axis by an
amount specified in angle. Rotation is relative. A negative value for angle
will rotate it in the opposite direction.
PitchObject(int
objectindex, float angle) – Rotates an objects about the local x axis by an
amount specified in angle. Rotation is relative. A negative value for angle
will rotate it in the opposite direction.
RollObject(int
objectindex, float angle) -- Rotates an objects about the local z axis by an
amount specified in angle. Rotation is relative. A negative value for angle
will rotate it in the opposite direction.
SideObject(int
objectindex, float stepsize) – Shifts an object to the side by the amount
specified by stepsize. A negative stepsize value will shift it in the opposite
direction.
LiftObject(int
objectindex, float stepsize) – Raises an object up the global y axis by the
amount specified in stepsize. A negative stepsixe value will lower an object.
PointObjectAt(int
objectindex, float x, float y, float z) – Makes an object point to position (x,
y, z).
SetObjectDirection
(int objectindex, float x, float y, float z) – Set an object’s forward
direction to the vector [x,y, z].
ObjectTrackObject(int
objectindex1, int objectindex2, int mode) – Sets object1 to orient itself
towards object2. mode=1 The object will
not pitch while tracking . mode=0 The object will pitch while tracking.
ObjectReleaseObject(int
objectindex) – Object specified by objectindex will stop tracking behaviour.
TurnOnObject(int
objectindex, int mode) – Switches an object on or off. Objects that are off are
not visible in the scene. mode=1 is on. mode=0 is off
Object Query
Functions
GetObjectPosition(int
objectindex) – Returns the position of the local coordinate origin of an object
in a list.
GetObjectDirections(int
objectindex) – Returns a list containing the objects’s forward direction, up
direction and side direction. Each of the directions is stored inside a list.
DistanceBtwObjects(int
object1, int object2) – Returns the straight line distance between the local
origins of object1 and object2.
Camera
Functions
MoveCamera(float
stepsize) – Moves the camera forward or backwards by the amount specified in
stepsize.
RotateCamera(float
angle) – Turns the camera to the left and right
PitchCamera(float
angle) – Rotates the camera up or down.
RollCamera(float
angle) – Tilt the camera along the z axis
TrackCamera(float
stepsize) – Shifts the camera to its left or right side
LiftCamera(float
stepsize) – Raises camera up or down.
CameraTrackObject(int
objectindex, int mode) – Causes camera
to track an object
mode=2 Places
camera in relative-track mode. Camera will remain in the same position relative
to the object.
mode=3 Places camera in align-track mode.
Camera will track and align itself with the object it is tracking
mode=4 Places camera in static point at
mode. Camera will remain stationary
will pointing at the object.
CameraReleaseObject(
) – Camera will cease tracking
CameraPointAt(float
x, float y, float z) – Makes the camera point towards the position(x,y,z)
SetCameraMode(int
mode) – mode=0 Camera works using quaternion rotations. mode=1 Camera works
using normal Euler rotations. Note: Under track mode the camera will revert to
Euler mode
ResetCamera(
) – Resets the orientation of the camera to point in the negative z direction.
Light
functions
AddPositionalLight(float
x, float y, float z, float w) – Adds a positional light at the position(x,y,z).
If w=0 then the light is a directional light else it is a point source light.
Returns a light index number.
AddSpotLight(float
x, float y, float z, float dirx, float diry, float dirz) – Adds a spotlight at
the position(x,y,z) with the direction specified by the vector [dirx, diry,
dirz]. Returns a light index number.
MoveLight(int
lightindex, float x, float y, float z) – Sets the position of the specified
lightsource to the position(x,y,z)
TurnOnLight(int
lightindex, int switch) – Turns a light on or off. switch=1 turn light on.
switch=0 turns light off
SetLightDiffuse(int
lightindex, float R, float G, float B, float A) – Specifies the diffuse RGBA
intensities for the specified light source.
SetAmbientDiffuse(int
lightindex, float R, float G, float B, float A) –Specifies the ambient RGBA
intensities for the specified light source.
Miscellaneous
functions
ClearWorld( )
– Clears the contents of the scene graph.
Note: it is
recommended this function be called at the stopmovie handler of the lingo
script because objects will still persist in memory after the movie stops.
SetBackGroundColor(float
R, float B, float B, float A) – Sets the color of the background to the
specified RGBA color.
FrustumCull(int
mode) – Turns frustum culling on and off. mode=1 is on. mode=0 is off.
CheckCollision(int
object1, int object2) – Checks whether the bounding box of object1 has
intersected with the bounding box of object2. If true CheckCollision will
return a 1 else it will return 0.
Known
Bugs/Issues
The following
list is a collection of known bugs or issues with the software that was not
fixed due to time constraints.
1)
The model
loader can only handle a maximum of 10000 vertices and 5000 faces. It was an
early implementation that never got around to being fixed with dynamically
allocated memory.
2)
CloneObject
will create a copy of an object but any changes made to a clone might affect
all other clones and the master copy.
3)
Software is
likely to crash if the wrong types or wrong number of arguments are passed into
the Lingo commands.
4)
CheckCollision
is currently a very early prototype implementation. It may not be accurate at
times especially when the object has oriented such that the bounding box has
changed shape.
5)
It is
recommended that ClearWorld( ) be called at the stopmovie handler of the script
if the scene is being created in the startmovie handler because objects persist
in memory after the movie ends.
6)
The
ObjectTrackObject function contains a bug in it in which after a period of time
the tracking object’s transformation matrix will slip and the object will
orient out of control.
Bibliography
[1] Macromedia Director
http://www.macromedia.com/director
[2] J.D Foley et al. Computer Graphics: Principles and Practice. Addison-Wesley, second
edition, 1990.
[3] M.R Kaplan. The design of the Dore graphics
system. In P.Wisskirchen E.H Blake, editor, Advances in Object Oriented
Graphics I, volume 1, pages 177-197. John Wiley and Sons, Canada, 1991.
[4] P.Wisskirchen. Object Oriented Graphics. Springer Verlag, first edition, 1990
[5] L. Koved and W.L Wooten. Groop: an
object-oriented toolkit for animated 3d graphics. ACM SIGPLAN NOTICES OOPSLA
’93, 28(10):309-325, 1993.
[6] J.Wernecke. The Inventor Mentor. Programming Object-Oriented 3D Graphics with Open
Inventor, Release 2. Addison- Wesley, first edition, 1994.
[7] H.Sowizral. Scene graphs in the new
millennium. IEEE Computer Graphics and Aplications 20(1):56-57, 2000.
[8] M.Shantz, L.Bishop et al, M.Finch. Designing
a PC game engine. IEEE Computer Graphics and Applications, 18(1):46-53, 1998.
[9] E.Gamma
et al. Design patterns : elements of
reusable object-oriented software. Addison- Wesley, 1995
[10] M.O’Rouke. Principles
of Three-Dimensional Computer Animation. W.W. Norton & Company, first
edition 1995
[11] D. Conway. CSC428:
Advanced object oriented techniques in C++.
Course lecture notes, School of Computer Science and Software Engineering,
Monash University, March 2000.
[12] P.Martz . OpenGL FAQ and TroubleShooting Guide, http://www.frii.com/~martz/oglfaq/#indx0010
[13] M.Woo,
J.Neider, T.Davis. OpenGL Programming
Guide. Addison- Wesley, second edition, 1998
[14] A.Watt,
M.Watt. Advanced Animation and Rendering
Techniques. Addison- Wesley, first edition, 1992
[15] M.DeLoura (editor). GameProgramming Gems, Charles River Media, Inc. (Rockland, Massachusetts), 2000
[16] D.Hearn
and M.P Baker. Computer Graphics.
Prentice Hall, second edition, 1994
[17] WaveFront’s
OBJ file format,
http://www.wotsit.org/search.asp?page=2&s=3d
[18]
R.S. Wright, M.Sweet. OpenGL SuperBible,
Waite Group Press, second edition, 2000
[19] C.Petzold.
Programming Windows, Microsoft Press,
fifth edition, 1999
[20] The
Logo Foundation,
http://lcs.www.media.mit.edu/groups/logo-foundation/logo/index.html
[21] S.Papert.
Mindstorms. Children, Computers, and
Powerful Ideas, Basic Books/Harper Collins, second edition, 1993
[22] J.Rumbaugh et al. Object-Oriented Modelling and Design. Prentice-Hall, first edition,
1991.
[23] Conway et al. Alice: lessons learned from building
a 3D system for novices. Submitted to CHI99.
[24] J.R. Nyquist and R.Martin. Director
8 and Lingo bible. Foster City, CA : IDG Books Worldwide, 2000