7. 形状モデルとソリッドの表現

第4章から第6章では、形を動かし、投影し、ピクセルに変えてきましたが、コンピュータの中で「形」とは一体何なのかは一度も問いませんでした。
其れが此の章の主題で、モデリングを扱う3つの章の最初です。
形状モデルの3つの段階、ソリッドを記述する古典的な方法（プリミティブの集合演算、境界、スイープ）、CADプログラムが境界の上を素早く辿る為のデータ構造、全ての正しいソリッドが満たす数え上げの規則、そして稜線を面取りしたり丸めたりする局所的な操作を見ていきます。

何故此れが大事なのでしょうか？
3次元の形を作ったり使ったりするプログラムは全て、何らかの方法で其の形を保存しなければならず、其の選び方によって答えられる問いが決まります。
ゲームなら表面を描ければ十分ですが、CADプログラムは部品の体積、2つの部品がぶつかるかどうか、モデルを壊さずに稜線を丸める方法を知っていなければなりません。
検定対策としては、此の章は分野3の最初の3つのシラバス項目、形状モデル、ソリッドモデルの形状表現、境界表現のデータ構造と局所変形を扱います。
曲線と曲面は第8章で、ポリゴンメッシュ、ボクセル、八分木は第9章で扱うので、此処では指し示す必要がある所にだけ出てきます。

7.1 3種類の形状モデル

形状モデルとは、コンピュータが保存する、物体の形の記述です。
古典的なCADでは3つの段階を区別し、後の物ほど多くの情報を持ちます：

• ワイヤーフレームモデルは頂点と其の間の辺だけを保存します。3次元の線画です。
• サーフェスモデルは面も保存するので、物体の表面が何処にあるかは分かりますが、其の表面のどちら側が「内側」かは分かりません。
• ソリッドモデルは内側を知っています。空間の任意の点について、其の点が物体の内側か、外側か、表面上かを答えられます。

違いは小さく聞こえますが、出来る事を決めます。
立方体の12本の辺を見て下さい：

中身の詰まった立方体、蓋の無い箱、両端の開いた四角い筒は、全て全く同じ12本の辺を持っています。
辺は、どの辺の輪が面で埋まっているかを教えてくれないので、ワイヤーフレームモデルには此れらを区別出来ません。
画面上では2つ目の種類の曖昧さもあります。
ワイヤーフレームの線画には隠れ線が無いので、2つの正方形のどちらが手前なのかさえ分からず、見ている間に目が2つの解釈の間を行き来します。
サーフェスモデルは面を保存するので、1つ目の問題は無くなります。
しかし、蓋の無い箱が薄いボール紙なのか、空洞のある重いブロックなのかは、やはり分かりません。
「内側」がモデルに含まれていないからです。

従って、3つのモデルは別々の問いに答えます：

問い	ワイヤーフレーム	サーフェス	ソリッド
辺を素早く描く	出来る	出来る	出来る
陰影付きの面を描き、隠面を消す	出来ない	出来る	出来る
此の点は物体の内側か？	出来ない	出来ない	出来る
体積、質量、重心	出来ない	出来ない	出来る
2つの部品がぶつかるか（干渉チェック）	出来ない	表面が交わる所だけ	出来る
フライス盤の工具経路を作る（CAM）	出来ない	表面についてのみ	出来る

其々を見かける場所：

• ワイヤーフレームは最初の3次元CADの表示でした（ベクタースキャンの画面は線しか描けませんでした）。今でも全てのモデリングソフトの高速プレビュー表示や、ゲームエンジンの「辺を表示」機能として使われています。
• サーフェスモデルはゲームや映画が描く物です。三角形メッシュは陰影付けの為に表面だけあれば十分です。車のボディの様な自由曲面の形も、サーフェス（第8章の曲面パッチ）として設計されます。
• ソリッドモデルは機械系CAD、CAM、3Dプリント（プリンターは何を埋めるかを知る必要があります）、物理シミュレーションの土台です。

此の章の残りでは「ソリッド」は常にソリッドモデルを意味し、問題は其れをどう保存するかです。

7.2 CSG表現

最初の考え方は、職人が金属の塊に何かを付け足したり穴を開けたりして部品を作る様に、単純なソリッドから複雑なソリッドを組み立てる事です。
CSG表現（Constructive Solid Geometry）は、ソリッドを単純なプリミティブ（直方体、球、円柱、円錐、トーラス等。其々に大きさと配置があります）と、3つの集合演算の組み合わせとして記述します：

• 和 $A\cup B$：AかBに含まれる全て、
• 差 $A-B$：Aに含まれ、Bには含まれない全て、
• 積 $A\cap B$：両方に含まれる全て。

ソリッド全体はCSG木として保存します。
葉はプリミティブで、内部の各節点は其の2つの子に適用する集合演算です。
次の図は、2つの直方体と1つの円柱から作った小さなブラケットです：

3つのプリミティブは全てz方向に伸びた柱体なので、正面図で全てが分かります：

• 直方体A：$0\le x\le 5$、$0\le y\le 2$、$0\le z\le 1$（横の腕）、
• 直方体B：$0\le x\le 2$、$0\le y\le 5$、$0\le z\le 1$（縦の腕）、
• 円柱C：軸は$(3.5,1)$を通るz方向、半径0.6、$z=-0.5$から$z=1.5$まで。

ソリッドは$S=(A\cup B)-C$です。
円柱が板の厚さより長い事に注目して下さい。
此れはわざとで、理由はすぐ後で分かります。

点の内外判定：計算例

ソリッドに対する最も基本的な問いは「此の点は内側か？」で、CSGは其れに見事に答えます。
葉に聞き、其の答えを木の上へと組み合わせていくだけです。
此れを点の内外判定（point membership classification）と呼びます。
各プリミティブはin（内側）、on（表面上）、out（外側）の3つの値のどれかで答え、演算が其れらを組み合わせます：

• 和：どちらかの子がinならin、両方がoutならout、
• 差：左の子がinで右の子がoutならin、左がoutか右がinならout、
• 積：両方がinならin、どちらかがoutならout。

（onが関わる場合、答えは大抵onですが、1つだけ微妙な場合があり、後で戻ってきます。）
板の厚さの真ん中、$z=0.5$にある4つの点を判定してみましょう：

点	A	B	$A\cup B$	C	$S=(A\cup B)-C$
$p_1=(3.5,1,0.5)$	in	out	in	in	out
$p_2=(1,4,0.5)$	out	in	in	out	in
$p_3=(1,1,0.5)$	in	in	in	out	in
$p_4=(4,4,0.5)$	out	out	out	out	out

$p_1$を1段階ずつ追ってみます。
直方体A：、、で、全て厳密な不等号なのでinです。
直方体B：$3.5>2$なのでoutです。
和：inです。
円柱C：軸からの距離の2乗はで、なのでinです。
差：左の子はinですが右の子もinなのでoutです。
$p_1$は穴の中にあります。
$p_3$はAとBが重なる領域にありますが、和は単にinと答え、重なりは余計な手間無しに1回だけ数えられます。

同じ考え方で、境界を一度も計算せずにCSG木を直接レンダリングする事も出来ます。
各ピクセルを通るレイを飛ばし、其のレイが各プリミティブに入る所と出る所を求め、レイに沿って木全体の判定が「in」になる最初の点を取ります。
次のブラケットの絵は正に其の方法で作りました（CSG木のレイキャスティングは1982年のRothの論文に遡ります）：

正則化集合演算

普通の集合演算は、ソリッドに対して厄介な副作用を持ちます。
面で接する2つの直方体、$x=0$から$x=2$までのAと、$x=2$から$x=4$までのBを考えます。
普通の積$A\cap B$は空ではありません。
共有する面$x=2$、つまり体積の無い平らな薄膜です。
下の断面図では線分ですが、3次元では宙に浮いた面（dangling face）、つまりどちら側にもソリッドが無い面になります。
そんな物を部品と呼ぶ職人はいませんし、其処から作った境界表現は壊れています。

解決策は正則化集合演算で、星印を付けて書きます：

${\cup }^{\ast }$と${-}^{\ast }$も同様です。
$\mathrm{int}$は内部（境界を除いた集合）、上の線は閉包（集合に其の境界を加えた物）です。
内部を取ると厚さの無い物が全て捨てられ（共有する面には内部の点がありません）、閉包を取ると残った物に境界が戻ります。
接する直方体では$\mathrm{int}(A\cap B)$が空なので、$A{\cap }^{\ast }B$も空になり、職人の期待通りです。

図の2段目は問題のもう半分を示しています。
普通の差$A-B$では、Bの境界上の点もAから取り除かれるので、結果にはBが切った所の境界がありません。
閉じていない集合になりますが、ソリッドは自分の表面を含まなければなりません。
閉包の段階で其の境界が加え直されます。
要するに、正則化演算は常に正則集合、つまり其の内部の閉包に等しく、宙に浮いた面や辺や孤立した点を持たない集合を返します。
ソリッドモデリングでは正則化演算だけを使うので、此れ以降、ソリッドに対する$\cup$、$-$、$\cap$は正則化版を意味します。

ブラケットの円柱が板の両側に突き出しているのも此の為です。
もし円柱の長さが板の厚さと丁度同じなら、其の端の面は板の前面と背面に正確に重なり、僅かな丸め誤差次第で、穴の上に紙の様に薄い膜が残るかどうかが決まってしまいます。
切り取る道具を必要より少し長くするのは、CSGを使う人が早い段階で覚える習慣です。

そして、点の内外判定の微妙な場合です。
和の両方の子に対してonの点が、結果の内側にある事があります。
接する直方体では、$(2,1)$はAに対してもBに対してもonですが、$A\cup B$の内側です。
其の点の左側をAが、右側をBが埋めているからです。
従って、実際の判定器はonを其の儘上に渡すのではなく、表面のどちら側が埋まっているか（其の点の近傍）も渡し、其れらを組み合わせます。

実際のCSG

CSG木はコンパクトで（ブラケットはプリミティブ3つと演算2つです）、常に正しいソリッドを表し、編集も簡単です。
円柱の半径を変えればソリッドも更新されます。
弱点は、境界が何処にも保存されていない事です。
GPUでソリッドを描く、表面積を求める、稜線の1本を丸める、といった事をするには、プログラムは先ず木から境界を計算しなければなりません。
此れを境界評価と呼びます。
又、CSG木は一意ではありません。
此処ではCがBに触れないので、$(A\cup B)-C$と$(A-C)\cup B$は同じブラケットになります。

CSGはスクリプト型のCAD（OpenSCADは全ての部品をCSG木として記述します）、機械系CADのフィーチャー履歴の中、Blenderの様なメッシュモデラーの「ブーリアン」機能、そして足し算と引き算のブラシでレベルを組み立てていた昔のゲームのレベルエディタで見かけます。

7.3 境界表現、スイープ、其の他のソリッド表現

境界表現（B-rep）

ソリッドは其の表面で完全に決まります。
境界が正確に分かれば、内側は其れが囲む物です。
境界表現（B-rep、Boundary Representation）は正に其れを保存します。
ソリッドの面、面が出会う稜線（エッジ）、稜線が出会う頂点、そして其れらの繋がり方です。
各面は自分の幾何も保存します。
平面か、円柱面やNURBSパッチ（第8章）の様な曲面です。
ブラケットを境界表現で表すと、前面と背面（其々丸い穴の開いたL字形）、L字の周りの6つの平らな側面、そして穴の内側の1つの円柱面になります。

境界表現は今日の機械系CADの主な表現です。
長所は境界に直接アクセス出来る事です。
描画、面積の計測、丸める稜線を選ぶ事、そして7.7節の局所的な操作は全て、境界表現の上で直接行えます。
短所は、データが大きい事と、正しくない物を簡単に作れてしまう事です（面が欠ける、2つの面が交差する、1本の稜線に3枚の面が付く）。
此の章の残りの殆どは、境界表現を正しく保つ為の話です。
7.4節の位相の規則、7.5節のデータ構造、7.6節のオイラーの公式です。

スイープ表現

多くの部品は、2次元の形を空間の中で動かして作られます。
スイープ表現は2次元の断面（プロファイル）と、其れが動く経路を保存します：

• 平行移動スイープは、一般には押し出し（extrusion）と呼ばれ、断面を直線に沿って動かします。
• 回転スイープは、断面を其の平面内にある軸の周りに回します。

上の段は、CSGのブラケットが押し出しでもある事を示しています。
穴の開いたL字形の断面を、z方向に1だけ動かした物です。
同じソリッドには複数の表現があり、此れは後で表現を比べる時に大事になります。

スイープを使うと体積が簡単に求まります。
押し出しの体積は、断面の面積と動かした距離の積です。
ブラケットでは、L字の面積は$5\cdot 2+2\cdot 5-2\cdot 2=16$（2本の腕から、2回数えた正方形を引きます）、穴は$\pi \cdot {0.6}^2\approx 1.131$なので、体積は$(16-1.131)\cdot 1\approx 14.87$です。
回転スイープでは、パップス・ギュルダンの定理により、体積は断面の面積と其の重心が動く距離の積、$V=2\pi \overline{x}A$です。
此の長方形は$x=1$から$x=2$、$y=0$から$y=3$までなので、$A=3$、$\overline{x}=1.5$です：

2つの円柱の差として確かめましょう：$\pi \cdot 2^2\cdot 3-\pi \cdot 1^2\cdot 3=12\pi -3\pi =9\pi$です。

スイープは設計者が実際に使う方法です。
「断面をスケッチして押し出す」と「断面の半分をスケッチして回転させる」は、どのCADプログラムでも最もよく使われる2つのコマンドで、旋盤が作るのも正に回転スイープです。
曲がった経路に沿ったスイープや、ソリッド全体のスイープ（動くフライス工具が削り取る体積）は其の一般化です。
限界は、そういった対称性を持つ形しかスイープ出来ない事で、2つのスイープを組み合わせた途端に、結局CSGか境界表現が必要になります。

プリミティブインスタンシング

プリミティブインスタンシングはCSGのプリミティブより更に一歩進み、部品のファミリー全体を種類と幾つかのパラメータで記述します。
「六角ボルト、M8、長さ30」や「平歯車、歯数24、モジュール2」の様にです。
考えられる限り最もコンパクトな記述で、CADの規格部品ライブラリは此の方法で動いていますが、誰かが前もってプログラムしたファミリーしか記述出来ず、別の表現を使わずに2つのインスタンスを組み合わせて新しい形を作る事も出来ません。

セル分割表現とボクセル表現

セル分割表現は、重ならず面だけを共有する単純なセルを積み木の様に貼り合わせてソリッドを作ります。
例えば穴の無いブラケットは、直方体$[0,5]\times [0,2]\times [0,1]$と、其れと正方形1つだけで接する直方体$[0,2]\times [2,5]\times [0,1]$を貼り合わせた物です。
規則正しい格子上の同じ立方体を使う特別な場合がボクセル表現（spatial occupancy enumeration、直訳すると空間占有列挙）で、ソリッドは内側にある格子のセル、つまりボクセルのリストになります。
ボクセルと其の適応的な版である八分木は第9章の主題なので、此処では1点だけ述べます。
ボクセルモデルは単純で、集合演算も（セルごとに行えば良いので）簡単ですが、常に近似であり、メモリは解像度の3乗で増えます。

表現の間の変換

1つのソリッドを幾つかの方法で記述出来るので、CADシステムは常に変換を行っています：

• CSG → 境界表現（境界評価）：プリミティブの表面同士の交線を求め、表面を断片に切り、各断片が木全体に対してin、on、outのどれかを判定し、境界上の断片を残します。大変な作業ですが完全に体系的で、CSGを使う全てのCADプログラムが行っています。
• スイープ → 境界表現：簡単です。押し出しの面は、断面2枚と、断面の辺1本ごとに側面1枚です。
• 何でも → ボクセル：簡単です。全てのセルの中心を判定します。
• 境界表現 → CSG：難しく、一意でもありません。同じソリッドに対する木は無数にあり、良い木を見つけるのは研究課題です。
• ボクセル → 境界表現：近似としてなら、マーチングキューブ法（第9章）で可能です。

比較

表現	保存する物	長所	短所
CSG	プリミティブと集合演算の木	コンパクト、常に正しい、編集が簡単、内外判定が簡単	境界を評価する必要がある、一意ではない
境界表現	面・稜線・頂点、其の繋がりと幾何	境界に直接アクセス出来る（描画、局所的な操作）、殆どのCADが使う	大きい、正しさを確かめる必要がある
スイープ	断面と経路	非常にコンパクト、押し出しや旋盤加工の部品に自然	一部の形だけ
プリミティブインスタンシング	種類と其のパラメータ	最もコンパクト	予め決めたファミリーだけ、組み合わせられない
セル分割、ボクセル	セルのリスト	単純、集合演算が簡単	近似、メモリがすぐ増える

実際のCADプログラムは此れらを組み合わせます。
ユーザーが行った操作のCSGの様な履歴（7.7節）と、現在の結果の境界表現の両方を持っています。

検定のポイント

• ワイヤーフレーム：辺だけ、曖昧。サーフェス：面はあるが内側が無い。ソリッド：内側が定義されているので、体積、質量、干渉チェックが可能。
• CSG ＝ プリミティブ ＋ 集合演算（和・差・積）の木。点の内外判定は、in・on・outを木の上へ組み合わせる。
• 正則化集合演算：内部の閉包、$\overline{\mathrm{int}(A\cap B)}$。宙に浮いた面や辺を取り除く。
• 境界表現 ＝ 面・稜線・頂点と、其の繋がり（位相）と形（幾何）。
• 平行移動スイープ ＝ 押し出し、回転スイープ ＝ 回転体。CSG → 境界表現は日常的、境界表現 → CSGは難しい。

7.4 位相と幾何

境界表現は2種類の情報を保存し、其れらを分けて考えると此の章の残りが全て分かり易くなります：

• 位相情報は部品の繋がり方です。どの頂点がどの稜線の端か、どの稜線がどの面を囲むか、どの面が或る稜線で出会うか。物体をゴムの様に変形しても残る情報です。
• 幾何情報は部品が何処にあるかです。頂点の座標、稜線の曲線と面の曲面の方程式です。

簡単な例を2つ挙げます。
立方体の頂点を動かし、傾いて引き伸ばされた箱にします。
幾何は変わりますが、位相（頂点8、稜線12、面6、同じ様に繋がっている）は変わらず、7.5節のデータ構造は全く変わりません。
次に、立方体の前面を対角線で2つの三角形に分けます。
形は全く変わりませんが、位相は変わります（面7、稜線13）。
どちらも他方を決めないので、境界表現には両方が必要です。

多様体と非多様体

普通のソリッドの境界は、局所的には平らなシートの様に見えます。
立方体の表面の任意の点に、稜線上でも角でも、ズームインすると、見える物は小さな円板に平らに伸ばせます。
そういう曲面を2次元多様体（二多様体、単に多様体とも）と呼び、境界が2次元多様体であるソリッドを多様体ソリッドと呼びます。
ポリゴンモデルでは、此れは2つの具体的な規則になります：

1. 全ての稜線は丁度2枚の面に属する。
2. 全ての頂点の周りの面は、頂点の周りを一周して閉じる1つの扇形を作る。

此れを破るモデルは非多様体です：

• 稜線だけを共有する2つの立方体：其の稜線に4枚の面が集まり、規則1を破ります。
• 頂点だけを共有する2つの立方体：其の頂点の周りで面が2つの別々の扇形（先端で接する2つの錐）になり、規則2を破ります。
• ひれの付いた立方体。ひれとは、稜線の1本から垂れ下がった1枚の面です。其の稜線に3枚の面が集まります。ひれは正に、正則化集合演算が取り除く宙に浮いた面です。

最初の2つは点の集合としては全く問題無く、2つの立方体の普通の和から出来てしまう事もあります。
其れでも除外するのは、7.5節のデータ構造が全ての稜線に丁度2つの側があると仮定しているからで、又3Dプリンターや有限要素法のプログラムも厚さ0の稜線をどう扱えば良いのか分からないからです。
（ソリッド、シート、ワイヤーを1つのモデルに混ぜる為などに、わざと非多様体のモデルを扱えるCADカーネルもありますが、より豊かなデータ構造が必要です。）

向きとウォータータイト

ソリッドの各面には外側と内側があります。
其れを第5章と第6章と同じ方法で記録します。
面の頂点を外側から見て反時計回りに並べ、連続する2本の辺の外積が右手の法則で外向き法線を与える様にするのです。
此の選び方が面の向きで、正に背面除去が使う物です（第6章の6.4節）。

向きが一貫している為には、隣り合う2つの面は共有する辺を逆向きに辿らなければなりません。
並んだ2つの正方形を、両方とも反時計回りに思い浮かべて下さい。
左の正方形は共通の辺を上向きに、右の正方形は下向きに辿ります。
もし両方が上向きに辿れば、2つの法線の一方は内側を向いてしまいます。
一貫した向きを付けられない曲面を向き付け不可能と呼び、有名な例はメビウスの帯で、表と裏の区別がありません。
ソリッドの境界は常に内側と外側を分けるので、必ず向きを付けられます。

最後に、サーフェスモデルに境界の辺、つまり面が1枚しか無い辺が無ければ、其のモデルは閉じている、又はウォータータイトであると言います。
7.1節の蓋の無い箱は、開口部の周りに4本の境界の辺を持ち、立方体は1本も持ちません。

此の2つの性質は、とても実用的な結果をもたらします。
閉じていて一貫した向きを持つ三角形メッシュは体積を囲み、其の体積は境界だけから計算出来ます。
全ての三角形$(𝐚,𝐛,𝐜)$について、原点と作る四面体の符号付き体積を足し合わせます：

（線型代数の第10章のスカラー三重積で、第5章の外積を使います。）
ソリッドの外側から見える四面体は負の符号で数えられ、外側にはみ出した分を丁度打ち消します。
此れはメッシュが閉じていて、全ての面が外向きの場合にしか成り立ちません。
線型代数シリーズのlinalg.hhヘッダーを使ったC++版です。
立方体$[0,1{]}^3$をインデックス付きの面集合（頂点リストと、面ごとの頂点の番号。7.5節で詳しく見ます）として保存しています：

#include <cstdio>
#include <map>
#include <utility>
#include <vector>
#include "linalg.hh"

// An indexed face set: vertex positions, and for every face its vertex indices,
// counter-clockwise seen from outside.
struct Mesh {
  std::vector<Vec3> v;
  std::vector<std::vector<int>> f;
};

// Volume of a closed, consistently oriented mesh: the sum of the signed volumes of the
// tetrahedra (origin, a, b, c) over a fan of triangles in every face.
float volume(const Mesh &m) {
  float sum = 0;
  for (const auto &face : m.f) {
    for (size_t i = 1; i + 1 < face.size(); ++i) {
      sum += dot(m.v[face[0]], cross(m.v[face[i]], m.v[face[i + 1]]));
    }
  }
  return sum / 6;
}

// Closed and consistently oriented: every directed edge a->b is used by exactly one face,
// and its reverse b->a by exactly one other face.
bool closedAndOriented(const Mesh &m) {
  std::map<std::pair<int, int>, int> count;
  for (const auto &face : m.f) {
    for (size_t i = 0; i < face.size(); ++i) {
      ++count[{face[i], face[(i + 1) % face.size()]}];
    }
  }
  for (const auto &[e, n] : count) {
    auto back = count.find({e.second, e.first});
    if (n != 1 || back == count.end() || back->second != 1) return false;
  }
  return true;
}

int main() {
  Mesh cube{{{0, 0, 0}, {1, 0, 0}, {1, 0, 1}, {0, 0, 1},
             {0, 1, 0}, {1, 1, 0}, {1, 1, 1}, {0, 1, 1}},
            {{0, 1, 2, 3}, {4, 7, 6, 5}, {2, 6, 7, 3}, {0, 4, 5, 1}, {0, 3, 7, 4}, {1, 5, 6, 2}}};
  printf("cube:       volume %g, closed and oriented: %s\n", volume(cube),
         closedAndOriented(cube) ? "yes" : "no");

  Mesh flipped = cube;
  flipped.f[1] = {5, 6, 7, 4}; // the top face listed clockwise
  printf("flipped:    volume %g, closed and oriented: %s\n", volume(flipped),
         closedAndOriented(flipped) ? "yes" : "no");

  Mesh open = cube;
  open.f.erase(open.f.begin() + 1); // no top face
  printf("open box:   volume %g, closed and oriented: %s\n", volume(open),
         closedAndOriented(open) ? "yes" : "no");
  return 0;
}

cube:       volume 1, closed and oriented: yes
flipped:    volume 0.333333, closed and oriented: no
open box:   volume 0.666667, closed and oriented: no

原点を通る立方体の3つの面は何も寄与せず（其の四面体は潰れています）、残りの3つの面が其々$\frac{1}{3}$ずつ寄与します。
其の1つを裏返すと寄与は$-\frac{1}{3}$になるので$1-\frac{2}{3}=\frac{1}{3}$、取り除くと$1-\frac{1}{3}=\frac{2}{3}$です。
どちらの間違った答えも何のエラーメッセージも無しに出てきます。
3Dプリント用のソフトウェアが何よりも先に、正に此の2つの性質（「多様体」と「ウォータータイト」）をメッシュについて確認するのは其の為です。

7.5 境界表現のデータ構造

では、実際のソリッド、下の番号付けをした単位立方体を使って、境界表現を保存してみましょう。
$i=0\dots 3$の頂点$v_i$が底の正方形で、$v_{i+4}$は$v_i$の真上にあります。
面は$f_0$が底面（$y=0$）、$f_1$が上面（$y=1$）、$f_2$が前面（$z=1$）、$f_3$が背面（$z=0$）、$f_4$が左面（$x=0$）、$f_5$が右面（$x=1$）です。
全ての稜線には、矢印で示した向きを付けます。

座標は$v_0=(0,0,0)$、$v_1=(1,0,0)$、$v_2=(1,0,1)$、$v_3=(0,0,1)$で、$v_4$から$v_7$は其れらの$y$を1にした物です。

頂点リストと面リスト（インデックス付きの面集合）

最も単純な構造は、上のコードで使った物です。
座標を持つ頂点リストと、面ごとに其の頂点の番号を外側から見て反時計回りに並べた面リストです：

面	頂点
$f_0$ 底面	0, 1, 2, 3
$f_1$ 上面	4, 7, 6, 5
$f_2$ 前面	2, 6, 7, 3
$f_3$ 背面	0, 4, 5, 1
$f_4$ 左面	0, 3, 7, 4
$f_5$ 右面	1, 5, 6, 2

幾何（座標）と位相（番号）がきれいに分かれていて、共有される頂点は1回だけ保存され、其れを動かすと其の頂点を持つ全ての面が動きます。
ファイル形式やGPUが使うのは此の形です（第9章でインデックスバッファを詳しく見ます）。
しかし、隣接関係の問い合わせには素早く答えられません。
「$v_6$を囲む面はどれか？」や「此の辺の向こう側の面はどれか？」に答えるには、面リスト全体を探さなければなりません。
面が6枚なら何でもありませんが、100万枚の面を持つCADモデルで、そういう問いを何百万回も行う操作（稜線を丸める、法線を滑らかにする、曲面を細分割する）では遅過ぎます。
次の2つの構造は隣の要素を明示的に保存するので、そういう巡回の1歩1歩が定数時間で済みます。

ウイングドエッジ構造

ウイングドエッジ構造（ウィングドエッジ構造とも書きます）は、1970年代にBruce Baumgartがコンピュータビジョンの為に考案し、境界表現の古典的なデータ構造になりました。
考え方は、繋がりを稜線に持たせる事です。
各稜線のレコードは8つの参照を持ちます：

• 2つの頂点、startとend（始点と終点）、
• 2つの面。leftは反時計回りのループで稜線を始点から終点へ辿る面、rightは終点から始点へ辿る面、
• 4つのウイング、つまり其の2つのループの中で隣にある稜線。leftPredとleftSucc（左の面のループで直前と直後の稜線）、rightPredとrightSucc（右の面のループでの同じ物）。

其れに加えて、各頂点は自分に接する稜線を1本、各面は自分の境界の稜線を1本保存します。
名前やウイングの正確な選び方は本によって違いますが（時計回りと反時計回りの次の稜線を保存する流儀もあります）、どの版でも稜線1本につき8つの参照を持つ事は同じです。
上の面ループから計算した、此の立方体の完全な表です：

稜線	start	end	left	right	leftPred	leftSucc	rightPred	rightSucc
$e_0$	$v_0$	$v_1$	$f_0$	$f_3$	$e_3$	$e_1$	$e_5$	$e_4$
$e_1$	$v_1$	$v_2$	$f_0$	$f_5$	$e_0$	$e_2$	$e_6$	$e_5$
$e_2$	$v_2$	$v_3$	$f_0$	$f_2$	$e_1$	$e_3$	$e_7$	$e_6$
$e_3$	$v_3$	$v_0$	$f_0$	$f_4$	$e_2$	$e_0$	$e_4$	$e_7$
$e_4$	$v_0$	$v_4$	$f_3$	$f_4$	$e_0$	$e_8$	$e_{11}$	$e_3$
$e_5$	$v_1$	$v_5$	$f_5$	$f_3$	$e_1$	$e_9$	$e_8$	$e_0$
$e_6$	$v_2$	$v_6$	$f_2$	$f_5$	$e_2$	$e_{10}$	$e_9$	$e_1$
$e_7$	$v_3$	$v_7$	$f_4$	$f_2$	$e_3$	$e_{11}$	$e_{10}$	$e_2$
$e_8$	$v_4$	$v_5$	$f_3$	$f_1$	$e_4$	$e_5$	$e_9$	$e_{11}$
$e_9$	$v_5$	$v_6$	$f_5$	$f_1$	$e_5$	$e_6$	$e_{10}$	$e_8$
$e_{10}$	$v_6$	$v_7$	$f_2$	$f_1$	$e_6$	$e_7$	$e_{11}$	$e_9$
$e_{11}$	$v_7$	$v_4$	$f_4$	$f_1$	$e_7$	$e_4$	$e_8$	$e_{10}$

1行を図と照らし合わせてみましょう。
$e_6$は$v_2$から$v_6$へ上向きです。
其れを上へ歩くと、前面$f_2$が左に、右面$f_5$が右にあります。
前面のループ2, 6, 7, 3の中で、$e_6$の直前の稜線は$v_3$から$v_2$に着き（$e_2$）、直後の稜線は$v_6$から$v_7$へ出ます（$e_{10}$）。

検索例1：面の稜線。
面$f$の周りを歩くには、其の稜線のどれか$e$から始め、次を繰り返します。
$e$の左の面が$f$ならleftSuccへ、そうでなければrightSuccへ進みます。
$f_5$について、$e_5$（左の面が$f_5$）から始めると：

• $e_5$：左が$f_5$なので、其のleftSuccの$e_9$へ。
• $e_9$：左が$f_5$なので、$e_6$へ。
• $e_6$：右が$f_5$なので、其のrightSuccの$e_1$へ。
• $e_1$：右が$f_5$なので、$e_5$へ。出発点に戻りました。

従って右面は$e_5,e_9,e_6,e_1$に囲まれ、此れらは$v_1,v_5,v_6,v_2$を通ります。
正に面リストの1, 5, 6, 2です。

検索例2：頂点の周りの面。
此れは、頂点リストと面リストでは探索無しに答えられなかった問いです。
頂点のレコードが保存している稜線から始め、次を繰り返します。
頂点が稜線のstartなら稜線の左の面を記録してleftPredへ、endなら右の面を記録してrightPredへ進みます。
（稜線が頂点から出ていく面では、其の直前の稜線は同じ面の中で頂点に着く稜線です。其れを越えると、頂点の周りの次の面に移ります。）
レコードに$e_{10}$を保存している$v_6$では：

• $e_{10}$は$v_6$から始まる：面$f_2$（前面）、leftPredの$e_6$へ。
• $e_6$は$v_6$で終わる：面$f_5$（右面）、rightPredの$e_9$へ。
• $e_9$は$v_6$で終わる：面$f_1$（上面）、rightPredの$e_{10}$へ。出発点に戻りました。

$v_6$の周りの面は、外側から見て反時計回りに前面、右面、上面で、周りの稜線は$e_{10},e_6,e_9$です。
3つの面に3歩、探索は無く、1歩のコストはモデルの大きさに依存しません。

ハーフエッジ構造

ウイングドエッジ構造には1つ面倒な点があります。
稜線は1つの向きしか持たないので、毎回「頂点は始点か終点か、面は左か右か」を判定しなければなりません。
ハーフエッジ構造は、全ての稜線を面ごとに1本ずつ、2本のハーフエッジに分け、其々が自分の面が辿る向きを指す様にして、其の判定を無くします。
ハーフエッジは次を保存します：

• origin：始まる頂点、
• twin：隣の面にある同じ稜線のハーフエッジで、逆向きの物、
• nextとprev：自分の面のループで次と前のハーフエッジ、
• face：属する面。

各頂点は自分から出ていくハーフエッジを1本、各面は自分のハーフエッジを1本保存します。

立方体では全ての稜線が2本のハーフエッジになり、合計24本です。
向きの付いた頂点の組はどれも1回しか現れないので、ハーフエッジを端点で名付けられます。
$h_{67}$は$v_6$から$v_7$へのハーフエッジです。
必要になるハーフエッジは次の通りです：

ハーフエッジ	origin	twin	next	prev	face
$h_{67}$	$v_6$	$h_{76}$	$h_{73}$	$h_{26}$	$f_2$
$h_{73}$	$v_7$	$h_{37}$	$h_{32}$	$h_{67}$	$f_2$
$h_{26}$	$v_2$	$h_{62}$	$h_{67}$	$h_{32}$	$f_2$
$h_{62}$	$v_6$	$h_{26}$	$h_{21}$	$h_{56}$	$f_5$
$h_{56}$	$v_5$	$h_{65}$	$h_{62}$	$h_{15}$	$f_5$
$h_{65}$	$v_6$	$h_{56}$	$h_{54}$	$h_{76}$	$f_1$
$h_{76}$	$v_7$	$h_{67}$	$h_{65}$	$h_{47}$	$f_1$

巡回は1行で書けます：

• 面の周り：$h\to \text{next}(h)$。$h_{67}$から：$h_{67}\to h_{73}\to h_{32}\to h_{26}\to h_{67}$なので、前面は6, 7, 3, 2です。
• 頂点の周り：$h\to \text{twin}(\text{prev}(h))$で、外側から見て反時計回りに進みます。$h_{67}$（面$f_2$）から：$\text{prev}(h_{67})=h_{26}$で其のtwinは$h_{62}$（面$f_5$）、$\text{prev}(h_{62})=h_{56}$で其のtwinは$h_{65}$（面$f_1$）、$\text{prev}(h_{65})=h_{76}$で其のtwinは出発点の$h_{67}$です。前面、右面、上面で、ウイングドエッジの検索と同じ答えです。
• 辺の向こうの面：$\text{face}(\text{twin}(h))$。

（頂点の周りを逆向きに回るのは$h\to \text{next}(\text{twin}(h))$です。）
頂点リストと面リストからハーフエッジ構造を作るのは数行で済みます。
面ごとにハーフエッジを作り、其の後、頂点の組を逆にして探す事で各twinを見つけます。

#include <cstdio>
#include <map>
#include <utility>
#include <vector>

struct HalfEdge {
  int origin, twin, next, prev, face;
};

struct HalfEdgeMesh {
  std::vector<HalfEdge> h;
  std::vector<int> vertexEdge; // one outgoing half-edge per vertex
  std::vector<int> faceEdge;   // one half-edge per face
};

// Builds the half-edges of a closed, consistently oriented polygon mesh.
HalfEdgeMesh build(int vertexCount, const std::vector<std::vector<int>> &faces) {
  HalfEdgeMesh m;
  m.vertexEdge.assign(vertexCount, -1);
  std::map<std::pair<int, int>, int> byEnds; // (origin, target) -> half-edge index
  for (int fi = 0; fi < (int)faces.size(); ++fi) {
    const auto &face = faces[fi];
    int first = (int)m.h.size(), n = (int)face.size();
    m.faceEdge.push_back(first);
    for (int i = 0; i < n; ++i) {
      int a = face[i], b = face[(i + 1) % n];
      m.h.push_back({a, -1, first + (i + 1) % n, first + (i + n - 1) % n, fi});
      byEnds[{a, b}] = first + i;
      if (m.vertexEdge[a] < 0) m.vertexEdge[a] = first + i;
    }
  }
  for (const auto &[ends, i] : byEnds) {
    m.h[i].twin = byEnds.at({ends.second, ends.first}); // the same edge, walked the other way
  }
  return m;
}

int main() {
  std::vector<std::vector<int>> faces{{0, 1, 2, 3}, {4, 7, 6, 5}, {2, 6, 7, 3},
                                      {0, 4, 5, 1}, {0, 3, 7, 4}, {1, 5, 6, 2}};
  HalfEdgeMesh m = build(8, faces);

  // faces around vertex 6, counter-clockwise seen from outside: h -> twin(prev(h))
  printf("around v6:");
  int start = m.vertexEdge[6], h = start;
  do {
    const HalfEdge &e = m.h[h];
    printf(" f%d (h%d%d)", e.face, e.origin, m.h[e.next].origin);
    h = m.h[e.prev].twin;
  } while (h != start);
  printf("\n");

  int V = (int)m.vertexEdge.size(), E = (int)m.h.size() / 2, F = (int)m.faceEdge.size();
  printf("V - E + F = %d - %d + %d = %d\n", V, E, F, V - E + F);
  return 0;
}

around v6: f1 (h65) f2 (h67) f5 (h62)
V - E + F = 8 - 12 + 6 = 2

此のプログラムでは$v_6$のレコードがたまたま$h_{65}$（面リストの中で$v_6$から出る最初のハーフエッジ）なので上面から始まりますが、巡回は同じです。
最後の行は7.6節の予告です。
twinが見つからないとbyEnds.atは例外を投げる事に注意して下さい。
開いたメッシュや非多様体のメッシュでは、此の構造を其の儘では作れません。
其れが、稜線1本につき面が丁度2枚と仮定する事の代償です。

3つの比較

立方体について、座標を除いた参照（ポインタ又は番号）の数を数えます：

構造	1要素あたり	立方体の合計
頂点リストと面リスト	面ごとに頂点番号4つ	$6\cdot 4=24$
ウイングドエッジ	稜線ごとに8、頂点と面ごとに1	$12\cdot 8+8+6=110$
ハーフエッジ（origin, twin, next, prev, face）	ハーフエッジごとに5、頂点と面ごとに1	$24\cdot 5+8+6=134$

隣接関係を持つ構造は4倍から6倍のメモリを使い、其れが取引です。
頂点リストと面リストは保存と描画には理想的ですが、「此の隣は何か？」を絶えず問うモデリング操作には、ウイングドエッジかハーフエッジが必要です。
（prevはnextで面を一周すれば見つかるので省くと、ハーフエッジの数は$24\cdot 4+14=110$に減ります。）
多くのメッシュ処理ライブラリ（例えばOpenMeshやCGAL）はハーフエッジを使っていて、ウイングドエッジ構造に出会うのは主に教科書と検定の中です。

検定のポイント

• ウイングドエッジ：稜線ごとに頂点2つ ＋ 面2つ ＋ ウイングの稜線4本 ＝ 8つの参照。各頂点と各面は稜線を1本保存する。
• ハーフエッジ：origin、twin、next（prev）、face。twinは隣の面にあり、逆向き。
• 面の周り：nextを辿る。頂点の周り：prevのtwin（又はtwinのnext）。辺の向こうの面：twinのface。
• どちらも多様体、つまり稜線1本につき面が丁度2枚である事を仮定している。

7.6 オイラーの公式とオイラー操作

オイラーの公式

凸多面体の頂点の数V、辺の数E、面の数Fを数えて$V-E+F$を計算してみましょう：

立体	V	E	F	V − E + F
四面体	4	6	4	4 − 6 + 4 = 2
立方体	8	12	6	8 − 12 + 6 = 2
三角柱	6	9	5	6 − 9 + 5 = 2
八面体	6	12	8	6 − 12 + 8 = 2

いつも2です。
此れが18世紀にレオンハルト・オイラーが見つけたオイラーの公式（オイラーの多面体定理）です：

此れは、表面を膨らませると球になる全てのソリッド、つまり貫通する穴も空洞も無く、全ての面が穴の無い円板であるソリッドについて成り立ちます。
形や大きさは関係無く、此れが位相だけについての主張である事を示しています。
モデラーにとっては手軽な健全性チェックです。
数が此の公式を破る境界表現は確実に壊れています。
（必要条件であって十分条件ではありません。数が正しくてもモデルが正しいとは限らず、壊れたモデルが偶然正しい数を持つ事もあります。）

三角形メッシュについて役に立つ結果があります。
全ての面が三角形なら、各面は3本の辺を持ち、各辺は2枚の面に属するので、$2E=3F$です。
此れをオイラーの公式に代入すると$F=2V-4$、$E=3V-6$になります。
穴の無い閉じた三角形メッシュは、頂点の約2倍の三角形と約3倍の辺を持つのです。
八面体で確かめると、$V=6$、$F=2\cdot 6-4=8$、$E=3\cdot 6-6=12$です。

オイラー・ポアンカレの式

次に、立方体に前面から背面まで四角い穴を開けます：

(a)では、前面と背面は四角い穴の開いた正方形です。
各面は外側の境界と、1つの内側の境界、つまりリング（面の内側のループ）を持ちます。
数えると、外側の頂点8つと内側の頂点8つで$V=16$、外側の辺12本、2つの内側の正方形の周りの$2\cdot 4$本、トンネルに沿った4本で$E=24$、立方体の面6枚とトンネルの壁4枚で$F=10$です。
$V-E+F=16-24+10=2$で問題無さそうに見えますが、此れは偶然で、此の公式は此処では当てはまりません。
一般化した物がオイラー・ポアンカレの式です：

Rはリングの数、Sはシェル（繋がった別々の境界面）の数、Hはソリッドを貫通する穴の数（種数）です。
(a)では$R=2$、$S=1$、$H=1$です：

(b)は同じソリッドで、リングを持つ面を其々4本の辺（オレンジ色）で4つの台形に分けたのでリングがありません。
$V=16$、$E=24+8=32$、$F=10-2+8=16$、$R=0$です：

そして空洞のあるソリッドです。
内部に小さな立方体形の空洞を持つ立方体は、2つのシェル（外側の表面と空洞の表面）を持ち、$V=16$、$E=24$、$F=12$、$R=0$、$S=2$、$H=0$です：

穴もリングも無い1つのシェルでは$S=1$、$H=R=0$で、式は元のオイラーの公式$V-E+F=2$になります。

オイラー操作

全ての正しいソリッドが此の式を満たすなら、式を満たしたままにする操作だけでソリッドを編集すれば良いのではないでしょうか？
其れがオイラー操作の考え方で、Baumgartが導入し、1980年代にソリッドモデラーの完全な体系に発展しました（Mäntyläの本が古典的な文献です）。
各操作は決まった要素の組を作る（Make、「M」）か消す（Kill、「K」）かします：

操作	意味	ΔV	ΔE	ΔF	ΔR	ΔS	ΔH
MVFS	頂点・面・シェルを作る	+1	0	+1	0	+1	0
MEV	辺・頂点を作る	+1	+1	0	0	0	0
MEF	辺・面を作る	0	+1	+1	0	0	0
KEMR	辺を消しリングを作る	0	−1	0	+1	0	0
KFMRH	面を消しリングと穴を作る	0	0	−1	+1	0	+1

其々に、元に戻す逆操作があります。
KVFS、KEV、KEF、MEKR、MFKRHです。
（綴りは本によって違い、MVFSはMVSFやMSFVとも書かれます。）
1つ確かめましょう。
MEFは$V-E+F-R$を$0-1+1-0=0$だけ、$2(S-H)$を0だけ変えます。
KFMRHは左辺を$0-0+(-1)-1=-2$、右辺を$2(0-1)=-2$だけ変えます。
表の全ての操作が両辺を等しく保つので、此れらだけで作ったモデルは常にオイラー・ポアンカレの式を満たします。

計算例：立方体を作る。
7.5節の番号付けを使います：

1. MVFSが$v_0$を、1つの面と1つのシェルと一緒に作ります。1点だけでも「面」を持ちます。其の周りの表面で、分割されると2つの面になります。$V=1$、$E=0$、$F=1$で、$1-0+1=2$です。
2. MEVを3回で辺$e_0,e_1,e_2$と新しい頂点$v_1,v_2,v_3$を描きます。$V=4$、$E=3$、$F=1$、$4-3+1=2$です。
3. MEFが$e_3$で正方形を閉じ、面を2つ、底面$f_0$と正方形の反対側に分けます。$V=4$、$E=4$、$F=2$です。
4. MEVを4回で4本の縦の辺$e_4$から$e_7$を、上の頂点$v_4$から$v_7$と共に立てます。$V=8$、$E=8$、$F=2$です。
5. MEFが$v_4$から$v_5$への$e_8$を加え、背面$f_3$を切り分けます。$V=8$、$E=9$、$F=3$です。
6. MEFを3回で$e_9,e_{10},e_{11}$を加え、$f_5$、$f_2$、$f_4$を切り分けます。元の面の残りが上面$f_1$になります。$V=8$、$E=12$、$F=6$です。

13個の操作で、其の1つ1つの後で$V-E+F=2$です。
此れはオイラーの公式が何故成り立つかを見る良い方法でもあります。
MVFSは$1-0+1=2$から始まり、MEVとMEFは其の値を決して変えません。

計算例：穴を開ける。
立方体（図の大きさに拡大した物）から続けて、(a)の貫通穴には更に15個の操作が必要です：

段階	操作	V	E	F	R	S	H	V − E + F − R	2(S − H)
立方体	（上の通り）	8	12	6	0	1	0	2	2
外側の角から前面の中へ橋渡しの辺を引き、内側の正方形の残り3つの頂点を作る	MEVを4回	12	16	6	0	1	0	2	2
内側の正方形を閉じる：前面の中に新しい面が出来る	MEF	12	17	7	0	1	0	2	2
橋渡しの辺を消す：内側の正方形が前面のリングになる	KEMR	12	16	7	1	1	0	2	2
内側の正方形の角から背面に向かうトンネルの辺	MEVを4回	16	20	7	1	1	0	2	2
トンネルの壁を閉じる：内側の面は凹みの底になる	MEFを4回	16	24	11	1	1	0	2	2
凹みの底が背面のリングになる：凹みが貫通穴になる	KFMRH	16	24	10	2	1	1	0	0

最後には丁度(a)の数になり、式は全ての段階で成り立っていました。
実際のモデラーがオイラー操作を1つずつ呼ぶ事は滅多にありませんが、より高水準の操作（押し出し、切り取り、面取り）はオイラー操作の列として実装されていて、其れが位相の一貫性を保証します。
幾何（新しい頂点を何処に置くか）は別に設定します。

検定のポイント

• オイラーの公式：穴も空洞もリングも無いソリッドで$V-E+F=2$。オイラー・ポアンカレの式：$V-E+F-R=2(S-H)$。
• Rは面の内側のループ、Sは別々のシェル（空洞があると1増える）、Hはソリッドを貫通する穴の数。
• 此の式は正しさの必要条件であり、十分条件ではない。
• オイラー操作（MVFS、MEV、MEF、KEMR、KFMRHと其の逆操作）は、全ての段階で式を成り立たせたままにする。

7.7 局所変形

局所変形は、境界表現を作り直さずに其の小さな部分を変えます。
頂点を1つ動かす、稜線を削る、角を丸める、といった操作です。
其々の操作は、位相の小さな変更（幾つかのオイラー操作）と新しい幾何の組み合わせです。
立方体$[0,2{]}^3$を使い、前・上・右の角$(2,2,2)$と、$(2,2,0)$から$(2,2,2)$への上右の稜線を変えます。

頂点や面を動かす

最も単純な局所操作は幾何だけを変えます。
頂点を動かし、位相は其の儘にするのです。
しかし面は平面のままでなければならず、此れは簡単に崩れます。
角$(2,2,2)$を$(2,3,2)$へ持ち上げます。
4つの点が同一平面上にあるのは、其の1つから出る3本の辺ベクトルのスカラー三重積が0の時だけです。
上面の$𝐚=(0,2,0)$、$𝐛=(2,2,0)$、$𝐜=(2,3,2)$、$𝐝=(0,2,2)$について：

上面はもう平面ではありません。
右面（$x=2$）と前面（$z=2$）は問題ありません。
頂点はyの方向に動いたので、両方の平面に留まっているからです（其の面のxは全て、又はzは全て、まだ2です）。
平面でない面は本当の問題です。
法線が1つに決まらず、プログラムによって埋め方が違ってしまいます。
きれいな解決策は2つあります：

• 頂点1つではなく面全体を動かす：上の4つの頂点全てを$y=3$に持ち上げれば、全ての面は平面のままです。
• MEFで面を2つの三角形に分ける：三角形は常に平面です。位相は$V=8$、$E=13$、$F=7$（$8-13+7=2$）に変わり、対角線の選び方が重要です。図は$(2,2,0)$–$(0,2,2)$で分けていて此れは谷（凹んだ折れ目）になり、動かした頂点を通るもう一方の対角線では尾根になります。

最後の点は再び7.4節の位相と幾何の区別です。
同じ8つの点でも、1本の稜線次第で2つの違うソリッドになるのです。

面取り

面取りは稜線を平面で切り落とし、鋭い稜線を細い平らな面で置き換えます。
機械加工では鋭いバリを取る為に行います。
$(2,2,0)$から$(2,2,2)$への稜線を$d=0.5$で面取りすると、上面は$x=1.5$で、右面は$y=1.5$で終わり、新しい面の角は$(1.5,2,0)$、$(2,1.5,0)$、$(2,1.5,2)$、$(1.5,2,2)$です。
其の幅は$\sqrt{{0.5}^2+{0.5}^2}=0.5\sqrt{2}\approx 0.707$で、取り除く三角柱の体積は$\frac{1}{2}\cdot 0.5\cdot 0.5\cdot 2=0.25$、残りは$8-0.25=7.75$です。
位相としては、稜線の両端が其々2つの頂点に分かれ、新しい面が1つ出来ます。
$V=8+2=10$、$E=12+3=15$、$F=6+1=7$で、$10-15+7=2$です。
オイラー操作では、両端で1回ずつMEV（頂点を分け、新しい短い辺は背面又は前面を横切ります）、そして新しい面を右面から切り分ける1回のMEFです。
前面と背面は頂点が1つずつ増え、五角形になりました。
稜線ではなく角を切り落としても、別の理由で同じ数になります。
角は3つの頂点（+2）、3本の新しい辺（+3）、1つの新しい面（+1）を持つ小さな三角形で置き換えられるからです。

丸め（フィレット）

丸め（フィレット）は、稜線を両方の面に折れ目無く滑らかに繋がる曲面で置き換えます。
此の90°の稜線と半径$r=0.5$では、丸めは軸が直線$x=1.5$、$y=1.5$上にある円柱の4分の1で、上面とは$x=1.5$に沿って、右面とは$y=1.5$に沿って接します。
其の断面は長さ$\frac{\pi r}{2}=\frac{\pi }{4}\approx 0.785$の4分の1円で、面取りの0.707より少し長く、取り除く体積は$\left(r^2-\frac{\pi r^2}{4}\right)\cdot 2\approx 0.107$で、面取りより少なくなります。
位相は面取りと全く同じ（10, 15, 7）で、違うのは幾何だけです。
新しい面は平面ではなく円柱面で、其の稜線は直線と円弧です。
此れは境界表現に典型的な事で、同じ局所的な位相の操作に、違う種類の曲面が付くのです。
丸めた3本の稜線が出会う角では、コーナーブレンド（此処では球の一部）も必要になり、ブレンド一般には第8章の自由曲面が必要です。

フィーチャーベースモデリングと履歴

現代の機械系CAD（SolidWorks、CATIA、NX、Fusion、FreeCADの様なプログラム）は、ユーザーにオイラー操作で考える事を求めません。
ユーザーはフィーチャーで作業します。
「此のスケッチを10 mm押し出す」「此処に6 mmの穴を開ける」「此れらの稜線を半径2で丸める」といった物です。
プログラムは其れらを履歴（フィーチャーツリー）に記録し、各フィーチャーは幾何モデリングカーネル（ParasolidやACISの様な商用のカーネル、又はオープンソースのOpen CASCADE）によって境界表現の操作として実行されます。
最初の方のフィーチャーの数値を変えると履歴全体が再実行され、部品が更新されます。
此れがパラメトリック、つまり履歴ベースのモデリングです。
或る意味で、履歴はより多くの種類の操作を持つCSG木であり、境界表現は其の評価された境界です。
7.3節の2つの表現が一緒に働いているのです。
よく知られた難しさが1つあります。
上流の変更が位相を変えると、後のフィーチャーが「自分の」稜線を見つけられなくなる事があり（丸めた稜線が分割されたり消えたりしているかもしれません）、此れはトポロジカルネーミング問題と呼ばれます。

プログラム間でのやり取りには、境界表現のソリッドはSTEP（ISO 10303）の様な中立的な形式で保存されます。
一方、STLの様な形式は三角形、つまりサーフェスモデルしか保存しませんが、メッシュが閉じていて向きが揃っていれば、3Dプリンターには其れで十分です。

検定のポイント

• 頂点や面の移動は位相を変えない。動かした頂点は面を平面でなくする事がある（スカラー三重積で確かめる）。
• 面取り：平らな面が稜線を置き換える（立方体で10, 15, 7）。丸め：両隣に接する曲面で、位相は面取りと同じ。
• 局所的な操作は、オイラー操作の列と新しい幾何の組み合わせ。

7.8 まとめ

• ワイヤーフレームモデルは辺を、サーフェスモデルは面を、ソリッドモデルは内側も保存します。体積、質量、干渉の問いに答えられるのはソリッドだけです。
• CSGはプリミティブを和・差・積で組み合わせた木を保存します。点は葉から上へin・on・outで判定され、木はレイキャスティングで直接レンダリング出来ます。
• 正則化集合演算（内部の閉包）は、結果から宙に浮いた面や辺を取り除きます。
• 境界表現は面・稜線・頂点を、其の位相（繋がり）と幾何（位置と曲面）と共に保存します。スイープ、プリミティブインスタンシング、セル分割は別の表現で、CADは其れらの間を変換します。
• 多様体の境界では、全ての稜線に面が丁度2枚あり、全ての頂点の周りに扇形が1つあります。面は外側から見て反時計回りに向きを付けます。閉じていて向きの揃った境界は、計算出来る体積を囲みます。
• 頂点リストと面リストはコンパクトですが隣接関係には遅く、ウイングドエッジは稜線ごとに8つの参照を、ハーフエッジはハーフエッジごとにorigin、twin、next、prev、faceを保存し、巡回が1行で書けます。
• オイラーの公式：$V-E+F=2$。オイラー・ポアンカレの式：$V-E+F-R=2(S-H)$。オイラー操作は全ての段階で此れを成り立たせたままにします。
• 局所変形：頂点や面の移動（平面性に注意）、面取り、丸め。フィーチャーベースのCADは操作を履歴に記録し、境界表現のカーネルで再実行します。

7.9 用語

English	日本語
shape model	形状モデル
wireframe model	ワイヤーフレームモデル
surface model	サーフェスモデル
solid model	ソリッドモデル
interference check	干渉チェック
constructive solid geometry (CSG)	CSG表現
primitive	プリミティブ
set operation (union, difference, intersection)	集合演算（和・差・積）
CSG tree	CSG木
point membership classification	点の内外判定
regularized set operation	正則化集合演算
interior, closure	内部、閉包
boundary representation (B-rep)	境界表現（B-rep）
boundary evaluation	境界評価
sweep representation	スイープ表現
translational sweep (extrusion)	平行移動スイープ（押し出し）
rotational sweep (revolution)	回転スイープ
primitive instancing	プリミティブインスタンシング
cell decomposition	セル分割表現
spatial occupancy enumeration	ボクセル表現（空間占有列挙）
topology, geometry	位相情報、幾何情報
manifold, non-manifold	多様体、非多様体
orientation	向き
watertight (closed)	ウォータータイト（閉じている）
vertex list, face list (indexed face set)	頂点リスト、面リスト
adjacency	隣接関係
winged-edge structure	ウイングドエッジ構造
half-edge structure	ハーフエッジ構造
Euler's formula	オイラーの公式
Euler–Poincaré formula	オイラー・ポアンカレの式
ring, shell, hole	リング、シェル、穴
Euler operator	オイラー操作
local deformation	局所変形
chamfer	面取り
fillet, round	丸め（フィレット）
feature-based modeling	フィーチャーベースモデリング

7.10 課題

1. ★ 四角錐、六角柱、そして1つの角を平面で切り落とした立方体について、V、E、Fを数え、其々でオイラーの公式を確かめて下さい。
2. ★ 点$q_1=(4.2,1,0.5)$、$q_2=(2,3,0.5)$、$q_3=(3.5,1,1.2)$を7.2節のブラケット$(A\cup B)-C$に対して判定し、木の全ての節点のin・on・outの値を書いて下さい。
3. ★★ 7.5節のウイングドエッジの表を使い、$e_1$から始めて$v_1$の周りの面を、$e_8$から始めて上面$f_1$の稜線を求めて下さい。両方の答えを立方体の図と照らし合わせて下さい。
4. ★★ 何も無い所から三角柱を作るオイラー操作の列を書き、各操作の後のV、E、Fを書いて下さい。操作は幾つ必要で、立方体の13個と比べてどうですか？
5. ★★★ 種数$g$の閉じた三角形メッシュ（シェル1つ、リング無し）は$F=2V-4+4g$枚の面と$E=3V-6+6g$本の辺を持つ事を示して下さい。大きなメッシュでは、ハーフエッジ構造は頂点1つあたり大体何本のハーフエッジを必要としますか？又、其の数に種数が殆ど関係しないのは何故ですか？

選択問題

問1 ★ 次のうち、形状モデルについて正しい物はどれか。

あ	ソリッドモデルは内側と外側を区別するので、体積や質量を計算し、部品同士の干渉をチェック出来る。
い	ワイヤーフレームモデルは物体の面を保存するので、体積を計算出来る。
う	サーフェスモデルは各面のどちら側が内側かを知っているので、2つの部品の干渉を常に検出出来る。
え	ワイヤーフレームモデルは常に1つのソリッドを一意に決める。
お	サーフェスモデルは曲面を含む事が出来ない。

問2 ★★ 1つのシェルから成るソリッドが、頂点32、辺48、面18を持ち、其のうち2つの面が其々3つの内側のループ（リング）を持つ。オイラー・ポアンカレの式によると、此のソリッドを貫通する穴の数$H$は幾つか。

あ	此れらの数を持つ正しいソリッドは存在しない。
い	$H=0$
う	$H=1$
え	$H=2$
お	$H=3$

問3 ★ 次のうち、境界表現のデータ構造について正しい物はどれか。

あ	ハーフエッジ構造では、各ハーフエッジが其の辺を共有する両方の面を保存する。
い	頂点リストと面リストだけで、頂点の周りの面を探索無しに定数時間で見つけられる。
う	ウイングドエッジ構造では、各稜線が其の2つの頂点、2つの面、4本の隣の稜線、合わせて8つの参照を保存する。
え	ハーフエッジ構造では、ハーフエッジと其のtwinは同じ面に属する。
お	ウイングドエッジ構造は、3枚の面が共有する稜線を何も変えずに表現出来る。

7.11 実践課題

小さな家を手で完全にモデリングします。
描き、此の章の全ての方法で保存し、オイラーの公式で確かめ、そして変形します。
方眼紙（又は等角方眼紙）、定規、鉛筆、2色のペン、電卓を用意して下さい。

家は直方体$[0,2]\times [0,2]\times [0,2]$に切妻屋根を載せた物で、棟は$(1,3,0)$から$(1,3,2)$まで伸びています。
前面（$z=2$）は五角形$(0,0,2)$、$(2,0,2)$、$(2,2,2)$、$(1,3,2)$、$(0,2,2)$で、背面は$z=0$の同じ形です。

1. 描いて番号を付ける。 家を平行投影（等角投影又はキャビネット図、第5章）で描き、頂点に$v_0$から$v_9$の番号を付けて下さい。前面の五角形が上の順に$v_0$から$v_4$、$v_{i+5}$は$v_i$の真後ろです。面に名前を付けます（前面、背面、底面、左の壁、右の壁、左の屋根、右の屋根）。
2. 頂点リストと面リスト。 頂点リストと面リストを、各面の頂点を外側から見て反時計回りに並べて書いて下さい。各面について外積で向きを確かめます。法線は家から離れる向きでなければなりません。
3. ウォータータイトとオイラーの確認。 全ての面の向きの付いた辺を全て書き出し、各辺が其々の向きで丁度1回ずつ現れる事を確かめて下さい。V、E、Fを数え、$V-E+F=2$を確かめます。
4. ウイングドエッジ。 全ての稜線に向きと$e_0$から$e_{14}$の名前を付け、前面の五角形の5本の稜線と棟の稜線について、ウイングドエッジの表（start、end、left、right、4つのウイング）を埋めて下さい。次に、7.5節の検索で棟の頂点$v_3$の周りの面を求めます。
5. オイラー操作。 家を作るオイラー操作の列を書き（前面の五角形から始めます）、各操作の後のV、E、Fを記録して下さい。
6. 体積。 家は前面の五角形の平行移動スイープです。五角形の面積（正方形と三角形に分けて求めます）と家の体積を求めて下さい。
7. 変形する。 (a) 棟全体を$y=3.5$に持ち上げ、全ての面が平面のままである事をスカラー三重積で確かめて下さい。(b) 代わりに前の棟の頂点$v_3$だけを$y=3.5$に持ち上げると、どの面が平面でなくなりますか？(c) 棟から各屋根面に沿って0.25ずつ動かした所で棟の稜線を面取りし、新しいV、E、Fを求めて下さい。

自分で確認する方法：手順3では、同じ向きで2回使われる辺も、1回しか使われない辺もあってはいけません。
手順5の全ての操作の後と完成した家で、$V-E+F$は2でなければなりません。
手順4で$v_3$の周りの面は、図の中で棟の手前の端に集まって見える3つの面と丁度一致しなければならず、又、頂点の周りの面の数は常に其の周りの稜線の数と等しくなります。
手順6の体積は、直方体の8と、直方体に屋根の高さ分の箱を丸ごと足した12の間になければなりません。
そして手順7 (c)で面取りした家も、やはりオイラーの公式を満たさなければなりません。