Spline Mesh Deformation

B Spline 정의와 공식

B-Spline (Basis Spline) 공식은 한 셋트의 Control Points로 구성된다. n + 1차의 B-Spline은 변수 t에 대한 p의 영향 정도(degree)를 piecewise 다항식

의 모음이다.

위 이미지는 B-Splie의 예시이다. 보통 첫 번째와 맨 마지막 점이 각각 시작점과 끝점이 되고, 중간 부분은 Control Point와 직접 만나지 않는다.

t는 0 ~ 1 까지의 값을 갖는 파라미터이다. 공식에 t 값을 대입하면 Pi 의 위치를 구할 수 있다.

두 번째 식에서 n, i는 행렬이 아닌, n에 의해 선택된 i 라는 의미이다. (i는 n의 coefficient 이다)

위 그림에서는 Control Point가 4개 있으므로, 3차 B-Spline (Cubic B-Spline) 이다.

아래는 3차 B-Spline에 대해 위 식을 전개해 본 것이다.

Cubic B-Spline formula.차수가 높아질수록 커브가 더 매끄러워지지만, 계산량이 늘어나는 것에 비해 눈에 띄는 차이가 없어 실제 사용례에서 3차 이상으로는 잘 사용하지 않는다고 한다.

이것을 다시 행렬식으로 정리하면, 아래와 같다.

P0 ~ P3의 영향을 해당 지점에 맞게 스케일링 한 뒤, 이것을 모두 더하는 방식이다.

이것을 다시 행렬식으로 정리하면, 아래와 같다.

Bernstein polynomial : P0 ~ P3의 영향을 해당 지점에 맞게 스케일링 한 뒤, 이것을 모두 합산한다.

오른쪽에 그려진 그래프는 Spline 상의 위치 t에 따른 각 점에 대한 영향 정도를 의미한다.

즉, Control Point의 P0, P1, P2, P3 의 공간 상 위치를 알면, Spline 상의 위치 t

(0일때는 P0 즉 Spline 의 시작점, 1일 때는 Spline 의 끝점)

가 주어졌을 때, 해당 점의 실제 공간상의 위치를 알 수 있다.

이것을 이용해서 Mesh의 버텍스 위치를 Spline 에 맞게 이동시킬 것이다.

B-Spline 과 Bezier Curve

B-Spline만으로는 복잡하고 긴 커브를 그리기 어렵다. Control Point들을 지나지 않기 때문에, 실제 커브의 모양을 디테일하게 조정하는 데 제약이 있고, Control Point 하나만 움직여도 커브 전체에 영향을 미친다.

이런 점을 보완하기 위해 고안된 것이 Bezier Curve이다.

Bezier Curve는 B-Spline 여러 개를 이어 만든 커브이다. 즉, Bezier Spline 의 Segment 1개는 1개의 B-Spine 이다.

각 Segment 는 시작점과 끝점을 공유한다. 이 공유되는 점들을 Knot 또는 Join 이라고 한다.

Knot 점들은 반드시 Spline 위에 위치한다.

앞서 t가 0 ~ 1 값을 갖는, Spline 상의 퍼센티지였다면, 이제는 이 값을 Spline 전체로 확장할 필요가 있다.

Bezier Spline에서의 Input key가 이 역할을 하게 된다. 각 Segment 의 t 값을 누적한 값이다.

Bezier Curve는 여러 개의 B-Spline Segment로 이루어진다.

각 Control Point의 영향이 특정 부분에 국한되기 때문에, 더 정교한 컨트롤이 가능하게 된다.

Knot들로부터 인접한 두 개의 Control Point 까지의 벡터를 Tangent 라고 한다.

Knot의 양 Tangent 값이 대칭(Mirrored) 이 아닌 경우, Broken tangent 라고 한다. Broken Tangent를 적절히 사용하면 부드러운 모양 뿐 아니라 날카로운 모양 표현도 가능하다. 이러한 여러 장점들 덕분에 포토샵, 일러스트레이터 등의 커브 표현 툴에서도 널리 사용되고 있다.

Unreal의 Spline Mesh Component

Unreal Engine에도 Spline Mesh Component가 있다(USplineMeshComponent). Spline의 시작점과 끝점, 그리고 각 점의 Tangent를 지정해 주면, B-Spline 공식을 적용해 Mesh의 Vertex들의 위치를 Spline 을 따라 변형해 준다.

https://www.youtube.com/watch?v=oYmfq1GJaMQ&t=442s

언리얼의 SplineMesh Component의 사용 예시

USplineMeshComponent에서 Spline에 대한 정보를 얻은 뒤, LocalVertexFactory 에 파라미터들을 전달해 준다. 아래는 전달되는 파라미터들의 목록이다. (in SplineMeshComponent.h)

FSplineMeshParams()
		: StartPos(ForceInit)
		, StartTangent(ForceInit)
		, StartScale(ForceInit)
		, StartRoll(0)
		, StartOffset(ForceInit)
		, EndPos(ForceInit)
		, EndScale(ForceInit)
		, EndTangent(ForceInit)
		, EndRoll(0)
		, EndOffset(ForceInit)
	{
	}

위 파라미터들을 PackSplineMeshParams() 함수로 묶은 뒤, VertexFactory로 전달된다.

void PackSplineMeshParams(const FSplineMeshShaderParams& Params, const TArrayView<FVector4f>& Output)
{
	auto PackSNorm16 = [](float Value, uint32 Shift = 0) -> uint32
	{
		float N = FMath::Clamp(Value, -1.0f, 1.0f) * 0.5f + 0.5f;
		return uint32(N * 65535.0f) << Shift;
	};

	static_assert(SPLINE_MESH_PARAMS_FLOAT4_SIZE == 8, "If you changed the packed size of FSplineMeshShaderParams, this function needs to be updated");
	check(Output.Num() >= SPLINE_MESH_PARAMS_FLOAT4_SIZE);
	
	Output[0]	= FVector4f(Params.StartPos, Params.StartScale.X);
	Output[1]	= FVector4f(Params.EndPos, Params.StartScale.Y);
	Output[2]	= FVector4f(Params.StartTangent, Params.EndScale.X);
	Output[3]	= FVector4f(Params.EndTangent, Params.EndScale.Y);
	Output[4]	= FVector4f(Params.StartOffset, Params.EndOffset);

	Output[5].X	= Params.StartRoll;
	Output[5].Y	= Params.EndRoll;
	Output[5].Z	= Params.MeshScaleZ;
	Output[5].W	= Params.MeshMinZ;

	Output[6].X = BitCast<float, uint32>(PackSNorm16(Params.SplineUpDir.X) | PackSNorm16(Params.SplineUpDir.Y, 16u));
	Output[6].Y = BitCast<float, uint32>(PackSNorm16(Params.SplineUpDir.Z));

	const FQuat4f MeshRot = FQuat4f(FMatrix44f(Params.MeshDir, Params.MeshX, Params.MeshY, FVector3f::ZeroVector));
	Output[6].Z = BitCast<float, uint32>(PackSNorm16(MeshRot.X) | PackSNorm16(MeshRot.Y, 16u));
	Output[6].W = BitCast<float, uint32>(PackSNorm16(MeshRot.Z) | PackSNorm16(MeshRot.W, 16u));

	Output[7].X	= Params.MeshDeformScaleMinMax.X;
	Output[7].Y	= Params.MeshDeformScaleMinMax.Y;
	Output[7].Z	= Params.bSmoothInterpRollScale ? 1.0f : 0.0f;
	Output[7].W	= 0.0f;
}

SplineDir, SplinePos 함수를 살펴보면, 위에서 살펴본 Spline 공식을 통해 방향과 위치를 보간하고 있음을 알 수 있었다..

static FVector3f SplineEvalPos(const FVector3f& StartPos, const FVector3f& StartTangent, const FVector3f& EndPos, const FVector3f& EndTangent, float A)
{
	const float A2 = A * A;
	const float A3 = A2 * A;

	return (((2 * A3) - (3 * A2) + 1) * StartPos) + ((A3 - (2 * A2) + A) * StartTangent) + ((A3 - A2) * EndTangent) + (((-2 * A3) + (3 * A2)) * EndPos);
}

static FVector3f SplineEvalPos(const FSplineMeshParams& Params, float A)
{
	// TODO: these don't need to be doubles!
	const FVector3f StartPos = FVector3f(Params.StartPos);
	const FVector3f StartTangent = FVector3f(Params.StartTangent);
	const FVector3f EndPos = FVector3f(Params.EndPos);
	const FVector3f EndTangent = FVector3f(Params.EndTangent);

	return SplineEvalPos(StartPos, StartTangent, EndPos, EndTangent, A);
}

static FVector3f SplineEvalDir(const FVector3f& StartPos, const FVector3f& StartTangent, const FVector3f& EndPos, const FVector3f& EndTangent, float A)
{
	const FVector3f C = (6 * StartPos) + (3 * StartTangent) + (3 * EndTangent) - (6 * EndPos);
	const FVector3f D = (-6 * StartPos) - (4 * StartTangent) - (2 * EndTangent) + (6 * EndPos);
	const FVector3f E = StartTangent;

	const float A2 = A * A;

	return ((C * A2) + (D * A) + E).GetSafeNormal();
}

static FVector3f SplineEvalDir(const FSplineMeshParams& Params, float A)
{
	// TODO: these don't need to be doubles!
	const FVector3f StartPos = FVector3f(Params.StartPos);
	const FVector3f StartTangent = FVector3f(Params.StartTangent);
	const FVector3f EndPos = FVector3f(Params.EndPos);
	const FVector3f EndTangent = FVector3f(Params.EndTangent);

	return SplineEvalDir(StartPos, StartTangent, EndPos, EndTangent, A);
}

위 함수들은 CalcSliceTransfom 에서 불린다. Alpha = Mesh 의 Vertex Position X의 Spline 상 위치이다.

FTransform USplineMeshComponent::CalcSliceTransformAtSplineOffset(const float Alpha) const
{
	// Apply hermite interp to Alpha if desired
	const float HermiteAlpha = bSmoothInterpRollScale ? SmoothStep(0.0, 1.0, Alpha) : Alpha;

	// Then find the point and direction of the spline at this point along
	FVector3f SplinePos = SplineEvalPos(SplineParams, Alpha);
	const FVector3f SplineDir = SplineEvalDir(SplineParams, Alpha);

	// Find base frenet frame
	const FVector3f BaseXVec = (FVector3f(SplineUpDir) ^ SplineDir).GetSafeNormal();
	const FVector3f BaseYVec = (FVector3f(SplineDir) ^ BaseXVec).GetSafeNormal();

	// Offset the spline by the desired amount
	const FVector2f SliceOffset = FMath::Lerp(FVector2f(SplineParams.StartOffset), FVector2f(SplineParams.EndOffset), HermiteAlpha);
	SplinePos += SliceOffset.X * BaseXVec;
	SplinePos += SliceOffset.Y * BaseYVec;

	// Apply roll to frame around spline
	const float UseRoll = FMath::Lerp(SplineParams.StartRoll, SplineParams.EndRoll, HermiteAlpha);
	const float CosAng = FMath::Cos(UseRoll);
	const float SinAng = FMath::Sin(UseRoll);
	const FVector3f XVec = (CosAng * BaseXVec) - (SinAng * BaseYVec);
	const FVector3f YVec = (CosAng * BaseYVec) + (SinAng * BaseXVec);

....
}

그러나 SplineMeshComponent 1개는 StartPoint, EndPoint 1개씩 만을 가질 수 있다. 즉 SplineMeshComponent 1개당 Bezier Spline 이 아닌 B-Spline 만을 표현할 수 있다.

따라서 여러 개의 B-Spline 으로 이루어진 Besizer Spline 전체를 Spline Mesh Component로 표현하려면, Segment 갯수만큼의 Spline Component가 필요하게 된다. 이 Component의 갯수는 곧 드로우콜의 갯수의 증가로 이어진다.

이 글의 목적은 Spline을 따라 변형된 Mesh Instance들 모두를 1개의 드로우콜로 그리는 것이다.

이렇게 하려면 기존 Vertex Factory 로 넣어주던 Spline 데이터를 Instance buffer 를 통해서 넘겨주고, 넘겨받은 값을 Vertex shader에서 계산해야 한다. 그렇게 하면 머터리얼 파라미터를 매 인스턴스마다 변경하지 않고, 1개의 머터리얼로 모든 인스턴스를 드로우콜 1번으로 그릴 수 있게 된다.

Spline상에 Instance 배치하기

먼저 그려진 Spline 상에 인스턴스들을 정렬해 본다. 인스턴스 하나당 1개의 Segment, 즉 B-Spline 1개가 맵핑되고, 각 인스턴스의 시작점과 끝점이 B-Spline 의 시작점(P0)과 끝점(P3) 에 위치하도록 정렬할 것이다.

계산 편의를 위해 원본 Spline 으로부터 Segment를 Mesh 길이에 맞게 Spline Point를 재정렬한 Spline을 생성해 주었다.

원본 Spline 의 모양을 따르되, segment의 시작점으로부터 실제 월드 상 거리가 Mesh Length와 일치하는 위치를 원본 Spline상에서 탐색해서, 이 점이 segment 끝점이 되도록 하였다.

다음 segment의 endPoint 탐색시 이 위치가 다음번 segment의 시작점이 된다.

이 과정을 탐색 Distance가 0에서 시작해 원본 Spline Length에 도달할 때까지 반복한다.

원본 Spline이 User Spline (흰색), 이를 수정해서 생성한 Spline이 Corrected Spline (분홍색) 이다.

// Initialize Distance and Location First
float CurrentDistance = 0.0f;
FVector CurrentLocation = UserSpline->GetLocationAtSplinePoint(0, ESplineCoordinateSpace::Local);

// Loop until current distance exceeds useSpline length
while (CurrentDistance < (UserSpline->GetSplineLength()))
{   
    CurrentDistance += 0.1f;
    float Distance = FVector::Distance(CurrentLocation, UserSpline->GetLocationAtDistanceAlongSpline(CurrentDistance, ESplineCoordinateSpace::Local));
    if (Distance >= MeshXSize)
    {
        CurrentLocation = UserSpline->GetLocationAtDistanceAlongSpline(CurrentDistance, ESplineCoordinateSpace::Local);
        CorrectedSpline->AddSplinePoint(CurrentLocation, ESplineCoordinateSpace::Local, true);
        CorrectedSpline->SetTangentAtSplinePoint(   CorrectedSpline->GetNumberOfSplinePoints() - 1, 
                                                    UserSpline->GetTangentAtDistanceAlongSpline(CurrentDistance, ESplineCoordinateSpace::Local),
                                                    ESplineCoordinateSpace::Local,
                                                    true);          
    }
}

새로운 포인트를 추가할 때, 기존 Spline 상의 Tangent를 복사해 오되, 각 Spline point간의 간격을 고려해 너무 긴 Tangent Vector가 들어오지 않도록 Tangent 벡터 길이를 Mesh X Length로 제한해 주었다.

수정된 Spline이 생성되었다면, 이것으로부터 각 인스턴스의 Transform을 계산해서 Spline 위에 배치할 수 있다.

인스턴스 1개당 1개의 Segment가 대응되기 때문에, n번째 인스턴스의 시작점은 Spline 상의 n번째 point, 끝점은 n + 1 번째 Point에서 얻어올 수 있다. Tangent도 마찬가지이다.

인스턴스의 Position은 StartPos + ( normalize(EndPos - StartPos) * ( MeshLength / 2.0f ) ) 이 되고,

인스턴스의 Rotation은 ( normalize(EndPos - StartPos )를 X축 (Forward Vector) 로 하는 Rotation 을 갖는다.

(Conv_VectorToRotator(FVector InVec))

인스턴스의 Scale은 따로 수정하지 않았다.

Spline 의 Segment 정보 Instance에 전달하기

Translate

정렬이 완료되었으면, 먼저 인스턴스가 위치한 각 B-Spline의 P1, P2 위치를 전달해 준다.

(P0, P3은 인스턴스의 시작점, 끝점이므로 계산해서 전달할 필요가 없다)

에디터 상에서 Spline을 봤을 때, 각 Point에 달린 핸들의 점 위치가 곧 P1, P2의 위치이다.

이 위치들은 각 Knot들로부터 Tangent Vector만큼을 더하거나 빼서 구할 수 있다.

(어쩐 일인지 Tangent Vector의 길이를 1/2 해야 원하는 위치를 얻을 수 있었다)

P1 = StartPos + ( StartTangent / 2.0f )

P2 = EndPos - ( EndTangent / 2.0f )

여기에서 StartTangent는 segment 시작점의 Leave Tangent, EndTangent는 segment 끝점의 Arrive Tangent이다.

각 점마다 X, Y, Z 축의 정보가 필요하므로, 위치 정보를 전달하는 데에는 총 6개의 Instance Custom Data 값이 사용되었다.

Rotate

StartTangent, EndTangent 값을 전달해 준다. Shader에서는 인스턴스가 얼마나 회전되었는지 모르기 때문에, 현재 Instance가 회전된 상태로부터 상대적인 각도를 전달해야 한다. 즉 Instance Space의 회전값이어야 한다.

StartAngle = normalize(EndPos - StartPos) → normalize(StartTangent) 로의 Rotation

EndAngle = (normalize(EndPos - StartPos) * -1.0f ) → normalize(EndTangent) 로의 Rotation

이 값들을 전달하는 데 파라미터 6개가 더 사용되었다.

버텍스 이동량 계산하기

P0, P3의 위치는 Instance 공간에서의 메시 x축 시작점, x축 끝점이 된다.

앞에서 Instance Data로 전달한 P1, P2 위치를 받아온다. 모든 Translation은 인스턴스 스페이스에서 진행하였다.

P0, P1, P2, P3 값을 알았으니 이제 위에서 본 Spline 공식에 t 값을 대입해, 보간된 위치를 계산해낼 수 있다.

아래 이미지는 위에서 본 B-Spline 공식을 그대로 구현한 것이다.

B-Spline 공식으로 Spline 형태에 따른 위치를 머터리얼에서 재구성한 모습

메시의 Instance 공간에서의 X축 Position을 t로 사용할 것이다. 이때 메시의 왼쪽 끝이 0, 오른쪽 끝이 1이 되도록 Pivot 위치를 고려해서 먼저 조정해 주어야 한다. Pivot 의 X축 위치가 메시의 정 가운데에 있다고 할 때, t로 사용할 값은 아래와 같다.

t = ( vertexPos.x / MeshLength ) + 0.5f;