曲面を眺めたとき、その外形を縁取る線を輪郭線(シルエット、occluding contour)といいます。曲面上の点が輪郭線に乗るのは、その点の法線が視線と直交するとき、つまり面が視線に対してちょうど真横を向いた瞬間です。視点を E とすると、条件は次の1本の式で書けます。
f > 0 の領域と f < 0 の領域がそれぞれ裏向きの面と表向きの面に対応し、その境界が輪郭線です。平行投影であれば視線方向 D は一定なので、条件は f(u,v) = D · N(u,v) = 0 とさらに簡単になります。
この式の重要な性質は、E を光源の位置に置き換えると、そのまま明暗境界線(ターミネータ)の条件になることです。輪郭線・影の境界・ハイライト線(D·N = 一定)は、すべて同じ関数の等値集合として統一的に扱えます。
ベジエクリッピング法を使う前提は、対象がベジエ関数として表せることです。f(u,v) は積と差だけでできているので、ベジエ関数どうしの積の公式
を繰り返し適用すれば、f の制御係数を厳密に求められます。双3次パッチ(3×3次)の場合、次数は次のように上がります。
| 量 | 次数(u×v) | 備考 |
|---|---|---|
| S(u,v) | 3×3 | 元の曲面 |
| Su | 2×3 | u 方向の微分で u の次数が1下がる |
| Sv | 3×2 | 同様 |
| N = Su×Sv | 5×5 | 外積=積の差なので次数が加算される |
| f = (S−E)·N | 8×8 | 透視投影。係数は 9×9 = 81 個 |
| f = D·N | 5×5 | 平行投影・平行光源。定数ベクトルとの内積なので次数は上がらない |
なぜ「係数を厳密に求める」ことが重要か
平面による断面抽出では f = n·S − d が点について線形だったため、制御点 Pij にそのまま n·Pij − d を当てはめれば f の係数になりました。しかし輪郭線の f は法線 N を含むため制御点について3次の式であり、この近道は使えません。制御点における値を並べただけでは f の係数にならず、凸包性が成立しないので「全部同符号だから輪郭線なし」という判定が誤ったものになってしまいます。積の公式で正しい係数を組み立てて初めて、次節の棄却判定が保証つきになります。
交点計算と違い、求める解は点ではなく曲線(零集合)です。したがって「解の位置を1点に追い込む」のではなく、「解が通り得ない領域を確実に削り落とし、解の周囲だけを細かくする」という使い方になります。
この手法の要は、②③で捨てる領域が「f が 0 になり得ないことが数学的に保証された領域」だけである点です。したがって、どんなに細い枝や小さな閉ループであっても見落としません。サンプリングに基づく手法では、格子の目を細かくしても「たまたま格子点の間をすり抜けた」輪郭が消えてしまう可能性を排除できませんが、ベジエクリッピング法ではその心配がありません。
いずれも上記のアルゴリズムをそのまま実行した結果です。隠線消去を行っていないため、裏側の輪郭線も描かれています。トーラスの内側の輪郭のように、外形線ではない内部の輪郭(内部シルエット)も同じ処理で自動的に得られる点に注意してください。物体の外形だけを求める手法ではなく、曲面上で法線が視線と直交する点の集合をすべて求める手法だからです。
曲面を三角形メッシュに分割し、隣り合う2面の表裏が食い違う稜線を輪郭エッジとして拾う方法です。実装が簡単でGPUとも相性がよく、リアルタイムCGでは事実上の標準です。ガウス写像や法線錐を使った階層構造で、輪郭を含み得ない部分をまとめて棄却する高速化も広く使われています。
弱点は、結果が分割の細かさに完全に依存することです。得られる輪郭はポリゴンの稜線をつないだ折れ線なので拡大すると角張り、分割が粗ければ細部の輪郭が丸ごと消え、逆に細かすぎると平坦部でも微小な偽の輪郭が出ます。視点を動かすと輪郭エッジの集合が不連続に切り替わるため、アニメーションでちらつきが生じることもあります。
まず f = 0 を満たす点をニュートン法などで1点見つけ、そこから輪郭曲線の接線方向に少しずつ進んでは修正する、という方法です。滑らかな曲線が直接得られ、1本の輪郭を追う分には高速です。
弱点は開始点の網羅性です。独立した閉ループが別の場所にあっても、そこに開始点が見つからなければ丸ごと見落とします。また輪郭曲線が自己交差したり尖点を持ったりする箇所で追跡が破綻しやすく、分岐の処理に個別の場合分けが必要になります。
u,v 空間を一様な格子で刻んで f を評価し、マーチングスクエアで等値線を得る方法です。単純で堅実ですが、精度を上げようとすると評価点数が格子の2乗で増え、しかも格子の間をすり抜ける輪郭を原理的に排除できません。ベジエクリッピング法は、この方法の「末端処理」だけを残し、その前段を凸包判定による確実な棄却に置き換えたものと見ることもできます。
深度バッファや法線バッファにエッジ検出フィルタをかける、あるいは背面ポリゴンを法線方向に少し押し出して描く方法です。極めて高速でリアルタイム描画向きですが、得られるのは画面解析の結果であって曲面上の曲線ではないため、画面解像度に依存し、線の太さを自在に制御したり図面データとして出力したりすることには向きません。
終結式やグレブナー基底で f = 0 を代数的に解く方法です。厳密ですが、8×8次の2変数多項式を扱うことになり、計算量と数値的安定性の両面で現実的ではありません。
| 手法 | 取りこぼし | 精度 | 特徴 |
|---|---|---|---|
| ポリゴン近似 | あり得る | 分割依存 | 簡単・高速。折れ線になる。視点変化でちらつく |
| 数値追跡 | あり得る | 高い | 滑らかだが開始点の網羅と特異点の処理が難しい |
| 一様サンプリング | あり得る | 格子依存 | 単純。精度を上げると急激に重くなる |
| 画像空間 | — | 画素依存 | 最高速。曲面上の曲線としては得られない |
| 代数的手法 | なし | 厳密 | 高次では計算量・安定性が問題 |
| ベジエクリッピング | なし | 任意 | 凸包性で確実に棄却。要求精度まで収束させられる |
輪郭曲線が自己交差したり尖点を持ったりするのは、∂f/∂u = 0 かつ ∂f/∂v = 0 となる点です。これも連立ベジエ関数の零点なので、同じ枠組みで検出できます。輪郭線の位相を正しく構成したい場合(隠線消去など)には、この特異点をあらかじめ求めておくと安定します。
もう一点、制御点が縮退したパッチ(ティーポットの蓋の頂点のように、1辺の制御点がすべて同一点になっているもの)では、その辺上で N = 0 となるため f も 0 になり、輪郭線でない線が現れます。実用上は、N の大きさが十分小さい箇所を除外する処理を入れるか、縮退辺をあらかじめ登録しておく必要があります。