ThorVG #1758 이슈를 해결한 과정에 대해 간단히 서술했다. 상세한 내용은 ThorVG #4655를 참고해주시길 바란다.
(사실 완전한 해결은 아니라 과도기적 단계지만, 해결책을 찾기 위해 고민하는 과정에도 의미가 있다고 생각하여 글을 작성했다)
증상
2023년도에 발견된 꽤나 오래된 이슈로, Lottie를 gif로 변환하여 export할 때 팔레트가 이상하게 생성되는 문제였다. 해당 기능에 대한 구현은 tvgGifEncoder.cpp에 있었는데, 대부분의 기능이 gif-h라는 라이브러리로부터 상당 부분을 가져온 것으로 보였다. 하지만 해당 라이브러리가 2024년 7월을 마지막으로 현재는 유지보수가 적극적으로 되고 있지 않았다.
원인 & 해결
두 가지 독립적인 문제가 존재했다.
1. 무조건 절반씩 나누는 구조
문제 인식
tvgGifEncoder.cpp는 팔레트 생성 시 k-d tree와 유사한 구조를 이용하여 이후 탐색 시에도 빠르게 색상을 찾게 하는 구조였는데, 공간을 분할할 때 픽셀 범위와 팔레트 범위 둘 모두를 무조건 절반으로 나누고 있었다.
팔레트 범위를 절반으로 나누는 이유는 깊이 8의 균형 이진 트리를 만들기 위함이며, 이후에 탐색 단계에서 빠르게 주어진 색상 값에 대해 가장 가까운(유사한) 팔레트 색상을 찾기 위한 구조였다.
하지만 픽셀 집합 또한 언제나 절반으로 분할했기 때문에, 분할이 끝난 시점에 하나의 팔레트 엔트리가 대략 numPixels / 256개의 픽셀에 대응되었다. 이보다 적은 픽셀에서 사용되는 색상은 하나의 팔레트 엔트리를 온전히 채울 수 없으며, 다른 색상과 섞여 평균 색상이 팔레트에 들어가게 되었다.
하나의 팔레트 엔트리가 담당하는 픽셀 개수는 엄밀히 말하면
numPixels / 255개. ThorVG의 현재 구현 상 팔레트 엔트리 0이 ‘투명’을 나타내는 용도로 사용되기 때문.
해결
픽셀 집단을 언제나 절반으로 나누는 것 대신, 중앙값에 해당하는 색상을 기준으로 분할하도록 수정했다. 이제 동일한 색상의 픽셀은 서로 다른 하위 트리로 분리되지 않으며, 모든 픽셀이 한 가지 색상으로 구성된 서브트리는 더 이상 분할되지 않고 LEAF_NODE로 표시하여 탐색 단계에서 불필요한 재귀를 하지 않도록 했다.
2. 첫 번째 프레임에 대한 처리 오류
문제 인식
팔레트를 만드는 함수인 _makePalette()는 가장 먼저 현재 프레임에서 팔레트를 생성하기 위해 고려할 픽셀의 개수를 _pickChangedPixels()를 통해 계산한다.
여기서 먼저 알아두어야 할 것이 있는데, tvgGifEncoder.cpp는 배경의 유무에 따라 내보낼 gif의 특수한 데이터 필드인 GCE (Graphics Control Extension)을 설정한다.
fputc((transparent ? 0x09 : 0x05), f); //clear prev frame or not.
0x09는 disposal method 2 (restore to background)로, 매 프레임 모든 내용을 지우고 다시 그린다. 반면 0x05는 disposal method 1 (do not dispose)로, 이전 프레임 내용을 그대로 유지하며, 이번 프레임에선 일정 부분만 덮어쓰는 방식으로 동작한다.
_pickChangedPixels()에서는 픽셀의 alpha 채널이 TRANSPARENT_THRESHOLD보다 낮은 경우를 ‘완전히 투명한 픽셀’로 특수하게 처리하여 팔레트 생성에 참여하지 못하도록 구현되어 있다.
- GIF는 그 특성상 ‘투명’ 또는 ‘비투명’ 둘 중 하나만 표현할 수 있다.
- alpha 채널을 해석하는 가장 간단한 방식이 thresholding이며, 다른 방식도 존재한다.
다만 _pickChangedPixels의 호출부를 보면 아래와 같이 첫 번째 프레임일 때에는 아예 _pickChangedPixels()를 호출하지 않고 있었다.
int numPixels = (int)(width * height);
if (lastFrame) numPixels = _pickChangedPixels(lastFrame, writer->tmpImage, numPixels, transparent);
_pickChangedPixels()에서는 배경이 존재하는 경우 이전 프레임 픽셀과 비교해서 바뀐 개수만을 반환하는 동작을 수행하는데, 첫 프레임에서는 이전 프레임이 존재하지 않으므로 이런 가드를 넣어둔 것으로 보인다. 다만 이것 때문에 적절한 alpha thresholding이 이루어지지 못하고, numPixels는 width * height가 된다. 결과적으로 아무런 필터 없이 모든 픽셀이 팔레트 생성에 참여하게 되어 첫 번째 프레임의 팔레트가 망가진다.
해결
lastFrame 여부와 상관없이 언제나 _pickChangedPixels()를 호출하도록 수정했다. 이제 첫 번째 프레임에서도 alpha 채널이 TRANSPARENT_THRESHOLD보다 낮은 경우를 걸러낼 수 있게 되었다. lastFrame 체크는 _pickChangedPixels() 내부로 이동해주었다.
후기
역시 타인이 작성한 코드를 분석하는 건 쉽지 않다. 특히 문제가 발생했을 때 원인을 특정하는 것은 더더욱. 개선 결과를 더 잘 보여주기 위해 gif 렌더링 결과와 팔레트 덤프 결과를 전/후로 나누어서 PR에 첨부했는데, 좋은 생각이었던 것 같다.
다만 미심쩍은 점이라면, 개선 이후에도 팔레트 덤프 결과를 봤을 때 대부분 엔트리가 중복 색상으로 가득 차 있었다는 것. 중복 엔트리를 줄이면 더 다양한 색상을 나타낼 수 있지 않을까 생각했지만, 일단은 문제가 해결된 것 같아 적절히 끊었다.
하지만 얼마 지나지 않아 아직 해결되지 않은 케이스가 발견되었다. 여전히 몇몇 gif에서는 팔레트 생성이 이상하게 된다는 것. 이번 PR로 어느 정도 개선을 하긴 했지만, 충분히 검증하지 못했던 것 같다.
긍정적인 점은 이미 이 새로운 이슈에 대해서 작업 중이며, 본 글에서 작업한 상당 부분을 재활용할 수 있었다는 점이다.