Tesselation project (and a simple concave polygon hit test algorithm)

I’ve exhibited at Colony of Artists several times, a vibrant art festival at Abbeyhill Colonies in Edinburgh.

One of the things I was showing and selling was my tesselation pieces: designs inspired by MC Escher’s work, particularly matamorphosing tesselations.

Some of these pieces play with negative space and the transition from 3D to 2D:

Some have recomposition of objects:

Others play with simple rules that evolve designs:¹

I made these images (and animations) with a python script I wrote. It outputs SVG and takes config from JSON files.

This tessselation engine is feeling a bit cranky and limited now, so I’m going to re-implement and improve it. And I’ve been thinking about implementing the tesselations in a GLSL shader for live animations.

… wobbly image, mysterious music, segue into hideous details…

Tesselated polygons in a GLSL shader

Yes, it’s probably silly, but I like the idea of having a tesselation engine in a single GLSL shader. None of your fancy vertex shaders here!

So the essential problem, for the colourful tesselation images, is detecting when a point is inside a polygon or not.

What kind of polygon?

Convex polygons (simple shapes, no bites taken out of them) are easy to implement in a shader – just check if a point is on a certain side of all the polygon edges.

Concave polygons (shapes with bites taken out) are not so straightforward. There’s some well known algorithms, such as Winding, for checking point+polygon hits.

But I’m wanting to keep it fairly simple. I’d like a simple-ish algorithm that:

• can handle some concavity, enough to do some kinds of tesselation
• stream based (scans a list of vertices, and in \(O(n)\) time) – no need for separate lists of ‘bite’ polygons/vertices
• uses only simple operations like isRightOf, no ray casting and dealing with edge case stuff

After some play in Swift² with algorithms and shapes, I’ve found a fairly simple algorithm that handles a subset of concave polygons.

Concavex: a convex polygon with convex bites

Yeah, I made up a silly word. Please tell me if there’s an actual word for this!

A concavex is a concave polygon formed from a convex polygon minus convex bites at its edges (holes aren’t handled).

(pic coming!)

About the algorithm:

• runtime \(O(n)\)
• scans the list of vertices for the polygon stream-style, maintaining a few simple bits of state
• bails out early if it knows there can’t be a hit³
• does a pre-flight scan over the vertices to find an edge that turns right (as the starting point)⁴

I’ve implemented the algorithm in Swift and wrote unit tests for my sanity.

Here’s pseudo-code for the algorithm. It assumes vertices are given in clockwise order.⁵

// Inputs:
//   vertices: points for the polygon (clockwise order!)
//   point:    coordinate to check for polygon inclusion
//
// Returns:
//   true if point is in the polygon, otherwise false

let edges = vertices.makeEdges()
previousEdge = edges.last

// find first edge with RH turn at its start
start_edge_index = 0

while true {
    let edge = edges[start_edge_index]
    if edge.isToRight(previousEdge) {
     	break
    }
    previousEdge = edge
    start_edge_index += 1
}

// streaming scan of edges
failOnNextRight = false
edge_index = start_edge_index
edges_scanned = 0

while edges_scanned <= vertices.count {
    edges_scanned += 1
	edge = edges[edge_index]

	edgeIsToRightPrevEdge = edge.direction.isToRight(ofVector: previousEdge.direction)

    if edgeIsToRightPrevEdge && failOnNextRight {
    	return false
    }
    pointIsToLeftEdge = (point - edge.start).isToLeft(ofVector: edge.direction)
    failOnNextRight = pointIsToLeftEdge && (edgeIsToRightPrevEdge || failOnNextRight)
    previousEdge = edge
    edge_index = (edge_index + 1) % vertices.count
}
return true

The code above doesn’t look very complex. But it was pretty annoying to find the exact logic needed!

(More code to come)

• Graphics
• Maths
• Geometry
• Art
• Tesselation
• Glsl
• Dev