geometric modelling

1. Introduction

Geometric modelling is the process of representing geometrical objects - points, lines, triangles, polynomial curves, and so forth - and their relative orientations. Geometric modelling has applications in the fields of computer animation, computer graphics, computer vision, robotics, CAD/CAM, fluid dynamics, and structural analysis.

(One caveat: I'm a computer graphics person, so this writeup will have a CG bias. My hope, however, is that this writeup will be useful for non-CG people as well. /msg me for any corrections and/or suggestions.)

Recently, almost all geometric modelling has been done with computers. This process of modelling geometry with computers is called computer aided geometric design, or CAGD for short. In the computer animation industry, this is also called 3D modelling.

Absolutely essential to the digital representation of geometry within computers is the theory of coordinate geometry and the related theory of linear algebra. During the modelling process, all geometrical information is represented within the computer by the numbers that describe them. For example:

• A point could be represented by its x, y, and z cartesian coordinates.
• A triangle could be represented by its three vertices.
• A relative rotation between two triangles could be described by a rotation matrix.

There are two main ideas in geometric modelling:

1. Primitives - which are simple shapes like points, and lines.
2. Composition - putting several primitives together to form complex objects.

Each of the two ideas will be explored in the following sections.

2. Primitives

There are several types of primitives used in geometric modelling. The most basic of these is the 3D point. As noted above, points are often represented by their (x, y, z) cartesian coordinates. In linear algebraic terms, those coordinates can be considered as a vector of length 3. Often, an additional coordinate, w, is added to create what is called the homogenous coordinates of the point. Working with homogenous coordinates simplifies many operations performed on points.

Almost all modelling software includes support for lines, triangles, cubes, and spheres. Some even have support for general quadric surfaces. Quadratic surfaces are usually represented as implicit surfaces. Fluid dynamics simulation is usually done using implicit surfaces.

More complex primitives are usually needed. Primitives that represent curved arcs, such as Bezier curves and B-splines, are often supported using the general framework of Non-Uniform Rational B-Splines (NURBs, for short). These methods were first invented by automotive engineers trying to model car bodies. Triangle meshes are often used to approximate smooth surfaces. Curved surfaces are represented directly using tensor product surfaces, total degree surfaces, and more recently (as popularized in the animated short film Geri's Game), subdvision surfaces. These primitives are examples of parametric models.

Three dimensional objects can also be represented directly, without the need for a representation of its surface. Tetrahedral meshes are often used by the mechanical engineers using finite-element analyses. Octtrees and voxel arrays are often used by radiologists to represent the results of CAT scans.

Sometimes even more esoteric methods are needed to create realistic-looking geometry. Fractals are used for representing mountain ranges (see fractal mountains), and L-systems are used for representing plant life. Since those methods are more properly described in the field of procedural modelling, I won't go into them here.

3. Composition

Now that we have the primitives, we need to put them together to form complex models like robots and spaceships. To do this, we need to have a way of (mathematically) specifying the orientations of primitives with respect to each other. Primitives are often represented as lists of 3D points and they are moved using geometrical transformations. Geometrical transformations include those that rotate, translate, reflect, scale, and shear. These geometrical transformations can be represented using matrix multiplications.

Often, complex models have a hierarchical structure. For example, a model of a person can be composed of a head, a torso, two arms and two legs. The head in turn could be composed of a mouth, two eyes, a nose, two ears and (possibly) hair. An arm could be composed of a forearm, an elbow, a wrist, and a hand. A hand could be composed of a palm and fingers, and so forth.

This hierarchical structure can easily be represented using a graph theoretical object called a tree. Primitives are inserted into this tree with appropriate geometrical transformations that relate the primitive to its parent node. More often, a part (say, an arm) could be reused, with the appropriate geometrical transform (reflection for the case of the arm), on two different parts of the tree. In this case, the structure is a directed acyclic graph.