Computer Graphics Using OpenGL / Edition 3

by Francis Hill Jr.

Overview

Updated throughout for the latest developments and technologies, this book combines the principles and major techniques in computer graphics with state-of-the-art examples. KEY TOPICS: Updates treatment of graphics hardware and algorithms. Discusses the development of video games through history. Emphasizes interactive graphics more strongly than in previous editions. Relates examples to things readers see everyday on the Internet and in computer-generated movies. Carefully presents each concept, explains the underlying mathematics, shows how to translate the math into program code, and displays the result. MARKET: A thorough, useful reference for anyone interested in computer graphics.

Product Details

ISBN-13:	9780131496705
Publisher:	Pearson Education
Publication date:	12/20/2006
Edition description:	Revised Edition
Pages:	800
Product dimensions:	7.90(w) x 10.00(h) x 1.80(d)

About the Author

F.S. Hill Jr. is a Professor Emeritus of the Electrical and Computer Engineering Department at the University of Massachusetts at Amherst. He received a Ph. D. degree from Yale University in 1968, worked for 3 years in digital data transmission at Bell Telephone Laboratories, and joined the University in 1970. He is the author of numerous articles in the field of signal processing, communications, and computer graphics. He has been editor and associate editor of the IEEE Communications Society magazine. He is also a fellow of the IEEE. He is co-author of the book Introduction To Engineering and has won several awards for outstanding teaching.

Stephen M. Kelley and Dr. Hill met in 2000 in connection with a National Science Foundation distance learning project. Since then co-teaching courses in computer graphics at the University of Massachusetts and co-authoring Computer Graphics using OpenGL, 3 ^rd Edition. Stephen Kelley recently graduated from the University of Massachusetts with a degree in Interactive Multimedia and Computer Graphics along with a minor in Information Technology. Stephen also runs his own web development and consulting company, Intangible Inc.

Read an Excerpt

This book provides an introduction to computer graphics for students who wish to learn the basic principles and techniques of the field, and in addition want to write substantial graphics applications themselves. The field of computer graphics continues to enjoy tremendous vitality and growth. The growing number of feature-length animated movies has generated heady excitement about what graphics can do, and the ready access to graphics everyone now has through computer games and the internet is stimulating people to learn how to do it themselves.

Graphics systems are getting better, faster, and cheaper at a bewildering rate, and many new techniques are emerging each year from researchers and practitioners around the world, but the underlying principles and approaches comprise a stable and coherent body of knowledge. Much of this knowledge can be acquired through a single course in graphics, and this book attempts to organize the ideas and methods to bring the reader from the beginning with modest programming skills, to being able to design and produce significant graphics programs.

Intended audience.

This book is designed as a text for either a one- or two-semester course at the senior undergraduate or first-year graduate level. It can also be used for self-study. It is aimed principally for students majoring in computer science or engineering but will also suit students in other fields, such as physics and mathematics.

Mathematical background required.

The reader should have the equivalent of one year of college mathematics; knowledge of elementary algebra, geometry, trigonometry, and elementary calculus is assumed. Some exposure to vectors and matrices is useful but not essential; vector and matrix techniques are introduced in the context of graphics as they are needed, and an appendix also summarizes the key ideas.

Computer graphics tends to use a lot of mathematics to express the underlying geometric relationships between lines, surfaces, and the viewing "eye". Although no single mathematical notion is difficult in itself the number of tools required can be daunting. The book places particular emphasis on revealing the reasons for using this or that technique, and on showing how the objects of interest in a graphics program are properly described by the mathematical objects we use.

Computer programming background required.

In general, the reader should have at least one semester of experience writing computer programs in C, C++, or Java. A lot of the programming in graphics involves the direct translation of geometric relationships into code, and so uses straightforward variables, functions, arrays, looping, and testing, which is similar from language to language. C++ is used throughout the book, but much of the material will be familiar to someone with only a background in C.

It is helpful for the reader to have experience as well in manipulating struct's in C or classes in C++. These are used to capture the rather complicated structure of some graphical objects that reside in a scene, where the object (say, a castle or an airplane) consists of many parts, and these parts themselves consist of complex subparts. Some experience with elementary linked data structures such as linked lists or trees is also desirable but not essential.

A reader with knowledge of C but not C++ will need to pick up the basics of object-oriented programming. We define a number of useful classes (such as the Canvas, Mesh, Scene, Camera, and Texture classes) and show why they are so convenient and usable. Some of the hallmarks of object-oriented programming, such as inheritance and polymorphism, are used in a few contexts to make the programmer's job easier, but we don't place inordinate emphasis on a pure object-oriented approach.

Philosophy

The book has been completely reorganized and rewritten from the first edition but the basic philosophy remains: Computer graphics is learned by doing it. One must write and test real programs to comprehend fully what is going on. A principal goal of the book is to show readers how to translate a particular design "task" first into its underlying geometric components, to find a suitable mathematical representation for the objects involved, and finally to translate this representation into suitable algorithms and program code. Readers first learn how to develop simple routines to produce pictures. Then methods for producing drawings of ever more complex objects are presented in a step-by-step fashion.

Exercises and Problems

More than 350 practice exercises appear throughout the book. Most of these are of the "stop-and-think" variety that don't require programming and allow readers to self-test their grasp of the material. Some urge the student to implement some of the new ideas in program code.

In addition, over 50 Case Studies appear at the end of chapters. They are normally programming projects suitable for homework assignments, and range from the simple to the challenging. These exercises expand on the material within their chapter, and often extend ideas in new directions. Whether or not the Case Studies are actually carried out by students, they should be studied as an integral part of the chapter.

A suggested "Level of Effort" is associated with each Case Study, to indicate the approximate investment in time a student may need to accomplish the task. Programming is an unpredictable business and students' abilities vary, but the rough guide is:

Level of Effort:
I: A simple project that can be implemented in an evening, suitable to be made due at the next class meeting.

II: A more extensive project that might be assigned due in a week, so that a student has thinking time for designing the program, and adequate time for the iterative (and sometimes frustrating) testing and debugging cycle that projects always seem to require.

III: A major project that might require three weeks of design and implementation effort. Such a project requires substantial design effort and careful program layout, but would (correctly) be viewed as a major accomplishment by the student.
The use of OpenGL

A frequent stumbling block as one first brushes up against computer graphics is getting started making pictures. It's often easy enough to write a program, but there must be an underlying tool that ultimately draws the lines and curves on the screen. It's a boon that such a tool exists and is readily available. OpenGL emerged from Silicon Graphics Inc. in 1992, and has become a widely adopted graphics application programming interface (API). It provides the actual drawing tools through a collection of functions that are called within an application. As described in Appendix 1, it is available (usually through free downloads over the internet) for all types of computer systems encountered in colleges, universities, and industry. It is easy to install and learn, and its longevity as a standard API is being nurtured by the OpenGL Architecture Review Board (ARB), an industry consortium responsible for guiding its evolution.

One aspect of OpenGL that makes it so well-suited for use in a computer graphics course is its "device independence" or portability. Many university computer laboratories contain a variety of different computer types. A student can develop and run a program on any available computer. The same program can then be run on a different computer, for testing or grading purposes perhaps, and the graphics will be the same on the two machines.

OpenGL offers a rich and highly usable API for 2D graphics and image manipulation, but its real power emerges with 3D graphics. Using OpenGL students can progress rapidly and produce stunning animations in only a single-semester course.

The use of C++ as the programming language.

C++ is now familiar enough to most students in engineering and computer science through a first programming course that it is the natural choice of the language to use. It offers several advantages over C, such as passing parameters to functions by reference, which reduces the need for explicit pointers and simplifies reading the code. File I/O is also greatly simplified through streams, and in general the syntax for all kinds of I/O is clearer in C++ than in C. To keep things simple in this book, no emphasis is placed on implementing operators in C++.

Furthermore, it is easy to develop handy utility classes in C++, such as those for 2D or 3D points, a line, a window, or a color, which make code simpler and more robust. Students see the benefit of hiding the details of a geometric object within the object itself, and of imbuing the object with the ability to do things like draw itself, or test whether it intersects another object. The Canvas class developed in Chapter 3 offers a good example, as it maintains its own notion of a window, a viewport, and a current position, and it can draw basic figures with very little programming effort.

The emphasis on 3D computer graphics.

Because playing games on PC's has become so popular, and so many dazzling animations are appearing in movies, students are particularly interested in developing 3D interactive graphics applications. Several chapters from the first and second editions have been rewritten and rearranged in order to get to topics in 3D graphics as quickly as possible. In a number of situations concepts are presented for the 2D case and the 3D case together, which helps to clarify the distinctions between the two.

Describing 3D scenes using the Scene Design Language

It can be very awkward and time consuming to design a scene of many 3D objects using "raw" OpenGL commands (for example, describing a cube by its 6 faces each time it is used can become tedious.). So a simple Scene Design language (SDL) is introduced in Chapter 5 (and fully defined in an appendix). Using this language students can describe scenes with familiar terms like "cube", "sphere", and "rotate", and build files of such instructions that can be read into their program at runtime. Code for an interpreter is provided in an appendix (and on the book's web site) that can read SDL files and build a list of objects described in the file. It is then a simple matter to use OpenGL to draw the scene from the object list.

This same language and interpreter is put to fine use in Chapter 12 on ray tracing, where the student develops code for ray tracing a scene described using SDL. This permits students to design and ray trace much more elaborate and interesting scenes than would be possible otherwise.

Organization of the Book and Course Plans

There is much more in this book than can be covered in a one-semester course, or even in a two-semester course (which was also the case for the first two editions). The book has been arranged so the instructor can select different groups of chapters for close study, depending on the length of a course and the interests and backgrounds of the class. Several such paths through the book are suggested here, after the principal topics in each chapter are described.

Brief Overview of each Chapter.

Chapter 1. This chapter gives an overview of the computer graphics field, with examples of how various fields are using graphics. The different kinds of available graphics display systems are described, along with the types of primitives (polygons, text, images, etc.) that a graphic system displays. The chapter also describes some of the many kinds of input devices (mouse, tablet, data glove, etc.) in common use.

Chapter 2. This chapter gets students started with writing graphics applications. Programming using OpenGL is described and several complete line-drawing applications are developed, (including the popular Sierpinski gasket). Techniques are discussed for using OpenGL to draw various primitives such as polylines and polygons, and to use the mouse and keyboard in an interactive graphics application. Case Studies at the end of the chapter provide interesting programming projects to help students get a clear initial sense of how a graphics application is implemented. One Case Study focuses on building a class for which the application programmer can properly initialize and open an OpenGL window for drawing.

Chapter 3. This chapter develops the central notion of the window to viewport mapping, for sizing and positioning pictures on the display. Do-it-yourself management of windows and viewports is discussed, as is using OpenGL to handle the details. Zooming and panning to achieve interesting visual effects are described, as is simple animation of figures. A Canvas class is developed that encapsulates all of the drawing tools. The drawing of complex polygon-based figures, circles, and arcs is discussed. The parametric form for representing curves is discussed for both 2D and 3D curves.

Chapter 4. This chapter reviews vectors and their basic operations, and shows the great benefits to be gained by using vector tools in graphics. Students familiar with vectors can read this chapter quickly, focusing on how vectors describe relations between the geometric objects they are manipulating in their programs. One of the useful properties of vectors is that many vector operations may be treated without regard for the dimensionality of the space in question. The use of the cross product, on the other hand, is restricted to three dimensional vectors.

The notion of a coordinate frame is introduced, and it is shown how this makes it natural to work with homogeneous coordinates. Affine combinations of points are discussed to clarify the difference between vectors and points (to help avoid a common pitfall when writing graphics applications). Several applications involving interpolation, elementary Bezier curves, and line intersections are developed. The fundamental algorithm to clip a line against a convex polygon is developed in detail. (An interesting project for 2D ray tracing is suggested in a Case Study.)

Chapter 5. Transformations are of central importance in computer graphics, and students sometimes have difficulty developing intuition about them - particularly about 3D transformations. This chapter develops the underlying theory of transforming figures and coordinate systems using affine transformations in both the 2D and 3D cases. Homogeneous coordinates are used from the start for describing transformations. Special care is given to rotations in 3D, which are notoriously difficult to visualize.

Tools are added to the Canvas class begun in Chapter 3 to translate, scale, and rotate figures through the current transformation, and OpenGL's matrix operations are enlisted to facilitate this. An overview of the OpenGL viewing pipeline is then developed, and the roles of the modelview, projection, and viewport transformations are described. Drawing of 3D objects using OpenGL's tools is developed. The use of the Scene Description Language (SDL) is introduced, and it is shown how to use the SDL interpreter to read in a description of a 3D scene from a file, and to draw the objects.

Chapter 6. This chapter develops tools for modeling and drawing complicated mesh objects. Example meshes are developed including polyhedra such as the dodecahedron and Buckyball, and more complex shapes such as domes, tubes that undulate through space, and surfaces of revolution. Techniques are developed for rendering these objects either with flat shading or smooth shading.

Chapter 7. This chapter develops tools for flexible viewing of 3D scenes. The synthetic camera that forms perspective views is defined and its relationship to the low-level viewing tools OpenGL provides is discussed. A convenient Camera class is built that encapsulates the details of manipulating the camera and makes it easy to fly the camera through a scene in an animation.

The mathematics of perspective projections is then developed in detail along with a discussion of how OpenGL produces perspective views through matrix manipulations. The clipping algorithm that operates in homogeneous coordinate space, (which OpenGL also uses) is developed in detail. Methods for producing stereo views are also introduced.

Chapter 8. This chapter tackles ways to make pictures of 3D scenes more realistic. Shading models are developed that compute the various light components (ambient, diffuse, and specular) that reflect off of objects that are bathed in light. Methods for using OpenGL to set up light sources and alter the surface material properties of objects are described. The depth-buffer method of hidden surface removal that OpenGL uses is described in detail. Techniques for painting texture onto the surface of an object to make it more realistic are developed, for both procedural and image textures. Methods for adding simple shadows to pictures are developed.

Chapter 9. Chapter 9 discusses powerful graphics methods for manipulating images formed on a raster display. The basic pixmap is revisited as a fundamental object for storing and manipulating images, and a number of operations for pixmaps are developed. The classical Bresenham's algorithm for line-drawing is described in detail. Particular attention is given to filling a polygonal region. The phenomenon of aliasing that plagues graphics programmers is discussed and some techniques for reducing aliasing are developed. The techniques of dithering and error diffusion that produce the effect of more colors than a device can display are also described.

Chapter 10. This chapter is devoted to the design and drawing of smooth curves and surfaces. The theory of Bezier and B-spline curves is described, along with that for rational B-splines that leads to NURBS curves. Interactive curve design is discussed, wherein a designer specifies a set of control points with a mouse, and uses a curve generation algorithm to preview the curve. The curve may either interpolate the points or merely be attracted to them.

Complex surface design using Bezier, B-spline, and NURBS patches is also developed, and the issue of joining two patches together seamlessly is addressed.

Chapter 11. This chapter discusses some intricacies of the human color vision system, and addresses the problem of representing colors numerically. The CIE standard chromaticity diagram is described, along with various ways to use it in color calculations. Color gamuts of various devices are also discussed, as are different color spaces and conversions of colors between them.

Chapter 12. Chapter 12 introduces the powerful ray tracing approach to rendering scenes with high realism. Working through this chapter the student can develop first a primitive but simple ray tracer, and then add on capabilities to produce ultimately a full ray tracer that can produce dazzling images. Methods to intersect rays with various shapes are first described, followed by ways to render the objects using different shading models. Techniques for painting texture onto ray traced surfaces, both 3D textures such as marble and image-based textures, are described in detail. Methods to speed up ray tracing using bounding boxes are also developed.

Some great advantages of ray tracing are that it automatically performs hidden surface removal, and it is easy to create exact shadows of objects. In addition, it allows one to simulate the reflection of light from shiny surfaces as well as the refraction of light through a transparent object. Methods to accomplish each of these are described. The chapter ends with a discussion of ray tracing complex objects formed using Constructive Solid Geometry.

Suggested paths through the book.

All suggested paths include Chapters 1 through 5 as fundamental, although Chapter 4 can be perused independently by students familiar with vectors.

Possible course plans.

• For a one-semester undergraduate course where interest is highest in 3D graphics: Chapters 1 through 5, with parts of Chapter 6 and Chapter 7.
• If extending to a two-semester course add the rest of Chapter 7 and parts of Chapters 8, 9, and 10.
• For a one-semester undergraduate course where interest is highest in 2D and raster graphics: Chapters 1 through 3, with parts of Chapters 4 and 5.
• If extending to a two-semester course add parts of Chapters 7 and 8, and include Chapters 9 and 10, and parts of Chapter 11.
• For a one-semester graduate course where interest is highest in 3D graphics: Chapters 1 through 7, with parts of Chapters 8.
• If extending to a two-semester graduate course add the rest of Chapter 8, and include parts of Chapters 9, and all of Chapters 10 through 12.
• For a one-semester graduate course where interest is highest in 2D and raster graphics: Chapters 1 through 3, with parts of Chapters 4 through 8. Include Chapter 9.
• If extending to a two-semester course add Chapters 9, and parts of Chapters 10 through 12.

Book Appendices:

• Appendix 1: Obtaining and Installing OpenGL and GLUT
• Appendix 2: Mathematics for Computer Graphics
• Appendix 3: Utilities, Useful Classes and Routines
• Appendix 4: Scene Description Language (SDL)
• Appendix 5: Fractals and the Mandelbrot Set
• Appendix 6: Relative Drawing and Turtle Graphics

Supplements

Materials are available through the book's site on the internet (http://www.ecs.umass.edu/hill/book.) The source code in the book comes in a variety of fashions, some are simple functions and others are complete working programs. Those with a caption "Complete Working Application" have been compiled and tested thoroughly. Many code samples and utility libraries are available here, as well as images and textures. All may be used freely.

Acknowledgments

The first and second editions of this text have grown out of notes used in courses I [Hill] have been teaching at the University of Massachusetts for the last 25 years. During this time a large number of students have helped to develop demonstrations and make suggestions for improving the courses. They have also produced many exquisite graphical samples, some of which appear here. Some students and colleagues who have been particularly helpful in the first and second editions are Tarik Abou-Raya, Earl Billingsley, Dennis Chen, Daniel Dee, Brett Diamond, Jay Greco, Tom Kopec, Adam Lavine, Russell Turner, Bill Verts, Shel Walker, Noel Llopis, Russell Swan, Chandrashekhara A. , Emmanuel Agu, Tom Laramee, Chang Su, Xiongzi Li, Jung-Yao Huang, Anjul Srivastava, and Steve Morin. I apologize for any inadvertent omissions.

Several colleagues have provided inspiration and guidance during the germination of the three books. I am particularly grateful to Charles Hutchinson (Dartmouth College) for his support in starting the graphics effort at the university, to Michael Wozny (RPI) for his enthusiasm and encouragement in its development, and to Charlie Rupp for the many creative ideas in graphics he passed on to me. I would especially like to thank Daniel Bergeron (UNH), who made substantial contributions to the coherence and readability of the first edition.

I would like to thank the following individuals, and many others who are not mentioned by name, for their advice and help: Edward Hammerand, Arkansas State University, Deborah Walters, SUNY at Buffalo, Suzanne M. Lea, University of North Carolina at Greensboro, John Neitzke, Northeast Missouri State University, Norman Hosay, University of New Haven, David F. McAllister, North Carolina State University, John DeCatrel, Florida State University, Steve Cunningham, California State University, Stanislaus, Paul Heckbert, Carnegie Mellon University, Angelo Yfantis, University of Nevada, Lee H. Tichenor, Western Illinois University, Norman Wittels, Worcester Polytechnic Institute, Matthew Ward, Worcester Polytechnic Institute, Richard E. Neapolitan, Northeastern Illinois University, Jack E. Bresenham, Winthrop University, Michael Goss, Colorado State University, Bikash Sabata, Wayne State University, Mike Purapura, Alcoa, Norton Starr, Amherst College, and Paul T. Barham, North Carolina State University. Special thanks are due to Edward Angel at the University of New Mexico, who so rightly aimed me at OpenGL as the standard API to use for the second edition of this book, without his guidance the second edition would have been a far less successful project. A portion of the programming examples have been contributed by Rob Hall, University of Massachusetts, Amherst.

Portions of the book were written while on sabbatical working with Dr. Hermann Maurer (http://www.iicm.edu.maurer) at the Institute for Information Processing and Computer Supported Media, Technical University Graz in Graz, Austria, and portions were written while on a Fulbright grant at the Indian Institute of Science in Bangalore. I am grateful for the stimulation and support I received during these visits.

This book would not have been possible without my gifted partner Stephen Kelley. He and I met and joined forces in August of 2000 in connection with a National Science Foundation grant to teach the Fundamentals of Computer Graphics. Stephen developed all of the visuals and demonstrations for the course and in addition he was responsible for the video production and post editing.

While working on this book, Stephen was always helpful, enthusiastic, and a joy to work with. He also provided strong technical help to me through his deep knowledge of operating systems as well as his artistic sense necessary to teach people about computer graphics. Some people are particularly fortunate in the partner they choose for an immense project such as this and I was indeed fortunate to have Stephen work with me. Stephen would like to thank his family and friends for their support on all his endeavors.

Finally, thanks to my parents, to my wife Merilee, and to Greta, Jessie, and Rosy, for all their patience and support while these books slowly took shape.

Note to the reader: How to View the Stereo Pictures

Several stereoscopic figures appear in the book to clarify discussions of 3D objects. They appear as a pair of nearly identical figures placed side by side. To gain the full value of these stereo pictures coerce your left eye to look at the left-hand one and your right eye to look at the right-hand one, this may be facilitated by holding the figures at arm's length. This may take some practice: some people catch on quickly; others, after many bleary-eyed attempts; some people, never. Of course the figures still help to clarify the discussion even without the stereo effect.

One way to practice is to hold the index fingers of each hand upright in front of you, about 2 inches apart, and to stare through them at a blank wall in the distance. Each eye sees two fingers, of course, but two of the fingers seem to overlap in the middle. This overlap is precisely what is desired when looking at stereo figures: Each eye sees two figures, but the middle ones are brought into perfect overlap. When the middle ones fuse together like this, the brain constructs out of them a single 3D image. Some people find it helpful to place a piece of white cardboard between the two figures and to rest their nose on it. The cardboard barrier prevents each eye from seeing the image intended for the other eye.

Table of Contents

• Chapter 1 Introduction to Computer Graphics
• Chapter 2 Getting Started Drawing Figures
• Chapter 3 Additional Drawing Tools
• Chapter 4 Vector Tools for Graphics
• Chapter 5 Transformations of Objects
• Chapter 6 Modeling Shapes with Polygonal Meshes.
• Chapter 7 Three-Dimensional Viewing
• Chapter 8 Rendering Faces for Visual Realism
• Chapter 9 Tools for Raster Displays
• Chapter 10 Curve and Surface Design
• Chapter 11 Color Theory
• Chapter 12 Ray Tracing
• References
• Index

Preface

This book provides an introduction to computer graphics for students who wish to learn the basic principles and techniques of the field, and in addition want to write substantial graphics applications themselves. The field of computer graphics continues to enjoy tremendous vitality and growth. The growing number of feature-length animated movies has generated heady excitement about what graphics can do, and the ready access to graphics everyone now has through computer games and the internet is stimulating people to learn how to do it themselves.

Graphics systems are getting better, faster, and cheaper at a bewildering rate, and many new techniques are emerging each year from researchers and practitioners around the world, but the underlying principles and approaches comprise a stable and coherent body of knowledge. Much of this knowledge can be acquired through a single course in graphics, and this book attempts to organize the ideas and methods to bring the reader from the beginning with modest programming skills, to being able to design and produce significant graphics programs.

Intended audience.

This book is designed as a text for either a one- or two-semester course at the senior undergraduate or first-year graduate level. It can also be used for self-study. It is aimed principally for students majoring in computer science or engineering but will also suit students in other fields, such as physics and mathematics.

Mathematical background required.

The reader should have the equivalent of one year of college mathematics; knowledge of elementary algebra, geometry, trigonometry, and elementary calculus is assumed. Some exposure to vectors and matrices is useful but not essential; vector and matrix techniques are introduced in the context of graphics as they are needed, and an appendix also summarizes the key ideas.

Computer graphics tends to use a lot of mathematics to express the underlying geometric relationships between lines, surfaces, and the viewing 'eye'. Although no single mathematical notion is difficult in itself the number of tools required can be daunting. The book places particular emphasis on revealing the reasons for using this or that technique, and on showing how the objects of interest in a graphics program are properly described by the mathematical objects we use.

Computer programming background required.

In general, the reader should have at least one semester of experience writing computer programs in C, C++, or Java. A lot of the programming in graphics involves the direct translation of geometric relationships into code, and so uses straightforward variables, functions, arrays, looping, and testing, which is similar from language to language. C++ is used throughout the book, but much of the material will be familiar to someone with only a background in C.

It is helpful for the reader to have experience as well in manipulating struct’s in C or classes in C++. These are used to capture the rather complicated structure of some graphical objects that reside in a scene, where the object (say, a castle or an airplane) consists of many parts, and these parts themselves consist of complex subparts. Some experience with elementary linked data structures such as linked lists or trees is also desirable but not essential.

A reader with knowledge of C but not C++ will need to pick up the basics of object-oriented programming. We define a number of useful classes (such as the Canvas, Mesh, Scene, Camera, and Texture classes) and show why they are so convenient and usable. Some of the hallmarks of object-oriented programming, such as inheritance and polymorphism, are used in a few contexts to make the programmer’s job easier, but we don’t place inordinate emphasis on a pure object-oriented approach.

Philosophy

The book has been completely reorganized and rewritten from the first edition but the basic philosophy remains: Computer graphics is learned by doing it. One must write and test real programs to comprehend fully what is going on. A principal goal of the book is to show readers how to translate a particular design 'task' first into its underlying geometric components, to find a suitable mathematical representation for the objects involved, and finally to translate this representation into suitable algorithms and program code. Readers first learn how to develop simple routines to produce pictures. Then methods for producing drawings of ever more complex objects are presented in a step-by-step fashion.

Exercises and Problems

More than 350 practice exercises appear throughout the book. Most of these are of the 'stop-and-think' variety that don't require programming and allow readers to self-test their grasp of the material. Some urge the student to implement some of the new ideas in program code.

In addition, over 50 Case Studies appear at the end of chapters. They are normally programming projects suitable for homework assignments, and range from the simple to the challenging. These exercises expand on the material within their chapter, and often extend ideas in new directions. Whether or not the Case Studies are actually carried out by students, they should be studied as an integral part of the chapter.

A suggested 'Level of Effort' is associated with each Case Study, to indicate the approximate investment in time a student may need to accomplish the task. Programming is an unpredictable business and students’ abilities vary, but the rough guide is:

Level of Effort:
I: A simple project that can be implemented in an evening, suitable to be made due at the next class meeting.

II: A more extensive project that might be assigned due in a week, so that a student has thinking time for designing the program, and adequate time for the iterative (and sometimes frustrating) testing and debugging cycle that projects always seem to require.

III: A major project that might require three weeks of design and implementation effort. Such a project requires substantial design effort and careful program layout, but would (correctly) be viewed as a major accomplishment by the student.
The use of OpenGL

A frequent stumbling block as one first brushes up against computer graphics is getting started making pictures. It’s often easy enough to write a program, but there must be an underlying tool that ultimately draws the lines and curves on the screen. It’s a boon that such a tool exists and is readily available. OpenGL emerged from Silicon Graphics Inc. in 1992, and has become a widely adopted graphics application programming interface (API). It provides the actual drawing tools through a collection of functions that are called within an application. As described in Appendix 1, it is available (usually through free downloads over the internet) for all types of computer systems encountered in colleges, universities, and industry. It is easy to install and learn, and its longevity as a standard API is being nurtured by the OpenGL Architecture Review Board (ARB), an industry consortium responsible for guiding its evolution.

One aspect of OpenGL that makes it so well-suited for use in a computer graphics course is its 'device independence' or portability. Many university computer laboratories contain a variety of different computer types. A student can develop and run a program on any available computer. The same program can then be run on a different computer, for testing or grading purposes perhaps, and the graphics will be the same on the two machines.

OpenGL offers a rich and highly usable API for 2D graphics and image manipulation, but its real power emerges with 3D graphics. Using OpenGL students can progress rapidly and produce stunning animations in only a single-semester course.

The use of C++ as the programming language.

C++ is now familiar enough to most students in engineering and computer science through a first programming course that it is the natural choice of the language to use. It offers several advantages over C, such as passing parameters to functions by reference, which reduces the need for explicit pointers and simplifies reading the code. File I/O is also greatly simplified through streams, and in general the syntax for all kinds of I/O is clearer in C++ than in C. To keep things simple in this book, no emphasis is placed on implementing operators in C++.

Furthermore, it is easy to develop handy utility classes in C++, such as those for 2D or 3D points, a line, a window, or a color, which make code simpler and more robust. Students see the benefit of hiding the details of a geometric object within the object itself, and of imbuing the object with the ability to do things like draw itself, or test whether it intersects another object. The Canvas class developed in Chapter 3 offers a good example, as it maintains its own notion of a window, a viewport, and a current position, and it can draw basic figures with very little programming effort.

The emphasis on 3D computer graphics.

Because playing games on PC’s has become so popular, and so many dazzling animations are appearing in movies, students are particularly interested in developing 3D interactive graphics applications. Several chapters from the first and second editions have been rewritten and rearranged in order to get to topics in 3D graphics as quickly as possible. In a number of situations concepts are presented for the 2D case and the 3D case together, which helps to clarify the distinctions between the two.

Describing 3D scenes using the Scene Design Language

It can be very awkward and time consuming to design a scene of many 3D objects using 'raw' OpenGL commands (for example, describing a cube by its 6 faces each time it is used can become tedious.). So a simple Scene Design language (SDL) is introduced in Chapter 5 (and fully defined in an appendix). Using this language students can describe scenes with familiar terms like 'cube', 'sphere', and 'rotate', and build files of such instructions that can be read into their program at runtime. Code for an interpreter is provided in an appendix (and on the book’s web site) that can read SDL files and build a list of objects described in the file. It is then a simple matter to use OpenGL to draw the scene from the object list.

This same language and interpreter is put to fine use in Chapter 12 on ray tracing, where the student develops code for ray tracing a scene described using SDL. This permits students to design and ray trace much more elaborate and interesting scenes than would be possible otherwise.

Organization of the Book and Course Plans

There is much more in this book than can be covered in a one-semester course, or even in a two-semester course (which was also the case for the first two editions). The book has been arranged so the instructor can select different groups of chapters for close study, depending on the length of a course and the interests and backgrounds of the class. Several such paths through the book are suggested here, after the principal topics in each chapter are described.

Brief Overview of each Chapter.

Chapter 1. This chapter gives an overview of the computer graphics field, with examples of how various fields are using graphics. The different kinds of available graphics display systems are described, along with the types of primitives (polygons, text, images, etc.) that a graphic system displays. The chapter also describes some of the many kinds of input devices (mouse, tablet, data glove, etc.) in common use.

Chapter 2. This chapter gets students started with writing graphics applications. Programming using OpenGL is described and several complete line-drawing applications are developed, (including the popular Sierpinski gasket). Techniques are discussed for using OpenGL to draw various primitives such as polylines and polygons, and to use the mouse and keyboard in an interactive graphics application. Case Studies at the end of the chapter provide interesting programming projects to help students get a clear initial sense of how a graphics application is implemented. One Case Study focuses on building a class for which the application programmer can properly initialize and open an OpenGL window for drawing.

Chapter 3. This chapter develops the central notion of the window to viewport mapping, for sizing and positioning pictures on the display. Do-it-yourself management of windows and viewports is discussed, as is using OpenGL to handle the details. Zooming and panning to achieve interesting visual effects are described, as is simple animation of figures. A Canvas class is developed that encapsulates all of the drawing tools. The drawing of complex polygon-based figures, circles, and arcs is discussed. The parametric form for representing curves is discussed for both 2D and 3D curves.

Chapter 4. This chapter reviews vectors and their basic operations, and shows the great benefits to be gained by using vector tools in graphics. Students familiar with vectors can read this chapter quickly, focusing on how vectors describe relations between the geometric objects they are manipulating in their programs. One of the useful properties of vectors is that many vector operations may be treated without regard for the dimensionality of the space in question. The use of the cross product, on the other hand, is restricted to three dimensional vectors.

The notion of a coordinate frame is introduced, and it is shown how this makes it natural to work with homogeneous coordinates. Affine combinations of points are discussed to clarify the difference between vectors and points (to help avoid a common pitfall when writing graphics applications). Several applications involving interpolation, elementary Bezier curves, and line intersections are developed. The fundamental algorithm to clip a line against a convex polygon is developed in detail. (An interesting project for 2D ray tracing is suggested in a Case Study.)

Chapter 5. Transformations are of central importance in computer graphics, and students sometimes have difficulty developing intuition about them - particularly about 3D transformations. This chapter develops the underlying theory of transforming figures and coordinate systems using affine transformations in both the 2D and 3D cases. Homogeneous coordinates are used from the start for describing transformations. Special care is given to rotations in 3D, which are notoriously difficult to visualize.

Tools are added to the Canvas class begun in Chapter 3 to translate, scale, and rotate figures through the current transformation, and OpenGL’s matrix operations are enlisted to facilitate this. An overview of the OpenGL viewing pipeline is then developed, and the roles of the modelview, projection, and viewport transformations are described. Drawing of 3D objects using OpenGL’s tools is developed. The use of the Scene Description Language (SDL) is introduced, and it is shown how to use the SDL interpreter to read in a description of a 3D scene from a file, and to draw the objects.

Chapter 6. This chapter develops tools for modeling and drawing complicated mesh objects. Example meshes are developed including polyhedra such as the dodecahedron and Buckyball, and more complex shapes such as domes, tubes that undulate through space, and surfaces of revolution. Techniques are developed for rendering these objects either with flat shading or smooth shading.

Chapter 7. This chapter develops tools for flexible viewing of 3D scenes. The synthetic camera that forms perspective views is defined and its relationship to the low-level viewing tools OpenGL provides is discussed. A convenient Camera class is built that encapsulates the details of manipulating the camera and makes it easy to fly the camera through a scene in an animation.

The mathematics of perspective projections is then developed in detail along with a discussion of how OpenGL produces perspective views through matrix manipulations. The clipping algorithm that operates in homogeneous coordinate space, (which OpenGL also uses) is developed in detail. Methods for producing stereo views are also introduced.

Chapter 8. This chapter tackles ways to make pictures of 3D scenes more realistic. Shading models are developed that compute the various light components (ambient, diffuse, and specular) that reflect off of objects that are bathed in light. Methods for using OpenGL to set up light sources and alter the surface material properties of objects are described. The depth-buffer method of hidden surface removal that OpenGL uses is described in detail. Techniques for painting texture onto the surface of an object to make it more realistic are developed, for both procedural and image textures. Methods for adding simple shadows to pictures are developed.

Chapter 9. Chapter 9 discusses powerful graphics methods for manipulating images formed on a raster display. The basic pixmap is revisited as a fundamental object for storing and manipulating images, and a number of operations for pixmaps are developed. The classical Bresenham’s algorithm for line-drawing is described in detail. Particular attention is given to filling a polygonal region. The phenomenon of aliasing that plagues graphics programmers is discussed and some techniques for reducing aliasing are developed. The techniques of dithering and error diffusion that produce the effect of more colors than a device can display are also described.

Chapter 10. This chapter is devoted to the design and drawing of smooth curves and surfaces. The theory of Bezier and B-spline curves is described, along with that for rational B-splines that leads to NURBS curves. Interactive curve design is discussed, wherein a designer specifies a set of control points with a mouse, and uses a curve generation algorithm to preview the curve. The curve may either interpolate the points or merely be attracted to them.

Complex surface design using Bezier, B-spline, and NURBS patches is also developed, and the issue of joining two patches together seamlessly is addressed.

Chapter 11. This chapter discusses some intricacies of the human color vision system, and addresses the problem of representing colors numerically. The CIE standard chromaticity diagram is described, along with various ways to use it in color calculations. Color gamuts of various devices are also discussed, as are different color spaces and conversions of colors between them.

Chapter 12. Chapter 12 introduces the powerful ray tracing approach to rendering scenes with high realism. Working through this chapter the student can develop first a primitive but simple ray tracer, and then add on capabilities to produce ultimately a full ray tracer that can produce dazzling images. Methods to intersect rays with various shapes are first described, followed by ways to render the objects using different shading models. Techniques for painting texture onto ray traced surfaces, both 3D textures such as marble and image-based textures, are described in detail. Methods to speed up ray tracing using bounding boxes are also developed.

Some great advantages of ray tracing are that it automatically performs hidden surface removal, and it is easy to create exact shadows of objects. In addition, it allows one to simulate the reflection of light from shiny surfaces as well as the refraction of light through a transparent object. Methods to accomplish each of these are described. The chapter ends with a discussion of ray tracing complex objects formed using Constructive Solid Geometry.

Suggested paths through the book.

All suggested paths include Chapters 1 through 5 as fundamental, although Chapter 4 can be perused independently by students familiar with vectors.

Possible course plans.

• For a one-semester undergraduate course where interest is highest in 3D graphics: Chapters 1 through 5, with parts of Chapter 6 and Chapter 7.
• If extending to a two-semester course add the rest of Chapter 7 and parts of Chapters 8, 9, and 10.
• For a one-semester undergraduate course where interest is highest in 2D and raster graphics: Chapters 1 through 3, with parts of Chapters 4 and 5.
• If extending to a two-semester course add parts of Chapters 7 and 8, and include Chapters 9 and 10, and parts of Chapter 11.
• For a one-semester graduate course where interest is highest in 3D graphics: Chapters 1 through 7, with parts of Chapters 8.
• If extending to a two-semester graduate course add the rest of Chapter 8, and include parts of Chapters 9, and all of Chapters 10 through 12.
• For a one-semester graduate course where interest is highest in 2D and raster graphics: Chapters 1 through 3, with parts of Chapters 4 through 8. Include Chapter 9.
• If extending to a two-semester course add Chapters 9, and parts of Chapters 10 through 12.

Book Appendices:

• Appendix 1: Obtaining and Installing OpenGL and GLUT
• Appendix 2: Mathematics for Computer Graphics
• Appendix 3: Utilities, Useful Classes and Routines
• Appendix 4: Scene Description Language (SDL)
• Appendix 5: Fractals and the Mandelbrot Set
• Appendix 6: Relative Drawing and Turtle Graphics

Supplements

Materials are available through the book’s site on the internet ( http://www.ecs.umass.edu/hill/book. ) The source code in the book comes in a variety of fashions, some are simple functions and others are complete working programs. Those with a caption 'Complete Working Application' have been compiled and tested thoroughly. Many code samples and utility libraries are available here, as well as images and textures. All may be used freely.

Acknowledgments

The first and second editions of this text have grown out of notes used in courses I [Hill] have been teaching at the University of Massachusetts for the last 25 years. During this time a large number of students have helped to develop demonstrations and make suggestions for improving the courses. They have also produced many exquisite graphical samples, some of which appear here. Some students and colleagues who have been particularly helpful in the first and second editions are Tarik Abou-Raya, Earl Billingsley, Dennis Chen, Daniel Dee, Brett Diamond, Jay Greco, Tom Kopec, Adam Lavine, Russell Turner, Bill Verts, Shel Walker, Noel Llopis, Russell Swan, Chandrashekhara A. , Emmanuel Agu, Tom Laramee, Chang Su, Xiongzi Li, Jung-Yao Huang, Anjul Srivastava, and Steve Morin. I apologize for any inadvertent omissions.

Several colleagues have provided inspiration and guidance during the germination of the three books. I am particularly grateful to Charles Hutchinson (Dartmouth College) for his support in starting the graphics effort at the university, to Michael Wozny (RPI) for his enthusiasm and encouragement in its development, and to Charlie Rupp for the many creative ideas in graphics he passed on to me. I would especially like to thank Daniel Bergeron (UNH), who made substantial contributions to the coherence and readability of the first edition.

I would like to thank the following individuals, and many others who are not mentioned by name, for their advice and help: Edward Hammerand, Arkansas State University, Deborah Walters, SUNY at Buffalo, Suzanne M. Lea, University of North Carolina at Greensboro, John Neitzke, Northeast Missouri State University, Norman Hosay, University of New Haven, David F. McAllister, North Carolina State University, John DeCatrel, Florida State University, Steve Cunningham, California State University, Stanislaus, Paul Heckbert, Carnegie Mellon University, Angelo Yfantis, University of Nevada, Lee H. Tichenor, Western Illinois University, Norman Wittels, Worcester Polytechnic Institute, Matthew Ward, Worcester Polytechnic Institute, Richard E. Neapolitan, Northeastern Illinois University, Jack E. Bresenham, Winthrop University, Michael Goss, Colorado State University, Bikash Sabata, Wayne State University, Mike Purapura, Alcoa, Norton Starr, Amherst College, and Paul T. Barham, North Carolina State University. Special thanks are due to Edward Angel at the University of New Mexico, who so rightly aimed me at OpenGL as the standard API to use for the second edition of this book, without his guidance the second edition would have been a far less successful project. A portion of the programming examples have been contributed by Rob Hall, University of Massachusetts, Amherst.

Portions of the book were written while on sabbatical working with Dr. Hermann Maurer ( http://www.iicm.edu.maurer ) at the Institute for Information Processing and Computer Supported Media, Technical University Graz in Graz, Austria, and portions were written while on a Fulbright grant at the Indian Institute of Science in Bangalore. I am grateful for the stimulation and support I received during these visits.

This book would not have been possible without my gifted partner Stephen Kelley. He and I met and joined forces in August of 2000 in connection with a National Science Foundation grant to teach the Fundamentals of Computer Graphics. Stephen developed all of the visuals and demonstrations for the course and in addition he was responsible for the video production and post editing.

While working on this book, Stephen was always helpful, enthusiastic, and a joy to work with. He also provided strong technical help to me through his deep knowledge of operating systems as well as his artistic sense necessary to teach people about computer graphics. Some people are particularly fortunate in the partner they choose for an immense project such as this and I was indeed fortunate to have Stephen work with me. Stephen would like to thank his family and friends for their support on all his endeavors.

Finally, thanks to my parents, to my wife Merilee, and to Greta, Jessie, and Rosy, for all their patience and support while these books slowly took shape.

Note to the reader: How to View the Stereo Pictures

Several stereoscopic figures appear in the book to clarify discussions of 3D objects. They appear as a pair of nearly identical figures placed side by side. To gain the full value of these stereo pictures coerce your left eye to look at the left-hand one and your right eye to look at the right-hand one, this may be facilitated by holding the figures at arm’s length. This may take some practice: some people catch on quickly; others, after many bleary-eyed attempts; some people, never. Of course the figures still help to clarify the discussion even without the stereo effect.

One way to practice is to hold the index fingers of each hand upright in front of you, about 2 inches apart, and to stare through them at a blank wall in the distance. Each eye sees two fingers, of course, but two of the fingers seem to overlap in the middle. This overlap is precisely what is desired when looking at stereo figures: Each eye sees two figures, but the middle ones are brought into perfect overlap. When the middle ones fuse together like this, the brain constructs out of them a single 3D image. Some people find it helpful to place a piece of white cardboard between the two figures and to rest their nose on it. The cardboard barrier prevents each eye from seeing the image intended for the other eye.