I have been writing a program for a couple of months now. It started as something else but now it’s turning into a game.

First: Video time:

When I used to do 3D modeling and animation, I remember being fascinated when I stumbled upon Take Igarashi’s T.E.D.D.Y. Years later, after I decided I wanted to be a programmer, I attempted to write an implementation. It wasn’t that long ago, but I didn’t have the programming chops to pull it off and I failed miserably.

My second attempt started in November of 2011; about two months before my internship at Google (of which I intend to write a huge blogpost when I know what points I can convey without burning any bridges, especially since I intend to compare my experiences at both Microsoft and Google). These series of posts will be solely a devlog on the most fun project I have ever worked on.

The Idea.

I wanted to make a “Modeler for the Masses” based on Teddy’s paper (freely available and excelent). I don’t even know if Takeo’s paper was the first but I later found out that this idea has already been explored; it is called Sketch Modeling and I assume that it hasn’t been very succesful. I haven’t looked into it further.

My idea is to bring auto 3d mesh generation from 2d shapes to the tablet and smartphone as a core game mechanic. I didn’t want to make a game, especially since I intend to sell this, but this is what I want to work on so this is what I’m working on. It’s too damn fun.

The initial, very mutable, idea is a terraforming sandbox game. You start with nothing but a horizon (with maybe an ocean). And you create your world using some “elements” like cloud, earth or wood. Think of inception’s limbo. Unconstructed dream space.

But before I speak of the fun bits, I want to say something about the money part.

First off, I chose the name for my “studio” (aka me): devolve_inc. It sounded cool. Bought a domain and everything. I even attempted to make a website but I soon realized I was just stroking my ego…

I bought “The Lean Startup”. A really hip business book. I’m not a business guy but I have to become one since this is a one man operation (even though I tried my best to recruit friends). I liked the idea of extremely fast iteration. Even though it is a short book I feel like the main ideas, like the concepts of pivoting and learning could be put in a smaller package. At first I didn’t think this development method could be applied to games. Games, to me, were works of art done in seclusion by a team or individual and then released to a violent environment where it might not succeed. That is why I was afraid of working on a game for profit. Then I thought of Minecraft. Minecraft was developed in an open an continuous fashion. The user base was huge by the time v1.0 was available. Even now I think Minecraft is always changing (I quit after I actually forgot to eat for a whole day while playing it and realized it would eventually kill me). I think games without stories can use the methods in the book easily, not as much as a web app, but easy enough on an environment like the android market, where apps update automatically. This is why I chose Android as my first target: no app review process so I can launch an unfinished product and iterate with feedback. I also chose C++ as the implementation language; I didn’t want to at first, but it really is the only sensible choice for this kind of project. Python + Kivy was another consideration but speed was a concern. A couple days ago I met a game programmer on Google+ who is rewriting the code of his hobby game from Java to C++ because of performance problems. I don’t want that to happen to me. C++ is also the language I know best so it’s not so bad. I have a love-hate relationship with C++. Right now I’m tending to “Love” so I won’t rant. Eventually I will hate it again and I will dedicate a post to C++ hatred. Like any long-term relationship, there are problems and it takes work to make it work.

The fun stuff.

Mesh generation is almost done. It’s essentially finished but it doesn’t look like it because it is still an orthographic projection. I’m working on a 3D renderer right now. I debated with myself on using a middleware engine, but there were enough reasons against it that I chose to roll my own renderer:
*) Portability: I am targeting Android, iOS and development is being done on a linux box.
*) Requirements/Features: A third party engine might be used for a FPS or a Flight Simulator or anything else, the needs of my game are very basic. For instance, I don’t think I need fancy space subdivision data structures for the first version of the game. Also, the nature of the game calls for code that moves between Eye coordinates, World coordinates and Screen coordinates with ease. I feel more comfortable knowing that I have complete control.
*) Fun: It’s just fun. I’m on a self-imposed deadline but I am a hedonistic programmer.
OpenSceneGraph is still an option I haven’t ruled out in case that writing a custom scene manager and renderer proves too much of a burden.
I am using the Armadillo library for Matrix math but I have my own unnecessarily-optimized-with-SIMD-extensions classes for 2d and 3d vectors for the mesh generation code.

Mesh generation closely follows the Teddy paper; the paper could be more detailed on the mesh creation section. For example, searching for “Chordal Axis” got me topology and biology results and it wasn’t well defined in the paper as far as I recall.

The idea is to take a 2d stroke that is not self intersecting as an array of mostly-equidistant points, create a Delaunay triangulation and then subdivide it using a skeleton that is very easily derived from the triangulation (that’s the chordal axis).
My implementation is a simple incremental Delaunay algorithm. Theoretically this algorithm is O(n^2) but in this case, the guarantee that contiguous points are next to each other makes point location really really efficient (Thanks to my friend Jason Bandlow for realizing this; I was too dumb to see it). Thanks to practically-constant point location, on the average case the algorithm is O(n). This is awesome. Without excessive optimization my algorithm’s bottleneck is now the STL’s hash table implementation. I can optimize further but I won’t until there is a real need.

The subdivision process consists of adding points along the inner edges of the triangulation. The z-values of the new points are calculated with an ellipse function that depends on the length of the edge. This means that wider parts of the shape become fatter and thight parts become thinner.

I didn’t follow Teddy’s paper to the letter. I am not subdividing manually. After knowing the location the new points, the algorithm just retriangulates with the original boundary points and the new interior points. This is all 2d, but the creation keeps a height map that is used to create a 3d-mesh really quickly after re-triangulating.

The subdivision is not always clean. There are some inputs it likes and some that it really hates. Sometimes there are triangles that are too big, and sometimes some triangles are too small. Sometimes both. I know how to make it better; in fact, it’s in the design and it has not been implemented. Right now the subdivision is good enough that I believe the end-user won’t notice if the triangulation is not beautiful or uniform. If the difference in triangle size causes rasterization artifacts then I will go ahead and implement the mesh-refining part of the generation algorithm.

This is what I have. I have a long way to go but I have some very smart people that I might convince to help me =)