A
`
`‘A
`
`ot
`
`7
`
`“_
`
`2
`
`It
`
`l a
`
`C
`=
`—
`
`
`Ta
`
`———eeeeSS|
`
`2 Nn< -
`
`i
`if
`
`79
`4
`
`Te
`
`SS =
`
`0001
`
`Exhibit 1015 page 1 of 65
`DENTAL IMAGING
`
`

`

`
`
`ISBN O-201-6b05921-
`90100>
`| |
`|
`780201'609219
`
`
`
`0002
`
`0002
`
`Exhibit 1015 page 2 of 65
`DENTAL IMAGING
`
`

`

`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
`
`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
`
`0003
`
`Exhibit 1015 page 3 of 65
`DENTAL IMAGING
`
`

`

`Sponsoring Editor Peter S. Gordon
`Seni r Pr duction Sup 1vi or Jim Rigne
`Copy Erut r
`Lyn Dupre and Joyce Grandy
`Te t De igner Sandra Ri mey
`Technical Art C n ultant Joseph K. Verere
`trator C&C A sociale and Tech Graphics
`Ill
`Cover D ·igner Eileen Hoff
`anager Roy Logan
`enior
`anufacturing
`Marketing Manager Robert Donegan
`
`Cover image fr m "Lu· o Jr.," by J. Las ·eter W. Re ve , E. 0 tby,
`. Leffler. ( opyright © 19 6 Pixar.) "Lu
`" i a trademark of
`and
`Ja Jacob en lndustricr.
`
`f Computer Graphic : Principles
`Thi book is an abridged and modi.fied ver ion
`and Practice, S cond Edi tion, by oley, van Dam, Feiner. and Hughe , publi hed
`in 1990 in the Addison-We lcy Sy tems Programming Serie , IBM Editorial
`Board, con ulting editors.
`
`lany of 1he designations u ed by manufacturers and eller 10 dislingui h Lheir product arc
`cJajn,ed a Lrademarks. Where tho e designations appear in this book, and ddi on-W
`Icy
`wru, aware fa trad mark claim. the de ·igaations have been printed in ini1ial cap. or all cap .
`
`The program and appLi ation presented in I.hi ' book have been included f rtheir instru tional
`value. The are n t 0 uaranteed r r any panicular purpo e. The pub Ii. her and th author do aot
`offer any warranties or rcpreseatations. nor do they accept any Liabiliti with respect to the
`r appli ation ·.
`program
`
`Librar of Congre Cataloging-in-Publication data
`
`Introduction to computer graphic / Jame D. Foley . . . f r al.] . ].
`p. cm.
`Include bibliographical reference and index.
`[SB 0-20 1-6092 l -5
`l. Computer graphic .
`T385.153
`1993
`006.6-dc20
`
`l. Foley, Jame D. 1942-
`
`93- 16677
`CIP
`
`Reprinted with corrections February, 1994
`
`Copyright © 1994. 1990 by Addi on-Wesley Publi ' hing ompany, Inc .
`
`AU right reserved. No part ofthi publication may b reproduced , stored in a reLrieval
`• rem,
`or mm mitted, in any fom, orb any means, el ctronic, mechanical, photo opying, recording,
`orotherwi c, wiLhout rhe prior written permission oi'thc publisher. Printed in the nited State ·
`of mericn
`
`4 S 6 7
`
`9 10
`
`9 97969594
`
`0004
`
`Exhibit 1015 page 4 of 65
`DENTAL IMAGING
`
`

`

`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 lnJeractive 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
`
`0005
`
`Exhibit 1015 page 5 of 65
`DENTAL IMAGING
`
`

`

`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
`
`0006
`
`Exhibit 1015 page 6 of 65
`DENTAL IMAGING
`
`

`

`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.1 O 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
`
`0007
`
`Exhibit 1015 page 7 of 65
`DENTAL IMAGING
`
`

`

`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 2D Transformations 168
`5.3 Homogeneous Coordinates and Matrix Representation of 20
`Transformations 170
`5.4 Composition of 2D Transformations 175
`5.5 The Window-to-Viewport Transformation 177
`5.6 Eff iclency 179
`5.7 Matrix Representation of 3D Transformations 180
`5.8 Composition of 3D 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 3D Viewing 193
`6.2 Projections 195
`6.2.1 Perspective Projections 197
`6.2.2 Parallel Projections 198
`6.3 Specification of an Arbitrary 3D 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
`
`0008
`
`Exhibit 1015 page 8 of 65
`DENTAL IMAGING
`
`

`

`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
`
`239
`
`Exercises 235
`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
`
`0009
`
`Exhibit 1015 page 9 of 65
`DENTAL IMAGING
`
`

`

`xxiv
`
`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
`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 3D 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
`
`297
`
`0010
`
`Exhibit 1015 page 10 of 65
`DENTAL IMAGING
`
`

`

`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
`
`369
`
`1 Q Solid Modeling
`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
`
`0011
`
`Exhibit 1015 page 11 of 65
`DENTAL IMAGING
`
`

`

`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 410
`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
`
`0012
`
`Exhibit 1015 page 12 of 65
`DENTAL IMAGING
`
`

`

`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.1 O 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
`
`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 tor 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
`
`441
`
`477
`
`0013
`
`Exhibit 1015 page 13 of 65
`DENTAL IMAGING
`
`

`

`xxvill
`
`Contents
`
`14.1.1 Ambient Light 478
`14.1.2 Diffuse Reflection 4 79
`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
`
`0014
`
`Exhibit 1015 page 14 of 65
`DENTAL IMAGING
`
`

`

`36
`
`Programming in the Simple Raster Graphics Package (SRGP)
`
`2.2 BASIC INTERACTION HANDLING
`
`and texr, our next t pis ro learn how
`ow that \i e know how ro draw basic hap
`to write interactive program that communicate effectively with Lhe u er via input
`look at g neral guidelines
`device· uch a the keyboard and tbe mou e. First, w
`for making effective and ple ant-to-u e inteiactiv program · then we discu
`the
`fundamental noti n of logical (ab tra t) input de ice . Finally, we look at RGP'
`mechani. m ~ r dealing wilh variou a p
`ts of interaction handling.
`
`2.2.1 Human Factors
`
`The designer of an interactive program mu ·t deal with many matters that do not
`ari e in a noninteractive, batch program. They are the o-called human factors of
`a pr gram u ha it intera tio,1 tyle (often called look and f'e I) and i ca e of
`learning and f u e and th y are
`it functional completene
`imp rtant a
`and
`corTeclness. Techniques for u er-computer interaction that exhibit good humnn
`tudied in m r detail in
`hapter 8. Th guideline di cus ed there
`facto, are
`in Jude these:
`
`■ Provjde simple and consistent int racti n equ nee .
`■ Do not overload the user with too many different options and tyle .
`■ Show the available option clearly at every tag of the interaction.
`■ Give appropriacefeedback to the u · r.
`
`■ Allow the u er to recover gracefully from mistak
`
`e attempt to foll w the e guideline for good human factor
`in our ample pro(cid:173)
`gram . For example, we 1ypically us menus to aUow the u er t
`indicate " hi<.:h
`function to exc ute next, by u ing a mouse to pick a I
`t button in a menu o su h
`button . Also common ar palettes (iconic menu ) f basic geometric primitives,
`ati fy our fir L
`application- pccific ymbol , and fill pattern .
`nu and pal rt
`three guideline in that their ntrie prompt the user with a li t of available option
`and provide a in •le, con. isL nt way of hoo ing am ng the e options. Unavai lable
`irher deleted temporarily r grayed 0111 by being drawn in a low(cid:173)
`option may b
`inten ily gray- cale pattern rather Lhan a olid olor ( ee Programming Proj ct
`2.14).
`Feedback occur at every step of a menu operation to satisfy the fourth guide(cid:173)
`lfoe: The appli at ion program will highlight the menu hoic or object elccri n(cid:173)
`to draw atlemion
`for example di play it in in erse video r framed in a rectangl
`to it. The packag itself may al o provid an echo in which an immediate re p n ·e
`to the manipul ation of an input dev ic
`i given. For c ampl , haracter app ar
`immediately at the po ition of the cur or a keyboard input is typed· a th mou e
`is moved on the table or de ktop a cur or ecboe th corresponding location on th
`
`0015
`
`Exhibit 1015 page 15 of 65
`DENTAL IMAGING
`
`

`

`Basic Interaction Handling
`
`37
`
`pa kage offer a va.riecy of cur or hap · that can be u ed by lhe
`creen. Graphj
`app lication program to refle I the -rate of the program. ln many di play systems,
`the ur or bape an b vari d dynamically as a function f the cur or' po ition on
`the ere n. [n many word-proce
`ing program-, for example, th
`ur or i
`. hown
`as an arrow in menu areas and as a bLinking vertical bar in text area .
`Graceful error recovery, our fifth ujdeline, i u ually provided lhrougb cancel
`and undo/redo feature . They require the application program to maintain a record
`of op ration and their inver, e, con
`tive action .
`
`2.2.2 Logical Input Devices
`
`Device types in RGP.
`major goal in de ·igning grnphic pa kages i devi e
`independence, which enhances portability of application . RGP achiev
`Lhi
`goal for graphi
`utput by providing primitiv
`speci.fi d in term of an abstract
`integer c ordinate sy tern , thus shielding the application from the need to ct lhe
`individual pixel
`in the frame buffer. To provid a level of ab traction for 0 raphi
`input, SRGP uppon a et of logical input d
`ice
`that hield he application
`from the derajls o· the phy ical input device wailable. Two logical device are
`upported by SR P:
`
`■ Locator
`device for p cifying creen coo.rdinat
`more a ociated butt ns
`■ Kc board a devic for pecifying charac~ r string input
`
`and the • tate of ne or
`
`SRGP map the logical device onto the physical devices available (e.g., the
`tick, tabl t or tou h- en itive crecn). This
`locator could map to a mou e. jo
`mapping of logical to phy ical i · familiar from
`nventionaJ pr cedural languages
`in which I/0 device
`and op rating y terns
`uch a
`t nninal , disks, and lape
`drive ' are ab tracted to I gi al data file
`to a hicve both dcvi.ce-independen
`and
`implicity of application programming.
`
`in other package . SRGP' input model i e entinlly a ub el
`Device handlin
`of the GKS and PHlGS input model . SRGP implementation
`uppo1t onl one
`logical Locator and one keyboard dcvic , wh reas OKS and PHIG allow multiple
`of each type. Th e package also ·upport additional device type : the
`devic
`f cursor po ition entered wirh the pby. ical
`troke dcvke (r turning a polyline
`locaLOr . the choice device ab tra ting a fun lion-key pad and r turning a key
`identifi r), the valuator (abstracting a Jider or ontrol dia] and r turning a float(cid:173)
`ing-point number), and th pick devi e (ab lracting a pointing d vice uch a a
`mou e or data tablet with an associal d button to signify a election. and .returning
`the identification of the logical entity picked). Other packages, such a Quick.Draw
`and th X Window System, banciJe Lnpur device in a mor device-dependent way
`lh programm r finer conlrol over an individual device'
`that gi
`peration at
`the co t of greater appli aLion-program complexity and reduced portability to other
`plalforms.
`
`0016
`
`Exhibit 1015 page 16 of 65
`DENTAL IMAGING
`
`

`

`38
`
`Programming in the Simple Raster Graphics Package (SAGP)
`
`f logical devices. Her we
`laborates funher on the properrie
`Chapter
`in g neral, and Lhen
`briefly ummariz modes of interacting with logical d vice
`examine SRGP' int raction functions in more detail.
`
`2.2.3 Sampling Versus Event-Driven Processing
`
`Two fundamental technique-~ are used to re eive in.formation created by u er inter(cid:173)
`action . ln sampling (also called polling) U,e application program querie the cur(cid:173)
`rent
`aJu of a logical input device (called the m asure of the de ice) and
`continue execution. The amp ling i performed regardle of whether the de i e'
`measure has changed since the last sampling; indeed, only by conti nuous sampling
`of Lhe d vice will changes in ihe device' state be known to the application. Thi
`mode i co tly for iotcractiv application , becau e th y would ·pend mo t of lheir
`CPU cycles in tight ampling loops waiting for measure change .
`interrupt-driven
`An al ternative to the PU-intensive polling loop is th
`interaction ; in thi technique the appli atio11 enables one or mor devices for input
`and then continue nonnal e ecuti.on until interrupted by ome inpul e enl (a
`change in a device
`late aused by user action); control then pa · e asynchro(cid:173)
`nous ly to an in terrupt procedur , whi h re ponds Lo the evenL For each inpul
`device, an event trigger i defined; th ev nt trigger i the u er action that aus
`an e ent to o cur. Typically. cbe trigger i a button pu h ucb
`a pr
`of the
`mou e button (mou e down) or a pres of a eyboard key.
`~ free applications pr grammer from the tricky and difficult aspects of
`asynchronous tran fer of control, many graphic packages, including OKS,
`PHIO , and SRGP offer e ent-dri en intera tion a a ynchronou
`imularion of
`interrupt-driven interaction. In tbi
`technique, an application enable de ices and
`th n continue exc ution. 1n the background, the package monitor · the device. and
`tores information about each event in an event queue (Fig. 2. 11 ). The appli ation
`al it
`onvenience heck th event queue and pro
`the ev nc
`in remp ral
`order. In effect th application pecifie when it would like to be imerrupied.
`When an application che k the event queue it p cifies whether il would like
`late. If the queue contain · one or more event reports the head
`to enter a wait
`i. removed, and iLS in~ m1a(cid:173)
`event (repre enting U1e event that occurr d earlie t
`tion i made a ailnble to th application. If the queue i empty and a wait
`tat i
`not de ired, the application i informed that no event i avaiJable and that it i free
`to continue execuLion. If the queue is emply and a wait tate i d
`ired, the applica(cid:173)
`tion pau
`until the next ev nt ccurs or until an appli arioo- p
`ificd maximum(cid:173)
`wait-time intervaJ pa es. In effect, event mode replace polling of the input
`devi e with the much more ef6cienl wai ting on the cv nt queue.
`In ummary, in , ampling mode, th device i p li ed and an event measure i
`collected regardle of any u er activity. ln event mode, the appli ation either gets
`an event repo11 fr m a prior u er a Lion or wait until a u er a tion (or timeout
`oc ur . ft is thi respond only when the us r acts behavior of event mode that is the
`essential different: between umpled and event-driv n input. Evenl-driven pro(cid:173)
`gramming may eem more complex than ampling but you arc already familiar
`wilh a imilar te ·hnique u d with the anf function in an interacti e C program:
`
`0017
`
`Exhibit 1015 page 17 of 65
`DENTAL IMAGING
`
`

`

`n
`
`r(cid:173)
`ur-
`
`ir
`
`n
`Ut
`(a
`to-
`
`. ,.
`
`Basic Interaction Handling
`
`39
`
`Commands:
`setlnputMode
`set<attrtbuie>
`waitEvent
`
`Application
`program
`
`sample<device>
`
`Device
`handler
`
`Mouse
`
`Figure 2.11
`
`Sampling versus event-handling using the event queue.
`
`Program2.4
`
`Event-driven interaction
`scheme.
`
`C enables the keyboard, and the application waits in th scanf until rhe u er ha
`completed entering a line of text. ome environments allo
`can£ tatement to
`th
`acce character that wer typed and queued before the canf wa i sued.
`in SRGP and in
`implc event-driven progran
`imilar pa kage
`follow the
`reacLive pin •-pong intera 1ion introduced in Section 1.4.3 and p eud cod d in
`Frog. 2.4; this interaction can be nicely modeled as a finite-state automaton. M re
`complex tyl of interacti n, aUowing
`imuJtan u pr gram and u er activity
`are djscus ·cd i□ Chapter 8.
`
`initialize, including generating the initial image;
`activate interactive device(s) in event mode;
`r main event loop 'I
`do {
`wait for user-triggered event on any of several devices;
`switch ( which device caused event) {
`case DEVJCE_1 : co/lectDEVICE_1 event measure data process, respond;
`case DEVICE_2: collect DEVICE_2 event measure data, process, respond;
`
`}
`while ( user does not request quit);
`
`in a wait
`typically pend mos1 of Lhcir tim
`tate.
`Event-driven applica1ion
`ince interaction i dominated by think time during which Lhe u ·er decide what to
`do next; even in fa t-paced game application
`th number of event a user can
`generate in a sec nd i a fraction of what the application could handle. Since
`SRGP typically implement event mode u ing true (hardware) interrupts, the ~ ait
`stat effe tively u e no PU time. On a multita king y tern the ad antag
`i,
`obvio □ s: The event-mode applica tion requires PU time only for short bw- ts of
`
`0018
`
`Exhibit 1015 page 18 of 65
`DENTAL IMAGING
`
`

`

`40
`
`Programming in the Simple Raster Graphics Package (SRGP)
`
`r a tion. thereby .freeing the PU for other
`
`a ti ity imm diat ly 6 Jlowing u
`ta k.
`One other point, about corre t u
`of vent mod , sh uld b memion d.
`Although the queueing, mechanism doe allow program and user to operate a yn(cid:173)
`chronou ly, the u er should nor b allowed t g_et too far ahead of the program,
`becau e each event h uld re ult in an echo
`well as ome feedback from the
`application program. It i t11.1
`that exp ri.enc d us rs have learned to u ' C typea-
`head to type in parameter uch as file nam or even operating-
`t m c mmand
`whi le the sy tern i proce sing earlier reque ts, c p cially if at I ast a character-by(cid:173)
`character echo i provided immediat ly. In contra 1., mou ahead for graphi al
`command
`is genentlly not a usefuJ (and is much more dangerou ·), because tbe
`u er u ually need to ee the creen updated t refl ct th application model
`ur(cid:173)
`rem state before the ne l graphical int raction.
`
`2.2.4 Sample Mode
`
`cti ating deacti ating, and setting the mode of a de ice. The following
`function is u ·ed to activate or deactivate ad vice; takin a dcvi e and a mode a
`param l r:
`
`void SRGP _setlnputMode ( lnputDevlce LOCATOR / KEYBOARD,
`lnputMode INACTIVE/ SAMPLE/ EVENT);
`
`Thu , to set the locator to sample mode, we call
`
`SRGP _setlnputMode (LOCATOR, SAMPLE)·
`
`lniLially, both devices are inactive. Placing a dev ice in a mode in no way affect the
`imullaneou Ly and ven then need not be
`other i.nput devico--both may be ,l tiv
`in the ame mode.
`
`T he locator m ea u r • The locator i a Logical ab traction of a mous or data
`tablet returning the cur or po ition as a creen (x, y) coordinat pair the number of
`the button that mo t re ently exp rienced a tran ition, and th
`tale of the button
`can be pr
`· a chord array ( ince multiple bu110
`ed imultaneou ly . The ec(cid:173)
`ond field let the application know which bullo n caused the trigger for tbat event.
`
`typedef struct {
`point position;
`enum {
`UP, DOWN
`} buttonChord[MAX_BUTTON_COUNT];
`int buttonOIMostRecentTransition;
`} locatorMeasure;
`
`rTypically 1-3 I
`
`H av ing acti ated the locator in ample mode with the SRGP _ etlnputMode func(cid:173)
`tion , we can a k it current measure using
`
`void SRGP _sampleLocator ( locatorMeasure *measure);
`
`0019
`
`Exhibit 1015 page 19 of 65
`DENTAL IMAGING
`
`

`

`er
`
`g
`
`Basic Interaction Handling
`
`41
`
`Let us e amine the prol rype ampling application hown in Prog. 2 .. a simple
`pain1ing loop involving only button I on the locator. Such painting entails leaving
`a trail of pain where Lhe user has dragged the locator while holding down button l;
`Lhe locator i ampled in a loop a the u er move· it. PirsL, we mu t detect when the
`u er start painting by ampling the button until it i depr s cd· then w place th
`painl (a filled rectangle in our irnpl example) al each sample point until the user
`relca es the button.
`
`Program2.5
`
`·ng loop for painting.
`
`set up color/pattern attributes, and brush size in halfBrushHeight and ha/fBrushWidth
`SRGP _setlnputMode(LOCATOR, SAMPLE);
`
`t First, sample until the buttoh goes down ."/
`do {
`SRGP _samplelocator(locMeasure);
`} while (locMeasure.buttonChord[0J "'"" UP);
`
`/" Perform the painting loop:
`Continuously place brush and then sample, until button is released.*/
`
`do {
`reel = SRGP _def Rectangle( locMeasure.posltion.x - halfBrushWidth
`locMeasure.posltlon.y - halfBrushHeight,
`locMeasure.position.x + hal!BrushWidth,
`locMeasure.position.y hal!BrushHeight )·
`SRGP _fillRectangle (rec! );
`SRGP _sampleLocator( &locMeasure );
`} while ( locMeasure.buttonChord[0J == DOWN );
`
`equence are crude: The paint rectangles are arbitrarily
`The re: ult of r.hl
`together or far apart, with Lheir den ity ompletely dep nd nt on how far the
`clo
`locator wa · m ved between consecutive sample . The sampling rate is detennined
`entialiy by the peed al which th CPU run 1J1e operating ·ystem, ch package,
`and the applicatjon.
`Sample mode is available for both logical devices; however, the keyboard
`d vice is almost alway operated in event mode, so technique · for sampling it are
`not addre eel here.
`
`2.2.5 Event Mode
`
`ing e ent mode for initiation of ampling loop . Although the two ampling
`loop of the painting e mnple (one to detect the bunon-down tran ition, th other
`to paint until the button-up transition) certainly do the job th y put an unnecessary
`load on the P . Although overloading may not be a eriou concern in a per onaJ
`omputer, it i not advi able in a y tern running multipl
`ta. k · let alone doing
`time-sharing. Although it i certainly nece sary to ampl
`the locator rep Litively
`fo r the painting loqp itself (because we need to know I.he p sition of the locator at
`alJ tim · whil the button i down) we do not need to use a ampling loop to wait
`for the button-down event that initiate
`the painting int r
`tion. Event mode,
`
`0020
`
`Exhibit 1015 page 20 of 65
`DENTAL IMAGING
`
`

`

`42
`
`Programming in the Simple Raster Graphics Package (SRGP)
`
`di. u ed ne ·1 can be u ed when there i no need for mea ure .information while
`wairing for an event.
`
`R P _ wait
`ent. AL any time after RGP _ erlnputMode Ir
`acti ated a
`in peel the vent queu by entering lhe
`de i e in event mode. the pr gram ma
`wait slate with
`
`inputDevice SRGP _waitEvent ( Int maxWaitnme );
`