JPH01201777A - 三次元図形処理システムにおけるパッチのｂスプライン記述のトリミング方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （発明の技術分野〕 本発明は、高性能三次元図形処理システムに関する。

〔発明の技術的背景及びその問題点〕

典型的な高性能三次元図形処理システムはバッチごとに
関数により規定される表面パッチとなるべき表面を記述
する。このような関数としては、たとえば、不拘−有理
Ｂスプライン（ｎｏｎｕｎｉｆｏｒ＋５ｒａｔｉｏｎａ
ｌ　Ｂ−ｓｐｌｉｎｅ　）がある、Ｂスプラインを使用
すると表面パンチの緑がある程度制限される。

生関数がｘｙｚ空間の座標の値を計算する。長方形のｕ
ｖ空間に、より、Ｂスプライン・パンチ発生関数が、あ
る形状の縁を有する表面パンチを表わすことができる正
確さが制限される。たとえば、その内部に取り除かれた
円形部分を持つ長方形領域であるパンチについて良好な
りスプライン記述を作ることは困難である。長方形領域
あるいは円形部分はいずれもそれ自身は実用的であるが
、それらの組合せはパッチ・レベルでの単一統合（ｓｉ
ｎｇｌｅ　ｕｎｉｆｉｅｄ）　Ｂスプライン記述として
はあまりにも複雑で幼稚である。パッチを細分すれば、
まず第一にパッチを持たせるという目的が阻害される。

トリミングは円形部分に対して別の一つを持つ長方形領
域のＢスプライン記述を増大し、−方のＢスプライン記
述が他方によって規定された表面を「刈り整える」ハイ
ブリッド表面パンチを作る方法である。

従来の技術では、トリミングは装置座標を表示ハードウ
ェアに送る前に図形処理システムのソフトウェアにより
行われていた。このようなトリミングは必然的に非常に
複雑な仕事であり、−最に活動映像または対話式システ
ムに使用するには速さが遅すぎる。

〔発明の目的〕

本発明はＢスプラインの効用を保持するとともに表面記
述のその技術により得られる利点を活用し、しかも同時
に高速トリミングができる方法を提供することを目的と
する。

〔発明の概要〕

本発明の好ましい方法によれば、トリミングはハードウ
ェア図形処理加速器でＢスジ９４フ表面パッチ記述に関
して行われる。この加速器はトリムしていないパッチの
バッチ発生関数のＢスプライン記述と、パッチ発生関数
のＵシパラメータ空間におけるトリミング曲線のＢスプ
ライン記述とを受取る。トリミング曲線のＢスプライン
記述はそれ自身パラメータｔの関数である０図形処理加
速器は、ＸＹｚ空間のその関連多角形がパンチを近似す
るｕｖ空間内の個々の要素スパンの一点一点の表現に加
えて、ｕｖ空間内の各トリミング曲線の点表現により充
分密度の濃い点を計算する０図形処理加速器は、トリミ
ング曲線の直線近似線分がどこで要素スパン境界と交差
し、関連多角形の部分を刈込み整理する要素スパンの頂
点を変えるかを求める。加速器はトリムされていない多
角形とこれを切断するトリミング曲線とを表わす頂点表
の連結リストのデータ構造を構築することによりそれを
行う、データ構造のリストの上を適切に動き廻ることに
より装置座標で表わしたトリムずみ多角形の頂点のリス
トが作られる。このリストは更に図形処理加速器の他の
ハードウェアによりピクー　セル・レベルにまで処理す
ることができる。

丸め誤差の害を避けるためかなりな注意を払う。

スパン内のどこにトリミング曲線があるかを記述する機
構によりトリミング動作が処理中の多角形におそら（影
響することがあり得ないトリミング曲線を考えることか
ら解放される。他の機構はトリミング曲線機能の非理想
的パラメータ化の影響を補償し、不必要に数多くの多角
形頂点を発生しないようにする。トリミング方法は数多
くのトリミング曲線を用いてパッチを取扱うパッチの帰
納的細分化とも適合する。

〔発明の実施例〕

三次元表面が図形処理システムの内部で表わすことがで
きるという一つの方法を考えることから始めよう、たと
えば、第１図に描いたもののような（ら形表面ｌを表わ
そうとすることを考える。

これは全表面ｌをより小さな部分（一般にパンチと呼ぶ
）に分割することにより行われる。この分割したものの
中のパッチ２を図示しである０表面を適宜にくら形１は
どに複雑にするには、非常に多くのパッチが必要になる
であろう、簡単のための一つのパッチ２だけを示すこと
から始める０図形処理システムは表面を適切なパッチに
分割する成る手段を備えていることがわかるであろう、
また、第１図の他の各種曲線は他のパッチを示すためで
はなく、表面１の形状を認める際の補助として示されて
いる。更に、表面ｌは双曲放物面に似ているが、説明す
る方法は不規則（「自由形態」）表面、特にパラメトリ
ックロスプライン記述から得られるもの、に特に適用で
きる。

パッチに関連してパラメータ空間３の部分５がある。こ
の部分をスパンと言う、ｘｙｚ空間の三次元表面を記述
するには二次元パラメータ空間を採用する。現在の例で
は、二つのパラメータはＵとＶとであり、それぞれは関
連する最大値と最小値との間で変化することができる０
図に示すように、−組のパラメトリックパッチ発生式４
がパラメータ空間３内の値をＸＹＺ空間に写像してパッ
チ２の上に乗る（Ｘ、Ｙ、Ｚ）二数を発生する。

最新の高性能図形処理システムは、欲しくなる可能性の
ある特定の図とは無関係に、対象の完全な記述を格納す
る。この記述はデータスペースの形を取ることが非常に
多く、特に対象の部分が別々に記述されて、次に参考の
ため、おそら（は何回も展開されるときにそうである０
表面の点を徹底的に集めてデータベースに格納するので
はな（、数値を所望の程度の分解能で発生する近似関数
のように、−層簡潔にまとまった形式の記述を使用する
のが普通である。特定の図が欲しいときは、データベー
ス内の近似関数を評価して最初に見つかった点に対して
平行移動または回転を計算すれば見つかる。Ｂスプライ
ンはこのような簡潔な表現をパラメトリック関数により
得る技法である。

Ｂスプラインの導入説明でさえ、ここで説明できる範囲
を超えており、読者はこの主題に関する各種参考論文を
参照するのがよい（たとえば、Ｊ。

Ｄ、ＦｏｌｅｙおよびＡ、Ｖａｎ　Ｄａ−著の対話式コ
ンピュータ・グラフィックスの基礎（Ｆｕｎｄａｓ＋ｅ
ｎｔａｌｓ　ｏｆＩｎｔｅｒａｃｔｉｖｅ　Ｃｏｓ＋ｐ
ｕｔｓｒ　Ｇｒａｐｈｉｃｓ）　、１９８４年、Ａｄｄ
ｉｓｏｎ−Ｗｅｓｌｅｙ発行、また１９８３年９月のＩ
Ｅ２１ＩＣｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　ａｎｄ
　Ａｐｐｌｉｃａｔｉｏｎ　％　ＶＯｌ、３Ｎ１６の曲
線および表面を表現する有理Ｂスプラインと題する論文
）、幸いにも、ここではＢスプラインとは何であり、こ
れがどういう働きをするかについて深く理解する必要は
ない、所望の固体対象および表面のＢスプライン記述を
発生する各種ソフトウェア・パフケージが存在している
。ここで行おうとする要点は、本発明の方法が固体対象
および表面のＢスプライン記述と組合せて使用するのに
役立つが、Ｂスプラインを使用する必要が少しも無いと
いうことである。しかしながら、好ましい方法がＢスプ
ラインを利用する図形処理システム内で使用されてきた
ので、方法をその設定で記述するのが最も便利である。

その図形処理システムはヒユーレット・パラカード９０
００・３２０ＳＲＸ型であり、これは特にＢＰ９８７２
０Ａ型図形処理加速器を備えている。

特に、第１図は当該表面１の各点６をパラメータ空間３
の成る部分５の対応する点７で表わし得ることを示して
いる０図形処理システムのユーザはそのシステムの取扱
説明書に記された規定の方法でそのシステムと対話する
。適切な命令を使用することにより所望の表面を作りあ
げることができる。一般に、表面は複数のパッチで構成
される。

ＸＹＺ空間の表面上の各パッチについて、図形処理シス
テムの内部動作によりＵおよびＶの三つ（または多分四
つ）のパッチ発生関数が発生する。

変数ＵおよびＶはパラメータ空間３に属する０点６のＸ
座標は（多項式）関数Ｆｘ　（ｕ、ｖ　）を評価するこ
とにより見つかる。対応する関数ｐｙとＦｚとが点６の
ｙ座標と２座標とを作る。３座標に関する更に一般的な
場合（有理Ｂスプライン）には次の四つの関数を利用す
る。

ｘ　ｓｗＦｘ　（ｕ、ｖ）／　Ｈ（ｕ、ｖ））ｌ　−Ｆ
ｙ　（ｕ＋ｖ）／　Ｈ（ｕ＋ｖ）ｚ　＝Ｆｚ　（ｕ、ｖ
）／　Ｈ（ｕ、ｖ）この場合に各関数ＦＸ％　Ｆ３’％
およびＰｚは間数Ｈで割ることにより有理化されている
。説明する方法は有理または非有理の不拘−Ｂスプライ
ン表現のいずれにも適合することができる。

概念的には、表面に関するすべてのビクセル値を、変数
ＵおよびＶの充分に密度の濃いカルテシアン積について
Ｂスプライン・パッチ発生関数を評価することにより、
すなわち、パラメータ空間３の中の充分に密度の濃い点
の集まりを評価することにより計算することができる。

ただし、実際上は、このような方法は法外な量の実行時
間を必要とするので、−層迅速に、かつ−層容易に行わ
れる計算だけを必要とする人々のために一般に回避され
る。第６図〜第８図に関連して説明しようとする多角形
法はこのような好ましい方法である。

この方法によれば、所定のパッチについてパラメータ空
間で評価された点の集合が、濃淡により補間するとき、
受容可能ななめらかな表面を生ずる多角形の多角形頂点
を生ずるのに丁度充分なだけの濃さになるように選択さ
れる。各多角形にはその値がハードウェアで行う直線補
間で比較的容易に見出される多数のビクセルが入ってい
るので、映像作製時間がかなり短縮される。

関数４の一つの集合が考慮中の完全な面を全部記述する
ということはありそうもない、その代わり、所望の表面
を小さな領域上で良く近似するＢスプライン、バッチ発
生関数の集まりが見つかる。

この断片式近似はパラメータ空間をスパンと言う領域に
分割する。断片式近似は実際に表面を対応するパッチに
分割するものである。バッチにするには、その対応する
Ｂスプライン関数を対応するスパンの範囲にわたり評価
する０表示された対象の所定の分解能（すなわち、多角
形の大きさ）にしたがい、ＵおよびＶを増進させる適切
なステップの大きさを選択する。パラメータＵはＵｍｉ
ｎからＵｍａｘまで等しいステップにすることができる
。−方、パラメータＶはＶａｉｎからνｗａｘまで等し
いステップ（必らずしもＵのステップと同じではない）
にすることができる。スパンのこの評価により、表示さ
れるまでに一般に更にかなりな量の処理を受ける「生の
」多角形頂点が作られる。

このように、表示すべき表面はバッチの集まりとして記
述され、その各々が、対応するスパンを備えていること
がわかる。各スパンに関連するのはＢスプライン・パン
チ発生関数の特定の集まりである。

先に、適切な命令によりユーザは所望の表面を作り上げ
ることができると述べたことを思い起すこと、たとえば
、穴のおいている平板が所望の対象であると考えよう、
典型的な固体モデル化パッケージを用いてユーザはメニ
エーから、長方形固体のような、適当な原始形状を選択
し、その寸法を指定する０次にユーザは穴の中心の位置
を指定し、板から所定直径の円筒を「差引＜」、長方形
板のＢスプライン記述を作ることは実際的事柄である。

穴を「キリもみする」ことにより除去する円筒のＢスプ
ライン記述を求めることも実際上の事柄である。ただし
、既に穴がおいている板が其自身の特定のＢスプライン
記述を持っている原始形状であると考えることは実際的
でない。

本発明の方法は実用上のＢスプライン記述を持っていな
い複雑平面の問題に対する解答を与える。

板の穴の縁が丁度ＸＹＺ空間にあるときは、ｕｖ空間内
に、評価したとき、穴を作るように除去すべき材料の縁
を正確に記述するか厳密に近似する対応点が存在する。

これらの点はＵν空間内のトリミング曲線と呼ぶ曲線に
沿って存在している。トリミング曲線は一つ以上の関数
で表わすことができる。これらの関数は固体モデル化バ
フケージにより見つけることができる。その後で、パッ
チ発生関数を対応スパンについて適格に評価することに
より、「差引かれた１部分を備えたパンチを描くことが
できる。この適性化は、パッチ発生関数の評価中に、手
近にある（ｕ、　　ｖ）対がトリミング曲線の内側にあ
るか外側にあるかを確認するという形を取る。適性化に
より、関連する（Ｘ、Ｙ、２）二数を表示するか否かに
関する判断が生ずる。

二数を表示することになれば、事は先述のとうりに進行
する。しかし、その（ｕ、ｖ）対の評価により発生する
多角形頂点が、差引（べき領域内に存在することになれ
ば、二数を表示することができず、現存する多角形構造
を修正しなければならない。

第２図はバッチ２から差引くべき領域９のＸＹＺ空間に
おける境界を記述するトリミング曲線８の使用法を示す
、トリミング曲線８は、パラメータ空間３のスパン５で
規定される。好ましい方法２ε。

でトリミング曲線８はそれ自身Ｂスプラインで規定する
ことができる。パラメータｔの一対のパラメトリック式
９はｕｖ空間の２次元トリミング曲線を規定することが
できる。バッチ発生関数を作ってからは、トリミング曲
線関数９は有理または非有理の不拘−Ｂスプラインのい
ずれであってもよい。

表面が丁度バッチとそれらに関連する別のバッチ発生関
数の集合である場合には、トリミング曲線は一般に線分
と呼ばれる要素部分から断片的に組立てられなければな
らなむ１各線分にはそれ自身の特定のトリミング曲線関
数９がある。

この状態を第２図のトリミング曲線８について第３図に
描いである。そのトリミング曲線は多数の線分Ｓｔから
Ｓｈに分かれている。各線分にはｔ空間１０の対応する
スパンにわたり規定されているそれ自身の関数があるこ
とに注意すること。

第４図はトリミング曲線の応用の一般化を示す。

示したのは第２図および第３図に描いた状況と同じであ
るが、トリミング曲線１１が今回はｕｖ空間のいくつか
のスパン１２〜１５を横切っていることが異なる。この
状況は、運悪く、表面１から差引くべき部分９が対応す
る四つのパンチ１６〜１９を占めているために生ずる。

トリミング曲線１１の線分境界は第４図のその曲線上に
示しである。一般に、線分Ｓ、からＳ、までの間の境界
はトリミング曲線１１に沿うどこかに落ちることに注意
する。特に、スパン１２〜１５０間の境界に特別な関係
を持たせる必要はない。

第５図は第４図の線分化したトリミング曲＆１１１の断
片式表現を示す、１分ごとに別のパラメトリック式を使
用すること、およびこれらの式の各集合はｔ空間２０の
中のそれ自身の関連スパンにわたり規定されていること
に注意。

第１図およびバッチ発生関数の説明中に、多角形の概念
を手短かに導入した。今度は第６図から始めて、この話
題に戻り、多角形を用いて表面を表わす技法にトリミン
グがおよぼす効果について一層詳しく検討する。

第６図は、太い矢印にしたがって、４個のパンチ１６〜
１９に写像される４個のスパン１２〜１５を示す。

各スパンをトリミング曲＆ｉｌｌが横断するが、その目
的は結果的に得られる表面の刈り込まれた（あるいは「
差引かれたＪ　）　Ｍ域９を画定することである。現在
のところ第６図での我々の関心は（刈り込まれていない
）多角形の発生にある。トリミング曲線１１がそれら多
角形に及ぼす影響をこの図および第６図に伴う本文から
始めて考案することにする。

バッチを発生するプロセスは一度に１バラＦ行われる。

したがってスパンは一度に一つ評価され、各スパンは一
つの対応するバッチを発生する。スパンの評価にはＵお
よびＶに対するステップの大きさを求めることが含まれ
る。これらステップの大きさは駄およびＶに対して必ず
しも同じではなく、各々は次のスパンの評価が始まると
再び求められる。すなわち、スパン１３に対するステッ
プの大きさΔｕ１とΔＶ！とは互いに等しい必要はない
し、スパンに対するステップの大きさΔｕｊおよびΔＶ
ｊとの間に何らかの関係がある必要もない、特に、簡単
のため、図では　等しいように描いてあったとしても、
Δｕｉが　Δ咳、あるいはΔｈと等しくなければならな
いという条件はない、おなしことは各ΔＶにも適用され
る。

図形処理システムのユーザはステップの大きさを少なく
とも間接的に制御することになる。成る方が可能性が多
い、たとえば、ユーザは図形処理システムに、結果的に
得られる多角形の縁がほぼ特定数のピクセルを備えてい
るようにステップの大きさを選ぶように指示することが
できる。一般に、ステップの大きさはスパンごとに新し
く再決定することができることに留意すること。

スパンに対してステップの大きさを選択するとそのスパ
ン内部の（ｕ、ｖ）対の集まりが決まる。

これをスパン１２〜１５の中の点線で表わしである。

点線同志の交点、および点線と、スパンの境界を表わす
実線との交点はパンチ発生関数が評価される点である。

たとえば、点２１〜２３でパッチ発生関数を評価すると
多角形頂点２４〜２６が生ずる。

第６図から離れる前に注意する事項が更に二つある。第
１に、パンチ１６〜１９の多角形の隣り合う縁は直線線
分である０図でこのことを示す試みが行われてきた。対
照的に、パッチの境界と、トリムされた領域９の縁とは
はるかに滑らかに現れてでいる。これらも直ｖＡ腺分に
することができるが、かなり短い直線線分となる。すな
わち、パッチ内のこれらの線を作るのに評価されたｕｖ
空間にはも９と多数の点が存在する。実質的に、余分な
点を゛　　スパン評価プロセスに滑り込ませる機構が存
在する。この微分密度という概念についてはこの後の話
題の中で更に説明することにする。第２に、パッチ発生
関数をｕｖ空間内の点で評価する上述のプロセスは、最
終的に刈り取られてしまうことになるものをも含めて、
スパンのあらゆる部分で点を評価する。トリミングはか
なり複雑なプロセスであり、可能な状況の幾つかを分析
しなければならない、たとえば、所定の頂点は、トリミ
ングによって全体的に影響されない多角形に、そっくり
そのまま刈り取られることになる多角形に、あるいは、
トリミング曲線と交差する多角形に属する。

この後者の場合に、多角形の一部は残り、一部は残らな
い、このため多角形の形状を変えてトリミング曲線に合
わせる必要がある。このため今度はその多角形の新しい
頂点、すなわち第６図に示すＵおよびＶのステップでス
パンを評価して発生されなかったものを見つけることが
必要となる。

今度は第７図を参照する。示したのは第６図の一部を拡
大したものである。特に、写像したトリミング曲線２７
の一部とともにパッチ１６および１７の部分を描いであ
る。「写像した」トリミング曲線とはパンチ発生関数に
よりパッチに写像されたトリミング曲線１１を意味する
。

パッチ境界に沿う２種類の多角形頂点を第７図に示しで
ある。中空の円は、ａ）第６図の点線とスパン境界との
交点の、およびｂ）点線同志の交点の、パッチへの写像
に対応する。黒塗り円はスパン境界に沿う別の（ｕ、ｖ
）対を評価することにより加えられる「余分の」頂点に
対応する。この余分な点はΔＵの各ステップを等しい要
素部分室 に分割−る、ΔＶのステップは同様に分割される。ユー
ザがこれら余分の頂点を加えるプロセスを成る程度管理
するのが普通である。

第７図ば写像されたトリミング曲線２７に沿う多角形頂
点をも示している０図を検討することにより、トリミン
グ・プロセスの一部として多数の良好な余分の頂点が多
角形に加えられていることが明らかである。これに関し
て言うべきことが多（あり、今度は第８図に戻ると、写
像されたトリミング曲線２７のパッチ１７に関する部分
を更に拡大覆し 翼たちのが示されている。

第８図に関しては重要な二つの基本的課題がある。第１
は黒（塗りつぶした正方形がどこから来るかということ
である。これらは写像されたトリミング曲線２７が交差
する多角形の多角形頂点として取られる、写像されたト
リミング曲線２７に沿う点である。トリミング曲線１１
は線分から構成されているということが想定されよう（
第５図を参照）。

第８図のか伊瞳・この例の基礎として役立つ第５図の特
定のトリミング曲線１１について、線分Ｓ、からＳ、は
パッチ１７をトリムするものである。

線分Ｓ６からＳ、までは（その、あるいは任意の他の、
トリミング曲線の他のすべての線分と同様）、線分ごと
に、ｕｖ空間で、中空の円に対応するスパン境界に沿う
点とその最も近い、第７図のパッチ境界上で隣接する黒
く塗りつぶした円との間の距離に各々がほぼ等しいＵと
Ｖとのステップを理想的に発生するΔｔを見つけること
によって評価される。Δｔを選定するこの仕事はパンチ
境界に対する余分な頂点に関連して行われるユーザの選
択二 に影響される。実際には（理想的な場合とは対象）、ト
リミング曲線１１を評価すれば、上述のように、役に立
つにはあまりに互いに密接しすぎて配置された多数の（
ｕ、ｖ）対が発生する。更に洗練するにはパラメトリッ
ク関数（手近の例ではこれらはＦｕ＆とＦＶｈ％　Ｆ、
ｔとＦｖｔ、ＦＢＩとＦ　ｗｅ）を評価することにより
発生する対を検討し、それらの先行者から光分離れてい
ない対を削除する。第８図の黒く塗りつぶした正方形は
（第７図のものも）これら洗練された（ｕ、ｖ）対でパ
ッチ発生関数を評価することにより得られたものである
。

第８図で重要な第２の事柄は中空の正方形である。これ
らは写像されたトリミング曲線２７と多角形の縁との交
点を表わしている。ＸＹＺ空間で交点を探すよりは、交
点の対応する点をｕｖ空間で探し、ＸＹＺ空間に写像す
る。特に、探すのはｕｖ空間の二つの直線線分の交点で
ある。直線線分の一つはトリミング曲線１１に沿う二つ
の連続する洗練された（ｕ、　　ｖ）対の間にある。他
の直線線分は第６図の点線またはスパン境界の一部（た
とえば、第６図の２８または２９）である。

第８図を離れる前に、多角形の部分を示す点線、および
トリミング・プロセスで見えな（なる多角形全体などは
表示してないことを注意しておく。

今度は第９図に目を転する。この図は高性能図形処理シ
ステムのハードウェア装置の変換エンジン部が実行する
活動の簡略疑似コードで説明したものである。このハー
ドウェア装置はこの明細書およびその図の後の部分に現
われる説明の主題を成すものである。上述の動作は第８
図に示したように主として多角形のトリミングである。

第９図は第８図と関連して記述した形式のトリミングを
実行する圧縮した街路地図として理解することができる
。

好ましい方法では図形処理システムは、その各々をいろ
いろにトリムすることができる、い（つかのＢスズ５４
フ表面を表示することができる。

各表面は一般に複数のパンチから構成されることになる
。トリミング動作は各バッチ内の多角形処理のレベルで
発生する。したがって、第９図の（ステップ１５と１６
とに関連する）ステップ１と２とはステップ３〜１４に
関連して説明するプロセスをすべての表面の各パッチに
適用する。ステップ２は図形処理システムと関連するコ
ンピュータにより実行されるソフトウェアで実施される
。とりわけ、ステップ２は、表面をパッチに分割し、表
現すべきパッチを選択し、関連スパンに対してυｗｉｎ
ｓυ−ａＸｓ　Ｖ−ｉｎｓおよびＶｍａｘを計算し、ど
のトリミング曲線のどの線分がパッチをトリムするのに
必要かを決定する。ステップ３〜１４は図形処理システ
ムのハードウェア内の多角形表現機構により表示するこ
とができる、トリムされた多角形頂点を発生する。

今度はステップ３から１４までのＦＯＲループの範囲内
の動作を考察する。この動作は主として各種多角形の発
生（ステップ３および１４により示した）とそれに続き
（かつ即座に）おこなわれるトリミング（ステップ４か
ら１３までに示した）とを含んでいる。

パッチ内の多角形発生の一般的順序を第１θ図の例題ス
パン３０により示す、そのスパンは、この例では、発生
すべき、トリムされていない各多角形について一つづつ
、１６個の要素スパンに区切られている。各要素スパン
の大きさは表面の所定の視覚的なめらかさに関するユー
ザの指示によって決まる。好ましい方法では多角形は前
進差分法Ｕｏｒｗａｒｄ　ｄｉＨｅｒｅｎｃｉｎｇ）と
呼ばれる技法によって作られるが、この方法では各要素
スパンの境界のＵ値およびＶ値を明白に計算する必要が
、ない。

前進差分法は要素スパンの各隅角でパッチ発生関数を評
価するより速いので望ましい方法である。

前進差分法の説明についてはＦｏｌｅｙとＶａｎ　Ｄａ
−の５３５〜５３６ページを参照のこと。

トリミング動作の追求は、発生しつつある多角形の要素
スパンに対応するクリップ限界を利用しなければならな
い０例のとうり、「クリップ限界」という言葉は当該の
窓を言う、窓の中の対象は保持されるが、窓の外の対象
は捨てられる。こ＼で記述されるトリミングにとって重
要となるクリップ限界は発生する多角形に関連するｕＶ
室空間要素スパン境界である。

残念ながら、上に注記したとうり前進差分法によりｘＹ
ｚ空間で多角形頂点を計算する動作からは要素スパンの
境界であるＵ値およびＶ値を明白には得られない、上に
注記したクリップ限界を使用しようとする場合には、こ
れを別に探さなければならない、ステップ４は現在作ら
れトリムされている多角形のクリップ限界（ｕｖ空間で
）を計算する。第９Ａ図にはクリップ限界ｕＬｉｆいｕ
、□ｊｈｔ　ｓＶ、。２、およびＶ、。１、。、を備え
た要素スパン３５が描かれている。たとえば、要素スパ
ン３５は第１０図の要素スパン＃６に対応することがで
き、ｕ　Ｌ＊ｔ＊は値３１となり、Ｕ、□、は値３２と
なり、ｖ　ｔｏｐは値３４となり、■、。い。、は値３
３になる。

第１０図を参照して、各種要素スパンのクリップ限界を
みつけるにはＵ軸およびＶ軸を区切るＵの値３１．３２
・・・とＶの値３３．３４、・・・とを求めなければな
らないことに注意する。好ましい実施例では、これらの
値は３２ビツトの浮動小数点２進数である。

所定の要素スパンの四つの隅角を独立に見つける手順を
想像することができる。このような手順は、どの要素ス
パンに現在関心があるかにはかかわりなく、同じ（Ｕ、
Ｖ）対（すなわち、そのビット・パターンが同一である
）が割当てられた隅角に対して常に得られる（すなわち
、Ｕ値３１とＶ値３３とが第１０図の要素スパン１．２
．５および６に対する共通隅角を記述する）ことを絶対
的に保証することができなければ回避される。独立に選
定した要素スパンに対してこのような保証を行うよりは
、好ましい方法は、次に説明するが、当該の成る上値を
記憶することにより、共通隅角が同じＵ値および同じＶ
値を確実に備えるようにしながら、多才 角形を別々の時刻に発生ぼることができる。

第１θ図に示すように、多角形発生の順序は行の中の左
から右へから、次に行方向に下から上へである。ステッ
プの大きさの値（△ＵとΔＶ）は前述のように見つかる
０行を（たとえば、要素スパン２から要素スパン３へ）
横断しながら、要素スパン２のｕ　ｒｉｇｈ＆が記憶さ
れ要素スパン３のｕＬｅｆ＆として再使用される０行の
始めにスパンのｕ、１．が（正確に）　ｕＬｅｆ＆とし
て取られる０行に沿って新しいＵ□ｍｋ１１がΔＵをｕ
ｒＡ□、の古い値に加えることにより見つかる０行の終
りにスパンのＵ□８を（正確に）　ｕｒ１ｗｈ＆として
取る。Ｂスプライン発生ソフトウェアが表面をパッチに
分割すると値ｕｓ！ａとＵ、□とが生ずる（第１図を参
照）。

最初の行を始めるとｕ、ｉｆｉが（正確に）ｖｂ＠Ｌ％
Ｌｈｍとして取られるｅ　ｖｔ＠１１の値はΔＶをＶ、
。１．。、に加えることにより見つかる。その後、新し
い行の始めにＶ、。、の古い値が格納され、新しいＶ＆
６ｔｌ。、として再使用される。新しいＶ。。

はΔＶをｖ　ｔｏｐの古い値に加えれば見つかる。要素
スパンの最上行を行うとＶ、□が（正確に）■、。、と
して取られる。

第９Ａ図の（ステップ１０と関連する）ステップ５は第
１１図を参照すれば更に良（理解することができる。こ
の図は多数の関連トリミング曲線３７〜４０が交差して
いるスパン３６を示している。トリミング曲線は一般に
分割されたＢスプラインとして定義されることを想起す
ること、特定のパッチをトリミングする際にどんな処置
を取るべきかを考察するときは、関連スパンの内側にあ
るトリミング曲線線分を考えなければならない。第９図
のステップ２と関連して言われていることにしたがい、
図形処理システムのソフトウェアの機構がトリミング曲
線の線分の一つ以上リストを各スパンと関連づける。た
とえば、第１１図のスパン３６のパッチを表現しようと
する場合には、トリミング曲線線分の四つのリスト（す
なわち、該線分のＢスプライン記述）、特定のパッチ発
生関数、スパンの定義、の他に成る他のスタッフを第９
図のステップ３〜１４を実行する機構に送ることになる
。現在の例におけるトリミング曲線の四つのリストの中
で、トリミング曲線３７と３８とに関連する二つは「閉
じた」トリミング曲線を記述するものとしてマークが付
けられ、トリミング曲線３９と４０とに対する二つのリ
ストは「開いた」ものとしてマークが付けられる。これ
により意味することはトリミング曲１３７と３８とのリ
ストはそれ自身で閉じる完成曲線を記述するということ
である。ただし、トリミング曲線３９と４０との部分は
スパン３６を表現することによって生じたパッチのトリ
ミングに影響を及ぼさないので捨てることができる。（
ただし、を舎てられる部分は成る他のパッチを表現する
とき必要になることがあり、その別のパッチのスパンを
伴うリストに現われる。）開いたトリミング曲線はその
関連スパンの外側で始まり、終わらなければならない、
好ましい方法では開いたトリミング曲線のリストに入れ
るべきトリミング曲線線分の数は増加して、丸め誤差に
より入って来る可能性のある不確かさあるいは誤差の他
に、「明確に」スパンの内側にあるかまたは「明確に」
スパンの外側にある始まり線分または終わり線分が入る
ことになる。これは、たとえば、スパンが、点線４１で
示したように、実際よりたとえば５パーセント大きいと
考えれば達成される。

今度は第９図のステップ６に進むと、これは（ステップ
９と関連して）トリミング曲線に沿う直線線分の概念に
関する。トリミングの仕事は各トリミング曲線に沿う多
数の点を見出すことを含むように進んでいる。たとえば
第８図を想起すること、写像されたトリミング曲ＮｌＡ
２７に沿う中空の正方形および塗りつぶした正方形はす
べてトリミング・プロセスの一部として（局部的には、
そのまま）見つからなければならない、特に、第９図の
ステップ６の「直線線分」は第８図の塗りつぶした正方
形の間の直線に対応する。ステップ６ＷＩ暗に含まれて
いるのは、パッチ発生関数４で評価するとき、塗りつぶ
した正方形を発生する（ｕ。

■）対を見つけることである。これは丁度今考察中の（
ｕ、ｖ）対を見つけることである。

第８図の写像されたトリミング曲線２７は第５図にしめ
ずトリミング曲線の線分Ｓ、からＳ、までに対応すると
いうことを想起することができる。

また同じトリミング曲線が第６図のＵν空間で示されて
いることを想起すること。現在探している（ｕ、ｖ）対
は第６図に示したのと同じｕｖ空間に属している。多角
形の発生のしかたの説明に関連して第６図を最後に使用
した。ここでは同様な動作が（ｕ、　　ｖ）対の別の集
まりを発生させて各トリミング曲線の各Ｂスプライン線
分の直線線分近似を作り上げようとしている。

求めたいのは、その間隔が多角形発生のスパン境界に加
えられた余分の頂点とはほぼ同じトリミング曲線に沿う
（ｕ、ｖ）対である。すなわち、トリミング曲線に沿う
Ｕのステップは余分な頂点の間のＵの距離より、もはや
太き（ないようにすべきである、余分な頂点が存在しな
ければ、最大距離を隅の頂点の間の距離とすべきである
。同じ要求条件はトリミング曲線に沿うＶのステップに
適用される。この（ｕ、ｖ）対の集まりは、他の、たと
えば、多角形発生に使用されたものとは異なる点な別の
集まりである。トリミング曲線に沿うステップは第８図
の塗りつぶした正方形に対応する。これらは第８図の中
空の正方形に対応する別の（ｕ、ｖ）対を求めるのに使
用される。今度はトリミング曲線に沿う最初のステップ
の見つけ方を説明する。

トリミング曲線はその独立変数としてｔを有するパラメ
ータ方程式により記述されることを想起すること、Ｕお
よびＶのステップの大きさをどの位にしたいかを知るこ
とが直ちにトリミング曲線関数を実際に評価するｔのス
テップの大きさを意味するものではない。更に、前進差
分法の技法を、パンチ評価関数について説明したと丁度
同じように、トリミング曲線関数を評価するのに使用で
きるならば望ましいことである。これにはｔのステップ
の大きさが一様でなければならない、必要なのはトリミ
ング曲線線分の評価を通じて不変のままであり、かつ第
８図の塗りつぶした正方形として使用するに充分な密度
の（ｕ、ｖ）対の集まりを発生する、ｔのステップの大
きさである。

基本的な考え方は各トリミング曲線の各線分を成る所定
の（および処理しやすい程に小さい）数の点で評価する
ことである。得られるＵの増進量の最大および得られる
Ｖの増進量の最大がそれぞれ貯えられる。これら増進量
はパッチ境界に沿う余分の頂点の間のＵおよびＶのそれ
ぞれの距離と比較される。比較が有利であればｔの所望
のステップが見つかっている。比較が不利であれば、ｔ
のステップの大きさは得られた最大のステップの大きさ
と所望のステップの大きさとの比にしたがって調節され
る。この確認プロセスはＵおよびＶに対して別々に行わ
れ、ｔのステップの大きさに対して二つの座標を生ずる
。二つのステップの大きさのうち小さい方が選択される
。

第９図のステップは第１２図を参照し、コーエン（Ｃｏ
ｈｅｎ　）およびサザーランド（Ｓｕｔｈｅｒｌａｎｄ
）のクリッピング・アルゴリズムを理解すれば理解する
ことができる。（このアルゴリズムの説明については、
ＦｏｌｅｙおよびＶａｎ　Ｄａｍの１４６〜１４９ペー
を参照、）第１２Ａ図に考察中のクリップ窓４３を横切
る（ｐ＋からＰ２への方向の）直線線分４２を描いであ
る。ｔの−様なステップの大きさを見つけ前進差分法を
使用してトリミング曲線関数を（ｔの増加する方向に）
評価する目的はトリミング曲線に沿う充分な数の点を見
つけることである。これらの点は図の塗りつぶされた正
方形であり、それらの間の指示された直線線分はＢスプ
ライン関数で記述された理想トリミング曲線の厳密な近
似である。クリッピングは各直線線分４２とクリップ窓
４３との交点（もし存在すれば）を見つける。これによ
り直線線分４２の正確にどの部分４４がクリップ窓内に
存在するかを確認することができる０部分４４がＮＥＷ
ＰＩ　とＮＥＷｈ　との間の線である第１２Ａ図の例で
は、ＮＥＨＰ　ｌ　とＮＥＨｈとはクリッピング・プロ
セスにより計算される。添字は線分４４の方向を示す、
明らかになるように、説明するトリミング方法はトリミ
ング曲線に沿う誘導運動の概念を利用している。簡単に
言うと、トリミング曲線（またはその直線近似）に沿っ
て走行するにつれて右側の要素が刈り取られる。

上述のコーエンとサザーサンドのクリッピング・アルゴ
リズムは多数の補強資料と関連して使用される。今度は
第１２図とＦｏｌｅｙとＶａｎ　Ｄａｍの１４６〜１４
９ページに記されているコーエン・とサザーランドのク
リ７ピング・アルゴリズムの方法とを参照して、好まし
い方法は次の改善案を取り入れている。

（ｌｌ　　クリップ限界はｕ　Ｌ１１ｆイｕ　ｒｉｌｈ
ｔ　、Ｖ　ｂＯｔｔｌｌｌｊｓＶ、。、の順にチエツク
される。そのわけはこれが多角形が発生される順序（す
なわち、行内で左から右へ、・行方向に下から上へ）だ
からである。

（２）　　クリップ窓と直線線分との相対的位置により
、ＮＥＷＰＩまたはＮＥＨＰ２、または双方が計算され
る。（第１２図は多数の可能な情況の中の二つだけを示
している。）クリッピング・アルゴリズムの任意の段階
でこのような交差点の計算が藁のＰ、に対して常に行わ
れて、第１２Ｂ図に示すように、同じ交差点が隣のクリ
ップ窓について確実に計算されるようにする。窓、とＰ
、からＰ２までの直線線分とを考えると、窓、の中のＮ
Ｅ、ＷＰｔと記した交点が計算される。窓、について同
じ直線線分を考えると、窓＝の中のＮＥＷＰ。

と記した交点が計算される。　ＮＥＷＰＩについて計算
された数値はＮＥＷＰＩについて計算された数値と同一
でなければならない。

数式 ％式％） ただし、 は二つの窓に対する交点のＶ座標の値を与える。

Ｕ座標は窓、に対してｕｒｌ、ｈｔあり、窓２に対して
ｕＬ＊ｆ％である。

（３）　　左、右、下、および上の各境界に対してクリ
ップすると、（浮動少数点丸め誤差のため）Ｎｌ！ＷＰ
ｔまたはＮＥＩＩＰ！の−っの座標をクリップ窓のわず
か外側に置くことができる。これはＮＥＷＰ。

（および／またはＮＥＷＰｘ　）のその外側座標をクリ
ップ後のクリップ境界に動かすことにより補正される。

このチエツクは四つのクリップ境界のすべてに対して行
われる。（丸め誤差は最終点の一つの座標をクリップ窓
の内側に容易に動かすことができる。この場合は後にト
リミング動作に問題を生ずることがなく、無視すること
ができる。）（４１トリミング曲線がＢスプラインとし
て表わされる場合には、所定の線分がそのスパンの終り
で（すなわち、そのスパン内のｔの最大値に対して）評
価されるとき得られる（ｕ、ｖ）対が次の線分がそのス
パンの始めで（すなわち、他のスパン内のｔの最小値に
対して）評価されるとき得られる（ｕ、ｖ）対と正確に
は等しくないというのが典型的な場合である。これは浮
動少数点丸め誤差の、または線分の間にそれらの「接合
点」を正確に収束させるＢスプライン近似が失敗した、
結果である。この問題は前の線分の最後の点の代りに後
の線分の最初の点を使用することにより回避される。

このようにして、所定のトリミング曲線線分に対する直
線線分近似の最後の直線線分がその線分の最後の点の次
から次の線分の最初の点まで進む。

（５）　　典型的には、所定の直ｖＡｖＡ分のＰ２が次
の直線線分のＰ、になる、こうなったら、Ｐ２の古い値
をＰｌにコピーすることができる０次にクリッパはクリ
ップ窓に対するＰｌの位置に関する情報を保存し、この
情報を再度計算しな（てもよいようにできる。

（６）　　クリンパは三つのフラグをセットする（これ
は後に使用される）。

ＡＣＣＥＰＴ　：　Ｐ、からＰ２までの直線線分が部分
的にまたは完全にクリップ窓の内側にあれば真である。

ＣＮＥＷＰ、　：新しいＰｌが計算された（すなわち、
Ｐｌがクリップ窓の外側にあった）場合に真である。

ＣＮＥＷＰ、　？新しいＰ８が計算された（すなわち、
Ｐｌがクリップ窓の外側にあった）場合に真である。

（７１ＡＣＣＥＰＴフラグが真であればクリッパはＮＥ
ＷＰ　＋とＮＥＷＰｚとを更新する。Ｐ、がクリップ窓
の縁または内側にあればＮＥＷＰ＋　”ｈ、　ｈは同様
に取り扱われる。

今度は第９図のステップ８を参照する。各直線線分が現
在のクリップ窓に対してクリップされると、点ＮＥＷＰ
、およびＮＥＷＰｔに関する情報がＡＣＣＥＰＴフラグ
が真の場合表のリストに保存させる。一般に、トリミン
グ曲線は現在のクリップ窓の中に多数の点を備えること
ができる。（第８図がここで役立つ。同図は写像された
トリミング曲線２７に沿う多角形頂点を示している。各
要素スパンでクリッピング・プロセスはトリミング曲線
について複数の点を戻している。）トリミング曲線はク
リップ窓に入り、その中で、出るまでに多数の点につい
て続けることができる。トリミング曲線は出たり再び入
ったりできる。トリミング曲線はクリップ窓の中間の成
る場所を単に出発（ｔ＝０の場合）することさえできる
、トリミング曲線はクリップ窓と忘の丁度−つの隅で交
差することがある。リストに加えられた表の表現で、所
定のトリミング曲線はリストに加えるべき一つ以上の表
を作ることができる。トリミング曲線にはこれに関連す
る方向（ｔの増加する値）があるので、ａ）クリップ窓
の、トリップ曲線が窓に入る境界に沿う交点、ｂ）クリ
ップ窓の内側にあるトリミング曲線に沿う点、およびＣ
）クリップ窓の、トリミング曲線が窓から出る境界に沿
う点、を区別するのに役立つ。これらの点をそれぞれｒ
ＢＥＧＩＮ　４点、ｒＭＩＤＤＬＥＪ点、およびｒＥＮ
Ｄ　４点と呼ぶことにする。一般にクリップ窓はいくつ
かのトリミング曲線により切断することができる。各個
々のトリミング曲線に対する表を特定のクリップ窓につ
いて作られたすべての表の、よりおおきなリストの中の
円形に連結した別々の要素リストに分けるのが望ましい
。

表の一般的様式を第９図に示す０表の最初の二つの記述
環４５と４６とは考察中の点（ＮＥＷＰ、またはＮＥＷ
Ｐ、　）のＵ座標およびＶ座標の２進浮動少数点値であ
る。第３の記述環４７は三つの部分を含んでいる。０ま
たは非０のトリミング曲線数（８ピントの整数）　、Ｌ
ＩＶ空間の点が乗っているトリミング曲線を区別する０
または非ＯのＢスプライン線分数、および６ケのフラグ
・フィールド、（最初の二つの部分の０は後に好ましい
実施例の更に詳しい説明で述べる特別な場合を示してい
る。）６ケのフラグ・フィールドは次のとうりである。

ＦＦＩ　　：この表がｒＢＥＧＩＮ　４点、ｒＭＩ［１
ＤＬＩＥＪ点、ｒＥＮＤ　４点、またはｒＯＴｌｌＥＲ
４点のいずれに対すのものかを示す２ビツトのフィール
ド。

ｒＯＴＨＥＲ４点は、下に記すように、隅角と余分な頂
点とを含む。

ＦＦ２　：クリップ窓のどの縁（すなわち、左、右、下
、または上の縁）に点が乗っているかを示す２ビツトの
フィールド、このフィールドは主として隅角および余分
な頂点を記す表として使用される。

ＦＦ３　　：この表を飛び越すべきかどうかを示す１ビ
ツトのフィールド、このビットはこの表が第９図のステ
ップ１１と関連して説明すべき特別の場合の一つである
場合にセットされる。このフラグを５ＫＩＰフラグと呼
ぶ。

ＦＦ４　　：第９図のステップ１２に使用してこの表が
既に取扱われたことがあることを示す１ビツトのフィー
ルド。このフラグをＭＡＲＫフラグと呼び、最初はＦＡ
ＬＳＥ　　（偽）である。

ＦＦ５　　：第９図のステップ１２に使用してこの表が
取扱われるべき最初の表であることを示す１ビツトのフ
ィールド。このフラグを５ＴＡＲＴフラグと呼び、最初
はＦＡＬＳＥである。

ＦＦ６　　：第９図のステップ１１で決まり、この表に
対応するＸＹＺ空間の頂点が現在表面上に残っている（
　ｒＯＮＪ　、刈り取られてしまっていない）か、ある
いは表面に存在しない（ｒＯＦＦＪ　、刈り取られてし
まっている）かを示す１ビツトのフィールド。このフラ
グをＯＮフラグと呼ぶ。

（現在表面上にのこっていることは頂点が実際に見える
ことを意味するものではない、陰れた表面の除去、裏面
の摘取り、およびクリフプングの動作は表面上に存在す
る点が最終的に表示されないようにすることができる。

他方、表面上に存在しない点は決して見ることができな
い、） 頂点の存在または非存在を、あるいは頂点が表面上にあ
るか表面外にあるかを、参照する機会が後に沢山あるで
あろう。同じ方法で多角形あるいはパッチ全体を存在す
るか存在しないか、ＯＮかＯＦＦかとして参照するのが
便利である。多角形およびパンチにはそれ自身の個々の
ＯＮフラグは無い、その存在または不存在はそれらの中
に一定の頂点が存在するか存在しないかによって決まる
。これら重要な頂点のＯＮフラグはそれらに遭遇したと
きに保存される。

第４の記述項４８は包みアドレスと次アドレスとを備え
ている。０でない包みアドレスは表のそうでない場合に
は直線形（すなわち、物理的に順序づけられた）リスト
の中の円形リンクである。０の包みアドレスは次の物理
的表もリスト内の次の論理表であることを示す０表はト
リミング曲線をｔの値が増加する方向に横断するとき順
に表のリストの終りに挿入される。トリミング曲線に対
して所定の円形に連結した要素リストを作るには、その
トリミング曲線に対する最初の表のアドレスをそのトリ
ミング曲線に対する最後の表の包みアドレスに挿入する
だけでよい。

次のアドレスは第９図のステップ１１と１２とで決まる
。このアドレスは表を存在している多角形の部分を表示
するのに使用される別のリストに結び付ける。

第９図のステップ８の説明の一部として、クリッパによ
り供給される情報に応じて表のリストを作り上げるのに
使用される所定基準を述べることが適切である。一般に
、ＰｌからＰｔまでの線のクリップ窓に対する位置によ
り、リストに０、一つ、または二つの表を追加すること
が必要になる。下記判断表はこれを行う方法を示してい
る。これら判断表においてフラグｌＮ５ＩＤＥはＰ２が
クリップ窓の内側にあるか外側にあるかを想起するのに
使用される。

トリミング曲線に沿う第１の（Ｐ＋、Ｐｇ）対のための
判断ＡＣＣＥＰＴ　＝　ＦＡＬＳＥのときｌＮ５ＩＤＥ
：＝　ＦＡＬＳＥＡＣＣＥＰＴ　＝　ＴＲＵＥのときは
以下の表を参照。

トリミング曲線の　　の（ｐ、、　ｐ、）　　のための
′１　中ｌＮ５ＩＤＥ　＝　ＴＲＵＥのとき、 ＡＣＣＥＰＴ　＝　ＦＡＬＳＥならば次の（Ｐ、、　Ｐ
、）対へ行（。

ステップ９とステップ１０とはそれぞれ上述のステップ
６および５と協働する。これら入れ子にしたＦＯＲルー
プの結果は各トリミング曲線を直線線分に分割すること
である。これら線分は次にステップ７によりその多角形
を表現しようとしている要素スパンに対してクリップさ
れる。ステップ８はクリップされた直ＮＩＡ線分を記述
する表のリストを作り上げる。

ステップ１１　（ａ）〜（ｄ）で、ステップ８で作られ
た表のリストが四つの方法で処理される。その第１は第
１３Ａ図および第１３Ｂ図に示す二つの特別の場・合に
関するステップ１１　（ａ）による検査である。

今度は第１３Ａ図を参照すると、要素スパン４９とクリ
ップ窓の「丁度外側」に存在する点５１を備えたトリミ
ング曲線５０とが示されている。第９図のステップ７で
説明したクリッピング・アルゴリズムにしたがい、トリ
ミング曲線５０がクリップ窓４９を「出て行く」場合の
交点５２が計算される０例題によれば、トリミング曲線
は右から再び中に戻る。

クリッパの他の交点５３を忠実に作り出す０点５１がク
リップ限界（これは例題では右側の縁であるが、どの縁
でもよい）に充分近ければ、計算に使用する数の分解能
が有限のため互いの最上部にある出口点と入口点とを生
ずることができる。これが第１３Ａ図が示すすべてであ
る。使用している演算精度の範囲内で、点５２と点５３
とは同じ点である。これが実際に「丁度かろうじて」外
側が意味するところである。

上述の状況が発生すると、一定の性質を備えた二つの表
が連続してリストに加えられる。特に、最初のものはＥ
ＮＤ表（第９図のステップ８に関連するＦＦＩを参照）
であり、第２のものはＢＥＧＩＮ表である。更に、二つ
の表のＵ値は正確に同じであり、Ｖ値は正確に同じであ
る。この事態はステップ１１　（ａｌにより表のリスト
を処理することに関連する第１の特別の場合である。

第１の特別の場合はトリミング曲線に関連する円形に連
結された各要素リストを調べることにより見つかる。要
素リストに論理的に隣接する（すなわち、包みアドレス
を適切に考慮して正しい論理的順序を作る）、それぞれ
が同じ（ｕ、ｖ）対を備えているＢＥＧＩＮ表およびＥ
ＮＤ表を含んでいるものがあれば、これら各表はＭＩＤ
ＤＬＥ表に変換される。

チエツクされる第２の特別の場合を第１３Ｂ図に示す、
この場合は一般に第１の特別の場合に似ているが、トリ
ミング曲ｖＡ５４がクリップ窓の中に「丁度かろうじて
」進入しているところが違う。

特に、交点の計算に使用する数の分解能が有限であるこ
とから点５６および５７に対して発生するＢＥＧＩＮ表
とＥＮＤ表とが同じ（ｕ、ｖ）対を備えることになる。

ただし、この場合ＢＥＧＩＮ表とＥＮＤ表とは点５８に
対するＭＩＤＤＬＥ表により分離される。

第２の特別の場合はステップ１１　（ａ）で同じ（ｕ。

Ｖ）対を含むＢＥＧＩＮ表とＥＮＤ表とを備えたＢｌｌ
：ＧＩＮ−ＭＩＤＤＬＥ−ＥＮＤのシーケンスを含む要
素リストに対するリストを調べることにより見つかる。

このようなシーケンスが見つかると５ＫＩＰフラグ（第
９図のステップ８を参照のこと）が三つの表すべてにセ
ットされる。これがこれらの表の後々の処理に及ぼす正
味の影響はそれらが効果的に削除されることである。す
なわちそれらは簡単に無視される。

ステップ１１　（ｂ）で表のリストが処理されて新しい
四つの要素リストが作られる。一つの要素リストはクリ
ップ窓の各緑に対するものであり、このような要素リス
トを用いて関連する緑を横断するトリミング曲線が数え
上げられる。これら新しい線要素リストは、要素リスト
を互いに結び付ける表（ＤＮＥＸＴ　ＡＤＤＲＥＳＳ７
４−７Ｌ、ドを用いて、そのまま、所定の場所に作られ
る。（これはＮＥＸＴ　ＡＤＤＲＥＳＳフィールドの中
間的利用に過ぎず、その最終的利用ではない、） その５ＫＩＰフラグがセットされていない単なるＢＥＧ
ＩＮ表とＥＮＤ表とが線要素リストに入れられる。

線要素リストを作るに際しては、ＢＥＧＩＮ表またはＥ
ＮＤ表の（ｕ、ｖ）対もクリンプ窓の隅の点であるとい
う場合に特別の注意を払う、この場合には幾つかのトリ
ミング曲線が横断しているクリップ窓を描いた第１４図
を参照するのが役に立つ、その（ｕ、ｖ）対も隅の点Ｉ
を（偶然に）記述するＢＥＧＩＮ表およびＥＮＤ表が上
縁５９の線要素リストに入る。同様に、隅■のＢＥＧＩ
Ｎ表またはＥＮＤ表は左縁６０の線要素リストに入る。

隅■のＢｌ！Ｇ　Ｉ　ＮまたはＥＮＤの各表は下縁６１
に関して入る。同様の仕方で、隅■のＢＥＧＩＮ表およ
びＥＮＤ表は右縁６２に関して入る。

一旦形成されると、各線要素リストは、どの縁を要素リ
ストが表わしているかにより、ＵまたはＶの上昇値か下
降値かによって分類される。属性。

ＢＥＧＩＮおよび［’ＮＯは分類に影響しない、左縁の
線要素リストはＶの下降値にしたがって分類される。

下縁の線要素リストはＵの上昇値にしたがって分類され
る。右縁の線要素リストはＶの上昇値にしたがって分類
される。上縁の線要素リストはＵの下降値にしたがって
分類される。

ステップ１１　（Ｃ１で表のリストが表を持つ四つの線
要素リストを隅角および余分の頂点の主リストにはさみ
込んでリスト内に新しい円形順序を生ずるように処理さ
れる。これはＮＥＸＴ　ＡＤＤＲＥＳＳフィールドの最
終的利用である。はさみ込みは（任意に）隅頂点Ｉから
始まり、クリップ窓の境界の周りを反時計方向に進む、
境界に沿う点の各表のＮＥＸＴＡＤＤＲＥＳＳフィール
ドは、それが余分な頂点であろうとトリミング曲線との
交点であろうと、更に境界に沿う次の点と結び付けられ
る０次の頂点が次の隅であるという場合さえあり得る。

この再順序付けは第１４図でＣ，Ｘ、Ｂ、およびＥと記
した点を接続する矢印で表わしである。任意に頂点！か
ら始まって、得られる順序はＣ−Ｘ−Ｅ−Ｘ−Ｘ−Ｃ−
Ｘ−Ｂ−Ｘ−Ｅ−Ｃ−Ｂ−Ｃ−Ｅ−Ｂ−Ｃである。　ｏ
ｘｆ　ＡＤＤＲＥＳＳフィールドを用いるこの再順序付
けに含まれる表の種類は隅、余分な頂点、およびＢＥＧ
　Ｉ　ＮおよびＥＮＤの交点表だけである。乱されずに
そのままになっているのはクリップ窓内部の各トリミン
グ曲線に沿う点を数え上げる各トリミング曲線の要素リ
ストである（　ＢＩｌ’ＧＩＮとＥＮＤと）？ｌＩＤ０
ＬＥ）　。

この点で、隅角頂点の表および余分な頂点の表を考察中
のクリップ窓の表の全体リストに載せておくという方法
については特に言及されていないことがわかる、明らか
に、このような表を追加するためおよび後に探すために
何らかの機構が必要であり、したがって上述のはさみ込
みを行うことができる。この種の事柄を行う各種技法が
周知であり、特定の実施例に利用するものは、大部分、
設計者の傾向に依存することになる。提示した実施例で
は、それらは関連ポインタにより区別されるそれ自身の
連結要素リスト内に配置されている。

第９図のステップ１１　（ｄ＋は第１４図と第９図のス
テップ１１　（Ｃ１とに関連して上に述べた円形連結リ
ストの各表に対するＯＮフラグを計算する。ＯＮフラグ
は頂点が表面上に残存しているか刈り取られてしまって
いるかを示す。ここで重要なのはＯＮフラグをどう計算
することができるかである。簡単に言えば、これはトリ
ミング曲線が要素スパンを去る点を見つけることによっ
て行われる。定義により、トリミング曲線上の各点は存
在するものと仮定する。トリミングには更にトリミング
曲線の左側（ｔの増加する方向にトリミング曲線に沿っ
て進むとき）にある要素スパン内のものもすべて存在す
るという仮定が□ある。したがって、トリミング曲線の
出口でもある要素スパン境界上の一点から出発すれば、
反時計方向の次の頂点、およびトリミング曲線に遭遇す
るまでのすべての後続頂点も存在する。読者は第１４図
への懇請によりｒ（ｔが増加するとき）の左側」と「要
素スパンの周りに反時計方向」との間の関係に関して得
心することができる０表面上に存在する頂点を摘み、時
計方向と反時計方向の両方に進ませてみよう。

ＯＮフラグは、出発点、たとえば第１４図の点６３とし
て任意のＥＮＤ表を拾うことにより計算される。

そのＯＮフラグは既にＯＮを割当てている。次に、ＢＥ
ＧＩＮ表に遭遇するまで、表の円形リストを横断し、各
ＯＮフラグもＯＮを割当てるようにセントする。

後続の表に対するＯＮフラグはＥＮＤ表に遭遇するまで
ＯＦＦを割当てるようにクリアされる。このプロセスは
最初のＥＮＤ表６３に再び遭遇するまで続けられる。こ
れが第１４図に示す例について、ＥＮＤ点６３から始め
て、行われると、ＯＮフラグの下記シーケンスが得られ
る（１１０は０Ｎ１０ＦＦ）　　：　１．１．１、Ｌ　
　１，１．０．１，１．１．０．１，１　０．０゜ 要素スパンの円形連結リストにＢＥＧＩＮ表またはＥＮ
Ｄ表が入っていない場合がある。これは二つの異なる方
法で起こり得る。第１は要素スパンにそれに関連するト
リミング曲線が全く無いことがある。このような要素ス
パンには隅角および余分な頂点のテーブルしか無い、第
２の場合は要素スパンに一つ以上のトリミング曲線が完
全に含まれている。（これらは要素スパン境界に接触ま
たは一致することがあるが、それらと交差せず、影響は
曲線が接触せずに完全に内部にあるときと同じである。

このような要素スパンは、隅角、余分な頂点、およびト
リミング曲線のＭＩＤＯＬＥに対する表を備えたリスト
を伴う。

上の第１の場合に対応する多角形を表現するときその多
角形の有無は隣接多角形の有無によって決まる。それは
完全に存在するか全く存在しないかのいずれかである。

第２の場合にはトリミング曲線は「考察中の単位」の最
小のもの（すなわち多角形）より小さい、トリミング曲
線は無視され、多角形全体が試みに保存される。ただし
、多角形が存在したままでいるということは必ずしも守
られない、多角形はそれ自身更に大きなトリミング曲線
の内部にあることがあり、したがって刈り取られてしま
う、第２の場合には、第１の場合のように、多角形の有
無は隣接多角形の有無によって決まる。

第２の場合は内部トリミング曲線自身が他のトリミング
曲線を含んでいるときでも説明したとおりになる。多分
この状況は表面上の存在と不存在とが交互に変る領域に
対応するであろう、ただし、このような特徴は選択した
多角形の大きさの内部で見るには小さすぎる。多角形の
大きさがトリミング曲線が要素スパン境界を横切り始め
るところまで減少する場合の状況と混同してはならない
。

圧絞に出した状況は通常どうり単に正常のトリミングを
発生するだけである。

前述のことから、各個別の多角形を処理している間に一
定の多角形が存在していたか存在していなかったかを思
い出す成る機構が必要であることが明らかである。この
機構はパッチの処理中に所定の要素スパンに対する一定
の表のＯＮフラグの値を保存することを含むことになる
。今度は第１０図と第１４図とを参照して、要素スパン
は明確な順序で取られていることを想起する。各行の最
初の要素スパンについて頂点ＩＶ６４のＯＮフラグは次
の行を処理するのに使用するために保存される。行内で
各要素スパンの頂点■のＯＮフラグはその行内の次の多
角形を表現する際使用するために保存される。

その他、最初の行の最後の要素スパンの頂点１１１６６
のＯＮフラグは現在のパンチの右側のパッチを処理する
際使用するために保存される。（これまでそう言わなか
ったが、表面はパッチの行および列から作り上げられて
いる。第１Ｏ図はパッチ内の要素スパンを参照するのと
同じ程度容易にそれを参照することができよう、）同様
に、（パッチの行を収容するには）パンチ内の要素スパ
ンの最後の行の最初の要素スパンの頂点１６７のＯＮフ
ラグも、頂点Ｉと正確に一致するＢＥＧＩＮ表またはＥ
ＮＤ表が存在すれば補足してから、保存される。このよ
うな保存も後続のパッチを処理する際に使用するためで
ある。補足は次の章で説明する特別な場合考慮している
。

第９図のステップ１１（ｂｌと関連して頂点■と同じ（
ｕ、　ｖ）対を偶然に備えているＢＥＧＩＮ表またはＥ
ＮＤ表は要素スパンの上縁の縁要素リストに含まれるこ
とになると言ったことを想起しよう。ステップ１１　（
Ｃ１で四つの縁要素リストが、頂点Ｉから始めて、要素
スパンの周りに時計方向にはさみ込まれるということを
言った。このことはトリミング曲線が頂点１６？を通過
することにより境界を横切る特別の場合に円形連結リス
ト内に実際に頂点■を記述する二つの表があるというこ
とを意味する。

その一つは頂点！それ自身に対するものであり一つは頂
点Ｉと一致するＢＥＧＩＮまたはＥＮＤに対するもので
ある。これら各表にはＯＮフラグがある。それらをセッ
トする規則および手近にある特別な事例に照らしてこれ
らをどう解釈するかに特別な注意を払わなければならな
い。

ＯＮフラグに適用される前述の三つの規則あるいは約束
事がある。それらは、 （ｌ）トリミング曲線に沿う点はすべて表面上に存在す
る。

（２）トリミング曲線に沿ってｔの値が増える方向に進
むとき、トリミング曲線の左側にある表面の点は表面上
に存在する。

（３）要素スパンの周りに反時計方向に進むとき、ＥＮ
Ｄに直ぐ続（頂点は、やはりＯＮの印の付いている次の
ＢＥＧ　Ｉ　ＮまでＯＮの印が付いた表を備えている。

同様に、ＢＥＧＩＮに直ぐ続く頂点は、それ自身ＯＮの
印が付いている次のＥＮＤまでＯＦＦである。

さてＢＥＧＩＮは頂点■と一致しているとしよう。

規則３により、頂点■にはＯＦＦの印が付（（不存在）
ことになる。ただし、現在のパッチの上の隣接パッチは
、規則２により、ＯＮ　（存在）である。

したがって、次のパッチまで伝ｔｔした頂点１６７に対
するＯＮフラグの値はＯＦＦからＯＮに変る必要がある
。

ＥＮＤは頂点Ｉと一致しているとしよう、規則３により
、頂点ＩにはＯＮの印が付（ことになる、ただし、現在
のパッチの上の隣接バッチは、規則２により、ＯＦＦで
ある。したがって、次のパッチまで伝播した頂点１６７
に対するＯＮフラグの値はＯＮからＯＦＦに変る必要が
ある。

このように、最後の行の最初の要素スパンの頂点１６７
のＯＮフラグを伝播させる一般的規則は次のようになる
。頂点１６７と一致するＢＥＧＩＮまたはＥＮＤでは頂
点１６７に対するＯＮフラグの値が不変に伝播するもの
はない、頂点１６７と一致するＢＥＧＩＮまたはＥＮＤ
が存在すれば、頂点夏６７のＯＮフラグの値の補数が伝
播する。

表面全体の文字どうり最初の頂点に対するＯＮフラグを
計算するには特別な規則が必要である。このような規則
は慣習に帰するが、その文字どうり最初の頂点に適用さ
れるトリミング動作に適合すべきである。たとえば、文
字どうり最初の頂点が常に表面上に存在すると仮定する
ことはその頂点を刈り取らせない０文字どうり最初の頂
点のＯＮ）ラグの計算に関する便利な規則は存在する（
ＯＮ）その表面縁または部分がトリミング曲線で束ねら
れなければならないとすることである。この方法を用い
て文字どうり最初の頂点をＯＦＦと仮定することができ
る。この仮定値はトリミング曲線が最初の多角形に対す
る少くとも一組のＢＥＧＩＮ／ＥＮＤ頂点表を生ずるな
らば無視される。というのはこのような場合には、上に
示したように、各頂点に対するＯＮフラグの正しい値を
計算することが可能だからである。このような−組の頂
点表が存在しない場合には、最初の多角形全体が実際に
刈り取られてしまっている。

表面の縁の周りのトリミング曲線が文字どうり最初の多
角形と関連する唯一のトリミング曲線であるときは興味
ある特別な場合が生ずる。この場合にはその多角形の左
縁および下縁がそのトリミング曲線と一致し、これら二
つの縁を記述する二組の頂点が生ずる。−組はそれら多
角形の縁に対する隅および余分な頂点が表面から無くな
っていることを記述し、一方それらの縁とトリミング曲
線との交点について計算された頂点は、定義により、表
面上に存在する。クリンパが動作する方法により、ＯＦ
Ｆ隅角の頂点はトリミング曲線上の頂点として複製され
るので、最初の多角形の形状が保存される。第１６図お
よび第１７図と関連して下に述べる頂点表の連結リスト
を処理する機構は二重の記述を容認し、ＯＦＦ縁を無視
してＯＮ縁から多角形を作る。二つのＯＦＦｇは二つの
ＯＮ縁と同じであることは気にならない。したがってＯ
Ｎ多角形に存在するのはＯＦＦ隅角である。

今度は第９図のステップ１２を考える。その任務は表の
リストを横断することである。ステップ１１はどの最初
の頂点がトリミング後も残存しているかについての情報
の他に、どのトリミング曲線の頂点をトリムされた多角
形に組入れるべきかについての情報をリストに追加した
。ステップ１１は元の多角形を二つ以上のより小さな多
角形に効果的に分割することができることに注意、ステ
ップ１２には入れ子ループという簡単な手順を使用して
ステップ１１で準備されたデータ構造を横断する。その
データ構造が第１４図の状況をどう表わすかを簡単に表
現したものを第１５図に示す、ステップ１２による横断
の結果はステップ１３により多角形を実際に表示する機
構に送られる一連の現在の多角形頂点である。ステップ
１２にはトリミング；プロセスから現われる現在の各多
角形または現在の要素多角形（他の部分が刈り取られて
しまってから残っている多角形の一部）に対する頂点の
一つの完全なリストを作る。

第１５図は第９Ｂ図のステップ１１Ｃを第１４図の例題
に通用して得られる頂点表の一つの可能な円形連結リス
トを簡単に示したものである。トリミング曲線＃１　（
この特定の多角形に対する）は第１４図の点６８から出
発しく１＝０）、他の二つのトリミング曲線は要素スパ
ンの外側のどこかから出発するという仮定を置く、第１
５図の円形連結リスト全体は境界リストと言ってもよい
０次のアドレス・フィールドはトリムされない多角形頂
点および多角形の縁とトリミング曲線との交点を境界リ
ストに結び付ける。境界リストに埋込まれてトリミング
曲線要素リストがある。トリミング曲線要素リストは物
理的順序づけと包みアドレス・フィールドとを組合せて
結び付けられる。各トリミング曲線に対して一つのトリ
ミング曲線要素リストが存在する。境界リストを横断し
ているときにＢＥＧＩＮに出会うと、境界リストに沿っ
て続行するか、トリミング曲線要素リストの横断へ切替
えるかの選択を行うことができる。（境界リストとトリ
ミング曲線要素リストとはＢＥＧＩＮ表とＥＮＤ表とを
分は持っている。切替えに必要なのはリンクの別のチェ
ーンをたどることだけである。）トリミング曲線要素リ
ストをそのＥＮＤまで横断すると、その点で境界に再び
入ることになる。

ステップ１２を第１６図に簡略流れ図として示してあり
、第１７図に第９図のステップ８で設定した情報を含む
表のリストで動作する擬似コードとして示しである。

第１６図の流れ図はこれに先行するものが何かという文
脈でとらえるときかなり自明であると信ぜられている。

これには、第１６Ａ図に示すように、「最初」であった
として印を付ける最初の頂点として円形に連結した境界
リストの中の任意の頂点を選択する外部ループが含まれ
ている。したがって外部ループは境界リストを横断する
。「最初」と印の付いた頂点に戻ったことがわかると、
プロセスは完了し、ループは終結する。外部ループの主
な動作はまだ巡見を受けないで表面上に存在する頂点を
見分けることである。このような頂点が見つかると、境
界リストにその位置が格納されるので、外部ループは中
間ループおよび内部ループがリストを自分自身で横断で
きるようになってからこの点でリストの横断を再開する
ことができる。

外部ループをこのように、そのまま「中止」して、更に
中間ループによるリストの処理が始まる。

中間ループは多角形リストに現在の非トリミング曲線頂
点を加え、ＢＥＧＩＮ頂点またはＥＮＤ頂点を見分ける
。　　ＢＥＧＩＮ頂点が見つかると、これが多角形リス
トに追加されて、内部ループに入る。ＥＮＤ頂点も多角
形リストに追加される。何故ならそれは多角形上に存在
する次の頂点であり、また今は巡見されたと印が付けら
れ、再び巡見されなければ更に処理されることがないか
らである。

内部ループは外部ループおよび中間ループを備えた境界
リストに沿って横断することにより頭に到達したトリミ
ング曲線要素リストを横断する。

中間ループはＢＥＧＩＮ頂点を多角形リストに追加して
から内部ループに入る。内部ループはトリミング曲線要
素リストの残りを完全に横断し、かつ関連頂点を多角形
リストに追加してしまうと中間ループに戻る０次に中間
ループは境界リストの横断を再開する。内部ループは新
しいトリミング曲線要素リストの頭に出会うたびに必要
に応じて再使用される。中間リストは閉じた多角形全体
が多角形リストに追加されてしまうと完了する。この状
態は中間ループが既に巡見されている頂点に戻ったとき
に検出される。このことは境界リストが完全に処理され
てしまったということを必らずしも意味するものではな
い、トリミングは元の多角形を二つ以上の要素多角形に
切断することができる。

外部ループがまだ完了まで動いてしまわないかぎり、境
界リストが記述した要素多角形がまだ沢山ある可能性が
ある。

完成多角形を多角形リストに追加すると中間ループは外
部ループに戻る。外部ループは境界リストの立ち去った
点からその処理を再開する。外部ループはまだ巡見され
ていない頂点を探してリストの横断を続ける。それが見
つかれば他の要素多角形全体を多角形リストに載せるの
に中間ループを再使用する。

頂点情報を隅角頂点および余分な頂点に対する多角形リ
ストに追加すること（第１６図の動作６９）はトリミン
グ曲線に沿う点に対する多角形リストに追加する（第１
６図の動作７０と７１）より本質的に容易である。先に
述べたとうり、前者の情報は前進差分の技法により計算
される。後者の情報は、ｕｖ空間の任意の点に対し、ｘ
ｙｚ空間の頂点位置と頂点における表面法線ベクトルと
を評価することを含んでいる。概念的に差違はないが、
これははるかに時間がかかる操作である。

第１７図は第１６図に流れ図の形で示したのと同じ動作
を行う擬似コードの簡略部分である。違うのは第１７図
が第９図のステップ８〜１１に関連して述べた裏構造を
更に多く取入れていることである。

表面多角形をトリムする好ましい方法の提示を方法に組
入れることができる一定の向上操作を検討することで締
めくくることにする０次の数節でトリミング曲線関数の
理想的パラメータ化とはほど遠い効果を最小にし、各要
素スパンおよびその多角形を処理しながら考察しなけれ
ばならないトリミング曲線の数を最小にまで減らす方法
を考えよう。

理想的には、Ｕの等しい増進とＶの等しい増進とを生ず
るのにｔの等しいステップが欲しい、この性質はトリミ
ング曲線を表わすのに選定したＢスプライン関数の性質
から生ずるもので、多かれ少かれ得ることができる。こ
のような同等性が得られれば、トリミング曲線関数に対
する良好なパラメータ化が存在すると言われる。悪いパ
ラメータ化はいつでも避けることができるとはかぎらず
、補正されないままになっているとトリミング・プロセ
スに一定の問題が生ずる。特に、トリムされた多角形に
対する多角形頂点の数がはなはだしく大きくなる可能性
がある。こうなると、今度は、多角形のトリミングに割
当てなければならないメモリの量が増加する。特定の利
益の無い現象を収容するのにメモリを追加するのではな
く、もっと満足な方法はトリミング曲線関数をｔの所定
のステップの大きさで評価することにより生じたｕｖ対
を調べ、その先行者から光分離れていないものを抑制す
ることである。説明しようとしているものへのこれ以上
の概説については、第８図の説明を参照のこと。

第１８図によりｕｖ空間のスパンで示したトリミング曲
線７２を考える。Δｔ７３の等しいステップの大きさか
ら異なるΔｕ７４と異なるΔｖ７５とが生ずる６曲線７
２に付けたｑ印の離れた距離はどれだけ異なっているか
に注意、これらはｔ空間で等距離離れたＶ印に対応する
ｕｖ空間の評価座標である。

第８図のおよび第９図のステップ６の説明から、ｔのス
テップの大きさ（Δｔ）は、パッチの縁に沿って測った
多角形頂点間の距離（この距離をエツジ・ステップ・サ
イズと言うことがある）にほぼ等しいΔＵとΔＶとの最
大値を生ずるように選ばれることを想起する。すなわち
第１８図の△ｔ７３の選び方である０例示の目的で、第
１８図に示す最大ΔＶ７５を使用して△ｔを求めると仮
定する。手近の例ではΔＶは△Ｕより大きくなる傾向が
ある。

異なるトリミング曲線については、最大ΔＵは最大ΔＶ
より大き（て△ｔを選定するのに使用される場合がある
。Δｔを選定するプロセスを第９図のステップ６に関連
して説明する。△ｔ７３の等しいステップの大きさでそ
の機能を評価することにより得られるトリミング曲線７
２の直線線分近似は少くとも一つのΔＵおよび△Ｖが縁
のメツシュの大きさの５２パーセントより大きくなけれ
ばならないとすることにより向上する。こうするものが
なければｕｖ空間のその点が無視され、次のものが考慮
され、以下同様、この技法によれば、点７６が無視され
、直線線分７７が点７８から点７９まで動くことになる
。各Ｂスプライン・トリミング曲線線分に沿う最初の点
は点選定プロセスが始まる最初の点である。これにより
Ｂスプライン・トリミング曲線線分は意図どうり相互に
確実に接合される。

５２パーセントという判定基準は受容可能な最短と最長
との直線線分の間に存在する関係から出て来る。この関
係は、一方において受容可能な最長直線線分（４５°に
なっているもの）がエツジ・ステップ・サイズを超す量
と他方において受容可能な最短直線線分（水平または垂
直になりでいるもの）がエツジ・ステップ・サイズより
小さい量との間の同等性を含んでいる。所望の同等性の
関係は選択判定基準がエツジ・ステップ・サイズのほぼ
５２パーセントであるとき得られることが示される。

要素スパンおよびその多角形を処理しているときに考慮
しなければならないトリミング曲線の数は以下の技法を
使用すれば減らすことができる。

簡単に言えば、スパン内の各トリミング曲線線分の位置
に関する情報はそのＢスプラインの定義と関係している
。この情報はおそらく処理されようとしている要素スパ
ンと交差することができない線分を考察から除外するの
に使用される。

新しいパッチに対する最初の多角形を作る前に各トリミ
ング曲線のＢスプライン線分ごとにＶｅｘ　ｔｅｎ　ｔ
を見つける。　　Ｖｅｘｔｅｎｔは第１８図に関連して
説明したパラメータ化を向上して得られる（ｕ。

■）対の集合の最小Ｖ値から最大Ｖ値までのＶの範囲で
ある。以下に記すＵｅｘ　ｔｅｎ　ｔも同様に定義され
る。各Ｂスプライン線分に対するＶｅｘｔｅｎｔはパッ
チに対するトリミング曲線を備えたデータ構造内の場所
に格納される。

多角形は要素スパンを行方向に順序づけして作られるこ
とを想起すること、第１Ｏ図の説明を参照。

多角形の各行の始めにパッチに対する各トリミング曲線
線分のＶｅｘｔｅｎｔを調べる。現在の行のＶの範囲と
重なるＶｅｘｔｅｎｔを備えるトリミング曲線線分を更
に評価してその関連のＵｅｘｔｅｎｔを探す、このよう
な各型なり線分のＵｅｘ　ｔｅｎ　ｔもトリミング曲線
のデータ構造に格納される。

行に沿う各多角形についてそのＵｅｘｔｅｎｔとＶｅｘ
　ｔｅｎ　ｔとが共に現在の要素スパンと重なるＢスプ
ライン線分だけを第６図〜第１６図と関連して説明する
クリッピング・トリミング・プロセスで考える。たとえ
ば、第６図を再び参照して、トリミング曲線線分８０は
パッチ１２の行８２の要素スパン・多角形に対しては重
要でない。線分８ｏは行８２のＶｅｘ　ｔｅｎ　ｔに重
なるＶｅｘ　ｔｅｎ　ｔを備えていない。一方、線分８
１のＶｅｘ　ｔｅｎ　ｔは行８２のＶｅｘ　ｔｅｎ　ｔ
と重ならず、線分８１のＵｅｘｔｅｎｔは行８２に沿う
要素スパンを処理する前に計算される。線分８１のＵｅ
ｘｔｅｎｔは要素スパン８３のＵｅｘｔｅｎｔと重なる
から、トリミング曲線１１のＢスプライン線分８１はそ
の要素スパンに関するクリッピング・トリミング動作に
含まれる。線分８０は行８２に沿う要素スパン・多角形
に関する動作に含まれず、更にたとえば、要素スパン８
４と関連して使用されることもない、また同じように、
線分８０も線分８１も行８５に沿う要素スパン・多角形
に関する動作に含まれることはなく、それら線分に対す
るＶｅｘｔｅｎｔがその行に対するＶｅｘｔｅｎｔと重
なることはない。

今度は第１９図を参脇すると、本発明の方法を具体化す
る実際の図形処理システムを絵画的に表わしである。特
に、図形処理システムは、コンピュータ８６、キーボー
ド８７、ノブ・ボックス８８、ボタン・ボックス８９、
およびマウス９０を備えている。

コンピュータ８６はこの明細書の始めに述べたソフトウ
ェアを実行することができ、ユーザと対話して表面とそ
のトリミング曲線とのＢスプライン記述を作製する。コ
ンピュータ８６は高速ローカル図形処理母線９２を介し
て図形処理加速器９１と結合している０図形処理加速器
９１は、赤、緑、および青（ＲＧＢ）の各ビデオ信号を
伝える３本の同軸ケーブルを介してカラー・モニタ９４
に結合されている。

上述のトリミング動作は完全に図形処理加速器９１の内
部で行われる。今まで述べたトリミングの方法はコンピ
ュータ８６のソフトウェアで行うことができると考えら
れるが、このような方法は適切なハードウェアによるト
リミングと比較して性能が落ちるため実質上不利である
。この目標および他の目標を達成するため、図形処理加
速器９１は多数の命令を実行することによりコンビエー
タ８６に応答する。それらのいくつかを挙げると、図形
処理加速器に一つ以上のトリミング曲線をデータ構造に
格納するように指示すること、データ構造に表面パッチ
の定義を格納し、あらかじめ定義したトリミング曲線に
従ってトリミングして表現すること、あらかじめ定義し
たすべてのトリミング曲線を削除する命令がある。ＯＮ
フラグのスタックを押してはじき出す命令もある。所定
パッチの右上隅および左下隅のＯＮフラグは二つの別々
のスタックに保存されてパンチを細分しやすくしている
。

パッチを要素パッチに細分するのは所定のパッチに入っ
ているトリミング曲線が多過ぎるときに行われる０図形
処理加速器９１で処理することができる単一パッチに対
してトリミング曲線の数を制限する実際的、かつ費用に
関連する問題（すなわち、メモリのりがある。

上述のメモリの限界はパッチに適用できるトリミング曲
線の数を実際上限定するものではない。

コンピュータのソフトウェアは所定のパンチに対するト
リミング曲線の数が約４０から６０を超したときパッチ
を細分する必要性を決定する。（ソフトウェアは図形処
理加速器の限界を認識するか０、あるいは図形処理加速
器から送られたオーバーフローの指示に応じて細分する
かのいずれかを行うことができる。）あらかじめ細分さ
れていないパッチは１６回まで分割することができる。

細分の動作ごとに手近のパッチを４ケの要素パッチに分
割することができる。

細分が発生するたびに、既に表現されている適切な他の
パンチのＯＮフラグがそのスタック上に押される。各パ
ッチの多角形の最後の行の最初の多角形の頂点！に対し
て一つのスタックがあり、各パッチの多角形の最初の行
の最後の多角形の頂点■に対してもう一つのスタックが
ある。これらスタックはコンピュータ８６が実行するソ
フトウェアと協同して別々に維持される。パッチ細分化
に対して得られる機構はパンチをトリミングする上述の
方法に対して透明である。その方法は、手近のバッチが
要素パッチであると否とに関係な（、常に同じ仕方で動
作する。

第２０Ａ図〜第２０Ｃ図は第１９図に示す図形処理加速
器９１のブロック図である。インターフェース機構９５
はトリミング曲線およびコンピュータ８６からのバッチ
定義命令を変換エンジン９６と結び付ける。

定義はマイクロシーケンサ９７によりデータＲＡＭ９８
に格納されている。マイクロシーケンサはこれらの定義
に基いて動作し、トリムされた多角形の頂点の座標を発
生する。トリムされた多角形の頂点の画面座標はＤＣ（
装置座標）母線９９を経由して走査変換器１００に送ら
れ、ここで多角形表現のプロセスがピクセル・レベル（
たとえば、区域充填、またはぼかしのためのカラー挿間
）で更に行われる。

マイクロシーケンサ９７は各種の整数・浮動小数点演算
ユニットと関連して動作するが、たとえば八ｄｖａｎｃ
ｅｄ　Ｍｉｃｒｏ　Ｄｅｖｉｃｅｓ社のＡ　Ｍ　Ｄ２９
１０を使用することができる。

〔発明の効果〕

以上説明したように、本発明を用いることにより、Ｂス
プラインの効用を保持したまま表面記述のその技術によ
り得られる利点が活用でき、しかも同時に、丸め誤差が
少なく、高速トリミングができるようになる。

【図面の簡単な説明】

第１図は不拘−有理Ｂスプラインのようなパラメトリッ
クバッチ発生関数で二次元ｕｖパラメータ空間のスパン
をＸＹＺ空間へ写像することにより形成されたパンチに
よってＸＹＺ空間内に近似された表面を示す図である。 第２図は表面から削除される領域を区分するためにＸＹ
Ｚ空間へ写像されうる、ｕｖ空間内のトリミング曲線を
、−次元を空間のパラメトリック関数が規定しうる様子
を示す図である。 第３図は一次元を空間のいくつかのスパンにわたって分
けられ、二次元ｕｖ空間のトリミング曲線を規定するパ
ラメトリック・トリミング曲線関数を示す図である。 第４図は分割されたトリミング曲線関数がｕｖ空間の数
スパンを横断し、ｘＹＺ空間の対応する数のパッチ内に
、写像されたトリミング曲線を規定する様子を示す図で
ある。 第５図は第４図の分割トリミング曲線を、より詳細に示
す図である。 第６図は、ｕｖ空間のスパンが要素スパンに分割された
ＸＹＺ空間の表面用の表面近似多角形を生ずる様子を示
し、また、ｕＶ空間のトリミング曲線が要素スパンを横
断する一方、写像されたトリミング曲線が表面上の多角
形をトリムすることを示す図である。 第７図は第６図の部分拡大図である。 第８図は第７図の部分拡大図であって、写像されたトリ
ミング曲線が横断することにより多角形の形状が変化す
る様子を示す図である。 第９Ａ図、第９Ｂ図、及び第９Ｃ図は写像されたトリミ
ング曲線により横断され、それに従って形状が調整され
る多角形を発生するのに用いられる処理ステップを記述
した擬似コードの簡略部を示す図である。 第１０図はｘｙｚ空間の表面用の近似多角形を作成する
のに要素スパンが取られるスパン内の順序を示す図であ
る。 第１１図はスパン上で規定されたトリミング曲線のいく
つかの形式を示す図であって、算術丸め誤差を避けるの
に役立つスパンの回りのガード領域の存在を示す図であ
る。 第１２Ａ図及び第１２Ｂ図は要素スパンを横断してトリ
ミング曲線の直線線分と要素スパンの境界との間の交点
を生ずるトリミング曲線の近似点、ｖ！線分上で、クリ
ッピング機構が動作する様子を示す図である。 第１３Ａ図及び第１３Ｂ図はトリミング曲線が当該要素
スパンの境界へきわめて近接しているｕｖ空間内の点を
表わす、ある特別の場合を示す図である。 第１４図はある特定のトリミング曲線によって横断され
るｕｖ空間内の要素スパンの有用な例を示す図である。 第１５図は第１４図の例に対応する頂点表層のトリミン
グ曲線サブリスト及びリンクされた境界リストの簡略化
表示を示す図である。 第１６Ａ図、第１６Ｂ図、及び第１６Ｃ図は第９Ｃ図の
ステップ１２にしたがって頂点表のリンクされたリスト
を処理するための簡略フローチャートを含む図である。 第１７図は第１６Ａ図ないし第１６Ｃ図と同様の主題に
適する１４１２コードの簡略部を示す図である。 第１８図はｕｖ空間におけるトリミング曲線を示施例に
用いられるハードウェアの簡略プロ７り図　。 である。 第２０Ａ図、第２０Ｂ図、及び第２０Ｃ図は第１９図の
図形処理加速器の簡略ハードウェア・ブロック図を備え
た図である。 ８６：コンピュータ　　　　９１：図形処理加速器９４
：カラーモニター ｃカ （）−Ｊ Ｏ〕 ｄ、１ へ （イ） 図面の、′ｉ・ガ 舅 ト ド Ｃ，Ｒ１− 手続補正書 昭和６３年０２月１乙日 １、事件の表示　　　　　昭和６３年０２月０５日出願
の特許１１１（２）３、補正をする者 事件との関係　　　　　　　特　許　出　願　人４、代
理人

Claims (1)

【特許請求の範囲】
1. （１）次の（イ）〜（ト）の各段階を含むことを特徴と
   する表面パッチ・パラメトリック記述のトリミング方法
   。 （イ）相互連結線線分がトリムされるべき領域の境界で
   あるパラメータ空間のトリムされていない点の順序集合
   を選択する段階。 （ロ）トリミング関数を評価して前記パラメータ空間の
   トリミング点の順序集合を得る段階。 （ハ）前記トリミング点を結ぶ直線線分とトリムされる
   べき前記表面パッチの境界との間の交点を求める段階。 （ニ）トリムされるべき前記表面パッチの内側にあるト
   リミング点の順序集合を区別する段階。 （ホ）トリムされていない点の前記順序集合と、前記交
   点と、トリムされるべき前記表面パッチの内側点の順序
   集合とをデータ構造内へ差挟む段階。 （ヘ）トリムされる領域を記述する前記点を識別し、選
   択するために前記データ構造を横断する段階。 （ト）トリムされる前記表面パッチとして識別され、選
   択された点を表現する段階。