- Chapter 18 Graphics Kernel
- 1 Graphics Kernel
- 2 Graphical Representation
- 3 Graphical Storage
- 4 Graphical Manipulation
- 5 Classes Form and Bitmap
- 6 Spatial Reference
- 7 Line Drawing
- 8 Text Display
- 9 Notes
Object Magnitude Character Date Time Number Float Fraction Integer LargeNegativeInteger LargePositiveInteger SmallInteger LookupKey Association Link Process Collection SequenceableCollection LinkedList Semaphore ArrayedCollection Array Bitmap*** DisplayBitmap*** RunArray String Symbol Text ByteArray Interval OrderedCollection SortedCollection Bag MappedCollection Set Dictionary IdentifyDictionary Stream PositionableStream ReadStream WriteStream ReadWriteStream ExternalStream FileStream Random File FileDirectory FilePage UndefinedObject Boolean False True ProcessorScheduler Delay SharedQueue Behavior ClassDescription Class MetaClass Point*** Rectangle*** BitBit*** CharacterScanner*** Pen DisplayObject DisplayMedium Form Cursor DisplayScreen InfiniteForm OpaqueForm Path Arc Circle Curve Line LinearFit Spline
Figure 18.1 shows a view of the display screen for a Smalltalk-80 system. It illustrates the wide range of graphical idiom available to the system. Rectangular areas of arbitrary size are filled with white, black, and halftone patterns. Text, in various typefaces, is placed on the screen from stored images of the individual characters. Halftone shades are "brushed" by the user to create freehand paintings. Moreover, although not shown on the printed page, images on the display can be moved or sequenced in time to provide animation.
The example interaction with the system given in the previous chapter illustrated some of the ways in which objects can be observed and manipulated graphically. Meaningful presentation of objects in the system demands maximum control over the display medium. One approach that provides the necessary flexibility is to allow the brightness of every discernible point in the displayed image to be independently controlled. An implementation of this approach is a contiguous block of storage in which the setting of each bit is mapped into the illumination of a corresponding picture element, or pixel, when displaying the image. The block of storage is referred to as a bitmap. This type of display is called a bitmapped display. The simplest form of bitmap allows only two brightness levels, white and black, corresponding to the stored bit values 0 or 1 respectively. The Smalltalk-80 graphics system is built around this model of a display medium.
Images are represented by instances of class Form. A Form has height and width, and a bitmap, which indicates the white and black regions of the particular image being represented. Consider, for example, the man-shape in Figure 18.2. The height of the Form is 40, its width is 14, and its appearance is described by the pattern of ones and zeros (shown as light and dark squares) in its bitmap. The height and width of the Form serve to impose the appropriate two-dimensional ordering on the otherwise unstructured data in the bitmap. We shall return to the representation of Forms in more detail later in this chapter.
New Forms are created by combining several Forms. The freehand drawing in the center of Figure 18.1 is an example of a large Form that was created by combining and repeating several Forms that serve as "paint brushes" in a Smalltalk-80 application system. The text in Figure 18.1 is a structured combination of Forms representing characters.
A Form can be presented to the display hardware as a buffer in memory of the actual data or of the image to be shown on a display screen. Since the interface to the hardware is through a Form, there is no difference between combining images internally and displaying them on the screen. Animation can be displayed smoothly by using one Form as the display Form while the next image to be displayed is prepared in a second Form. As each image is completed, the two Forms exchange roles, causing the new image to be displayed and making the Form with the old image available for building yet another image in the sequence.
The Forms used as buffers for data to be shown on the display screen are instances of class DisplayScreen, a subclass of Form. Contiguous storage of bits is provided by instances of class Bitmap. DisplayScreen's bitmap is an instance of DisplayBitmap, a subclass of Bitmap. DisplayScreen and DisplayBitmap provide protocol specific to the actual hardware and to the fact that the Form represents the whole display screen rather than potential parts of it.
A basic operation on Forms, referred to as BitBlt, supports a wide range of graphical presentation. All text and graphic objects in the system are created and modified using this single graphical operation. The name "BitBlt" derives from the generalization of data transfer to arbitrary bit locations, or pixels. One of the first computers on which a Smalltalk system was implemented had an instruction called BLT for block transfer of 16-bit words, and so "bit block transfer" became known as BitBlt.
Operations are represented by messages to objects. So BitBlt could have been implemented with a message to class Form. However, because BitBlts are fairly complicated operations to specify, they are represented by objects. These objects are instances of the class named BitBlt. The basic operation is performed by sending an appropriately initialized instance of BitBlt the message copyBits. The BitBlt operation is intentionally a very general operation, although most applications of it are graphically simple, such as "move this rectangle of pixels from here to there."
Figure 18.3 illustrates the process of copying a character of text into a region on the display. This operation will serve to illustrate most of the characteristics of BitBlt that are introduced in the remainder of this section.
Source and Destination Forms
The BitBlt copy operation involves two Forms, a source and a destination. The source in the example in Figure 18.3 is a font containing a set of character glyphs depicted in some uniform style and scale, and packed together horizontally. The destination in the example is assumed to be a Form that is used as the display buffer. Pixels are copied out of the source and stored into the destination. The width and height of the transfer correspond to the character size. The source x and y coordinates give the character's location in the font, and the destination coordinates specify the position on the display where its copy will appear.
BitBlt includes in its specification a rectangular area which limits the region of the destination that can be affected by its operation, independent of the other destination parameters. We call this area the clipping rectangle. Often it is desirable to display a partial window onto larger scenes, and the clipping rectangle ensures that all picture elements fall inside the bounds of the window. By its inclusion in the BitBlt primitive, the clipping function can be done efficiently and in one place, rather than being replicated in all application programs.
Figure 18.4 illustrates the result of imposing a clipping rectangle on the example of Figure 18.3. Pixels that would have been placed outside the clipping rectangle (the left edge of the "N" and half of the word "the") have not been transferred. Had there been other characters that fell above or below this rectangle, they would have been similarly clipped.
Often it is desirable to fill areas with a regular pattern that provides the effect of gray tone or texture. To this end, BitBlt provides for reference to a third Form containing the desired pattern. This Form is referred to as a halftone or mask. It is restricted to have height and width of 16. When halftoning is specified, this pattern is effectively repeated every 16 units horizontally and vertically over the entire destination.
There are four "modes" of supplying pixels from the source and halftone controlled by supplying nil for the source form or the halftone form:
- no source, no halftone (supplies solid black)
- halftone only (supplies halftone pattern)
- source only (supplies source pixels)
- source AND halftone (supplies source bits masked by halftone pattern)
Figure 18.5 illustrates the effect of these four modes with the same source and destination and a regular gray halftone.
The examples above have all determined the new contents of the destination based only on the source and halftone, storing directly into the destination. The previous contents of the destination can also be taken into account in determining the result of the copying.
There are 16 possible rules for combining each source element S with the corresponding destination element D to produce the new destination element D'. Each rule must specify a white or black result for each of the four cases of source being white or black, and destination being white or black.
Figure 18.6 shows a box with four cells corresponding to the four cases encountered when combining source S and destination D. For instance, the cell numbered 2 corresponds to the case where the source was black and the destination was white. By appropriately filling the four cells with white or black, the box can be made to depict any combination rule. The numbers in the four cells map the rule as depicted graphically to the integer value which selects that rule. For example, to specify that the result should be black wherever the source or destination (or both) was black, we would blacken the cells numbered 4, 2, and 1. The associated integer for specifying that rule is the sum of the blackened cell numbers, or 4 + 2 + 1 = 7.
Figure 18.7 illustrates four common combination rules graphically. In addition, each is described by a combination diagram, its integer rule number, and the actual logical function being applied. The full set of 16 combination rules appears later in the chapter as part of the detailed simulation of BitBlt.
Classes Form and Bitmap
Figure 18.8 shows further information about the Form shown in Figure 18.2. The width and height are stored as Integers. The actual pixels are stored in a separate object which is an instance of class Bitmap. Bitmaps have almost no protocol, since their sole purpose is to provide storage for Forms. They also have no intrinsic width and height, apart from that laid on by their owning Form, although the figure retains this structure for clarity. It can be seen that space has been provided in the Bitmap for a width of 16; this is a manifestation of the hardware organization of storage and processing into 16-bit words. Bitmaps are allocated with an integral number of words for each row of pixels. This row size is referred to as the raster size. The integral word constraint on raster size facilitates movement from one row to the next within the operation of BitBlt, and during the scanning of the display screen by the hardware. While this division of memory into words is significant at the primitive level, it is encapsulated in such a way that none of the higher-level graphical components in the system need consider the issue of word size.
Two classes, Rectangle and Point, are used extensively in working with stored images. A Point contains x and y coordinate values and is used to refer to a pixel location in a Form; a Rectangle contains two Points--the top left corner and the bottom right corner--and is used to define a rectangular area of a Form.
Class Form includes protocol for managing a rectangular pattern of black and white dots. The bitmap of a Form can be (re)set by copying bits from a rectangular area of the display screen (fromDisplay:), and the extent and offset of the Form can be set (extent:, extent:offset:). Two messages provide access to the individual bits (valueAt: and valueAt:put:). Constants for modes and masks are known to class Form and can be obtained by the following class messages of Form.
|fromDisplay: aRectangle||Copy the bits from the display screen within the boundaries defined by the argument, aRectangle, into the receiver's bitmap.|
|extent: aPoint||Set the width and height of the receiver to be the coordinates of the argument, aPoint.|
|extent: extentPoint offset: offsetPoint||Set the width and height of the receiver to be the coordinates of the argument, extentPoint, and the offset to be offsetPoint.|
|valueAt: aPoint||Answer the bit, 0 or 1, at location aPoint within the receiver's bitmap.|
|valueAt: aPoint put: bitCode||Set the bit at location aPoint within the receiver's bitmap to be bitCode, either 0 or 1.|
|Form instance protocol|
|fromDisplay: aRectangle||Answer a new Form whose bits are copied from the display screen within the boundaries defined by the argument, aRectangle, into the receiver's bitmap.|
|erase||Answer the Integer denoting mode erase.|
|over||Answer the Integer denoting mode over.|
|reverse||Answer the Integer denoting mode reverse.|
|under||Answer the Integer denoting mode under.|
|black||Answer the Form denoting a black mask.|
|darkGray||Answer the Form denoting a dark gray mask.|
|gray||Answer the Form denoting a gray mask.|
|lightGray||Answer the Form denoting a light gray mask.|
|veryLightGray||Answer the Form denoting a very light gray mask.|
|white||Answer the Form denoting a white mask.|
|From class protocol|
Since the images represented by Forms are inherently two-dimensional, image manipulation is simplified by providing objects representing two-dimensional locations and areas. Instances of class Point represent locations and instances of class Rectangle represent areas.
A Point represents an x-y pair of numbers usually designating a pixel in a Form. Points refer to pixel locations relative to the top left corner of a Form (or other point of reference). By convention, x increases to the right and y down, consistent with the layout of text on a page and the direction of display scanning. This is in contrast to the "right-handed" coordinate system in which y increases in the upward direction.
A Point is typically created using the binary message @ to a Number. For example, the result of evaluating the expression
200 @ 150
is a Point with x and y coordinates 200 and 150. In addition, the class protocol of Point supports the instance creation message x: xInteger y: yInteger.
Point x: 200 y: 150
represents the same location as 200@150. The instance protocol for Point supports accessing messages and messages for comparing two Points.
|x||Answer the x coordinate.|
|x: aNumber||Set the x coordinate to be the argument, aNumber.|
|y||Answer the y coordinate.|
|y: aNumber||Set the y coordinate to be the argument, aNumber.|
|< aPoint||Answer whether the receiver is above and to the left of the argument, aPoint.|
|< = aPoint||Answer whether the receiver is neither below nor to the right of the argument, aPoint.|
|> aPoint||Answer whether the receiver is below and to the right of the argument, aPoint.|
|> = aPoint||Answer whether the receiver is neither above nor to the left of the argument, aPoint.|
|max: aPoint||Answer the lower right corner of the rectangle uniquely defined by the receiver and the argument, aPoint.|
|min: aPoint||Answer the upper left corner of the rectangle uniquely defined by the receiver and the argument, aPoint.|
|Point instance protocol|
With respect to the coordinates labeled in Figure 18.9, example expressions are
|(45@230) < (175@270)||true|
|(45@230) < (175@200)||false|
|(45@230) > (175@200)||false|
|(175@270) > (45@230)||true|
|(45@230) max: (175@200)||175@230|
|(45@230) min: (175@200)||45@200|
Arithmetic can be carried out between two Points or between a Point and a Number (a scaling factor). Each of the arithmetic messages takes either a Point or a Number (a scalar) as an argument, and returns a new Point as the result. Truncation and round off messages, similar to those for Numbers, are also provided in the instance protocol of Point.
|* scale||Answer a new Point that is the product of the receiver and the argument, scale.|
|+ delta||Answer a new Point that is the sum of the receiver and the argument, delta.|
|- delta||Answer a new Point that is the difference of the receiver and the argument, delta.|
|/ scale||Answer a new Point that is the quotient of the receiver and the argument, scale.|
|// scale||Answer a new Point that is the quotient (defined by division with truncation toward negative infinity) of the receiver and the argument, scale.|
|abs||Answer a new Point whose x and y are the absolute values of the receiver's x and y.|
|truncation and round off|
|rounded||Answer a new Point that is the receiver's x and y rounded.|
|truncateTo: grid||Answer a new Point that is the receiver's x and y truncated to the argument, grid.|
|Point instance protocol|
|(45@230) + (175@300)||220@530|
|(45@230) + 175||220@405|
|(45@230) - (175@300)||-130@-70|
|(160@240) / 50||(16/5)@(24/5)|
|(160@240) // 50||3@4|
|(160@240) // (50@50)||3@4|
|((45@230) - (175@300)) abs||130@70|
|(120.5 @ 220.7) rounded||121@221|
|(160 @ 240) truncateTo: 50||150@200|
Various other operations can be performed on Points including computing the distance between two Points, computing the dot product of two Points, transposing a point, and determining Points within some gridded range.
|dist: aPoint||Answer the distance between the argument, aPoint, and the receiver.|
|dotProduct: aPoint||Answer a Number that is the dot product of the receiver and the argument, aPoint.|
|grid: aPoint||Answer a Point to the nearest rounded grid modules specified by the argument, aPoint.|
|normal||Answer a Point representing the unit vector rotated 90 deg clockwise.|
|transpose||Answer a Point whose x is the receiver's y and whose y is the receiver's x.|
|truncatedGrid: aPoint||Answer a Point to the nearest truncated grid modules specified by the argument, aPoint.|
|Point instance protocol|
|(45@230) dist: 175@270||136.015|
|(160@240) dotProduct: 50@50||20000|
|(160@240) grid: 50@50||150@250|
|(160@240) truncatedGrid: 50@50||150@200|
Points and Rectangles are used together as support for graphical manipulation. A Rectangle contains two Points--origin, which specifies the top left corner, and corner, which indicates the bottom right corner of the region described. Class Rectangle provides protocol for access to all the coordinates involved, and other operations such as intersection with other rectangles. Messages to a Point provide an infix way to create a Rectangle with the Point as the origin.
|corner: aPoint||Answer a Rectangle whose origin is the receiver and whose corner is the argument, aPoint.|
|extent: aPoint||Answer a Rectangle whose origin is the receiver and whose extent is the argument, aPoint.|
|Point instance protocol|
Thus (45@200) corner: (175@270) represents the rectangular area shown earlier in the image of display coordinates.
Instances of Rectangle represent rectangular areas of pixels. Arithmetic operations take points as arguments and carry out scaling and translating operations to create new Rectangles. Rectangle functions create new Rectangles by determining intersections of Rectangles with Rectangles.
In addition to the messages to Point by which Rectangles can be created, class protocol for Rectangle supports three messages for creating instances. These messages specify either the boundaries of the rectangular area, the origin and corner coordinates, or the origin and width and height of the area.
|left: leftNumber right: rightNumber top: topNumber bottom: bottomNumber||Answer a Rectangle whose left, right, top, and bottom coordinates are determined by the arguments.|
|origin: originPoint corner: cornerPoint||Answer a Rectangle whose top left and bottom right corners are determined by the arguments, originPoint and cornerPoint.|
|origin: originPoint extent: extentPoint||Answer a Rectangle whose top left corner is originPoint and width by height is extentPoint.|
|Rectangle class protocol|
The accessing protocol for Rectangle is quite extensive. It supports detailed ways of referencing eight significant locations on the boundary of the Rectangle. These points are shown in Figure 18.10.
Messages for accessing these positions have selectors with names like those shown in the diagram.
|topLeft||Answer the Point at the top left corner of the receiver.|
|topCenter||Answer the Point at the center of the receiver's top horizontal line.|
|topRight||Answer the Point at the top right corner of the receiver.|
|rightCenter||Answer the Point at the center of the receiver's right vertical line.|
|bottomRight||Answer the Point at the bottom right corner of the receiver.|
|bottomCenter||Answer the Point at the center of the receiver's bottom horizontal line.|
|bottomLeft||Answer the Point at the bottom left corner of the receiver.|
|leftCenter||Answer the Point at the center of the receiver's left vertical line.|
|center||Answer the Point at the center of the receiver.|
|area||Answer the receiver's area, the product of width and height.|
|width||Answer the receiver's width.|
|height||Answer the receiver's height.|
|extent||Answer the Point receiver's width @ receiver's height.|
|top||Answer the position of the receiver's top horizontal line.|
|right||Answer the position of the receiver's right vertical line.|
|bottom||Answer the position of the receiver's bottom horizontal line.|
|left||Answer the position of the receiver's left vertical line.|
|origin||Answer the Point at the top left corner of the receiver.|
|corner||Answer the Point at the bottom right corner of the receiver.|
|Rectangle instance protocol|
Suppose the Rectangle referred to as frame is created by the expression
frame ← Rectangle origin: 100@100 extent: 150@150
Each of the Rectangle's locations can be modified by an accessing message whose keyword is one of the positions named in Figure 18.10. In addition, the width and height can be set with the messages width: and height:, respectively. Two messages are listed below that are commonly used in the implementation of the system programming interface in order to reset the variables of a Rectangle.
|origin: originPoint corner: cornerPoint||Set the points at the top left corner and the bottom right corner of the receiver.|
|origin: originPoint extent: extentPoint||Set the point at the top left corner of the receiver to be originPoint and set the width and height of the receiver to be extentPoint.|
|Rectangle instance protocol|
Rectangle functions create new Rectangles and compute relationships between two Rectangles.
|amountToTranslateWithin: a Rectangle||Answer a Point, delta, such that the receiver, when moved by delta, will force the receiver to lie within the argument, aRectangle.|
|areasOutside: aRectangle||Answer a collection of Rectangles comprising the parts of the receiver which do not lie within the argument, aRectangle.|
|expandBy: delta||Answer a Rectangle that is outset from the receiver by delta, where delta is a Rectangle, Point, or scalar.|
|insetBy: delta||Answer a Rectangle that is inset from the receiver by delta, where delta is a Rectangle, Point, or scalar.|
|insetOriginBy: originDeltaPoint cornerBy: cornerDeltaPoint||Answer a Rectangle that is inset from the receiver by originDeltaPoint at the origin and cornerDeltaPoint at the corner.|
|intersect: aRectangle||Answer a Rectangle that is the area in which the receiver overlaps with the argument, aRectangle.|
|merge: aRectangle||Answer the smallest Rectangle that contains both the receiver and the argument, aRectangle.|
|Rectangle instance protocol|
Figure 18.11 shows three Rectangles, A, B, and C, created as follows.
A ← 50@50 corner: 200@200. B ← 120@120 corner: 260@240. C ← 100@300 corner: 300@400
Then expressions using these three Rectangles are listed below. Notice that Rectangles print in the form originPoint corner: cornerPoint.
|A amountToTranslateWithin: C||50@250|
|A areasOutside: B||OrderedCollection((50@50 corner: 200@120) (50@120 corner: 120@200))|
|C expandBy: 10||90@290 corner: 310@410|
|C insetBy: 10@20||110@320 corner: 290@380|
|A intersect: B||120@120 corner:200@200|
|B merge: C||100@120 corner: 300@400|
The testing protocol for Rectangles includes messages to determine whether a Point or other Rectangle is contained within the boundaries of a Rectangle, or whether two Rectangles intersect.
|contains: aRectangle||Answer whether the receiver contains all Points contained by the argument, aRectangle.|
|containsPoint: aPoint||Answer whether the argument, aPoint, is within the receiver.|
|intersects: aRectangle||Answer whether the receiver contains any Point contained by the argument, aRectangle.|
|Rectangle instance protocol|
Continuing the above example
|A contains: B||false|
|C containsPoint: 200@320||true|
|A intersects: B||true|
Like the messages for a Point, the coordinates of a Rectangle can be rounded to the nearest integer. A Rectangle can be moved by some amount, translated to a particular location, and the coordinates can be scaled or translated by some amount. Rectangles also respond to scaling and translating messages; they are part of the protocol for any object that can display itself on a display medium.
|truncation and round off|
|rounded||Answer a Rectangle whose origin and corner coordinates are rounded to the nearest integer.|
|moveBy: aPoint||Change the corner positions of the receiver so that its area translates by the amount defined by the argument, aPoint|
|moveTo: aPoint||Change the corners of the receiver so that its top left position is the argument, aPoint.|
|scaleBy: scale||Answer a Rectangle scaled by the argument, scale, where scale is either a Point or a scalar.|
|translateBy: factor||Answer a Rectangle translated by the argument, factor, where factor is either a Point or a scalar.|
|Rectangle instance protocol|
|A moveBy: 50@50||100@100 corner: 250@250|
|A moveTo: 200@300||200@300 corner: 350@450|
|A scaleBy: 2||400@600 corner: 700@900|
|A translateBy: -100||100@200 corner: 250@350|
The most basic interface to BitBlt is through a class of the same name. Each instance of BitBlt contains the variables necessary to specify a BitBlt operation. A specific application of BitBlt is governed by a list of parameters, which includes:
|destForm||(destination form) a Form into which pixels will be stored|
|sourceForm||a Form from which pixels will be copied|
|halftoneForm||a Form containing a spatial halftone pattern|
|combinationRule||an Integer specifying the rule for combining corresponding pixels of the sourceForm and destForm|
|destX, destY, width, height||(destination area x, y, width, and height) Integers which specify the rectangular subregion to be filled in the destination|
||(clipping rectangular area x, y, width, and height) Integers which specify a rectangular area which restricts the affected region of the destination|
|sourceX, sourceY||Integers which specify the location (top left corner) of the subregion to be copied from the source|
The BitBlt class protocol consists of one message for creating instances; this message contains a keyword and argument for each BitBlt variable. The BitBlt instance protocol includes messages for initializing the variables and a message, copyBits, which causes the primitive operation to take place. It also contains a message, drawFrom: startPoint to: stopPoint, for drawing a line defined by two Points.
BitBlt class protocol instance creationg destForm: destination sourceForm: source halftoneForm: halftone combinationRule: rule destOrigin: destOrigin sourceOrigin: sourceOrigin extent: extent clipRect: clipRect
|Answer a Bitblt with values set according to each of the arguments, where rule is an Integer; destination, source, and halftone are Forms; destOrigin, sourceOrigin, and extent are Points; and clipRect is a Rectangle.|
|sourceForm: aForm||Set the receiver's source form to be the argument, aForm.|
|destForm: aForm||Set the receiver's destination form to be the argument, aForm.|
|mask: aForm||Set the receiver's halftone mask form to be the argument, aForm.|
|combinationRule: anInteger||Set the receiver's combination rule to be the argument, anInteger, which must be an integer between 0 and 15.|
|clipHeight: anInteger||Set the receiver's clipping area height to be the argument, anInteger.|
|clipWidth: anInteger||Set the receiver's clipping area width to be the argument, anInteger.|
|clipRect||Answer the receiver's clipping rectangle.|
|clipRect: aRectangle||Set the receiver's clipping rectangle to be the argument, aRectangle.|
|clipX: anInteger||Set the receiver's clipping rectangle top left x coordinate to be the argument, anInteger.|
|clipY: anInteger||Set the receiver's clipping rectangle top left y coordinate to be the argument, anInteger.|
|sourceRect: aRectangle||Set the receiver's source form rectangular area to be the argument, aRectangle.|
|sourceOrigin: aPoint||Set the receiver's source form top left coordinates to be the argument, aPoint.|
|sourceX: anInteger||Set the receiver's source form top left x coordinate to be the argument, anInteger.|
|sourceY: anInteger||Set the receiver's source form top left y coordinate to be the argument, anInteger.|
|destRect: aRectangle||Set the receiver's destination form rectangular area to be the argument, aRectangle.|
|destOrigin: aPoint||Set the receiver's destination form top left coordinates to be the argument, aPoint.|
|destX: anInteger||Set the receiver's destination form top left x coordinate to be the argument, anInteger.|
|destY: anInteger||Set the receiver's destination form top left y coordinate to be the argument, anInteger.|
|height: anInteger||Set the receiver's destination form height to be the argument, anInteger.|
|width: anInteger||Set the receiver's destination form width to be the argument, anInteger.|
|copyBits||Perform the movement of bits from the source form to the destination form. Report an error if any variables are not of the right type (Integer or Form), or if the combination rule is not between 0 and 15 inclusive. Try to reset the variables and try again.|
|Bitblt instance protocol|
The state held in an instance of BitBlt allows multiple operations in a related context to be performed without the need to repeat all the initialization. For example, when displaying a scene in a display window, the destination form and clipping rectangle will not change from one operation to the next. Thus the instance protocol for modifying individual variables can be used to gain efficiency.
Much of the graphics in the Smalltalk-80 system consists of lines and text. These entities are synthesized by repeated invocation of BitBlt.
The BitBlt protocol includes the messages drawFrom: startPoint to: stopPoint to draw a line whose end points are the arguments, startPoint and stopPoint.
|drawFrom: startPoint to: stopPoint||Draw a line whose end points are the arguments, startPoint and stopPoint. The line is formed by displaying copies of the current source form according to the receiver's halftone mask and combination rule.|
|Bitblt instance protocol|
By using BitBlt, one algorithm can draw lines of varying widths, different halftones, and any combination rule. To draw a line, an instance of BitBlt is initialized with the appropriate destination Form and clipping rectangle, and with a source that can be any Form to be applied as a pen or "brush" shape along the line. The message drawFrom:to: with Points as the two arguments is then sent to the instance. Figure 18.12 shows a number of different pen shapes and the lines they form when the BitBlt combination rule is 6 or 7.
The message drawFrom: startPoint to: stopPoint stores the destX and destY values. Starting from these stored values, the line-drawing loop, drawLoopX: xDelta Y: yDelta, shown next, accepts x and y delta values and calculates x and y step values to determine points along the line, and then calls copyBits in order to display the appropriate image at each point. The method used is the Bresenham plotting algorithm (IBM Systems Journal, Volume 4, Number 1, 1965). It chooses a principal direction and maintains a variable, p When p's sign changes, it is time to move in the minor direction as well. This method is a natural unit to be implemented as a primitive method, since the computation is trivial and the setup in copyBits is almost all constant from one invocation to the next.
The method for drawLoopX: xDelta Y: yDelta in class BitBlt is
drawLoopX: xDelta Y: yDelta | dx dy px py p | dx ← xDelta sign. dy ← yDelta sign. px ← yDelta abs. py ← xDelta abs. self copyBits. "first point" py > px ifTure: "more horizontal" [p ← py // 2. 1 to: py do: [ :i | destx ← destx + dx. (p ← p - px) < 0 ifTrue: [desty ← desty + dy. p ← p + py]. self copyBits]] ifFalse: "more vertical" [p ← px//2. 1 to: px do: [ :i | desty ← desty + dy. (p ← p - py) < 0 ifTrue: [destx ← destx + dx. p ← p + px]. self copyBits]]
One of the advantages derived from BitBlt is the ability to store fonts compactly and to display them using various combination rules. The compact storage arises from the possibility of packing characters horizontally one next to another (as shown earlier in Figure 18.3), since BitBlt can extract the relevant bits if supplied with a table of left x coordinates of all the characters. This is called a strike format from the typographical term meaning a contiguous display of all the characters in a font.
The scanning and display of text are performed in the Smalltalk-80 system by a subclass of BitBlt referred to as CharacterScanner. This subclass inherits all the normal state, with destForm indicating the Form in which text is to be displayed and sourceForm indicating a Form containing all the character glyphs side by side (as in Figure 18.3). In addition CharacterScanner defines further state including:
|text||a String of Characters to be displayed|
|textPos||an Integer giving the current position in text|
|xTable||an Array of Integers giving the left x location of each character in sourceForm|
|stopX||an Integer that sets a right boundary past which the inner loop should stop scanning|
|exceptions||an Array of Symbols that, if non-nil, indicate message for handling the corresponding characters specially|
|printing||a Boolean indicating whether characters are to be printed|
Once an instance has been initialized with a given font and text location, the scanWord: loop below will scan or print text until some horizontal position (stopX) is passed, until a special character (determined from exceptions) is found, or until the end of this range of text (endRun) is reached. Each of these conditions is denoted by a symbolic code referred to as stopXCode, exceptions (an Array of Symbols) and endRunCode.
scanword: endRun | charIndex | [textPos < endRun] whileTrue: ["pick character" charIndex ← text at: textPos. "check exceptions" (exceptions at: charIndex) > 0 ifTrue: [↑exceptions at: charIndex]. "left x of character in font" sourceX ← xTable at: charIndex. "up to left of next char" width ← (xTable at: charIndex + 1) - sourceX. "print the character" printing ifTrue: [self copyBits]. "advance by width of character" destX ← destX + width. destX > stopX ifTrue: [↑stopXCode]. "passed right boundary" "advance to next character" textPos ← textPos + 1]. textPos ← textPos - 1. ↑endRunCode
The check on exceptions handles many possibilities in one operation. The space character may have to be handled exceptionally in the case of text that is padded to achieve a flush right margin. Tabs usually require a computation or table lookup to determine their width. Carriage return is also identified in the check for exceptions. Character codes beyond the range given in the font are detected similarly, and are usually handled by showing an exceptional character, such as a little lightning bolt, so that they can be seen and corrected.
The printing flag can be set false to allow the same code to measure a line (break at a word boundary) or to find to which character the cursor points. While this provision may seem over-general, two benefits (besides compactness) are derived from that generality. First, if one makes a change to the basic scanning algorithm, the parallel functions of measuring, printing, and cursor tracking are synchronized by definition. Second, if a primitive implementation is provided for the loop, it exerts a threefold leverage on the system performance.
The scanword: loop is designed to be amenable to such primitive implementation; that is, the interpreter may intercept it and execute primitive code instead of the Smalltalk-80 code shown. In this way, much of the setup overhead for copyBits can be avoided at each character and an entire word or more can be displayed directly. Conversely, the Smalltalk text and graphics system requires implementation of only the one primitive operation (BitBlt)to provide full functionality.
Simulation of Bitblt
We provide here a simulation of an implementation of copyBits in a subclass of BitBlt referred to as BitBltSimulation. The methods in this simulation are intentionally written in the style of machine code in order to serve as a guide to implementors. No attempt is made to hide the choice of 16-bit word size. Although the copyBits method is presented as a Smalltalk-80 method in BitBltSimulation, it is actually implemented in machine-code as a primitive method in class BitBlt; the simulation does the same thing, albeit slower.
|instance variable names||sourceBits sourceRaster|
sx sy dx dy w h
|class variable names||AllOnes RightMasks|
initialize "Initialize a table of bit masks" RightMasks ← #(0 16r1 16r3 16r7 16rF 16r1F 16r3F 16r7F 16rFF 16r1FF 16r3FF 16r7FF 16rFFF 16r1FFF 16r3FFF 16r7FFF 16rFFFF). AllOnes ← 16rFFFF
operations copyBits "sets w and h" self clipRange. (w < = or: [h < = 0]) ifTrue: [↑self]. "null range" self computeMasks. self checkOverlap. self calculateOffsets. self copyLoop private clipRange "clip and adjust source origin and extent appropriately" "first in x" destX > = clipX ifTrue: [sx ← sourceX. dx ← destX. w ← width] ifFalse: [sx ← sourceX + (clipX - destX). w ← width - (clipX - destX). dx ← clipX]. (dx + w) > (clipX + clipWidth) ifTrue: [w ← w - ((dx + w) - (clipX + clipWidth))]. "then in y" destY > = clipY ifTrue: [sy ← sourceY. dy ← destY. h ← height] ifFalse: [sy ← sourceY + clipY - destY. h ← height - clipY + destY. dy ← clipY]. (dy + h) > (clipY + clipHeight) ifTrue: [h ← h - ((dy + h) - (clipY + clipHeight))]. sx < 0 ifTrue: [dx ← dx - sx. w ← w + sx. sx ← 0]. sx + w > sourceForm width ifTrue: [w ← w - (sx + w - sourceForm width)]. sy < 0 ifTrue: [dy ← dy - sy. h ← h + sy. sy ← 0]. sy + h > sourceForm height ifTrue: [h ← h - (sy + h - sourceForm height)]
Clipping first checks whether the destination x lies to the left of the clipping rectangle and, if so, adjusts both destination x and width. As mentioned previously, the data to be copied into this adjusted rectangle comes from a shifted region of the source, so that the source x must also be adjusted. Next, the rightmost destination x is compared to the clipping rectangle and the width is decreased again if necessary. This whole process is then repeated for y and height. Then the height and width are clipped to the size of the source form. The adjusted parameters are stored in variables sx, sy, dx, dy, w, and h. If either width or height is reduced to zero, the entire call to BitBlt can return immediately.
ComputeMasks | startBits endBits | "calculate skew and edge masks" distBits ← destForm bits. destRaster ← destForm width - 1 // 16 + 1. sourceForm notNil ifTrue: [sourceBits ← sourceForm bits. sourceRaster ← sourceForm width - 1 // 16 + 1]. halftoneForm notNil ifTrue: [halftoneBits ← halftoneForm bits]. skew ← (sx - dx) bitAnd: 15. "how many bits source gets skewed to right" startBits ← 16 - (dx bitAnd: 15). "how many bits in first word" mask1 ← RightMasks at: startBits + 1. endBits ← 15 - ((dx + w - 1) bitAnd: 15). "how many bits in last word" mask2 ← (RightMasks at: endBits + 1) bitInvert. skewMask ← (skew = 0 ifTrue:  ifFalse: [RightMasks at: 16 - skew + 1]). "determine number of words stored per line; merge masks if necessary" w < startBits ifTrue: [mask1 ← mask1 bitAnd: mask2. mask2 ← 0. nWords ← 1] ifFalse: [nWords ← (w - startBits - 1) // 16 + 2].
In preparation for the actual transfer of data, several parameters are computed. First is skew, the horizontal offset of data from source to destination. This represents the number of bits by which the data will have.to be rotated after being loaded from the source in order to line up with the final position in the destination. In the example of Figure 18.3, skew would be 5 because the glyph for the character "e" must be shifted left by 5 bits prior to being stored into the destination. From skew, skewMask is saved for use in rotating (this is unnecessary for machines with a rotate word instruction). Then mask1 and mask2 are computed for selecting the bits of the first and last partial words of each scan line in the destination. These masks would be 16r1FFF and 16rFFC0 respectively in the example of Figure 18.3 since startBits= 13 and endBits=6. In cases such as this where only one word of each destination line is affected, the masks are merged to select the range within that word, here 16r1FC0.
checkOverlap | t | "check for possible overlap of source and destination" hDir ← vDir ← 1. "defaults for no overlap" (sourceForm = = destForm and: [dy > = sy]) ifTrue: [dy > sy "have to start at bottom" ifTrue: [vDir ← - 1. sy ← sy + h - 1. dy ← dy + h - 1] ifFalse: [dx > sx "y's are equal, but x's are backward" ifTrue: [hDir ← -1. sx ← sx + w - 1. "start at right" dx ← dx + w - 1. "and fix up masks" skewMask ← skewMask bitInvert. t ← mask1. mask1 ← mask2. mask2 ← t]]]
A check must be made for overlapping source and destination. When source and destination lie in the same bitmap, there is the possibility of the copy operation destroying the data as it is moved. Thus when the data is being moved downward, the copy must start at the bottom and proceed upward. Similarly when there is no vertical movement, if the horizontal movement is to the right, the copy must start at the right and work back to the left. In all other cases the copy can proceed from top to bottom and left to right.
calculateOffsets "check if need to preload buffer (i.e., two words of source needed for first word of destination)" preload ← (sourceForm notNil) and: [skew ,~= 0 and: [skew < = (sx bitAnd: 15)]]. hDir < 0 ifTrue: [preload ← preload == false]. " calculate starting offsets" sourceIndex ← sy * sourceRaster + (sx// 16). destIndex ← dy * destRaster + (dx// 16). " calculate increments from end of 1 line to start of next" sourceDelta ← (sourceRaster * vDir) - (nWords + (preload ifTrue:  ifFalse: ) * hDir). destDelta ← (destRaster * vDir) - (nWords * hDir)
In cases where two words of source are needed to store the first word into the destination, a flag preload is set indicating the need to preload a 32-bit shifter prior to the inner loop of the copy (this is an optimization; one could simply always load an extra word initially). The offsets needed for the inner loop are the starting offset in words from the source and destination bases; deltas are also computed for jumping from the end of the data in one scanline to the start of data in the next.
inner loop copyLoop I prevWord thisWord skewWord mergeMask halftoneWord mergeWord word | 1 to: h do: " here is the vertical loop:" [:i | (halftoneForm notNil) ifTrue: [halftoneWord ← halftoneBits at: (1 + (dy bitAnd: 15)). dy ← dy + vDir] ifFalse: [halftoneWord ← AllOnes]. skewWord ← halftoneWord. preload ifTrue: [prevWord ← sourceBits at: sourceIndex + 1. "load the 32-bit shifter" sourceIndex ← sourceIndex + hDir] ifFalse: [prevWord ← 0]. mergeMask ← mask1. 1 to to: nWords do: "here is the inner horizontal loop" [ :word | sourceForm notNil " if source is used" ifTrue: [prevWord ← prevWord bitAnd: skewMask. thisWord ← sourceBits at: sourceIndex + 1. "pick up next word" skewWord ← prevWord bitOr: (this Word bitAnd: skewMask bitInvert). prevWord ← thisWord. skewWord ← (skewWord bitShift: skew) bitOr: (skewWord bitShift: skew - 16)]. " "16-bit rotate" mergeWord ← self merge: (skewWord bitAnd: halftoneWord) with: (destBits at: destIndex + 1). destBits at: destIndex + 1 put: ((mergeMask bitAnd: mergeWord) bitOr: (mergeMask bitInvert bitAnd: (destBits at: destIndex + 1))). sourceIndex ← sourceIndex + hDir. destIndex ← destIndex + hDir. word = (nWords - 1) ifTrue: [mergeMask ← mask2] ifFalse: [mergeMask ← AllOnes]]. sourceIndex ← sourceIndex + sourceDelta. destIndex ← destIndex + destDelta]
The outer, or vertical, loop includes the overhead for each line, selecting the appropriate line of halftone gray, preloading the shifter if necessary, and stepping source and destination pointers to the next scanline after the inner loop. It should be noted here that the reason for indexing the halftone pattern by the destination y is to eliminate "seams" which would occur if the halftones in all operations were not coordinated this way.
The inner, or horizontal, loop picks up a new word of source, rotates it with the previous, and merges the result with a word of the destination. The store into the destination must be masked for the first and last partial words on each scanline, but in the middle, no masking is really necessary.
merge: sourceWord with: destinationWord "These are the 16 combination rules:" combinationRule = 0 ifTrue: [↑O]. combinationRule = 1 ifTrue: [↑sourceWord bitAnd: destinationWord]. combinationRule = 2 ifTrue: [↑sourceWold bitAnd: destinationWord bitInvert]. combinationRule= 3 ifTrue: [↑sourceWord]. combinationRule= 4 ifTrue: [↑sourceWord bitInvert bitAnd: destinationWord]. combinationRule = 5 ifTrue: [↑destinationWord]. combinationRule =6 ifTrue:[↑sourceWord bitXor: destinationWord]. combinationRule= 7 ifTrue: [↑sourceWord bitOr: destinationWord]. combinationRule = 8 ifTrue: [↑sourceWord bitInvert bitAnd: destinationWord bitInvert]. combinationRule = 9 ifTrue: [↑sourceWord bitInvert bitXor: destinationWord]. combinationRule = 10 ifTrue: [↑destinationWord bitInvert]. combinationRule = 11 ifTrue: [↑sourceWord bitOr: destinationWord bitInvert]. combinationRule = 12 ifTrue: [↑sourceWord bitInvert]. combinationRule= 13 ifTrue: [↑sourceWord bitInvert bitOr: destinationWord]. combinationRule= 14 ifTrue: [↑sourceWord bitInvert bitOr: destinationWord bitInvert]. combinationRule = 15 ifTrue: [↑AllOnes]
Our experience has demonstrated the value of BitBlt's generality. This one primitive is so central to the programming interface that any improvement in its performance has considerable effect on the interactive quality of the system as a whole. In normal use of the Smalltalk-80 system, most invocations of BitBlt are either in the extreme microscopic or macroscopic range.
In the macroscopic range, the width of transfer spans many words. The inner loop across a horizontal scan line gets executed many times, and the operations requested tend to be simple moves or constant stores. Examples of these are:
- clearing a line of text to white
- clearing an entire window to white
- scrolling a block of text up or down
Most processors provide a fast means for block moves and stores, and these can be made to serve the applications above. Suppose we structure the horizontal loop of BitBlt as
- move left partial word,
- move many whole words (or none),
- move right partial word (or none).
Special cases can be provided for 2 if the operation is a simple store or a simple copy with no skew (horizontal bit offset) from source to destination. In this way, most macroscopic applications of BitBlt cab be made fast, even on processors of modest power.
The microscopic range of BitBlt is characterized by a zero count for the inner loop. The work on each scanline involves at most two partial words, and both overall setup and vertical loop overhead can be considerably reduced for these cases. Because characters tend to be less than a word wide and lines tend to be less than a word thick, nearly all text and line drawing falls into this category. A convenient way to provide such efficiency is to write a special case of BitBlt which assumes the microscopic parameters, but goes to the general BitBlt whenever these are not met. Because of the statistics (many small operations and a few very large ones), it does not hurt to pay the penalty of a false assumption on infrequent calls. One can play the same trick with clipping by assuming no clipping will occur and running the general code only when this assumption fails.