(57)【要約】      （修正有）【課題】処理スピードを改良するとともにメモリスペース量を節減するジオメトリを処理するためのシステムを提供する。【解決手段】システムは、頂点に関するキューにおいてデータが引き渡されるにつれて当該データが開放され、最少限度の中間結果のみが記憶されるように頂点に関するキュー７０に頂点を順々に引き渡す。この増分評価によって、必要なメモリスペースが節減される。別の態様においては、分類演算が排除できるように、頂点が適切な順序に維持される。頂点リスト全体の再分類が防止可能であるように分類済みの頂点に関するキュー７０および未分類頂点リスト７２が用いられる。さらに、分類済みかつ減少済み頂点に関するキューから多くの情報を再導出することができるという事実に基づいて、ジオメトリを記憶するための圧縮されたフォーマットが用いられる。【選択図】図８ａ
2009199616.tif 000002
【特許請求の範囲】
【請求項１】
ジオメトリの頂点ベース表現を処理するためのシステムであって、
(a)頂点ベースジオメトリデータを入力し、
(b)所定の増分における前記頂点ベースジオメトリデータを処理し、
(c)前記ステップ(b)において処理されたデータを頂点に関するキューに順々に引き渡す
ステップを有する方法。
【請求項２】
さらに、
(d)ジオメトリのソースから頂点が分類されているかどうかを判定し、
(e)前記ジオメトリが分類済みであることを前記ステップ(d)が検出する場合に分類済み
頂点に関するキューにおける前記ジオメトリの頂点を記憶し、および、前記ジオメトリが
未分類であることを前記ステップ(d)が検出する場合に未分類頂点リストにおける前記ジ
オメトリの頂点を記憶する請求項１に記載された方法。
【請求項３】
さらに、排他的OR演算を実施するステップを有する請求項２に記載された方法。
【請求項４】
前記ジオメトリの真の反転が表現可能であるように、無限におけるジオメトリフィール
ド深度は随意である請求項２に記載された方法。
【請求項５】
ジオメトリの頂点ベース表現を処理するためのシステムであって、
頂点ベースジオメトリデータを入力するための手段と、
前記頂点ベースジオメトリデータを所定の増分において処理し、前記データを頂点に関
するキューに順々に引き渡すためのプロセスとを有するシステム。
【請求項６】
さらに、ジオメトリのソースから頂点が分類済みであるかどうかを検出するためのディ
テクタと、
前記ジオメトリが分類済みであることを前記ディテクタが検出する場合に前記ジオメト
リの頂点を記憶するための分類済みの頂点に関するキューと、
前記ジオメトリが未分類であることを前記ディテクタが検出する場合、前記ジオメトリ
の頂点を記憶するための未分類頂点リストとを有する、請求項５に記載されたシステム。
【請求項７】
前記プロセッサは排他的ORオペレーションを実施する請求項６に記載されたシステム。
【請求項８】
前記ジオメトリの真の反転が表現可能であるように、無限における前記ジオメトリのフ
ィールド深度は随意である請求項６に記載されたシステム。
【請求項９】
ジオメトリの頂点ベース表現を処理するための方法であって、
(a)頂点ベースジオメトリデータを未分類頂点リストに入力し、
(b)前記ステップ(a)において入力された前記頂点ベースジオメトリデータが前記未分類
頂点リストの容量を表す所定量に到達しているかどうかを検出し、
(c)前記ステップ(b)において前記所定量に到達済みであることを検出した後に、前記未
分類頂点リストにおける前記の頂点ベースジオメトリデータを分類し、
(d)前記ステップ(c)において分類済みの頂点ベースジオメトリデータを分類済みの頂点
に関するキューに記憶し、
(e)追加入力される頂点ベースジオメトリデータを受け取るために利用可能であるよう
に、前記未分類頂点リストをクリアするステップとを有する方法。
【請求項１０】
ジオメトリの頂点ベース表現を処理するためのシステムであって、
頂点ベースジオメトリデータを入力するための未分類頂点リストと、
前記未分類頂点リストに入力された前記頂点ベースジオメトリデータが前記未分類頂点
リストの容量を表す所定量に到達したかどうかを検出するためのディテクタと、
前記所定量に到達したことを検出した後に、前記未分類頂点リストにおける前記の頂点
ベースジオメトリデータを分類するための手段と、
前記の分類済み頂点ベースジオメトリデータを記憶するための分類済みの頂点に関する
キューと、
追加入力される頂点ベースジオメトリデータを受け取るために利用可能であるように、
前記未分類頂点リストをクリアするための手段とを有するシステム。
【請求項１１】
スケーリング演算の後でジオメトリの頂点ベース表現を分類するための方法であって、
(a)ジオメトリの頂点に関するスケーリング演算のスケールファクタが１未満であるか
どうかを検出し、
(b)前記スケールファクタが１未満であることを前記ステップ(a)が検出される場合に分
類演算を実施し、
(c)前記スケールファクタが１以上であることを前記ステップ(a)が検出される場合に分
類演算が実施されることを防止する方法。
【請求項１２】
前記ステップ(b)は、複数の元の走査線からの頂点を含むが、分類済みの走査線を形成
する頂点の部分集合に前記の分類演算を実施する請求項11に記載された方法。
【請求項１３】
スケーリング演算の後でジオメトリの頂点ベース表現を分類するためのシステムであっ
て、
ジオメトリの頂点に関するスケーリング演算のスケールファクタが１未満であるかどう
かを検出するためのディテクタと、
前記スケールファクタが１未満であることを前記ディテクタが検出する場合に分類演算
を実施し、前記スケールファクタが１以上であることを前記ディテクタが検出する場合に
分類演算が実施されることを防止するためのプロセッサとを有するシステム。
【請求項１４】
前記プロセッサは、複数の元の走査線からの頂点を含むが、分類済みの走査線を形成す
る頂点の部分集合に前記の分類演算を実施する請求項13に記載されたシステム。
【請求項１５】
拡大および縮小演算の後でジオメトリの頂点ベース表現を分類するための方法であって
、
(a)前記拡大および縮小演算の後で前記ジオメトリの頂点をそれぞれの頂点が移動した
方向に基づいて四組に分割し、
(b)二組の分類済みの頂点を生成する前記ステップ(a)において分類された前記四組の頂
点の第一および第二の対に併合/分類演算を実施し、
(c)一組の分類済みの頂点を生成するために前記ステップ(b)からの二組の分類済み頂点
に併合/分類演算を実施する方法。
【請求項１６】
拡大および縮小演算の後でジオメトリの頂点ベース表現を分類するためのシステムであ
って、
前記拡大および縮小演算の後で、それぞれの頂点が移動した方向に基づいて、前記ジオ
メトリの頂点を四組に分割するための分割手段と、
二組の分類済みの頂点を生成するために前記四組の頂点の第一および第二の対に併合/
分類演算を実施し、一組の分類済みの頂点を生成するために前記二組の頂点に併合/分類
演算を実施するためのプロセッサとを有するシステム。
【請求項１７】
ジオメトリの頂点ベース表現をミラーリングするための方法であって、
(a)各走査線における前記ジオメトリの頂点を蓄積し、
(b)前記頂点を分類することなしに各走査線に平行な軸におけるジオメトリをミラーリ
ングするために、各走査線において前記頂点を反転するステップを有する方法。
【請求項１８】
ジオメトリの頂点ベース表現をミラーリングするためのシステムであって、
各走査線における前記ジオメトリの頂点を蓄積するための手段と、
前記頂点を分類することなしに各走査線に平行な軸における前記ジオメトリをミラーリ
ングするために、各走査線において前記頂点を反転するためのミラーリング手段とを有す
るシステム。
【請求項１９】
ジオメトリの頂点ベース表現をミラーリングするための方法であって、
(a)前記ジオメトリの四隅を同一方法によって圧縮および記憶し、
(b)第一頂点に類似する各走査線の最後の頂点を明確に記憶し、
(c)前記頂点を分類することなしにXおよびY両軸方向において前記ジオメトリをミラー
リングするために、アンパッカ機能によってデータのバイトストリームを後方に読み取る
方法。
【請求項２０】
ジオメトリの頂点ベース表現をミラーリングするためのシステムであって、
前記ジオメトリの四隅を同一方法により圧縮および記憶し、
第一の頂点に類似する各走査線の最後の頂点を明確に記憶するための手段と、
前記頂点を分類することなしにXおよびY両軸方向において前記ジオメトリをミラーリン
グするためにデータのバイトストリームを後方に読み取るためのアンパック手段とを有す
るシステム。
【請求項２１】
ジオメトリの頂点ベース表現に関するデータを圧縮するための方法であって、
(a)分類済みの頂点に関するキューにアクセスし、
(b)前記ジオメトリの各走査線における第一の頂点の完全なXおよびY値を記憶し、
(c)各走査線において残りの各頂点間の各走査線に沿った距離の増分差のみを記憶する
方法。
【請求項２２】
ジオメトリの頂点ベース表現に関するデータを圧縮するためのシステムであって、
分類済みの頂点に関するキューにアクセスするための手段と、
前記ジオメトリの各走査線における第一の頂点の完全なXおよびY値を記憶し、各走査線
における残りの各頂点の間の各走査線に沿った距離における増分差のみを分類するための
手段とを有するシステム。
【請求項２３】
ジオメトリの頂点ベース表現に関するデータを圧縮するための方法であって、
(a)分類済みかつ減少済み頂点に関するキューへアクセスし、
(b)前記ジオメトリの三隅の頂点を記憶し、
(c)アンパッカ機能によって前記ジオメトリの残りの第四の隅の頂点を決定する方法。
【請求項２４】
ジオメトリの頂点ベース表現に関するデータを圧縮するためのシステムであって、
分類済みかつ減少済み頂点に関するキューにアクセスするための手段と、
前記ジオメトリの三隅の頂点を記憶するための手段と、
前記ジオメトリの残りの第四の隅の頂点を決定するためのアンパック手段とを有するシ
ステム。
【請求項２５】
ジオメトリの頂点ベース表現に関する圧縮されたデータをアンパックするための方法で
あって、
(a)分類済みかつ減少済み頂点リストにアクセスし、
(b)頂点の周りの三象限内にジオメトリが存在するかどうかを前後関係から決定し、
(c)頂点タイプが必要とされない頂点リストにおける前記頂点の存在または不在に基づ
き、前記頂点の残りの第四象限内にジオメトリが存在するかどうかを決定する方法。
【請求項２６】
ジオメトリの頂点ベース表現に関する圧縮されたデータをアンパックするためのシステ
ムであって、
分類済みかつ減少済み頂点リストにアクセスする手段と、
頂点の周りの三象限内にジオメトリが存在するかどうかを前後関係から決定し、頂点タ
イプが必要とされない頂点リストにおける前記頂点の存在または不在に基づき、前記頂点
の残りの第四象限内にジオメトリが存在するかどうかを決定するためのプロセッサとを有
するシステム。
【請求項２７】
ジオメトリの頂点ベース表現を処理するための方法であって、
(a)拡大または縮小演算をジオメトリに実施し、
(b)前記ジオメトリを表すために用いられる頂点データを節減するためにただ一つのコ
ーナタイプ型における拡大または縮小演算による変化を表す一組の合成頂点を加える方法
。
【請求項２８】
前記一組の合成頂点は、元の未処理ジオメトリにおける一つの頂点を置き換える三つの
頂点を有する請求項27に記載された方法。
【請求項２９】
ジオメトリの頂点ベース表現を処理するためのシステムであって、
ジオメトリに拡大または縮小演算を実施するための手段と、
前記ジオメトリを表すために用いられる頂点データを節減するようにただ一つのコーナ
タイプにおける拡大または縮小演算による変化を表す一組の合成頂点を加えるためのプロ
セッサとを有するシステム。
【請求項３０】
前記一組の合成頂点は、元の未処理ジオメトリにおける一つの頂点を置き換える三つの
頂点を有する請求項29に記載されたシステム。
【請求項３１】
ジオメトリの頂点ベース表現を処理するための方法であって、
(a)ジオメトリにAndまたは縮小演算を実施し、
(b)前記ステップ(a)において実施された演算の結果を減少させることなく、他のAndま
たは縮小演算へ引き渡す方法。
【請求項３２】
ジオメトリの頂点ベース表現を処理するためのシステムであって、
ジオメトリにAndまたは縮小演算を実施するための手段と、
実施された演算の結果を減少させることなく、他のAndまたは縮小演算へ引き渡すため
の手段とを有するシステム。
【請求項３３】
ジオメトリの頂点ベース表現を増分的に評価するための方法であって、
(a)順々に頂点を頂点に関するキューに引き渡し、
(b)ステップ(a)において頂点が引き渡されるにつれて、前記頂点に関するキューに記憶
されているデータを開放し、
(c)データの生成部と消費部との間でデータが能率的に移動するように、前記ステップ(
b)においてデータが開放されるにつれて中間結果を生成することによってデータを増分的
に評価する方法。
【請求項３４】
ジオメトリの頂点ベース表現を増分的に評価するためのシステムであって、
頂点に関するキューに頂点を順々に引き渡すための手段と、
前記頂点に関するキューに記憶されているデータを、頂点が引き渡されるにつれて、開
放するための手段と、
データの生成部と消費部との間でデータが能率的に移動するように、データが開放され
るにつれて中間結果を生成することによってデータを増分的に評価するための手段とを有
するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集積回路設計に使用するための頂点ベースのジオメトリエンジンシステムに
関する。さらに詳細には、本発明は、入力データの増分評価を実行し、メモリの集中的な
演算を回避することによって用いる記憶容量が比較的小さく、さらに、ジオメトリエンジ
ンシステムのスピードも改良する、集積回路設計のジオメトリを処理するためのシステム
に関する。
【背景技術】
【０００２】
ジオメトリエンジンは、通常、集積回路ジオメトリを処理するための一組の基本的ルー
チンとして定義され、この種の基本ルーチンの例としては、ブール演算（And、Or、AndNo
t）、サイジング演算（拡大(Grow)および縮小(Shrink)）、変換演算（変換、回転、ミラ
ーリング）が含まれる。ジオメトリエンジンは、設計規則のチェックおよび集積回路レイ
アウトの分割のためのVLSI設計に特に適する。
【０００３】
二つのジオメトリエリア（AおよびB）に関し、ジオメトリエンジンによって実施可能な
ブール演算の幾つか例を図1(a)から1(c)に示す。図1(a)では、二つのジオメトリ領域Aお
よびBに関してAnd演算が実施されており、この演算の結果として得られる領域を太い線で
取り囲んでいる。図1(b)では、二つのジオメトリ領域AおよびBにOr演算が実施されており
、この演算の結果として得られる領域を太い線で取り囲んでいる。図1(c)においては、二
つのジオメトリ領域AおよびBに関してA AndNot B演算が実施されており、この演算の結果
として得られる領域は太い線内に含まれる。
【０００４】
ジオメトリエンジンによって実施可能なサイジング演算の複数の例を図2(a)および2(b)
に示す。図2(a)においては、斜線を施したジオメトリ領域に関して量Δだけ拡大演算が実
施され、その結果、太い線によって取り囲まれたジオメトリ領域を達成するためにすべて
の縁が固定量Δだけ外側に動かされる。図2(b)においては、斜線を施したジオメトリ領域
に関して縮小演算が実施され、その結果、太い線によって囲まれたジオメトリ領域を生成
するためにすべての縁が固定量Δだけ内側に動かされる。拡大および縮小演算は、二つ以
上のジオメトリ領域が設計規則における正しい間隔を保っているかどうかを判定する集積
回路設計のための設計規則チェックにしばしば用いられる。
【０００５】
様々なベースの表現機能を備えたジオメトリエンジンシステムが公知であり、前記表現
機能には、図3(a)および3(b)に示すように連続的な多角形体によるジオメトリベース表現
、図3(c)および3(d)に示すようにオーバラップしない四辺形（長方形または台形）による
ジオメトリベース表現、図3(e)および3(f)に示ように頂点によるジオメトリベース表現が
含まれる。これら公知の表現は集積回路設計に用いられて成功しているが、同時に、各表
現と関連した欠点および問題がある。例えば、一般に、複雑な表現方法は操作の重荷とな
るので、連続的な多角形体によるジオメトリベース表現はメモリおよびスピードにおける
問題を有している。重複しない四辺形によるジオメトリベース表現は、重複しない四辺形
が一緒に結合して生じる誤った縁（false edge）を生じてしまい、この場合もやはり複雑
な表現が生成される。頂点による公知のジオメトリベース表現は、大きいメモリを要求し
てしまい、また、全体的に処理スピードが低速であることに起因する問題を抱えている。
頂点によるジオメトリベース表現が抱える潜在的な問題は、これらの表現が角度が任意で
あるジオメトリに充分良好には適していないことであるが、一般に集積回路設計者は、角
度が任意であるジオメトリを回避するために、設計を簡素化し、幾つかのフォトリソグラ
フィプロセスを最適化する直角の設計を採用するので、上記の理由は多くの集積回路設計
アプリケーションにとって問題とならない。
【０００６】
これら公知の表現のうち、頂点ベース表現システムは、集積回路設計アプリケーション
に対して、全体的に最も多くの利点を提供する。頂点ベース表現によって提供されるこの
種の利点のうちの一つは、簡単で一貫性のあるデータタイプが使用可能なことである。例
えば、一頂点に関し、各象限（四分円）での１６種類の実行可能データの組合せは、解析
を目的とする場合に１０種の実行可能データ組合せに減少させることが可能である。図4(
a)から4(j)までに示すこれら１０種類の可能な組合せには、頂点における４種類の凹状デ
ータ配置（図4(a)から4(d)まで）、頂点における４種類の凸状データ配置（図4(e)から4(
h)まで）、コンプレックス配置と称する頂点における二種類の向かい合ったデータ配置（
図4(i)および図4(j)）が含まれる。頂点ベース表現の他の利点は、ジオメトリの誤った特
徴が生成されないことである。誤った特徴が一切存在しないことは、誤った縁に関して余
分な構成線を生成してしまう四辺形によるジオメトリベース表現と比較して、用いられる
メモリ容量を小さくし、処理時間を短縮し得る。結果的に、この種の構成線を回避するこ
とにより、頂点表現を用いて基本ルーチンを実施するために必要な処理時間やメモリスペ
ースが軽減される。さらに、頂点ベース表現による処理は直接的なジオメトリ間相互作用
を生成し、その結果、複雑かつ多くの部分からなる図形が用いられることにより複雑なジ
オメトリ的相互作用に導かれる多角形体ベース表現と比較して、基本ルーチンの処理に必
要な時間が節減される。さらに、頂点ベース表現は、当該頂点によって表される隅部（co
rner）にてルーチンおよび演算を容易に実施することを可能にする。
【０００７】
ただし、公知の頂点ベース表現システムは、或る態様の集積回路設計アプリケーション
においては不利である。ほとんどのジオメトリが機械生成されることから、特定のフォト
リソグラフィプロセスおよび簡素性（simplicity）のために、水平縁と垂直縁との間で最
良のフォトリソグラフィ解像度を供給するので、当技術分野は直角の設計を用いる傾向に
あり、頂点ベース表現システムが角度が任意であるジオメトリに対してあまり適していな
いことは、一般的に集積回路設計における大きい問題とはならない。従って、公知の頂点
ベース表現システムにおける主たる欠点はスピードおよびサイズにおける欠陥である。換
言すれば、公知の頂点ベース表現システムは、中間結果および不必要な処理のために多量
の記憶容量を使用してしまい、その結果当該システムは、メモリ操作に起因して低速動作
となってしまう。
【０００８】
公知の頂点ベースジオメトリエンジンシステムの一例は「ファング(fang)」システムと
称されており、カリフォルニア大学バークレイ校のPeter Mooreによって1980年代半ばに
開発されたが、ソースコードおよびそれから発展された疑似コード(pseudo code)以外は
、このシステムの発表については一切知られていない。
【０００９】
公表された文書が無いので、ファングシステムの一般的な説明を次に述べる。図５は、
ファングデータ構造の幾つかの例を示す。ファングデータ構造は、「分類済み（sorted）
」および「減少済み（reduced）」フラグビット522および524を有するファングジオメト
リデータ構造520を含む。ファングにおいては、一般に用語「併合済み（merged）」が用
いられるが、用語の一貫性を保持するために、ここでは、「併合済み」の代わりに用語「
減少済み」が用いられる。分類済みフラグビット522は、頂点の頂点リスト526が分類済み
であるかどうかを表示し、減少済みフラグビット524は、ジオメトリ頂点が減少済みであ
るかどうか（ジオメトリの自己オーバラップが無いかどうか）を表示する。
【００１０】
図５の例はリンクされた頂点リストにおける二つの頂点530および540を示す。頂点530
および540用のフィールドはネクストポインタ532および542を含み、これらのポインタは
、リンクされたリストにおける連続したエントリ、頂点タイプフィールド534および544、
xおよびyの値536および538、並びに、546および548を指示する。ファングシステムでは、
頂点の分類が、左から右へ、および、下から上へと、走査線の順序に従って実施される。
追加的なジオメトリの読取りまたは収集によって、新規なジオメトリ図形が追加される場
合、新規頂点が単純に頂点リストに追加されるので、頂点の順序が乱れる。さらには、例
えば、拡大、ミラーリング、或いは、回転のような演算が実施される場合には、頂点は異
なる方向に動き、それによって、頂点リスト526における頂点の順序が乱れるかもしれな
い。従って、頂点が順序を乱さないことを保証する必要のある場合には、頂点リスト526
は、ファングシステムによって自動的に分類される。ファングシステムでは、頂点リスト
526は極めて頻繁に分類され、そして、nがリスト内の頂点の個数である場合に、各分類に
必要な演算の数はn log2 n、または“O(n log2 n)”の次数（order）で表現可能であるの
で、これらの演算は実質的な時間量を消費しうる。
【００１１】
ファングシステムにおける重要な演算は減少である。減少演算に関する背景として、ジ
オメトリ「深度（depth）」について次に簡単に説明する。一般に、ジオメトリ深度とは
、特定点におけるジオメトリの重なりピース（overlapping piece）の数である。例えば
、ジオメトリ深度ゼロが示すのは、ジオメトリ図形の間に空間が存在し、その点には一切
のジオメトリが存在しないことである。ジオメトリ深度１は、その点に一つのジオメトリ
図形が存在することを示し、そして、一般にジオメトリ深度の値は一つの点において重な
る図形数に対応する。ジオメトリ深度の概念は、ジオメトリ深度が当該ジオメトリ全体に
亙ってゼロまたは１の何れかである場合にジオメトリ減少されるという事実により、減少
演算において使用される。ジオメトリは、一つの新規なジオメトリ図形が追加され、既存
のジオメトリに重なった後、一般に、減少されないままの状態で残される。従って、新規
なジオメトリ図形が追加された場合、ファングシステムは、オーバラップが発生したと仮
定して、減少済みフラグをクリアする。同様に、拡大およびOr演算に関し、二つのジオメ
トリ図形はオーバラップ可能であるので、ジオメトリが減少されることを保証するために
、当該ファングシステムは減少済みフラグをクリアする。減少済みジオメトリを要求する
演算が実施される場合には、減少済みフラグが解析され、そして、減少済みフラグがセッ
トされない場合には、減少演算が実施される。
【００１２】
図６を参照しながら、ファングシステムの減少方法についてさらに詳細に検討すること
とする。ファングシステムにおいて、頂点は走査線順序に従って調査され、そして、現行
走査線を切る（cutting）垂直縁の一時的なリストが作成され、減少演算の間維持される
。ファングシステムの減少方法では、頂点が入力ジオメトリ内に存在するか、或いは、入
力頂点を含む走査線を垂直縁が横切る場合に、点が解析される。これらは、図６において
aからjにラベル表示された点である。これら解析された点それぞれにおいて、解析された
点の左（上下）までのジオメトリ深度は既知であり、頂点（存在する場合）は、当該点の
ジオメトリの右上にジオメトリ深度までのオフセットを加え、そして、縁（存在する場合
）は、当該点の右（上下両方）にジオメトリ深度までのオフセットを加える。その結果、
各象限におけるジオメトリ深度に応じて出力頂点が生成され、当該縁は、当該点の上のジ
オメトリ深度Δ（右上および左上までの領域の間の深度差）に基づいて、加えられるか、
或いは、除去される。
【００１３】
この減少方法の一つの例について、図６の点aからjに関して検討を続けることにする。
点aにおいて、左の縁が縁リストに加えられ、そして、出力頂点が作成される。点bにおい
て、右の縁が縁リストに加えられ、そして、出力頂点が作成される。点cにおいて、左縁
が確認され、そして、動作は一切実施されない。点dにおいて、左縁が縁リストに加えら
れ、そして、出力頂点は作成されない。点eにおいて、右縁が確認され、そして、出力頂
点が作成される。点fにおいて、右縁が縁リストに加えられ、そして、出力頂点が作成さ
れる。点gにおいて、左縁が縁リストから除去され、そして、出力頂点が作成される。点h
において、左縁が縁リストから除去され、そして、出力頂点は作成されない。点iにおい
て、右縁が縁リストから除去され、そして、出力頂点は作成されない。点jにおいて、右
縁が縁リストから除去され、そして、出力頂点が作成される。これらの動作によって、図
６に示すジオメトリがジオメトリ深度ゼロまたは１まで完全に減少される。ファングシス
テムにおいて、ジオメトリは頻繁に減少され、そして、不必要な減少演算が実施されるか
も知れず、その結果、システムのスピードが低下する。例えば、ファングシステムは、An
d演算の結果を不必要に減少させ、別のAnd演算を生じさせるかもしれない。最悪の場合に
おいて、各減少にはO(n2)時間を要するが、実際には、演算動作の数は線形、O(n)に近い
。
【００１４】
公知の頂点ベースジオメトリシステムにおいて、一般的には、当該ジオメトリを処理す
るために必要なメモリサイズが最大の問題であると考えられる。例えば、ファングシステ
ムにおいては、各頂点を表すために16または20バイトのデータが用いられることで、大量
のメモリが必要とされる。さらに、ファングは、完全なソースデータと各演算の結果との
ためにメモリを同時使用する必要があり、そのことで大量のメモリが用いられることとな
る。従って、本発明は、第一に、ルーチンを実行するために必要な記憶量を減少すること
に関する。そして、本発明は、第二に、メモリサイズを減少させることで、これらのルー
チンを実行するためのスピードを向上させることにも関する。
【発明の概要】
【００１５】
本発明は、ジオメトリを処理し、その結果として、ジオメトリを処理するために必要な
記憶量を減少し、同時に処理スピードを改良するためのシステムおよび方法に関する。本
発明の一態様において、本システムおよび方法は、データが渡されるにつれて頂点に関す
るキュー内のデータが開放され、最少限度の中間結果だけが記憶されるように、頂点に関
するキューへ頂点を順々に渡す。この増分評価により、消費部(consumer)がデータを開放
するにつれて、中間結果の生成部(producer)がデータを生成する。従って、あらゆる時点
において中間結果の小さい部分だけが存在するので、必要なメモリスペースが節減される
。
【００１６】
本発明の他の態様において、本システムおよび方法は、分類演算を排除することができ
るように、適切な順序に頂点を維持する。さらに詳細には、頂点リスト全体の再分類を防
止することができるように、分類済みの頂点に関するキューおよび未分類頂点リストが利
用される。分類済みの頂点に関するキューおよび未分類頂点リストの使用は、入力データ
の読取り或いは収集に際して特に有用である。この種のデータ収集に際して、所定量のデ
ータに達するまで、未分類頂点リストがデータを受け取り、未分類頂点リスト内に存在す
るデータは分類され、その後で、分類済みの頂点に関するキュー内に記憶される。その後
、データの収集および未分類頂点リスト内への読込みが継続可能である。分類済みの頂点
に関するキューと未分類頂点リストをこのように使用すると、分類済みの頂点に関するキ
ューと未分類頂点との間でデータを能率的に記憶および管理することが可能である。さら
に、分類済み（および減少済み）の頂点に関するキューはコンパクトな形式において記憶
されることが可能であり、結果的に、記憶に必要な空間量が節減される。
【図面の簡単な説明】
【００１７】
【図１ａ】ジオメトリに実施されるブール演算の例を示す。
【図１ｂ】ジオメトリに実施されるブール演算の例を示す。
【図１ｃ】ジオメトリに実施されるブール演算の例を示す。
【図２ａ】ジオメトリに実施される拡大および縮小プロセスの例を示す。
【図２ｂ】ジオメトリに実施される拡大および縮小プロセスの例を示す。
【図３ａ】ジオメトリの種々異なる表現に関する例を示す。
【図３ｂ】ジオメトリの種々異なる表現に関する例を示す。
【図３ｃ】ジオメトリの種々異なる表現に関する例を示す。
【図３ｄ】ジオメトリの種々異なる表現に関する例を示す。
【図３ｅ】ジオメトリの種々異なる表現に関する例を示す。
【図３ｆ】ジオメトリの種々異なる表現に関する例を示す。
【図４ａ】直線で囲まれた頂点に関して可能なデータ組合せを示す。
【図４ｂ】直線で囲まれた頂点に関して可能なデータ組合せを示す。
【図４ｃ】直線で囲まれた頂点に関して可能なデータ組合せを示す。
【図４ｄ】直線で囲まれた頂点に関して可能なデータ組合せを示す。
【図４ｅ】直線で囲まれた頂点に関して可能なデータ組合せを示す。
【図４ｆ】直線で囲まれた頂点に関して可能なデータ組合せを示す。
【図４ｇ】直線で囲まれた頂点に関して可能なデータ組合せを示す。
【図４ｈ】直線で囲まれた頂点に関して可能なデータ組合せを示す。
【図４ｉ】直線で囲まれた頂点に関して可能なデータ組合せを示す。
【図４ｊ】直線で囲まれた頂点に関して可能なデータ組合せを示す。
【図５】公知の頂点ベース表現ジオメトリエンジンシステムに関するデータ構造を示す。
【図６】公知の頂点ベースシステムにおいて減少されるべきジオメトリに関して調査するべき点を示す。
【図７】本発明の一実施形態に従った頂点ベースジオメトリエンジン用システムを示す。
【図８ａ】本発明の一実施形態に従い頂点ベースジオメトリエンジンシステム用として使用可能なデータ構造を示す。
【図８ｂ】本発明の一実施形態に関して、一つのキューから一つの頂点を抽出するためのフローチャートである。
【図８ｃ】本発明の一実施形態に従ったキューデータ構造を示す。
【図８ｄ】本発明の一実施形態に関するマージャーのソースデータ構造を示す。
【図８ｅ】本発明の一実施形態に従ったマージャーの補充機能に関するフローチャートである。
【図８ｆ】システムへの入力データを配送して、処理するためのフローチャートを示す。
【図９】８アイテムリスト用の併合/分類プロセスの一例を示す。
【図１０】本発明の一実施形態に基づく頂点ベースシステムの分類演算を最小限化するためのプロセスを示す。
【図１１】本発明の一実施形態において実施されるブール演算プロセスの一例を示す。
【図１２ａ】公知の頂点ベースシステムと本発明の実施形態に従った頂点ベースジオメトリエンジンシステムとの間の拡大演算および縮小演算の比較を示す。
【図１２ｂ】公知の頂点ベースシステムと本発明の実施形態に従った頂点ベースジオメトリエンジンシステムとの間の拡大演算および縮小演算の比較を示す。
【図１２ｃ】公知の頂点ベースシステムと本発明の実施形態に従った頂点ベースジオメトリエンジンシステムとの間の拡大演算および縮小演算の比較を示す。
【図１２ｄ】公知の頂点ベースシステムと本発明の実施形態に従った頂点ベースジオメトリエンジンシステムとの間の拡大演算および縮小演算の比較を示す。
【図１２ｅ】公知の頂点ベースシステムと本発明の実施形態に従った頂点ベースジオメトリエンジンシステムとの間の拡大演算および縮小演算の比較を示す。
【図１２ｆ】公知の頂点ベースシステムと本発明の実施形態に従った頂点ベースジオメトリエンジンシステムとの間の拡大演算および縮小演算の比較を示す。
【発明を実施するための形態】
【００１８】
本発明の実施形態は、既知の頂点ベース表現システムと比較して空間特性およびスピー
ド特性を改良するための頂点ベース表現法を備えたジオメトリエンジンを利用するシステ
ムに関する。本発明を理解し易くするために、例示的な実装例に関して以下に記述する。
ただし、本発明の原理がこの特定の実施形態に制限されるものではないことを理解された
い。むしろ、本発明は、あらゆるタイプのコンピュータまたはジオメトリ用に、頂点ベー
ス表現を用いることが望ましいシステムに適用可能である。コンピュータシステムの特定
ハードウェア構成要素は本発明自体の一部を形成しないが、プロセスおよび演算を生成す
るために本発明の機能がコンピュータシステムの当該ハードウェアと協働する方法を完全
に理解することを可能にするために、これらの要素について簡単に説明することとする。
【００１９】
図７において、本発明の一実施形態において使用可能な例示的なコンピュータシステム
は、それに接続された様々の外部周辺デバイス12を備えるコンピュータ10を有する。コン
ピュータ10は中央処理装置(CPU)14および関連記憶装置を含む。前記の関連記憶装置には
、通常、一般にRAM16の形で具体化される主記憶装置、例えばROM18のような静的記憶装置
、および、例えば磁気または光学デバイス20のような固定記憶デバイスが含まれる。CPU1
4は、内部バス22を介して前記の記憶装置、および、一つまたは複数の入力/出力ポート32
により外部周辺デバイス12と交信する。前記周辺デバイス12には、例えばキーボード24の
ようなデータ入力デバイス、および、例えばマウス、トラックボール、ペン、或いは、そ
の類似品のような指示またはカーソル制御デバイス 26を含む。コンピュータ10内で処理
される本発明のビジュアルディスプレイを提供するために、例えばCRTモニタまたはLCDス
クリーンのようなディスプレイデバイス28も外部周辺デバイス12に含まれる。処理済み情
報のハードコピーは、プリンタ30、或いは、同様に外部周辺デバイス12に含まれる他の類
似のデバイスを介して提供可能である。
【００２０】
本発明の一実施形態に従い、ジオメトリ用に頂点ベース表現を使用するシステムは、入
力データの増分評価の実施が可能であるように、例えば図8(a)に示すような基礎的データ
構造を有する。図8(a)に示す基礎的データ構造50の一例には、オーバラップ（overlap）
フラグビット52、ボイド（void）フラグビット54、および、フリーオンユース（free-on-
use）フラグビット56が含まれる。オーバラップフラグビット52は、処理されるべきジオ
メトリが複数の自己オーバラップ（すなわち、ジオメトリ深度が１を超える場所）をもつ
か、或いは、もつことが可能であるかどうかを表示する。ボイドフラグビット54は、ジオ
メトリがボイド（すなわち、ジオメトリ深度がゼロ未満である場所）をもつか、或いは、
もつことが可能であるかどうかを表示する。フリーオンユースフラグビット56は、ジオメ
トリの使用に際して当該ジオメトリが開放されるべきであるかどうか（すなわち、ジオメ
トリを維持するか、或いは、削除するかどうか）を表示する。さらに、データ構造50は、
分類済みの頂点に関するキュー70に対するポインタ58、および、未分類の頂点リスト72に
対するポインタ60を含む。
【００２１】
分類済みの頂点に関するキュー70および未分類の頂点リスト72は、当該ジオメトリのフ
ィールド深度を有する。本発明のデータ構造50においては、無限におけるジオメトリ深度
がゼロであると定義されているファングシステムとは対照的に、無限におけるジオメトリ
のフィールド深度は一般にゼロまたは１である（しかし、任意の値であってもよい）ので
、本発明によって真の逆ジオメトリ（true inverse geometry）が表現され得る。
【００２２】
さらに、分類済みの頂点に関するキュー70および未分類頂点リスト72は、リンク済みリ
スト内に頂点の小さいキャッシュも有する（ファングシステムの頂点リストに類似する）
。分類済みの頂点に関するキュー70は、さらに、頂点のキャッシュが空である場合に呼び
出される補充機能に対するポインタ、および、補充機能が必要とするあらゆるデータに対
するポインタを含む。
【００２３】
使用に際して、図8(b)のフローチャートの例に示すように、一つのキューから一つの頂
点を抽出するために一つのキューからその次の頂点を得るための標準手順が提供される。
図8(b)においては、頂点キャッシュが空であるかどうかはステップS100において決定され
る。頂点キャッシュが空である場合には、ステップS102において補充機能が呼び出される
。次に、ステップS104において、当該頂点キャッシュが依然として空であるかどうかが再
度決定される。頂点キャッシュが未だ空である場合には、この過程は完了する。ただし、
ステップS100またはステップS104の何れかにおいて当該頂点キャッシュが空でないことが
決定された場合には、ステップS106において、当該頂点キャッシュから第一の頂点が除去
され、そして、この過程が完了する前に戻される。
【００２４】
通常、補充機能が呼び出されると、当該機能は、頂点の小さいグループを当該頂点キャ
ッシュ内に置く。補充機能は頂点のすべてのグループに関してただ一度だけ呼び出される
ので、よって補充機能を呼び出すオーバヘッド時間は短縮される。この頂点グループの正
確なサイズは変化し得るが、当該頂点グループのサイズは、当該頂点キャッシュが必要と
するメモリが小さくなるように、当該頂点キャッシュ内に少数の頂点を置くように指定さ
れる。例えば、（例えば、アンパックおよび減少処理のような）走査線処理を実行中の補
充機能においては、一般に、１回の呼び出しにつき一つの走査線が処理され、そこから、
一度で頂点キャッシュ内に置かれる頂点の個数が決定される。
【００２５】
本発明の一実施形態において、分類済みの頂点に関するキュー70用に用いる場合と同一
のデータ構造を用い、未分類頂点リスト72を具体化しても良いが、ここでは「補充機能」
が決して当該頂点キャッシュの補充することはない。従って、当該頂点キャッシュは完全
な頂点リストを含む。
【００２６】
このデータ構造は、分類済みの頂点に関するキュー70内のデータが、当該データが引き
渡されるにつれて、開放（free）されるように、分類済みの頂点に関するキュー70によっ
て順番に頂点が引き渡されることを可能にする。結果を計算するために入力データが使わ
れるにつれて、当該入力データを開放することによって、データが増分評価されることが
可能となる。ゆえに、あらゆる所与の時間において、中間的な結果の小さな部分のみが存
在し、データを処理するために必要とされるメモリ空間の量を減少させ得る。
【００２７】
補充機能および関連するデータについて包括的に説明したが、説明をより明瞭にするた
めに、特定の実施形態の適用について以下に説明する。データのブロックを併合する場合
、補充機能は、二つのキューから頂点をピールアウト（peel out）可能であり、出力に適
切な順序で当該頂点を引き渡すことが可能である。この実施形態に用いたデータ構造は、
二つの入力キューに対するポインタ、および、各入力キューから取り除いたばかりの頂点
に対する一つのポインタを含む。補充機能は、比較のために頂点を除去することが可能で
あり、その後、一方が将来参照するためにセーブされる一方で、他方を戻すことが可能で
なければならない。
【００２８】
図8(c)は、キュー自体に関する本発明の実施形態に使用可能なデータ構造を示す。キュ
ーデータ構造200は無限における深度を表すフィールド深度データ 202、補充機能254と関
連した補充機能ポインタ204、コピー機能256と関連したコピー機能ポインタ206、開放機
能258と関連した開放機能ポインタ208、補充機能254に関するデータを備えた構造260と関
連したソースデータポインタ210、キャッシュにおける頂点の個数を表すキャッシュカウ
ントデータ212、キャッシュヘッドポインタ214、および、キャッシュテールポインタ216
を含む。構造260の形式は補充機能254に応じて可変である。キャッシュヘッドポインタ21
4は、キャッシュ2201、2202、…、220nのリンク済みリストの初めを指示し、キャッシュ
テールポインタ 216はキャッシュのリンク済みリストの終りを指示する。キャシュされた
各頂点は、次のポインタ2221、2222、…、222n、頂点のタイプに関するフィールド 2241
、2242、…、224n、並びに、xおよびyフィールド2261、2262、…、226nおよび2281、2282
、…、228nを含む。この場合、接地記号によって表されるように、キャッシュリストにお
ける次の最後のポインタは無効（null）ポインタである。
【００２９】
図8(d)および8(e)は、それぞれ、マージャ(merger)におけるソースデータに関する構造
およびマージャの補充演算に関するフローチャートを示す。図8(d)において、ソースデー
タに関する構造300は第一のキューポインタ302、第一のキューピークポインタ304、第二
のキューポインタ306、および、第二のピークポインタ308を含む。第一のキューポインタ
302は第一のデータキュ−310を指示し、第一のキューピークポインタ 304は、第一のキュ
ーデータ構造310から第一の頂点データ312までを指示する。第一の頂点データ312は、ネ
クストデータポインタ314、頂点のタイプのデータ 316、並びに、xおよびyデータ318およ
び320を含む。第二のキューポインタ306は第二のデータキュー322を指示し、第二のキュ
ーピークポインタ308は第二の頂点データ324を指示する。第二の頂点データ324はネクス
トデータポインタ326、頂点のタイプのデータ328、並びに、xおよびyデータ330 および33
2を含む。
【００３０】
図8(e)に示すような本発明の実施形態用のマージャ補充機能が、図8(d)のソースデータ
構造のために説明され得る。第一のピークポインタに関する頂点のデータが第二のピーク
ポインタに関する頂点のデータの前に来るかどうかがステップS400で決定される。第一ピ
ークポインタが第二ピークポインタの前に来ない場合には、第二ピークポインタと関連し
た頂点のデータは、ステップS410において、頂点キャッシュまで動かされる。次に、ステ
ップ S420において、第二キューが空であるかどうかが決定される。第二キューが空であ
る場合には、メモリは開放され、ステップS450において、第一データキューによって置き
換えられ、その後で、当該プロセスは完了する。ステップS420において第二データキュー
が空でないことが決定された場合には、第二データキューからの第一頂点データは、ステ
ップS430において、第二ピークポインタに置かれる。次に、ステップS440において、当該
キャッシュ内に充分な頂点が存在するかどうかが決定される。当該キャッシュ内に充分な
頂点が存在しない場合には、当該プロセスはステップS400に戻るが、当該キャッシュ内に
充分な頂点が存在する場合には、プロセスが完了する。
【００３１】
ステップS400に戻り、第一ピークポインタ用の頂点データが、第二ピークポインタ用の
頂点データの前に来る場合には、第一ピークポインタと関連した頂点データは、ステップ
S460において、キャッシュへ移動される。次に、ステップS470において、第一キューが空
であるかどうかが決定される。第一キューが空である場合には、メモリが開放され、ステ
ップS490において、第二データキューによって置き換えられ、その後で、当該プロセスは
完了する。ステップS470において、第一データキューが空でないことが決定された場合に
は、ステップS480において、第一データキューからの第一頂点データは第一ピークポイン
タ内に置かれる。次に、当該キャッシュ内に充分な頂点が存在するかどうかを決定するた
めに、プロセスはステップS440まで進む。
【００３２】
分類済みの頂点に関するキュー70および未分類頂点リスト72を使用することは、大量の
入力データをシステム内へ読込むことも可能にする。既知のファングシステムにおいて、
当該システムヘ読込み可能な入力データの量は、未分類入力リストによって制限されてい
る。ファングシステムが入力データを受け取ると、未分類入力データは、一つの単一未分
類頂点リストに直接記憶され、ここで、受け取り可能な入力データの量は前記単一未分類
頂点リストのサイズに依存している。入力データ量が処理システムの記憶容量を超過した
場合、当該ファングシステムは、一切の入力データを処理することなしに、処理を中止す
る。
【００３３】
本発明の一実施形態において、分類済みの頂点に関するキューおよび未分類頂点リスト
は、ファングシステムのこの制限を処理するために利用される。本発明のこの実施形態に
おいて、入力データは未分類頂点リスト72に直接引き渡され、当該システムは、入力デー
タが、いつ未分類頂点リスト72の所定の最大サイズに到達する、或いは、超過するのか決
定する。入力データがこの所定量に到達するか、或いは、超過した場合には、未分類頂点
リスト72へ読込まれたデータは分類され、圧縮された形式に変換され、その後で、この検
出に際して分類済みの頂点に関するキュー70内に記憶されるので、未分類頂点リスト72が
一掃され、そして、追加入力データを受け取る準備が整えられる。分類済みの頂点に関す
るキューが、未分類リストよりも一層コンパクトに記憶されることが可能であるので、シ
ステムは、未分類頂点リスト72における利用可能な記憶空間を超過する大量の入力データ
を読取ることができる。
【００３４】
本実施形態の一例を図8(f)に示す。入力データ量が利用可能な記憶空間の所定量に到達
するか、或いは、これを超過した場合、入力データは、分類され、分類済みの頂点に関す
るキュー70へ転送される前に、未分類頂点リスト72へ読込まれる。この決定を実施するた
めのプロセスステップの一例を図 8(f)に示す。ステップS10において、データは、未分類
頂点リスト72に入力される。次に、システムは、未分類頂点リスト72へ入力されたデータ
が、ステップS20において、未分類頂点リスト72内に入力データを記憶するために利用可
能な空間量を表す所定量に到達するか、或いは、これを超過するかどうかを決定する。入
力データがこの所定量に到達するか、或いは、これを超過した場合には、未分類頂点リス
ト72におけるすべての新規データは、ステップS30において、分類される。新規データを
分類済みの頂点に関するキュー70に併合するために、新規データは、ステップS32におい
て、減らされ、ステップS34において圧縮され、その後、ステップS40において、分類済み
の頂点に関するキュー70に記憶される。未分類頂点リスト72も、ステップS40において一
掃され、さらに大量のデータ受取りのために利用可能となる。ステップS40の後、または
、入力データが所定の入力値を超過しないことがステップS20において決定された場合、
プロセスはステップS50まで進み、ここで、さらに多量の入力データが利用可能かどうか
について決定が行われる。さらに多くの入力データが利用可能である場合には、プロセス
は、未分類頂点リスト72へさらに多くのデータを入力するために、ステップS10まで進む
。それ以上の入力データが利用可能でない場合には、この入力データ処理は完了する。上
記のプロセスは、システムへデータを入力するためのメモリ空間とメモリ速度に関する問
題を最適化する。
【００３５】
さらに、別体の（separate）分類済みの頂点に関するキュー70および未分類頂点リスト
72は、頂点リスト全体を再分類することなしに、追加のジオメトリ図形を現行ジオメトリ
に加えることも可能にする。分類プロセスは、頂点ベースシステムにおいて頻繁に実施さ
れる基本的プロセスであるので、一般的な併合/分類プロセスについて簡単に検討するこ
とにする。併合分類プロセスにおいて、リストマージャは、各リストの第一エレメントを
繰り返し比較し、その後、最初に到来したエレメントを当該出力リストへ入れることによ
り、二つの分類済みのリストを併合する基本的なエレメントである。さらに一般的には、
n個のアイテムを含む一つの未分類リストは、それぞれ１個のアイテムを含むn個のリスト
に分割されるが、図による説明を容易にするために、８個のアイテムを含む一つのリスト
を図示することにする。１個のアイテムを含むリストの対は、２個のアイテムを含む半分
の個数のリストに併合され、２個のアイテムを含むリストの対は、４個のアイテムを含む
半分の個数のリストに併合される。これらの相互作用的プロセスは、結果が一つのリスト
に記憶されるまで繰り返される。
【００３６】
８個のアイテムを含む一つのリストを分類するための併合/分類プロセスを図９に示す
。図９において、８個のアイテムを含むリストは、(a)(g)(d)(c)(e)(b)(h)(f)によって表
される。ステップの最初のグループにおいて、併合/分類ユニット100、102、104、106は
、一個のアイテムを含むリスト対、(a)および(g)、(d)および(c)、(e)および(b)、(h)お
よび(f)を併合する。最終ステップにおいて、併合/分類ユニット112は、４個のアイテム
を含む二対のリスト（a,c,d,g）および（b,e,f,h）を８個のアイテムを含む一つの分類済
みのリスト（a-h）に併合する。n個のアイテムを一つの分類済みのリストに併合するため
に各頂点が必要とするステップ数に関して、一般化された関係式はlog2 nであり、必要な
ステップの全個数はn log2 nである。このケースで言う「ステップ」とは、サブリストか
らの頂点をまず比較すること、および、この比較に基づいて最初に到来するべき頂上を出
力することを含む。図９に示す８個のアイテムを含むリストに関する例において、アイテ
ム当たり必要なステップ数は３ステップ(log2 8)である。併合分類プロセスを用いて８個
のアイテムすべてを処理するためには、24ステップ(8 log2 8)が必要である。
【００３７】
分類(sorting)はシステムのスピードを低下させる低速プロセスであるので、本発明は
、頂点の乱れをできる限り防止することで、分類を制限する。本発明の一実施形態におい
て、分類演算を回避するための技法は、頂点リストを再分類する前にスケールファクタ(s
cale factor)を決定することに関係している。本実施形態の一般原則は、スケーリングが
、頂点の完全分類を開始することを防止することである。スケーリング演算は高頻度で実
施されるので、前記の原則は集積回路設計に有用である。さらに詳細には、スケールファ
クタが１より大きい場合には、当該リスト内の頂点は秩序を保っているので、再分類演算
は一切実施されない。ただし、スケールファクタが１未満である場合には、走査線が併合
するかもしれない。従って、基準化された同一Y座標をもつすべての頂点が収集され、複
数のオリジナル走査線を有する頂点に関する再分類演算が実施される。頂点の再分類はス
ケーリング後に自動的に実行されるわけではないので、本実施形態において、スケーリン
グプロセスに際して不必要な分類を実施することが回避され、その結果としてシステムス
ピードが改良されることとなる。
【００３８】
本発明のさらに別の実施形態においては、さらに迅速な併合分類演算が実行されるよう
に拡大および縮小演算の後に、短縮された併合分類演算が実行される。対照的に、既知の
ファングシステムは、さらなる時間を消費する完全な併合分類演算を実行する。さらに詳
細には、即時の減少には分類済みのリストを要する減少を必要とするので、前記ファング
システムは、縮小演算直後に分類演算動作を実行してしまう。拡大演算後、前記ファング
システムは、未分類リストとしての頂点リストに単純にタグを付けるのに過ぎず、通常、
その次の演算の前に類別されるべき頂点リストを必要とする。しかし、本発明において、
完全分類は、さらに迅速な短縮された併合分類によって代置される。拡大または縮小演算
の後の分類を制限する技法は、図10に示すように、各頂点が四方向（左上、右上、右下、
左下）のうちの一方向のみに移動可能であるという事実に基づく。所定の方向の任意の一
方向に移動する頂点は適切に分類された状態に留まるので、本実施形態においては、頂点
が移動する方向に基づいて各頂点を類別した後、二つの最終ステップとして、併合/分類
が実施される。拡大および縮小演算後の再分類に必要な時間量は、この技法によって大幅
に減少される。明確には、完全分類によるステップ数(n log2 n)は、本実施形態の技法の
ためのステップ数(n log2 4)によって置き換えられるので、当該システムのスピードは、
係数log2 n / log2 4だけ増大される。ここで、nは分類されるべき回数である。
【００３９】
本発明の他の実施形態では、回転およびミラーリング演算の間、再分類が回避され得る
。X方向におけるミラーリング演算に関しては、各走査線における頂点は蓄積され、その
後で、反転し得る。X座標をX方向で反転することにより、X方向におけるミラーリング演
算に関する再分類を回避し得る。アンパッカ演算（後に詳細に説明する）は、頂点が走査
線順に取得され、エッジリストが維持される減少機能に類似する。ファングシステムにお
けるのと同様に、対象となる点を解析するコンセプトが実行される。さらに、右上象限に
おけるジオメトリ深度が予測され、入力データに当該頂点が見付かった場合には、前記予
測は訂正される。
【００４０】
しかし、アンパッカ演算は、ゼロおよび１の深度のみを扱い、減少機能と異なる予測規
則が用いられるという点において、減少機能とは異なっている。データの圧縮された形式
がすべての四隅を全く同じに記憶し、第一頂点の場合と同じ方法において各走査線におけ
る最終頂点を明確に記憶する場合には、アンパッカ演算は、Y方向におけるミラーリング
演算に関して、バイトストリームを後方に向かって読取り得る。事実上、この演算は、Y
およびX両方向をミラーリングする。例えば90度回転のような座標交換演算を実施するた
めには、非回転ジオメトリのO(√n)走査線列であったO(√n)カラムを併合することが必要
である。ステップ数は依然としてO(n log2 n)のままである。ここで、n=アイテム個数で
あるが、ただし、各カラムは圧縮された形式に留まるので、完全な分類と比較すると必要
とされる記憶容量は少なくなる。
【００４１】
本発明はオーバラップとボイドの両方を表現可能であるので、現在知られている頂点ベ
ースシステムの場合と比較して、より迅速で、より少ない記憶容量を用いて、より能率的
にブール演算を実施することができる。次に、OrおよびAnd演算について記述する。まず
、各ジオメトリオペランドからの頂点に関するキューがアクセスされる。未分類頂点リス
トがデータを含む場合には、当該リストは、分類され、その後、分類済みのキューに併合
されなければならない。当該ジオメトリの使用がフリーオンユース(free on use)である
場合には、ジオメトリ構造は開放される。当該ジオメトリがボイド（Or演算）、または、
オーバラップ（And演算）をもつ場合に、減少済みフラグがセットされていないならば、
キューは減少機能をパスする。この減少機能はコピー演算の前に実施されるので、このジ
オメトリを将来使用する際に、減少の必要がない。当該ジオメトリの使用がフリーオンユ
ースである場合には、結果として得られる頂点に関するキューは簡単に使用される。すな
わち、使用に際して、頂点がそこから除去されるにつれて、メモリが開放される。そうで
ない場合には、当該キューは使用前にコピーされる。各ジオメトリオペランドに関する頂
点に関するキューにアクセスした後で、オペランドから結果として得られる頂点に関する
キューが併合される。従って、フィールド深度はオペランドフィールド深度の和であり（
And機能に関しては−１）、結果として深度がゼロよりも大きいあらゆる場所にジオメト
リが存在するものと考えられる。結果的に、オーバラップをもつがボイドは持たない（Or
演算）、或いは、ボイドはもつがオーバラップは持たない（And演算）ジオメトリが提供
される。
【００４２】
図11は、C=(a Or b)、または、C=(a And b)のいずれかである、ブールジオメトリ演算
のダイアグラムを示す。図11に示すように、未分類頂点は、併合ユニット154および156に
入力される以前に、分類ユニット150および152にそれぞれ入力される。分類済みのキュー
は、併合ユニット154および156に直接入力される。併合ユニット154および156の出力は減
少ユニット158および160に入力される。対応するジオメトリが既に減少済みである場合に
は、これらの減少演算の一方または双方が省略可能である。次に、減少ユニット158およ
び160の出力は、頂点の分類済みのリストを出力する併合ユニット162に入力される。デー
タの各ブロックは、その補充機能が供給（feeding）キューから引張られる（pull）、頂
点の小さなバッチの併合または減少を一時に実行するキューを形成する。この時点におい
ては、分類のみが未分類頂点リストに実行済みである。すなわち、他の演算は準備が完了
しており、結果Cがその所望とする目的に用いられると、増分的に実行される。
【００４３】
さらに、本発明は、ジオメトリを頂点あたり16バイト/頂点で記憶するファングシステ
ムと比較した場合に、頂点あたり約3/4バイトでジオメトリを記憶する圧縮済みフォーマ
ットも用いる。本発明の圧縮済みフォーマットは、ジオメトリを記憶するために必要なメ
モリ空間量を大幅に減少する。本発明の圧縮済みデータ形式は、多量の情報は分類され減
少された頂点に関するキューから再導出可能であるという事実に基づくものである。走査
線に関しては、第一頂点だけがY座標を必要とする。従って、反復的なY座標のストレージ
が排除されるので、データストレージは圧縮される。データは、実際の各X値を記憶する
代わりに記憶されている前の頂点とX 値との差を単に記憶することによってさらに圧縮さ
れる。さらに、任意のポイントにおけるアンパッカ演算は、当該ポイントの下方および左
の三つの象限にジオメトリが存在するかどうかを前後関係(context)から決定するので頂
点タイプのストレージが削除可能である。
【００４４】
次に、アンパッカ演算は、右上の象限にジオメトリが存在するかどうかを推測する。記
憶済み頂点が検討中の点に所在する場合には、推測は誤っており訂正しなければならない
。従って、頂点のタイプは記憶する必要がない。さらに、アンパッカ演算は、ジオメトリ
の右上隅について、常に正しく推測することが可能であるので、このコーナを記憶する必
要が無く、これにより、記憶する必要のあるデータ量はさらに減少する。
【００４５】
パッカ/アンパッカの組合せを実現可能である幾つかの方法があるが、すべての場合（
減少演算の実施に際して）に共通するアイデアは、当該ポイントの左および下に所在する
三つの象限におけるあらゆるポイントの深度をアンパッカが既知であるということである
。これらに基づき、アンパッカは、右上象限における深度がゼロまたは１のどちらである
かを推測する。圧縮隅データ内に記憶された一つの頂点がある場合には、この推測は誤っ
ていたことになり、アンパッカは他方の深度を選定する。アンパッカがどのように推測す
るかをパッカが理解する限り、必要な場合には頂点を記憶し、そうでない場合には記憶し
ないようにアレンジ可能である。
【００４６】
原則としては、アンパッカ演算の推測アルゴリズムは、既知の象限における深度に基づ
いた表を使用することができる。実際、アンパッカにとっては、減少演算に関する規則に
従って「解析」されるはずのポイントに存在する頂点を含む推測を実施することだけが望
ましい。そうでない場合には、アンパッカ演算は、所定の場所全体における頂点の存在を
推測することになり、これらの推測を訂正するために非常に多くの頂点を記憶しなければ
ならなかったはずであるので、「圧縮された」形式が極度に大きくなってしまう。さらに
、走査線が垂直な縁を横切る際に、この点に頂点が所在すると推測することも有り得る。
従って、関心の対象になるパッカ/アンパッカの組合せ数は小さい。表２は、あらゆる「
良好な」アンパッカが、任意の点において何を推測しなければならないか（或いは、どち
らの選択が良好と考えられるか）、および、二つのアンパッカに関する選択を示す。
【００４７】
【表１】
2009199616.tif 000003
LRとULの深度が同じであり、LL深度が異なる場合には差が推測される。この場合、頂点
は存在しなければならないので、ここでの推測は存在する頂点の種類を決定するだけのも
のである。アンパッカ１による仮定は、それが単純に右上頂点であることを意味するもの
である（二つのケースで、各々凹状若しくは凸状）。アンパッカ２の仮定は、それが複雑
な頂点であることを意味する。複雑な頂点は稀であり、正常な頂点の集まりにおける約1/
4は右上頂点によって占められるので、本発明の好ましい実施形態においてはアンパッカ
１を使用した。アンパッカ２は、前方と同様に後方へもアンパックすることを可能にする
唯一のアンパッカであり、Y方向において能率的にミラーリングする本発明の実施形態を
実現するために用いることが好ましい。
【００４８】
パッカは極めて単純なジョブを有することに留意されたい。パッカは、入ってくる頂点
に関するキューを単純に取って、頂点のタイプに厳格に基づいて、それを記憶するか、或
いは、当該頂点のロケーションを記憶しない。アンパッカ１に関しては、当該パッカは、
右上の頂点を除いて、すべての頂点のロケーションを記憶しなければならない。アンパッ
カ２に関しては、当該パッカは、複雑な頂点を除いて、すべての頂点のロケーションを記
憶しなければならない。
【００４９】
本発明における圧縮済みデータ形式を使用することにより、メモリレイアウトのバイト
ストリーム（byte stream）をファイル内にセーブすることができる。メモリレイアウト
は、メモリ割当の便宜上、管理可能な部分に分割しても良い。本発明の一実施形態におい
て、各走査線は、ゼロのΔX値によって指示されている走査線の終端を伴った一連のΔXが
後続する全体X-Y位置（full X-Y position）でスタート可能である。各ΔXのバイト数は
可変である。例えば、一つのバイトの最上位のビットが１である場合には、その次のバイ
トは、さらに七個の前記値のビットを含むことが予測されるはずである。ほとんどのΔX
値は128未満であり、４個の頂点のうちの３個だけが記憶されるので、この圧縮されたデ
ータ形式は、頂点あたり約3/4バイトでジオメトリを記憶可能である。
【００５０】
圧縮済みデータフォーマットは、複数回にわたってデータが処理されるべき場合、最も
有利に使用される。非フリーオンユースジオメトリがアクセスされる場合いつでも、頂点
に関するキューがコピーされなければならない。本実施形態では、圧縮された分類済みの
頂点に関するキューに限りコピーされることが可能である。従って、非圧縮型のキューは
、コピーされる前に、圧縮されなければならない。圧縮済みキューのコピーは比較的速い
演算であるが、用語「コピー」は幾分誤った呼び方である。既に述べたように、メモリレ
イアウトは管理可能なブロックに分割され、この種の各メモリブロックは基準カウントを
もつ。この種のコピーは、すべての基準カウントがインクリメント（増加）される場合に
、有利に使用される。アンパッカ演算が一つのブロックで終了する場合には、基準カウン
トがデクリメント（減少）され、基準カウントがゼロである場合には、メモリは開放され
る。このことが、コピー演算の迅速な実施を可能とする。Y方向におけるミラーリング演
算に関しては、アンパッカ演算は、圧縮済み形式のデータに関連して使用可能である。
【００５１】
本発明の他の技法は、拡大および縮小演算に起因する問題へと向けられる。小さい図を
縮小する、或いは小さい孔を原形が無くなる程拡大する場合に、実際の頂点タイプを歪め
てしまうという、特定の問題が起きる。この場合、各頂点の属性である深度Δのみが検討
対象になり、実際の頂点タイプは検討対象とならないので、減少機能に際してこれらの問
題が発生する。対角線上で対向するコーナの深度Δは同じであるので、ジオメトリ図形が
両軸において反転される場合、当該ジオメトリ図形は、図12(a)および12(b)に示すように
、戻る（come back）。ファングシステムにおいては、図12(c)および12(e)に示すように
、合成頂点を付加することが知られている。対照的に、本発明は、図12(d)および12(f)に
示すように、一つのコーナタイプに余分の頂点を追加するだけである。その結果として、
用いられる頂点情報は少なくなり、必要なメモリスペース、および、これらの演算に必要
な処理時間が短縮される。
【００５２】
ゼロ未満の深度や１よりも大きい深度を対称的に扱うことによって、本発明によって更
なるスピード改善が達成される。詳述すると、あるAndまたは縮小演算の結果が、他のAnd
または縮小演算に用いられれば、結果を減少させる必要がない。一方で、別法で生じ得る
ボイドは表現されないので、ファングシステムはAndまたは縮小演算の後、常に減少する
。結果として、処理時間が短縮される。また、減少演算の変形例は、ゼロより大きい深度
を有するエリアのみがジオメトリを有しているとして解釈するのではなく、奇数深度を有
するエリアをジオメトリを有しているとして解釈することでもある。このことで、排他的
OR演算が基本演算として実行されることが可能となる。排他的OR演算のためのジオメトリ
オペランドは、この機能が適切に作動するために、一切のオーバラップまたはボイドをも
ってはならない。
【００５３】
本発明の実施形態は、スピードを向上させる一方で、既知の頂点ベースシステム全体に
わたって用いられるメモリの量を減少させる頂点ベースジオメトリエンジンに関する。メ
モリスペースの減少は、主として、中間結果の小さい部分だけが任意の時点において常に
存在するように、入力データが使用され結果が計算されるにつれて、入力データを開放す
る当該入力データの増分評価に起因させることができる。メモリスペースの量の節減は、
さらに小さいメモリスペースでジオメトリを記憶するため、圧縮されたフォーマットを利
用することによっても達成される。本発明の頂点ベースジオメトリエンジンシステムはス
ピードも改良する。スピード改善は、メモリスペースの節減改善に大きく貢献し得る。追
加的なスピード改善は、分類演算が減るように、頂点の乱れを可能な限り防止することに
よって達成される。追加的なメモリスペースおよびスピード改善を提供する拡大および縮
小演算の間は不必要な頂点の生成が排除されるので、ジオメトリの減少演算は、また、最
小限化される。
【００５４】
本発明を以上のように説明したが、本発明は多くの方法で変化可能であることは明白で
あろう。この種の変形は、本発明の精神および範囲からの逸脱と見なされるべきではなく
、この種すべての改変は、次の請求の範囲内に含まれることを意図したものであることは
当該技術分野における当業者にとっては明白であるはずである。
【図１ａ】
2009199616.tif 000004
【図１ｂ】
2009199616.tif 000005
【図１ｃ】
2009199616.tif 000006
【図２ａ】
2009199616.tif 000007
【図２ｂ】
2009199616.tif 000008
【図３ａ】
2009199616.tif 000009
【図３ｂ】
2009199616.tif 000010
【図３ｃ】
2009199616.tif 000011
【図３ｄ】
2009199616.tif 000012
【図３ｅ】
2009199616.tif 000013
【図３ｆ】
2009199616.tif 000014
【図４ａ】
2009199616.tif 000015
【図４ｂ】
2009199616.tif 000016
【図４ｃ】
2009199616.tif 000017
【図４ｄ】
2009199616.tif 000018
【図４ｅ】
2009199616.tif 000019
【図４ｆ】
2009199616.tif 000020
【図４ｇ】
2009199616.tif 000021
【図４ｈ】
2009199616.tif 000022
【図４ｉ】
2009199616.tif 000023
【図４ｊ】
2009199616.tif 000024
【図５】
2009199616.tif 000025
【図６】
2009199616.tif 000026
【図７】
2009199616.tif 000027
【図８ａ】
2009199616.tif 000028
【図８ｂ】
2009199616.tif 000029
【図８ｃ】
2009199616.tif 000030
【図８ｄ】
2009199616.tif 000031
【図８ｅ】
2009199616.tif 000032
【図８ｆ】
2009199616.tif 000033
【図９】
2009199616.tif 000034
【図１０】
2009199616.tif 000035
【図１１】
2009199616.tif 000036
【図１２ａ】
2009199616.tif 000037
【図１２ｂ】
2009199616.tif 000038
【図１２ｃ】
2009199616.tif 000039
【図１２ｄ】
2009199616.tif 000040
【図１２ｅ】
2009199616.tif 000041
【図１２ｆ】
2009199616.tif 000042
【手続補正書】
【提出日】平成21年5月1日(2009.5.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
拡大および縮小演算の後で集積回路の設計のジオメトリの頂点ベース表現を分類するための方法であって、
(a)前記拡大および縮小演算の後で前記ジオメトリの頂点をそれぞれの頂点が移動した方向に基づいて四組に分割し、
(b)二組の分類済みの頂点を生成する前記ステップ(a)において分類された前記四組の頂点の第一および第二の対に併合/分類演算を実施し、
(c)一組の分類済みの頂点を生成するために前記ステップ(b)からの二組の分類済み頂点に併合/分類演算を実施する方法。
【請求項２】
拡大および縮小演算の後で集積回路の設計のジオメトリの頂点ベース表現を分類するためのシステムであって、
前記拡大および縮小演算の後で、それぞれの頂点が移動した方向に基づいて、前記ジオメトリの頂点を四組に分割するための分割手段と、
二組の分類済みの頂点を生成するために前記四組の頂点の第一および第二の対に併合/分類演算を実施し、一組の分類済みの頂点を生成するために前記二組の頂点に併合/分類演算を実施するためのプロセッサとを有するシステム。
【外国語明細書】
2009199616000001.pdf