Categories

# Image Triangulation

Previously, I split an image into a bunch of rectangles. What about using triangles? This requires more thought, as it’s a little trickier to divide up the plane using triangles. The natural solution is to keep track of a set of vertices, then use a Delaunay triangulation to split up the image.

First, let’s do constant-color triangles. How do we pick where to put the new points? Let’s define the error as the absolute difference between the original image and the approximation. Since we know that a vertex is where the image is broken up, a good guess is to put a vertex at a low-error point. This isn’t quite obvious, but because the current estimate is the average over a region, the lowest error points will be where the average level is crossed. This ends up splitting the image along edges! Check it out:

Here’s a comparison of four different error cutoffs, with the error decreasing by 5x as you move across. As expected, smaller allowable error results in smaller triangles.

What about using gradients inside the triangles? Edges become a problem, because small triangles are needed to span an edge to properly render it. The best method that I found was to put a new vertex at the highest-error point in the triangle.