Computer Graphics
`
`PRINCIPLES AND PRACTICE
`
`Foley • van Dam • Feiner • Hughes
`SECOND EDITION
`
`THE SYS1EMS PROGRAMMING SERIES
`
`Page 1 of 9
`
`SONY EXHIBIT 1015
`
`

`

`Sponsoring Editor: Keith Wollman
`Production Supervisor: Bette J. Aaronson
`Copy Editor: Lyn Dupre
`Text Designer: Herb Caswell
`Technical Art Consultant: Joseph K. Vetere
`Illustrators: C&C Associates
`Cover Designer: Marshall Henrichs
`Manufacturing Manager: Roy Logan
`
`This book is in the Addison-Wesley Systems Progtamming Series
`Consulting editors: IBM Editorial Board
`
`Library of Congtess Cataloging-in-Publication Data
`Computer graphics: principles and practice/James D. Foley ... [et
`al.).-2nd ed.
`p. em.
`Includes bibliographical references.
`ISBN 0-201-12110-7
`I. Computer graphics.
`T38S.CS87 1990
`006.6-<ic20
`
`I. Foley, Jam~s D., 1942-.
`
`To Marylou, Ht
`
`To Debbie, my
`my children Eli
`
`To Jenni, my p:
`
`To my family, 1
`my father in mt
`
`And to all of 01
`
`89-35281
`CIP
`
`Cover: "Dutch Interior," after Vermeer, by J. Wallace, M. Cohen, and D. Greenberg, Cornell University
`(Copyright © 1987 Cornell University, Program of Computer Graphics.)
`
`Many of the designations used by manufacturers and sellers to distinguish their products are claimed as
`trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark
`claim, the designations have been printed in initial caps or all caps.
`
`The programs and applications presented in tltis book have been included for their instructional value. They are
`not guaranteed for any particular purpose. The publisher and the author do not offer any warranties or
`representations, nor do they accept any liabilities with respect to the programs or applications.
`
`Copyright© 1990 by Addison-Wesley Publishing Company, Inc.
`
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted,
`in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior
`written permission of the publisher. Printed in the United States of America.
`
`ABCDEFGHIJ-D0 -943210
`
`continued on the back flap
`
`Page 2 of 9
`
`

`

`210
`
`Geometrical Transformations
`
`5.4
`
`MJ
`Translate
`Scale
`Rotate
`Scale (with s~ = s,)
`
`M2
`Translate
`Scale
`Rotate
`Rotate
`
`In these cases, we need not be concerned about the order of matrix manipulation.
`
`6 .4 THE WINDOW-TO-VIEWPORT TRANSFORMATION
`
`Some graphics packages allow the programmer to specify output primitive coordinates in a
`floating-point world-coordinate system, using whatever units are meaningful to the
`application program: angstroms, microns, meters, miles, light-years, and so on. The term
`world is used because the application program is representing a world that is being
`interactively created or displayed to the user.
`Given that output primitives are specified in world coordinates, the graphics subroutine
`package must be told how to map world coordinates onto screen coordinates (we use the
`sp!!cific term screen coordinates to relate this discussion specifically to SRGP, but that
`hardcopy output devices might be used, in which case the term device coordinates would be
`more appropriate). We could do this mapping by having the application programmer
`provide the graphics package with a transformation matrix to effect the mapping. Another
`way is to have the application programmer specify a rectangular region in world
`coordinates, called the world-coordinate window, and a corresponding rectangular region in
`screen coordinates, called the viewport, into which the world-coordinate window is to be
`mapped. The transformation that maps the window into the viewport is applied to all of the
`output primitives in world coordinates, thus mapping them into screen coordinates. Figure
`5.10 shows this concept. As seen in this figure, if the window and viewport do not have the
`same height-to-width ratio, a nonuniform scaling occurs. If the application program
`changes the window or viewport, then new output primitives drawn onto the screen will be
`affected by the change. Existing output primitives are not affected by such a change.
`T he modifier world-coordinate is used with window to emphasize that we are not
`discussing a window-manager window, which is a different and more recent concept, and
`
`Maximum range
`t - - - - - - - - - , of screen
`coordinates
`
`[ill
`
`Window
`
`World coordinates
`
`Viewport
`
`Screen coordinates
`
`Fig. 5 .1 0 The window in world coordinates and the viewport in screen coordinates
`determine the mapping that is applied to all the output primitives in world coordinates.
`
`Wi
`
`World coo
`
`Fig. 5 .1 1 The eft
`primitives specifyin
`changed to viewpc
`package to draw th
`
`which unfortunately
`of window is meant
`If SRGP were tc
`the current canvas , '
`be able to change t
`specified output pri
`included a different·
`in positions differen
`Awindowmam
`which case not all c
`Chapter 10, we ft
`viewports, and wine
`Given a windo~
`from world coordil
`developed as a thn
`
`y
`
`(Xmax • Ymax : 0
`
`Window in
`world coordinates
`
`Fig. 5 .1 2 The s
`
`Page 3 of 9
`
`

`

`5.4
`
`The Window-to-Viewport Transformation
`
`211
`
`Maximum range
`1 - - - - - - - - - - , of screen
`
`[ill Viowport 2
`[Z5J coordinates
`
`Window
`
`World coordinates
`
`Viewport 1
`Screen coordinates
`
`Fig. 5 .1 1 The effect of drawing output primitives with two viewports. Output
`primitives specifying the house were first drawn with viewport 1, the viewport was
`changed to viewport 2, and then the application program again called the graphics
`package to draw the output primitives.
`
`which unfortunately has the same name. Whenever there is no ambiguity as to which type
`of window is meant, we will drop the modifier.
`If SRGP were to provide world-coordinate output primitives, the viewport would be on
`the current canvas, which defaults to canvas 0, the screen. The application program would
`be able to change the window or the viewport at any time, in which case subsequently
`specified output primitives would be subjected to a new transformation. If the change
`included a different viewport, then the new output primitves would be located on the canvas
`in positions different from those of the old ones, as shown in Fig. 5. 11.
`A window manager might map SRGP's canvas 0 into less than a full-screen window, in
`which case not all of the canvas or even of the viewport would necessarily be visible. In
`Chapter 10, we further discuss the relationships among world-coordinate windows,
`viewports, and window-manager windows.
`Given a window and viewport, what is the transformation matrix that maps the window
`from world coordinates into the viewport in screen coordinates? This matrix can be
`developed as a three-step transformation composition, as suggested in Fig. 5.12. The
`
`y
`
`y
`
`v
`
`v
`
`Maximum
`range
`of screen
`coordinates
`
`(X max • Ymax) 0
`
`1...------x
`Window In
`world coordinates
`
`' - - -L---x
`Window translated
`to origin
`
`..__..__ ___ u
`
`Window scaled to
`size of viewport
`
`(u max • V max} 0
`
`1------...l...• u
`Translated by (u min,
`Vmin) to final position
`
`Fig. 5 .12 The steps in transforming a world-coordinate window into a viewport.
`
`,f matrix manipulation.
`
`RMATION
`
`1tput primitive coordinates in a
`units are meaningful to the
`~ht-years, and so on. The term
`;enting a world that is being
`
`linates, the graphics subroutine
`screen coordinates (we use the
`specifically to SRGP, but that
`rm device coordinates would be
`g the application programmer
`to effect the mapping. Another
`rectangular region in world
`:esponding rectangular region in
`·rid-coordinate window is to be
`viewport is applied to all of the
`into screen coordinates. Figure
`:JW and viewport do not have the
`rs. If the application program
`es drawn onto the screen will be
`affected by such a change.
`• to emphasize that we are not
`1t and more recent concept, and
`
`Maximum range
`----. of screen
`coordinates
`
`rdinates
`
`viewport in screen coordinates
`primitives in world coordinates.
`
`Page 4 of 9
`
`

`

`212
`
`Geometrical Transform ations
`
`y
`
`Window
`
`v
`
`~
`
`Viewport
`
`Maximum range
`of screen
`coordinates
`
`~-------------+ X
`World coordinates
`
`~------------~u
`Screen coordinates
`
`Fig. 5.13 Output primitives in world coordinates are clipped against the window.
`Those that remain are displayed in the viewport.
`
`window, specified by its lower-left and upper-right corners, is first translated to the origin of
`world coordinates. Next, the size of the window is scaled to be equal to the size of the
`viewport. Finally, a translation is used to position the viewport. The overall matrix Mwv is:
`- u · v - v.)
`
`max
`mm
`Xmin' Ymax
`
`mm
`Ymin
`
`• T( _ Xn,·
`'"'
`
`_ Y . )
`mm
`
`M = T(~ V . )
`n• mm
`wv
`
`u
`• S max
`(
`Xmax
`
`[Umax - umin
`0]
`0
`1 0 u · ]
`= 0 1 v~. Xmax-Xmin v -v
`0
`min 0
`max
`mm
`[
`0 0
`1
`Ymax - Ymin
`0
`
`0
`
`1
`
`[ 1
`. 0
`0
`
`0 -x ·]
`
`~ -~:
`
`"max - Umin
`Xmax
`Xrnin
`
`0
`
`0
`
`vmax -
`Ymax
`
`vmin
`Ymin
`
`=
`
`u
`-x . max
`Xmax
`v
`-y . max
`Ymax
`
`- u.
`nun+ U .
`Xmin
`nun
`- v.
`mm + V .
`Ymin
`mm
`
`(5.33)
`
`0
`
`l ]T gives the expected result:
`
`0
`Multiplying P = Mwv [x y
`[<
`) Urnax - Umin +
`X - Xmin
`'
`_
`
`P -
`-
`
`Vmin +
`Ymtn
`Xma.,
`Many graphics packages combine the window-viewport transformation with clipping
`of output primitives against the window. The concept of clipping was introduced in Chapter
`3; Fig. 5. 13 illustrates clipping in the context of windows ~nd viewports.
`
`Umin
`
`(y
`
`) Vmax -
`- Ymin '
`_
`Ymax
`
`Ymin
`
`l].
`
`(5.34)
`
`Xmm
`
`5 .5 EFFICIENCY
`
`The most general composition of R, S. and T operations produces a matrix of the form
`
`M ~ [:&: ;; :;]
`
`(5.35)
`
`5 .6
`
`The upper 2 X 2
`are composite translat
`nine multiplies and s
`simplifies the actual ·
`
`reducing the process
`since the operation c
`Thus, although 3 X
`tions, we can use tht
`structure. Some hare
`diminishing or remo
`Another area wt
`such as a molecule o;
`view can be created
`object will appear tc
`each individual poin
`(Eq. (5.6)) require f
`recognizing that, be>
`approximation, Eq.
`
`which requires just
`significant on comp1
`Equation (5.37)
`small error is built h
`error gets a bit large
`correct values, and t
`lines.
`A better approJt
`
`y' = x' :
`This is a better 1
`corresponding 2 x
`unchanged.
`
`5 .6 MATRIX I
`
`Just as 20 transfo
`coordinates, so 3D
`homogeneous coo1
`representing a poi
`
`Page 5 of 9
`
`

`

`358
`
`Input Devices, Techniques, and Interaction Tasks
`
`8 .2
`
`There is great variation among keyboards in design parameters , such as keycap shape,
`distance between keys, pressure needed to press a key, travel distance for key depression,
`key bounce, auditory feedback, the feeling of contact when the key is fully depressed , and
`the placement and size of important keys such as "return" or " enter." Improper choice of
`parameters can decrease productivity and increase error rates. Making the "return" key too
`small invites errors, as does placing a hardware "reset" key close to other keys. These and
`other design parameters are discussed in [KLEM71; GREE87], and have been the 5ubject
`of recent international standardization efforts.
`The tip of a short joystick shaft moves through a short distance, forcing use of a small
`CID ratio; if we try to compensate by using a longer joystick shaft, the user cannot rest the
`heel of her hand on the work surface and thus does not have a steady platform from which to
`make fine adjustments. Accuracy and speed therefore suffer.
`The implication of these device differences is that it is not enough for a user interface
`designer to specify a particular device class; specific device characteristics must be defined.
`Unfortunately, not every user interface designer has the luxury of selecting devices; often,
`the choice has already been made. Then the designer can only hope that the devices are well
`designed, and attempt to compensate in software for any hardware deficiencies.
`
`8.2 BASIC INTERACTION TASKS
`
`With a basic interaction task, the user of an interactive system enters a unit of information
`that is meaningful in the context of the application. How large or small is such a unit? For
`instance, does moving a positioning device a small distance enter a unit of information?
`Yes, if the new position is put to some application purpose, such as repositioning an object
`or specifying the endpoint of a line. No, if the repositioning is just one of a sequence of
`repositionings as the user moves the cursor to place it on top of a menu item: here, it is the
`menu choice that is the unit of information.
`Basic interaction tasks (BITs) are indivisible; that is, if they were decomposed into
`smaller units of information , the smaller units would not in themselves be meaningful to the
`application. BITs are discussed in this section. In the next section, we treat composite
`interaction tasks (CITs), which are aggregates of the basic interaction tasks described here.
`If one thinks of BITs as atoms, then CITs are molecules .
`A complete set of BITs for interactive graphics is positioning, selecting, entering text,
`and entering numeric quantities. Each BIT is described in this section, and some of the
`many interaction techniques for each are discussed. However, there are far too many
`interaction techniques for us to give an exhaustive list, and we cannot anticipate the
`development of new techniques. Where possible, the pros and cons of each technique are
`discussed; remember that a specific interaction technique may be good in some situations
`and poor in othe.. _
`
`8 .2 .1 The Position Interaction Task
`
`,The positioning task involves specifying an (x, y) or (x, y, z) position to the application
`program. The customary interaction techniques for carrying out this task involve either
`moving a screen cursor to the desired location and then pushing a button, or typing the
`
`desired position's
`device can be dil'
`cursor-movement
`or the same comn
`can be used to!
`positioning, and :
`precise postionin.
`A number of
`the general issue:
`
`Coordinate sys
`which feedback i
`which direction .
`could move alor
`increasing x din
`object's own coc
`The first altf
`the latter two op·
`the screen coord
`rotation, then tt
`coordinates' x a>
`movement of th1
`180°! Such a :
`stimulus-respon·
`user actions mu
`the responses st
`tablet is rotated
`
`Resolution.
`'
`hundred to onf
`unlimited resol
`can cursor-mo•
`typically as lea
`the window-to·
`arrange for on
`world-coordim
`Touch pan
`1000 units. Bu
`Using the first
`be able to dra!
`contact with th
`the cursor arm
`point of contac
`albeit slower, 1
`is not recomn
`
`Page 6 of 9
`
`

`

`sks
`
`8.2
`
`Basic Interaction Tasks
`
`359
`
`meters, such as keycap shape,
`1 distance for key depression,
`he key is fully depressed, and
`·"enter." Improper choice of
`Maldng the "return" key too
`close to other keys. These and
`:7], and have been the 6ubject
`
`istance, forcing use of a small
`shaft, the user cannot rest the
`steady platform from which to
`
`tot enough for a user interface
`haracteristics must be defined.
`try of selecting devices; often,
`t hope that the devices are well
`trdware deficiencies.
`
`~m enters a unit of information
`·ge or small is such a unit? For
`:e enter a unit of information?
`such as repositioning an object
`1g is just one of a sequence of
`> of a menu item: here, it is the
`
`if they were decomposed into
`hemselves be meaningful to the
`l(t section, we treat composite
`1teraction tasks described here.
`
`ioning, selecting, entering text,
`this section, and some of the
`J~ever , there are far too many
`and we cannot anticipate the
`and cons of each technique are
`nay be good in some situations
`
`•, z) position to the application
`ing out this task involve either
`>ushing a button, or typing the
`
`desired position's coordinates on either a real or a simulated keyboard. The positioning
`device can be direct or indirect, continuous or discrete, absolute or relative. In addition,
`cursor-movement commands can be typed explicitly on a keyboard, as Up, Left, and so on,
`or the same commands can be spoken to a voice-recognition unit. Furthermore, techniques
`can be used together- a mouse controlling a cursor can be used for approximate
`positioning, and arrow keys can be used to move the cursor a single screen unit at a time for
`precise postioning.
`A number of general issues transcend any one interaction technique. We first discuss
`the general issues; we introduce specific positioning techniques as illustrations.
`
`Coordinate systems. An important issue in positioning is the coordinate system in
`which feedback is provided. If a locator device is moved to the right to drag an object, in
`which direction should the object move? There are at least three possibilities: the object
`could move along the increasing x direction in the screen-coordinate system, along the
`increasing x direction in world coordinates, or along the increasing x direction in the
`object's own coordinate system.
`The first alternative, increasing screen-coordinate x direction, is the correct choice. For
`the latter two options, consider that the increasing x direction need not in general be along
`the screen coordinates' x axis. For instance, if the viewing transformation includes a 180°
`rotation, then the world coordinates' x axis goes in the opposite direction to the screen
`coordinates' x axis, so that the right-going movement of the locator would cause a left-going
`movement of the object. Try positioning with this type of feedback by turning your mouse
`180°! Such a system would be a gross violation of the human-factors principle of
`stimulus-response compatibility (S-R compatibility), which states that system responses to
`user actions must be in the same direction or same orientation, and that the magnitude of
`the responses should be proportional to the actions. Similar problems can occur if a data
`tablet is rotated with respect to the screen.
`
`Resolution. The resolution required in a positioning task may vary from one part in a few
`hundred to one part in millions. Clearly, keyboard typein of an (x, y) pair can provide
`unlimited resolution: The typed digit strings can be as long as necessary. What resolution
`can cursor-movement techniques achieve? The resolution of tablets, mice, and so on is
`typically as least as great as the 500 to 2000 resolvable units of the display device. By using
`the window-to-viewport transformation to worn in on part of the world, it is possible to
`arrange for one unit of screen resolution to correspond to an arbitrarily small unit of
`world-coordinate resolution.
`Touch panels present other interesting resolution issues. Some panels are accurate to
`1000 units. But the user's finger is about~inch wide, so how can this accuracy be achieved?
`Using the first position the finger touches as the final position does not work. The user must
`be able to drag a cursor around on the screen by moving or rolling his finger while it is in
`contact with the touch panel. Because the finger obscures the exact position being indicated,
`the cursor arms can be made longer than normal, or the cursor can be offset from the actual
`point of contact. In an experiment, dragging an offset cursor was found to be more accurate,
`albeit slower, than was using the first point contacted [POTT88]. In general, the touch panel
`is not recommended for frequent high-resolution positioning tasks.
`
`Page 7 of 9
`
`

`

`:>mrnand, say
`te root node is
`
`In the Xerox
`reen cursor on
`)rd rather than
`e hierarchy are
`
`1ely fixed-sized
`
`:iers, including
`tsed first, most
`e orders can be
`1 alphabetically
`·use. Figure 8.7
`from one menu
`on is important.
`md many menu
`
`tal menu design
`1 a menu can be
`uence of choices
`
`quence. (b) Menu
`til as alphabetical(cid:173)
`different applica(cid:173)
`•lication's menus;
`•se used in Card's
`
`8.2
`
`Basic Interaction Tasks
`
`365
`
`shift- i
`to move
`selection up
`using keyboard
`
`i to scroll window
`up using keyboard
`
`shift -,I.
`to move selection
`down using
`keyboard
`
`,I. to scroll window
`down using keyboard
`
`Fig. 8.8 A menu within a scrolling window. The user controls scrolling by selecting the
`up and down arrows or by dragging the square in the scroll bar.
`
`to be paged or scrolled through. A scroll bar of the type used in many window managers
`allows all the relevant scrolling and paging commands to be presented in a concise way. A
`·fast keyboard-oriented alternative to pointing at the scrolling commands can also be
`provided; for instance, the arrow keys can be used to scroll the window, and the shift key
`can be combined with the arrow keys to move the selection within the visible window, as
`shown in Fig. 8.8. In the limit, the size of the window can be reduced to a single menu
`item, yielding a "slot-machine" menu of the type shown in Fig . 8.9.
`With a hierarchical menu, the user first selects from the choice set at the top of the
`hierarchy, which causes a second choice set to be available. The process is repeated until a
`leaf node (i.e., an element of the choice set itself) of the hierarchy tree is selected. As with
`hierarchical object selection , navigation mechanisms need to be provided so that the user
`can go back up the hierarchy if an incorrect subtree was selected. Visual feedback to give
`the user some sense of place within the hierarchy is also needed.
`Menu hierarchies can be presented in several ways. Of course, successive levels of the
`hierarchy can replace one another on the display as further choices are made, but this does
`not give the user much sense of position within the hierarchy. The cascading hierarchy, as
`depicted in Fig. 8.10, is more attractive. Enough of each menu must be revealed that the
`complete highlighted selection path is visible, and some means must be used to indicate
`whether a menu item is a leaf node or is the name of a lower-level menu (in the figure, the
`right-pointing arrow fills this role). Another arrangement is to show just the name of each
`
`Current Menu Item 1-g
`(Accept) (concet)
`
`Fig. 8 .9 A small menu-selection window. Only one menu item appears at a time. The
`scroll arrows are used to change the current menu item, which is selected when the
`Accept button is chosen.
`
`Page 8 of 9
`
`

`

`366
`
`Input Devices, Techniques, and Interaction Tasks
`
`8.2
`
`(a)
`
`(b)
`
`(c)
`
`Fig. 8.10 A pop-up hierarchical menu. (a) The first menu appears where the cursor is,
`in response to a button-down action. The cursor can be moved up and down to select
`the desired typeface. (b) The cursor is then moved to the right to bring up the second
`menu. (c) The process is repeated for the third menu.
`
`selection made thus far in traversing down the hierarchy, plus all the selections available at
`the current level.
`A panel hierarchy is another way to depict a hierarchy, as shown in Fig. 8.11; it takes
`up somewhat more room than the cascading hierarchy. If the bjerarchy is not too large, an
`explicit tree showing the entire hierarchy can also be displayed.
`When we design a hierarchical menu, the issue of depth versus breadth is always
`present. Snowberry et al. [SNOW83] found experimentally that selection time and accuracy
`improve when broader menus with fewer levels of selection are used. Similar results are
`reported by Landauer and Nachbar [LAND85] and by other researchers. However, these
`
`r-:
`
`I ont Pan!!l
`
`~
`
`results do not necessarily !
`structure.
`Hierarchical menu sel
`key accelerator technique
`users. This is easy if each
`name directly , and the m
`names are unique only "
`complete path name to tl-
`Menu placement. Mer
`screen (Fig. 8.12); they c
`menus can be static an•
`(tear-off, appearing, pop·
`A static menu printe
`fixed-application systems
`user look away from the
`advantages are the savi
`accommodation of a lar1
`A pop-up menu app(
`to an explicit user ac
`automatically because th
`appears at the cursor Joe.
`
`Fig. 8:11 A hierarchical-selection menu. The leftmost column represents the top level;
`the chll~ren of the selected item in this column are shown in the next column; and so on.
`If there 1s no selected item, then the columns to the right are blank. (Courtesy of NeXT,
`Inc. © 1989 NeXT, Inc.)
`
`Fig. 8 .12 A dual-di~
`overview of a drawin!
`and menus on the ott
`
`Page 9 of 9
`
`