输入： 预期轨迹和其他特征的 feature
输出： 最匹配的 pose
具体来说一个传统的motion matching分为以下几步：
- Projection: 当用户输入的轨迹和查找到的目标 Frame 的轨迹不一致（或是出路很大），则需要重新搜索，搜索的过程主要是通过用户模拟的轨迹和当前 pose 的状态来去 database 中进行 match，然后作为修正的 Frame
- Decompression: 要把当前的目标 Frame 重新映射回目标 Pose
- Stepping: index++ 逐步推出下一个的 Frame
在MM的三个步骤中，Decompression 和 Stepping 的难度都不是很大，因为表示 feature 的 x 和 对应的 pose y 都被储存在database 中，所以MM中玩家与角色之间的交互可以表示为：
使用的时候直接读取就OK了，在这个算法中耗时间空间的主要是 Projection ，育碧同样给出了他们的解决思路：
- LOD
- KD-Tree
先来看看MM 的代码思路，其实很简单
- 每一帧都是在database 中对index++
- 在需要搜索的时候，在database 中搜索，如果 best_index 可用则切换
// 判断是否为最后一帧
bool end_of_anim = database_trajectory_index_clamp(db, frame_index, 1) == frame_index;
if (force_search || search_timer <= 0.0f || end_of_anim){
// 在数据库中寻找最匹配帧
database_search();
// 更新 pose 数据
if (best_index != frame_index){
trns_bone_positions = db.bone_positions(best_index);
trns_bone_velocities = db.bone_velocities(best_index);
trns_bone_rotations = db.bone_rotations(best_index);
trns_bone_angular_velocities = db.bone_angular_velocities(best_index);
inertialize_pose_transition();
frame_index = best_index;
}
// Reset search timer
search_timer = search_time;
}
// Tick frame
frame_index++; // Assumes dt is fixed to 60fps
// 查询下一 frame_index 对应的 Pose
curr_bone_positions = db.bone_positions(frame_index);
curr_bone_velocities = db.bone_velocities(frame_index);
curr_bone_rotations = db.bone_rotations(frame_index);
curr_bone_angular_velocities = db.bone_angular_velocities(frame_index);
curr_bone_contacts = db.contact_states(frame_index);
具体搜索是怎么算的呢
best_cost = 0.0;
for (int i = 0; i < nfeatures; i++){
best_cost += squaref(query_normalized(i) - features(best_index, i));
}
在 database_search() 中用的是欧氏距离，再看看维数，MM 总的特征对比按照如下计算
D
i
s
s
i
m
i
l
a
r
i
t
y
(
e
i
,
e
c
)
=
w
v
×
D
i
s
t
v
(
v
i
,
v
c
)
+
w
p
×
D
i
s
t
p
(
p
i
,
p
c
)
+
w
t
×
D
i
s
t
t
(
t
i
,
t
c
)
Dissimilarity(ei,ec)=w_v×Dist_v(v_i,v_c)+w_p×Dist_p(p_i,p_c)+w_t×Dist_t(t_i,t_c)
Dissimilarity(ei,ec)=wv×Distv(vi,vc)+wp×Distp(pi,pc)+wt×Distt(ti,tc)
总的特征对比由 velocity、position 和 trajectory，三个变量得到，其中velocity、position为三维变量，trajectory是二维变量，假设取两个关节的velocity、position，三个未来trajectory，此时的维度：
d
i
m
(
D
i
s
s
i
m
i
l
a
r
i
t
y
)
=
(
3
+
3
)
∗
2
+
2
∗
3
=
18
dim(Dissimilarity) = (3+3)*2+2*3=18
dim(Dissimilarity)=(3+3)∗2+2∗3=18
按照KD-tree的定义有：
2
18
=
262
,
144
≪
d
a
t
a
b
a
s
e
f
r
a
m
e
n
u
m
b
e
r
2^{18}=262,144 ll database frame number
218=262,144≪database frame number
结论：方案可行
以下给出kd-tree 的 python 代码，参考资料：
k-d tree算法的研究
class KDNode(object):
def __init__(self, value, split, left, right):
# value=[x,y]
self.value = value
self.split = split
self.right = right
self.left = left
class KDTree(object):
def __init__(self, data):
# data=[[x1,y1,...],[x2,y2,...],...]
# 维度
k = len(data[0])
def CreateNode(split, data_set):
if not data_set:
return None
# 排序
data_set.sort(key=lambda x: x[split])
# 取中位数
split_pos = len(data_set) // 2
median = data_set[split_pos]
# 计算下一维度
split_next = (split + 1) % k
return KDNode(median, split, CreateNode(split_next, data_set[: split_pos]),
CreateNode(split_next, data_set[split_pos + 1:]))
self.root = CreateNode(0, data)
def search(self, root, x, count=1):
nearest = []
for i in range(count):
nearest.append([-1, None])
self.nearest = np.array(nearest)
def recurve(node):
if node is not None:
axis = node.split
daxis = x[axis] - node.value[axis]
if daxis < 0:
recurve(node.left)
else:
recurve(node.right)
dist = sqrt(sum((p1 - p2) ** 2 for p1, p2 in zip(x, node.value)))
for i, d in enumerate(self.nearest):
# 如果当前nearest内i处未标记（-1），或者新点与x距离更近
if d[0] < 0 or dist < d[0]:
# 插入比i处距离更小的
self.nearest = np.insert(self.nearest, i, [dist, node.value], axis=0)
self.nearest = self.nearest[:-1]
break
# 找到nearest集合里距离最大值的位置，为-1值的个数
n = list(self.nearest[:, 0]).count(-1)
# 切分轴的距离比nearest中最大的小（存在相交）
if self.nearest[-n - 1, 0] > abs(daxis):
if daxis < 0: # 相交，x[axis]< node.data[axis]时，去右边（左边已经遍历了）
recurve(node.right)
else: # x[axis]> node.data[axis]时，去左边，（右边已经遍历了）
recurve(node.left)
recurve(root)
return self.nearest
# 最近坐标点、最近距离和访问过的节点数
result = namedtuple("Result_tuple", "nearest_point nearest_dist nodes_visited")
data = [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]
# 创建KD-tree
kd = KDTree(data)
#[3, 4.5]最近的3个点
n = kd.search(kd.root, [3, 4.5], 3)
print(n)
#[[1.8027756377319946 list([2, 3])]
[2.0615528128088303 list([5, 4])]
[2.692582403567252 list([4, 7])]]
