Microsoft PowerPoint - lecture18-ch7.ppt [호환 모드]

Similar documents
Microsoft PowerPoint - lecture18-ch7 [호환 모드]

Microsoft PowerPoint - lecture20-ch7.ppt [읽기 전용]

Microsoft PowerPoint - lecture19-ch7.ppt

<4D F736F F F696E74202D204347C3E2BCAEBCF6BEF D325FC4C4C7BBC5CDB1D7B7A1C7C8BDBA20B1E2BABBBFE4BCD22E >

(Microsoft PowerPoint - EDIDFDXLLBYN.ppt [\310\243\310\257 \270\360\265\345])

Microsoft Word - cg12-midterm-answer

Microsoft PowerPoint - Chapter 9.pptx

Microsoft Word - cg08-final-answer.doc

Microsoft PowerPoint - 04primitives.ppt

Microsoft PowerPoint - Lect17-FromGeoToPixels-1.pptx

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2

Computer Architecture

Microsoft Word - cg07-final.doc

PowerPoint 프레젠테이션

Python과 함께 배우는 신호 해석 제 5 강. 복소수 연산 및 Python을 이용한 복소수 연산 (제 2 장. 복소수 기초)

FGB-P 학번수학과권혁준 2008 년 5 월 19 일 Lemma 1 p 를 C([0, 1]) 에속하는음수가되지않는함수라하자. 이때 y C 2 (0, 1) C([0, 1]) 가미분방정식 y (t) + p(t)y(t) = 0, t (0, 1), y(0)

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2

2 장수의체계 1. 10진수 2. 2진수 3. 8진수와 16진수 4. 진법변환 5. 2진정수연산과보수 6. 2진부동소수점수의표현 한국기술교육대학교전기전자통신공학부전자전공 1

1 peaieslvfp3 1. 두점사이의거리 수직선위의두점사이의거리를구할수있다. 좌표평면위의두점사이의거리를구할수있다. 수직선위의두점사이의거리 todrkrgo qhqtlek 오른쪽그림은충무로역을중심으로한서울시지하철 3`호선노선도의일부분이다. 충무로역을` 0, 을지로 3`

Introduction to Computer Science

Microsoft PowerPoint - chap04-연산자.pptx

OCW_C언어 기초

PowerPoint 프레젠테이션

슬라이드 1

ch3.hwp

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

제 2 교시 2019 학년도 3 월고 1 전국연합학력평가문제지수학영역 1 5 지선다형 1. 의값은? [2점] 일차방정식 의해는? [2 점 ] 두수, 의최대공약수는? [2 점 ] 일차함수 의그래프에서

Microsoft PowerPoint - 강의자료8_Chap9 [호환 모드]

Microsoft PowerPoint - hw8.ppt [호환 모드]

Microsoft PowerPoint - chap03-변수와데이터형.pptx

PowerPoint 프레젠테이션

(Microsoft PowerPoint - Ch19_NumAnalysis.ppt [\310\243\310\257 \270\360\265\345])

컴퓨터그래픽스 기본요소

최종 고등수학 하.hwp

벡터(0.6)-----.hwp

01

PowerPoint Presentation

슬라이드 1

untitled

일반각과호도법 l 삼각함수와미분 1. 일반각 시초선 OX 로부터원점 O 를중심으로 만큼회전이동한위치에동경 OP 가있을때, XOP 의크기를나타내는각들을 ( 은정수 ) 로나타내고 OP 의일반각이라한다. 2. 라디안 rad 반지름과같은길이의호에대한중심각의 크기를 라디안이라한

Microsoft PowerPoint - Java7.pptx

Microsoft PowerPoint - 1-2장 디지털_데이터 .ppt

Microsoft PowerPoint - chap-06.pptx

LIDAR와 영상 Data Fusion에 의한 건물 자동추출

이미지 워핑과 모핑

<B4EBC7D0BCF6C7D02DBBEFB0A2C7D4BCF62E687770>

Microsoft PowerPoint - chap06-2pointer.ppt

고 학년도 9월고수학 1 전국연합학력평가영역문제지 1 1 제 2 교시 수학영역 5 지선다형 3. 두다항식, 에대하여 는? [ 점 ] 1. 의값은? ( 단, ) [ 점 ] 다항식 이 로인수분해될때, 의값은? ( 단,,

쉽게 풀어쓴 C 프로그래밍

Microsoft PowerPoint - ch07 - 포인터 pm0415

Microsoft PowerPoint 다변수 방정식과 함수(1).ppt

<BFACBDC0B9AEC1A6C7AEC0CC5F F E687770>

Open GL


Microsoft PowerPoint - chap-05.pptx

Microsoft PowerPoint - 3ÀÏ°_º¯¼ö¿Í »ó¼ö.ppt

= ``...(2011), , (.)''

<30325FBCF6C7D05FB9AEC7D7C1F62E687770>

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각

쉽게 풀어쓴 C 프로그래밍

C# Programming Guide - Types

Structure and Interpretation of Computer Programs: Assignment 3 Seung-Hoon Na October 4, George (아래 3개의 문제에 대한 구현이 모두 포함된 george.rkt파일을 제출하시오.

PowerPoint 프레젠테이션

<4D F736F F F696E74202D20C1A63037B0AD202D20B1A4BFF8B0FA20B1D7B8B2C0DA>

Microsoft Word - SDSw doc

초4-1쌩큐기본(정답)본지

STATICS Page: 7-1 Tel: (02) Fax: (02) Instructor: Nam-Hoi, Park Date: / / Ch.7 트러스 (Truss) * 트러스의분류 트러스 ( 차원 ): 1. 평면트러스 (planar tru

Frama-C/JESSIS 사용법 소개


PowerPoint Presentation

쉽게 풀어쓴 C 프로그래밍

프로그래밍개론및실습 2015 년 2 학기프로그래밍개론및실습과목으로본내용은강의교재인생능출판사, 두근두근 C 언어수업, 천인국지음을발췌수정하였음

Microsoft PowerPoint - C++ 5 .pptx

기본도형과작도 1 강 - 연습문제 1. 오른쪽그림과같이직선l 위에점,, 가있을때, 옳지않은것은? 1 = 2 = 3 = 직선l 4 = 5 = l 2. 오른쪽그림에서 = = 이다. 다음( ) 안에알맞은수를쓰시오. 1 =( 2 =( 3 =( 4 =( ) ) ) ) 3. 한평

PowerPoint 프레젠테이션

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx

문제지 제시문 2 보이지 않는 영역에 대한 정보를 얻기 위하여 관측된 다른 정보를 분석하여 역으로 미 관측 영역 에 대한 정보를 얻을 수 있다. 가령 주어진 영역에 장애물이 있는 경우 한 끝 점에서 출발하여 다른 끝 점에 도달하는 최단 경로의 개수를 분석하여 장애물의

스무살, 마음껏날아오르기위해, 일년만꾹참자! 2014학년도대학수학능력시험 9월모의평가 18번두이차정사각행렬 가 를만족시킬때, 옳은것만을 < 보기 > 에서있는대로고른것은? ( 단, 는단위행렬이다.) [4점] < 보기 > ㄱ. ㄴ. ㄷ. 2013학년도대학수학능력시험 16번

Microsoft PowerPoint - 07-Data Manipulation.pptx

2018 학년도대학수학능력시험문제지 1 제 2 교시 홀수형 5 지선다형 1. 두벡터, 모든성분의합은? [2 점 ] 에대하여벡터 의 3. 좌표공간의두점 A, B 에대하여선분 AB 를 으로내분하는점의좌표가 이다. 의값은? [2점] ln

Microsoft PowerPoint - java1-lab5-ImageProcessorTestOOP.pptx

장연립방정식을풀기위한반복법 12.1 선형시스템 : Gauss-Seidel 12.2 비선형시스템 12.1 선형시스템 : Gauss-Seidel (1/10) 반복법은초기근을가정한후에더좋은근의값을추정하는체계적인절차를이용한다. G-S 방법은선형대수방정

슬라이드 1

OCW_C언어 기초

중간고사

슬라이드 1

제 3강 역함수의 미분과 로피탈의 정리

Microsoft PowerPoint - D03_SpatialDomainEnhance_note.ppt [호환 모드]

PowerPoint 프레젠테이션

04 Çмú_±â¼ú±â»ç


; struct point p[10] = {{1, 2, {5, -3, {-3, 5, {-6, -2, {2, 2, {-3, -3, {-9, 2, {7, 8, {-6, 4, {8, -5; for (i = 0; i < 10; i++){ if (p[i].x > 0 && p[i

11장 포인터

금오공대 컴퓨터공학전공 강의자료

2_안드로이드UI

Observational Determinism for Concurrent Program Security

제 14 장포인터활용 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.

PowerPoint Presentation

<C3D1C1A4B8AE B0E6BFECC0C720BCF B9AE2E687770>

집합 집합 오른쪽 l 3. (1) 집합 X 의각원소에대응하는집합 Y 의원소가단하나만인대응을 라할때, 이대응 를 X 에서 Y 로의라고하고이것을기호로 X Y 와같이나타낸다. (2) 정의역과공역정의역 : X Y 에서집합 X, 공역 : X Y 에서집합 Y (3) 의개수 X Y

Transcription:

Geometric Pipeline From Vertices to Fragments 기하파이프라인 (geometric pipeline) 정점처리 (verte processing) 클리핑과기본요소로조립 (clipping and primitive assembl) 래스터화 (rasterization) ti 단편처리 (fragment processing) 응용프로그램 39 4 년봄학기 5/3/4 박경신 ( 정점 ) ( 픽셀 ) 그래픽스시스템 프레임버퍼 Clipping 차원클리핑윈도우 (clipping window) 3 차원클리핑경계입체 (clipping volume) 곡선과텍스트는먼저선과다각형으로바꿔줄것 D Line-Segment Clipping 선분클리핑 (clipping D line segments) 절단기 (clipper) 는어떤기본요소또는그일부가화면에나타나야되고래스터화기로보내져야하는지를결정 수용 (accepted): 지정한관측공간에들어온기본요소는수용 거부 (rejected) 또는선별 (culled): 화면에나타날수없는기본요소는제거됨 차원선분클리핑

D Line-Segment Clipping Cohen-Sutherland Algorithm 클리핑윈도우의모든변들에대해서교점을계산하는방법 매교점당하나의나눗셈을해야하므로비효율적임 Cohen-Sutherland 클리핑알고리즘. 클리핑윈도우의 4개의변무한대로확장하고, 공간을 9개의영역으로분할 = ma = min = ma = min. 각영역에고유의외곽부호 (outcode), b b b b 3 를다음과같이할당 if ma if min if ma if min b b b b3 otherwise otherwise otherwise otherwise 3. 외곽부호에기초하여 4가지경우를판단 Cohen-Sutherland Algorithm 선분 AB 의경우 : A s outcode = B s outcode = 선분의양끝점이클리핑윈도우내부에있는경우, accepted 선분 CD 의경우 : C s outcode AND D s outcode 선분의양끝점이클리핑윈도우의같은변의외부에있는경우, rejected A s outcode = B s outcode = = ma B = min A = ma = min C s outcode = C D D s outcode = C AND D = Cohen-Sutherland Algorithm 선분 EF 의경우 : E s outcode, F s outcode = 선분의한끝점은클리핑윈도우내부에있고, 다른하나는외부에 있는경우, subdivide 개교차점 (intersection) 을찾아야함 선분 GH, 선분 IJ의경우 : G s outcode AND H s outcode = 선분의양끝점이모두외부에있는경우, subdivide. 선분 GH경우 선분의일부가클리핑윈도우내부에있음 적어도윈도우한J 변과교차계산하고그결과점의외곽부호를 H 점검할것 = F ma G s outcode = I H s outcode = G G AND H = = min E = ma I s outcode = = min I AND J = J s outcode = E s outcode = F s outcode =

Liang-Barsk Algorithm Liang-Barsk Algorithm Liang-Barsk 클리핑알고리즘. 매개변수형직선공식 P( ) ( ) P P, ( ) ( ) p ( ) ( ). 선분이클리핑윈도우의확장된변과교차하는 4 점을계산하여 α 값의순서를살펴봄으로써판별함 ma ( 3) 3 min ( ) ma 3 min 4 3 4 3 우, 상, 좌, 하순서로교차하므로단축 p 우, 좌, 상, 하순서로교차하므로기각 Liang-Barsk 클리핑알고리즘 3. 클리핑윈도우내에존재하는직선은다음을만족함 min ) min ) ( ( ma ma 4. 클리핑윈도우의바깥에위치하는직선은, (, ) 이 min, ma 또는 min, ma 바깥이있을경우임 q k where ( k q q q q 3,,3,4 ) ma min min 4 ma Liang-Barsk Algorithm Polgon Clipping Liang-Barsk 클리핑알고리즘 5. 직선의두점중, 값이적은점을 (, ) 이라가정, 직선을무한히연장하면각각클리핑윈도우를바깥쪽에서안쪽으로, 안쪽에서바깥쪽으로지나게됨 오목한다각형 (concave polgon) 의클리핑 방법 : 클리핑후하나의다각형으로묶는방법 방법 : 오목한다각형의집합으로나누고 (tessellate), 클리핑 J H = ma F 4 D I G = min 3 B A E C = ma 클리핑후 하나의다각형생성 = min 4 3 클리핑전 분할 (Tessellation)

Pipeline Clipping of Line Segments Sutherland-Hodgeman 알고리즘 절단기를각각윈도우의한변에대해서클리핑하는더간단한절단기의파이프라인으로세분함 3 ( ma ) 3 ma = min = ma = ma Pipeline Clipping of Polgons Sutherland-Hodgeman 알고리즘 Input: 다각형 ( 정점리스트 ) 과클리핑면 Output: 새로운클리핑이된다각형 ( 정점리스트 ) 차원다각형에대한연속적인절단기 (pipeline clipping i of polgons) 3 차원의경우, 전변 (front) 과후변 (back) 클리핑을추가함 = min Bounding Boes 다각형의축정렬경계상자 (ais-aligned bounding bo) 또는범위 (etent) 를클리핑에사용 많은변을가진복잡한다각형의경우 경계상자는다각형을포함하는윈도우에정렬된가장작은사각형 경계상자는다각형정점 와 값의최소값 (min) 과최대값 (ma) 를계산하여얻어짐 Bounding boes 경계상자를사용하여간단한클리핑수행 Accept 윈도우안에있으므로내부에있는것으로수용 Reject 윈도우밖에있으므로클리핑이필요없음 Requires detailed clipping 다각형의모든변을사용하여상세한클리핑을수행

Cohen-Sutherland Algorithm in 3D Liang-Barsk Algorithm in 3D 3차원에서는평면에서의경계영역이아닌경계공간 (bounding volume) 에대하여클리핑 Cohen-Sutherland 클리핑알고리즘 클리핑공간에대한 4비트외곽부호를 6비트외곽부호로대체하고 차원의경우와같이계산함 if z zma b4 otherwise if z zmin b5 otherwise Liang-Barsk 클리핑알고리즘 선분의 3 차원매개변수표현 P( ) ( ) P P ( ) ( ) ( ) ( ) z ( ) ( ) z z, 평면 (P, n) 의공식으로부터 유도 P( ) ( ) P P n( P( ) P ) n ( P ) P n ( P P) Rasterization 래스터화 (rasterization)/ 스캔변환 (scan conversion) 프레임버퍼에서단편의형성에이르는과정의마지막단계 물체를표현하기위해어떤화소를밝힐것인지를결정하는작업 정규화가시부피 (normalized device coordinates) 에서뷰포트 (viewport) 로의사상 정점좌표를화면좌표로변환한결과를기준으로 선분을화면좌표로변환 내부면을화면좌표로변환 아래그림에서 A, B, C 으로둘러싸인곳에서어떤화소를칠해야삼각형 ABC를가장잘표현할수있는가? Rasterization 실수 (float) 좌표를정수 (int) 좌표로변환 때로는반올림이필요 예를들어, 정점의뷰포트좌표가 (.95,.4) 화소 (, ) 로변환됨 화소경계선내부 (.5 <= <.5) 이고 (.5 <= <.5) 인모든정점은 (, ) 로사상됨 3 3 A B 3 3 A, B 는모두같은선분으로사상됨

Line Scan-Conversion 래스터변환알고리즘이적용되는가장기본적인객체가선분 (line segment) 임 일단선분양끝정점이화면의어떤화소로사상되는지를결정한후에나머지화소부분을처리 기울기를기준으로샘플링 보다크면 좌표를증가 보다작으면 좌표를증가 기울기가음수라면절대값이용 Line Scan-Conversion 교차점계산에의한변환은부동소수곱셈으로인해속도저하 void LineDraw(int, int, int, int ) (,) { float, m; int d, d; d = - ; (,) d = - ; m = d / d; for ( = ; <= ; ++) { = m*( - ) + ; DrawPiel(, round()); 두점 (, )(, ) 을지나는직선방정식 ( ) DDA (Digital Differential Analzer) 부동소수곱셈을부동소수덧셈으로변환 void LineDraw(int, int, int, int ) { (,) ) float m, ; int d, d; d = - ; d = - ; m=d/d; d; (,) = ; for (int = ; <= ; ++) { += m; m h where m DrawPiel(, round()); m m ( 가 씩증가할때 ) DDA (Digital Differential Analzer) DDA 알고리즘에의한연산 (, ) 반올림결과 = (,.) (, ) = (,.33) (, ) = (,.66) (, ) =3 (3,.99) (3, ) = 4 (4,.3) (4, ) =5 (5,.65) (5, ) = 6 (6,.98) (6, )

DDA (Digital Differential Analzer) DDA 단점 부동소수연산 부동소수덧셈이정수연산에비해느림 반올림연산 round( ) 함수실행에걸리는시간 연산결과의정확도 부동소수의경우뒷자리가잘려나감 연속적인덧셈에의한오류누적 선택된화소가실제선분에서점차멀어져서표류 (Drift) 중점알고리즘 (Midpoint Algorithm) 라고도불림 모든부동소수점계산을피하고정수계산만이용 현재래스터기의표준알고리즘이된직선래스터화알고리즘 (,) (+,+) (,) (,) (+,) M(+,+½) +½) A (, ) 선택 다음화소는 B (+, ), C (+, +) 중하나 화소중심과선분간의수직거리에의해판단 선분이중점 M 아래에있으면화소 B, 위에있으면화소 C 를선택 화소 A=(, ) 이라하면화소 B, C 의중점 M 의좌표는 ( +, + ½) 이되는데, 이를 F 에대입해보면 d m h, m d d h d d d hd d d hd F(, ) d d hd F(, ) F, d d hd d d hd d d F(, ) d d F (, ) d d hd F(, ) d d 결정변수 (decision variable) 에의해중점이선분의위인지아래인지를판단 만약 F(, ) < 이라면, 중점이선분위에있고따라서동쪽화소를선택 만약 F(, ) > 이라면, 동북쪽화소를선택 F(, ) d d if ( F (, ) ) else select NE select E // 동쪽화소선택 // 동북쪽화소선택 d d d>d => F(,) <

현재고려되고있는화소의좌표를 (, ) 라고하고만약동쪽화소가선택되었다면, 다음단계위치는 (+, ) 동북쪽화소가선택되었다면다음단계위치는 (+, +) 다음단계의결정변수와현단계의결정변수의차이는다음과같이계산 incre F(, ) F(, ) ( ) d d hd d d hd d incrne F (, ) F (, ) ( ) d d hd d d hd d d void MidpointLineDraw(int, int, int, int ) m { int d, d, incre, incrne, D,, =; d = - ; d = - ; D = *d - d; // 결정변수값을초기화 incre = *d; // 동쪽화소선택시증가분 incrne = *d - *d; // 동북쪽화소선택시증가분 for (=; <= ; ++) { if (D <= ) { // 결정변수가음수. 동쪽화소선택 D += incre; // 결정변수증가 else { // 결정변수가양수. 동북쪽화소선택 D+= incrne; // 결정변수증가 ++; // 다음화소는동북쪽 DrawPiel (, ); // 화소그리기 m >. 와 를바꿔서계산함 방향으로증가시키면서, 값을결정함 그외에, 특수한경우는따로처리함 Δ = (horizontal line) Δ = (vertical line) Δ = Δ (diagonal lines) Δ = (vertical line) < < - < m < - < m < < - m < m < m < - m 예를들어 (, ) 과 (6, 4) 를연결하는선분 (, ) D > (,) D < (, ) (6, 4) < < m < < - < m < -

정수연산에의한속도증가 + 하드웨어로구현 첫 8 분면에서만정의 다른선분은이동, 반사하여적용 Polgon Scan-Conversion 다각형의래스터화 = 다각형채우기 (polgon filling) 점이다각형의내부에있다면그것을내부색으로칠함 다각형내부의판단규칙 홀짝규칙 (even-odd rule) 주사선별로경계가홀수 (odd) 번째교차하면내부, 짝수 (even) 번째교차하면외부가시작된다고판단 접기횟수규칙 (non-zero winding rule) 주사선별로아래쪽경계와교차하면접기횟수를 증가, 위쪽방향의경계와교차하면 감소 이때접기횟수가 보다큰구간은다각형의내부영역으로판단 원생성알고리즘 선분생성알고리즘과유사 Flood Fill 범람채우기 (flood fill) 내부로정의된영역채우기 다각형내부의시작점 (seed point) 에서시작하여, 순환적으로이웃을살펴보고, 만약이들이변의점이아니라면채우기색으로칠함 void flood_fill(int fill(int, int ) { // 다각형내부초기점 (, ) 에서시작 if(read_piel(,)= = WHITE) { // 현재픽셀이배경색 (white) 이면 write_piel(,,black); // 채우기색 (black) 으로칠함 flood_fill(+, ); // 오른쪽으로반복 flood_fill(-, ); // 왼쪽으로반복 flood_fill(, fill(, +); // 아래로반복 flood_fill(, -); // 위로반복 Scan Line Fill 주사선채우기 (scan line fill) Y-X 다각형주사선알고리즘 : 3 4 5 6 7 8 9 전체 edge를 Y값순서로정렬하여 Edge List (EL) 를구성 매주사선이새로교차하는에지를 EL 에서꺼내어 Active Edge List (AEL) 로이동 해당주사선과각 edge와교차점을 개씩짝을지어사이를채움 e e3 e Edge List e e e3 Active Edge List = = =3.. =6.. =9 e e e e3

Aliasing 계단 (Stair-step, Jaggies) 모양의거친경계선 비트맵표현에서는화소단위로근사화할수밖에없기때문 무한해상도를지닌물체를유한해상도를지닌화소면적단위로근사화할때필연적으로일어나는현상 Anti-Aliasing Aliasing 수퍼샘플링 (Super-Sampling) 부분화소에서샘플링. 사후필터링 부분화소의평균값을반영 지터 (jitter) 에의한수퍼샘플링 물체자체가불규칙이라면불규칙샘플링이유리 Anti-Aliasing Aliasing Aliasing Anti-aliased Magnified