Return to GeoComputation 99 Index

PAR Government Systems Corporation

E-Mail: kevin_trott@partech.com, ian_greasley@partech.com

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.

- 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

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

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.

- 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.

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.

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.

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.

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.

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.

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.

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.

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.

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].

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.

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.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.

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.

- 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. |

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.

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

[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.