MikeTracker

MikeTracker is a small project I've been developing these days. It's a tracker, just like M4G, but for PC. It's also uglier. It uses the FMOD library (great lib!) and Allegro, as usual.

MkPerfMon

MkPerfMon showing CPU idle time.
MkPerfMon is a test program for the PDH API in Windows.

Raytracing - Part 1

A raytracer is a program which creates images tracing rays from the camera to the scene. It can handle easily things that are described with mathematical methods, it's capable of creating photorealistic images. Unfortunately, it's (often) a slow method. Examples of raytracing include Pixar movies, POV-Ray...

The algorithm is simple: you have to trace a ray for each pixel on the screen. If a ray touches a shape, then calculate lighting for that point and plot it. It's simple, but you need to code intersection testing code for each shape you want to render (spheres, planes...). Sphere-ray intersection testing code is one of the easiest to code. So, the main loop for a raytracer is:

For each point:
Trace ray and test intersection.
If it exists, calculate lighting and plot point.

You can use orthographic projection for the ray: set the ray's origin to the point, and set the direction as an unit vector pointing forward.

The formula for testing line-sphere intersection is:

d: distance
l: direction of the ray (normalized)
o: start position of the ray
c: sphere center
r: sphere radius

d = (l * c) +- sqrt( (l * c)2 - c2 + r2 )
If the value under the root is less than zero, the ray doesn't intersect the sphere.
If the value is greater than zero, there are two intersection points (using +-):
p = o + d*l

This formula is easy to code. I'll handle lighting in part 2.

Starfield

The starfield effect is a popular effect, present in a lot of demos. It's easy to code and optimize.

A starfield effect consists of a lot of 3D points, that are animated and projected. The initial position of the stars is usually random. After projecting each point, you decrement the Z coordinate of the point. If the point goes off-screen, the point needs to be recreated.

To project a 3D point, use this formula:

projected x = x / z
projected y = y / z

Create an array of random points. After projecting each point, decrement its Z coordinate. If Z becomes a negative number, or the projected point goes offscreen, calculate another random point. You should scale/translate the projected point.

When you plot the point you can apply different effects, like antialiased particles, different velocities, motion blur, lines or circles instead of pixels...

Metaballs

The metaball effect is a famous demoscene effect. It's a cool effect, and it's easy to optimize.
The theory is pretty simple: for each ball, you evaluate the value of a function for a given point, and add it to a variable. If it's over some threshold, then you can plot that point. The function is usually:

P: center of the metaball
S: screen point

f(S, P) = 1 / (S - P)2
For each metaball add f(S, P) to a variable (P: current ball center)


It's very easy to compute this function for each metaball. Howewer, this function is slow, due to the division. For this reason, you must find an alternate function. Another possible function is:
f(S, P) = (1 - S - P2)2

You can erase the square root, due to this:
sqrt(x)2 = x

So, the final formula is:

r = (Sx - Px)2 + (Sy - Py)2
f(S, P) = (1 - r)2


This formula is faster, but not fast enough. However, there's another trick you could do. Most of the space in the screen won't be covered by the metaballs, so you can change the code to scan for metaballs (each rectangle in the image, for example), instead of scanning each pixel of the screen.

Mandelbrot Fractal - Part 3

In my last post I said I was going to show the fractal with colors, and here it is! In this post I'll describe colors in the Mandelbrot fractal.

In my last post I wrote some pseudocode you could use to draw the fractal. In the pseudocode I told you to count the number of times you use the formulas. That's an index for your pallete. You should be able to implement that easily.

If you draw it, though, you'll notice a problem. You can see "banding" in the fractal. No matter how high your iteration limit is, the banding will still be there. You can fix this by changing your formula. Up until now you were doing something like this:

i: index into pal
cnt: iteration counter

i = (pal_size * cnt) / limit
plot pallete[i]


The algorithm should be similiar to that. To eliminate banding, replace the algorithm to this:

i: index into pal
cnt: iteration counter

(calculate iteration formulas 4 more times)
cnt = cnt + 5 - ( log(log(|z|)) / log(2) )
i = (pal_size * cnt) / limit
plot pallete[i]

If you test it using these formulas, banding should be gone (mostly). Alter your pallete until you get something you like.

MK-Hextiler

This is MK-Hextiler, an enhanced version of Hextiler (a program we use at NSN). It uses the Agar library.