62,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
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.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 669
Veröffentlichungsjahr: 2014
Ähnliche
Table of Contents
Cover
Title Page
Copyright
Dedication
Preface
Chapter 1: Basics
1.1 Graphics Pipeline
1.2 Mathematical Descriptions
1.3 Position
1.4 Distance
1.5 Complements and Details
1.6 Exercises
Chapter 2: Vector Algebra
2.1 Basic Vector Characteristics
2.2 Two Important Products
2.3 Complements and Details
2.4 Exercises
Chapter 3: Vector Geometry
3.1 Lines and Planes
3.2 Distances
3.3 Angles
3.4 Intersections
3.5 Additional Key Applications
3.6 Homogeneous Coordinates
3.7 Complements and Details
3.8 Exercises
Chapter 4: Transformations
4.1 Types of Transformations
4.2 Linear Transformations
4.3 Three Dimensions
4.4 Affine Transformations
4.5 Complements and Details
4.6 Exercises
Chapter 5: Orientation
5.1 Cartesian Coordinate Systems
5.2 Cameras
5.3 Other Coordinate Systems
5.4 Complements and Details
5.5 Exercises
Chapter 6: Polygons and Polyhedra
6.1 Triangles
6.2 Polygons
6.3 Polyhedra
6.4 Complements and Details
6.5 Exercises
Chapter 7: Curves and Surfaces
7.1 Curve Descriptions
7.2 Bézier Curves
7.3 B-splines
7.4 Nurbs
7.5 Surfaces
7.6 Complements and Details
7.7 Exercises
Chapter 8: Visibility
8.1 Viewing
8.2 Perspective Transformation
8.3 Hidden Surfaces
8.4 Ray Tracing
8.5 Complements and Details
8.6 Exercises
Chapter 9: Lighting
9.1 Color Coordinates
9.2 Elementary Lighting Models
9.3 Global Illumination
9.4 Textures
9.5 Complements and Details
9.6 Exercises
Chapter 10: Other Paradigms
10.1 Pixels
10.2 Noise
10.3 L-Systems
10.4 Exercises
Appendix A: Geometry and Trigonometry
A.1 Triangles
A.2 Angles
A.3 Trigonometric Functions
Appendix B: Linear Algebra
B.1 Systems of Linear Equations
B.2 Matrix Properties
B.3 Vector Spaces
References
Index
End User License Agreement
Pages
xiii
xiv
xv
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
Guide
Cover
Table of Contents
Preface
Chapter 1: Basics
List of Illustrations
Figure 1.1
Figure 1.2
Figure 1.3
Figure 1.4
Figure 1.5
Figure 1.6
Figure 1.7
Figure 1.8
Figure 1.9
Figure 1.10
Figure 1.11
Figure 2.1
Figure 2.2
Figure 2.3
Figure 2.4
Figure 2.5
Figure 2.6
Figure 2.7
Figure 2.8
Figure 2.9
Figure 2.10
Figure 2.11
Figure 2.12
Figure 3.1
Figure 3.2
Figure 3.3
Figure 3.4
Figure 3.5
Figure 3.6
Figure 3.7
Figure 3.8
Figure 3.9
Figure 3.10
Figure 3.11
Figure 3.12
Figure 3.13
Figure 3.14
Figure 3.15
Figure 3.16
Figure 3.17
Figure 3.18
Figure 3.19
Figure 3.20
Figure 3.21
Figure 3.22
Figure 4.1
Figure 4.2
Figure 4.3
Figure 4.4
Figure 4.5
Figure 4.6
Figure 4.7
Figure 4.8
Figure 4.9
Figure 4.10
Figure 4.11
Figure 4.12
Figure 4.13
Figure 4.14
Figure 4.15
Figure 4.16
Figure 4.17
Figure 5.1
Figure 5.2
Figure 5.3
Figure 5.4
Figure 5.5
Figure 5.6
Figure 5.7
Figure 5.8
Figure 5.9
Figure 5.10
Figure 5.11
Figure 5.12
Figure 5.13
Figure 5.14
Figure 6.1
Figure 6.2
Figure 6.3
Figure 6.4
Figure 6.5
Figure 6.6
Figure 6.7
Figure 6.8
Figure 6.9
Figure 6.10
Figure 6.11
Figure 6.12
Figure 6.13
Figure 6.14
Figure 6.15
Figure 6.16
Figure 6.17
Figure 6.18
Figure 6.19
Figure 6.20
Figure 6.21
Figure 6.22
Figure 6.23
Figure 6.24
Figure 6.25
Figure 6.26
Figure 6.27
Figure 6.28
Figure 6.29
Figure 6.30
Figure 6.31
Figure 6.32
Figure 6.33
Figure 7.1
Figure 7.2
Figure 7.3
Figure 7.4
Figure 7.6
Figure 7.5
Figure 7.7
Figure 7.8
Figure 7.9
Figure 7.10
Figure 7.11
Figure 7.12
Figure 7.13
Figure 7.14
Figure 7.15
Figure 7.16
Figure 7.17
Figure 7.18
Figure 7.19
Figure 7.20
Figure 7.21
Figure 7.22
Figure 7.23
Figure 7.24
Figure 7.25
Figure 8.1
Figure 8.2
Figure 8.3
Figure 8.4
Figure 8.5
Figure 8.6
Figure 8.7
Figure 8.8
Figure 8.9
Figure 8.10
Figure 8.11
Figure 8.12
Figure 8.13
Figure 9.1
Figure 9.2
Figure 9.3
Figure 9.4
Figure 9.5
Figure 9.6
Figure 9.7
Figure 9.8
Figure 9.9
Figure 9.10
Figure 9.11
Figure 9.12
Figure 9.13
Figure 9.14
Figure 9.15
Figure 10.1
Figure 10.2
Figure 10.3
Figure 10.4
Figure 10.5
Figure 10.6
Figure 10.7
Figure 10.8
Figure 10.9
Figure 10.10
Figure 10.11
Figure 10.12
Figure A.1
Figure A.2
Figure A.3
Figure A.4
Figure A.5
List of Tables
Table 6.1
Table 6.2
Table 6.3
Table 6.4
Table 6.5
Table 8.1
Table 8.2
Table 8.3
Table 9.1
Table A.1
Mathematical Structures for Computer Graphics
Steven J. Janke
Copyright © 2015 by John Wiley & Sons, Inc. All rights reserved
Published by John Wiley & Sons, Inc., Hoboken, New Jersey
Published simultaneously in Canada
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.
Library of Congress Cataloging-in-Publication Data:
Janke, Steven J., 1947- author.
Mathematical structures for computer graphics / Steven J. Janke, Department of Mathematics,
Colorado College, Colorado Spring, CO.
pages cm
Includes bibliographical references and index.
ISBN 978-1-118-71219-1 (paperback)
1. Computer graphics–Mathematics. 2. Three-dimensional imaging–Mathematics. I. Title.
T385.J355 2014
006.601′51–dc23
2014017641
To Deborah
Preface
Computer graphics includes a large range of ideas, techniques, and algorithms extending from generating animated simulations to displaying weather data to incorporating motion-capture segments in video games. Producing these images requires an array of artistic, technical, and algorithmic skills. Software can help by offering a flexible user interface, but under the hood, mathematics is orchestrating the images. Not everything in graphics begins with a mathematical result, but nearly everything is founded on mathematical ideas, because ultimately algorithms direct the computer to light up specified pixels on the screen.
The evolution of computer graphics started in the early 1970s, and since then key mathematical ideas and techniques have risen to the surface and have proved their worth in solving graphics problems. This text tries to lay out these ideas in a way that is easily accessible to those interested in a sound footing in the field and to those software engineers eager to fill in gaps where their understanding faltered.
Organized to mimic the flow of a standard graphics course, this manuscript grew from the notes for an undergraduate graphics course taught regularly over a span of 20 years. Appropriate mathematical ideas are introduced along with the details of various techniques. The style is more informal than formal, yet the approach includes thorough derivations in the hope that context and careful arguments will build confidence in constructing new approaches and new algorithms.
One or two courses in calculus should give the readers sufficient mathematical maturity to work through the text, and even if their linear algebra background is limited to matrix multiplication, they should be able to develop some useful algebraic and geometric tools. Standard mathematics courses rarely have the time to cover all the important mathematical constructs used in graphics such as the description of curves necessary for surface design, or homogeneous coordinates necessary for affine transformations. This text fills in those gaps and looks behind the results enough to understand how they fit into the rest of mathematics. It does not rely on the rigorous theorem/proof format, and instead uses intuition and example to develop careful results. Although the mathematics is interesting in its own right, the text hopefully does not lose sight of the ultimate goal which is to produce interesting and useful images.
There are plenty of examples and exercises to help fix the ideas and several suggestions of other directions to investigate. At the end of each chapter (except the last), there is a section titled Complements and Details that collects a few historical notes, several calculation details, and occasionally some ideas which may lead to interesting tangents. The text is independent of any particular graphics system, but it does have OpenGL in mind when presenting details of the viewing frustum in the chapter on visibility. Otherwise, there are programming exercises throughout, which can be done with almost any language and graphics interface.
Chapters 1–3 carefully develop vector geometry assuming very little background. They highlight the difference between vectors and points and emphasize the connection between geometry and algebra. Coordinate-free expressions and homogeneous coordinates are both introduced.
Chapters 4 and 5 examine transformations, both linear and affine. Along the way, they develop basic matrix algebra, construct various transformations including the perspective transformation, examine coordinate systems (world, local, and camera), unravel Euler angles and quaternions, and consider alternate coordinate systems.
Chapters 6 and 7 develop modeling techniques through an exploration of polygons (particularly triangles), polyhedra, parametric description of curves, Lagrange interpolation, Bézier curves, splines, nonuniform rational B-splines (NURBS), and surface construction.
Rendering is covered in Chapters 8 and 9, starting with a look at the view frustum, hidden surface algorithms, and simple ray tracing. Then an elementary lighting model is examined in detail before introducing shading, shadows, the bidirectional reflectance distribution function (BRDF), the basics of radiosity, and texture mapping.
The final chapter collects three separate mathematical techniques that represent arguably different paradigms. Bresenham's algorithm starts a discussion of pixel-based mathematics, Perlin's noise prompts a visit to random distributions, and L-systems offer an alternative algebraic description of organic forms.
When used as a course text, the first five chapters as well as selections from the last five could serve to cover an appropriate amount of material. The idea is to rely on the text for the mathematics and supplement it with algorithms perhaps specific to the available graphics systems. There are both mathematical and programming exercises in each chapter. Throughout the examples in the text, the calculation results are rounded to two or three decimal places. This still leads to round-off error, and a good exercise for the student is to reconcile any perceived discrepancies in the results.
In the way of acknowledgement, first note that most of the figures in the text were prepared using Mathematica®. Second, many thanks go to my graphics students over the years who prompted me to learn the nuances of the subject and who offered constructive feedback on my courses. Thanks also go to Cory Scott whose comments on the completed manuscript were essential and to Craig Janke for cover ideas along with continued encouragement. Finally, without my wife Deborah and her unending support, this project would have dissolved on the screen.
STEVEN J. JANKE
Colorado College, 2014
Chapter 1Basics
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:
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.
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.
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.
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.
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.
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.
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 easier and more succinct.
The cube may be made of wood, making the faces more bumpy than smooth and making light reflect in a way that shows the grain. The scene description is now moving further and further from a simple list of vertices, and we will need additional means of describing the detail.
The larger goals are to make the mathematical description as simple as possible, as easy as possible to alter during the design process, and as independent of any fixed coordinate system as possible. Then the resulting computer code will be general and flexible.
To draw an object on the computer screen, we need to identify which pixels to light up (and what color to make them). Since most computer monitors are rectangular, locating a pixel usually means specifying its horizontal and vertical position in the rectangular array of pixels which make up the entire screen. This seems simple enough, but our common descriptions of objects are not usually in terms of the horizontal and vertical distances to each point. A cartoon character's head might be described as “oval, with a button nose, and beady eyes.” And a tree may be “conical with short drooping branches covered with folded, heart-shaped leaves.” To draw these objects on the screen, there is no escape from determining the horizontal and vertical positions of appropriate pixels, but the challenge forthe graphics programmer is to find ways of describing the objects that are between the intuitive common way and the hard-core quantitative way that lists the horizontal and vertical positions of all the points. Unfortunately, qualitative descriptions of objects are not easily incorporated into computer programs, so it makes sense, at least at first, to concentrate on more quantitative descriptions.
1.3 Position
In the geometry of Euclid, there are no coordinates. Instead, geometric objects are compared to each other in order to understand their features; lines are compared to other lines, and triangles to triangles. This approach is not sufficient for computer graphics because we eventually need the absolute position of an object in order to determine which pixels on the screen to turn on. In the seventeenth century, Descartes, the philosopher and mathematician, made attempts to connect algebra and geometry, and although he did not develop coordinate systems as we know them now, we still refer to the rectangular coordinate system as the Cartesian coordinate system. This is the default coordinate system for computer graphics and the one we are all familiar with from high school (Figure 1.2).
Figure 1.2 2D Cartesian coordinate system
In two dimensions, we have two perpendicular axes, the horizontal one labeled and the vertical one labeled . They cross at a unique origin labeled . Each is a number line increasing either to the right or up. Any point in the plane has a coordinate representation which is a pair of numbers indicating how far to go horizontally (negative distance indicates left of the origin) and then how far to go vertically (negative here means down from the origin). Note that this is a unique representation; any pair of numbers determines exactly one point in the plane and any point determines exactly one pair of numbers.
In computer graphics, the fundamental task is to locate points in a scene, and to make that process easier and perhaps more intuitive, we define a new mathematical object called a vector.
Definition 1.1
A two-dimensional vector is an object representing a displacement in the plane. It has a length and a direction.
A vector is intended to describe how to get from one point to another. If our vector has a length of five units and is pointing to the right, then it represents moving from an arbitrary point to a point five units to the right. It is important to note that the vector is not positioned at any particular place in the plane. It represents displacement, not position. Once we apply the displacement to a point, we reach another point that is positioned in the plane. Visually, vectors are represented as arrows; they have length and direction. As we will soon see, a convenient way of describing a two-dimensional vector mathematically is to give two numbers indicating its displacement in the horizontal and vertical directions. Often the representative arrow is drawn with its tail at the origin, say, and its head (the end with the arrow) positioned to show the displacement. This can be a little confusing because the vector is really not positioned at any particular point in the plane; setting the tail at the origin is just a default approach to representing the vector visually (Figure 1.3).
Figure 1.3 Vectors indicating displacement
We now can give a slightly different perspective on the standard Cartesian coordinate system. To describe a two-dimensional (2D) coordinate system, we specify a unique origin and two vectors. For the standard system, these vectors both have the same unit length and are perpendicular to each other. The vector with direction along the positive -axis is usually referred to as , and the one in the direction of the positive -axis is denoted as . Describing any point in the plane is now a matter of indicating how many unit steps in the direction of and how many in the direction of we need to take to reach the point. For example, the point is the point we reach when starting at the origin, then taking 4 unit steps in the -direction, and finally 1.5 unit steps in the -direction. As you may have guessed, since and have unit length, the algebra of vectors allows us to represent the point as . This will prove to be useful in making geometric calculations (Figure 1.4).
Figure 1.4 Vectors and
Without much effort, we can move to three-dimensional space by adding a third axis labeled perpendicular to the - and y-axes. With our vector perspective, we have added a new vector, often called . Now each point in space is represented by a unique triple of numbers, or in terms of vectors as a combination of the three vectors and .
The nature of the Cartesian coordinate system depends on the direction of the unit vectors. The standard two-dimensional system has vector pointing to the right along the positive -axis and the perpendicular vector pointing up. However, we might also let point down. This is actually the default coordinate system for the computer screen when using some standard programming languages. An easy transformation can get us back to the standard system with pointing up, and usually this is desirable. As we will see later, we could pick the two vectors for a system so that they are not perpendicular. These systems may prove useful in describing some objects, so we will have to develop transformations that allow us to easily move between all these various possibilities.
In three dimensions, there is one, often troubling, complication. There are two geometrically different ways to add a third vector and this time the mathematical consequences are not trivial. Basically, the third vector could point in the direction designated in Figure 1.5 or in the opposite direction. To standardize, we designate a right-handed system to be one where if we position our right hand with the fingers pointing in the direction of and adjust so that when we curl our fingers they point in the direction of , then our thumb points in the direction of . Figure 1.5 shows a right-handed coordinate system. It is important to distinguish right-handed from left-handed systems in order to keep track of whether vectors point out of or into an object.
Figure 1.5 Right-handed coordinate system
1.4 Distance
Now that we have set up a coordinate system, we turn to the fundamental problem of determining the distance between two points. This is a job for the venerable Pythagorean theorem, named after an itinerant teacher of ancient Greece who led his devoted followers through a wide range of ideas drawn from topics as diverse as number theory and vegetarian diets. He is credited for the famous theorem about right triangles, but the result was undoubtedly known much earlier by at least Babylonian scholars if not others 1.
Theorem 1.1 (Pythagorean Theorem)
In a right triangle, the sum of squares of the two legs equals the square of the hypotenuse.
Proof Sketch.
First remember that a right triangle is one with a 90° angle. Figure 1.6 shows four identical right triangles with legs and . They are arranged in a large square on the left and then rearranged in the same large square on the right. On the left, the area not taken up by triangles is equal to , the area of the labeled square in the middle. On the right, the area outside the triangles is in two pieces equaling . Hence the Pythagorean theorem: .
Figure 1.6 (a,b) Visual proof of the Pythagorean theorem
This result allows us to calculate the distance between any two points on the screen or in an arbitrary plane. Simply, the distance is the length of the hypotenuse of a right triangle. The two points are the opposite corners of a rectangle with sides parallel to the vectors and which determine the coordinate system. The distance between the corners of the rectangle is the length of the hypotenuse of a right triangle. The legs of the right triangle are easy to find by taking differences of the Cartesian coordinates for the two points. If one point has coordinates and the other , then the Pythagorean theorem gives
In three dimensions, the distance between points is not much harder to find once we visualize two right triangles. Suppose the two points are labeled and . This time, they can be thought of as the opposite corners of a rectangular box where the faces of the box are parallel to the three coordinate planes (Figure 1.7). The distance between the points is the length of the hypotenuse of the right triangle . The leg is just one edge of the box, called in the figure. The leg is a diagonal of one face of the box and hence the hypotenuse of triangle . By the Pythagorean theorem,
Since , we finally have
where , , and are all edges of the rectangular box.
Figure 1.7 Distance in three dimensions
The Pythagorean theorem is essential to computer graphics. Dropping perpendiculars and forming right triangles is one of the most useful tools in the mathematics toolbox. Triangles are everywhere in graphics, and, in fact, they are central to all of geometry. Projections and visibility questions invariably involve drawing a triangle usually including the eye position as a vertex. Complicated objects are usually built from triangles because triangular faces are guaranteed to be planar; they can be drawn in a plane. (This is unlike quadrilateral faces which might be twisted so that the four vertices do not all lie in a plane.) So calculations with triangles are central to computer graphics and we rely both on the Pythagorean theorem and on a generalization that covers triangles of arbitrary angles. To reach this generalization, we use the cosine function (reviewed in Appendix A).
Theorem 1.2 (Law of Cosines)
In a triangle with sides , let the angle be opposite the side . Then we have .
Proof Sketch.
Note that is an angle inside the triangle, so we know it is less than 180°. When , then and we have a right triangle so the Pythagorean theorem applies and the law of cosines reduces to it. In general, we try making right triangles out of the original triangle to see why the law holds. There are actually two cases: γ > 90° and γ < 90°. Figure 1.8 shows the first case.
In the figure, the side is perpendicular to the baseline . Then we have three triangles: the given triangle and two right triangles and . With the lower case letters indicating lengths, apply the Pythagorean theorem to the triangle to get
Applying the Pythagorean theorem to the second right triangle, gives
Notice that is the supplement of (i.e., they add to 180°). This means , and since , we now have the result .
For the second case where γ < 90°, we proceed just as above by drawing a new side and building new right triangles. The algebra is just a little different (Section 1.5).
Figure 1.8 Law of cosines
Example 1.1 (Triangles in 3D)
Suppose we have three vertices in three dimensions complete with coordinates . Although we are in three dimensions, the triangle does lie in a single plane, so using the tools we developed we can completely describe it. Applying the Pythagorean theorem, first we get the lengths of all the sides:
Comparing the squares of the lengths, we can determine whether each angle is larger or smaller than a right angle. For example, since , we know that must be larger than a right angle. That makes the other two smaller than a right angle because the sum of all angles must be 180° (or radians).
Now, an application of the law of cosines gives us the actual angle:
This indicates that . The same procedure gives the other two angles: and .
Once we can completely describe the triangle, we should be able to determine whether a light ray hits it. This is a common problem that we will solve later by first finding where the light ray hits the plane of the triangle and then deciding whether the intersection point is inside or outside the triangle. In order to solve this problem, it helps to translate the tools we are using to the language of vectors, and this we do in the next chapter.
1.5 Complements and Details
1.5.1 Pythagorean Theorem Continued
No one knows how Pythagoras proved his theorem because even the basic facts of his life (about 500 BCE) are a bit sketchy. Since then, there have been many proofs devised including a somewhat complicated one given by Euclid in Proposition 47 of Book I of his Elements (about 300 BCE). Just a little later, the illustrated square on the left in Figure 1.6 appeared in a Chinese manuscript, and in 1876 a New England education journal published a proof apparently constructed by James A. Garfield who later became President of the United States. Most of the proofs involve constructing geometric figures in one way or another. (A more complete history of the theorem is given in 1.)
For a slightly more algebraic approach to the proof in Figure 1.6, notice that the area of the large square in the left half of the figure is . Yet, this must be equal to the area of four triangles plus the area of the square in the middle ().
One important number-theoretic consequence of the theorem emerges when we draw the right triangle with both legs equal to . Then the hypotenuse is and this number was important to the Greeks because it was incommensurable. To us now, this means the number is irrational; it cannot be represented as the quotient of two integers. The discovery of irrational numbers was both progress and an annoyance to the Greeks.
Other right triangles are equally surprising. If the legs are 3 and 4, then the hypotenuse is 5. This set of three integers is called a Pythagorean triple and is used frequently by carpenters to quickly construct a right angle. There are infinitely many of these Pythagorean triples and a detailed theory surrounding them (see Exercises for further examples).
1.5.2 Law of Cosines Continued
To derive the law of cosines, we noted that, if we do not have a right triangle, there are two cases: one where , and one where . The first case was covered in Figure 1.8, so now we consider the second case.
When , our triangle looks like the one in Figure 1.9. We have constructed two right triangles by adding the perpendicular . The Pythagorean theorem says
Figure 1.9 Law of cosines:
Note that and . By adding to both sides of , we have
Rearranging just a little gives the law of cosines.
1.5.3 Law of Sines
Yes, there is a law of sines as well as a law of cosines.
Theorem 1.3 (Law of Sines)
In a triangle , where the angles at the vertices are, respectively, , and the sides opposite the vertices are , respectively, we have
where is the diameter of the circumcircle for the triangle.
Proof Sketch.
Any triangle can be inscribed in a circle so that the three vertices are on the circle (Appendix A). Figure 1.10 shows one such arbitrary triangle, . Draw diameter CD and dotted line DB. Since is inscribed in a semicircle, it is a right triangle. The sine of is . But angle equals angle because they cut the same arc from the circle. Hence or . The same argument for each angle shows the ratio of the sine to the side opposite is always the reciprocal of the diameter.
The diameter in Figure 1.10 cuts through the triangle. There is a second case where the diameter is outside the triangle. The argument changes only slightly (see Exercises).
Figure 1.10 Law of sines
The common ratio of the sine to the side opposite is equal to the reciprocal of the diameter of the circumcircle for the triangle.
1.5.4 Numerical Calculations
One slight hitch for the graphics programmer is the fact that calculating the square root and trigonometric functions (e.g., sine, cosine, and tangent) takes time. Modern processors incorporate floating point operations much more efficiently that they once did, but still, floating point arithmetic is slower than integer arithmetic. Making graphics programs run quickly requires attention to the length of calculations.
Consider the square root first. If the task is to simply compare distances, using the square of the distances works equally well. However, if the square root is actually needed, then often an approximation can work. To illustrate, suppose we need to calculate . Start with a guess, say . Then should be if it is the square root. It probably is not, so take a next guess ; this is the mean of the first guess and the quotient. Similarly, we can define successive guesses. For example, to find , let 10 be the first guess. Then and . This last guess is accurate to two decimal places. (This algorithm for square root is actually Newton's method applied to the square root function.) Of course, this approximation is useful only if the time required to execute it is reasonably short.
Calculating the sine and cosine causes similar timing issues. One solution is to precalculate a table of common values and simply look up the answer when needed. For example, we could calculate the sine and cosine for all angles of radian measure where . If we need more accuracy, we can recall the Taylor series expansion (from calculus) of sine and cosine for small angles. The first few terms of these expansions (for radian measure) give
The Taylor series approximations are more accurate for small angles, so one scheme is to precalculate a table as before, let be the difference between the desired angle and the closest angle in the table (say ), approximate the sine or cosine of , and then use the addition formulas for sine and cosine to get or .
1.6 Exercises
1
. The standard Cartesian coordinate system has the vectors
,
, and
positioned to form a right-handed system. We can replace any or all of these vectors with one pointing in the opposite direction. This gives us a total of eight different coordinate systems. Determine which of these are right-handed systems.
2
. Consider an isosceles right triangle. (This is one where both legs are equal.) Construct a square on each of the three sides. The Pythagorean theorem says that the sum of the areas of the two smaller squares equals the area of the larger square. By dividing each square into triangles equal to the initial triangle, establish the theorem in this special case.
3
. For another proof of the Pythagorean theorem, consider
Figure 1.11
. Triangle
is a right triangle with the right angle at
. Each of the smaller triangles is a right triangle and each is similar to
. This means that the ratio of sides in one triangle equals the ratio of sides in another. Find two of these equations which when added together give the Pythagorean theorem.
Figure 1.11 Alternate proof of Pythagorean theorem
4
. The vertices
,
, and
form a triangle. Find the perpendicular distance from the origin
to this triangle using right triangles.
5
. Find the three angles of the triangle with vertices
,
,
.
6
. The four vertices
,
,
, and
form four triangles in space. Determine which of the four, if any, are right triangles.
7
. Given two points in the plane, where are all the points that are at the same distance from both these selected points? Given three points in the plane that are not on a line, where are all the points equidistant from all three?
8
. Describe all points that are at a fixed distance from a solid square in the plane. (The distance from a point to the square is the minimum distance between the point and any point on the square.)
9
. For some right triangles, the two legs and the hypotenuse are all integers. For example, sides 3, 4, 5 form a right triangle. We call the triple
a Pythagorean triple. Of course, any multiple of these three numbers [such as
] also forms a Pythagorean triple. Find two Pythagorean triples that are not multiples of
or of each other.
10
. Pick two positive integers
and
such that one is odd, one is even, and
. Show that
,
, and
form a Pythagorean triple as defined in the previous exercise. If, in addition,
and
do not have a common divisor greater than
, the triple is said to be primitive and all primitive triples can be found in this way.
11
. The vectors
and
define the two-dimensional coordinate system. Suppose we replace
with the vector
. In this new coordinate system, what are the coordinates of the point with old coordinates
?
12
. If we use the vectors
and
to define a Cartesian coordinate system and we move the origin to the point
in the original coordinate system, what are coordinates of the point with old coordinates
Chapter 2Vector Algebra
Vectors are essential for computer graphics. As we saw in Chapter 1, they represent displacement as we describe an object by moving from point to point. If we wish to move from point to point , an arrow drawn starting at point and ending at point tells us which direction to go and how far to go. This arrow is the vector and has both direction and length.
Displacement alone is not sufficient reason to develop the notion of a vector. It turns out that we can define operations between vectors that connect with geometric operations. For example, adding two vectors means adding two displacements and we can geometrically understand what it should mean to add displacements. Although not as intuitive, we can also define the multiplication of two vectors in such a way that there are geometric interpretations of the result. The plan then is to develop an algebra of vectors that corresponds to geometric operations and may make the task of describing geometric objects for images just a little easier.
Vectors are especially useful because they are independent of any particular coordinate system. A displacement in a given direction makes sense regardless of which coordinate system we use. It may be that in a particular coordinate system the displacement description is “two units to the left and one unit up” while in another system, perhaps one rotated relative to the first, the description is very different. The vector description might change, but the direction and length of the vector does not. So there is some hope that vector algebra will be general enough to help describe objects without the added detail of which coordinate system we are in. This can make graphics programs more efficient, even though at some stage of a calculation actually finding the direction and length of a vector does require settling on some coordinate system.
2.1 Basic Vector Characteristics
When we talk about points and vectors more abstractly, we will keep them separate symbolically by using upper case letters (e.g., ) for points and a small arrow over lower or upper case letters (e.g., or ) for vectors. When we need to describe a particular point or a particular vector, we simply use Cartesian coordinates for a default description and use ordered pairs in two dimensions and ordered triples in three dimensions. With this notation, there is still ambiguity between points and vectors, but usually the context resolves the confusion.
For studying geometric transformations, matrices play an essential role, and it makes sense to represent vectors and points as columns of numbers (just small matrices). So in two dimensions, a vector which represents a displacement of five units to the left and three units up is represented as a column matrix with two entries.
A point with coordinate and coordinate 3 is represented exactly the same way. Since it is awkward to write columns of coordinates in normal text, we will use the ordered pair or ordered triple notation as well as the column matrix notation depending on which is clearer.
Starting in two dimensions, let point have coordinates and . Then let be the vector from point to point .
Here, we take the coordinates of and subtract the coordinates of , component by component, to get . The vector is the displacement: four units in the -direction and two units in the -direction. The description is relative to a default Cartesian coordinate system.
To find the length and direction of the vector , consider the vector as the hypotenuse of a right triangle (Figure 2.1) with angle describing the direction. The length of is denoted by , and using the Pythagorean theorem we get . We find the direction angle from the sine or cosine (or both). For , and hence (measured counterclockwise from the horizontal direction which points to the right).
Figure 2.1 Vector length
It is important to note that the vector denotes a displacement and therefore could represent the displacement between two other points, say and . That is, the vector is not tied down in space.
Example 2.1 (Building a Regular Polygon)
To see how vectors might prove useful in describing objects, imagine an image of a regular hexagon. It is not too hard to calculate the coordinates for the six vertices especially if the hexagon is centered at the origin in a coordinate system. However, it is also easy to see how we could move from vertex to vertex regardless of where we place the first vertex. Let the vector be the displacement indicated in Figure 2.2. When added to our initial point, say , this will give us the next vertex .
Figure 2.2 Regular polygon
Now, if we can rotate the vector counterclockwise by ( radians), then adding it to will give us vertex . Repeating this procedure produces all the other vertices. Notice that this approach can build the hexagon image no matter where we begin and no matter what original direction we choose. Yes, we do need to learn how to rotate a vector, but that turns out to be relatively straightforward and will be addressed in a later chapter.
2.1.1 Points Versus Vectors
To define above, we subtracted two points ( from ). With Cartesian coordinates for the points, it does make sense to subtract the coordinates component-wise to get the displacement. However, adding two points is another matter. Adding the coordinates together gives another point, but this resulting point does depend on which coordinate system we are using. For example, adding the two points and from above gives the point . Now imagine the coordinate system is shifted two units to the left to give a second Cartesian coordinate system. In this system, and , giving . This point has coordinates in the first coordinate system, so it is definitely a different point from the original . Addition depends on which coordinate system we are in, so addition of two points is not well defined if we want to stay independent of coordinate systems.
