Structural Decomposition

"Divide and Conquer" is a commonly used technique for attacking design problems. It is particularly useful when modeling. If an object can be structurally decomposed into logical parts, then creating each of those parts becomes a somewhat simpler design problem. Constructing the complex object now requires solving each of these simpler problems. Additionally, modification of the objects becomes much easier as the code becomes more modular.

Animals, plants, machines, and architecture are a few examples of frequently modeled items that can be decomposed into component parts.

When working with a procedural system, a logical breakdown exploiting similarities in sub-objects is desirable. If any positional or geometric regularities exist, the computer can be used to save a great deal of tedious work. All of the above examples have components that are duplicated in their structure:

Animals: limbs, hair, scales, digits...
Plants: leaves, fruits, branches, flowers...
Machines: Buttons, wheels, slots, wires...
Architecture: Doors, windows, supports, walls...

Copying redundant components is frequently referred to as "instancing". We will discuss more examples of this when we get to iteration.

Hierarchical Construction

As an example, let's examine a simple head. It can be broken down into a skull, neck, nose, mouth, and eyes. We now have much simpler objects to model. We will break the eyes down even further. Notice we can take advantage of some redundancy. We will only have to model one eye, but we will use it twice. Here are the simple part definitions. Once defined, these parts can be assembled hierarchically.

To build the eye, we assemble the three components using separators and transform gops:

(define (eye)
  (separator

   (separator
    ; lid-rotation
    (rotate 0 x-axis)
    (lid)
    )
   ; eye-rotation
   (rotate 10 (vec3 1 0 0))
   (rotate 15 (vec3 0 1 0))
   (eye-ball)

   ; pupil-translation
   (translate (vec3 0 0 .155))
   (pupil)
   )
  )

Notice three things:

The eye lid, along with its rotation, have been isolated with a separator. The lid rotation will only affect the lid. The eye ball and pupil are not rotated if the lid opens and closes.
There are two rotations before the eyeball, so that we can make it rotate vertically, as well as horizontally. The rotations are not placed inside a separator with the eyeball, because we want them to also be applied to the pupil.
The pupil translation only affects the pupil, since transform gops only affect gprims occuring after them.

When objects are created from multiple sub-objects, and we want transforms to certain parts to affect other parts, we usually refer to this as a hierarchy. For example, if the head below turns, we would like the eyes to stay to attached to the proper place on the face.

(define (head)
  (separator

   (neck)

   ; neck-transform
   (translate (vec3 0 1 .25))
   (rotate 0 (vec3 0 1 0))
   (skull)

   ; nose
   (separator
    ; nose-translation
    (translate (vec3 0 -.35 .95))
    (nose)
    )

   ; left eye
   (separator
    ; left-eye-translation
    (translate (vec3 .25 0 .9))
    (eye)
    )

   ; right eye
   (separator
    ; right-eye-translation
    (translate (vec3 -.25 0 .9))
    (eye)
    )

   ; mouth
   (separator
    ; mouth-translation
    (translate (vec3 0 -.5 .9))
    (mouth)
    )
   )
  )

Notice how for each part of the head, the transformation that places the part is localized to just affect that part, using a separator.

Joint Chains

Hierarchies with multiple levels of joints quickly become confusing.

Drawing each part in a chain of joints requires a series of transformations. After the first sub-object is drawn, there must be a translation from the local coordinate system origin of the first part to the joint position. The joint is rotated, followed by a translation to the local origin of the next part.

After the next part is drawn the series is repeated: Translate-to-joint, Rotate, Translate-to-local-origin, Draw. Here is an example of an arm capable of bending at the wrist and elbow.

Source Code

The concept of "parent" and "child" parts is central to creating such hierarchies. The bottom arm segment is called the "root". It is fixed in the sense that no joint rotation will move it. Bending the elbow joint moves the upper arm and wrist. When talking about the elbow joint, we refer to the bottom arm segment as the "parent" and the upper arm segment as the "child". For similar reasons, when we speak of the wrist, the upper arm segment is the parent (as it is stationary when bending the wrist), and the hand is the child.

Return to Schedule Information

mrl