Delaunay Triangulation On The iPhone with SpriteKit

The use of Delaunay triangulation as a visual effect has become very popular recently in motion graphics, and interactive works. It’s a pretty cool effect, but there aren’t a lot of examples of how to get it working. In this post I’m using this collection of Objective C Delaunay triangulation math classes I found on GitHub, ported by Christopher Z Garrett. They’re a few years old, so I’ve updated some of the code to remove Xcode warnings and also added compiler flags so they can be ARC’d.

The thing you need to know about Delaunay triangulation is that it doesn’t draw anything. It’s just math for working out vertices of the triangles. We’re going to be using SpriteKit to do the drawing. Because of this separation between drawing and positional calculations, and also because Delaunay triangulation is quite processor intensive, it’s a perfect candidate for drawing to a single SKTexture, as opposed to adding each sprite to the scene (see my post here on drawing particles with textures). However for simplicity in this example I’m just going to add sprites straight to the display hierarchy. Download the finished project here.

- (void)redrawTriangles
{
    CGRect rect = CGRectMake(0, 0, self.frame.size.width, self.frame.size.height);
    
    self.delaunayVoronoi = [DelaunayVoronoi voronoiWithPoints:[self randomPointsWithLength:kMaxNumPoints] plotBounds:rect];
    
    [self removeAllChildren];
    
    for (DelaunayEdge *e in self.delaunayVoronoi.edges) {
        SKShapeNode *line = [SKShapeNode node];
        line.path = [self linePathWithStartPoint:e.delaunayLine.p0 andEndPoint:e.delaunayLine.p1];
        line.lineWidth = .5;
        [line setStrokeColor:[UIColor whiteColor]];
        [self addChild:line];
    }
}

The redraw triangles method is where all of the magic happens.
We create an instance of the DelaunayVoronoi object and parse it an NSArray of CGPoints that have been converted to NSValues. I’ve created a helper method randomPointsWithLength that does this for us. We also parse it a CGRect to describe the bounds to the area.
Then cycle through the DelaunayVoronoi’s edges array and get the x,y properties of the start and end of the delaunayLine in the edge.
Draw the line into an SKShapeNode, by parseing it a CGPathRef. I’ve created a little helper method that takes two points and draws the line between them.
Then add it to the scene.

// generate random points for the verticies of the triangles
- (NSArray *)randomPointsWithLength:(NSInteger)length
{
    NSMutableArray *pointsArray = [NSMutableArray array];
    
    for (int i = 0; i < length; i++) {
        CGPoint point1 = CGPointMake(arc4random_uniform(self.frame.size.width), arc4random_uniform(self.frame.size.height));
        NSValue *value = [NSValue valueWithCGPoint:point1];
        [pointsArray addObject:value];
    }

    return pointsArray;

}

- (CGPathRef)linePathWithStartPoint:(CGPoint)p0 andEndPoint:(CGPoint)p1
{
    CGMutablePathRef path = CGPathCreateMutable();
    CGPathMoveToPoint(path, NULL, p0.x, p0.y);
    CGPathAddLineToPoint(path, NULL, p1.x, p1.y);
    
    return path;
}

-(void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
    /* Called when a touch begins */
     [self redrawTriangles];
}

-(void)update:(CFTimeInterval)currentTime {
    /* Called before each frame is rendered */
}

@end

The other two helper methods should be pretty straight forward, and I also redraw the lines again on touch.