[소프트웨어 3D 엔진] Software Rendering School: Part I

Software Rendering School: Part I
Mihail Ivanchev and Hans Th?rnquist 19/10/2003

Legality Info The tutorials in this series as well as the source that comes with them are intellectual property of Mihail Ivanchev and Hans T?rnqvist. You may not claim that they are your property, nor copy, redistribute, sell, or anything of the nature, the tutorials without permission from the authors. All other articles, documents, materials, etc. are property of their respective owners. Please read the legality info shipping with them before attempting to do anything with them! Introduction to the Series Hello computer fans and welcome to our software rendering school, which is a series of tutorials that will show you the interesting world of software rendering. The tutorials are written by me, Mihail Ivanchev, and my pal, Hans T?rnqvist, and we hope that you’ll enjoy them as much as we’ve enjoyed writing them. What exactly is the goal of these tutorials? The goal is to teach you the basics of 3D graphics. The further you read, the more advanced the techniques will become. Each tutorial comes will full source code and executables for at least two platforms (Windows and Linux). Feedback is welcome so that we can correct any bugs, problems, etc. and of course, so that we can make better tutorials. Why learn software rendering when hardware accelerators are loved and used by all? First, in order to work with advanced APIs, like OpenGL and Direct3D that work with the hardware, and to achieve as much as possible from them, one must know how they work and what in fact they do. Second, we are entering an age when people demand great visual quality and flexibility, which sometimes is impossible to do in hardware. Dual CPUs are starting to get cheaper and more popular which will aid us a lot. The good thing with dual CPU-systems is that while the first processor is handling general game code (managing resources, calculating AI, generating sounds, etc.), the other can render the visuals, almost exactly like a GFX accelerator. The obvious difference is that we can control a CPU much more freely than a GPU (try write a game on a GPU without the help of OpenGL or Direct3D ;)). Of course not many people have dual CPU-systems but not many people had GFX accelerators 5 years ago either. What will the tutorials include? Well, basically everything you need to know to start programming 3D applications; mathematics (oh boy!), polygon rasterization, depth buffering, hidden surface removal, texture mapping, mip-mapping, multi-texturing, blending and so on. Sounds tasty and crunchy, right? The tutorials include a large number of diagrams and schemes to make things easier to grasp. We will also recommend articles and other tutorials so you can study things we did not fully cover, or to check that we’re no big fat liars! Now it’s time to move on. The first tutorial will introduce the basic mathematics of the 3D. Basic Mathematics In this tutorial we go through a short explanation of 3D and some of the math that we will need in the future tutorial. We do NOT explain all of it since that would take way too much time and space. Some information we've left out in this tutorial may show up later on. If you’re interested in knowing more, than visit some of the links that are given at the end of the tutorial. Well let’s get on with it! The Real Basics Let’s start with what 3D really is. This is a subject often overlooked in other tutorials; they never explain what 3D actually is. It's not as hard as some of you might think. I hope you are familiar with 2D graphics programming and the all-favorite coordinate systems that are used there. We always have two axes, let’s call them X and Y, perpendicular to each other. Now if you want to put a point on the screen using this kind of coordinate system, you must choose a coordinate on the X axis and a coordinate on the Y axis for the point. Let’s look at a small example for all this: The graph above shows where the point with coordinates (x;y) is on-screen using that coordinate system. But when we move into 3D, we add a new dimension, which means another axis for the coordinate system. How do we handle this? The screen is always flat and we use a 2D coordinate system to draw on it. Well, this is the main issue of 3D graphics; to project 3D coordinates to a 2D coordinate system so that they can be drawn to the flat screen. So how do we convert the coordinates from 3D to 2D? We will come to this later, we mentioned the 3D problem for the people with some doubt in their minds. First, you have to learn how to represent coordinates in 3D. Let’s see how a point in 3D coordinate system will look like: This time, you see that the point is given with 3 coordinates for 3 axes (x; y; z). Nothing strange about 3D, that’s all the super-basics there is to it actually. Objects and Operations in 3D Space Let’s begin with how to represent objects. Everything in 3D is built up by points called "vertices". A triangle has three vertices, for instance. A vertex is a point plus possible various specific parameters. Note that there is a significant difference between vertices and points; points are simply (x; y; z) while vertices may have more data bound to them. But the most prominent difference is that points are random positions in space, vertices are positions bound to primitives (like triangles or entire objects). You may call us picky with details like this, but if there is a difference between two things, saying they are equal is totally wrong. In the beginning, we do not need any additional data for vertices than the point. Here is some sample source for how a vertex can be defined: typedef struct { float x, // Position on the X axis y, // Position on the Y axis z; // Position on the Z axis } vertex; Remember about vertices that they are actually nothing more than simple points for now. The operations that you can perform with points are not very complex but they are the basis for all 3D representation. They are translation, scaling and rotation. To help out, translation is just a fancy word for moving. Let’s see some sample code: new.x = point.x + translate.x; new.y = point.y + translate.y; new.z = point.z + translate.z; As you can see from this code, translation is really nothing much than a simple movement. The main reason we believe is that you most often use this operation for translating objects between coordinate systems. This will become apparent later on. Imagine you move the point in the picture above along the axes. We sure hope you understand what this is good for. The next operation is scaling: new.x = point.x * scale.x; new.y = point.y * scale.y; new.z = point.z * scale.z; From this code we see that scaling is also some kind of movement but we multiply the coordinates by the scale values. The point is scaled relatively to the origin. If we scale by factors of 2, the new point will be as double as far away from the origin as the original one. The third and most complex operation is the rotation. Here is some sample source: // X-Rotation new.x = v.x new.y = v.y * cos(a) ? v.z * sin(a) new.z = v.y * sin(a) + v.z * cos(a) // Y-Rotation new.x = v.x * cos(a) ? v.z * sin(a) new.y = v.y new.z = v.x * sin(a) + v.z * cos(a) // Z-Rotation new.x = v.x * cos(a) ? v.y * sin(a) new.y = v.x * sin(a) + v.y * cos(a) new.z = v.z There are deep explanations to why this works but we will not get into them. Just remember that this is the most common way to rotate something. There are tons of other ways but they are a lot more advanced and hard to use and work only in specific cases. Now it’s time for something more complex (ok a lot more complex). It’s time to take a look at vectors. First question of course is what vectors are. This is quite a complex question, because vectors can be described in so many ways. The most important are position, direction and magnitude, but we will not use them for positions. One way of expressing directions is to use angles. This however is very impractical in 3D, since angles induce trigonometry which is slow. We will try to keep away from trigonometry as much as possible. Fortunately, we can express directions with a "position". Observe that vectors are not physical nor objects, they are merely imaginative helps. For example, we have a latitude and longitude grid over the Earth, but we do not see it. It's the same with vectors, we do not see them but they help tremendously. Another important feature is that they are “nowhere”. Let's take the Earth as an example again; we do not know where in Universe our planet is. There is no definite reference origin except the Earth itself. The same with vectors, there is no real reference origin for them since they describe ONLY direction and possibly speed, so we need a new origin for every vector. This origin will be the numerical origin, (0, 0, 0). To define a vector we need at least two points. We have our first (the origin) so we need a second. This is how we will be defining vectors in the most cases. Only with one point since we assume the second one to be the origin. This will make the work a lot easier as you will later see. Now let’s see a simple example of a vector: As you can see the vector on the graph above is defined with exactly two points, the origin and the point V. We understand that this is all confusing, but it’s in fact very simple. Say we want to show a direction to the right: (x; 0; 0) where "x" is a positive value. If we want a vector that points straight down: (0; -x; 0) where again x is a positive value. To help even more, let's look at a car in motion relative to the ground. The position of the car is actually a position vector, describing the location of the car relative to everything else. The direction, however, is a directional vector only showing where the car is heading. The directional vector is nowhere in space, but shows numerically related to (0, 0, 0) what the direction is. The best way to learn vectors is to see them in action and how they work, so let's get into that. We will now delve into some basic mathematics with vectors, which we need in order to explain the more complex ones. Addition of two vectors, the simplest operation, produces new vector: new.x = v1.x + v2.x; new.y = v1.y + v2.y; new.z = v1.z + v2.z; As you can see from the sample code above you only have to add the coordinates for the corresponding axes. The subtraction of two vectors looks just like the addition: new.x = v1.x ? v2.x; new.y = v1.y ? v2.y; new.z = v1.z ? v2.z; Not hard, huh? Ok let’s move to multiplication: // 1. Two vectors new.x = v1.x * v2.x; new.y = v1.y * v2.y; new.z = v1.z * v2.z; // 2. One vector and a scalar new.x = v.x * scalar; new.y = v.y * scalar; new.z = v.z * scalar; As you can see there are two types of multiplication. You can multiply a vector with another one or vector with a scalar. The division of two vectors (or vector with scalar) looks exactly the same except for the division operator so we won’t waste space here. Now that we can do some basic operations with vectors let’s examine the elements a vector has. First as you already know the vector represents a direction. We can find a direction like this: v = p2 ? p1 where p1 and p2 are two points that we would like to know the direction between. For example, we could find the direction of a car by taking two points along its route. The vector v will point from in a direction from p1 to p2. Now we give the formula for the length of the vector, which is also called the magnitude of the vector. The length of the vector is the distance between the numerical origin and the direction point of the vector. Here is the formula: len = sqrt(v.x * v.x + v.y * v.y + v.z * v.z); This is simply Pythagora's theorem extended into 3D. Note that this can actually be used to find the distance between two points. Now we will get into the more complex vector operators. First of is an operation that is clearly useable, the dot product (or "inner" product): dot = v1.x * v2.x + v1.y * v2.y + v1.z * v2.z; where v1 and v2 are two vectors. As you can see the dot product is not a vector but a scalar. But what's the meaning of this value? The dot product is in fact the cosine of the angle between the two vectors: dot = cos(angle) This has no practical use, but can help you understand how the dot product works. The next operation is the cross product which is given with this formula: new.x = v1.y * v2.z ? v2.y * v1.z new.y = v2.x * v1.z ? v1.x * v2.z new.z = v1.x * v2.y ? v2.x * v1.y The cross product of two vectors is another vector, which is perpendicular to both source vectors. This means, the cross product will only work in R3 and above, which means in spaces with more than three real dimensions. We can't have a perpendicular vector to two vectors in 2D, can we :) Weehee, this is getting hefty... Now after all the real basics, we need some way to make everything we have gone through simple and fast. There is a way, with the help of "matrices". We won’t give a deep explanation of the matrices so if you are interested look at one of the links posted at the end of the article. A matrix is simply an object with a given number of rows and columns where each cell holds a value. Let’s look at a simple example matrix: [ 1 0 ] [ 0 1 ] The matrix shown above has 2 rows and 2 columns. As you can see they are truly filled only with numbers. We say that the matrix above is a 2x2 matrix. Note that the number of rows and columns in a matrix could be different. For instance, we may have: [ 0 0 ] [ 1 0 ] [ 0 1 ] Which is 3x2 matrix. In 3D applications, we normally use 4x4 matrices (3x3 can occur as well). What can we do with these matrices and why are they so useful? As with vectors, we'll first look at the addition of two matrices. It’s very easy actually and it’s done like this: [ a b ] + [ e f ] = [ a + e , b + f ] [ c d ] [ g h ] [ c + g , d + h ] You just have to add the corresponding elements from the operand matrices and place them at the corresponding positions in the resultant matrix. One important thing to notice is that the resultant matrix has the same dimensions (rows and columns) as the two operand matrices. Time for subtraction which is the same as the addition but with a minus sign (you didn’t expected that, huh?): [ a b ] - [ e f ] = [ a ? e , b ? f ] [ c d ] [ g h ] [ c ? g , d ? h ] And at last let’s look at the multiplication which is a little bit harder. I will assume that you will require only NxN matrices (square matrices) and so the all you need to remember is: [ a b ] * [ e f ] = [ a * e + b * g , a * f + b * h ] [ c d ] [ g h ] [ c * e + d * g , c * f + d * h ] Generally, it's "the sum of matrix A's rows and matrix B's columns at the same index, where each cell is multiplied". The easiest way to show this is with some simple code: for (j = 0; j < size; j++) { for (i = 0; i < size; i++) { value = 0; for (k = 0; k < size; k++) value += A[j][k] * B[k][i]; result[j][i] = value; } } NOTE! (A * B) is NOT equal to (B * A). Just put that somewhere in your head and don't let it loose. Forgetting this can cause some serious bugs. But what were these matrices all about? How do they relate to vertices? Funny you asked, we were just about getting there ;) To incorporate matrices to vertices, do this: R.x = v.x*m[0][0] + v.y*m[0][1] + v.z*m[0][2] + m[0][3]; R.y = v.x*m[1][0] + v.y*m[1][1] + v.z*m[1][2] + m[1][3]; R.z = v.x*m[2][0] + v.y*m[2][1] + v.z*m[2][2] + m[2][3]; This is actually a pure matrix multiplication. What we do, is we multiply a column matrix by a square matrix. If you want to look deeper into matrix multiplication, we suggest you take a look at the explanations offered by (1). In fact, they got notes for pretty much everything in this tutorial. As you can see the result from the operation is a vector and not a matrix. Further Reading www.mathworld.com ? Here you can learn just everything there is to be learned about mathematics, physics and chemistry. There are deep explanations why stuff work with a lot of diagrams and etc. stuff that will help you to understand the fun and exciting world of mathematics.

원본 사이트 : http://www.devmaster.net/articles/software-rendering/part1.php