32leaves.net

Raytracing: second shot

Alright, this is propably the last shot I’m taking on raytracing. I implemented some pretty neat features. First of all: reflection:
rawreflection_0

The left picture shows the image without reflection, the right one with reflection enabled. Actually reflection is pretty easy to implement. All we need to do is recursivly trace the reflected rays.

The second feature is also pretty neat: anti-aliasing. Actually that also is not too difficiult to implement. I implemented the most simple way of doing anti-aliasing which is supersampling. The following picture shows the difference between un-aliased and aliased rendering:
reflection_comparison

To get a better impression on what anti-aliasing does, the following three pictures show the same image with no antialising, 2 times, 4 times and 16 times anti-aliasing:
reflection_0reflection_2reflection_4reflection_16

Of course the changes are in the SVN. The username, as well as the password, is guest

Raytracing: my first shot

After revisiting the Google talk about splines and fractals I had the idea to do this in three-dimensional space by using quaternions instead of complex numbers. It turned out that it wasn’t utterly difficult to render a simple three-dimensional Sierpinski gasket (or Menger-Sponge) using PovRay. At least installing PovRay on my Mac took more time than writting the script.
mengerSierpinski
While fuzzing around with PovRay a crazy idea came to my mind: why not write my own ray tracer. Of course that would only be the simplest possible as I only wanted to get a rough understanding on how this stuff works. After doing a bit of research it turned out that it shouldn’t be a too difficult task. Hey, this is one of the excercises in every “Computer graphics basics” lecture.
Three hours later I had a rough shot, but somehow my maths for calculating the rays was wrong. The day after, a friend of mine and myself went to a maths professor at my University and asked him if he could have a quick look at the formulas. His explanations were (as always) very insightful and simply brilliant. With the ideas he gave us we went on to get the missing bits done. And 4 more hours later we had a working ray tracer. (The sierpinski gasket was not rendered by my ray tracer, but I can’t figure out how to exclude images from the WordPress gallery).
Of course after 7 hours of work the ray tracer is far from being perfect. There are a few neat features missing (which might follow) such as shadows, reflection and radiosity (which would really be a big task). Also the maths concerning the projection plane are not totaly right. We should rather introduce a coordinate system transformation to get this done than hacking things together as it is right now. All in all it was a lot of fun to write that thing. If you want to have a look at the source code, check it out here (username: guest, password: guest).

Note to myself: tail recursion in Haskell does not allow me to stop thinking

We’ve propably all heard that tail recursion is the way to go. That’s true, but as I’ve learned today applying this principle does not free you from thinking about your code.
The task was to implement the Josephus game. That’s particularly straight forward in imperative languages such as Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
private int josephus(int amountOfSoldiers, int interval) {
    List<Integer> soldiers = new LinkedList<Integer>();
    for(int i = 1; i <= amountOfSoldiers; i++) soldiers.add(i);
   
    int index = 1;
    while(soldiers.size() != 1) {
        for(Iterator<Integer> iter = soldiers.iterator(); iter.hasNext() && iter.next() != null; ) {
            if(index++ % 3 == 0) iter.remove();
        }
    }
   
    return soldiers.get(0);
}
But Java is not much of a challange, so lets give this a shot in Haskell:

1
2
3
4
5
6
7
8
9
10
11
12
13
josephus :: [Int] -> Int
josephus []  = 0
josephus [x] = x
josephus l   = josephus_ l 1 where
    josephus_ [x] _ = x
    josephus_ xs o  = let
        len = length xs
        off = ((o + len) `mod` 3) in
        josephus_ (dropByInject o xs) off

dropByInject _ []     = []
dropByInject m (x:xs) | m `mod` 3 == 0 = dropByInject (m + 1) xs
                      | otherwise      = x:(dropByInject (m + 1) xs)

Obviously the dropByInject function is not tail recursive. When we call the following program

1
main = putStrLn (show [josephus [1..l] | l <- [1..2000]])

which computes the “Josephus number” from 1 to 2000 soldiers, takes roughly 0.792s.

So I did a second shot which is tail recursive:

1
2
3
dropByInject r _ []     = r
dropByInject r m (x:xs) | m `mod` 3 == 0 = dropByInjectAp r (m + 1) xs
                        | otherwise      = dropByInjectAp (r ++ [x]) (m + 1) xs

. And here is where I stopped thinking – which immediately became clear to me as the same task as above takes 23.791s. Wow, that’s not really better than the 0.792s of the not-tail-recursive version. So why is that:
if we take a look at how the list is constructed in the otherwise part of the dropByInject function we see that the x is appended to the end of the list via

1
(r ++ [x])

. And that was the mistake – lists in Haskell are linked lists and appending to linked lists takes

    \[\mathcal{O}(n)\]

as we have to find the end of the list first. Upps

Alright, let’s go for a third shot:

1
2
3
dropByInject r _ []     = reverse r
dropByInject r m (x:xs) | m `mod` 3 == 0 = dropByInjectTr r (m + 1) xs
                        | otherwise      = dropByInjectTr (x:r) (m + 1) xs

This version takes only 0.704s. That’s not lightyears of speed gain compared to the first version, but hey at least it’s tail recursive.

Fork me on GitHub