tag:blogger.com,1999:blog-51385109331448924542023-11-15T16:39:43.425+02:00Umbrella Development LogStatus and development of Umbrella Engine and the Sad Umbrella RPG game project. Discussing 3d real time graphics, game development and other kinds of things related to making a modern close to commercial class indie game.Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-5138510933144892454.post-53881293706748940092011-01-07T19:18:00.012+02:002011-01-21T17:02:38.432+02:00A Graphics Programmer's Toolbox, part 2 (Matrices and Coordinate Systems)The second round of "what's in your mathematical toolbox".<br /><br />If you missed the previous part, consider <a href="http://sadumbrella.blogspot.com/2010/12/graphics-programmers-toolbox-part-1.html">part 1</a> first.<br /><br /><span style="font-weight:bold;">Coordinate Systems</span><br /><br />A vector <span style="font-style:italic;">(u, v, w)</span> can be expressed as <span style="font-style:italic;">u<span style="font-weight:bold;">i</span> + v<span style="font-weight:bold;">j</span> + w<span style="font-weight:bold;">k</span></span>, which is the representation of the vector in the standard coordinate system. We can define other coordinate systems with different basis vectors. For example, if we take a mirrored coordinate system in which the basis vectors are <span style="font-style:italic;">-<span style="font-weight:bold;">i</span>, -<span style="font-weight:bold;">j</span></span> and <span style="font-style:italic;">-<span style="font-weight:bold;">k</span></span>, then the point whose coordinates in that system are <span style="font-style:italic;">(-u, -v, -w)</span> matches the same point:<br /><center><pre><br />(-u)(-<b>i</b>) + (-v)(-<b>j</b>) + (-w)(-<b>k</b>) = u<b>i</b> + v<b>j</b> + w<b>k</b>.<br /></pre></center><br /><br />Co-ordinates of a point in a system are simply the multipliers of the basis vectors: if the basis vectors are <span style="font-style:italic;"><span style="font-weight:bold;">i'</span></span>, <span style="font-style:italic;"><span style="font-weight:bold;">j'</span></span> and <span style="font-style:italic;"><span style="font-weight:bold;">k'</span></span> and the coordinates are <span style="font-style:italic;">(u, v, w)</span>, then, if the the coordinate system's origin is at zero, the point matching those coordinates is <span style="font-style:italic;">u<span style="font-weight:bold;">i'</span> + v<span style="font-weight:bold;">j'</span> + w<span style="font-weight:bold;">k'</span></span>. If the coordinate system's origin is not at zero, we have to take that into account. In that case, if the origin is at <span style="font-style:italic;"><span style="font-weight:bold;">p</span></span>, the point becomes <span style="font-style:italic;">u<span style="font-weight:bold;">i'</span> + v<span style="font-weight:bold;">j'</span> + w<span style="font-weight:bold;">k'</span> + <span style="font-weight:bold;">p</span></span>.<br /><br /><br />Now if the vectors <span style="font-style:italic;"><span style="font-weight:bold;">p</span>, <span style="font-weight:bold;">i'</span>, <span style="font-weight:bold;">j'</span></span> and <span style="font-style:italic;"><span style="font-weight:bold;">k'</span></span> are known in the standard basis, we can calculate the coordinates of the point in the standard coordinate system:<br /><center><pre><br />(u <b>i'</b>.x + v <b>j'</b>.x + w <b>k'</b>.x + <b>p</b>.x, <br /> u <b>i'</b>.y + v <b>j'</b>.y + w <b>k'</b>.y + <b>p</b>.y, <br /> u <b>i'</b>.z + v <b>j'</b>.z + w <b>k'</b>.z + <b>p</b>.z),<br /></pre></center><br />or simply<br /><center><pre>u <b>i'</b> + v <b>j'</b> + w <b>k'</b> + <b>p</b>.</pre></center><br /><br />Often the basis vectors <span style="font-weight:bold;"><span style="font-style:italic;">i'</span></span>, <span style="font-weight:bold;"><span style="font-style:italic;">j'</span></span> and <span style="font-weight:bold;"><span style="font-style:italic;">k'</span></span> are of unit-length and orthogonal to each other. The mathematical notation for this is <span style="font-style:italic;">|<span style="font-weight:bold;">i'</span>| = 1, |<span style="font-weight:bold;">j'</span>| = 1, |<span style="font-weight:bold;">k'</span>| = 1</span> and <span style="font-style:italic;"><span style="font-weight:bold;">i'</span>·<span style="font-weight:bold;">j'</span> = 0, <span style="font-weight:bold;">j'</span>·<span style="font-weight:bold;">k'</span> = 0</span> and <span style="font-style:italic;"><span style="font-weight:bold;">k'</span>·<span style="font-weight:bold;">i'</span> = 0</span>, where · is the dot product. If all these hold, the coordinate system is called orthonormal. If the basis vectors are only orthogonal but not necessarily normalized, then the coordinate system is called just orthogonal.<br /><br /><br /><span style="font-weight:bold;">Matrices</span><br /><br />A matrix is simply an array of numbers. Another fancy term here. That's all.<br /><br /><br /><span style="font-weight:bold;">Matrix notation</span><br /><br />There are different sizes of <s>arrays</s> matrices of course, although the <i>3x3</i> and <i>4x4</i> <s>arrays</s> matrices are the most useful in 3d graphics. Like in many programming languages, the first number is the <s>height</s> number of <s>horizontal lines</s> rows, and the last number is the <s>width</s> number of <s>vertical lines</s> columns. An example for a <i>3x4</i> <s>array</s> matrix in <i>C</i> would be <i>float matrix[3][4]</i>.<br /><br />Like vectors, <s>arrays</s> matrices can be summed. It's just the componentwise sum. The difference of matrices is the same componentwise difference as for vectors. Like vectors, you can multply and divide them by <s>numbers</s> scalars. There's also the Hadamard product (componentwise product), but that's not so common. Like for vectors, the most useful <s>array</s> matrix multiplications are something different. I'll come back to that later.<br /><br />Elements of <s>an array</s> a matrix are usually denoted by subscript notation; first the row and then the column:<br /><center><pre><br /> [<b>A</b><sub>1,1</sub> <b>A</b><sub>1,2</sub> <b>A</b><sub>1,3</sub> <b>A</b><sub>1,4</sub>]<br /> <b>A</b> = [<b>A</b><sub>2,1</sub> <b>A</b><sub>2,2</sub> <b>A</b><sub>2,3</sub> <b>A</b><sub>2,4</sub>]<br /> [<b>A</b><sub>3,1</sub> <b>A</b><sub>3,2</sub> <b>A</b><sub>3,3</sub> <b>A</b><sub>3,4</sub>]<br /></pre></center><br />For example, if<br /><center><pre><br /> [11 12] <br /> <b>A</b> = [21 22] <br /> [31 32],<br /></pre></center><br />then <b>A</b><sub>1,2</sub> = 12, <b>A</b><sub>2,1</sub> = 21 and <b>A</b><sub>3,2</sub> = 32.<br /><br /><br /><span style="font-weight:bold;">Matrices and Coordinate Systems</span><br /><br />Let's go back to the coordinate systems and take one whose origin is at zero and whose basis vectors are <b>i'</b>, <b>j'</b> and <b>k'</b>, not necessarily orthogonal nor unit-length. Let's store these vectors as a <i>3x3</i> matrix:<br /><center><pre><br /> [<b>i'</b>.x <b>j'</b>.x <b>k'</b>.x] <br /><b>M</b> = [<b>i'</b>.y <b>j'</b>.y <b>k'</b>.y].<br /> [<b>i'</b>.z <b>j'</b>.z <b>k'</b>.z] <br /></pre></center><br />This matrix is often called the base of the coordinate system since it contains the basis vectors. Next, let's make the vector <i>(u, v, w)</i> a matrix too:<br /><center><pre><br /> [u] <br />(u, v, w) = [v].<br /> [w] <br /></pre></center><br />Let's call that previous point <i>(u, v, w)</i> with the name <b>p</b> and let's suppose that these coordinates are given with respect to the previously given base. To get the coordinates of <b>p</b> in the standard coordinate system, we need to know the vectors <b>i'</b>, <b>j'</b> and <b>k'</b> in the standard coordinate system. If we do, we have<br /><center><pre><br /> (u <b>i'</b>.x + v <b>j'</b>.x + w <b>k'</b>.x, <br /><b>p</b> = u<b>i'</b> + v<b>j'</b> + w<b>k'</b> = u <b>i'</b>.y + v <b>j'</b>.y + w <b>k'</b>.y, <br /> u <b>i'</b>.z + v <b>j'</b>.z + w <b>k'</b>.z).<br /></pre></center><br />According to the previously introduced scheme, let's make this vector a matrix too:<br /><center><pre><br /> [u <b>i'</b>.x + v <b>j'</b>.x + w <b>k'</b>.x] <br /><b>p</b> = [u <b>i'</b>.y + v <b>j'</b>.y + w <b>k'</b>.y].<br /> [u <b>i'</b>.z + v <b>j'</b>.z + w <b>k'</b>.z] <br /></pre></center><br />After all, vectors are matrices too. Now let's introduce the matrix product for a <i>3x3</i> <s>array</s> matrix and a <s>3-vector</s> <i>3x1</i> matrix (which is often called a <i>column vector</i>):<br /><center><pre><br />[<b>i'</b>.x <b>j'</b>.x <b>k'</b>.x] [u] [u <b>i'</b>.x + v <b>j'</b>.x + w <b>k'</b>.x]<br />[<b>i'</b>.y <b>j'</b>.y <b>k'</b>.y] * [v] = [u <b>i'</b>.y + v <b>j'</b>.y + w <b>k'</b>.y]<br />[<b>i'</b>.z <b>j'</b>.z <b>k'</b>.z] [w] [u <b>i'</b>.z + v <b>j'</b>.z + w <b>k'</b>.z]<br /><br /> [<b>i'</b>.x] [<b>j'</b>.x] [<b>k'</b>.x] <br /> = u [<b>i'</b>.y] + v [<b>j'</b>.y] + w [<b>k'</b>.y] = u<b>i'</b> + v<b>j'</b> + w<b>k'</b>.<br /> [<b>i'</b>.z] [<b>j'</b>.z] [<b>k'</b>.z] <br /></pre></center><br />In other words, <span style="font-style:italic;">matrix * vector</span> transforms the vector from another coordinate system to the standard coordinate system.<br /><br /><br /><span style="font-weight:bold;">Matrix Times a Matrix</span><br /><br />Well then, how about <span style="font-style:italic;">matrix * matrix</span>? It's simple. Really, just multiply with the columns of the second matrix one by one and collect the results. Denoting the columns of the second matrix as <b>a1</b>, <b>a2</b> and <b>a3</b> and the first matrix as <b>M</b>, we have<br /><center><pre><br /> [<b>i'</b>.x <b>j'</b>.x <b>k'</b>.x] [<b>a1</b>.x <b>a2</b>.x <b>a3</b>.x] <br /><b>M</b> = [<b>i'</b>.y <b>j'</b>.y <b>k'</b>.y], <b>A</b> = [<b>a1</b> <b>a2</b> <b>a3</b>] = [<b>a1</b>.y <b>a2</b>.y <b>a3</b>.y].<br /> [<b>i'</b>.z <b>j'</b>.z <b>k'</b>.z] [<b>a1</b>.z <b>a2</b>.z <b>a3</b>.z] <br /></center></pre><br />Now then, the multiplication is done to the column vectors one by one and collected:<br /><center><pre><br /><b>M</b> * [<b>a1</b> <b>a2</b> <b>a3</b>] = [<b>M a1</b> <b>M a2</b> <b>M a3</b>].<br /></pre></center><br />The column vectors of the result matrix are, like we had it before, just the three vectors transformed one by one. The result is a <i>3x3</i> matrix<br /><center><pre><br />[(<b>M a1</b>).x (<b>M a2</b>).x (<b>M a3</b>).x] <br />[(<b>M a1</b>).y (<b>M a2</b>).y (<b>M a3</b>).y].<br />[(<b>M a1</b>).z (<b>M a2</b>).z (<b>M a3</b>).z] <br /></pre></center><br /><br />Now we're able to transform points to the standard coordinate system by matrix multiplication. But how about the inverse? Surprisingly, that's done by multiplying by the <i>inverse matrix</i>; more about that later.<br /><br />That's all, folks!<br /><br /><span style="font-weight:bold;">The Future ...</span><br />Please ask for details in the comments. The next topic might be <i>4x4</i> matrices, homogenous coordinates and coordinate systems whose origin is not at zero. Probably also discussing matrix transpose and inverse. Please comment and request for a topic if you want.<br /><br />You might want to read more about <a href="http://en.wikipedia.org/wiki/Matrix_multiplication">matrix multiplication</a> or <a href="http://en.wikipedia.org/wiki/Coordinate_system">coordinate systems</a>. ;)Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com0tag:blogger.com,1999:blog-5138510933144892454.post-72823567280672111222010-12-21T07:40:00.010+02:002010-12-21T12:04:55.909+02:00A Graphics Programmer's Toolbox, part 1 (Vectors)Everyone needs to know the basic tools of their art. I thought I'd like to share with you my equivalents of a screwdriver, a hammer and maybe a saw, some of the everyday tools of a graphics programmer.<br /><br /><span style="font-weight:bold;">Vectors</span><br /><br />A <span style="font-style:italic;">vector</span> is just a fancy word for a point in space. So in 2d, a vector is just a co-ordinate pair <span style="font-style:italic;">(x, y)</span>. In 3d it's <span style="font-style:italic;">(x, y, z)</span> and in 4d it's <span style="font-style:italic;">(x, y, z, w)</span>. A mental image of four dimensions is not important here - don't even try.<br /><br />Some vectors are given a special name. The vector in the middle of the space, the zero-vector, is called the <span style="font-style:italic;">origin</span>. In 3d, that's <span style="font-style:italic;">(0, 0, 0)</span>. The vector to the right, <span style="font-style:italic;">(1, 0, 0)</span>, is called <span style="font-weight:bold;">i</span>. The up-vector, <span style="font-style:italic;">(0, 1, 0)</span> is <span style="font-weight:bold;">j</span>. The remaining vector, <span style="font-style:italic;">(0, 0, 1)</span>, is named <span style="font-weight:bold;">k</span> and it's the backwards-vector.<br /><br /><span style="font-weight:bold;">Sum, Difference and Multiplication</span><br /><br />These points, or vectors, can be added and subtracted. Adding a vector to another is just summing the coordinates of the vectors; if <span style="font-style:italic;"><span style="font-weight:bold;">a</span> = (X, Y)</span> and <span style="font-style:italic;"><span style="font-weight:bold;">b</span> = (x, y)</span>, then <span style="font-style:italic;"><span style="font-weight:bold;">a</span> + <span style="font-weight:bold;">b</span> = (X+x, Y+y)</span>. Subtracting is done in a similar way, <span style="font-style:italic;"><span style="font-weight:bold;">a</span> - <span style="font-weight:bold;">b</span> = (X-x, Y-y)</span>. Multi-dimensional calculation is not really that much more complicated. It's basically just the same, but doing the operations to all co-ordinates, instead of just one.<br /><br />Sum and difference are easy, but with multiple components (co-ordinates) there are many kind of vectors multiplications with different meanings. Complicated? I didn't say anything; not yet.<br /><br /><span style="font-style:italic;">Multiplying by a scalar</span> just multiplies the distance of the point with respect to the origin. This <span style="font-style:italic;">scalar</span> is just a fancy name for a <span style="font-style:italic;">real number</span>; you might have noticed mathematicians love fancy words. So in other words, if <span style="font-style:italic;"><span style="font-weight:bold;">a</span> = (x, y, z)</span> and <span style="font-style:italic;">r</span> is a real number, then <span style="font-style:italic;"><span style="font-weight:bold;">a</span>*r = (x*r, y*r, z*r)</span>. If <span style="font-style:italic;">r</span> is negative, you can see that the point will also be mirrored with respect to the origin.<br /><br />The <span style="font-style:italic;">componentwise product</span> works the same way as sum and addition, but it's a bit rarer in the mathematical context. It's very useful in computer graphics though, mostly in lighting calculations. This product is denoted with <span style="font-style:italic;">○</span>, and if <span style="font-style:italic;"><span style="font-weight:bold;">a</span> = (R, G, B, A)</span> and <span style="font-style:italic;"><span style="font-weight:bold;">b</span> = (r, g, b, a)</span>, then <span style="font-style:italic;"><span style="font-weight:bold;">a</span> ○ <span style="font-weight:bold;">b</span> = (R*r, G*g, B*b, A*a)</span>. Mathematicians call this product the <span style="font-style:italic;">Hadamard product</span> (Jacques Hadamard, 1865 to 1963). <span style="font-style:italic;">Componentwise product</span> is fine too.<br /><br />There are also at least two more very useful products.<br /><br /><span style="font-weight:bold;">Dot and Cross Product</span><br /><br />The <span style="font-style:italic;">dot product</span> is the screwdriver of the toolbox. This product is written with the symbol •, and it's the sum of the components' products; if <span style="font-style:italic;"><span style="font-weight:bold;">a</span> = (X, Y, Z)</span> and <span style="font-style:italic;"><span style="font-weight:bold;">b</span> = (x, y, z),</span> then <span style="font-style:italic;"><span style="font-weight:bold;">a</span> • <span style="font-weight:bold;">b</span> = X*x + Y*y + Z*z</span>. Notice that the result is a <span style="font-style:italic;">scalar</span>, or a real number. The usefulness of this product comes mainly from the fact that if <span style="font-style:italic;"><span style="font-weight:bold;">a</span></span> and <span style="font-style:italic;"><span style="font-weight:bold;">b</span></span> are both unit-length (<span style="font-style:italic;">X<sup>2</sup> + Y<sup>2</sup> + Z<sup>2</sup> = 1<sup>2</sup></span>), then, denoting the angle between <span style="font-style:italic;"><span style="font-weight:bold;">b</span></span> and <span style="font-style:italic;"><span style="font-weight:bold;">a</span></span> with <span style="font-style:italic;">α</span>, it holds that <span style="font-style:italic;"><span style="font-weight:bold;">a</span> • <span style="font-weight:bold;">b</span> = cos α</span>. Generally, if <span style="font-weight:bold;"><span style="font-style:italic;">a</span></span> and <span style="font-weight:bold;"><span style="font-style:italic;">b</span></span> are not necessarily of unit length, then <span style="font-style:italic;"><span style="font-weight:bold;">a</span> • <span style="font-weight:bold;">b</span> / |<span style="font-weight:bold;">a</span>||<span style="font-weight:bold;">b</span>| = cos α</span>, where <span style="font-style:italic;">|<span style="font-weight:bold;">v</span>|</span> denotes the length of a vector.<br /><br />In 3d there's the <span style="font-style:italic;">cross product</span>. Its main purpose is outputting a vector that's orthogonal to two given vectors, i.e. getting their normal vector. It can also be used to calculate the sine of the angle between two vectors. A funny fact is that a cross product only exists in 3 and 7 dimensions. The formula for cross product is pretty symmetric; if <span style="font-style:italic;"><span style="font-weight:bold;">a</span> = (X, Y, Z)</span> and <span style="font-style:italic;"><span style="font-weight:bold;">b</span> = (x, y, z)</span>, then <span style="font-style:italic;"><span style="font-weight:bold;">a</span> × <span style="font-weight:bold;">b</span> = (Yz - Zy, Zx - Xz, Xy - Yx)</span>. Notice that this product is a bit special in that <span style="font-style:italic;"><span style="font-weight:bold;">a</span> × <span style="font-weight:bold;">b</span> = - <span style="font-weight:bold;">b</span> × <span style="font-weight:bold;">a</span></span>, so you can't just switch the order mindlessly. It is also true, like stated before, that <span style="font-style:italic;"><span style="font-weight:bold;">a</span> × <span style="font-weight:bold;">b</span></span> is orthogonal to both <span style="font-style:italic;"><span style="font-weight:bold;">a</span></span> and <span style="font-style:italic;"><span style="font-weight:bold;">b</span></span>. In mathematical notation, <span style="font-style:italic;">(<span style="font-weight:bold;">a</span> × <span style="font-weight:bold;">b</span>) • <span style="font-weight:bold;">a</span> = 0</span> and <span style="font-style:italic;">(<span style="font-weight:bold;">a</span> × <span style="font-weight:bold;">b</span>) • <span style="font-weight:bold;">b</span> = 0</span>. For the direction of the cross product vector there's the <span style="font-style:italic;">right-hand rule</span>, well described in <a href="http://en.wikipedia.org/wiki/Cross_product#Definition">this wiki article</a>.<br /><br /><span style="font-weight:bold;">Continuing soon...</span><br />It's a known fact that once you open a Wikipedia page, you just can't stop reading. I'll set here a trap for you and I bet you can't oppose it:<br /><a href="http://en.wikipedia.org/wiki/Euclidean_vector">Euclidean vector</a><br /><a href="http://en.wikipedia.org/wiki/Unit_vector">Unit vector</a><br /><a href="http://en.wikipedia.org/wiki/Gram-schmidt">The Gram-Schmidt algorithm</a><br /><br />I'm planning to continue with matrices, bases, coordinate transforms, quaternions and such. If you'd like to suggest a topic or ask a question, please comment! :)Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com3tag:blogger.com,1999:blog-5138510933144892454.post-55622961450420910702010-11-18T21:10:00.006+02:002010-11-18T22:08:16.972+02:00BeamcastingI am Topi "Sharph" Talvitie, the other coder in the Umbrella Project. I've been mostly helping with path finding related algorithms in the project.<br /><br />Efficient path finding algorithms run on a graph of links between vertices. These graphs are a bit large to be distributed as precalculated data, so they need to be generated at runtime. If possible, this process should be fast enough to be unnoticeable. Our solution to the problem is casting a beam from each vertex to find the vertices that this vertex is linked to.<br /><br />In the figure below there is a beam (the red area) cast from vertex A of polygon P. The vertices seen from vertex A are circled.<br /><br /><center><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/beamcast1.png"></center><br /><br />If we are able to query the whole visible polygon from any point, we can use the same algorithm for many interesting effects too, such as checking if the player is seen by a character in the game. Thus we need an algorithm that can cast a beam from both polygon vertices and free space.<br /><br /><center><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/beamcast3.png"></center><br /><br />So how to do this efficiently? After considering some grid accelerated algorithms that turned out to be quite complex, we realized that a triangle tessellation (triangulation) of the map would be very useful.<br /><br /><center><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/triangulaatio.png"></center><br /><br />We will shortly describe the algorithm. There's still a cake for you <a href="#action">in the <b>action phase</b></a> after that.<br /><br /><h3>Initiating the Cast</h3><br />Because the polygon map is tessellated, the starting point of the beam O (lower right) is an interior point of exactly one triangle T. We divide the beam (lower left) into at most three smaller beams (lower right: A, B and C) by splitting it by the sectors to the triangle edges.<br /><br />Each of these smaller beams sees exactly one edge of the triangle T. If that edge is a wall of a polygon, just add it. For the unblocked beams, we advance to the next neighboring triangle. (N1 for A, N3 for B, N2 for C)<br /><br /><center><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/initialcase1.png" style="display: inline;"> <img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/initialcase2.png" style="display: inline;"></center><br /><br />The case of starting from a vertex is very similar.<br /><br /><h3>Recursion</h3><br />In the recursion step we consider a smaller beam, recursed to a triangle (the lower triangle in the figures below). Due to splitting the beam when entering new triangles, the beam will enter the neighboring triangle (gray) through exactly one edge (L-R). <br /><br />We take the line to the opposite vertex of this new triangle (lower right, O-S) and use this line to deduce which neighbors of the current triangle (gray) will need to be recursed into. If both edges (L-S, S-R) are seen, both neighboring triangles will need to be analyzed (lower right).<br /><br /><center><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/recursioninside1.png"> <img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/recursioninside2.png"><br /></center><br /><br />If only the leftmost edge is seen, only the left triangle will need to be analyzed (lower left). If only the rightmost edge is seen, only the right triangle will need to be analyzed.<br /><br /><center><br /><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/recursionright.png"> <img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/recursionleft.png"><br /></center><br /><br />Again, if the triangle we are advancing into is part of an obstacle polygon, just add the edge. And finally, to keep the result polygon correctly ordered, the search should be done depth-first and always to the same direction first.<br /><br />There exist many good libraries for triangulation. We used <a href="http://code.google.com/p/poly2tri/">poly2tri</a>, licensed under the New BSD License.<br /><br /><h3>Something to think...</h3><br />It is proven that in pathfinding, links from vertex A to vertices in beam C are not needed. Can you figure out why? Might be confusing at first!<br /><br /><center><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/beamcast2.png"></center><br /><br />And at last...<br /><br /><h3 id="action">Action!</h3><br />We prepared a scene for your investigation for this very realistic simulation of a<br />crime-in-action, a western style bank robbery. The blue casting star represents the sheriff and the red casting robber represents the bad guy. Enjoy!<br /><br /><center><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/scene1.png" style="width: 300px; height: 300px;"><br /><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/scene2.png" style="width: 300px; height: 300px;"><br /><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/scene3.png" style="width: 300px; height: 300px;"><br /><img src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101118/scene4.png" style="width: 300px; height: 300px;"></center><br /><br /><small>(Written by Topi Talvitie, edited by Markus Kettunen)</small>Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com0tag:blogger.com,1999:blog-5138510933144892454.post-18611064731266292422010-10-18T16:08:00.011+03:002010-10-18T23:05:28.221+03:002010-10-18. A Game Engine from ScratchAfter modifying the collision detection algorithm to suit a vector map, and fixing some very nontrivial floating point problems I decided that it might be time to take a step towards the level editor. Back then I had no nice means for more advanced interaction with the user, so my next step was to make a widget system.<br /><br />While playing with Google's V8 engine, which I later abandoned, I had become familiar with Javascript and its event system. I found it quite nice so I decided to take its design as a base for designing my own system. It appeared to be a rather good plan.<br /><br />Here is the debugging view I used at this point.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101018_widget.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 406px;" src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20101018_widget_small.png" border="0" alt="" /></a><br /><br />On the left lower corner you can see some widgets, one of them showing the mouse position and the other being an <i>automatic FPS calculator</i>. Whoa!<br /><br />The small squares in the ground show the space division that is used to accelerate collision detection. Collision detection against the walls only needs to be done when the player is inside one of those bluish rectangles, and only the walls going through the same rectangle need to be checked against. In real use, though, the rectangles should be a lot larger.<br /><br />Another noteworthy object in the picture is that steamtank. Alas, this time without all that eye candy. When the time is right I will have finished generalizing the rendering engine for arbitrary scenes, also supporting a large variety of options to make the game playable on a bit older computers too. This is something that I'm doing with ubershaders, though more on them later.<br /><br />Currently I'm writing a more user friendly exporter for Milkshape 3d for our model and animation formats. Why not use an existing format? That's an interesting question with an even more interesting answer. I have also been rewriting the animation system to better support animation changes. But all this will be ready soon enough, and there will be so many interesting things to discuss.<br /><br />It surely isn't a small job to make a complete game engine from scratch, but it's so much fun!Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com0tag:blogger.com,1999:blog-5138510933144892454.post-48135127807183848892010-09-12T18:14:00.006+03:002010-09-13T00:08:51.703+03:002010-09-12. Path findingAfter abandoning V8 I wrote some code for collision detection. The plan was that our maps would be made of squares, and inside those squares we would have a grid for more precise collisions. I also wanted that the player would slide along the walls instead of getting stuck, so I needed to do some <a href="http://en.wikipedia.org/wiki/Ray_casting">raycasting</a>. The resulting collision map would be too large to keep in memory, so I ended up writing a system for raycasting edges that were created in real-time...<br /><br />At this point another competent coder joined the team and we were discussing path finding algorithms for the game. He made a quick A* implementation for testing, and it was soon apparent that the desired grid size was far too large.<br /><br />After thinking of this for a while we deduced that our lives would be much easier if we changed the maps into vector maps and forgot about the tiles. It also made my life easier. This one was a really good decision!<br /><br />One of the problems we had with the new polygon-based path finding algorithm was that the precalculation time required for fast path finding would be all too large. We needed to search all the visible polygon corners from all the other polygon corners in the map. Each one of these would require checking all the other polygons. This was unacceptable. Moving from a map to map had to be fast.<br /><br />Even after heavily optimizing visibility tests: raycasting with grid-based acceleration and limited polygon density, it would still be at least O(n<sup>2</sup>). For fast precalculation times we really didn't have the time to find all the visible corners. We needed a local approximation, caring only of the nearest polygons. We achieved this by limiting the visibility range and adding 'dummy points' where there were no polygon corners nearby, to connect to the far-away polygons. The resulting precalculation time was unbelievably fast and the actual path-finding part didn't suffer much.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/blog/20100912_path.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20100912_path_small.png" border="0" alt="" /></a><br /><br />Here's an image of the precalculation process. The green grid represents the grid used in the acceleration. It should be a lot sparser in a real use case. The blue polygons represent the actual walls used in the path finding, pulled out from the red original walls next to them. The resulting, somewhat optimized network of links, is drawn in red.<br /><br />This local system requires the found route to be cleaned afterwards, by dropping any possible unnecessary waypoints. But there's also a bug in the image. Can you spot it? Can you be sure? :-)Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com0tag:blogger.com,1999:blog-5138510933144892454.post-57357718962736626492010-07-26T02:20:00.005+03:002010-07-26T14:24:12.105+03:002010-07-26. Scripting with V8<span style="font-weight:bold;">Map scripting</span><br /><br />After a long break in writing here I'm back again, and the project has taken some nice steps forward. We have been researching useful scripting languages for map scripting. This process isn't what I'm most interested in, nor does it produce cool images, so I haven't been too motivated to write about it before. I will now, shortly.<br /><br />To implement complex behaviour in maps we need to use some scripting language. Common scripting languages include Javascript, Lua and Python, among others. These all have been good candidates for us.<br /><br />At first I took a look at embedding Python into a C++ program. Python's micromanagement of resources, like manually incrementing and decrementing reference counters, looked shuddering. It's also a rather slow language, typical efficiency (compared to C) being around 1/200th.<br /><br />I had also heard horror stories about people needing ridiculous optimizations in their Lua scripts to get even decent speed. On the other hand, Google's Chrome is one of the fastest web browsers out there when it comes to Javascript. And Google's Javascript engine, V8, is out there for free. And it natively supports C++ too. Javascript by itself isn't a dirty language either. Sounds like a dream, no?<br /><br />I took some time to experiment with it. I wrote wrappers to understand it better, experimented with it, made test APIs and tools and other small libraries for it. It worked somewhat, but I ended up rewriting stuff too many times, trying to find a clean general solution for my needs.<br /><br />There wasn't too much documentation for the new V8 library yet so I ended up having lots of trouble and frustration with it. I had gotten it to work, even in a way that would be useful for a small project, but I couldn't get it clean enough to use in a large game, without the frustration of having to cope with dirty code. <br /><br />On top of that, when trying to compile Sad Umbrella for Arch Linux, it then appeared that the V8 release didn't even compile; it had constructs in the source code that weren't supported by the newest GCC version. Maybe they have fixed it by now, maybe not, but that wasn't the only Linux distribution having problems with V8. Many other people reported difficulties getting V8 from their Linux distribution's repositories, and it would be almost impossible to get V8 for a handheld device. If we ever decided to port the game for one.<br /><br />I feel the library is still too immature for actual use by 3rd parties.Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com0tag:blogger.com,1999:blog-5138510933144892454.post-86680608806277955802010-05-19T22:22:00.007+03:002010-05-19T22:55:00.552+03:002010-05-19. Music for the Umbrella Project<span style="font-weight:bold;">Coining the term 'idea music'</span><br /><br />I am <span style="font-weight:bold;">Pauli "Gwaur" Marttinen</span>. I am the appointed composer for the Umbrella Project, though one other composer has also been invited to fill some of the stylistic gaps that I don't span. I specialize in music in the symphonic or otherwise classical sense. I am far for being a pro, but I'm aiming for professional studies in percussion and/or conducting.<br /><br /><object width="640" height="505"><param name="movie" value="http://www.youtube.com/v/QHCV6gshYGM&hl=en_GB&fs=1&"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/QHCV6gshYGM&hl=en_GB&fs=1&" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="640" height="505"></embed></object><br /><br />At this point of the Umbrella Project, virtually no game exists. There's an incomplete graphics engine, the game and scripting engines are just being conceived, and the plot setting is only starting to get out of the "vague idea" state. This is the opposite of an ideal phase for making the score: I have no idea what I am making music for.<br /><br />I have practically no mental image of where the project is headed to. There's too little concept art, 3D models, scripts or storyboards to follow. It is hard to get any inspiration that's directly linked to this game. If I make a piece of music for the game at this point, who knows if it will it be used in a cutscene or a playable place, or in the closing credits? Should I make it repeatable? Should I make other versions of it, for different situations?<br /><br />It is of course never a bad idea to store ideas beforehand. Even if a piece I go ahead and finish now will ultimately be unused, ideas can be recycled. Maybe a new piece with a new structure but some same themes. Or the same structure and new themes in the same style. On the other hand, changing things may be difficult if, for instance, some pieces have music played with real instruments instead of computerized ones.<br /><br />Something like this has been done at Studio Ghibli, a film studio that produces some of the most popular animated features. If you look for soundtracks of Ghibli's films, you might come across some albums subtitled "Image Album". These are albums of music inspired by storyboards and concept art, composed by the composer in the earliest phases of filmmaking, as opposed to music often being one of the last things to be made. With this, the composer has more time to fine-tune the music, discard some and make some new, according to the project leader's wish.<br /><br />In our case, we are currently trying out something I might call "idea music" instead of image music, since we have no images yet. What happens right now is that the project coordinator asks me to make "something based on this idea". I try to follow that idea, make something, and suggest whatever I come up with. By now we have three pieces of music, but none of us knows exactly where and how to use them.<br /><br />Things are starting out slow, and there are several reasons for it. None of us are professionals, and we have little experience on working on such an ambitious project. We live quite far away from each other, so we are relayed through the Internet and seldom meet in real life, but the Internet doesn't always do it for you. Also, frankly, my personal video game interests don't match with this one. ;)Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com0tag:blogger.com,1999:blog-5138510933144892454.post-46677466917193170982010-04-17T22:48:00.011+03:002010-05-24T00:31:49.591+03:002010-04-18. Emission maps<span style="font-weight:bold;">Terrain generation from a height map</span><br /><br />I spent some time pondering how to implement terrain to the engine. The choices were either heightmap-based or tile-based terrain. Tiles fit the engine better but our modeler already has enough work... We'd need a second modeler I guess.<br /><br />The initial plan was to support multiple levels of detail (LOD) and draw areas farther away with less triangles. But I also wanted the terrain to have adaptive precision. Combining these two proved to be quite tricky.<br /><br />Here are some results of the tessellation algorithm I wrote. The sand castle is only a test to see how the algorithm does. No castles like this in the real game, done with a heightmap at least.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_wireframe.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_wireframe_small.jpg" border="0" alt="" /></a><br /><br />The results are quite nice. This is the same with real shading:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_shaded.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_shaded_small.jpg" border="0" alt="" /></a><br /><br />Sadly, with adaptive terrain it's not easy to make the level of detail changes seamless. There would be unacceptable artifacts, pixels of the sky seen through artifacts in the height map. No wai.<br /><br /><br /><span style="font-weight:bold;">Edges again!</span><br /><br />Someone complained about the jaggy edges in the pictures. HDR rendering requires rendering to texture but rendering to texture with high precision doesn't support <a href="http://en.wikipedia.org/wiki/Multisample_anti-aliasing">Multisample Anti-Aliasing (MSAA)</a>. This means there's not much I can do without a huge cost, like using <a href="http://en.wikipedia.org/wiki/Anti-aliasing#Full-scene_anti-aliasing">Fullscreen Anti-Aliasing</a>.<br /><br />There is still hope, though. An OpenGL extension named GL_EXT_framebuffer_multisample could possibly save the situation. I must take another look at it later.<br /><br />Inspired by the complainment aboud jaggy edges I decided to try enabling the edges again. Jagginess still persists but it might be a bit better.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_edges.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_edges_small.jpg" border="0" alt="" /></a><br /><br /><br /><span style="font-weight:bold;">Light bleeding</span><br /><br />If you take a close look in the fullscreen version of the picture above you can see that the shadows aren't as soft as they used to be. This is because I encountered horrible light bleeding with the <a href="http://www.punkuser.net/vsm/">variance shadows</a>. You can see some of it in the image below. Please don't mind the burnt terrain, it was a bug in the terrain normals.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_lightbleed.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_lightbleed_small.jpg" border="0" alt="" /></a><br /><br />Now this doesn't look much like a shadow, does it? This is why I replaced the shadows with a quick implementation of <a href="http://http.developer.nvidia.com/GPUGems/gpugems_ch11.html">Percentage-Closer Shadows (PCF)</a>.<br /><br /><br /><span style="font-weight:bold;">Emission textures</span><br /><br />I watched some demos from <a href="http://breakpoint.untergrund.net/">Breakpoint 2010</a>. <a href="http://pouet.net/prod.php?which=54588">One of them</a> had very impressive lighting effects. I wondered if I could produce similar effects too.<br /><br />This effect is done by giving a material a high emission factor so that it is self-lit. Now that its color is very bright the bloom filter of HDR rendering gives it a nice halo, making it look very bright.<br /><br />Our modeler, Juutis, had been asking for specular maps for some time. I hadn't implemented them yet since there were no free channels in our textures. But now I needed another channel for emission so it was clear that I needed to replace the traditional material-wide properties with an emission-specular-diffusion map.<br /><br />Here are a few samples with some temporary hearts and a lit warning label. ;)<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_emission1.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_emission1_small.jpg" border="0" alt="" /></a><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_emission2.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_emission2_small.jpg" border="0" alt="" /></a><br /><br /><br /><span style="font-weight:bold;">Cel-shading?</span><br /><br />I took some time to play around with cel-shading. I'm not sure how well it fits a HDR rendering system, but at least I figured that cel-shading systems need a huge amount of parameter tweaking to get them to work in different lighting options.<br /><br />I don't find these results very pleasing but I thought it would still be fun sharing them. But this is not the direction we'll be taking in the near future.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_celshading1.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_celshading1_small.jpg" border="0" alt="" /></a><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_celshading2.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/blog/20080417_celshading2_small.jpg" border="0" alt="" /></a>Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com0tag:blogger.com,1999:blog-5138510933144892454.post-49981765595157612172010-04-05T20:47:00.009+03:002010-05-24T00:21:30.848+03:002010-04-05. Death to the bottlenecks<span style="font-weight:bold;">Larger VBOs for speed, yes?</span><br /><br />While playing with the engine I noticed the steamtank looked possibly better without the dark edges so I took them off. I may put them back later though. We'll probably play around here quite a bit.<br /><br />So here I was at 20 fps with a cool Steamtank. I decided to add another tank and boom, frame rate was down at 10 fps. Huh? For other computers this didn't affect the frame rate at all. Yummy.<br /><br />At the moment I was using <a href="http://en.wikipedia.org/wiki/Vertex_Buffer_Object">Vertex Buffer Objects</a> of size of one mesh each, where by mesh I mean a part of model that consists of a single material. I have read that the VBO size should be kept between around half and two megabytes. Mine were closer to few dozen kilos, so maybe this was a source of slowness? I went and combined the VBOs.<br /><br />Here's a screenshot I took while the process wasn't quite ready yet.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/bug5.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/bug5s.jpg" border="0" alt="" /></a><br /><br />Got it ready and, oh the speed increase. Frame rate had dropped from 10 to 5 per second. Software fallback? Too large VBOs? Pfft.<br /><br /><br /><span style="font-weight:bold;">No software fallback for me, please</span><br /><br />The size of my vertex information was 76 bytes per vertex. It had vertex position, vertex normal, vertex tangent, four joint IDs and four joint weights for skeletal animation. It's said that this number should be a multiple of 32 bytes for best performance. Our model was using at most two vertex weights so we thought three vertex weights should be enough, saving 8 bytes. As the sum of the vertex weights has to be one, I could calculate the third one from the remaining two in the vertex shader. I had reached the goal of 64 bytes.<br /><br />No significant performance increase.<br /><br />Then something caught my eye. Everything else in the vertex information was floating point numbers but the joint numbers were integers... Like they naturally should be. I vaguely remembered that for optimal performance only floats should be used here, but at the time I read this I didn't pay too much attention to it. I tried changing them to floats and <span style="font-style:italic;">boom</span>, the program was running at 45 frames per second. Huh!<br /><br />Apparently the graphics hardware didn't support integer parameters in the vertex structure so it resorted to software fallback instead... Vertex shaders in software, no thanks.<br /><br />Here's a video capture of the engine running at 40 fps on HD 4650 Mobility with resolution 1280x720.<br /><br /><object width="640" height="385"><param name="movie" value="http://www.youtube.com/v/HoLjTWhd8BI&hl=en_US&fs=1&hd=1"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/HoLjTWhd8BI&hl=en_US&fs=1&hd=1" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="640" height="385"></embed></object><br /><br />Oh and by the way, toggling larger VBOs increases the frame rate by around one frame per second.Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com0tag:blogger.com,1999:blog-5138510933144892454.post-77215094955738412642010-04-03T23:56:00.008+03:002010-05-24T00:21:23.952+03:002010-04-02. Alpha maps<span style="font-weight:bold;">A real model</span><br /><br />I wrote some code for the adaptive terrain tessellation thing I told you about but I didn't test it yet so it's most probably broken. But enough of that. The topic for today is that Juutis, our 3d modeller, made us our first real model. Want to see it? Guessed so.<br /><br />She's going to shoot fire and push some steam up once we're ready. And keep some good noise and be reeeeal cool! But for now, she's just our new test model. Wave farewell to Ultimato as that wormie has done her job.<br /><br />So ladies and gentlemen! Please welcome... Steamtank!<br /><br /><br /><object width="640" height="385"><param name="movie" value="http://www.youtube.com/v/rrrgevMdMOo&hl=en_US&fs=1&hd=1"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/rrrgevMdMOo&hl=en_US&fs=1&hd=1" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="640" height="385"></embed></object><br /><br /><br /><span style="font-weight:bold;">Alpha maps</span><br /><br />This version of the engine has only some minor additions. I spent much of the day debugging why some parts of the tank didn't show up. Finally I found that some vertices had vertex weights plain zero... Blame <a href="http://chumbalum.swissquake.ch/">Milkshape</a>! Seems it sometimes "forgot" to return vertex weight 1.0 when a vertex was bound to only one joint. So a few lines to our MS3D exporter and the bug was dealt with.<br /><br />The other addition to the engine was alpha maps. They're as simple as it gets: if a pixel has alpha value below 0.5, discard it. You can see the effect in some of the wheels of the steamtank. They are just rotating rectangles with a bump map and an alpha map. But they look so real. Pretty cheap.<br /><br />...<br /><br />Though to be honest, this is not cheap at all. My frame rate dropped from 35 back to 20 due to this new model. I'm not sure where the bottleneck is but I really need to do something. Texture fetches? But I like the environment map... :(<br /><br /><br />Edit: Some more images with another environment map (original by Hipshot)<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/umbrella0028.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/umbrella0028s.jpg" border="0" alt="" /></a><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://xob.kapsi.fi/~makegho/trash/umb/umbrella0028b.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 640px; height: 374px;" src="http://xob.kapsi.fi/~makegho/trash/umb/umbrella0028bs.jpg" border="0" alt="" /></a>Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com0tag:blogger.com,1999:blog-5138510933144892454.post-68474006600126758702010-04-02T08:20:00.002+03:002010-05-24T00:21:15.533+03:002010-04-01. Deferred shading<span style="font-weight:bold;">HDR shading improved</span><br /><br />I spent a few days improving the conversion curve from HDR to LDR [see previous post]. I divided the screen into 5x5 sub-screens and rendered the same view with five different curve types and parameters. Then I dropped the worst looking curves, saved the best ones and "zoomed in" to fine-tune the parameters.<br /><br />The HDR->LDR conversion system also includes a dynamically changing shutter time of the camera. It's not very visible in this homogenous lighting but it makes the scene look very beautiful in darkness too. Think of entering a dark tunnel... Yum!<br /><br />Here's a shot with an abstract skeletal animated worm.<br /><br /><object width="640" height="385"><param name="movie" value="http://www.youtube.com/v/cyOoujXISMM&hl=en_US&fs=1&hd=1"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/cyOoujXISMM&hl=en_US&fs=1&hd=1" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="640" height="385"></embed></object><br /><br /><span style="font-weight:bold;">Deferred shading</span><br /><br />When I uploaded the last video the frame rate was around 20 fps at resolution 1280x800 on my ATI Mobility HD 4650, which is around half speed of GeForce 8800 GT. Even though it's clear there was a bottleneck, most of the time was spent in constant time postprocessing effects. This is good because it means adding triangles won't make it slower. <br /><br />I was able to remove many rendering steps by entering the world of <a href="http://en.wikipedia.org/wiki/Deferred_shading">deferred shading</a>. This means I no longer render the objects straight, calculating the lighting as I go. Instead I save vertex normals, texture colors and material parameters of each pixel into textures, and then in another pass I calculate the lighting for each pixel based on these. This way I only need to calculate lighting for those pixels that are actually shown.<br /><br />On top of this I took the edge detect shader (sobel) and combined it with the blur shader; they both need to be applied to make good edges. For those interested in details, I just combined the sobel kernel and the blur 1-2-1 kernel, resulting in a single rendering pass. I went even further and combined this blurred sobel shader with the HDR->LDR conversion shader into a single rendering pass. In the end I had FPS 35, which is a HUGE improvement. Yippee!<br /><br />...<br /><br />Next up is showing some terrain with adaptive tessellation. Without the fancy words it means the triangle mesh will be more accurate where needed, just like it should. And the terrain will be rendered in less accuracy when it's far away. Wish me luck.Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com1tag:blogger.com,1999:blog-5138510933144892454.post-66734791468373658782010-04-02T06:29:00.003+03:002010-05-24T00:21:05.100+03:002010-03-28. HDR Rendering<span style="font-weight:bold;">Sobel filters</span><br /><br />Last night before I went to bed I read about the so called <a href="http://en.wikipedia.org/wiki/Sobel_operator">sobel operator</a> that is often used to find edges in images in programs like Photoshop. The filter basically gives every pixel a number that is large for large differences<br />in adjacent pixels. This was a very easy algorithm to implement.<br /><br />Running the filter against image data would be a bad idea though. To find the edges I had extracted the shape of the surface (normals and depth values) from the partially rendered image. When I run the sobel filter against this data I get large values wherever there is a jump in the shape. Exactly what I want!<br /><br />But this gives equally sized edges everywhere and to be honest it looks quite bad. Fortunately the values of the sobel filter often go much above 1 which is the maximum I can use. I figured if I blur these values I get wider edges where the shape had larger jumps.<br /><br /><object width="640" height="385"><param name="movie" value="http://www.youtube.com/v/-X-iM-Z5i7A&hl=en_US&fs=1&hd=1"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/-X-iM-Z5i7A&hl=en_US&fs=1&hd=1" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="640" height="385"></embed></object><br /><br /><span style="font-weight:bold;">HDR rendering</span><br /><br />Today I read some papers about <a href="http://en.wikipedia.org/wiki/High_dynamic_range_imaging">High Dynamic Range imaging</a>. Be sure to see <a href="http://images.google.com/images?q=hdr">some images Google gives when asked for "HDR"</a>, they're very cool. The idea is that normally every pixel rendered has to have color values between 0 and 1 and this leaves the image very flat. The sun can be dozens of times brighter than a room so they simply don't fit in the same range.<br /><br />To fix this the scene is first rendered without this cramping restriction. Only after everything has been drawn completely to a texture, with color values more like between 0 and 100, the image is downscaled back to between 0 and 1 by some curve. This gives a very satisfying result, though finding a curve good enough takes time.<br /><br />...<br /><br />Oh and by the way, the fps I get on this laptop keeps going down. A few days ago I was still 60. Then I added soft shadows, rendering normals and depths to textures and all kinds of post processing effects like HDR rendering.<br /><br />Everyone of those rendering phases basically takes 2 to 5 fps down. Now I'm at 20. I hope I won't need any more ;)Markus Kettunenhttp://www.blogger.com/profile/06638623514665436879noreply@blogger.com0