KR100719480B1 - 고속의 안티알리아싱 처리 방법 - Google Patents

Abstract

본 발명은 벡터그래픽에 있어서 고속의 안티알리아싱(Anti-aliasing) 처리 방법에 관한 것으로, 더욱 상세하게는 벡터그래픽을 이루는 도형이 각 선분과 겹쳐지는 픽셀을 추출하는 과정에서, 종래와 같이 도형에 의해 겹쳐지는 픽셀 부분에 대한 면적을 계산하지 않고, 픽셀을 여러 서브픽셀로 나눈 뒤 특정 서브픽셀이 도형과 겹쳐지는지를 알아보는 간단한 계산을 수행하고, 하나의 픽셀을 이루는 서브픽셀들 중에서 몇 개가 도형에 겹쳐졌는지 헤아려 픽셀의 색상 강도를 결정함으로써 면적 계산에 따른 곱셈 및 나눗셈 연산 과정을 제거할 수 있어 수학적으로 기술된 도형들을 보다 빠르게 도시할 수 있도록 해주는 고속의 안티알리아싱 처리 방법에 관한 것이다. 본 발명에 의하면 도형의 디스플레이 처리에 따른 보다 빠른 연산이 가능하도록 해주어 시스템 효율을 극대화시킴과 동시에 서비스 품질을 향상시켜 주는 뛰어난 효과가 있다.

디스플레이 장치, 안티알리아싱 알고리즘, 서브픽셀 추출

Description

고속의 안티알리아싱 처리 방법{Fast anti-aliasing method}

도 1 내지 도 4는 일반적인 안티알리아싱 처리 방식을 나타내는 도면,

도 5 내지 도 7은 종래 안티알리아싱 처리 방식의 문제점을 나타내는 도면,

도 8은 본 발명의 일 실시예에 따른 고속 안티알리아싱 방법이 적용된 디스플레이 장치의 구성을 나타내는 기능 블록도,

도 9는 본 발명의 일 실시예에 따른 고속 안티알리아싱 처리 방법을 나타내는 동작 플로우챠트,

도 10 내지 도 12는 도 9의 고속 안티알리아싱 처리 방법에서 제10 단계(S10)를 나타내는 도면,

도 13 내지 도 15는 16 픽셀로 삼각형을 그리는 과정을 나타내는 도면,

도 16 내지 도 35는 도 9의 고속 안티알리아싱 처리 방법에서 픽셀의 좌표, 강도, 커버리지를 기록하는 과정을 나타내는 도면,

도 36은 도 9의 고속 안티알리아싱 처리 방법에서 제20 단계(S20)의 결과값을 나타내는 도면,

도 37는 도 9의 고속 안티알리아싱 처리 방법에서 제30 단계(S30)의 결과값을 나타내는 도면,

<도면의 주요 부분에 대한 부호의 설명>

10 : 연산기 11 : 서브픽셀정보 추출모듈

12 : 서브픽셀정보 정렬모듈 13 : 픽셀색상값 계산모듈

20 : 메모리 21 : 도형정보 저장부

22 : 서브픽셀정보 저장부 23 : 디스플레이 버퍼

30 : 디스플레이부

본 발명은 벡터그래픽에 있어서 고속의 안티알리아싱(anti-aliasing) 처리 방법에 관한 것으로, 더욱 상세하게는 벡터그래픽을 이루는 도형이 각 선분과 겹쳐지는 픽셀을 추출하는 과정에서, 종래와 같이 도형에 의해 겹쳐지는 픽셀 부분에 대한 면적을 계산하지 않고, 픽셀을 여러 서브픽셀로 나눈 뒤 특정 서브픽셀이 도형과 겹쳐지는지를 알아보는 간단한 계산을 수행하고, 하나의 픽셀을 이루는 서브픽셀들 중에서 몇 개가 도형에 겹쳐졌는지 헤아려 픽셀의 색상 강도를 결정함으로써 면적 계산에 따른 곱셈 및 나눗셈 연산 과정을 제거할 수 있어 수학적으로 기술된 도형들을 보다 빠르게 도시할 수 있도록 해주는 고속의 안티알리아싱 처리 방법에 관한 것이다.

주지하다시피, 현대 사회는 컴퓨터, 정보 통신, 전자 통신 산업 및 이와 관련된 기술의 급속한 발전으로 인해, 디스플레이 장치의 이용 가치가 날로 증대되고 있다. 이러한 가운데, 수학적으로 기술된 도형을 실제로 디스플레이 장치에 도시해야 하는 경우가 빈번히 늘어나고 있으며, 이와 관련된 기술들의 개발이 활발히 진행되고 있다.

그런데, 수학적 도형을 디스플레이 장치로 나타낼 때 장치의 특성으로 인하여 영상 왜곡이 유발된다. 예를 들어, 삼각형을 나타내는 경우 도 1과 같이 그려져야 하나, 실제 디스플레이 장치에서는 각 좌표를 픽셀 단위로 지정할 수밖에 없으므로, 도 2와 같이 나타나게 된다. 이러한 현상을 계단 현상이라 하는데, 이를 제거하기 위하여 컴퓨터 그래픽에서는 안티알리아싱 처리를 수행한다. 안티알리아싱 처리란 계단 현상을 일으키는 경계 부분의 픽셀에 대해 밝기 강도를 조절하여 계단 현상을 줄이는 작업을 의미한다. 도 2의 도형에 안티알리아싱 처리를 수행하면, 도 3과 같은 모습으로 보여지게 된다.

이 때, 경계 부분의 픽셀 강도는 실제 수학식으로 표현된 삼각형이 한 픽셀의 몇 퍼센트(%)를 커버하는가로 계산하여 결정하는데, 이를 계산하는 알고리즘을 구역-샘플링(area-sampling)이라 한다. 도 4와 같이 삼각형의 한 경계 부분에 존재하는 픽셀이 있을 때, 이 픽셀의 밝기 강도는 삼각형이 이 픽셀을 덮는 면적을 기반으로 계산되어 표시된다.

한편, 이러한 구역-샘플링(area-sampling) 알고리즘을 적용하기 위해서는 각 픽셀 내에서의 x축과 y축에 대해 삼각형의 선분이 접하는 접점을 찾아야 하고, 면 적 계산을 위해서는 곱셈 연산 등이 필요하기 때문에 많은 컴퓨팅 파워를 요구하게 되는 문제점이 있다. 좌표 "(3, 1), (1, 6), (7, 8)"로 구성된 삼각형을 렌더링하는 경우를 예로 들어 설명한다. 이 때, 수학적인 삼각형은 도 5와 같이 나타낼 수 있는데, 여기에 구역-샘플링을 적용하여 삼각형의 외곽 부분의 픽셀 강도(intensity)를 구하려면 삼각형의 각 선분을 추적하여 선분과 겹쳐지는 경계부분의 픽셀을 찾아내고, 각 픽셀들이 삼각형에 의해 얼마나 덮여지는가를 구하게 된다. 즉, "(3, 1)→(1, 6)"으로 진행하는 선분에 대해서는 도 6에 도시된 면적들을 구하게 되고, 이 때 한 픽셀에서 이루어지는 계산은 도 7와 같으며, 이와 같은 경우 면적은 하기의 [수학식 1]과 같이 계산된다.

( (L1 + L2) * 픽셀높이 ) / 2

이 때, 만일 한 픽셀의 가로, 세로 크기를 "1"이라 하면 도 7의 그림에서 L1과 L2는 1보다 작은 소수점으로 표현되고, 이는 부동소수점 연산이 필요하게 되는 문제점이 있다. 따라서, 실제 대부분의 알고리즘에서는 한 픽셀의 가로, 세로 크기를 예컨대 "256"과 같이 업-스케일링(up-scaling)하여 표현한다. 따라서, 삼각형 좌표 "(3, 1), (1, 6), (7, 8)"은 프로그램이 이를 처리하는 동안 "(3*256, 1*256), (1*256, 6*256), (7*256, 8*256)"으로 업-스케일링하여 이용될 것이다. 그리고, 최종 단계에서 다시 좌표값을 "256"으로 나누는 다운-스케일링(down- scaling)을 처리를 수행하여 원래 값으로 되돌린다. 이 때, "256"을 곱하거나 나누는 식은 8비트를 쉬프트 연산함으로써 매우 빠르게 처리될 수 있다.

하지만, 이러한 식으로 부동소수점 연산을 제거한다 할지라도, 상술한 바와 같이 면적을 구해내는 종래의 구역-샘플링 알고리즘에서는 각 픽셀에서의 X, Y축과 선분이 교차되는 교차점을 구해야 하고, 또한 이를 통해 면적을 계산하는 과정에서 곱셈과 나눗셈이 포함되게 되므로, 결과적으로 많은 시간이 소모될 수밖에 없는 문제점이 있었다.

따라서, 본 발명은 상기와 같은 종래의 문제점을 해결하기 위해 이루어진 것으로서, 본 발명의 목적은 수학적으로 기술된 도형들을 디스플레이 장치에 도시함에 있어, 보다 빠른 도형의 디스플레이가 가능하도록 해주는 고속의 안티알리아싱 처리 방법을 제공하는 데 있다.

상기와 같은 목적을 달성하기 위하여 본 발명의 안티알리아싱 처리 방법은 도형정보 저장부와 서브픽셀정보 저장부와 디스플레이 버퍼를 구비한 디스플레이 장치에 적용하기 위하여, 도형정보 저장부에 저장된 도형 정보를 이용하여 도형의 각 선분을 따라 겹쳐지는 서브픽셀들을 추출하여 서브픽셀정보 저장부에 저장하는 제10 단계(S10); 서브픽셀정보 저장부에 저장된 상기 서브픽셀을 X, Y에 대해 정렬 하는 제20 단계(S20); 및 서브픽셀정보 저장부에 정렬된 서브픽셀을 통해 각 픽셀의 강도를 계산한 후 그 결과값을 디스플레이 버퍼에 저장함으로써 상기 픽셀 강도가 물리적 디스플레이에 반영되도록 하는 제30 단계(S30);를 포함하여 구성된다.

또한, 본 발명의 안티알리아싱 처리 방법에서 상기 제10 단계(S10)는, 도형정보 저장부에 저장된 도형 정보를 이용하여 도형의 선분을 따라 겹쳐지는 서브픽셀을 추출하기 위해 선분을 따라 스캔하면서 서브픽셀의 X-좌표, Y-좌표를 추출하여 서브픽셀정보 저장부에 저장하는 제11 단계(S11)와; 도형정보 저장부에 저장된 도형의 남아 있는 선분이 존재하는지의 여부를 판단하여, 존재하면 제11 단계(S11)로 진행하고, 존재하지 않으면 제20 단계(S20)로 진행하는 제12 단계(S12)를 포함하여 구성된다.

또한, 본 발명의 안티알리아싱 처리 방법은 상기 제11 단계(S11)에서 서브픽셀의 X-좌표값과 Y-좌표값을 서브픽셀정보 저장부에 저장할 때 커버리지 및 강도를 함께 기록하도록 동작한다.

이하, 본 발명의 일 실시예에 의한 고속의 안티알리아싱 처리 방법에 대하여 첨부된 도면을 참조하여 상세히 설명하기로 한다.

도 8은 본 발명의 일 실시예에 따른 고속 안티알리아싱 방법이 적용된 디스플레이 장치의 구성을 나타낸 도면으로, 서브픽셀정보 추출모듈(11)과 서브픽셀정보 정렬모듈(12)과 픽셀색상값 계산모듈(13)을 구비한 연산기(10); 도형정보 저장부(21)와 서브픽셀정보 저장부(22)와 디스플레이 버퍼(23)를 구비한 메모리(20); 그리고 디스플레이부(30)를 포함하여 구성된다.

먼저 연산기(10)의 구성을 설명한다. 서브픽셀정보 추출모듈(11)은 메모리(20)의 도형정보 저장부(21)에 저장된 도형의 좌표 정보를 이용하여 도형의 각 선분을 따라 도형과 겹쳐지는 서브픽셀들을 추출한 후 그 결과값을 서브픽셀정보 저장부(22)에 저장하는 역할을 한다. 서브픽셀정보 정렬모듈(12)은 서브픽셀정보 저장부(22)에 저장된 서브픽셀들을 X, Y 좌표에 대해 정렬하는 역할을 하는데, 이러한 정렬의 일 실시예로서 1차로 Y좌표-오름차순, 2차로 X좌표-오름차순으로 정렬하도록 구성할 수 있다. 픽셀색상값 계산모듈(13)은 서브픽셀정보 저장부(22)에 정렬된 서브픽셀 정보를 통해 각 픽셀의 강도를 계산한 후 그 결과값을 디스플레이 버퍼(21)에 저장함으로써 디스플레이 버퍼(21)의 내용이 물리적 디스플레이부(30)에 반영되도록 하는 역할을 한다.

이어서 메모리(20)의 구성을 설명한다. 도형정보 저장부(21)는 도형에 대한 정보, 즉 도형을 이루는 선분에 대한 정보 또는 베지어커브에 대한 정보를 유지하는 메모리로서, 이 때 베지어커브는 쉽게 선분으로 근사화될 수 있다. 서브픽셀정보 저장부(22)는 도형을 구성하는 선분을 따라 추출된 서브픽셀 좌표들을 유지하는 메모리로서, 본 발명에 따른 안티알리아싱 처리에 관한 알고리즘의 진행단계에서 사용되는 각종 정보 테이블을 추가로 유지한다. 디스플레이 버퍼(23)는 디스플레이부(30)에 도시될 각 픽셀의 강도를 유지하는 메모리이다.

상기와 같은 구성을 갖는 장치에 적용된 본 발명의 고속의 안티알리아싱 처 리 방법의 일 실시예를 도 9를 참조하여 설명한다. 개념적으로, 본 발명에 따른 알고리즘에서는 도형의 각 선분과 겹쳐지는 셀들을 추출하는 과정에서 도형과 겹쳐지는 부분에 대한 면적을 계산하지 않고, 그 대신 하나의 픽셀을 4, 16, 64 또는 256개의 서브픽셀로 나누어 계산을 수행한다.

서브픽셀정보 추출모듈(11)은 도형정보 저장부(21)에 저장된 도형의 좌표 정보를 이용하여, 도형의 각 선분을 따라 도형과 겹쳐지는 서브픽셀을 추출한 후 서브픽셀정보 저장부(22)에 저장한다(S10).

이러한 제10 단계(S10)는 서브픽셀정보 추출모듈(11)이 도형정보 저장부(21)에 저장된 도형 좌표 정보를 이용하여 도형의 선분을 따라 겹쳐지는 서브픽셀을 추출하기 위해 선분을 따라 스캔하면서 서브픽셀의 x, y 좌표를 추출한 후 서브픽셀정보 저장부(22)에 저장하는 제11 단계(S11)와; 서브픽셀정보 추출모듈(11)이 도형정보 저장부(21)에 저장된 도형의 남아 있는 선분이 존재하는지의 여부를 판단하여, 존재하면 다시 제11 단계(S11)로 진행하고, 존재하지 않으면 제20 단계(S20)로 진행하는 제12 단계(S12)를 포함한다.

제20 단계(S20)와 관련하여, 서브픽셀정보 정렬모듈(12)이 서브픽셀정보 저장부(22)에 저장된 서브픽셀들을 X, Y 좌표에 대해 정렬하는 방식은 전술한 바와 같이 선택에 따라 다양하게 설정될 수 있는데, 도 9에서는 이러한 정렬 방식의 일 실시예로서 1차로 Y좌표-오름차순, 2차로 X좌표-오름차순으로 정렬하도록 구성하는 경우에 대해서 도시하였다.

이러한 제10 단계(S10)의 처리 과정에 대해 도 10 ~ 도 35를 참조하여 보다 구체적으로 설명하면 다음과 같다.

도 10은 하나의 픽셀을 16개의 서브픽셀로 나눈 것이고, 이에 대해서 삼각형을 이루는 선분이 어느 서브픽셀과 겹쳐지는지 만을 계산한다. 즉, 선분과 겹쳐지는 면적에 대해서는 계산하지 않는 것이다. 이 때, 하나의 픽셀을 16개의 서브픽셀로 나누는 경우 각 좌표는 "(3*16, 1*16), (1*16, 6*16), (7*16, 8*16)"으로 업-스케일링된다. 여기서, 상기와 같이 16을 곱하는 연산은 4 비트를 쉬프트함으로써 매우 빠르게 처리된다.

도 10에서 선분과 겹쳐지는 서브픽셀을 찾아내면 도 11과 같은 결과를 얻을 수 있다. 이처럼 선분과 겹쳐지는 서브픽셀의 추적에는 예컨대 브레센함 라인드로잉(Bresenham Line Drawing) 알고리즘이나 DDA(Digital Differential Analyzer) 알고리즘이 사용될 수 있다.

도 10의 픽셀 강도를 결정하기 위해서는 도형에 의해 덮여지는 서브픽셀의 개수를 세어야 하는데, 도형에 의해서 덮여지는 서브픽셀은 도 12와 같고, 이것은 도 11에서 구해진 각 서브픽셀 좌표의 하위 4비트를 확인함으로써 알 수 있다. 결국 픽셀 강도는 12/16, 즉 75%로 계산되는 것이다. 이 때, 픽셀을 얼마나 많은 서브픽셀로 나누느냐에 따라 더 높은 퀄리티(quality)를 얻을 수 있는데, 256개의 서브픽셀로 나누는 경우 256 단계의 값을 얻을 수 있고, 이는 매우 고품질의 안티알리아싱 처리를 가능하게 한다.

한편, 하기에서는 16 서브픽셀을 이용하여 도 13과 같은 삼각형을 그리는 과정에 대해 예를 들어 살펴본다.

먼저, 도 14에 도시된 바와 같이 삼각형의 좌표에 대하여 각각 16을 곱셈 연산하여 업-스케일링하는데, 이에 따라 삼각형 좌표는 "(1, 0)→(16, 0), (0, 1)→(0, 16), (2, 2)→(32, 32)"과 같이 변경된다. 그리고, 각 선분을 따라서 도형과 겹쳐지는 서브픽셀을 추적하면서 각 픽셀의 강도(intensity)와 커버리지(coverage)를 기록한다. 이를 위해서는 변형된 라인 드로잉(Line Drawing) 알고리즘, 즉 브레센함 라인드로잉 알고리즘이나 DDA(Digital Differential Analyzer) 알고리즘 등이 사용될 수 있다. 즉, 각 서브픽셀들을 찾으면서 실제 픽셀들에 대한 강도나 커버리지를 기록한다.

이 때, 강도는 아래 방향으로 진행하는 선분과 윗 방향으로 진행하는 선분에 대해 부호가 다르게 기록되고, 커버리지는 선분에 의해 한 픽셀의 높이가 얼마만큼 덮여졌는가를 기록하며, 이 또한 아래 방향으로 진행하는 선분과 윗쪽 방향으로 진행하는 선분에 대해 부호가 다르게 기록된다. 따라서, 각 서브픽셀들을 추적하면 결론적으로 도 15와 같은 서브픽셀들을 찾으면서 강도와 커버리지를 기록하게 되는 것이다.

도 16 ~ 도 35에서는 상술한 계산이 이루어지는 과정을 보이고 있다. 도 16는 첫 번째 테이블 엔트리(Table Entry)가 추가된 모습을 나타내며, 테이블 엔트리가 추가될 때 강도와 커버리지 값은 "0"으로 초기화 한다. 이 때, 선분의 방향이 아래로 진행될 때에는 강도와 커버리지는 음수 값을 갖고, 선분의 방향이 위로 진행될 때에는 강도와 커버리지 값이 양수를 갖는다. (이는 픽셀 색상값 계산 모듈에 서 처리하는 방식에 따라 서로 반대로 기록할 수도 있다. 본 명세서에서는 아래로 진행될 때는 음수를 갖고 위로 진행될 때에는 양수를 갖는 것으로 가정하여 설명하되, 본 발명의 사상은 여기에 한정되지 않는다.)

도 16은 현재 "(16, 0)→(0, 16)"으로 진행중이므로, 강도와 커버리지는 음수 값을 갖는다. 픽셀 내의 같은 서브 Y-스캔라인에 있는 서브픽셀에 대해서는 왼쪽으로부터 각각 "0, 1, 2, 3"의 강도를 가지므로, 따라서 도 16에 표시된 서브픽셀은 한 픽셀 내에서 가장 왼쪽에 위치하므로 강도 "0"이고, 커버리지는 선분의 방향에 따라 항상 "1" 증가하거나 "1" 감소하므로 "-1"이 된다. 도 16에 나타난 서브픽셀에 대한 강도 "0"과 커버리지 "-1"을 테이블에 반영한 결과가 도 16의 테이블에 나타나 있다.

다음으로, 도 17에 나타난 서브픽셀은 픽셀좌표 (0, 0)에 위치하고, 이것은 테이블의 마지막 엔트리 좌표인 (1, 0)과 다르므로 새롭게 엔트리를 추가한다. 이 경우 초기 강도와 커버리지 값은 도 17의 테이블과 같이 "0"으로 초기화 된다. 한편, 도 17에 나타난 서브픽셀의 강도와 커버리지는 "-3"과 "-1"이므로 이를 반영하여 도 17의 테이블과 같은 결과를 얻는다.

도 18의 서브픽셀에 대한 픽셀 좌표는 테이블 엔트리의 마지막 엔트리 좌표와 같으므로 새롭게 엔트리가 추가되지는 않는다. 이 경우 도 18의 테이블과 같이 바로 이전의 테이블 엔트리에 강도와 커버리지 값을 더하게 된다.

도 19와 도 20은 "(16, 0)→(0, 16)"의 마지막 서브픽셀을 나타낸 것이고, 이 경우의 강도와 커버리지 값은 도 20의 테이블과 같다.

도 21은 다음 선분인 "(0, 16)→(32, 32)"로 진행하는 선분에 대한 에지 트래킹(Edge Tracking)을 시작하는 모습을 나타낸다. 이 때, 두 선분이 만나는 지점의 서브픽셀은 항상 두 번 검출되게 되는데, 서브픽셀 (0, 16)은 "(16, 0)→(0, 16)"으로 진행할 때 한번 검출되고(바로 이전 단계에서 기록되었음), "(0, 16)→(32, 32)"로 진행할 때 다시 검출된다. 이렇게 선분이 겹쳐지는 지점의 셀은 만일 선분의 방향이 변하는 경우에는 기록하는 반면에, 선분의 방향이 같은 경우에는 기록하지 않는다. 도 21의 상황에서는 "(16, 0)→(0, 16)"의 방향과 "(0, 16)→(32, 32)"의 방향이 모두 아랫쪽으로 진행하므로 기록하지 않는다.

도 22 ~ 도 24는 "(0, 16)→(32, 32)"에 새로은 테이블 엔트리가 추가되는 모습을 보여주는 것이고, 도 25는 "(0, 16)→(32, 32)"의 마지막 서브픽셀을 나타낸 것이며, 이 경우 강도와 커버리지 값은 도 25의 테이블과 같다.

도 26는 "(32, 32)→(16, 0)"으로 진행하는 선분에 대한 에지 트래킹(edge tracking)을 시작하는 모습을 보여주고 있다. 이 때, 첫 서브 셀인 (32, 32)는 이전 선분인 "(0, 16)→(32, 32)"와 현재의 선분인 "(32, 32)→(16, 0)"의 방향이 서로 반대이므로 도 26의 테이블과 같이 기록한다.

한편, 도 27 ~ 도 33은 "(32, 32)→(16, 0)"에 새로은 테이블 엔트리가 추가되는 모습을 보여주는 것이고, 도 34는 "(32, 32)→(16, 0)"의 마지막 서브픽셀을 나타낸 것이며, 이 경우 강도와 커버리지 값은 도 34의 테이블과 같다. 이 때, 상기에서 가장 첫 번째 서브픽셀을 기록할 것인지는 첫 번째 선분과 가장 마지막 선분의 진행 방향이 같은지 여부에 따라 결정되어야 한다. 상기의 과정에서는 편의 상 이러한 판단 부분을 부분적으로 생략하였다.

상술한 과정에 의해 최종적으로 도 35와 같은 테이블을 얻게 되는데, 이 테이블 값이 메모리(20)의 서브픽셀정보 저장부(22)에 저장되는 것이다.

그런 후, 서브픽셀정보 정렬모듈(12)은 도 36에 나타낸 바와 같이 서브픽셀정보 저장부(22)에 저장된 서브픽셀들을 X, Y 좌표에 대하여 정렬한다(S20). 상기 정렬의 순서는 일반적으로는 1차로 Y좌표-오름차순, 2차로 X좌표-오름차순이 될 것이나, 그림을 그리는 방향(화면의 위에서 아래로 혹은 아래에서 위로)과 각각의 라인을 그리는 방향(화면의 왼쪽에서 오른쪽으로 혹은 오른쪽에서 왼쪽으로)에 따라 달리 선택될 수 있으며, 정렬 방법은 "Quick Sort" 정렬 알고리즘 이나 "Shell Sort" 정렬 알고리즘 등을 사용할 수 있다.

이어서, 픽셀색상값 계산모듈(13)은 동일한 픽셀 좌표들의 강도와 커버리지 값을 합산 한다. 예를 들어 도 36의 테이블에 좌표 값 (1, 0)인 두 개의 테이블 엔트리가 존재하나 이 두 테이블 엔트리의 커버리지 값 및 강도값을 합산하여 도 37에서는 좌표 값 (1, 0)인 엔트리는 하나가 되었다. 픽셀색상 값 계산 모듈을 통해서 이와 같은 과정을 완료하면 도 36 테이블로부터 도 37과 같은 결과를 얻는다. 계속 해서 최종적으로 얻어진 도 37 테이블로부터 픽셀색상값 계산 모듈은 디스플레이 버퍼(23)에 픽셀의 색상 값을 반영함으로써, 디스플레이 버퍼(23)의 내용이 물리적 디스플레이부(30)에 반영되도록 한다(S30). 따라서, 도 37과 같은 정보를 통해 위에서부터 아래로 각 Y-픽셀라인을 적절한 강도로 그리게 되는 것이다.

픽셀색상값 계산모듈(13)이 각 픽셀의 강도를 계산하는 방식에 관하여는 아래에 예시적으로 나타낸 의사 코드(Pseudo Code)를 이용하여 계산 가능하다.

아래에서 테이블(table)이라 명시된 것은 도 37의 테이블을 말하고 While 반복문을 통해서 각 테이블 엔트리의 정보를 액세스하여 Span(스팬-래스터 장치에 그림을 출력하기 위해서 그려야 하는 각 행(row) 이미지)을 그려낸다. 현재 그리고 있는 픽셀의 X 및 Y 좌표는 $CurrX, $CurrY 좌표에 의해서 유지되며 픽셀의 색상 강도는 $C로써 나타내어진다. 그 밖에 $Coverage는 현재 액세스되고 있는 엔트리의 커버리지 값을 유지한다. 아래의 처리과정은 화면의 위에서 아래로 그리고 화면의 왼쪽에서 오른쪽으로 그림을 그리는 것을 가정하나, 이는 구현방법에 따라 그 반대로 구현될 수도 있다. 또한 아래의 코드는 하나의 픽셀을 16개의 서브픽셀로 나눈 경우를 가정한 것이다.

Function Rasterize Select the first element in the table While Current element is not exceed table $CurrY = Current element's Y $Coverage = 0; Do If $Coverage <> 0 $C = -$Coverage * 4 'There are 4 subpixels in row in one pixel $CurrX = $CurrX + 1 While $CurrX < Current element's X Draw pixel at ($CurrX, $CurrY) with $C intensity. $CurrX = $CurrX + 1 End While End If $CurrX = Current element's X $C = -(Current element's intensity) + -$Coverage * 4 Draw pixel at ($CurrX, $CurrY) with $C intensity Select the next element. While $CurrY == Current element's Y; End While End Function

이상에서 몇 가지 실시예를 들어 본 발명을 더욱 상세하게 설명하였으나, 본 발명은 반드시 이러한 실시예로 국한되는 것이 아니고 본 발명의 기술사상을 벗어나지 않는 범위 내에서 다양하게 변형실시될 수 있다.

상술한 바와 같이 본 발명에 의한 안티알리아싱 처리 방법에 의하면, 도형의 각 선분과 겹쳐지는 픽셀을 추출할 때 커버리지 면적을 계산하지 않고 서브픽셀이 선분과 겹쳐지는지 여부만을 판단함으로써 도형의 면적 계산에 따른 곱셈, 나눗셈 연산 과정을 없애주어 수학적으로 기술된 도형을 보다 빠르게 도시할 수 있도록 해주고, 이로 인해 시스템 효율을 극대화시킴과 동시에 서비스 품질을 향상시켜 주는 뛰어난 효과가 있다.

Claims (3)

1. 도형정보 저장부와 서브픽셀정보 저장부와 디스플레이 버퍼를 구비한 디스플레이 장치에 적용하기 위한 안티알리아싱 처리 방법으로,

   도형정보 저장부에 저장된 도형 정보를 이용하여 도형의 각 선분을 따라 겹쳐지는 서브픽셀들을 추출하여 서브픽셀정보 저장부에 저장하는 제10 단계(S10);

   서브픽셀정보 저장부에 저장된 상기 서브픽셀을 X, Y 좌표에 대해 정렬하는 제20 단계(S20); 및

   서브픽셀정보 저장부에 정렬된 서브픽셀을 통해 각 픽셀의 강도를 계산한 후 그 결과값을 디스플레이 버퍼에 저장함으로써 상기 픽셀 강도가 물리적 디스플레이에 반영되도록 하는 제30 단계(S30);

   를 포함하여 구성되는 안티알리아싱 처리 방법.
2. 제 1 항에 있어서,

   상기 제10 단계(S10)는,

   도형정보 저장부에 저장된 도형 정보를 이용하여 도형의 선분을 따라 겹쳐지는 서브픽셀을 추출하기 위해 선분을 따라 스캔하면서 서브픽셀의 X-좌표, Y-좌표를 추출하여 서브픽셀정보 저장부에 저장하는 제11 단계(S11)와;

   도형정보 저장부에 저장된 도형의 남아 있는 선분이 존재하는지의 여부를 판단하여, 존재하면 제11 단계(S11)로 진행하고, 존재하지 않으면 제20 단계(S20)로 진행하는 제12 단계(S12);

   를 포함하여 구성되는 것을 특징으로 하는 안티알리아싱 처리 방법.
3. 제 2 항에 있어서,

   상기 제11 단계(S11)에서 서브픽셀의 X-좌표값과 Y-좌표값을 서브픽셀정보 저장부에 저장할 때 커버리지 및 강도를 함께 기록하는 것을 특징으로 하는 안티알리아싱 처리 방법.

Images