March 2008 Archives

Project Overview: perfectstorm

| | Comments (29)

with-health-bars.png

perfectstorm is a real time strategy game study written in common lisp using OpenGL for graphics display and cairo for texture generation. It is in active development with many of the basic features still unimplemented, but i decided the effort put into it justifies some public documentation.

Terrain Generation 90ies-style

| | Comments (1)

If you have played with Bryce or Terragen you know that Terrain Generation is fun and useless. The Midpoint Displacement Algorithm is one of the simplest methods to build a triangle mesh that resembles the terrain found in nature. You can see its output on the right. displacement.jpg

While this looks like a mountain of some sorts, the algorithm does not produce good mountains every time you invoke it. Instead, the result is quite random and almost always bad. Have a look at the algorithm:

  1. Make one triangle.
  2. Subdivide all your triangles into four new ones (use the edge midpoints as new vertices).
  3. Move your new midpoints along the y-axis by a random offset.
  4. Repeat 2 and 3 with half the offset.

The algorithm refines its terrain model recursively with every step, producing self-similar (in other words fractal) patches of terrain. It is short and easy to understand. Too bad real mountains are only superficially self-similar. One of the most visible shortcomings of the algorithm can be seen when the random displacement is replaced by its expected value. The “expected value” for the algorithm looks like this:

displacement-norandom.jpg

These furrows can be seen in most randomly displaced terrains, too, when viewed from specific angles or directly from above. (The yellow cube is the light source)

A better approach might be to use Perlin noise as a heightmap since it does not introduce visible artifacts. I’ll probably test this later.

Concerning the implementation, i spent most of the time implementing the fundamental mesh operations like splitting lines and triangles. Since this will not be last time i’ll handle triangle meshes and i might save other Lispers the pain i am thinking about expanding this and publishing it as a general mesh handling and drawing library for Common Lisp.

a quick guide to shaders

| | Comments (1)

A shader is a small program that is executed on the graphics card. On modern graphics cards, up to 128 shader programs can be executed in parallel. Conventional parallel programming is hard because there are resources to be shared, but shader programs are completely independent, allowing the graphics card manufacturers to add more shader pipelines at will. Currently there are two important types of shaders: vertex shaders and fragment shaders. For each frame that is rendered, all visible vertices (read: nodes of the mesh) are processed by vertex shaders which can modify their position or attributes like normals, color or any other user-defined attributes.

fraktale_teekanne.png One fragment corresponds to one pixel on the screen. For each fragment, the fragment shader is called. A fragment belongs to the polygon visible at the position of the corresponding pixel on the screen, i.e. the intersection of the pixel ray with the polygon defines the fragment’s position in the 3d world. The fragment shader thus knows its position within the polygon and can use this information, e.g. for looking up (and returning) the color of the polygon’s texture at that place. When using fragment shaders, OpenGL will not do texture mapping, you will have to use a trivial fragment shader to accomplish what would happen automatically without shaders.

Information can pass from the vertex shader to the fragment shader, but not in the other direction. The shader programmer may define arbitrary “varying” constants which can be written by the vertex shader and are, linearly interpolated between the vertices, available to the fragment shader. For each triangle three vertex shader executions need to be made, but a much larger amount of fragment shader executions is needed, depending on the size of the triangle on the screen.

Naturally, the fragment shader has access to all of the triangle’s textures. For advanced shaders, like those in modern games, these auxiliary textures usually contain a normal map and/or a height map, i.e. the direction of the normal for each texel (the three coordinates of the normal are stored as rgb) or the height of the texel compared to the triangle plane (as a grey value) is available. With this information a fragment shader can do arbitrarily complex stuff, ranging from good old bump mapping to a wide variety of occlusion and parallax mapping techniques, the use of gloss maps or the design of weird materials, their colors changing with the angle the camera looks at them.

Since it is also possible to pass values (e.g. a tick count or wind speed) from OpenGL to the shaders, they are used to implement flags fluttering in the wind, rocket engines causing ripples in the air or other animations or effects you would have thought the CPU knew about.

In my experiments i used GLSL (the OpenGL Shader Language), a c-like mid-level language that is compiled into assembly code that can be executed on the graphics hardware. GLSL provides clipping, matrix multiplication, dot product, etc. as primitive operations, along with some useful predefined special variables that are always present and need not be declared.

In the quest for more and more parallelization in computing, shaders may be the most successful example since shader parallelization itself demands no intervention by the programmer at all. Shaders are bound to become even more complex: with geometry shaders (available on graphics cards labeled “Shader Level 4” or “DirectX 10”, something my setup lacks) it becomes possible to generate geometry on the fly and even run particle systems entirely on the GLPU. It can be expected that even more parallelizable work will be taken from the CPU and put onto the GPU, providing an infinite playground for the demo coder. Graphics programming has never been this easy and fun. 500 GFLOPS are just $400 $200 away :)

If you are interested, have a look at typhoon labs’ hard-to-find ex-website, hosting Shader Designer, the tool used in the screenshot above as well as a very nice GLSL tutorial with shiny pictures.