MSRI Graphics School - Lecture 5 on PostScript

More about ps3d

I review here in more detail some of the features of drawing in 3D with the PostScript package ps3d.inc.

Visibility of a face

In 3D, what the eye usually perceives are surfaces. The standard way to simulate this using ps3d is by building surfaces from flat plates. Each one will have an array of points lying in a plane as well as an outward direction. In practice, I find that the simplest way to represent such a plate is as a pair - i.e. an array - consisting of an array of 3D points plus an affine function f(x) = ax + by + cz + d such that the outside of the plate is precisely the half-space f(x) > 0. Thus in the following program the two faces being drawn have the same polygon [ [0 0] [1 0] [1 1] [0 1] ] but different normal functions z and -z specifying its opposite faces. In order to make this apparent, I have added to each face an RGB array.

Shading

The point of the 3D programming we are doing here is to help the eye perceive various features of a diagram, not necessarily a realistic image. Nonetheless simple features can add enormously to the effectiveness of a diagram, and one of the more effective is shading. One sets up a light source, usually in a certain direction, and then colors faces that are oriented towards the light source lighter than those facing away from it. Darkness thus serves as a cue to the direction a face is pointing towards. Diffuse shading is often all that's needed (rather than shiny specualr reflections). In this scheme, the darkness of a face depends only on the angle between the outward normal from the face and the direction of the light source, or more precisely on its cosine c, which varies between -1 (dark) and +1 (bright). We obtain a suitable darkness factor by applying some function in turn to this number c, again obtaining a number between -1 and +1. In ps3d are provided a family of functions (Bernstein polynomials) parametrized by arrays of numbers also lying between 0 and 1 (the control values of the polynomial). A good choice for good contrast with diffuse backlighting is [ 0.3 0.3 1 1].

Complicated displays

The relatively simple scheme described above (taking into account the orientation of each face with respect to the eye and to a light source) will work to display a single convex object reasonably well, but for several objects or for even a single non-convex object something more complicated is definitely necessary. This is illustrated by a rotating pair of cubes.

As the cubes rotate, one obscures the other. One of the cubes might lie behind the other, and it must be drawn first, so that drawing the second will paint over it. The real problem is the one which is in back at one point is in front at another, so the determination of back and front must be decided dynamically. This is done by inserting a plane between the two cubes, and deciding in terms of the virtual eye which cube lies on the side of that plane away from the eye, and which on the same side. In the following picture, the cube in the white region would be drawn first, then that in the gray region. In general, something yet more complicated has to be done. In the following picture, there is no way to order the three plates so that they are drawn correctly. In this case, the plates must be split into smaller fragments to make back-to-front drawing possible. The required fragmentation is shown by lines in the figure above. This is part of a rather complicated scheme called binary space partitioning.

Binary space partitioning

This is a common scheme to draw surfaces in 3D, one used when parts of a figure cannot be drawn directly into pixels, as with PostScript. It starts with a collection of oriented faces, splits them up as necessary and allocates them to regions of space in such a way that for any given rigid transformation of the collection it is easy to decide how to order them back to front with respect to a possible eye location. This is implemented in the file bsp.inc. The principal procedures defined there are bsp-tree, which takes as single argumenta n array of faces and returns a tree whose leaves are faces, and traverse, whose arguments are a tree returned by bsp-tree and a procedure to be applied to each leaf. How to use these is illustrated for the case of the triad above in the file triad.eps.