A 3D spatial data model for terrain reasoning

Kevin C. Trott and Ian Greasley
PAR Government Systems Corporation
E-Mail: kevin_trott@partech.com, ian_greasley@partech.com

1. Introduction

This paper describes a 3D spatial data model, based on the 2D spatial data model that underlies NIMA's Vector Product Format (VPF)[1], which is capable of supporting three-dimensional representations of natural and man-made environments that include either partial or full 3D topology. It's development was driven by requirements for highly detailed synthetic environment databases that provide realistic representations of real-world locations for training and mission rehearsal purposes. Structures such as overpasses, tunnels, bodies of water, and the interiors of buildings cannot be fully represented using 2D topology, and require either partial or full 3D topology.

The 3D spatial data model is presented in terms of the types of 3D spatial entities required and the topological relationships among them. Level 4 (partial 3D) and Level 5 (full 3D) topology are then defined. Finally, an object-oriented implementation of 3D topology is briefly described.

2. 3D spatial entities

The 3D topology model includes the following types of spatial entities:

nodes,
edges,
faces,
volumes.

In addition, there are two supporting entity types:

rings, collections of edges that bound a face
shells, collections of faces that bound a volume

2.1 Nodes

A node is a zero-dimensional spatial entity that defines a location in 2D or 3D space. The location of a node is defined by a single coordinate tuple.

The location of each node must be unique, i.e., multiple nodes cannot be colocated. When 3D coordinates are used, the locations of two nodes can differ only in their vertical (Z/height) coordinates.

A node cannot be located within the interior of an edge. However, a node may be located within the interior of a face or within the interior of a volume.

A two-dimensional topology model can classify nodes into two subtypes, according to their topological relationships. A connected node is found at each endpoint of an edge, and is topologically linked to all edges that it bounds. An entity node is contained within the interior of a face, and is not located on or topologically linked to any edge that bounds that face. The 3D topology model adds a third type. A space node is contained within the interior of volume, and is not located within or topologically linked to any face which bounds that volume.

In the 3D topology model, it is not always possible to classify a node as being exclusively of a single type. It is possible for a node to be in the interior of a face, while also being the endpoint of an edge which does not bound that face, as shown in Figure 1. Similarly, a node can simultaneously be contained within a volume, and be the endpoint of an edge which does not bound that volume. This is also shown in Figure 1.

Figure 1

2.2 Edges

An edge is a one-dimensional spatial entity that defines a path through 2D or 3D space. The geometry of an edge is defined by an ordered collection of two or more distinct coordinate tuples, as shown in Figure 2. The orientation of an edge is defined by the ordering of its coordinate tuples.

Figure 2

An edge is bounded by a node at each of its two endpoints. The locations of the endpoints of an edge and the locations of the corresponding bounding nodes are identical. Whether or not the endpoint coordinates of an edge are stored explicitly within the edge is an implementation decision.

An edge may not intersect with or overlap itself or any other edge. An edge cannot pass through a node, or through a face, without being broken into separate edges. Two or more edges may meet only at a node.

An edge may be completely contained within a face, or completely within a volume. An edge may not be partially contained within a face or volume.

2.3 Faces

A face is a two-dimensional spatial entity that defines a closed area in 2D or 3D space. The geometry of a face is defined by:

a collection of one or more edges that bound the face
a collection of zero or more nodes that are contained within the face,
a collection of zero or more interior points that are analogous to the interior points of an edge.

The coordinate tuples of the bounding edges of a face are not necessarily coplanar. Any entity nodes that are contained within the face also help to define its three-dimensional shape. Also, just as the shape of an edge is defined by its interior points as well as by its endpoints, a face may contain one or more interior points with 3D coordinate tuples which also help to define its shape. The face shown in Figure 3 includes two interior points, one slightly below and one slightly above the outer boundary of the face.

Figure 3

A face has two sides. The orientation of a face is defined by the order of the edges that make up its outer boundary. The "top" side of a face is the side for which the outer boundary is defined in counter-clockwise order. In order to support vertical and overhanging surfaces, the orientation of the "top" side of a face must be capable of being defined to be an arbitrary direction, not necessarily parallel to the positive Z axis. Therefore, a face must have an explicit "up" vector. The three-dimensional shape of the face must be monotone with respect to this "up" vector, so that the face forms a 2D-pseudomanifold [2].

The outer boundary of a face is defined by an ordered collection of one or more edges. Faces may contain "holes", each of which is defined by an inner boundary consisting of an ordered collection of edges.

All of the points that make up the bounding edges of a face, including their common nodes, are considered to be part of the face for the purpose of defining its geometry. Any nodes or other interior points that are contained within the face are considered to be part of the face for the purpose of defining its geometry. Whether or not the boundary point, or any contained node coordinates, are stored explicitly is an implementation decision. Interior points of the face, if any, must be explicitly stored.

A face may not intersect with or overlap itself or any other face. Two or more faces may meet only at one or more common nodes, and/or along one or more common edges.

A face may be completely contained within a volume. A face may not be partially contained within a volume.

2.4 Rings

A ring is a sequentially connected set of edges that bound a face. Each ring is associated with a specific face. An edge which forms the boundary of one or more faces will appear in one ring for each of the faces which it bounds. An edge may appear twice in the same ring, if it is contained within the face that is associated with the ring. In such cases, traversing the ring will result in traversing the edge twice, once in each direction. Note also that it is possible for a node linking consecutive edges within a ring to be encountered more than once when the ring is traversed.

An outer ring defines the outer boundary of a face. Any edges that are contained in the face, but which are connected to the outer boundary of the face, are included in the outer ring. In Figure 4, the outer ring of Face 2 consists of Edge 1, Edge 2, Edge 3 (in one direction), and Edge 3 (in the other direction). The outer ring of Face 3 consists of Edge 4 and Edge 5.

Figure 4

An inner ring defines an inner boundary of a face (i.e., a "hole" in the face). In Figure 4, Face 2 has three inner rings, the first consisting of Edge 4 and Edge 5, the second consisting of Edge 6, Edge 7, and Edge 8 (twice, once in each direction), and the third consisting of Edge 9 (twice, once in each direction).

While it is common for an inner ring to contain one or more faces, it is possible for an inner ring to not contain any faces at all, and therefore to represent a true physical hole in the face. In Figure 4, there is an actual hole in Face 2. This is necessary in order to represent structures such as tunnel entrances and exits, open windows, or the hole in a bagel. The alternative would require that any such openings be "covered" by a "logical" face, which represents the logical opening, but which is not considered to be a physical barrier.

A collection of one or more edges which are connected to one another, and which are contained within the face, but which are not connected to the outer boundary of the face, form an inner ring even if they do not enclose an area. Each of the edges appears twice in such a degenerate inner ring, once in each direction. In Figure 4, Edge 9 forms such an inner ring within Face 2. Note that it is possible for such an edge to also be included in the outer boundary of one or more other faces which touch the containing face along that edge.

2.5 Volumes

A volume is a three-dimensional geometric primitive that is composed of the closed region of space bounded by a collection of faces. Volumes may be topologically linked to nodes, edges, and faces. The volume shown in Figure 5 is a simple rectangular prism bounded by six faces: top, bottom, front, back, left and right (the front face is transparent so that the others can be seen). The right and top faces contain one and two interior points, respectively.

Figure 5

A volume may not intersect with or overlap itself, or any other volume. Volumes may contain "bubbles", each of which is defined by an inner boundary consisting of a collection of faces.

2.6 Shells

A shell is an unordered collection of two or more faces that bound a volume. While it is possible, for many simple volumes, to order the faces that make up a shell such that each consecutive pair of faces in the sequence share a common edge, this is not possible in general. Each shell is associated with a specific volume. A face that forms the boundary between two volumes appears in exactly two shells, one for each of the volumes that it bounds. A face may appear twice in the same shell, once in each orientation, if it is contained within the volume associated with the shell.

An outer shell defines the outer boundary of a volume. Any faces that are contained within the volume, and that are connected to the outer boundary of the volume along an edge, are included in the outer shell. Figure 6 shows a cube (Volume 2) nested inside a larger cube (Volume 1). The outer shell of Volume 1 consists of Faces 1 through 6, while the outer shell of Volume 2 consists of Faces 7 through 12. An inner shell defines an inner boundary of a volume (i.e., a "bubble" within the volume). In Figure 6, the inner shell of the Volume 1 is made up of the same set of faces, Faces 7 through 12, as the outer shell of Volume 2.

Figure 6

A collection of one or more faces that are connected to one another along common edges, and that are con-tained within a volume, but are not connected to the outer boundary of the volume along a common edge, form an inner shell even if they do not enclose a volume. This includes any faces, or collections of connected faces, that are contained within the volume, and that touch the outer boundary of the volume only at one or more nodes. Each of these faces appears twice in such a degenerate inner shell, once for each orientation of the face.

An edge which is contained within a volume, but which is not part of the boundary of any face, is not considered to be a degenerate shell.

3. 3D topological relationships

This section defines the topological relationships that may exist between 3D spatial entities.

Note that there is a general symmetry that exists between the k-dimensional spatial entities and the N-k dimensional spatial entities within an N-dimensional space. In the 2D (N=2) case, this symmetry appears between nodes (k=0) and faces (N-k=2). Each edge is associated with exactly two nodes and exactly two faces. The graph of any 2D topological structure can be mapped into a dual graph in which a node replaces each face, and each edge represents a pair of adjacent faces.

In the 3D (N=3) case, the symmetry is between nodes (k=0) and volumes (N-k=3), and between edges (k=1) and faces (N-k=2). Just as every edge is associated with exactly two nodes, every face is associated with exactly two volumes. The relationships between edges and volumes and analogous to the relationships between faces and nodes.

The key relationship in 3D topology, which is the primary source of its complexity, is the many-to-many relationship between edges and faces.

3.1 Node-edge relationships

As shown in Figure 7, each edge can be associated with two nodes, one at each of its endpoints. The edge's start node is the node that is located at its starting endpoint. The edge's end node is the node that is located at its terminating endpoint.

Figure 7

A node may be associated with one or more edges. In 2D topology, these connected edges can be ordered in a counterclockwise direction around the node, starting with an arbitrary edge. However, in 3D topology, the collection of edges that are associated with a node cannot always be completely ordered, as the edges may connect to the node from any direction in three-dimensional space. When volumes are defined, subsets of the connected edges which bound a given volume can be identified, and the connected edges in each of these subsets can be ordered, just as in the 2D case.

3.2 Node-face relationships

As shown in Figure 8, a node can be associated with each face that contains it. These faces are called the node's containing faces. Note that with non-planar faces in 3D space, it is possible for more than one face to contain a specific node.

Figure 8

Conversely, each face is associated with a collection of zero or more nodes that are contained within its interior, which are called its contained nodes.

3.3 Node-volume relationships

As shown in Figure 9, a node can be associated with the volume that contains it. This volume is called the node's containing volume.

Figure 9

Conversely, each volume is associated with a collection of zero or more nodes that are contained within its interior, called its contained nodes.

3.4 Edge-face relationships

Under full 2D topology, each edge is associated with exactly two faces, which are called its left face and its right face, as shown in the left half of Figure 10. These names are defined relative to the orientation of the edge. However, under 3D topology, each edge can be associated with an ordered collection of zero or more faces, as shown in the right half of Figure 10. These bordered faces are ordered in a counterclockwise direction around the edge, starting with an arbitrary face, relative to the direction of the edge.

Figure 10

Each face is associated with one or more ordered collections of edges, each of which composes a ring, as shown in Figure 4. For all faces except the universe face, there is exactly one outer ring, which must contain one or more edges. (The outer ring of the universe face is at infinity, and so contains no edges.) Each face also may have zero or more inner rings, each of which must also contain one or more edges.

The many-to-many relationship between edges and faces is the primary source of the 3D spatial data model's additional complexity. An interesting implementation of this relationship can be found in [3], and is exploited in [4].

3.5 Edge-volume relationships

Under full 3D topology, each edge that bounds one or more faces is also associated with an ordered collection of one or more volumes, as shown in Figure 11. These bordered volumes can be ordered in a counterclockwise direction around the edge, alternating with the bordered faces, starting with an arbitrary volume, relative to the direction of the edge, just as edges are ordered around a connected node in 2D.

Figure 11

Under full 3D topology, a "floating" edge which does not bound any faces is contained within a volume (possibly the universe volume). The containing volume of such an edge is similar to the containing volume of an entity node.

Each volume is associated with one or more collections of edges. A collection of edges is associated with each of the shells that bound a volume, forming the outer rings of the faces that make up that shell, as shown in Figure 6. If the faces that make up the shell can be ordered such that each consecutive pair of faces share a common edge, then these edges can also be ordered in the same manner. However, this is not always possible.

A volume may also be associated with a collection of edges that are contained within it, but which are not included in any of its shells. Such "floating" edges are discussed further below.

3.6 Face-volume relationships

Under full 3D topology, each face is associated with exactly two volumes, which are called its top volume and bottom volume. These names are defined relative to the orientation of the face, as shown in Figure 12.

Figure 12

Under full 3D topology, each volume is associated with one or more collections of faces, each of which composes a shell. For all volumes except the universe volume, there is exactly one outer shell, which must contain two or more faces. (The outer shell of the universe volume is at infinity, and contains no faces.) A volume may have zero or more inner shells, each of which also must contain two or more faces. Because the collection of faces which makes up a shell cannot, in general, be ordered such that each face is connected to the next by a common edge, this one-to-many relationship must be explicitly defined.

3.7 Floating/dangling nodes & edges

Full 2D topology allows for edges, or collections of connected edges, that are "dangling" within a face (i.e., attached to a boundary of the face at only one end). A dangling edge, or collection of edges, is considered to be included in the ring to which it is attached. Each dangling edge appears twice in the ring, once in each orientation. A collection of dangling edges can enclose one or more faces. These edges appear in the outer rings of the faces that they enclose, as well as in the inner ring of the face that contains them.

The 2D topology model also allows for edges, or collections of connected edges, which are "floating" within a face (i.e., not attached to the outer ring of the face). A floating edge, or a collection of connected floating edges, is considered to be a degenerate inner ring of the containing face. Each edge appears twice in such a ring, once when it is traversed in each direction. Examples of floating and dangling edges under 2D topology are shown in the left half of Figure 13.

Figure 13

In an analogous manner, the 3D topology model allows for "dangling" or "floating" faces within a volume. A dangling face, or connected collection of faces, within a volume, is attached to either the outer shell or an inner shell of that volume along one or more, but not all, of its bounding edges. A dangling face is considered to be a part of the shell to which it is attached. Each such face appears twice in the shell, once in each orientation.

Similarly, a floating face, or collection of faces, within a volume, is not attached to any other shell of the volume along any of its bounding edges, and is considered to form a degenerate inner shell of the containing volume. Each floating face appears twice in the shell, once in each orientation. A face which is contained within a volume, and is attached to the boundaries of that volume only at one or more nodes, and not along a common edge, is considered to be a floating face rather than a dangling face.

The 3D topology model must also support "floating" edges within a volume. Any edge which is contained within a volume, and which does not bound any of the faces which form the outer shell, or any inner shell, of that volume, is considered to be a floating edge.

Under partial 3D topology, when no volumes exist, any edge which is not contained within a face is considered to be a floating edge. These are also loosely referred to as "entity edges". Examples of floating and dangling edges and faces under 3D topology are shown in the right half of Figure 13.

4. Levels of topology

Several of the topological relationships defined in the preceding sections depend on the level of topology that is present. Table 1 summarizes the topology levels. Note that the phrases in the Relationships column of the table, such as "start node" and "connected edges", actually refer to the topological relation-ships between two types of spatial entities, in this case connected nodes and edges. Only the entity that is the target of the relationship is explicitly named. Complementary pairs of these unidirectional relationships make up each bi-directional topological relationship.

Levels 0, 1, and 2 are defined as in the current VPF standard. At Level 0, only entity nodes and edges may exist, and there are no topological relationships. At Level 1, connected nodes appear, and edges may meet at connected nodes, but are not required to do so. At Level 2, 2D edges, or 3D edges when projected onto the XY plane, may meet only at connected nodes.

At Level 3 faces are added, and must completely partition the 2D space. Level 3 is defined exactly as in the current VPF standard, with one minor addition to better support 3D data. The three-dimensional shape of a face is defined not only by the 3D coordinates of its bounding edges and connected nodes (in both outer and any inner rings, including any dangling or floating edges), but also by the 3D coordinates of any entity nodes and/or any interior points that it contains. The shape of each face must be monotone with respect to the positive Z axis.

Although 3D coordinates can be included when Level 0, 1, 2, or 3 is present, the topological relationships at these levels are strictly two-dimensional. While it would be possible to define one or more 3D analogs of these levels, such as a 3D Level 2 which could be used to define three-dimensional networks of nodes and edges, we have not done so, as such structures can be considered to be included in Level 4.

Levels 4 and 5 require 3D coordinates, and represent partial and full 3D topology, respectively. When Level 4 or Level 5 topology is present, the surface defined by a face must be monotonic with respect to an explicitly defined "up" vector, rather than the positive Z axis.

Level 4 represents partial 3D topology, and is intermediate between Level 3 (full 2D topology) and Level 5 (full 3D topology). The Level 4 model includes the same types of primitives as Level 3, but some of the constraints found at Level 3 are eliminated or relaxed to allow limited 3D structures to be created. The characteristics of the Level 4 topology model are:

The locations of nodes are unique in 3D.
Nodes may simply be "floating" in space, with no topological relationships to any other primitives.
An edge may be associated with zero or more faces which it bounds, rather than just a left face and a right face, and therefore may be included in zero or more rings. An edge which does not bound any faces may touch faces at one or both ends, or may just "float" in space.
Faces may be non-planar, but must be monotone with respect to a specified "up" vector. Faces have distinct "top" and "bottom" sides, with an explicit orientation.
An arbitrary number of faces may meet at a common edge. The Level 3 requirement that faces must be mutually exclusive and exhaustive does not necessarily hold.
A face may touch other faces at one or more nodes, but such faces are not considered to be fully connected to each other.
A face may contain zero or more actual, physical "holes". While such holes are bounded by inner rings, these rings do not contain any faces.
Volumes are not explicitly represented.

Level 5 represents full 3D spatial topology, adding volumes as a three-dimensional primitive. Some of the characteristics of Level 5 topology are:

The modeled space is completely partitioned into a collection of volumes, forming a 3D manifold, including a universe volume, which represents all 3D space outside of the space contained in the explicitly represented volumes.
Space nodes, which are not connected to any edge or face, are each contained in a volume.
Floating, or "entity", edges, which do not bound any face, are contained in a volume.
Each volume has one outer shell and zero or more inner shells, representing "bubbles" within the volume. Each shell consists of an unordered collection of faces. The outer shell of the universe volume is at infinity.

Level	Spatial Entities	Relationships	Description
5 - Full spatial topology (3D coordinates)	Connected nodes, entity nodes, space nodes, edges, faces, & volumes (including universe volume)	Start & end nodes, connected edges, containing face, containing volume, contained entity nodes,contained space nodes, contained entity edges, bordered faces, bordered volumes, outer & inner rings, outer & inner shells	The space is partitioned by a set of mutually exclusive and collectively exhaustive volumes. Volumes meet only at faces, faces meet only at edges, and edges meet only at nodes.
4 - 3D Face Topology (3D coordinates)	Connected nodes, entity nodes, space nodes, edges, & faces (no universe face)	Start & end nodes, connected edges, containing face, contained entity nodes, bordered faces, outer & inner rings	A set of faces, edges and nodes where the faces meet only at edges and the edges meet only at nodes.
3 - Full planar topology (2D or 3D coordinates)	Connected nodes, entity nodes, edges, & faces (including universe face)	Start & end nodes, connected edges, containing face, contained entity nodes, left & right faces, outer & inner rings	The surface is partitioned by a set of mutually exclusive and collectively exhaustive faces. Faces meet only at edges, and edges meet only at nodes.
2 - Planar graph (2D or 3D coordinates)	Entity nodes, connected nodes, & edges	Start & end nodes, connected edges	A set of edges and nodes where, when projected onto a planar surface, the edges meet only at nodes.
1 - Non-planar graph (2D or 3D coordinates)	Entity nodes, connected nodes, & edges	Start & end nodes, connected edges	A set of entity nodes and edges that may meet at nodes.
0 - Boundary representation (2D or 3D coordinates)	Entity nodes & edges	None	A set of entity nodes and edges. Edges contain only coordinates.

5. Object model implementation

The 3D spatial data model described in the previous sections has been implemented as a collection of C++ classes. This section briefly describes the implementation of the topological relationships.

The 3D topological relationships are shown in Figure 14, using Object Modeling Technique (OMT) notation. Note the symmetry in this diagram, such that Nodes and Volumes are duals of each other, as are Edges and Faces.

Figure 14

All Nodes must be capable of supporting all of the possible topological relationships that a Node may participate in. If a Node is located within a Volume, it will have a containing Volume relationship with that Volume object. If it is located within one or more Faces, it will have a containing Face relationship with that Face object. Note that these two relationships are mutually exclusive. A Node may also be associated with an unordered collection of Edges that are connected to it. Note that this collection is unordered because the Edges can be attached to the Node from any direction in three-dimensional space. Each Edge also has a Coordinate Tuple object which defines its 3D geographic location.

Each Edge is associated with exactly two Nodes, its start node and its end node. Each Edge is also associated either with a containing Volume, if it is located within a Volume, or with an ordered collection of one or more Faces which it bounds. Each Edge also has an ordered collection of two or more Coordinate Tuple objects which define its 3D path.

Each Face is associated with exactly two Volumes, its top volume and bottom volume. Each Face has an outer Ring which defines its outer boundary, and zero or more inner Rings which define any inner "hole" boundaries. Each Ring is associated with an ordered collection of one or more Edges which define the boundary of the Face. Each Face may also be associated with an unordered collection of Nodes which it contains. Each Face may also have an unordered collection of Coordinate Tuple objects which, along with its bounding Edges and any contained Nodes, define its three-dimensional shape.

Each Volume has an outer Shell which defines its outer boundary, and zero or more inner Shells which define any inner "bubble" boundaries. Each Shell is associated with an unordered collection of two or more Faces which define the boundary of the Volume. Each Volume may also be associated with an unordered collection of Nodes which it contains, and/or an unordered collection of Edges which it contains.

Acknowledgements

This work was sponsored by the National Imagery and Mapping Agency (NIMA) under Contract No. NMA202-97-C-1044, VPF 3D Topology Extensions.

References

[1] MIL-STD-2407, Interface Standard for Vector Product Format, 28 June 1996.

[2] S. Pigot, "Generalized Singular 3-Cell Complexes". Proceedings of the Sixth International Symposium on Spatial Data Handling, pp. 89-111, 1994.

[3] K. J. Weiler, "Topological Structures for Geometric Modeling," Ph.D. Thesis, Rensselaer Polytechnic Institute, Troy, NY, 1986.

[4] M. Abdelguerfi, R. Ladner, K. Shaw, M. Chung, and R. Wilson, "VPF+: A Vector Product Format Extension Suitable for Three-Dimensional Modeling and Simulation", Draft, June 1998.