2
\$\begingroup\$

I first posted this question on stackoverflow and have been indicated that cordereview would be a better place for my question. I have had very good suggestions, such as using RMS for the fitness fonction, using UInt8Arrays and drawing to an invisible canvas.

I have written a javascript program that uses a genetic algorithm to recreate an image only using triangles. Here's the strategy:

  • generate a random pool of models, each model having an array of triangles (3 points and a color)
  • evaluate the fitness of each model. To do so, I compare the original image's pixel array with my model's. I use Cosine Similarity to compare arrays
  • keep the best models, and mate them to create new models
  • randomly mutate some of the models
  • evaluate the new pool and continue

It works quite well after some iterations as you can see here: enter image description here

The problem I have, is that it is very slow, most of the time is spent getting model's pixels (converting list of triangles (color + points) to a pixel array). Here's how I do so now:

My pixel-array is a 1D array, I need to be able to convert x,y coordinates to index:

static getIndex(x, y, width) {
  return 4 * (width * y + x);
}

Then I am able to draw a point:

static plot(x, y, color, img) {
  let idx = this.getIndex(x, y, img.width);

  let added = [color.r, color.g, color.b, map(color.a, 0, 255, 0, 1)];
  let base = [img.pixels[idx], img.pixels[idx + 1], img.pixels[idx + 2], map(img.pixels[idx + 3], 0, 255, 0, 1)];
  let a01 = 1 - (1 - added[3]) * (1 - base[3]);

  img.pixels[idx + 0] = Math.round((added[0] * added[3] / a01) + (base[0] * base[3] * (1 - added[3]) / a01)); // red
  img.pixels[idx + 1] = Math.round((added[1] * added[3] / a01) + (base[1] * base[3] * (1 - added[3]) / a01)); // green
  img.pixels[idx + 2] = Math.round((added[2] * added[3] / a01) + (base[2] * base[3] * (1 - added[3]) / a01)); // blue
  img.pixels[idx + 3] = Math.round(map(a01, 0, 1, 0, 255));
}

Then a line:

 static line(x0, y0, x1, y1, img, color) {
  x0 = Math.round(x0);
  y0 = Math.round(y0);
  x1 = Math.round(x1);
  y1 = Math.round(y1);
  let dx = Math.abs(x1 - x0);
  let dy = Math.abs(y1 - y0);
  let sx = x0 < x1 ? 1 : -1;
  let sy = y0 < y1 ? 1 : -1;
  let err = dx - dy;

  do {
    this.plot(x0, y0, color, img);
    let e2 = 2 * err;
    if (e2 > -dy) {
      err -= dy;
      x0 += sx;
    }
    if (e2 < dx) {
      err += dx;
      y0 += sy;
    }
  } while (x0 != x1 || y0 != y1);
}

And finally, a triangle:

static drawTriangle(triangle, img) {
  for (let i = 0; i < triangle.points.length; i++) {
    let point = triangle.points[i];
    let p1 =
      i === triangle.points.length - 1
        ? triangle.points[0]
        : triangle.points[i + 1];
    this.line(point.x, point.y, p1.x, p1.y, img, triangle.color);
  }
  this.fillTriangle(triangle, img);
}

static fillTriangle(triangle, img) {
  let vertices = Array.from(triangle.points);
  vertices.sort((a, b) => a.y > b.y);
  if (vertices[1].y == vertices[2].y) {
    this.fillBottomFlatTriangle(vertices[0], vertices[1], vertices[2], img, triangle.color);
  } else if (vertices[0].y == vertices[1].y) {
    this.fillTopFlatTriangle(vertices[0], vertices[1], vertices[2], img, triangle.color);
  } else {
    let v4 = {
      x: vertices[0].x + float(vertices[1].y - vertices[0].y) / float(vertices[2].y - vertices[0].y) * (vertices[2].x - vertices[0].x),
    y: vertices[1].y
    };
    this.fillBottomFlatTriangle(vertices[0], vertices[1], v4, img, triangle.color);
    this.fillTopFlatTriangle(vertices[1], v4, vertices[2], img, triangle.color);
  }
}

static fillBottomFlatTriangle(v1, v2, v3, img, color) {
  let invslope1 = (v2.x - v1.x) / (v2.y - v1.y);
  let invslope2 = (v3.x - v1.x) / (v3.y - v1.y);

  let curx1 = v1.x;
  let curx2 = v1.x;

  for (let scanlineY = v1.y; scanlineY <= v2.y; scanlineY++) {
    this.line(curx1, scanlineY, curx2, scanlineY, img, color);
    curx1 += invslope1;
    curx2 += invslope2;
  }
}

static fillTopFlatTriangle(v1, v2, v3, img, color) {
  let invslope1 = (v3.x - v1.x) / (v3.y - v1.y);
  let invslope2 = (v3.x - v2.x) / (v3.y - v2.y);

  let curx1 = v3.x;
  let curx2 = v3.x;

  for (let scanlineY = v3.y; scanlineY > v1.y; scanlineY--) {
    this.line(curx1, scanlineY, curx2, scanlineY, img, color);
    curx1 -= invslope1;
    curx2 -= invslope2;
  }
}

You can see full code here

So, I would like to know:

  • is it possible to optimize this code ?
  • if yes, what would be the best way to do so ? Maybe there is a library doing all of the drawing stuff way better than I did ? Or by using workers ?

Thanks !

\$\endgroup\$
  • \$\begingroup\$ I don't know a much about Javascript, but I can imagine it's not the most efficient language to work with large arrays of pixels. Anyway, you draw the tree vertices of the triangle first, then proceed to fill it. That duplicates a lot of work. Do your triangles not look right without those three lines? The best known polygon filling algorithm does more or less the same thing, filling horizontal lines from one edge to the opposite edge. Note that for these horizontal lines, you can get away with a much simpler line drawing algorithm. \$\endgroup\$ – Cris Luengo Mar 31 '18 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.