CONTENTS
Preface xi
1 Geometry and Line Generation l
Introduction 1
Lines 3
Line Segments 5
Perpendicular Lines 7
Distance between a Point and a Line 8
Vectors 10
Pixels and Frame Buffers 11
Vector Generation 11
Bresenham's Algorithm 17
Antialiasing of Lines 20
Thick Line Segments 21
Character Generation 22
Displaying the Frame Buffer 24
Further Reading 26
Exercises 27
Programming Problems 29
2 Graphics Primitives 33
Introduction 33
Display Devices 34
Primitive Operations 37
The Display-File Interpreter 40
Normalized Device Coordinates 41
Display-File Structure 42
Display-File Algorithms 45
Display Control 47
Text 49
The Line-Style Primitive 55
An Application 57
Further Reading 60
Exercises 61
Programming Problem 63
3 Polygons 70
Introduction i 70
Polygons 70
Polygon Representation 71
Entering Polygons 72
An Inside Test 74
Polygon Interfacing Algorithms 76
Filling Polygons 79
Filling with a Pattern 91
Initialization 93
Antialiasing 94
An Application 94
Further Reading 96
Exercises 97
Programming Problems 99
4 Transformations 107
Introduction 107
Matrices 107
Scaling Transformations 109
Sin and Cos 112
Rotation 113
Homogeneous Coordinates and Translation 116
Coordinate Transformations 118
Rotation about an Arbitrary Point 119
Other Transformations 120
Inverse Transformations 122
Transformation Routines 125
Transformations and Patterns 131
Initialization 136
Display Procedures 136
\n Application 139
Further Reading 140
Exercises 141
Programming Problems 143
5 Segments 146
Introduction 146
The Segment Table 147
Segment Creation 149
Closing a Segment 150
Deleting a Segment 150
Renaming a Segment 153
Visibility 154
Image Transformation 155
Revising Previous Transformation Routines 157
Saving and Showing Segments 159
Other Display-File Structures 161
Some Raster Techniques 163
An Application 165
Further Reading 166
Exercises 167
Programming Problems 169
6 Windowing and Clipping 172
Introduction 172
The Viewing Transformation 173
Viewing Transformation Implementation 178
Clipping 181
The Cohen-Sutherland Outcode Algorithm 182
The Sutherland-Hodgman Algorithm 184
The Clipping of Polygons 190
Adding Clipping to the System 195
Generalized Clipping 196
Position Relative to an Arbitrary Line 197
Multiple Windowing 198
An Application 199
Further Reading 200
Exercises 201
Programming Problems 202
7 Interaction 205
Introduction 205
Hardware 206
Input Device-Handling Algorithms 211
Event Hanclli ng 214
Sampled Devices 221
The Detectability Attribute 222
Simulating a Locator with a Pick 225
Simulating a Pick with a Locator 225
Echoing 230
Interactive Techniques 230
Further Reading 239
Exercises 241
Programming Problems 242
8 Three Dimensions 244
Introduction 244
3D Geometry 244
3D Primitives 249
3D Transformations 251
Rotation about an Arbitrary Axis 256
Parallel Projection 261
Perspective Projection 264
Viewing Parameters 268
Special Projections 276
Conversion to View Plane Coordinates 279
Clipping in Three Dimensions 285
Clipping Planes 290
The 3D Viewing Transformation 298
An Application 302
Further Reading 304
Exercises 305
Programming Problems 308
9 Hidden Surfaces and Lines 311
Introduction 311
Back-Face Removal 312
Back-Face Algorithms 316
Z Buffers 319
Scan-Line Algorithms 320
The Painter's Algorithm 321
Comparison Techniques 322
Warnock's Algorithm 323
Franklin Algorithm 325
Hidden-Line Methods 326
Binary Space Partition 327
An Application 341
Further Reading 341
Exercises 342
Programming Problems 343

10 Light, Color, and Shading 345
Introduction 345
Diffuse Illumination 345
Point-Source Illumination 348
Specular Reflection 349
Shading Algorithms 355
Smooth Shading of Surface Approximations 362
Transparency 365
Reflections 367
Shadows 368
Ray Tracing 370
Halftones 372
Color 376
Color Models 379
Gamma Correction 388
Color Tables 389
Extending the Shading Model to Color 390
Further Reading 391
Exercises 394
Programming Problems 395
11 Curves and Fractals' 397
Introduction 397
Curve Generation 397
Interpolation 400
Interpolating Algorithms 404
Interpolating Polygons 409
B Splines 410
B Splines and Corners 415
Curved Surface Patches 417
Bezier Curves 420
Fractals 424
Fractal Lines 427
Fractal Surfaces 431
An Application 435
Further Reading 437
Exercises 441
Programming Problems 442
Appendixes 444
A Information Guide 444
B Pidgin Algol 447
C Graphics on an Alphanumeric Terminal 453
Index 459