Mathematical Structures for Computer Graphics (eBook)

Steven J. Janke (Autor)

eBook Download: EPUB

2014
John Wiley & Sons (Verlag)
978-1-118-71198-9 (ISBN)

Infos

A comprehensive exploration of the mathematics behind the modeling and rendering of computer graphics scenes

Mathematical Structures for Computer Graphics presents an accessible and intuitive approach to the mathematical ideas and techniques necessary for two- and three-dimensional computer graphics. Focusing on the significant mathematical results, the book establishes key algorithms used to build complex graphics scenes.

Written for readers with various levels of mathematical background, the book develops a solid foundation for graphics techniques and fills in relevant graphics details often overlooked in the literature. Rather than use a rigid theorem/proof approach, the book provides a flexible discussion that moves from vector geometry through transformations, curve modeling, visibility, and lighting models. Mathematical Structures for Computer Graphics also includes:

• Numerous examples of two- and three-dimensional techniques along with numerical calculations
• Plenty of mathematical and programming exercises in each chapter, which are designed particularly for graphics tasks
• Additional details at the end of each chapter covering historical notes, further calculations, and connected concepts for readers who wish to delve deeper
• Unique coverage of topics such as calculations with homogeneous coordinates, computational geometry for polygons, use of barycentric coordinates, various descriptions for curves, and L-system techniques for recursive images

Mathematical Structures for Computer Graphics is an excellent textbook for undergraduate courses in computer science, mathematics, and engineering, as well as an ideal reference for practicing engineers, researchers, and professionals in computer graphics fields. The book is also useful for those readers who wish to understand algorithms for producing their own interesting computer images.

Steven J. Janke, PhD, is Professor of Mathematics and Computer Science at Colorado College. He has over 20 years of teaching experience in the field of computer graphics and is the coauthor of Introduction to Linear Models and Statistical Inference, also published by Wiley.

Inhalt

Preface iii

1 Basics 1

1.1 Graphics Pipeline 2

1.2 Mathematical Descriptions 5

1.3 Position 6

1.4 Distance 9

1.5 Complements and Details 13

1.6 Exercises 17

2 Vector Algebra 21

2.1 Basic Vector Characteristics 22

2.2 Two Important Products 31

2.3 Complements and Details 42

2.4 Exercises 46

3 Vector Geometry 49

3.1 Lines & Planes 49

3.2 Distances 55

3.3 Angles 63

3.4 Intersections 65

3.5 Additional Key Applications 73

3.6 Homogeneous Coordinates 86

3.7 Complements and Details 90

3.8 Exercises 94

4 Transformations 99

4.1 Types of Transformations 100

4.2 Linear Transformations 101

4.3 Three dimensions 113

4.4 Affine Transformations 123

4.5 Complements and Details 134

4.6 Exercises 145

5 Orientation 149

5.1 Cartesian Coordinate Systems 151

5.2 Cameras 159

5.3 Other Coordinate Systems 182

5.4 Complements and Details 190

5.5 Exercises 193

6 Polygons & Polyhedra 197

6.1 Triangles 197

6.2 Polygons 213

6.3 Polyhedra 230

6.4 Complements and Details 245

6.5 Exercises 250

7 Curves & Surfaces 255

7.1 Curve Descriptions 256

7.2 Bézier Curves 268

7.3 B-Splines 278

7.4 NURBS 295

7.5 Surfaces 300

7.6 Complements and Details 311

7.7 Exercises 316

8 Visibility 321

8.1 Viewing 321

8.2 Perspective Transformation 323

8.3 Hidden Surfaces 333

8.4 Ray Tracing 344

8.5 Complements and Details 351

8.6 Exercises 356

9 Lighting 359

9.1 Color Coordinates 359

9.2 Elementary Lighting Models 364

9.3 Global Illumination 384

9.4 Textures 391

9.5 Complements and Details 403

9.6 Exercises 408

10 Other Paradigms 411

10.1 Pixels 412

10.2 Noise 421

10.3 L-Systems 435

10.4 Exercises 443

A Geometry & Trigonometry 447

A.1 Triangles 447

A.2 Angles 449

A.3 Trigonometric Functions 450

B Linear Algebra 455

B.1 Systems of Linear Equations 455

B.2 Matrix Properties 458

B.3 Vector Spaces 460

Rezensionen

"The book is suitable for undergraduate students of computer science, mathematics, and engineering, as well as an ideal reference for researchers and professionals in computer graphics." (Zentralblatt MATH, 1 June 2015)

Textauszug

Chapter 1
Basics

It is rather amazing that a finite rectangular array of colored dots (called pixels as an abbreviation of picture elements) is sufficient to display the nearly limitless collection of images we recognize as realistically or symbolically representing portions of our world. The power of combinatorics helps us to explain the situation (millions of possible colors for each pixel in the large display array), but we can hardly conceive of all the images we have already seen let alone those that are yet to be seen. From this reductionist viewpoint, the whole idea of computer graphics is to set the right pixels to the right color. Easier said than done. Yes, a plain red square is easy, but one that looks like it is made of bricks is tougher, and one that includes a human face taxes the best of known algorithms.

Of course, the computer graphics enterprise includes any and all manipulations of images. We can start from scratch and produce a photo-realistic image of a new airliner or perhaps construct a landscape design complete with a variety of plants. Maybe the challenge is to translate CAT (computerized axial tomography) scan data into an image of the brain or correct the color balance in a photo being readied for publication. To bring some order to the very long list of possibilities, it is helpful to consider two main categories: either we are generating images, or we are processing existing images. Both require mathematical tools, but the first category encompasses the broad mathematical approaches necessary to understand three-dimensional descriptions of objects and their interactions with light. The second category starts with an image and draws on the mathematics of transformations and filters necessary to convert it into a more useful visual representation. In this survey of mathematical tools that are useful in computer graphics, we will focus on the first category where we can start with the basics of mathematical descriptions and work through the generation and manipulation of objects in space.

1.1 Graphics Pipeline

As we examine the steps necessary to produce a new image on the computer screen, we are tracing what is often called the graphics pipeline. The pipeline analogy is intended to highlight the stages we go through both in designing images and in processing them on the computer to produce the final properly colored array of pixels on the display screen. As one frame is being completed, the next ismaking its way down the pipeline. Most modern hardware includes the main microprocessor (central processing unit, CPU), the graphics microprocessor (graphics processing unit, GPU), and various associated memory banks. The CPU and GPU work in parallel, as the CPU supplies descriptions of objects to the GPU which in turn processes the descriptions to determine which pixels on the screen need to be turned on. The exact order of all the required steps depends on the hardware and on the graphics software we use. However, we can make a more general description of the pipeline to enumerate the stages of image generation and set the context for understanding the associated mathematics. Our pipeline then looks like this:

1. Modeling. We need a mathematical description of objects, background, and light sources as well as a description of their placement in a scene. For more primitive objects such as buildings which are more or less constructed out of simple plane surfaces, the description includes a list of vertices and a list showing which vertices determine individual faces. For curved surfaces, we may attempt an accurate description (e.g., a sphere) or rely on an approximation with small flat triangles. These descriptions are, of course, just the beginning, as we need also to know the details of how the objects are placed in a scene and how light will interact with them. Mathematically, a geometric description including vertices and faces (surfaces) forms the kernel of our model, but certainly if the object is a tree or if there is fog affecting the lighting, the description may well require a deeper extension of the standard high school geometry. This modeling stage can be done with design software, allowing artists to manipulate the scene to reach the desired effect.
2. Transformation. Building a scene requires positioning objects relative to each other and includes rotation, scaling, and translation. Transformations reposition an object and convert its coordinate descriptions appropriately. Then, to view the scene, imagine a camera placed somewhere in space looking in a particular direction. (Alternatively, imagine your eye positioned in space looking at the scene.) Another transformation adjusts the mathematical descriptions so that they are relative to the camera position.
3. Visibility. Depending on where the camera is, we may not see the entire scene. Rather, some parts are outside the field of view and consequently can be ignored when generating the image. Even those objects within the field of view usually have some surfaces that are facing away from the camera and need not be considered. Some objects in the scene may be only partially visible since they fall both inside and outside the field of view. These objects are clipped (often after projection) so that only the relevant pieces continue down the graphics pipeline. Dealing with only the visible portions of a scene improves the efficiency of image generation because the calculations necessary to determine pixel color are computationally expensive.
4. Projection. Once we position the camera (or our eye), the actual image of the scene is produced on a two-dimensional surface in the camera (or on our retina). The three-dimensional scene is projected onto a two-dimensional screen. It is somewhat easier to imagine that there is a window placed just in front of our eye or camera and the scene itself is painted on this window. Positions of points in the scene, including how far away from the window they are, determine where on the window they are projected. Done correctly, the projection preserves the perspective in the scene and adds realism. If the dimensions of the window do not match the display screen, yet another transformation is necessary to convert window coordinates to display coordinates.
5. Rasterize. Mathematical descriptions of objects are usually continuous, allowing line segments, for example, to have an infinite number of points. At some stage of the graphics pipeline, the continuous line must be approximated by a finite set of screen pixels. This process requires some care to avoid distorting the line and introducing unintended artifacts, but then we have a finite set of pixels rather than an infinite set of points. The task of determining the colors of the pixels is now manageable and, if done appropriately, can maintain the illusion of a continuous image.
6. Shading. Light determines the exact shade of color that an object reflects, and that light depends on the position of light sources, their intensity, and their color. Some objects may be casting shadows and others may actually be reflecting light onto the rest of the scene. The geometry of light rays is essential for making these shading calculations. Positioning light sources and determining the material properties of objects occurs early in the pipeline, but it is late in the process when color calculations are actually completed for individual pixels.
7. Texturing. Describing the surface of an object as mathematically planar indicates that it is flat and smooth. Yet surfaces can be rough or covered with patterns of color. For example, in a computer game, the walls of a room may well be made of stone, so it becomes important to determine how light reflects off stone. In the texturing stage, this type of surface detail is added somewhat artificially by either copying the detail from existing images (e.g., taking a picture of real stone) or generating it mathematically with functional descriptions (e.g., some function describing how bumpy stone really is). To determine final colors for pixels, textures need to be generated and mapped to individual pixels.

This is the general notion of a graphics pipeline. The first stage, modeling, is often done interactively and builds the contents of the image, while all the rest of the stages taken together render the image on the screen. Depending on the hardware and software, the order of the rendering stages may be slightly permuted, but the scope of the process indicates the range of mathematical tools we need to explore (Figure 1.1).

Figure 1.1 Graphics pipeline

1.2 Mathematical Descriptions

To generate an image, we need to mathematically describe a scene. For a simple object such as a cube, we can list the position of its vertices and then list which vertices anchor each face. This is easy enough, but the positions of the vertices depend on the coordinate system we are using and it is not obvious which one we should use. Putting the origin of our coordinate system at the center of the cube makes describing the vertex positions easier, but there may be other objects in the scene which are good candidates for the origin. The answer may well be to use many coordinate systems and develop means of combining them into an all-inclusive scene.

If next to the cube there is a more organic object such as a flower, then we have an added difficulty because a flower is probably not well described by giving vertices and faces. There could be such a description, but there is also a special system of symbols (L-system) that was designed to capture the way plants grow, making a description both...

Produkt-Details

• Erscheint lt. Verlag: 18.9.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Grafik / Design
• Themenwelt: Informatik ► Office Programme ► Outlook
• Themenwelt: Informatik ► Software Entwicklung ► Spieleprogrammierung
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Naturwissenschaften
• Schlagworte: Angewandte Mathematik • Applied mathematics • Computer Game Software • Computer-Ratgeber • Computer Science • computer science</p> • Computerspiele • curve modeling • End-User Computing • Informatik • <p>Computer graphics • Mathematics • Mathematik • programming • two- and three-dimensional computer graphics • Vector Geometry • Visualisierung u. Computergraphik • Visualization & Computer Graphics
• ISBN-10: 1-118-71198-X / 111871198X
• ISBN-13: 978-1-118-71198-9 / 9781118711989