＞トップ

稜線探索法についての解説、というか、まだメモ

3D コンピュータグラフィックスにおける、隠線消去の技法のひとつである稜線探索法についてのメモ。

輪郭線（輪郭候補線）は複雑になりうる

W ペントミノの例を示す。輪郭候補線は一筆書きのループになっているが、多重に干渉している。


また、テトラキューブの一例を示すが、ループが 2 個とも 1 個とも解釈できる形状になることがある。


以上から、輪郭をひとつながりとして扱うのは面倒ではないかと思われる。

輪郭候補線が通る点で、不可視数が不連続になること


この例で、左端の頂点の側から辿ろうとした場合、赤で示した可視の稜線と、青で示した不可視の稜線を、デプステスト以外で識別する方法はない、と思われる。

参考文献について

(1)『コンピュータ・グラフィックス』

穂坂衛著、産業図書発行『コンピュータ・グラフィックス』（1974）5章 5.4 節「隠線消去問題」 pp. 257〜263

解説は理論的には詳しく、特に変なところはないようである。ソースコードによる説明はない。文献のrefは「穂坂、高橋栄：3次元形状処理方式と Hidden-line algorithm、10回情処大予、p. 77（1969）」「穂坂、木村文彦：立体の内部記述と立体処理の一般解法、14回情処大予、p. 407（1973）」等

(2)『実習グラフィックス』

佐藤義雄著、アスキー発行『実習グラフィックス』（1986）3章 3.1 節「稜線探索法」 pp. 87〜127

参考文献として (1) を挙げている。(1) では、辺（edge）を総称して「境界線」、凸か凹かに応じて「稜線」「谷線」と呼んでいるが、こちらでは総称して「稜線」、分ける際は「凸稜線」「凹稜線」としておりわかりやすいように思う。

しかし、ところどころ怪しい記述が見られる。p. 96に、「輪郭稜線のうち、谷線（凹頂点を少なくとも一端に持つ稜線）」という文章があるが、この文献では使っていない「谷線」という用語を突然使っており、しかも説明が変で、袋小路でない谷すなわち、どちらの端も混合頂点（凸頂点でも凹頂点でもない頂点）である凹稜線であっても、この文の説明には該当する。

また、輪郭候補線がループになることや、不可視数の説明がなく、一方であらかじめ他の面に干渉されない面を計算で求めておくなど、BSP法っぽい手法をとりいれたハイブリッド的アルゴリズムを実装しているように思われる。

文章と図による解説だけでなく完全なソースコードも付いているが、古典的 Basic で書いてあるのでコードを読むのは苦労するかもしれない。また前述の「谷線」の説明が変であることが波及しているのか、本文ではほとんど説明されない H7 というフラグ変数があったりする（どうもBSP法っぽい処理をしている？）。

以下に用語の対応を表にして示す。

『コンピュータ・グラフィックス』『実習グラフィックス』
外側への法線表向き法線ベクトル
境界線稜線
稜線凸稜線
谷線凹稜線
---前方稜線
---後方稜線
---可視稜線
凸頂点凸頂点
凹頂点凹頂点
混頂点混合頂点
干渉点干渉点
---可視点
視点向面前方面
反視点向面後方面
---優位面
輪郭候補線輪郭稜線
輪郭線---

(3)『CAD 工学』

山口富士夫著、培風館発行『CAD 工学』5章 5.4 節「一般の対象形状に対する隠れ線・面の消去」 pp. 139〜141

参考文献は、前述の『コンピュータ・グラフィックス』と、次節の (1) と (3)

(4)『Jim Blinn's Corner 日本語版 (1)』

Jim Blinn著、オーム社発行『Jim Blinn's Corner 日本語版 (1)』（2004）10章「分数の不可視数」 pp. 89〜101

頂点と辺がちょうど重なった場合のために、不可視数（ある点の手前にある面の数。これが >0 だったら不可視）に分数を導入することを提案している。

以下、この本に ref のある文献