주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

2-10

다음 그림은 직선 운동에서 점점 느리게 가는 경우를 나타낸 위치 자료다.

( a ) 각 시간 구간의 속도벡터 방향과 속도벡터의 상대적 크기를 그림에 나타내라.

( b ) 이 운동에서 가속도 방향은 어느 방향인가?

( a )

딱히 "평균속도" 나 "평균가속도" 같은 단서가 붙지 않았기 때문에 두 위치를 연결한 것이 속도벡터이고 그것이 크기를 나타냅니다.

( b )

오른쪽으로 갈수록 속도가 줄어들고 있기 때문에 가속도는 왼쪽방향으로 적용되고 있습니다.

2-11

왼쪽( - ) 방향으로 운동하는 물체의 빠르기가 점점 빨라질 때 평균가속도는 어떤 방향( 부호 )인가?

왼쪽 방향으로 운동하는 물체를 더욱 빠르게 만들기 위해서는 왼쪽으로 가속도가 주어져야 합니다. 그러므로 평균가속도의 방향은 왼쪽( - ) 입니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

일정한 빠르기로 원운동을 하는 물체가 있다. 이 경우 물체가 원을 한 바퀴 도는 데 걸리는 시간을 T 라고 하고, 빠르기를 v₀ 라고 하자. 시계 방향으로 원운동을 하는 물체의 처음 위치를 A 라고 할 때, 그 위치에서의 속도는 접선 방향인 동쪽이 된다. 그리고 시간 T / 4 가 지난 후의 위치 B 에서의 속도는 남쪽을 향한다.

( a ) T / 4 구간에서 속도벡터 변화량 방향, 즉 평균가속도 방향은 어느 방향인가?

( b ) T / 4 구간에서 평균 가속도의 크기가  임을 보여라.

( a )

B 에서의 속도를 v₁ 이라고 할 때, 구간에서의 평균 속도의 방향인 Δv 는 v₁ - v₀ 입니다.

즉, 평속 속도 방향은 남서쪽을 향합니다.

( b )

일정 구간에서 평균가속도의 크기는 다음과 같습니다.

일정한 빠르기로 원운동을 하고 있기에 v₀ 의 속력과 v₁ 의 속력은 동일합니다. 그러므로 피타고라스 정리와 닮은꼴 삼각형의 성질을 이용하면 빗변의 길이를 구할 수 있습니다.√

그림에서 bold 체이면 벡터이고 그렇지 않으면 스칼라라는 점에 주의해 주시기 바랍니다. 그러므로 그림에서 |v₀| = v₀ 입니다.

이제 평균가속도 구하는 식에 값을 대입합니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

어떤 두 시각에서의 속도벡터 v1, v2 가 다음과 같다고 할 때, 평균가속도 벡터를 그림에 표시하라.

"평균가속도" 는 "속도변화량 / 시간변화량" 입니다.

표현을 단순화하기 위해서 일단

t2 - t1 = Δt 

라 하겠습니다. 그러면 평균가속도는 다음과 같습니다.

만약 Δt 가 1 이라면 평균가속도는 그냥 v2 - v1 이 되겠죠.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

달이 원운동을 한 번 하는 데는 약 28 일이 걸린다. 지구 반지름은 6,400 km 고, 지구에서 달까지의 거리는 지구 반지름의 약 60 배다. 달의 빠르기를 시속으로 나타내라.

"시속 = 이동거리 / 시간" 으로 계산되므로 이와 관련한 식을 세워야 합니다.

지구 반지름을 r 이라 하면, 지구에서 달 까지의 거리는 60 r 입니다. 그러면 달이 회전하는 궤도의 반지름이 60r 이라는 의미이며, 그 둘레는 2π * 60r 입니다.

이제 실제 계산을 해 보겠습니다.

달은 지구 주위를 시속 약 3600 km 의 속력으로 회전합니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

원운동에서 원을 한 바퀴 도는 데 걸리는 시간을 주기라 하고, 이를 T 로 나타낸다. 원운동에서 중심점을 원점으로 할 때, 

( a ) 특정 시각의 위치벡터와 그 시각에서부터 1/4 주기 후의 위치벡터를 화살표로 나타내라.

( b ) 변위 벡터를 화살표로 나타내라.

시간 t [second] 에서의 회전각을 θ [radian] 라고 할 때, 시간 T 일 때 θ 는 2pi 입니다. 즉 1 초에 2pi / T 만큼의 각도를 이동하게 됩니다.

반지름이 1 인 원에서 각 θ 일 때의 벡터 r_t 는 ( cos( θ ), sin( θ ) ) 입니다. 만약 반지름이 r 이라 한다면, r_t 는 ( r * cos( θ ), r * sin( θ ) ) 입니다.

여기에서 1/4 주기만큼 이동했다고 하면 그 각 α 는 ( 2pi / T ) / 4 입니다. 정리하면 pi / 2T 입니다.

그러면 θ + α = ( 4 * t + 1 )pi / 2T 입니다.

이제 변위 Δr 은 다음과 같습니다.

실제 벡터를 구하고자 한다면 θ 와 α 에 t 와 T 로 이루어진 식을 할당하면 됩니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

다음 물음들에 답하여라.

( a ) 두 벡터 A, B 가 있을 때, 벡터의 덧셈연산의 정의를 사용하여 다음 관계가 있음을 보여라.

즉 벡터의 덧셈연산은 '교환법칙' 을 만족시킨다.

( b ) 세 벡터 A, B, C 가 있을 때, 다음 관계가 있음을 보여라.

즉 세 벡터에서 덧셈연산은 어떤 순서로 해도 상관없으며, 따라서 '결합법칙' 도 만족시킨다.

( a )

책에서 벡터에 대한 정의를 수학적으로 하지 않은 것으로 봐서는 도식화를 해서 증명하라는 것으로 보입니다.

굳이 수학적으로 증명하자면 다음과 같습니다.

N 차원 벡터 Vn 은 { v1, v2, ..., vn } 이라는 집합으로 정의됩니다. 벡터의 덧셈은 같은 축의 성분끼리의 덧셈입니다.

그러므로 다음이 성립합니다.

각 축 요소들은 스칼라이므로 교환법칙이 성립합니다.

( b )

그림을 그리기 귀찮으니 수학적으로 증명하겠습니다.

각 축 요소들은 스칼라이므로 결합법칙이 성립합니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

2-1

무선 통신에 쓰이는 전자기 파동의 진동수는 1 GHz 다. 여기에서 1 Hz = 1 S^-1 으로 정의하는 양으로, 1 Hz( 헤르츠 ) 는 1 초에 1 번 진동하는 진동수를 뜻한다. 진동수가 1 GHz 인 파동은 1 초에 몇 번 진동하는가?

Giga 는 10⁹ 을 의미하므로 초당 10⁹ 만큼 진동합니다.

2-2

각 변의 길이가 1 nm( 나노미터 ) 인 정육면체 나노입자에는 약 몇 개의 원자가 있다고 추정되는가? 단 원자의 한 변의 길이가 10^-10, 즉 1/10 nm 인 정육면체 형태로 가정하라.

나노입자의 부피는 다음과 같습니다.

원자의 부피는 다음과 같습니다.

나노입자 안의 원자의 개수는 다음과 같이 계산합니다.

나노입자 안에는 원자가 10³ 개 만큼 들어 있습니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

인체는 약 10¹⁵ 개의 세포로 이루어져 있다고 한다. 인체를 이루는 원자의 개수가 10²⁷ 개라면 세포 하나는 약 몇 개의 원자로 이루어져 있는가?

"a" 는 "atomic" 을 의미하고 "c" 는 "cell" 을 의미합니다. 문제는 세포당 원자개수를 구하는 것이기 때문에 다음과 같이 풀수 있습니다.

세포 하나는 약 10¹² 개의 원자로 구성되어 있습니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

공이나 책과 같이 우리가 주위에서 보는 물체의 크기는 1 cm, 1 m 등과 같이 미터 단위로 측정할 수 있다. 우리가 주위에서 볼 수 있는 물체의 원자가 몇 개나 모여서 이루어진 것인지 짐작해 보자.

( a ) 정육면체 모양의 물체의 한 변의 길이를 0.1 m 라 가정하면, 그 부피는 얼마인가?

( b ) 원자의 지름은 10^-10 m 이다. 원자를 한 변의 길이가 10^-10 m 인 정육면체로 본다면, 원자를 차곡차곡 쌓아 ( a ) 의 물체를 이루었을 때 물체 속 원자 개수는 몇 개인가?

( a )

정육면체의 부피를 구하는 식은 한 변의 길이를 n 이라고 할 때 다음과 같습니다.

그러므로 한 변의 길이가 0.1 m 인 정육면체의 부피는 다음과 같습니다.

( b )

한 변의 길이가 10^-10 m 인 원자 정육면체의 부피는  10^-30 [ m³ ] 입니다. 그러므로 물체속의 원자 개수를 다음과 같이 계산할 수 있습니다. "N" 은 "Number" 를 의미합니다. 첨자 "o" 는 "object" 를 "a" 는 "atomic" 을 의미합니다.

정육면체 물체에는 원자가 10²⁷ 개가 들어 있습니다. 

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

원자핵의 반지름이 원자 반지름의 10^-5 일 때, 핵의 부피는 원자 부피의 몇 배인가?

문제를 풀기 전에 책의 설명이 좀 부실해서 부연하고자 합니다. 

[ Units of Measurement ] 에 의하면 소수점 1000 단위마다 밀리( milli ), 마이크로( micro ), 나노( nano )라는 단위로 나뉩니다( 나중에 표 2-2 로 나오기는 하네요 ).

출처 : [ Units of Measurement ].

원자의 중심에 원자핵이 있으므로 원자와 원자핵의 관계는 다음과 같습니다.

원자핵의 반지름을 r 이라 하고 원자의 반지름을 r' 이라고 할 때 다음과 같은 관계식을 만들 수 있습니다.

이를 부피를 구하는 관계식에다가 넣으면 다음과 같습니다. 여기에서 아래첨자 "a" 는 "atomic" 을 "n" 은 "nucleus" 를 의미합니다 .

그러므로 원자의 부피는 원자핵의 부피보다 10¹⁵ 만큼 큽니다.

주의 : 답이 틀릴 수도 있습니다. 그냥 정리하는 용도로 올립니다. 혹시라도 도움이 필요한 분이 있다면 도움이 되었으면 좋겠네요.

경고 : 숙제하려고 베끼는 데 사용하지 마십시오. 본인의 미래를 망칠 뿐입니다. 나중에 저를 원망하지 마세요.

부탁 : 문제 풀이가 잘못되었으면 지적해 주셨으면 좋겠습니다.

우리가 보는 달과 태양은 크기가 비슷하게 보인다. 태양이 달보다 훨씬 크지만, 달보다 더 멀리 떨어져 있어서 그렇게 보일 뿐이다. 실제로 달까지의 거리는 지구 반지름의 약 60 배이고, 태양까지의 거리는 약 23450 배이다.

( a ) 이로부터 추정되는 태양의 반지름은 달의 반지름의 몇 배인가.

( b ) 태양이 달과 같은 물질로 구성되어 있다고 가정하면( 실제로는 그렇지 않다 ), 태양의 질량은 달의 질량의 몇 배인가?

( a )

지구의 반지름을 r, 달의 반지름을 r', 태양의 반지름을 r'' 이라고 하죠. 그러면 아래와 같은 관계가 형성됩니다.

닮은꼴 삼각형이 두 개가 존재함을 알 수 있습니다. 그러므로,

입니다.

태양은 달보다 약 400 배 정도가 큽니다.

( b )

밀도를 구하는 식은 다음과 같습니다. ρ 는 밀도, M 은 질량, V 는 부피입니다. 

즉 질량은 밀도 곱하기 부피입니다. 같은 물질로 구성되었다고 가정하면 밀도는 동일하므로 결국 질량은 부피에 비례합니다.

구의 부피를 구하는 식은 다음과 같습니다. 잘 모르시는 분들은 [  구의 부피와 구의 겉넓이 ] 를 참고하세요.

그러므로 태양과 달의 질량비는 다음과 같습니다.

그러므로 이 조건에서는 태양이 달보다 약 64,000,000 배 정도 무겁습니다.

원문 : Highly divisible triangular number

삼각수

일단 삼각수라는 것이 무엇인지 찾아 봤습니다. 위키백과에 따르면 삼각수란 다음과 같습니다[ 1 ].

삼각수(三角數, triangular number), 또는 "삼각형 수" 는 일정한 물건으로 삼각형 모양을 만들어 늘어 놓았을 때, 그 삼각형을 만들기 위해 사용된 물건의 총 수가 되는 수를 말한다.

예를 들어 아래와 같이 네 줄에 걸쳐 삼각형을 만들었을 때 늘어 놓은 물건의 총 수는 10 개가 되며, 10 은 삼각수의 하나가 된다.

n 번째 삼각수 N 은 1 부터 n 까지의 자연수를 모두 합한 것이고, 여기서 삼각수의 정의로 인하여 n 은 반드시 자연수여야 한다. 삼각수의 수열은 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 230... 과 같고 n 번째의 삼각수 N 은 N = n( n + 1 ) / 2 로 나타낼 수 있다. 모든 자연수는 최대 3 개의 삼각수의 합으로 표현할 수 있다는 정리가 있으며, 이는 카를 프리드리히 가우스가 1796 년( 가우스의 일기에 따르면 7월 10일 )에 증명하였다. 이 정리는 모든 자연수는 최대 n 개의 n 각수의 합으로 표현할 수 있다는 페르마의 다각수정리의 한 경우이다.

Solution

일단 먼저 n 번째 삼각수를 찾아야 합니다. 위키백과를 보지 않았다면 어쩔 수 없이 무식하게 삼각수를 더하면서 찾았겠죠. 

이 문제는 일단 해결이 되었습니다. n 번째 삼각수를 n( n + 1 ) / 2 로 나눌 수 있다고 했기 때문에 n 을 증가시켜가면서 삼각수를 찾는 것이 가능합니다. 그래도 진짜 식이 맞는 건지 확인을 해 보도록 하겠습니다. 

일단 위의 그림에서 삼각형의 1, 3, 6, 10 은 삼각수를 구성합니다. 패턴을 보니 숫자의 개수가 1, 2, 3, 4 이런 식으로 증가하는군요. 결국 삼각형의 행을 구성하는 마지막 숫자는 이것은 1 부터 n 까지의 자연수의 합을 구하는 문제와 같습니다. 1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3, 10 = 1 + 2 + 3 + 4, N = n( n + 1 ) / 2 입니다.

다음 문제는 이것의 인수를 찾는 건데요, 안타깝게도 문제에 있는 28 의 경우를 보면 소인수가 아니라 그냥 인수입니다. 일단 소인수를 다 구한다음에 그것을 곱해가면서 5 개의 인수로 만들어낼 수 있는지 찾아야 합니다.

저는 여기에서 하나의 규칙을 찾았습니다.

N = a * b 라 했을 때, a 는 [ 1, N / 2 ) 범위의 자연수입니다. 왜냐하면 a 가 1 일 때 b 가 N 이니까, a 가 2 일 때 가장 큰 b 가 나오기 때문이죠.

그리고 a 와 b 는 가능한 몫들을 나열했을 때 아래 그림처럼 대칭을 이루며 몫의 개수가 짝수가 됩니다.

하지만 28 의 경우를 보면 a 의 범위가 [ 1, 14 ) 가 되는데 그 범위에 7 이 들어 있습니다. 이렇게 되면 대칭이 안 되기 때문에 b 가 이미 a 로 선정이 된 경우에는 배제해야 합니다. 이를 자연스럽게 배제할 수 있는 방법을 생각해 봤습니다.

인수의 관점에서 생각해 봤습니다. b <= N / a 입니다. 그리고 a <= N / b 입니다. 여기에서 a == b 일 때가 a 의 최대값입니다. 그렇다면 N = a² or b² 이므로, a 는 다음과 같은 범위를 가진다고 할 수 있습니다: [ 1, root( N ) ]. 매우 간단한 사실인데 이상한 고민을 했군요.

마지막으로 몫의 개수에도 예외가 있습니다. N 이 제곱수일 경우입니다. 이 경우에는 몫이 홀수개가 나옵니다. 왜냐하면 제곱이니 a 와 b 가 동일하기 때문이죠. 위에서 1 의 몫도 홀수이고 36 의 몫도 홀수입니다. 그러니 N 이 제곱수라면 계산할 필요도 없겠죠. 문제에서 500 개의 몫을 가진다고 했기 때문에 몫의 개수가 짝수입니다. 그러므로 N 이 제곱수일 경우를 배제해야 합니다.

import math i = 0 while( True ) : tn = int( i * ( i + 1 ) / 2 ) # make triangulr number i += 1 # increase number for next loop root = math.sqrt( tn ) # get square-root nroot = int( root ) # get natural number of square-root if root == nroot : # if root is natural number continue # goto next number if( nroot < 250 ) : # if root is less than 250 continue # goto next number count = 0 # reset factor count for factor in range( 1, nroot + 1 ) : # for each number if 0 == ( tn % factor ) : # check if remainder is 0 count += 2 # add 2 factors if 500 == count : # if number of fa-ctors is 500 print( tn ) # print it break # break while

하지만 10 분이 지나도록 답이 없었습니다. 이렇게 해결하는 것은 좋은 답이 아닐 것 같다는 생각이 들더군요. 좀 더 규칙을 찾아 보기로 했습니다.

n 번째 삼각수가 n( n * 1 ) / 2 라고 하지만, 이것을 잘 살펴 보면 결국 n 번째 삼각수는 기존의 n 번째 삼각수에서 n 개 만큼 더한 것이라는 것을 알 수 있습니다.

그렇다면 다음과 같이 구현할 수 있습니다.

prev_tn = 0 i = 1 while( True ) : tn = prev_tn + i # make triangulr number prev_tn = tn # set previous triangular number i += 1 # increase number for next loop root = math.sqrt( tn ) # get square-root [ ... ] [ ... ]

그런데 아무래도 몫의 종류가 500 개라는 것을 최적화할 수 있는 방법이 떠 오르지 않더군요.

결국 다른 사람의 구현( Jason's code blog )을 찾아 봤습니다.

n 과 n + 1 의 소인수 분해를 알고 있다고 하면 그것을 다음과 같이 작성할 수 있습니다.

n 과 n + 1 은 어떤 소인수도 공유할 수 없다는 것에 주목하십시오( 왜냐하면 그것들은 연속적인 숫자이기 때문입니다 ). 그리고 우리는 pi 와 qi 가 구별되는 소수임을 알고 있습니다. 또한 n 이나 n + 1 은 둘 중에 하나만 2 로 나눠집니다. 그러므로 지수 ei 와 fi 만이 T( n ) 을 나누는 숫자를 결정하기 위해서 고려할 필요가 있는 것들입니다. T( n ) = ( n( n + 1 ) )/2 는 n 이나 n + 1 의 인수분해에서 두 숫자의 제곱을 배제할 필요가 있다는 것을 의미합니다( 둘중의 하나만의 짝수라는 것을 기억하세요 ). 일관성을 지키기 위해서 n 이 짝수이고 p = 2 라고 가정해 봅시다. 그러면 T( n ) 의 전체 인수의 개수는 다음과 같은 조합으로 표현될 것입니다:

더 개선하자면, 삼각수를 증가시킬 때, 이전의 n 은 이미 계산했기 땜누에 n + 1 만 계산해도 됩니다. 이는 실시간 비용을 조금이라도 줄여줄 것입니다.

그래서 다음과 같이 하더군요.

import time def num_divisors(n): if n % 2 == 0: n = n/2 divisors = 1 count = 0 while n % 2 == 0: count += 1 n = n/2 divisors = divisors * (count + 1) p = 3 while n != 1: count = 0 while n % p == 0: count += 1 n = n/p divisors = divisors * (count + 1) p += 2 return divisors def find_triangular_index(factor_limit): n = 1 lnum, rnum = num_divisors(n), num_divisors(n+1) while lnum * rnum < 500: n += 1 lnum, rnum = rnum, num_divisors(n+1) return n start = time.time() index = find_triangular_index(500) triangle = (index * (index + 1)) / 2 elapsed = (time.time() - start) print "result %s returned in %s seconds." % (triangle,elapsed)

결과는 76576500 입니다.

참고자료

[ 1 ] 삼각수. 위키백과.

원문 : Largest product in a grid.

Brute-Force

이 문제를 가시화하면 다음과 같습니다. ( i, j ) 요소를 중심으로 살펴 보시다. 그러면 아래 그림에서 검은색을 중심으로 색칠해져 있는 부분들의 곱을 구해서 가장 큰 숫자들을 찾으면 됩니다.

그런데 딱 봐도 루프를 돌 때 중복되는 부분이 많을 것 같다는 생각이 듭니다. 특정 방향은 다른 좌표를 중심으로 하는 셸을 계산할 때 서로 겹치므로 배제될 수 있습니다( 예를 들어 왼쪽과 오른쪽, 위쪽과 아래쪽, 위쪽 대각선과 아래쪽 대각선 ).

이 정도로 최적화라고 부르긴 좀 뭐해서 여기까지 Brute-Force 라 생각하도록 하겠습니다.

str_num = ( "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 " "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 " "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 " "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 " "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 " "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 " "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 " "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 " "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 " "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 " "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 " "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 " "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 " "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 " "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 " "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 " "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 " "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 " "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 " "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48" ) strs = str_num.split() count = 0 arr = [] for str in strs : arr.append( int( str ) ) def max_value( left, right ) : return left if ( left > right ) else right product = 0 for j in range( 20 ) : for i in range( 20 ) : index = j * 20 + i if i > 2 and j < 17 : current_product = arr[ index ] * arr[ index + 19 ] * arr[ index + 38 ] * arr[ index + 57 ] product = max_value( product, current_product ) if i < 17 : current_product = arr[ index ] * arr[ index + 1 ] * arr[ index + 2 ] * arr[ index + 3 ] product = max_value( product, current_product ) if j < 17 : current_product = arr[ index ] * arr[ index + 20 ] * arr[ index + 40 ] * arr[ index + 60 ] product = max_value( product, current_product ) if i < 17 and j < 17 : current_product = arr[ index ] * arr[ index + 21 ] * arr[ index + 42 ] * arr[ index + 63 ] product = max_value( product, current_product ) print( product )

답은 70600674 입니다.

Other's solution

다른 사람들의 구현을 살펴 봤는데, 루프를 도는 방식에 조금 차이가 있을 뿐이고 크게 다르지는 않더군요.

그런데 파이썬에서 동적으로 자료구조를 만드는 편리한( 코드가 짧은 ) 방법들이 있는데, 꽤 어렵네요. [ JASON'S CODE BLOG ] 에서는 다음과 같이 2 차 배열을 만듭니다.

M = [i.split() for i in L] M = [[int(j) for j in i] for i in M]

파이썬은 문법이 뭔가 살짝 괴랄하지만 익숙해지면 편하게 쓸 수 있을 것 같아 보이네요.

원문 : Summation of primes

계속해서 나오는 소수 문제네요. [ 3. Largest prime factor ] 에서는 가장 큰 소인수를, [ 7. 10001 st pime ] 에서는 n 번째 소수를, 이 번에는 일정 이하의 소수의 합을 구하는 겁니다.

Brute-Force

def sum_primes_until( max ) : primes = list() primes.append( 2 ) primes.append( 3 ) primes.append( 5 ) i = 7 # second prime number, and odd number. sum = 2 + 3 + 5 while( i < max ) : is_prime = True for p in primes : # for each prime number if 0 == ( i % p ) : # i is evenly divided by prime number is_prime = False # i is not prime number break if is_prime : primes.append( i ) sum += i i += 2 # select next odd number if 0 == ( i % 5 ) : # if next odd number is multiple of 5 i + 2 # select next odd number return sum print( sum_primes_until( 2000000 ) )

일단 답은 142913828922 입니다.

나름대로 최적화를 한다고 했지만 O( mn ) 의 시간 복잡도를 가집니다. m 과 n 의 크기가 크므로 비용이 장난이 아닙니다. 한 10 분은 걸린 것 같군요.

소수와 관련해서 점점 더 극악한 조건을 제시하면서 결국에는 최적화를 더 하게 만드는군요.

Others Optimization

[ 7. 10001 st pime ] 의 공식 [ PDF ] 에서 최적화를 위해 사용한 전제들은 다음과 같습니다.

• 1 은 소수가 아님.
• 2 를 제외한 모든 소수는 홀수임.
• 3 보다 큰 모든 소수는 6k+/-1 로 작성될 수 있음.
• 어떤 수 n 은 루트 n 보다 큰 소수를 하나만 가지고 있을 수 있음.
• 어떤 수 n 에 대한 소수 테스트를 하기 위한 수열은 : n 을 나누는 루트 n 보다 작거나 같은 숫자 f 를 발견하지 못한다면, n 은 소수임 : n 의 유일한 소인수는 n 자체임.

뭔가 최적화의 여지가 상당히 많군요.

import math def isprime( n ) : if 1 == n : # 1 is not prime. return False elif n < 4 : return True # 2, 3 elif 0 == ( n % 2 ) : return False # even is not prime. elif n < 9 : return True # even is excluded, reamins 5, 7, 9. elif 0 == ( n % 3 ) : return False # multiple of 3 is excluded else : r = math.floor( math.sqrt( n ) ) f = 5 while f <= r : # check if n is divided by other prime( form of 6k+/-1 ) if 0 == ( n % f ) : return False if 0 == ( n % ( f + 2 ) ) : return False f += 6 return True sum = 2 for n in range( 3, 2000001, 2 ) : if isprime( n ) : sum += n print( sum )

실행해 보니 정상적인 결과가 나왔고, 무진장 빠르군요. 이것도 사실 O( mn ) 의 비용이 듭니다만, Brute-Force 방식보다는 m 과 n 의 크기가  작으므로 매우 빠릅니다. 거의 20 초 정도면 끝나는군요.

원문 : Special Pythagorean triplet

Brute-Force

일단 연립방정식으로 풀 수 있는지 확인을 해 봤습니다만, 방정식이 하나가 부족해서 풀수가 없네요. 어떻게든 하나의 변수값은 알아야 나머지를 풀 수 있는 형태입니다.

결국 삼중 루프를 도는 수밖에 없습니다. 

다음을 만족하는 값들을 찾아야 합니다. 그런데 a 와 b 를 알면 c 를 구할 수 있으므로, 이중 루프만 돌아도 됩니다.

def find_pythagorean_product( sum ) : for b in range( 1, sum ) : b_2 = b * b for a in range( 1, b ) : # a < b a_2 = a * a c = sum - a - b # a + b + c = sum if ( b < c ) and ( ( c * c ) == ( a_2 + b_2 ) ) : # b < c, a^2 + b^2 = c^2 print( "a = {0}, b = {1}, c = {2}".format( a, b, c ) ) return a * b * c print( find_pythagorean_product( 1000 ) )

답은 31875000 입니다.

Others Solution

Math Blog 의 [ A 1000 Pythagorean triplets – Problem 9 ] 에 수학적인 접근이 있더군요. 궁금하면 확인해 보시기 바랍니다.

원문 : Largest product in a series

일단 간단하게 생각하면 그냥 루프를 돌면서 15 개씩 묶어서 곱해보는 것이 가장 단순합니다. 먼저 하나의 1000 자리 숫자를 여러 개의 1 자리 숫자로 나누는 작업이 필요하겠죠.

그런데 이 작업을 하려면 1000 자리가 들어 갈 수 있는 자료형이 필요합니다. 컴퓨터는 데이터를 이진수로 저장하기 때문에, 이를 표현하기 위해서는 얼마나 큰 비트가 필요할까요?

계산을 해 보도록 하겠습니다.

이진수로 자리수를 올리는 것은 한 비트씩 옮기는 겁니다. 아래 첨자가 2 라고 되어 있으면 이진수를 그렇지 않으면 십진수를 의미합니다.

그렇다면 십진수는 어떨까요( 아래에서 왼쪽 항을 볼 때 주의할 점은 십진수 표현이라는 것입니다. 줄을 맞추려고 앞에 0 을 넣었습니다. 아래 첨자가 없다는 점에 주의하세요 ).

그럼 10 의 멱승을 이진수로 표현해 보죠.

뭔가 규칙이 있을까요? 십진수가 1 자리 올라갈 때마다, 이진수는 3 자리나 4 자리가 올라가는 것을 알 수 있습니다. 이렇게 볼 때 십진수로 표현했을 때 1000 자리가 되려면 이진수로 고쳤을 때 최대 4000 자리( 즉 4000 비트 )가 필요함을 알 수 있습니다.

즉 1000 자리 숫자는 현재의 이진수 컴퓨팅 환경에서 표현하는 것이 불가능한 숫자입니다.

Brute-Force

그래서 이를 그냥 문자열로 표현하기로 했습니다. 그리고 계산할 때마다 형변환하는 것을 피하기 위해서 미리 형변환해서 리스트에 넣었습니다. 계산 방식 자체는 단순합니다. 그냥 처음부터 13 개씩 계산하면 됩니다.

str_num = ( "73167176531330624919225119674426574742355349194934" "96983520312774506326239578318016984801869478851843" "85861560789112949495459501737958331952853208805511" "12540698747158523863050715693290963295227443043557" "66896648950445244523161731856403098711121722383113" "62229893423380308135336276614282806444486645238749" "30358907296290491560440772390713810515859307960866" "70172427121883998797908792274921901699720888093776" "65727333001053367881220235421809751254540594752243" "52584907711670556013604839586446706324415722155397" "53697817977846174064955149290862569321978468622482" "83972241375657056057490261407972968652414535100474" "82166370484403199890008895243450658541227588666881" "16427171479924442928230863465674813919123162824586" "17866458359124566529476545682848912883142607690042" "24219022671055626321111109370544217506941658960408" "07198403850962455444362981230987879927244284909188" "84580156166097919133875499200524063689912560717606" "05886116467109405077541002256983155200055935729725" "71636269561882670428252483600823257530420752963450" ) nums = list() for c in str_num : nums.append( int( c ) ) max_product = 0 offset = 0 num_adjacency = 13 max_offset = len( nums ) - num_adjacency - 1 while( offset < max_offset ) : product = 1 for i in range( offset, offset + num_adjacency ) : product *= nums[ i ] max_product = max( max_product, product ) offset += 1 print( max_product )

답은 23514624000 입니다.

Optimization

하지만 다른 문제들처럼 뭔가 다른 빠른 방법이 있을 것이라는 강박관념이 들더군요.

MathBlog 의 [ Solution to Problem 8 of Project Euler ] 의 댓글을 보니, 마지막 곱들을 저장해 놓는 것에 대한 이야기가 있었습니다. 

그렇다면 이전의 곱셈 결과에서 이전의 시작값을 나누고 다음에 올 값을 곱한다면, 문제가 해결될 수 있겠다는 생각이 들더군요. 그런데 실제 해 보니 안 됐습니다. 중간에 0 이 있으면 모든 값이 무산된다는 것을 고려하지 않은거죠. 만약 0 인 숫자가 하나도 없다면 가능할 것 같네요.

Other's Solution

[ Project Euler 8: Find the largest product of 13 consecutive digits ] 에서는 파이썬의 언어특성을 잘 이용해서 매우 짧은 코드를 작성하고 있습니다.

#Project Euler Problem 8 from operator import mul d = map(int, ''.join(line.rstrip() for line in open('pe8.txt'))) L = 13 print 'Greatest product of', L, 'consecutive \ndigits =', print "None." if L>len(d) else \ max(reduce(mul, d[i:i+L]) for i in xrange(len(d)-L+1))

솔직히 파이썬 자료구조와 알고리즘에 대한 공부를 많이 안해서 이해하기가 힘드네요.

원문 : Smallest multiple

일단 특정 범위의 숫자로 나눴을 때 나머지가 없다는 이야기는 그 숫자들이 곱해져있다는 의미일 겁니다.

예를 들어 1 부터 10 까지의 숫자로 곱해진 숫자라면 어떤 수로 나눠도 나머지가 없는 수가 나오겠죠.

그런데 여기에서 우리는 규칙을 하나 알 수 있습니다. 합성수는 소수의 곱으로 되어 있기 때문에, 소수가 중복된다는 겁니다. 

예를 들어 10 은 2 * 5 로 구성되었기 때문에 2 와 5 가 중복됩니다. 그러면 2 와 5 를 한 번씩 빼도 2, 5, 10 으로 나누어 떨어질 수 있죠.

소인수 분해를 해 보도록 하겠습니다. 1 은 소수가 아니고 곱셈에 영향을 주지 않으므로 배제합니다.

여기에서 우리는 일련의 규칙을 발견할 수 있습니다. 소인수 분해를 했을 때 합성수를 만들기 위해서 필요한 최대 소수의 개수를 알 수 있다는 것입니다.

예를 들자면 4 로 나누기 위해서는 적어도 2 가 2 개가 존재해야 합니다. 6 으로 나누기 위해서는 적어도 2 가 1 개, 3 이 1 개가 존재해야 합니다. 8 로 나누기 위해서는 적어도 2 가 3 개가 존재해야 합니다. 9 로 나누기 위해서는 적어도 3 이 2 개는 존재해야 합니다. 10 으로 나누기 위해서는 적어도 2 가 1 개, 5 가 1 개가 존재해야 합니다. 그 이외의 소수들( 여기에서는 7 )은 1 개씩만 존재하면 되죠.

정리하면 2 가 3 개, 3 이 2 개, 5 가 1 개, 7 이 1 개가 필요합니다.

위의 문제와 동일한 답이 나오는군요.

Brute-Force

이제 알고리즘을 세워 보도록 하겠습니다.

• 2 부터 20 까지의 모든 수를 돌면서 소인수 분해를 합니다.
• 소인수 분해를 했을 때, 각 소인수의 개수를 세서, 소수의 최대 횟수를 구합니다.
• 소수의 최대 횟수만큼 곱합니다.

일단 소인수들을 구하는 함수는 [ 3. Largest prime factor ] 에서 가지고 왓습니다.

def get_prime_factors( target ) : quotient = target prime_factors = list() append_factors = prime_factors.append i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i append_factors( i ) else : i += 1 if 0 == ( i % 2 ) else 2 return prime_factors

이제 각 factor 의 카운트를 세서 곱하는 구현을 합니다.

total_max_count = dict() for i in range( 2, 21 ) : max_count = dict() prime_factors = get_prime_factors( i ) for p in prime_factors : if p in max_count : max_count[ p ] += 1 else : max_count[ p ] = 1 max_count_keys = max_count.keys() for key in max_count_keys : if key in total_max_count : total_max_count[ key ] = max( total_max_count[ key ], max_count[ key ] ) else : total_max_count[ key ] = max_count[ key ] smallest_number = 1 total_max_count_keys = total_max_count.keys() for key in total_max_count_keys : for c in range( total_max_count[ key ] ) : smallest_number *= key print( smallest_number )

조금 코드가 길지만 첫 번째 최상위 루프를 통해서 소인수들을 얻어서 최대 카운트를 셉니다. 그리고 두 번째 루프에서는 최대 카운트만큼 소인수들을 곱해줍니다.

결과는 232792560 입니다.

Other's solution

다른 해법이 있는지 찾아 봤습니다. 공식 PDF 에서는 뭔가 엄청 단순한 형태로 푸는군요. 뭔 sqrt 와 log 가 나오고 난리입니다. 기본적으로 반복횟수를 이용해서 푸는 것은 동일한데, 위의 식을 다음과 같이 표현하는데서 알고리즘을 시작합니다.

i 번째 소수를 pi 라고 하고 지수를 ai 라 할 때 N 은 다음과 같습니다.

여기에서 pi^ai 을 k 라고 하면, ai 는 다음과 같습니다.

예를 들어, k = 20 이라고 하면, 첫 번째 소수인 p1 = 2 입니다. 그러면 다음과 같이 a1 을 구할 수 있습니다.

정수여야 하므로 floor 를 사용합니다. 최적화를 위해서 pi <= sqrt( k ) 인 경우의 ai 만을 계산한다고 합니다.

이것을 일반화해서 다음과 같이 계산한다고 합니다.

자세한 건 pdf 에서 확인해 보시기 바랍니다.

원문 : Largest palindrome product

Brute-Force

일단 제가 생각한 알고리즘은 다음과 같습니다.

• 세 자리 수의 곱으로 표현할 수 있는 수들을 검색합니다.
• 그 중에서 대칭수를 찾습니다.
• 가장 큰 대칭수로부터 내림차순으로 소인수분해를 해서 세 자리 수의 곱으로 표현된다면 그것이 가장 큰 대칭수입니다.

세 자리 수 중에서 가장 큰 것은 999 이고 가장 작은 것은 100 입니다. 그러므로 대상이 될 수 있는 수의 범위는 [ 100 * 100, 999 * 999 ] 입니다; [ 10,000, 998,001 ].

일단 가장 먼저 할 일은 어떤 숫자를 자리수로 쪼개는 함수를 만드는 거겠죠. 만드는 김에 두 번째 인자로 진법( numeral_system )을 넣도록 해 봤습니다.

def split_value( value, numeral_system ) : values = list() quotient = value while( 0 != quotient ) : remainder = quotient % numeral_system values.append( int( remainder ) ) quotient = quotient // numeral_system values.reverse() return values

15 부터 25 까지 십진법과 이진법으로 출력해 보면 결과는 다음과 같습니다.

이제 해당 숫자가 대칭수인지 확인하는 함수가 필요하겠죠. 어떤 숫자가 있을 때 중심이 되는 인덱스를 구하고 하나는 오름차순으로 하나는 내림차순으로 인덱싱하면서 값을 비교합니다. 만약 홀수개로 구성된 숫자가 있다면, 중간값은 항상 한 개이므로 비교할 필요가 없겠죠.

def is_palindrome_number( value ) : values = split_value( value, 10 ) num_values = len( values ) count = num_values // 2 for i in range( count ) : a = values [ i ] b = values [ num_values - 1 - i ] if a != b : return False return True

이제 루프를 돌면서 대칭수를 전부 출력해 보겠습니다. 

for i in range( 10000, 998002 ) : if( is_palindrome_number( i ) ) : print( i )

엄청나게 많군요... 그래서 여기에 올리지는 않았습니다. 어쨌든 가장 큰 대칭수는 997799 입니다. 물론! 이것이 답은 아닙니다. 왜냐하면 세 자리 수의 곱으로 표현될 수 있어야 하기 때문입니다.

성능을 고려하면 이것을 큰 수부터 내림차순으로 해야 합니다. 파이썬의 for 는 이런 부분에서 참 불편하군요. 범위가 헷갈립니다.

for i in range( 998001, 9999, -1 ) :

자 이제 [ 3. Largest prime factor ] 에서 만들었던 소인수분해해서 소인수 리스트를 반환하는 함수를 가지고 와서 사용할 겁니다.

def get_prime_factors( target ) : quotient = target prime_factors = list() append_factors = prime_factors.append i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i append_factors( i ) else : i += 1 if 0 == ( i % 2 ) else 2 return prime_factors

리스트로 받은 소인수들을 곱해가지고 두 개의 세 자리 수를 만들어야 합니다. 여기가 가장 어려운데요...

• 일단 세 자리수가 나오는 경우의 수를 모두 찾습니다. 앞에서부터 곱해도 되고 뒤에서부터 곱해도 되겠죠. 아마도 뒤에서부터 곱하는 것이 빠를 겁니다. 왜냐하면 리스트의 뒤쪽으로 갈 수록 큰 소인수이기 때문입니다.
• 하나의 세 자리 수가 나오면 나머지 소인수들을 모두 곱했을 때, 그 결과가 세 자리 수가 아니면 실패입니다.

저는 뒤에서부터 숫자를 곱해 봤습니다.

def can_make_3_digit_product( val, factors ) : temp = factors.copy() factor_1 = 1 factor_2 = 1 while( 0 < len( temp ) ) : factor_1 *= temp.pop() if 99 < factor_1 < 1000 : break while( 0 < len( temp ) ) : factor_2 *= temp.pop() if ( 99 < factor_1 < 1000 ) and ( 99 < factor_2 < 1000 ) : print( "%d = %d * %d" % ( val, factor_1, factor_2 ) ) return True return False

물론 이렇게 하는 건 잘못된 결과를 산출합니다. 왜냐하면 다음과 같은 경우를 생각해 보죠.

2 * 79 = 158 이고 3 * 83 = 249 로 해야지 세 자리 수의 곱이 나옵니다. 결국 모든 경우의 수를 찾지 않으면 정확한 결과를 구할 수가 없습니다. 결국 세 자리를 만들수 있는 경우의 수를 모두 구해야 합니다.

친구( 햄짱 )에게 이걸 해결할 쌈박한 아이디어가 있는지 물어 봤습니다. 그런데 "경우의 수를 모두 구하는 건 너무 복잡하니 세 자리 수를 모두 곱해서 대칭수가 나오는 것을 찾는 게 낫지 않겠냐"는 대답을 들었습니다. 

생각해 보니, 문제가 "특정 수를 대칭으로 만드는 세 자리 수의 곱을 찾아라" 가 아니기 때문에, 그렇게 하는 게 낫겠다는 생각이 들었습니다.

result = 0 for i in range( 999, 99, -1 ) : for j in range( 999, 99, -1 ) : number = i * j if is_palindrome_number( number ) : result = max( number, result ) print( result )

답은 906609 입니다.

Optimization

그런데 제가 만든 식은 성능에 문제가 있습니다. 왜냐하면 코드를 보면 알 수 있겠지만, 중간에 break 를 하지 않습니다. 그 이유는 이중 루프를 사용했을 때 먼저 나오는 수가 가장 큰 수라고 보장할 수 없기 때문입니다.

예를 들면, 가장 먼저 나오는 수는 995 * 583 = 580085 입니다. 이것은 993 * 913 = 906609 보다 작습니다. 그래서 루프를 다 돌 수 밖에 없는데요, 이를 최적화할 수 있는 방법이 필요합니다. 

문제를 풀고 나면 나오는 Lster 이라는 사람이 작성한 PDF 를 보면, 다음과 같이 일반식을 찾습니다.

세 자리 수를 곱했을 때 나오는 대칭수는 최대 xyzzyx 형태의 여섯자리 수가 됩니다. 이를 식으로 정리하면 다음과 같습니다.

즉 11 의 배수 형태가 나온다는 것입니다. 그러므로 둘 중의 하나는 소인수분해를 했을 때 반드시 11 을 포함해야 합니다.

그러면 아래와 같이 코드를 작성해 볼 수 있습니다.

result = 0 for i in range( 999, 99, -1 ) : for j in range( 999, 99, -1 ) : if ( 0 == ( i % 11 ) ) or ( 0 == ( j % 11 ) ) : number = i * j if is_palindrome_number( number ) : result = max( number, result ) print( result )

해당 문서에서는 조금 더 복잡한 최적화를 하고 있는데, 관심이 있으면 살펴 보시기 바랍니다.

원문 : Largest prime factor

Prime factor

일단 소인수가 뭔지 알아야 합니다. 일단 제가 알고 있는있는 소인수의 정의는 다음과 같습니다.

자신과 1 을 제외하고는 나눠지지 않는 않는 수.

실제 정의를 찾아 보았습니다만, 위에서 제가 한 정의는 "소수( prime number )" 에 대한 정의군요. 그리고 자연수여야 한다는 조건도 빠졌구요.

소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. ( 중략 ) 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

출처 : [ 1 ].

구글 사전에서는 소인수를 다음과 같이 정의하더군요.

어떤 정수(整數)를 소수(素數)만의 곱으로 나타낸 때의 각 인수(因數).

구글 사전에서는 인수를 다음과 같이 정의하고 있습니다.

정수 또는 정식(整式)을 몇 개의 곱의 형태로 하였을 때, 그것의 각 구성 요소. 인자(因子).

즉 소인수는 "소수인 인수" 를 의미하는 거군요.

Generate prime numbers

그럼 가장 먼저 생각해 봐야 할 부분은 소수를 검사할 수 있는 방법이겠네요. 일단 소수값들을 나열해 봤습니다.

2 가 유일한 짝수이고 나머지는 홀수입니다. 그렇다면 계산의 시작은 더 이상 2 로 나눠질 수 없을 때까지 2 로 나누는 거겠죠.

예를 들어 60 이라는 수는 2 * 2 * 15 로 구성됩니다. 그러면 15 라는 수가 남네요. 이제 다음 소수인 3 으로 같은 작업을 반복할 수 있을 것입니다. 그러면 15 는 3 * 5 로 구성됩니다. 그러면 5 라는 수가 남네요. 이제 다음 소수인 5 로 같은 작업을 수행합니다. 그러면 5 * 1 이 되고, 1 은 나눌 수 없으니 계산이 종료될 겁니다. 결국 2, 3, 5 가 60 을 구성하는 소인수들이 됩니다. 

그런데 이건 합성수의 소인수를 찾는 것( 소인수분해 )이지 소수 자체를 구하는 것이 아닙니다. 그런데 이 소인수분해를 하는 과정자체가 소수를 찾는 과정이 아닐까라는 생각이 들었습니다.

왜냐하면 "자신과 1 을 제외한 자연수로 나눌 수 없는 자연수" 라는 정의를 생각하면 다음과 같은 가정을 깔 수 있을 것이기 때문입니다.

자신보다 작은 소수로 나눠봤을 때 나누어 떨어지면 그것은 소수가 아니다.

그러면 아래와 같이 소수를 생성해 볼 수 있습니다.

prime_numbers = [ 2 ] def generate_prime_numbers( max ) : for i in range( 3, max + 1) : is_prime_number = True for p in prime_numbers : if 0 == ( i % p ) : is_prime_number = False break if is_prime_number : prime_numbers.append( i ) generate_prime_numbers( 100 ) print( prime_numbers )

대충 살펴 보니 맞는 것 같군요.

그런데 여기에서 우리가 목표로 하는 600,851,475,143 을 넣고 generate_prime_factors() 를 호출하면 상상도 못할 시간이 걸리게 됩니다. 아무리 기다려도 끝날 생각을 하지 않습니다.

왜냐하면 이것의 시간복잡도는 O( i * p ) 이기 때문입니다; 여기에서 i 는 max 이고 p 는 i 보다 작은 소수의 개수입니다. 그러므로 최악의 경우라도 O( i^2 ) 보다는 작습니다만 max 가 워낙 크기 때문에 답이 없습니다.

그러므로 이건 적어도 이 문제를 풀기 위해서는 사용할 수 없는 함수입니다. 물론 언젠가는 계산이 끝나기는 하겠죠.

최적화를 위해서 병렬화를 고민해 볼 수도 있겠지만, 그건 너무 나간 것 같구요, 알고리즘적으로 해결할 수 있는 방법을 찾아 봐야 합니다.

Optimization : Only odd numbers

일단 단순하게 생각했을 때 2 의 배수인 숫자들( 즉, 짝수 )를 배제하면 대상이 절반이 줄어듭니다.

3 에서 시작한 것이니 for 문의 증가값을 2 로 하면 홀수만 나오게 되죠.

for i in range( 3, max + 1, 2 ) :

Optimization : Reduction

하지만 여전히 검사해야 할 숫자의 개수가 많습니다. 그런데 더 생각나는 방법은 없더군요. 그래서 참고자료를 찾아 봤습니다. [ 1 ] 에서는 다음과 같이 언급하고 있더군요.

그렇군요. 대상을 아예 없애 버리면 됩니다. 하지만 두 가지 문제가 있습니다.

• 메모리 문제 : 메모리가 버텨 줄 것인가?
• list operation : append, remove 등의 연산의 비용은 어떻게 할 것인가?

일단 메모리 문제를 검증해 봤습니다. 2 의 배수만을 배제한다고 가정했을 때, 배열의 크기는 1 GB 정도입니다. 5 의 배수까지 배제한다면 더 줄어들 수 있겠죠. 이 정도는 크게 문제가 없을 것이라는 판단을 했습니다.

두 번째로 list 관리 문제인데요, 소수가 아닌 것들에는 -1 값을 넣어 두면 되기 때문에 별 문제는 없을 것으로 보입니다. 게다가 저는 대상을 배제하는 기법을 사용하는 것이 아니라 소수인지 여부를 검사하는 기법을 사용하고자 합니다. 왜냐하면 대상을 배제하는 기법은 자신보다 큰 값들에 대해서 루프를 검사하는 비용이 들기 때문입니다. 결국에는 소수의 루프를 돌면서 검사하는 것과 크게 다르지 않은 비용이 나올 것이라고 생각합니다. 둘다 이중 루프로 시간복잡도는 거의 동일하기 때문입니다.

def generate_prime_numbers( max ) : prime_numbers = [ 2 ] # gather target numbers except multiples of 2 or 5 targets = list() for i in range( 3, max + 1, 2 ) : if 1 == ( i % 5 ) : targets.append( i ) # check if each item is not a prime number for i in targets : is_prime_number = True for p in prime_numbers : if 0 == ( i % p ) : is_prime_number = False break if is_prime_number : prime_numbers.append( int( i ) ) # return result. return prime_numbers

꽤 많이 배제한 상태임에도 불구하고, i7-4770K 에서 2 분이 지나도록 끝이 안 나더군요. 이것이 list 의 append() 에 드는 비용이 아닌가라는 의심이 들기 시작했습니다. 찾아 보니까, [ 간단한 구문 변경으로 속도를 향상시키기 ] 에서 백만개를 돌리는데 109 ms 를 소비하더군요. 물론 2015 년 자료니 머신의 성능이 어떤지는 모르겠지만, 시간이 많이 걸리는 건 사실입니다. 우리의 목표는 6000 억개이기 때문에 홀수만 따져도 3000 억개입니다. 단순하게 산술계산을 하면 60 만배이고 1000 ms 가 1 초이므로, 6 만초( 16.6 시간 )가 걸립니다. 그러므로 절대 append() 를 많이 사용해서는 안 되는 상황인 것입니다.

링크의 문서에 나온 것처럼 루프 밖에서 append 함수를 미리 선언하는 방식을 사용해 봤습니다( 마치 함수 포인터같은 녀석입니다 ).

target_append = targets.append for i in range( 3, max + 1, 2 ) : if 1 == ( i % 5 ) : target_append( i )

비용이 30 % 정도 줄어든다고 하니 기대시간은 약 11.62 시간입니다. 이것도 용납할 수 없는 수치입니다.

이걸 빠르게 할 수 있는 방법이 있으면 누군가 공유해 줬으면 좋겠군요.

추가 : [ 7. 10001st Euler ] 를 풀면서, 2 의 배수, 5 의 배수를 배제하고 소수를 뽑아 봤는데, 예상한 것과는 다르게 1 ~ 2 분 정도밖에 안 걸리더군요. 그러므로 위에서 예측한 비용은 잘못된 것으로 보입니다.

Prime Factorization

뭐 굳이 소수의 리스트가 없어도 문제를 해결할 방법은 있습니다.

원래 값을 2 부터 시작해서 나눕니다. 그리고 나머지가 0 이 아니면 다음 숫자로 넘어 갑니다. 나머지를 0 으로 만드는 수는 소인수라 생각할 수 있습니다.

def get_prime_factors( target ) : quotient = target prime_factors = list() append_factors = prime_factors.append i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i append_factors( i ) else : i += 1 return prime_factors prime_factors = get_prime_factors( 600851475143 ) print( prime_factors ) print( prime_factors[ len( prime_factors ) -1 ] )

답은 6857 입니다.

다른 사람들은 어떻게 풀었는지 확인해 봤는데 별 차이는 없네요. 단지 MathBlog 에서는 0 ms 에 가까운 대안을 소개하고 있습니다( 앞에서 소개했던 짝수배제 기법입니다 ). 

근데 컴퓨터가 좋아서인지 최적화를 안 해도 저는 0.0107 ms 가 나오는군요. 어쨌든 빠르면 좋은거니 저도 홀수를 배제해 봤습니다. 

i += 1 if 0 == ( i % 2 ) else 2

그랬더니 0.0058 ms 로 반쯤 줄어드는군요. 여기에서 5 의 배수도 배제해 봤습니다.

next = i + 1 i += 2 if ( 0 == ( next % 2 ) ) or ( 0 == ( next % 5 ) ) else 1

그런데 조건문이 두 개가 되지 비용만 더 올라갑니다( 0.0068 ms ). 너무 작은 비용에 대한 부적절한 최적화는 오히려 해가 된다는 사실을 알게 되네요.

전체 소인수 리스트를 수집하기 위해서 append() 를 사용하고 있습니다. 이를 배제하고 마지막 소인수만 반환한다면 더 빠른 결과를 볼 수 있습니다( 0.0048 ms ). 하지만 기본 while 비용이 있으므로 여기에서 드라마틱하게 내려가지는 않네요.

def get_last_prime_factor( target ) : quotient = target last_prime_factor = -1 i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i last_prime_factor = i else : i += 1 if 0 == ( i % 2 ) else 2 return last_prime_factor

참고자료

[ 1 ] 소수 ( 수론 ), 위키피디아.

[ 2 ] 소인수분해, 위키피디아.

원문 : Even Fibonacci numbers

문제 의도 해석

피보나치 수열에서 어떤 항은 앞의 두 수를 더해서 나온 것입니다.

• 3 = 1 + 2
• 5 = 2 + 3
• 8 = 5 + 3
• ...

문제에서는 짝수값만 더하라는 것이죠. 위의 예에서는 2 + 8 + 34 = 44 가 됩니다.

print_fibonacci function

일단 피보나치 수열의 값을 출력하는 함수를 만들어 보았습니다. 재귀적으로 호출하는 형식입니다. 단 100 을 넘지 않는 값을 출력하도록 했죠.

def print_fibonacci( a, b, max_term ) : if b > max_term : print( a ) return print( a ) print_fibonacci( b, a + b, max_term )

이를 실행하면 다음과 같은 결과가 나오죠.

물론 재귀 함수가 아니라 for 문을 통해서 구현하는 것도 가능합니다.

def print_fibonacci_with_while( a, b, max_term ) : a_val = a b_val = b while( b_val <= max_term ) : print( a_val ) temp = a_val a_val = b_val b_val = temp + b_val print( a_val )

sum_fibonacci function

이제 이 결과를 합쳐 보겠습니다. 결과를 더하는 건 결국 출력하는 순서와 동일하게 더해 가는 겁니다. 그런데 문제는 함수 내에서 a + b 가 발생하면, 다음 재귀 함수에서 b + next_term 를 하기 때문에( a' 로서 b, b' 로서 next_term, 그러므로 b 누적 ) 요소가 한 번씩 누적될 수 있다는 겁니다. 이에 주의해야 합니다.

def sum_fibonacci( a, b, max_term ) : if b > max_term : return a return a + sum_fibonacci( b, a + b, max_term )

sum_even_fibnoacci function

이제 문제의 의도대로 짝수값만 더하는 함수를 만듭니다. 임시 변수를 만들어서 홀수인 경우에는 0 취급을 해 주면 기존의 함수의 형태에서 크게 달라지지 않습니다.

def sum_even_fibonacci( a, b, max_term ) : a_val = 0 if ( a % 2 ) else a # a_val = ( a % 2 ) ? 0 : a if b > max_term : return a_val return a_val + sum_even_fibonacci( b, a + b, max_term )

파이썬 삼항 연산자가 좀 맘에 안 들기는 하지만, 어쨌든 비슷한 형태가 나옵니다.

4,000,000 까지의 피보나치 수열의 짝수항들을 더한 결과는 4613732 입니다.

More Efficient Method?

근데 재귀함수의 복잡도는 O( n ) 보다는 무조건 크게 나오는 것으로 보입니다; O( logn ), O( n^2 ), O( n^3 ). 그러므로 가급적이면 O( n ) 이 나오는 whlie 문을 사용하는 것이 좋을 것같습니다.

그런데 O( 1 ) 상수복잡도를 가지는 식은 없을까요? 왠지 불가능할 것 같습니다. 혹시 알고 계시다면 제보를 부탁드립니다.

우리는 짝수가 "홀수와 홀수" 혹은 "짝수와 짝수"를 더했을 때 나온다는 것을 알고 있습니다. 그래서 이를 이용해서 뭔가 간단한 규칙을 만들어 보려고 했습니다만, 어떻게 해야 할지 모르겠더군요. 그런데 이미 이걸 하신 분이 있더군요( F3 부터 세 번째 항들( F6, F9, ... )이 짝수라는 겁니다 ). 

"홀수 + 홀수 = 짝수" 이고 짝수 앞뒤에는 항상 홀수가 오니까 세 번째마다 반복되는 것으로 보입니다. 물론 이분은 "1, 1" 에서 시작하는 피보나치 수열을 가지고 계산한 것입니다.

이 분의 최종 코드는 다음과 같습니다( C# 으로 구현한 겁니다. 정확한 방식에 대해 알고자 하신다면 MathBlog 의 [ Project Euler - Problem 2 ] 를 참조하시기 바랍니다 ).

long[] fib = {2,0}; int i = 0; long summed = 0; while (fib[i] < 4000000) { summed += fib[i]; i = (i + 1) % 2; fib[i] = 4 * fib[(i + 1) % 2] + fib[i]; }

Where is Fibonacci Sequences?

피보나치 수열은 황금비를 형성한다고 합니다. [ 왜 자연은 피보나치 수열과 황금비를 택했을까 ] 를 읽어 보시면 재밌습니다. 엄청나게 세부적인 설명을 보려면 [ Fibonacci Numbers and Nature ] 라는 글을 참고하시면 좋습니다.

원문 :  Multiples of 3 and 5.

가장 쉽게 생각해 볼 수 있는 것은 루프를 돌면서 3 이나 5 의 배수이면 더하는 겁니다. 사실 이거 말고는 별 생각이 안 나더군요.

sum = 0 for i in range( 1000 ): if ( 0 == i % 3 ) | ( 0 == i % 5 ) : sum += i print( sum )

결과는 233168 입니다. 이것을 빅오 표기법으로 하면 O( N ) 이겠죠( 빅오 표기법에 대해서 더 자세히 알고자 하신다면, [ 강의노트 25. 자료구조, 알고리즘 - 성능측정 (Big-O ) ] 를 참조하시면 좋을 것 같네요 ).

다른 방식으로 푸는 사람이 있는지 확인해 봤습니다.

제가 푼 방법은 "brute-force" 방식이더군요. "geometric/arithmetic approach" 로 스마트하게 푸는 사람들이 있었습니다.

[ Project Euler - Problem 1 ] 에 의하면, 3 의 배수를 더한 것과 5 의 배수를 더한 것을 합하는 방식으로 문제 해결을 하더군요. 단순하게 생각해 봐도 전체 값에 대한 루프를 도는 것 보다는 훨씬 효율적인 것을 알 수 있었습니다.

거기에 더 나아가서 수학적인 기법을 이용해서 문제를 풀고 있었습니다. 아래는 우리가 많이 봤던 정수 덧셈에 대한 식이죠( 여러 가지 방법으로 생각해 볼 수 있는데, 궁금하다면 [ 정수의 합 공식 ] 을 참조하세요 ).

이걸 좀 변형해서 K 의 배수를 더한다고 해 보죠.

그럼 3 의 배수의 합과 5 의 배수의 합은 다음과 같습니다.

하지만 여기에서 끝이 아닙니다. 3 의 배수와 5 의 배수에는 두개의 최소 공배수인 15 의 배수가 겹쳐서 들어 가고 있습니다. 그러므로 15 의 배수를 빼 쭤야 정상적인 결과가 나옵니다.

def sum_of_multiples( base_value, max_value ) : num_values = int( max_value / base_value ) return int( base_value * num_values * ( num_values + 1 ) / 2 ) solution = sum_of_multiples( 3, 999 ) + sum_of_multiples( 5, 999 ) - sum_of_multiples( 15, 999 ) print( solution )

어떤 숫자든간에 sum_of_multiples 는 상수시간에 문제를 해결합니다. 한 마디로 어떤 값을 넣어도 일정한 시간이 걸린다는거죠. 빅오 표기법으로 하면 O( 1 ) 입니다.

역시 알아야 면장이라도 한다고.... 어떻게 하느냐에 따라서 성능에 큰 영향을 줄 수 있군요. 공부를 더 열심히 해야겠습니다.

p.s. 형변환 없이 다음과 같이 코드를 쓸 수도 있습니다.

def sum_of_multiples( base_value, max_value ) : num_values = max_value // base_value return base_value * num_values * ( num_values + 1 ) // 2 solution = sum_of_multiples( 3, 999 ) + sum_of_multiples( 5, 999 ) - sum_of_multiples( 15, 999 ) print( solution )

파이썬에서 "//" 연산자는 소수점을 버리는 나누기 연산자더군요.

Motivation

개인적으로 진행하는 프로젝트에서 double 수학이 필요한 상황이 되었습니다. 그래서 UE4 가 가지고 있는 수학 라이브러리를 미믹( mimic )해서 double 수학 라이브러리를 플러그인에서 구현하고 있었죠.

그런데 이 작업을 하다가 보니 matrix-matrix 곱에서 막히게 되었습니다. UE4 는 SSE 를 사용한다는 가정하에서 matrix-matrix, matrix-vector 곱을 SSE 로 구현해 놨습니다. 문제는 double 은 single( single-precision floating point )와는 SSE 구현 방식이 다르다는 거죠.

간단하게 예를 들면 Intel CPU 는 16 개의 mmx 레지스터를 제공하는데, 이것을 __m128 로 접근하죠. 128 비트를 가지고 있으니 이걸 32 로 나누면 4 가 됩니다. 즉 4 개의 single 을 하나의 레지스터에 저장할 수 있다는 것이죠. 하지만 double 을 사용하기 위해서는 __m128d 를 사용해야 하며, 그것의 크기는 256 비트입니다. 즉 2 개의 mmx 레지스터를 사용해 single 을 위해 했던 작업을 에뮬레이션해야 한다는 이야기입니다.

이런 작업이 좋은 경험이 될 것 같기는 하지만 귀찮아서 그냥 non-SSE 코드를 구현하기로 했습니다. 하지만 시작부터 벽에 부딪히게 되었습니다. 일단 UE4 는 matrix 에 다음과 같은 주석을 달았습니다.

/** * 4x4 matrix of floating point values. * Matrix-matrix multiplication happens with a pre-multiple of the transpose -- * in other words, Res = Mat1.operator*(Mat2) means Res = Mat2^T * Mat1, as * opposed to Res = Mat1 * Mat2. * Matrix elements are accessed with M[RowIndex][ColumnIndex]. */ struct FMatrix

여기에서 몇 가지 고민해 볼 지점이 발생합니다.

• pre-multiplication 이란 무엇인가?
• 이 행렬의 major 는 무엇인가?
• 계산 후에 행렬의 major 는 유지되는가?

이 때문에 어떤 식으로 계산해야 하는지 혼란이 왔고, 제가 생각하는 것보다 행렬 구현이 쉽지 않다는 것을 깨닫게 되었습니다. 역시 단순히 사용하는 것과 그것을 이해하고 구현하는 것은 다른 법이더군요.

이 문서에서는 그런 구현을 하는 데 있어서 필요한 배경 지식들을 정리하고자 합니다.

Basic rules & major

일단 기본을 점검해 보기로 했습니다. 수학에서 M X N 행렬과 N X K 행렬을 곱하면 M X K 행렬이 나옵니다. 그리고 앞의 행렬의 "행"과 뒤의 행렬의 "열"의 내적이 새로운 행렬의 행과 열이 되죠. [ 4 ] 에서는 다음과 같이 도식화해서 설명하고 있습니다.

그림1. Matrix multiplication rule. 출처 : [ 4 ]

그림 2 : Dot product rule. 출처 : [ 4 ].

수학적으로 볼 때 이런 규칙들은 반드시 지켜져야 합니다. 물론 프로그래밍 언어에서 구현할 때는 여러 가지 이유때문에 우리가 수학에서 보는 것과는 다른 순서로 데이터가 저장되어 있을 수 있습니다. 여기에서 major 라는 것이 중요해지죠.

[ 1 ] 에 의하면 row-major 와 column-major 를 구분하는 것은 메모리 상에서의 연속성이 행렬의 어느 방향을 향하고 있느냐를 의미한다고 합니다.

그림3. row-major 와 column-major 의 순서. 출처 : [ 1 ]

그림3 에서 볼 수 있듯이 실제 메모리에 행을 저장하느냐 열을 저장하느냐 에 따라 row-major 와 column-major 가 결정됩니다. [ 1 ] 에 의하면 row-major 를 택한 언어들은 C, C++, Objecttive-C, PLI, Pascal, Speakeasy, SAS, Rasdaman 등이고, column-major 를 택한 언어들은 Fortran, MATLAB, GNU Octave, S-Plus, R, Julia, Scilab 등이라고 합니다. OpenGL 과 OpenGL ES 의 경우에는 row 에다가 vector 를 저장함에도 불구하고 그것을 column 으로 취급합니다. 그리고 이도 저도 아닌 Java, C#, CLI, .NET, Scala, Swift, Python, Lua 같은 언어들도 있다고 하네요.

어쨌든 column-major 냐 row-major 냐는 것은 해석과 구현의 문제입니다. [ 3 ] 에서는 view matrix 를 다음과 같이 표현합니다.

그림4. View Matrix. 출처 : [ 3 ].

그리고 나서 열을 하나의 vector 로 보고 matrix 배열의 한 행에 넣습니다.

float right[4] = { 1, 0, 0, 0 }; float up[4] = { 0, 1, 0, 0 }; float forward[4] = { 0, 0, 1, 0 }; float position[4] = { 0, 0, 0, 1 }; float matrix[4][4] = { { right[0], right[1], right[2], right[3] }, // First column { up[0], up[1], up[2], up[3] }, // Second column { forward[0], forward[1], forward[2], forward[3] }, // Third column {position[0], position[1], position[2], position[3] } // Forth column };

한 행에 벡터들이 들어 가고 있으므로, 즉 column 들이 연속적인 메모리 공간에서 이어지고 있으므로 이는 column-major 라고 할 수 있습니다. 메모리에서의 저장순서는 아래와 같습니다.

Pre/Post-Multiplication

이 챕터는 [ 2 ] 의 [ The Matrix Chapter ] 의 번역입니다.

행렬곱은 두 행렬들에 대한 곱셈입니다. 행렬곱에는 결합법칙( associative law )이 적용되지만 교환법칙( communitative law )은 적용되지 않습니다.

결합법칙이 허용되면 다음과 같이 됩니다:

하지만 교환법칙이 허용되지 않으면 다음과 같이 됩니다:

행렬곱은 pre-multiplication 이나 post-multiplication 을 사용하여 계산될 수 있습니다. 이것은 벡터가 matrix 의 왼쪽( 혹은 "앞" )에 있어야 하는지 아니면 오른쪽( 혹은 "뒤")에 있어야 하는지를 가리킵니다.

행렬곱에는 교환법칙이 적용되지 않기 때문에 행렬 곱을 계산할 때 벡터가 행렬의 어느쪽에 있느냐에 따라 완전히 다른 결과가 발생됩니다. 그래픽 API 가 pre 혹은 post multiplication 을 사용하기로 선택하면, 동일한 결과 벡터를 얻으려면 전치된( transoposed ) 행렬을 사용해야합니다.

수학 문서에서는 post-multiplicaiton 이 일반적입니다. 이것은 행렬곱이 다음과 같이 계산된다는 것을 의미합니다. 주어진 행 R 과 열 C 에서 결과의 각 구성 요소는 왼쪽 행 행 R 과 오른쪽 열 C 의 내적으로 계산됩니다. 예를 들어 :

일 때, post-multiplication 을 사용하면, C 행렬의 1 행 2 열의 컴포넌트 b 의 결과를 계산하기 위해, A 의 1 행과 B 의 2 열을 내적합니다( 이것을 row-major 표기법이라 합니다 ). 모든 결과는 다음과 같습니다.

그러므로 그 결과는 다음과 같습니다:

이어지는 글에서는 별도의 표기가 없다면 row-major 표기법을 사용합니다.

하지만 이것은 정방 행렬을 곱하지 않을 때는 조금 더 까다로워 집니다. 3x3 행렬에 3x1 행렬( 3 행 1 열 벡터 )을 곱하면 3x1 행렬이 됩니다. 4x2 행렬에 2x3 행렬을 곱하면 4x3 행렬이 됩니다. 첫 번째 행렬의 행과 두 번째 행렬의 열에 대한 내적을 취하기 때문에, 첫 번째 행렬에는 두 번째 행렬의 행 수와 동일한 개수의 열이 있어야 합니다. 첫 번째 행렬의 각 행과 두 번째 행렬의 각 열에 대해 이 작업을 수행하므로, 결과 행렬의 행 개수는 첫 번째 행렬의 행의 개수와 같고 열 개수는 두 번째 행렬의 열 개수와 같습니다.

일반적으로, 서로 옆에 쓰여진 두 행렬의 차원을 취합니다. 내부의 두 값은 같아야하고 결과 행렬은 외부 값의 크기를가집니다. 4x3 * 3x2 = 4x2. 2x4 * 4x1 = 2x1. 4x3 및 2x4 행렬을 곱할 수는 없습니다. 왜냐하면 3 은 2 와 같지 않기 때문입니다.

자, 이제 pre-multiplication 에 대해서 이야기해 보도록 하겠습니다.

Pre-multiplication 을 사용하면 이제 행 벡터를 사용해야합니다. 열 벡터는 4x1 행렬이지만, 4x1 행렬에 4x4 행렬을 곱할 수는 없습니다. 대신 1x4 행 벡터를 사용해 1x4 행렬에 4x4 행렬 곱하기( 내부/가장 가까운 두 값의 일치 )의 결과로 1x4 행렬을 만들 수 있습니다( 바깥 쪽 두 값은 1 과 4 입니다 ).

그러나 pre-multiplication 을 사용하면 연산이 달라집니다. post-multiplicatin 의 4x4 행렬에 4x1 행 벡터를 곱한 결과 행렬의 각 행에 벡터가 포함됩니다. 이제 pre-multiplication 을 통한 내적은 ( 행렬이 곱셈 연산자의 오른쪽에 있기 때문에 ) 벡터와 행렬의 각 열을 사용해 연산을 합니다.

고맙게도, 이것은 쉽게 수정할 수 있습니다. Pre-multiplication 을 위해 행렬을 계산할 때, 단순히 post-multiplicatin 을 위해 사용했던 행렬을 전치하기만 하면 됩니다. 이것은 벡터를 4x1 열 벡터에서 1x4 행 벡터로 변환하기 때문에 의미가 있습니다.

2x2 행렬과 2x1 벡터에 대한 post-multiplication 은 다음과 같습니다:

1x2 벡터와 전치된 2x2 에 대한 pre-multiplication 은 다음과 같습니다:

결과는 동일하지만 전치된 벡터입니다:

OpenGL에서 일반적으로 사용하는 것처럼, column-major 표기법으로 post-multiplication 을 사용하면 어떻게 될까요. 수학적 결과는 같지만 행렬 크기의 순서는 바뀝니다. 따라서 column-major 4x3 행렬에 3x2 행렬을 곱할 수는 없지만, 2x4 및 1x2의 곱을 취하면 4x1 행렬(4 행 행 벡터)이 됩니다. 결과와 작동 방식은 모두 동일합니다. 표기법 만 다를 뿐입니다.

The Tricky Part

중요한 것은 pre-multiplication 이 사용되었는지 post-multiplication 이 사용되었는지의 여부입니다. D3DX 수학 라이브러리는 pre-multiplication 을 사용하고 OpenGL의 표준 행렬 스택은 post-multiplication 을 사용합니다. 그것은 일반적으로 행렬이 전치되어야 한다는 것을 의미합니다.

그러나 D3DX 는 row-major 행렬을 사용하고 OpenGL은 column-major 행렬을 사용한다는 점을 기억하십시오. 따라서 그들은 이미 전치되어 있습니다. 다음의 간단한 3x3 변환 행렬을 살펴 보죠. 2 의 uniform scale 과 (10, -5) 의 translation 을 표현합니다.

다음의 3x3 행렬은 row-vector 와 pre-multiplication 을 위해 사용되도록 의도되었습니다:

이것의 row-major 메모리 레이아웃은 다음과 같습니다:

다음의 3x3 행렬은 column-vector 와 post-multiplication 을 위해 사용되도록 의도되었습니다:

이것의 column-major 메모리 레이아웃은 다음과 같습니다 :

행렬은 특정 개념으로 작성되면 전치됩니다. 하지만 메모리에 저장되면 똑같습니다.

그것은 까다로우면서 멋진 부분입니다. 여러분의 코드들은 서로 다른 표기법과 서로 다른 행렬곱 순서 때문에 다르게 느껴질 겁니다. 하지만 실제 행렬값은 서로 교환가능합니다.

결과적으로 Direct3D 및 OpenGL 스타일을 모두 처리하는 단일 행렬 클래스를 쉽게 작성할 수 있습니다. Column-major 와 post-multiplication 을 사용하거나, row-major 와 pre-multiplication 을 사용하면, 그 데이터는 완전히 호환됩니다.

이것을 다시 강조하기 위해서 : 손으로 하는 일은 이것과 아무 상관이 없습니다! 왼손 좌표계 행렬이나 오른손 좌표계 행렬이라는 것은 존재하지 않습니다. 좌표계는 완전히 별도의 이슈입니다.

References

[ 1 ] Row- and column-major order, Wikipedia.

[ 2 ] Matrices, Handedness, Pre and Post Multiplication, Row vs Column Major, and Notations, Game Development by Sean.

[ 3 ] Understanding the View Matrix, 3D Game Engine Programming.

[ 4 ] Linear Algebra, Artifical Inteligence.

주의 : 허락받고 번역한 것이 아니므로 언제든 내려갈 수 있습니다.

주의 : 번역이 개판이므로 이상하면 원문을 참조하세요.

원문 : The Perils of Floating Point.

제가 "The Perils of Floating Point" 를 작성할 때, 이게 어느 정도까지 일이 커질지 알지 못했습니다. 그 문서에 수 백개의 링크가 걸렸고, 수 천번 참조되었습니다. 대학이나 프로그래밍 문서, 그리고 출간된 책들이나 많은 블로그들에서 참조되었죠. 얼마나 많은 사람들이 이 도움을 받게 되었는지 알고 싶네요.

The Perils of Floating Point by Bruce M. Bush © 1996 Lahey Computer Systems, Inc.

원문에 대한 표기와 함께 복제가 허용됩니다.

The Perils of Floating Point by Bruce M.Bush

최근 수십년 동안에 있었던 수 많은 훌륭한 엔지니어링과 과학적 모험들은 디지털 컴퓨터의 floating-point( 부동소수점 ) 기능없이는 불가능했을 것입니다. 하지만 여전히 일부 부동소수점 계산의 결과는 좀 이상하고, 심지어는 수학적 경험을 몇 년 동안 해 온 사람들에게조차도 이상합니다. 저는 이러한 이상한 결과들이 발생하는 원인에 대해서 설명하고 적용가능한 제안들을 제공할 계획입니다.

부동소수점 표현과 연산( arithmetic )은 부정확합니다. 하지만 그게 대부분의 프로그래머들에게 특별히 문제가 된다고는 생각하지 않습니다. 많은 입력값들이 내재적으로 부정확한 양( measurement )입니다. 그래서 출력 값에 대한 질문은 에러가 존재하느냐가 아니라 얼마나 많은 에러가 예상되느냐입니다. 그래서 여러분이 부동소수점을 가지고 컴퓨터보다 더 정확한 결과를 암산할 수 있다면, 의혹을 가지기 시작할 것입니다.

저는 몇 가지 이유로 FORTRAN 을 사용해 예제를 프로그래밍 했습니다 :

1. 포트란에서는 다른 컴퓨터 언어보다 더 많은 부동소수점 계산이 수행됩니다.
2. Lahey Computer System 이라는 회사에서 일하고 있는데, FORTRAN 언어 시스템을 개발하고 판매하고 있습니다.

이상한 결과들이 나오는 원인의 핵심은 하나에 기반합니다 : 컴퓨터에서 부동소수점이 보통 2 진수라는 것입니다. 반면에 외부적인 표현은 10 진수입니다. 우리는 1/3 이 정확하게 표현되지 않을 것이라 생각하지만, 그것은 직관적입니다. .01 이 되죠. Not so! IEEE 단일정밀도 형식( single-precision format )에서 .01 은 정확히 10737418/1073741824 이거나 대략 0.009999999776482582 입니다. 여러분은 다음과 같은 코드를 확인하기 전까지는 그 차이를 인지하지도 못할 것입니다:

10 진수 부동소수점 구현은 이런 변칙을 포함하지 않습니다. 하지만 10 진수 부동소수점 구현은 거의 보기가 힘듭니다. 왜냐하면 2 진수( binary ) 연산이 디지털 컴퓨터에서는 훨씬 빠르기 때문입니다.

Inexactness

디지털 컴퓨터에서 부동소수점 연산은 내재적으로 부정확합니다. 32 비트 부동소수점 수의 ( 숨겨진 비트를 포함한 ) 24 비트의 가수( mantissa )는 약 7 개의 유효 십진수( significant decimal digit ) 를 표현합니다. 예를 들어 대략 8,388,607 개의 단일정밀도 숫자가 1.0 과 2.0 사이에 존재합니다. 반면에 1024.0 과 2024.0 사이에는 단지 8191 개만이 존재합니다.

모든 컴퓨터에서, 수학적으로 동등한 표현식이 부동소수점 연산을 사용하면 서로 다른 결과를 산출할 수 있습니다. 다음 예제에서, Z 와 Z1 은 보통 서로 다른 값을 가지게 되는데, (1/Y) 혹은 1/7 이 이진 부동소수점에서 정확하게 표현되지 않기 때문입니다.

Insignificant Digits

다음 코드 예제는 유효 숫자로 보일 수 있는 무의미한 숫자들이 나오는 현상을 설명합니다.

단일 정밀도 (REAL) 요소는 대략 최대 7 개의 십진수 정밀도를 표현할 수 있습니다. 그래서 위의 빼기는 (1000.200 - 1000.000) 을 표현합니다. 그러므로 그 결과는 약 3 개의 십진수만을 표현할 수 있습니다. 하지만 프로그램은 "0.200012" 를 출력할 것입니다. 1000.2 는 이진 부동소수점에서 정확하게 표현되지 않고 1000.0 도 그렇기 때문에, 결과 A 는 0.2 보다 약간 큽니다. 하지만 컴퓨터는 ".200" 뒤쪽에 있는 숫자가 무의미하다는 것을 알지 못합니다.

아마도 언젠가는 컴퓨터가 결과에 있는 여러 개의 비트들에 대한 추척을 하겠죠. 하지만 지금은 여전히 그것은 프로그래머의 책임하에 있습니다. 만약 여러분이 데이터형에 의해 표현되는 십진수의 개수에 주의한다면, 유효 숫자의 개수를 근사계산하는 것은 직관적입니다. 하지만 아마도 시간이 걸리는 작업이 되겠죠. 가장 주의해야 할 점에 대해서 이야기해 보도록 하겠습니다:

1. 뺄셈은 값이 거의 같습니다.
2. 덧셈은 가수값이 거의 같습니다. 하지만 부호( sign )가 반대인 숫자에서는
3. 덧셈이나 뺄셈은 매우 다른 가수값을 반환합니다.

Crazy Conversions

정수로의 변환은 부동소수점 수에서의 부정확함을 드러낼 수 있습니다. 다음 예제에서 설명할 것입니다. 21.33 에 가장 가까운 단일정밀도 부동소수점 수는 21.33 보다는 약간 작습니다. 그래서 100. 을 곱하게 되면, 그 결과 Y 는 2133.0 보다 약간 작습니다. 만약 여러분이 Y 를 일반적인 부동소수점 형식으로 출력한다면, 반올림( rounding )이 발생해서 2133.00 으로 출력될 것입니다. 하지만, Y 를 정수에 할당하게 되면, 반올림이 발생하지 않습니다. 그래서 그 숫자는 2132 가 됩니다.

다음 프로그램은 Lahey 의 LF90 으로 컴파일하면 "1.66661000251770" 을 출력합니다.

여러분은 "왜 단일정밀도 수에 무작위인 것으로 보이는 '000251770' 이 붙은 걸까" 라는 의문이 들 것입니다. 글쎄요, 그 숫자는 무작위 숫자가 아닙니다; 컴퓨터의 부동소수점은 이진 표현에서 0 을 사용해 패딩( padding )함으로써 변환을 수행합니다. 그래서 D 는 X 와 정확히 같죠. 하지만 15 개의 십진수로 출력한다면, 부정확함이 드러나는 것입니다. 이것은 비유효( insignificant ) 숫자의 다른 예이기도 합니다. 단일정밀도 숫자를 배정밀도( double-precision ) 숫자로 변환하는 것은 유효 숫자의 개수를 증가시키지 않는다는 것을 기억하십시오.

Too Many Digits

여러분은 이전의 프로그램 예제를 사용해 D 와 X 를 같은 형식으로 출력함으로써 값을 확인해 보려고 할 것입니다:

일부 FORTRAN 구현에서는 두 숫자가 동일한 값을 출력합니다. 여러분은 만족하고 떠나겠죠. 하지만 실제로는 단일 정밀도 수의 낮은자리 숫자( low-order digits )가 출력되지 않는 것을 잘못 판단한 것입니다. Lahey FORTRAN 에서는 그 숫자들이 다음과 같이 출력됩니다.

1.66661000000000       1.66661000251770

이렇게 되는 이유는 매우 단순합니다: Formatted I/O 변환 루틴들은 절대적인 최대 십진수를 알고 있으며, 단일정밀도 요소를 출력할 때 모든 유효숫자는 9 가 됩니다. 나머지 부분들은 현재 "precision-fill" 문자로 채워집니다. 그것의 기본값은 "0" 입니다. Precision-fill 문자는 다른 ASCII 문자로 대체될 수 있는데요, '*'( asterik ) 나 ' '(blank )같은 것들을 예로 들 수 있습니다. Precision-fill 문자를 "*" 로 변경하는 것은 낮은자리 숫자의 비유효성을 강조합니다.

1.66661000******       1.66661000251770

Too Much Precision

IEEE 단일정밀도 형식은 23 비트의 가수, 8 비트의 지수, 1 비트의 부호로 구성되어 있습니다. 펜티엄( Pentium )과 같은 인텔( Intel ) 마이크로 프로세서에서는 내부 부동소수점 레지스터가 64 비트의 가수, 15 비트의 지수, 1 비트의 부호로 구성됩니다. 이는 다른 구현들보다 해상도 손실이 훨씬 더 적은 중간 계산( intermediate calculation )을 가능하게 합니다. 이것의 단점은 중간 값들이 레지스터에 유지되는 방식에 따라서 똑같아 보이는 계산의 결과가 달라질 수 있다는 것입니다.

다음 예제에서, 컴파일러는 A/B 를 계산해서 중간 결과를 단일 정밀도 임시 변수에 저장하고, X/Y 를 계산해서 임시 변수에서 빼고, 결과를 Z 에 저장하는 코드를 생성합니다. Z 는 0 이 아닐 것입니다. 왜냐하면 단일정밀도 임시변수에 저장하면서 해상도가 손실될 것이기 때문입니다. 만약 생성된 코드가 중간 값을 레지스터에 유지한다면, 해상도는 손실되지 않을 것이고, Z 는 0 이 될 것입니다.

다음 예제는 이전 예제의 변형들에 대해서 설명합니다. 컴파일러는 여전히 중간 결과 C 를 레지스터에 유지하는 코드를 생성할 수 있습니다. 이건 Z 값이 0 임을 의미합니다. 만약 A/B 를 C 에 넣음으로써 해상도가 손실된다면, Z 는 0 이 아닐 것입니다.

C 가 레지스터에서 유지되는 것을 막기 위해서 레이블( label ) 100 을 추가했습니다. 그래서 Z 는 아마도 거의 대부분의 컴파일러에서 0 이 아닐 것입니다.

Safe Comparison

다양한 컴퓨터들은 다양한 비트를 사용해 부동소수점 숫자를 저장합니다. 심지어는 같은 IEEE 형식을 사용해 숫자를 저장하고 있더라도, 계산하는 동안에는 다른 일이 벌어질 수 있습니다. 왜냐하면 중간 레지스터의 크기가 다르기 때문입니다. 이식을 증대하고 일정한( consistent ) 결과를 보장하기 위해서, 저는 FORTRAN 에서 실수의 정확한 동일성( equality )을 비교하는 것은 좋지 않다고 생각합니다. 더 좋은 기법은 두 숫자의 차이의 절대값을 비교하는 것인데, 이 때 적절한 엡실론( epsilon )값을 사용해서 거의 같은 관계, 명확하게 더 큰 관계 등을 얻는 것입니다. 예를 들어 :

비교 대상 중 하나를 사용하여 엡실론에 곱셈을하면 그 숫자의 범위가 조정됩니다. 그래서 하나의 엡실론을 여러 가지 비교를 위해 사용할 수 있습니다. 가장 예측 가능한 결과를 얻으려면 엡실론의 절반 정도로 큰 값을 사용하고 다음 예제에서와 같이 비교 대상의 합계를 곱합니다:

부동 소수점 계산이 수학적으로 가능하지 않은 값을 생성할 수 있기 때문에, 큼 이나 작거나 같음 등의 비교도 예기치 않은 결과를 생성 할 수 있습니다. 다음 예제에서 X 는 항상 수학적으로 J 보다 큽니다. 그래서 X/J 는 1.0 보다는 항상 커야 합니다. 하지만 큰 숫자의 J 를 사용했을 때 델타( delta )의 합은 X 로 표현되지 않습니다. 왜냐하면 가수 크기를 넘어서기 때문이죠.

Programming with the Perils

쉬운 답은 존재하지 않습니다. 앞에서 설명했던 방식으로 동작하는 것은 이진 부동소수점의 본성입니다. 컴퓨터 부동 소수점의 힘을 이용하려면 그 한계를 알아야하며 그 한계 내에서 작업해야합니다. 부동 소수점 연산을 프로그래밍 할 때 다음 사항을 염두에 두면 많은 도움이됩니다 :

1. 단일 정밀도 IEEE 형식에서는 약 7 자릿수, 배 정밀도 IEEE 형식에서는 약 16 자릿수만 표현할 수 있습니다.
2. 숫자가 외부 십진수에서 내부 이진수로 혹은 그 반대로 바뀔 때마다 정밀도가 손실 될 수 있습니다.
3. 항상 안전한 비교를 사용하십시오.
4. 덧셈과 뺄셈은 결과에서 실제 유효 숫자를 빠르게 침식할 수 있다는 것에 주의하십시오. 컴퓨터는 실제로 어떤 비트가 중요한지 알지 못합니다.
5. 데이터 유형 간의 변환은 까다로울 수 있습니다. 배 정밀도로의 변환이 실제 유효 비트수를 늘리지는 않습니다. 부동소수점 숫자가 더 큰 정수로 출력되는 경우에도 정수로의 변환은 항상 0 으로 잘립니다.
6. 두 가지 다른 부동소수점 구현에서 동일한 결과를 기대하지 마십시오.

제가 여러분에게 부동소수점 연산의 내부에서 어떤 일들이 발생하고 있는지 좀 더 알려줬기를 바랍니다. 그리고 그 이상한 결과들에 대해서 이해할 수 있게 되었기를 바랍니다.

"위험"중 일부는 피할 수 있지만 대부분은 이해하고 받아들일 필요가 있습니다.

IEEE Standard Floating-Point Formats

IEEE (Institute of Electrical and Electronics Engineers, Inc.)는 부동 소수점 표현 및 계산 결과에 대한 표준을 정의했습니다 (IEEE Std 754-1985). 이 절에서는 부동 소수점 수를 나타내는 IEEE 표준에 대한 개요를 제공합니다. 여기에 포함 된 데이터는이 기사의 나머지 부분에서 일부 내용을 설명하는 데 도움이되지만 기본 개념을 이해하는 데 반드시 필요한 것은 아닙니다.

대부분의 이진 부동 소수점 수는 1.ffffff x 2^n 으로 나타낼 수 있습니다. 여기서 1 은 정수 비트이고, f 는 소수 비트이며 n 은 지수입니다. 정수 비트와 소수 비트의 조합을 가수 ( 또는 significand )라고 합니다. 대부분의 숫자는 정수 비트에 1이 있도록 지수를 조정할 수 있기 때문에( 정규화라고 부르는 프로세스 ), 1을 저장할 필요가 없으므로 효율적으로 추가적인 정밀도를 허용하게 됩니다. 이 비트를 숨겨진 비트라고합니다. 숫자는 부호있는 가수로 표현되므로, 음수는 동일한 크기의 양수와 동일한 가수를 갖지만 부호 비트가 1 입니다. 바이어스( bias )라고 하는 상수가 지수에 더해져 모든 지수는 양수가 됩니다.

지수가 0이고 가수가 0 인 값 0.0 은 음수 기호를 가질 수 있습니다. 음수 0 은 대부분의 프로그램에서 분명하지 않은 미묘한 속성을 가지고 있습니다. 0 이 아닌 가수를 가진진 지수 0 은 "비정규 수( denormal )"입니다. 비정규 수는 크기가 너무 작아 정수 비트 1 로 표현 될 수가 없고 하나의 유효 비트보다 작은 값을 가질 수 있습니다.

지수의 비트값이 모두 1 인( 가장 큰 지수 ) 경우에는 특수한 숫자를 표현합니다. 가수가 0 이면 무한대( 양수 또는 음수 )를 표현합니다. 가수가 0 이 아니면 NAN( not-a-number )을 표현합니다. 잘못된 수치 연산의 결과로 발생하는 NAN 에 대해서는 이 기사에서 더 설명하지 않습니다.

IEEE 표준은 32 비트 및 64 비트 부동 소수점 표현을 정의합니다. 32 비트 ( 단일 정밀도 ) 형식은 상위에서 하위로, 부호 비트, 127 의 바이어스가 있는 8 비트 지수, 23 비트의 가수를 가집니다. 64 비트 ( 배 정밀도 ) 형식은 부호 비트, 1023 의 바이어스가 있는 11 비트 지수, 52 비트의 가수를 가집니다. 숨겨진 비트를 사용하면 정규화된 숫자의 유효 정밀도는 각각 24 비트와 53 비트입니다.

Single-precision format

31, 30-23, 22-0

S, Exponent, Significand

Double-precision format

63, 62-52, 51-0

S, Exponent, Significand

Bibliography

American National Standards Institute (1978), "American National Standard, Programming Language FORTRAN", ANSI X3.9-1978, ISO 1539-1980 (E).

IEEE Computer Society (1985), "IEEE Standard for Binary Floating-Point Arithmetic", IEEE Std 754-1985.

원문 : https://developer.nvidia.com/content/depth-precision-visualized

주의 : 번역이 개판이므로 이상하면 원문을 참조하세요.

주의 : 허락받고 번역한 것이 아니므로 언제든 내려갈 수 있습니다.

Depth Precision Visualized

By Nathan Reed, posted Jul 15 2015 at 03:54PM

Tags : Gameworks Expoert Developer, DX12, DX11

깊이 해상도( Depth Precision, 깊이 정밀도 ) 는 모든 그래픽 프로그래머가 이미 겪거나 나중에 겪게 되는 똥꼬의 고통( 골칫거리, pain in the ass )입니다. 많은 기사들과 논문들이 이 주제에 대해 다뤘으며, 다양한 깊이 버퍼 포맷과 설정들을 여러 게임들, 엔진들, 그리고 장치들에서 찾아 볼 수 있습니다.

그것이 원근 투영( perspective projection )과 상호작용하는 방식 때문에 GPU 하드웨어 깊이 매핑( mapping )은 다소 많이 알려져 있지 않으며, 그 공식에 대해 공부해도 즉각적으로 명확해지지 않을 것입니다. 그것이 동작하는 방식에 대한 직관을 얻기 위해서는 약간의 그림을 그려 보는 것이 도움이 됩니다.

그림 1.

이 기사는 세 개의 주요 파트로 나뉩니다. 첫 번째 파트에서는 비선형 깊이 매핑에 대한 약간의 동기( motivation )을 제공하려고 합니다. 두 번째 파트에서는 비선형 매핑이 서로 다른 상황에서 동작하는 방식을 이해할 수 있도록 돕는 몇 개의 다이어그래을 제공할 것입니다. 세 번째 파트에서는 Paul Upchurch 와 Mathieu Desbrun [2012 ] 에 의해 제시된 Tightening the Precision of Perspective Rendering 의 주요 결과에 대한 논의 및 재현( reproduction )을 제공합니다. 앞의 방법( 링크 )은 깊이 정밀도 상에서 실수( floating point ) 반올림( roundoff ) 에러의 효과와 관련이 있습니다.

GPU 하드웨어 깊이 버퍼는 일반적으로 카메라 앞의 놓인 오브젝트에 대한 거리를 선형적으로 표현하지 않습니다. 이는 사람들이 깊이 버퍼를 처음 접했을 때 기대하는 것과는 반대입니다. 그 대신, 깊이 버퍼는 월드 공간 깊이에 대한 역( reciprocal of world-space depth )에 비례하는 값을 저장합니다. 이러한 관례가 생긴 동기에 대해서 간단하게 언급하고자 합니다.

이 기사에서, 필자는 깊이 버퍼에 ( [0, 1] 로 저장된 ) 값을 표현하기 위해 d 를 사용할 것입니다. 그리고 뷰 축을 따라 측정된 거리인 월드 공간 깊이를 표현하기 위해서 z 를 사용할 것입니다. 월드 공간의 단위( unit )는 미터같은 단위입니다. 일반적으로 그것들의 관계는 다음 같은 형태입니다.

그림 2.

여기에서 a, b 는 ( 뷰 프러스텀의 ) near plane 과 far plane 의 설정입니다. 다시 말해, d 는 항상 1/z 의 선형 리매핑( remapping )입니다.

그것을 살펴 보면, 여러분은 d 를 취한다는 것은 여러분이 원하는 z 에 대한 어떤 함수가 될 것이라 생각할 수 있습니다. 그러면 왜 이런 선택을 하는 것일까요? 두 가지 주요 이유가 있습니다.

먼저, 1/z 은 원근 투영의 구조와 자연스럽게 어울립니다. 이는 거의 대부분의 범용 변환( transformation ) 클래스들이 직선( straight line )을 보존할 수 있도록 해 줍니다 -- 이는 하드웨어 래스터화( rasterization )를 유용하게 만들어 줍니다. 왜냐하면 삼각형의 곧은 엣지( straight edge )가 스크린 공간에서도 여전히 곧게 유지되기 때문입니다. 우리는 원근 나눗셈의 이점을 취함으로써 1/z 에 대한 선형 리매핑을 생성할 수 있습니다. 그 원근 나눗셈은 하드웨어가 미리 수행해 줍니다:

그림 3.

물론 이 접근법의 진정한 힘은 그 투영 행렬이 다른 행렬들과 곱해질 수 있다는 점이며, 그것은 여러분으로 하여금 여러 변환 단계들을 하나로 결합할 수 있도록 해 줍니다.

두 번째 이유는 Emil Persson 이 언급했듯이 1/z 가 스크린 공간에서 선형이라는 점입니다. 그러므로 래스터화를 수행하는 동안 삼각형에 대해 d 를 보간하는 것이 쉽습니다. 그리고 계층적 Z 버퍼, early Z-culling, 깊이 버퍼 압축과 같은 것들을 수행하는 것이 더욱 쉬워집니다.

공식은 어렵습니다; 그림을 몇 개 확인해 보죠.

그림 4.

이 그래프들은 읽는 방법은 오른쪽에서 왼쪽으로, 그리고 나서 위에서 아래로입니다. 왼쪽 축에 표시된 d 에서 시작합시다. d 는 1/z 에 대한 임의의 선형 리매핑일 수 있기 때문에, 우리는 이 축에서 원하는 곳에 0 과 1 을 배치할 수 있습니다. 눈금( tick mark )들은 개별적인 깊이 버퍼 값들을 표시합니다. 설명을 위한 목적으로, 필자는 4 비트로 정규화된 정수 깊이 버퍼를 시뮬레이션하고 있습니다. 그래서 16 개의 고르게 매치된 눈금들이 존재합니다( 역주 : 2⁴ = 16 ).

각 눈금에서 수평으로 갔을 때 1/z 커브와 만나는 곳에서 아래쪽 축으로 수선을 내려 봅시다. 이 축은 개별 값들이 월드 공간 깊이 범위로 나타나는 곳입니다.

위의 그래프는 "표준" 을 보여 줍니다. 이는 D3D 및 유사 API 들에서 사용되는 바닐라( vanilla ) 깊이 매핑입니다. 여러분은 1/z 커브가 near 평면과 가까운 곳의 값들을 모으고 far 평면과 가까운 값들을 흩트러 놓는다는 것을 즉각적으로 이해할 수 있을 겁니다.

또한 near 평면이 깊이 해상도에 있어서 엄청난 영향력을 미치는 이유도 쉽게 알 수 있습니다. Near 평면을 당기는 것은 d 범위를 1/z 커브의 점근선( asymptote )을 급등시키며( skyrocket ), 이는 값들이 더욱 한쪽으로 쏠리도록 분산( lopsided distribution of values )시키는 결과를 산출합니다:

그림 5.

이와 유사하게, 이러한 문맥에서 우리는 far 평면을 무한하게 밀어 내도 큰 영향을 주지 못하는 이유를 쉽게 알 수 있습니다. 그것은 단지 1/z = 0 으로 d 범위를 확장한다는 것을 의미할 뿐입니다:

그림 6.

실수 깊이 버퍼는 어떨까요? 다음 그래프는 3 개의 지수( exponent ) 비트와 3 개의 가수( mantissa ) 비트를 사용하는 실수 포맷을 시뮬레이션하는 것과 관련한 눈금들을 추가한 것입니다:

그림 7.

이제 [0, 1] 범위에 40 개의 눈금이 존재합니다 -- 앞의 16 개보다는 많지만, 대부분이 near 평면 근처에 불필요하게 몰려 있으며, 거기는 우리가 더 많은 정밀도를 필요로 하지 않는 곳입니다.

깊이 범위를 역전시키기 위해 요새 광범위하게 알려진 트릭은 d = 1 에 near 평면을 매핑하고 d = 0 에 far 평면을 매핑하는 것입니다 :

그림 8.

훨씬 낫군요! 이제 실수에 대한 quasi-logarithmic distribution 은 1/z 의 비선형성을 조금 없앱니다. 이는 우리에게 정수 깊이 버퍼와 비교했을 때 near 평면에서 유사한 정밀도를 제공하며, 원하는 곳에서 광범위하게 정밀도를 증가시킬 수 있게 해 줍니다. 이 정밀도는 여러분이 멀리 이동할 때마다 매우 천천히 악화됩니다.

역전된 Z 트릭은 아마도 여러 번 독립적으로 재창조되어 왔을 것입니다. 그러나 최소한 Eugene Lapidous 와 Guofang Jiao 에 의해 작성된 ( 안타깝게도 지금은 접근 가능한 무료 링크가 없는 ) GIGGRAPH '99 paper 까지 돌아갈 수 있습니다. 그것은 더욱 최근에 Matt Pettineo 와 Brano Kemen 의 블로그 포스트, 그리고 SIGGRAPH 2012 talk 에서 Emil Persson 의 Creating Vast Game Worlds 에서 다시 대중화되었습니다.

이전의 모든 다이어그램은 투영 후의 깊이 범위를 D3D 관례처럼 [0, 1] 이라 가정합니다. OpenGL 에서는 어떨까요?

그림 9.

 OpenGL 은 기본적으로 투영 후의 깊이 범위를 [-1, 1] 이라 가정합니다. 이는 정수 포맷에서는 별 차이를 만들지 않지만, 실수 포맷에서는 불필요하게 중간에 대부분의 정밀도가 몰립니다( 나중에 저장을 위해 깊이 버퍼에서 [0, 1] 로 매핑되기는 하지만, 그것은 도움이 되지 않습니다. 왜냐하면 [-1, 1] 로의 초기 매핑이 이미 그 범위의 뒤쪽 절반 정도를 날려먹었기 때문입니다 ). 그리고 대칭적인 관점에서 볼 때, 역전된 Z 트릭은 여기에서 아무것도 할 수 없을 것입니다.

운좋게도 데스크탑 OpenGL 에서는 광범위하게 지원되는 ARB_clip_control 을 사용해서 이 문제를 해결할 수 있습니다( 이제는 glClipControl 이라는 것을 통해서 OpenGL 4.5 의 코어에서 지원됩니다 ). 불운하게도, GL ES 에서는 못합니다.

1/z 매핑과 실수 깊이 버퍼를 사용하는 방식과 정수 깊이 버퍼를 사용하는 방식을 비교하는 것은 정밀도 스토리의 큰 부분이지 전부는 아닙니다. 심지어 여러분이 렌더링하려고 시도하는 씬을 표현하는데 충분한 깊이 정밀도를 확보하고 있다고 하더라도, 정점 변환 과정에서 정밀도 에러가 발생하기 쉽습니다.

이전에 언급했듯이, Upchurch 와 Desbrun 은 이에 대해 연구했고, 반올림 에러를 최소화하기 위한 두 개의 주요한 권고사항을 제시했습니다.

1. 무한 far 평면을 사용하십시오.

2. 투영 행렬을 다른 행렬과 분리하십시오. 그리고 정점 쉐이더에서 그것들을 뷰 행렬과 합치기보다는 개별적인 연산을 적용하십시오.

Upchurch and Desbrun came up with these recommendations through an analytical techunique, based on treating roundoff errors as small random perturbations introduced at each arithmetic operation, and keeping track of them to first order through the transform process. 필자는 그 결과를 직접적인 시뮬레이션을 통해 확인해 보기로 했습니다.

필자의 소스 코드는 여기에 있습니다 -- Python 3.4 with numpy. 이는 일련의 랜덤 점을 생성하고, 점들을 깊이에 의해 정렬하고, near 및 far 평면 사이에 점들을 선형적으로 혹은 대수적으로( logarithmically ) 배치합니다. 그리고 나서 그 점들을 뷰 및 투영 행렬들과 원근 나눗셈을 통해서 넘기는데, 32 비트 실수 정밀도 처리량( throughput )을 사용합니다. 그리고 선택적으로 최종 결과를 24 비트 정수로 양자화( quantize )합니다. 마지막으로 그것을 여러 번 실행해 인접한 두 개의 점들이, 같은 깊이 값으로 매핑되거나 실질적으로 순서가 바뀜으로 인해, 몇 번이나 구분불가능해지는지를 셈합니다. 다시 말해 그것은 서로 다른 시나리오 하에서 깊이 비교 에러가 발생하는 비율을 측정합니다 -- 우리는 이를 Z 파이팅과 같은 이슈라고 봅니다.

여기에서 near = 0.1 로 far = 10K 인 선형적으로 배치된 깊이들에 대해서 획득된 결과를 보여 줍니다( 필자는 logarithmic 깊이 배치를 시도해 봤고 다른 near/far 비율들도 배치해 봤습니다. 세부적인 수치들이 다양해져도 일반적인 경향은 같았습니다 ).

이 표에서 "indist" 는 indistinguishable 을 의미합니다( 두 개의 인접한 깊이가 최종적으로 같은 깊이 값으로 매핑된 것입니다 ). 그리고 "swap" 은 두 개의 인접한 깊이의 순서가 바뀌는 것을 의미합니다.

그림 10.

이를 그래프화하지 않은 점은 죄송합니다. 그러나 너무 많은 차원들이 존재해서 그래프로 만들기 힘들었습니다! 어떤 경우라도, 수치들을 보면, 몇 가지 일반화가 가능합니다.

• 대부분의 설정에서 실수냐 정수냐 하는 것은 의미가 없습니다. 수치 에러는 양자화 에러에서 발생합니다. 부분적으로 이는 ( float32 는 23 비트의 가수를 가지기 때문에 ) float32 와 int24 가 [0.5, 1] 에서 거의 유사한 크기여서 실제적으로는 대부분의 깊이 영역에서 추가적인 양자화 에러는 거의 존재하지 않기 때문에 발생합니다.
• 대부분의 경우에, ( Upchurch 와 Desbrun 의 제안대로 ) 뷰 및 투영 행렬들을 분리하는 것이 좀 더 나은 결과를 산출합니다. 그것은 전체적인 에러율을 낮춰주지는 않지만, it does seem to turn swaps into indistinguishables, which is a step in the right direction.
• 무한한 far 평면은 에러율에서 극소적인 차이를 보여줄 뿐입니다. upchurch 와 Desbrun 은 절대적인 수치 에러가 25% 감소한다고 했지만, 비교 에러의 비율을 감소시킨다고 해석하기는 어려워 보입니다.

그런데 위에서 지적한 것들은 실용적인 관점에서는 별로 없습니다. 왜냐하면 여기에서 중요한 실제 결과는 다음과 같기 때문입니다: 역전된 Z 매핑은 기본적으로 환상적입니다. 확인해 봅시다:

• 실수 깊이 버퍼를 사용하는 역전된 Z 는 이 테스트에서 0 의 에러율을 제공합니다. 물론 여러분은 입력 깊이 값들의 배치를 좀 더 타이트하게 만들어서 에러를 생성할 수는 있겠죠. 그래도 여전히 역전된 Z 는 다른 옵션들보다는 더욱 정확한 결과들을 산출할 것입니다.
• 정수 깊이 버퍼를 사용하는 역전된 Z 는 다른 정수 옵션들과 비교하면 좋은 결과를 산출합니다.
• 역전된 Z 는 미리 결합된 뷰/투영 행렬을 사용하는 것과 분리된 뷰/투영행렬을 사용하는 것에서의 차이를 제거해 버립니다. 그리고 무한한 far 평면을 사용하는 것과 유한한 far 평면을 사용하는 것의 차이도 제거합니다. 다시 말해 역전된 Z 값을 사용하면, 정밀도에 영향을 주지 않으면서도, 투영 행렬을 다른 행렬들과 결합시킬 수 있으며, 원하는 far 평면을 지정할 수 있다는 이야기입니다.

필자는 여기에서의 결론은 명확하다고 생각합니다. 어떤 원근 투영 상황이라고 할지라도, 실수 깊이 버퍼를 역전된 Z 와 함께 사용하십시오! 그리고 여러분이 실수 깊이 버퍼를 사용하지 못하는 상황이라고 해도 여전히 역전된 Z 버퍼를 사용해야 합니다. 이는 모든 정밀도 문제에 대한 만병통치약은 아닙니다. 여러분이 극단적인 깊이 범위를 포함하는 오픈 월드 환경을 만들고 있다면 더욱 그러합니다. 그렇지만 그것은 시작일 뿐입니다.

Nathan 은 Graphics Programmer 이며, 현재 NVIDIA 의 DevTech 소프트웨어 팀에서 일하고 있습니다. 여러분은 그의 블로그를 여기에서 구독하실 수 있습니다.

원문 : Moment of inertia, Wikipedia

주의 : 허락받고 번역한 것이 아니므로 언제든 내려갈 수 있습니다.

주의 : 번역이 개판이므로 이상하면 원문을 참조하세요.

주의 : 번역은 소개, 정의, 단순 진자 항목까지 되어 있습니다. 더 많은 정보는 원문에서 확인하시기 바랍니다.

Moment of inertia

이 기사는 회전하는 오브젝트의 질량 관성 모멘트( mass moment of inertia )에 대한 것입니다. 빔의 휨( beam bending )에서의 단면 관성 모멘트에 대해서 알고자 한다면 second moment of area 를 참조하십시오.

강체( rigid body ) 의 질량 관성 모멘트( moment of inertia )는 다른 말로는 각질량( angular mass )이나 회전 관성( rotational inertia ) 이라고도 알려져 있는데, 이는 회전 축에 대한 각 가속도( angular acceleration )를 위해 필요한 토크( torque, 돌림힘 )을 결정하는 텐서( tensor, 긴장 )입니다.  이는 물체( body )의 질량 분포( mass distribution ) 및 선택된 축에 의존하며, 모멘트가 클수록 바디의 회전을 변경하는데 더 많은 돌림힘이 요구됩니다. 이는 extensive( additive ) property^[각주:1] 입니다 : 복합시스템의 관성 모멘트는 ( 같은 축에 대해 수집된 ) 그것을 구성하는 서브시스템의 관성 모멘트의 합입니다. 그것의 정의들 중 하나가 축 r 로부터의 거리 관점에서의 질량에 대한 2차 모멘트이며, 전체 질량 Q 에 대한 적분입니다.

평면에서 회전하도록 제약이 걸려있는 물체들에 대해서는, 평면과 수직인 축에 대한 관성 모멘트만 고려해도 충분합니다. 3 차원에서 자유롭게 회전하는 물체들에 대해서는, 그것들의 모멘트들은 대칭 3x3 행렬에 의해 기술될 수 있습니다; 각 물체는 상호 수직적인 축들( mutually perpendicular axes )의 집합을 가지는데, 이 행렬은 대각행렬이며 그 축들에 대한 토크들은 다른 축들과는 독립적으로 작용합니다.

Introduction

물체가 축 주변을 회전하거나 자유롭게 회전할 때, 그것의 각 운동량( angular momentum )을 변경하기 위해서는 토크가 작용해야만 합니다. 각 운동량을 주어진 비율로 변경하기 위해 필요한 토크의 양은 물체의 관성 모멘트에 비례합니다. 관성 모멘트는 표준 단위계에서는 killogram-squre meters( kg ˙ m² )로 표현되며 imperial 이나 US 단위계에서는 pound-squre feet( lb_m ˙ ft² )으로 표현됩니다.

회전 운동역학( rotational kinetics )에서의 관성 모멘트는 선형 운동역학에서의 질량( 관성 )과 같은 역할을 수행합니다 - 둘다 물체의 움직임을 변경하는데 대한 저항으로써 작용합니다. 관성 모멘트는 회전 축 주변에 질량이 어떻게 분포되어 있느냐에 의존하며, 이는 어떤 축이 주어졌냐에 따라 매우 다양합니다. 점질량의 경우에, 어떤 축에 대한 관성 모멘트는 d²m 으로 주어지는데, 여기에서 d 는 축으로부터의 거리이며 m 은 질량입니다. 확장된 물체( extended body )의 경우에, 관성 모멘트는 작은 조각의 질량에다가 선택된 축으로부터의 거리의 제곱을 곱한 것들의 전체 합일 뿐입니다. 표준적인 모양을 가지고 균일한 밀도를 가진 확장된 물체의 경우에는, 보통 이러한 합은 오브젝트의 차수, 모양, 전체 질량등에 의존하는 간단한 식으로 표현될 수 있습니다.

1673 년에 Christiaan Huygens 는, 복합 진자( compound pendulum )라 알려진, 회전축( pivot )에 매달린 물체의 진동에 대한 자신의 연구에서 이 파라미터를 소개했습니다. 관성 모멘트라는 개념은 Leonhard Euler 에 의해 1765 년에 그의 저서인 Theoria motus corporum solidorum seu rigidorum 에서 소개되었으며, 이는 Euler's second law 에 통합되었습니다.

복합 진자의 자연적 진동 주파수는 진자의 질량에 작용하는 중력으로 인해 발생하는 토크와 관성 모멘트에 의해 정의되는 가속도에 대한 저항의 비율로부터 획득됩니다( 역주 : 문장이 길어서 헷갈리는데, "토크 vs 저항" 이라고 보심 될듯합니다 ). 이 자연적 주파수를 점질량으로 구성된 단순 진자의 주파수와 비교하는 것은 확장된 물체의 관성 모멘트를 위한 수학적 공식을 제공합니다.

관성 모멘트는 강체의 운동량( momentum ), 운동 에너지( kinetic energy ), 뉴턴의 운동 법칙( Newton's laws of motion )에서 모양과 질량을 겹합한 물리적 속성으로서 나타나기도 합니다. 평면적( planar ) 이동과 공간적( spatial ) 이동에서 관성 모멘트가 나타나는 방식에는 흥미로운 차이점이 있습니다. 평면적 이동은 관성 모멘트를 정의하는 단일 스칼라( scalar ) 값을 가지는 반면, 공간적 이동은 같은 계산이 관성 모멘트에 대한 3 x 3 행렬을 산출하며, 이는 관성 행렬 혹은 관성 텐서라 불립니다.

회전하는 플라이휠( flywheel, 기계나 엔진의 회전속도에 안정감을 주기 위한 무거운 바퀴 - 네이버 사전 )의 관성 모멘트는 회전 출력을 부드럽게 만들기 위해 적용되는 토크의 다양성( variation )에 저항하기 위해 기계에서 사용됩니다. 비행기의 장축, 수평축, 수직축에 대한 관성 모멘트는 자신의 날개, 뒷날개( elevator ), 꼬리의 제어면( control surface )에 적용되는 steering forces 가 비행기의 roll, pitch, yaw 에 미치는 영향을 결정합니다.

Definition

관성 모멘트 I 는 주축( principal axis ) 주위의 각속도( angular velocity ) ω 에 대한 계( system )의 각운동량( angular momentum ) L 의 비율로서 정의됩니다.

계의 각운동량은 상수입니다. 그래서 관성 모멘트가 작아질수록 각속도는 증가해야만 합니다. 이는 회전하고 있는 피규어 스케이터가 더 빠른 회전을 위해 바깥으로 뻗은 팔을 당기거나 다이빙 선수가 자신의 몸을 껴안기 형태로 굽힐 때 발생합니다.

회전하는 피규어 스케이터는 팔을 안으로 당김으로써 관성 모멘트를 줄일 수 있습니다.

이는 스케이터가 더 빠르게 회전하게 만드는데, 

그 이유는 각운동량 보존 법칙( conservation of angular momentum ) 때문입니다.

물체의 모양이 변하지 않으면, 그것의 관성 모멘트는 뉴튼의 운동 법칙에서 주축 주변의 각가속도( angular acceleration )에 대한 물체상에 적용된 토크 τ 의 비율로 나타납니다.

단순 진자( simple pendulum )에서 이 정의는 진자의 질량 m 항과 회전 중심으로부터의 거리 r  항으로 관성 모멘트 I 를 위한 공식을 산출합니다.

그러므로, 관성 모멘트는 물체와 그것의 지아메트리( geometry ) 혹은 모양( shape )의 질량 m 과 회전 축으로부터의 거리 r 에 모두 의존합니다.

이 단순한 공식은 임의의 모양을 가진 물체를 위한 관성 모멘트를 정의하기 위해서 일반화됩니다. 점질량 dm 을 축 S 에 대한 수직 거리 r 의 제곱과 곱한것을 모두 더함으로써 이루어집니다.

일반적으로, 질량 m 을 가진 물체가 주어졌을 때, 유효 반지름( effective radius ) k 는 질량 중심을 관통하는 축을 위해서 정의될 수 있으며, 그러한 물체의 관성 모멘트의 값은 다음과 같습니다.

여기에서 k 는 선회 반경( radius of gyration )이라 알려져 있습니다.

Simple pendulum

관성 모멘트는 단순 진자를 사용해서 측정될 수 있습니다. 왜냐하면 그것은 중력에 의해서 발생되는 회전에 대한 저항이기 때문입니다. 수학적으로 볼 때, 진자의 관성 모멘트는 ( 역주 : 끈이 고정된 ) 회전 중심에 대한 진자의 각가속도에 대한 진자의 회전중심에 대해 작용하는 중력 때문에 발생하는 토크의 비율입니다. 단순 진자의 경우, 이는 입자의 질량 m 과 회전축에 대한 거리 r 의 제곱의 곱으로 표현됩니다.

이는 다음과 같이 보일 수 있습니다: 단순 진자의 질량에 적용되는 중력의 힘은 진자 이동 평면에 수직인 축 주변의 토크를 생성합니다. 

여기에서 r 은 거리벡터인데 이는 토크 축에 대한 힘과 수직으로 작용합니다. 여기에서 F 는 질량에 대한 알짜힘( net force )의 탄젠트 요소( tangential component ) 입니다. 이 토크와 연관된 것은 끈의 각가속도 α 와 이 축 주변의 질량입니다. 그 질량은 원으로 제한되므로, 질량에 대한 접선 가속도( tangential acceleration )는 다음과 같습니다.

F = ma 이기 때문에, 토크 공식은 다음과 같습니다:

여기에서 e 는 진자 평면과 수직인 단위 벡터입니다( 두 번째 단계에서 마지막 단계로 가는 것은 BAC-CAB rule( vector triple product )때문인데, 이는 α가 항상 r 에 수직임을 이용합니다 ). I = mr² 이라는 물리량은 회전 중심 주변의 단일 질량에 대한 관성 모멘트입니다.

 I = mr² 은 단순 진자의 각운동량에서도 나타나는데, 여기에서는 회전축 중심의 진자 질량에 대한 속도 v = ω x r 로부터 계산되는데, 여기에서 ω 는 회전 중심 주변의 질량에 대한 각속도입니다. 이 각운동량은 다음에 의해 주어집니다.

그것과 비슷한 수학이 이전 공식을 유도하는데 사용되었습니다.

이와 유사하게 진자 질량에 대한 운동 에너지( kinetic energy )는 회전축 중심의 진자의 가속도에 의해서 정의됩니다.

이는  I = mr² 물리량은 회전 관성을 정의하기 위해서 물체의 모양과 질량을 결합한 것임을 보여줍니다. 임의의 모양을 가진 물체의 관성 모멘트는 물체 내의 질량 모든 질량 요소들에 대한 mr² 값의 합입니다.

원문 : Character Animation: Skeletons and Inverse Kinematics

주의 : 번역이 개판이므로 이상하면 원문을 참조하십시오.

주의 : 허락받고 번역한 것이 아니므로 언제든 내려갈 수 있습니다.

Introduction

자! 당신은 고딕 성을 만들었다 - 이제 영웅이 게임 안으로 달려 들어가 성벽을 방어할 시간이다. 당신의 게임 엔진은 스켈레톤과 역운동학( IK, Inverse Kinematics )라 불리는 애니메이션 시스템, 그리고 제어할 수 있는 복잡한 계층구조 설정을 지원한다. 당신은 그것들을 모두 시도해 보고 싶은 갈망을 가지고 있다. 훌륭하다! 그러나 당신이 이전에 스켈레톤을 써 본적이 없거나 관절이 있는 모델에 IK 를 적용해 본적이 없다면, 당신은 충격에 빠질 것이다. 일부는 당신이 좋아하게 될 것이고, 일부는 그렇지 않을 것이다... 적어도 처음에는 그럴 것이다.

이 문서는, 역운동학과 애니메이션되는 캐릭터들을 움직이기 위한 top-down 회전 시스템인 순운동학( Forward Kinematics )을 위해, 스켈레톤을 사용하기 위한 초급 및 중급 원칙들을 몇 가지 소개할 것이다. 그러다 보면, 그것은 당신이 갈망하는 질문들에 대한 답을 줄 것이다. 당신이 이 글을 모두 읽었을 때, 당신의 앞을 가로 막는 장애물들을 뛰어 넘을 수 있는 충분한 에너지를 느낄 수 있기를 바란다.

Forward Kinematics vs. Inverse Kinematics

얼마 전까지만 해도, 게임 캐릭터들은 a lot like shellfish( 역주 : 조개 껍데기 같이 쌓인 구조? )였다: 그것들은 기본적으로 돌같은 세그먼트( segment )들을 쌓아 놓은 것일 뿐이었다. 애니메이터들이 바랄 수 있는 최고의 것은 기본 계층구조를 다룰 수 있는 플랫폼이었으며, 이는 그들이 모든 세그먼트들의 위치와 키프레임을 한 번에 설정할 수 있도록 해 주었다. 여기에서 현실감있게 팔꿈치를 구부리거나 근육이 움직이는 것은 바라지 말기 바란다 - 이는 일어날 수 없는 일이었다. 실시간 표면 변형( deformation )을 다룰 수 있는 현대의 프로세싱 파워가 없이는, 게임은 단지 로봇이나 갑옷만을 표현했었다.

Advanced Processor Performance Enables Computer-generated Skeletons Animated with inverse kinematics

얼마동안은 게임 개발자들은 불편함을 조용히 감내했다. 그리고 나서 PC 들은 더욱 빠르고 스마트해졌으며, 이는 게임 엔진들을 더욱 빠르고 스마트하게 만들어 줬다. 발전된 처리 성능은 단순히 세그먼트화된 캐릭터를 함께 저장하는 것 뿐만 아니라 그 캐릭터들의 스킨을 실제로 변형하기 위해서 컴퓨터가 생성한 스켈레톤을 사용할 수 있도록 해 주었다. IK 가 선택할 수 있는 제어 시스템이 되었다.

The Scoop on Hierarchies

역운동학을 이해하기 위해서는 기본적인 계층구조 및 순운동학에 대해서 이해하는 것이 중요하다. 직접적으로 target-to-target morphing 을 하는 것 외에, 애니메이터들은 대부분 자신의 캐릭터들을 움직이기 위해서 갖가지 계층구조를 사용한다. 계층은 부모-자식-이웃 관계를 말한다. 하나의 오브젝트에 부모나 자식을 할당하는 작업은 "parenting" 이나 "grouping" 이라 불린다. 인간의 다리같은 경우에, 위쪽 다리( upper leg )의 부모는 엉덩이( hip )이며, 아래쪽 다리( lower leg )은 위쪽 다리의 자식이다. 그리고 발( foot )은 아래쪽 다리의 자식이다. 오른쪽 위쪽 다리는 왼쪽과 이웃 관계를 공유하며, 둘다 엉덩이의 자식들이다( 그림 1 참조 ).

그림 1. 순운동학을 위한 기본적인 아래쪽 몸 설정 및 계층.

또 다른 계층에 대한 학설은 "inverted tree" 모델을 사용한다. 여기에서는 부모( 엉덩이나 허리( pelvis ) )가 "루트( root )"라 불린다. While no part of a hierarchy is ever really referred as the "trunk", the children, and their children, become "branches"( 그림 1 참조 ).

The Trouble with Forward Kinematics

캐릭터의 손이 기본 계층 하에서 움직이기를 원한다면, 먼저 위쪽 팔( upper arm, 상박 )을 회전시키고 나서 아래쪽 팔( forearm, 팔뚝, 하박 )을 회전시키고, 마지막으로 손 자체를 회전시키는 작업을 전체 팔이 올바른 위치에 올 때까지 해야 한다. 이는 회전의 "top-down" 시스템이며 순운동학이라 불리며, 기본 애니메이션을 위한 훌륭한 시스템이다.

애니메이션은 순운동학과 기본 계층구조를 사용하면 단순해 보인다 - 당신의 캐릭터가 발이 바닥 위로 미끌어지지 않게 걷는다든가, 몸이 돌고 있는 동안에 발은 그대로 머물러 있는다든가 하는 특정 행위를 하기 전까지는 단순하다. 그런 경우에, 당신은 미적인 만족을 시켜 주지는 않는 두 가지 선택을 할 수 있다:

• 전체 계층을 회전시킨다( 이는 불필요하게 말이 미끄러지게 만든다 ).
• 계층구조의 위쪽( 엉덩이 )만 회전시키고 다른 부분은 그대로 둔다( 보기에 매우 고통스럽다 ).

그 시점에서, 순운동학( 그리고 당신의 캐릭터 )은 분리된다. 걷고 있는 캐릭터의 발을 ( 바닥에 ) 심는 것은 거의 불가능하다. 왜냐하면 오브젝트에 있어서 가장 어려운 것은 계층 구조의 맨 아래쪽이, 그 위쪽이 움직이고 있음에도 불구하고, 그대로 남아 있도록 하는 것이기 때문이다. The illusion of stability actually takes constant readjustment( 그림 2 참조 ).

그림 2. 기본 계층 구조와 순운동학을 사용할 때의 어려움은 전체 계층 구조를 회전시키거나 발을 미끄러지게 할 때 나타난다. 발들을 땅에 그대로 두면 그 결과는 참담할 수 있다.

The Advent of Computer-generated Skeletons using Inverse Kinematics

그림 3. Computer-generated skeleton

다행히도 오늘날의 게임 애니메이터들은 장편 극영화( feature film )을 위해서만 사용되었던 같은 애니메이션 기법들을 사용할 수 있게 되었다. 장편 극영화의 세계에서는, 다이노사우르스의 발목, 무릎, 허벅지, 엉덩이 등의 발가락 위쪽의 관절들이 미세하게 움직이기 때문에 발가락이 화면상에서 미끄러져 보이는 것을 보상하기 위해 발가락들에 대한 지속적인 재조정이 이루어진다. 그 조정은 픽셀보다는 피트 단위로 측정된다. 캐릭터를 현실감있게 움직이기 위해서는 순운동학 이외의 뭔가가 필요하다는 것은 확실해졌다. 또 다른 시네마틱 문제 - 캐릭터가 움직일 때마다 관절이 구겨지거나( crease ) 불룩해지는( bulge ) 그럴듯한 묘사 - 는 연속성있는 메쉬( continuous mesh )로부터 만들어진 모델을 사용해야만 해결될 수 있을 것이다. 그러나 어떻게 solid band 와 walk 를 만들 수 있을까? Turning to an earlier staple of film special effects, 스톱 모션( Stop Motion ) 소프트웨어 개발자들은 아마츄어 시스템이나 스켈레톤을 자신들의 computer-generated( CG ) 모델들에 포함시켰으며, 스켈레톤을 제어하기 위해서 역운동학( Inverse Kinematics )라 불리는 시스템을 개발했다.

개념적으로 볼 때, CG 스켈레톤은 이해하기 쉽다. 그것은 우리의 물리적 뼈대를 흉내낸 것이다 - 각 관절에 있는 힘줄( tendons )을 사용하는 강제 구조가 서로를 연결한다. 이는 inverted tree 구조이며, 부모는 뼈대의 루트라 불린다. 루트는 보통 캐릭터의 무게 중심에 위치한다; 이는 보통 이족 보행 동물의 등뼈( spine )의 시작점이다. 이 시스템을 ( 뼈대 없는, non-skeletal ) 기본 계층 구조보다 더 낫게 만드는 것은 힘줄이며, 이는 존재하기는 하지만 컴퓨터 3D 프로그램에서는 보이지 않는 요소이다. 뼈대 없는 오브젝트로부터 생성된 계층 속에 있으므로, 스켈레톤은 순운동학에 의해 top-down 으로 제어될 수 있다. 그러나 스켈레톤의 가장 큰 이점은 계층구조의 위족에서 아래쪽으로 제어를 전달할 수 있는 기능이다. 그것은 문제를 아래에서 위로 ( 순운동학의 역으로 ) "풀기( solve )" 때문에, 그 과정은 "역운동학" 혹은 IK 라 불린다. 이는 top-down 회전을 다루는 과정보다 더욱 직관적이며 더 적은 시간을 소비한다.

NOTE : 어떤 애니메이션 패키지들은 cube, sphere, 그리고 null object 들과 같은 "뼈대 없는" 오브젝트들에 대한 IK 응용프로그램을 허용한다. 하지만 이런 IK 를 생성하고 운용하는 것은 매우 복잡하다.

그림 4. IK 핸들을 사용하는 단순한 본 설정. 보통 본들은 루트( root )로 갈 수록 두껍고 이펙터( effector )로 갈수록 얇아지는 형태로 묘사된다. 녹색 삼각형은 "팔꿈치"를 구부림으로써 형성되는데, 어깨 위쪽과 손목은 팔꿈치의 회전 평면을 나타낸다. 이 평면은 팔꿈치를 바깥으로 휘두르는 것을 허용하기 위해서 조정된다.

스켈레탈 체인( skeletal chain )에서 가장 아래쪽에 있는 링크( link )는 보통 골( goal )이나 엔드이펙터( end-effector )라 불린다( 그림4 참조 ) ( 이 이름들은 다른 프로그램들에서는 다른 의미로 사용될 수 있다는 점에 주의하라 ). 세그먼트화된 모델의 경우에 캐릭터의 "피부( flesh )", 팔다리( limbs ), 몸통( torso ), 머리( head ) 등은 가장 가까운 스켈레톤의 본( 혹은 관절( joint ) )의 자식으로 붙는다. 단일 메쉬로 된 폴리곤 모델이나 seamless NURBS 모델의 경우에, 당신은 밑에 있는 스켈레톤 위에 모델을 씌우게( skin or envelope ) 될 것이다.

NOTE : 캐릭터의 팔다리, 머리, 피부, 혹은 옷은 보통 "지오메트리( geometry )" 이라 불린다. 지오메트리는 렌더링될 수 있지만, 스켈레톤은 렌더링되지 않는다.

지오메트리를 움직이는 대신에 스켈레톤을 사용하면, 스켈레톤 자체가 움직이게 되며, 지오메트리는 그것에 맞춰서 따라 가게 된다. 본들은 그것들 사이에 보이지 않는 힘줄을 가지고 있기 때문에, 계층구조의 일부만 회전하고 있을 때 관절이 분리되지 않는다. 한술 더 떠서, 당신은 스켈레탈 체인에 IK 를 적용할 수도 있다.

Adventage of Inverse Kinematics

자, 지금까지 말한 것들이 애니메이터에게 무슨 의미를 가질까? 그것은 당신이 체인의 말단- 예를 들어 손 - 을 확 잡아당길 수 있으며 손 위쪽에 있는 모든 본들이 자동으로 적절한 위치로 가기 위해 회전된다는 것을 의미한다. 이는 캐릭터가 어딘가에 도달해야만 할 때 정말 플러스 요인이 된다. 예를 들어 나무에서 사과를 딴다는가 하는 것 말이다. 마음속으로 어깨, 위쪽 팔, 팔꿈치, 손목을 그 위치에 도달하기 위해서 얼마나 회전시켜야 하는지를 계산할 필요가 없다. 애니메이터는 단지 손을 사과 위에 올리기만 하면 된다. 그러면 팔의 나머지 부분들은 따라 오게 된다.

기저에 깔린 스켈레톤을 사용하는 것의 부가 효과는 본과 관절이 표면을 변형( deformation )하기 위한 자연스런 제어 구조를 제공한다는 것이다. 변형을 사용하면, 기하 도형상의 각 제어점들은 본과 관절에 대한 상대 위치로 이동한다. 이는 지오메트리의 전체 조각을 한 번에 움직이는 것과 비교했을 때 뚜렷한 개선점이다.

모델이 스켈레톤 위에 입혀졌을 때( skinned or enveloped ), 운동학과 순운동학은 그것을 움직이기 위해서 사용될 수 있다. 스켈레톤의 일부분에 대해 운동학을 사용하는 것에 대한 이점들이 여전히 존재한다. 어떤 패키지들은 순운동학과 역운동학을 같은 스켈레탈 체인에 동시에 사용할 수 있도록 허용하며, 심지어는 실시간에 그것들 사이를 전환할 수 있도록 허용한다. 그리고 어떤 패키지들은 엄청난 노력을 해야지 그것들을 전환할 수 있도록 한다. 이를 위해서 당신은 제약( constraints )( 제약은 키프레임에 들어 가거나 빠질 수 있는 자성같은 것이라 생각할 수 있다 )이나 표현식( 수학적 공식 ), 혹은 그것들의 조합을 도입해야만 한다.

Bone Basics

먼저 소프트웨어 패키지를 살펴 보자. 그리고 나서 우리 본과 관절들을 살펴 보고, 마지막으로 그것들이 제어되는 방식에 대해서 살펴 보자.

Software Packages

모든 응용프로그램에서 스켈레톤이 같은 방식으로 제어되거나 표현되지는 않는다. IZWare Mirai, Alias Wavefront Maya, PowerAnimator 와 같은 패키지에서는, 당신이 완벽하고 완전히 붙어 있는 팔다리를 가진 스켈레톤들을 생성할 수 있었다. 이 문서를 작성한 시점에는 Softimage 3D 와 XSI 는 그런 기능을 지원하지는 않았지만, 그것들은 팔 체인, 다리 체인, 목 체인 등을 결합할 수 있는 도구를 제공하고 있었다. 이는 "제약"이라 불리는 독립된 제어 시스템들과 parenting 을 통해서 수행되었다.

그림 5. 지오메트리가 입혀지면, 서피스 제어점들은 그것들과 가장 가까운 본들에 의해 제어된다. 본들이 서피스에 대한 제어를 공유하면, 부드러운 주름과 구부림이 가능해진다. 그러나 서피스가 변형된 결과가 당신의 의도와 맞지 않는다 하더라도, 스켈레톤은 세그먼트화된 모델을 묶는 데 있어서 훌륭하며, 그것들의 관절들은 모든 조각들을 위한 자연스런 피봇( pivot ) 포인트를 제공한다.

어떤 패키지들은 역운동학 시스템을 제공하지만 본을 전혀 지원하지 않는다. 대신에 당신은 자신만의 스켈레톤을 주요 오브젝트로부터 만들어서 스켈레탈 속성들을 각 캐릭터의 개별 파트들에 부여할 수 있다. Softimage 3D, Hash Animation: Master, Discreet 3d Studio Max 와 같은 다른 패키지들은 두 가지 옵션을 모두 제공하는데, ( 보통 렌더링되지 않는 지오메트리를 사용하는 중심이나 피봇인 ) nulls 나 더미 오브젝트같은 다른 오브젝트들을 일반적인 스켈레탈 계층 구조 내로 포함시킬 수 있도록 허용해 준다. 여기에서 우리는 간략함을 위해 이러한 모든 오브젝트들을 "nulls" 라 부르기로 한다. 이 nulls 는 스케일, 회전, 이동될 수 있으며, 이는 당신의 캐릭터 메쉬의 제어점들을 그것들을 따라서 움직이도록 한다. 이 기법은 보통 근육을 볼록하게 만들거나 흉부를 확대하거나 하기 위해서 Softimage 3D 에서 사용된다( 그림 6 참조 ).

그림 6. Softimage 3D 에서 스켈레탈 구조( 보라색 오브젝트와 박스 )에 직접적으로 parenting 된 "null" 오브젝트를 사용하여 간단하게 근육 부풀리기( bulge ) 설정을 하는 모습. null 의 이동, 회전, 스케일링은 근육의 위치와 부풀림에 영향을 주며, 표현식( expressions )을 통해 팔꿈치 회전에 쉽게 엮일 수 있다. 왼쪽에 보이는 검은색 박스는 이 패밀리의 부모 역할을 하는 팔 지오메트리를 보여 준다. 파란색 박스는 루트, 팔꿈치, 손목의 관절이며 이는 그것들 사이의 "본들"을 회전시킨다. Softimage 3D 에서 관절들은 선택 가능한 오브젝트이며, 본들은 그렇지 않다는 것에 주의하라.  Softimage XSI 에서는 둘 다 선택할 수 있다.

개별 본들은 자신만의 로컬 축들을 가진 상태에서 생성되며, ( 항상은 아니고 ) 보통은 X, Y, Z 이다. 지오메트리를 사용할 때, 이 축들의 위치와 오리엔테이션( 역주 : orientation 은 기저 벡터로 이루어진 하나의 좌표계 공간을 의미함. 예를 들어 y-up 왼손 자표계, z-up 오른손 좌표계 )은 본의 피봇 포인트를 결정할 뿐아니라 그것의 회전 방향도 결정한다. 일반적으로 본들은 용접된 두 개의 조각으로 생각될 수 있다 - 본 자체와 본을 회전시킬 수 있도록 하는 관절. 그러나 모든 패키지들이 이러한 개념을 사용하는 것은 아니라는 것에 주의할 필요가 있다. 예를 들어 Softimage XSI 와 3D 는 전체 본 세그먼트들을 관절이라 부른다. Maya 와 IZWare Mirai 에서는 관절은 ( 본에 ) 붙어있는 것이지만, 개별적으로 선택될 수 있는 오브젝트이다. 이는 "굴근( flexors )"( 역주 : 구부리는데 사용하는 근육 ) 와 같은 변형되는 오브젝트들이 관절 자체나 본의 장축을 따라서 배치될 수 있도록 해 준다. 굴근들은 팔꿈치 안쪽의 주름( 관절 배치를 위한 좋은 후보 )과 같은 현실감있는 주름과 ( 본을 따라 배치된 굴근들의 ) 근육 부풀림을 가능하게 해 준다.

어떤 경우에, 축들은 고정된다 - 사용자는 본의 중심의 오리엔테이션을 변경할 수 없다. Softimage 3D 에서, X 축은 항상 본의 장축을 바라 본다. Maya 와 같은 다른 패키지들은 중심의 오리엔테이션을 선택할 수 있도록 한다. 이러한 패키지들은 본의 방향을 고려하지 않고 중심을 자유롭게 회전할 수 있도록 해 준다. 비록 그렇게 하는 것이 원하지 않는 결과를 나을 수 있기는 하지만 말이다.

피봇과 오리엔테이션이 중요한 이유는 무엇일까? 전문적인 애니메이션은 이것들을 올바르게 하는 것만을 고려하는 것은 아니다 - 그것을 빠르게 하는 것도 고려해야 한다. 만약 당신의 본들이 같은 방식으로 구성되었다면( 우리는 양의 X 축이 각 본의 장축을 바라보도록 설정할 것이다 ), 그것은 당신의 손가락들, 무릎들, 팔꿈치들, 척추가 같은 축을 중심으로 앞뒤로 구부려진다는 것을 의미한다. 대부분의 설정에서 그 축은 Z 축이다. 이는 딱부러진 표현을 창출하도록 한다( This makes creating expressions a snap ). 당신은 캐릭터가 어떤 방향으로 움직일지에 대해서 추측하거나 시도하거나 에러를 검사할 필요가 없다.

An Example of Surface Deformation using Bones

손바닥을 위로 바라보게 한 상태에서 손을 맞잡아 보라. 그리고 아래쪽 팔( forearm )을 보라. 이제 어깨를 움직이지 말고, 엄지 손가락이 천장을 가리키도록 회전해 보라. 만약 아래쪽 팔이 하나의 꽉찬 조각으로서 회전하고 있다면, 손목과 팔꿈치 사이에서 그리 미세하지 않은 회전을 보는 것은 불가능할 것이다( 혹은 적어도 고통스러울 것이다 ). 손과 더 가까운 피부는 손목 관절을 따라서 회전하지만 이 효과는 팔꿈치 쪽으로 갈 수록 낮아진다는 것에 유의하라. 서피스 변형을 사용하면, 덮혀 씌여진 지오메트리의 각 제어점들은 가장 가까운 관절이나 본에 의해서 제어된다.

This means that characters no longer need be loose piles of rock-hard segments. 팔꿈치는 자연스럽게 구부려진다; 심지어 이두박근( biceps )이 부풀려지거나 평평해진다( 그림 5 참조 ).

Bone Control

자, 이제 우리는 시작점으로 되돌아 왔다: 당신은 완벽한 스켈레탈 시스템과 IK 시스템을 지원하는 응용프로그램을 구입했다 치자. 당신의 문제는 끝났다. 맞나? 글쎄, 정확히 그렇진 않다. 나쁜 소식은 IK 시스템이 항상 순운동학 시스템보다 직관적이지는 않다는 것이다. 사과를 집거나 걷고 있는 동안에 바닥에 발을 붙이거나 하는 경우를 위해서는, IK 가 직관적이고 사용하기 쉬우며, 당신이 적절하게 그것을 설정할 수 있도록 해 준다. 그 "설정"은 본과 함께 동작하며 IK 가 시도되는 곳이다. 그 설정을 이해하는 데는 시간이 좀 걸린다.

Where to Begin

당신의 관절을 살펴 보라. 너무 깊이 들어 가기 전에, 당신의 몸이 작동하는 방식을 고려하고 컴퓨터가 생성해 준 스켈레톤은 인간의 스켈레톤과 완벽하게 같지 않음을 기억하라 - 그것은 하나의 표현일 뿐이다. 애니메이션 툴이 사실성을 반영하기 위해 점점 발전해 가고 있다고는 하지만, 애니메이션을 그럴싸하게 만드는 것은 여전히 애니메이터인 당신에게 달려 있다. 

관절이 동작하는 다양한 방식을 생각해 보라. 팔꿈치와 무릎은 어깨나 엉덩이와는 다르게 움직이는데, 그것들도 서로 조금씩 다르게 움직이며, 이 모든 것들은 등이나 목이 구부려지는 것과는 또 다르다. 일반적으로, 애니메이션 패키지들은 당신에게 하나나 혹은 두 가지 유형의 본들을 제공한다. 그것들은 본을 제어하기 위한 몇 가지 옵션들을 제공하기도 한다. 비록 우리 인간들은 발, 다리, 손, 장기들을 위한 수 백개의 본들을 가지고 있지만, CG 스켈레톤을 만들 때는 우리의 내부 본들은 거의 매칭될 필요가 없다. 모든 것을 매칭하려는 기법은 보통 애니메이션의 관점에서 역효과를 낸다: 서피스 제어를 위해서 너무 많은 본들을 가지는 것은 식당에서 너무 많은 메뉴를 가지고 있느 것과 같다. 타협하라. 가능한한 적은 개수의 본들만 사용하라. 다시 말하지만, 이는 그럴싸한 것을 만드는 것이지 실제를 만드는 것이 아니다.

Joint Types and Control

편의를 위해, 당신은 두 종류의 관절만을 가지고 있으면 된다: 하나는 소켓에서 모든 방향으로 휘두를 수 있는 것이고( which is really more than any of yours do without excruciating pain ), 다른 하나는 팔꿈치처럼 한 방향으로 구부릴 수 있는 것이다. Softimage 3D 는 모든 방향으로 회전할 수 있는 기능을 가진 모든 스켈레탈 체인에 대한 첫 번째 관절( root )과 절구공이 관절( ball-and-socket joint )을 제공함으로써 이를 다룬다. 그러면 당신은 "3D" 스켈레톤을 선택할지 "2D" 스켈레톤을 선택할지 결정하게 된다. 3D 스켈레톤은 루트처럼 모든 관절을 다루고 2D 스켈레톤은 볼소켓 관절처럼 특정 축을 따라서만 구부릴 수 있게 한다. 볼소켓 관절에서 시작해서 팔꿈치같은 관절에서 끝나는 "2D" 스켈레톤은 팔이나 다리를 위해서 최고이다. 또한 동시에 두 개 이상의 링크를 사용하지 않는 것이 최선이다.

Dealing with Challenges

동시에 두 개 이상의 링크를 사용하면 어떤 일이 벌어질까? 발과 같은 것을 위한 세 번째 링크를 추가한다거나 캐릭터가 사과를 집는 움직임을 만들기 위해서 IK 를 사용한다거나 하는 일반적인 도전들에 대해서 이야기해 보자.

The Third Link Dilemma: What About Adding Feet?

IK 에 의해서 제어되는 체인에서 두 개의 링크는 충분히 직관적이다. 하지만 발은 세 번째 링크를 표현한다. 발을 추가하는 것을 어떻게 다룰 것인가? Softimage 3D 에서, 발목은 실제로는 두 개이다: 다리 체인의 끝과 발 체인의 시작이다. 이 두개를 같이 넣으려면 당신은 발 체인을 다리 체인의 엔드 이펙터의 아래로 parenting 하거나 "제약"을 사용해야 한다. 제약에 대해서는 나중에 다루도록 하겠다. 두 개의 링크 다음에 IK 를 사용해 제어하는 것이 왜 어려운지에 대해서 이야기해 보자.

엄격히 말하자면, IK 에 의해 제어되는 체인은 체인의 가장 아래쪽에 있는 링크나 관절에 의해서 제어된다. 그 바닥 관절이나 엔드 이펙터의 모든 움직임은 계층구조상 최상위까지에 있는 모든 본들을 조금씩 회전시키게 된다.

두 개의 다리 본( 허벅지와 종아리 )으로 구성된 체인을 고려해 보자. 여기에서 발목은 바닥 관절이고 엔드 이펙터이다. 발목을 밀면 그 결과로 무릎이 구부려지고 허리에서 허벅지가 회전한다. 매우 직관적인 모션이다. 여기에다가 다른 링크를 추가하자: 발을 위한 본. 이번에는 발의 볼에 있는 엔드 이펙터를 밀어 보자. 그러면 발목이 구부려지고 무릎이 구부려지고 허리에서 허벅지가 회전한다. 그러나 각 관절이 구부려지는 순서와 각각이 회전하는 양이 약간의 조절만으로도 크게 달라진다. 이는 설정을 제어하기 어렵게 만든다( 그림 7 참조 ).

그림 7. 본이 많아질 수록 변형이 더 부드러워지기는 하지만, 그 본들에 대한 실제 IK 제어는 2 개의 링크를 넘어 가지 않는 체인으로 분리하는 것이 최선이다. 가장 왼쪽의 설정( 보라색 화살표 )은 Softimage 3D 에서 two-link 다리 체인에 대해 제출된 one-link 발 체인을 가지고 있다. 이 설정은 발목에 대해 하나의 엔드 이펙터를 제공하고, 발가락에 대해 다른 엔드 이펙터를 제공한다. 이는 three-link 체인에 대해 하나의 엔드 이펙터만을 사용하는 것보다 좋다.  일반적으로 IK 에서, 더 많은 본을 사용하는 것은 더 적은 제어를 한다는 것을 의미한다.

얼마나 직관적인가. 두 개의 본을 사용해서 쉽게 제어되는 모션은 세 개 이상의 본을 사용하게 되면 완전히 망가지게 된다. 이것이 Softimage 3D 스켈레탈 설정에서 많은 체인들이 서로 parenting 되거나 제약을 가지게 되는 현상을 보게 되는 하나의 이유이다. 당신의 소프트웨어에서 IK 솔루션들을 고려해야 하는 부분이 여기이다. 그것이 요구하는 제약과 parenting 을 창조적으로 사용함에도 불구하고, Softimage 3D 는 3D figure 애니메이션을 위한 확고한( solid ) IK 솔루션을 제공한다.

다른 패키지들은 다른 솔루션들을 제공한다. Maya 와 Mirai 는 허리에서 발가락까지 완전한 뼈대를 생성하는 기능을 제공한다( 그림 8 참조 ). Maya 는 체인들 자체에 배치된 분리된 "솔버( solver )" 들을 사용함으로써 긴 체인들의 예측불가성을 제어한다. 애니메이터는 필요한 곳에 솔버를 배치함으로써 솔버의 영향이 미치는 범위( 시작과 끝 )를 선언한다. 팔을 제어하기 쉽게 만들기 위해, 어깨에서 손목까지 솔버를 늘릴 수 있다. 손목에서 중지의 시작부분까지 솔버를 배치할 수도 있다. 손과 팔의 애니메이션은 각 솔버를 개별적으로 조작하는 것을 포함한다.

Maya 는 "스플라인( spline )" 솔버라는 특별한 솔버를 제공해 긴 목을 가진 생명체를 애니메이션할 수 있도록 하기도 한다. 이 솔버를 사용하면, 커브( 스플라인 )이 목의 척추뼈를 관통해 그려진다. 커브가 수정될 때마다, 척추뼈는 커브의 모양을 고려해 회전한다 - 해양 생물체를 위한 굉장한 솔루션이다.

IZWare( 공식적으로는 Nichimen ) 애니메이션 소프트웨어는 Walt Disney 의 Tron 을 만들 때부터 막후에서 사용되어 왔다. 그리고 이는 그것의 polygonal modeling package 로 유명하다. IZWare Mirai, a newcomer on the "off-the-shelf" animation package scene, helps beginning character animators get up and animating in no time( 역주 : IZWare Mirai 는 초보들이 시작하기 졶은 도구라는 의미인듯 ). The is because IZWare Technologies has done so much work up front( 역주 : 선불이 아니라는 의미인듯 ). Mirai 는 Maya 에서 처럼 완전한 branching skeletons 를 제공할 뿐만 아니라, 많은 캐릭터 솔루션들에 완벽히 걸맞는 이미 만들어진 뼈대들을 제공하기도 한다( 인간, 개, 심지어는 진드기도 ).

IZWare 는 매우 많은 공식( expressions )들과 팔다리 움직임을 자동으로 미러링( 혹은 뒤집기, mirroring or opposing )하기 위한 캐릭터 제어들을 추가함으로써 테크니컬 디렉터들의 두통을 해소해 주기도 한다. 이러한 움직임들의 예를 들면 걷거나 뛰는 사이클에서 팔과 다리를 흔드는 것을 뒤집는( 한 팔은 앞으로 한 팔은 뒤로 ) 것과 팔을 드는 컨덕터( conductor ) 등이 있다. 당신은 한 팔과 다리만 애니메이션시키고, 그 다음에 반대 팔다리를 자동으로 애니메이션시킬지 말지만 결정하면 된다. 이는 다른 프로그램들에서 스켈레톤들을 절반만 생성한 후에 거울면으로 복사( mirror-copied )하면 발생하는 음의 방향 회전( negative-rotation ) 문제도 교정해 준다.

그림 8. Mirai 에서 이미 만들어진 모델과 뼈대.소년, 개, 그리고 엄청 큰 진드기! 
자동 미러링과 음의 방향 회전 문제를 해결.

Dealing with IK Constraints

자, 이제 뼈대를 만들고 발을 제어하기 위해서 IK 를 사용하고 바닥에 발이 닿도록 했다. 손에도 IK 를 적용했다. 캐릭터가 앞으로 걷게되면 팔에 어떤 일이 벌어지는지 확인해 보자( 그림 9 참조 ).

그림 9. IK 에서 엔드 이펙터를 위한 위치들은 ( 단순한 계층 구조에서 처럼 ) 부모 공간의 위치에 대한 참조가 아니라 월드 공간에서 keyframed 되었다. 이는 실제로 IK 를 사용한 발이 쉽게 땅에 붙게 만드는 요인이다 - but it doesn't work well for wrist positions, which need to relate back to the skeleton( 역주 : 손목은 상대 위치여야 한다는 의미인듯 ). 이를 쉽게 해결하는 방법은 손목 엔드 이펙터를 null 오브젝트나 로케이터( locator )를 사용해 제약하는 것이다( 오른쪽 그림에서 십자 표시 ). 그리고 그 로케이터들을 계층 구조 내부로 다시 parenting 하는 것이다( 역주 : 월드공간에서 위치잡고 다시 그것을 부모 공간으로 돌리라는 의미인듯 ).

여기가 제약이 발생하는 곳이다. 엔드 이펙터를 keyframe 하는 것은 별로 좋은 생각이 아니라는 것이 밝혀졌다. 그렇게 하는 것은 실제로는 IK 를 사용할 때 발견할 수 있는 대부분의 문제를 발생시키며, 당신이 고민해서 만든 훌륭한 움직임들을 수행하는 것을 방해할 수 있다.

제약은 의지에 의해서 껐다 켰다 할 수 있는 강력한 자성이라고 설명하는 것이 최선일 것이다. 그것들은 하나의 오브젝트( 심지어는 null 오브젝트라도 )가 다른 오브젝트들에 영향을 미치도록 만든다. 서로 다른 제약들은 서로 다른 일을 수행할 수 있다. 제약은 거의 대부분 오브젝트의 중심이나 피봇에 대해서 작동하는데, 이는 오브젝트의 중심이나 피봇의 배치를 매우 중요하게 만든다. 어떤 패키지들은 다른 것들보다 더 많은 제약들을 포함하고 있지만, 세 개의 기본 제약들이 핵심이다:

• Aim or directional.
• Orientation.
• Point or positional.

Aim or Directional

Aim 혹은 Directional 제약은 "영향을 받는" 오브젝트가 "대상" 오브젝트의 중심이나 피봇에서 지속적으로 어떤 축( 어떤 패키지들은 그것을 당신이 선택하도록 함 )을 바라보도록 만든다. 영향을 받는 오브젝트의 오리엔테이션은 대상 오브젝트의 오리엔테이션과 일치한다.

Orientation

Orientation 제약은 싱크로나이징을 하는 선수와 비슷하다. 한 선수가 돌면, 다른 선수도 돈다. 영향을 받는 오브젝트의 중심 오리엔테이션은 대상 오브젝트의 오리엔테이션과 일치한다.

Point or Positional

Point 혹은 positional 제약은 IK 를 위해 가장 자주 사용된다. 이 제약은 한 오브젝트를 직접적으로 다른 오브젝트에 가져다 붙이는데, 각각의 중심 위치에 맞춘다. 한 오브젝트가 움직이면, 다른 것도 강제로 움직여진다.

제약 대상으로 사용되는 오브젝트들은 다른 오브젝트들의 부모일 수도 있는데, 이는 그것들이 기본 계층 구조의 룰을 따른다는 것을 의미한다. 계층 구조에서 그것들의 위치와 움직임은 부모에 대해 상대적이다.

The Apple-picking Problem

제약은 그림 9 에서 내 뼈대의 손이 뒤로 회전하는 이유를 제공한다. 이는 스켈레탈 계층 구조와 기본 오브젝트 혹은 지오메트리 계층구조 사이의 중요한 차이들 중 하나 때문이다. 이는 성공적인 IK 애니메이션이 보통 두 종류의 계층 구조를 포함하고 있는 이유이기도 하다. 계층 구조에서 몇 개의 오브젝트들의 예로 비행 편대를 들어 보자. 이 비행 편대에는 부모로 선도기( lead plane )가 있다. 만약 한 비행기가 그룹보다 높거나 낮게 날도록 하자고 결정했다면, 우리는 움직임을 keyframe 할 수 있으며, 그것은 교묘하게 움직이면서 계속해서 그룹과 함께 날것이다. 이는 그것의 움직임이 부모 오브젝트인 선도기의 움직임에 대해 상대적이기 때문이다.

기본 계층 구조에서, 자식의 위치는 자식의 부모의 위치에 대해 상대적이다. That's why the feet slide when a character held together solely by hierarchies ( without bones ) rotates his or her hips( 역주 : 순운동학에서는 발이 땅에 닿지 않고 끌리는 것을 의미하는듯 ).

역운동학에서는 그렇지 않다. 엔드 이펙터( IK 계층 구조에서 가장 아래의 자식 )의 위치는 월드 공간에 대해 상대적이다. 그것이 IK 를 사용해서 애니메이션된 발이 그대로 남아 있는 이유이다. 불행히도 이는 IK 를 사용해서 애니메이션된 손들이 그것이 keyframe 된 공간의 위치에 도달하지 못하는 이유이기도 하다.

IK 는 발 배치를 위해서는 자연스럽다. 하지만 캐릭터가 사과를 집을 때는 어떨까? 그 액션은 IK 를 사용해서 하는 것보다 쉽지 않은가? 그렇다. 그것은 기본 계층 구조와 제약들의 도움을 받으면 최상이다.

우리는 어깨를 회전시키고 나서 위쪽 팔을 회전시키고 나서 아래쪽 팔을 회전시키는 등의 행동을 하는 것보다 사과에 손을 배치하는 것이 더 쉽기 때문에 IK 를 사용하기를 원한다. 하지만 우리는 캐릭터의 손이 등 뒤로 넘어 가지 않고 사과 나무로 올라 가는 것을 원한다. 어떻게 해야 할까?

The Apple-picking Solution

우리는 IK point 제약을 기본 계층구조와 함께 사용한다:

• 
  
• 정사각형과 원인 두 오브젝트를 선택하는 것이 좋다. 왜냐하면 그것들은 스플라인일 뿐이고 렌더링되지 않을 것이기 때문에, 나중에 그것을 감추기 위해서 기억할 필요가 없다. 우리는 원을 사용할 것이다.
• 원 하나를 ( 팔 체인의 엔드 이펙터인 ) 손목에 배치한다. 그리고 다른 원 하나를 다른 손목에 배치한다. If you're really into it, point 제약을 사용해서 원들을 손목들에 직접 연결하고 그 제약들을 꺼 둔다. 
• 그 원들을 캐릭터 몸통의 자식으로 만들어라( 몸통에 grouping 하거나 parenting 한다 ). 이는 그것들이 몸통이 가는 곳을 따라 가고 원들의 모든 움직임들은 몸통에 대해 상대적임을 의미한다. 이제 손목 엔드 이펙터들을 각각의 원들에 대해 제약한다. 이 아이디어는 엔드 이펙터가 아니라 제약 오브젝트들을 keframe 하는 것이다.

최종 결과는 두 세계에 있어 최상이다: 손들은 캐릭터가 움직일 때 몸통을 따라서 움직이게 되고, 당신이 제약을 가진 원을 사과에 배치할 때 손은 그것을 따라 간다. 이는 당신에게 IK 의 이점을 제공한다.

IK-driven 뼈대를 개선하기 위해서 제약 오브젝트의 계층 구조를 사용하는 것은 캐릭터 애니메이션 문제를 95% 정도 해결해줄 것이다. Everything from two characters playing catch to a rider falling from or jumping up onto a horse can be done with some form of animated constraint hierarchies and IK( 역주 : IK 와 애니메이션되는 제약 계층구조를 사용하면 말에서 떨어지거나 뛰는 행위들에 대한 문제들도 해결할 수 있다는 의미인듯 ). With the addition or a little math in the form of expressions to control complex behaviors like foot rotation, you'll have the tools you need to handle just about anything.

Conclusion

자 로봇의 전원을 끄고 방어구만으로 구성된 캐릭터는 벽에 걸어 두자. 그리고 이제는 서피스 변형을 해 보자. 우리는 계층 구조, 역운동학 대 순운동학, 그리고 그것들을 제공하는 주요 애니메이션 패키지들에 대해서 다뤘다. 또한 IK 와 제약을 사용하여 일반적인 애니메이션 문제들도 해결했다.

이제 당신만의 것을 경험하는 것은 당신에게 달렸다. 먼저 엔진이 IK 와 제약 계층 구조를 지원하는지 확인하고, 그것들을 해 보라. 이 문서에서 언급되지 않은 3D 소프트웨어 패키지라고 할지라도, 가격과 상관없이 IK 시스템, 계층 구조, 어떤 종류의 제약 혹은 링크들은 가지고 있음을 기억하라. 어떤 것을 얻을 수 있는지 확인해 보고 나가서 움직여라!

For More Information

아래의 리스트에서, 당신은 앞에서 언급한 소프트웨어 패키지와 도구들에 대한 URL 들을 찾을 수 있다. 또한  Intel® Software Directory and Software Download Store 를 확인해서 도구들과 솔루션들의 리스트들을 찾아보기를 원할 것이다.

• Maya* evolved from Alias Power Animator* and Wavefront Explorer*, and is now owned byAutoDesk*, along with Discreet's 3d Studio Max*
• Hash Animation: Master*
• Smoother Animation with Intel® Pentium® III Processors (NURBS models)
• Softimage 3D and XSI*

About the Author

A professional animator and technical marketing engineer for Intel Corporation, Steve Pitzel has been a computer graphics instructor and animator for six years. He began his graphic arts career in college as an editorial cartoonist and courtroom sketch artist. After converting from pencil to mouse, he went on to convert others, teaching 3D applications such as Softimage, PowerAnimator, and Maya to traditional cell animators and computer graphic artists for Disney Feature Animation, Sony Pictures Imageworks, VIFX/Rhythm & Hues and UCLA. He was a lead animator for the CBS feature, The Nuttiest Nutcracker*, and a senior artist for Mattel. 

When he isn't animating, he's usually writing. His first novel, Wizrd, was published by St. Martin's Press in 1994 under his pen name, Steve Zell. He is currently working on his second novel.

[ 게임 개발자를 위한 물리, 2판 ] 책의 45 페이지에서 질량중심에 대해서 다음과 같이 설명하고 있습니다.

1차 모멘트를 계산하는 방법은 각 좌표축마다 원점으로부터 질량중심까지의 거리를 구한 뒤, 그 결괏값을 질량에 곱하면 됩니다.

이것 때문에 한참 헤맸네요. 일단 질량중심 구하는 식에서 "질량중심까지의 거리"를 구하라고 하는 것부터가 넌센스네요. 적절한 설명이 되려면 다음과 같아야 합니다.

1차 모멘트를 계산하는 방법은 각 좌표축마다 원점으로부터 각 원소의 질량중심까지의 거리를 구한 뒤, 그 결과를 각 원소의 질량에 곱하면 됩니다.

주의 : 공부하면서 정리한 것이라서 잘못된 내용이 있을 수 있습니다.

주의 : 이 글은 위키피디아의 모멘트를 주요 레퍼런스로 하여 작성되었습니다. 내용이 이상하면 원문을 참조하세요.

모티브

제가 물리 공부를 하다가 제일 먼저 접하게 된 헷갈리는 개념은 모멘트( moment )였습니다. [ 게임 개발자를 위한 물리 ] 같은 책에서는 질량관성모멘트( mass moment of interia )를 구하겠다면서, 뜬금없이 "질량계", "점질량", "1차 모멘트", "2차 모멘트" 등에 대한 별다른 설명없이, 그냥 계산식을 내 놓습니다. 고등학교 물리 정도는 대충 이해한 독자를 대상으로 한다고 서문에 써져 있기는 했지만, 저는 고등학교 졸업한지 20 년이 지난지라 이해할 수 없더군요.

하여간 검색해 보니, 대부분의 사람들은 추상적으로 계산 과정에 대해서만 다루고 모멘트 자체의 의미에 대해서는 설명하지 않더군요. 심지어는 모멘트와 모멘텀( momentum, 운동량 )에 대해서 헷갈리는 사람들도 있구요, "토크가 모멘트다"라고 하는 사람들도 있더군요. 그래서 이번 기회에 저와 같이 모멘트가 뭔지 모르는 사람들을 위해서 개념을 정리해 봐야겠다는 생각을 했습니다.

모멘트의 개념

위키피디아의 정의에 의하면 모멘트는 다음과 같습니다.

물리에서, 모멘트는 물리량( physical quantity )와 거리의 조합이다. 모멘트는 보통 기준( reference point )이나 축( axis )에 대해 정의된다; 모멘트는 물리량을 기준이나 축으로부터 일정 거리를 가진 것으로서 다룬다. 예를 들어 힘의 모멘트( moment of force )는 힘과 어떤 축으로부터의 거리의 곱인데, 이는 그 축에 대한 회전을 산출한다. 기본적으로 모멘트를 생성하기 위해서 어떤 물리량이라도 거리와 곱해질 수 있다; 보통 물리량은 힘( force ), 질량( mass ), electric charge distribution 이 사용된다.

 

- 출처 : Moment (Physics), Wikipedia.

간단하게 정리하자면, 모멘트는 어떤 기준에 대한 "거리 X 물리량" 을 의미합니다. 마치 내적( dot product )이나 외적( cross product )과 같은 개념이라고 생각하시면 됩니다. 일종의 함수라고 생각해야 한다고 할까나요? 내적과 외적은 수학적으로 보면 두 벡터를 곱하고 더하는 순서를 의미할 뿐입니다. 하지만 각각은 기하학적인 관점에서 보면 다른 의미를 가지고 있습니다. 마찬가지로 모멘트도 특정 상황에서 실질적인 의미를 가진다고 보시면 됩니다.

모멘트의 일반적인 표현식은 다음과 같습니다. 하지만 반드시 아래와 같은 형태인 것은 아닙니다. 왜냐하면 거리와 물리량의 조합이라는 것이 반드시 스칼라 곱을 의미하는 것은 아니기 때문입니다.

여기에서 Q 는 물리량( physical quantity )이고, r 은 거리입니다. 그런데 거리라는 것은 단순한 스칼라가 아니라 벡터일 수 있습니다. n 은 차수이구요. 만약 n = 1 이면 1차 모멘트라고 하고, n = 2 이면 2차 모멘트라고 합니다.

만약 물리량이 단일 점에 국한된 것이 아니라면 모멘트는 공간에서의 물리량들의 밀도에 대한 적분입니다.

여기에서 ρ 는 밀도입니다.

현재 시점에서는 내적이나 외적같이 그냥 공식으로서의 의미만 가지고 있습니다. 이제 이 모멘트가 어떤 식으로 사용되는지 한 가지 예를 들어 보도록 하겠습니다.

Torque

모멘트가 가장 단순한 형태로 사용되는 것은 토크( torque )입니다. 우리말로는 돌림힘이라고 합니다.

토크는 moment of force 를 의미하는데, 일반적으로 줄여서 그냥 moment 라고 하기도 한다고 합니다. 그래서 "토크가 모멘트다" 라는 말은 틀렸다고는 할 수 없지만, 엄밀한 정의를 생각하면 사용하지 않는 것이 낫지 않나라는 생각을 해 봅니다. 예를 들어 단위 벡터 A 와 어떤 벡터 B가 있을 때 A 와 B 를 내적하면, 그 결과는 B 를 A 에 사영한 길이가 나옵니다. 그렇다고 해서 내적의 정의를 "A 와 B 가 있을 때, B 를 A 에 사영한 길이이다" 라고 할 수는 없는 것이지 않겠습니까. 특수한 상황이고 자주 사용되는 상황이라고 해서 그냥 정의를 혼용해서 쓰는 것은 혼란을 가중시킨다고 생각합니다.

어쨌든 토크는 어떤 축( axis ), 받침점( fulcrum ), 중심( pivot )에 대해서 회전하게 하는 힘의 경향( tendency )를 의미합니다. 수학적으로 볼 때 토크는 힘이 적용되고 있는 점에 대한 위치 벡터와 회전을 유발하는 힘 벡터간의 외적입니다.

위의 식을 보면 거리 벡터와 힘 벡터의 조합임을 확인할 수 있습니다.

결론

모멘트는 거리와 물리량의 조합으로서, 다양한 물리량을 표현하기 위해서 사용됩니다. 그것의 활용예는 다양합니다. 위키피디아의 모멘트 항목의 See also 를 참조하시기 바랍니다.

추가 : [ http://contents.kocw.net/KOCW/document/2015/kumoh/ohchungseok/8.pdf ] 에 따르면 모멘트를 다음과 같이 정의하더군요.