Appendix

1. Pose History

We do not focus on its core algorithm, we just simply introduce it.

Now in Pose Search in Unreal Engine 5.4, we are using a new pose trajectory instead of the old one in plugin MotionTrajectory. The data struct are defined as followed:

PoseSearcjTrajectoryTypes.h
USTRUCT(BlueprintType, Category="Pose Search Trajectory")
struct POSESEARCH_API FPoseSearchQueryTrajectorySample
{
	GENERATED_BODY()

	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Pose Search Query Trajectory")
	FQuat Facing = FQuat::Identity;

	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Pose Search Query Trajectory")
	FVector Position = FVector::ZeroVector;

	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Pose Search Query Trajectory")
	float AccumulatedSeconds = 0.f;

	FPoseSearchQueryTrajectorySample Lerp(const FPoseSearchQueryTrajectorySample& Other, float Alpha) const;
	void SetTransform(const FTransform& Transform);
	FTransform GetTransform() const { return FTransform(Facing, Position); }
};
POSESEARCH_API FArchive& operator<<(FArchive& Ar, FPoseSearchQueryTrajectorySample& TrajectorySample);

USTRUCT(BlueprintType, Category = "Motion Trajectory")
struct POSESEARCH_API FPoseSearchQueryTrajectory
{
	GENERATED_BODY()

	// This contains zero or more history samples, a current sample, and zero or more future predicted samples.
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Pose Search Query Trajectory")
	TArray<FPoseSearchQueryTrajectorySample> Samples;

	FPoseSearchQueryTrajectorySample GetSampleAtTime(float Time, bool bExtrapolate = false) const;
	
#if ENABLE_ANIM_DEBUG
	void DebugDrawTrajectory(const UWorld* World, const float DebugThickness = 0.f, float HeightOffset = 0.f) const;
	void DebugDrawTrajectory(FAnimInstanceProxy& AnimInstanceProxy, const float DebugThickness = 0.f, float HeightOffset = 0.f, int MaxHistorySamples = -1, int MaxPredictionSamples = -1) const;
#endif // ENABLE_ANIM_DEBUG
};
POSESEARCH_API FArchive& operator<<(FArchive& Ar, FPoseSearchQueryTrajectory& Trajectory);
C++

By interpolate, we can get the runtime trajectory data of certain time:

PoseSearchTrajectoryTypes.cpp
FPoseSearchQueryTrajectorySample FPoseSearchQueryTrajectory::GetSampleAtTime(float Time, bool bExtrapolate) const
{
	const int32 Num = Samples.Num();
	if (Num > 1)
	{
		const int32 LowerBoundIdx = Algo::LowerBound(Samples, Time, [](const FPoseSearchQueryTrajectorySample& TrajectorySample, float Value)
			{
				return Value > TrajectorySample.AccumulatedSeconds;
			});

		const int32 NextIdx = FMath::Clamp(LowerBoundIdx, 1, Samples.Num() - 1);
		const int32 PrevIdx = NextIdx - 1;

		const float Denominator = Samples[NextIdx].AccumulatedSeconds - Samples[PrevIdx].AccumulatedSeconds;
		if (!FMath::IsNearlyZero(Denominator))
		{
			const float Numerator = Time - Samples[PrevIdx].AccumulatedSeconds;
			const float LerpValue = bExtrapolate ? Numerator / Denominator : FMath::Clamp(Numerator / Denominator, 0.f, 1.f);
			return Samples[PrevIdx].Lerp(Samples[NextIdx], LerpValue);
		}

		return Samples[PrevIdx];
	}

	if (Num > 0)
	{
		return Samples[0];
	}

	return FPoseSearchQueryTrajectorySample();
}
C++

In PoseSearchHistroy.h, the plugin defines an important interface which used in the final animation node, and also gives a animation message interface. The IPoseHistory has many implmentations:

PoseSearchHistory.h
struct POSESEARCH_API IPoseHistory
{
public:
	virtual ~IPoseHistory() {}
	
	// returns the BoneIndexType transform relative to ReferenceBoneIndexType: 
	// if ReferenceBoneIndexType is 0 (RootBoneIndexType), OutBoneTransform is in root bone space
	// if ReferenceBoneIndexType is FBoneIndexType(-1) (ComponentSpaceIndexType), OutBoneTransform is in component space
	// if ReferenceBoneIndexType is FBoneIndexType(-2) (WorldSpaceIndexType), OutBoneTransform is in world space
	virtual bool GetTransformAtTime(float Time, FTransform& OutBoneTransform, const USkeleton* BoneIndexSkeleton = nullptr, FBoneIndexType BoneIndexType = RootBoneIndexType, FBoneIndexType ReferenceBoneIndexType = ComponentSpaceIndexType, bool bExtrapolate = false) const = 0;
	virtual const FPoseSearchQueryTrajectory& GetTrajectory() const = 0;
	
	// @todo: deprecate this API. TrajectorySpeedMultiplier should be a global query scaling value passed as input parameter of FSearchContext during config BuildQuery
	virtual float GetTrajectorySpeedMultiplier() const = 0;
	virtual bool IsEmpty() const = 0;

	virtual const FBoneToTransformMap& GetBoneToTransformMap() const = 0;
	virtual int32 GetNumEntries() const = 0;
	virtual const FPoseHistoryEntry& GetEntry(int32 EntryIndex) const = 0;

#if ENABLE_DRAW_DEBUG && ENABLE_ANIM_DEBUG
	virtual void DebugDraw(const UWorld* World, FColor Color) const = 0;
	virtual void DebugDraw(FAnimInstanceProxy& AnimInstanceProxy, FColor Color) const = 0;
	virtual void DebugDraw(FAnimInstanceProxy& AnimInstanceProxy, FColor Color, float Time, float PointSize = 6.f, bool bExtrapolate = false) const;
#endif
};

...
...
...

class IPoseHistoryProvider : public UE::Anim::IGraphMessage
{
	DECLARE_ANIMGRAPH_MESSAGE(IPoseHistoryProvider);
public:
	virtual const IPoseHistory& GetPoseHistory() const = 0;
};
C++

And then, Pose history is implemented finally in AnimNode_PoseSearchCollector.h

2. KD Tree & VP Tree

k-d tree - Wikipedia
en.wikipedia.org
KD-Tree 演算法筆記 | YuCheng
KD-Tree 即 K-dimensional tree ( K 維樹 ),是一種分割 K 維資料空間的資料結構,樹的每一層都以不同的維度標準做分割,主要應用於多維空間搜索,例如範圍搜索和最近鄰居搜索。
blog.yucheng.me
Vantage-point tree - Wikipedia
en.wikipedia.org
VP trees: A data structure for finding stuff fast
stevehanov.ca

By JiahaoLi

Hypergryph - Game Programmer 2023 - Now Shandong University - Bachelor 2019-2023

2 thoughts on “Motion Matching in Unreal Engine 5(4) : What’new in Unreal Engine 5.4?”

Leave a Reply

Your email address will not be published. Required fields are marked *