One month later, and we’re still working on the editor backend — it’s actually going really well, aside from the fact that it’s taking much longer than we anticipated!
As you may have noticed, this is a recurring theme with Robotology: our scheduling estimates are based on the known hardest task, however the actual effort required to complete a specific goal is inevitably determined by a task which was undiscovered during the planning phase.. resulting in a state of perpetual under-estimation. Frustratingly, it seems like the very nature of what we’re trying to do — developing new ideas for which there are no known or established solutions — results in us frequently running into unforeseen issues.
The editor is a perfect case-study of this phenomenon; re-reading our previous post, we seemed to be convinced that most of the hard work was done. Sadly, this turned out to be a bit optimistic. 😉
First, some background: the basis of the editor is a Doubly-Connected Edge List data structure, which is a lot like a 2-dimensional doubly-linked-list (lists being inherently 1-dimensional). The world is described as a 2D graph — a set of nodes connected by edges — and the DCEL is how we represent this graph. We then generate surface geometry by assigning a “thickness” to each halfedge in the DCEL, in essence inflating the graph to generate polygonal shapes.
This approach is similar to metaballs (not to be confused with meatballs!) except that while metaballs use points as the fundamental primative, we use lines; the result is that where metaballs produce smooth, rounded surfaces, we produce angular, faceted surfaces.
Getting back to our previous topic — why the editor backend is taking much longer than anticipated — we had anticipated that development of the DCEL would be the main task. We made sure to carefully plan our implementation, because we knew from experience in school that writing linked-lists is often trickier than you’d think — and not at all fun to debug! It took us a couple days to implement the basic DCEL and iron out all the kinks. We then tried to take the next logical step, which was using the DCEL to generate a set of polygonal shapes.. and it was here that our plan fell apart.
While DCELs themselves are fairly straightforward and well-documented, the way we’re (ab)using them is unorthodox — rather than making a graph which explicitly describes polygons (nodes and edges representing the vertices and line segments which define a set of polygons), our graph is treated as a “skeleton” which is then inflated to generate polygons. During planning (before the DCEL was written) we had prototyped this inflation process, however once we created the proper version using the DCEL several holes in the prototype method became clear. And so, contrary to our initial assumptions, the actual hardest part of creating the editor backend wasn’t the DCEL itself, but the surface-generation algorithm.
We then spent several weeks trying to find a solution that worked.. this was a fairly harrowing ordeal which warrants a post or tutorial of its own. The short version is that we eventually got it all working. While it definitely sucks that it took almost a month to complete a task we didn’t think would take more than a day, we’re just happy that in the end we managed to find a good solution. Barring any further roadblocks, the remaining bits should be finished in the next week or two, and we can then get to work on the front-end/UI.
So far we haven’t found a good name for the editor.. candidates such as “The Line King” have been dismissed as too silly, while others such as “Inflated Polygonal Graph” are clearly not silly enough. Hopefully by the time it’s all done we’ll have hit upon a suitable title — or better yet, a clever and/or punny acronym.
That’s about all that’s new around here. For the past couple weeks, we’ve been judging IGF entries during our spare time; as usual there are tons of great games this year. In N+ news, we’ll be choosing winners for the third Contesque any day now, so keep those entries coming!
With any luck it won’t take another month for us to write the next post 😉