Skip to content

Latest commit

 

History

History
277 lines (232 loc) · 7.13 KB

README_ja.md

File metadata and controls

277 lines (232 loc) · 7.13 KB
Raw

[English 🇺🇸] / Japanese 🇯🇵

メッシュ簡略化

"Surface Simplification using Quadric Error Metrics, 1997" [Paper] を実装。

動作環境

python==3.12.0
scipy==1.11.3
numpy==1.26.0
scikit-learn==1.3.0
tqdm

インストール

# Clone
git clone https://github.com/astaka-pe/mesh_simplification.git
cd mesh_simplification

# Docker
docker image build -t astaka-pe/mesh-simp .
docker run -itd --gpus all --name mesh-simp -v .:/work astaka-pe/mesh-simp
docker exec -it mesh-simp /bin/bash

使用方法

python simplification.py [-h] -i data/ankylosaurus.obj [-v V] [-p P] [-optim] [-isotropic]

簡略化後のメッシュは data/output/ に出力される.

パラメータ

  • -i: 入力ファイル名 [必須]
  • -v: ターゲット超点数 [オプション]
  • -p: 簡略化比率 [オプション (-vを指定した場合には無効) | デフォルト: 0.5]
  • -optim: 価数最適化 [オプション | 推奨]
  • -isotropic: 等方的簡略化 [オプション]

簡略化のデモ

入力 簡略化 (50%) 簡略化 (20%) 簡略化 (1%)
14762 vertices 7381 vertices 2952 vertices 147 vertices
29520 faces 14758 faces 5900 faces 290 faces

価数最適化

三角形品質を向上させるため、頂点毎のvalence（価数）を考慮したエッジ縮約を実装した。

価数最適化なし (0.5%) 価数最適化あり (0.5%)
  • 価数がバラバラ
  • それ以上簡略化できない（価数3の）頂点を生じる
  • 三角形の形状が不均一
  • 価数6の頂点が増加
  • 正三角形に近い形状に揃う

現在の実装では、境界がないメッシュを想定し、valence=6を最適とする重みづけを行う。すなわち、valenceが6から離れるほど大きなペナルティが加わる。また、valence=3の頂点を生じるエッジ縮約には、過度に大きなペナルティを設定している。

等方的簡略化

エッジ長の不均一性を防ぐペナルティ項を追加。

Default (10%) Isotropic (10%)
  • エッジ長が不均一
  • 特徴が保存される
  • エッジ長が均一
  • 特徴が滑らかになる

アルゴリズム

概要

頂点 $\mathbf{v}=(v_x, v_y, v_z, 1)^T$ 毎のコストを、 $4\times4$ 対称行列 $Q$ を用いて、二次形式 $\Delta(\mathbf{v})=\mathbf{v}^T Q \mathbf{v}$ で定義。 縮約した場合に、コストが最小となる頂点ペアから縮約する。

手順

  1. 初期頂点で対称行列 $Q$ を計算する（後述）
  2. 縮約できる頂点ペアをリストアップする
  3. 2.の各頂点ペアに対し、縮約した場合のコストを計算する
    • 頂点 $\mathbf{v}_1$ を $\mathbf{v}_2$ にマージする場合、生成される頂点を $\mathbf{\bar{v}}=\frac{1}{2}(\mathbf{v}_1+\mathbf{v}_2)$ として、 $\mathbf{\bar{v}}^T (Q_1+Q_2) \mathbf{\bar{v}}$ を頂点ペア $(\mathbf{v}_1, \mathbf{v}_2)$ のコストとする。
  4. 3.で計算した各頂点ペアのコストを格納するヒープを作成
  5. ヒープから最小コストとなる頂点ペア $(\mathbf{v}_1, \mathbf{v}_2)$ を取り出し、そのエッジを縮約する
    • この際、頂点 $\mathbf{v}_1$ が関与する全ての頂点ペアに対するコストを更新する

Q の定義

頂点周りの平面（三角形）を表す方程式を、 $ax+by+cz+d=0$ とする。ただし、 $a^2+b^2+c^2=1$ である。 すなわち、 $(a, b, c)^T$ は三角形の法線ベクトルを意味し、三角形の重心座標を $(c_x, c_y, c_z)$ とすると、

$$ d = -1 \times \left[ \begin{matrix} a\\ b\\ c\\ \end{matrix} \right] \cdot \left[ \begin{matrix} c_x\\ c_y\\ c_z\\ \end{matrix} \right] $$

と表せる。 $\mathbf{p}=(a,b,c,d)^T$ として、 頂点 $\mathbf{v}$ から周囲の平面（三角形） $\mathbf{p}$ までの距離は

$$ \mathbf{p}^T \mathbf{v} = a v_x+ b v_y + c v_z + d $$

と表現でき、これらの二乗誤差の総和は、

$$ \begin{align} \Delta(\mathbf{v}) =& \sum_{\mathbf{p} \in N(\mathbf{v})}(\mathbf{p}^T \mathbf{v})^2 \\ =& \sum_{\mathbf{p} \in N(\mathbf{v})}(\mathbf{v}^T \mathbf{p})(\mathbf{p}^T \mathbf{v}) \\ =& \mathbf{v}^T \left(\sum_{\mathbf{p} \in N(\mathbf{v})}\mathbf{p}\mathbf{p}^T \right) \mathbf{v} \\ \end{align} $$

となる。ここで、

$$ K_p = \mathbf{p}\mathbf{p}^T = \left[ \begin{matrix} a^2 & ab & ac & ad \\ ab & b^2 & bc & bd \\ ac & bc & c^2 & cd \\ ad & bd & cd & d^2 \end{matrix} \right] $$

$$ Q = \sum_{\mathbf{p} \in N(\mathbf{v})} K_p $$

と定義することで、頂点のコストを二次形式

$$\Delta(\mathbf{v})=\mathbf{v}^T Q \mathbf{v}$$

で表せる。

制約事項

  • 非多様体を生じるエッジ縮約や、境界エッジの縮約は行わない。
  • エッジ角度を考慮していないため、自己交差や面のフリップが生じうる。