计算机图形学的算法基础 英文版PDF电子书下载

1-1 Overview of Computer Graphics 1

Chapter 1 Introduction To Computer Graphics 1

Representing Pictures 2

Preparing Pictures for Presentation 2

Presenting Previously Prepared Pictures 3

1-2 Raster Refresh Graphics Displays 6

Frame Buffers 7

1-3 Cathode Ray Tube Basics 11

Color CRT Raster Scan Monitors 13

1-4 Video Basics 14

American Standard Video 14

High Definition Television 17

1-5 Flat Panel Displays 17

Flat CRT 17

Plasma Display 18

Liquid Crystal Display 21

Electroluminescent Display 21

1-6 Hardcopy Output Devices 25

Electrostatic Plotters 25

Ink Jet Plotters 26

Thermal Plotters 28

Dye Sublimation Printers 30

Pen and Ink Plotters 31

Laser Printers 34

Color Film Cameras 36

1-7 Logical Interactive Devices 37

The Locator Function 38

The Valuator Function 39

The Buttom or Choice Function 39

The Pick Function 39

1-8 Physical Interactive Devices 39

Tablets 40

Control Dials 41

Touch Panels 41

Joystick 42

Trackball 42

Mouse 44

Function Switches 44

Light Pen 45

Spaceball 46

Data Glove 46

Simulation of Alternate Devices 47

1-9 Data Generation Devices 49

Scanners 49

Three-dimensional Digitizers 50

Motion Capture 51

1-10 Graphical User Interfaces 52

Cursors 54

Valuators 55

Radio Buttons 55

Scroll Bars 56

Grids 56

Dialog Boxes 57

Menus 58

Icons 59

Sketching 60

3-D Interaction 63

Summary 64

Chapter 2 Raster Scan Graphics 65

2-1 Line Drawing Algorithms 65

2-2 Digital Differential Analyzer 66

2-3 Bresenham s Algorithm 70

Integer Bresenham s Algorithm 74

General Bresenham s Algorithm 75

Faster Line Rasterization Algorithms 78

2-4 Circle Generation—Bresenham s Algorithm 79

2-5 Ellipse Generation 88

2-6 General Function Rasterization 95

2-7 Scan Conversion—Generation of the Display 97

Real-time Scan Conversion 97

A Simple Active Edge List Using Pointers 99

A Sorted Active Edge List 99

An Active Edge List Using a Linked List 101

Updating the Linked List 102

2-8 Image Compression 104

Run-length Encoding 104

Area Image Compression 107

2-9 Displaying Lines,Characters and Polygons 111

Line Display 111

Character Display 113

Solid Area Scan Conversion 114

2-10 Polygon Filling 115

Scan-converting Polygons 115

2-11 A Simple Parity Scan Conversion Algorithm 118

2-12 Ordered Edge List Polygon Scan Conversion 121

A Simple Ordered Edge List Algorithm 122

More Efficient Ordered Edge List Algorithms 123

2-13 The Edge Fill Algorithm 126

2-14 The Edge Flag Algorithm 131

2-15 Seed Fill Algorithms 133

A Simple Seed Fill Algorithm 134

A Scan Line Seed Fill Algorithm 137

2-16 Fundamentals of Antialiasing 142

Supcrsampling 143

Straight Lines 144

Polygon Interiors 151

Simple Area Antialiasing 152

The Convolution Integral and Antialiasing 156

Filter Functions 159

2-17 Halftoning 161

Patterning 161

Thresholding and Error Distribution 165

Ordered dither 169

Chapter 3 Clipping 175

3-1 Two-dimensional Clipping 175

A Simple Visibility Algorithm 176

End Point Codes 177

3-2 Cohen-Sutherland Subdivision Line Clipping Algorithm 181

3-3 Midpoint Subdivision Algorithm 187

3-4 Two-dimensional Line Clipping for Convex Boundaries 192

Partially Visible Lines 193

3-5 Cyrus-Beck Algorithm 196

Partially Visible Lines 199

Totally Visible Lines 201

Totally Invisible Lines 201

Formal Statement of Cyrus-Beck Algorithm 203

Irregular Windows 207

3-6 Liang-Barsky Two-dimensional Clipping 208

Comparison with the Cyrus-Beck Algorithm 212

3-7 Nicholl-Lee-Nicholl Two-dimensional Clipping 217

3-8 Interior and Exterior Clipping 221

3-9 Identifying Convex Polygons and Determining the Inward Normal 222

3-10 Splitting Concave Polygons 225

3-11 Three-dimensional Clipping 228

3-12 Three-dimensional Midpoint Subdivision Algorithm 231

3-13 Three-dimensional Cyrus-Beck Algorithm 233

3-14 Liang-Barsky Three-dimensional Clipping 239

3-15 Clipping in Homogeneous Coordinates 243

The Cyrus-Beck Algorithm 243

The Liang-Barsky Algorithm 245

3-16 Determining the Inward Normal and Three-dimensional Convex Sets 248

3-17 Splitting Concave Volumes 250

3-18 Polygon Clipping 253

3-19 Reentrant Polygon Clipping—Sutherland-Hodgman Algorithm 253

Line Intersections 257

The Algorithm 258

3-20 Liang-Barsky Polygon Clipping 265

Entering and Leaving Vertices 265

Turning Vertices 267

Development of the Algorithm 268

Horizontal and Vertical Edges 271

The Algorithm 272

3-21 Concave Clipping Regions—Weiler-Atherton Algorithm 276

Special Cases 282

3-22 Character Clipping 286

Chapter 4 Visible Lines and Visible Surfaces 287

4-1 Introduction 287

4-2 Floating Horizon Algorithm 289

Upper Horizon 290

Lower Horizon 290

Function Interpolation 291

Aliasing 295

The Algorithm 295

Cross-hatching 303

4-3 Roberts Algorithm 303

Volume Matrices 306

Plane Equations 308

Viewing Transformations and Volume Matrices 311

Self-hidden Planes 314

Lines Hidden by Other Volumes 318

Penetrating Volumes 327

Totally Visible Lines 327

The Algorithm 330

4-4 Warnock Algorithm 343

Quadtree Data Structure 345

Subdivision Criteria 347

The Relationship of a Polygon to a Window 349

Hierarchical Application of Polygon-Window Relations 354

Finding Surrounder Polygons 355

Determining the Visibility of a Point 355

The Basic Algorithm 357

4-5 Appel s Algorithm 363

4-6 The Haloed Line Algorithm 366

4-7 Weiler-Atherton Algorithm 370

4-8 A Subdivision Algorithm for Curved Surfaces 374

4-9 Z-Buffer Algorithm 375

Incrementally Calculating the Depth 378

Hierarchical Z-Buffer 383

4-10 The A-Buffer Algorithm 384

4-11 List Priority Algorithms 387

4-12 The Newell-Newell-Sancha Algorithm 389

Implementing the Tests 390

4-13 Binary Space Partitioning 393

The Schumaker Algorithm 393

Binary Space Partition Trees 395

Constructing the BSP Tree 395

BSP Tree Traversal 398

Summary 400

Culling 400

4-14 Scan Line Algorithms 401

4-15 Scan Line Z-Buffer Algorithm 402

4-16 A Spanning Scan Line Algorithm 406

Invisible Coherence 415

An Object Space Scan Line Algorithm 416

4-17 Scan Line Algorithms for Curved Surfaces 417

4-18 Octrees 421

Octree Display 424

Manipulation of Octrees 426

Boolean Operations 426

Linear Octrees 426

Finding Neighboring Voxels 427

4-19 Marching Cubes 427

Ambiguous faces 429

4-20 A Visible Surface Ray Tracing Algorithm 432

Bounding Volumes 435

Clusters 439

Constructing the Cluster Tree 440

Priority Sort 440

Spatial Subdivision 441

Uniform Spatial Subdivision 442

Nonuniform Spatial Subdivision 445

Ray-Object Intersections 447

Opaque Visible Surface Algorithm 451

4-21 Summary 456

Chapter 5 Rendering 457

5-1 Introduction 457

5-2 Illumination Models 460

5-3 A Simple Illumination Model 461

Specular Reflection 462

The Halfway Vector 465

5-4 Determining the Surface Normal 468

5-5 Determining the Reflection Vector 470

5-6 Gouraud Shading 474

5-7 Phong Shading 476

Fast Phong Shading 482

5-8 A Simple Illumination Model with Special Effects 483

5-9 A Physically Based Illumination Model 484

Energy and Intensity 485

Physically Based Illumination Models 487

The Torrance-Sparrow Surface Model 488

Wavelength Dependence—the Fresnel Term 491

Color Shift 492

Physical Characteristics of Light Sources 494

5-10 Transparency 496

Refraction Effects in Transparent Materials 497

Simple Transparency Models 498

Z-Buffer Transparency 500

Pseudotransparency 501

5-11 Shadows 502

The Scan Conversion Shadow Algorithms 506

Multiple-pass Visible Surface Shadow Algorithms 508

The Shadow Volume Algorithms 509

Penumbra Shadows 514

Ray Tracing Shadow Algorithms 517

5-12 Texture 517

Mapping Functions 525

Two-part Texture Mapping 528

Environment Mapping 531

Bump Mapping 534

Procedural Textures 536

Texture Antialiasing 539

Mipmapping(Image Pyramids) 542

Summed Area Tables 544

5-13 Stochastic Models 545

5-14 A Global Illumination Model Using Ray Tracing 548

5-15 A More Complete Global Illumination Model Using Ray Tracing 563

5-16 Advances in Ray Tracing 565

Cone Tracing 565

Beam Tracing 566

Stochastic Sampling 567

Pencil Tracing 567

Ray Tracing from the Light Source 570

5-17 Radiosity 571

Enclosures 573

Form Factors 575

The Hemicube 577

Rendering 582

Substructuring 584

Progressive Refinement 585

The Ambient Contribution 586

Sorting 586

Adaptive Subdivision 587

Hemicube Inaccuracies 589

Alternatives to the Hemicube 592

Hierarchical Radiosity and Clustering 594

Radiosity for Specular Environments 596

The Rendering Equation 597

5-18 Combined Ray Tracing and Radiosity 598

The Extended Two-pass Algorithm 602

5-19 Color 602

Chromaticity 603

Tristimulus Theory of Color 605

Color Primary Systems 606

Color Matching Experiment 606

Chromaticity Diagrams 609

The 1931 CIE Chromaticity Diagram 611

Uniform Color Spaces 615

Gamut Limitations 616

Transformations Between Color Systems 618

NTSC Color System 621

Color Cubes 622

The CMYK Color System 623

The Ostwald Color System 623

The HSV Color System 624

The HLS Color System 627

The Munsell Color System 630

The Pantone? System 631

Gamma Correction 631

5-20 Color Image Quantization 633

The Bit Cutting Algorithm 634

The Popularity Algorithm 635

The Median Cut Algorithm 637

Octree Quantization 640

Sequential Scalar Quantization 644

Other Quantization Algorithms 647

5-21 Color Reproduction 648

Offset Printing 649

Color Separation 649

Tone Reproduction 649

Quantization Effects 650

Calibration 650

The Black Separation 650

Gray Balance 650

Gamut Mapping 651

5-22 Specialty Rendering Techniques 654

Duotone Printing 654

Rendering Natural Objects 656

Particle Systems 656

Appendix Problems and Projects 657

References 665

Index 695