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

Size: px

Start display at page:

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

ゆあさかいざわ
5 years ago
Views:

1 コンピュータグラフィクス論モデリング (3) 2016 年 4 月 28 日高山健志

2 ソリッドモデリング 2

3 ソリッドモデルとは一枚のポリゴンで薄い形状を表現向き付け不可能 3D 空間の任意の位置でモデルの内側と外側が定義できるもの穴が空いている自己交差しているソリッドでないケース Klein bottle 主な用途 3D プリント物理シミュレーション 3

4 ソリッドモデルの predicate 関数 3D 座標 p R 3 がソリッドモデルの内部であれば true をそうでなければ false を返す関数 f p : R 3 true, false モデル内部全体を表す集合 : p f p = true } R 3 例 : 点 c を中心とした半径 r の球最小と最大の対角コーナーがそれぞれ x min, y min, z min と x max, y max, z max であるような直方体 f p p c < r c r f x, y, z x min < x < x max p max y min < y < y max z min < z < z max p min 4

5 Constructive Solid Geometry (Boolean 演算 ) 和 f A B p f A (p) f B (p) A B C D E 積 f A B p f A (p) f B (p) 差 f A B p f A (p) f B (p) A B C CSG Tree D 5 E

6 符号付き距離場によるソリッドモデル表現各点からモデル表面までの最短距離を表す関数 d p : R 3 R 符号付き : 内側では負外側では正対応する predicate: f p d(p) < 0 点 c を中心とした半径 r の球 d p p c r ゼロ等値面はモデル表面を表す :{p d(p) = 0} R 3 陰関数表現ボリューム表現 c r 勾配 d(p) は法線方向と一致 6

7 陰関数のデザイン例必ずしも距離関数とは限らない大半径 R, 小半径 a のトーラス 7

8 陰関数のデザイン例 : 等電位面 (Metaball) c 4 c 3 d i p = q i r p c i c 1 d p = d 1 p + d 2 p + d 3 p + d 4 p i c 2 d p = d 1 p + d 2 (p) d p = d 1 p d 2 (p) 8

陰関数の線形補間によるモーフィング d 1 p = 0 2 3 d 1 p + 1 3 d

9 陰関数の線形補間によるモーフィング d 1 p = d 1 p d 2 p = d 1 p d 2 p = 0 d 2 p = 0 9

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

(3) 関数値の線形補間から面の位置を決定最も有名 ( 特許問題でも ) Marching Cubes: A High

11 陰関数の表示方法 :Marching Cubes 等値面を三角形メッシュとして抽出立方体格子の各セルに対し (1) 立方体の 8 頂点で関数値を計算 (2) その正負のパターンから生成する面のタイプを決定対称性から 15 通りに分類 (3) 関数値の線形補間から面の位置を決定最も有名 ( 特許問題でも ) Marching Cubes: A High Resolution 3D Surface Construction Algorithm [Lorensen SIGGRAPH87] 11

12 Marching Cubes の曖昧性隣接するセルの間で面が整合しない不整合を解決する新たなルール The asymptotic decider: resolving the ambiguity in marching cubes [Nielson VIS91] 12

13 Marching Tetrahedra 立方体の代わりに四面体を使うパターンが少なく曖昧性が無い実装が簡単各立方体セルを 6 個の四面体に分割 ( 隣接セル間で分割の向きを合わせることに注意 ) きれいな三角形メッシュを取り出す工夫 Regularised marching tetrahedra: improved iso-surface extraction [Treece C&G99] 13

シャープなエッジを保持した等値面抽出格子サイズ :65 65 65 改善版 ( 陰関数の勾配も考慮 ) Marching Cubes 改善版 Marching Cubes ( 陰関数の値のみ考慮 ) Feature Sensitive Surface

14 シャープなエッジを保持した等値面抽出格子サイズ : 改善版 ( 陰関数の勾配も考慮 ) Marching Cubes 改善版 Marching Cubes ( 陰関数の値のみ考慮 ) Feature Sensitive Surface Extraction from Volume Data [Kobbelt SIGGRAPH01] Dual Contouring of Hermite Data [Ju SIGGRAPH02] 14

サーフェスメッシュ表現のみに基づく CSG ボリューム表現 (=Marching Cubes による等値面抽出 )

浮動小数の丸め誤差厳密に同じ位置で重複する複数の三角形ここ数年で著しく進化 Fast, exact, linear booleans

Meshes [Campen EG10] Mesh Arrangements for Solid Geometry [Zhou

15 サーフェスメッシュ表現のみに基づく CSG ボリューム表現 (=Marching Cubes による等値面抽出 ) 近似精度が格子の向きや解像度に依存サーフェスメッシュ表現による CSG 元のメッシュの形状を確実に保持ロバストで効率的な実装が難しい浮動小数の丸め誤差厳密に同じ位置で重複する複数の三角形ここ数年で著しく進化 Fast, exact, linear booleans [Bernstein SGP09] Exact and Robust (Self-)Intersections for Polygonal Meshes [Campen EG10] Mesh Arrangements for Solid Geometry [Zhou SIGGRAPH16] 15

16 メッシュの補修 (mesh repair) ボリューム表現四方八方から飛ばしたレイとの交差に基づいて内外を判定サーフェス表現定義を拡張した winding number に基づいて内外を判定 Simplification and Repair of Polygonal Models Using Volumetric Techniques [Nooruddin TVCG03] Robust Inside-Outside Segmentation using Generalized Winding Numbers [Jacobson SIGGRAPH13] 16

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

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

19 点群からのサーフェス形状再構成入力 :N 個の点群データ座標 x i = x i, y i, z i と法線 n i = n x y i, n i, z ni, i 1,, N 出力 : 関数 f(x) で値と勾配の制約を満たすもの f i f x i = 0 f x i = n i 等値面 f x = 0 が出力サーフェス形状 Scattered Data Interpolation と呼ばれる問題 Moving Least Squares Radial Basis Function CG 以外の分野 (e.g. 機械学習 ) でも重要 19

20 勾配を制約する二通りの方法法線方向にオフセットした位置に値の制約を追加簡単数学表現そのものに勾配制約を取り入れる ( エルミート補間 ) 高品質値と勾配の制約エルミート補間オフセット法 Modelling with implicit surfaces that interpolate [Turk TOG02] Hermite Radial Basis Functions Implicits [Macedo CGF10] 20

21 Moving Least Squares による補間 ( 移動最小二乗 ) 21

22 出発点 :Least SQuares ( 最小二乗 ) 求めたい関数が線形だと仮定する :f x = ax + by + cz + d a, b, c, d が未知係数 x (x, y, z) データ点における値の制約 f x 1 = ax 1 + by 1 + cz 1 + d = f 1 f x 2 = ax 2 + by 2 + cz 2 + d = f 2 f x N = ax N + by N + cz N + d = f N x 1 y 1 z 1 1 x 2 y 2 z 2 1 f 1 f 2 A a b c c d = f x N y N z N 1 f N ( 勾配制約は今は考えない ) 22

23 Overconstrained System # 未知数 < # 制約 (i.e. 縦長の行列 ) 全ての制約を同時に満たせない A c f A c A = = A f fitting の誤差を最小化 : A c f 2 = N i=1 f x i f i 2 c = A A 1 f A 23

24 LSQ の幾何的な解釈 q r d p x q x α p y q y = β p z q z r x r y r z β α p p と q が張る空間中で r に最も近い点を求める ( 投影する ) ことに相当 fitting 誤差は投影距離に相当 : d 2 = αp + βq r 2 24

25 Weighted Least Squares ( 重み付き最小二乗 ) 各データ点ごとの誤差に重み w i をつける重要度確信度以下の誤差を最小化 : N i=1 w i f x i f i 2 w 1 w2 W w N x 1 y 1 z 1 1 x 2 y 2 z 2 1 A a b c c d = W f x N y N z N 1 w 1 w2 w N f 1 f 2 f N 25

26 Weighted Least Squares ( 重み付き最小二乗 ) W A c = W f c = A W 2 A 1 f A W 2 26

27 Moving Least Squares ( 移動最小二乗 ) 重み w i が評価位置 x に依存 : w i x = w( x x i ) よく使われる関数 (Kernel): w r = e r2 /σ 2 w r = 1 r 2 +ε 2 評価位置に近いほど大きな重み重み行列 W が x に依存係数 a, b, c, d が x に依存 f x = x y z 1 a(x) b(x) c(x) d(x) A W x 2 A 1 A W x 2 f 27

28 法線制約の導入各データ点が表す 1 次式を考える : g i x = f i + x x i n i 各 g i を現在位置で評価したときの誤差を最小化 : N i=1 w i x f x g i x 2 w 1 (x) w 2 (x) w N (x) x y z 1 x y z 1 x y z 1 a b c d = w 1 (x) w 2 (x) w N (x) g 1 x g 2 x g N x Interpolating and Approximating Implicit Surfaces from Polygon Soup [Shen SIGGRAPH04] 28

29 法線制約の導入法線制約を利用法線方向にオフセットして値を制約 Input : Polygon Soup Interpolation Approximation 1 Approximation 2 Approximation 3 Interpolating and Approximating Implicit Surfaces from Polygon Soup [Shen SIGGRAPH04] 29

30 Radial Basis Function による補間 ( 放射基底関数 ) 30

31 基本的な考え方関数 f(x) を基底関数 φ(x) の重み付き和として定義 : f x = N i=1 w i φ(x x i ) 基底関数をデータ位置 x i に平行移動放射基底関数 φ(x):x の長さのみに依存 φ x = e x 2 /σ 2 (Gaussian) φ x = 1 x 2 +c 2 (Inverse Multiquadric) 各データ点における制約 f x i = f i から重み係数 w i を求める 31

32 基本的な考え方 φ i,j = φ x i x j と表記する f x 1 = w 1 φ 1,1 + w 2 φ 1,2 + + w N φ 1,N = f 1 f x 2 = w 1 φ 2,1 + w 2 φ 2,2 + + w N φ 2,N = f 2 φ 1,1 φ 1,2 φ 2,1 φ 2,2 φ 1,N φ 2,N w 1 w 2 f 1 f 2 Φ w = f φ N,1 φ N,2 φ N,N w N f N f x N = w 1 φ N,1 + w 2 φ N,2 + + w N φ N,N = f N これを解けば良い 32

33 Gaussian 基底関数を使う場合 φ x = e x 2 /σ 2 パラメタ σ の選び方によって結果が大きく変わる! σ 小なるべく滑らかな結果を得るには? 大 Scattered Data Interpolation for Computer Graphics [Anjyo SIGGRAPH14 Course] 33

34 関数の曲がり具合の尺度 (Thin-Plate Energy) 2 階微分 (= 曲率 ) の大きさを空間全体で積分したもの : E 2 f = x R d Δf(x) 2 dx 1 次元空間の場合 : E 2 f = f x 2 dx x R 2 次元空間の場合 : E 2 f = x R 2 f xx x 2 + 2f xy x 2 + f yy x 2 dx 3 次元空間の場合 : E 2 f = x R 3 f xx x 2 + f yy x 2 + f zz x 2 + 2f xy x 2 + 2f yz x 2 + 2f zx x 2 dx 34

35 数学分野の知見制約 f x i = f i を満たす関数全体のうち E 2 を最小化する関数は以下の基底を使った RBF として表せる : 1 次元空間の場合 :φ x = x 3 2 次元空間の場合 :φ x = x 2 log x 3 次元空間の場合 :φ x = x 参考有限要素法の場合 : 離散化した領域上で E 2 を最小化する f を近似的に求める RBF の場合 : グリーン関数を使って E 2 を最小化する f を解析的に求める Scattered Data Interpolation for Computer Graphics [Anjyo SIGGRAPH14 Course] 35

36 線形項の追加 E 2 [f] は 2 階微分を使って定義される任意の線形項 p x = ax + by + cz + d を加えても不変 : E 2 f + p = E 2 [f] 線形項を未知数に含めることで関数を一意に定める : f x = N i=1 w i φ x x i + ax + by + cz + d 36

37 線形項の追加 f x 1 = w 1 φ 1,1 + w 2 φ 1,2 + + w N φ 1,N + ax 1 + by 1 + cz 1 + d = f 1 f x 2 = w 1 φ 2,1 + w 2 φ 2,2 + + w N φ 2,N + ax 2 + by 2 + cz 2 + d = f 2 f x N = w 1 φ N,1 + w 2 φ N,2 + + w N φ N,N + ax N + by N + cz N + d = f N φ 1,1 φ 1,2 φ 1,N x 1 y 1 z 1 1 φ 2,1 φ 2,2 φ 2,N x 2 y 2 z 2 1 Φ P φ N,1 φ N,2 φ N,N x N y N z N 1 w 1 w 2 w w N a b cc d = f 1 f 2 f f N 4 個の未知数 a, b, c, d が追加されたので 4 個の制約を追加する必要がある 37

38 追加の制約条件 : 線形関数の再現性全てのデータ点の制約 x i, f i がある線形関数からのサンプリングであるとき RBF による補間結果はその線形関数と一致するこれを満たすための条件 : N i=1 w i = 0 N i=1 x i w i = 0 N i=1 y i w i = 0 N i=1 z i w i = 0 φ 1,1 φ 1,2 φ 1,N x 1 y 1 z 1 1 φ 2,1 φ 2,2 φ 2,N x 2 y 2 z 2 1 φ N,1 φ N,2 φ N,N x N y N z N 1 x 1 x 2 x N y 1 y 2 y N P z 1 z 2 y N w 1 w 2 Φ P w f w N a b cc d = f 1 f 2 f N Scattered Data Interpolation for Computer Graphics [Anjyo SIGGRAPH14 Course] 38

39 勾配制約の導入基底関数の勾配 φ の重み付き和を導入 : f x = N i=1 w i φ x x i + v i φ x x i + ax + by + cz + d f の勾配 : f x = N i=1 w i φ x x i + Hφ x x i v i + a b c 勾配の制約 f x i = n i を追加 Hφ = φ xx φ xy φ xz φ yx φ yy φ yz φ zx φ zy φ zz Hermite Radial Basis Functions Implicits [Macedo CGF10] Hessian 行列 39

40 w 1 勾配制約の導入 v 1 1 番目のデータ点について : 値の制約 : f x 1 = w 1 φ 1,1 + v 1 φ 1,1 + w 2 φ 1,2 + v 2 φ 1,2 + + w N φ 1,N + v N φ 1,N + ax 1 + by 1 + cz 1 + d = f 1 w 2 v 2 勾配の制約 : f x 1 = w 1 φ 1,1 + Hφ 1,1 v 1 + w 2 φ 1,2 + Hφ 1,2 v w N φ 1,N + Hφ 1,N v N + φ 1,1 φ 1,1 φ 1,1 Hφ 1,1 φ 1,2 φ 1,2 φ 1,2 Hφ 1,2 φ 1,N Hermite Radial Basis Functions Implicits [Macedo CGF10] φ 1,N φ 1,N Φ 1,1 Φ 1,2 Φ 1,N Hφ 1,N x 1 y 1 z P = w N v N a b c d a b c = n 1 f 1 n 1 40

41 w 1 f 1 Φ 1,1 Φ 1,2 Φ 1,N P 1 v 1 n 1 w 2 f 2 Φ 2,1 Φ 2,2 Φ 2,N P 2 v 2 n 2 = w N f N Φ N,1 Φ N,2 Φ N,N P N v N n N P 1 P 2 P N a b c d

42 比較勾配を制約オフセットして値を制約 42

43 参考サーベイ等 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] 43

44 参考ページ

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

コンピュータグラフィクス論モデリング (3) 2015 年 4 月 30 日高山健志陰関数表現による形状モデリング 3D 空間上のスカラー場 F x, y, z に対し F x, y, z = 0 で定義されるサーフェス別名 : ゼロ等値面陰関数 ( ボリューム ) 表現サーフェス表現 F p が正 ( 負 ) のとき p は物体の外部 ( 内部 ) 勾配 F は法線方向に一致 F(p)