## A non-Euclidean tessellation and its fundamental domain.

I’ve been interested in the subject of non-Euclidean tessellations for many years now, although the reality is that I’ve only managed to work on them infrequently.  My most recent spurt was in early 2009, when I created this image (click on it to open a larger version in a new window).

If you look closely at it, you’ll see that it consists of regions coloured blue, purple, and gray. It turns out that regions of the same colour are congruent, but not in the usual Euclidean sense of being rotations and translations of one another.  It turns out that the class of congruency transforms is the more general set of Moebius transformations.  If you’re not familiar with these, a visually intuitive introduction is given in this popular video.

Moebius transformations don’t preserve “straightness” and distance, but they map circles to circles and preserve angles. As such, they still preserve a lot of information, and they give rise to a vast number of beautiful tessellations.

Unlike the familiar Euclidean tessellations that consist of tiles with straight edges, the “tiles” in these non-Euclidean tessellations have edges that are circular arcs.  Using the appropriate circle-preserving Moebius transformations, they can transformed so that copies match perfectly along their edges, leaving no spaces, and fill the plane.

For the tessellation in question, the basic tile looks like this (click on it to see a larger version).  It has been transformed by the Moebius transformation 1/z to make it a finite region.

It consists of three regions – purple, gray and blue.   Shapewise, the tile is radially symmetric.  Although the purple/blue regions appear to have 4 sides, they actually have 6 sides each – the small sides are easier to see on the full-sized image. Similarly, the gray region has 8 sides – two are quite small and are truncations on what at first look like corners.

Another view of the basic tile – known in the parlance as a “fundamental domain”, or “Ford domain” – is given below.

Look for the labels “A”, “B”, “C” in the above image.  They label, respectively, purple, blue and gray regions.  The gray region is outside of the other regions in the picture, and has infinite extent (contains the point at infinity).  That’s why we transformed it by 1/z for the previous picture.

If you look carefully at the full sized version of the first picture in this post, you can see how the tiles fit together.  I find it remarkable that such an unlikely tile shape could tessellate the plane, let alone do it so beautifully. I like to contemplate a Moebius soup in which swim untold multitudes of such tiles, gradually assembling according to edge pairing rules (self-deforming as they mate along edges) into an infinitely detailed quasifuchsian crystal.

Anybody looking for more technical details should take a look at the book Indra’s Pearls. The tessellation here corresponds to the limit set in Figure 8.13 of that book.  And here is a movie that zooms out between Figure 1 and Figure 3:

## WebGL in the real world – a short case study – Part 2

In a recent post I described a WebGL pilot project for a client.  After experimenting with a couple of WebGL frameworks I reverted to basic principles and wrote a purpose-built display app that was able to display 506K textured triangles at interactive rates.  The demo let the user navigate through a pseudo-architectural scene using first-person-shooter style keyboard navigation.

There were some caveats on performance.  One was that the scenes appeared to be fill-rate limited.  That meant that performance would vary inversely with the size of the canvas that I was using.  Another is that interactivity would periodically “jump” every second or so – in other words, you’d miss a frame or two every second or so as you moved through the scene.  Anecdotally, I noticed this more in Chrome than Safari or Firefox (this was on the Mac — things looked better on Windows).

I attributed the jumping to browser issues, and to the way, perhaps, that WebGL flow control was being implemented.  My experience with real time browser programming in the past had conditioned me to not expect rock solid performance.  I’d seen this talk, which details some of the issues that Google was having with implementing WebGL.  And finally, my clients were not complaining about the jumping.  So I let it be.

But some weeks later when I returned to the project for some cleanup and refactoring I idly ran some profiling in the Chrome Developer Tools.  To my surprise, the profiler showed that a lot of time was being spent in a call to setMatrixUniforms(), which I was calling in the main display loop for every one of 560 objects.  The definition of this function is

  function setMatrixUniforms() {
gl.uniformMatrix4fv(shaderProgram.pMatrixUniform, false, new Float32Array(pMatrix.flatten()));
gl.uniformMatrix4fv(shaderProgram.mvMatrixUniform, false, new Float32Array(mvMatrix.flatten()));
}

and is responsible for setting the perspective and model view matrices in the GLSL shader program.  It turns out that these matrices were not changing on a per-object basis, so I moved this call from the display loop to the beginning of the scene display function. After this simple change, the profiler was no longer showing excessive activity, and the jumpiness in scene navigation went away.

Astute readers may already have guessed what was going on, but I have to admit that not only did I not have any idea, but I didn’t really care at the time because I was busy with other matters.  But I mentioned what had happened to a colleague and fortunately he was a little more interested than I was.  There were two hypotheses:

1. resetting the matrix uniforms was somehow bringing the whole WebGL pipeline to a halt and degrading performance.
2. the memory allocation and/or matrix flattening in new Float32Array(pMatrix.flatten()) were taking more time than we would have thought.

It was easy enough to test the hypotheses.  It turned out not to be the pipeline, and it wasn’t just the allocation of Float32Array.  Another look at the profiler showed that a lot of time was being spent on garbage collection.  There had been two memory allocations per object, for 560 objects, for 30 frames every second.  In other words, over 30,000 allocations per second.  Which presumably was triggering a garbage collection pass every second or so.

As it turns out, moving the function call was all I had to do.  But if that had not been the case, it would have been straightforward to rewrite the function to use a pre-allocated FloatArray to avoid the overhead of allocation and garbage collection.

I chalk this up to my relative inexperience with garbage collected languages, and to the relative unimportance of this issue in my previous programming projects.  Many years ago I spent a week doing a mathematical visualization with Java – my one and only experience with Java – and there I encountered a massive performance hit when garbage collection kicked in.  So maybe I should have seen this coming. I didn’t, but lesson learned.  Don’t be so fast to blame inconsistent WebGL frame rates on general browser flakiness.  And have more awareness of what’s going on in the bowels of Javascript.

Acknowledgement: the setMatrixUniforms() snippet comes from the lessons at learningwebgl.com, although I of course take full responsibility for my careless use of it.

Update: learningwebgl.com has updated to a new matrix library.  Not only does it look faster and more appropriate to WebGL, but I don’t think the problem described in this post exists any more.

## WebGL in the real world – a short case study – Part 1

I started following WebGL a few months ago when it was in beta in several browsers.  Many creative web folks were already working with it, and some of the experiments were spectacular.  Fast forward to the present, and Google Chrome now officially supports WebGL (although your computer may not be up to it), and Google has a WebGL Experiments website.

So the experiments are fun and impressive, and I’ve even done some myself. But potential employers and clients with visualization needs were properly skeptical.  WebGL was not generally available other than in beta, Internet Explorer was not going to support it, and iOS support was not even on the horizon. Plus it ran on Javascript (considered by many to be a slow toy language not suitable for realtime graphics), and was subject to the inefficiencies of having the browser as an intermediary between the app and the metal.

I was fortunate to be contacted by a client who needed a browser based visualization solution, and was willing to fund a short “show me” pilot project.  The objective was to create a small demo that would run a typical architectural scene of 500K triangles at 30 frames per second.  A secondary objective was to fail fast – there was no point in going on if download times and interactive performance were dismal.  It would be a win for both of us regardless of the outcome – I was going to get some practical experience in real-world WebGL development, and the client would have enough data to navigate the next fork in their visualization roadmap.

Since the client’s files were in Collada DAE format, I was able to try them out in some of the existing WebGL frameworks such as GLGE and SpiderGL, which happened to have Collada import functionality and demos.  Results were mixed: on the one hand, setting up a demo for an architectural scene was relatively easy (for GLGE, I started from the Quake-style demo).  On the other hand, the scene had some quirks (such as multi-texturing with multiple UV maps per surface) that the frameworks didn’t handle.  And performance was disappointing: 3 FPS for a 500K-triangle scene in GLGE. Nevertheless, my clients seemed to be excited by the fact that their scene could be displayed in a browser at all.

GLGE is an impressive framework, and there is much to learn by browsing its source code.  It is a “how to” for a number of techniques such as shadow generation, canvas textures, collision detection, and object selection, and I will refer to it when I want to see examples of advanced techniques.  But I concluded, wrongly or rightly, that its generality was what lay behind the disappointing performance.  If your scenes are not as large as the ones I was using, it may well work well for you.  But my next step was to write a display engine that exploited the relative simplicity and predictability of my scene to get maximum performance.

An excellent place to get started in WebGL development is the Learning WebGL website, so that’s where I went, resolving to learn the basics of WebGL.  It seems these days that getting past the “Hello world” stage of learning a new technology is getting harder and harder, and that’s certainly the case for the “Hello triangle” stage of learning WebGL.  The source code for that, not including some supporting libraries, is over 200 lines of not only HTML and Javascript, but also GLSL, which is the low level language for writing shaders on the GPU (Graphics Processing Unit).  You are working on several levels, from the overall HTML page to the canvas element to the geometry and colors in the scene, and the GPU code that makes it all work on a pixel level.  Somehow all this ties together to give you a white triangle (and square) on a black background.  These tutorials are well written and deservedly popular, and probably the best place to get started.

I quickly discovered that Lesson 10 involved downloading a small scene and navigating it Doom-style, so I skipped ahead and using it as a scaffolding to build the demo, slowly replacing most of what was there.  And after a day or two I had a pseudo-architectural scene that ran 506K triangles (spread over almost 600 objects, most of them textured, some semi-transparent) at something like 26-28FPS (on my MacBookPro) .  Success!  This was certainly enough for the client to greenlight a second phase.

I think the lesson learned was that WebGL can be very fast.  After all, the triangles – once they’re in the GPU – are rendering just as fast as they would in OpenGL, modulo some canvas compositing passes in browser.  The trick is to get them down there and control the draw with minimum overhead.  And there is at least one not-so-obvious gotcha involved with using Javascript that I will discuss in a subsequent post.

## Visualizing hyperbolic symmetries using WebGL (aka a hyperbolic doodler in your browser)

I’ve long been fascinated by non-Euclidean tessellations and symmetries. The most widely known examples of these are the circle limit images by M.C. Escher.  I’ve always wanted to create an interactive way of producing these images, and with the advent of WebGL I’ve made some preliminary steps to doing this in the browser.

To see what I’ve done, you need a WebGL-capable browser.  Hopefully it will work for you, but your platform may not be capable of supporting WebGL. (There are some more setup and troubleshooting tips at the Learning WebGL website.)

The current experiments are a hyperbolic doodler and a hyperbolic kaleidoscope.  In the scheme of things, they are just minor variations of one another.  In both cases, things happen when you drag the mouse across the disk (dragging slower is better, at least until you get the hang of what’s going on).  In the doodler, you get a trail of white dots which is reflected across hyperbolic lines to get an infinite symmetry going all the way to the border of the disk.  The occasional colored shape is thrown in for a splash of color.  In the kaleidoscope, you get the same trail of dots, and more frequent colored shapes, along with a movement effect.  The impression you get is of throwing confetti into a hyperbolic mirrored chamber.

These are preliminary experiments.  I hope to do a lot more to increase control and expressiveness (and to let you save your work), but the project is on a bit of hiatus as I do a paying gig.  So I’ve posted this in the interim.

## Tune up your Ninja senses: An Interview with the creators of iSlash

Even though I’ve created a game or two, I have to admit I don’t play them much.  But now and then I get caught up in playing.  iSlash by Duello Games is one of the few iPhone games that I’ve admired, played compulsively, and recommended to anyone who would listen. You can get a good idea of the gameplay by viewing the above video or, better still, downloading and playing the game.  According to Duello Games, there have already been 450,000 downloads, and the game has reached #1 status in Turkey, France, and Belgium.

Duello Games is located in Turkey, and consists of Ercan Caliskan and Benan Arıgil.  I was interested in writing up a review of the game and its strategy (hopefully in a future post), and reached out to them to find out more about the development of the game and their own take on things.  Here’s what I found out.

Tell me a little about your backgrounds.  The math grad seems to be the designer, the business grad is the developer

We always loved games and wanted to be part of that world. But 15 years ago it was difficult to have a career in this area. So we made what seemed logical decisions and studied programs that promised steady careers. But the love of creating something eventually won the fight and after graduation we pursued careers in digital media.

We were co-workers 10 years ago. Benan specialized in coding and Ercan specialized in design. Then Ercan went to USA and worked there for 6 years. Benan co-founded, now one of the biggest digital agencies, Rabarba and was the lead developer there. We designed and built interactive web projects, Flash games and adver-games.

But it was still difficult to make end user games and compete with million dollar companies like EA. Thanks to Apple and App Store, new doors opened to indie developers like us and we jumped on the bandwagon. Last May we quit our jobs and started our own independent game development company Duello Games.

Right from the beginning I noticed you guys were from Turkey.  Do you have any special advantages or disadvantages developing in Turkey?  Is there anything you want the world to know about Turkey?

One disadvantage is that there is lack of know-how when it comes to games.  There aren’t many game companies around. So you have to learn things by yourself and walk alone. Another disadvantage is it’s very hard to make your voice heard over in the USA. Our shouts get lost over the ocean 🙂 Even though our game iSlash got very popular here we couldn’t reach the majority of US game players, yet. One advantage for us is that we know a lot of people over here and we can easily market our games.

Have you developed any games before, either published games or hobby projects?

We’ve developed adver-games and flash games for brands.

Have your lives changed in any significant way, either as a result of building the game, or because of its success?

We are at the beginning of our journey. We haven’t seen a huge success yet, at least when it comes to sale numbers. But we are very happy that we are pursuing our dream of making games and we hope we never go back.

I noticed that the game was #1 in Turkey.  Any reason for that, given that the App Store is essentially international?  Are there other countries where you’re doing especially well?

The Turkish iPhone game market is a small one. Also we were good at what we were doing before, so people knew us. When we came with our first game there was a buzz around it. So all that helped the game to get into top 50. And after that it climbed to the top organically.

Where did you get the idea for iSlash?  How did it evolve?  Assuming that you were inspired by other games involving small bouncing balls that needed to be avoided, how far can you trace back the ideas?

You probably remember the games Volfied or Qix. (Qix has you drawing boxes on the field in order to capture as much of the playing field as possible. In iSlash, conversely, you slash away the playing field in order to keep the bouncing ninja stars trapped.) Those games are our initial starting point.

But we changed the dynamics a lot. We created new rules and made the game suitable for iPhone.

My other favorite iPhone game is called Surfacer.  A parallel concept, in that small bouncing particles will kill you if they hit you while you are taking away their space.  Are you familiar with it? The most fascinating thing about games like this is controlling and exploiting the “voids” created in a space of particles.

[a side note: as a tribute to Surfacer, I submitted a 1019-byte
Javascript version to the JS1K competition.  See js1k.com/demo/811.
Don’t expect much – it’s only 1019 bytes of source code!]

We didn’t know about Surfacer. But we have seen similar games. There was one with blow fish. Same concept different skin.

Did this start off as a more abstract concept, with the ninja theme coming in as a skin? Or was that theme there from the beginning?

Actually the gameplay inspired the concept. Slashing reminded us of samurai. So we went with Asian theme from the beginning.

The sound design is very effective.  Was that done by a third party?  How much refinement went into it?  Are the sounds stock or custom?

Sound design was created by our talented musician friends from Dound Sesign (www.doundsesign.com) All of it is original and made specifically for iSlash.

I have to say that the game makes sometimes me feel like a sumurai. Winning a board seems like I must summon all of my zen, kungfu and warrior powers.  When I am “on”, my cuts are elegant, and the world slows down. (Most of the time, of course, I am a total klutz.)  Did you work explicitly to achieve this feeling of timeless flow?

Yes, we spent a lot of time on level design. We went back and forth to fine tune it and make the gameplay a fun experience. The music helped us as well.

I like the post-game stats and map of cuts  Did you consider some sort of instant replay?

Yes, we are planning to have a replay feature in the future updates.

Was there a “less is more” philosophy to the design?  In other words did you throw out more elements than stayed in?  The absence of scoring, for example.

Definitely. We like less is more philosophy. The simpler the better. But we didn’t throw out a lot of elements. We had wire-frame designs from the beginning.

I like the way you build up the elements as you progress through the levels – metal edges, bombs and buddhas, red stars, ghosts.  Were there particular motivations for these?  Do they force or dictate any particular strategies?

All that was intentionally created to keep the game challenging and fresh. Metal edges bring strategy to the game. Red stars force you to act fast.

Did you explicitly decide to randomize the initial star positions for each board attempt? How would the game have been different if you had always set the initial star positions and velocities the same for each attempt? One con of the randomization is that sometimes the player is screwed from the beginning.  One of the pros is that the player cannot rely on learning a pattern, and must deal with randomness.  One interesting
element is that sometimes the player wins because of luck of the draw, although he must have the ninja-fu to exploit it.

Yes, we chose to go with random. As you have written, the randomness brings surprise and a chance factor to the game which makes it fun and addictive.

Are there any basic human instincts, emotions or skills that you are consciously trying to reach or exploit?

With new elements we feed curiosity. And since the game depends on reflexes it makes it addictive. When you fail you think “ohh, if I only waited a second I could have done it” and you play it again. Because you know if your reflexes are good you can win this time.

Innovation and good design often stem from, not so much total freedom but rather, a set of constraints.  Were there constraints to your development process that in the end made it a better game?

The iPhone itself has physical constraints. But also great features like touchscreen and gyro. So we designed our game to suit the device and it made it fun.

What was the hardest part of development?

Actually the hardest part was level design. It was hard to keep them balanced. Even now with the latest upcoming update we had to readjust the difficulty. There are a lot of people who finished the game in a day but there are more who got stuck on the final levels.

What was the most unexpected in terms of how the game turned out vs. what you originally set out to do?

Well, this was supposed to be our “hello world” game but it turned out to be a real game 🙂 Our plan was to finish it in a month and use it as a learning step. But it evolved, got better and better and became a game it is today.

How did you test this?  Did you have slow-motion versions, or automatic tests?  Or did you manually test at full speed?

We tested everything manually at full speed.

How did you set the difficulty?  I’ve gotten to various boards and considered them impossible.  Maybe that’s a good thing, because I’ve eventually beaten them, although perhaps only through good luck.  And of course, the board I’m currently on (the octagonal star) is impossible!  Have you guys manually played through all of the games?

We finished all levels a few times. But I guess we made the mistake of relying on our tests. We played the game a lot during development and got good at it without realizing. Also since we designed the levels we knew where to start and what to do to finish it. Next time we’ll have a larger pool of testers.

As mentioned earlier, with the next update we are readjusting the difficulty of levels. So you should be able to beat all with less effort.

Do you use any kind of formal process, or is it the usual kind of Agile?

We had a rough plan but it evolved. As I said before this game was supposed to be our “hello world” but it became “hello universe”. We still continue to revise our strategy as we learn new things and get new perspectives.

Is this your first game?

Yes, it is the first game we’ve created for the end user. Previously, we created flash adver-games for brands.

If I were to espouse a game development methodology it would be to find a fun mechanism or physics, and then set up puzzles to exploit the physics.  Do you guys have a philosophy?

We think in a similar way. Find a mechanism and build something fun on top of it. In our case we started with “swipe and slash” then it evolved.

How do you split the work?

Together we decide on the mechanics and elements but after that Ercan does the design work and Benan does the coding. But since we are two people we also have to build our website, do the marketing and all that.

What’s next?

iSlash HD for iPad is next. We are currently working on that. Hopefully it will be ready at the beginning of November and will support Game Center. After that we’ll start working on the second game. We have a few ideas but not sure yet which one will be the winner.

Are you guys gamers?

Yes 🙂

What games do you play the most?

Fallout, Star Craft 2, recently testing Play Station Move and of course iPhone games.
We normally like to play adventure ve rpg games but don’t have much time anymore.

What games do you admire the most?

Day of the Tentacle, Monkey Island, God of War.

What games have inspired you?

iPhone is a different environment where the majority of users are casual gamers. Popular games on iPhone tend to be different from other console games. So we can’t name any specific games that inspired us, but all contributed something.

In my day, videogame developers were far and few between – my guess is that there were less than a thousand.  These days, it seems everybody has been playing and writing games since they were seven years old.  There are probably tens if not hundreds of thousands of games out there, console, online, desktop, mobile.  On the other hand, there are now millions if not billions of gamers. Any thoughts on that?

It was difficult to become a developer back then. Now it is easier to access the information you need, thanks to internet and new technologies. But nowadays it is difficult to be noticed among thousands of developers and games.

I’d like to thank Ercan and Benan for taking time out of their busy schedule to answer my questions. They also answered some questions on strategy, and I’ll incorporate those into my write-up of the game and its strategy in a future post.

Duello Games just released a major update of iSlash, including an easier version of the board I’m currently stuck on.

## The Sound of Chaos

Chaos theory and its little cousin – strange attractors – have been around for a long time. Pictures of chaotic systems and strange attractors abound, and they are a mainstay for computer math experimentalists, although still in the minor leagues relative to the Mandelbrot set.

Most implementations tend to ignore the fact that these systems represent dynamics, that they move and evolve. Still pictures can hide the fact that, for example there are sink states, and that was supposed to represent 20,000 iterations only shows 5,000 because the system hit a fixed point at iteration 5,001.

Years ago I wrote a Windows program to show the dynamics of strange attractors, but that experiment quickly moved over to computing the dynamics of iterated function systems, iterated rational polynomials, and Kleinian groups. And I always wanted to use these systems to generate sounds.

All that remained on the back burner until this year. I recently discovered that the Flash Player now supports on-the-fly sound generation. And an implementation in Flash would conform to my self-imposed mandate to write only software that was browser based. So I downloaded the latest Flex Builder beta from Adobe and set about learning enough Actionscript to get this project going.

It’s been a tough slog because Flex 4 has many departures from Flex 3, in particular the Spark component set, which is sort of the same as Halo, but also different. So hard times for a newb.

Anyways, I’ve got a bare example experiment going, which is in my beta area. It comes with a video that should explain what’s going on.

## Math with a soundtrack

There’s something about music or a soundtrack that really enhances what would otherwise be just a silent movie. So I plan to add music to my visualizations as time and inspiration allow. Here’s an example that I did a week or two back. The original movie was 24 seconds long, but now it’s been slowed down to accommodate an atmospheric soundtrack.

## Scoring the Boulder Dash theme

A few weeks ago I discovered noteflight.com, a website that lets you create musical scores.  I’ve always wanted to use scoring software, but never got around to it until – well you know, the price was right.

Years ago I wrote a computer game called Boulder Dash.  The music for that was composed in a very basic soundtrack editor I wrote for the Atari 800, and was never actually played on a real-world instrument.  I’ve always wanted to convert that music to a real score and hear what it would sound like on, say, the piano.

I dug up some old listings and transcribed the music, which was encoded in all of 256 bytes, and represented 16 bars of music in two voices.

Here’s the result (the play button is at the upper left of the snippet):

In the original game, the 16 bar melody repeated endlessly, ceasing only when the user pressed the Start button.  Here, I give two reps, followed by a tacked-on finish.  According to a friend with music theory background, this kind of repeating passage is called a vamp (in musical theatre circles), and the key signature (which I admit had been puzzling me) is C minor.

By the way, some of Noteflight’s amazing features show through in the score snippet above.  Not only can you play the score by pressing the forward button, but you can click individual notes and play them (or play notes that share the same stem by clicking on the stem).  Each bar has its own play button, so you can start play in mid-score.  You can select groups of notes, staffs, bars, etc – check it out by hovering over different parts of the score. Shift-P will start playing from your current selection.  For more of this awesomeness – and actual music-editing functionaliy, go to their site. Or click on the Noteflight icon at the lower right of the snippet to see the full score.

## Updating classic math illustrations

I recently saw this classic image from over a century ago attempting to illustrate the limit set of a reflection group.

Benoit Mandelbrot computed a more exact version a few  decades ago.

Mandelbrot’s version is more correct as far as the limit set goes, but it doesn’t show the tessellation (the white and shaded regions in the first drawing).  The software I’ve been building should do a better job of showing both the limit set and tessellation.  But that’s a project for a bit later.

Jan 25, 2010: In a comment to this post, Xavier Buff has pointed out that the limit set and tessellation have been computed at http://images.math.cnrs.fr/Un-ensemble-limite.html.  The pictures there are very nice, especially since separate components of the fundamental region have been give different colorings.  The site contains other mathematical visualizations as well – you can browse at http://images.math.cnrs.fr/-Images-et-visualisation-.html.