Qef's Website

Just before I went home for Xmas, JH reminded me of the little ray tracer I wrote at University. It's called Silsna (for boring reasons). I've still got the code in CVS, so I dug it out to play with a bit, and put it on my laptop as something to keep me amused while I was on holiday. Silsna never really worked properly, and couldn't do much, but for someone who likes tinkering with computer graphics it's fun to hack on.

The code was a mess, and in C++, which I've learnt to hate in the last few years. I started tweaking the low-level maths routines, and started finding bugs straight away. Before I knew it I'd rewritten the whole thing in fairly sound C and added a test suite for a lot of the low-level functions. I've even used the excellent Valgrind to get rid of memory leaks and pointer bugs. While visiting my parents I added a little XML input language and some crufty expat code to read it. With a few more bits added I'll be able to release it, although it's not yet doing enough to be particularly interesting to anyone else. It still has only spheres and planes, for one thing.

Converting to C seemed like a good idea overall. It should give me greater portability, and probably better performance (because C++ compilers have their work cut out just parsing the language, so don't have much oomph left to optimise their output), and it's easier to understand. Also important is that it gives me vastly faster compile times (with gcc).

Object Oriented C

I'm writing this stuff down as I work through it, to straighten it out in my befuddled brain. I can't promise it makes any sense.

The only problem I've been having with C is dealing with calling methods on objects. Usually this isn't a big deal because most C programs don't try to do the OO thing, but a ray tracer is inherently object oriented. I need to be able to go through all the shapes in a scene and call the appropriate ray-shape intersection function, for example.

It is of course possible to do OO in C. It's just a bit more tedious than C++. GTK+ and Gnome have a huge elaborate infrastructure for this stuff, but I want just very simple method calls and the most basic of inheritance. I need to be able to do this stuff efficiently, and with out introducing bugs everywhere.

My first attempt, which works for the simplest things, was just to include function pointers in objects (which are just structs). This turns out to be not good enough:

• Each object has a function pointer (4 bytes on IA32) for every method, so when loading a big scene the memory usage could be quite high. I'm not too worried about this because memory is cheap nowadays, but it's a disadvantage.
• To inherit from a class I have to declare a struct for the subclass which has all the method pointers and member variables of the base class in the right order followed by the ones for the derived class. It would be easy to get these mixed up and break things. I also have to remember to initialise all these things at the right time.

The obvious way to fix the first problem is to do the standard thing for implementing OO, which is to have a vtable structure (an array of pointers to the methods) in one place and point to it from each object (pause to hack xfig support into my blog code):

So each object has a single pointer overhead, which is fine. That would also open the way for identifying objects (what C++ calls RTTI) in assertions, to detect bugs, simply by adding extra information to the vtable structure.

In the back of my mind was the worry that calling methods through the vtable would be less efficient, although I didn't think it would be a big deal. A little benchmark (method-bench.c) showed no significant difference for 10 billion method calls, so no need to worry about performance issues here.

The benchmark program made me realise one problem with having an array of pointers to functions as the vtable. The functions will be of different types, so I'll have to have the vtable be an array of void*, which will mean I'm calling methods without prototype checking. That's dangerous, so lets instead use a struct as the vtable. That would also make it easier to have a macro to call methods by name. I'll use the prefix meth_ for all the method entries in the vtable, in case I want to add other things later. OK, I've still got the problem that derived classes need to construct a vtable with all the right stuff in the right order, and if I add a method to the base class then it will have to go in the derived class too, or I'll be calling the wrong method and the compiler won't be able to warn me.

I don't want to get into any serious macrology, so lets see if something very simple will be sufficient. If I put the list of methods and object data into macros I can just expand those in the base class and the derived class to make sure we get the right things in the right order. It's not completely automatic, but it should be enough to prevent cock-ups. Here's what I used to have to declare the base class for shapes (spheres, etc.), with each derived class having a copy of all the values in the base class with other stuff added afterwards:

/* Forward reference */
struct SilsnaShape;

/* Types of method pointers */
typedef void (*SilsnaShapeFunDelete) (struct SilsnaShape *shape);
typedef int (*SilsnaShapeFunIntersecting) (const struct SilsnaShape *shape,
                                           const SilsnaVector eye,
                                           const SilsnaVector dir,
                                           SilsnaVector p, double *distance);
typedef void (*SilsnaShapeFunNormal) (const struct SilsnaShape *shape,
                                      SilsnaVector N, const SilsnaVector p);


/* Class declaration */
struct SilsnaShape {
    SilsnaFColor c;
    SilsnaMatrixP transform, transform_inv;
    SilsnaShapeFunDelete meth_delete;
    SilsnaShapeFunIntersecting meth_intersect;
    SilsnaShapeFunNormal meth_normal;
};
typedef struct SilsnaShape SilsnaShape;

With my new approach I put the list of methods and member variables in macros, so after declaring the function types I get this for the Shape class:

#define SILSNA_SHAPE_VTABLE \
    SilsnaShapeFunDelete meth_delete; \
    SilsnaShapeFunIntersecting meth_intersect; \
    SilsnaShapeFunNormal meth_normal;

#define SILSNA_SHAPE_DATA \
    SilsnaFColor c; \
    SilsnaMatrixP transform, transform_inv;

I use these macros to declare the struct types for the vtable (which will be a singleton) and the actual class (which includes a pointer to the vtable):

struct SilsnaShapeVtable {
    SILSNA_SHAPE_VTABLE
};
typedef struct SilsnaShapeVtable SilsnaShapeVtable;
extern SilsnaShapeVtable silsna_shape_vtable;

struct SilsnaShape {
    SilsnaShapeVtable *vtbl;
    SILSNA_SHAPE_DATA
};
typedef struct SilsnaShape SilsnaShape;

The Sphere class is declared in the same way, except that the macros just add new entries. We get the base class (Shape) methods and variables from the macros defined above, so that we won't have to alter the derived class if we add a method to the base class:

#define SILSNA_SHAPE_SPHERE_VTABLE \
    /* no extra methods */
#define SILSNA_SHAPE_SPHERE_DATA \
    SilsnaVector center; \
    double radius, radius_2;

struct SilsnaShapeSphereVtable {
    SILSNA_SHAPE_VTABLE
    SILSNA_SHAPE_SPHERE_VTABLE
};
typedef struct SilsnaShapeSphereVtable SilsnaShapeSphereVtable;
extern SilsnaShapeSphereVtable silsna_shape_sphere_vtable;

struct SilsnaShapeSphere {
    struct SilsnaShapeSphereVtable *vtbl;
    SILSNA_SHAPE_DATA
    SILSNA_SHAPE_SPHERE_DATA
};
typedef struct SilsnaShapeSphere SilsnaShapeSphere;

The vtables need to be initialised when the program starts up, so I've got a function called silsna_init() which calls silsna_shape_class_init() (and later similar functions for other class hierarchies when they're added). That function then calls a vtable initialisation function for each class in the hierarchy, passing in a pointer to the vtable we want initialised:

void
silsna_shape_class_init (void)
{
    silsna_shape_init_vtable(&silsna_shape_vtable);
    silsna_shape_sphere_init_vtable(&silsna_shape_sphere_vtable);
    silsna_shape_plane_init_vtable(&silsna_shape_plane_vtable);
}

The reason each of these takes a pointer to its vtable is so that I can call the base class one from the derived class ones, so I won't have to adjust the Sphere initialisation function when I add a method to Shape. They look like this:

void
silsna_shape_init_vtable (SilsnaShapeVtable *vtbl)
{
    assert(vtbl);
    vtbl->meth_delete = silsna_shape_delete;
    vtbl->meth_intersect = 0;
    vtbl->meth_normal = 0;
}

void
silsna_shape_sphere_init_vtable (SilsnaShapeSphereVtable *vtbl)
{
    assert(vtbl);
    silsna_shape_init_vtable((SilsnaShapeVtable *) vtbl);
    vtbl->meth_intersect = silsna_shape_sphere_intersect;
    vtbl->meth_normal = silsna_shape_sphere_normal;
}

The methods initialised to 0 are of course pure virtual. The Sphere class provides implementations. If the null ones get accidentally called an assertion will be thrown. Which brings me to calling methods. I've got a macro to do this. It's not too messy, although it has to use token pasting.

/* Macro to call a method on an object */
#define SILSNA_METHOD(object, method) ( \
    assert(object), \
    assert(object->vtbl), \
    assert(object->vtbl->meth_ ## method), \
    object->vtbl->meth_ ## method)

/* For example, to test a ray for intersecting with a sphere
 * (passing 5 arguments in): */
hit = SILSNA_METHOD(shape, intersect)(shape, eye, dir, p, &t);

This is all more complicated than I'd like, but it's not that bad. It should make things easy enough to maintain so long as I follow the right procedures for changing classes. Here's a rough stab at what those procedures are:

• To add a new base class, copy and adjust all the stuff from an existing base class, and then add a call to its class hierarchy initialisation function from silsna_init().
• To add a new derived class, copy and adjust all the stuff to declare it from an existing derived class, and add a call to its vtable initialisation function from the initialisation function for the class hierarchy.
• When writing a constructor, make sure it initialises the vtable and anything in the DATA macro for the class, and calls the base class constructor.
• When writing a destructor, make sure to delete any dynamically allocated stuff in the class's DATA macro and call the base class destructor.
• To add a method to the base class, add stuff to its VTABLE macro and the vtable initialisation function for that class, and add the function typedef and actual implementation. Derived classes will get it automatically without being altered.
• To add data to a class, add it to the DATA macro and put initialisation code in the constructor (and add code to the destructor if it's dynamically allocated).
• To override a base class method in a derived class, write the implementation and alter the class initialisation function to put it in the vtable, overwriting the pointer that the base class puts there.

Well, I seem to have ended up with something good enough. I've only got three classes so far though, so it'll be a while before I know how well this works in practice. There are still some things I want to add, like some extra information in the vtables that will allow me to assert that I have an object which derives from a particular class, or perhaps a way of printing out an object for debugging. Perhaps I should have an Object superclass to hold debugging methods. Still, I've got enough stuff for now that I can get back to doing the actual ray tracing and make some pretty pictures.