컴퓨터 그래픽스의 기본 요소 - 점, 선, 원뿔곡선, 다각형

컴퓨터 그래픽스의 기본 요소

DDA 알고리즘

- Digital Differential Analyzer

- |m|에 따라 기준 축을 정한 후, 기준 축의 좌표가 1만큼 변화할 때 나머지 축 좌표의 변화를 구하여 다음 점의 좌표를 계산

- |m| <= 1 인 경우: x축 좌표를 1씩 변화시킬 때, y축 좌표를 m만큼 변화시켜 다음 점의 좌표를 계산(기울기가 가파른 경우)

- |m| > 1인 경우: y축 좌표를 1씩 변화시킬 때, x축 좌표를 1/m만큼 변화시켜 다음 점의 좌표를 계산(기울기가 완만한 경우)

- 계산된 좌표를 반올림하여 구한 정수 좌표 위치에 점을 그림

​

|Xend - X0| >= |Yend - y0|

- 완만한 경우, x의 이동을 기준

- Xk+1 = Xl + 1, Yk+1 = Yk + m

​

|Xend - x0| < |Yend - Y0|

- 가파른 경우, y의 이동을 기준

- Yk+1 = Yl + 1, Xk+1 = Xk + 1/m

​

/// <summary>
/// DDA 알고리즘
/// x0 != xEnd 이며 y0 != yEnd 라고 가정
/// </summary>void DDA(int x0, int y0, int xEnd, int yEnd) {
    int dx = xEnd - x0, dy = yEnd - y0, steps, k;
    float xIncrement, yIncrement, x = x0, y = y0;

    if (abs(dx) > abs(dy)) steps = abs(dx);
    else                   steps = abs(dy);

    xIncrement = float(dx) / steps;
    yIncrement = float(dy) / steps;

    setPixel(round(x), round(y));
    for (k = 0; k < steps; k++) {
        x += xIncrement;
        y += yIncrement;
        setPixel(round(x), round(y));
    }
}

 

특성

기울기 값에 따라 한 축의 좌표는 1, 다른 축의 좌표는 m(또는 1/m)만큼 변화시키며 다음 좌표를 계산하여 가장 가까운 정수좌표에 해당하는 픽셀을 그림

​

문제점

부동소수점 계산을 해야 함(시간이 많이 소비됨)

긴 선분의 경우 부동소수점 연산의 오차가 누적되어 정확한 직선 경로를 벗어날 수 있음

​

Bresenham의 직선 알고리즘

- DDA알고리즘의 부동소수점 문제를 개선한 알고리즘

- 기울기가 0과 1 사이인 직선을 가정

- 기울기가 0과 1 사이에 해당하지 않는 경우, 0과 1사이에 있는것처럼 변환을 하여 연산

- 아래 정리에서는 기울기가 0과 1 사이인 경우만 생각

- 다음에 그릴 픽셀의 y위치를 계산된 y값이 중간값(0.5)에 해당하는지 판단하여 Yk에 그릴지, Yk+1에 그릴지 선택(중간점 선분 그리기 알고리즘)

- 직선의 방정식을 이용하여 계산

​

Xk+1 = Xk + 1

Yk+1 = Yk or Yk+1 (기울기가 0과 1 사이이기 때문)

​

판별식

직선의 방정식을 이용해서 구함

중간점을 아래 판별식에 대입하여 다음의 y좌표 값을 구함

이전 단계에서 사용한 판별식을 이용하여 계산을 최소화함

F(x,y) = -2W(Y-Yl) + 2H(X - Xl)

F(x,y) < 0 -> (x,y)가 직선의 위에 있음F(x,y) > 0 -> (x,y)가 직선의 아래에 있음

​

 

void bresenham_line(int xl, int yl, int xr, int yr) {
// 0 < H/W < 1 이라고 가정int x, y = yl, W = xr - xl, H = yr - yl;
    int F = 2 * H - W, dF1 = 2 * H, dF2 = 2 * (H - W);

    for (x = xl; x <= xr; x++) {
        setPixel(x, y);
        if (F < 0) F += dF1;
        else { y++; F += dF2; }
    }
}

 

원뿔곡선(conic sections)

두 개의 원뿔을 하나의 평면으로 잘랐을때 보여지는 단면의 형태

원, 타원, 포물선, 쌍곡선

​

원의 방정식

중심이(x_c, y_c), 반경이 r인 원

(x-x_c)^2 + (y-y_c)^2 = r^2

​

타원의 방정식

두 초점으로부터의 거리의 합이 일정한 점들의 집합

장축과 단축이 좌표축에 정렬된 방향으로 놓인 경우1=(x-x_c/r_x)^2 + (y-y_c/r_y)^2

​

포물선의 방정식

한 점(초점)과 하나의 직선(준선)과의 거리가 동일한 점들의 집합

y = ax^2 + bx + c

y = a(x-m)^2 + n

​

쌍곡선의 방정식

두 점으로부터의 거리의 차가 일정한 점들의 집합으로 구성된 곡선

중심이 원점에 존재하며 횡단축이 x축과 일치하는 쌍곡선

(x/r_x)^2 - (y/r_y)^2 = 1

​

원의 방정식

원은 어느 부분에서는 기울기가 가파르고, 어느 부분에서는 완만하기 때문에 이전에 사용한 직선의 방정식을 이용하기 어려움

원의 대칭 속성을 이용하여 연산을 최소화

​

원주 상의 좌표 계산

중심 좌표가 (0,0)인 원의 좌표들을 구한 후 (x_c, x_y)를 더하여 실제 좌표들을 구함

단위 x좌표 변화(즉, dx = 1)에 대한 y좌표 변화 크기가 1보다 작은 구간에서 원주상의 좌표를 구함. x=0 부터 x=y가 되는 구간

이렇게 구한 45도 구간((0,y)~(x,y))을 활용하여 대칭성을 이용하여 나머지 구간의 픽셀을 구함

​

판별 함수

x^2 + y^2 < r^2 -> 원 내부의 점

x^2 + y^2 = r^2 -> 원주 상의 점

x^2 + y^2 > r^2 -> 원 외부의 점

 

void bresenham_circle(int xc, int yc, int radius) {
    int F = 1 - radius;
    int x = 0;
    int y = radius;

    circlepoint(xc, yc, x, y);// 45도 간격으로 8포인트에 점을 그리는 함수while (y > x) {
        if (F < 0) F += x * 2 + 3;
        else { F += (x - y) * 2 + 5; y--; }
        x++;
        circlepoint(xc, yc, x, y);
    }
}

 

다각형 그리기

다각형?

세 개 이상의 선분으로 둘러싸인 평면 도형

단순 다각형: 다각형의 변들이 꼭짓점에서만 만나는 다각형

볼록(convex) 다각형: 모든 내각들이 180도 이하인 다각형

오목(concave) 다각형: 볼록 다각형이 아닌 다각형

CW 또는 CCW 알고리즘을 활용하여 볼록 다각형인지 판별함. CCW의 방향이 모두 동일하다면 볼록 다각형

(앞으로 오른손 법칙을 이용하여 외적의 결과 벡터의 방향을 정할 것)

​

다각형의 앞면과 뒷면

다각형을 이루는 버텍스가 ccw, cw 방향에서 앞면으로 할 것인지 결정

ccw가 앞면으로 결정된 경우 cw방향인 경우 뒷면

이를 이용하여 뒷면인 오브젝트를 그리지 않아 성능 최적화를 노림

​

홀-짝 규칙(내부/외부 검사)

판별하고자 하는 점으로부터 다각형 외부의 점을 잇는 선과 다각형의 변이 교차하는 횟수가 홀수면 내부, 짝수면 외부로 판단

​

OpenGL의 다각형 그리기

4.x의 opengl에서는 삼각형그리기만 지원. 시계 반대방향 순서

GL_TRIANGLES: 3개의 버텍스를 짝지어 삼각형을 그림

GL_TRIANGLE_STRIP: 우선 3개의 버텍스를 묶어 하나의 삼각형을 그림. 이후 처음 버텍스만 제외하고 남은 2버텍스를 재활용하여 계속해서 다음 삼각형을 그려나감

GL_TRIANGLE_FAN: 가장 처음의 버텍스를 공용 버텍스로 삼아 삼각형을 그려나감. 공용 버텍스를 제외하고 2개의 버텍스를 선택해나가며 삼각형을 그려나가는데, 이 2개중 나중에 사용한 버텍스를 재활용하여 삼각형을 그림

​

OpenGL에서 삼각형을 사용하는 이유

삼각형은 무조건 평면이라 취급하기 쉽다.

삼각형은 무조건 볼록하기 때문에 취급하기가 쉽다.