Cubic Bezier
나중에 봐야할 거
Bezier 간략 설명
Bezier 는 Lerp 의 반복임.
점이 A, B 가 있고 0~1 사이의 값인 t 가 있을 때
Lerp(A, B, t) = A * (1-t) + B * t
점이 A, B, C 가 있고 0~1 사이의 값인 t 가 있을 때
Bezier2 = Lerp(Lerp(A, B, t), Lerp(B, C, t), t)
이렇게 볼 수 있음.
점이 3개가 아니라 4개, 5개 등 수없이 많아도 재귀적으로 작업할 수 있음.
Bezier3 = Lerp(Bezier2(A, B, C, t), Bezier2(B, C, D, t), t)
Bezier4 = Lerp(Bezier3(A, B, C, D, t), Bezier3(B, C, D, E, t), t)
이렇게 말임.
Bernstein Basis Polynomials 간략 설명
Bezier 가 재귀함수라서 계산하기가 부하가 조금 있음.
대신 일반항을 사용하려고 하는데 그 때 쓰는 식이 바로 이 식.
n+1 개의 점과 0~1 사이의 값인 t 가 있어서 Bezier 함수의 v 번째의 점에 대한 일반항을 구할 때 ( v 는 [0, n] 의 범위 )
B(n, v, t) = nCv (t^v) * (1-t)^(n-v)
A, B, C, D 가 있고 C 점에 대한 것이면 " 3 * t^2 * (1-t) * C " 이렇게 된단 소리.
(t + (1-t))^n 한 다항식의 계수와 같음.
Cubic Bezier 적용
M=⎡⎣⎢⎢⎢P00P10P20P30P01P11P21P31P02P12P22P32P03P13P23P33⎤⎦⎥⎥⎥
∑∑Bm(u)Bn(v)M
P 는 위치값을 나타내며 16개의 점에 대해서 4개씩 묶여 사각형을 만듦.
즉 위 행렬이 나타내는 모양은 P_00, P_03, P_30, P_33 이 꼭짓점인 9칸의 격자임.
B 및의 지수는 행(m) 열(n) 을 나타내며 단순히 말해서 B_n 은 열에 대해서 Bezier 계산을 수행한다는 말임.
즉 현재 m = 0 의 경우 (1-t)^3*P_00 + 3*(1-t)^2*t*P_01 ... 을 수행한다는 말임.
Tangent 구하기
Berstein Basis 를 미분해서 t = uv.x 에 대해서 Polynomial 를 구함.
t = uv.y 에 대해서는 Berstein Basis 를 구함.
그리고 각각을 적용해주면 Tangent 를 구할 수 있음.
이는 위에서 시그마 중첩으로 표현한 식을 u 또는 v 에 대해서 편미분을 수행한 것과 똑같음.
여기까지의 hlsl 코드는 다음과 같음.
float4 BernsteinBasis(float t) { float invT = 1.0f - t; return float4(invT * invT * invT, // (1-t)^3 3.0f * t * invT * invT, // 3* t*(1-t)^2 3.0f * t * t * invT, // 3* t^2*(1-t) t * t * t); // t^3 } float4 dBernsteinBasis(float t) // derivative BernsteinBasis { float invT = 1.0f - t; return float4(-3 * invT * invT, // -3* (1-t)^2 3 * invT * invT - 6 * t * invT, // 3* (1-t)^2 - 6t(1-t) 6 * t * invT - 3 * t * t, // 6* t(1-t) - 3t^3 3 * t * t); // 3* t^3 } float4 evaluate_bezier(const OutputPatch<HullOutputType, 16> patch, float4 basisU, float4 basisV) { float3 value; value = basisV.x * ( patch[0].position * basisU.x + patch[1].position * basisU.y + patch[2].position * basisU.z + patch[3].position * basisU.w ); value += basisV.y * ( patch[4].position * basisU.x + patch[5].position * basisU.y + patch[6].position * basisU.z + patch[7].position * basisU.w ); value += basisV.z * ( patch[8].position * basisU.x + patch[9].position * basisU.y + patch[10].position * basisU.z + patch[11].position * basisU.w ); value += basisV.w * ( patch[12].position * basisU.x + patch[13].position * basisU.y + patch[14].position * basisU.z + patch[15].position * basisU.w ); return float4(value,1); } //////////////////////////////////////////////////////////////////////////////// // Domain Shader //////////////////////////////////////////////////////////////////////////////// [domain("quad")] PixelInputType ColorDomainShader(ConstantOutputType input, float2 uvCoord : SV_DomainLocation, const OutputPatch<HullOutputType, 16> patch) { PixelInputType output; float4 vertexPosition = float4(1,1,1,1); float3 tangent = float3(0,0,1); float3 bitangent = float3(0,0,1); // Determine the position of the new vertex. float4 basisU = BernsteinBasis(uvCoord.x); float4 basisV = BernsteinBasis(uvCoord.y); float4 d_basisU = dBernsteinBasis(uvCoord.x); float4 d_basisV = dBernsteinBasis(uvCoord.y); vertexPosition = evaluate_bezier(patch, basisU, basisV); bitangent = evaluate_bezier(patch, d_basisU, basisV); tangent = evaluate_bezier(patch, basisU, d_basisV); output.normal = normalize(cross(tangent, bitangent)); // Calculate the position of the new vertex against the world, view, and projection matrices. output.position = mul(vertexPosition, worldMatrix); output.position = mul(output.position, viewMatrix); output.position = mul(output.position, projectionMatrix); return output; }
PN Triangle
참고할 사이트
https://www.nvidia.com/content/PDF/GDC2011/John_McDonald.pdf
Cubic Bezier Triangle
https://en.wikipedia.org/wiki/B%C3%A9zier_triangle
기본 Bezier 가 선문에서 weight 가 들어간 무게중심을 구하는 거였음.
삼각형의 weight 가 들어간 무게중심을 구하는 것도 재귀적으로 만들 수 있음.
무게중심이 s, t, u 가 있어서 Dot( (P_0, P_1, P_3), (s, t, u) ) 로 무게중심을 구할 수 있음.
이걸 재귀적으로 수행해서 변이 2개로 쪼개진 경우는 다음처럼 계산할 수 있음.
BezierTri(P0,P1,P2)=(s∗P0+u∗P1+t∗P2)
QuadraticBezierTri(P0,P1,P2,P3,P4,P5)
=BezierTri(BezierTri(s,u,t,P0,P1,P2),BezierTri(s,u,t,P1,P3,P4),BezierTri(s,u,t,P2,P4,P5))
한변이 3개로 나누어지면 Cubic Bezier Triangle 이 됨.
직접 삼각형을 그려보면 알겠지만 Cubic 이상부터 도형 내부에 점이 생김.
PN Triangle 이란
https://en.wikipedia.org/wiki/Point-normal_triangle
Point Normal Triangle 로 정점 위치와 노말가지고 Cubic Bezier Triangle 을 만들어 삼각형을 쪼갠다는 말.
위의 Cubic Bezier 같은 경우는 정점이 사각형을 형성해야지 가능한데 이 경우는 우리가 많이 쓰는 메쉬에 대해서 작동을 함.
이하는 만드는 알고리즘임.
우선 위 그림을 이해해야함.
weight 가 각 꼭짓점에 대해서 u, v, w ( u + v + w = 3) 로 할당된다고 하고,
기존의 정점과 새로만들 정점을 u, v, w 의 조합으로 나타냄.
u 에 몰빵한 왼아래의 꼭짓점은 b300 이 되고, b012 는 w = 2, v = 1 로 만드는 것임.
어차피 나중에 3 으로 나눌 것이기 때문에 u + v + w 이 3 이라고 당황할 필요없음.
다음은 노말로 정점을 만드는 알고리즘임.
1. 기존의 꼭짓점은 그대로 사용함.
2. 삼각형의 변 위에 있는 것은 가장 가까운 노말을 이용해 보간함.
멀리있는 점을 B, 가까이 있는 점을 A 라고 하면
1/3 ( 2A + B - Normal of A * Dot( (B-A), Normal of A ) ) 가 됨.
예를들어
b012 = 1/3(b003 * 2 + b030 - Normal of b003 * Dot( (b030 - b003), Normal of b003) )
이를 설명하면 변 위에 있기 때문에 u, v, w 중에 하나는 0 으로 고정인 것을 주목.
Dot 은 Normal 의 weight 로 작용하는데 다음 세가지 경우를 생각하면 이해가 쉬움.
Normal 과 변이 수직일 때 => (2A + B) / 3 => 변을 3등분 해서 가까운 쪽.
Normal 이 변과 평행하며 다른 꼭짓점을 향할 때 => (2A + B - B + A)/3 => A
Normal 이 변과 평행하며 삼각형 바깥을 향할 때 => (2A + B + B - A)/3 => 변을 3등분 해서 먼쪽.
즉 Normal 이 변과 이루는 각도에 따라서 A ~ (2A + B) / 3 ~ (A + 2B) / 3 사이를 움직이게 됨. 그리고 실제로 빼지는 것은 Normal 이므로 삼각형이 이루는 평면과 수직된 방향으로 그 사이값이 움직이게 될 것임. 예를들어 A ~ (2A + B) / 3 사이의 값이면 움푹 들어갈 것이고 (2A + B) / 3 ~ (A + 2B) / 3 사이의 값이면 볼록 튀어나올 것임.
3. 1, 2 각각으로 만든 무게중심을 가지고 이용.
3에 대해서 설명하면 식은 매우 간단함.
우선 2번에서 만든 무게중심을 G1, 1번의 정점의 무게중심을 G2 라고 함.
무게중심은 다른말로는 정점을 다 더해서 정점 수만큼 나누는 것임.
그리고 G1 + (G1 - G2)/2 를 함.
2번에서 만든 정점들은 삼각형 평면과 수직된 높이가 변화되어 있음.
세 변에서 높이가 변화된 정점이 있으면 가운데는 그거보다 더 변화가 심해야함.
예를들어 삼각형이 볼록해질려면 세 변이 오목함과 동시에 세 변보다 가운데가 더 올라가야함.
그래서 그 차이를 2로 나눠서 더해주는 것임. 그럼 오목하면 더 오목해지고 볼록하면 더 볼록해짐.
왜 3 도 아니고 4도 아니고 2인지는 모르겠음.
장단점
계산하기 편하지만 정점 하나에 노말이 여러개가 될 가능성이 있음.
또한 삼각형이 양쪽이 볼록해지면 경계부분에 공백이 생김.
HLSL 코드
//////////////////////////////////////////////////////////////////////////////// // Hull Shader //////////////////////////////////////////////////////////////////////////////// [domain("tri")] // patch 의 종류 [partitioning("integer")] // 데셀레이션 분할 종류 [outputtopology("triangle_cw")] // 데셀레이터가 출력할 도형 종류 [outputcontrolpoints(3)] // 출력할 제어점들의 수 [patchconstantfunc("ColorPatchConstantFunction")] // 패치상수함수 HullOutputType ColorHullShader(InputPatch<HullInputType, 3> patch, uint pointID : SV_OutputControlPointID, uint patchId : SV_PrimitiveID) { HullOutputType output; const uint nextPointID = pointID < 2 ? pointID+1 : 0; output.position[0] = patch[pointID].position; output.position[1] = ComputeCP(patch[pointID].position, patch[nextPointID].position, patch[pointID].normal); output.position[2] = ComputeCP(patch[nextPointID].position, patch[pointID].position, patch[nextPointID].normal); output.color = patch[pointID].color; output.normal = patch[pointID].normal; return output; }
//////////////////////////////////////////////////////////////////////////////// // Domain Shader //////////////////////////////////////////////////////////////////////////////// [domain("tri")] PixelInputType ColorDomainShader(ConstantOutputType input, float3 uvw : SV_DomainLocation, const OutputPatch<HullOutputType, 3> patch) { PixelInputType output; float u = uvw.x; float v = uvw.y; float w = uvw.z; float uu = u * u; float uu3 = uu*3; float vv = v * v; float vv3 = vv*3; float ww = w * w; float ww3 = ww*3; float3 b300 = patch[0].position[0], b210 = patch[0].position[1], b120 = patch[0].position[2], b030 = patch[1].position[0], b021 = patch[1].position[1], b012 = patch[1].position[2], b003 = patch[2].position[0], b102 = patch[2].position[1], b201 = patch[2].position[2]; float3 E = (b210 + b120 + b021 + b012 + b102 + b201) / 6.f; float3 V = (b300 + b030 + b003) / 3.f; float3 b111 = E + (E - V)/2.f; float3 pos = b300 * uu * u + b030 * vv * v + b003 * ww * w + b210 * uu3 * v + b120 * vv3 * u + b021 * vv3 * w + b012 * ww3 * v + b102 * ww3 * u + b201 * uu3 * w + b111 * 6 * u * v * w; output.position = mul(float4(pos,1), projectionMatrix); output.normal = normalize(patch[0].normal * u + patch[1].normal * v + patch[2].normal * w); output.color = patch[0].color; return output;}
Hull Shader 에서 정점 위치를 3개씩 계산하는 것을 주목.
별건 아니고 Control Point 마다 병렬로 함수가 호출되므로 효율성 최적화를 위해 그렇게 됨.
Domain Shader 에서는 그렇게 계산한 걸 묶어서 최종 결과를 계산함.
노말을 바깥쪽으로 향하게 한 예제.
평면으로 보니 불룩 튀어나와 보이진 않지만 볼록 튀어나옴.
PN AEN Triangle
참고할 사이트
https://www.nvidia.com/content/PDF/GDC2011/John_McDonald.pdf
http://developer.download.nvidia.com/whitepapers/2010/PN-AEN-Triangles-Whitepaper.pdf
장단점
PN Triangle 이 낳는 경계부분의 공백이 없음.
대신 계산이 복잡하고 무엇보다 Second Index 가 필요함
이를 자동으로 만들어주는 프로그램이 Nvidia 에서 제공은 함.
Displacement Mapping
LOD 와 지형매핑
https://victorbush.com/2015/01/tessellated-terrain/