4.2.3 Solid-Based Representations

Solid-based representations are used where either the method of acquisition is volumetric in nature or where the application dictates a requirement for solid-based computations and manipulations. For example, consider the simple problem of computing the volume of a 3D object. If the object was stored, for example, as a closed surface represented using a mesh, there is no simple way in which this can be calculated. Using some of the solid-based representations described in this section, this is trivial. Common areas of application for solid-based representations include:

1.Medical Imaging [62]. Imaging modalities such as MRI and CT are volumetric in nature. Analyzing and visualizing such data necessitates volumetric representations. This is discussed further in Chap. 11.

2.Engineering. Components must be designed not only so that they fit together, but also so that their structural properties, determined by their 3D shape, meet specifications.

3.Scientific visualization [46]. Volumetric data arises in fields ranging from oceanography to particle physics. In order for humans to interact with and draw inferences from such data, it must be possible to visualize it in a meaningful way.

4.Finite-element analysis [79]. A numerical technique for finding approximate solution of partial differential equations and integrals.

5.Stereolithography [2]. A process in which an ultraviolet laser is used to trace out cross-sections through a 3D object, building up layers of resin until a complete object has been fabricated. Commonly known as “3D printing”.

6.Interference fit [35]. Designing object shapes so that two parts can be held together by friction alone.

Solids can either be represented volumetrically or by the surface which encloses them. In this section, we summarize the most common solid-based representations.

4.2.3.1 Voxels

Voxels are the 3D analog of pixels (the name is a contraction of “volumetric pixel”). They are sometimes also referred to as a spatial occupancy enumeration. Each voxel corresponds to a small cubic volume within space. At each voxel, a boolean is stored which indicates the presence or absence of the volume at that point. Alternatively, it may be more appropriate to store a scalar which represents, for example, density at that point in the volume. The precision of the representation is determined by the size of the voxel. A voxel representation is very efficient for making volumetric calculations such as clearance checking. Data storage requirements are high, since the number of voxels grows cubically with the resolution along each dimension. Voxels are the natural representation for volumetric imaging modalities. This is where the sensing device measures surface properties at discrete spatial locations over a 3D volume. Common examples include Magnetic Resonance Imaging (MRI) and Computed Tomography (CT). In vision, volumetric representations are also appropriate for methods such as space carving [33], where image cues are used to determine whether a voxel lies within the volume of an object.

There are two common ways to visualize voxel data: direct volume rendering or conversion to polygonal surface for traditional mesh rendering. In direct volume rendering, voxels are projected to a 2D viewplane and drawn from back to front using an appropriate color and opacity for every voxel. Such visualizations allow multiple layered surfaces to be visualized simultaneously (often exploited in medical imaging where skin, soft tissue and bone can all be visualized in the same image). Conversion to a polygonal mesh requires extraction of an isosurface of equal surface value throughout the volume. The most commonly used approach for this purpose is the marching cubes algorithm of Lorensen and Cline [40]. The algorithm proceeds by examining cubes formed by 8 neighboring voxels. Each of the 8 scalar values is treated as a bit in an 8-bit integer. If a scalar value is higher than the iso-value (i.e. inside the surface) it is set to one, otherwise it is set to zero. Hence, there are 28 = 256 possible configurations. The 8-bit integer is used to access a lookup table which stores a polygon associated with each voxel configuration. The individual polygons are then fused to form a surface.

A space efficient representation for voxel data is the octree. This uses adaptive resolution depending on the complexity of the surface throughout the volume. The key idea is that voxels which are fully occupied or fully empty are not subdivided,

Fig. 4.5 The 8 voxels produced by an octree voxel subdivision

Fig. 4.6 A volume represented using equally sized voxels (left) and the octree adaptive representation (right). Figure courtesy of lecture notes in computer graphics, Department of Computer Science, University of York

while partially occupied voxels are. This continues until either all voxels are occupied or empty, or the smallest allowable voxel size is reached. Subdividing a voxel into smaller cubes results in 8 smaller voxels (see Fig. 4.5). This representation can be stored in a tree structure in which nodes have 8 children. Leaves are fully occupied or empty voxels and the root represents the complete volume in which the object lies. The finest resolution is determined by the depth of the tree. The example shown in Fig. 4.6 demonstrates how, in regions of high curvature, subdivision can continue to obtain an arbitrarily high accuracy approximation to the underlying smooth volume. A 2-dimensional analog of the octree representation in which pixels are recursively subdivided into four smaller pixels can be stored in a quadtree.

4.2.3.2 K -d Trees

K-dimensional trees, or K -d trees for short, generalize the notion of space partitioning to arbitrary, axis-aligned planes. Whereas the octree uses a regular subdivision of space, a K -d tree is a data structure whose interior nodes represent a partition of space along a plane which is orthogonal to one of the axes. A K -d tree is stored in a binary tree where interior nodes represent a partition over an axis-aligned plane and leaf nodes represent a volume in space. As well as a volumetric representation for shape, K -d trees are widely used for organizing points to speed up multidimensional search [3], such as nearest-neighbor searches.

For example, Fig. 4.7 shows a K -d tree constructed over a 3-dimensional volume (initially comprising the white boxed region). The first subdivision is shown by the red plane. Each of the two subdivided regions are then split by the green planes and finally the blue planes yield 8 leaf volumes. The canonical method of construction cycles through the axes of the space, subdividing along each in turn, before returning to the first again. So, in the example in Fig. 4.7, the next partitions would be parallel to the red plane. The position of the partitioning is chosen by the median point

Fig. 4.7 A 3D example of a K -d tree. Figure courtesy of [76]

within the volume along the axis of partitioning. This strategy leads to balanced trees in which each leaf node is at the same depth.

K -d trees provide a way of reducing the complexity of nearest neighbor searches or distance-based segmentation. For example, in the problem of range searching the aim is to find all vertices which lie within a certain Euclidean distance of a target vertex (i.e. within a sphere centered on the target vertex with a radius given by the distance threshold). This is an important problem for computing local features and properties on surfaces. The brute force approach requires computation of the distance between the target vertex and all others. With a K -d tree, the volume in which the vertex lies can be found and only the distance to points within that volume need be considered. The overhead of constructing the tree becomes worthwhile when many such operations need to be performed. Note that for general range searching over a surface, the use of a distance threshold will fail for complex, highly curved surfaces (where Euclidean and geodesic distances vary greatly). In this case, it is necessary to consider vertex connectivity to ensure only connected regions of the surface are returned. This is discussed further in the next section.

4.2.3.3 Binary Space Partitioning

Binary Space Partitioning (BSP) further generalizes the notion of space partitioning to arbitrary subdivisions. Unlike the K -d tree, the cutting planes can be any orientation, thus a K -d tree is an axis-aligned BSP tree. A volume (or in 2D, an area) is represented by a series of binary tests determining which side of a plane (or in 2D, a line) a point lies on. This representation leads to a binary tree structure with the leaf nodes indicating whether a point lies inside or outside the volume