ベジエ曲面の輪郭線(シルエット)抽出

1.輪郭線の条件

曲面を眺めたとき、その外形を縁取る線を輪郭線(シルエット、occluding contour)といいます。曲面上の点が輪郭線に乗るのは、その点の法線が視線と直交するとき、つまり面が視線に対してちょうど真横を向いた瞬間です。視点を E とすると、条件は次の1本の式で書けます。

f(u,v) = ( S(u,v) − E ) · N(u,v) = 0   N(u,v) = Su × Sv

f > 0 の領域と f < 0 の領域がそれぞれ裏向きの面と表向きの面に対応し、その境界が輪郭線です。平行投影であれば視線方向 D は一定なので、条件は f(u,v) = D · N(u,v) = 0 とさらに簡単になります。

視点 E 法線 N 輪郭線上の点 f = 0 輪郭線上の点 f = 0 表向き f < 0 裏向き f > 0
断面で見たところ。視点からの接線が接する点が輪郭線上の点で、そこでは法線が視線と直交する。

この式の重要な性質は、E を光源の位置に置き換えると、そのまま明暗境界線(ターミネータ)の条件になることです。輪郭線・影の境界・ハイライト線(D·N = 一定)は、すべて同じ関数の等値集合として統一的に扱えます。

2.f(u,v) がベジエ関数になること

ベジエクリッピング法を使う前提は、対象がベジエ関数として表せることです。f(u,v) は積と差だけでできているので、ベジエ関数どうしの積の公式

( Σ aiBip )( Σ bkBkr ) = Σm [ Σi+k=m pCi · rCk / p+rCm · aibk ] Bmp+r

を繰り返し適用すれば、f の制御係数を厳密に求められます。双3次パッチ(3×3次)の場合、次数は次のように上がります。

次数(u×v)備考
S(u,v)3×3元の曲面
Su2×3u 方向の微分で u の次数が1下がる
Sv3×2同様
N = Su×Sv5×5外積=積の差なので次数が加算される
f = (S−E)·N8×8透視投影。係数は 9×9 = 81 個
f = D·N5×5平行投影・平行光源。定数ベクトルとの内積なので次数は上がらない

なぜ「係数を厳密に求める」ことが重要か

平面による断面抽出では f = n·S − d が点について線形だったため、制御点 Pij にそのまま n·Pij − d を当てはめれば f の係数になりました。しかし輪郭線の f は法線 N を含むため制御点について3次の式であり、この近道は使えません。制御点における値を並べただけでは f の係数にならず、凸包性が成立しないので「全部同符号だから輪郭線なし」という判定が誤ったものになってしまいます。積の公式で正しい係数を組み立てて初めて、次節の棄却判定が保証つきになります。

3.ベジエクリッピング法による抽出手順

交点計算と違い、求める解は点ではなく曲線(零集合)です。したがって「解の位置を1点に追い込む」のではなく、「解が通り得ない領域を確実に削り落とし、解の周囲だけを細かくする」という使い方になります。

  1. 凸包による棄却 f の制御係数がすべて正、またはすべて負なら、凸包性よりそのパッチ上で f は決して 0 にならないので、輪郭線は存在しません。符号を見るだけの判定です。実際のモデルでは大半のパッチが完全に表向きか裏向きなので、ほとんどがこの1回の判定で捨てられます
  2. 包絡線によるUV範囲の収縮 符号が混在する場合、u を固定すると f は各 u 列の係数の凸結合になります。よって列ごとの最小係数を制御点とするベジエ関数 L(u) と、最大係数によるベジエ関数 U(u) が f の安全な下限・上限を与えます。L(u) ≤ 0 になり得る範囲U(u) ≥ 0 になり得る範囲の共通部分の外では f = 0 は絶対に起こらないので、そこまで一気に u 範囲を縮められます。v 方向も同様です。これが本来のベジエクリッピング(FAT Line によるクリップ)の2変数版にあたります。
  3. 分割と再帰 範囲が十分縮まればその部分パッチを de Casteljau で切り出して再帰します。縮まらない場合(零集合がパッチを大きく横切る場合など)は4分割して各象限に再帰します。
  4. 末端で零集合を線分化 十分小さくなったパッチの内部を細かい格子で評価し、マーチングスクエア法によって f = 0 の等値線を線分として取り出します。境界上に限れば f は1変数のベジエ関数になるので、より高い精度が必要ならここも通常のベジエクリッピングで厳密に交点を求められます。
u →v ↓凸包で棄却 9 / クリップで収縮 15 / 末端 22 (緑=f=0 の零集合)
UVパラメータ空間で見た判定の様子(ティーポットの1パッチ)。赤=凸包で棄却された領域、橙=クリップで収縮した範囲、青=末端パッチ、濃緑=実際の零集合 f=0。末端パッチが零集合のまわりだけに集中しているのが分かる。

取りこぼしが起こらないこと

この手法の要は、②③で捨てる領域が「f が 0 になり得ないことが数学的に保証された領域」だけである点です。したがって、どんなに細い枝や小さな閉ループであっても見落としません。サンプリングに基づく手法では、格子の目を細かくしても「たまたま格子点の間をすり抜けた」輪郭が消えてしまう可能性を排除できませんが、ベジエクリッピング法ではその心配がありません。

4.実行例

楕円体(8パッチ)
トーラス(8パッチ)— 内側の穴の輪郭も抽出される
ユタティーポット(32パッチ)— 注ぎ口・取っ手・蓋のつまみまで

いずれも上記のアルゴリズムをそのまま実行した結果です。隠線消去を行っていないため、裏側の輪郭線も描かれています。トーラスの内側の輪郭のように、外形線ではない内部の輪郭(内部シルエット)も同じ処理で自動的に得られる点に注意してください。物体の外形だけを求める手法ではなく、曲面上で法線が視線と直交する点の集合をすべて求める手法だからです。

▶ 実演プログラム 視点をドラッグして回転させながら、輪郭線がリアルタイムに再計算される様子を確認できます。凸包による棄却率、包絡線クリップの収縮回数、計算時間が統計として表示され、クリップの ON / OFF による判定ノード数の違いも比較できます。
bezier_surface_silhouette.html を開く

5.従来法との比較

(a) ポリゴン近似による方法(最も一般的)

曲面を三角形メッシュに分割し、隣り合う2面の表裏が食い違う稜線を輪郭エッジとして拾う方法です。実装が簡単でGPUとも相性がよく、リアルタイムCGでは事実上の標準です。ガウス写像や法線錐を使った階層構造で、輪郭を含み得ない部分をまとめて棄却する高速化も広く使われています。

弱点は、結果が分割の細かさに完全に依存することです。得られる輪郭はポリゴンの稜線をつないだ折れ線なので拡大すると角張り、分割が粗ければ細部の輪郭が丸ごと消え、逆に細かすぎると平坦部でも微小な偽の輪郭が出ます。視点を動かすと輪郭エッジの集合が不連続に切り替わるため、アニメーションでちらつきが生じることもあります。

(b) 数値追跡法(予測子・修正子)

まず f = 0 を満たす点をニュートン法などで1点見つけ、そこから輪郭曲線の接線方向に少しずつ進んでは修正する、という方法です。滑らかな曲線が直接得られ、1本の輪郭を追う分には高速です。

弱点は開始点の網羅性です。独立した閉ループが別の場所にあっても、そこに開始点が見つからなければ丸ごと見落とします。また輪郭曲線が自己交差したり尖点を持ったりする箇所で追跡が破綻しやすく、分岐の処理に個別の場合分けが必要になります。

(c) パラメータ空間の一様サンプリング

u,v 空間を一様な格子で刻んで f を評価し、マーチングスクエアで等値線を得る方法です。単純で堅実ですが、精度を上げようとすると評価点数が格子の2乗で増え、しかも格子の間をすり抜ける輪郭を原理的に排除できません。ベジエクリッピング法は、この方法の「末端処理」だけを残し、その前段を凸包判定による確実な棄却に置き換えたものと見ることもできます。

(d) 画像空間の手法

深度バッファや法線バッファにエッジ検出フィルタをかける、あるいは背面ポリゴンを法線方向に少し押し出して描く方法です。極めて高速でリアルタイム描画向きですが、得られるのは画面解析の結果であって曲面上の曲線ではないため、画面解像度に依存し、線の太さを自在に制御したり図面データとして出力したりすることには向きません。

(e) 代数的手法

終結式やグレブナー基底で f = 0 を代数的に解く方法です。厳密ですが、8×8次の2変数多項式を扱うことになり、計算量と数値的安定性の両面で現実的ではありません。

手法取りこぼし精度特徴
ポリゴン近似あり得る分割依存簡単・高速。折れ線になる。視点変化でちらつく
数値追跡あり得る高い滑らかだが開始点の網羅と特異点の処理が難しい
一様サンプリングあり得る格子依存単純。精度を上げると急激に重くなる
画像空間画素依存最高速。曲面上の曲線としては得られない
代数的手法なし厳密高次では計算量・安定性が問題
ベジエクリッピングなし任意凸包性で確実に棄却。要求精度まで収束させられる

6.特異点と退化への注意

輪郭曲線が自己交差したり尖点を持ったりするのは、∂f/∂u = 0 かつ ∂f/∂v = 0 となる点です。これも連立ベジエ関数の零点なので、同じ枠組みで検出できます。輪郭線の位相を正しく構成したい場合(隠線消去など)には、この特異点をあらかじめ求めておくと安定します。

もう一点、制御点が縮退したパッチ(ティーポットの蓋の頂点のように、1辺の制御点がすべて同一点になっているもの)では、その辺上で N = 0 となるため f も 0 になり、輪郭線でない線が現れます。実用上は、N の大きさが十分小さい箇所を除外する処理を入れるか、縮退辺をあらかじめ登録しておく必要があります。

7.応用分野