(Dec 26, 2022 작성글. 블로그 이전)
현재 텔레스트레이션 게임 구현을 위해 리액트에서 canvas를 이용해 그림판을 구현 중에 있다. 그림판의 기능으로는 선 그리기, 지우기, 채우기, 초기화, 색상 변경을 목표로 하고 있는데 그 중에서 채우기 기능을 어떻게 구현해야 좋을지 고민이 있었다.
채우기 기능은 moveTo(), lineTo() 등을 이용해 그린 캔버스에서 border가 끊기지 않고 연결된 부분이 있다면 해당 흰색 공간을 선택한 색상으로 채워지는 기능을 의미한다.
getImageData()를 통해 캔버스 내 픽셀 정보를 불러올 수 있다는 사실은 알았지만, 단순히 전체를 탐색해야 하는 것인가? 이건 아닐 것 같은데.. 라는 생각이 들었다. 이에 대한 구현 방법을 찾아보다가 flood fill 이라는 알고리즘을 보게 됐고, 해당 내용을 좀 더 공부해보고 캔버스에 적용해보려고 한다. 아이디어는 stackoverflow 를 참고했다.
사전지식
getImageData()
우선 getImageData()가 어떤 값을 반환하는지 확인이 필요했고,
console.log(getImageData(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);
뭐가 좀 많음을 느껴 찾아봤다.
먼저 해당 함수를 이해하기 위해서 캔버스 내 이미지 개념을 확인할 필요가 있었다.
getImageData(x, y, w, h): ImageData 객체를 리턴하며, data는래스터 정보이다.- 래스터(Raster) : 이미지 내 픽셀 정보로, 래스트 정보는 한 점당 R, G, B, A 요소 각각에 대해 4바이트씩 값을 가지며 이런 픽셀 정보가 좌→우로, 위→아래로 나열된다. (참조 링크)
즉, 우리가 보는 이미지는 2차원 배열이지만 ImageData의 정보는 1차원 배열로 얻게 되고, 일차원 배열의 길이는 w * h * 4임을 알 수 있었다.
이 정보를 알고나니 위에서 CANVAS_WIDTH가 742이고, CANVAS_HEIGHT가 468였기 때문에 배열의 길이가 347,256이 되지 않을까 예상했지만 이보다 4배를 더한 1,389,024의 값이 어떻게 나오게 됐는지 알게 되었다.
flood fill이란?
픽셀 데이터를 어떻게 얻는지를 확인했으니 이제 어떤 식으로 구현해야 좋을지를 봐야한다.
플러드 필(flood fill)에 대한 정의는 다음과 같다. (참조 링크-위키백과)
정의
플러드 필(flood fill) 혹은 시드 필(seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다.
[사용 영역]
- 그림 프로그램에서 연결된 비슷한 색을 가지는 영역에 “채우기” 도구에 사용
- 바둑 등의 게임에서 어떤 비어 있는 칸을 표시할지 결정할 때 사용
알고리즘
플러드 필 알고리즘은 시작 칸, 목표 색, 대체 색의 세 개의 인자를 받는다. 이 알고리즘은 배열에 있는 시작 칸에서 목표 색으로 연결된 모든 칸을 방문해서 대체 색으로 바꾼다. 플러드 필 알고리즘을 구현하는 방법은 여러가지가 있지만, 대부분 큐나 스택과 같은 자료구조를 사용한다. 모서리가 맞닿은 칸이 연결되어 있는 지에 따라서 두 가지 변형이 있다: 각각 4방향과 8방향이다.
이해하고 보니 dfs를 이용해 재귀함수로 구현하거나 bfs로 큐를 이용해 구현하는 방식인 것 같다. 이렇게 생각하니 그냥 백준 단지 채우기였나? 그 문제 풀던 것처럼 생각하면 좋을 것 같다. 오랜만에 그래프 알고리즘을 푼다니.. 설렌다. 단, 조금 더 생각해 볼만한 조건들이 필요하다.
고민거리
1. ImageData를 2D Array로 바꿔서 푸는것?
ImageData의 data가 일차원 배열 형태인데 이를 이차원 배열로 바꿔서 풀면 dfs 알고리즘을 풀듯이 직관적으로 문제 풀이가 가능할 것 같다.
⇒ 처음에 이런 방식을 이용해 구현했는데, 이차원 배열로 바꿨다가 다시 일차원 배열로 만드는 과정에서 오류가 있었고, 결국 1차원 배열을 그대로 사용하는 대신 offset = (y * imageData.width + x) * 4로 계산하여 필요한 픽셀 위치의 인덱스를 찾았다.
2. 각 픽셀이 4칸(rgba)를 갖는 방식이 효율적인가?
한 픽셀이 하나의 값을 가지면 좋겠지만, 쭉 나열된 일차원 배열은 하나의 픽셀이 4칸의 정보를 가지고 있는 형태다. 그렇다면 1) 4칸씩 다시 하나의 배열로 묶어 이용하거나 2) 4칸의 정보를 rgba 값이 아닌 hex로 바꿔놓고 한 픽셀이 한 칸을 갖도록 하는 방식이 있을 것 같다.
⇒ 마지막에 바꾼 imageData를 캔버스에 다시 얹는 과정(putImageData())이 필요해서 hex로 바꾸지 않는 편이 더 효율적이다.
구현
stackoverflow를 참조했다.
1. 캔버스에 클릭한 영역의 좌표와 선택된 색상을 구한다.
const paintCanvas = useCallback(
(event: MouseEvent) => {
if (drawState.current === CanvasState.PAINT) {
const curPos = getCoordinates(event);
if (!curPos) return;
floodFill(curPos.x, curPos.y, curColor.current);
}
},
[drawState],
);추가로 코드에서 선택된 색상이 hex로 다뤄지고 있었고, 색상을 imageData에 적용하기 위해서는 [r,g,b,a] 꼴로 변환하는 과정이 필요해 hex-to-rgba 라이브러리를 이용했다.
2. 캔버스의 imageData 객체의 data 값을 floodfill 시켜준다.
먼저 getImageData()를 이용해 캔버스의 전체 이미지 데이터를 가져오고, 해당 객체의 data 속성을 우리는 floodfill 시켜줘야 한다. 이 과정을 처음에 간단하게 재귀호출을 이용해보았다가 역시 Maximum call stack… 에러를 마주했고, 다시 스택 기반의 iterative 방식으로 구현했다(Iterative stack flood fill).
const floodFill = (x: number, y: number, fillColor: Uint8ClampedArray) => {
const imageData = ctxRef.current.getImageData(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);
const visited = new Uint8Array(imageData.width, imageData.height);
const targetColor = getPixelColor(imageData, x, y);
if (!isSameColor(targetColor, fillColor)) {
// (1)
const stack = [{ x, y }];
while (stack.length > 0) {
const child = stack.pop();
if (!child) return;
const currentColor = getPixelColor(imageData, child.x, child.y); // (2)
if (
!visited[child.y * imageData.width + child.x] &&
isSameColor(currentColor, targetColor) // (3)
) {
setPixel(imageData, child.x, child.y, fillColor); // (4)
visited[child.y * imageData.width + child.x] = 1;
stack.push({ x: child.x + 1, y: child.y });
stack.push({ x: child.x - 1, y: child.y });
stack.push({ x: child.x, y: child.y + 1 });
stack.push({ x: child.x, y: child.y - 1 });
}
}
ctxRef.current.putImageData(imageData, 0, 0); // (5)
}
};아래는 위 코드 내 주석에 대한 설명이다.
(1) targetColor와 fillColor가 달라야 하는 이유
if (!isSameColor(targetColor, fillColor)) { // (1)targetColor: 클릭한 위치의 색상 (색칠될 시작점의 현재 색상)fillColor: 팔레트에서 선택된 색상 (색칠하고자 하는 색상)
이 부분은 없어도 되지만, 같은 색상으로 같은 위치를 여러번 선택하여 불필요하게 실행되는 부분에 대한 방지다. 이미 선택된 색상으로 칠해진 부분을 클릭한다면, floodfill이 실행되지 않아도 된다.
(2) currentColor
const currentColor = getPixelColor(imageData, child.x, child.y); // (2)currentColor: 스택에서 pop() 시킨, 탐색하려는 픽셀의 색상
(3) targetColor와 currentColor가 같은지 비교하는 이유
if (isSameColor(currentColor, targetColor)) { // (3)현재 클릭한 위치의 색상과 같은 색을 가진 부분만을 fillColor로 채운다. 즉, 테두리에 둘러싸인 곳을 클릭한다면 테두리는 색상이 채워지지 않는다.
(4) 색상 칠하기
export const getPixelOffset = (imageData: any, x: number, y: number) => {
return (y * imageData.width + x) * 4;
};const setPixel = (imageData: any, x: number, y: number, color: Uint8ClampedArray) => {
const offset = getPixelOffset(imageData, x, y);
imageData.data[offset + 0] = color[0];
imageData.data[offset + 1] = color[1];
imageData.data[offset + 2] = color[2];
imageData.data[offset + 3] = color[3];
};
setPixel(imageData, child.x, child.y, fillColor); // (4)이제 클릭한 위치 주변으로 색을 칠할 조건을 만족하는 픽셀에 색상을 입혀야 한다. imageData의 data 배열에 참조할 위치의 인덱스를 구해(getPixelOffset()) r, g, b, a 값을 선택된 fillColor로 입혀준다.
(5) 캔버스에 바뀐 이미지데이터를 띄우기
ctxRef.current.putImageData(imageData, 0, 0); // (5)getImageData()로 받아온 imageData의 data를 지금까지 수정했다. 이를 캔버스에 적용하기 위해서는 putImageData()를 이용할 수 있다.
Issues
특정 색이 안채워지는 문제❓
팔레트의 파란색, 노란색, 초록색 등이 안채워지는 문제가 있다. 그외의 팔레트 색상이나 hex 색상 선택기에서 고른 색들은 모두 적용이 잘 된다. 이거는 정말 원인을 모르겠었는데 관련 있을 문제를 찾았다.
같은 색상으로 선을 그리고 색을 칠했는데 칠할 때의 색상이 연하게 출력되는 문제가 있었다.
분명 펜으로 그릴 때와 채우기의 색상을 같이 설정했는데 채우기 색상이 연하게 출력됨을 인지했고, 이것의 원인을 해결하면 모든 색상이 잘 채워질 것이라 생각됐다. 그러고보니 기존에 잘 채워진다고 생각했던 색상들도 연하게 칠해지고 있었다🤯
그래서 rgba 값 중 투명도를 결정하는 알파 값이 문제인 것 같아 색칠하는 함수를 다시 보니 마지막 줄에 color[0]으로 써놨었다 ㅎㅎ 🤯🤯
imageData.data[offset + 3] = color[3]; 로 수정해서 바로 고쳐질 줄 알았는데..
이상하게 색상이 안채워지는 문제가 있었다. imageData.data에 값이 잘못 들어가는 문제는 아니었다. 이 오류를 해결하는데도 시간이 오래 걸렸는데 이것의 원인은 canvas의 ImageData의 data 타입이 Uint8ClampedArray 였기 때문이었다.
📎 ImageData.data는 Uint8ClampedArray형식이며 1차원 배열로 RGBA순서로 정의된 이미지 데이터를 나타낸다. 각 원소는 정수값으로 0에서 255사이의 값을 갖는다.
본래의 rgba 값 중 알파 값은 0~1의 범위를 가지며 0에 가까울 수록 투명하고 1에 가까울수록 원색을 띈다. 그런데 Uint8ClampedArray 타입에서는 이 알파값의 범위가 0~255로 확장되어 사용이 되고, 나는 hex-to-rgba 라이브러리를 써서 색상의 rgba값을 구했기 때문에 마지막 알파값이 0~1 수준으로 나타나는 것이었다. 그래서 결국 화면 상에는 보이지 않았다..😞 이런 문제가 있었다.
그냥 255로 고정할까 했지만 color picker 안에 투명도를 설정할 수 있는 부분이 있어 0~1을 0~255 안의 숫자로 매핑해 주는 부분을 추가했다.
export const convertHexToRgba = (color: string) => {
...
rgba[3] = rgba[3] * 255;
return new Uint8ClampedArray(rgba);
};
이제 다 잘 채워진다 흑
전체 코드
import hexToRgba from 'hex-to-rgba';
const convertHexToRgba = (color: string) => {
const rgbaStr = hexToRgba(color);
const rgba = rgbaStr
.substring(5, rgbaStr.length - 1)
.split(',')
.map((str: string) => Number(str));
rgba[3] = rgba[3] * 255;
return new Uint8ClampedArray(rgba);
};
const isValidSquare = (imageData: any, x: number, y: number) => {
return x >= 0 && x < imageData.width && y >= 0 && y < imageData.height;
};
const getPixelOffset = (imageData: any, x: number, y: number) => {
return (y * imageData.width + x) * 4;
};
const getPixelColor = (imageData: any, x: number, y: number) => {
if (isValidSquare(imageData, x, y)) {
const offset = getPixelOffset(imageData, x, y);
return imageData.data.slice(offset, offset + 4);
} else {
return [-1, -1, -1, -1]; // invalid color
}
};
const isSameColor = (a: Uint8ClampedArray, b: Uint8ClampedArray) => {
return a[0] === b[0] && a[1] === b[1] && a[2] === b[2] && a[3] === b[3];
};
const setPixel = (imageData: any, x: number, y: number, color: Uint8ClampedArray) => {
const offset = (y * imageData.width + x) * 4;
imageData.data[offset + 0] = color[0];
imageData.data[offset + 1] = color[1];
imageData.data[offset + 2] = color[2];
imageData.data[offset + 3] = color[3];
};
const floodFill = (x: number, y: number, fillColor: Uint8ClampedArray) => {
const imageData = ctxRef.current.getImageData(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);
const visited = new Uint8Array(imageData.width, imageData.height);
const targetColor = getPixelColor(imageData, x, y);
if (!isSameColor(targetColor, fillColor)) {
const stack = [{ x, y }];
while (stack.length > 0) {
const child = stack.pop();
if (!child) return;
const currentColor = getPixelColor(imageData, child.x, child.y);
if (
!visited[child.y * imageData.width + child.x] &&
isSameColor(currentColor, targetColor)
) {
setPixel(imageData, child.x, child.y, fillColor);
visited[child.y * imageData.width + child.x] = 1;
stack.push({ x: child.x + 1, y: child.y });
stack.push({ x: child.x - 1, y: child.y });
stack.push({ x: child.x, y: child.y + 1 });
stack.push({ x: child.x, y: child.y - 1 });
}
}
ctxRef.current.putImageData(imageData, 0, 0);
}
};
const paintCanvas = useCallback(
(event: MouseEvent) => {
if (drawState.current === CanvasState.PAINT) {
const curPos = getCoordinates(event);
if (!curPos) return;
floodFill(curPos.x, curPos.y, curColor.current);
}
},
[drawState],
);Optimization
Reference
Flood fill algorithm in javascript - LearnersBucket
Comparing Flood Fill Algorithms in JavaScript - Codeheir
How can I perform flood fill with HTML Canvas?
