コンピュータグラフィクス論

(1)

コンピュータグラフィクス論

– モデリング (3) –

2015年4月30日高山健志

(2)

陰関数表現による形状モデリング

• 3D空間上のスカラー場 𝐹 𝑥, 𝑦, 𝑧 に対し、 𝐹 𝑥, 𝑦, 𝑧 = 0 で定義されるサーフェス • 別名：ゼロ等値面、陰関数 (ボリューム) 表現 •  サーフェス表現 • 𝐹 𝒑 が正 (負) のとき、𝒑 は物体の外部 (内部) • 勾配 𝛻𝐹 は法線方向に一致 • 𝛻𝐹(𝒑) = 1 ∀𝒑 のとき、F は物体表面からの距離 2 半径 2 の球 𝐹 𝑥, 𝑦, 𝑧 = 𝑥2 + 𝑦2 + 𝑧2 − 4 = 0

(3)

陰関数の例

3

(4)

陰関数の例：等電位面

(Metaball)

4 𝐹 𝒑 = 𝐹₁ 𝒑 − 𝐹₂(𝒑) 𝐹 𝒑 = 𝐹₁ 𝒑 + 𝐹₂(𝒑) 𝐹_𝑖 𝒑 = 𝑞𝑖 𝒑 − 𝒑_𝑖 𝐹 𝒑 = 𝐹1 𝒑 + 𝐹2 𝒑 + 𝐹3 𝒑 + 𝐹4 𝒑

(5)

陰関数の線形補間によるモーフィング

5 𝐹 𝒑 = 𝐹₁(𝒑) _{𝐹 𝒑 =} 2 3𝐹1 𝒑 + 1 3𝐹2 𝒑 𝐹 𝒑 = 1 3𝐹1 𝒑 + 2 3𝐹2 𝒑 𝐹 𝒑 = 𝐹2(𝒑)

(6)

複数の陰関数を組み合わせたモデリング

(7)

Constructive Solid Geometry (Boolean演算)

7

積：𝐹_𝐴∩𝐵 𝒑 = min 𝐹_𝐴 𝒑 , 𝐹_𝐵 𝒑 和：𝐹_𝐴∪𝐵 𝒑 = max 𝐹_𝐴 𝒑 , 𝐹_𝐵 𝒑

(8)

陰関数の表示方法：

Marching Cubes

• 等値面を三角形メッシュとして抽出 • 立方体格子の各セルに対し、 (1) 立方体の 8 頂点で関数値を計算 (2) その正負のパターンから、生成する面のタイプを決定 • 対称性から 15 通りに分類 (3) 関数値の線形補間から面の位置を決定 • 最も有名 (特許問題でも ) 8

(9)

Marching Cubes の曖昧性

9

The asymptotic decider: resolving the ambiguity in marching cubes [Nielson VIS91]

(10)

Marching Tetrahedra

• 立方体の代わりに四面体を使う • パターンが少なく、曖昧性が無い  実装が簡単 • 各立方体セルを、6 個の四面体に分割 • (隣接セル間で分割の向きを合わせることに注意) • きれいな三角形メッシュを取り出す工夫 10 http://paulbourke.net/geometry/polygonise/

(11)

シャープなエッジを保持した等値面抽出

11

Feature Sensitive Surface Extraction from Volume Data [Kobbelt SIGGRAPH01]

http://www.graphics.rwth-aachen.de/IsoEx/

格子サイズ：65×65×65

Marching Cubes 改善版 Marching Cubes (値のみ考慮)

(12)

陰関数の表示方法：レイトレーシング

12

Modelling with implicit surfaces that interpolate [Turk TOG02]

(13)

応用例：スケッチベース

3D モデリング

13

A sketching interface for modeling the internal structures of 3d shapes [Owada SmartGraphics03] ShapeShop: Sketch-Based Solid Modeling with BlobTrees [Schmidt SBIM05]

(14)

応用例：メッシュの穴埋め

14

(15)

点群からのサーフェス再構成

(16)

3D 形状の計測

• 得られるデータ：点群 • 3D座標 • 法線 (面の向き) • 得られない場合もある • ノイズが多すぎる場合もある 16 Range Scanner (LIDAR) Structured Light Multi-View Stereo Depth Camera

(17)

点群からのサーフェス形状再構成

• 入力：N 個の点群データ • 座標 𝐱_𝑖 = 𝑥_𝑖, 𝑦_𝑖, 𝑧_𝑖 と法線 𝐧_𝑖 = 𝑛_𝑖x, 𝑛_𝑖y, 𝑛_𝑖z , 𝑖 ∈ 1, … , 𝑁 • 出力：関数 𝑓(𝐱) で、値と勾配の制約を満たすもの • 𝑓 𝐱_𝑖 = 0 • 𝛁𝑓 𝐱_𝑖 = 𝐧_𝑖 • 等値面 𝑓 𝐱 = 0 が出力サーフェス形状

• “Scattered Data Interpolation” と呼ばれる問題

• Moving Least Squares • Radial Basis Function

CG以外の分野 (e.g. 機械学習) でも重要

17

(18)

勾配を制約する二通りの方法

• 法線方向にオフセットした位置に値の制約を追加 • 簡単 • 数学表現そのものに勾配制約を取り入れる (エルミート補間) • 高品質 18

Modelling with implicit surfaces that interpolate [Turk TOG02] Hermite Radial Basis Functions Implicits [Macedo CGF10]

(19)

Moving Least Squares による補間

(移動最小二乗)

(20)

出発点：

Least SQuares (最小二乗)

• 求めたい関数が線形だと仮定する：𝑓 𝐱 = 𝑎𝑥 + 𝑏𝑦 + 𝑐𝑧 + 𝑑 • 𝑎, 𝑏, 𝑐, 𝑑 が未知係数 • データ点における値の制約 • (勾配制約は今は考えない) 20 𝐱 ≔ (𝑥, 𝑦, 𝑧) 𝑥₁ 𝑦₁ 𝑧₁ 1 𝑥₂ 𝑦₂ 𝑧₂ 1 𝑥_𝑁 𝑦_𝑁 𝑧_𝑁 1 𝑎 𝑏 𝑐 𝑑 𝑓₁ 𝑓₂ 𝑓_𝑁 ・・・・・・ = 𝐴 𝐜 𝐟 𝑓 𝐱₁ = 𝑎𝑥₁ + 𝑏𝑦₁ + 𝑐𝑧₁ + 𝑑 = 𝑓₁ 𝑓 𝐱₂ = 𝑎𝑥₂ + 𝑏𝑦₂ + 𝑐𝑧₂ + 𝑑 = 𝑓₂ 𝑓 𝐱_𝑁 = 𝑎𝑥_𝑁 + 𝑏𝑦_𝑁 + 𝑐𝑧_𝑁 + 𝑑 = 𝑓_𝑁 ・・・

(21)

Overconstrained System

• #未知数 < #制約 (i.e. 縦長の行列)  全ての制約を同時に満たせない • fitting の誤差を最小化： 21 𝐴 𝐜 𝐟 𝐴 𝐜 𝐟 𝐜 𝐴⊺𝐴 −1 𝐟 𝐴⊺ 𝐴⊺ 𝐴⊺ = = = 𝑨 𝐜 − 𝐟 2 = 𝑖=1 𝑁 𝑓 𝐱_𝑖 − 𝑓_𝑖 2

(22)

LSQ の幾何的な解釈

• 𝐩 と 𝐪 が張る空間中で 𝐫 に最も近い点を求める (投影する) ことに相当 • fitting 誤差は投影距離に相当： 𝑑2 = 𝛼𝐩 + 𝛽𝐪 − 𝐫 2 22 𝑝_x 𝑝_y 𝑝_z = 𝛼 𝛽 𝑞_x 𝑞_y 𝑞_z 𝑟_x 𝑟_y 𝑟_z 𝐪 𝐩 𝐫 𝛼 𝛽 𝑑

(23)

Weighted Least Squares (重み付き最小二乗)

• 各データ点ごとの誤差に、重み 𝑤_𝑖 をつける • 重要度、確信度 • 以下の誤差を最小化： 𝑖=1 𝑁 𝑤_𝑖 𝑓 𝐱_𝑖 − 𝑓_𝑖 2 23 𝑥₁ 𝑦₁ 𝑧₁ 1 𝑥₂ 𝑦₂ 𝑧₂ 1 𝑥_𝑁 𝑦_𝑁 𝑧_𝑁 1 𝑎 𝑏 𝑐 𝑑 𝑓₁ 𝑓₂ 𝑓_𝑁 ・・・・・・ = 𝑤₁ 𝑤₂ 𝑤_𝑁 𝑤₁ 𝑤₂ 𝑤_𝑁 𝐴 𝐜 𝐟 𝑊 𝑊

(24)

Weighted Least Squares (重み付き最小二乗)

24 𝐴 𝐜 𝐟 𝐜 𝐴⊺𝑊2𝐴 −1 𝐴⊺𝑊2 𝐟 = = 𝑊 𝑊

(25)

Moving Least Squares (移動最小二乗)

• 重み 𝑤_𝑖 が、評価位置 𝐱 に依存： 𝑤_𝑖 𝐱 = 𝑤( 𝐱 − 𝐱_𝑖 ) • よく使われる関数 (Kernel)： • 𝑤 𝑟 = 𝑒−𝑟2/𝜎2 • 𝑤 𝑟 = _𝑟₂_+𝜖1 ₂ • 重み行列 𝑊 が 𝐱 に依存  係数 𝑎, 𝑏, 𝑐, 𝑑 が 𝐱 に依存 25 𝑓 𝐱 = 𝑥 𝑦 𝑧 1 𝑎(𝐱) 𝑏(𝐱) 𝑐(𝐱) 𝑑(𝐱) 𝐴⊺𝑊 𝐱 2𝐴 −1 𝐴⊺𝑊 𝐱 2 𝐟 評価位置に近いほど大きな重み

(26)

法線制約の導入

• 各データ点が表す 1 次式を考える： 𝑔_𝑖 𝐱 = 𝑓_𝑖 + 𝐱 − 𝐱_𝑖 ⊺𝐧_𝑖 • 各 𝑔_𝑖 を現在位置で評価したときの誤差を最小化： 𝑖=1 𝑁 𝑤_𝑖 𝐱 𝑓 𝐱 − 𝑔_𝑖 𝐱 2 26 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑎 𝑏 𝑐 𝑑 𝑔₁ 𝐱 𝑔₂ 𝐱 𝑔_𝑁 𝐱 ・・・・・・ = 𝑤₁(𝐱) 𝑤₂(𝐱) 𝑤_𝑁(𝐱) 𝑤₁(𝐱) 𝑤₂(𝐱) 𝑤_𝑁(𝐱)

(27)

法線制約の導入

27

法線制約を利用法線方向にオフセットして値を制約

Interpolating and Approximating Implicit Surfaces from Polygon Soup [Shen SIGGRAPH04]

(28)

Radial Basis Function による補間

(放射基底関数)

(29)

基本的な考え方

• 関数 𝑓(𝐱) を、基底関数 𝜙(𝐱) の重み付き和として定義： 𝑓 𝐱 = 𝑖=1 𝑁 𝑤_𝑖𝜙(𝐱 − 𝐱_𝑖) • 放射基底関数 𝜙(𝐱)：𝐱 の長さのみに依存 • 𝜙 𝐱 = 𝑒− 𝐱 2/𝜎2 (Gaussian) • 𝜙 𝐱 = 1 𝐱 2+𝑐2 (Inverse Multiquadric) • 各データ点における制約 𝑓 𝐱_𝑖 = 𝑓_𝑖 から、重み係数 𝑤_𝑖 を求める 29 基底関数をデータ位置 𝐱_𝑖 に平行移動

(30)

基本的な考え方

30 𝑓 𝐱₁ = 𝑤₁𝜙_1,1 + 𝑤₂𝜙_1,2 + ⋯ + 𝑤_𝑁𝜙_1,𝑁 = 𝑓₁ 𝑓 𝐱₂ = 𝑤₁𝜙_2,1 + 𝑤₂𝜙_2,2 + ⋯ + 𝑤_𝑁𝜙_2,𝑁 = 𝑓₂ 𝑓 𝐱_𝑁 = 𝑤₁𝜙_𝑁,1 + 𝑤₂𝜙_𝑁,2 + ⋯ + 𝑤_𝑁𝜙_𝑁,𝑁 = 𝑓_𝑁 𝜙_𝑖,𝑗 = 𝜙 𝐱_𝑖 − 𝐱_𝑗 と表記する・・・これを解けば良い 𝜙_1,1 𝜙_1,2 𝜙_1,𝑁 𝜙_2,1 𝜙_2,2 𝜙_2,𝑁 𝜙_𝑁,1 𝜙_𝑁,2 𝜙_𝑁,𝑁 𝑤₁ 𝑤₂ 𝑤_𝑁 𝑓₁ 𝑓₂ 𝑓_𝑁 ・・・ = ・・・ Φ 𝐰 𝐟

(31)

Gaussian 基底関数を使う場合

• パラメタ 𝜎 の選び方によって、結果が大きく変わる！

• なるべく滑らかな結果を得るには？

31

𝜙 𝐱 = 𝑒− 𝐱 2/𝜎2

Scattered Data Interpolation for Computer Graphics [Anjyo SIGGRAPH14 Course]

𝜎

(32)

関数の

“曲がり具合” の尺度 (Thin-Plate Energy)

• 2 階微分 (＝曲率) の大きさを空間全体で積分したもの： 𝐸₂ 𝑓 = 𝐱∈ℝ𝑑 Δ𝑓(𝐱) 2𝑑𝐱 • 1 次元空間の場合： 𝐸₂ 𝑓 = 𝑥∈ℝ 𝑓′′ 𝑥 2𝑑𝑥 • 2 次元空間の場合： 𝐸₂ 𝑓 = 𝐱∈ℝ2 𝑓_xx 𝐱 2 + 2𝑓_xy 𝐱 2 + 𝑓_yy 𝐱 2 𝑑𝐱 • 3 次元空間の場合： 𝐸₂ 𝑓 = 𝐱∈ℝ3 𝑓_xx 𝐱 2 + 𝑓_yy 𝐱 2 + 𝑓_zz 𝐱 2 + 2𝑓_xy 𝐱 2 + 2𝑓_yz 𝐱 2 + 2𝑓_zx 𝐱 2 𝑑𝐱 32

(33)

数学分野の知見

• 制約 𝑓 𝐱_𝑖 = 𝑓_𝑖 を満たす関数全体のうち、𝐸₂ を最小化する関数は以下の基底を使った RBF として表せる： • 1 次元空間の場合：𝜙 𝑥 = 𝑥 3 • 2 次元空間の場合：𝜙 𝐱 = 𝐱 2 log 𝐱 • 3 次元空間の場合：𝜙 𝐱 = 𝐱 • 参考 • 有限要素法の場合：離散化した領域上で 𝐸₂ を最小化する 𝑓 を近似的に求める • RBF の場合：グリーン関数を使って 𝐸₂ を最小化する 𝑓 を解析的に求める 33

(34)

線形項の追加

• 𝐸₂[𝑓] は 2 階微分を使って定義される  任意の線形項 𝑝 𝐱 = 𝑎𝑥 + 𝑏𝑦 + 𝑐𝑧 + 𝑑 を加えても不変： 𝐸₂ 𝑓 + 𝑝 = 𝐸₂[𝑓] • 線形項を未知数に含めることで、関数を一意に定める： 𝑓 𝐱 = 𝑖=1 𝑁 𝑤_𝑖 𝜙 𝐱 − 𝐱_𝑖 + 𝑎𝑥 + 𝑏𝑦 + 𝑐𝑧 + 𝑑 34

(35)

線形項の追加

35 𝑓 𝐱₁ = 𝑤₁𝜙_1,1 + 𝑤₂𝜙_1,2 + ⋯ + 𝑤_𝑁𝜙_1,𝑁 + 𝑎𝑥₁ + 𝑏𝑦₁ + 𝑐𝑧₁ + 𝑑 = 𝑓₁ 𝑓 𝐱₂ = 𝑤₁𝜙_2,1 + 𝑤₂𝜙_2,2 + ⋯ + 𝑤_𝑁𝜙_2,𝑁 + 𝑎𝑥₂ + 𝑏𝑦₂ + 𝑐𝑧₂ + 𝑑 = 𝑓₂ 𝑓 𝐱_𝑁 = 𝑤₁𝜙_𝑁,1 + 𝑤₂𝜙_𝑁,2 + ⋯ + 𝑤_𝑁𝜙_𝑁,𝑁 + 𝑎𝑥_𝑁 + 𝑏𝑦_𝑁 + 𝑐𝑧_𝑁 + 𝑑 = 𝑓_𝑁 ・・・ 𝜙_1,1 𝜙_1,2 𝜙_1,𝑁 𝑥₁ 𝑦₁ 𝑧₁ 1 𝜙_2,1 𝜙_2,2 𝜙_2,𝑁 𝑥₂ 𝑦₂ 𝑧₂ 1 𝜙_𝑁,1 𝜙_𝑁,2 𝜙_𝑁,𝑁 𝑥_𝑁 𝑦_𝑁 𝑧_𝑁 1 𝑤₁ 𝑤₂ 𝑤_𝑁 𝑎 𝑏 𝑐 𝑑 𝑓₁ 𝑓₂ 𝑓_𝑁 ・・・・・・ = ・・・ Φ 𝐰 𝐟 P 𝐜 4 個の未知数 𝑎, 𝑏, 𝑐, 𝑑 が追加されたので、 4 個の制約を追加する必要がある

(36)

追加の制約条件：線形関数の再現性

• 「全てのデータ点の制約 𝐱_𝑖, 𝑓_𝑖 がある線形関数からのサンプリングであるとき、RBF による補間結果はその線形関数と一致する」 • これを満たすための条件： • _𝑖=1𝑁 𝑤_𝑖 = 0 • _𝑖=1𝑁 𝑥_𝑖𝑤_𝑖 = 0 • _𝑖=1𝑁 𝑦_𝑖𝑤_𝑖 = 0 • _𝑖=1𝑁 𝑧_𝑖𝑤_𝑖 = 0 36 𝜙_1,1 𝜙_1,2 𝜙_1,𝑁 𝑥₁ 𝑦₁ 𝑧₁ 1 𝜙_2,1 𝜙_2,2 𝜙_2,𝑁 𝑥₂ 𝑦₂ 𝑧₂ 1 𝜙_𝑁,1 𝜙_𝑁,2 𝜙_𝑁,𝑁 𝑥_𝑁 𝑦_𝑁 𝑧_𝑁 1 𝑥₁ 𝑥₂ 𝑥_𝑁 0 0 0 0 𝑦₁ 𝑦₂ 𝑦_𝑁 0 0 0 0 𝑧₁ 𝑧₂ 𝑦_𝑁 0 0 0 0 1 1 1 0 0 0 0 𝑤₁ 𝑤₂ 𝑤_𝑁 𝑎 𝑏 𝑐 𝑑 𝑓₁ 𝑓₂ 𝑓_𝑁 0 0 0 0 ・・・・・・ = ・・・・・・ Φ P 𝐰 𝐟 𝐜 P⊺

(37)

勾配制約の導入

• 基底関数の勾配 𝛁𝜙 の重み付き和を導入： 𝑓 𝐱 = 𝑖=1 𝑁 𝑤_𝑖𝜙 𝐱 − 𝐱_𝑖 + 𝐯_𝑖⊺𝛁𝜙 𝐱 − 𝐱_𝑖 + 𝑎𝑥 + 𝑏𝑦 + 𝑐𝑧 + 𝑑 • 𝑓 の勾配： 𝛁𝑓 𝐱 = 𝑖=1 𝑁 𝑤_𝑖𝛁𝜙 𝐱 − 𝐱_𝑖 + H𝜙 𝐱 − 𝐱_𝑖 𝐯_𝑖 + 𝑎 𝑏 𝑐 • 勾配の制約 𝛁𝑓 𝐱_𝑖 = 𝐧_𝑖 を追加 37 H𝜙 = 𝜙_xx 𝜙_xy 𝜙_xz 𝜙_yx 𝜙_yy 𝜙_yz 𝜙_zx 𝜙_zy 𝜙_zz

(38)

勾配の制約： 𝛁𝑓 𝐱₁ = 𝑤₁𝛁𝜙_1,1 + H𝜙_1,1𝐯₁ + 𝑤₂𝛁𝜙_1,2 + H𝜙_1,2𝐯₂ + ⋯ + 𝑤_𝑁𝛁𝜙_1,𝑁 + H𝜙_1,𝑁𝐯_𝑁 + 𝑎 𝑏 𝑐 = 𝐧1 値の制約： 𝑓 𝐱₁ = 𝑤₁𝜙_1,1 + 𝐯₁⊺𝛁𝜙_1,1 + 𝑤₂𝜙_1,2 + 𝐯₂⊺𝛁𝜙_1,2 + ⋯ + 𝑤_𝑁𝜙_1,𝑁 + 𝐯_𝑁⊺ 𝛁𝜙_1,𝑁 + 𝑎𝑥₁ + 𝑏𝑦₁ + 𝑐𝑧₁ + 𝑑 = 𝑓₁

勾配制約の導入

• 1 番目のデータ点について： 38

Hermite Radial Basis Functions Implicits [Macedo CGF10]

𝐧₁ 𝑓₁ 𝜙_1,1 _𝛁𝜙_1,1 ⊺ H𝜙_1,1 𝛁 𝜙 1,1 𝜙_1,2 _𝛁𝜙_1,2 ⊺ H𝜙_1,2 𝛁 𝜙 1,2 𝜙_1,𝑁 _𝛁𝜙_1,𝑁 ⊺ H𝜙_1,𝑁 𝛁 𝜙 1,𝑁 𝑥₁ 𝑦₁ 𝑧₁ 1 1 0 0 0 0 1 0 0 0 0 1 0 ・・・ P₁ = 𝑤₁ 𝐯₁ 𝐯₂ 𝑤₂ ・・・ 𝐯_𝑁 𝑤_𝑁 𝑎 𝑏 𝑐 𝑑 Φ_1,1 Φ_1,2 Φ_1,𝑁

(39)

39 𝐧₁ 𝑓₁ = 𝑤₁ 𝐯₁ 𝐯₂ 𝑤₂ ・・・ 𝐯_𝑁 𝑤_𝑁 𝑎 𝑏 𝑐 𝑑 P₁ Φ_1,1 Φ_1,2 Φ_1,𝑁 ・・・・・・ P₂ Φ_2,1 Φ_2,2 Φ_2,𝑁 P_𝑁 Φ_𝑁,1 Φ_𝑁,2 Φ_𝑁,𝑁 ・・・ 𝑃₁⊺ 𝑃₂⊺ 𝑃_𝑁⊺ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 𝐧₂ 𝑓₂ 𝐧_𝑁 𝑓_𝑁 ・・・・・・

(40)

比較

40

(41)

参考サーベイ等

• State of the Art in Surface Reconstruction from Point Clouds [Berger EG14 STAR]

• A survey of methods for moving least squares surfaces [Cheng PBG08]

• Scattered Data Interpolation for Computer Graphics [Anjyo SIGGRAPH14 Course]

• An as-short-as-possible introduction to the least squares, weighted least squares and moving least squares for scattered data

approximation and interpolation [Nealen TechRep04]

(42)

参考ページ

• http://en.wikipedia.org/wiki/Implicit_surface • http://en.wikipedia.org/wiki/Radial_basis_function • http://en.wikipedia.org/wiki/Thin_plate_spline • http://en.wikipedia.org/wiki/Polyharmonic_spline 42