A script that takes in an image and creates a new image consisting of triangles which roughly resembles the colors in the original image. One use case is lock screens.

Makefile

triangulate: triangulate.cpp
	g++ $< -o $@ -L ../HConLib/lib/ -I ../HConLib/include/ -mavx -std=gnu++17 -lFlatAlg -lOpenImageIO -lHGraf -g -O3

triangulate.cpp

#include <OpenImageIO/imageio.h>

#include <HGraf.hpp>

#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

using namespace OIIO;

struct EdgeSpec {
    // Minimum x, maximum x
    int ind0, ind1;

    // Which triangle does it belong to?
    int triangle;
};

struct PointSpec {
    int ind;
    int triangle;
};

void assign_triangles(std::vector<falg::Vec2>& points,
                      std::vector<hg::TriInd>& inds,
                      std::vector<int>& outs,
                      int w, int h) {
    std::vector<EdgeSpec> edge_specs;
    std::vector<PointSpec> point_specs;
    
    point_specs.reserve(points.size());
    edge_specs.reserve(3 * inds.size());
    for (unsigned int i = 0; i < inds.size(); i++) {

        for (int l = 0; l < 3; l++) {
            int nl = (l + 1) % 3;

            falg::Vec2 vv = points[inds[i].inds[nl]] - points[inds[i].inds[l]];
            
            if (vv.y() <= 0) {
                EdgeSpec es;
                es.ind0 = vv.x() < 0 ? inds[i].inds[nl] : inds[i].inds[l];
                es.ind1 = vv.x() < 0 ? inds[i].inds[l] : inds[i].inds[nl];
                es.triangle = i;


                edge_specs.push_back(es);
            }
        }
    }

    std::sort(edge_specs.begin(), edge_specs.end(),
              [&points](const EdgeSpec& e0, const EdgeSpec& e1) {
                  if (points[e0.ind0].x() == points[e1.ind0].x()) {
                      falg::Vec2 v1 = points[e0.ind1] - points[e0.ind0];
                      falg::Vec2 v2 = points[e1.ind1] - points[e1.ind0];
                      
                      return v1.x() / v1.norm() < v2.x() / v2.norm();
                  } else {
                      return points[e0.ind0].x() < points[e1.ind0].x();
                  }
              });

    for (unsigned int i = 0; i < edge_specs.size(); i++) {
        EdgeSpec& es = edge_specs[i];

        int iout[2][2] = {
            { (int)points[es.ind0].x(), (int)points[es.ind0].y() },
            { (int)points[es.ind1].x(), (int)points[es.ind1].y() },
        };

        {
            int dx = iout[1][0] - iout[0][0];
            int dy = iout[1][1] - iout[0][1];

            int ydir = dy / std::abs(dy);

            int ady = std::abs(dy);
            int ycount = 0;
            int xi = 0;

            if(ady == 0) {
                int cy = std::min(h - 1, std::max(0, iout[0][1]));
                int cx = std::min(w - 1, std::max(0, iout[0][0]));
                outs[cy * w + cx] = es.triangle + 1;
                continue;
            }
            
            for(int yi = 0; std::abs(yi) <= std::abs(dy); yi += ydir) {
                int cy = std::min(h - 1, std::max(0, yi + iout[0][1]));
                int cx = std::min(w - 1, std::max(0, xi + iout[0][0]));
                outs[cy * w + cx] = es.triangle + 1;

                ycount += dx;
                while (ycount > ady) {
                    xi++;
                    ycount -= ady;
                }
            }
        }
    }

    int curr = 0;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            int ind = i * w + j;
            if( outs[ind] != 0) {
                curr = outs[ind];
                curr--;
            }
            outs[ind] = curr;
        }
    }
}

int main(int argc, const char** argv) {

    const int num_points = 1000;

    if(argc < 3) {
        std::cerr << "Usage: ./triangulate <input file> <output file>" << std::endl;
        return -1;
    }
    
    ImageInput* in = ImageInput::open(argv[1]);
    if(!in) {
        std::cerr << "[triangulate] Could not open image file " << argv[1] << std::endl;
        return -1;
    }

    const ImageSpec &spec = in->spec();
    int w = spec.width;
    int h = spec.height;
    int chans = spec.nchannels;

    std::vector<uint8_t> pixels(w * h * 4);
    std::vector<uint8_t> out_pixels(w * h * 4);

    in->read_image(TypeDesc::UINT8, pixels.data());
    in->close();

    if(chans == 3) {
        for(int i = w * h - 1; i >= 0; i--) {
            for(int j = 2; j >= 0; j--) {
                pixels[4 * i + j] = pixels[3 * i + j];
            }
            pixels[4 * i + 3] = 255;
        }
    } else if(chans != 4) {
        std::cerr << "[triangulate] Image did not have 3 or 4 channels" << std::endl;
    }

    
    std::default_random_engine engine(123);
    std::uniform_real_distribution<float> dist_x(0.0f, w);
    std::uniform_real_distribution<float> dist_y(0.0f, h);
    std::uniform_int_distribution<uint8_t> dist_col(0, 255);

    std::vector<falg::Vec2> points(num_points);
    for(unsigned int i = 0; i < points.size(); i++) {
        points[i] = falg::Vec2(dist_x(engine), dist_y(engine));
    }

    hg::DelaunayTriangles deltris = hg::delaunay_triangulation(points,
                                                               0, 0, w, h);

    std::vector<int> tri_ind(w * h);

    std::vector<falg::Vec3> cols(deltris.indices.size());
    for(unsigned int i = 0; i < deltris.indices.size(); i++) {
        cols[i] = falg::Vec3(dist_col(engine), dist_col(engine), dist_col(engine));
    }

    assign_triangles(deltris.points, deltris.indices,
                     tri_ind, w, h);

    for(int i = 0; i < deltris.indices.size(); i++) {
        
        for(int l = 0; l < 3; l++) {
            int nl = (l + 1) % 3;

            hg::drawLineSafe(out_pixels.data(), w, h,
                             deltris.points[deltris.indices[i].inds[l]].x(),
                             deltris.points[deltris.indices[i].inds[l]].y(),
                             deltris.points[deltris.indices[i].inds[nl]].x(),
                             deltris.points[deltris.indices[i].inds[nl]].y(),
                             (255 << 24) | (255 << 8));
        }
    }

    
    // zero-initialized (?)
    std::vector<falg::Vec3> avs(deltris.indices.size(), falg::Vec3(0.0f, 0.0f, 0.0f));
    std::vector<int> nums(deltris.indices.size(), 0);
    

    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            falg::Vec3 vv(pixels[4 * (i * w + j) + 0],
                          pixels[4 * (i * w + j) + 1],
                          pixels[4 * (i * w + j) + 2]);
            
            avs[tri_ind[i * w + j]] += vv;
            nums[tri_ind[i * w + j]]++;
        }
    }

    
    for (unsigned int i = 0; i < deltris.indices.size(); i++) {
        if (nums[i] > 0) {
            avs[i] /= nums[i];
        }
    }

    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            out_pixels[4 * (i * w + j) + 0] = (uint8_t)avs[tri_ind[i * w + j]].x();
            out_pixels[4 * (i * w + j) + 1] = (uint8_t)avs[tri_ind[i * w + j]].y();
            out_pixels[4 * (i * w + j) + 2] = (uint8_t)avs[tri_ind[i * w + j]].z();
            
            out_pixels[4 * (i * w + j) + 3] = 255;
        }
    }

    ImageOutput* out = ImageOutput::create(argv[2]);
    if(!out) {
        std::cerr << "[triangulate] Could not open file " << argv[2] << " for writing" << std::endl;
        return -1;
    }

    ImageSpec out_spec(w, h, 4, TypeDesc::UINT8);
    out->open(argv[2], out_spec);
    out->write_image(TypeDesc::UINT8, out_pixels.data());
    out->close();

    std::cout << "[triangulate] Output written to " << argv[2] << std::endl;

    return 0;
}