Tuesday 29 December 2009

Group theory

This is one of the cases where I've simply got bored of solving a problem the conventional way and decided it could be a much better use of my time writing a program rather than pressing multiply on my calculator repeatedly.

Here's a simple python program to find the order of an element of a group modulo some number (the binary operation being multiplication):

#!/usr/bin/env python
import sys

def element_order_mul(n,g):
    r=g
    o=1
    while r%n != 1:
        print "not",r
        r=r*g
        o=o+1
    return o

# calculates the element order under multiplication mod n.
# takes: n, element
n=int(sys.argv[1])
g=int(sys.argv[2])
o=element_order_mul(n,g)
print g,"^",o,"is congruent to 1 mod",n
To find the order of g=4 in the group G={1,2,4,5,7,8} with the binary operation being multiplication modulo 9:
[simon@simon ~]$ ./order.py 9 4
not 4
not 16
4 ^ 3 is congruent to 1 mod 9
Excellent!

Saturday 9 May 2009

Trig identities

I always have trouble remembering these, here's a simple derivation using Euler's formula:


Note that the imaginary and real parts are separate so the line , which is real, corresponds to on the top line.

Friday 17 April 2009

Terrain 2

The algorithm I will implement is based on a restrictive quad tree approach. All this means is that for each node in the tree, each of its directly adjacent neighbours will need to be only one LOD level different. The reason for this is that the index buffers can be computed in advance and simply re-used for the 16 (2^4) different cases. Each of north, east, south and west can either be the same level or one less (if a neighbour is of a higher level then we would be a lower level to it and hence we would join two seams of the same detail - see figure 1).


Figure 1. Paint rocks

In regard to calculating the vertices, I'm thinking it might be a good idea to separate the load across cores (everyone uses multicore now right?). The general idea is to:-

  1. Traverse the tree splitting nodes as usual.
    1. Create child nodes, update neighbour pointers, etc. This may be recursive to keep the quadtree restricted to one LOD difference (note: pain, if not impossible, to parallelise).
    2. Add a pointer to each node that needs its vertices calculated to a list and defer actual calculation until after the tree has been processed.
  2. Simply dispatch calculation jobs to threads, these jobs are independent and nicely parallelisable.
  3. Vertex buffers also need to be created to please direct3d, shouldn't be too hard to squeeze them in somewhere.

Geomorphing is causing me to think, I can't find much on the internet to base my implementation from. I have never done anything to do with vertex interpolation before so this could be a horrible way of doing it. I'm thinking of sending the vertex shader: x, y, z, base_y where base_y is the value of y at the previous LOD level. This can be simply calculated by either taking the value as-is (for when the point coincides with the same point in the last LOD) or interpolating between two values from the last LOD (i.e. where there was an edge on a triangle). It's then just a case of interpolating between base_y and y for each vertex using a per frame shader constant.

Results soon.

Thursday 16 April 2009

Terrain

In March last year I made a terrain renderer that used noise functions to generate a reasonable looking mountain range. Since then I've learned a lot and I would like to re-visit it but this time take into account:

  • Normal maps
  • Texturing
  • Interpolation between LOD levels
  • Decent lighting
  • Post processing (HDR?)
  • Lots of small optimisations
I would also like to give test driven design (TDD) a chance, and this seems like the perfect place to use it. I had a look at Boost.Test, being boost I trust it to be high quality. It also seems reasonably easy to use.

Here is the old terrain renderer on youtube:

Saturday 21 February 2009

Quaternions

Quaternions, discovered in 1843 by Hamilton, are the extension of complex numbers to four dimensions. As it turns out, they are very useful in computer graphics and can represent any rotation in 3D space in a compact and computationally cheap form. Another advantage of quaternions is that they avoid gimbal lock as they can describe a rotation in one operation as opposed to Euler angles that combine yaw, pitch and roll in separate operations.

A quaternion can be written as \hat{\mathbf{q}}=iq_x+jq_y+kq_z+q_w=\mathbf{q}_v+q_w where i,j,k are all different square roots of -1 such that, \begin{align*}ij & = k, & \qquad ji & = -k, \\jk & = i, & kj & = -i, \\ki & = j, & ik & = -j.\end{align*} The vector \hat{\mathbf{q}}_v is closely related to the axis of rotation and the angle of rotation affects all parts of the quaternion as we shall see below.

A unit quaternion, \hat{\mathbf{q}}, can represent a rotation of 2\phi radians around an axis, \mathbf{u}, by \hat{\mathbf{q}}=(\sin \phi \mathbf{u}, \cos \phi). To rotate a point or vector, \mathbf{p}, by this quaternion is, \hat{\mathbf{q}}\mathbf{p}\hat{\mathbf{q}}^{-1}. It can be shown that the inverse, \hat{\mathbf{q}}^{-1}, for a unit quaternion, \hat{\mathbf{q}}, is actually the conjugate where this is defined as, \hat{\mathbf{q}}^{*} = (-\mathbf{q}_v, q_w).

The product of two quaternions is determined by the product of the basis elements and the distributive law, \begin{align*}\hat{\mathbf{q}}\hat{\mathbf{r}} & = (iq_x+jq_y+kq_z+q_w)(ir_x+jr_y+kr_z+r_w)\\& = i(q_y r_z-q_z r_y+r_w q_x+q_w r_x)\\& \quad + j(q_z r_x-q_x r_z+r_w q_y+q_w r_y)\\& \quad + k(q_x r_y-q_y r_x+r_w q_z+q_w r_z)\\& \quad + q_w r_w-q_x r_x-q_y r_y-q_z r_z\\& = (\mathbf{q}_v \times \mathbf{r}_v + r_w \mathbf{q}_v + q_w \mathbf{r}_v,q_w r_w - \mathbf{q}_v \cdot \mathbf{r}_v).\end{align*} The transformation expressed by a unit quaternion can also, and more usefully in computer graphics, be represented by the matrix, M =\begin{pmatrix} 1-2(q_y^2+q_z^2) & 2(q_xq_y-q_wq_z) & 2(q_xq_z+q_wq_y) & 0 \\ 2(q_xq_y+q_wq_z) & 1-2(q_x^2+q_z^2) & 2(q_yq_z-q_wq_x) & 0 \\ 2(q_xq_z-q_wq_y) & 2(q_yq_z+q_wq_x) & 1-2(q_x^2+q_y^2) & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}

Monday 9 February 2009

Text rendering

I was looking for a good library for text rendering. Something that would support truetype faces, antialiasing and kerning and be relatively easy to use. I noticed freetype in the credits to Braid (which I really need to play when the PC version appears - the demo is awesome). So after a bit of research, I found it had everything I was looking for and decided to implement it in my renderer.

Most of the time I spent in implementing this was actually writing the parts of the renderer I needed. I used the approach of using freetype to render a string to a texture and then rendering a quad with this texture. However, I feel uneasy about this as it makes the assumption that the strings I'm rendering don't change much (how fast is freetype at rendering?) and that it will probably take up more texture memory than storing individual glyphs as textures. This is something I'd like to investigate more but at the moment don't have the time. Anyway here's something to look at:

Friday 6 February 2009

Logging

It's often useful to use logging messages or error messages in case something abnormal happens. Or just for fun. A useful trick is to send them straight to the visual studio output window. Using a small amount of code we can even override std::cout and std::cerr which is pretty cool. I'm just going to dive straight into some code:

class logbuf : public std::streambuf
{
public:
    virtual std::streamsize xsputn( const char *s, std::streamsize n )
    {
        // Output to visual studio output window
        OutputDebugStringW(widen(s).c_str());
        return n;
    }
    virtual int overflow(int c = EOF)
    {
        if(c != EOF) OutputDebugString(widen(std::string(1, c)).c_str());
        return 1;
    }
private:
    int indent_;
    char last_;
};
int main(int argc, const char* argv[])
{
    // Create the new stream to redirect cout and cerr output to vs.
    logbuf merr;
    std::ostream out(&merr);

    // Smart class that will swap streambufs and replace them
    // when object goes out of scope.
    class StreamBuf_Swapper
    {
    public:
        StreamBuf_Swapper( std::ostream& orig, std::ostream& replacement )
            : buf_(orig.rdbuf()), str_(orig)
        { orig.rdbuf( replacement.rdbuf() ); }
        ~StreamBuf_Swapper() { str_.rdbuf( buf_ ); }
    private:
        std::streambuf* buf_;
        std::ostream& str_;
    } cerrswap(std::cerr, out), coutswap(std::cout, out);

    try
    {
        // ... Lots of code
    }
    catch( const std::exception& e )
    {
        std::cerr << e.what();
    }

    return 0;
}

This code takes the streambuf associated with cout and cerr and simply swaps it with a streambuf derived class (vsstream) that prints anything to the visual studio output window. Simple and useful. One other thing to note is that if the output window contains a line formatted:

<filename>(<line number>) : <message>

then it will automatically display that file and line in the editor when double clicked. A few more things you could do with it would be to log errors to a file as well or maybe have something differentiate between normal log messages and error messages (in fact, I'll probably have to do this at some point).

Tuesday 20 January 2009

Maths

Looking around the Internet, I was a little disappointed to find that blogger doesn't natively support Latex. Fortunately there's a nifty program that you can run on a web server that will output latex code as a png.

Let H \leq G and x, y \in G. Then either xH \cap yH = \emptyset or xH = yH.

The two dimentional gradient vector for a function u(x, y) is, \nabla u=\left(\frac{\partial u}{\partial x},\frac{\partial u}{\partial y}\right).

All made possible thanks to http://www.forkosh.com/mathtex.html - cheers!

Monday 19 January 2009

Plans

This journal (I hate the word blog) is going to be a place for me to organise my thoughts. I intend to list projects I'd like to do and follow them through development with regular posts showing the problems I encounter. I hope maybe it can be of use to others as well, but that is not my primary motive. Anyway, if you're actually reading this I must have done something right.

The list of projects I'd like to complete:

  • Collada loader
  • Decent text rendering
  • Screen space ambient occlusion (SSAO)
  • A simple memory allocation tracker
  • Light perspective shadow maps
  • Self-shadowed normal mapping
  • Rain on glass shader
  • Efficient perlin noise generated terrain with dynamic LOD
  • Sky dome with vertex shader to interpolate given colours
    • Real time modification of shader inputs

Also my loan came through last night so I went on a shopping spree. I ended up buying:

I'll try and do a brief review of them when I'm done reading.