塗りつぶしといえばスキャンライン。
名前は知っていても作ったことはありませんでした。
たまたま塗り絵アプリを作ろうとしている学生さんがいましたので、参考まで実装してみました。ちなみに、彼らはUnityで実装しているわけですが。
アルゴリズムの説明はぐぐって調べると以下が見つかりました。絵付きの説明が非常にわかりやすい感じです。
ただ、コードをそのまま実装するのは面倒そうだったので、以下の説明部分だけ参考にさせていもらいました。ありがとうございます。
さて、コードはこんな感じになりました。アルゴリズムはシンプルなのですぐ実装できたのですが、なかなか思うように動いてくれませんでした。数時間くらい試行錯誤することになりましたが。。。動いてしまえばなんとかなりました。
let img;
let q = [];
function preload() {
// img = loadImage('a.jpg');
}
function setup() {
createCanvas(300, 300);
draw_stage();
colorMode(HSB);
}
function is_blank(x, y) {
let c = get(x, y);
return (c[0] == 255 && c[1] == 255 && c[2] == 255); //(x,y)の色が背景色か？
}
function search_left(x, y) {
while(is_blank(--x, y)) {
if (x < 0) break;
}
return x + 1;
}
function search_right(x, y) {
while(is_blank(++x, y)) {
if (x > width) break;
}
return x - 1;
}
function search_line(x1, x2, y) {
let pre = false;
for (let x = x1; x < x2; x++) {
let cur = is_blank(x, y);
if (pre && !cur) {
q.push([x, y]);
}
pre = cur;
}
if (pre) q.push([x2, y]);
}
function draw_stage() {
background(255);
stroke(0);
strokeWeight(3);
for (let i = 0; i < 10; i++) {
noFill();
circle(random(width), random(height), random(100, 200));
}
strokeWeight(1);
// image(img, 0, 0);
}
let c = 0;
function draw() {
if (q.length > 0) {
let x = q[0][0];
let y = q[0][1];
q.splice(0, 1);
let x1 = search_left(x, y);
let x2 = search_right(x, y);
line(x1, y, x2, y);
search_line(x1, x2, y - 1);
search_line(x1, x2, y + 1);
}
}
function mousePressed() {
// f(mouseX, mouseY);
stroke(random(255),255,255);
q.push([mouseX, mouseY]);
}動かすと以下のような感じになります。めっちゃ低速ですが。。。
さて、翌日、暇だったので少し速くならないものかと遊び始めました。アルゴリズムの見直しをしようと思ったのですが（確かに無駄な計算をしていることはよくわかったので）なかなかシンドそう。
もっと効果がありそうなのが、上記のコードでgetしているis_blank関数のところです。背景色かどうかをgetを使って色を取得しているのですが、これが遅いことは知っていました。公式のリファレンスにも「遅いからね」と書かれています。
pixelsというやつでアクセスするようにすれば速くなりそうです。
で、実際にやってみたのが、以下のコードです。
//https://fussy.web.fc2.com/algo/algo3-1.htm
//シードピクセル(X,Y)から左右方向に走査し、塗り潰しの境界を探す(得られた境界の x座標をそれぞれ XL,XRとする)
//水平線分 H(XL,Y)-(XR,Y)を描く
//描画した水平線分 Hの上側の線分 HU(XL,Y + 1)-(XR,Y + 1)を左から走査して、"塗り潰すべきピクセルが横に連続している部分"を全て探し、それぞれの最も右側の座標をバッファに格納する(但し、境界が見つからないうちにウィンドウ右端に達した場合は、ウィンドウ右端の座標をバッファに格納する)
//描画した水平線分 Hの下側の線分 HD(XL,Y - 1)-(XR,Y - 1)に対して上記と同様の処理を行う
//以下、バッファから有効なシードを取り出しては 1～4を繰り返す
//バッファが空になった時点で塗り潰しは完了している
let img;
let q = [];
let d;
let c_r, c_g, c_b;
function preload() {
// img = loadImage('a.jpg');
}
function setup() {
createCanvas(300, 300);
d = pixelDensity();
draw_stage();
}
function is_blank(x, y) {
let p = (4 * d * x) + (y * d) * (4 * d * width);
return (pixels[p] == 255 && pixels[p+1] == 255 && pixels[p+2] == 255); //(x,y)の色が背景色か？
}
function search_left(x, y) {
while(is_blank(--x, y)) {
if (x < 0) break;
}
return x + 1;
}
function search_right(x, y) {
while(is_blank(++x, y)) {
if (x > width) break;
}
return x - 1;
}
function search_line(x1, x2, y) {
let pre = false;
for (let x = x1; x < x2; x++) {
let cur = is_blank(x, y);
if (pre && !cur) {
q.push([x, y]);
}
pre = cur;
}
if (pre) q.push([x2, y]);
}
function draw_stage() {
background(255);
stroke(0);
strokeWeight(3);
for (let i = 0; i < 10; i++) {
noFill();
circle(random(width), random(height), random(100, 200));
}
strokeWeight(1);
// image(img, 0, 0);
}
function draw() {
}
function draw_line(x1, x2, y) {
for (let x = x1; x < x2; x++) {
for (let i = 0; i < d; i++) {
for (let j = 0; j < d; j++) {
let p = 4 * ((y * d + j) * width * d + (x * d + i));
pixels[p] = c_r;
pixels[p + 1] = c_g;
pixels[p + 2] = c_b;
// pixels[p + 3] = c_a;
}
}
}
}
function mousePressed() {
// f(mouseX, mouseY);
c_r = random(255);
c_g = random(255);
c_b = random(255);
q.push([mouseX, mouseY]);
loadPixels();
while (q.length > 0) {
let x = q[0][0];
let y = q[0][1];
q.splice(0, 1);
let x1 = search_left(x, y);
let x2 = search_right(x, y);
draw_line(x1, x2, y);
search_line(x1, x2, y - 1);
search_line(x1, x2, y + 1);
}
updatePixels();
}で、動かしている様子が以下です。断然速いですね。。。
openprocessingのコードも以下においておきます。もし、興味があれば遊んでみてください。
◆改良前
◆改良後
でわ！
