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 (staircase pattern)
  • 이미지를 확대했을 때 계단같은 artifact가 보이는 현상

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

• CMU: COMPUTER GRAPHICS
• 2020 김영민 교수님 그래픽스 프로그래밍 강의자료