Review of Visualisation Systems

3.3 Algorithms

3.3.1 - Introduction

3.3.2 - Classification

3.3.3 - Interpolation

3.3.4 - Algorithms for scalar data over 3D

3.3.5 - Algorithms for vector field over 3D

3.3.6 - Scalar field over 2D

3.3.7 - Scalar field over 1D

3.3.8 - AVS

3.3.9 - IBM Data Explorer

3.3.10 - IRIS Explorer

3.3.11 - Khoros

3.3.12 - PV-WAVE

• first, we characterise the nature of the data - this effectively gives us classes of problems, such as scalar fields in 3D etc., (see section 3.3.2);
• next, we review briefly interpolation techniques - this gives us a means of creating a model from the data that is defined everywhere (see section 3.3.3);
• then, for each of the classes, we describe some of the possible visualization techniques (see section 3.3.4 to section 3.3.7);
• finally, we look at the availability of the different techniques in each system (see section 3.3.8 to section 3.3.12).

3.3.2 Classification

Indeed we shall use the nature of the underlying field as our means of classifying the visualization algorithms. We use a subset of the classification derived at the AGOCG Visualization Workshop in 1991 [11].

The letter represents the entity to be visualized, and a subscript denotes the dimension of the independent variables. Thus represents an entity defined over a 3D region. Time is treated specially - so in the above example, if the entity varies over time, we write .

The type of dependent variable can be scalar ( ), vector of dimension k ( ) or tensor ( ), and this is written as a superscript.

So a vector field over 3D is written as: .

3.3.3 Interpolation

There are a variety of methods and a good reference is the book by Lancaster and Salkauskas [44]. Here we give only a brief summary.

Consider first just . We shall be given a set of points . The interpolation problem is to construct a model F(x) which matches the data at the given points.

The simplest method is nearest neighbour, in which the value of F is taken to be the f-value of the nearest datapoint to x. Notice two features: it is very quick; but F(x) has a discontinuity midway between each datapoint.

Continuity can be improved by linear interpolation, in which F(x) is a linear function (that is, a straight line) between data points. This requires some computation so is slower, but F(x) is now continuous. Note however the slope of F(x) is not continuous, so if we know the underlying entity is smooth, then our recreation of it may be misleading in this sense.

Slope continuity (continuity of the first derivative of F(x)) can be achieved, but at the expense of more computation. A usual method is to estimate the slopes at the data points (for example, as the average of the slopes of the lines to adjacent data points) and then to fit a cubic function in each interval between data points. There are a variety of techniques for doing this piecewise cubic interpolation [12].

Second derivative continuity can be achieved, at even more computational expense, using cubic splines.

There are analogs of these methods in 2D and 3D. Consider first data on a rectilinear grid. The nearest neighbour extends in an obvious manner - it is quick, but discontinuous as in 1D.

Linear interpolation extends to bilinear (2D) or trilinear (3D). Bilinear interpolation proceeds thus: find the grid square of interest; use linear interpolation in x for both extreme values of y; use these two calculated values in a further linear interpolation step in the y-direction. Trilinear is an obvious extension to 3D. These give continuity of function value, at extra computation expense. Hill [21] describes computational aspects of linear, bilinear and trilinear interpolation.

It is important to note that the bilinear interpolant in 2D is deceptively complex to visualize: it is a curved surface with contour lines which are hyperbolic. Similarly, the trilinear interpolant in 3D is likewise complex: surfaces of constant value are hyperbolic in nature. For this reason it can be useful to split the rectangles into triangles, or cuboids into tetrahedra, and fit simpler interpolants in each triangle or tetrahedron. These have straight line contours, or planar surfaces of constant value, respectively.

Piecewise cubic interpolation extends to piecewise bicubic and piecewise tricubic; these provide first derivative continuity, but are relatively rare (especially tricubic) on account of the computation involved.

Suppose now the data does not lie on a rectilinear grid. A variety of techniques have been suggested for scattered data, and a good recent review is by Foley and Nielson [16]. A very simple and reliable method is multiquadric (MQ) interpolation. The MQ interpolant is continuous in all derivatives, and is defined (in 2D) as:

where

with R a constant and d the distance of (x,y) from the ith data point (xi,yi). The coefficients ai are found by solving the N linear equations:

The extension to 3D (and indeed higher dimensions) is straightforward.

Another good method is the quadratic Shepard's method. This has the form:

where Li(x,y) is a quadratic function constructed to be a good approximation to the underlying function near the corresponding data point (xi,yi), and wi(x,y) is a weighting based on the distance of the interpolation point (x,y) from the corresponding data point. Again the extension to 3D is straightforward.

Another approach is to construct, in 2D a triangulation of the data, or in 3D a tetrahedral decomposition. There are well known algorithms for this: the Delaunay triangulation has optimal properties in terms of avoiding long, skinny triangles - traditionally thought to be a good thing. (Note however that views on this are changing - data dependent triangulations that align the triangles with features of the data, rather than across them, can give superior results in practice - see the paper by Dyn et al [14])

The triangulation is useful because local interpolants can be fitted within each triangle. Again these can be linear to give function value continuity, or higher order to give slope continuity.

There are many other techniques for interpolating scattered data, and the reader is referred to [16] for detail. Renka [60] gives an efficient implementation of the quadratic Shepard method.

3.3.4 Algorithms for scalar data over 3D

---

A large class of applications require the visualization of a scalar field over a 3D region. For example, data from medical scanners, temperature or pressure data from CFD.

There are essentially two approaches:

• Surface Extraction: In this approach, a 2D surface of interest is extracted. The surface can be extracted as a 2D planar slice through the 3D region, with 2D algorithms being used to display the data. Alternatively, the surface can be extracted as an isosurface, comprising all points with the same value of the scalar field. The slice therefore extracts in the space of the independent variable; the isosurface extracts in the space of the dependent variable.
  
  Of course, these techniques display only a 2D subset of the data. However, the third dimension can be visualized through animation - in the case of slicing, the cross-section can moved in time through the 3D region; in the case of isosurfacing, the isolevel can be moved in time from minimum to maximum.
  
  Note that in the case of an isosurface, it is possible to visualize a second scalar field over the extracted surface, by assigning colour values to the surface corresponding to the second scalar field.
• Volume Rendering: In this approach, the entire 3D volume is visualized. This is achieved by mapping the scalar value to colour and opacity, to form a coloured jelly-like material which can then be rendered. This allows the interior of the volume data to be inspected, and varying the classification of data by colour and opacity enables different features of the data to be extracted. For example, in an extreme case, an isosurface can be extracted by classifying all values greater than a threshold to be opaque.

We now look at these approaches in greater detail:

Surface Extraction

---

Slicing

---

This is relatively elementary: the slice can be positioned anywhere in the volume, a special case being the orthogonal slice which is perpendicular to one axis. A typical visualization technique on the slice is the image display, in which each pixel is coloured according to the scalar value at the corresponding position on the slice; but other 2D techniques are possible (e.g. contour lines). The 2D algorithms are described in

Isosurfacing

The best known algorithm is marching cubes [47]. This assumes data defined on a set of cubical cells, and constructs a polygonal approximation to the isosurface on a cell-by-cell basis. The extraction uses linear interpolation along edges of the cube cells, and a simple strategy to determine the surface across faces and in the interior. This strategy needs some care however, as topological ambiguities can occur, and as a consequence there can be holes in the resulting surface. Ning and Bloomenthal [49] explain how this can occur, and the remedies which can be taken. Certainly a good algorithm will contain some robust disambiguation strategy.

One such strategy is to decompose each cell into a number of tetrahedra. If this is done carefully - again see Ning and Bloomenthal - then linear interpolation along edges is sufficient to uniquely define a piecewise linear interpolant within each tetrahedron, and hence an unambiguous surface over the entire volume. This is known as marching tetrahedra.

Other strategies are possible, and some are more efficient than marching tetrahedra because they generate fewer triangles.

If the data are not given on a structured mesh, then there are techniques to construct a tetrahedral mesh from the data

Marching tetrahedra can then be used on this mesh.

A common feature of all algorithms is the generation of a set of triangles which approximate the isosurface. These are passed to a geometry renderer for display. For lighting and shading, it is important to calculate surface normals at the triangle vertices, and different strategies are possible:

• Calculate the gradient of the scalar field (which is in the direction of the surface normal) at the data points - for cubical cells, central differences can be used. Linear interpolation along edges will give estimates of the normal at the triangle vertices.
• Calculate the normal at a vertex as the average of the normals to the triangles which share that vertex.

As mentioned earlier, the colour of the isosurface may be assigned by some transfer function of a second scalar field.

Volume Rendering

• Colour Classification: The range of scalar data values are mapped to a range of colours, using some transfer function.
• Opacity Classification: The range of scalar values are mapped to a range of opacity values, using again some transfer function.

3.3.5 Algorithms for vector field over 3D

---

This is the type: . The field is defined by position only, that is, it is time-invariant or steady.

There are a variety of techniques for the display of vector field data. For a good review, see [50] and [22]. We summarise the main techniques here:

• Arrows: A glyph showing the flow speed and direction, usually as an arrow of variable length, is drawn at a given set of points. One may choose to draw the glyph at some or all data points, in which case the data provides sufficient information. Alternatively, one may wish to draw the arrows at user-specified positions, in which case interpolation will be needed.
  
  There are serious perception problems when this technique is used in 3D. It is more successful when a 2D surface is extracted, and the arrows are shown only for data points on the surface - indeed it is often effective to draw only lines without an arrowhead giving a spiked appearance (hence the term "hedgehogs"). Some success has been obtained in 3D by using 3D glyphs.
• Particle Advection: This is based on a traditional experimental technique for flow visualization. A light-emitting particle is released into the field and its progress is filmed over a specified time interval. In experimental flow visualization, this is commonly called a pathline.
  
  In practice, this visualization technique is implemented as follows. An initial particle position is specified: say , at time . Then its progression is governed by the system of Ordinary Differential Equations (ODEs):
  
  
  with the initial values:
  
  
  Because the flow is steady, the velocities vx, vy and vz are dependent only on position, not on time. The solution of these equations is done numerically, and the quality of the ODE solver will determine the accuracy of the resulting path. Euler's method is simple and quick, but generally inaccurate. Better results will be gained by a Runge-Kutta method. There are a family of R-K methods, with differing orders of accuracy. Second order R-K is commonly used.
  
  The solution will also need interpolation to calculate the velocity at the points required by the ODE solver, and the different algorithms described earlier can be used.
  
  The presentation can be as the animated movement of the particle, or the trace of the particle path can be rendered. In this latter case, the path is identical to a stream line as explained below.
• Stream lines: These are lines which are everywhere tangential to the velocity field. The speed of flow is also indicated by the relative closeness of the streamlines. The method is better in 2D than 3D, some depth cueing being needed to assist perception.
  
  For steady flows, particle paths and stream lines are identical, and so the computation process is identical. The user will typically provide a set of starting positions from which the stream lines are generated.
• Stream ribbons: This is a variation in which a pair of adjacent stream lines are considered to be the edges of a ribbon, and rendered as such. This is useful to display twist in a flow field [23].
• Stream surfaces: This is another variation, where a number of adjacent streamlines are connected into a polygonal surface [24].
• Time lines: This is based on the experimental technique of releasing a line of hydrogen bubbles into the flow at a given time. The position of this line at a number of successive time intervals is then displayed - as an advancing front.
  
  In practice, this can be computed by selecting initial positions on a line in the flow. These are imagined as the start points of particle paths, and the positions of the particles at regular time intervals are recorded - interpolation through the positions at any time gives the corresponding time line.
• Streak lines: In experimental flow visualization, this is defined as a line composed of those particles which have passed through a specified location in a specified period of time. In computational visualization, the term is used somewhat loosely. Sometimes it is used to refer to the release of a line of particles whose position is tracked through the flow; in a steady flow, these particle tracers will follow stream lines. On other occasions, it is used to indicate particle paths through a time-varying field. When we look at different systems, we shall try to indicate the meaning of the term in the context of the system.
• Topology Methods: This approach identifies the critical points where velocity vector is zero - and classifies them as sources, sinks, etc. The connection of critical points divides the space into regions of common flow properties. This is described in [20]. This has been implemented in the FAST [9] visualization environment developed at NASA Ames Research Center, but to our knowledge is not available in other visualization systems.

• magnitude of velocity
• magnitude of vorticity

3.3.6 Scalar field over 2D

• Slicing
  
  This is elementary: typically values along the slice direction are extracted, and a simple graph is drawn. The 1D interpolation techniques mentioned earlier can be used to fill in between the extracted samples.
• Contouring
  
  There is a vast literature on contouring which has been a popular 2D visualization technique for geographers and other scientists for many years. A good review paper is by Sabin [61].
• If the data is defined on a regular grid, then there is a simple method (the analogue of marching cubes in 3D) in which linear interpolation is used to estimate the intersection of isolines and grid lines - with some strategy for determining the lines within grid cells. Ambiguities can again occur, so care is needed (see Sutcliffe [62]).
  
  Methods based on linear interpolation will have slope discontinuities as the isolines move between grid cells. For smoother lines, one needs a method based on bicubic interpolation - see Preusser [51].
  
  For scattered data, one approach is to create a triangulation of the data points. Within any triangle, the intersection of the isoline with the edges can be found. Joining the intersections with straight lines gives the isoline of a linear interpolant within the triangle.
  
  An alternative approach for scattered data is to use an interpolant to estimate the underlying field on a grid, and then use a gridded contouring method. It is often useful to enhance the appearance by shading the regions between isolines - indeed the isolines may be removed altogether. As with volume rendering, one needs a colour transfer function to associate colour values with values of the underlying field.

Surface Drawing

It is possible to show a second scalar field by draping a colour shaded contour map over the surface - that is, one scalar variable is represented by height, the other by colour.

Image Display

3.3.7 Scalar field over 1D

3.3.8 AVS

3.3.9 IBM Data Explorer

• Surface Extraction
  
  Slicing: The Slice module extracts an orthogonal slice through a volume of data, and this can be passed to a 2D visualization technique.Slice extracts an n-1 dimensional slice from an n dimensional dataset. The nth dimension is removed, i.e. a Slice from a 2D dataset produces a 1D line, a Slice through a 3D dataset produces a 2D grid (with no third dimension).
  
  Slab does a similar job to Slice except it maintains the nth dimension of the data and allows the slab thickness to be controlled.
  
  MapToPlane allows users to define non-orthogonal slices by controlling both the position of and normal to the plane
  
  Isosurface: The Isosurface module creates an isosurface from a scalar field. The particular algorithm used is an implementation of marching tetrahedra [41].
  
  The gradient vector (for shading) can be generated internally (again how it does it is not specified), or it can be supplied explicitly. The Gradient module will calculate the gradient of the scalar field, and this can feed into the Isosurface for shading.
• Volume Render
  
  The Render module creates a volume rendering of volume data (alternative modules are Display and Image. The data is of the "scalar field" datatype. The algorithm used is specified in [48].
  
  Note that the module can handle a combination of volume data and surfaces.

Vector field over 3D

• Particle Advection, Streamlines, Stream Ribbons
  
  The Streamline module produces streamlines for static vector fields. It traces the flow of a particle released from a defined point. The tracing is done by proceeding step-by-step, each step being in the direction of the vector field at the current point; this direction is found by interpolation from the vector data. The user has control over the step length. (This would appear equivalent to Euler's method.)
  
  There is a sophisticated set of controls. The starting points can be given as a list of points, or as a geometric entity - which could be an isosurface for example. The lines themselves can be drawn as lines, ribbons (by connecting to the Ribbon module), or 3D tubes (by connecting to the Tube module).

• Streaklines
  
  The Streaklines module produces streaklines for time-varying vector fields. This works as follows. Successive vector fields advancing in time are passed to the module. The streaklines are traced step-by-step as for streamlines, but the direction is calculated now by interpolation in space and time.

Scalar field over 2D

• Contouring
  
  The Isosurface module will create isolines from 2D data. A number of threshold values can be specified. The technique used is not described.
  
  The Band module, together with the Autocolor module, will create a visualization with coloured regions denoting ranges of values.
• Surface View
  
  The Rubber Sheet module can be used to create a surface view.
• Image Display
  
  The Autocolor module converts data at each point of a scalar field to a colour.

Scalar field over 1D

There are also some other related modules that can be used in conjunction with the Plot module to produce other 2D representations of data.

• Histogram regroups your data into a specified number of bins. The output of Histogram is a new field which are the bars on the histogram
• Connecting Histogram through AutoColor then Plot produces a colored plot of the data distribution.

• Surface Extraction
  
  Slicing: The Slice module slices a uniform 3D lattice by taking regular samples on a cutting plane, which may be at any orientation. The output is a 2D lattice of the same datatype and number of channels as the input lattice.
  
  The SliceLat module takes a slice through a 3D lattice and outputs the coloured plane as geometry. The lattice cells are intersected with the slice plane, forming polygons. The polygon vertices are coloured by values interpolated from the lattice values.
  
  Other slicing options are provided by Orthoslice, which generates 2D slices which are oriented with the coordinates of the input 3D lattice, and MultiSlice, which gives geometry output from a number of slice planes.
• Isosurface
  
  The IsosurfaceLat module generates an isosurface from a scalar 3D lattice. The algorithm used in earlier releases of IRIS Explorer was based on Marching Cubes, although this has been updated in version 2.2.
  
  The gradient vector (for shading) can be generated internally from the gradient of the scalar field (the Smooth parameter "on"). Alternatively the renderer can generate vertex normals from the geometry of the triangular mesh (the Smooth parameter "off").
  
  The surface may be optionally coloured according to the value of another lattice. The colours used can be controlled by means of a colourmap, which may optionally be passed to the module.
  
  The Contour module generates a set of isosurfaces (i.e. 3D contours) in wireframe. The user has control over the minimum and maximum isolevels, and the number of contours to be calculated. They are generated by calculating contour lines in orthogonal 2D slices of the 3D dataset; the user can control the direction of the slices to be used.
• Volume Render
  
  The VolumeToGeom module The VolumeToGeom module uses a volume rendering algorithm to convert a 3D lattice into a geometry. The method used is the so-called hierarchical splatting algorithm of Laur and Hanrahan [45], which fills the space within the volume using screen-oriented planar shapes (or splats). The algorithm uses a small number of large splats in uniform regions of the volume, and fills more detailed areas with a lot of smaller splats. The user has control over the error tolerance associated with the subdivision of the volume, and also over the size and type of the splat, which gives interactive control over rendering time and quality. The geometry produced may be combined with other geometry in the rendering of the final scene (see section 3.4.7), unlike the VolumeRender module (below) which performs direct volume rendering on the input lattice.
  
  The VolumeRender module performs volume rendering on a 3D byte lattice. It offers the choice between two algorithms offering different speed and quality advantages, so the user can trade off between interactivity and quality. The "Transform" algorithm gives interactive rendering speeds for moderately sized datasets, while the "Slicer" algorithm produces high quality images with longer rendering times. In the latter case, the user has interactive control over the number of slices (and so, the quality of the final image).

Vector field over 3D

• Arrows
  
  The Vectors module displays a 3D vector field for a 1D, 2D or 3D lattice having 1,2 or 3 channels (i.e. vectors having 1,2 or 3 components). Vectors are located at the lattice coordinate locations and point in the direction of the data vector field. The vectors may be optionally coloured using a scalar lattice of the same dimensionality and size. They may be displayed as lines, tubes (cylinders) or arrows (cylinders plus cones).
  
  The VectorGen module is a simplified version of the same module - here, each vector is represented as a bi-coloured line segment.
• Particle Advection, Streamlines, and Streaklines
  
  The Streakline module calculates a streakline through a velocity field. It stops when either the new velocity is 0, or when the streak intersects the bounds of the velocity field. The user has control over how each iteration is calculated and displayed. The full solution can be shown or each iteration as it is calculated. The current particle path is shown in red with the old paths in green.
  
  Particle advection is provided by the module ParticleAdvect which was developed as part of the NCSA Pathfinder project (http://redrock.ncsa.uiuc.edu/PATHFINDER/pathrel2/explorer/ParticleAdvect/ParticleAdvect.html)

Scalar field over 2D

• Contouring
  
  The contour module generates contour lines for a 2D lattice (or a 3D lattice - see above). For lattices with several channels, the user can select the channel to be contoured. The lines are coloured according to an internal colourmap; this can be optionally overridden by passing another colourmap to the module.
• Surface View
  
  The DisplaceLat displaces the coordinates of one input lattice by the data values of the other. The two input lattices can be the same. This can be used to create a surface view of a 2D lattice. The user can control the amount of displacement interactively.
• Image Display
  
  The LatToGeom module creates geometry from a 1D or 2D lattice i.e., it produces lines or sheets, depending on the dimensionality of the input lattice. The user can control whether the geometry is produced as points, lines or (in the case of sheets) polygons. The geometry can be optionally coloured via an input colourmap.
  
  The DisplayImg module displays 2D lattices as images. IRIS Explorer also contains a number of image processing modules, which may be used to filter or modify the image before display. See section 3.4.7, below, for more details.

Scalar field over 1D

• Gnuplot: This is an implementation of gnuplot 3.0. Some additions to standard gnuplot have been made to allow the plot/splot commands to extract data and coordinate information from the input lattice.
• Graph: This module plots an X-Y graph of one or more channels of data from a 1-D lattice. The Draw Mode selector allows the user to select between single channel plotting and drawing of all channels.

IRIS Explorer release 3.0 will also have NAGGraph with more advanced features than Graph.

3.3.11 Khoros

There are numerous operators in the Image Toolbox which are general image processing operators and more information is given in section 3.4.8.

Xprism can also produce line, mesh, coloured contour and shaded 3D plots. There are also facilities to alter annotation and parameters associated with these plots within Xprism.

Scalar field over 1D

• line and scatter plots
• bar charts
• discrete plots

3.3.12 PV-WAVE

• Surface Extraction
  
  Isosurface: The SHADEVOLUME procedure calculates an isosurface from data in cubical cell arrangement. The algorithm used is that described in [40]. It is said to be variation on marching cubes.
  
  The gradient calculation for shading is not described in the manual.
• Volume Render
  
  The VOLREND function in the Advanced Rendering Library creates a volume rendering from data in cubical cell arrangement.

Vector field over 3D

• Arrows
  
  The VECTORFIELD3 function in the Advanced Rendering Library plots vector glyphs at a set of points specified by user. Form of interpolation not specified in the manual.

Scalar field over 2D

• Contouring
  
  The CONTOUR procedure draws a contour plot from a uniform 2D grid, with very sophisticated control over the annotation and presentation. There are two methods: one draws all lines per cell then moves on to next cell; the other traces a line through all cells, then moves to next line. No further algorithmic details are given.
  
  The IMAGE_CONT procedure overlays a contour plot onto an image display. Bilinear interpolation is used in image display.
  
  The SHOW3 procedure overlays image, surface view and contours.
• Surface View
  
  The SURFACE procedure draws a surface view, with sophisticated control over the annotation and presentation.
• Image Display
  
  See contouring above.

Scalar field over 1D

• 2D line
• 2D scatter
• 2D histogram

Generated with CERN WebMaker

Graphics     Multimedia      Virtual Environments      Visualisation      Contents