http://www.developer.com/

## Getting Started with the Vector Dot Product: Math for Java Game ProgrammersOctober 7, 2008 Java Programming Notes # 1714 - Preface
- General background information
- Preview
- Discussion and sample code
- The game-math library named GM02
- The program named DotProd2D01
- The program named DotProd2D02
- The program named DotProd3D01
- The program named DotProd3D02
- Interpreting the vector dot product?
- More than three dimensions
- Run the programs
- Summary
- What's next?
- Resources
- Complete program listings
- Copyright
- About the author
## Preface## General
This tutorial is the next lesson in a series designed to teach you some of the mathematical skills that you will need In addition to helping you with your math skills, I will also help you learn how to incorporate those skills into object-oriented programming using Java. If you are familiar with other object-oriented programming languages such as C#, you should have no difficulty porting this material from Java to those other programming languages.
Since most computer games make heavy use of either 2D or 3D graphics, you will need skills in the mathematical areas that are required for success in 2D and 3D graphics programming. As a minimum, this includes but is not limited to skills in: *Geometry**Trigonometry***Vectors****Matrices****2D and 3D transforms****Transformations between coordinate systems****Projections**
Of course, game programming requires mathematical skills beyond those required for graphics. However, for starters, this series will concentrate on the last five items in the above list.
In the previous lesson, you learned how to write your first interactive 3D game using the game-math library. You also learned how to write a Java program that simulates flocking behavior such as that exhibited by birds and fish and how to incorporate that behavior into a game. Finally, you examined three other programs that illustrate various aspects of both 2D and 3D animation using the game-math library.
This lesson is the first part of a two-part mini-series on the vector dot product. By the time you finish both parts, you will learn the fundamentals of the vector dot product in both 2D and 3D, you will learn how to update the game-math library to support various aspects of the vector dot product, and you will learn how to write 2D and 3D programs that use the vector dot product for various applications such as the back-face culling procedure that was used to convert the left image in Figure 1 to the right image in Figure 1.
## Viewing tipI recommend that you open another copy of this document in a separate browser window and use the following links to easily find and view the figures and listings while you are reading about them. ## Figures- Figure 1. Using the vector dot product for back-face culling.
- Figure 2. Two vectors with their tails at the origin, program DotProd2D02.
- Figure 3. Dot product of two vectors with the same orientation in 2D.
- Figure 4. Dot product of two vectors with the same orientation in 3D.
- Figure 5. Dot product of a 3D vector with an identical vector.
- Figure 6. Dot product of vectors with opposite orientations.
- Figure 7. The dot product of perpendicular vectors in 2D.
- Figure 8. A general formulation of 2D vector perpendicularity.
- Figure 9. Another interesting 2D case of perpendicular vectors.
- Figure 10. A general formulation of 3D vector perpendicularity.
- Figure 11. A pair of perpendicular 3D vectors.
- Figure 12. Another pair of perpendicular 3D vectors.
- Figure 13. GUI for the program named DotProd2D01.
- Figure 14. A screen shot of the output from the program named DotProd3D01.
- Figure 15. Six
*(magenta)*vectors that are perpendicular to a given*(black)*vector.
## Listings- Listing 1. Source code for the method named GM02.ColMatrix3D.dot.
- Listing 2. Source code for the method named GM02.Vector3D.dot.
- Listing 3. Source code for the method named GM02.Vector3D.angle.
- Listing 4. The actionPerformed method in the program named DotProd2D01.
- Listing 5. Format the dot product value for display in the GUI.
- Listing 6. Beginning of the actionPerformed method in the program named DotProd2D02.
- Listing 7. Compute the dot product and the angle between the two vectors.
- Listing 8. Source code for the game-math library named GM02.
- Listing 9. Source code for the program named DotProd2D01.
- Listing 10. Source code for the program named DotProd2D02.
- Listing 11. Source code for the program named DotProd3D01.
- Listing 12. Source code for the program named DotProd3D02.
## Supplementary materialI recommend that you also study the other lessons in my extensive collection of online Java tutorials. You will find a consolidated index at www.DickBaldwin.com. ## General background informationIn this series, I will frequently refer you to an excellent interactive tutorial on In the process, I will develop and explain a game-math library that you can use to experiment with and to confirm what you learn from the Kjell tutorial. The library will start out small and grow as we progress through more and more material in subsequent lessons. For this lesson, I recommend that you concurrently study the Kjell tutorial through ## PreviewI won't repeat everything that Dr. Kjell has to say. However, there are a few points that I will summarize in this section.
The vector dot product is a special way to multiply two vectors to produce a real result. Fundamentally, the vector dot product of two vectors is the product of the lengths of the vectors multiplied by the cosine of the angle between them. By the angle between them, I mean the angle that would be formed if you were to draw the two vectors with their tails in the same location. For example, Figure 2 shows a black vector and a magenta vector drawn with their tails at the origin. Eyeballing the picture suggests that the angle between the two vectors is forty or fifty degrees.
Fortunately, we can do more than eyeball the angle between two vectors. Figure 2 shows the screen output produced by the program named In Figure 2, the top four user input fields allow the user to enter the x and y coordinate values of two vectors according to the labels that identify those fields. When the user clicks the OK button, the first vector is drawn in black with its tail at the origin and the second vector is drawn in magenta with its tail at the origin. The dot product of the two vectors is computed and displayed in the bottom left text field, and the angle between the two vectors is computed and displayed in the bottom right text field.
Upon seeing the definition of the dot product given above, you may reasonably be concerned about needing to know the angle between the vectors before you can compute the dot product. Fortunately, as you will see later, it is possible to compute the dot product of two vectors without knowing the angle. In fact, being able to compute the dot product is one way to determine the angle between two vectors. As you can see, the value of the dot product of the two vectors shown in Figure 2 is 6000 and the angle between the vectors is 49.3987 degrees. You will learn how those values were computed shortly.
Here are some of the major properties of the dot product of two vectors: - The dot product of two vectors with the same orientation is the product of their lengths.
- The length of a vector is the square root of the dot product of the vector with itself.
- The dot product of two vectors having opposite orientations is the negative of the product of their lengths.
- The dot product of perpendicular vectors is zero.
- The angle between two vectors is the same as the angle between normalized versions of the vectors, which is equal to the arc cosine of the dot product of the normalized vectors.
As you will see later, these properties apply to both 2D and 3D vectors. In many cases, they also apply to vectors having more than three dimensions as well.
Figure 3 illustrates the first property in the above list:
You may recall from some earlier experience that when a right triangle has sides with lengths of 30 and 40, the length of the hypotenuse is 50. That is the case for the magenta vector shown in Figure 3. Similarly, when the sides of the triangle are 60 and 80, the length of the hypotenuse is 100, as is the case for the black vector in Figure 3. From the property given above, we know that the dot product of the black and magenta vectors shown in Figure 3 is 5000, which agrees with the value shown in the
Figure 4 shows the dot product of two vectors with the same orientation in 3D. The image in Figure 4 was produced by the program named
You may need to get your calculator out to compute the lengths of the two vectors in Figure 4. Computing the lengths as the square root of the sum of the squares of the three components of each vector gives me the following lengths: - Black length = 141.42
- Magenta length = 70.71
Rounding the product of the two lengths gives the dot product value of 10000, which matches the value shown in the bottom left output field in Figure 4.
Figure 5 illustrates the second property in the above list:
Figure 5 displays two vectors having the same coordinate values as the black vector in Figure 4. We concluded earlier that the length of each of these vectors is 141.42. This length is the square root of the dot product of the vector with itself. Squaring and rounding this length gives a dot product value of 20000, which matches the value shown in the bottom left output field in Figure 5.
Figure 6 illustrates the third property of the dot product given above:
The two vectors shown in Figure 6 have the same absolute coordinates as the two vectors shown in Figure 4. However, the algebraic signs of the coordinates of the magenta vector in Figure 6 were reversed relative to Figure 4, causing the magenta vector to point in the opposite direction from the black vector. The point here is that the dot product of the two vectors in Figure 6 is the negative of the dot product of the two vectors in Figure 4. This property will be used in another program in the second part of this two-part miniseries to achieve the back-face culling shown in Figure 1.
If you have studied the Kjell tutorial through Chapter 10
Similarly, in the 3D case, the dot product is given by:
Note that these two formulations don't require the program to know anything about the angle between the two vectors, as is the case in the earlier definition.
The dot product has many uses in game programming, not the least of which is determining if two vectors are perpendicular. Figure 7 illustrates the fourth property in the above list:
By eyeballing Figure 7, you can see that the magenta vector is probably perpendicular to the black vector. Looking at the output fields at the bottom left and the bottom right in Figure 7, you will see that the dot product of the two vectors is zero and the angle between the two vectors is 90 degrees.
Most of us learned in our plane geometry classes that the angle between perpendicular lines is 90 degrees. Therefore, the angle between perpendicular vectors must be 90 degrees. Most of us also learned in our trigonometry classes that the cosine of 90 degrees is 0.0. Since, by definition, the value of the dot product of two vectors is the product of the lengths of the vectors multiplied by the cosine of the angle between them, and the angle must be 90 degrees for two vectors to be perpendicular, then the dot product of perpendicular vectors must be zero as stated by the fourth property in the above list of properties.
By observing Figure 7, it shouldn't be too much of a stretch for you to recognize that there are an infinite number of different vectors that could replace the magenta vector in Figure 7 and be perpendicular to the black vector. However, since we are discussing the 2D case here, all of those vectors must lie in the same plane and must have the same orientation
By performing some algebraic manipulations on the earlier 2D formulation of the dot product, we can formulate the equations shown in Figure 8 that define the infinite set of perpendicular vectors described above.
As you can see from Figure 8, we can assume any values for y1, y2, and x1 and compute a value for x2 that will cause the two vectors to be perpendicular.
One very interesting 2D case is the case shown in Figure 7. In this case, I initially specified one of the vectors to be given by the coordinate values (50,100).; Then I assumed that y2 is equal to x1 and computed the value for x2. The result is that the required value of x2 is the negative of the value of y1. Thus, in the 2D case, we can easily define two vectors that are perpendicular by swapping the coordinate values between two vectors and negating one of the coordinate values in the second vector. The actual direction that the second vector points will depend on which value you negate in the second vector.
Another interesting 2D case is shown in Figure 9.
In Figure 9, I assumed the same coordinate values for the black vector as in Figure 7. Then I assumed that the values of the y-coordinates for both vectors are the same. Using those values along with the equation in Figure 8, I manually computed a required value of -200 for the x-coordinate of the magenta vector. I entered that value into the field labeled
You can see that the value of the dot product of the two vectors in Figure 9 is 0.0, and the angle between the two vectors is 90 degrees. Therefore, although the magenta vector in Figure 9 is much longer than the magenta vector in Figure 7, the magenta vector in Figure 9 is still perpendicular to the black vector. Thus, Figure 7 and Figure 9 show two of the infinite number of magenta vectors that are perpendicular to the black vector in those figures.
As I mentioned earlier, the topic of perpendicularity in 3D is more complicated than is the case in 2D. As is the case in 2D, there are an infinite number of vectors that are perpendicular to a given vector in 3D. In 2D, the infinite set of perpendicular vectors must have different lengths taken in pairs, and the vectors in each pair must point in opposite directions.
However, in 3D there are an infinite number of vectors having the same length that are perpendicular to a given vector. All of the perpendicular vectors having the same length must point in different directions and they must all lie in a plane that is perpendicular to the given vector. Perpendicular vectors having different lengths may point in the same or in different directions but they also must lay in a plane that is perpendicular to the given vector.
Kjell explains the situation of an infinite set of 3D vectors that are perpendicular to a given vector by describing an old-fashioned wagon wheel with spokes that emanate directly from the hub and extend to the rim of the wheel. The hub surrounds the axle and each of the spokes is perpendicular to the axle.
In this case, the wagon wheel lays in a plane that is perpendicular to the axle. There is normally another wheel at the other end of the axle. Assuming that the axle is straight, the second wheel is in a different plane but that plane is also perpendicular to the axle. Thus, the spokes in the second wheel are also perpendicular to the axle. If there were two identical wheels at each end of the axle for a total of four wheels
By performing some algebraic manipulations on the earlier 3D formulation of the dot product, we can develop the equations shown in Figure 10 that describe an infinite set of vectors that are perpendicular to a given vector.
Unlike with 2D vectors, While this is a fairly tedious computation with a hand calculator, it is very easy to write Java code to perform the computation. Therefore, given a 3D vector, it is fairly easy to write Java code that will compute an infinite number of vectors that are perpendicular to the given vector.
Figure 11 and Figure 12 each show a magenta 3D vector that is part of the infinite set of vectors that are all perpendicular to the black 3D vector. In Figure 11, y1 was assumed to be equal to y2, and z1 was assumed to be equal to z2. For an x1 value of 25, a value of -125 was required to cause the magenta vector to be perpendicular to the black vector.
In Figure 12, x1 was assumed to be equal to x2, and z1 was assumed to be equal to z2.
For a y1 value of 50, a y2 value of - 25 was required to cause the magenta vector to be perpendicular to the black vector.
Note that the black vector is the same in Figure 11 and Figure 12. However, the magenta vectors are different in Figure 11 and Figure 12. They represent just two of the infinite set of vectors that are perpendicular to the black vector.
The fifth property in the previous list reads: In other words, given two vectors, we can compute the angle between the two vectors by first normalizing each vector and then computing the dot product of the two normalized vectors.
This is the procedure that is used by the programs in this lesson to compute and display the angle between two vectors as illustrated by the contents of the output field labeled I will have more to say about this topic as I explain the code in the upgraded game-math library named - DotProd2D01
- DotProd2D02
- DotProd3D01
- DotProd3D02
## Discussion and sample code
## The game-math library named GM02In this section, I will present and explain an updated version of the game-math library named This game-math library is an update to the game-math library named The following methods are new instance methods of the indicated static top-level classes belonging to the class named **GM02.ColMatrix2D.dot**- computes dot product of two ColMatrix2D objects.**GM02.Vector2D.dot**- computes dot product of two Vector2D objects.**GM02.Vector2D.angle**- computes angle between two Vector2D objects.**GM02.ColMatrix3D.dot**- computes dot product of two ColMatrix3D objects**GM02.Vector3D.dot**- computes dot product of two Vector3D objects.**GM02.Vector3D.angle**- computes angle between two Vector3D objects.
I have explained much of the code in the game-math library in previous lessons, and I won't repeat those explanations here. Rather, I will explain only the new 3D code in this lesson. Once you understand the new 3D code, you should have no difficulty understanding the new 2D code. You can view a complete listing of the updated game-math library in Listing 8 near the end of the lesson.
Listing 1 shows the source code for the new instance method named
This is one of those cases where it is very easy to write the code once you understand the code that you need to write. Listing 3 implements the equation for the 3D dot product that I provided earlier and returns the result of the computation as type
Listing 2 shows the source code for the method named
Once again, the code is straightforward. All
Listing 3 shows the source code for the method named
If you understand trigonometry, you will find the code in Listing 3 straightforward. If not, simply take my word for it that the method shown in Listing 3 behaves as described above. The method begins by calling the Then Listing 3 computes the dot product of the two normalized vectors. The value of the dot product is the cosine of the angle between the two original vectors. After that, Listing 3 calls the Finally, Listing 3 calls the That completes the discussion of the updates to the game-math library resulting in the new library named ## The program named DotProd2D01To understand this program, you need to understand the material in the Kjell tutorial through The purpose of this program is simply to confirm proper operation of the
The program creates a GUI that allows the user to enter the first and second values for each of a pair of
Much of the code in this program is similar to code that I have explained in earlier lessons, so I won't repeat those explanations here. I will explain only the code contained in the
The beginning of the
Listing 4 begins by instantiating a pair of Then Listing 4 calls the
In some cases, the format of the returned value is not very suitable for display in the lower-left field in Figure 13. For example, if the value is very small, it is returned in an exponential notation requiring a large number of digits for display. Similarly, sometimes the dot-product value is returned in a format something like 0.33333333 requiring a large number of digits to display. Listing 5 formats the dot product value to make it suitable for display in the text field in Figure 13.
Listing 5 begins by simply setting small values that are less than 0.001 to 0.0 to eliminate the exponential format for very small, non-zero values. Then Listing 5 executes some code that formats the dot product value to four decimal digits. I will leave it as an exercise for the student to decipher how this code does what it does.
I recommend that you plug a few values into the input fields, click the That concludes the discussion of the program named ## The program named DotProd2D02To understand this program, you need to understand the material in the Kjell tutorial through This program allows the user to experiment with the dot product and the angle between a pair of A screen shot of the output from this program is shown in Figure 2. The GUI shown in Figure 2 is provided to allow the user to enter four double values that define each of two In addition, the GUI provides a 2D drawing area. When the user clicks the Once again, much of the code in this program is similar to code that I have explained before. I will explain only the method named
This method is called to respond to a click on the
Listing 6 gets the four user input values that define the two vectors and draws them in black and magenta on the GUI shown in Figure 2. There is nothing new in the code in Listing 6.
Listing 7 computes the dot product and the angle between the two vectors by first calling the
In both cases, the code in Listing 7 formats the returned
Because this is a 2D display, it is easy to make an eyeball comparison between the drawing of the two vectors and the reported angle between the two vectors to confirm agreement. However, I recommend that you use this program to define several vectors and then use your scientific calculator to confirm that the results shown are correct. That concludes the explanation of the program named ## The program named DotProd3D01To understand this program, you need to understand the material in the Kjell tutorial through The purpose of this program is to confirm proper operation of the
A screen shot of the output from the program named
Except for the fact that this program calls the That concludes the explanation of the program named ## The program named DotProd3D02You need to understand the material in the Kjell tutorial through
A screen shot of the output of this program is shown in Figure 11. This program allows the user to experiment with the dot product and the angle between a pair of In addition, the GUI provides a 3D drawing area. When the user clicks the
A complete listing of this program is provided in Listing 12. Almost all of the new and interesting code in this program is in the method named
If you compare the method named That concludes the explanation of the program named ## Interpreting the vector dot product?In effect, the dot product of two vectors provides a measure of the extent to which the two vectors have the same orientation. If the two vectors are parallel, the dot product of the two vectors has it maximum value of 1.0 multiplied by the product of the lengths of the two vectors. Normalizing the vectors before computing the dot product will eliminate the effect of the vector lengths and will cause the results to be somewhat easier to interpret. If the normalized vectors are parallel and point in the same direction, the dot product of the normalized vectors will be 1.0. If the normalized vectors are parallel and point in opposite directions, the value of the dot product will be -1.0. If the vectors are perpendicular, the dot product of the two vectors will be 0.0 regardless of whether or not they are normalized. For all orientations, the value of the dot product of normalized vectors will vary between -1.0 and +1.0. ## More than three dimensionsYou may have it in your mind that the use of mathematical concepts such as the vector dot product is limited to the three dimensions of width, height, and depth. If so, that is a false impression. The vector dot product is very useful for systems with more than three dimensions. In fact, engineers and scientists deal with systems every day that have more than three dimensions. While it usually isn't too difficult to handle the math involved in such systems, we have a very hard time drawing pictures of systems with more than three or four dimensions.
I have spent much of my career in digital signal processing where I have routinely dealt with systems having thirty or forty dimensions. For example, in the lesson titled One way to think of digital convolution is that it is a running dot product computation between one vector Often, the input data will consist of samples taken from a channel consisting of signal plus noise. The objective is often to design a vector ## Run the programsI encourage you to copy the code from Listing 8 through Listing 12, compile the code, and execute the programs in conjunction with the game-math library named ## SummaryIn this lesson, you learned the fundamentals of the vector dot product in both 2D and 3D. You learned how to update the game-math library to support various aspects of the vector dot product, and you learned how to write 2D and 3D programs that use the vector dot product methods in the game-math library. ## What's next?In the second part of this two-part miniseries, you will learn how to use the dot product to compute nine different angles of interest that a vector makes with various elements in 3D space. You will learn how to use the dot product to find six of the infinite set of vectors that are perpendicular to a given vector as shown in Figure 15.
You will also learn how to use the dot product to perform back-face culling as shown in Figure 1. ## Resources- Index to Baldwin tutorials
- 1700 Math for Java Game Programmers, Getting Started
- 1702 Math for Java Game Programmers, Updating the Math Library for Graphics
- 1704 Math for Java Game Programmers, Working with Column Matrices, Points, and Vectors
- 1706 Math for Java Game Programmers, Vector Addition
- 1708 Math for Java Game Programmers, Putting the Game-Math Library to Work
- 1710 Math for Java Game Programmers, Venturing into a 3D World
- 1712 Math for Java Game Programmers, Our First 3D Game Program
- Vector Math for 3D Computer Graphics, An Interactive Tutorial by Dr. Bradley P. Kjell
- Perpendicularity, a definition
- Arc
*(inverse)*cosine, a description - Convolution and Frequency Filtering in Java
## Complete program listingsComplete listings of the programs discussed in this lesson are shown in Listing 8 through Listing 12 below.
## CopyrightCopyright 2008, Richard G. Baldwin. Reproduction in whole or in part in any form or medium without express written permission from Richard Baldwin is prohibited. ## About the author
Richard has participated in numerous consulting projects and he frequently provides onsite training at the high-tech companies located in and around Austin, Texas. He is the author of Baldwin's Programming Tutorials, which have gained a worldwide following among experienced and aspiring programmers. He has also published articles in JavaPro magazine. In addition to his programming expertise, Richard has many years of practical experience in Digital Signal Processing (DSP). His first job after he earned his Bachelor's degree was doing DSP in the Seismic Research Department of Texas Instruments. (TI is still a world leader in DSP.) In the following years, he applied his programming and DSP expertise to other interesting areas including sonar and underwater acoustics. Richard holds an MSEE degree from Southern Methodist University and has many years of experience in the application of computer technology to real-world problems. |