###### tags: `Paper`、`3D Computer Game`、`Motion`
# **[Interactive Motion Generation from Examples](https://dl.acm.org/doi/10.1145/566654.566606)**

本篇論文提出一個 framework ，通過剪切和黏貼 motion capture data 來生成新的 human motion。不同於 motion graph，本篇作者沒有在原始 motion capture 之間生成 transition capture，而是使用一種局部平滑的形式處理不連續性。

**Website:** [Okan Arikan](http://www.okanarikan.com/paper/2002/08/05/SynthesisFromExamples.html)

## 1 Introduction

在電腦上生成逼真的 human motion 是很困難的，基本的解決方案是 motion capture，然而缺點是：

1. 大多數動作捕捉系統使用起來非常昂貴，因為這個過程對於演員和技術人員來說非常耗時，而且動作數據往往不會被重複使用。
2. 很難獲得完全符合動畫師想要的動作。滿足複雜的 timed constraints 很困難，並且可能涉及許多 motion capture iterations。包括在特定時間準確地處於特定位置或將運動與之前拍攝的背景動作同步。

合成 motion 的三個階段：

1. Obtaining motion demands: 涉及指定運動的 constraints，例如運動的長度、身體或單個關節應該在哪裡，或者身體在特定時間需要做什麼。這些 constraints 可能來自動畫師使用的 interactive editing system，也可能來自電腦遊戲引擎本身。
2. Generating motion: 涉及獲得滿足要求的粗略運動。在本文中，我們描述了一種技術，該技術將示例運動的點點滴滴剪切和粘貼在一起以創建這樣的運動。
3. Post processing: 涉及修復小規模的錯誤部分。包括固定腳，使它們不會在地面上穿透或滑動，加長或縮短步幅以及修復 constraint violations。

## 3 Synthesis as Graph Search

### 3.1 Motion Graph

motion sequence 為一個 directed graph，與 [Motion Graph](https://hackmd.io/SoHgBtv0QBGoEZB4_ezOUA) 不同的是，這邊每一個 node 對應到的是一個 frame。

<center>


</center>

然而，若每一幀都對應到一個點，將會造成此圖過於龐大，因此，作者將始於同一個 motion sequence 的所有點(幀)折疊起來，產生一個新的圖 $G$，在圖 $G$ 上的每個點都是一段單獨的 motion sequence。在這張圖中，最上面的部分是一個有向圖，每一個 node 代表的都是一段 motion sequence，每段 motion sequence 裡的每個 frame 都是一個 node 可以連接自身 sequence 或是 其他 sequence 中的 frame，如圖中間所示，最後透過 randomized search 方法在該圖找出適合的 path 來合成新的 constrained motion sequence。

<font color="red">$$D_{s_it_j} = [(P(s_i) - P(t_j)) (|T(s_i)| - |T(t_j)|)' (|R(s_i| - |R(t_j|)'] \tag{2}$$</font>

這段距離公式裡，$P$ 指的是 position，$T$ 指的是 translation，$R$ 指的是 rotation。==與 Motion Graphs 不同，這邊要多判斷一個 rotation 是因為，在這篇並沒有做動作與方向是分開這個假設，因此，當動作相同，方向不同時，仍被視為不同的 motion。==

### 3.2 Constraints

給定任意兩個 position，可能出現沒有任何 path 可以連接兩點的情況，因此本篇論文定義可以完全且必須完全滿足要求者為 hard constraint。

**hard constraint：** 包含在特定 time slot 使用特定 frame，例如，限制在特定時間通過特定 nodes，而不是將所有 path 都考慮進去。這樣，就可以將移動的圖形限制在特定時間的特定姿勢。

**soft constraint：** 通常無法完全滿足 soft constraint，因此作者透過對 sequence 進行評分的方式，嘗試找到最接近(適合?)的 sequence。soft constraint 包含：

1. 總幀樹應該是一個特定數字。
2. motion 不能穿透任何物體。
3. body 應該在特定時間處於特定位置和方向。
4. 特定關節應在特定時間處於特定位置（並且可能具有特定速度）。
5. motion 在特定時間應具有特定的風格（如快樂或精力充沛）。

==以成果為例，第三張圖中，有一條藍色的線，限制 motion 在該 frame 的高度，此為 hard constraint，其餘每個 frame 為 soft constraint。==

## 4 Randomized Search

motion graph 很難用 [dynamic programming](https://web.ntnu.edu.tw/~algo/DynamicProgramming.html) search，因為有許多有效路徑同樣滿足 constraint。同樣有效的路徑之間可能存在巨大差異。而在此處 branch and bound 演算法起到的作用很小。

### 4.1 Summarizing the Graph

兩個 node $s$, $t$ 之間的 edges 可以用一個 matrix $P_{st}$ 來表示，matrix 的 $(i, j)$ 表示連接 $s_i$ 和 $t_j$ 的 edge 的權重，若不存在 edge 則以 $\infty$ 表示。

$$(P_{st})_{ij} =
\begin {cases}
C(s_i, t_j) & \text{if there is an edge from $s_i$ to $t_j$} \\
\infty & \text{otherwise} \\
\end{cases}
$$

下圖為兩個 motion clip 的 weight matrix，並且透過 clustering 來壓縮這些 block。可以看到每個 group 皆趨近橢圓，因若兩個 frame 相似，則兩者附近之 frame 也可能相似。

<center>


</center>

### 4.2 Searching the Summaries

使用 randomized search 方法，在該圖中搜索適當的路徑來合成 constrained motion sequences，該方法隨機從圖中的一組路徑開始，對每條路徑和所有可能的 mutations ，與原始路徑比較 constraints，並進行評分，接受比原始路徑更好的 mutations，重複直到不能通過mutations 產生更好的路徑，得到最終的路徑。

其中，mutations 有兩種方式：
1. **Replace a sequence:** 如圖上半部分，刪除路徑的某些部分，並用另一組邊替換該部分。
2. **Demoting two edges:** 如圖下半部分，刪除路徑中的一些邊，並在我們的層次結構中用它們的子項替換已刪除的邊。

<center>


</center>

在合成 motion 時，方向不連續是不可避免的。論文中使用局部平滑的形式處理這些不連續性。在左上角，一個不連續的方向信號，其不連續性顯示在右上角。我們現在為這個不連續性構造一個插值，顯示在右下角，並將其添加回原始信號以獲得左下角顯示的連續版本。通常，方向的不連續性足夠小，不需要更複雜的策略。

<center>


</center>

### 4.3 Authoring Human Motions

<center>


</center>

在 motion 上放置 “checkpoint”。在圖中，右側的箭頭表示所需的起始位置和方向，左側的箭頭表示所需的結束位置和方向。 所有 constraint 也帶有時間戳，強制主體在時間戳處的 constraint 符合要求。 對於這兩個 body constraint，我們可以 realtime 生成許多滿足 constraint 的 motion。

<center>


</center>

我們可以在一個動作中使用多個 “checkpoint”。在這個圖中，從右箭頭到左箭頭的途中，運動需要通過中間的箭頭（body constraint）。

<center>


</center>

除了 body constraint 之外，joint constraint 還可用於進一步為單個關節分配 “checkpoint”。 在這個圖中，人物的頭部也被限制高(藍色線條)，呈現跳躍運動。

<center>


</center>

使用 hard constraint，我們可以強製圖中人物執行特定的活動。 在這裡，我們將運動的末端限制為在特定位置/方向和時間。 以圖為例，限制角色最終平躺在地上，該框架即可 realtime 生成所需的一系列翻滾運動。