High-resolution Computer Graphics Using Pascal

Computer graphics devices come in all shapes and sizes: storage tubes, raster devices, vector refresh displays, flat-bed plotters etc., which is why in recent years so much effort has been put into graphics software standards (such as G.K.S. (Hopgood et al., 1983)) as well as into the portability of graphics packages (GINO, CalComp etc.). This book will concentrate on the techniques of modelling and rendering (that is, drawing, colouring, shading etc.) two-dimensional and three-dimensional objects, which surprisingly require only a small part of the above systems. Rather than restrict ourselves to one software system, and in order to make this book relevant to as many different graphics devices as possible, we will identify a general model for a graphics device together with a few (nine) elementary routines (primitives) for manipulating that model. From the outset it must be realised that we are using the word ‘primitive’ in the literal sense of describing the basic level at which the programs in this book communicate with graphics devices; the word has different meanings in other graphics environments, such as G.K.S. The Pascal programs that follow will use only these primitives for drawing on this basic model (apart from a few very exceptional cases). Since even the most complex programs given in this book interface with the model device through relatively few primitive routines, the graphics package we create is readily portable.

The underlying mathematical theory is important in any branch of computer programming but particularly so in graphics. The majority of techniques presented in this book rely entirely upon a solid background of co-ordinate and vector geometry and it is imperative that the reader gains some grounding in the methods involved before progressing to the later applications.

In all pictures drawn so far the co-ordinate origin, axes and scale of the window have been identified with the ABSOLUTE axes defined for two-dimensional space. This is not the general case. Usually we want the window to move around in space, not necessarily being anchored to this arbitrary but fixed co-ordinate system. We must, therefore, consider what happens to the definition of an object, be it a point, line or curve, when the co-ordinate system is changed. As we have seen in previous chapters, the drawing of any object in computer graphics may ultimately be considered in terms of specifying and joining groups of points, and so all that is necessary is to discover what happens to the co-ordinate representation of a point with a change of co-ordinate system.

The methods introduced so far enable us to create and draw a simple representation of any two-dimensional scene consisting of a set of vertices, lines and polygonal facets. In this chapter we shall consider a number of techniques which may be used for more complex pictures of two-dimensional scenes along with some which we will need when developing algorithms to deal with three-dimensional solid models. Naturally these routines must be merged into the complete program at positions that ensure a valid scope.

Before we lead on to a study of the graphical display of objects in three-dimensional space, we first have to come to terms with the three-dimensional Cartesian co-ordinate geometry and introduce some useful procedures for manipulating objects in three-dimensional space. (For further reading we recommend books by Cohn (1961) and McCrae (1953)). As in two-dimensional space, we arbitrarily fix a point in the space, named the co-ordinate origin (origin for short). We then imagine three mutually perpendicular lines through this point, each line extending to infinity in both directions. These are the x-axis, y-axis and z-axis. Each axis is thought to have a positive and a negative half, both starting at the origin — that is, distances measured from the origin along the axis are positive on one side and negative on the other. We may think of the x and y axes in a similar way to two-dimensional space, both lying on the page of this book say, the positive x-axis horizontal and to the right of the origin, and the positive y-axis vertical and above the origin. This just leaves the position of the z-axis: it has to be perpendicular to the page (since it is perpendicular to both x and y axes). The positive z-axis can be into the page (the so-called left-handed triad of axes) or out of the page (the right-handed triad). You can realise the difference on your hands. On either hand, hold the thumb, index finger and middle finger at right angles to one another with the middle finger perpendicular to the palm of your hand: the thumb may be taken as the positive x-axis, the index finger as the positive y-axis and the middle finger the positive z-axis. See figure 6.1.

Transformations of co-ordinate axes in two-dimensional space were introduced in chapter 4. An extension to three-dimensional systems is an essential step before we are able to proceed to projections of three-dimensional space onto the necessarily two-dimensional graphics viewport. As in the lower dimension, there are three basic transformations: translation of origin, change of scale and axes rotation; we will ignore all other transformations such as shear. Since we have already introduced the idea of matrix representation of transformations in two dimensions, we shall move directly to a similar representation of three-dimensional transformations. It should once more be noted that certain graphics devices will have these operations in hardware. The techniques are, nevertheless, very important so a full description is given. Again the square matrices representing the transformations will be one dimension greater than the space — that is, 4 × 4 — and a general point in space will be represented, by a column vector, relative to some triad of co-ordinate axes We start with our library of routines used for creating the matrices representing three-dimensional transformations, and declaring them globally in listing 7.1. We also declare TYPE matrix4×4 to hold 4 by 4 matrices. Place the routines from listing 7.1 following those of listing 1.3 in your combined program.

We now address the problem of representing views of three-dimensional scenes on the graphics viewport. There are three major stages. In chapter 7 we saw how to construct a model of a three-dimensional scene in ACTUAL position. In this chapter we consider observing the scene and the display of a corresponding view. The display of the scene is co-ordinated by routine drawit which may take a number of different forms, depending on the type of image required (line drawing, colour etc). This routine will be called at the end of the scene routine after the construction of the model and the positioning of the observer. We shall deal with the observer before going on to consider the drawit display.

The previous chapter introduced our method for constructing and drawing scenes: a routine scene is used to construct data about a three-dimensional scene via construction routines, some input from file. Then the vertices are transformed into the OBSERVED position, and the routine drawit is called to display the scene. In the following chapters we will give a number of different types of drawit, project and facet display routines, dependent only on the projection and type of picture you require: line drawing, colour with/without shading, shadows etc. All the reader need do is create the relevant scene and construction routines and call the correct drawit routine.

By now you should be aware that there are many different types of hidden line and/or surface algorithm (Sutherland et al., 1974). One variety involves a rectangular array representing the totality of pixels on the screen. We imagine rays of light entering the eye through each of the pixels on the screen. These rays naturally pass through objects in our scene and we can note the co-ordinates of these points of intersection. The array will hold the ‘z co-ordinate’ (initially minus infinity) of the nearest point of intersection. So we build up a picture by adding new objects, finding where the rays cut the object, and changing the array values (and the pixel colour on the screen) whenever the latest point of intersection is nearer the eye than the corresponding value stored in the array. This technique is very useful if we wish to shade-in areas in subtly differing tones of a given colour (chapter 15). It does, however, have enormous storage requirements and needs a very powerful computer. In this chapter we give another type of general algorithm more suitable for use with small computer systems and raster-scan display devices, which works on the ‘back-to-front’ principle mentioned earlier.

In chapter 5 we considered the clipping of lines and facets in two-dimensional space, determining which parts lay within a rectangular window with dimensions horiz × vert. These methods are also sufficient for dealing with orthographic projections of three-dimensional scenes since the whole of space can be projected onto the view plane and clipped in two dimensions. Dealing with perspective projections is rather more complex. Once again we assume that we have a view plane some distance from the eye along the negative z-axis of the right-handed OBSERVER system. A rectangular (horiz × vert) window on this plane is to be identified with the graphics viewport. In previous chapters we have assumed that the eye is positioned in such a way that each vertex has a strictly negative OBSERVED z co-ordinate. This ensures that every vertex can be projected onto the view plane by a standard perspective projection as defined in chapter 11, whence two-dimensional clipping ascertains which parts of the image lie totally within the window. Suppose, however, that we wish to depict a scene as viewed from a position within the model, such as a point lying in a landscape with a large ground plane. Clearly, parts of the model will lie behind the eye and consequently cannot be projected onto the view plane. Such problems cannot be resolved by two-dimensional clipping and so extended methods must be developed. Three-dimensional clipping must determine which parts of a line or facet can be projected onto the window before the projection occurs.

In chapter 10 we introduced the routine facetfill to produce the viewport representation of a facet. Up to now this routine has consisted of a simple area-fill using a logical colour prescribed in the data construction routines. We can do much more than this! The realism of the images we produce is greatly enhanced by the use of shading. We take advantage of the colour display of the graphics device to model the different appearances of surfaces depending on the light striking them. Plates III, XIII and IX show pictures produced using the shading techniques introduced in this chapter.

A facet which obscures all or part of another facet from exposure to a light source is said to cast a shadow onto this other facet. A shadow cast by a convex polygonal facet, J, onto another convex polygonal facet, I, is also a convex polygon which may be considered to lie on the surface of facet I. We call this polygon a shadow polygon. The amount of light reflected from a point in shadow was discussed in chapter 15: in this chapter we turn our attention to the finding and displaying of shadow polygons. We shall describe an algorithm which may be used to achieve this aim. This algorithm is merely an example to show how the problem can be tackled. There are many alternative solutions (Crow, 1977). The criterion for finding shadows is very similar to that for finding hidden surfaces and most hidden surface algorithms can be adapted accordingly. The method which we describe here is based on the general hidden surface algorithm of chapter 13.

In this chapter we shall discuss an exciting recent development in the representation of objects in three-dimensional space. We take a totally different approach to the definition of a scene: instead of approximating surfaces with a polygonal mesh, we define them as combinations of primitive objects. Each primitive object is mathematically defined in terms of an analytic function: we have already introduced this idea in the analytic representation of surfaces in chapter 6. This approach allows a very simple definition of many scenes, but the ease of definition has to be paid for with a large increase in processing overheads, although not necessarily in program complexity. To illustrate these ideas we look at two implementations. The first, the quad-tree (Sidhu and Boute, 1972; Tanimoto, 1977; Hunter and Steiglitz, 1979; Woodwark, 1984), will be used to draw simple molecular models composed of a grouping of spheres of arbitrary radius and position. A program, using listings 1.1, 1.3, 3.3, 7.1 and 8.1 linked to the draw_ a_picture routine of listing 17.1 is used to illustrate it. Also required are dot3 (listing 6.1), insource (listing 15.1), findlogicalcolour and colourtable (listing 15.10), and cshade (listing 15.9). Secondly there is the oct-tree method (Clark, 1976; Meagher, 1982): we do not give a program but outline the method and also describe the construction of a binary tree defining a scene as the union, intersection and complement of various primitives. (Such a description can also be used with ray-tracing and the quad-tree method.)

Produce a program package that can draw Data Diagrams. It must include listings for the construction of Bar-Charts and Histograms, Pie-Charts. and both Discrete and Continuous graphs. An example of a discrete graph is given in figure 18.1. Note you must be able to add text to your diagrams, and also have a facility for drawing labelled axes as well as the option of drawing in various graphics modes (XOR etc.). See Angell (1985) for an implementation of data diagrams on the IBM Personal Computer.