Ray Tracer Challenge: Smalltalk

Dear diary,

It looks like I have some time off coming up, and it feels like a good chance to try something different. I've had The Ray Tracer Challenge1 for almost a year now and haven't even touched it yet! And it would be really cool to make use of that copy of the Smalltalk-80 Purple Book I've had lying around for almost as long.

I wonder how far we can get in the space of a week. Don't worry, diary, I'll let you know how it goes.

Just so I don't forget, here's a picture of what I would like to achieve.

thegoal.jpg

Day 1

Setting up my environment

So it looks like I can choose Pharo, Squeak, or GNU Smalltalk2. The introduction to the GNU version says it closely follows Smalltalk-80, so that should be useful I think! It also says it's headless, so it can be used with files, and has some bindings to graphics libraries like SDL3, but doesn't have a graphical environment like the other two.

Documentation seems fairly minimal but apparently Smalltalk is self-descriptive, so many I'm not supposed to be searching the web for these things.

Perhaps I'll get Squeak ready instead.

This Smalltalk book is quite weird

Hm, a lot of the examples in the Purple Book don't seem to directly correspond to the syntax I would type into the environment. The implementation description reads like a spec, in layout and formatting, so I'm not sure if that's something I actually write in code somewhere.

book-syntax.jpg

I can only assume this is all in reference to the original Smalltalk environment. The thing is I can make sense of what it's describing, I'm just not sure how to write it or where I would actually put this code.

That said, I really do like this way of documenting code and it's clear some thought has been put into how to organise it too. It reminds me a bit of regions in C# or pragmas in Objective-C, except that those use special comments to group things in large objects.

How the fuck do you actually do something?

Alright, people say that switching from object-oriented code like Ruby or Java to something pure functional like Haskell is difficult, because it requires a different way of thinking.

I challenge that assertion!

It would still take me only a few minutes to do a trivial hello world in Haskell, C, Ruby, Java, C++, Javascript, or any other similar language. I put code into a file and then I point the interpreter or compiler to that file and then I either get "Hello, World!" straight away or a nice executable that will then print it out.

The example in Smalltalk is to open a workspace and use an object called Transcript, but it doesn't seem much different to doing console.log inside my browser's console.

"Semicolon is called cascading, which is like method chaining"
Transcript open; show: 'Hello world!'.
helloworld.png

I guess that's enough to play around with things, but I want to do this ray tracer challenge and for that I need to learn how to make classes. Then I can use the workspace or a special renderer class to make it appear on the screen.

So, it looks like I probably have to do something with the browser, to set up a little hierarchy for my project. Looking through the stuff that's there, there's all sorts of stuff I can look at. And the code that appears when I click on a selector looks super similar to how things are printed in the Purple Book.

Thinking in images

I ordered a copy of Squeak By Example4 to help out, since I feel like I have to unlearn how I normally do programming. I'm so used to building everything as a hierarchy of files and directories, or placing everything into just a handful of files to begin with.

Turns out you have an image and everything you do is saved inside it, and you basically live inside that image. Those workspaces are essentially REPLs, then, but you can also open as many of those as you want and when you save and reload the image, they will all be there still. Pretty cool!

Actually, it makes me wonder how you deploy stuff for other people to use, but that's a question for another time.

Anyway, I think I've done enough today. I'm sure that once I understand the fundamentals I can start thinking about the challenge I want to complete.

Day 2

Squeak by Example arrived! Just flicking through the pages and I think it should give me enough to become self-sufficient. One of the sections is about how to add a new method, and it shows how you do it TDD-style, which is cool. It uses the example of making a shouty string, like converting it to uppercase and then adding an explanation mark at the end.

Everything in the browser

I'm starting to make sense of it now; pretty much everything is done via the browser. It feels a little fiddly to search through, but I suppose I've just not found an easy way of doing that yet.

Just to get into the habit, I scrolled through the list of objects to see if there were any that would talk to the network. Poking around Network-Url and also NetworkTests-Url gave me a good idea of how to download the contents of a URL and then print them out into the transcript. I tried it out on my own website.

testUrl := 'https://leemeichin.com' asUrl.
Transcript open; show: testUrl retrieveContents contents.
printurl.png

No-code before no-code was cool

It feels more useful to provide screenshots of all of this, and I've wondered if this is an example of a 'no-code' sort of programming environment. It's not visual in the sense of connecting nodes together to form a graph though, which is what a lot of visual languages and no-code products do.

morph.png

One of the powerful features is that literally everything is configurable. If I middle click on one of the windows it becomes surrounded by a bunch of little tools that allow me to play with the UI, debug it, customise it, and more. Squeak calls it Morph, and it seems like an evolution of MVC. I think Pharo has a very similar thing.

What separates Smalltalk from these other no-code tools, I think, is that it accepts that you will actually have to write code at some point if you want to build anything useful. You know, like how Haskell accepts that non-pure code needs to exist if you want programs that actually do something.

Smalltalk and its environments seem to solve that problem by giving you interactive tools to create and organise code. It's quite interesting really and it makes me wonder how something similar would look if you rendered the contents of a running Ruby VM in the same way.

It's all older than I am

I guess I can only marvel at the various kinds of systems that were built so many decades ago that all show how cool it can be to work with a dynamic programming language. Lisp is old enough to be my dad and the way of working with Lisp was to basically modify the program as it was running (this is pretty much how Emacs works via emacs-lisp) via a REPL. It feels like you might do similar with Smalltalk, too.

Neither of these are like C, C++, Rust, or other compiled languages that require an executable to be compiled and then shipped, or deployed. Ruby offers a middle ground, I suppose, which is also what makes it a pleasure to work with.

Anyway, I haven't made too much progress today but I think I understand more. I'll come back tomorrow and see if I can figure out how to render an empty canvas or just something I can draw things onto.

Day 3

Opened up Sqeak so I could get cracking today. Must have saved the image in a weird state last night since it was behaving strangely. Managed to close the project and make a fresh one and that was fine.

Data structures

The ray tracer challenge book starts off by defining some data structures. I think I'll get on with that first, so I can feel like I've achieved something.

I suppose it'll be useful to keep all of the objects I create under one category, so I created one called RayTracerChallenge. It doesn't do anything by itself though, so some new classes are needed.

The first one is a tuple, which contains 3D co-ordinates and an extra value to state whether this is a point in space, or a direction (or vector). All I had to do here was update the code example in the browser and save it, and then the class was created.

(One thing that feels odd is listing instance variables as a space separated string. Not even a list data structure.)

Object subclass: #Tuple
       instanceVariableNames: 'x y z pointOrVector'
       classVariableNames: ''
       poolDictionaries: ''
       category: 'RayTracerChallenge'
tuple.png

I'll make two subclasses from that, called Point and Vector. The only difference is that one will initialise pointOrVector to 0 and the other will initialise it to 1. I'll leave screenshots out this time.

conflict.png

Oh…I guess these objects aren't namespaced or anything. I'll just add a prefix to each object instead, like RTC for RayTracerChallenge. Reminds me of how it was in Objective-C.

In fact, why not do this TDD-style. I'll make some tests first.

TestCase subclass: #RTCTupleTest
         instanceVariableNames: ''
         classVariableNames: ''
         poolDictionaries: ''
         category: 'RayTracerChallenge-Tests'.
RTCTupleTest»testAsPoint
    "A tuple where w is set to 1 is a point"
    tuple := RTCTuple asPoint.
    self assert: (tuple class asString) equals: 'RTCPoint'.
    self assert: (tuple w) equals: 1.
RTCTupleTest»testAsVector
    "A tuple where w is set to 0 is a vector"
    tuple := RTCTuple asVector.
    self assert: (tuple class asString) equals: 'RTCVector'.
    self assert: (tuple w) equals: 1.
testing.png

There's a lot of clicking around and not very much typing so far, so it definitely feels slower as I get to grips with this. It actually occurs to me that the Acme editor from Plan9 is quite similar, except it does it all through text rather than UI widgets.

These tests aren't passing, of course, because I don't have my Point and Vector subclasses. The joy of TDD here is that I can automatically add them via the UI. Which I just did. After that, they just needed to be initialised with sensible defaults and some accessors.

RTCTuple»initialize
    x := 0.
    y := 0.
    z := 0.
    w := 0.
RTCVector»initialize
    w := 0.
RTCPoint»initialize
    w := 1.

The w field is readonly to avoid mixing up Points and Vectors by changing the state of the object.

Mathemologics

Turns out there's still a fair bit to do with these objects: I've got to make them comparable and it has to be possible to do maths with them, e.g. adding two tuples together, or subtracting them, or multiplying them as you would with a matrix.

According to my two Smalltalk books, it seems like Smalltalk has an abstract class called Magnitude which is used for comparison. All I need to do is define an implementation for = (equals), < (less than) and hash and then I'll get a lot of convenience methods from it. Before I do that, it would be more helpful to define some arithmetic operations though, so that I can use subtraction to compare two objects for example.

Subtraction

As usual, tests first and then implementation second. I'm using the test examples from the ray tracer book and my vague knowledge of vector maths from the last time I messed around with games and stuff.

RTCTupleTest»testSubtractTwoPoints
  "Subtracting two points creates a vector describing the distance between two points."
  | pointA pointB |

  pointA := RTCTuple asPoint x: 3 y: 2 z: 1.
  pointB := RTCTuple asPoint x: 5 y: 6 z: 7.

  self assert: (RTCTuple asVector x: -2 y: -4 z: -6) equals: pointA - pointB.

Subtracting one point from another doesn't mean I'll get another point, I'll actually get the distance between those two points instead, which is a vector. But when I subtract a vector from a point instead, then I will get another point.

RTCTupleTest»testSubtractVectorFromPoint
    "Subtracting a vector from a point results in another point."
    | vector point |

    vector := RTCTuple asVector x: 5 y: 6 z: 7.
    point := RTCTuple asPoint x: 3 y: 2 z: 1.

    self assert: (RTCTuple asPoint x: -2 y: -4 z: -6) equals: point - vector.

The test debugger is kinda cool, actually, although the output could be more helpful. I haven't got to the testing chapters in the books yet, so I expect that I've just missed out some things that would show me more useful info.

testfail.png

Back to the maths, the implementation of the subtraction feature is this (and it's in that screenshot too):

RTCTuple»- aTuple
    "Subtract aTuple from this tuple"
    ^RTCTuple
        x: x - aTuple x
        y: y - aTuple y
        z: z - aTuple z
        w: w - aTuple w.

All it does is make a new tuple by taking the values of one tuple and removing them from the other. The use of w to tell the difference between a point or vector makes it very easy to convert them, without having loads of logic to check if a Point should become a Vector, or vice-versa. I also notice I haven't really used the special subclasses I made because of this.

There are some other tests I need to add but they follow the same pattern: subtracting two vectors gives me another vector. And there is the edge case where it doesn't make sense to subtract a point from a vector.

Addition

I'm just going to breeze through the rest of these because otherwise I'll be rewriting the whole damn book.

Addition is like subtraction, so there's not much to do there. It has a similar edge-case in terms of adding two points together, but I'm not going to bother handling errors.

RTCTuple»+ aTuple
    "Add aTuple on to this tuple, resulting in either another point or a vector"
    ^RTCTuple
        x: x + aTuple x
        y: y + aTuple y
        z: z + aTuple z
        w: w + aTuple w.

Negation

Getting the opposite a vector (or negating it) is a case of subtracting it from a 'zero' value. I've already done subtraction, so this is child's play.

RTCTuple»negate
  "Create a tuple with the opposite values, e.g. by swapping the signs. The w value is not affected."
  ^(RTCTuple zero) - self

Distance

In rendering, a vector can represent a distance. It's basically the length of a straight line from the starting point of the vector to the ending point.

In fact it's not so different to calculating the hypotenuse of a triangle, except this time there are three dimensions rather than two.

RTCVector»length
    "Calculate the distance represented by a vector."
    ^(x squared + y squared + z squared) sqrt

I added that one to my Vector subclass, since it doesn't make sense to calculate the length of a point.

Wrapping up for the day

Between taking notes on my progress and going through the challenge, it's taken maybe half a day to get to this point. I think that's enough for one day, I've still got the rest of the week ahead of me after all. And I'm starting to feel more comfortable in the environment which is nice.

Looks like the next chapter is actually about rendering. I've still got to handle a couple more operations (like the dot product and cross product) but I'll finish that up later.

Until tomorrow, dear diary!

Day 3.5

I really wanted to finish off this first chapter, so I did! Using the example in the ray tracer challenge book, I made a little ticker in the workspace to demonstrate a projectile falling to the ground.

Console Cannon

cannons.png

I'll just leave it here, it's a nice little toy example. The Projectile and Environment objects are just containers for some vectors and points. The Ticker calculates a new position based on the projectile's velocity and some values corresponding to wind and gravity.

Transcript clear.

p := RTCProjectile
        withPosition: (RTCTuple asPoint x: 0 y: 1 z: 0)
        andVelocity: (RTCTuple asVector x: 1 y: 1 z: 0) normalize.

e := RTCEnvironment
        withWind: (RTCTuple asVector x: 0 y: -0.1 z: 0)
         andGravity:  (RTCTuple asVector x: -0.01 y: 0 z: 0).

t := RTCTicker new.

i := 1.
[ p position y > 0 ] whileTrue: [
    Transcript showln: 'Tick #', i asString.

    p := t tickwithEnv: e andProj: p.

    Transcript showln: 'X: ' , (p position x) asString;
               showln: 'Y: ', (p position y) asString.

    i  := i + 1.
]

Now to play some real games.

Day 4

A lovely winter morning indeed, and here I am back at my desk to do more of this challenge.

Flicking through the second chapter, it seems to start off with a bit of colour theory but there isn't anything scary there. In fact, in terms of implementation I'm set up for re-using all of the stuff I did with tuples, vectors and points yesterday.

The smalltalk standard library

There's nothing special to show off here, I just made another subclass of my RTCTuple and then created fresh accessor functions to refer to x, y and z as red, green and blue respectively.

Smalltalk already has a Color object, the same as it has a Point object, and I was tempted to use those instead of my home-grown copies. I decided against it because the Point only represented two dimensions and I need three, and as convenient as the Color one might be I would be making things needlessly difficult by having to convert it back and forth.

I'm not good with colours

I had to add a function to calculate the Hadamard product of two colours. The hadamard product is similar to calculating the dot product of a vector, but rather than getting a scalar value back that represents the sum of x, y and z, you get a new colour where the two reds were multiplied, the two greens, and the two blues.

hadamard.png

Since I'm not good with colours, my attempts to demonstrate how it works aren't so good. I just plugged a few different numbers in until I got something that wasn't black.

Data driven design

I'm reminded of what little I know about data driven design, where one is encouraged to work with primitive data structures over high level abstractions around them. A list of structs might be more effective to work with than a collection of classes, for example.

Knowing how much I'm typing things like RTCVector new x: 1 y: 2 z: 3, I'm considering adding some convenience methods to the array object.

#(1 2 3) asVector.
#(0.1 0.2 0.3) asColor. "I bet this already exists"
#(4 5 6) asPoint.
#(1 2 3 0) asTuple.

I'll come back to that one later, since I'm bikeshedding. The real problem is that I made a generic tuple and rather than indexing into it, I gave the values names that only make sense for vectors and points.

For now I'll make it work and then I'll go and tidy it up.

Hello world but for rendering

Now for the fun part and slightly more difficult part! Yay!

By doing the demo with colours I figured out how to draw things into the workspace. Squeak calls these Morphs, presumably because the framework is called Morphic. I can do basic things like change their colour, add text into them, put other UI thingies into them and so on. Looking through the documentation though I'm not convinced that this is low level enough since I need to be able to draw individual pixels. I need something like an OpenGL canvas.

blackimage.png

After a bit of playing around I've got something that renders into an image. Like another hello world I suppose :).

RTCRenderer»initialize
    form := Form extent: 800@600 depth: 32.
    form fillBlack.
    canvas := FormCanvas on: form.
    image := ImageMorph new.
    image image: form.
    image position: 30@30.
    image openInWorld.

I'm under no illusion that rendering code is inherently procedural, so I expect that I'll be wrangling a few bulky methods sooner or later. I've already moved the image rendering out of the initialize method though. And I changed openInWorld to openInHand, which basically puts the image under my cursor in drag-and-drop mode so I can place it where I like.

RTCRenderer»display
    "Renders the form/canvas to an image morph in the world."
    | morph |

    morph := ImageMorph new.
    morph image: form;
          position: 30@30;
          openInHand.

I did have some trouble getting to this point. Some of the examples I found essentially drew the buffer straight onto the workspace. There's some situation where that is required (as it is when you run games in fullscreen mode and they take over the entire display instead of going through the windowing system), but for me it meant that the 'image' would be destroyed by dragging some other UI over it. It's like accessing or writing over memory you don't own. The extra step to make a 'morph' basically turned this into a self-contained canvas that I can play with more safely.

Drawing pixels

The book's moved on to drawing individual pixels now. This is normally the point where I'd give up on testing and just start eyeballing shit, but I'm interested to see if I can get these tests to pass.

The test case

The Ray Tracer Challenge book provides test cases in the form of BDD specs, using Gherkin-style syntax. This is maybe one of the one situations where BDD-style specs work well, because the author of the book wrote them to describe, well, the behaviour of the things you need to implement. Usually when someone gets the idea of setting up, say, Cucumber, they skip that step where someone in product actually writes up the specs to help disambiguate requirements, and so it falls onto the programmer to write both the Cukes and also the test cases themselves. No one outside of engineering actually bothers to read these, because they're stored alongside the code.

And I digress… I've converted the spec in the book to a little test case here. It obviously fails.

RTCRendererTest»testWritePixelAt
    | renderer color point |

    renderer := RTCRenderer new.
    color := RTCColor new r: 1 g: 0 b: 0.
    point := RTCPoint new x: 2 y: 3 z: 0.

    renderer drawPixelAtPoint: point withColor: color.

    self assert: color equals: (renderer pixelAt: point).

I've made some up-front decisions on the interface here. Seems sensible enough I think.

The smalltalk (Squeak) environment is actually really nice for this. Because you're only seeing one method at a time, and because the structure of the method requires you to write document and declare your local variables up front, you can structure your tests in such a way that you only need to read the first few lines to get a feel for what will happen next.

These tests are all super small as a result.

The implementation

Based on the test I created, I have a good idea of what I need to do. When I made the RTCRenderer class I stored a FormCanvas context as an instance variable, which is the thing I will do all of my drawing on. So, I just need to poke around the browser to see what I can do with one of these canvases.

canvasform.png

I wasn't sure what exactly to look for, by name at least, but I need a way to draw a pixel of a given colour onto a canvas and I need a way to find the colour of a given pixel. So, one write operation and one read operation.

For drawing, it looks like I can call point:color: on the canvas object but I'll need to convert my 3D point to a 2D one (note to self: can I drop the RTC prefixes and refer to my version of Point as 3DPoint?), and I'll need to convert my home-made Color object too as the built-in one does lots of things my version can't. No biggie.

RTCRenderer»drawPixelAtPoint: point withColor: color
    "Draws a pixel at the x and y coordinates of point with the given color."

    canvas point: (point x)@(point y) color: color asColor.

I have a feeling that most of these methods I add will be simple wrappers over what Smalltalk already offers.

Anyway, that's one part of the test done, but I don't have an easy way to check that what I did is correct besides rendering it, which is awkward. How do I find the value of a pixel on my canvas?

Ten minutes later…

The canvas doesn't have a way to do this that I can tell, but the implementation of Canvas»point:color: manipulates an internal Form object. Objects all the way down. That form object defines colorAt:put: and, just as I thought, it means there is a colorAt method too.

RTCRenderer»pixelAt: point
    "Returns the colour of the pixel at point"
    | color |

    color := canvas form colorAt: point. "...duck typing, yay"
    ^ RTCColor new r: (color red) g: (color green) b: (color blue).

Test has just gone from red to green. Woohoo!

Writing to disk

The next step of the book talks about writing the image to disk. It talks about writing the contents of the canvas to PPM (Portable Pixmap) format.

Honestly? I don't wanna do that when I already have the tools to create a PNG or a JPEG from this canvas. The PPM format is quite literally a space separated list of RGB values for pixels, with some metadata to define the resolution of the image and how many colours are supported.

Imma just make a PNG instead since this is a distraction from the main challenge.

RTCRenderer»exportPNG: filename
  "Export the canvas to PNG for your viewing pleasure."
   canvas form writePNGfileNamed: filename

Console Cannons v2

I should have enough here to take the console cannon example from yesterday and render an image instead of writing values to the transcript.

Hopefully this script should be enough.

p := RTCProjectile
        withPosition: (RTCTuple asPoint x: 0 y: 1 z: 0)
        andVelocity: ((RTCTuple asVector x: 1 y: 1.8 z: 0) normalize) * 11.25.

e := RTCEnvironment
        withWind: (RTCTuple asVector x: 0 y: -0.1 z: 0)
         andGravity:  (RTCTuple asVector x: -0.01 y: 0 z: 0).

t := RTCTicker new.

r := RTCRenderer new.

i := 1.

[ p position y > 0 ] whileTrue: [
        p := t tickwithEnv: e andProj: p.
        r drawPixelAtPoint: (p position) withColor: (RTCColor new r: 0 g: 1 b: 0).
        i  := i + 1.
].

r writePNG: 'cannonsv2.png'.

And here's the result:

cannonsv2.png

Wow, not bad! It's close enough to the example in the book, the only difference is that I hard-coded the size of the canvas to 800x600 so the velocity of the projectile sends it out of the picture.

Luckily I'm not doing this in C or anything so I don't have to care about bounds checking, eh? ;)

Oh yeah, it's also upside down. I suppose I could just rotate the image in an editor but where's the fun in that? All I need to do is subtract the Y co-ordinate from the height of the canvas, so 600 - y really.

[ p position y > 0 ] whileTrue: [
        p := t tickwithEnv: e andProj: p.
        r drawPixelAtPoint: (p position x)@(600 - p position y)
          withColor: (RTCColor new r: 0 g: 1 b: 0).
        i  := i + 1.
].

There's probably a fancy vector-based way to do that but right now I don't know it. The results are in, though!

cannonsv2fix.png

Perfect!

Wrapping up for the day

And that actually marks the end of the chapter, so I'm gonna call it a day here. One big takeaway from today's adventure was that there isn't that much to be gained from turning to the internet for help. In fact, I think I might have googled something once, and I've spent less time referring to my two Smalltalk books.

I mean, they're still useful for reference but now I'm more familiar with Squeak, the immense discoverability of the environment is starting to take over. Not only that, but I'm already comfortable browsing for methods and then seeing what the docs and the implementations say. Smalltalk code, so far, is remarkably easy to follow. This actually feels more like my experience with Ruby now, where I would generally browse through Ruby's docs and the lists of methods to see if there was anything that would help me out (Enumerable is a classic example of this, easily one of the best bits of Ruby).

That said, matrices and matric transformations are on the menu tomorrow, so we're back to the mathemology again.

I think I said this last time but chances are I'll gloss over much of that, so I can get the foundational work out of the way and come back to the sexy graphical stuff.

Until tomorrow!

Day 5

Technically it's day 3 since I started over the weekend and spent 2 days just setting up. Anyway, I was supposed to take time off work and I'm treating this challenge like a day job.

I've got my mug of hot coffee (some brew from Kenya this time, I get a random packet every 2 weeks; always love a surprise) and I think I'll spend the morning playing more of Chrono Trigger.

I'll come back to the matrix stuff later on - I did have a look around and Smalltalk again has its own implementation of a Matrix. I'll go with the book and roll my own for now and then summarise the bits that I found interesting.

This is awkward

So, the built in Matrix class does a bunch of helpful things, but not quite enough. I could subclass it and add the extra bits in but I definitely want a better understanding of what I'm working with. I imagine it'll take most of the day to do this.

Today's agenda

Essentially I need to be able to:

  • Create a matrix, ideally from a multi-dimensional list for convenience.
  • Multiply two matrices by other matrices and tuples
  • Create an identity matrix (a matrix where all the diagonal values are 1)
  • Transpose them (as in, swap the rows and columns around)
  • Invert them, which means calculating determinants
  • Compute cofactors
  • Errr, manipulate minors? (this is what the book says, lol)
  • And do multiplication on inverted matrices, if that's somehow different to normal multiplication.

How hard can it be?

Syntax sugar

Smalltalk's way of creating a matrix appears to be to initialise one with certain dimensions, and then to expect you to iterate over your rows and columns by hand to set the values at certain positions. I'm too lazy for that, so I'll just generate one from a list of lists instead.

First, the tests.

RTCMatrix»testMatrixAccessAtPoint
    | matrix |

    matrix := RTCMatrix fromList: #(
        (1 2 3 4)
        (5.5 6.5 7.5 8.5)
        (9 10 11 12)
        (13.5 14.5 15.5 16.5)
    ).

    self assert: 1 equals: (matrix at: 0@0).
    self assert: 4 equals: (matrix at: 0@3).
    self assert: 5.5 equals: (matrix at: 1@0).
    self assert: 7.5 equals: (matrix at: 1@2).
    self assert: 11 equals: (matrix at: 2@2).
    self assert: 13.5 equals: (matrix at: 3@0).
    self assert: 15.5 equals: (matrix at: 3@2).

And some code to make it work. RTCMatrix»at is just a simple method that uses x as the row index and y as the column index and digs through the stored list to get the value there. Array indices start at 1 in Smalltalk though, and my matrix is zero-indexed, so it has to account for that.

RTCMatrix»fromList: aList
    "Create a new matrix from a multi-dimensional list."

    | matrix numCols numRows |

    numRows := aList length.
    numCols := (aList at: 0) length.

    (aList allSatisfy: [ :elem | elem length = numCols ])
      ifFalse: [ ^ self error: 'Number of columns must all be equal' ].

    matrix := self new.
    matrix rows: numRows; columns: numCols; data: aList.

    ^ matrix.

I added in some basic error checking to prevent the creaton of wonky matrices.

I done fucked up

In attempting to implement matrix equality, I've accidentally defined an = class method that doesn't return anything. Squeak emphatically does not like this, so now I have to figure out how to actually undo the change when I can no longer actually get to the broken code.

Oops!

… after some fiddling around I was able to find the method in the changeset browser. This seems to track the things I've done throughout the project although it's not connected to git or anything.

changeset.png

Unfortunately I clicked 'remove from changeset' instead of 'delete change', which meant I hadn't fixed the problem. Eventually I figured out how to do it programmatically inside a workspace.

RTCMatrix class removeSelector: #=.

Crisis averted. And at least I know how to recover from a failure without throwing everything out.

What did I get myself into?

I gotta admit that algorithmic stuff isn't my strong suit.

matrixmultiply.png

It took me more time than I could care to imagine to be able to multiply two matrices together. Part of the problem was that the example in the ray tracing book had basically hard-coded the algorithm to a fixed-size matrix, because as far as the book was concerned I wouldn't be multiplying matrices of any other kind.

I wanted to do this right though and make a general solution. I don't think this is the most elegant way since it contains three nested loops and then a fourth iteration. That said, for a data structure that will at most contain 16 elements (for a 4x4 matrix) it's not exactly a big deal.

RTCMatrix»* aMatrix
    "Answer with this matrix multiplied by the other matrix."
    | matrix |

    matrix := RTCMatrix fill: rows@columns.

    (0 to: rows - 1) do: [:rowNum | "loop 1"
        (0 to: columns - 1) do: [:colNum | "loop 2"
            | value |

            value := ((self rowAt: rowNum)
                collectWithIndex: "loop 3"
                    [ :rowVal :i | rowVal * (aMatrix at: (i - 1)@colNum) ])
                sum. "loop 4"

            matrix at: rowNum@colNum put: value.
            ]
        ].

        ^ matrix.

Of course, forcing zero-based indexing into a language that doesn't do it is also painful, but I'd rather handle that in my interfaces instead of mentally subtracting in every example the book gives.

Calling it a day

Hopefully the remainder of the section isn't too awkward but I think this might take a while longer as I'm in unfamiliar territory now. Multiplying by a tuple should be easy enough since a tuple in my case will be a 4x1 matrix.

In any case, I think I'll deal with transposing, inverting, etc. tomorrow. That was surprisingly exhausting in spite of how rewarding it felt to get this far.

Day 5.5

Sooo…. I figured out how to get git working. That's a little bit different too but it's pretty consistent with how Squeak works. I'll have to learn how to make good commits with it since it's all based on a Smalltalk implementation of git and you basically don't (or can't, even) work with this from a terminal.

git.png

I'll just drop the repo here (https://git.sr.ht/~mrlee/RayTracerChallenge) and throw in a footnote so I can reference it again.5

Day 6

Been doing more matrix operations so far today. I've hit the wall once or twice just because of what feels like a lack of composition. For example, I can doWithIndex and collectWithIndex but there isn't a selectWithIndex or whatever. It's just a nitpick but since there isn't a generic enumerable thing in Smalltalk (more a variety of them that you have to convert between), I can't do the kind of things I'd get away with in Ruby, for example, chaining an enumerable method with with_index.

It's made things like calculating a submatrix a bit awkward but I'm probably overthinking it too, and of course I've only been working with Smalltalk for half a week and not the decade I've spent with Ruby.

Enumerate collections for great good!

worldpeace.png

This is exactly the kind of message I'm looking for when I want to split an array into chunks!

Creating sub-matrices

The ray tracer book completely glosses over this task: "there's no magic here, and really, no math."

To create a submatrix, you slice out a chosen row and column to get a new, smaller matrix. So, a 4x4 matrix becomes a 3x3 matrix, and a 3x2 matrix becomes a 2x1 matrix.

submatrix.jpg

Because I'm storing my matrix as a two-dimensional array ([[1, 1], [2, 2]...]), it took a bit of finesse to remove these items. This code passes my tests but I don't feel particularly proud of it, and there is clear room to improve.

Mainly I broke it down into steps so I could understand the process.

RTCMatrix»sub: point
    "Answers with a new matrix excluding the row and column represented by point."
    | collection list |

    collection := data concatenation asOrderedCollection.

    "Null out the row from the matrix"
    1 + (point x * rows) to: (point x * rows) + rows
        do: [ :index | collection at: index put: nil ].

    "Null out the column from the matrix"
    point y + 1 to: collection size by: rows
        do: [ :index | collection at: index put: nil ].

    "Remove the null values"
    collection removeAllSuchThat: #isNil.

    "Group back into nested list"
    list := (1 to: collection size by: rows - 1)
        collect: [ :row |
           collection collect: #yourself from: row to: row + (rows - 1) - 1].

    ^RTCMatrix fromList: list.

Two steps of that process involve looping over a range and setting a value at an index to nil. I could combine those into one and then loop over it once:

"Null out the rows and columns from the matrix"
(1 + (point x * rows) to: (point x * rows) + rows),
(point y + 1 to: collection size by: rows)
    do: [ :index | collection at: index put: nil ].

The reason I have to null the values out and then remove them is because modifying a collection while iterating over it is undefined behaviour. I could do this in a pure, immutable way, but it's much ado about nothing since I'm manipulating a temporary data structure inside a method.

This bit, however, is still a bit nasty:

"Group back into nested list"
list := (1 to: collection size by: rows - 1)
    collect: [ :row |
       collection collect: #yourself from: row to: row + (rows - 1) - 1].

Thinking about optimisation

The Smalltalk implementation of a matrix maintains a flat array which in this case is easier to work with. I didn't anticipate any of this so I chose my data structure because it's easy to access a value (matrix[row][column] or matrix[row, column]), but the trade-off is evident when it requires manipulation. To start with, what I could have solved with some basic arithmetic to index into a flat array has turned into a nightmare of nested iteration.

For example, take the following 4x4 matrix:

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

My data structure tries to mimic the shape of this, so I have a list that contains four other lists, and those four lists contain four values each. I'll write this in Ruby for simplicity.

# Identity matrix
matrix = [
  [1, 0, 0, 0], # row 1, cols 1 to 4
  [0, 1, 0, 0], # row 2, cols 1 to 4
  [0, 0, 1, 0], # row 3, cols 1 to 4
  [0, 0, 0, 1], # row 4, cols 1 to 4
]

It's super easy to grab a single row out of this, if I want the third row then I just index into the top-level list (remembering it's zero-indexed): matrix[2]. If I want a full column, however, I would have to loop over each row.

row_3 = matrix[2] #=> [0, 0, 1, 0]
column_1 = matrix.dig(0) #=> [1, 0, 0, 0]

I probably should have used Go as an example or something, Ruby makes this too easy lol. If I wanted to get all the values on the diagonal (so, all of the 1 values), I would do something like this:

diagonal = (0...matrix.size).map { |n| matrix.dig(n, n) }
# => [1, 1, 1, 1]

That really isn't so bad when you look at it in isolation, especially in a language that has nice ways to deal with iterable data structures. It might be more difficult when trying to render a large scene though because there could be thousands of these matrices flying around. I mean, for every 4x4 matrix I create, I'm allocating 5 arrays.

Matrices, Harry Style(s)

Because he's from One Dimension innit. I'll see myself out…

Instead of the above structure, then, I could have it flat (or one-dimensional). The same identity matrix would therefore be represented thus, formatted for readability:

matrix = [
  1, 0, 0, 0,
  0, 1, 0, 0,
  0, 0, 1, 0,
  0, 0, 0, 1,
]

Accessing an element of a matrix this way requires some arithmetic. You can do this in your head, or on paper. For my 4x4 matrix above, I know it has 4 rows and 4 columns.

r - - -  r - - -  r - - -  r - - -
c c c c  c c c c  c c c c  c c c c
1 0 0 0  0 1 0 0  0 0 1 0  0 0 0 1

The number of values (or cells) in a matrix is found by multiplying the number of rows by the number of columns: rows x cols = 4 x 4 = 16.

Therefore, to get the first column of a row, you multiply that number by the number of rows.

rows = 4
row_0_col_0 = matrix[0 * cols] #=> 1
row_1_col_0 = matrix[1 * cols] #=> 0
row_2_col_0 = matrix[2 * cols] #=> 0
row_3_col_0 = matrix[3 * cols] #=> 0

If you want the row instead, you need to find where it ends too. You already have the start of the row from above, so to get the end you simply have to add the number of columns to it, subtracting one because you already have the first value: row_0_col_0 + (num_cols - 1) = 0 + 4 - 1 = 3. Put those two together and you can slice your row out.

rows = 4
columns = 4

# using `...` in Ruby would do the same as `-1` but that's Ruby...
row_0 = matrix[(0 * rows)..(0 * rows + columns - 1)]
#=> [1, 0, 0, 0]

It's a similar affair for getting columns. A column is the /n/th cell from every row, and since you know how to find both the start and an end of a row, you can tweak the formula to get something in between.

col_3 = (0...rows).map { |n| matrix[n * rows + 2] }
#=> [0, 0, 1, 0]

You can't avoid a loop there but it's much tighter than it was before.

Anyway, that's the bare minimum needed to work with a matrix that way. It's wonderfully elegant.

That said, I'm not doing any premature refactoring as a rule so I'm not changing this now: you gotta deal with the hand that falls as it may, so to speak.

Skeuomorphic data

So basically what I started with was a skeumorphism of a grid. I made a data structure that, when you look at it, has the appearance of a grid. It's a leaky abstraction and it causes more trouble than it's worth.

Back on task

So, where was I? I've wasted most of the day implementing a single. fucking. function. I need to finish off my determinants and matrix minors.

Not a chance I could have done this in a weekend (like that other ray tracer challenge) unless I already knew how to do the damn thing.

See ya tomorrow. I'll leave you with a screenshot of my workspace after learning all this.

workspace.png

Day 7

A whole seven days! Time does indeed fly like a banana.

These matrix operations have been a real time sink and, in all honesty, the book hasn't been as helpful as it could have been here. For example, when calculating the determinant of a matrix the Ray Tracer Challenge guides you through calculating the determinant of a 2x2 matrix first, and then attempts to expand it outwards so you can do it for 3x3 matrices and 4x4 matrices, and so on. In doing so it starts talking about how you calculate cofactors and minors, and you can make tests pass for those. Finally, it shows a rough way to calculate the determinent which involves calculating the cofactor of a smaller matrix until you're left with a 2x2 one.

Circular logic

The problem here is that the definition becomes circular and while it pays lip service to solving this problem via recursion, the steps you take to get to that point don't lend to an intuitive solution. For example, to get the determinant of a larger matrix you need to get the cofactor of a submatrix, which involves getting the determinant of that matrix which involves getting the subfactor of another submatrix, and so on and so forth.

Personally I feel like it had the effect of over-complicating the explanation. In the end I took to the internet to see what an algorithm for calculating a determinant looked like.

Going recursive

Those examples are largely recursive, which is fine. Just have to see if that kind of solution goes well in Smalltalk.

I've ended up with this, now. It passes my tests so I'm happy.

RTCMatrix»determinant
  "Answer with the determinant of the matrix."
  | sign det |

  det := 0.
  sign := 1.

  "Base case - return the value for a 1x1 matrix."
  (self size = 1) ifTrue: [ ^ self at: 0@0 ].

  "Calculate the determinant of every submatrix."
  (0 to: self size - 1) do: [ :n |
      det  := det + (sign * ((self at: 0@n) * (self sub: 0@n) determinant)).
      sign :=  sign negated
  ].

  ^ det.

To be honest I'm not convinced I would have reached this solution based solely on the guidance offered by the book. I just want to get to the action at this point because it's a bit boring hitting wall after wall and I don't want to give up.

I'll probably find a better book that can explain the maths here though. Last time I did anything relating to linear algebra was almost 20 years ago at sixth-form.

Inversion and cofactor matrices

Only two more to go and then the chapter is done. There is still a second chapter that relates to matrix transformations though, which I hope I'll have a better grasp off because of the familiarity of it when making little games.

I think I better understand the stuff from before now, in terms of calculating a cofactor. I was doing that inline in the implementation of determinant, so I was able to extract out that logic to get the cofactor.

And the book is starting to make sense now I'm able to grasp this, particularly because it's a lot easier for me to reason with the generalised solution as opposed to trying to handle smaller matrices, then bigger ones.

"det := det + (sign * ((self at: 0@n) * (self sub: 0@n) determinant))."

cofactor := sign * (self sub: 0@n) determinant.

I pulled that out into a method of its own because I need to reuse it here:

RTCMatrix»inverse
    "Answers with the inverse of the current matrix."

    | matrix |

    self invertible or: [ self error: 'Matrix is not invertible' ].

    matrix := self class size: self size.

    0 to: rows - 1 do: [ :row |
        0 to: columns - 1 do: [ :col |
             matrix at: col@row put: (self cofactor: row@col) / determinant ]].

    ^ matrix.

That was quite a bit easier to do, thankfully. If I want a cofactor matrix then I can do more or less the same as this but without the bit where I divide the cofactor by the determinant.

One problem is that I'll be dealing with floating point numbers with this, and quite often. Smalltalk itself offers #closeTo as a selector on floats, which is used to test equality with some margin for error. With that in mind, I'm trying to avoid hard-coding floats in the code and the tests in favour of using Smalltalk's Fraction object. So, rather than testing for a value like 0.21804511278195488, I'll just store it as (29/133) and handle any conversion at rendering time.

Quick recap

Given my earlier frustration with trying to grasp this, I have a better understanding now.

  • A determinant is calculated in terms of the cofactors of a single row or column in the matrix.
  • A cofactor is calculated in terms of the minor of a cell in the matrix (or an element).
  • A minor is the determinant of the submatrix at that row and column.

So yeah I can see how this is naturally recursive now. It's a bit like this:

1 0 0 0  -> 1 0 0  -> 1 0  -> 1 (row 1 col 0)
0 1 0 0     0 1 0     0 1
0 0 1 0     0 0 1
0 0 0 1                         (repeat for each column)

I must have got turned around somewhere with the book, but re-reading the chapter shows me that all the info was there.

Matrix transformations

Just one more step to go and I'm done with this stuff! I need to add operations to translate, rotate, scale and shear. I think I'll do some of that tonight and then wrap up tomorrow.

Knowing what I know now, I think that if I were to do this challenge again, I would breeze through this stuff much more quickly. Even if I needed to implement matrix functions from scratch to do this again, it wouldn't take as long now that I've actually learned how to do it.

The chapter after that goes back to rendering. I imagine it'll take another week to finish that up but since I'll be back at work again I won't have as much time to do this.

Once I'm finished I think I'll take this entire diary and rejig it into something more akin to a small book. It'll take a bit of editing and cleaning up but it could be worth it.

Day 8

I couldn't resist, so I did some refactoring today based on what I learned over the past week. My matrix implementation is now based on a flat array and I do some arithmologics to access rows, columns and cells within it. Didn't need to change any of the tests except for how I actually created the instances - they all passed without changing the actual assertions.

Deriving a tuple from a matrix

I realised I could also refactor my tuple code, so that a tuple would really be a 1x4 matrix. In fact, if I want to do transformations then it's in my best interest to do this otherwise I'll have to litter the code with matrix conversions. And since a matrix is simply a flat array under the hood now, it means I can share some logic.

As with the other refactoring, the test suite covered my ass well enough that changing the underlying structure was fairly trivial.

For example, a lot of the operations are now basic operations on arrays which means I can lean on Smalltalk's standard library. The dot product of two tuples now looks like this:

RTCVector»dot: other
    "Calculate the dot product of this vector and another vector"
    ^(self data * other data) sum

Getting on with it

The yak shaving is out of the way so now I should be able to proceed more easily.

That said, this is also the point where I should think about the messages I want to pass rather than trying to copy the API presented by the book. For example, it makes more sense for me to send a message called `translate` to a tuple, rather than overloading my multiplication operator. I can deal with the transform matrix internally.

RTCTupleTest»testTranslatePoint
    | pointA pointB expected |

    pointA := RTCPoint x: -3 y: 4 z: 5.
    pointB := RTCPoint x: 5 y: -3 z: 2.

    expected := RTCPoint x: 2 y: 1 z: 7.

    self assert: expected equals: (pointA translate: pointB).

Given the above test, I can satisfy it with the following implementation:

RTCTuple»translate: to
    "Translate the tuple to the given point."
    | transform |

    transform := RTCMatrix translation: to.

    ^self class fromList:       
        ((0 to: rows - 1) collect: [ :row |
            ((transform rowAt: row) * self data) sum ]).

Knowing this, I can probably make my multiplication operator do the heavy lifting, as I'll be re-using this quite often when implementing various transforms. The multiplication stays the same but the transform matrix is different each time.

RTCMatrix»* other
  "Answer with this matrix multiplied by the other matrix."     
  | matrix |

  "If other is a tuple (point / vector), calculate a new point/vector."
  (other isKindOf: RTCTuple) ifTrue: [
      ^ other class fromList: ((0 to: other rows - 1) collect: [ :row |
          ((self rowAt: row) * other data) sum ])].
  " ... rest of method"

The rest of that is still pretty ugly, since I hacked it together about a week ago and it was designed around the old nested data structure. It still works as intended, so I've not changed it yet.

Inverted transformation matrices

The book mentions that using an inverted matrix has the effect of reversing the direction of the translation. I've been thinking about skipping this, but looking ahead it appears that I'll need it for other transformations. For example, an inverted translation is the same as translating by using a negated point (e.g. pointA * -pointB). However, that doesn't necessarily track for a scale transform because the equivalent will actually give you a reflection instead.

Scaling, reflecting, rotating

Thanks to the refactoring, all I need to do to implement this is create some more transformation matrices. Fundamentally all I'm doing with these is taking an identity matrix and then setting certain values within it.

For example, translating looks like this, where x, y, and z correspond to the destination point:

1 0 0 x
0 1 0 y
0 0 1 z
0 0 0 1

And scaling looks like this:

x 0 0 0
0 y 0 0
0 0 z 0
0 0 0 1

Multiply this with the point or vector you want to mess with and you will get the desired effect. I'm just setting these up with basic class methods on my matrix class.

(class)RTCMatrix»translation: point
    "Answer with a transformation matrix that can perform translate"
    | matrix |

    matrix := self identity: 4.

    matrix at: 0@3 put: point x;
           at: 1@3 put: point y;
           at: 2@3 put: point z.

    ^ matrix.

Same deal for the other ones really. Once they're set up, you just multiply them by a point or vector for the intended result.

Finishing for the day

A good summary of changes done today can be found on the git repo I've got set up6.

I still have to deal with rotation and shearing, as well as allowing for chaining transformations for efficiency's sake. I know what I'm doing there now though.

Next update tomorrow will focus on the next chapter, which takes me back to rendering.

Day 8.5

I thought I'd do matrix rotations while I'm here.

Rotating matrices

RTCMatrix»rotating: point
    "Calculate a 3 dimensional rotation matrix given point."
    | rotateX rotateY rotateZ |

    rotateX := (self identity: 4)
        at: 1@1 put: point x degreesToRadians cos;
        at: 1@2 put: point x degreesToRadians sin negated;
        at: 2@1 put: point x degreesToRadians sin;
        at: 2@2 put: point x degreesToRadians cos.

    rotateY := (self identity: 4)
        at: 0@0 put: point y degreesToRadians cos;
        at: 0@2 put: point y degreesToRadians sin;
        at: 2@0 put: point y degreesToRadians sin negated;
        at: 2@2 put: point y degreesToRadians cos.

    rotateZ := (self identity: 4)
        at: 0@0 put: point z degreesToRadians cos;
        at: 0@1 put: point z degreesToRadians sin negated;
        at: 1@0 put: point z degreesToRadians sin;
        at: 1@1 put: point z degreesToRadians cos.

    ^ rotateX * rotateY * rotateZ.

The book implements this as three separate functions but since you can chain transformations by multiplication, I thought I'd do it in one shot.

For example, to rotate along the X axis I can call #rotate: (RTCPoint x: 45 y: 0 z: 0), where the value is the number of degrees to rotate.

The reason this works is basically because the sine of 0 is zero, but the cosine of 0 is 1. The transformation matrices for each axis of rotation use the cosine value along the diagonal, and since it started with an identity matrix the result of rotating 0 degrees x, y, or z is just another identity.

Interestingly enough, this doesn't work with scaling. Scaling a matrix by 0 in all directions is as good as removing it, whereas scaling by 1 in all directions is equivalent to identity.

Testing this shit

Unfortunately this is a bit more awkward because I'm not getting fractional objects back this time, just straight floats. I've not figured that one out just yet.

I also broke my environment by printing out a line in one of the array comparison methods. Self DOS, yay!

I'll figure out a way but I'll probs have to do it the ugly way by looping through the matrix and doing inexact float comparisons and more strict comparisons for everything else.

The main problem is that you can't just compare the full list in linear fashion if you're dealing with a non-square matrix, because a 2x3 and 3x2 matrix will look different despite containing the exact same data underneath.

So, I've ended up with a looser equality function that does the job:

RTCMatrix»hasEqualElements: other
    "Answer if this matrix is like the other matrix."

    (rows = other rows) ifFalse: [ ^ false ].
    (columns = other columns) ifFalse: [ ^ false ].

    0 to: rows - 1 do: [ : row |
        0 to: columns - 1 do: [ : col | 
            ((self at: row@col) closeTo: (other at: row@col))
                ifFalse: [ ^ false ]]].

    ^ true

My = function delegates to this one. closeTo basically compares numbers within a value known as epsilon, which is something like 0.00001. It allows you to compare floats whena direct equality would cause a failure if the number was off by one at the 12th decimal place.

Day 9

Just a quick one today. I finished off that last chapter and did the rendering challenge.

fakeclock.png

Works exactly as the example said it would! A nice way to show that what I've got so far is for a purpose, but it definitely took more effort than I imagined to get to this point.

The code for it is pretty simple, but I tripped up at first because I decided that I'd pass degrees of rotation into my #rotate: method and then convert it to radians internally, because degrees are nice and simple to reason with. Of course, the code examples do the conversion to radians up front and I forgot that.

Here it is, anyway…

r := RTCRenderer new.

center := 400.

1 to: 12 do: [ :h |
    p := RTCPoint x: 0 y: 0 z: 1. 
    deg := (360 / 12) * h.

    p := p rotate: (RTCPoint x: 0 y: deg z: 0 ).

    p := p scale: (RTCPoint x: 300 y: 1 z: 300).

    p := p translate: (RTCPoint x: center y: 0 z: center ).

    r drawPixelAtPoint: (p x@p z) withColor: (RTCColor r: 255 g: 0 b: 0)
].

r writePNG: 'fakeclock.png'.

I haven't done anything with chained or fluent interfaces so far but that's partly because I see it more of an API design challenge than a ray tracing one.

Also, since all of the code is immutable and changes are made by creating new objects, I think I'd have to build a special class for chaining operations, such that I had something that could hold state. The cascading operator would make this super easy.

Chapter 5 is all about ray-sphere intersections so things should start to get more interesting now, if they weren't already interesting.

Footnotes: