Sector Director – An Exploration into Classic Graphics Programming

November 11, 2019

This is the third post in my series on the value of personal projects. Check out the first and second posts for context.

Sector Director

Sector Director is an on-going (as of writing) project to create my own 3D renderer for the 1993 game Doom. There is nothing terribly novel about this – tons of people have done this before. Doom is one of the most popular games of all time, after all. However, I was interested in classic graphics programming techniques and methods.

Exploring 90’s graphics techniques seemed like the least work-relevant personal project I’ve had, but it actually ended up being directly useful!

An Excuse to Investigate Parsing

Sector Director builds off some of the framework I had already created in Tiledriver, my previous personal project. Part of this involves parsing level data into an in-memory representation. This was a good excuse to take a deeper dive into the topic since I was not entirely happy with my parsing approach on Tiledriver.

Takeaways I learned:

  • Monadic Parser Combinators are a fairly modern approach to parsing that is extremely flexible and fairly easy to use. Although I didn’t end up using them in Sector Director, it would be my go-to for a first approach at a custom parser in the future.
  • Parser generator frameworks like ANTLR and Hime did not impress me. Setting up and optimizing them is fairly complicated.  I would only see myself using them in a very specific set of cases.
  • To get the ultimate in performance and flexibility, a custom hand-written parser is still the gold standard.

I was able to learn enough about parsing along the way to give a brown bag presentation at work and a presentation at a local meetup.

Rasterize Like It’s 1962

Sector Director starts from scratch and builds up drawing primitives from the basics of being able to draw pixel-by-pixel onto a canvas. Even fundamental things like drawing lines had to be implemented using classic techniques like Bresenham’s line algorithm (from 1962!) and Wu’s antialiased line drawing algorithm.

This actually ended up being useful for a work project!

Drawing 2D Paths

One of my work projects involved a display embedded in a vehicle that had to do a lot of 2D geospatial calculations. One subproblem that it dealt with was keeping track of where the machine had driven in a particular 2D area. It did this by keeping a large binary 2D map of the location (0 = not covered, 1 = covered). New vehicle paths would be drawn onto the map to add coverage. I should note that the machine covers a fairly wide area, so you should think of drawing coverage as using a wide marker, not a skinny pen 🙂.

The code we inherited used a custom drawing approach that initially seemed very dense. In graphics code it’s hard to avoid having a bunch of loops and cryptic variable names.  This unfortunately makes it very hard to follow most of the time.

However, closer inspection revealed that this was really just Bresenham’s algorithm combined with a simple area fill! Since I had seen it before, I was more comfortable that the code really was correct. The process of turning geometric shapes into a grid of pixel data is called rasterization. This was still something that people wrote custom code for in early 1990s games.

In case you’re curious, I did verify that using a custom rasterizer was faster than using the framework’s standard drawing methods. In fact, I even managed to optimize and clean up the path drawing a bit.

See, This Is Useful After All

Sector Director is still in progress so I’m not sure what other surprises it will have in store for me. It does highlight one of the best case outcomes – something you’re just doing for fun unexpectedly becomes relevant for a work project.

However, all of my personal projects have provided useful experience for me:

  • More experience with a framework
  • An excuse to try out a tool in a low-risk environment
  • A reason to do enough of a deep-dive to share it out with my colleagues and community in a talk

Keep hacking!