개요

8장. 가시성 판단

• 학습목표

• 후면제거의 정의와 처리방법을 이해한다.

• 절단작업의 정의와 처리방법을 이해한다.

• 지엘의 절단 방법을 이해한다.

• 은면제거의 정의를 이해한다.

• 지-버퍼 알고리즘을 구체적으로 이해한다.

개요

• 기초

– 모든 좌표계는 원점 O와 이 원점으로부터 발현되는 축을 가진다

• 거리는 각 축에 대한 위치로 기술됨 – b)오른쪽 좌표계 c)왼쪽 좌표계

벡터

• 정의

• 크기와 방향을 가지는 물리량

• 크기만을 의미하는 스칼라량과 비교되는 양

• 스칼라량은 하나의 크기량만을 나타내지만 벡터량은 크기와 방향을 동시에 나타 내는 표현도구이다

4.2 Review of vectors

• 변위로 표현된 벡터

• Vector : 두 점들간의 차 – v=Q-P

– 벡터와 점의 합은 점 ⇒Q=P+v

– N-dimension, N-tuple ⇒ w=(w¹,w2,w3,…,wn)

– 편의상 행행렬로 표기하지만 벡터와 점을 행렬식에 곱할 경우 열행렬(Column matrices)로 표현

4.2 Review of vectors

• 벡터 연산 : 덧셈, 뺄셈, 스칼라곱셈 – a=(2,5,6), b=(-2,7,1)

– a+b = (0,12,7) and 6a=(12,30,36)

4.2 Review of vectors

• 벡터의 크기 : 단위 벡터

– 벡터 w 가 n-tuple(w

,w

,…,w

)에 의해 표현된다면 – 벡터의 크기는 다음과 같이 정의

– w=(4,-2),

– 만약 w 가 A, B 두 점으로부터 나온 벡터라면.

• |w|는 A와 B 두 점 사이의 거리임

– 단위 길이로 바꾸는 것이 유용할 때가 있음

• 이를 정규화(normalizing)라고 한다

순서대로 정렬된 값들의 세트

벡터

• 정규화 벡터(Normalized Vector)

• 벡터의 크기(절대값)

벡터 내적과 외적

• 내적(Inner Product, Dot Product)

• 외적(Outer Product, Cross Product)

• 정규화 법선벡터

• =정규화 외적벡터

내적

– 가끔 단위 벡터를 방향(direction)이라고 함.

• 모든 벡터는 그 단위 벡터와 크기를 곱하여 생성할 수 있다

• 내적의 정의

– 두 n-차원 벡터의 v=(v¹,v2,...,vn)과 w=(w¹,w2,…,wn)의 내적은 v·w 로 표기하며 다음과 같은 값을 가진다

– 내적의 결과는 스칼라가 됨

d = v · w =

X

i=1

v

w

4.3.1 내적의 특성

1. 교환법칙 2. 분배법칙

3. Homogeneity 4.

• 교환법칙 성립(commutative)

a · b = b · a (a + c) · b = a · b + c · b (sa) · b = s(a · b)

|b|

= b · b

삼각함수

• sin

• 직각삼각형의 빗변에 대한 높이의 비

• sin A = a/h

• cos

• 직각삼각형의 빗변에 대한 밑변의 비

• cos A = b/h

• tan

- 직각삼각형의 밑변에 대한 높이의 비

- tan A = a/b

두 벡터사이의 각도

• 내점의 가장 중요한 응용 : 두 벡터나 선분 사이의 각연산 – 그림에서 두 벡터 b, c는 각과 거리로 표현가능

삼각함수의 합,차 공식

b · c

b · c = |b||c|cos( ) cos( ) = ˆb · ˆc

b = ( |b|cos

, |b|sin

) c = ( |c|cos

, |c|sin

)

b·c 내적값과 직교성

• 이러한 내적의 성질을 이용하면 두 벡터의 직교성 검사가 가능

– >0 이면 <90 b·c>0 – =0 이면 = 0 b·c=0 – <0 이면 >90 b·c<0

직교성 검사

– 정의

• 두 벡터의 내적 b·c=0 이면 두 벡터는 직교한다

– 정의

• 삼차원 표준 단위 벡터의 성분

• i=(1,0,0) , j=(0,1,0) , and k = (0,0,1)

• (a,b,c)=ai+bj+ck.

투영의 응용 : 반사

– a : 광선(ray)의 방향, L : 반사면, 반사방향 r?

– n: L에 수직인 벡터.

– 표면에 반사되는 벡터 r을 a,n을 이용하여 구하자?

. . .

– a=(4,-2) and n=(0,3). Then r=(4,2)

평면 표현

두 벡터의 외적

• 외적(外積)(또는 벡터곱)

– v,w 벡터가 있을 경우 두 벡터에 수직인 벡터 u를 구하는 연산 – 두 벡터의 수직 벡터는 두개가 존재함

외적

• 외적연산에는 오른손 법칙이 적용됨

• v x w = - (w x v) : 외적에는 교환법칙이 성립하지 않음

• ‖v x w‖ = ‖v‖‖w‖sin θ

• v x w = (vywz – wyvz, vzwx – wzvx, vxwy – wxvy)

= (vywz, vzwx, vxwy) – (wyvz, wzvx, wxvy) -> 9 Operation

• 외적에 관한 6개 주요 규칙

• vⅹw = -wⅹv

• uⅹ(v+w)=(uⅹv)+(uⅹw)

• (u+v)ⅹw=(uⅹw)+(vⅹw)

• a(vⅹw)=(av)ⅹw=vⅹ(aw)

• vⅹ0=0ⅹv=0

• vⅹv=0

• v x w 벡터를 계산하여 정규화하는 것은 한 방향의 법선벡터를 만들 것이다

• w x v 벡터는 반대방향의 벡터를 만들게 됨

외적

• 외적은 삼차원 공간에서만 정의됨

– 외적의 결과 두 벡터에 수직인 벡터가 만들어짐 – 외적의 크기는 두 벡터가 이루는 평행사변형의 면적

외적의 기하적인 해석

• 외적의 성질 중 매우 유용한 성질

+

평면의 법선 벡터 구하기

– 평면을 이루는 세 점을 P1, P2, P3라 할 때 이 평면에 수직인 벡터를 외적을 통해서 알 수 있다

– a=P2-P1, b=P3-P1, n=a x b

지엘의 법선벡터

법선벡터 방향

• 오른 손을 명시된 정점 순으로 감싸 쥐었을 때 엄지방향

법선벡터

• 평면상의 점과 법선벡터를 이용한 평면의 식

– 법선벡터 n은 평면상에 있는 임의의 직선과 수직으로 간주됨

후면

전면과 후면

• 후면(Back-Facing Polygon)

• 전면(Front-Facing Polygon)

후면제거(Backface Culling, Backface Removal)

• 시점과 면의 오리엔테이션만으로 판단

• 보이지 않는 면의 거의 절반을 제거

• 벡터의 내적의 성질을 이용하여 쉽게 계산

관측자에게 안보이는 부분

지엘의 후면제거

• 정규화 가시부피

• 법선벡터의 z 값만으로 판단가능

• (b)의 z 값이 A는 +, B는 - 임

• A 는 후면임

• glEnable(GL_CULL_FACE);

• glCullFace(GL_FRONT);

표면과 이면

하나의 면 = 표면 + 이면

표면

• 반시계방향으로 정의된 면

▪ glFrontFace(GL_CCW)

• 시계방향으로 정의된 면

▪ glFrontFace(GL_CW)

표면과 이면

후면의 이면

• 시점이 결정되면 다각형의 표면과 이면 중 하나의 면만 보임.

• 지엘은 표면과 이면 중 하나만을 선택하여 그 면으로 해당 다각형을 대신함

후면이면 = 표면

절단(Clipping)

2차원 절단

• 윈도우(Window), 뷰포트(Viewport), 시저 박스(Scissor Box) 3차원 절단

• 가시부피(View Volume) 절단 다각형

• 절단 사각형(Clip Rectangle)

Lab

코헨-서더런드 알고리즘

• 4비트 아웃코드(Outcode)

• 테스트 1) E1 = E2 = 0000

• 완전히 사각형 내부 선분이므로 보이는 선분으로 판정한다. (선분 A)

• 테스트 2) E1 & E2 != 0000

• 선분이 온전히 절단 사각형 밖에 있으므로 제거한다. (선분 B)

• 테스트 3) E1 != 0000, E2 = 0000 (또는 그 반대)

코헨-서더런드 알고리즘

• 선분분할

• 분할된 선분을 대상으로 다시 테스트

• 선분 D: E3 & E2 != 0000 이므로 온전히 외부 선분으로 무시

리앙-바스키(Liang-Barsky) 알고리즘

• 교차점에서의 파라미터 값의 순서를 기준으로 여러 가지 경우를 판단

서더런드 핫지먼 알고리즘

• 절단 다각형을 기준으로 순서대로 절단

• 절단 규칙

서더런드 핫지먼 알고리즘

서더런드 핫지먼 알고리즘

• 선분을 연장한 직선을 기준으로 절단

• Ex. 좌변기준의 절단

• 3차원 절단

• 상, 하, 좌, 우, 전, 후의 6개의 면을 기준으로 절단

• 면을 기준으로 내외부 판정

볼록, 오목

• 서더런드-핫지먼

• 볼록 다각형에만 적용

• 하나의 다각형으로 취급

• 오목 다각형 처리결과: 오류

• 해법 1: 다각형 분할(Tessellation)

• 오목 -> 볼록

웨일러-애서톤 알고리즘

내부에서 외부로 가는 교차점이 추가되면 즉시 그 교차점으로부터 절단 사각형을 따라 서 반 시계 방향으로 간다. 즉, 가장 최근에 외부에서 내부로 들어온 교차점을 만날 때 까지 간다.

1-C-D-2로 구성되는 하나의 다각형이 완성

정점의 내외부 판정

동차좌표 사용

점과 평면간의 거리

• 법선벡터 방향이 면의 외부로 정의됨

교차점 계산

지엘의 절단

• 3차원좌표(x’, y’, z’)

• 정규화 장치좌표계

• 절단 좌표계 (동차 좌표)

지엘의 절단

• 서더런드 핫지만 알고리즘과 유사

• 지엘은 4차원 절단

• 4차원 교차점 계산이 필요

• 내부점, 외부점, 동일점

선분의 절단

은면제거

• Hidden Surface Removal

• 앞 물체에 가려서 안 보이는 부분

• 물체의 깊이정보(z값)를 기준으로 판단

페인터 알고리즘(painter’s algorithm)

멀리 있는 배경위에 가까운 물체를 덧칠

• 모든 객체에 대한 깊이 정렬(Depth Sort)이 필요

• 물체를 이루는 점 중에서 시점으로부터 가장 먼 Z^max를 기준으로 물체를 정렬

페인터 알고리즘

페인터 알고리즘

• 만일 객체의 Z^max 값이 같을 경우는 어떻게 해야할까?

• A, B, B‘, B’’ 의 Z^max 값이 모두 같다

• B‘, B'‘

• Zmin이 A의 Z^min보다 앞에 있으면 그것을 나중에 그려야 함.

• B

• Zmin이 A의 Z^min보다 뒤에 있으면 그것을 먼저 그려야 함.

• B'‘

• x 또는 y 범위가 서로 중첩되지 않으므로 어느 것을 먼저 그리던지 무관함.

페인터 알고리즘

• 실제로는 이와 같이 단순하지 않으므로 면의 분할이 필요함

• (1)

• 먼저 A, B를 Z^max 기준으로 그려냄.

• (2)

• C와 D는 Z^max는 같지만 x(또는 y)의 범위가 중첩되지 않으니 어느 것을 먼저 그려도 무방함

• (3)

• 최종결과

페인터 알고리즘

페인터 알고리즘

• 가시성 사이클(Visibility Cycle)과 침투(Penetration)

• 페인터 알고리즘

• 물체공간 알고리즘(Object Space Algorithm)

• 정밀도는 높지만 실행속도가 느림

지-버퍼 알고리즘

• 물체공간 vs. 화소공간

• 결국 화소공간으로 사상

• 화소공간 해상도로 은면을 판단하면 됨

• 지-버퍼 알고리즘의 시선

지-버퍼 알고리즘

• 지-버퍼(Z-Buffer) 또는 깊이버퍼(Depth Buffer)

• 지-버퍼 알고리즘

• Initialize Frame Buffer with Background Color;

• Initialize Z Buffer with Infinite Distance;

• for Each Polygon {

• for Each Pixel {

• Calculate z of Intersection

• if (Calculated z < Current z of Z-Buffer) {

• Update Z-Buffer with Calculate z;

• Update Frame Buffer with the Color of Current Polygon;

지-버퍼 알고리즘

지-버퍼 알고리즘

선형보간

• 래스터 변환 단계에서 실행

• 정점으로부터 내부점의 깊이(Depth)및 컬러(Color)를 보간

• 속도개선효과

• 단일 면에 대해서만 적용가능한