論文読み: Differential Coordinates for Interactive Mesh Editing (SMI 2004)

以下の論文に関するメモです。

Differential Coordinates for Interactive Mesh Editing
Yaron Lipman, Olga Sorkine, Daniel Cohen-Or, David Levin, Christian Roessl, Hans-Peter Seidel
International Conference on Shape Modeling and Applications (SMI) 2004

論文について

SMI 2004 という IEEE 系の国際会議で発表された論文です。この会議は現在では消滅してしまったか改名してしまったかで、そのままは残っていなさそう*1です。

Google Scholar によると 2017 年 3 月 21 日時点で 278 件の文書に引用されている*2ようです。これは Computer Graphics 分野では非常に多い*3引用件数です。

後続研究がたくさんありそうです。例えば同年の SGP や翌年の SIGGRAPH で発表された以下の論文は同じ研究グループからの論文で、いずれも 300 件以上の引用がある*4 *5有名研究です。

Linear Rotation-invariant Coordinates for Meshes
Yaron Lipman, Olga Sorkine, David Levin, Daniel Cohen-Or
SIGGRAPH 2005

Laplacian Surface Editing
Olga Sorkine, Daniel Cohen-Or, Yaron Lipman, Marc Alexa, Christian Roessl, Hans-Peter Seidel
SGP 2004

他にも多くの解説論文やサーベイ論文が出ていそうですが、ここでは省略します。

論文の主旨

Differential coordinates という考え方を利用して、三角形メッシュで表現された三次元形状を編集する手法を提案しています。Differential coordinates は、

In this paper we advocate the use of linear differential coordinates as means to preserve the high-frequency detail of the surface.

とあるように、サーフェスの高周波な詳細を保存するために導入されます。

さらにこの論文では編集による局所的な回転をうまく扱うための工夫をしていて、そこがこの論文の重要なところなのですが、ここでは省略します。

Differential Coordinates の概要

Differential coordinates とは座標の表現の一種で、ここではメッシュの各頂点の座標を表すために世界座標系による表現の代わりに用いることを想定しています。

日本語訳は不明です。もしかしたらまだないのかもしれません。

後述するように、Laplacian coordinates は differential coordinates の一種です。

世界座標系による表現が与えられたとき、それに対応する differential coordinates は、ある線形変換 $D$ によって得ることができます。逆に differential coordinates が与えられたとき、それに対応する世界座標系による表現は、線形変換 $D$ の逆変換 $D^{-1}$ によって得ることができます。実際には線形変換 $D$ は行列として表現されるので、逆変換を行うには線形方程式を解くことになります。

Differential Coordinates の導入

ここでは論文の Section 3: Fundamentals に当たる部分を簡単に紹介します。

まず $G=(V, E)$ を三角形メッシュとします。ここで $V$ は頂点の座標の集合、 $E$ は辺の集合です。また $j$ 番目の頂点の位置を $\mathbf{p}_j$ と表すことにします。

続いて、 $S$ を $\mathbf{p}_j \in V$ を受け取りその近似的な位置を返す写像 $S$ :

$\mathbf{p}_j \approx S(\mathbf{p}_j)$
を考えます。特にここでは、近似的な位置がその他の頂点位置の線形和で表されるものを考えます。つまり、
$\displaystyle{S(\mathbf{p}_j) = \sum_{i \in \text{supp}(j), i \neq j} \alpha_{ji} \mathbf{p}_i}$
と表される場合を考えます。ここで $\text{supp}(j)$ は $j$ 番目の頂点を近似するために使われる頂点の集合、 $\alpha_{ji}$ は $j$ 番目の頂点を近似する際に $i$ 番目の頂点位置に対して乗じられる重みを表します。 $\text{supp}(\cdot)$ と $\alpha$ を定めることで写像 $S$ は定まります。

次に、頂点位置を変換するための線形変換演算子 $D$ を

$D(\mathbf{p}_j) = \mathbf{p}_j - S(\mathbf{p}_j)$
と定義します。ベクトル $D(\mathbf{p}_j)$ を $j$ 番目の頂点の differential coordinates であると呼びます。

演算子 $D$ は線形であるため、行列形式で書くことが可能です。 $n = \left| V \right|$ とし、 $\mathbf{M}$ を $n \times n$ の行列として、

$M_{ij} = \begin{cases} 1 & (i = j) \\ - \alpha_{ij} & (j \in \text{supp}(i)) \\ 0 & (\text{otherwise}) \end{cases}$
と定義します。すると、
$\begin{bmatrix} \delta^{(x)} & \delta^{(y)} & \delta^{(z)} \end{bmatrix} = \mathbf{M} \begin{bmatrix} \mathbf{p}^{(x)} & \mathbf{p}^{(y)} & \mathbf{p}^{(z)} \end{bmatrix}$
という関係式が成立します。ただし $\delta^{(x)} \in \mathbb{R}^{n}$ は $i$ 番目の要素に $i$ 番目の頂点の differential coordinates の $x$ 座標を持つベクトルです。 $\delta^{(y)}, \delta^{(z)}$ も同様です。また、 $\mathbf{p}^{(x)} \in \mathbb{R}^{n}$ は $i$ 番目の要素に $i$ 番目の頂点の元の $x$ 座標を持つベクトルです。 $\mathbf{p}^{(y)}, \mathbf{p}^{(z)}$ も同様です。

なお、 $\left| \text{supp}(\cdot) \right|$ が小さければ $\mathbf{M}$ は疎行列になるため、元の座標から differential coordinates への変換は比較的高速です。

逆に differential coordinates の情報から元の座標情報を再構築するには、上述の線形連立方程式を解けば良い*6ことになります。その際にユーザによる形状編集の意図*7を soft constraints としてこの線形連立方程式に組み込み、それを最小二乗法で解くというのが、この手法の流れとなります。

Laplacian Coordinates との関係

Laplacian coordinates は differential coordinates の特殊形です。特に

$\displaystyle{\text{supp}(j) = \{ i \mid (j, i) \in E \}, \alpha_{ji} = \frac{1}{d_{ij}}}$
としたときの differential coordinates のことを Laplacian coordinates と呼びます。ここで $d_{ij}$ は頂点間の距離に応じた値などが使われますが、幾つかバリエーションがあります。

*1:http://dblp2.uni-trier.de/db/conf/smi/

*2:https://scholar.google.com/scholar?q=differential+coordinates+for+interactive+mesh+editing

*3:参考までに、本ブログでも散々言及している Muller らによる Position Based Dynamics という論文は現時点で 362 件でした。

*4:https://scholar.google.com/scholar?q=linear+rotation-invariant+coordinates+for+meshes

*5:https://scholar.google.com/scholar?q=laplacian+surface+editing

*6:ただし $\mathbf{M}$ が特異行列の場合は soft constraints を足さないと解が定まりません。

*7:例えば「 $i$ 番目の頂点をある位置に固定したい」などの線形な制約であれば、上述の連立方程式を拡張することで組み込むことができます。