pdf version of writeup available here

Introduction

The purpose of this project was to create an extension of our SVG renderer that could convert an image into a low polygon version. This would mostly be used for artistic effect, although depending on how many triangles you use, it could also use up less storage. I didn’t want to look up any existing algorithms for this kind of functionality, so I created my own from scratch as I will describe below.

I devised and implemented an algorithm for simplifying an image into an svg of only triangles. This algorithm could be useful for either compressing images or for stylizing images as a lowpoly render.

I also implemented a command-line interface that automatically constructs this ImageSimplifierSettings struct based on the following command-line arguments:

--triangulate (null) Adding this flag will turn on triangulation of all images for the SVG renderer. Without it, none of the other flags will do anything.

--num_triangles (int) How many triangles to divide the image into.

--num_samples (int) How many sample points are used in each triangle to determine the color and amount of detail in a triangle.

--save_to_path (str) If a file path is specified, a polygon version of the image will be saved as an SVG file using just objects.

--amount_chaos (float) Degree to which the place where triangles are split is optimized to maximize detail. A value of 0 will result in perfectly regular triangles. A value of 0.5 is recommended.

--area_priority (float) Degree to which larger triangles are preferentially split more than smaller triangles. A value of 0 will split triangles only based on how much detail is in that triangle. A value of 0.5 is recommended.

--show_pos (null) Instead of plotting triangles, the centroid of each triangle is plotted. This makes it very easy to visualize the distribution of triangles and where the algorithm thinks there is more detail in the image.

Algorithm

The algorithm I created starts with 14 randomly placed non-overlapping triangles which cover the entire image (shown below).

These triangles are placed into a priority queue which is sorted based on the benefit we would receive from splitting any given triangle into two triangles. This benefit is calculated based on both the size of the triangle and the standard deviation of the various color channels at different randomly sampled points within the triangle. Essentially we are finding the triangle that is the worst approximation of its underlying data.

1priority = pow(area, settings.areaPriority) * (sqrt(sd_r) + sqrt(sd_g) + sqrt(sd_b)) * (1 + getRand() / settings.numTriangles);

When splitting a triangle, we pick a point along its longest side which is calculated by using the average location of the detail within the image (a weighted average of the sample points’ locations using their standard deviations). These two smaller triangles are then placed back in the priority queue.

Once we have enough triangles, we pop each triangle, one at a time, and fill the corresponding part of the sample buffer with the correct color. This color is determined by averaging the color from each randomly selected sample point from within the triangle.

Examples

I will demonstrate the capabilities of my SVG renderer extension by showing examples of modulating some of the algorithm’s parameters.

--num_triangles

As you increase the number of triangles, there is more detail preserved in the final image. With a few hundred triangles, you get a cool mosaic pattern, with a few thousand you get a stylized low-poly version of the original photo, and with tens of thousands of triangles, you get a pretty close approximation of the original image.

--area_priority

Area priority affects which triangles are chosen to be split. With a value of 0, the algorithm always chooses the triangle that is covering the most detailed part of the image. That’s why most of the triangles are used near the eyes but almost none are used for the gray background. As the value is increased, larger triangles will be prioritized to be split even if they don’t cover as much detail. I found 0.5 to be a good compromise between prioritizing detail and maintaining a homogenous look over the whole image.

--amount_chaos

The amount of chaos is the degree to which triangles are split unevenly to maximize detail. With a value of 0, the triangles are all similar and occur at 90-degree angles to the x and y-axis. As it’s increased, the image has a more natural feel and ends up looking better in the end.

--num_samples

The number of samples determines how many samples are used per triangle to check the amount of detail for that triangle and to calculate the average color of the triangle. Increasing the number accomplishes the same thing as supersampling with the added benefit of giving the algorithm a more accurate idea of detail in the image.

Analysis

This section is simply to demonstrate that the algorithm correctly places more triangles in places where there is higher frequency data (more detail). The left picture is the result of calling my algorithm with 50,000 triangles. The right image is what the image looks like if we plot just the centroid of each of the triangles.

Conclusion

I’m actually really pleased with how well this project turned out. I wasn’t sure if I would be able to pull it off or if the results would end up looking good. Some early results (shown to the right) had me pessimistic that my algorithm would even work. But after weeks of fine-tuning the code and trying different computations, I think the results are pretty cool! On the last page, I show the same image simplified with 5,000 triangles twice. The first one is a naive approach where we uniformly place triangles over the image and sample each triangle at its centroid for its color. The second one is using my fully functioning algorithm. I think it has a really nice balance of keeping the details we care about (the hair and the eyes) while still keeping the background simple and artistic.

Code

Here is the ImageSimplifier class which does all of the heavy lifting

1class ImageSimplifier;
2
3struct ImageTriangleSample {
4    ImageTriangleSample(int a, int b, int c, ImageSimplifier *image_simplifier, ImageSimplifierSettings settings) : a(a), b(b), c(c), image_simplifier(image_simplifier), settings(settings) {
5        float x = getPos(a).x + getPos(b).x + getPos(c).x;
6        float y = getPos(a).y + getPos(b).y + getPos(c).y;
7        x /= 3;
8        y /= 3;
9        centroid = CS248::Vector2D(x,y);
10        averageChaos = centroid;
11        area = abs(getPos(a).x * (getPos(b).y - getPos(c).y) + getPos(b).x * (getPos(c).y - getPos(a).y) + getPos(c).x * (getPos(a).y - getPos(b).y));
12        setProps();
13    }
14
15
16    void setProps();
17    CS248::Vector2D getPos(int index);
18    CS248::Vector2D getPosA();
19    CS248::Vector2D getPosB();
20    CS248::Vector2D getPosC();
21
22    int a;
23    int b;
24    int c;
25    ImageSimplifier *image_simplifier;
26    // CS248::Texture &tex;
27    float benefit; // benefit from breaking into two triangles
28    CS248::Color color;
29    // CS248::Sampler2D *sampler;
30    CS248::Vector2D centroid;
31    CS248::Vector2D averageChaos;
32    float area;
33    ImageSimplifierSettings settings;
34};
35
36bool operator<(const ImageTriangleSample& r1, const ImageTriangleSample& r2);
37
38struct SamplePoint {
39    SamplePoint(float u, float v, CS248::Color color) : u(u), v(v), color(color) {
40    }
41    float u;
42    float v;
43    CS248::Color color;
44};
45
46template<class T> struct PQueue {
47    void insert(const T& item) {
48        queue.insert(item);
49    }
50    void remove(const T& item) {
51        if(queue.find(item) != queue.end()) {
52            queue.erase(item);
53        }
54    }
55    const T& top(void) const {
56        return *(queue.begin());
57    }
58    void pop(void) {
59        queue.erase(queue.begin());
60    }
61    size_t size() {
62        return queue.size();
63    }
64
65    std::set<T> queue;
66};
67
68
69class ImageSimplifier {
70    public:
71        ImageSimplifier(ImageSimplifierSettings settings,
72                        CS248::Texture &tex,
73                        CS248::Sampler2D *sampler);
74
75        ~ImageSimplifier() {};
76
77        int getNumTriangles();
78
79        void addTriangle();
80
81        void subdivideTriangle();
82
83        void simplify();
84
85        void createPoints();
86
87        ImageSimplifierSettings getSettings();
88
89        ImageTriangleSample popTriangle();
90
91        CS248::Color sample(CS248::Vector2D uv);
92
93        int addPos(CS248::Vector2D pos) {
94            vert_positions.push_back(pos);
95            return vert_positions.size() - 1;
96        }
97
98        int setPos(int index, CS248::Vector2D pos) {
99            vert_positions[index] = pos;
100            return index;
101        }
102
103        CS248::Vector2D getPos(int index) {
104            return vert_positions[index];
105        }
106
107    private:
108
109        CS248::Texture &tex;
110        CS248::Sampler2D *sampler;
111        PQueue<ImageTriangleSample> queue;
112        std::vector<CS248::Vector2D> vert_positions;
113        ImageSimplifierSettings settings;
114};

Here is the entry point for the program. This will parse your commands and adjust the triangulation settings accordingly

1int main( int argc, char** argv ) {
2
3  // create viewer
4  Viewer viewer = Viewer();
5
6  // create drawsvg
7  DrawSVG* drawsvg = new DrawSVG();
8
9  // set drawsvg as renderer
10  viewer.set_renderer(drawsvg);
11
12  // load tests
13  if( argc >= 2 ) {
14
15    ImageSimplifierSettings triangulate_options;
16    for (int i = 2; i < argc; i++) {
17      if (strcmp(argv[i], "--triangulate") == 0) {
18        triangulate_options.simplifyType = TRIANGULATE;
19        continue;
20      }
21      if (strcmp(argv[i], "--amount_chaos") == 0 && argc > i + 1) {
22        triangulate_options.amountChaos = atof(argv[i+1]);
23        i++;
24        continue;
25      }
26      if (strcmp(argv[i], "--save_to_path") == 0 && argc > i + 1) {
27        triangulate_options.saveToPath = argv[i+1];
28        i++;
29        continue;
30      }
31      if (strcmp(argv[i], "--num_triangles") == 0 && argc > i + 1) {
32        triangulate_options.numTriangles = atoi(argv[i+1]);
33        i++;
34        continue;
35      }
36      if (strcmp(argv[i], "--num_samples") == 0 && argc > i + 1) {
37        triangulate_options.numSamples = atoi(argv[i+1]);
38        i++;
39        continue;
40      }
41      if (strcmp(argv[i], "--area_priority") == 0 && argc > i + 1) {
42        triangulate_options.areaPriority = atof(argv[i+1]);
43        i++;
44        continue;
45      }
46      if (strcmp(argv[i], "--show_pos") == 0) {
47        triangulate_options.showPos = true;
48        continue;
49      }
50      msg("Usage: drawsvg <path to test file or directory> --triangulate --show_pos --num_triangles <int> --num_samples <int> --amount_chaos <float> --area_priority <float>"); exit(0);
51    }
52    drawsvg->setTriangulateOptions(triangulate_options);
53    if (loadPath(drawsvg, argv[1]) < 0) exit(0);
54  } else {
55    msg("Usage: drawsvg <path to test file or directory> --triangulate --show_pos --num_triangles <int> --num_samples <int> --amount_chaos <float> --area_priority <float>"); exit(0);
56  }
57
58  // init viewer
59  viewer.init();
60
61  // start viewer
62  viewer.start();
63
64  return 0;
65}

Here are the actual function definitions

1#include "image_simplifier.h"
2
3#include <cmath>
4#include <vector>
5#include <iostream>
6
7#include "CS248.h"
8#include "texture.h"
9#include "svg_renderer.h"
10
11bool operator<(const ImageTriangleSample& r1, const ImageTriangleSample& r2) {
12    if(r1.benefit != r2.benefit) {
13        return r1.benefit > r2.benefit; // switched so that minHeap becomes maxheap
14    }
15    if (r1.centroid.x != r2.centroid.x) {
16        return r1.centroid.x < r2.centroid.x;
17    }
18    return r1.centroid.y < r2.centroid.y;
19}
20
21float getRand() {
22    return static_cast <float> (rand()) / static_cast <float> (RAND_MAX);
23}
24
25CS248::Vector2D ImageTriangleSample::getPos(int index) {
26    return image_simplifier->getPos(index);
27}
28CS248::Vector2D ImageTriangleSample::getPosA() {
29    return image_simplifier->getPos(a);
30}
31CS248::Vector2D ImageTriangleSample::getPosB() {
32    return image_simplifier->getPos(b);
33}
34CS248::Vector2D ImageTriangleSample::getPosC() {
35    return image_simplifier->getPos(c);
36}
37
38void ImageTriangleSample::setProps() {
39    int numSamples = image_simplifier->getSettings().numSamples;
40    std::vector<CS248::Vector2D> samples;
41    samples.push_back(centroid);
42    CS248::Vector2D p = getPos(a);
43    CS248::Vector2D a_vec = getPos(b) - p;
44    CS248::Vector2D b_vec = getPos(c) - p;
45    CS248::Vector2D avg_chaos = CS248::Vector2D(0,0);
46    float color_r = 0;
47    float color_g = 0;
48    float color_b = 0;
49    float color_a = 0;
50    for (int i = 0; i < numSamples; i++) {
51        float a_rand = getRand();
52        float b_rand = getRand();
53        while (a_rand + b_rand > 1) {
54            a_rand = getRand();
55            b_rand = getRand();
56        }
57        CS248::Vector2D loc = p + a_rand * a_vec + b_rand * b_vec;
58        // loc.x = std::max(0., loc.x);
59        // loc.x = std::min(1., loc.x);
60        // loc.y = std::max(0., loc.y);
61        // loc.y = std::min(1., loc.y);
62        // if (loc.x < 0 || loc.x > 1 || loc.y < 0 || loc.y > 1) {
63        //     std::cout << loc << " " << p << " " << a_vec << " " << b_vec << " " << a_rand << " " << b_rand << std::endl;
64        //     continue;
65        // }
66        samples.push_back(loc);
67    }
68
69    for (CS248::Vector2D &sample : samples) {
70        CS248::Color sample_color = image_simplifier->sample(sample);
71        // std::cout << sample_color.r << std::endl;
72        color_r += sample_color.r * sample_color.a;
73        color_g += sample_color.g * sample_color.a;
74        color_b += sample_color.b * sample_color.a;
75        color_a += sample_color.a;
76    }
77    int len = samples.size();
78    color = CS248::Color(color_r / len, color_g / len, color_b / len, color_a / len);
79    // std::cout << "Final:" << color.r << std::endl;
80    float sd_r = 0;
81    float sd_g = 0;
82    float sd_b = 0;
83    for (CS248::Vector2D &sample : samples) {
84        CS248::Color sample_color = image_simplifier->sample(sample);
85        sd_r += pow(abs(color.r - sample_color.r), 2);
86        sd_g += pow(abs(color.g - sample_color.g), 2);
87        sd_b += pow(abs(color.b - sample_color.b), 2);
88        avg_chaos += sample * (sd_r + sd_g + sd_b) / len;
89    }
90    averageChaos = avg_chaos;
91    benefit = pow(area, settings.areaPriority) * (sqrt(sd_r) + sqrt(sd_g) + sqrt(sd_b)) * (1 + getRand() / settings.numTriangles);
92    // color = sampler->sample_bilinear(tex, centroid.x, centroid.y, 0);
93}
94
95ImageSimplifierSettings ImageSimplifier::getSettings() {
96    return settings;
97}
98
99CS248::Vector2D getRandomInCircle(CS248::Vector2D center, float radius) {
100    float theta = getRand() * PI;
101    float r = getRand() * radius;
102    return center + r * CS248::Vector2D(cos(theta), sin(theta));
103}
104
105CS248::Vector2D getRandomAlongVector(CS248::Vector2D center, CS248::Vector2D dir, float max) {
106    float a = getRand() * max;
107    return center + a * dir;
108}
109
110ImageSimplifier::ImageSimplifier(ImageSimplifierSettings settings,
111                                 CS248::Texture &tex,
112                                 CS248::Sampler2D *sampler) : 
113                                    settings(settings),
114                                    tex(tex),
115                                    sampler(sampler)
116{
117    srand(time(NULL));
118    int b_l = addPos(CS248::Vector2D(0, 0));
119    int t_l = addPos(CS248::Vector2D(0, 1));
120    int b_r = addPos(CS248::Vector2D(1, 0));
121    int t_r = addPos(CS248::Vector2D(1, 1));
122
123    float distance = std::min(settings.amountChaos, 1.f) * 0.25;
124
125    int l_mid = addPos(getRandomAlongVector(CS248::Vector2D(0, 0.5), CS248::Vector2D(0, 1), distance));
126    int t_mid = addPos(getRandomAlongVector(CS248::Vector2D(0.5, 1), CS248::Vector2D(1, 0), distance));
127    int r_mid = addPos(getRandomAlongVector(CS248::Vector2D(1, 0.5), CS248::Vector2D(0, 1), distance));
128    int b_mid = addPos(getRandomAlongVector(CS248::Vector2D(0.5, 0), CS248::Vector2D(1, 0), distance));
129
130    float radius = std::min(settings.amountChaos, 1.f) * 0.1;
131
132    int circ_b_l = addPos(getRandomInCircle(CS248::Vector2D(0.25,0.25), radius));
133    int circ_b_r = addPos(getRandomInCircle(CS248::Vector2D(0.75,0.25), radius));
134    int circ_t_l = addPos(getRandomInCircle(CS248::Vector2D(0.25,0.75), radius));
135    int circ_t_r = addPos(getRandomInCircle(CS248::Vector2D(0.75,0.75), radius));
136
137
138    queue.insert(ImageTriangleSample(b_l, circ_b_l, l_mid, this, settings));
139    queue.insert(ImageTriangleSample(circ_t_l, circ_b_l, l_mid, this, settings));
140    queue.insert(ImageTriangleSample(circ_t_l, t_l, l_mid, this, settings));
141
142    queue.insert(ImageTriangleSample(t_l, circ_t_l, t_mid, this, settings));
143    queue.insert(ImageTriangleSample(circ_t_l, circ_t_r, t_mid, this, settings));
144    queue.insert(ImageTriangleSample(circ_t_r, t_r, t_mid, this, settings));
145
146    queue.insert(ImageTriangleSample(t_r, circ_t_r, r_mid, this, settings));
147    queue.insert(ImageTriangleSample(circ_t_r, circ_b_r, r_mid, this, settings));
148    queue.insert(ImageTriangleSample(circ_b_r, b_r, r_mid, this, settings));
149
150    queue.insert(ImageTriangleSample(b_l, circ_b_l, b_mid, this, settings));
151    queue.insert(ImageTriangleSample(circ_b_l, b_mid, circ_b_r, this, settings));
152    queue.insert(ImageTriangleSample(circ_b_r, b_mid, b_r, this, settings));
153
154    queue.insert(ImageTriangleSample(circ_b_l, circ_b_r, circ_t_l, this, settings));
155    queue.insert(ImageTriangleSample(circ_t_r, circ_b_r, circ_t_l, this, settings));
156}
157
158int ImageSimplifier::getNumTriangles() {
159    return queue.size();
160}
161
162// splits into three
163void ImageSimplifier::subdivideTriangle() {
164    ImageTriangleSample triangle = queue.top();
165    queue.pop();
166
167    CS248::Vector2D a = triangle.getPos(triangle.a);
168    CS248::Vector2D b = triangle.getPos(triangle.b);
169    CS248::Vector2D c = triangle.getPos(triangle.c);
170    CS248::Vector2D mid = triangle.averageChaos;
171    
172    
173    // int ab_mid = addPos(CS248::dot(mid - a, b - a) * (b - a) / (b-a).norm() + a);
174    // int bc_mid = addPos(CS248::dot(mid - b, c - b) * (c - b) / (c-b).norm() + b);
175    // int ca_mid = addPos(CS248::dot(mid - c, a - c) * (a - c) / (a-c).norm() + c);
176
177    int ab_mid = addPos((a+b) / 2);
178    int bc_mid = addPos((b+c) / 2);
179    int ca_mid = addPos((c+a) / 2);
180
181    queue.insert(ImageTriangleSample(triangle.a, ab_mid, ca_mid, this, settings));
182    queue.insert(ImageTriangleSample(triangle.b, bc_mid, ab_mid, this, settings));
183    queue.insert(ImageTriangleSample(triangle.c, ca_mid, bc_mid, this, settings));
184    queue.insert(ImageTriangleSample(ab_mid, bc_mid, ca_mid, this, settings));
185}
186
187//splits into two triangles
188void ImageSimplifier::addTriangle() {
189    ImageTriangleSample triangle = queue.top();
190    queue.pop();
191
192    std::vector<int> orig_corners;
193    orig_corners.push_back(triangle.a);
194    orig_corners.push_back(triangle.b);
195    orig_corners.push_back(triangle.c);
196
197    int i = 0; // index of corner opposing longest side
198    float side2 = (getPos(triangle.b) - getPos(triangle.a)).norm();
199    float side0 = (getPos(triangle.c) - getPos(triangle.b)).norm();
200    float side1 = (getPos(triangle.a) - getPos(triangle.c)).norm();
201
202    if (side1 > side0 && side1 > side2) {
203        i = 1;
204    } else if (side2 > side1 && side2 > side0) {
205        i = 2;
206    }
207    CS248::Vector2D point_a = getPos(orig_corners[(i + 1) % 3]);
208    CS248::Vector2D point_b = getPos(orig_corners[(i + 2) % 3]);
209
210    float weight_a = (triangle.averageChaos - point_a).norm();
211    float weight_b = (triangle.averageChaos - point_b).norm();
212
213    weight_a = pow(weight_a, settings.amountChaos);
214    weight_b = pow(weight_b, settings.amountChaos);
215
216    weight_a = std::min(weight_b * (1 + settings.amountChaos), weight_a);
217    weight_a = std::max(weight_b / (1 + settings.amountChaos), weight_a);
218
219    // CS248::Vector2D diff = triangle.averageChaos - triangle.centroid;
220
221    // float weight_a = CS248::dot(diff, point_a - triangle.centroid);
222    // float weight_b = CS248::dot(diff, point_b - triangle.centroid);
223
224    // float offset = abs(weight_a) + abs(weight_b);
225
226    // weight_a += offset;
227    // weight_b += offset;
228
229    // weight_a = pow(weight_a, settings.amountChaos);
230    // weight_b = pow(weight_b, settings.amountChaos);
231
232    // weight_a = std::min(weight_b * (1 + settings.amountChaos), weight_a);
233    // weight_a = std::max(weight_b / (1 + settings.amountChaos), weight_a);
234
235    int midpoint = addPos((point_a * weight_a + point_b * weight_b) / (weight_a + weight_b));
236
237    queue.insert(ImageTriangleSample(orig_corners[(i + 0) % 3], midpoint, orig_corners[(i + 1) % 3], this, settings));
238
239    queue.insert(ImageTriangleSample(orig_corners[(i + 0) % 3], midpoint, orig_corners[(i + 2) % 3], this, settings));
240}
241
242CS248::Color ImageSimplifier::sample(CS248::Vector2D uv) {
243    return sampler->sample_bilinear(tex, uv.x, uv.y, 0);
244}
245
246ImageTriangleSample ImageSimplifier::popTriangle() {
247    ImageTriangleSample triangle = queue.top();
248    queue.pop();
249    return triangle;
250}
251
252void ImageSimplifier::createPoints() {
253    for (float x = 0.0; x < 1; x += 0.001) {
254        for (float y = 0.0; y < 1; y += 0.001) {
255            int point = addPos(CS248::Vector2D(x,y));
256            queue.insert(ImageTriangleSample(point, point, point,this,settings));
257        }
258    }
259}
260
261void ImageSimplifier::simplify() {
262    while (getNumTriangles() <= settings.numTriangles) {
263      addTriangle();
264        // subdivideTriangle();
265    }
266}