Edmund Kapusniak

Here I present some of the software projects that I have worked on in my spare time. I hope that you find them inspirational, or useful, or both! I certainly learned a lot from creating them.

You can contact me.

OUYA Controller Driver for OSX

I like the OUYA controller. It's a Bluetooth device with an integrated touchpad. My Mac speaks Bluetooth, but unfortunately decided that the controller must be a mouse. And then got the analog stick and the mouse pointer inputs confused. Whoops!

So I spent a day or so delving into IOKit and writing a very simple driver. To my surprise just loading a driver other than the standard one seemed to fix the pointer jumping problem. To make sure, the driver reports the device as a gamepad instead of a mouse. It seems to have made my system happy - although the touchpad no longer moves the pointer.

Use at your own risk: OUYA Controller Driver

Monotonic Bezier Curves for Animation

Bézier curves are ubiquitous in computer graphics and computer animation. These curves are most naturally expressed in a parametric form. The problem with parametric curves is that it is difficult to perform certain queries on the curve that would be trivial if we had an analytical representation. This includes even conceptually very simple operations such as finding the curve point at a particular x or y coordinate.

It has always frustrated me that discussions of Bezier curves avoid giving exact solutions to these kinds of problems. The recommended approach is always to approximate the curve by recursive subdivision into some number of line segments. This might be the most pragmatic solution, but the original curve is only a cubic equation - surely it is not impossible for a computer to solve them exactly!

It turns out that cubic equations were solved around 500 years ago by Rennaisance mathematicians Niccolò Tartaglia, Gerolamo Cardano, and François Viéte. In the process they invented complex numbers. The general cubic formula is indeed very complicated, and you can see why recursive subdivision is the preferred alternative.

This paper is the result of my attempt to find an analytical solution for a problem involving a special case of cubic Bezier curves. Curves used for animation must be constrained so that there is only one valid curve point for each point in time. I worked out the specifics of these constraints, and I followed in the footsteps of those ancient mathematicians to derive a formula that gives the value of the curve parameter at a particular time.

Subsequent experience has shown that my intuition about the correct value of t was mistaken - my current approach here is to explicitly check which of the three possible t values lie on the curve - but it makes a pretty graph.

Likely to be obvious to proper mathematicians but perhaps it will be of use to fellow apprentice number-crunchers:

Apollua

In the managed world of Xbox Live Indie Games, although it was possible to compile C to pure MSIL, it was not officially supported. Lacking an official C# version of Lua, and being somewhat obsessed with the implementation of programming languages, I decided to write my own version in C#.

The virtual machine supports the same bytecode format as the standard Lua distribution. Dynamic values are manipulated as instances of the LuaValue class. This is probably sub-optimal, but greatly simplifies the implementation of the interpreter. Benchmarking against some mocked-up operations using value types instead did hint that the performance impact was not as great as I had feared - you need some kind of virtual dispatch, and switching on the type of the value is not much different to calling a virtual function.

The frontend is a hand-written recursive descent parser that I hope shows the syntax of the language in a very clear way. Unlike the C version of Lua, it builds a full AST in memory before traversing it to emit interpreter opcodes. It attempts to emit an optimal sequence of opcodes.

This project never did see use in an indie game, but it is released here under an MIT license in case others find it useful: svn co http://svn.birotanker.com/Apollua

GrammarC

This is a parser generator in the vein of bison or lemon. It was my attempt to meet the following goals:

  • Specify grammars in a natural, modular syntax.
  • Decouple the grammar specification from the application actions.
  • Support parsing of ambiguous grammars by generating a 'parse forest'.
  • Generate both parsers (context-free grammars) and lexers (regular grammars).

Parser generators generate a state machine which matches the productions of a grammar. At each state, the parser traverses the state machine by looking at the next token read from the input or the last production matched and following the edge corresponding to this symbol - which leads the parser to the next state. Yacc-descended parsers generally use an LR parsing technique where each symbol is shifted onto a stack as it is read. When the state machine reaches a reduce state, a grammar production has been matched. The symbols corresponding to the production are popped from the stack and replaced with a symbol representing the production.

One limitation of the LR approach is that for each reduce state we must know in advance exactly how many symbols to pop from the stack. We don't have any information about where productions began. You can see this in any LR grammar for a list - you have to write a recursive rule that appends to the list by repeatedly matching one symbol at a time. Ambiguities in LR grammars can also be difficult to understand and difficult to resolve, as mentally we tend to conceptualize grammars top-down and left-to-right rather than bottom-up and right-to-left.

In contrast, GrammarC generates left-corner (LC) parsers. In left-corner parsing we remember where each production began by inserting a push state wherever one production refers to another. When we push, we save the current state and begin matching the child production. Parsing proceeds similarly to LR, save that whenever we reach a reduce state we reduce all symbols since the last push rather than a fixed number of symbols. If a reduce matches the production that was pushed then we have accepted the production and we can resume matching the parent production from the saved state.

Using this technique we can more easily support productions containing repetition of symbols or optional symbols. Reduce states can more frequently be merged together as we do not need to keep states that match different numbers of symbols separate. In exchange, we must ensure that our grammar is free of conflicts where productions are pushed rather than solely where productions are reduced.

GrammarC's lexer generator is fairly standard, although I am quite proud of a rule whereby literal characters will be matched in preference to character ranges or wildcards. This allows natural specification of terminal character sequences without the need to worry about 'greedy matching'.

I am not sure how much practical use GrammarC is - the runtime library is quite bulky - but it is available here nonetheless under an MIT license: svn co http://svn.birotanker.com/Grammar

CppParser

Back in the dark days of 2006, parsing C++ source code was a tricky proposition. Disentangling GCC's frontend from the rest of the code was purposefully difficult and explicitly discouraged. Clang was only just peeking over the horizon. Elsa and Elkhound were impressive, but couldn't parse the MSVC headers.

However, Scott McPeak's achievement with Elsa demonstrated to me that it was possible for a lone developer to solve what had previously seemed to be an intractable problem. This was the motivation behind the development of GrammarC and of this, my own attempt to parse C++.

Times have moved on, but I have released the code under an MIT license to preserve it for posterity: svn co http://svn.birotanker.com/Cpp