;
`ck
`ce
`7==
`
`*
`+}
`‘4
`-
`—s
`iP _ :— a
`
`DOMPUTER GRAF
`
`Ta
`
`Align EX1044 Align v. 3Shape
`
`a T
`
`e
`
`me eeeeee
`
`10dPAOP PEVOD Ee
`
`Align EX1044
`Align v. 3Shape
`IPR2022-00145
`
`

`

`
`
` wt
`
`9 780201 609219
`
`
`
`
`
`

`

`James D. Foley
`Georgia Institute of Technology
`
`Andries van Dam
`Brown University
`
`Steven K. Feiner
`Columbia University
`
`John F. Hughes
`Brown University
`
`Richard L. Phillips
`Los Alamos National Laboratory
`and The University of Michigan
`
`,.f.., ADDISON-WESLEY PUBLISHING COMPANY
`
`Reading, Massachusetts • Menlo Park, California • New York
`Don Mills, Ontario • Wokingham, England • Amsterdam • Bonn
`Sydney • Singapore • Tokyo • Madrid • San Juan • Milan • Paris
`
`

`

`Sponsoring Editor Peter S. Gordon
`Senior P roduction Supervisor Jim Rigney
`Copy Editors Lyn Dupre and Joyce Grandy
`Text Designer Sandra Rigney
`Technical Art Consultant Joseph K. Vetere
`Illustrator C&C Associates and Tech Graphics
`Cover Designer Eileen Hoff
`Senior Manufacturing Manager Roy Logan
`Marketing Manager Robert Donegan
`
`Cover images from "Luxo Jr.," by J. Lasseter, W. Reeves, E. Ostby,
`and S. Leffler. (Copyright© 1986 Pixar.) "Luxo" is a trademark of
`Jae Jacobsen lndustrier.
`
`This book is an abridged and modified version of Computer Graphics: Principles
`and Practice, Second Edition, by Foley, van Dam, Feiner, and Hughes, published
`in l 990 in the Addison-Wesley Systems Programming Series, IBM Editorial
`Board, consulting editors.
`
`Many of tlle designations used by manufacturers and sellers to distinguish Lhcir products arc
`claimed as Lrademarks. Where those designations appear in this book, and Addison-Wesley
`was aware of a trademark claim. the designations have ooen printed in initial caps or all caps.
`
`The programs and applications presented in this 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 warranLies or representations, nor do they accept any liabilities with respect to the
`programs or applicarions.
`
`Library of Congress Cataloging-in-Publication data
`
`Introduction to computer graphics/ James D. Foley . . . [et al.].].
`p. cm.
`Includes bibliographical references and index.
`lSBN 0-20 l -60921-5
`1. Computer graphics.
`T385.l538 1993
`006.6-dc20
`
`I. Foley, James D., 1942-
`
`93- 16677
`CIP
`
`Reprinted with corrections February, 1994
`
`Copyright © 1994, 1990 by Addison-Wesley Publishing Company, Inc.
`
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval sys rem,
`or transmitted, io any fom1 or by any means, electronic, mechanical, photocopying, recording,
`or otherwise, without the prior written permission of the publisher. Primed in the United Stales
`of America
`
`4 5 6 7 8 9 10 MA 9897969594
`
`

`

`1 Introducing: Computer Graphics
`1.1 A Few Uses of Computer Graphics 1
`1.2 A Brief History of Computer Graphics 6
`1.2.1 Output Technology 8
`1.2.2 Input Technology 11
`1 .2.3 Software Portability and Graphics Standards 12
`1.3 The Advantages of Interactive Graphics 14
`1.4 Conceptual Framework for Interactive Graphics 15
`1 .4.1 Application Modeling 16
`1 .4.2 Display of the Model 16
`1.4.3 Interaction Handling 17
`SUMMARY 18
`Exercises 19
`
`2 Programming in the Simple Raster
`Graphics Package (SRGP)
`2.1 Drawing with SRGP 22
`2.1.1 Specification of Graphics Primitives 22
`2.1.2 Attributes 27
`2.1.3 Filled Primitives and Their Attributes 29
`2.1.4 Saving and Restoring Attributes 33
`
`1
`
`21
`
`xix
`
`

`

`xx
`
`Contents
`
`2.1.5 Text 33
`2.2 Basic Interaction Handling 36
`2.2.1 Human Factors 36
`2.2.2 Logical Input Devices 37
`2.2.3 Sampling Versus Event-Driven Processing 38
`2.2.4 Sample Mode 40
`2.2.5 Event Mode 41
`2.2.6 Pick Correlation for Interaction Handling 45
`2.2.7 Setting Device Measure and Attributes 47
`2.3 Raster Graphics Features 49
`2.3.1 Canvases 49
`2.3.2 Clipping Rectangles 52
`2.3.3 The SRGP _copyPixel Operation 52
`2.3.4 Write Mode or RasterOp 54
`2.4 Limitations of SRGP 58
`2.4.1 Application Coordinate Systems 58
`2.4.2 Storage of Primitives for Respecification 59
`SUMMARY 61
`Exercises 62
`Programming Projects 63
`
`3 Basic Raster Graphics Algorithms for Drawing
`2D Primitives
`3.1 Overview 66
`3.1.1 Implications of Display-System Architecture 66
`3.1 .2 The Output Pipeline in Software 69
`3.2 Scan Converting Lines 70
`3.2.1 The Basic Incremental Algorithm 71
`3.2.2 Midpoint Line Algorithm 73
`3.2.3 Additional Issues 77
`3.3 Scan Converting Circles 80
`3.3.1 Eight-Way Symmetry 80
`3.3.2 Midpoint Circle Algorithm 81
`3.4 Filling Rectangles 85
`3.5 Filling Polygons 87
`3.5.1 Horizontal Edges 89
`3.5.2 Slivers 90
`3.5.3 Edge Coherence and the Scan-Line Algorithm 90
`3.6 Pattern Filling 94
`3.6.1 Pattern Filling Using Scan Conversion 94
`
`65
`
`

`

`Contents
`
`xxl
`
`3.6.2 Pattern Filling Without Repeated Scan Conversion 95
`3.7 Thick Primitives 97
`3.7.1 Replicating Pixels 98
`3.7.2 The Moving Pen 99
`3.8 Clipping in a Raster World 100
`3.9 Clipping Lines 101
`3.9.1 Clipping Endpoints 102
`3.9.2 Clipping Lines by Solving Simultaneous Equations 102
`3.9.3 The Cohen-Sutherland Line-Clipping Algorithm 103
`3.9.4 A Parametric Line-Clipping Algorithm 107
`3.10 Clipping Circles 111
`3.11 Clipping Polygons 112
`3.11.1 The Sutherland-Hodgman Polygon-Clipping Algorithm 112
`3.12 Generating Characters 116
`3.12.1 Defining and Clipping Characters 116
`3.12.2 Implementing a Text Output Primitive 117
`3.13 SRGP _copyPixel 119
`3.14 Antialiasing 119
`3.14.1 Increasing Resolution 119
`3.14.2 Unweighted Area Sampling 120
`3.14.3 Weighted Area Sampling 122
`3.15 Advanced Topics 125
`
`SUMMARY 126
`Exercises 126
`
`129
`
`4 Graphics Hardware
`4.1 Hardcopy Technologies 130
`4.2 Display Technologies 135
`4.3 Raster-scan Display Systems 141
`4.3.1 Simple Raster Display System 142
`4.3.2 Raster Display System with Peripheral Display Processor 145
`4.3.3 Additional Display-Processor Functionality 148
`4.3.4 Raster Display System with Integrated Display Processor 150
`4.4 The Video Controller 151
`4.4.1 Video Mixing 152
`4.5 Input Devices for Operator Interaction 153
`4.5.1 Locator Devices 153
`4.5.2 Keyboard Devices 156
`
`

`

`xxli
`
`Contents
`
`4.5.3 Valuator Devices 156
`4.5.4 Choice Devices 157
`4.6 Image Scanners 157
`
`Exercises 158
`
`161
`
`5 Geometrical Transformations
`5.1 Mathematical Preliminaries 161
`5.1 .1 Vectors and Their Properties 162
`5.1.2 The Vector Dot Product 164
`5.1 .3 Properties of the Dot Product 164
`5.1 .4 Matrices 165
`5.1 .5 Matrix Multiplication 165
`5.1.6 Determinants 166
`5.1 . 7 Matrix Transpose 166
`5.1.8 Matrix Inverse 167
`5.2 20 Transformations 168
`5.3 Homogeneous Coordinates and Matrix Representation of 20
`Transformations 170
`5.4 Composition of 20 Transformations 175
`5.5 The Window-to-Viewport Transformation 177
`5.6 Efficiency 179
`5.7 Matrix Representation of 30 Transformations 180
`5.8 Composition of 30 Transformations 183
`5.9 Transformations as a Change in Coordinate System 187
`Exercises 191
`
`193
`
`6 Viewing in 3D
`6.1 The Synthetic Camera and Steps In 30 Viewing 193
`6.2 Projections 195
`6.2.1 Perspective Projections 197
`6.2.2 Parallel Projections 198
`6.3 Specification of an Arbitrary 30 View 201
`6.4 Examples of 30 Viewing 206
`6.4.1 Perspective Projections 207
`6.4.2 Parallel Projections 211
`6.4.3 Finite View Volumes 212
`6.5 The Mathematics of Planar Geometric Projections 213
`
`

`

`Contents
`
`xxiil
`
`6.6 Implementation of Planar Geometric Projections 216
`6.6.1 The Parallel Projection Case 217
`6.6.2 The Perspective Projection Case 222
`6.6.3 Clipping Against a Canonical View Volume in 30 227
`6.6.4 Clipping in Homogeneous Coordinates 229
`6.6.5 Mapping into a Viewport 231
`6.6.6 Implementation Summary 233
`6.7 Coordinate Systems 234
`
`Exercises 235
`
`239
`
`7 Object Hierarchy and Simple PHIGS (SPHIGS)
`7.1 Geometric Modeling 240
`7.1.1 Geometric Models 242
`7 .1.2 Hierarchy in Geometric Models 243
`7.1.3 Relationship Among Model, Application Program, and Graphics
`System 245
`7.2 Characteristics of Retained-Mode Graphics Packages 247
`7.2.1 Central Structure Storage and Its Advantages 247
`7.2.2 Limitations of Retained-Mode Packages 248
`7.3 Defining and Displaying Structures 249
`7.3.1 Opening and Closing Structures 249
`7.3.2 Specifying Output Primitives and Their Attributes 250
`7.3.3 Posting Structures for Display Traversal 253
`7.3.4 Viewing 253
`7.3.5 Graphics Applications Sharing a Screen via Window
`Management 256
`7.4 Modeling Transformations 257
`7 .5 Hierarchical Structure Networks 262
`7.5.1 Two-Level Hierarchy 262
`7.5.2 Simple Three-Level Hierarchy 263
`7.5.3 Bottom-Up Construction of the Robot 265
`7.5.4 Interactive Modeling Programs 268
`7.6 Matrix Composition in Display Traversal 269
`7.7 Appearance-Attribute Handling in Hierarchy 273
`7.7.1 Inheritance Rules 273
`7.7.2 SPHIGS Attributes and Text Unaffected by
`Transformations 275
`7.8 Screen Updating and Rendering Modes 276
`7.9 Structure Network Editing for Dynamic Effects 277
`7.9.1 Accessing Elements with Indices and Labels 278
`
`

`

`xxfv
`
`Contents
`
`7.9.2 lntrastructure Editing Operations 278
`7.9.3 Instance Blocks for Editing Convenience 279
`7.9.4 Controlling Automatic Regeneration of the Screen Image 281
`7.10 Interaction 282
`7.10.1 Locator 282
`7.10.2 Pick Correlation 282
`7.11 Advanced Issues 289
`7.11.1 Additional Output Features 289
`7.11.2 Implementation Issues 290
`7.11.3 Optimizing Display of Hierarchical Models 292
`7.11.4 Limitations of Hierarchical Modeling in PHIGS 292
`7.11.5 Alternative Forms of Hierarchical Modeling 293
`7 .11.6 Other (Industry) Standards 293
`SUMMARY 294
`Exercises 295
`
`297
`
`8 Input Devices, Interaction Techniques, and
`Interaction Tasks
`8.1 Interaction Hardware 298
`8.1.1 Locator Devices 299
`8.1.2 Keyboard Devices 300
`8.1.3 Valuator Devices 300
`8.1.4 Choice Devices 301
`8.1 .5 Other Devices 301
`8.1.6 30 Interaction Devices 301
`8.2 Basic Interaction Tasks 304
`8.2.1 The Position Interaction Task 304
`8.2.2 The Select Interaction Task-Variable-Sized Set of
`Choices 305
`8.2.3 The Select Interaction Task-Relatively Fixed-Sized Choice
`Set 308
`8.2.4 The Text Interaction Task 311
`8.2.5 The Quantify Interaction Task 311
`8.2.6 30 Interaction Tasks 312
`8.3 Composite Interaction Tasks 314
`8.3.1 Dialogue Boxes 315
`8.3.2 Construction Techniques 315
`8.3.3 Dynamic Manipulation 316
`8.4 Interaction-Technique Toolkits 318
`
`SUMMARY 319
`Exercises 319
`
`

`

`Contents
`
`XXV
`
`321
`
`g Representation of Curves and Surfaces
`9.1 Polygon Meshes 323
`9.1 .1 Representing Polygon Meshes 323
`9.1 .2 Plane Equations 325
`9.2 Parametric Cubic Curves 328
`9.2.1 Basic Characteristics 329
`9.2.2 Hermite Curves 332
`9.2.3 Bezier Curves 336
`9.2.4 Uniform Nonrational B-Splines 342
`9.2.5 Nonuniform, Nonrational B-Splines 345
`9.2.6 Nonuniform, Rational Cubic Polynomial Curve Segments 348
`9.2.7 Fitting Curves to Digitized Points 348
`9.2.8 Comparison of the Cubic Curves 349
`9.3 Parametric Bicubic Surfaces 351
`9.3.1 Hermite Surfaces 351
`9.3.2 Bezier Surfaces 353
`9.3.3 B-Spline Surfaces 354
`9.3.4 Normals to Surfaces 354
`9.3.5 Displaying Bicubic Surfaces 355
`9.4 Quadric Surfaces 357
`9.5 Specialized Modeling Techniques 358
`9.5.1 Fractal Models 358
`9.5.2 Grammar-Based Models 363
`SUMMARY 366
`Exercises 367
`
`1 O Solid Modeling
`
`369
`
`10.1 Representing Solids 370
`10.2 Regularized Boolean Set Operations 371
`10.3 Primitive Instancing 375
`10.4 Sweep Representations 376
`10.5 Boundary Representations 377
`10.5.1 Polyhedra and Euler's Formula 378
`10.5.2 Boolean Set Operations 380
`10.6 Spatial-Partitioning Representations 381
`10.6.1 Cell Decomposition 381
`10.6.2 Spatial-Occupancy Enumeration 382
`10.6.3 Octrees 383
`10.6.4 Binary Space-Partitioning Trees 386
`
`

`

`xxvl
`
`Contents
`
`10. 7 Constructive Solid Geometry 388
`10.8 Comparison of Representations 390
`10.9 User Interfaces for Solid Modeling 392
`
`SUMMARY 392
`Exercises 393
`
`11 Achromatic and Colored Light
`11.1 Achromatic Light 395
`11.1 .1 Selection of Intensities 396
`11.1 .2 Halftone Approximation 399
`11 .2 Chromatic Color 402
`11 .2.1 Psychophysics 403
`11.2.2 The CIE Chromaticity Diagram 406
`11 .3 Color Models for Raster Graphics 410
`11.3.1 The RGB Color Model 41 O
`11.3.2 The CMY Color Model 411
`11.3.3 The YIQ Color Model 412
`11 .3.4 The HSV Color Model 413
`11 .3.5 Interactive Specification of Color 417
`11.3.6 Interpolation in Color Space 418
`11.4 Use of Color in Computer Graphics 418
`
`SUMMARY 421
`Exercises 421
`
`12 The Quest for Visual Realism
`12.1 Why Realism? 424
`12.2 Fundamental Difficulties 425
`12.3 Rendering Techniques for Line Drawings 427
`12.3.1 Multiple Orthographic Views 427
`12.3.2 Perspective Projections 428
`12.3.3 Depth Cueing 428
`12.3.4 Depth Clipping 429
`12.3.5 Texture 429
`12.3.6 Color 429
`12.3. 7 Visible-Line Determination 429
`12.4 Rendering Techniques for Shaded Images 430
`12.4.1 Visible-Surface Determination 430
`12.4.2 Illumination and Shading 430
`12.4.3 Interpolated Shading 431
`
`395
`
`423
`
`

`

`Contents
`
`xx vii
`
`12.4.4 Material Properties 431
`12.4.5 Modeling Curved Surfaces 432
`12.4.6 Improved Illumination and Shading 432
`12.4.7 Texture 432
`12.4.8 Shadows 432
`12.4.9 Transparency and Reflection 432
`12.4.10 Improved Camera Models 433
`12.5 Improved Object Models 433
`12.6 Dynamics and Animation 434
`12.6.1 The Value of Motion 434
`12.6.2 Animation 434
`12.7 Stereopsis 437
`12.8 Improved Displays 438
`12.9 Interacting with Our Other Senses 438
`
`SUMMARY 439
`Exercises 440
`
`441
`
`13 Visible-Surface Determination
`13.1 Techniques for Efficient Visible-Surface Algorithms 443
`13. 1 .1 Coherence 443
`13.1.2 The Perspective Transformation 444
`13.1 .3 Extents and Bounding Volumes 446
`13.1.4 Back-Face Culling 448
`13.1 .5 Spatial Partitioning 449
`13.1.6 Hierarchy 450
`13.2 The z-Buffer Algorithm 451
`13.3 Scan-Line Algorithms 454
`13.4 Visible-Surface Ray Tracing 459
`13.4.1 Computing Intersections 460
`13.4.2 Efficiency Considerations for Visible-Surface Ray
`Tracing 462
`13.5 Other Approaches 465
`13.5.1 List-Priority Algorithms 465
`13.5.2 Area-Subdivision Algorithms 468
`13.5.3 Algorithms for Curved Surfaces 471
`SUMMARY 473
`Exercises 474
`
`14 Illumination and Shading
`14.1 Illumination Models 478
`
`477
`
`

`

`xxviil
`
`Contents
`
`14.1 .1 Ambient Light 4 78
`14.1.2 Diffuse Reflection 479
`14.1.3 Atmospheric Attenuation 483
`14.1.4 Specular Reflection 484
`14.1.5 Improving the Point-Light-Source Model 487
`14.1.6 Multiple Light Sources 488
`14.1.7 Physically Based Illumination Models 489
`14.2 Shading Models for Polygons 491
`14.2.1 Constant Shading 492
`14.2.2 Interpolated Shading 492
`14.2.3 Polygon Mesh Shading 493
`14.2.4 Gouraud Shading 494
`14.2.5 Phong Shading 495
`14.2.6 Problems with Interpolated Shading 496
`14.3 Surface Detail 498
`14.3.1 Surface-Detail Polygons 498
`14.3.2 Texture Mapping 498
`14.3.3 Bump Mapping 500
`14.3.4 Other Approaches 501
`14.4 Shadows 501
`14.4.1 Scan-Line Generation of Shadows 502
`14.4.2 Shadow Volumes 503
`14.5 Transparency 505
`14.5. 1 Nonrefractive Transparency 505
`14.5.2 Refractive Transparency 507
`14.6 Global Illumination Algorithms 509
`14.7 Recursive Ray Tracing 510
`
`14.8 Radiosity Methods 514
`14.8.1 The Radiosity Equation 515
`14.8.2 Computing Form Factors 517
`14.8.3 Progressive Refinement 519
`14.9 The Rendering Pipeline 521
`14.9.1 Local Illumination Pipelines 521
`14.9.2 Global Illumination Pipelines 523
`14.9.3 Progressive Refinement 524
`SUMMARY 525
`Exercises 525
`
`Bibliography 527
`Index 545
`
`

`

`36
`
`Programming in the Simple Raster Graphics Package (SRGP)
`
`2.2 BASIC INTERACTION HANDLING
`
`Now that we know how to draw basic shapes and text, our next step is to learn how
`to write interactive programs that communjcate effectively with the user, via input
`devices such as the keyboard and the mouse. First, we look at general guidelines
`for making effective and pleasant-to-use interactive programs; then we discuss the
`fundamental notion of logical (abstract) input devices . Finally, we look at SRGP's
`mechanisms for dealing with various aspects of interaction handling.
`
`2.2.1 Human Factors
`
`The designer of an interactive program must deal with many matters that do not
`arise in a noninteractive, batch progran1. They are the so-called human factors of
`a program, such as its interaction style (often called look and feel) and its case of
`learning and of use, and they are as important as its functional completeness and
`correctness. Techniques for user-computer interaction that exhibit good human
`factors are studied in more detail in Chapter 8. The guidelines discussed there
`include these:
`
`• Provide simple and consistent interaction sequences.
`• Do not overload the user with too many different options and styles.
`• Show the available options clearly at every stage of the interaction.
`• Give appropriate feedback to the user.
`• Allow the user to recover gracefully from mistakes.
`
`We attempt to follow these guidelines for good human factors in our sample pro(cid:173)
`grams. For example, we typically use menus to allow the user to indicate which
`function to execute next, by using a mouse to pick a text button in a menu of such
`buttons. Also common are palettes (iconic menus) of basic geometric primitives,
`application-specific symbols, and fill patterns. Menus and palettes satisfy our first
`three guidelines in that their entries prompt the user with a list of avrulable options
`and provide a single, consistent way of choosing among these options. Unavailable
`options may be either deleted temporarily or grayed out by being drawn in a low(cid:173)
`intensity gray-scale pattern rather than a solid color (see Programming Project
`2.14).
`Feedback occurs at every step of a menu operation to satisfy the fourth guide(cid:173)
`line: The application program will highlight the menu choice or object selection(cid:173)
`for example, display it in inverse video or framed in a rectangle-
`to draw allention
`to it. The package itself may also provide an echo in which an immediate response
`to the manipulation of an input device is given. For example, characters appear
`immediately at the position of the cursor as keyboard input is typed; as the mouse
`is moved on the table or desktop, a cursor echoes the corresponding location on the
`
`

`

`I
`
`Basic Interaction Handling
`
`37
`
`screen. Graphics packages offer a variety of cursor shapes that can be used by the
`appl ication program to reflect tJ1e stale of the program. ln many display systems,
`the cursor shape can be varied dynamically as a function of the cursor's position on
`the screen. Tn many word-processing programs, for example, the cursor is shown
`as an arrow in menu areas and as a blinking vertical bar in text areas.
`Graceful error recovery, our fifth guideline. is usually provided through cancel
`and undo/redo features. They require the application program to maintain a record
`of operations and their inverse, corrective actions.
`
`2.2.2 Logical Input Devices
`
`Device types in SRGP. A major goal in designing graphics packages is device
`independence, which enhances portability of applications. SRGP achieves this
`goal for graphjcs output by providing prin1itives specified in tenns of an abstract
`integer coordinate system , thus shieldjng the application from the need to set the
`inruvidual pixels in the frame buffer. To provide a level of abstraction for graphics
`input, SROP suppons a set of logical input devices that shield the application
`from the details of the physical input devices available. Two logical devices are
`supported by SROP:
`
`• Locator, a device for specifying screen coordinates and the state of one or
`more associated buttons
`• Keyboard, a device for specifying character string input
`
`SRGP maps the logical devices onto the physical devices available (e.g., the
`locator could map to a mouse, joystick, tablet, or touch-sensitive screen). This
`mapping of logical to physical is familiar from conventional procedural languages
`and operating systems, in which 1/0 devices such as terminals, disks, and tape
`drives are abstracted to logical data files to achieve both device-independence and
`simplicity of application programming.
`
`Device ha ndling in other packages. SRGP's input model is essentially a subset
`of the OKS and PHlOS input models. SRGP implementations suppo1t only one
`logical l.ocator and one keyboard device, whereas OKS and PHIGS allow multiple
`devices of each type. Those packages also support additional device types: the
`stroke device (returning a polyline of cursor positions entered with the physical
`locator). Lhe choice device (abstracting a function-key pad and returning a key
`identifier), the valuator (abstracting a slider or control dial and retunung a float(cid:173)
`ing-point number), and the pick device (abstracting a pointing device, such as a
`mouse or data tablet, with an associated bunon to signify a selection, and retuming
`the identification of the logical entity picked). Other packages, such as QuickDraw
`and the X Window System, handle input devices in a more device-dependent way
`that gives the programmer finer control over an individual device's operation, at
`the cost of greater application-program complexity and reduced portability to other
`plarforms.
`
`

`

`38
`
`Programming in the Simple Raster Graphics Package (SRGP)
`
`Chapter 8 elaborates funher on the properties of logical devices. Here, we
`briefly summarize modes of interacting with logical devices in general, and then
`examine SRGP's interaction functions in more detail.
`
`2.2.3 Sampling Versus Event-Driven Processing
`
`Two fundamental techniques are used to receive information created by user inter(cid:173)
`actions. In sampling (also called polling), the application program queries the cur(cid:173)
`rent value of a logical input device (called the measure of the device) and
`continues execution. The sampling is performed regardless of whether the device's
`measure has changed since the last sampling; indeed, only by continuous sampling
`of the device wil l changes in the device's state be known to the application. This
`mode is costly for interactive applications, because they would spend most of their
`CPU cycles in tight sampling loops waiting for measure changes.
`An alternative to the CPU-intensive polling loop is the interrupt-driven
`interaction; in this techojque, the application enables one or more devices for input
`and then continues normal execution until interrupted by some input event (a
`change in a device's state caused by user action); control then passes asynchro(cid:173)
`nously to an interrupt procedure, which responds to the event. For each input
`device, an event trigger is defined; the event trigger is the user action that causes
`an event to occur. Typically, the trigger is a button push, such as a press of the
`mouse button (mouse down) or a press of a keyboard key.
`To free applications programmers from the tricky and difficult aspects of
`asynchronous transfer of control, many g raphics packages, including OKS,
`PHlGS, and SRGP, offer event-driven interaction as a synchronous simulation of
`interrupt-driven interaction. In Lhis technique, an application enables devices and
`then continues execution. ln the background, the package monitors Lhe devices and
`stores information about each event in an event queue (Fig. 2. 11 ). The application,
`at its convenience, checks the event queue and processes the events in temporal
`order. [n effect, the application specifies when it would like to be interrup1ed.
`When an appUcation checks the event queue, it specifies whether it would Like
`to enter a wait state. If the queue contains one or more event reports, the head
`event (representing the event that occurred earliest) is removed, and its informa(cid:173)
`tion is made available to the application. l f the queue is empty and a wait state is
`not desired, the applicaLion is informed that no event is available and that it is free
`to continue execution. If the queue is empty and a wait state is desired, the applica(cid:173)
`tion pauses until the next event occurs or until an application-specified maximum(cid:173)
`wait-tin1e interval passes. In effect, event mode replaces polling of the input
`devices with the much more efficient waiting on the event queue.
`In summary, in sampling mode, the device is polled and an event measure is
`collected, regardless of any user activity. ln event mode, the application either gets
`an event report from a prior user action or waits until a user action (or timeout)
`occltrs. It is this respond only when the user acts behavior of event mode that is the
`essential difference between sampled and event-driven input. Event-driven pro(cid:173)
`gramming may seem more complex than sampling, but you are already familiar
`with a similar technique used with the scanf function in an interactive C program:
`
`

`

`r
`
`we
`1en
`
`~r(cid:173)
`ur(cid:173)
`
`tnd i: fiis
`
`teir
`
`en
`put
`(a
`ro-
`pur
`es
`e
`
`of
`s.
`
`Basic Interaction Handling
`
`39
`
`Commands:
`setlnputMode
`sel<attribute>
`waitEvent
`
`Application
`program
`
`sample<device>
`
`Device
`handler
`
`Mouse
`
`Figure 2.11
`
`Sampling versus event-handling using the event queue.
`
`C enables the keyboard, and the application waits in the scanf until the user has
`completed entering a line of text. Some environments allow the scanf statement to
`access characters that were typed and queued before the scanf was issued.
`Simple event-driven programs in SRGP and in similar packages follow the
`reactive pi11g-po11g interaction inlroduced in Section l.4.3 and pseudocoded in
`Prog. 2.4; this interaction can be nicely modeled as a finite-state automaton. More
`complex styles of interaction, allowing simultaneous program and user activity,
`are discussed in Chapter 8.
`
`Program2.4
`
`Event-driven interaction
`scheme.
`
`initialize, including generating the initial image;
`activate interactive device(s) in event mode;
`do {
`f main event loop*/
`wait for user-triggered event on any of several devices;
`switch ( which device caused event) {
`case DEVICE_ 1: collect DEVICE_ 1 event measure data, process, respond;
`case DEVICE_2: collect DEVICE_2 event measure data, process, respond;
`
`}
`while ( user does not request quit);
`
`Event-driven applications typically spend most of their time in a wait stale,
`since interaction is dominated by think time during wh ich tl1e user decides what to
`do next; even in fast-paced game applications, the number of events a user can
`generate in a second is a fraction of what the application could handle. Since
`SRGP typically implements event mode using true (hardware) inlem1pts, the wait
`state effectively uses no CPU time. On a multitasking system, the advantage is
`obvious: The event-mode application requires CPU time only for short bursts of
`
`

`

`40
`
`Programming in the Simple Raster Graphics Package (SRGP)
`
`activity immediately folJowing user action, thereby freeing the CPU for other
`tasks.
`One other point, about correct use of event mode, should be mentioned.
`Although the queueing mechanism docs allow program and user to operate asyn(cid:173)
`chronously, the user should not be allowed to get too far ahead of the p rogram,
`because each event should result in an echo as well as some feedback from the
`application program. It is true that experienced users have learned to use typea(cid:173)
`head to type in parameters such as file names or even operating-system commands
`while the system is processing earlier requests, especially if at least a character-by(cid:173)
`character echo is provided immediately. In contrast, mouseahead for graphical
`commands is generally not as useful (and is much more dangerous). because the
`user usually needs to see the screen updated to reflect the application model's cur(cid:173)
`rent state before the next graphical interaction.
`
`2.2.4 Sample Mode
`
`Activating, deactivating, and setting the mode of a device. The foUowing
`function is used to activate or deactivate a device; taking a device and a mode as
`parameters:
`
`void SRGP _setlnputMode ( inputDevlce LOCATOR / KEYBOARD,
`inputMode INACTIVE / SAMPLE / EVENT);
`
`Thus, to set the locator to sample mode, we call
`
`SRGP _setlnputMode (LOCATOR, SAMPLE);
`
`lnitiaJJy, both devices are inactive. Placing a device in a mode in no way affects the
`other input devico-both may be active simultaneously and even then need not be
`in the same mode.
`
`The locator 's m easure. The locator is a logical abstraction of a mouse or data
`tablet, returning the cursor position as a screen (x, y) coordinate pair, the number of
`the button that most recently experienced a transition, and the state of the buttons
`as a chord array (since multiple buttons can be pressed simultaneously). The sec(cid:173)
`ond field lets rhe application know which button caused the trigger for that event.
`
`typedef struct {
`point position;
`enum {
`UP, DOWN
`} buttonChord!MAX_BUTTON_COUNT];
`int buttonOfMostRecentTransition;
`} locatorMeasure;
`
`!'Typically 1-3*/
`
`Having activated the locator in sample mode with the SRGP _setlnputMode ftmc(cid:173)
`tion. we can ask its current measure using
`
`void SRGP _sampleLocator ( locatorMeasure *measure);
`
`

`

`plher
`
`eel.
`
`the
`.ur-
`
`.ng
`as
`
`Program2.5
`
`~~ ng loop for painting,
`
`Basic Interaction Handling
`
`41
`
`Let us examine the prototype sampling application shown in Prog. 2.5, a simple
`painting loop involving only button I on the locator. Such painting entails leaving
`a trail of paint where Lhe user has dragged the locator while holding down button l;
`lhe locator is sampled in a loop as lhc user moves it. Pirst, we must detect when the
`user starts painting by sampling the button until it is depressed; then we place the
`paint (a filled rectangle in our simple example) at each sample point until the user
`releases the button.
`
`set up color/pattern attributes, and brush size in halfBrushHeight and halfBrushWidth
`SRGP _setlnputMode(LOCATOR, SAMPLE);
`r First, sample until the button goes down.*/
`do {
`SRGP _samplelocator(locMeasure);
`} while (locMeasure.buttonChord[0) == UP);
`
`/*Perform the painting loop:
`Continuously place brush and then sample, until button is released.*/
`
`do {
`rect = SRGP _defRectangle( locMeasure.position.x - halfBrushWidth,
`locMeasure.position.y - halfBrushHeight,
`locMeasure.position.x + halfBrushWidth,
`locMeasure.position.y + halfBrushHeight );
`SRGP _fillRectangle (rect );
`SRGP _samplelocator( &!ocMeasure );
`} while ( !ocMeasure.buttonChord[0] == DOWN );
`
`The results of this sequence are crude: The paint rectangles are arbitrarily
`close together or far apart, with the ir density completely dependent on how far the
`locator was moved between consecutive samples. The sampling rate is determined
`essentially by the speed al which the CPU runs the operating system, the package,
`and the application.
`Sample mode is available for both logical devices; however, the keyboard
`device is almost always operated in event mode, so techniques for sampling it are
`not addressed here.
`
`2.2.5 Event Mode
`
`Using event mode for initiation of sampling loop. Although the two sampling
`loops of the painting example (one to detect the bunon-down transition, the other
`to paint until the button-up transition) certainly do the job, they put an unnecessary
`load on the CPU. Although overloading may not be a serious concern in a personal
`computer, it is not advisable in a system running multiple tasks, let alone doing
`time-sharing. Although it is certainly necessary to sample the locator repetitively
`for the painting loqp itself (because we need to k.now the position of the locator at
`aJI times while the button is down), we do not need to use a sampling loop to wait
`for the button-down event that initiates the painting interaction. Event mode,
`
`

`

`42
`
`Programming in the Simple Raster Graphics Package (SRGP)
`
`discussed next, can be used when there is no need for measure information while
`waiting for an event.
`
`SRGP waitEvent. At any time after SRGP _setlnputMode has activated a
`device in event mode, the program may inspect Lhe event queue by entering the
`wait slate with
`
`lnputDevice SRGP _waitEvent ( Int maxWaitTime );
`
`The function returns immediately if the queue is not empty; otherwise, the param(cid:173)
`eter specifies the maximum amount of time (measured in 1/oo second) for which the
`function should wait for an event to fill the queue. A negative maxWaitTime (spec(cid:173)
`ified by the symbolic constant 1NDEFIN1TE) causes the function to wait indefi(cid:173)
`nitely, whereas a value of zero causes it to return immediately, regardless of the
`state of the queue.
`The function retu