3D Animation Using SVG and XSLT

Keywords: XSLT, SVG, 3D, animation

Mr Peter Gould
Systems Programmer
Amdocs
London Road
Reading
Berkshire
UK
PeterxGould@GMail.com

Biography

Peter Gould was a Masters Student at Oxford Brookes in Web Technologies and the work presented here was the basis for his MSC Dissertation completed in July 2004. He currently works for Amdocs producing pagination software for the yellow pages.

Prof Bob Hopgood
Professor
Oxford Brookes University
Wheatley Campus
Oxford
UK
bhopgood@brookes.ac.uk

Biography

Bob Hopgood is a visiting Professor at Oxford Brookes University. Prior to that he worked at the Rutherford Appleton Laboratory and W3C. He was active in establishing a Web Profile for the Computer Graphics Metafile. He also established W3C's Offices in Europe, Morocco, Australia and Israel. He has 40 years of experience in computer graphics, especially in standardisation activities and has lectured internationally on emerging web standards. He was Programme Chair for WWW5 in Paris.

Prof David A. Duce
Professor
Oxford Brookes University
Wheatley Campus
Oxford
UK
daduce@brookes.ac.uk

Biography

David Duce is Professor in Computing at Oxford Brookes University. He has been involved in the development of standards for computer graphics for 20 years, starting with the Graphical Kernel System (GKS). Together with Bob Hopgood and Vincent Quint, he submitted a proposal to W3C entitled Web Schematics, which launched the SVG activity. He has participated in the development of SVG 1.0 and represents Oxford Brookes University on the Advisory Committee of W3C. His research interests include web graphics and mulitiservice systems.


Abstract


A system, called PAEPOS (Perspective Animated Episodes Producing Output in SVG), has been developed to support the rendering of solid objects with shading from a light source at infinity. Objects can be assembled from parts made up of basic primitives (cylinders, cones etc), Bezier patches, face sets and user-defined parts. Objects are defined using XML and transformed by XSLT into SVG. The generated SVG is restricted to the Tiny profile to see whether it was feasible to generate 3D animations on devices with modest capabilities.


Table of Contents


1. Wire-Frame PAEPOS
     1.1 Introduction
     1.2 CAMPER
     1.3 Wire-Frame PAEPOS
2. Extending PAEPOS to Render Solid Objects
     2.1 Introduction
     2.2 Input Format
     2.3 Animation Parameters
     2.4 Camera Position
     2.5 Light Source Position
     2.6 Objects and Parts
          2.6.1 Object/Part Animation
     2.7 Part Composition
          2.7.1 Paths
          2.7.2 Double sided Polygons
          2.7.3 Basic Shapes
          2.7.4 Patch Set
          2.7.5 Face Set
          2.7.6 User Defined
3. Generating 3D View
     3.1 3D Pipeline
     3.2 Local Coordinates
     3.3 Local to World Transform
     3.4 Animation Positions
     3.5 Back Face Removal
     3.6 Lighting
     3.7 World to Camera Transform
     3.8 Object Clipping and Face Sorting
     3.9 Perspective Transform
     3.10 Output SVG
4. Implementation
     4.1 Overview
     4.2 Efficiency
     4.3 Peep-hole Optimisation
5. Examples
     5.1 Basic Shapes
     5.2 Walk Through
     5.3 Clipping
     5.4 Chess: Basic Shapes
     5.5 Chess: User Defined Shapes
     5.6 Face Set
     5.7 Patch Set
     5.8 Conclusions
Acknowledgements
Bibliography

1. Wire-Frame PAEPOS

1.1 Introduction

Oxford Brookes runs a Masters programme in Web Technologies which includes the teaching of SVG and XSLT. SVG used in conjunction with XSLT has been the basis for a number of coursework assignments and Masters dissertations. An earlier paper [1], described the first version of PAEPOS, that allowed simple 3D wire-framed animations to be defined in XML and transformed by XSLT into SVG. This was defined as a piece of Coursework that gave students an understanding of both SVG and XSLT.

1.2 CAMPER

The motivation for the wire-framed PAEPOS system was an earlier system called CAMPER. In 1967, Sherwood (Woody) Anderson [2], under the direction of Don Weiner, developed two systems called CALD and CAPER for his Masters Thesis at Syracuse University [3]. These were developed further to become CAMP and CAMPER [4][5]. CAMPER [7] was a 3D extension of CAMP. A deck of cards defined the animation of objects and their viewing as a set of quite simple commands. It was possible for non-programmers to produce quite pleasing line drawn animation using a microfilm recorder as the output device.

1.3 Wire-Frame PAEPOS

Wire-Frame PAEPOS (Perspective Animated Episodes Producing Output in SVG) had similar functionality to CAMPER but expressed it in a form more amenable to XSLT processing. Also, the basic CAMPER drawing primitives were aligned with those of SVG. The result was a 3D extension to SVG that took about 60 hours to develop and was the right size for a piece of Coursework.

The architecture, shown in Figure 1, was based on CAMPER but took into account the strengths and weaknesses of SVG and XSLT. CAMPER defined pictures in terms of stacks and arrays. Transformations could be applied to a complete stack or to an array within a stack. Here the terms object and part replaced stack and array. Arrays in CAMPER were made up of polylines (a sequence of joined line sections) or line sets (a sequence of disjoint lines). In PAEPOS the two types were amalgamated into a single curve element where for each point it was possible to define whether this is a move or a line. Thus it encompassed the two CAMPER primitives but extended their usage in line with the path primitive of SVG.

fig01.svg

Figure 1: Wire-Frame PAEPOS Architecture

fig02.svg

Figure 2: PAEPOS Viewing System

The viewing system, shown in Figure 2 was quite simple with the viewing direction being towards the origin and specified in a spherical coordinate system. Individual objects could have their own viewing system; one object could be animated while retaining a static view of related material. Objects were viewed by a 3D perspective transformation defined by:

Each curve was transformed by the viewing perspective transformation into:

<path d="M . . L . . Z" />

Example 1: PAEPOS Output

CAMPER generated output a frame at a time. For PAEPOS, the mechanisms for animation were retained but the approach was more declarative. As the animation functionality of SVG can be used to define the intermediate frames, the approach in PAEPOS was that it produced the keyframes rather than the individual frames leaving the animation functionality of SVG to do the inbetweening. This reduced the number of frames that needed to be output and allowed larger steps between animated values. Some care needed to be taken that the inbetweened frames were still approximately in the correct perspective.

Both the object and the viewing system could be animated. Each PAEPOS document was aimed at generating a single episode. For complex animations, it was necessary to specify many episodes in much the same way that a film is made up of many scenes.

Figure 3 shows an aeroplane [8], originally defined by Woody Anderson.

fig03.svg

Figure 3: CAMPER Aeroplane

The Wire-Frame PAEPOS system achieved the desired results of being a reasonably demanding system to implement and exercised most of the features of XSLT. The question was whether the initial system could be extended to render solid objects. This was a more demanding piece of work and became the dissertation project of one of the authors (Peter Gould) as part of his MSc.

2. Extending PAEPOS to Render Solid Objects

2.1 Introduction

Apart from adding the lighting model, a similar architecture to Wire-Frame PAEPOS was considered initially for the new system (key frames generated and using SVG to inbetween the attributes). This would not have been difficult to implement for static views as sufficient Z information is available to sort the elements into the correct order. However to animate an object, the rendering order would need to change for some transformations in mid sequence or mid inbetween which would be quite demanding for XSLT to sort out. It would clearly be easier to use frame-based animation. This would require more processing in that there would be no inbetween frames provided by SVG. On the other hand, it ensured that there are no ambiguous frames. The brain does the inbetweening much better than SVG can.

Making the animation frame based enabled the problems of Z-order to be solved relatively easily. The position of each polygon can be calculated and sorted and then output for each frame, using SVG's ability to switch the display attribute so that one entire frame was visible at a time. The only potential draw back to this method is performance, the SVG viewer may not be able to deliver the required frame rates. Some crude concept hand coded SVG files were created to assess the initial feasibility of frame switching and it was demonstrated that a rate of 15 frames per second was feasible at least for simple objects.

2.2 Input Format

The input document must provide all the data necessary to create and animate all the defined geometry throughout the animation duration. The document root element was defined as <svg3D> and its children defined:

2.3 Animation Parameters

The animation parameters are:

<duration>100</duration>
<fps>15</fps>
<repeat>yes</repeat>
<freezeframe>
  <pause>
    <start>60</start>
    <stop>75</stop>
  </pause>
  <pause>
    <start>90</start>
    <stop>105</stop>
  </pause>
</freezeframe>

Example 2: Animation Parameters

The duration of the animation is defined in seconds, The frame rate (fps) dictates the number of frames displayed per second of animation.

Some animations may be required to repeat on a cyclical basis, to enable this feature the <repeat> element is defined with permissible values being 'yes' or 'no'. A value of 'no' will cause the animation to end after the specified duration, and hold the last frame visible.

When no animation occurs during a sequence of frames, it would be inefficient to flip frames that are essentially static. To prevent frames needlessly switching, the <freezeframe> element defines temporary suspensions of the animation.

2.4 Camera Position

The camera position determines the position of the camera within 3D space. It is composed of an XYZ coordinate, and three angles, roll, pitch and yaw. This replaced the earlier viewing system shown in Figure 2. This does not force the camera to be directed at the origin as the old system did.

<camera>
  <initial>
    <x>-360</x> <y>0</y> <z>60</z>
    <roll>0</roll> <pitch>0</pitch> <yaw>90</yaw>
  </initial>
  <animated>
    <start>15</start>
    <stop>30</stop>
    <x>-180</x> <y>80</y> <z>60</z>
    <roll>0</roll> <pitch>30</pitch> <yaw>90</yaw>
  </animated>
</camera>

Example 3: Camera Position

The roll, pitch and yaw determine the orientation of the camera. The <initial> element determines the starting point for the camera, if it is to be animated, an <animated> element must be included. This element indicates the final animated position and provides starting and ending frame numbers for the movement, via the elements <start> and <stop>. This methodology of using the <animated> and <initial> elements was adopted for any object or part that requires animating.

2.5 Light Source Position

The lighting model defines shading from an infinite light source. The position of the source is defined by an XYZ position that establishes the vector to infinity.

<lightsource>
  <x>500</x> <y>500</y> <z>0</z>
</lightsource>	

Example 4: Light Source

2.6 Objects and Parts

The part set was extended so that objects are composed of parts where a part can be made up of any of the following:

The parts of an object may be animated, and the set of parts of an object may also be animated. An object is defined by the XML element <object>. It must contain at least one child element of type <part>.

2.6.1 Object/Part Animation

There are three operations that can be performed on any object or object part:

<translate>
  <initial><x>0</x> <y>0</y> <z>0</z></initial>
</translate>	
<scale>
  <initial><x>1</x><y>1</y><z>1</z></initial>
<rotatexy>
  <initial>
    <local> <angle>0</angle> </local>
    <world> <angle>0</angle> <x>0</x> <y>0</y> </world>
  </initial>
  <animated>
    <start>1</start>
    <stop>75</stop>
    <local> <angle>355</angle> </local>
    <world> <angle>355</angle> <x>10</x> <y>10</y> </world>
  </animated>
</rotatexy>

Example 5: Translation, Scaling and Rotation

The translation operation is used to move a part from one position in 3D space to another.

The scaling transformation is defined using all the same child elements as the translate operation. The result of scaling is to multiple the XYZ component of the part by the specified value within the scaling child elements.

Rotation is the most complex operation that can be performed on an object or object part. There are three planes of rotation, X-Z, Y-Z and X-Y. X-Z causes a part to rotate about the Y axis, Y-Z rotates about the X axis and X-Y rotates about the Z axis, as shown in Figure 4.

fig04.svg

Figure 4: XYZ Planes

To further complicate rotation the coordinate position that the point rotates about must be specified. Two types of rotation have been defined within the system, local and world. Local rotation will cause the part/object to rotate about its locally defined origin, world rotation will cause the object/part to rotate about a point defined in world space.

Figure 5 shows the use of the two rotation types within the same animation. In Figure 11, rotating the individual spheres would be done using a local transformation while rotating the three spheres about the centre would be achieved by animating the world coordinates.

fig05.svg

Figure 5: Local/World Rotation

The cube within the figure is rotating about it's local X axis, the origin of the cube is defined at its centre. In addition to the local rotation, the cube is also performing a world rotation about a point specified on the XZ plane.

Animation can be defined by including an <animated> child element within the definition of the <translate>, <scale>, or rotate element, with a start/stop declaration and the destination coordinate set.

2.7 Part Composition

2.7.1 Paths

The basic component of a part is the <path> element. This specifies the vertices that make up the polygon that the path represents. The number of vertices that the path may contain is unlimited, it must however create a polygon that is co-planar, if this is not the case, errors will occur with back-face culling and lighting.

<part colour="rgb(0,255,0)">
  <path>M10,10,10,L-10,10,10,L-10,10,-10,L10,10,-10,</path>
</part>

Example 6: Part Definition

The 'M' denotes the first point in the polygon, and the comma-separated values that follow are XYZ coordinates. The character 'L' prefixes all other vertices within the polygon definition. Multiple paths may be defined within the same part. A colour value can be specified within the part element, defining the base colour of items declared within the part. This takes precedence over parent colour definitions. The colour specified must be in RGB format.

2.7.2 Double sided Polygons

Polygons created by the system will normally be single sided. Any polygon that is not visible to the cameras viewpoint will not be rendered. This reduces the output file size and improves final viewing efficiency. The system needs to calculate the face positions relative to the viewpoint. All polygon definitions are defined counter clockwise, Figure 6, to establish the direction of the front face.

fig06.svg

Figure 6: Polygon Definition

There may be instances when it is undesirable to have a polygon only viewable from one side. To override this rule an element is provided that defines a polygon to be rendered with faces on both sides.

<doublesided/>

Example 7: Double Sided

The above element can be a child of any part element or primitive declaration.

2.7.3 Basic Shapes

The system defines a set of basic parts that can be extended. Each basic part has an XSLT transformation that generates the appropriate set of paths given the parameters specified for that basic part. It is quite easy to extend that set of transformations.

<part>
  <sphere id="sphere" use="sphere">
    <radius>7</radius>
    <definition>3</definition>
  </sphere>
</part>
<part>
  <cylinder id="cylinder" use="cylinder">
    <height>20</height>
    <radius>6</radius>
  </cylinder>
</part>
<part>
  <cone id="cone" use="cone">
    <height>20</height>
    <radius>7.5</radius>
  </cone>
</part>
<part>
  <box  id="box" use="box">
    <width>10</width>
    <height>30</height>
    <depth>10</depth>
  </box>
</part>
<part>
  <pyramid id=" pyramid" use="pyramid">
    <width>12</width>
    <depth>12</depth>
    <height>30</height>
  </pyramid>
</part>

Example 8: Basic Parts

Each part is created as a set of path elements based on the parameters provided for the basic part type. The sphere requires the radius to be specified and a value ranging from 1 to 3 which defines the number of polygons used to construct the sphere.

The cylinder is open ended and defined by specifying the radius of the base and the height. Polygons constructing the cylinder are double sided by default.

The cone is open ended and also defined by specifying the radius of the base and the height.

The box element defines 3-dimensional cube by specifying the height, width and depth of the shape.

A pyramid element is also specified by its height, width and depth.

Each part is added to the output document if it has a 'use' attribute that references a defined primitive with an 'id' attribute equivalent to the 'use' attributes value. In the examples so far this is self-referential so, for example, a sphere with id set to 'sphere1' will be defined. This technique provides the ability to define one primitive and then create multiple instances of it and helps to improve the efficiency of the XSLT transformation process. The extract below creates a second instance of the previously defined sphere.

<part>
  <sphere use="sphere"/>
</part>

Example 9: Use

A circle is also provided as a primitive, this is the only non 3-dimensional shape that the system will define as a primitive. This is due to the complexities involved in generating circular based shapes. Other 2-dimensional shapes are mainly composed of straight lines that can be easily plotted manually.

2.7.4 Patch Set

The patches within each set are composed of 16 vertices. As patches will often share a particular vertex, the vertices are stored within a separate list. The patch then references a vertex within the list. This yields a single vertex definition that has multiple instances used. The <refine> element specifies the levels of sub-division required. The value '1' will result in the display of the defined data only.

As can be seen in Figure 7, each patch defines four Bezier cubic splines in one direction {(a,b,c,d), (e,f,g,h) (i,j,k,l), (m,n,o,p)} and four in the other {(a,e,i,m), (b,f,j,n), (c,g,k,o), (d,h,l,p)}. Only four of these are points on the surface (a,d,p,m) and the rest are control points not on the surface.

fig07.svg

Figure 7: Bezier bicubic patch

<part colour="rgb(255,0,0)">
  <patchset id="pot" use="pot">
    <refine>1</refine>
    <!--spout-->
    <patch>165,164,163,162,169,168,167,166,173,172,171,170,177,176,175,174,</patch>
    <patch>162,179,178,165,166,181,180,169,170,183,182,173,174,185,184,177,</patch>
    <patch>177,176,175,174,189,188,187,186,193,192,191,190,197,196,195,194,</patch>
    <patch>174,185,184,177,186,199,198,189,190,201,200,193,194,203,202,197,</patch>
    <vertices>
      <vertex>1.4,0.0,2.4</vertex>
      <vertex>1.4,-0.784,2.4</vertex>
       ...
    </vertices>
  </patchset>
</part>

Example 10: Patch Set

fig08.svg

Figure 8: Newell's Teapot with 4, 8 and 16 lines per patch

The easiest way to improve the presentation is to split each patch into four. This is fairly straightforward ([6] and requires the midpoint to be found for each of the four Bezier curves in one direction. At the same time, the new control points for the left and right hand parts of the curve are obtained. This gives seven points for each Bezier curve (the centrepoint is shared by both the left and right parts of the curve). The same bisection is applied to these 7 curves in the other direction also resulting in 7 points for each of these making 49 points in all. These are the unique points in the 64 needed to represent the four patches (the seven points across the middle in each direction are used twice with the centre point used all four times).

This can be set up a recursive loop in XSLT. Figure 8 also shows the results for two levels of refinement.

Although it was Newell's teapot that captured the imagination and became part of computer folklore, he did also hand generate definitions of a teacup and teaspoon in the same format. These are shown in Figure 9.

fig09.svg

Figure 9: Newell's Teacup and Teaspoon

2.7.5 Face Set

A face set provides the same flexibility as the patch set with regard to compact file size. It adopts the same principles of defining faces in a separate list to the vertices that they are composed of.

<faceset id="face" use="face">
  <vertices>
    <vertex>-90,-5,160</vertex>
    <vertex>-90,-5,-20</vertex>
    <vertex>90,-5,-20</vertex>
    <vertex>90,-5,160</vertex>
    <vertex>-85,0,155</vertex>
    <vertex>-85,0,-15</vertex>
    <vertex>85,0,-15</vertex>
    <vertex>85,0,155</vertex>
    <vertex>-90,-20,160</vertex>
    <vertex>-90,-20,-20</vertex>
    <vertex>90,-20,-20</vertex>
    <vertex>90,-20,160</vertex>
  </vertices>
  <face>7,5,6,</face>
  <face>8,5,7,</face>
  ...
</faceset>

Example 11: Face Set

A big advantage to using the <faceset> element is that objects defined with other graphics packages export data using the same or similar formats.

2.7.6 User Defined

A user defined primitive is used when a complex object needs creating and duplicating within the animation.

<part colour="rgb(0,0,0)">
  <userdefined id="ComplexObject" use="ComplexObject ">
    <path colour="rgb(0,0,0)">M-80,0,-10,L-60,0,-10,L-60,0,10,L-80,0,10,</path>
    <path colour="rgb(255,255,255)">M-60,0,-10,L-40,0,-10,L-40,0,10,L-60,0,10,</path>
    <path colour="rgb(0,0,0)">M-40,0,-10,L-20,0,-10,L-20,0,10,L-40,0,10, ,</path>
    <path colour="rgb(255,255,255)">M-20,0,-10,L0,0,-10,L0,0,10,L-20,0,10, path>
  </userdefined>
</part>
<part>
  <userdefined use=" ComplexObject "/>
</part>

Example 12: User Defined

The <userdefined> element may contain any of the previously defined primitives. This method reduces the complexity of the input document, aids maintenance and yields a smaller XML animation definition file.

3. Generating 3D View

3.1 3D Pipeline

The philosophy for converting the input XML file into an SVG output file is to create a 3D pipeline, the initial coordinate data is inserted at one end, and the end results output at the other, this is shown graphically in Figure 10. A summary of the operations that will be performed on each of the vertices/polygons throughout the pipeline is given below. The development process is to be incremental, testing is to be performed at each stage, where possible. The process blocks in cyan in Figure 10 are a minimum requirement in order to produce a system that provides an output.

fig10.svg

Figure 10: 3D Pipeline

3.2 Local Coordinates

The user will generate all the local coordinate data within the input file for all objects that are non-system primitives. The system primitive data will be generated by the system and held within a global variable. This action will take place before the root template is processed, it will ensure that system primitive data need only be generated once. For example, if this was not the case, each new frame that is created would have no knowledge about local data for system primitives and would have to re-calculate it from the data held about the primitive within the input file, an inefficient time consuming process.

3.3 Local to World Transform

The Local to World transformation process involves transforming all polygon vertices to the correct location, as specified within the input file for the current frame being processed. This will involve all the rotation, scaling and translation transformations. All calculations involving transforming vertices will be performed using matrix algebra.

3.4 Animation Positions

The only information permanently held within the system is the local coordinate data, the system has no stored knowledge of the position of an object in the previous frame. When an object is being animated the system must calculate the point it is currently located at by iterating through all the previous animation data.

3.5 Back Face Removal

Back face removal is the process of eliminating faces from the pipeline that are not visible from the camera viewpoint. This process will not only aid in more efficient processing of the style sheet, it will also reduce the size of the final output SVG file. A face is visible if the angle between the camera viewpoint and the face normal is between 0 and 90 degrees.

The face normal is a vector that is perpendicular to two of the vectors which comprises the face. It is calculated by the formula:

n = <uy x vz - vy x uz , - ux x vz - vx x uz , ux x vy - vx x uy>

where n is the normal, u and v are face vectors. Once the face normal has been calculated, the angle between the normal and camera viewpoint vector must be calculated. This is achieved using the following formula:

theta = cos-1 ((ux x vx + uy x vy + uz x vz) / |u| x |v|)

where u and v are the vectors (camera and face normal) and |u|, |v| indicates the vector lengths.

3.6 Lighting

As this simple 3D ouput may be useful on small devices, lighting was defined using the SVG Mobile profile rather than using the lighting available with the SVG filter effects.

Lighting is to be generated by calculating the cosine of the angle between the face and the light source vectors and calculating new colour values for each polygon. Colour values will be capped at maximum and minimum values, this will ensure that a colour will not be set to white or black when at extreme angles to the light source. The range that a colour may be changed within, will be the differential between the desired value and the max/min capping values. When adding light to a colour the value will be calculated using the formula:

OutputRGB = InputRGB + (Range x Cosine of Angle)

where Range = MaxCap Value - InputRGB

When subtracting light from a colour the value will be calculated using the formula:

OutputRGB = MinLevel + (Range x (1 + Cosine of Angle))

where Range = InputRGB - MinCap Value

When subtracting light, the angle between the face normal to the light source will be greater than 90 degrees, so will generate a negative cosine value. The above formulae will be applied to each individual component that makes up the RGB value.

3.7 World to Camera Transform

The world to camera transformation aligns the camera at the origin (0,0,0) with all its angles set to 0, and the camera pointing in the direction of the positive z-axis. All the objects within the 3D space must then be moved to maintain the same relationship with the camera coordinates. By setting the camera to the origin, it becomes easy to calculate which objects are outside of the camera's field of view and it simplifies the calculations involved in the rendering of the 3D objects onto the 2D screen.

To achieve this, every point within the animation must be multiplied by the inverse camera matrix. The first process is to perform a translation of all the objects by the inverse of the camera position. Once complete, a rotation is performed that aligns the camera with the z axis. Every point within the animation will be altered. The camera inverse matrix must be computed by multiplying the inverse of the three orientation matrices (roll, pitch and yaw) together with the inverse location matrix.

3.8 Object Clipping and Face Sorting

There is no value in processing objects that will not be rendered because they are outside the viewable area. More importantly, objects must be clipped or removed that are behind the camera viewpoint. If this is not the case then they will be inverted and rendered in front of the viewpoint. An object can easily be tested to verify it is completely inside or completely outside the clipping planes, this is achieved by testing the relevant component of the coordinate against the value of the clipping plane.

If an object is completely outside a clipping plane then no further processing need be performed on it and it can be removed from the pipeline. If an object crosses the clipping plane, then new points will need to be calculated to preserve the objects structure.

A depth-sort is applied to the faces to define the rendering order for a specific view [11]. By grouping all the faces that make up an object it is possible to speed up what can be a time consuming process.

3.9 Perspective Transform

The perspective transformation converts the 3D coordinate data into 2D so it can be rendered on a 2 dimensional screen.

3.10 Output SVG

The coordinates generated from the perspective transformation is directly input into the 'd' attribute of an SVG path element.

Each generated frame of animation is grouped within a 'g' element with the id of the frame number.

Frame switching is accomplished by creating a timer that runs for the length of the animation. If repeated animation is required within the input document, the timer will restart when it completes its cycle.

<animate id="t1" begin="0s; t1.end;" dur="100"/>

Example 13: Restart via Main Timer

4. Implementation

4.1 Overview

The XSLT transformation follows the pipeline in Figure 10 and is about 4000 lines of XSLT. The main steps are:

4.2 Efficiency

A major problem in doing such a transformation efficiently in XSLT is the quality of the XSLT code. Unnecessary levels of recursion, time-consuming functions for intrinsic functions like cosine and square root can greatly increase the time taken for demanding transformations. Most of the compilations were done using Saxon.

Quite a bit of time has been taken improving the efficiency of the basic algorithm checking different approaches against each other. Style Studio's XSLT Profiler proved useful in analysing where time was spent and resulted in significant performance gains for some of the intrinsic functions required.

4.3 Peep-hole Optimisation

By generating code a frame at a time, no optimisation between frames occurs. For example, if the same objects appear in the same position on several frames and their Z-order position remains unchanged, it would be feasible to only redraw the changed parts of the display at the next frame.

To implement this as part of the basic rendering algorithm would complicate the algoritm significantly. A better approach is to use a technique used in compilers called peep-hole optimisation. A pass is made over the generated SVG code looking for the same drawing sequence on two neighbouring frames and making changes accordingly.

A library of functions has been developed in XSLT to manipulate SVG path elements. Using these to do peep-hole optimisation on the output from PAEPOS has improved the drawing speed significantly on the more complex examples, such as the animated basic shapes chessboard described later.

5. Examples

5.1 Basic Shapes

Animations of the basic shapes all render smoothly even with a number of shapes per animation. File sizes can get quite large (2 Mbytes unzipped, 256 kbytes zipped) even for a few seconds of animation.

fig11.svg

Figure 11: Basic Shapes

5.2 Walk Through

This was a typical city walk-through with 30 buildings rendered. It was mainly used to check the clipping facilities. At the end of the walk-through, the camera goes through a wall to reveal the interior. File size is 9 Mbytes unzipped. Animation is reasonably smooth on a modern PC although frames are lost on one with less power.

fig12.svg

Figure 12: Walk Through

5.3 Clipping

Clipping is performed in X, Y and Z directions. This animation tests all directions.

fig13.svg

Figure 13: Clipping

5.4 Chess: Basic Shapes

This is an animation of the Immortal Game [9] previously animated in 2D by Max Froumentin [10].

This was a demanding test to run at 15 frames per second. The pieces are animated to move from their starting position to their new position on each move. It required peephole optimisation of the PAEPOS output to allow it to render smoothly on a modern PC. The output size was initially 30 MBytes and the peephole optimisation reduced it to 22 Mbytes (unzipped).

fig14.svg

Figure 14: Chess: Basic Shapes

5.5 Chess: User Defined Shapes

This is the most demanding test so far. The semi-traditional pieces were created using 3ds Max 4's [12] line tool to create the piece outline and a lathe tool to produce the 3D face set. This turned out to be the limit of what could be rendered at 15 frames per second. In consequence, the animation justs moves the piece directly from its start position to the end position with no inbetween frames. The board and pieces consisted of 4500 polygons.

fig15.svg

Figure 15: Chess: User Defined Shapes

5.6 Face Set

fig16.svg

Figure 16: Face Set

5.7 Patch Set

fig17.svg

Figure 17: Patch Set

5.8 Conclusions

Some of the main conclusions coming out of the implementation are:

Acknowledgements

Many of the ideas in this paper have had input from Ivan Herman at CWI/W3C and our students which we gratefully acknowledge.

Bibliography

[1]
Using XSLT and SVG in Teaching: 3D, Sound and Nostalgia Bob Hopgood, David Duce, Paul Hopgood, SVG Open, 2003.
[2]
CALD and CAPER Instruction Manuals S.E. Anderson, Electrical Engineering Laboratory Technical Report No TR-67-6, May 1967.
[3]
A Graphical Programming Language for Computer Generation of Incremental Plots and Animated Motion Pictures S.E. Anderson, Masters Thesis, Syracuse University, 1968.
[4]
A Computer Animated Movie Language for Educational Motion Pictures D.D. Weiner, S.E. Anderson, FJCC Proceedings, Vol 33, 1968 pp 1317-1320.
[5]
Generating Computer Animated Movies from a Graphical Console S.E. Anderson, CG70 Proceedings, Brunel University, 1970.
[6]
Computer Graphics, Principles and Practice J.D. Foley, A van Dam, S.K. Feiner, J.F. Hughes, Second Edition, Addison-Wesley, 1990, Pg 508,
[7]
CAMPER on the ICL 1906A and DEC PDP15 A H Francis, F R A Hopgood, D Ralphs, February 1973, http://www.chilton-computing.org.uk/acl/literature/manuals/camper/overview.htm.
[8]
Tomorrows World, BBC 1971 http://www.chilton-computing.org.uk/acl/applications/animation/p007.htm.
[9]
The Immortal Game B. Wall, http://www.geocities.com/siliconvalley/lab/7378/immortal.htm
[10]
Displaying Chess Games in Web Pages using ChessGML and SVG M. Froumentin, http://people.w3.org/maxf/ChessGML/.
[11]
Adding Another Dimension to Scalable Vector Graphics P.A. Mansfield,http://www.idealliance.org/papers/dx_xml03/papers/03-02-04/03-02-04.html, XML Conference 2003.
[12]
3ds Max 4 - In Depth J. McFarland, R. Polevoi, Coriolis 2001.

XHTML rendition made possible by SchemaSoft's Document Interpreter™ technology.