Laplacian Smoothing

This explanation is currently available in Japanese.

ひとことで

メッシュの各頂点を、辺でつながった周りの頂点の平均の位置へ少しずつ近づけることで、表面の細かい凸凹を消してなめらかにする方法です。画像のぼかしをメッシュでやるようなものです。計算がとても簡単で速い反面、くり返すと形全体が縮んでいくので、縮まない改良版（タウビン法）もよく使われます。

頂点 $\mathbf{p}_i$ につながった頂点の集合を $N(i)$ とすると、ラプラシアン（周りの平均からのずれ）は

L(\mathbf{p}_i) = \frac{1}{|N(i)|} \sum_{j \in N(i)} \mathbf{p}_j - \mathbf{p}_i

です。これに割合 $\lambda$ （0〜1）を掛けて足します。

\mathbf{p}_i \leftarrow \mathbf{p}_i + \lambda\, L(\mathbf{p}_i)

細かい凸凹ほどラプラシアンが大きいので、先に消えていきます。ところが、球のような大きなふくらみも「周りの平均より外側」なので、くり返すと少しずつ内側へ引き寄せられ、形全体が縮みます。

タウビン法は、 $\lambda$ で縮める一歩のあとに、負の値 $\mu$ （ $|\mu| > \lambda$ ）で押し戻す一歩を行います。

\mathbf{p} \leftarrow \mathbf{p} + \lambda L(\mathbf{p}), \qquad \mathbf{p} \leftarrow \mathbf{p} + \mu L(\mathbf{p})

細かい凸凹（高い周波数）は縮める一歩でほぼ消え、押し戻す一歩では戻りません。大きなふくらみ（低い周波数）は縮めた分だけ押し戻されるので、大きさが保たれます。通過させる周波数 $k_{PB}$ （0.1 程度）から $\mu = 1 / (k_{PB} - 1/\lambda)$ と決めます。

同時に更新する：頂点を 1 つずつその場で書き換えると、処理の順番で結果が偏ります。新しい位置は別の配列に書いて、最後に入れ替えます。
境界と固定：開いたメッシュの縁の頂点は、内側にしか隣がないので内側へ縮みます。縁は動かさないか、縁に沿った隣だけで平均します。
重みの工夫：単純な平均（均一重み）は、三角形の大きさがばらばらだと形がゆがみます。辺の向かいの角から決める余接（コタンジェント）重みを使うと、形に忠実になります。
部分的にかける：ブラシのように、影響の強さを場所ごとに変えて $\lambda$ に掛けます。