Computing Derivatives
직관적인 방법으로 Perlin noise method를 설명하는 책과 웹의 문서들이 거의 없다; 그러나 Perlin noise derivatives를 어떻게 연산하는지에 대한 정보를 찾는 것은 심지어 더 어렵다 (특히, analytical 방법으로). 이러한 derivatives가 무엇인지 모르고 그것이 왜 유용한지 모르는 사람들에게, derivatives를 빠르게 봐보자.
A Quick Introduction to (Partial) Derivatives
어떤 함수의 Derivatives(도함수) (그것이 1, 2, 3 차원의 함수이든), 매우 유용하다. 그러나 우리가 예제를 주기전에, 처음에 그것들이 무엇인지 한 번 봐보자. 만약 너가 2D noise의 한 image를 만들고, 그 이미지의 top위에 어떤 regular grid를 적용한다면, 그러면 우리는 그 noise function이 x와 y 방향을 따라 그리드의 각 점에서 얼마나 변하는지를 알기를 원할지도 모른다 (그림1). 아마도 이 아이디어는 벌써 친숙하게 들리지 않는가? 이전 챕터에서, 우리가 한 mesh를 옮기기 위해 2D noise function의 결과를 사용했다는 것을 기억해라. 그러나, 우리가 여기에서 얻으려고하는 것으로 돌아가보자: 어떻게 x축과 y축을 따라서 우리의 2D noise function의 변화율을 알 수 있는가? 이 문제에 대한 갇난한 솔루셔은 그 점에서 noise 값을 취하는 것으로 구성되는데, 그 점에서, 너는 이 변화를 연산하길 원한다 (이 점은 Gn_x라고 부르자), 그리고 Gn_x의 한 칸 옆에 있는 점의 noise value를 취하고 (이것을 두 번쨰 점Gn_x+1 이라고 부르자), 그리고 두 번째 값을 첫 번째 것으로 부터 뺀다. 예를들어, 만약 Gn_11에 있는 noise가 0.1과 같고, 그 Gn_12에 있는 noise value가 0.7이라면, 그러면 우리는 noise가 Gn_11에서 Gn_12로 (x축을 따라) 0.6만큼 변했다고 가정할 수 있다 (그림1). 방정식의 형태로, 우리는 다음을 쓸 수 있다:
물른 y축을 따라 변화율을 연산하기 위해서, 우리는 같은 것을 할 것이지만, 아래로 내려가야 할 것이다. 우리의 방정식을 다음처럼 보일 것이다
기술적으로, 이 차이를 normalize하는 것이 최고인데, 우리가 grids들에 있는 두 점을 분리하는 거리에 상관없이 일관된 결과를 얻로록 하기위해서 이다 (만약 그 결과가 normalized 되어있따면, 다른 grid spacing으로 만들어진 measurements가 그러고나서 서로서로 비교되어질 수 있다). 이 결과를 normalize하기 위해서, 우리는 G_11과 G_12사이의 거리로 그 차이를 나눌 필요가 있다. 그래서 만약 grid에 있는 두 점 사이의 거리가 예를들어 2라고 하면, 그러면 우리는 다음을 쓸 수 있다:
수학에서, 이 기법은 forward difference라고 불려진다. 왜냐하면 우리가 다음 연산될 점을 취하고, 다음 점의 값으로 부터 현재의 점에 있는 값을 빼기 때문에 forward라고 한다.
Backward differencing은 또한 가능하다: 너는 당므 점 대신에 이전 점을 사용한다. 너는 또한 central difference를 사용할 수 있다.
수학적으로, 우리는 이 개념을 다음의 방정식으로 공식화한다:
f'(x) 표기는 이것이 f(x)함수의 도함수라는 것을 의미한다.
이것은 우리가 그 함수 f(x)의 도함수를 우리가 방금 소개했던 forward difference 기법을 사용하여 연산할 수 있다는 것을 의미한다. 그러나 이 도함수 값이 두 점 사이의 거리가 더 작아질 수록 (이론 상으로 h가 0을 향한다면) 더 정확해진다는 것도 의미한다. 그 spacing(간격)이 클 때, 너는 주어진 점 x에서 도함수 값에 대해 어느정도 매우 조잡한 값을 얻게 된다. 그러나 그 spacing이 작아질 수록, 이 근사는 향상된다. 우리의 noise image의 경우에, 그 grid의 spacing은 꽤 크다. 그래서 사실, 너는 만약 그 grid spacing이 더 작다면 (그림2), grid의 각 점에서 noise function의 변화에 대한 더욱 좋은 근사를 얻을 것이다.
이 개념은 1D example로 더 쉽게 이해된다. 그림 3은 1차원 함수의 profile을 보여준다. 우리가 이제 이 함수가 P의 proximity(가까움) 내에서 얼마나 변하는지를 알길 원한다고 가정하자. forward differencing의 원리를 사용해서, 우리는 example x1과 같은 x축을 따라 한 점을 취할 수 있고, 그 점에서 그 함수의 값을 연산하고, 그래소 f(x1) 를 f(x)로 뺀다. 우리가 f(x0에서 f(x1)으로 가는 한 line을 따라 갈 때, 그 line은 x에서 그 함수에 tangent이다. 그것은 왜냐하면 사실 1차원 함수의 도함수는 그 함수에 대해 접선인 직선의 기울기(slope)를 준다. 그 함수에서, 그 함수의 도함수가 연산된다. 그래서 우리는 어떻게 기하학적으로 한 함수의 도함수를 해석할지를 알았으니, 너는 쉽게 만약 우리가 x1보다 더 먼 점을 취한다면, 예를들어 x2, 그러면 x와 x2 사이의 그 직선이 x에 x-x1보다 접선이지 않다는 것을 알 수 있다. 결론으로, 만약 너가 한 함수의 도함수를 연산하기 위해 forward difference를 사용한다면, 그러면 x와 x+h사이의 거리가 더 작을수록 더 좋다.
우리가 이제까지 무엇을 배웠는가?
- 우리는 일차원 함수 f(x)의 도함수 f'(x)가 x에서 f(x)의 접하는 line의 slope로서 해석될 수 있다는 것을 배웠다.
그 기울기 외에도, 도함수 f'(x)는 또한 x에서 함수 f(x)의 instantaneous 변화율로 고려될 수 있다.
- 우리는 또한 그 기울기의 "근사"를 연산하기 위해 우리가 forward difference라고 불리는 기법을 (일반적인 방법은 finite difference라고 불려진다) 사용할 수 있다는 것을 배웠다. 뿐만 아니라, 이 근사가 forward difference 방정식에서 h가 더 작아질수록 더 좋아진다고 배웠다.
우리가 어떻게 이 챕터의 나중에서 도함수를 사용할지 (실제로 편미분)에 대해 이해하기 위해서 이해해야할 정말 중요한 것이 있다. 지금까지, 우리는 한 함수의 도함수가 x의 어떤 값에서 함수 f(x)의 slope로서 해석될 수 있다고 설명했다. 우리가 x에서 (우리가 함수 f(x)의 도함수를 연산하는 곳) 그 접선을 추적하는 방식은 간단히 그 함수의 점에서 y = mx의 직선을 그리는 것인데, 그 함수에서, 우리는 그 함수의 도함수를 연산했다. 그 m 값은 여기에서 물론 우리가 연산한 함수의 slope이다. 왜 이것이 중요한가? x = 1일 때 y = m이라는 것을 주목해라. 이것은 이 관찰을 사용해서, 우리가 그 점에서 곡선의 2D vector tangent가 Vec2f(1, m)과 같다고 말할 수 있다. 너는 동의 하는가? 물론, 그러고나서 너는 이 벡터를 표준화 할 필요가 있지만, 그럼에도 불구하고, 이 벡터가 그 점에 어떻게 접하는지를 주목해라. 이 아이디어를 이해하는 것이 중요하다 (그림 4에서 보여지는).
너는 3D perlin noise function을 서로에 수직인 2개의 2D functions이라고 볼 수 있다. 그래서 만약 원한다면, xy 평면에서 2D function의 도함수를 연산하는 1D function을 가질 것이고, yz 평면에서 2D noise function의 도함수를 연산하는 또 다른 1D function을 가질 것이다. 그림 5에서 보여지듯이. 이제 만약 우리가 이러한 함수들의 각각에서 접선을 연산하기 위해서 배웠던 기법을 적용한다면, 두 개의 얻어진 접선들이 서로에 수직하다는 것에 주목해라. 그러나 좀 더 흥미롭게도, 이러한 두 벡터의 외적을 취해서, 너는 2D noise function이 원래 연산되는 그 점에 접하는 평면에 수직인 벡터를 얻게된다. 이 벡터가 P에서 우리의 함수의 normal이다. 바라건데, 너가 그것을 이해하기 시작하기 바란다. 이러한 도함수들은 3D or 2D noise function으로 옮겨진 우리의 mesh의 normals를 연산하는데 유용할 것이다.
이것은 중요한 결과인데, 왜냐하면 이것은 우리가 3D noise function에 의해 옮겨진 한 mesh의 normal를 어떻게 연산할지에 대한 방법이기 때문이다. 우리는 어떤 주어진 점 (가령 P)에서 그 함수의 도함수를 evaluate할 것이고, 그러고나서 그 x축을 따라서 P에 접하는 벡터를 연산할 것이다 (이 벡터를 T_x라고 하자). 그러고나서 우리는 P에서 그 z축을 따라서 noise function의 도함수를 연산할 것이다. 그러고나서, z축을 따라서 P에 접선을 연산할 것이다 (이것을 T_z라고 부르자). 마지막으로 우리는 P에서의 normal를 구하기 위해서 외적에서 그 두 벡터들을 사용할 것이다:
이것은 간단하고 우아하다. 이제 한 가지 말할 것과 질문이 있다.
Remark : 우리가 여기에서 noise function의 도함수를 정말로 연산하지 않는다느 ㄴ것에 주목해라. 우리는 어느정도 x축을 따라서 그 함수의 도함수를 연산하고 그러고나서 z축을 따라서 또 다른 도함수를 연산하여 cheat를 한다. 흥미로운 것은, 우리가 그것을 할 때, 그 양의 오직 하나만이 변한다. 예를들어, x축을 따라서 3D noise function의 도함수를 연산할 때, 물론 우리가 얻는 값은 z축을 따라서 그 값의 변화 때문에 변하지 않는다 ( 왜냐하면 우리는 xy 평면에서 그 noise function을 evalutate하기 때문이다 - z에서 어떠한 변화도 없다고 알려져있듯이). 수학에서, 너가 몇 가지 변수가 있는 함수를 가질 때, 그러나 너가 그것의 변수들 중 하나로만 관련하여 그것의 도함수를 연산할 때, 다른 것들은 상수로 고정되고, 그러면 우리는 그 함수의 partial derivatives를 연산한다고 말한다. 예제를들어 보자. 만약 너가 다음의 함수를 가지고 있다면:
그러고나서 만약 너가 y를 상수로 유지하면서 그 함수의 도함수를 연산하길 원한다면, 너는 다음을 얻는다:
너는 그 함수를 x와 관련된 f(x,y)의 편도함수라고 읽을 수 있다. 다시 말해서, 우리는 우리의 예제에서 y^2 같은 x가 나타나지 않느 항들을 모든 항들을 무시하는데, 그러고나서 x가 나타나는 각 항에 대해 x의 도함수를 연산한다. 예를들어, 만약 그 항들 중 하나에서, 우리가 x^2y를 가지고 있다면, 우리는 그 편도함수에서 그것을 2xy로 바꾼다. 만약 우리가 xy를 가진다면, 우리는 그 항을 편도함수에서 y로 바꾼다. 간단하지 않은가?
질문: 우리는 이러한 편도함수들을 어떻게 계산하는가?
한 방법은 forward difference technique을 사용하는 것으로 구성된다 (그리고 이것이 우리가 이 챕터의 초기에 그것에 대해 배운 이유이다). 만약 우리가 우리의 옮겨진 메쉬들의 예제를 가지고 온다면, 그러면 우리는 vertex V_x+1,x에서 noise value의 도함수를 Vx,z정점의 noisevalue로부터 빼서 vertex Vx,z에서 그 도함수를 연산할 수 있다 (그림 6). 다시 말해서, 우리는 다음으로 쓸 수 있다:
그 질문은 이제, 우리가 이 실수 값을 어떻게 벡터로 (도함수가 x와 z축을 따라 연산되는 점에서의 noise function에 접하는 vector) 변환하는가 이다. 이것은 간단하다. 우리가 x축을 따라서 편도함수를 연산할 때, xy 평면에서 작업한다는 것을 깅거해라. 따라서, 그 x축을 따라가는 noise function에 접하는 벡터의 z좌표는 반드시 0이다:
T_x = {?, ?, 0}.
다른 두 좌표들을 연산하기 위해서, 너는 다시 그림 4를 볼 필요가 있다. 거기에서 우리는 한 평면에서 그 함수의 접선을 연산하기 위해서, 너는 x 좌표를 1로 설정하고 그 벡터의 y좌표를 편도함수 값으로 설정할 필요가 있다 (만약 너가 yz평면에서 그 벡터의 접선을 연산하기 원한다면, 그러면 너는 그 접선으 z좌표를 1로 설정하고, 그 벡터의 y좌표를 z와 관ㄹ녀된 편도함수의 값으로 설정하고, 접선 벡터의 x좌표를 0으로 설정한다). 마지막으로 우리는 다음을 갖는다:
T_x = {1, N_x, 0}
T_z = {0, N_z, 1}.
마지막으로, 그 정점의 normal를 연산하기 위해서, 너가 이제 할 필요가 있는 것은 이러한 두 벡터의 외적을 연산하는 것이다 (그 외적의 결과는 두 개의 input vectors가 표준화 되어 있지 않더라도 올바르다: 그 최종 벡터가 두 개의 입력 벡터에 대해 수직일 것이다, 비록 그것이 자체로 표준화되어있지 않을지라도):
이 기법은 훌륭한 작동하지만 :
- 우리가 grid의 edges에 있는 정점에 대한 도함수를 연산하길 원할 때 처음에 무슨일이 발생하는가? 우리는 할 수 없다.
- 우리느 또한 (그림 3) forward difference를 사용하여 도함수를 연산할 때 두 샘플들 사이의 공간이 더 작을 수록, 그 결과가 더 정확해진다고 설명했었다. 다시 말해서, 그 정점들 사이의 공간이 더 클 수록, 편도함수의 연산은 덜 정확해진다. 이 챕터의 나중에, 우리는 forward difference로 연산된 편도함수와, 우리가 이제 공부할 analytical solution 사이의 차이를 보여줄 것이다.
Analytical Partial Derivatives of the Perlin Noise Function
그래서 이러한 편도함수를 연산하는 더 좋은 방법이 있다. 이 기법은 오직 수학에만 의존하고, "정확한" 솔루션을 제공한다 (그 항의 수학적인 의미에서). quick remider: 다음의 방정식의 편도함수:
x축에 관해서는:
이제 그 Noise function을 조금 다시 써보자. 모든 내적을 문자로 바꿔보자 (아래에 보이듯이):
a = dot(c000, p000)
b = dot(c100, p100)
c = dot(c010, p010)
d = dot(c110, p110)
e = dot(c001, p001)
f = dot(c101, p101)
g = dot(c011, p011)
h = dot(c111, p111)
연습을 위해서, 파라미터들 u,v,w들이 다음과 같이 연산된다는 것을 다시 기억해보자 (우리는 smoothstep function을 사용한다):
u = tx * tx * (3 - 2 * tx)
v = ty * ty * (3 - 2 * ty)
w = tz * tz * (3 - 2 * tz)
이제 Perlin noise function의 다른 interpolations들을 하나의 single line으로 써보자 (첫 번째 챕터를 보라):
lerp(
lerp(
lerp(a, b, u),
lerp(c, d, u),
v)
lerp(
lerp(e, f, u),
lerp(g, h, u),
v),
w)
lerp(a,b,t)의 호출을 실제 코드 (a(1-t) + bt)로 바꿔보자:
((a(1 - u) + bu)(1 - v) + (c(1 - u) + du)v)(1 - w) +
((e(1 - u) + fu)(1 - v) + (g(1 - u) + hu)v)w
((a - au + bu)(1 - v) + (c - cu + du)v)(1 - w) +
((e - eu + fu)(1 - v) + (g - gu + hu)v)w
(a - au + bu - av + auv - buv + cv - cuv + duv)(1 - w) +
(e - eu + fu - ev + euv - fuv + gv - guv + huv)w
a - au + bu - av + auv - buv + cv - cuv + duv -
aw + auw - buw + avw - auvw + buvw - cvw + cuvw - duvw +
ew - euw + fuw - evw + euvw - fuvw + gvw - guvw + huvw
그러고나서 마지막으로 그 항들을 다음과 같이 묶어보자:
a + u(b - a) + v(c - a) + w(e - a) +
uv(a + d - b - c) + uw(a + f - b - e) + vw(a + g - c - e) +
uvw(b + c + e + h - a - d - f - g)
너도 볼 수 있듯이 (그리고 예ㅊ측되듯이) 이것은 세 함수들의 한 함수이다 :u ,v 그리고 w. 만약 우리가 변수들 중의 하나와 관련하여 한 함수의 편도함수를 연산하기 위해 배웠떤 기법을 적용한다면, 우리는 궁금한 변수를 포함하지 않는 모든항을 제거할 필요가 있고, 나머지 항에서 그 변수를 그것의 도함수로 대체 한다. 예를들어, 만약 우리가 u와 관련하여 noise function 편도함수를 연산하길 원한다면 우리는 다음을 얻는다:
u'(b - a) +
u'v(a + d - b - c) + u'w(a + f - b - e) +
u'vw(b + c + e + h - a - d - f - g)
u'((b - a) + v(a + d - b - c) + w(a + f - b - e) + vw(b + c + e + h - a - d - f - g))
유사하게, v와 w와 과련된 편도함수들은:
// partial derivative with respect to v
v'(c - a) +
uv'(a + d - b - c) + v'w(a + g - c - e) +
uv'w(b + c + e + h - a - d - f - g)
v'((c - a) + u(a + d - b - c) + w(a + g - c - e) + uw(b + c + e + h - a - d - f - g))
// partial derivative with respect to w
w'(e - a) +
uw'(a + f - b - e) + vw'(a + g - c - e) +
uvw'(b + c + e + h - a - d - f - g)
w'((e - a) + u(a + f - b - e) + v(a + g - c - e) + uv(b + c + e + h - a - d - f - g))
남은 질문은 u', v' 그리고 w'의 도함수가 무엇이냐는 것이다. 간단한 u, v, w는 다음으로 연산된다:
u = 3tx^2 - 2tx^3
v = 3ty^2 - 2ty^3
w = 3tz^2 - 2tz^3
따라서 이러한 함수들의 도함수들은:
u' = 6tx - 6tx^2
v' = 6ty - 6ty^2
w' = 6tz - 6tz^2
해냈다1 너가 이제 필요한 모든 것은 이러한 도함수들을 연산하고, 그러고나서 우리가 여기에서 제공한 기법을 사용하여 그 함수가 evaluated되는 그 점에 접선이 벡터들을 구하는 것이다. 여기에 3D noise function을 evalutes하고 주어진 위치에서 그것의 편도함수를 구하는 eval function의 변경된 버전이 있다:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | float eval(const glm::vec3& p, glm::vec3& derivs) const { int xi0 = ((int)std::floor(p.x)) & tableSizeMask; int yi0 = ((int)std::floor(p.y)) & tableSizeMask; int zi0 = ((int)std::floor(p.z)) & tableSizeMask; int xi1 = (xi0 + 1) & tableSizeMask; int yi1 = (yi0 + 1) & tableSizeMask; int zi1 = (zi0 + 1) & tableSizeMask; // gradients at the corner of the cell const glm::vec3& c000 = gradients[hash(xi0, yi0, zi0)]; const glm::vec3& c100 = gradients[hash(xi1, yi0, zi0)]; const glm::vec3& c010 = gradients[hash(xi0, yi1, zi0)]; const glm::vec3& c110 = gradients[hash(xi1, yi1, zi0)]; const glm::vec3& c001 = gradients[hash(xi0, yi0, zi1)]; const glm::vec3& c101 = gradients[hash(xi1, yi0, zi1)]; const glm::vec3& c011 = gradients[hash(xi0, yi1, zi1)]; const glm::vec3& c111 = gradients[hash(xi1, yi1, zi1)]; float tx = p.x - ((int)std::floor(p.x)); float ty = p.y - ((int)std::floor(p.y)); float tz = p.z - ((int)std::floor(p.z)); // generate vectors going from the grid points to p /*** 18-12-28 Chanhaneg Lee To clear why this code is as it is, if you assume c000 is (0, 0, 0), then the vector from grid points to p is Vector = P - (Grid Point c000). And tx, ty tz is the thing, c000 because p.x - ((int)floor(p.x)) makes it. And the reason x1 is subtracted by 1, such as p100, the coordinate c100 is (1, 0, 0). The equation of calculating the vector P - (Grid Point c100). Therefore, tx should be added by -1 (c100 is added by 1, compared c000) ***/ float x0 = tx, x1 = tx - 1; float y0 = ty, y1 = ty - 1; float z0 = tz, z1 = tz - 1; glm::vec3 p000 = glm::vec3(x0, y0, z0); glm::vec3 p100 = glm::vec3(x1, y0, z0); glm::vec3 p010 = glm::vec3(x0, y1, z0); glm::vec3 p110 = glm::vec3(x1, y1, z0); glm::vec3 p001 = glm::vec3(x0, y0, z1); glm::vec3 p101 = glm::vec3(x1, y0, z1); glm::vec3 p011 = glm::vec3(x0, y1, z1); glm::vec3 p111 = glm::vec3(x1, y1, z1); float u = smoothStep(tx); float v = smoothStep(ty); float w = smoothStep(tz); float a = dot(c000, p000); float b = dot(c100, p100); float c = dot(c010, p010); float d = dot(c110, p110); float e = dot(c001, p001); float f = dot(c101, p101); float g = dot(c011, p011); float h = dot(c111, p111); float k0 = (b - a); float k1 = (c - a); float k2 = (e - a); float k3 = (a + d - b - c); float k4 = (a + f - b - e); float k5 = (a + g - c - e); float k6 = (b + c + e + h - a - d - f - g); float du = smoothstepDeriv(tx); float dv = smoothstepDeriv(ty); float dw = smoothstepDeriv(tz); derivs.x = du * (k0 + v * k3 + w * k4 + v * w * k6); derivs.y = dv * (k1 + u * k3 + w * k5 + u * w * k6); derivs.z = dw * (k2 + u * k4 + v * k5 + u * v * k6); return a + u * k0 + v * k1 + w * k2 + u * v * k3 + u * w * k4 + v * w * k5 + u * v * w * k6; } |
Analytical Solution vs Forward Difference
우리는 이제 그 옮겨진 mesh의 두 개의 버전을 compete할 수 있다. 하나는 그 mesh의 vertex normals를 계싼하기 위해 geometric solution을 사용한 것. 그리고 analytic solution을 사용한 것. 이러한 solutions들 중 하나를 연산하는 코드는 다음과 같다:ㅣ
{
Analytical Normals
Vec3f tangent(1, derivs.x, 0); // tangent
Vec3f bitangent(0, derivs.z, 1); // bitangent
// equivalent to bitangent.cross(tangent)
poly->normals[i] = Vec3f(-derivs.x, 1, -derivs.z);
poly->normals[i].normalize();
Geometry Normal
세점으로 이루어진 삼각형 두 변을 이용하여 외적을 해서 normal
}
여기에 그것들의 연관된 vertex normals가 있는 두 개의 메쉬들의 이미지가 있다 (오른쪽에 보여지는):
vertex normals들이 mesh의 edge에서 정의되지 않았다는 것에 주목해라. 거기에서 normals들이 forward difference method를 사용해서 연산되었다 (geometric solution). 또한 vertex normals의 방향이 상당히 두 메쉬 사이에 다르다는 것에 주목해라 비록 그것들의 모야이 같을지라도). 이것은 명백히 두 개의 메쉬들의 shading이 눈에 띄게 또한 다르게 한다 (normals이 shading에 사용된다는 것을 기억해라).
댓글 없음:
댓글 쓰기