Computer Graphics #01. Drawing triangle: the basics of sampling/anti-aliasing

업데이트:

About Computer Graphics..

Geometry, rendering, animation, imaging, Materials & lighting, VR/AR, mobile GPU, deep learning

  • 김영민 교수님의 컴퓨터 그래픽스 수업을 듣고 요약한 글입니다.

2. Drawing triangle: the basics of sampling/anti-aliasing

Drawing a triangle to a frame buffer

  • Triangle rasterization
    • rasterization
      • 선이나 이미지를 표현하기 위해 어떤 픽셀을 선택하느냐, 즉 물체를 pixel grid로 옮기는 것
      • 각각의 rule에 맞게 픽셀을 선택 ex) diamond rule
        • 어떤 픽셀을 선택하느냐 자체도 computation이 필요하므로 효율적으로 픽셀을 고르는 알고리즘을 사용하는게 중요
      • bresenham line rasterization


2.1 Triangle

  • fundamental primitive
  • most basic polygon
    • 삼각형을 기본으로 하면 더 많은 다각형을 그릴 수 있으며, 내부를 잘 define할 수 있음(늘 평면이어서)
    • basycentric interpolation에 용이

Drawing method

  • point sampling
    • sampling은 graphics의 핵심 아이디어
      • sampling: continuous한 값들 중에서 discrete한 값을 뽑는 것
      • time(1D), area/angle(2D), volume(3D) …
    • function을 정의하려면 특정 point들을 sampling 해야함

    • reconstruction
      • point들을 dense하게 sampling 할수록 reconstruction이 잘됨
      • nearest, linear interpolation 등의 방식으로 recon 가능

  • Rasterization: sampling a 2D indicator function
    • 픽셀의 중앙점을 기준으로 해당 픽셀이 삼각형의 inside에 있는지 outside에 있는지 binary하게 결정하는 방식이 가장 간단하게 삼각형을 색칠하는 방식
    • binary function f(x, y) = inside(try, x, y)

      for(int x =0; x< xmax; x++)
        for(int y =0; y< ymax; y++)
          image[x][y] = f(x + 0.5, y + 0.5)
      


2.2 Evaluating inside

  • triangle = intersection of three half planes

  • normal vector와 내적을 했을 때 음수이면 point가 edge보다 안쪽에 있는 것
   
  • incremental triangle traversal
    • 다음과 같이 모든 픽셀에 대해서 확인을 하는게 아니라 인접한 픽셀에 대해서만 확인하도록 incremental triangle traversal 방식을 사용하면 더 빠르게 computation이 가능

incremental triangle traversal

  • tiled triangle traversal
    • modern graphics에서는 display raster 자체를 block 단위로 tiling하여 전체 block이 inside인지 outside인지 1차적으로 판단을 한 후, 판단이 안된 block들만 따로 뽑아서 다시 판단 (더 빠른 연산 가능)

tiled triangle traversal


2.3 Super-sampling

Jaggies

  • 하나의 픽셀을 여러개로 쪼개는 super-sampling (pre-filtering)을 하여 Jaggie와 같은 문제를 해결
    • 일부는 진하게, 일부는 연하게 이미지가 생성

super-sampling

   

2.4 aliasing

Aliasing Example: 하단으로 갈수록 aliasing 정도가 심해짐

  • aliasing이란?
    • 우리는 original signal이 바뀌는 만큼 sampling을 해야함
    • sampling frequency가 original frequency를 따라가지 못하고 under-sampling 되면 aliasing이라는 문제가 생기게 됨
    • 따라서 anti-aliasing을 통해 sampling한 frequency가 original과 비슷하도록 만들어야 함 !

jaggies

  • 물체를 image grid로 sampling하는 rasterization을 하다보면 jaggie와 같은 artiface가 생기므로 이를 없애는 anti-aliasing을 해야함

  • sampling이 불가능한 high-frequency에 대해 smoothing하게 바꿔주는 Nyquist theorem을 통해 물체를 blurry하게 바꿔준 후(filtering), sampling을 통해 rasterized traingle의 edge를 anti-aliasing 해줌
    • Nyquist theorem: aliasing을 없애려면, Nyquist frequency(=sampling frequency/2)보다 높은 frequency가 없도록 해야함
    • 즉, signal 자체의 high-frequency보다 2배 이상 높은 frequency로 sampling 해야 artifact가 없이 anti-aliasing 해짐

(1) original signal을 보면 하얀색이랑 빨간색으로 나뉘어져 있음 = high-frequency edge가 있다는 뜻

(2) 이를 super sampling으로 dense하게 sampling한 후

(3) 얼마나 많은 점들이 선 안에 영역에 들어갔는지에 따라 색깔을 흐릿하게 만드는.. 그런 방식으로 anti-aliasing을 진행

(3) anti-aliasing by computing average pixel value


Reference

댓글남기기