Categories
english

Speeding up Swift code using an enum

The most significant limitation of SwiftRay is its slowness. A few weeks ago, I had already sped it up by exploiting more than one core. Since my Mac has 4 cores, it ran about 3,5 times faster.

The algorithm

The first version of SwiftRay was built after a book, which I bought the second volume, Ray Tracing: the Next Week. It exposes an algorithm, the Bounding Volume Hierarchy, which consists in sorting primitives — only spheres at the moment — in a binary tree. The principle is that instead of testing if a ray hits any object in the scene, we first test if it hits the volume of the whole hierarchy at all. If it does, then we test for the two halves, then their two halves, and so on, until we get to a leaf of the tree — that is a primitive.

The speed-up comes from the facts that:

  1. a lot of rays won’t hit any object at all
  2. we can get quickly to the object that does receive the ray

Straight from C++

The original C++ code is the following:

class bvh_node: public hitable {
    public:
        bvh_node() {}
        bvh_node(hitable **l, int n, float time0, float time1);
        virtual bool hit(const ray& r, float t_min, float t_max, hit_record& rec) const;
        virtual bool bounding_box(float t0, float t1, aab& box) const;
        hitable *left;
        hitable *right;
        aaab box;
}

A bvh_node inherits the hitable “protocol” (thought there’s no such thing in C++). Its constructor method takes a list of hitables, which are actually the primitives in the scene.

I will spare you the implementation of the constructor, which actually produces the binary tree. When the tree has been built, each bvh_node has a left hitable and a right hitable as children, which either have two children as well, or point on the same hitable.

The following method determines whether the volume (bounding box) of the BVH node is hit. If it is, it calls itself recursively for its left and right children to see which one is closer, or it hit at all:

bool bvh_node::hit(const ray& r, float t_min, float t_max, hit_record &rec) const {
    if(box.hit(r, t_min, t_max)) {
        hit_record left_rec, right_rec;
        bool hit_left = left->hit(r, t_min, t_max, left_rec);
        bool hit_right = right->hit(r, t_min, t_max, right_rec);
        if(hit_left && hit_right) {
            if(left.rec.t < right_rec.t)
                rec = left_rec;
            else
                rec = right_rec;
            return true;
        }
        else if(hit_left) {
            rec = left_rec;
            return true;
        }
        else if(hit_right) {
            rec = right_rec;
            return true;
        }
        else
            return false;
    }
    else return false;
}

 

Let us take a look at my implementation. It is nearly a straight port, with the exception that my Swift code makes use of optionals instead of booleans to tell if there is a hit:

protocol Hitable {
    func hit(ray: Ray, distMin: Float, distMax: Float) -> HitIntersection?
    func boundingBox(startTime: Float, endTime: Float) -> BoundingBox
}
struct BoundingNode: Hitable {
    let left: Hitable // A Node has necessary two branches, but they can point on the same Hitable if needed
    let right: Hitable
    let boundingBox: BoundingBox
    
 // I spare you the init method which builds the tree
    
    func hit(ray: Ray, distMin: Float, distMax: Float) -> HitIntersection? {
        guard boundingBox.isHitBy(ray: ray, distMin: distMin, distMax: distMax) else {
            return nil
        }
        
        if let leftIntersec = left.hit(ray: ray, distMin: distMin, distMax: distMax) {
            if let rightIntersec = right.hit(ray: ray, distMin: distMin, distMax: distMax) {
                return leftIntersec.distance < rightIntersec.distance ? leftIntersec : rightIntersec
            } else {
                return leftIntersec
            }
        } else {
            if let rightIntersec = right.hit(ray: ray, distMin: distMin, distMax: distMax) {
                return rightIntersec
            } else {
                return nil
            }
        }
    }
    
}

 

When the optimization slows down computations

I had a problem: images still rendered, but computations were actually much slower ! By a factor of 2 to 40 depending on the scene.

Since I’m only human, my premise was that my code had an error. And yes it had: the code to determine if a Bounding Box was hit was wrong. This would make the process slower. But once fixed, it still was very slow.

My second thought was that maybe building the tree was buggy. This would also slow down by big amounts the code since it would not tell quickly if a volume was hit. It was very hard to see in the debugger, so I eventually introduced Rectangle primitives, so I could draw Bounding Boxes. And to my surprise, my code was correct!

That was the time I thought that profiling my code could provide me an insight, so I fired up Instruments > Time Profiler, to state that the code spent a lot of time into

protocol witness for Hitable.hit() in conformance BoundingNode

Searching the web, I learned that “protocol witness” is a virtualization table to solve the conformance to protocol.  That was odd to me. BoundingNode being a struct, I expected to have a straight call to the hit() method, with no indirection.

I watched a video of the WWDC ’16 which proved me I was wrong. Yes, Swift does Dynamic Dispatch on structs when they conform to a protocol.

Once, I learned a little Haskell

A few months ago, I took some time off to learn the basics of Haskell. A lot of exercises in the books have to do with… Trees.

A binary tree in Haskell may be declared as:

data Tree = Leaf a | Branch Tree Tree

In English: A Tree is either a Leaf (with a as data) or a Node with two child trees.

I have watched a presentation which was boring for the most part, but had an interesting point: Haskell’s Algebraic Data types can be implemented as Enums in Swift:

indirect enum Tree {
    case leaf(Hitable, BoundingBox)
    case branch(Tree, Tree, BoundingBox)
}

The indirect keyword is a recent addition to Swift (version 3?) and informs the compiler that the recursive definition of the enum is voluntary.

In case you have not yet understood: I am going to replace the struct calling its own method with an enum, to get rid of Dynamic Dispatch.

The new code

struct BoundingVolumeHierarchy: Hitable {
    
    indirect enum Tree {
        case leaf(Hitable, BoundingBox)
        case branch(Tree, Tree, BoundingBox)
    }
    
    var root: Tree? = nil

    private func boxOf(tree: Tree) -> BoundingBox {
        let box: BoundingBox
        switch tree {
        case .leaf(_, let leafBox):
            box = leafBox
        case .branch(_, _, let branchBox):
            box = branchBox
        }
        
        return box
    }

    
    private func hit(tree: Tree, ray: Ray, distMin: Float, distMax: Float) -> HitIntersection? {
        switch tree {
        case .leaf(let hitable, _):
            return hitable.hit(ray: ray, distMin: distMin, distMax: distMax)
        case .branch(let left, let right, let bbox):
            let isHit = bbox.isHitBy(ray: ray, distMin: distMin, distMax: distMax)
            if isHit == false {
                return nil
            } else {
                if let leftIntersec = hit(tree: left, ray: ray, distMin: distMin, distMax: distMax) {
                    if let rightIntersec = hit(tree: right, ray: ray, distMin: distMin, distMax: distMax) {
                        return leftIntersec.distance < rightIntersec.distance ? leftIntersec : rightIntersec
                    } else {
                        return leftIntersec
                    }
                } else {
                    return hit(tree: right, ray: ray, distMin: distMin, distMax: distMax)
                }
            }
        }
    }
    
    func hit(ray: Ray, distMin: Float, distMax: Float) -> HitIntersection? {
        return hit(tree: self.root!, ray: ray, distMin: distMin, distMax: distMax)
    }

}

I don’t find the new implementation very elegant, since I need the box() method to extract the Bounding Box from the Tree, but I don’t know Swift enough yet to envision a better solution.

Results

I won’t make you wait: yes, the implementation is efficient now. I’m very happy for the improvement, since I was hopping for a speed improvement of 2 times.

Simple Scene

200 x 200 px @ 100 rays/px
without BVH: 10.76 s
with BVH: 11.01 s
speed-up: 0.977 times

In this Scene, there is a slight slow down, which is not surprising since there are only 4 spheres, and hierarchizing them does not provide any benefit.

Sphere Array Scene

200 x 200 px @ 100 rays/px
without BVH: 42.25 s
with BVH:  11.42 s
speed-up: 3.7 times

I designed this scene knowing that the algorithm would be efficient. Removing the rectangles makes it more efficient.

Big and Small Spheres

400 x 266 px @ 100 rays/px
without BVH: 523 s
with BVH: 48s
speed-up: 10.9 times

The algorithm becomes really efficient when there are a lot of objects, which only occupy small portions of the space. The speed up is impressive in this reference scene.

Categories
english

So, I made a Raytracer

I decided to take a month off from client projets, so I could work on subjects which I don’t usually have the time to work on.

Since I began learning Haskell lately, I knew that I had to code a real project. Actually, I think it’s the only way to study programming seriously: stick to a problem and find ways to attack it. A Raytracer looked like a reasonable idea for a project, since Raytracers use recursivity, which is the specialty of functional languages like Haskell.

Anyway, to sum up: I began with Haskell, and I ended with Swift. I met some difficulties regarding pseudo-random numbers in Haskell, I was tired and I was not sure about what was wrong (this was my first raytracer). I have not really given up, just passed on to keep my motivation.

The result is two projects:

https://github.com/Ceroce/HaskellRay

https://github.com/Ceroce/SwiftRay

SwiftRay

I had no precise idea on how to code a raytracer, so I followed an e-book, Ray Tracing in One Weekend by Peter Shirley.

The original source code was written in C++. I was asked if porting it to Swift had been hard: Not really. Sometimes it was difficult to follow the C++ code, because of the way it is written, but Swift is way more elegant than C++, and has all required features — in particular operators overloading, which are more than useful when working with vectors.

The second question was how it performs, compared to C++. I don’t know, since I have not measured. I don’t care really, and that was not an aim for my experiment. All I can say is that it’s about the speed I expected: very slow. Shirley uses a “Pathtracer” algorithm. Wikipedia says that this is a characteristic of these raytracers. It already takes hours to render with 100 rays by pixel (112 minutes on my Mac for the very small and simple image above), and the image is still very noisy. At least 500 rays would be needed!

Currently the program uses a single thread. The obvious next step is therefore to parallelize the work so I can use all 4 cores of my Mac. Since I mostly used Structs (≃ immutable objects), it should be easy. I let you know when I find the time…