Voronoi: Touchable Diagrams in iOS Simulator

Posted by Jeffrey

Note: This is an archived version of the Voronoi page, for those interested in earlier versions. The most recent version is at Voronoi: Touchable Diagrams in iOS Simulator.

I’ve put together another OCaml app that you can run on the iOS Simulator. It lets you make colorful pictures based on Voronoi diagrams. Although Voronoi diagrams are computationally interesting, they also just look very cool.

A Voronoi diagram is based on a set of dots on the screen. Each dot “claims” the area closest to it, and gets to say what color it should be. As you move the dots around, the shapes of the claimed areas adapt to the different layout, and the colors change. It’s hard to describe, but very enjoyable to play with.

If you don’t want to build it yourself, a prebuilt binary for Voronoi is available from Psellos. See below for how to extract and try it out in the iOS Simulator (it’s extremely easy). Otherwise you can get the sources from Psellos, compile using Xcode tools, and run the app in the iOS Simulator. This is also pretty easy. All you need for either approach is an installation of Xcode with the iOS SDK; you don’t need an iOS device or have to be a registered Apple developer.

Here are some hints for trying out the app:

• Touching the screen in an open area creates a new dot that you can move around to any place you like. Touching near an existing dot allows you to move the dot to a new place.

• If you move a dot on top of another dot (or almost on top), they combine into a larger dot.

• If you combine three dots near the center of the screen, a large number of randomly placed dots are added to the screen. (The number of dots is doubled.)

• If you combine three dots near the edge of the screen, a large number of dots are randomly removed. (The number of dots is divided in half.)

• If you shake the device, you get a menu for starting over (with just one dot), or for changing the colors. To shake the phone in the iOS Simulator, use the Hardware -> Shake Gesture menu.

• If you combine four dots (which is tricky to do), all four of the dots disappear. This can be useful if you want to clear randomly placed dots from an area.

The app has been built and tested with Xcode 3.2.5 and Xcode 4.0.2. It will work with any recent Xcode release.

Please note that a few of the command lines of the following discussions are too long to fit on a single line of a typical browser window. In a lot of cases there is no good place to split them into smaller lines, usually because of a long filename or URL. Take care that you enter them as a single line if you’re typing them in by hand.

Running Prebuilt Voronoi Binary

If you want to run the prebuilt Voronoi binary (to prove to yourself that it works), just download the binary for Voronoi 1.0.0 from Psellos:

    $ curl -O -s http://psellos.com/pub/voronoi/voronoi-simapp-1.0.0.tgz
    $ ls -l voronoi-simapp-1.0.0.tgz
    -rw-r--r--  1 psellos  staff 165540 Jul  7 13:45 voronoi-simapp-1.0.0.tgz

To save typing, you can download it directly from this link:

• Voronoi Simulator App 1.0.0

Now untar.

    $ tar -xzf voronoi-simapp-1.0.0.tgz

This creates a directory named voronoi-simapp-1.0.0 in which you should see the binary (Voronoi) and a script named runsim that runs the app in the iOS Simulator. To run Voronoi, just cd and run the script:

    $ cd voronoi-simapp-1.0.0
    $ runsim

If you don’t have Xcode installed in the usual place, you should edit the script appropriately before running it.

Note: for simplicity, this script uses an unsupported interface of the iOS Simulator. Since it’s unsupported, the interface could disappear in a future release of Xcode. There will always be a way to run the app through the Xcode IDE, of course.

Voronoi Overview

My first OCaml iOS Simulator app, Gamut, shows how to compile an app using the OCamlXSim compiler that I put together, described here. It also shows how to link and execute the app in the iOS Simulator. However, the Gamut app itself is quite simple. The Voronoi app has more of the feel of a real iOS app.

• It has an interactive UIKit component.

• It uses the touch interface to manipulate visible objects, and responds to the shake gesture.

• It does more complex graphics.

• It performs some non-trivial computation.

Voronoi shows how to wrap the UIActionSheet class, which is used to display a menu when you shake the phone. This is interesting both for the typing and the implementation. At the type level, you want to have a good handling for the action sheet delegate, the object that responds to user touches on the displayed menu. The uiActionSheet.mli file shows one way to define two mutually recursive classes that capture the typing.

At the implementation level, you need to wrap the delegate object correctly in an ObjC object to pass the menu touches from the ObjC world to the OCaml world. This is a special case of the general problem of handling dynamically constructed callbacks from ObjC to OCaml. The ASDelegate class in wrap.m shows a simple solution to the problem.

Each dot of a Voronoi diagram is called a site. The region around each site is a polygon called a cell. The code for drawing a cell seems particularly concise when written in OCaml:

    val bezierpath : UiBezierPath.t = UiBezierPath.bezierPath ()

    let polypath = function
        | [] -> () (* Nothing to draw *)
        | p1 :: rest ->
            begin
            bezierpath#moveToPoint' p1;
            List.iter bezierpath#addLineToPoint' rest;
            bezierpath#closePath;
            end

While the Gamut app doesn’t do much interesting computation, Voronoi does quite a bit: as you move the sites, it continuously calculates the Voronoi cells to keep the picture updated. It also uses a different set of Voronoi cells (generated internally) to give an interesting color to each point of the screen. As a result, the amount of OCaml code compared to Objective C code in Voronoi is quite a bit higher than in Gamut.

The fraction of OCaml code can continue to increase as you write more complex apps. At Psellos we have a mostly fixed amount of Objective C for our iOS apps, and in fact we write our wrappers mainly in OCaml. So the amount of Objective C is relatively small and independent of the size of the project.

Building Voronoi from Source

Before starting, make sure you have installed Apple’s Xcode and iOS SDK. I used both Xcode 3.2.5 and Xcode 4.0.2 to build and test Voronoi, but any recent version of Xcode will work. You also need an OCaml compiler that conforms to the iOS Simulator ABI. You can use the one I put together—binaries and instructions for building from source are given here.

Now download the sources for Voronoi 1.0.0 from Psellos:

    $ curl -O -s http://psellos.com/pub/voronoi/voronoi-1.0.0.tgz
    $ ls -l voronoi-1.0.0.tgz
    -rw-r--r--  1 psellos  staff  26915 Jul  7 13:46 voronoi-1.0.0.tgz

To save typing, you can download it directly from this link:

• Voronoi 1.0.0

Now, untar and cd into the Voronoi directory.

    $ tar -xzf voronoi-1.0.0.tgz
    $ cd voronoi-1.0.0

Building and running Voronoi is done by a Makefile. You may need to change some of the specific settings in this file:

    PLAT = /Developer/Platforms/iPhoneSimulator.platform
    SDK = /Developer/SDKs/iPhoneSimulator4.2.sdk
    OCAMLDIR = /usr/local/ocamlxsim

Change PLAT to the location of your iPhoneSimulator platform directory, part of the Xcode iOS SDK. Change SDK to the iOS SDK you wish to use. Probably you want to set it to the most recent SDK that you have installed. Change OCAMLDIR to the location of your OCaml compiler for the iOS Simulator.

Now you can build and run the app:

    $ make
       ...
    /usr/local/ocamlxsim/bin/ocamlc -c vorocells.mli
    /usr/local/ocamlxsim/bin/ocamlopt -cc '/Developer/Platforms/iPhoneSimulator.platform/Developer/usr/bin/gcc-4.2' -ccopt '-arch i386 -isysroot /Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator4.2.sdk -gdwarf-2 -D__IPHONE_OS_VERSION_MIN_REQUIRED=30200 -isystem /usr/local/ocamlxsim/lib/ocaml -DCAML_NAME_SPACE' -c vorocells.ml
       ...
    ibtool --compile Voronoi.nib Voronoi.xib
    echo -n 'APPL????' > PkgInfo
    $ make execute
    $

You should see the Voronoi app running in the iOS Simulator.

Note: for simplicity, make execute uses an unsupported interface of the iOS Simulator. Since it’s unsupported, the interface could disappear in a future release of Xcode. There will always be a way to run the app through the Xcode IDE, of course.

Theory of Operation

Voronoi essentially follows the MVC paradigm. The model is a list of points representing the Voronoi sites, and a value called a “color field” that associates a color with each point of the display. The view is the graphical representation of the Voronoi diagram: the colored polygons and dots. These are coordinated by the controller, an instance of the class Voronoictlr.t.

As in the Gamut app, graphics are handled through an Objective C class named ViewDelegator. It’s a subclass of the Cocoa Touch UIView class, and its instances delegate their GUI methods to a specified delegate object. In particular, instances delegate touch events, motion events, and the drawing method drawRect:. The Voronoictlr class participates in this ViewDelegate protocol, and thus the controller receives notifications of touch, motion, and drawing events. The controller also participates in the UIApplicationDelegate protocol to receive notifications of changes in the application state.

When you touch the screen, Cocoa Touch calls a method in the Voronoictlr (inverse) wrapper class, which is translated directly into an OCaml method call to the controller. The controller determines whether the touch is near an existing site or is in an open area. In the first case, the existing site is moved to the beginning of the site list. In the second case, a new site is created at the touch point and added at the beginning of the list. Thus, the site to be moved is always first in the list.

While the touch is active, the controller moves the first site to follow it. After each incremental move, the voronoi cells are recalculated and redisplayed. Calculations of the Voronoi cells are handled by the Vorocells module, and colors for the cells are chosen using the Colorfield module. The Vorocells module uses a straightforward (quadratic) algorithm to calculate the cells. The Colorfield module goes to a fair amount of work to choose colors that look good together.

When you shake the phone and ask to change the colors or the sites, the controller updates the appropriate part of the model accordingly. The controller then recalculates and displays the view.

The startup of an iOS app is controlled by a nib file, generated by Interface Builder. For Voronoi, the file is Voronoi.nib. This file says to create three objects: the main window; an instance of ViewDelegator that covers the whole screen; and an instance of Voronoictlr.t. The action sheet (an instance of UiApplicationSheet.t) is created dynamically when the app is launched, and so does not appear in the nib file.

Interface Builder

In versions of Xcode prior to 4.0, Interface Builder was a separate utility. In Xcode 4.0, it has been integrated as one of the many specialized editors for project components. If you’re using an older version of Xcode, you should be able to open the source file Voronoi.xib directly with Interface Builder. For those using Xcode 4, I created a small project named Voronoi.xcodeproj whose only purpose is to examine and modify the Voronoi.xib file. If you double-click on Voronoi.xcodeproj in the Finder, it will start Xcode on the project. You can then navigate to the Voronoi.xib file and examine its contents. (Hint: to see the detailed properties of objects, open the Utility window at the right of the screen.)

In either case, you’ll see that Voronoi.xib is pretty simple. There are only three interesting objects: the main window, a ViewDelegator instance that occupies the whole window, and an instance of Voronoictlr.t.

There is a connection to the controller from the delegate outlet of the application (represented by File’s Owner). This supports the application startup notification.

There is a connection from the delegate outlet of the ViewDelegator to the controller, and a connection from the delegator outlet of the controller back to the ViewDelegator. These support the notifications for touches, motion, and drawing.

Since Interface Builder (IB) doesn’t know anything about OCaml (at least not yet), it gets its information from the header files for your wrapper classes. In earlier Xcode versions, you may need to manually tell IB to load the wrapper header files. To load header files into earlier versions of IB, click on the File -> Read Class Files menu item, and navigate to your ObjC header files, i.e., to the wrapper files for your OCaml classes. Note that you need wrappers only for OCaml classes that are accessed from ObjC, which should be just a few of them.

Discussion

Although I’ve packaged up Voronoi to run in the iOS Simulator, it will naturally also run directly on iOS devices (iPhone, iPod Touch, iPad) with no changes to the code. The only changes required for iPhone and iPod Touch are to the building environment. For iPad, the nib file will also need to change. The code is written to be independent of the screen resolution, so it ought to run nicely as a native iPad app, in fact.

Feel free to send me any cool looking pictures that you create using the Voronoi app. If you modify the app to make even cooler pictures, please let me know about it so I can give you credit.

If you’re interested in learning more about Voronoi diagrams as mathematical and computational geometric objects, a good place to start is the Wikipedia article. An interesting project would be to replace the simple algorithm in the Vorocells module with a more sophisticated one, such as Fortune’s Algorithm, and see if this makes the app more responsive when there are many cells.

Compiling OCaml to run directly on iOS is described in an accompanying note here. I’ve also put together two apps that are packaged to run on iOS devices. There is a simple app named Portland that tracks the device’s orientation (portrait or landscape), and a slightly more complicated app named Slide24 that plays (and solves) the classic 5x5 sliding tile puzzle.

I’d be very happy to explain any part of Voronoi in more detail. The only thing stopping me is my natural shyness. If you have questions, comments, or corrections please email me at jeffsco@psellos.com.