Modelling

The criteria for a good modelling scheme are

• scope and uniqueness, and
• stability and sensitivity.

The two areas where extensive modelling has occurred are CAD and computer vision.

The various models used in CAD are

1.

wire frame,

2.

CSG, or Constructive Solid Geometry,

3.

spatial occupancy techniques, and

4.

surface boundary representations, for example polygons, B-splines, or Bezier surfaces etc.

The first approach, namely that of representing objects by a wire frame, has problems of non-uniqueness, since several objects may correspond to the same wire frame. For example, the classic Necker cube may correspond to a box viewed from above, or one viewed from below.

In the second approach, that of CSG, we construct a binary tree corresponding to each object. The leaves are solid primitives such as cylinders, cones, spheres, cubes, etc. Solids are then represented as composition, via the set operations of union, intersection and set differencing, of these primitives, which may have undergone rigid motions. Thus, the primitives may be arbitrarily placed in space, and also arbitrarily scaled.

Some examples of objects constructed from a cylindrical solid primitive are given below in figure 2.

 

Figure: Object representation via constructive solid geometry.

The CSG representation scheme works under the assumption that the objects to be modelled are regular sets, and the combining operators are regularized versions of set union, intersection and difference. A set X is regular if $X = \overline{X^o}$, that is, X is the closure of its interior. This prevents the set from having isolated points or dangling boundary points. It is a natural formalization of set operations that preserve dimension, that is the resulting set must have the same dimension everywhere.

Spatial occupancy schemes use either voxels (volume elements) or an octree, which is a three dimensional version of a quadtree. In a voxel representation, an object is built up from a 3D binary array, where elements have the value 1 if occupied, otherwise 0. The resolution is uniform throughout the representation. An octree representation, on the other hand, has a varying resolution across the model, depending on the shape of the object. Octrees are most easily illustrated with their 2D equivalents, quadtrees, which are a useful way of encoding a spatial occupancy array.

Imagine a pyramid made from the base level image, where each ascending level is defined by deresolving the image by a factor of 2. Each pixel in a level above the base is black or white if all its corresponding pixels in the lower level are black or white, otherwise it is grey. This is illustrated in figure 3 below.

 

Figure: Spatial occupancy representation via a quadtree.