Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Fundamentals of computer graphics
Nội dung xem thử
Mô tả chi tiết
✐ ✐ ✐ ✐ ✐ ✐ ✐ ✐
✐
✐
✐
✐
✐
✐
✐
✐
Fundamentals of Computer Graphics
Third Edition
✐ ✐ ✐ ✐ ✐ ✐ ✐ ✐
✐
✐
✐
✐
✐
✐
✐
✐
Fundamentals of Computer Graphics
Third Edition
Peter Shirley Steve Marschner
NVIDIA Corporation Cornell University
with
Michael Ashikhmin
Michael Gleicher
Naty Hoffman
Garrett Johnson
Tamara Munzner
Erik Reinhard
Kelvin Sung
William B. Thompson
Peter Willemsen
Brian Wyvill
A K Peters
Natick, Massachusetts
CRC Press
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742
© 2009 by Taylor & Francis Group, LLC
CRC Press is an imprint of Taylor & Francis Group, an Informa business
No claim to original U.S. Government works
Version Date: 20110714
International Standard Book Number-13: 978-1-4398-6552-1 (eBook - PDF)
This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author
and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not
been acknowledged please write and let us know so we may rectify in any future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other
means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from
the publishers.
For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance
Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For
organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe.
Visit the Taylor & Francis Web site at
http://www.taylorandfrancis.com
and the CRC Press Web site at
http://www.crcpress.com
✐
✐
✐
✐
✐
✐
✐
✐
Contents
Preface xi
1 Introduction 1
1.1 Graphics Areas . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Major Applications . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Graphics APIs . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Graphics Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Numerical Issues . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7 Designing and Coding Graphics Programs . . . . . . . . . . . . 8
2 Miscellaneous Math 13
2.1 Sets and Mappings . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Solving Quadratic Equations . . . . . . . . . . . . . . . . . . . 17
2.3 Trigonometry . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5 Curves and Surfaces . . . . . . . . . . . . . . . . . . . . . . . 30
2.6 Linear Interpolation . . . . . . . . . . . . . . . . . . . . . . . 44
2.7 Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3 Raster Images 53
3.1 Raster Devices . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.2 Images, Pixels, and Geometry . . . . . . . . . . . . . . . . . . 59
v
✐
✐
✐
✐
✐
✐
✐
✐
vi Contents
3.3 RGB Color . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4 Alpha Compositing . . . . . . . . . . . . . . . . . . . . . . . . 65
4 Ray Tracing 69
4.1 The Basic Ray-Tracing Algorithm . . . . . . . . . . . . . . . . 70
4.2 Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 Computing Viewing Rays . . . . . . . . . . . . . . . . . . . . 73
4.4 Ray-Object Intersection . . . . . . . . . . . . . . . . . . . . . 76
4.5 Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.6 A Ray-Tracing Program . . . . . . . . . . . . . . . . . . . . . 84
4.7 Shadows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.8 Ideal Specular Reflection . . . . . . . . . . . . . . . . . . . . . 87
4.9 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . 88
5 Linear Algebra 91
5.1 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3 Computing with Matrices and Determinants . . . . . . . . . . . 98
5.4 Eigenvalues and Matrix Diagonalization . . . . . . . . . . . . . 103
6 Transformation Matrices 111
6.1 2D Linear Transformations . . . . . . . . . . . . . . . . . . . . 111
6.2 3D Linear Transformations . . . . . . . . . . . . . . . . . . . . 125
6.3 Translation and Affine Transformations . . . . . . . . . . . . . 130
6.4 Inverses of Transformation Matrices . . . . . . . . . . . . . . . 134
6.5 Coordinate Transformations . . . . . . . . . . . . . . . . . . . 135
7 Viewing 141
7.1 Viewing Transformations . . . . . . . . . . . . . . . . . . . . . 142
7.2 Projective Transformations . . . . . . . . . . . . . . . . . . . . 148
7.3 Perspective Projection . . . . . . . . . . . . . . . . . . . . . . 151
7.4 Some Properties of the Perspective Transform . . . . . . . . . . 156
7.5 Field-of-View . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8 The Graphics Pipeline 161
8.1 Rasterization . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.2 Operations Before and After Rasterization . . . . . . . . . . . . 173
8.3 Simple Antialiasing . . . . . . . . . . . . . . . . . . . . . . . . 180
8.4 Culling Primitives for Efficiency . . . . . . . . . . . . . . . . . 181
✐
✐
✐
✐
✐
✐
✐
✐
Contents vii
9 Signal Processing 185
9.1 Digital Audio: Sampling in 1D . . . . . . . . . . . . . . . . . . 186
9.2 Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
9.3 Convolution Filters . . . . . . . . . . . . . . . . . . . . . . . . 203
9.4 Signal Processing for Images . . . . . . . . . . . . . . . . . . . 210
9.5 Sampling Theory . . . . . . . . . . . . . . . . . . . . . . . . . 218
10 Surface Shading 233
10.1 Diffuse Shading . . . . . . . . . . . . . . . . . . . . . . . . . 233
10.2 Phong Shading . . . . . . . . . . . . . . . . . . . . . . . . . . 236
10.3 Artistic Shading . . . . . . . . . . . . . . . . . . . . . . . . . 239
11 Texture Mapping 243
11.1 3D Texture Mapping . . . . . . . . . . . . . . . . . . . . . . . 244
11.2 2D Texture Mapping . . . . . . . . . . . . . . . . . . . . . . . 250
11.3 Texture Mapping for Rasterized Triangles . . . . . . . . . . . . 252
11.4 Bump Textures . . . . . . . . . . . . . . . . . . . . . . . . . . 255
11.5 Displacement Mapping . . . . . . . . . . . . . . . . . . . . . . 256
11.6 Environment Maps . . . . . . . . . . . . . . . . . . . . . . . . 256
11.7 Shadow Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
12 Data Structures for Graphics 261
12.1 Triangle Meshes . . . . . . . . . . . . . . . . . . . . . . . . . 262
12.2 Scene Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
12.3 Spatial Data Structures . . . . . . . . . . . . . . . . . . . . . . 278
12.4 BSP Trees for Visibility . . . . . . . . . . . . . . . . . . . . . 289
12.5 Tiling Multidimensional Arrays . . . . . . . . . . . . . . . . . 297
13 More Ray Tracing 303
13.1 Transparency and Refraction . . . . . . . . . . . . . . . . . . . 304
13.2 Instancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
13.3 Constructive Solid Geometry . . . . . . . . . . . . . . . . . . . 309
13.4 Distribution Ray Tracing . . . . . . . . . . . . . . . . . . . . . 309
14 Sampling 317
14.1 Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
14.2 Continuous Probability . . . . . . . . . . . . . . . . . . . . . . 322
14.3 Monte Carlo Integration . . . . . . . . . . . . . . . . . . . . . 326
14.4 Choosing Random Points . . . . . . . . . . . . . . . . . . . . . 329
✐
✐
✐
✐
✐
✐
✐
✐
viii Contents
15 Curves 339
15.1 Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
15.2 Curve Properties . . . . . . . . . . . . . . . . . . . . . . . . . 345
15.3 Polynomial Pieces . . . . . . . . . . . . . . . . . . . . . . . . 348
15.4 Putting Pieces Together . . . . . . . . . . . . . . . . . . . . . . 356
15.5 Cubics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
15.6 Approximating Curves . . . . . . . . . . . . . . . . . . . . . . 365
15.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
16 Implicit Modeling 385
16.1 Implicit Functions, Skeletal Primitives
and Summation Blending . . . . . . . . . . . . . . . . . . . . . 386
16.2 Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
16.3 Space Partitioning . . . . . . . . . . . . . . . . . . . . . . . . 395
16.4 More on Blending . . . . . . . . . . . . . . . . . . . . . . . . 401
16.5 Constructive Solid Geometry . . . . . . . . . . . . . . . . . . 402
16.6 Warping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
16.7 Precise Contact Modeling . . . . . . . . . . . . . . . . . . . . 406
16.8 The BlobTree . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
16.9 Interactive Implicit Modeling Systems . . . . . . . . . . . . . . 410
17 Computer Animation 413
17.1 Principles of Animation . . . . . . . . . . . . . . . . . . . . . 414
17.2 Keyframing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
17.3 Deformations . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
17.4 Character Animation . . . . . . . . . . . . . . . . . . . . . . . 427
17.5 Physics-Based Animation . . . . . . . . . . . . . . . . . . . . 433
17.6 Procedural Techniques . . . . . . . . . . . . . . . . . . . . . . 436
17.7 Groups of Objects . . . . . . . . . . . . . . . . . . . . . . . . 439
18 Using Graphics Hardware 445
18.1 What Is Graphics Hardware . . . . . . . . . . . . . . . . . . . 445
18.2 Describing Geometry for the Hardware . . . . . . . . . . . . . 446
18.3 Processing Geometry into Pixels . . . . . . . . . . . . . . . . . 453
19 Building Interactive Graphics Applications 467
19.1 The Ball Shooting Program . . . . . . . . . . . . . . . . . . . 468
19.2 Programming Models . . . . . . . . . . . . . . . . . . . . . . 470
19.3 The Modelview-Controller Architecture . . . . . . . . . . . . . 487
✐
✐
✐
✐
✐
✐
✐
✐
Contents ix
19.4 Example Implementations . . . . . . . . . . . . . . . . . . . . 499
19.5 Applying Our Results . . . . . . . . . . . . . . . . . . . . . . 509
20 Light 517
20.1 Radiometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
20.2 Transport Equation . . . . . . . . . . . . . . . . . . . . . . . . 526
20.3 Photometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
21 Color 531
21.1 Colorimetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
21.2 Color Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 542
21.3 Chromatic Adaptation . . . . . . . . . . . . . . . . . . . . . . 548
21.4 Color Appearance . . . . . . . . . . . . . . . . . . . . . . . . 552
22 Visual Perception 553
22.1 Vision Science . . . . . . . . . . . . . . . . . . . . . . . . . . 554
22.2 Visual Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . 555
22.3 Spatial Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
22.4 Objects, Locations, and Events . . . . . . . . . . . . . . . . . . 585
22.5 Picture Perception . . . . . . . . . . . . . . . . . . . . . . . . 593
23 Tone Reproduction 597
23.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
23.2 Dynamic Range . . . . . . . . . . . . . . . . . . . . . . . . . . 601
23.3 Color . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603
23.4 Image Formation . . . . . . . . . . . . . . . . . . . . . . . . . 605
23.5 Frequency-Based Operators . . . . . . . . . . . . . . . . . . . 605
23.6 Gradient-Domain Operators . . . . . . . . . . . . . . . . . . . 607
23.7 Spatial Operators . . . . . . . . . . . . . . . . . . . . . . . . . 608
23.8 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 610
23.9 Sigmoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
23.10 Other Approaches . . . . . . . . . . . . . . . . . . . . . . . . 616
23.11 Night Tonemapping . . . . . . . . . . . . . . . . . . . . . . . 619
23.12 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 620
24 Global Illumination 623
24.1 Particle Tracing for Lambertian Scenes . . . . . . . . . . . . . 624
24.2 Path Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
24.3 Accurate Direct Lighting . . . . . . . . . . . . . . . . . . . . . 629
✐
✐
✐
✐
✐
✐
✐
✐
x Contents
25 Reflection Models 637
25.1 Real-World Materials . . . . . . . . . . . . . . . . . . . . . . . 637
25.2 Implementing Reflection Models . . . . . . . . . . . . . . . . . 639
25.3 Specular Reflection Models . . . . . . . . . . . . . . . . . . . 641
25.4 Smooth Layered Model . . . . . . . . . . . . . . . . . . . . . . 642
25.5 Rough Layered Model . . . . . . . . . . . . . . . . . . . . . . 645
26 Computer Graphics in Games 653
26.1 Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
26.2 Limited Resources . . . . . . . . . . . . . . . . . . . . . . . . 655
26.3 Optimization Techniques . . . . . . . . . . . . . . . . . . . . . 659
26.4 Game Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 660
26.5 The Game Production Process . . . . . . . . . . . . . . . . . . 664
27 Visualization 675
27.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
27.2 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678
27.3 Human-Centered Design Process . . . . . . . . . . . . . . . . 680
27.4 Visual Encoding Principles . . . . . . . . . . . . . . . . . . . . 682
27.5 Interaction Principles . . . . . . . . . . . . . . . . . . . . . . . 689
27.6 Composite and Adjacent Views . . . . . . . . . . . . . . . . . 690
27.7 Data Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 696
27.8 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701
28 Spatial-Field Visualization 709
28.1 2D Scalar Fields . . . . . . . . . . . . . . . . . . . . . . . . . 710
28.2 3D Scalar Fields . . . . . . . . . . . . . . . . . . . . . . . . . 711
References 721
Index 745
✐
✐
✐
✐
✐
✐
✐
✐
Preface
This edition of Fundamentals of Computer Graphics adds four new contributed
chapters and contains substantial reorganizations and improvements to the core
material. The new chapters add coverage of implicit modeling and of two important graphics applications: games and information visualization. The fourth new
contributed chapter is a major upgrade to the material on color science. As with
the chapters added in the second edition, we have chosen the contributors both for
their expertise and for their clear way of expressing ideas.
We have made a number of changes to the early chapters of the book, integrating the second author’s experience teaching introductory graphics at Cornell using
the first and second editions. Most of these have been revised and updated, particularly the chapters on images, viewing, ray tracing, the graphics pipeline, and the
material on triangle meshes. Some of the original material from these chapters
has been reorganized, sometimes with topics appearing in different chapters than
in the previous editions.
Our aim in this reorganization has been to move the elementary material towards the beginning. In our thinking, Chapters 2 through 8 constitute the “core
core,” taking the straight and narrow path through what is absolutely required
for understanding how images get onto the screen using the complementary approaches of ray tracing and rasterization. Ray tracing is covered first, since it is
the simplest way to generate images of 3D scenes, followed by the mathematical machinery required for the graphics pipeline, then the pipeline itself. After
that, the “outer core” covers other topics that would commonly be included in an
introductory class. For example, ray tracing is split into two chapters, with the
more advanced material now in Chapter 13. The material on spatial data strucxi
✐
✐
✐
✐
✐
✐
✐
✐
xii Preface
tures (some formerly under Ray Tracing and Hidden Surfaces) is consolidated in
Chapter 12 together with an expanded section on triangle meshes.
In all these revisions, we have endeavored to retain the informal, intuitive
style of presentation that characterizes the earlier editions, while at the same time
improving consistency, precision, and completeness. We hope the reader will find
the result is a better platform for a variety of courses in computer graphics.
About the Cover
The cover image is from Tiger in the Water by J. W. Baker (brushed and airbrushed acrylic on canvas, 16” by 20”, www.jwbart.com).
The subject of a tiger is a reference to a wonderful talk given by Alain Fournier
(1943–2000) at the Cornell Workshop in 1998. His talk was an evocative verbal
description of the movements of a tiger. He summarized his point:
Even though modelling and rendering in computer graphics have
been improved tremendously in the past 35 years, we are still not
at the point where we can model automatically a tiger swimming in
the river in all its glorious details. By automatically I mean in a way
that does not need careful manual tweaking by an artist/expert.
The bad news is that we have still a long way to go.
The good news is that we have still a long way to go.
Online Resources
The web site for this book is http://www.cs.cornell.edu/∼srm/fcg3/. We will continue to maintain a list of errata and links to courses that use the book, as well as
teaching materials that match the book’s style. Most of the figures in this book are
in Abobe Illustrator format, and we would be happy to convert specific figures into
portable formats on request. Please feel free to contact us at [email protected]
Acknowledgments
The following people have provided helpful information, comments, or feedback
about the various editions of this book: Ahmet Oguz Aky¨ ˘ uz, Josh Andersen,
Zeferino Andrade, Adam Berger, Adeel Bhutta, Solomon Boulos, Stephen
Chenney, Michael Coblenz, Greg Coombe, Frederic Cremer, Brian Curtin, Dave
✐
✐
✐
✐
✐
✐
✐
✐
Preface xiii
Edwards, Jonathon Evans, Karen Feinauer, Amy Gooch, Eungyoung Han, Chuck
Hansen, Andy Hanson, Razen Al Harbi, Dave Hart, John Hart, John “Spike”
Hughes, Helen Hu, Vicki Interrante, Doug James, Henrik Wann Jensen, Shi Jin,
Mark Johnson, Ray Jones, Revant Kapoor, Kristin Kerr, Erum Arif Khan, Mark
Kilgard, Dylan Lacewell, Mathias Lang, Philippe Laval, Marc Levoy, Howard
Lo, Joann Luu, Ron Metoyer, Keith Morley, Eric Mortensen, Koji Nakamaru,
Micah Neilson, Blake Nelson, Michael Nikelsky, James O’Brien, Steve Parker,
Sumanta Pattanaik, Matt Pharr, Peter Poulos, Shaun Ramsey, Rich Riesenfeld,
Nate Robins, Nan Schaller, Chris Schryvers, Tom Sederberg, Richard Sharp,
Sarah Shirley, Peter-Pike Sloan, Hannah Story, Tony Tahbaz, Jan-Phillip
Tiesel, Bruce Walter, Alex Williams, Amy Williams, Chris Wyman, and
Kate Zebrose.
Ching-Kuang Shene and David Solomon allowed us to borrow their examples. Henrik Wann Jensen, Eric Levin, Matt Pharr, and Jason Waltman generously
provided images. Brandon Mansfield helped improve the discussion of hierarchical bounding volumes for ray tracing. Philip Greenspun (philip.greenspun.com)
kindly allowed us to use his photographs. We are extremely thankful to J. W.
Baker for helping create the cover Pete envisioned. In addition to being a talented
artist, he was a great pleasure to work with personally.
Many works that were helpful in preparing this book are cited in the chapter notes. However, a few key texts that influenced the content and presentation
deserve special recognition here. These include the two classic computer graphics texts from which we both learned the basics: Computer Graphics: Principles & Practice (Foley et al., 1990) and Computer Graphics (Hearn & Baker,
1986). Other texts include both of Alan Watt’s influential books (Watt, 1993,
1991), Hill’s Computer Graphics Using OpenGL (Francis S. Hill, 2000), Angel’s
Interactive Computer Graphics: A Top-Down Approach Using OpenGL (Angel,
2002), Hugues Hoppe’s University of Washington dissertation (Hoppe, 1994), and
Rogers’ two excellent graphics texts (D. F. Rogers, 1985, 1989).
We would like to especially thank Alice and Klaus Peters for encouraging
Pete to write the first edition of this book and for their great skill in bringing a
book to fruition. Their patience with the authors and their dedication to making
their books the best they can be has been instrumental in guiding us through three
editions. This book certainly would not exist without their extraordinary efforts.
Salt Lake City, Utah
Ithaca, New York
May 2009