Copyright (c) Susan Laflin. August 1999.

These methods, which are also known as "Spatial Occupancy Methods" or "voxel methods", are based on a very simple concept. We assume that either the whole of three-dimensional space or a finite volume within it is divided into "cells" or "voxels" (volume-cells). Each cell is classed as either "occupied" (full) or "empty" in the simple, binary case. In more complex cases we might have a range of values indicating that the cell, if occupied, may contain one of a range of different substances, each substance being allocated a different numerical value.

If the array of voxels is stored as a three-dimensional array within the computer, then either the method is restricted to a small mesh and so has very poor resolution and large errors in defining the shape of the object, or it makes very large demands on the storage of the computer and soon runs out of space. Note that when defining the object, those cells that have more than half their volume empty are defined as "empty" while the other partially filled ones are defined as "occupied". The figure shows a slice across such an object, indicating in two-dimensions which squares are "occupied" and which are "empty". The occupied squares are indicated by shading in the diagram and would have the value "1" in the computer while the empty squares would have the value "0".

Profile and Cells.

Since each voxel may be represented by one bit, an obvious form of compression is to pack the data along one axis into whatever length of computer word your machine uses. This requires some form of unpacking when you wish to examine an area of the data.

Other compression techniques make use of oct-tree coding or run-length encoding. In all these cases, the resolution of the data usually remains lower than we would like and some means of interpolation is needed to recover the smooth shape of the object. The project by Steven Bright, undertaken during the summer of 1985, studies these problems and finds solutions for a specific problem. (This was later written up and published in Computer Graphics Forum volume 5 Number 2. I can lend you a copy if you wish to read this.) In his particular case, he finds a form of run-length encoding which appears to be more efficient than the oct-tree method. This is not a usual result.

The TIPS-1 modeller developed at Hokkaido university uses this approach. Most other modellers use a combination of methods, with the voxel approach used to estimate volumes and weights of the objects.