Common graphical object models and how to translate them to SVG

Dr. Philip A. Mansfield
President
Schema Software Inc.
Vancouver
British Columbia
Canada
philipm@schemasoft.com
http://www.schemasoft.com

Keywords: Graphics, SVG, object model, file format, conversion, translation, filter, viewer, XML

Abstract

SVG was designed as a general-purpose vector graphics language primarily for Web delivery. Its utility in specific application domains is partly dependent on the degree to which popular domain-specific formats can be mapped to SVG. Examples of domains and formats of interest are shown in the table below.

Domain Representative Format
Frame-based animation Macromedia Flash SWF
Presentations Microsoft PowerPoint
Professional graphics Adobe Illustrator
Schematics Microsoft Visio
Computer-aided design Autodesk AutoCAD
Geographic information systems OGC Geographic Markup Language
Charts Microsoft Charts
Formulas W3C Mathematical Markup Language

An object model can be ascribed to each domain-specific format, whether or not that format has an official DOM specification. The problem of mapping to SVG can then be represented as a set of object model transformations.

This paper reports on a large collection of completed software development projects involving translation of graphical formats to SVG. In particular, we present methodology, tools, examples, and lessons learned from the work.

Methodology

We will briefly demonstrate how to

  1. Classify formats into application domains
  2. Determine object model information for representative formats
  3. Map representative object structures from domain-specific formats to SVG
  4. Implement software to perform these mappings
  5. Automate the implementation of mapping software with SVG as its target

Tools

An XML infrastructure has been developed to systemize the storage and analysis of object model information and mapping information. This infrastructure includes a DTD for encoding graphical file format features and mappings, as well as various XSLT files that present selected information as SVG or HTML. A RAD tool has also been developed to automate the process of creating translation software from XML formats to SVG. The ultimate goal is to complete the picture with a tool that automates the creation of binary format parsers that "dump" their results as XML, thereby speeding up development at every stage of the graphical format translation problem.

Examples

We present some of the more interesting object model transformation problems solved along the way, such as how to use parameter-based animation (SMIL) to efficiently replicate frame sequences and sprites.

Lessons Learned

Just as there are design patterns appropriate for the study of object models, there are mapping patterns appropriate for the study of mappings between object models. It is important that the tools to facilitate graphical format conversion be tuned to the mapping patterns commonly needed. We will report on the process of creating graphical conversion tools, the need for a flexible design, and the adaptations that were necessary as we went along.


Table of Contents

1. The Case for Conversion to SVG
     1.1 The Emergence of XML File Formats
     1.2 How to Encode Graphics
         1.2.1 Picture Structure
         1.2.2 Plug or Play?
         1.2.3 SVG to the Rescue!
2. Domain-Specific Semantics
     2.1 Domain: Frame-Based Animation
         2.1.1 Feature: Nondeterministic Frame Sequences
              2.1.1.1 Issues
              2.1.1.2 Options
     2.2 Domain: Presentations
         2.2.1 Feature: Slide Navigation
              2.2.1.1 Issues
              2.2.1.2 Options
     2.3 Domain: Professional Graphics
         2.3.1 Feature: Proprietary Filter Effects
              2.3.1.1 Issues
              2.3.1.2 Options
     2.4 Domain: Schematics
         2.4.1 Feature: Constrained Geometry
              2.4.1.1 Issues
              2.4.1.2 Options
     2.5 Domain: Computer-Aided Design
         2.5.1 Feature: 3D Modelling
              2.5.1.1 Issues
              2.5.1.2 Options
     2.6 Domain: Geographic Information Systems
         2.6.1 Feature: Application-Specific Schemas and Styling
              2.6.1.1 Issues
              2.6.1.2 Options
     2.7 Domain: Charts
         2.7.1 Feature: Data Extent Determines Scale
              2.7.1.1 Issues
              2.7.1.2 Options
     2.8 Domain: Formulas
         2.8.1 Feature: Hierarchical Container Layout
              2.8.1.1 Issues
              2.8.1.2 Options
3. Mapping Patterns
     3.1 Pattern Example: Subdivided Area
         3.1.1 Object Model
         3.1.2 Sample Input
         3.1.3 Mapping
         3.1.4 Results
     3.2 Generalizing the Mapping Pattern
         3.2.1 Elimination of Source Format Dependency
         3.2.2 Method of Generalization
     3.3 Parameterized Polygons
         3.3.1 Input Object Tree
         3.3.2 Mapping Specificaton
4. A Schema for File Formats
     4.1 Re-use and Styling
     4.2 Methodology
     4.3 Document Type Definition
     4.4 Description of Elements
     4.5 Interpretation Guidelines
         4.5.1 Support
         4.5.2 Exportability
         4.5.3 Property Values
5. Automating File Format Documentation
6. Automating Translator Code Development
     6.1 Code Re-use
     6.2 Improving on Filter Frameworks
     6.3 Technology Choices
         6.3.1 Parameterization Format
         6.3.2 Programming Languages
     6.4 Re-using the File Format Schema
         6.4.1 XML Schema for Object Models
         6.4.2 Code Generators for Mapping Patterns
7. Conclusion
Bibliography


1. The Case for Conversion to SVG

1.1 The Emergence of XML File Formats

During the pre-Web era of PC software, there evolved a plethora of proprietary binary file formats. These formats had a survival advantage, since application vendors could keep customers by generating formats that only their software could parse.

However, each generation of software brought with it new versions of the formats, and users soon discovered that their older files were becoming inaccessible and that few of their files could necessarily be shared with others. This new-found user awareness brought with it a new evolutionary pressure toward universal file formats and open standards.

Coincident with this, the Web formed and grew to be a widely accessible file exchange medium. In this new environment, the rules for survival had changed: The fittest file species is one that is accessible to the largest audience. This implies a distinct advantage for open, standardized text formats such as the XML formats produced by the W3C.

1.2 How to Encode Graphics

1.2.1 Picture Structure

Since XML's roots are in text markup, the first XML formats treated images as non-XML external entities. HTML did this as well, for the same reason. Pretty soon vendors of vector graphic applications began to realize that the graphics themselves could benefit from XML encoding. Recently a number of these vendors have been coming out with XML file format variants of their native binary application formats. Here are some examples:

Table 1: Specialized XML formats for vector graphic applications
Application XML Format Reference
Autodesk AutoCAD DesignXML + AcDbXML http://www.designxml.org
Microsoft PowerPoint VML + other Office XML Formats http://msdn.microsoft.com/workshop/author/vml/shape/introduction.asp
Microsoft Visio VDX http://msdn.microsoft.com/library/en-us/devref/XMLR_XMLBasics_817.asp

A number of other graphical file formats have been modified so that XML metadata can be appended to individual graphic objects or to the file as a whole, and the XML can be extracted in a Web publishing context. These include:

Table 2: Vector graphic applications with XML tagging capability
Application XML Tagging Technology Reference
Adobe PDF, Illustrator, InDesign, etc. XMP (Extensible Metadata Platform) http://www.adobe.com/products/xmp/
Macromedia Flash XML ActionScript object http://www.macromedia.com/support/flash/action_scripts/
QuarkXPress avenue.quark http://www.quark.com/products/avenue/

However, to allow end-users to take advantage of specialized vector graphic XML file formats, it is necessary to provide a plug-in or applet that extends the functionality of the Browser. Browser-native functionality tends to be reserved for general-purpose formats, not specialized formats. An example is MathML, which as of this writing is not directly supported by Internet Explorer or Netscape despite being a W3C Recommendation since April 7, 1998 [MathML1] .

1.2.2 Plug or Play?

The problem with requiring users to download specialized software to view a graphic is that many are not willing to go to the trouble of doing so, and even if they do, results may be unreliable or inconsistent due to the fact that there are so many possible combinations of browser, operating system, locale and versions of each. Because of this, Web site authors do not tend to publish content in specialized XML formats.

1.2.3 SVG to the Rescue!

SVG, on the other hand, is a generalized vector graphic XML language that has a decent chance of either being natively supported in browsers or supported by plug-ins that need not be downloaded because they are so widely distributed with other application software. Finally there is a way to publish specialized vector graphic content to the Web in a manner that is accessible to the masses: convert existing graphical file formats to SVG, and publish the output.

An added benefit comes from using SVG as a common format for all vector graphic publishing, allowing you to merge content from many different sources and semantic origins. These include specialized file formats as well as data formats. For an approach toward dynamically generating SVG graphs, maps and diagrams from XML data sources using XSLT, see the Graphical Stylesheets paper [GS] .

2. Domain-Specific Semantics

Before discussing tools to assist in the creation of file format converters, we need to have a good idea of the range of use cases, and the translation issues that arise therein. Each application domain will have its own unique geometric semantics which will not align perfectly with the semantics of SVG. It is beyond the scope of this paper to completely catalog all semantic features of all graphical application domains. Instead, we will choose one representative file format feature for each of a range of graphical application domains, discuss the issues that arise in translating this feature to SVG, and suggest conversion options.

2.1 Domain: Frame-Based Animation

2.1.1 Feature: Nondeterministic Frame Sequences

2.1.1.1 Issues

The SMIL Animation used by SVG allows one to specify continuous variation of attribute values and CSS properties over time. SVG viewer software might ultimately render this as a collection of frames, but the subdivision into frames can be adapted to the platform and to rendering speeds rather than being specified in advance by the SVG author. This permits smoother animations than are typical with frame-based animation formats. Effectively the graphic has been rasterized in the time dimension when it has been turned into frames, and as with spatial rasterization, it is preferable to wait until the time of rendering to choose resolution.

If we are converting a frame-based animation format to SVG, it is necessary to simulate the frames, along with the looping, event triggers and logic that determines frame sequencing and timing.

2.1.1.2 Options

One way to simulate frames is to define each one in a <defs> section, then point to successive frames in sequence from a <use> element that has an animated xlink:href attribute. The animated xlink:href can be achieved with a sequence of SMIL animation <set> elements or, equivalently, via a SMIL animation <animate> element that has multiple values. This method is capable of simulating linear sequences of frames and simple loops. An example is the bouncing ball of Fig. 1 , which is produced by the following SVG source:

<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN"
  "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg width="100%" height="100%" viewBox="-50 -30 100 150">
  <defs>
    <g id="ball">
      <circle r="10" fill="rgb(63,191,127)"/>
      <path fill="rgb(255,63,127)" d="M0,-10 A10,10 0 0,0 0,10 A13,13 0 0,1 0,-10z"/>
      <path fill="rgb(255,127,63)" d="M0,-10 A10,10 0 0,1 0,10 A13,13 0 0,0 0,-10z"/>
    </g>
    <use id="frame0" xlink:href="#ball"/>
    <use id="frame1" xlink:href="#ball" transform="translate(0,1) rotate(36)"/>
    <use id="frame2" xlink:href="#ball" transform="translate(0,4) rotate(72)"/>
    <use id="frame3" xlink:href="#ball" transform="translate(0,9) rotate(108)"/>
    <use id="frame4" xlink:href="#ball" transform="translate(0,16) rotate(144)"/>
    <use id="frame5" xlink:href="#ball" transform="translate(0,25) rotate(180)"/>
    <use id="frame6" xlink:href="#ball" transform="translate(0,36) rotate(216)"/>
    <use id="frame7" xlink:href="#ball" transform="translate(0,49) rotate(252)"/>
    <use id="frame8" xlink:href="#ball" transform="translate(0,64) rotate(288)"/>
    <use id="frame9" xlink:href="#ball" transform="translate(0,81) rotate(324)"/>
    <use id="frame10" xlink:href="#ball" transform="translate(0,100) rotate(360)"/>
  </defs>
  <text x="0" y="-20" text-anchor="middle" font-family="sans-serif" font-size="5">
    Click the ball to make it bounce
  </text>
  <line x1="-40" y1="111" x2="40" y2="111" stroke="black" stroke-width="2"/>
  <use xlink:href="#frame0">
    <animate attributeName="xlink:href" calcMode="discrete" begin="click" dur="3.8s"
      repeatCount="5" values="#frame0;#frame1;#frame2;#frame3;#frame4;#frame5;
      #frame6;#frame7;#frame8;#frame9;#frame10;#frame9;#frame8;#frame7;#frame6;
      #frame5;#frame4;#frame3;#frame2;#frame1"/>
  </use>
</svg>

Fig. 1: Simulation of Frame-Based Animation in SVG

Note that the ball's geometry is defined in the <defs> section and re-used in each frame definition with a different transformation applied. Thus the rendered object is a <use> element that references another <use> element. This is another common theme in frame-based animation: graphic elements called sprites are moved across a background, and frames can be defined by the current state of the sprites and the background images.

Unfortunately a pure SMIL Animation solution is not enough to handle cases of more complex frame sequencing. In particular, SMIL Animation is inadequate if there are non-deterministic branch points in which more than one frame may follow the current one (depending on number of loops, user actions, or other conditions being satisfied). The problem stems from limitations on the SMIL Animation begin attribute: The same conditions that trigger one animation to start cannot be used to constrain another animation from starting. This effectively prevents implementation of a general 'switch' statement in SMIL Animation.

A solution to the problem is to generate JavaScript to deal with branch points. If we are strictly simulating switch statements at the branch points then a small subset of the JavaScript language is sufficient. However, if we have to map from a scripting language in the source format (such as ActionScript in Macromedia Flash files) then a full-blown compiler might be needed, depending on the degree of feature support required in the mapper.

2.2 Domain: Presentations

2.2.1 Feature: Slide Navigation

2.2.1.1 Issues

SVG does not have an implicit structure for multiple canvases or sheets. However, presentations consist of multiple slides and, similarly, many other formats have some sort of pagination. There is a need to create separate slide or page views in SVG, as well as a mechanism to navigate from one slide or page to the next. If more than one SVG file is generated, there is a need to deal with the one-to-many mapping of files or streams, which has implications with regard to naming conventions, packaging, etc.

2.2.1.2 Options

In order to keep file sizes reasonable, one might wish to generate a separate SVG file for every slide, and distinguish them via a numbering system appended to the file name. This enables access to previous slide, next slide or Nth slide by file number. Alternatively, for ease of packaging and sending files over the internet, one might prefer to place all slides into one file. Slides can then be selected for display by manipulating either the <view> element or the visibility property.

Navigation controls can be provided for flipping through the slides, accessing them by number, accessing them by thumbnail, or searching their content. These can occur once in a master SVG file that references each slide, or be replicated in every SVG slide. They can be written using SVG hyperlinks and/or ECMAScript. Alternatively, they can be placed in an HTML container, written using HTML hyperlinks, HTML forms, or ECMAScript. The choice of design is primarily determined by usability and UI style considerations rather than technical considerations such as performance.

2.3 Domain: Professional Graphics

2.3.1 Feature: Proprietary Filter Effects

2.3.1.1 Issues

Vector graphic filter effects are algorithms to modify whatever geometry they are applied to, either before or after rasterization, to achieve artistic goals, affect rendition quality, or speed the creation of complex geometry. Vendors of professional graphic applications often try to distinguish themselves with unique, proprietary filter effects. Furthermore, plug-in architectures for filter effects have enabled thriving 3rd-party businesses that create and sell specialized filter effects.

The proliferation of filter effects creates difficulties when it comes to mapping professional graphic formats to SVG. It is impractical to support every filter effect, the algorithms for many are not publicly available, and many do not map in any obvious way to SVG's basic set of filters.

2.3.1.2 Options

Despite the foregoing, many filter effects can be simulated using creative (and unintended) combinations of SVG's 'feBlend', 'feColorMatrix', 'feComponentTransfer', 'feComposite', 'feConvolveMatrix', and 'feDisplacementMap'. These filter effects embody pixel-by-pixel operations that combine, move or change color, and may include table lookups or generalized functions. By combining them, one has considerable power to determing exactly how each pixel will end up. Simulating a foreign filter effect may involve constructing an appropriate lookup table, function, or artificial raster image used as a filter input, or some combination of these.

If heroic creative problem solving is still not enough, or if it is enough but your simulated filter effect takes hours to run, then the fallback option is to rasterize everything in the region affected by the foreign filter, and to store the resulting raster as an SVG <image>. There is no need to write your own rasterization code for this purpose, since SVG rasterization can be accomplished with toolkits such as Batik, which is available at http://xml.apache.org/batik.

2.4 Domain: Schematics

2.4.1 Feature: Constrained Geometry

2.4.1.1 Issues

Schematic diagrams tend to have two types of constraints:

  1. Formulas that determine one geometric quantity relative to others. For example, if the end of an arrow is supposed to be attached to the middle of the top side of an upright rectangle, then its position is determined from the rectangle's defining parameters as (x + .5w, y) where (x, y) are the coordinates of the top left corner of the rectangle and w is its width. As another example, the flow region for a text label for any shape or connector is determined by formula from the geometry of the shape or connector, and the size of text may also be keyed to the region size. Some formats allow you to apply a succession of formulas to compute geometry. Microsoft Visio is an example, since each shape has an associated "ShapeSheet", which is an entire workbook of spreadsheets that determine its geometry.
  2. Layout constraints that apply to groups of objects as a whole and are not easily expressed directly as formulas for individual geometric quantities. The most important of these is object avoidance: the closed shapes in a schematic diagram should not overlap one another, and connectors should route themselves around these shapes. This may be combined with "snap to grid", alignment or adjacency constraints.
2.4.1.2 Options

Often the source format will store the computed geometrical values after enforcing constraints, so that the geometry can be directly mapped to SVG, and full visual fidelity is possible without encoding constraint information in the SVG. However, if there is a need to make the SVG graphic interactively enforce constraints, or if computed geometry is not stored in the source format, then one can use ECMAScript to encode the constraint information. In this scenario, script is used to compute SVG attribute values upon loading of the document and/or in response to user events, and these attributes are updated using the SVG DOM.

Fig. 2 provides an example of a glue point constraint, wherein a specified point on one object is constrained to be glued or attached to a specified point on another object. In this example, a point on the kite is glued to the end of its string. If you click and drag the kite, the glued end of the string moves with it, while the other end of the string remains fixed. The scripted SVG that produced this is as follows:

<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN"
  "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg width="400" height="400" viewBox="-200 -200 400 400"
  onmouseup="DoOnMouseUp(evt)" onmousemove="DoOnMouseMove(evt)">
  <script><![CDATA[
    var kiteX = 0;
    var kiteY = 0;
    var newKiteX = 0;
    var newKiteY = 0;
    var mousedownX = 0;
    var mousedownY = 0;
    var kite = null;
    var string = null;
				
    function DoOnMouseDown(evt)
    {
      var document = evt.getTarget().getOwnerDocument();
      kite = document.getElementById("kite");
      string = document.getElementById("string");
      mousedownX = evt.getClientX();
      mousedownY = evt.getClientY();
    }
    
    function DoOnMouseUp(evt)
    {
      if( kite != null )
      {
        kite = null;
        string = null;
        kiteX = newKiteX;
        kiteY = newKiteY;
      }
    }
    
    function DoOnMouseMove(evt)
    {
      if( kite != null )
      {
        newKiteX = kiteX + evt.getClientX() - mousedownX;
        newKiteY = kiteY + evt.getClientY() - mousedownY;
        var transform = "translate(" + newKiteX + " " + newKiteY + ")";
        kite.setAttribute("transform", transform);
        string.setAttribute("x2", newKiteX);
        string.setAttribute("y2", newKiteY);
      }
    }
  ]]></script>
  <rect x="-200" y="-200" width="400" height="400" fill="lightblue"/>
  <text x="0" y="-160" text-anchor="middle" font-family="sans-serif" font-size="15">
    Click and drag to fly the kite
  </text>
  <g id="kite" onmousedown="DoOnMouseDown(evt)">
    <g transform="rotate(-30)" fill="yellow" stroke="red" stroke-width="2">
      <polygon points="0,0 -20,-40 0,-60 20,-40"/>
      <line x1="-20" y1="-40" x2="20" y2="-40"/>
      <line x1="0" y1="0" x2="0" y2="-60"/>
    </g>
  </g>
  <line id="string" x1="-50" y1="150" x2="0" y2="0" stroke="black" stroke-width="1"/>
</svg>

Fig. 2: Glue Point Constraint Implemented in SVG

2.5 Domain: Computer-Aided Design

2.5.1 Feature: 3D Modelling

2.5.1.1 Issues

SVG has no direct support for views of 3D geometry. This involves:

perspective.png

Fig. 3: Perspective transformation with camera position O, mapping objects on the plane P to the camera plane Q. The transformation is defined everywhere but on the line L.

2.5.1.2 Options

Full 3D modelling requires 3D coordinates to be stored, which is an obvious non-starter for SVG. However, one can attempt to model different 3D perspectives on 2D elements, and this is important for CAD applications. For example, walls, windows, doors, floors etc. are all 2D surfaces put together into a 3D scene, and other 3D shapes are modelled as facetted surfaces, each facet of which is 2D. Perspective transformations of the plane are expressible using general 3x3 invertible matrices and homogeneous coordinates, whereas SVG only supports the smaller class of affine transformations. An option is to apply all the perspective transformations before mapping to SVG. For each curve in the original CAD file, a new curve is directly computed, and the transformation that led to that curve is no longer retained. This will accurately reproduce a 2D view of the 3D scene, but without the ability for the user to interact with their diagram to see other 2D views. Such interaction could be achieved by allowing the user to request new views that are generated from the original CAD file on the server. A client-side script solution is possible, but considerably more complicated.

There are two approaches to shading effects: If it is more important to have a one-for-one polygon representation in your SVG than it is to have pretty shading effects, then one can simply use an SVG flat fill for each facet that is an average of the colors at its vertices. If, on the other hand, visual fidelity is more important than polygon count, then one can simulate Gouraud shading by compositing multiple copies of each polygon.

In fact, a perfect visual simulation of Gouraud shading can be achieved by adding edge-perpendicular linear gradients using the <feComposite> arithmetic operator. As a demonstration, the following SVG file produces the shaded triangle in Fig. 4 :

<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN"
  "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg width="100%" height="100%" viewBox="0 0 3 4">
  <defs>
    <filter id="colorAdd">
      <feComposite in="SourceGraphic" in2="BackgroundImage" operator="arithmetic" k2="1" k3="1"/>
    </filter>
    <linearGradient id="grad1" x1="0" y1="0" x2="1.8" y2="3.6" gradientUnits="userSpaceOnUse">
      <stop offset="0" stop-color="purple" stop-opacity="1"/>
      <stop offset="1" stop-color="purple" stop-opacity="0"/>
    </linearGradient>
    <linearGradient id="grad2" x1="1" y1="4" x2="2.5" y2="2.5" gradientUnits="userSpaceOnUse">
      <stop offset="0" stop-color="green" stop-opacity="1"/>
      <stop offset="1" stop-color="green" stop-opacity="0"/>
    </linearGradient>
    <linearGradient id="grad3" x1="3" y1="3" x2=".8824" y2="3.5294" gradientUnits="userSpaceOnUse">
      <stop offset="0" stop-color="orange" stop-opacity="1"/>
      <stop offset="1" stop-color="orange" stop-opacity="0"/>
    </linearGradient>
    <polygon id="triangle" points="0,0 1,4 3,3"/>
  </defs>
  <use xlink:href="#triangle" fill="url(#grad1)"/>
  <use xlink:href="#triangle" fill="url(#grad2)" filter="url(#colorAdd)"/>
  <use xlink:href="#triangle" fill="url(#grad3)" filter="url(#colorAdd)"/>
</svg>

Fig. 4: Simulation of Gouraud shading in SVG

2.6 Domain: Geographic Information Systems

2.6.1 Feature: Application-Specific Schemas and Styling

2.6.1.1 Issues

GIS systems tend to be highly specialized for individual domains of application, such as transportation, agriculture, demographics, telephone/electrical/gas/water utilities, weather, agriculture, tourism, forestry, geology, etc. Each domain of application will have its own feature names and semantics, and each will expect the information to be rendered in a different way.

As far as file formats are concerned, a consequence is that generic GIS formats are incompletely specified, and additional application-specific information is needed. For example, Geographic Markup Language [GML] has the notion of Application Schemas, in which application-specific definitions are added to GML itself. A single converter from a generic GIS format to SVG is insufficient; one must add the ability to interpret Application Schemas or their equivalent in other formats.

2.6.1.2 Options

To accommodate application-specific schemas and styling, one needs a tool to create custom GIS format translators, rather than a specific translator. Although this paper is about tools to produce translator software, the focus is on developers rather than users of the translation software. Within the GIS problem domain, it is possible to create a user-friendly tool that allows custom translator creation without the need for software development expertise. SchemaSoft is working on such a tool for GML, which is described more fully in a GML Dev Days 2002 conference paper [SVGMaps] .

In addition to the wholesale customization possible with a translator-generating tool, one can customize map stylings after translation by applying various stylesheets to the SVG. To facilitate this, is is a good idea to generate appropriate class attribute values in the SVG to identify the originating application-specific semantic. Then XSLT and/or CSS can be applied, depending on the degree of custom styling desired.

2.7 Domain: Charts

2.7.1 Feature: Data Extent Determines Scale

2.7.1.1 Issues

When drawing a bar chart, line graph, stock chart, or any of a variety of other chart types, one has to ensure that a reasonable amount of data is shown in a reasonable amount of screen real estate, and that all data is visible. Axes should span an appropriate value range, the right units and tick mark spacing should be chosen, the height and width of data should fit the screen without being too small to see, text and data markings should not overlap one another, contrasting colors or patterns should be chosen to distinguish multiple data sets, etc. Applications that render charts may store rendering information in their native file format; but if not, then these computations have to be performed when mapping to SVG.

2.7.1.2 Options

If the nature of the data source is known, then one option is to build in uniform assumptions about data ranges in the translation software. However, for more general charting it is necessary to develop heuristic algorithms for scaling and positioning, and encode these in the translation software. As an example, an implementation of such algorithms for 10 different chart types is included in the SchemaSoft Catwalk download at http://www.schemasoft.com/catwalk/.

2.8 Domain: Formulas

2.8.1 Feature: Hierarchical Container Layout

2.8.1.1 Issues

Just as mathematical operators and functions can act upon one another in a nested fashion, the layout of mathematical formulae can involve a nesting of rectangular containers. Each container in this hierarchy is positioned horizontally and vertically relative to parent and sibling containers. The size and position of each sub-formula affects and is affected by its containing formula, so the order of processing is not obvious.

2.8.1.2 Options

As a general rule, layout is done by recursive processing from outermost container to innermost. Each recursive function call passes position coordinates as input arguments and returns container size as output. There are exceptions, for example, when a container is vertically aligned relative to a descendant of one of its siblings rather than one of its siblings. These exceptions can generally be dealt with by passing additional arguments in the recursion. Font metrics play a significant role, and one option is to simplify the problem by using a monospaced font throughout. As an example, software to convert from Mathematical Markup Language [MathML2] to SVG can be downloaded from SchemaSoft at http://www.schemasoft.com/mathml/.

3. Mapping Patterns

Now that we have analyzed file format mapping from a semantic perspective, we are in a position to consider the concrete object models used to represent file format features, and the recurring patterns descriptive of mappings between these object models - mapping patterns. While the previous section concerned itself with semantic mapping issues, the current section will deal mostly with syntax.

When studying mapping patterns, our objective is to identify commonalities that can be exploited in code re-use. For now we will be content to focus on a prototypical example of a file format mapping pattern. Toward this aim, we will provide XML descriptions of the source objects, the target objects, and the transformation from source to target. In later sections we will discuss an effort to formally abstract or template such mapping patterns, so that mapping code can be automatically generated from instance data.

NOTE: The following example uses XML to present example input objects, XML Schema [Schema] to present the object model (class definitions), and XSLT [XSLT] to present the transformation to SVG. It is important to recognize that these are strictly a means of presenting or storing the information, and they are not the encodings actually being proposed for efficient file format translator code. To begin with, binary input formats are not XML and, once parsed into in-memory objects, do not need to be serialized as XML. Secondly, XSLT processors expect XML as input - either serialized, as SAX events, or as an XML DOM implementation. None of these options is necessarily the most efficient interface with a binary format parser, which can create tailored, format-specific events or objects in memory rather than generic SAX events or XML DOM nodes. Although the XML DOM has been implemented in a format-specific way [BizDOM] , this requires a (less efficient) interpreted language because the class definitions are effectively constructed at runtime. Furthermore, XSLT is most useful only for the tree-walking aspects of transformation, not the raw mathematical computation aspects. So, at the very least an XSLT solution should be cross-compiled with code written in a more traditional language, such as Java (using XSLTC from http://xml.apache.org/xalan-j/xsltc_usage.html), or C# (using VisualStudio.NET).

3.1 Pattern Example: Subdivided Area

Consider the example of an area which is subdivided into a number of immediately adjacent regions, as is common in maps, tilings, 2D renditions of facetted 3D shapes, etc. For simplicity, suppose the regions are all polygons. These regions share polygonal boundary segments, and the same vertex data is repeatedly used in constructing all the regions. To avoid unnecessary redundancy, the source format might store a master list of points, with vertices recorded as indexes into that list.

The individual regions would normally also have some sort of styling information associated with them. For simplicity, we will limit allowed styling to colors that can be applied either to the interior or boundary of each region. Suppose that our source format accesses rendering styles by looking up a unique ID in a stored style table. This allows us to demonstrate a second, distinct lookup mechanism within the same example.

3.1.1 Object Model

Here is an object model for the proposed source format, drawn in Fig. 5 as a UML diagram, following which is a corresponding XML Schema file:

Fig. 5: Subdivided Area Object Model

<?xml version="1.0" encoding="UTF-8"?>
<schema targetNamespace="http://www.schemasoft.com/schema/subdividedArea.xsd"
  xmlns:area="http://www.schemasoft.com/schema/subdividedArea.xsd"
  xmlns="http://www.w3.org/2001/XMLSchema">
  <element name="subdividedArea">
    <complexType>
      <sequence>
        <element name="vertices">
          <complexType>
            <sequence>
              <element name="point" minOccurs="0" maxOccurs="unbounded">
                <complexType>
                  <attribute name="x" type="decimal"/>
                  <attribute name="y" type="decimal"/>
                </complexType>
              </element>
            </sequence>
          </complexType>
        </element>
        <element name="styles">
          <complexType>
            <sequence>
              <element name="style" minOccurs="0" maxOccurs="unbounded">
                <complexType>
                  <attribute name="id" type="ID"/>
                  <attribute name="color" type="string"/>
                  <attribute name="applyTo">
                    <simpleType>
                      <restriction base="string">
                        <enumeration value="interior"/>
                        <enumeration value="boundary"/>
                      </restriction>
                    </simpleType>
                  </attribute>
                </complexType>
              </element>
            </sequence>
          </complexType>
        </element>
        <element name="region" minOccurs="0" maxOccurs="unbounded">
          <complexType>
            <sequence>
              <element name="pointRef" minOccurs="0" maxOccurs="unbounded">
                <complexType>
                  <attribute name="index" type="nonNegativeInteger"/>
                </complexType>
              </element>
            </sequence>
            <attribute name="styleRef" type="IDREF"/>
          </complexType>
        </element>
      </sequence>
    </complexType>
  </element>
</schema>

3.1.2 Sample Input

In order to experiment with the conversion to SVG, we will begin with sample data expressed in the subdividedArea object model. The following XML describes a single triangle subdivided into four triangular regions, with the outer three regions filled in red and the central region outlined in blue:

<?xml version="1.0" encoding="UTF-8"?>
<area:subdividedArea
  xmlns:area="http://www.schemasoft.com/schema/subdividedArea.xsd"
  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
  xsi:schemaLocation="http://www.schemasoft.com/schema/subdividedArea.xsd
  subdividedArea.xsd">
  <vertices>
    <point x="200" y="0"/>
    <point x="100" y="100"/>
    <point x="200" y="100"/>
    <point x="0" y="200"/>
    <point x="100" y="200"/>
    <point x="200" y="200"/>
  </vertices>
  <styles>
    <style id="style1" color="red" applyTo="interior"/>
    <style id="style2" color="blue" applyTo="boundary"/>
  </styles>
  <region styleRef="style1">
    <pointRef index="1"/>
    <pointRef index="3"/>
    <pointRef index="2"/>
  </region>
  <region styleRef="style1">
    <pointRef index="3"/>
    <pointRef index="6"/>
    <pointRef index="5"/>
  </region>
  <region styleRef="style1">
    <pointRef index="2"/>
    <pointRef index="5"/>
    <pointRef index="4"/>
  </region>
  <region styleRef="style2">
    <pointRef index="3"/>
    <pointRef index="2"/>
    <pointRef index="5"/>
  </region>
</area:subdividedArea>

3.1.3 Mapping

To translate XML written as above into SVG, we must:

  1. generate a polygon for each region
  2. look up style properties by reference
  3. insert a fill or stroke style depending on the value of applyTo
  4. look up point lists by index
  5. fill in the polygon points attribute for each region

It is convenient to express such code as XSLT, particularly with the powerful XPath functions available for look-up. Here is XSLT that does the conversion:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"
   doctype-public="-//W3C//DTD SVG 1.0//EN"
   doctype-system="http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"/>
  
  <xsl:template match="/">
    <svg>
      <xsl:apply-templates select="//region"/>
    </svg>
  </xsl:template>
  
  <xsl:template match="region">
    <polygon>
      <xsl:attribute name="points">
        <xsl:apply-templates select="pointRef"/>
      </xsl:attribute>
      <xsl:apply-templates
        select="//style[@id=string(current()/@styleRef)]"/>
    </polygon>
  </xsl:template>
  
  <xsl:template match="pointRef">
    <xsl:apply-templates
      select="//vertices/point[number(current()/@index)]"/>
  </xsl:template>
  
  <xsl:template match="point">
    <xsl:value-of select="@x"/>,<xsl:value-of select="@y"/><xsl:text> </xsl:text>
  </xsl:template>
  
  <xsl:template match="style[@applyTo='interior']">
    <xsl:attribute name="fill"><xsl:value-of select="@color"/></xsl:attribute>
  </xsl:template>
  
  <xsl:template match="style[@applyTo='boundary']">
    <xsl:attribute name="stroke"><xsl:value-of select="@color"/></xsl:attribute>
    <xsl:attribute name="stroke-width">4</xsl:attribute>
    <xsl:attribute name="stroke-linejoin">bevel</xsl:attribute>
    <xsl:attribute name="fill">none</xsl:attribute>
  </xsl:template>
  
</xsl:stylesheet>

3.1.4 Results

Applying the above program to the sample input, we get the following succinct SVG file:

<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN"
  "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg>
  <polygon points="200,0 200,100 100,100 " fill="red"/>
  <polygon points="200,100 200,200 100,200 " fill="red"/>
  <polygon points="100,100 100,200 0,200 " fill="red"/>
  <polygon points="200,100 100,100 100,200 " stroke="blue"
    stroke-width="4" stroke-linejoin="bevel" fill="none"/>
</svg>

which looks much better in picture form, as in Fig. 6

Fig. 6: Result of mapping the subdivided area to SVG

Having demonstrated a fully-worked example, we are now in a position to consider how one might extract general patterns from specific mapping examples such as this. Are the lookup mechanisms part of the pattern, or can the geometrical idea of mapping subdivisions into separate regions be extracted on its own? Do the source object model or the result object model enter into the mapping pattern, or can the mapping pattern somehow be abstracted from its source or target? The next section attempts to provide an answer.

3.2 Generalizing the Mapping Pattern

3.2.1 Elimination of Source Format Dependency

The foregoing example of a mapping pattern was specific to both source format and result format. In practise, there is only one way that objects are stored in the source format, but there are many choices for how to encode the mapped result using the result format. Therefore we can choose one way to express an object model in the result format, and enforce this in our representation of a mapping pattern, but we have no choice over source format modelling. In order to be able to re-use the same mapping pattern on multiple source formats, we must generalize our notion of mapping patterns to be independent of the source format, and provide a mechanism to specialize those patterns to each candidate source format.

The assumption here is that there is a single result format being used. Indeed, a result format of SVG is the focus of this paper, and is particularly relevant for the problem of Web publishing a variety of vector graphic source formats. In practise, file format translation problems tend to have a single result format or a small number of result formats. Another way to say this is that import filters are much more popular than export filters. The reason for this is that vendors tend to want to bring all external formats to a single application format as a way of promoting that format and providing a focus for all their software tools. Ideally, their choice of result format is an open standard like SVG, but this is not always the case.

3.2.2 Method of Generalization

Well-factored XSLT code has the property that the essential source format dependency is expressed mostly in XPaths. That which cannot be expressed in XPaths can be encapsulated in XSLT functions. This observation applies to the translator code example of Section 3.1.3 , and to the examples of [GS] . XPath queries are used to identify the source of the data, and functions are used for any computations needed to re-parameterize that data, such as conversion of coordinate system. These functions can in general be nested, and not all their arguments need be functions or queries; some could simply be constants. Putting it all together, our source dependency is modelled as a function-query-constant tree, wherein the node types are functions, queries and constants; and the child nodes of a function node are its arguments.

The function-query-constant tree model can be preserved in file format translator code even if the code is not XSLT and the source objects it consumes are not serialized as XML. In fact, this is what we do in the file format translator RAD kit discussed in Chapter 6 , and it is the essential method of factoring out source format dependencies from mapping patterns. Specifically, we parameterize each mapping pattern, and an instance of the parameterized mapping pattern is obtained by assigning one function-query-constant tree to each parameter. Rather than use a simple list of parameters, we allow hierarchical groupings of parameters, expressed as XML trees with the parameters at leaf nodes. These are called input object trees, and they describe the structure of the source-format-specific information that needs to be filled in. Specializing a parameterized mapping pattern to a specific input format therefore involves appending one function-query-constant tree to each leaf node of the input object tree. Section 4.3 includes the specific syntax used for these trees, and its use for generating code is discussed in Section 6.4.2 .

As a simple example, consider conversion from polar to cartesian coordinates. If the polar angle is measured in degrees rather than radians, the relevant formulas are as given in Fig. 7 .

Fig. 7: Formulas for polar to cartesian coordinate conversion

If our source format represents polar coordinates as

<polar r="2" theta="60"/>

and the input object tree we choose for cartesian coordinates is

<object name="cartesian">
  <param name="x"/>
  <param name="y"/>
</object>

then the parameters of any mapping pattern expecting cartesian coordinate input can be filled in to access source polar coordinates as follows:

<object name="cartesian">
  <param name="x">
    <func name="multiply">
      <query xpath="/polar/@r/text()"/>
      <func name="cos">
        <func name="multiply">
          <func name="divide">
            <const value="3.14159265"/>
            <const value="180"/>
          </func>
          <query xpath="/polar/@theta/text()"/>
        </func>
      </func>
    </func>
  </param>
  <param name="y">
    <func name="multiply">
      <query xpath="/polar/@r/text()"/>
      <func name="sin">
        <func name="multiply">
          <func name="divide">
            <const value="3.14159265"/>
            <const value="180"/>
          </func>
          <query xpath="/polar/@theta/text()"/>
        </func>
      </func>
    </func>
  </param>
</object>

Applying this instance of the mapping pattern to the example polar coordinates above leads to the following cartesian coordinates:

<object name="cartesian">
  <param name="x" value="1"/>
  <param name="y" value="1.73205"/>
</object>

3.3 Parameterized Polygons

Now that we have defined a mechanism for generalizing mapping patterns, let's revisit the subdivided area example of Section 3.1 to apply this generalization mechanism. When we factor out the source format dependency, this removes both the index-based lookup and the ID-based lookup from the pattern. In fact, the pattern ends up being characterized more closely by the nature of the output in Section 3.1.4 . It generalizes to any collection of polygons, with fill color and stroke color specifiable for each polygon.

3.3.1 Input Object Tree

Here is a simple object model for the pattern: polygons consist of a list of polygon objects, each of which consists of a list of point objects, along with a fill and stroke property. Each point object has an x and a y property.

This can be formally written as the following input object tree:

<object name="polygons">
  <object name="list">
    <param name="for"/>
    <object name="polygon">
      <object name="list">
        <param name="for"/>
        <object name="point">
          <param name="x"/>
          <param name="y"/>
        </object>
      </object>
      <param name="fill"/>
      <param name="stroke"/>
    </object>
  </object>
</object>

An object has been used to represent lists, and it has a for parameter meaning one list item is created for each source node provided as input to this parameter.

3.3.2 Mapping Specificaton

To make a mapping specification from subdivided area format to parameterized polygons, we have to add a function-query-constant tree to each input parameter. Taking advantage of the XPath queries found in Section 3.1.3 , a full mapping specification would read:

<object name="polygons">
  <object name="list">
    <param name="for">
      <query xpath="/subdividedArea/region"/>
    </param>
    <object name="polygon">
      <object name="list">
        <param name="for">
          <query xpath="./pointRef"/>
        </param>
        <object name="point">
          <param name="x">
            <query xpath="//vertices/point[number(current()/@index)]/@x"/>
          </param>
          <param name="y">
            <query xpath="//vertices/point[number(current()/@index)]/@y"/>
          </param>
        </object>
      </object>
      <param name="fill">
        <query xpath="//style[@id=string(current()/@styleRef)][@applyTo='interior']/@color"/>
      </param>
      <param name="stroke">
        <query xpath="//style[@id=string(current()/@styleRef)][@applyTo='boundary']/@color"/>
      </param>
    </object>
  </object>
</object>

Although this specifies the mapping, it does not implement the mapping. In Chapter 6 we will discuss the process of generating code to implement mapping specifications.

4. A Schema for File Formats

4.1 Re-use and Styling

A first step toward file format software re-use is file format information re-use. This is achieved by creating a file format data repository that stores features, object structures and mapping information. By encoding this in XML, it becomes a straightforward matter to query and present custom views of the data using XSLT that maps to presentation formats such as XHTML+CSS or SVG. Different XSLT stylesheets are used, for example, for:

4.2 Methodology

We distinguished between four different types of graphical application information:

  1. Properties that are saved to file;
  2. The actual file format: that is, the layout of bytes within a file and their significance;
  3. Graphical application functionality;
  4. SDK functionality.

Only the first two of these are of interest for the data repository, though all four types of information can be used in the process of gaining this information.

The DTD for storing file format information was designed and modified partly in response to actual data collection. Because at each stage of the project the existing content already conformed to a previous version of the format comparison DTD, it was possible to migrate the documents to new versions of that DTD, using XSLT, as documenters uncovered complexities in new areas. The use of XML also offered the possibility for each file format to be documented independently. These separate XML documents could then be merged into a single XML document, again using XSLT. This merged XML document serves as the basis for further processing, such as styling or delivering reports. In essence the merged XML document becomes a database which may be queried and transformed in any way desired.

A set of feature categories was first defined, containing all of the distinct features offered by all of the file formats. This was based fairly directly on the SVG specification chapters, which are considered reasonably general, and was extended as the capabilities of each of the file formats were examined. Support for each format was then determined by deriving a set of properties for each feature available in that format. The exportability of each property, from its own file format to SVG, and from SVG to each of the other file formats, was then documented.

When file format information is not already fully documented, it is necessary to perform file format analysis. The methods and tools used for this are integrated with our file format mapping tools, although a detailed description of these is beyond the scope of this paper. To understand a format to the level of documenting features (but not necessarily their byte layout), one can take advantage of automation APIs, user documentation, and XML export capabilities. A key source of information can be the use of the actual applications to empirically determine features, properties and values. In brief, the process consisted of a set of steps:

  1. Apply a change to an object, using different property values than the defaults;
  2. Save and close the application;
  3. Re-open the application with the same document;
  4. Select the same object to which the change was applied, and;
  5. Determine if the targeted parameters can be edited.

4.3 Document Type Definition

The DTD for the file format information repository is:

<?xml version="1.0" encoding="UTF-8"?>
<!ENTITY % XMLSchema PUBLIC "-//W3C//DTD XMLSCHEMA 200102//EN" "XMLSchema.dtd">
%XMLSchema;
<!ELEMENT formatComparison (header?, preamble?, category*)>
<!ELEMENT header (title?, author*, date?)>
<!ELEMENT title (#PCDATA)>
<!ELEMENT author (#PCDATA)>
<!ATTLIST author
  affiliation CDATA #IMPLIED
>
<!ELEMENT date (#PCDATA)>
<!ELEMENT preamble (section | description)*>
<!ATTLIST preamble
  title CDATA "Introduction"
>
<!ELEMENT section (section | description)*>
<!ATTLIST section
  title CDATA #IMPLIED
>
<!ELEMENT category (description*, feature*)>
<!ATTLIST category
  name CDATA #REQUIRED
>
<!ELEMENT feature (description*, support*)>
<!ATTLIST feature
  name CDATA #REQUIRED
>
<!ELEMENT support (detail*, property*, featureRef*, xs:schema?)>
<!ATTLIST support
  format CDATA #REQUIRED
  supported (true | false | undefined) #REQUIRED
>
<!ELEMENT property (description?, values?, default?, appliesTo?, detail*, export*, featureRef*)>
<!ATTLIST property
  name CDATA #REQUIRED
>
<!ELEMENT featureRef (detail*, export*)>
<!ATTLIST featureRef
  category CDATA #REQUIRED
  feature CDATA #IMPLIED
  property CDATA #IMPLIED
>
<!ELEMENT export (detail*, mapping*)>
<!ATTLIST export
  to CDATA #REQUIRED
  degree (none | partial | full) "none"
>
<!ELEMENT mapping (object)>
<!ATTLIST mapping
  uri CDATA #REQUIRED
  version CDATA #IMPLIED
>
<!ELEMENT object (object | param)*>
<!ATTLIST object
  name CDATA #IMPLIED
>
<!ELEMENT param (func | query | const)?>
<!ATTLIST param
  name CDATA #IMPLIED
  type CDATA #IMPLIED
  default CDATA #IMPLIED
>
<!ELEMENT func (func | query | const)*>
<!ATTLIST func
  ns CDATA #IMPLIED
  name CDATA #REQUIRED
>
<!ELEMENT query EMPTY>
<!ATTLIST query
  xpath CDATA #REQUIRED
>
<!ELEMENT const EMPTY>
<!ATTLIST const
  type CDATA #IMPLIED
  value CDATA #REQUIRED
>
<!ELEMENT description (#PCDATA | a | list | code)*>
<!ELEMENT detail (#PCDATA | a | list | code)*>
<!ELEMENT values (#PCDATA | a | list | code)*>
<!ELEMENT default (#PCDATA | a | list | code)*>
<!ELEMENT appliesTo (#PCDATA | a | list | code)*>
<!ELEMENT list (item*)>
<!ATTLIST list
  type (unordered | ordered) "unordered"
>
<!ELEMENT item (#PCDATA | a | list | code)*>
<!ELEMENT a (#PCDATA)>
<!ATTLIST a
  xmlns:xlink CDATA #FIXED "http://www.w3.org/1999/xlink"
  xlink:type (simple) #FIXED "simple"
  xlink:href CDATA #REQUIRED
>
<!ELEMENT code (#PCDATA)>

4.4 Description of Elements

The approach taken is to uniformly classify standard graphical features, but provide format-specific descriptions of how those features are supported and mapped. Specifically, here are the elements and their meaning:

<formatComparison>

A formatComparison document has a root formatComparison element. This may contain an optional header element for metadata, an optional preamble element for general documentation, and any number of category elements to provide categorized file format feature information.

<header>, <title>, <author> and <date>

These elements are used for encoding title, author and date metadata at the top of the file.

<preamble>, <section>

The preamble element and its section descendents to any level are intended for providing basic chapter and section structures for introductory information. The actual textual content is written within description, list and a elements.

<description>, <detail>, <a>, <list>, <item>, <code>

description and detail elements can be used in various places to append documentation to formal file format structure information. The former is for high-level descriptive information, and the latter is for more detailed information. Both may contain text mixed with hyperlinks, lists and code. Hyperlinks are encoded with a elements, lists with list and item elements, and code with code elements.

<category>

category elements are used to provide named categories of file format features, where the chosen categories are common across all graphical file formats. Each category element contains any number of feature elements.

<feature>

A feature element represents a named file format feature, where the chosen features are common across all graphical file formats. Typically they correspond to objects in an object model, elements in an XML format, or items on a graphical application menu or toolbar. Each feature element contains one support element for each format that is being described in the repository, and that support element describes if and how the given file format supports this feature.

<support>

A support element has a format attribute that identifies the graphical file format under consideration, and a supported attribute that describes whether or not the file format supports the containing feature. A support element may contain any number of property elements specific to the file format of that support. These property elements detail the nature of feature support available in the given format.

<property>, <values>, <default>, <appliesTo>

A property element represents a named property of the containing feature. Each file format will in general parameterize a shared feature with different sets of properties, which is why there can be a different collection of property elements within each support element. Typically properties correspond to fields in an object model, attributes in an XML format, or geometric parameters in a graphical editing application. property elements can contain values elements as well as a default element to indicate a default value. They can also contain an appliesTo element in the case of properties that apply to many features; e.g. CSS properties.

By convention, only a property that has a values element may have an export element.

By convention, if a property has no values element, any featureRef elements in it should be followed to discover its values. If a property has a values element, its total value is defined by that values element, and all featureRef elements in it are considered to be "see also" kinds of references. This allows a complex property, which is composed of other parts, to be decomposed into multiple properties.

<featureRef>

A featureRef element is used to reference a category, feature, or property element from within a property or support element. By convention a featureRef is assumed to reference only elements that belong to the same file format. featureRef elements indicate relationships between features that are not strictly encoded in the XML tree hierarchy. Referencing is needed, for example, when the object hierarchy is deeper than feature-property-values and the properties of a given feature are listed as features themselves.

A featureRef element may contain any number of export elements. In practice, export elements on featureRefs are used only rarely, to indicate when exportability of the referenced property differs from that defined on the referencing property itself.

<export>

export elements determine the degree to which their containing property can be mapped from its file format to another format. An export element must have a to attribute that indicates the target format of the exportability, and should have a degree attribute that indicates the extent to which the property is deemed exportable (none, partial or full).

<xs:schema>

This is for describing format-specific object models using XML Schema. It is used for machine-generated class definitions, as is explained further in Section 6.4.1 .

<mapping>, <object>, <param>, <func>, <query>, <const>

The mapping element references a defined mapping pattern, and the remaining elements formally specify an instance of that pattern. These are used for machine-generated mapping code, as is explained further in Section 6.4.2 .

4.5 Interpretation Guidelines

Consistent use of the above schema requires consistent interpretation of its key elements and attributes. Here are some guidelines to help with this interpretation:

4.5.1 Support

A feature is shown as being supported, or not being supported, by each of the file formats. Feature support must not be confused with the ability to map easily to or from a feature. We say, for example, that neither Microsoft Visio nor Adobe Illustrator offer support for rectangles. Both Visio and AI are perfectly capable of displaying rectangles, but neither has a simple rectangle data type, and both use path expressions to draw rectangles.

4.5.2 Exportability

Our file format comparison DTD allows one to enter the degree to which each of the properties of one format can be "exported", or somehow represented using another format. A number of rules of thumb were adopted to aid documenters in this process, and keep the same standards across multiple file formats and multiple documenters:

4.5.3 Property Values

For the sake of simplicity, the document design defined a single level of properties for each supported feature. In most cases this proved to be adequate, but some features mapped to multiple file-format-specific elements, each with their own properties, and others inherited or reused generic properties, or groups of generic properties used by other features. To accommodate these we allow a property of a feature to reference other properties that are defined both within that feature and elsewhere. This occasionally leads to multiple levels of reference. It also opens up the possibility of circular references which would prove problematic for certain types of query made on the XML document structure. To constrain that, the following rules were introduced:

  1. If a property of a feature contains no values and it contains one or more feature references, those references may be followed to discover the actual values for the property. Such a property may contain more than one feature reference. In that case all of the referenced properties are considered to be components of the original property, and thus contribute to the definition of its values.
  2. If a property contains values, those are the complete values for that property. If it also contains one or more feature references, those references are not to be considered as the property's values, nor as components of the original property. Instead they are to be considered as "see also" references.

5. Automating File Format Documentation

Now that detailed file format information has been entered and marked up, we can easily generate documentation to suit a wide variety of interests and objectives.

Here are examples of tables generated from our repository using XSLT, for purposes of project planning. The proposed project is a Micrografx Designer 9 to CorelDRAW 10 converter, and we have generated summary-level tabular reports of two categories of features: Shapes ( Fig. 8 ) and Filters & Effects ( Fig. 9 ). In each case, checklists of feature support and feature mapping capabilities are recorded.

Fig. 8: Generated file format documentation

Fig. 9: Generated file format documentation

Note that we have organized the categories of graphical file format features to correspond closely to SVG's organization, the above two categories being examples. This organization is both a symptom of the level of generality of SVG and a strategy based on the fact that SVG is a very common target for current graphical format conversions.

6. Automating Translator Code Development

6.1 Code Re-use

Earlier we alluded to the possibility of exploiting mapping patterns for code re-use. Code re-use can take many forms, including:

Existing generalized filter frameworks tend to take advantage of a number of the above strategies. In particular, they tend to rely on a generic intermediate object model. Any mapping from format A to format B is done in two steps: an import filter from A to the intermediate object model, followed by an export filter from the intermediate object model to B.

This design scales really well: to support all possible mappings between N formats, you only need 2N filters, rather than the N2-N that would be needed if an intermediate format were not used. However, this design has at least two major drawbacks:

  1. The double conversion is inefficient. There is usually a more direct mapping that avoids the intermediate format.
  2. There tends to be unnecessary loss of information in the conversion, since the intermediate format tends to be a "lowest common denominator".

6.2 Improving on Filter Frameworks

We seek an alternate design that avoids these problems yet still achieves at least the same level of scalability and code re-use. Fundamentally, the re-use comes from identifying commonalities among all formats and representing these in code. An intermediate format achieves this by identifying sets of similar features across all file formats (e.g. the set of all "path" object models), and creating a prototypical representation of each set of features (e.g. one particular "path" object model). The problem is that this prototypical representation is just another instance, and does not capture the full generality of the set.

What we need, then, is a way to represent entire sets of similar features from different file formats. This suggests some sort of parameterization, or template for the object model. However, it is clear from the examples given in this paper that neither C++ templates nor preprocessing macros are sufficient to achieve the required degree of generality. What we need is code generators: programs that take a parameterized description of a feature as input, and output the code that implements that feature, using the full power of a programming language to determine what code is produced by the given parameters.

What, exactly do we mean by "implement that feature" in the above proposal? Naively, since we were talking about parameterized object models, the implementation would be to write out the class definitions. But surely we have the opportunity to do more. We have seen above that patterns can be found in the mappings between object models, not just in the object models themselves. Therefore we should parameterize the mappings, which implicitly includes a parameterization of the object models.

To recap, we are proposing the following new approach to the creation of a file format mapping rapid development tool:

  1. Identify mapping patterns across all graphical file formats.
  2. For each such pattern,
    1. Parameterize the set of instances of the pattern
    2. Write a code generator that takes parameter values as input and produces format-specific mapping code as output.

To use this RAD kit, one would fill out the parameters of the relevant code-generators, generate code, and wire each code snippet to the relevant parser-generated event (so that a mapping is not performed until all the source objects used by that mapping have been constructed in memory).

6.3 Technology Choices

6.3.1 Parameterization Format

When filling out the parameters of a code generator, the developer must specify things like where to get data from the source format object model, what formulas to apply to this data, and what variations of the mapping pattern to choose. An effective model for this is presented in the UI of our Graphical Stylesheet generator [Catwalk] : the user fills in each parameter by constructing a tree whose interior nodes are functions and whose leaf nodes are either constants or XPath "queries" into the source object model. However the similarity ends there: the underlying processing of the filled-in data is very different for the two applications.

6.3.2 Programming Languages

A primary objective of the current code-generating proposal is that the format mappings be as efficient as hand-coded, natively compiled C++. Therefore we have chosen C++ as the programming language of the generated code. The code generator itself is used at design time and has no such efficiency constraints. It consumes a tree data structure that could be formulated as XML and it performs a very general templating function driven by the input XML. XSLT is ideal for such a task, so we choose it as the programming language of the code generator. Note that this XSLT has C++ as its target. This is the opposite of the approach warranted for [Catwalk] , in which a C++ program generates XSLT from similar input parameters. To improve the accessibility of the XPath inputs to the XSLT, we envisage using an XML encoding for these XPaths: one in which each axis specifier corresponds to an element type, for example.

6.4 Re-using the File Format Schema

Along with human-readable file format information, the formatComparison DTD of Section 4.3 permits inclusion of machine-readable code generator input. By keeping the two together in the same XML repository, the associations between documented mapping patterns and implementation of those patterns is preserved.

6.4.1 XML Schema for Object Models

The formatComparison DTD includes the entire XML Schema DTD by reference. This is for storing graphical object models in XML Schema notation.

The <xs:schema> element is a child of <support>, since each file format's support for a feature will have its own object representation. The descendents of each <xs:schema> provide the detailed object model definition, where elements are equated with objects, sub-elements are treated as member objects, and attributes are treated as member fields of primitive type.

Using XML Schema syntax for object models facilitates the creation of software to style this information into class definitions for machine consumption, SVG-encoded UML diagrams for human consumption, or any other useful representation of the object model.

6.4.2 Code Generators for Mapping Patterns

Instead of defining a file format mapping as XSLT (as was done in the subdivided area example of Chapter 3 ), we can now define it as a particular set of inputs to the parameters of a code generator identified by URI. This same URI is used to identify the namespace of the XML Schema for the parameter inputs of that code generator, so file format resources and tools can be nicely catalogued and cross-referenced.

Parameter inputs for the code generator are stored in the <mapping> element, which is a child of <export> because for each source format and each exported format there is a different set of mappings. The uri attribute of the <mapping> element identifies the code generator to be used and points to the XML Schema for that code generator's input object model. The <object> descendents of the <mapping> element must conform to the input object model, and their <param> children manifest an instance of that object model by providing parameter inputs. The parameter inputs are in general computed from source format objects by applying any number of nested functions, represented by <func> elements, to source object data, accessed by the XPaths in the xpath attributes of <query> elements. Constants are also allowed as function inputs in this calculation, encoded as <const> child elements of <func> elements.

Thus each mapping specification includes an input object tree structured according to the expected inputs of the relevant code generator, inside of which is nested a function-query-constant tree for each input parameter. The latter has interior nodes that are functions, and leaf nodes that are either XPath queries on the source objects of the mapping or they are constants. This structure provides a very general mechanism to describe how the input information needed for the mapping pattern gets encoded in the source objects. As a result, code generators for mapping patterns can be constructed independent of knowledge of the input format details, and can be re-used on many very different input formats.

7. Conclusion

To answer the need for Web publishing of a multitude of vector graphics locked in proprietary binary file formats, one needs a powerful, generalized file format toolkit capable of producing translator software with SVG as its target. This should include tools to encode file format mapping patterns, generate code that performs the mappings, and document the object models and mappings. By employing XML standards throughout the design process and storing file format information in XML repositories, one gains the benefit of re-use of sophisticated XML standards implementations, and a high degree of automation can be achieved.

Bibliography

[BizDOM]
Dynamic Classes API for XML DOM, P. A. Mansfield, Y. Khramov, R. Houben, XTech 2000 Conference Presentation, 1 March 2000. Available at http://www.gca.org/attend/2000_conferences/xtech_2000/proceedings/technicaltrack_wednesday.htm.
[Catwalk]
Catwalk, a RAD Tool for Dynamic SVG-Generating Web Applications, P. A. Mansfield, XML 2001 Conference Presentation, 13 December 2001. Available at http://www.idealliance.org/papers/xml2001papers/slides/Mansfield/Catwalk.zip.
[GML]
Geography Markup Language (GML) 2.0, S. Cox, A. Cuthbert, R. Lake, R. Martell, editors, OpenGIS Implementation Specification, 20 February 2001. Available at http://www.opengis.net/gml/01-029/GML2.html.
[GS]
Graphical Stylesheets: Using XSLT to Generate SVG, P. A. Mansfield, D. W. Fuller, XML 2001 Conference Paper, 13 December 2001. Available at http://www.idealliance.org/papers/xml2001/papers/html/05-05-02.html.
[MathML1]
Mathematical Markup Language (MathML) Version 1.0, P. Ion, R. Miner, editors, W3C Recommendation, 7 April 1998. Available at http://www.w3.org/TR/1998/REC-MathML-19980407.
[MathML2]
Mathematical Markup Language (MathML) Version 2.0, D. Carlisle, P. Ion, R. Miner, N. Poppelier, editors, W3C Recommendation, 21 February 2001. Available at http://www.w3.org/TR/MathML2/.
[Schema]
XML Schema, D. D.C. Fallside, Henry S. Thompson, D. Beech, M. Maloney, N. Mendelsohn, P.V. Biron, A. Malhotra, editors, W3C Recommendation, 2 May 2001. Available in three parts at http://www.w3.org/TR/xmlschema-0, http://www.w3.org/TR/xmlschema-1, http://www.w3.org/TR/xmlschema-2.
[SVG]
Scalable Vector Graphics (SVG) 1.0 Specification, J. Ferraiolo, editor, W3C Recommendation, 4 September 2001. Available at http://www.w3.org/TR/SVG/.
[SVGMaps]
Rapid Development and Publishing of Custom SVG Maps Using Graphical Stylesheets, D. W. Fuller, J. Howard, J. Lindgren, P. A. Mansfield, GML Dev Days 2002 Conference Paper, 26 July 2002. Conference site http://www.gmldev.org/.
[XPath]
XML Path Language (XPath) Version 1.0, J. Clark, S. DeRose, editors, W3C Recommendation, 16 November 1999. Available at http://www.w3.org/TR/xpath.
[XSLT]
XSL Transformations (XSLT) Version 1.0, J. Clark, editor, W3C Recommendation, 16 November 1999. Available at http://www.w3.org/TR/xslt.

Valid XHTML 1.0!