컴퓨터그래픽스 기본요소

Transcription

1 Video & Image VIPLProcessing Lab Myoung-Jin Kim, Ph.D.

2 목차 1 점그리기 2 선그리기 3 원그리기 4 다각형그리기

3 점그리기 점 하나의좌표로표현되는기하요소 y 3 차원그래픽스에서는기본적으로 50 x, y, z 의세좌표축으로표현되는 3 차원직교좌표계를사용하여 점의좌표를표현함 x X 와 y 축으로표현되는 2 차원 평면은 z 축의값이 0 인 3 차원 좌표로볼수있음 z

4 OpenGL - 꼭짓점지정 glvertex* 함수 void glvertex*( 좌표 ); * : 접미사코드 첫째 둘째 2, 3, 또는 4 : 좌표공간의차원 OpenGL 에서는기본적으로 3 차원을사용하지만, 2 차원인경우 z 좌표를 0 으로계산함 4 차원은동차좌표계로기하변환에서사용 i(integer), s(short), f(float), d(double) 셋째 v : 배열형태 (vector) 의좌표지정 교재관련부분 : 66 쪽

5 OpenGL - 꼭짓점지정 glvertex* 함수 void glvertex*( 좌표 ); 예 glvertex2i(50, 100); glvertex3f(50.0f, 100.0f, 0.0f); glvertex4d(50.0, 100.0, 0.0, 1.0); GLint point[ ] = {50, 100}; glvertex2iv(point); 교재관련부분 : 66 쪽

6 OpenGL - 점그리기 glvertex* 함수로좌표위치지정 glbegin 함수와 glend 함수사이에좌표를나열 void glbegin(glenum mode); void glend(void); mode : 그리고자하는도형을나타내는상수 GL_POINT, GL_LINES, GL_LINE_STRIP, GL_LINE_LOOP, GL_TRIANGLES, GL_TRIANGLE_STRIP, GL_TRIANGLE_FAN, GL_QUADS, GL_QUAD_STRIP, GL_POLYGON 점그리기에서는 glbegin 함수에 GL_POINTS 상수를입력 교재관련부분 : 67 쪽

7 OpenGL - 점그리기 예 glbegin(gl_points); glvertex2i(50, 100); glend( ); y 200 GLint p[3][2] = {{50, 100}, {75, 150}, {100, 200}}; glbegin(gl_points); glvertex2iv(p[0]); glvertex2iv(p[1]); glvertex2iv(p[2]); glend( ); x 교재관련부분 : 66~68 쪽

8 OpenGL - 점크기지정 glpointsize 함수 void glpointsize(glfloat psize); psize : 점의직경, 디폴트는 1.0 glbegin 과 glend 내부에넣으면안됨 예 glpointsize(5.0); glbegin(gl_points); glvertex2f(100, 150); glend( ); 교재관련부분 : 66~68 쪽

9 목차 점그리기 선그리기 원그리기 4 다각형그리기

10 OpenGL - 직선그리기 glbegin 함수와 glend 함수사이에 glvertex* 함수로양끝점좌표위치지정끝점을연결하는세가지방법중하나를 glbegin에서지정 GL_LINES : 나열된끝점들을두개씩짝을지어선분을그림 GL_LINE_STRIP : 나열된점들을계속연결하여다중선을그림 GL_LINE_LOOP : 나열된점들을계속연결하여닫힌다중선을그림 교재관련부분 : 68~69 쪽

11 OpenGL - 직선그리기 예 glbegin(gl_lines); glvertex2iv(p1); glvertex2iv(p2); glvertex2iv(p3); glvertex2iv(p4); glvertex2iv(p5); glend( ); p5 p2 p3 p4 p1 교재관련부분 : 68~69 쪽

12 OpenGL - 직선그리기 예 glbegin(gl_line_strip); glvertex2iv(p1); glvertex2iv(p2); glvertex2iv(p3); glvertex2iv(p4); glvertex2iv(p5); glend( ); p5 p2 p3 p4 p1 교재관련부분 : 68~69 쪽

13 OpenGL - 직선그리기 예 glbegin(gl_line_loop); glvertex2iv(p1); glvertex2iv(p2); glvertex2iv(p3); glvertex2iv(p4); glvertex2iv(p5); glend( ); p5 p2 p3 p4 p1 교재관련부분 : 68~69 쪽

14 직선방정식 기울기 - 절편방정식 y y = m x + b y 2 y 1 m = y 2 - y 1 x 2 - x 1 b O x 1 x 2 x y = m x x = y / m 교재관련부분 : 71 쪽

15 DDA 알고리듬 DDA 알고리듬개요 Digital Differential Analyzer 한축의좌표를 1씩변화시킬때, 다른축의좌표를직선의기울기 ( 또는기울기의역수 ) 만큼변화시켜다음점의좌표계산 기울기 ( 또는기울기의역수 ) 의절대값이 1 이하가되게기준축을정함 계산된좌표를반올림하여구한정수좌표위치에점을그림 교재관련부분 : 71~73 쪽

16 DDA 알고리듬 y y y end y = m x + b y end Δy = 1 y = m x + b y 0 x 0 Δx = 1 x end x y 0 x 0 x end x x end -x 0 y end -y 0 x k+1 = x k + 1 y k+1 = y k + m x end -x 0 < y end -y 0 y k+1 = y k + 1 x k+1 = x k + 1/m 실수좌표가발생 실수좌표가발생 (x k+1, Round(y k+1 )) (Round(x k+1 ), y k+1 ) 교재관련부분 : 71~73 쪽

17 DDA 알고리듬 #define round(x) (int((x) >= 0? (x)+0.5 : (x)-0.5)) void DDA(int x0, int y0, int xend, int yend) { //Assume (x0, y0) (xend, yend) y int dx = xend - x0, dy = yend - y0, steps, k; float xincrement, yincrement, x = x0, y = y0; } if (abs(dx) > abs(dy)) else steps = abs(dx); steps = abs(dy); xincrement = float (dx) / float (steps); yincrement = float (dy) / float (steps); setpixel(round(x), round(y)); for (k = 0; k < steps ; k++) { x += xincrement; y += yincrement; setpixel(round(x), round(y)); } steps steps void setpixel(glint x, GLint y) { glbegin(gl_points); glvertex2i(x, y); glend(); } x 교재관련부분 : 73 쪽

18 DDA 알고리듬 DDA 알고리듬의특성 기울기의크기에따라한축의좌표는 1, 다른축의좌표는 m 또는 1/m만큼변화시키며다음좌표를계산하여가장가까운픽셀을그림 문제점 부동소수점계산을해야함 반올림및부동소수점연산으로시간이많이소비됨 긴선분의경우부동소수점연산의오차가누적되어정확한직선경로를벗어날수있음 교재관련부분 : 73 쪽

19 Bresenham 의직선알고리듬 기울기가 0 과 1 사이인직선 k 번째점 (x k, y k ) y k +2 y k +1 y k?? k+1 번째점 (x k+1, y k+1 ) x k+1 = x k +1 x k x k +3 x k +2 x k +1 y k y k+1 =? yk +1 중간점알고리즘 (midpoint algorithm) 교재관련부분 : 73 쪽

20 Bresenham 의직선알고리듬 y (x r, y r ) 기울기가 0 과 1 사이인직선 (x l, y l ) 선분 (x l, y l ) - (x r, y r ) x y k +2 y k +1 y k P k?? x k+1 x k U k+1 M k+1 L k+1 x k+3 x k+2 H H y = x + y l - x W W l y l = y = H W W = x r - x l H = y r - y l H W x l + b x + b x 에 x l, y 에 y l 을넣어 b 를계산 b = y l - H W 교재관련부분 : 74 쪽 x l

21 Bresenham 의직선알고리듬 기울기가 0 과 1 사이인직선 선분 (x l, y l ) - (x r, y r ) y k +2 y k +1 y k P k?? U k+1 L k+1 x k+3 x k+2 x k+1 x k H H y = x + y l - x W W l M k+1 H H y > x + y l - x W W l (x, y) 가직선위에있음 H H y < x + y l - x W W l (x, y) 가직선아래에있음

22 Bresenham 의직선알고리듬 기울기가 0 과 1 사이인직선 y k +2 y k +1 y k P k?? U k+1 M k+1 L k+1 x k+3 x k+2 x k+1 x k 선분 (x l, y l ) - (x r, y r ) H H y > x + y l - x W W l H H -y + x + y l - x l < 0 W W 양변에 w 를곱한다 -Wy + Hx + Wy l Hx l < 0 양변에 2 를곱한다 -2Wy + 2Hx + 2Wy l 2Hx l < 0 F(x, y) = -2W(y - y l ) + 2H(x - x l ) < 0 > 0 (x, y) 가직선위에있음 (x, y) 가직선아래에있음

23 Bresenham 의직선알고리듬 기울기가 0 과 1 사이인직선 선분 (x l, y l ) - (x r, y r ) y k +2 y k +1 y k P k?? U k+1 M k+1 L k+1 x k+3 x k+2 x k+1 x k H H y > x + y l - x W W l (x, y) 가직선위에있음 H H y < x + y l - x W W l (x, y) 가직선아래에있음 F(M k+1 ) < 0 > 0 M k+1 이직선위에있음 M k+1 이직선아래에있음 P k+1 = L k+1 = (x k +1, y k ) P k+1 = U k+1 = (x k +1, y k +1) 교재관련부분 : 74~75 쪽

24 Bresenham 의직선알고리듬 (x k+1, y k+1 ) 을결정하기위한판별식 M k+1 = (x k +1, y k +0.5) F(M k+1 ) = -2W(y k y l ) + 2H(x k x l ) 다음위치를계산하기위한정수형판별식 (x k+2, y k+2 ) 를결정하기위한판별식 F(M k+1 ) < 0 인경우 1 M k+2 = (x k +2, y k +0.5) F(M k+2 ) = -2W(y k y l ) + 2H(x k x l ) = F(M k+1 ) + 2H y k +2 y k +1 y k 이전수식에정수값만더한다 P k? x k P k+1? U k+2 M k+2 L k+2 x k +3 x k +2 x k +1 교재관련부분 : 74~75 쪽

25 Bresenham 의직선알고리듬 (x k+1, y k+1 ) 을결정하기위한판별식 M k+1 = (x k +1, y k +0.5) F(M k+1 ) = -2W(y k y l ) + 2H(x k x l ) (x k+2, y k+2 ) 를결정하기위한판별식 F(M k+1 ) > 0 인경우 2 M k+2 = (x k +2, y k +1.5) F(M k+2 ) = -2W(y k y l ) + 2H(x k x l ) = F(M k+1 ) + 2(H - W) y k +2 y k +1 y k P k+1 L k+2 P k x k?? x k +2 x k +1 U k+2 M k+2 x k +3 교재관련부분 : 74~75 쪽

26 Bresenham 의직선알고리듬 판별식의초기값 F(M 1 ) M 1 = (x l +1, y l +0.5) F(M 1 ) = -2W(y l y l ) + 2H(x l x l ) = 2H W 다음픽셀위치의결정및판별식갱신 F < 0 인경우 F > 0 인경우 (x k+1, y k ) 위치에점을그림 F F + 2H (x k +1, y k +1) 위치에점을그림 F F + 2(H - W) 교재관련부분 : 74~75 쪽

27 Bresenham 의직선알고리듬 예 : (1, 1) (6, 4) W = 5, H = 3 F = 2H W = 1 F < 0 : F F + 6, y k+1 = y k 2H F 0 : F F - 4, y k+1 = y k + 1 2(H-W) k F (x k+1, y k+1 ) 1 (2, 2) -3 (3, 2) 3 (4, 3) -1 (5, 3) 5 (6, 4) 교재관련부분 : 74~75 쪽

28 Bresenham 의직선알고리듬 void bresenham_line (int xl, int yl, int xr, int yr) { // Assume 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; } } 교재관련부분 : 75~76 쪽

29 목차 점그리기 선그리기 원그리기 4 다각형그리기

30 원뿔곡선 (conic sections) 원, 타원포물선쌍곡선

31 원뿔곡선 (conic sections) 원뿔곡선의방정식 Ax 2 + Bxy + Cy 2 + Dx + Ey + F = 0 A, B, C 중최소한하나는 0 이아님 B 2-4AC < 0 타원또는원 (A=C 이고 B=0 인경우 ) B 2-4AC = 0 B 2-4AC > 0 포물선 쌍곡선

32 원뿔곡선 (conic sections) 원의방정식 중심이 (x c, y c ), 반경이 r 인원 (x - x c ) 2 + (y - y c ) 2 = r 2 y r (x c, y c ) (x, y) (y-y c ) (x-x c ) x

33 원뿔곡선 (conic sections) 타원의방정식 장축과단축이좌표축에정렬된방향에놓인경우 x - x c r x 2 + y - y c r y 2 = 1 (-x, y) y r y r y (x, y) 타원의방정식 (-x, -y) r x x (x, -y) x c = 0, y c = 0 인타원 대칭

34 원뿔곡선 (conic sections) 포물선의방정식 준선이 x 축과평행한경우 y = ax 2 + bx + c y y = a(x - m) 2 + n 초점 최소점 (m, n) 준선 x

35 원뿔곡선 (conic sections) 쌍곡선의방정식 준선이 y 축과평행한경우 x r x 2 - y r y 2 = 1 초점 y x 준선

36 원의방정식 데카르트좌표계에서원의방정식 y 실수연산 r (x, y) (x - x c ) 2 + (y - y c ) 2 = r 2 y c r x c x 의범위 r x y = y r 2 - (x - x c ) 2 c ± x c - r x x c + r (y - y c ) 2 = r 2 - (x - x c ) 2 y - y r 2 - (x - x c ) 2 c =

37 원의방정식 극좌표를이용한원의방정식 y (x, y) 실수연산 y c r r cos r sin x = x c + r cos y = y c + r sin x c x

38 중간점원그리기알고리듬 원주상의좌표계산 y y c y x c x y x=y r 원의대칭성이용 45 x x 중심좌표가 (0, 0) 인원의좌표들을구한후 (x c, y c ) 를더하여실제좌표들을구함 단위 x좌표변화 ( 즉, x=1) 에대한 y좌표변화크기가 1보다작은구간에서원주상의좌표를구함 x=0부터 x=y가되는구간

39 중간점원그리기알고리듬 원의대칭성을이용한좌표계산 (-x, y) (-y, x) (-y, -x) (-x, -y) 45 (x, y) (x, -y) (y, x) (y, -x) void circlepoints (int xc, int yc, int x, int y) { setpixel(xc+x, yc+y); setpixel(xc-x, yc+y); setpixel(xc+x, yc-y); setpixel(xc-x, yc-y); setpixel(xc+y, yc+x); setpixel(xc-y, yc+x); setpixel(xc+y, yc-x); setpixel(xc-y, yc-x); }

40 중간점원그리기알고리듬 판별함수 x 2 + y 2 > r 2 x 2 + y 2 < r 2 x 2 + y 2 = r 2 P k U k+1 y k? M y k -1? k+1 y k -2 L k+1 F(x, y) = x 2 + y 2 - r 2 x k x k +3 x k +2 x k +1 F(x, y) < 0, 원내부 = 0, 원경계 > 0, 원외부

41 중간점원그리기알고리듬 판별함수값에따른다음좌표결정 P k U k+1 y k? M y k -1? k+1 y k -2 L k+1 P k U k+1 y k? M y k -1? k+1 y k -2 L k+1 x k +3 x k +2 x k +1 x k x k +3 x k +2 x k +1 x k F(M k+1 ) < 0 인경우 P k+1 = U k+1 = (x k +1, y k ) F(M k+1 ) > 0 인경우 P k+1 = L k+1 = (x k +1, y k -1)

42 중간점원그리기알고리듬 (x k+1, y k+1 ) 을결정하기위한판별식 M k+1 = (x k +1, y k -0.5) F(M k+1 ) = (x k +1) 2 + (y k -0.5) 2 - r 2 (x k+2, y k+2 ) 를결정하기위한판별식 F(M k+1 ) < 0 인경우 M k+2 = (x k + 2, y k - 0.5) F(M k+2 ) = F(M k+1 ) + 2x k + 3 y k -1 y k -2 y k P k P k+1?? U k+2 M k+2 L k+2 x k +3 x k +2 x k +1 x k

43 중간점원그리기알고리듬 (x k+1, y k+1 ) 을결정하기위한판별식 M k+1 = (x k +1, y k -0.5) F(M k+1 ) = (x k +1) 2 + (y k -0.5) 2 - r 2 (x k+2, y k+2 ) 를결정하기위한판별식 F(M k+1 ) > 0 인경우 M k+2 = (x k + 2, y k - 1.5) F(M k+2 ) = F(M k+1 ) + 2x k - 2y k + 5 y k -1 y k -2 y k P k U k+2 P k+1 x k? M L k+2 k+2? x k +2 x k +1 x k +3

44 중간점원그리기알고리듬 P 0 판별식의초기값 F(M 1 ) P 0 = (0, r), M 1 = (1, r - 0.5) F(M 1 ) = (r - 0.5) 2 - r 2 = r 1 - r 0.25 는판별식의부호를결정하는데영향을주지않음 다음픽셀위치의결정및판별식갱신 F < 0인경우 (x k+1, y k ) 위치에점을그림 F F + 2x k + 3 중심좌표및반경이모두정수인경우 F > 0 인경우 (x k +1, y k -1) 위치에점을그림 F F + 2x k - 2y k + 5

45 중간점원그리기알고리듬 void bresenham_circle (int xc, int yc, int radius) { void circlepoints(int, int, int, int); int F = 1 - radius, x = 0, y = radius; circlepoint(xc, yc, x, y); while (y > x) { if (F < 0) F += x * 2 + 3; else { F += (x - y) * 2 + 5; y--; } x++; circlepoint(xc, yc, x, y); } }

46 목차 점그리기선그리기원그리기다각형그리기

47 다각형 다각형의정의 세개이상의선분으로둘러싸인평면도형 모서리 (edge) 또는변 (side) : 다각형을구성하는선분 꼭짓점 (vertex) : 2개의변이만나는점 꼭짓점 변, 모서리 교재관련부분 : 83 쪽

48 다각형 볼록다각형과오목다각형 볼록 (convex) 다각형 : 모든내각들이 180 이하인다각형 오목 (concave) 다각형 : 볼록하지않은다각형 (180 이상인내각이존재함 ) 볼록다각형 오목다각형 교재관련부분 : 84 쪽

49 다각형 볼록다각형과오목다각형의판별 꼭짓점을와인딩순서에따라연결하는벡터로보고두인접벡터의외적을구함 y E3 E3 E4 E2 E3 E2 E4 E1 E4 E1 E1 E2 < 180 z방향 z 모든외적의방향이동일 x z y E4 E3 E3 E4 E4 E5 E2 E3 E5 E2 E1 E1 E5 E1 E1 E2 일부외적의방향이반대 x 교재관련부분 : 85 쪽

50 다각형 내부 / 외부검사 홀 - 짝규칙적용 외부의점 경계상자 P1 내부 P2 외부 교재관련부분 : 86 쪽

51 다각형 다각형의표현 꼭짓점, 변, 각면정보를저장하는표를사용 V 1 변표 E 1 : V 1, V 2, S 1 E 1 E 3 E 6 E 2 : V 2, V 3, S 1 V 2 E 2 S 1 S2 V 3 E 4 V 4 E 5 V 5 꼭짓점표 V 1 : x 1, y 1, z 1 V 2 : x 2, y 2, z 2 E 3 : V 3, V 1, S 1, S 2 E 4 : V 3, V 4, S 2 E 5 : V 4, V 5, S 2 E 6 : V 5, V 1, S 2 V 3 : x 3, y 3, z 3 각면표 V 4 : x 4, y 4, z 4 S 1 : E 1, E 2, E 3 V 5 : x 5, y 5, z 5 S 2 : E 3, E 4, E 5, E 6 교재관련부분 : 87 쪽

52 다각형 다각형의앞면과뒷면 눈에보이는면 ( 앞면 ) 과보이지않는객체내부의면 ( 뒷면 ) z y N = (A, B, C) Ax + By + Cz + D = 0 x Ax + By + Cz + D > 0 (x, y, z) 는평면앞에위치 Ax + By + Cz + D < 0 (x, y, z) 는평면뒤에위치 교재관련부분 : 88 쪽

53 다각형 와인딩 (winding) 다각형의앞면을정의하기위해정한꼭짓점의나열순서 시계반대방향 (CCW) 와인딩 y y 시계방향 (CW) 와인딩 V 2 V 2 (V 0, V 1, V 2 ) (V 0, V 2, V 1 ) V 0 V 1 x V 0 V 1 x 다각형의정면 ( 디폴트값 ) 다각형의뒷면 교재관련부분 : 84 쪽

54 OpenGL 의다각형그리기 glbegin 함수에그리고자하는다각형의종류를입력 GL_TRIANGLES GL_TRIANGLE_STRIP GL_TRIANGLE_FAN GL_QUADS GL_QUAD_STRIP GL_POLYGON 교재관련부분 : 89~93 쪽

55 OpenGL 의다각형그리기 GL_TRIANGLES glbegin(gl_triangles); glvertex2i(0, 0); glvertex2i(20, 0); glvertex2i(10, 10); glend(); (10, 10) (0, 0) (20, 0) 교재관련부분 : 89 쪽

56 OpenGL 의다각형그리기 GL_TRIANGLE_STRIP glbegin(gl_triangle_strip); glvertex2iv(v0); V0 V2 V4 glvertex2iv(v1); glvertex2iv(v2); glvertex2iv(v3); glvertex2iv(v4); glend(); V1 V3 교재관련부분 : 89~90 쪽

57 OpenGL 의다각형그리기 GL_TRIANGLE_FAN glbegin(gl_triangle_fan); glvertex2iv(v0); glvertex2iv(v1); glvertex2iv(v2); glvertex2iv(v3); glvertex2iv(v4); glend(); V1 V0 V2 V3 V4 교재관련부분 : 90~91 쪽

58 OpenGL 의다각형그리기 GL_QUADS glbegin(gl_quads); glvertex2iv(v0); glvertex2iv(v1); glvertex2iv(v2); glvertex2iv(v3); glend(); V0 V1 V3 V2 교재관련부분 : 91~92 쪽

59 OpenGL 의다각형그리기 GL_QUAD_STRIP glbegin(gl_quad_strip); glvertex2iv(v0); glvertex2iv(v1); V0 V2 V4 glvertex2iv(v2); glvertex2iv(v3); glvertex2iv(v4); glvertex2iv(v5); glend(); V1 V3 V5 교재관련부분 : 92 쪽

60 OpenGL 의다각형그리기 GL_POLYGON glbegin(gl_polygon); glvertex2iv(v0); glvertex2iv(v1); glvertex2iv(v2); V1 V0 V4 glvertex2iv(v3); glvertex2iv(v4); glend(); V2 V3 교재관련부분 : 93 쪽

61 정리하기 1 OpenGL 에서꼭짓점을지정하기위해서는 glvertex* 함수를사용한다. 2 OpenGL 에서도형을그릴때는 glbegin 함수와 glend 함수사이에꼭짓점을나열한다. 이때 glbegin 함수에그리고자하는 도형및그리기방법을나타내는상수를전달한다. 점그리기상수 : GL_POINTS 선분그리기상수 : GL_LINES, GL_LINE_STRIP, GL_LINE_LOOP 삼각형그리기상수 : GL_TRIANGLES, GL_TRIANGLE_FAN, GL_TRIANGLE_STRIP 사각형그리기상수 : GL_QUADS, GL_QUAD_STRIP 다각형그리기상수 : GL_POLYGON

62 정리하기 3 DDA 알고리듬은한축의좌표를 1 씩변화시킬때, 다른축의좌표를직선의기울기 ( 또는기울기의역수 ) 만큼변화시켜다음 점의좌표계산한다. 4 Bresenham 직선알고리듬 정수형덧셈연산만으로직선상의점들의위치를계산할수있는알고리듬 기울기가 0과 1 사이의값이라고가정할때, 어느점에서 x좌표가 1 증가할경우 y좌표는그대로이거나 1만큼증가 이를판단할수있는판별식을통해점증적으로직선상의점들의위치를계산

63 정리하기 5 꼭짓점을나열하는와인딩에의해다각형의앞면방향을정의할수있다. 6 볼록다각형은꼭짓점을와인딩순서에따라연결하는벡터들에대해두인접벡터쌍의외적의방향이모두같다. 7 다각형외부의점으로부터어떠한점을잇는선이다각형경계와교차하는횟수가홀수이면그점은다각형내부이고, 짝수 이면외부이다.