SourceForge.net Logo

D.R.I.V.E.

Digraph Research Inside Virtual Environments


Tridimensional Digraph Document

TDF Version 2.01

This version:
http://drive.sf.net/tdf/2.01
Latest version:
http://drive.sf.net/tdf
Author:
Sandro Bonazzola

Questo documento è disponibile anche in italiano.

Copyright (c) 2003-2004 by Sandro Bonazzola


Abstract

The Tridimensional Digraph Document is a specification for the description of a digraph in the tridimensional space.
This specification was developed as a part of a major project for Politecnico di Milano by the author for the data exchange with a path finder software. This specification formalize a generic, multipurpose, tridimensional digraph that allow a developer to describe a digraph in the 3D space and adding some information about the nodes, inside the document itself or outside the document using an uniform resource locator (URL).

Status of This Document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. New version may be available from D.R.I.V.E. project.

This document should be the latest version of the TDF specification. No more changes should be made in the nearest future. The author has planned the following versions:

A list of changes to this specification:

Tridimensional Digraph Format Library Documentation Copyright (c) 2003-2004 by Sandro Bonazzola Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License". You should have received a copy of the GNU Free Documentation License along with this document; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

Table of Contents

  1. Introduction
    1. Tridimensional Digraph Format
    2. Terminology
    3. Design Rationale
  2. Conformance
    1. Document Conformance
    2. Client Conformance
  3. Tridimensional Digraph Document Type
    1. The Digraph element
    2. The Node element
    3. The Arc element
  4. How to use libtdf
    1. Requirements
    2. Building
    3. Using libtdf c library
    4. Using libtdf shell scripts
  5. Acknowledgements
  1. Tridimensional Digraph DTD
  2. Tridimensional Digraph XSL
  3. References
    1. Normative References
    2. Informative References

1. Introduction

All sections of this document are normative unless noted as informative.

1.1. Tridimensional Digraph Format

This section is informative.

The Tridimensional Digraph Document is a specification for the description of a digraph in the tridimensional space.
This specification was developed as a part of a major project for Politecnico di Milano by the author for the data exchange with a path finder software. This specification formalize a generic, multipurpose, tridimensional digraph that allow a developer to describe a digraph in the 3D space and adding some information about the nodes, inside the document itself or outside the document using an uniform resource locator (URL [URL]).
With the document type definition (DTD) you can find an XSLT [XSL]application that allow a traduction of the XML [XML] digraph in a VRML97 [VRML97] compliant rappresentation of the digraph structure.

The format is designed to be simple, human readable, complete.

1.2. Terminology

The keywords "MUST", "SHALL", "MUST NOT", "SHALL NOT", "REQUIRED", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" when used in this document are to be interpreted as described in RFC 2119 [RFC2119]. However, for readability, these words might not appear in all uppercase letters in this specification.

1.3. Design Rationale

The definition of a tridimensional digraph may be optained by a simple list of nodes and arcs. In the most general case, a digraph may be oriented or not. In many digraph application, each node may store some information about the node itself.

A node definition requires the knowledge of its spatial position. It has to be possible to give some information with the node. The nature of this information can't be defined here. In the most general case, it has to be possible to store the informations inside the document or in an external location. These goals were reached using XML, with the document definition described in this specification.

It should be possible for a human to see the digraph in a comprehensible and simple way. For this reason, should be provided a way to render graphycally the digraph. This goal were reached using XSL-T in order to produce a VRML97 compliant file from a TDF document conforming to this specification.

2. Conformance

2.1. Document Conformance

A conforming TDF document is a document that requires only the facilities described as mandatory in this specification. Such a document SHALL meet all of the following criteria:

  1. The document SHALL conform to the constraints expressed in the DTD found in Appendix A and conform to the constraints expressed in Design Rationale.
  2. The root element of the document MUST be Digraph.
  3. There MAY be a xml-stylesheet declaration in the document prior to the doctype declaration. If present, the stylesheet SHOULD reference the XSL-T found in Appendix B of this specification.
  4. There SHALL be a DOCTYPE declaration in the document prior to the root element. If present, the public identifier included in the DOCTYPE declaration SHALL reference the DTD found in Appendix A of this specification, using its Formal Public Identifier. The system identifier MAY be modified appropriately.
        <?xml version="1.0" encoding="utf8" standalone="no" ?>
        <?xml-stylesheet type="text/xsl" 
            href="http://drive.sf.net/tdf/tridimensionaldigraph.xsl"?>
        <!DOCTYPE Digraph PUBLIC "-//DRIVE//DTD TDF 2.01//EN"
          "http://drive.sf.net/tdf/tridimensionaldigraph.dtd">
    

    or
        <?xml version="1.0" encoding="utf8" standalone="no" ?>
        <?xml-stylesheet type="text/xsl" 
            href="file:///polimi/dtd/tridimensionaldigraph.xsl"?>
        <!DOCTYPE Digraph SYSTEM "-//DRIVE//DTD TDF 2.01//EN"
          "file:///polimi/dtd/tridimensionaldigraph.dtd">
    
  5. The MIME type used to refer to a conforming TDF document SHALL be "application/xml". An OPTIONAL "charset" parameter MAY be provided with the MIME type. Invalid values MUST be ignored and the result be as if the value were "utf-8". Usage of the OPTIONAL "charset" parameter is as described in section 3.2 of RFC3023 - XML Media Types [RFC3023].

2.2. Client Conformance

  1. Clients SHALL produce a well-formed TDF document as defined in Document Conformance.

Tridimensional Digraph Document Type

This section describes the elements defined for the Tridimensional Digraph Document and gives some examples about how to use them.

3.1. The Digraph element

<!ELEMENT Digraph (Node+, Arc*)>

The Digraph element is the root node for the dendrogram.
It is REQUIRED at least a Node element in order to obtain a well formed Graph.
It is REQUIRED that the Node's list is followed by the Arc list.
Attributes for the Digraph element:

author:
The author of the digraph
description:
A simple description for the purpose of the graph
url:
IETF RFC 1738: Uniform Resource Locators (URL)

Example:

    <Digraph
        author="John Doe - jd at foe.home"
        description="My apple tree"
        url="http://localhost:2000/my_apple_tree.jpg">

        <Node ... />
        ...
        <Node .../>
        <Arc .../>
        ...
        <Arc .../>
    </Digraph>

3.2. The Node element

<!ELEMENT Node EMPTY>

The Node element MUST be empty.
Attributes for the Node element:

id:
A unique identifier for the node like defined in REC-xml-19980210: 3.3.1 Attribute types.
description:
A simple description for the purpose of the node
url:
IETF RFC 1738: Uniform Resource Locators (URL)
center:
A string containing x, y, z coordinates of the node separated by a white space.

Example:

    <Node
        id="N1"
        description="The best apple"
        url="http://localhost:2000/my_best_apple.jpg"
        center="2.0 2.0 2.0" />

3.3 The Arc element

<!ELEMENT Arc EMPTY>

Attributes for the Arc element:

id:
A unique identifier for the node like defined in REC-xml-19980210: 3.3.1 Attribute types.
begin:
A defined node id. If the arc is oriented, this is the begin of the arc.
end:
A defined node id. If the arc is oriented, this is the end of the arc.
length:
The length of the arc. If it is specified it MUST be equal to the length of the vector connecting begin to end.
oriented:
A boolean flag to specify if the arc is oriented or not.

Example:

    <Arc id="L1" begin="N1" end="N2" length="1.01" oriented="true" />

4. How to use libtdf

This section explain how to build and use the libtdf library.

4.1. Requirements

The libtdf requires the following software correctly installed onto your system:

4.2. Building

Be sure that all requirements are satisfied. Then, if you have make configure Makefile with your preferences. Now just launch
make
For a binary distribution just launch
make bin
If you haven't make, compile all c files then link all object files to test object in order to get a working test suit. Use your library tool for creating a library containing xslt-tdf, cat-tdf and inline-tdf objects.

4.3. Using libtdf c library

For using libtdf c library just include libtdf.h in your source code, add libtdf to your library path and link your objects with the library. Example:
gcc -Imyincludepath/libtdf -Lmylibrary/libtdf myfyle.o -ltdf
In your source code use
tdftransform(infile, outfile, tdfstylesheet);
Where infile is a tdf document, outfile the output vrml file to write to, tdfstylesheet the location of the tdf xslt document.
To append the newly created vrml file to an existing vrml file you can use:
cattdf(infile, outfile);
Concatenate the newly created infile to the existent vrml file.
inlinetdf(infile, outfile);
inline the new infile into the existent vrml file using VRML97 Inline node.

4.4. Using libtdf shell scripts

Be sure that all requirements are satisfied. Then add inline-tdf.sh and cat-tdf.sh to your bin path. Now you can use the scripts:
for inlining the tdf document into an existent vrml file using VRML97 Inline node just type:

inline-tdf.sh source.xml destination.wrl

where:

for appending the tdf document at the end of an existent vrml file type:

cat-tdf.sh source.xml destination.wrl

where:

5. Acknowledgements

This section is informative.

This specification was prepared by Sandro Bonazzola for the course of Informatica Grafica I, Politecnico di Milano. Many thanks to Alessandro Saiani for his help.

A. Tridimensional Digraph DTD

<!--
# Document Type Definition (DTD) tridimensionaldigraph.dtd
#
# This is the first draft designed for the 3D path finding project for
# the course of Informatica Grafica 1 at Politecnico di Milano
#
# system location for this resource:
#   file:///polimi/dtd/tridimesionaldigraph.dtd
#	http://drive.sf.net/tdf/tridimesionaldigraph.dtd
#
# author:
#   "Sandro Bonazzola" <sandrobonazzola at users dot sourceforge dot net>
#
#
#    This file is part of Tridimensional Digraph Format Library - Manipulating TDF files
#    Copyright (C) 2003 by Sandro Bonazzola <sandrobonazzola at users dot sourceforge dot net>
#
#    This library is free software; you can redistribute it and/or
#    modify it under the terms of the GNU Lesser General Public
#    License as published by the Free Software Foundation; either
#    version 2.1 of the License, or (at your option) any later version.
#
#    This library is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    Lesser General Public License for more details.
#
#    You should have received a copy of the GNU Lesser General Public
#    License along with this library; if not, write to the Free Software
#    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA


-->


<!ELEMENT Digraph (Node+, Arc*)>
<!--
# Attributes for the Digraph element.
# author:   The author of the Graph
# description:  A simple description for the purpose of the graph
# url:      IETF RFC 1738: Uniform Resource Locators (URL)
# 
# Example:
#
#   <Digraph author="John Doe - jd at foe.home" description="My apple trees" 
#           url="http://localhost:2000/my_apple_tree.jpg">
#       <Node ... />
#       ...
#       <Node .../>
#       <Arc .../>
#       ...
#       <Arc .../>
#   </Digraph>
#
-->
<!ATTLIST Digraph
    author      CDATA   #IMPLIED
    description CDATA   #IMPLIED
    url         CDATA   #IMPLIED
>


<!ELEMENT Node EMPTY>
<!--
# Attributes for the Node element.
# id:           A unique identifier for the node like defined in REC-xml-19980210: 3.3.1 Attribute types.
# description:  A simple description for the purpose of the node
# url:          IETF RFC 1738: Uniform Resource Locators (URL)
# center:       A string containing x, y, z coordinates of the node separated by a white space.
# 
# Example:
#
#   <Node id="N1" description="The best apple tree" 
#         url="http://localhost:2000/my_best_apple.jpg" center="2.0 0.0 2.0" />
#
-->
<!ATTLIST Node 
    id          ID      #REQUIRED
    description CDATA   #IMPLIED
    url         CDATA   #IMPLIED
    center      CDATA   #REQUIRED
>

<!ELEMENT Arc EMPTY>
<!--
# Attributes for the Arc element.
# id:       A unique identifier for the arc like defined in REC-xml-19980210: 3.3.1 Attribute types.
# begin:    A defined node id. If the arc is oriented, this is the begin of the arc.
# end:      A defined node id. If the arc is oriented, this is the end of the arc.
# length:   The length of the arc. If it is specified it MUST be equal to the length of the vector
#           connecting begin to end.
# oriented: A boolean flag to specify if the arc is oriented or not.
# 
# Example:
#
#   <Arc id="L1" begin="N1" end="N2" length="1.01" oriented="true" />
#
-->
<!ATTLIST Arc 
    id          ID      #REQUIRED
    begin       IDREF   #REQUIRED
    end         IDREF   #REQUIRED
    length      CDATA   #IMPLIED
    oriented    (true|false) "false"
>

B. Tridimensional Digraph XSL

<?xml version='1.0' encoding="ISO-8859-1"?>
<!--
#    This file is part of Tridimensional Digraph Format Library - Manipulating TDF files
#    Copyright (C) 2003 by Sandro Bonazzola <sandrobonazzola at users dot sourceforge dot net>
#
#    This library is free software; you can redistribute it and/or
#    modify it under the terms of the GNU Lesser General Public
#    License as published by the Free Software Foundation; either
#    version 2.1 of the License, or (at your option) any later version.
#
#    This library is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    Lesser General Public License for more details.
#
#    You should have received a copy of the GNU Lesser General Public
#    License along with this library; if not, write to the Free Software
#    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

-->
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">
<xsl:strip-space elements="*" />
<xsl:output
  method="text"
  encoding="utf-8"
  media-type="model/vrml"
  indent="no"
  cdata-section-elements="Script"
/>

<!-- Add the VRML97 header and some information from the Graph node-->
<xsl:template match="Digraph">
  <xsl:text>#VRML V2.0 utf8
</xsl:text>
  <xsl:text>#author:     </xsl:text><xsl:value-of select="@author"/><xsl:text>
</xsl:text>
    <xsl:text>#description:</xsl:text><xsl:value-of select="@description"/><xsl:text>
</xsl:text>
  <xsl:text>#url:        </xsl:text><xsl:value-of select="@url"/><xsl:text>
</xsl:text>
  <xsl:apply-templates/>
  <xsl:text>#End of file</xsl:text>
</xsl:template>

<!--Add the nodes to the world-->
<xsl:template match="Node">
  <xsl:text>Transform { translation </xsl:text>
  <xsl:value-of select="@center"/>
    <xsl:text>
children [
</xsl:text>
    <xsl:text>Anchor{
 children [
</xsl:text>
    <xsl:text> Shape {geometry Sphere {radius 0.1} 
		appearance Appearance{material Material{emissiveColor 1 0 0}}}</xsl:text>
    <xsl:text>
]
</xsl:text>
    <xsl:text> url ["</xsl:text>
    <xsl:value-of select="@url"/>
    <xsl:text>"]
</xsl:text>
    <xsl:text> description "</xsl:text>
    <xsl:value-of select="@description"/>
    <xsl:text>"
}
</xsl:text>
    <xsl:text> ]}
</xsl:text>
</xsl:template>

<!--Add the arcs to the world-->
<xsl:template match="Arc">
    <xsl:text>Shape{appearance Appearance{material Material{emissiveColor 0 1 0}}
  geometry IndexedLineSet {coordIndex [0, 1] coord Coordinate{ point [</xsl:text>
    <xsl:variable name="b" select="@begin"/>
    <xsl:variable name="e" select="@end"/>
    <xsl:value-of select="//Node[contains(@id, $b)]/@center"/>
    <xsl:text>, </xsl:text>
    <xsl:value-of select="//Node[contains(@id, $e)]/@center"/>
    <xsl:text>]}}}
</xsl:text>
</xsl:template>
</xsl:stylesheet>

C. References

This section collect all bibliographyc references cited in this specification.

C.1 Normative References

[XML]
Extensible Markup Language (XML) 1.0 (Second Edition) - W3C Recommendation 6 October 2000 http://www.w3.org/TR/2000/REC-xml-20001006
[XSL]
Extensible Stylesheet Language (XSL) Version 1.0 - W3C Recommendation 15 October 2001 http://www.w3.org/TR/2001/REC-xsl-20011015
[VRML97]
ISO/IEC 14772-1:1997 - the Virtual Reality Modeling Language (VRML) -- Information technology -- Computer graphics and image processing -- The Virtual Reality Modeling Language (VRML) -- Part 1: Functional specification and UTF-8 encoding -- http://www.web3d.org/technicalinfo/specifications/vrml97/index.htm
[URL]
IETF RFC 1738 Uniform Resource Locator http://ds.internic.net/rfc/rfc1738.txt
[RFC2119]
RFC2119 - Key words for use in RFCs to Indicate Requirement Levels - http://www.ietf.org/rfc/rfc2119.txt
[RFC3023]
RFC3023 - XML Media Types - http://www.ietf.org/rfc/rfc3023.txt

A.2 Informative References

None.