I’ve been rendering surfaces for a few years now, and have even written a couple of demos around the topic. An arbitrary surface plotter was a natural evolution: enter an equation and see the result in real time.

I brought this Android app to a working demo, then decided I didn’t have a use-case or story for it, and decided to open it instead. The source code is on GitHub, and you may do whatever you like with it.

The bulk of the graphics code comes from my previous open-source release, 4est. I copied over the 3D toolkit, which includes an implementation of the marching-cubes algorithm for rendering arbitrary surfaces. The movement code has been simplified and folded into the renderer and surface view classes to allow the user to scroll “around” the rendered surface. The surface mapper converts a function of the form f(x, y, z) into a set of triangles that represent the surface, and draws them.

The important question: how to generate that f(x, y, z) function from user input?

Well, I knew I’d need a parser–or rather, a parser generator. I once had to create a compiler for a C-like scripting language, and the experience taught me one essential lesson. Never write a parser. For all but the simplest inputs, it’s easier to write a grammar that describes your symbols and syntax, then use a third-party tool to generate a parser from that grammar.

Back when I was writing C, I used the flex lexical analyzer (transforms an input stream into a sequence of defined tokens) and the bison parser generator. For Java, I discovered Antlr, which combines both of these functions into one tool. If you’re already familiar with context-free grammars, the syntax should be familiar enough, and if not, there are plenty of examples (and the documentation, though not free, is inexpensive).

With Antlr, I developed a grammar that could handle expressions of the form f(x, y, z)=g(x, y, z), and a compiler to interpret the output of the parser. At this point, all I needed was a way to actually solve the calculation for a given point (x, y, z).

My initial instinct was to create an actual Java (or rather, Dalvik) bytecode compiler, so the expression code would run with as little overhead as possible. I found the DexMaker library, which can generate Android code at run-time. Though I found DexMaker easy to use, and was able to produce a working expression compiler without much trouble, invoking the generated code created a significant problem.

Any code generated via this library has to be called using the reflection API, which requires creation of internal objects, and thus incurs overhead. The marching cubes algorithm must test the expression at several points to generate each triangle, and many thousands of triangles must be generated to produce enough of a surface to observe. Multiply the object-creation overhead by a hundred thousand and it’s a major performance problem. The app was taking nearly a minute to render even simple surfaces.

I removed the DexMaker code and tried again, creating a simple virtual machine that could perform a few operations and transcendental functions on its internal registers and return the result. Of course, the most significant feature of this VM was that it didn’t create any objects on execution. With this, the app was able to render even complex surfaces in under a second.