JP3103793B2

JP3103793B2 - オブジェクトの構造グラフ生成装置、それを利用することの可能なデータ変換装置およびシステム

Info

Publication number: JP3103793B2
Application number: JP09362413A
Authority: JP
Inventors: 嘉久品川; 和樹廣瀬
Original assignee: 株式会社モノリス
Priority date: 1997-03-11
Filing date: 1997-11-25
Publication date: 2000-10-30
Anticipated expiration: 2017-11-25
Also published as: JPH10312472A; US6323863B1

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、オブジェクトの
構造を示すグラフを生成する方法と装置、およびそれら
を利用することの可能なデータ変換の方法、装置、シス
テムおよび記録媒体に関する。この発明は、例えばＣＡ
Ｄ（コンピュータ支援設計）やＣＧ（コンピュータグラ
フィクス）における立体のデータに適用することができ
る。

【０００２】

【従来の技術】ＣＡＤやＣＧの分野で物体または立体な
どのオブジェクトを記述するとき、従来よりポリゴン
（多角形）を用いた近似表現が知られている。この方法
はオブジェクトの表面を細分化してポリゴンパッチを貼
り付けていくもので、今日まで数多くのオブジェクトが
ポリゴンデータの形で作成され、データベース等に保持
されている。ポリゴン表現がこれほど普及した理由とし
て、方法が単純で理解しやすいことや、どのようなオブ
ジェクトでも、根気よく作業をすれば必ず三角形パッチ
で覆い尽くせることがあげられる。

【０００３】すでに指摘されて久しいが、ポリゴン表現
の問題は、精緻性の追求がデータ量の増加に直結する点
にある。ポリゴン自体は平面的であるから、曲面の滑ら
かさや複雑な形状を表現する場合、より小さなポリゴン
をより多数貼り付ける他に有効な手がない。例えば人物
をある程度精緻にモデリングするとき、一般に数万から
数十万のポリゴンが必要である。ジュラシックパークや
アポロ１３など、ＣＧを駆使した映画の驚異的な映像に
慣らされてしまった現在、ユーザはＣＧによってどのよ
うな映像でも創り出すことができると考える。こうした
ユーザの要求に少しでも沿おうとすれば、ポリゴン表現
を使う限り、自ずとポリゴン数増加の途を辿るほかな
い。

【０００４】ポリゴン数の激増を受容した背景に、最近
のコンピュータハードウエアの長足の進歩がある。メイ
ンメモリ搭載量、二次記憶装置容量、ＣＰＵ性能のいず
れをとっても数年前とは比較にならない改善がなされて
おり、大きなポリゴンデータにもある程度対応ができ
る。しかし、インターネットを利用した通信の普及に伴
い、電話回線を介した精緻画像の伝送にきわめて長時間
を要する問題が露呈し、画像のデータ量が一般に大きい
ことが広く認識されるようになった。今後、さらに大き
なポリゴンデータを扱うのであれば、回線等のインフラ
ストラクチャも含めたハードウエアのさらなる改良の他
に手だてはなく、ハードウエアとポリゴン数の「いたち
ごっこ」には終わりが見えない。

【０００５】こうした事情に鑑み、ポリゴンのデータ量
削減については従来よりいろいろな取り組みがなされて
きた。特開平８−１５３２１１号公報（コンピュータグ
ラフィックスデータのポリゴン削減装置）には、視点情
報に応じて冗長なポリゴンを削減する装置が開示されて
いる。この装置によれば、表示品質を維持しながら描画
速度を高めることができる。しかしこの装置の場合、オ
ブジェクトを表現するオリジナルのポリゴンデータはそ
のまま残されているから、その意味でデータ量は削減さ
れない。

【０００６】特開平７−２６２４０２号公報（曲面の表
示方法）には、ポリゴンの辺をその両端点の法線方向に
注目して円弧に変換し、オブジェクトの輪郭線をより滑
らかに表示する方法が開示されている。一般に、ポリゴ
ン数が少ない場合、オブジェクトの曲面に凹凸が目立つ
が、この方法によればその欠点が緩和される。しかしな
がら、この方法はオリジナルのポリゴン数が少ないとき
に効果的であっても、この方法によってポリゴンデータ
量が減るわけではない。

【０００７】一方、ポリゴンではなく、パラメトリック
パッチと呼ばれる曲面要素によってオブジェクトを表現
する方法もある。一般に曲面要素によれば、より滑らか
な曲面を比較的少ないデータで表現できる。共立出版株
式会社「３次元ＣＡＤの基礎と応用」（鳥谷浩志、千代
倉弘明編著）の６２ページには、特徴線によって曲線メ
ッシュを生成し、曲面パッチを貼り付ける旨が記載され
ている。この教科書では、曲面パッチをどのような数式
で記述するか、パッチどうしの継ぎ目をいかに滑らかに
するか、四辺形以外の不規則形状のパッチをどのように
記述するか、などについても解説がなされている。

【０００８】

【発明が解決しようとする課題】しかしながら、曲面パ
ッチの利用における最大の課題は、処理自動化の困難性
にある。円筒など単純な形状であればパッチの貼り付け
も容易であるが、複雑なオブジェクトの場合、どこをど
のように分割すればうまく曲面パッチが貼れるか、ま
た、必要最小限の分割はどのようになせばよいのか、な
どに理論的な裏付けを与えるシステムの設計はきわめて
難しい。このため一般に、オペレータが手作業でパッチ
の貼り方を指定したり、修正する必要があった。パッチ
の貼り付けは、オペレータの経験や勘に頼る部分が大き
かった。その一方、自由曲面表現に対する取り組みを諦
めてポリゴン表現に終始すれば、重くなる一方の形状表
現に将来的展望は開けない。

【０００９】本発明はこうした現状に鑑みてなされたも
のであり、その目的は、既存のポリゴン表現に代わる表
現方法の提供にある。本発明の別の目的は、ポリゴンデ
ータを自由曲面表現に向く、より精緻な形状データに変
換する技術の提供にある。本発明のさらに別の目的は、
理論的な裏付けにもとづき、ポリゴンデータを他の表現
形式のデータに一意的かつ確実に変換する技術の提供に
ある。本発明のさらに別の目的は、単なるデータの圧縮
技術ではなく、ポリゴン表現とは本質的に異なる表現形
式のデータを生成する技術の提供にある。本発明のさら
に別の目的は、ポリゴンデータよりもデータ量の少ない
形状データを必要に応じてポリゴンデータに戻す技術の
提供にある。本発明のさらに別の目的は、ポリゴンとは
異なる形状表現を行う際に、莫大な既存のポリゴンデー
タ資産を活かす技術の提供にある。本発明のさらに別の
目的は、以上のようなデータ変換技術の実現に利用する
ことの可能なオブジェクト構造の表現技術の提供にあ
る。

【００１０】本出願人は先に特願平９−３０３２４６号
において、ドローイングツール程度の簡単なシステム
で、複雑なオブジェクトも精緻かつ一意的にモデリング
することのできる技術を提案している。本発明はその技
術と従来のポリゴン表現の架け橋としての意義も持ち、
先の出願とともにポリゴンに依存する現状の形状表現に
質的な変革をもたらすことを第一の目的とする。

【００１１】

【課題を解決するための手段】本発明の構造グラフ生成
方法は、オブジェクトの形状を表すポリゴンデータから
そのオブジェクトの位相情報を抽出することによって、
そのオブジェクトの骨格グラフを生成する。

【００１２】ここで「オブジェクト」とは、ｎ次元デー
タの形で表現できるすべてのものをいい、ＣＡＤでいう
立体（ｓｏｌｉｄ）のほか、温度分布などでもよい。
「オブジェクトの位相情報」とは、オブジェクトの構造
に関する情報といってもよい。この方法により、オブジ
ェクトの骨格に関する情報が得られるため、これをその
オブジェクトの形状定義に利用できる。骨格グラフの例
としてレーブグラフがある。レーブグラフは古典的なも
ののほか、本発明者が提案したアイコン表示（後述）で
もよい。その場合、オブジェクトの内部構造にも対応で
きる。

【００１３】本発明の別の態様は、オブジェクトの形状
を表すポリゴンデータを取得する工程と、そのポリゴン
データに関するモース関数の特異点を検出する工程と、
特異点どうしの接続情報を取得する工程とを含む。構造
グラフが特異点とそれらの接続情報を用いて記述され
る。

【００１４】本発明のデータ変換方法は、まずオブジェ
クトの形状を表すポリゴンデータからそのオブジェクト
の位相情報を抽出する。つづいて、そのポリゴンデータ
を、前記位相情報を利用した位相幾何学的データ（以下
これを単に「位相幾何学的データ」ともいう）へ変換す
る。別の表現では、本発明はオブジェクトの位相構造に
注目することより、そのオブジェクトの形状を表すポリ
ゴンデータを曲面データへ変換する。変換後のデータは
もとのポリゴンデータと表現形式が異なり、その表現形
式において最適化された形状定義に従ってデータ量が決
まる。

【００１５】本発明の別の態様は、まずオブジェクトの
位相情報を利用する位相幾何学的データを取得する。つ
ぎに、そのデータにおけるオブジェクトの表現形式に注
目して前記データをポリゴンデータへ変換する。このた
め、ポリゴンデータしか扱えないような機器と容易にイ
ンタフェイスをとることができる。

【００１６】本発明の別の態様は、オブジェクトの形状
を表すポリゴンデータを取得する工程と、そのポリゴン
データに関するモース関数の特異点を検出する工程と、
特異点どうしの接続情報を取得する工程と、オブジェク
トの断面の輪郭線情報を取得する工程とを含む。特異点
とその接続情報によって骨格グラフを生成することがで
きる。この骨格グラフに輪郭線情報を付加することでオ
ブジェクトの形式を定義することができる。

【００１７】一方、本発明の構造グラフ生成装置は、オ
ブジェクトの形状を表すポリゴンデータを入力する手段
と、そのポリゴンデータからオブジェクトの位相情報を
抽出することによってオブジェクトの骨格グラフを生成
する手段とを含む。本発明のデータ変換装置はこれらに
加え、入力されたポリゴンデータから、オブジェクトの
断面の輪郭線情報を取得する手段を含む。ただし、骨格
グラフを生成する手段は、骨格グラフを明示的に描く必
要はなく、その生成に必要な情報を収集すれば足りる。

【００１８】データ変換装置の別の態様は、オブジェク
トの位相情報を利用する位相幾何学的データを入力する
手段と、そのデータにおけるオブジェクトの表現形式に
注目して前記データをポリゴンデータへ変換する手段と
を含む。すでに位相幾何学的データが存在するとき、こ
れをポリゴンデータに戻すことができる。

【００１９】本発明のデータ変換システムは、オブジェ
クトの形状を表すポリゴンデータを位相幾何学的データ
へ変換する手段と、その結果得られたデータを記憶する
手段を含む。こうして得られたデータをポリゴンデータ
に戻すために、このシステムはさらに、記憶されたデー
タを読み出し、そのデータ構造を解析してこれをポリゴ
ンデータへ逆変換する手段を含む。データのストレージ
や伝送の際に位相幾何学的データを利用し、必要なとき
にそのデータをポリゴンデータに戻して利用する。

【００２０】

【発明の実施の形態】本発明の好適な実施形態を説明す
る。本発明を理解するに際し、本発明者が先に公表した
論文の内容を「前提技術」として説明することは有用で
ある。この前提技術は本発明者のひとりの論文（東京大
学博士論文１９９３年品川嘉久）の一部である。以下、
前提技術を引用した後、その前提技術に対して修正また
は拡張を加える形で実施形態を説明する。

【００２１】［前提技術］［１］モース理論に基づく曲面符号化システム（１）はじめに三次元空間におけるオブジェクト、つまり立体や曲面の
形状を符号化するとき、通常これらをなんらかの記号の
配列として表現する。ここで符号化とはモデリングに必
要な情報でそのオブジェクトを表現することをいう。自
然界に見られるオブジェクトの場合は、形状は非常に多
くの自由度をもつ。そのため符号化の際には一定の単純
化が必要となる。位相幾何学（トポロジー）はこうした
単純化を行うための数学的手段である。

【００２２】本システムは、位相幾何学におけるモース
（Ｍｏｒｓｅ）理論を数学的ツールとして三次元物体の
解釈を行う。後述のごとく、この理論によってオブジェ
クトのモデリングをきわめて効率的かつ矛盾なく行うこ
とができる。しかし、三次元の曲面を完全な正確さをも
って符号化するためにはモース理論だけでは不十分であ
る。以下、その理由を説明し、モース理論を拡張するこ
とによってこの間題の解消を図る。

【００２３】（２）モース理論もともとモース理論は変分法を取扱うために提唱され
た。そしてその目的は、無限次元の道の空間における汎
関数の極小値を記述することにあった。このことから逆
に、汎関数の極小値を利用することにより、それ以外の
方法での記述が困難であるような空間の位相的な特徴を
記述することが可能になる。以下、モース理論の概要を
説明する。

【００２４】◎可微分多様体モース理論を適用できる空間は可微分多様体である。有
限次元の多様体を考えてみる。いま任意の整数ｎについ
て、ｎ次元多様体は位相空間であって、そこではすべて
の点がｎ次元空間Ｒ^ｎの部分集合の上に一対一かつ両連
続に写像可能な近傍をもつとする。このような写像は
「チャート」と呼ばれ、その領域に含まれる点について
局所座標系を提供する。地球を例にとれば、緯度と経度
が局所座標系に当たる。多様体がｐ回微分可能であるた
めには、一方の座標系から他方の座標系への変換が、２
つの異なるチャートの値域に含まれる点についてｐ回微
分可能でなければならない。

【００２５】このため多様体は、可微分的に重なり合っ
たＲ^ｎの領域から構成されていると考えることができ
る。例えば、直線や円周は一次元多様体の構造を与えら
れる。また、球の表面は例えば北半球と南半球のよう
に、少なくとも２つのチャートを用いた二次元多様体を
用いて表現できる。同様にトーラスの表面は、少なくと
も４つのチャートを用いた二次元多様体によって表現で
きる。Ｒ^３から結び目のある円を取り除けば三次元多様
体の一例となる。

【００２６】◎可微分写像および特異点チャートを用いることにより、ｐ次元多様体からｎ次元
多様体への写像はＲ^ｐの各区分からＲ^ｎの各区分への写
像として（区分ごとに）数値表現することができる。こ
れらの写像については微分可能性を検証することができ
る。要素がｋ回連続的に微分可能であれば、その写像は
Ｃ^ｋ級である。

【００２７】ここで局所座標系の上で高さ関数を定義す
る。高さ関数は与えられた点の高さ（物体が埋め込まれ
ている三次元空間におけるｚ座標など）を返す関数であ
る。高さ関数ｈ：Ｒ^２→Ｒのヤコビ行列は、

【００２８】

【数１】

【００２９】で与えられる。ヤコビ行列は各点について
計算することができ、そのランクの最大値はｎとｐの小
さいほうである。ヤコビ行列のランクがこの最大値に等
しい点は「正則点」と呼ばれ、それ以外の点は「特異点
（ｓｉｎｇｕｌａｒｐｏｉｎｔ）」または「臨界点
（ｃｒｉｔｉｃａｌｐｏｉｎｔ）」と呼ばれる。例え
ば、高さ関数に関する特異点には、頂上点（ｐｅａ
ｋ）、鞍点（ｓａｄｄｌｅｐｏｉｎｔ）、谷底点（ｐ
ｉｔ）がある。別のいいかたをすれば、特異点はヤコビ
行列がゼロベクトルとなる点であり、特異点では法線ベ
クトルが高さ方向と同じ方向を向く。

【００３０】◎ヘッセ行列と指数ｎ次元多様体からＲへの写豫（以下「多様体上の関数」
と呼ぶ）については、ある点における偏微分の値がすべ
て０の場合、その点が臨界点となる。そのような点にお
いて、前述の関数は二次偏微分に基づく二次形式によっ
て近似される。この行列表示はヘッセ行列と呼ばれ、そ
の要素は以下のように記述される。

【００３１】

【数２】

【００３２】特異点におけるヘッセ行列の負の固有値の
数をその特異点の指数（ｉｎｄｅｘ）と呼ぶ。指数は後
述の図１に示すとおり、被約形式におけるマイナス符号
の数に等しい。すなわち、頂上の指数は２、鞍点は１、
谷底点は０である。後述の図３（ａ）〜（ｃ）のごと
く、トーラスの場合、指数２、１、０の臨界点はそれぞ
れ１個、２個、１個である。

【００３３】臨界点におけるヘッセ行列のランクがｎで
あるとき、その特異点は縮退していない、すなわち「非
縮退」と呼ばれる。どのようなＣ^２級関数でも、モース
関数によって近似することができる。モース関数とは、
臨界点の縮退がないような関数をいう。したがって、モ
ース関数の臨界点は孤立しているはずであり、コンパク
トな多様体に関する限り、臨界点は有限個しか存在しな
い。

【００３４】◎ホモトピーの型モース理論によれば、多様体とその多様体上のモース関
数が与えられ、その関数の特異点の指数の列び方が判明
すれば、各特異点に対応する一連の演算を行うことによ
って、その多様体と同じホモトピータイプの位相空間を
胞複体（ｃｅｌｌｃｏｍｐｌｅｘ）として構築するこ
とができる。

【００３５】高さを表す任意の実数について、セル（胞
体）はその実数の示す高さ以下の点からなる多様体の部
分に関するモデルを与える。Ｒが上下に走査されると
き、２つの連続する特異点間ではセルの位相は変化しな
いが、特異点を横切るたびに、それ以前のセルに対して
「ｋ次元セル」をつなげていくことにより、胞セルを作
り上げていくことができる。ここでｋは横切った特異点
の指数である。簡単にいえば、物体の形はその臨界点の
指数と同じ次元をもつセルというものを貼り合わせるこ
とで復元できる。

【００３６】図１は、特異点の指数、ｋ次元セルおよび
それによって符号化される物体の関係を示す図である。
ここでは物体としてトーラスを挙げている。同図のごと
く、注目する高さが臨界点を含む高さを横切るとき、そ
の高さより下の点によって構成される位相が変化する。
この変化は、位相的に見れば後述するようにｋ次元セル
をつないでいくことと同じである。同図のごとく、二次
元セル（ｋ＝２）はお椀を伏せたような形、一次元セル
（ｋ＝１）は紐のような形、０次元セル（ｋ＝０）はひ
とつの点で表すことができる。もとの物体の形は、それ
らのセルをつなげた上で、粘土細工のように変形するこ
とで得られる。トーラスの場合、二次元セルを１個、一
次元セルを２個、０次元セルを１個つなげて得られる。

【００３７】ここで注意すべきは、指数の配列だけでは
セルを完全に記述することはできないことである。図２
（ａ）〜（ｃ）は、それぞれが同じモースの指数の配列
をもつ３組の曲面を示す。このように、指数の配列だけ
でセルを完全に決めることはできない。そのため、セル
をつないでいくときにいずれの連結成分（それぞれ独立
した実体）が関連するかを知らなければならない。

【００３８】レーブ（Ｇ．Ｒｅｅｂ）は、多様体から位
相商空間として得られるグラフを提唱した。レーブグラ
フは特異点の相互関係を示すもので、物体表面を等高線
で表し、各等高線の連結成分をひとつの点として表すこ
とで得られる。レーブは、多様体（コンパクトとする）
において、モース関数の下で同じ値をもち、かつ対応す
る断面として同じ連結成分に含まれるすべての点をアイ
デンティファイすることにより、このグラフを導出し
た。つまり、２つの臨界点を含む平面間に存在する多様
体の部分の連結成分はグラフのエッジ（辺）として表現
され、各特異点はグラフの各頂点に対応する。レーブグ
ラフは物体の骨格を示すグラフということができる。

【００３９】図３（ａ）〜（ｃ）は、トーラスとそのレ
ーブグラフの関係を示す図である。図３（ａ）は、もと
のトーラス、図３（ｂ）はその断面図、図３（ｃ）はレ
ーブグラフを示している。図３（ｂ）において、同一
平面内にあって重なり合わない円の部分が、（ｃ）にお
ける２つの別々のエッジに相当する。このレーブグラフ
はアイコンとして極めて表現力に優れているため、以降
必要に応じてこのグラフをアイコン表示に用いる。

【００４０】（３）理論上の限界重要なのは、モース理論をこのように古典的な方法で用
いた場合、多様体に内在する位相的な性質を発見するこ
とができるに過ぎないことである。指数の配列だけで
は、多様体が空間に埋め込まれている状態を符号化する
ことができない。例えば、空間に埋め込まれたトーラス
に結び目があるかどうかは知ることができない。図２
（ｂ）に示すとおり、２つの異なる形状が同じ特異点に
帰着するためである。同様に図２（ｃ）に示すとおり、
連結があるかどうかもモース理論による単純な符号化で
は示せない。

【００４１】（４）モース理論に基づく符号化の拡張ここでは、議論の対象をＣ^２級（三次元空間に埋め込ま
れたＣ^２）のコンパクトな二次元多様体の表面に限る。
本システムが用いる曲面上のモース関数は、空間におけ
る高さ関数から誘導する。事実、Ｃ^２曲面をわずかに回
転させれば臨界点の縮退をなくすことができるため、そ
の高さ関数をモース関数にすることができる。

【００４２】モース理論によれば、２つの臨界レベル
（臨界点が含まれる平面の高さ）の間では断面の位相は
変化しない。このことから、曲り具合の異なる多くの円
筒を用いて、２つの臨界レベルの間の曲面をモデル化す
ることができる。この事実を利用してシステムを構築す
る。特異点のない断面は平面に埋め込まれた円から構成
されるため、輪郭線どうしの包含関係を表示するために
構造的な符号化が必要となる。すなわち同じ円に含まれ
る複数の円をグループ化する符号化である。

【００４３】本システムは、レーブグラフから得られる
情報（すなわち各頂点間の接続状態）の他に、モースの
指数に新たな情報を付け加える拡張符号化を提案する。
すなわちこの情報は、２つの連続する臨界値の間で複数
の円筒がどのように交換され、どのような向きに接続さ
れるかに関する情報である。

【００４４】（５）符号化システムの例符号化システムの概要を説明する。このシステムでは、
曲面に対してｋ次元セルを次々につないでいくことによ
り曲面を表現する。そして各断面における輪郭線の階層
構造を追跡する。ここで、セルの接続を示す演算子を導
入し、これらの演算子を用いて曲面を符号化する。演算
子によって接続されていくセルをアイコンで表現するこ
とにより、符号化の対象となる曲面の構造の理解を容易
にする。この符号化システムの最大の特徴は、得られる
符号化の結果が位相の正しさを保証することにある。

【００４５】◎親子関係と輪郭線輪郭線の階層構造の表現方法を説明する。ここでは木構
造を用いる。まず、ある輪郭線が別の輪郭線を包含する
とき、前者を後者の親輪郭線、後者を前者の子輪郭線と
呼ぶ。図４（ａ）と（ｂ）は輪郭線の親子関係、および
その木構造による表現を示す図である。図４（ａ）のご
とく、親子関係はネスティング構造にすることができ
る。以下、輪郭線の一番目を♯１で示す。♯１は♯２の
親輪郭線、♯２は♯４の親輪郭線である。♯１や♯７の
ように親輪郭線をもたない輪郭線は「仮想輪郭線♯０」
の子輪郭線と表現する。したがって、♯０は木構造の頂
点にくる。

【００４６】ある輪郭線の親を示すために、配列Ｐａｒ
ｅｎｔ♯［］を定義する。たとえばＰａｒｅｎｔ♯
［１］＝０である。一方、ある輪郭線の子輪郭線はＣｈ
ｉｌｄｒｅｎという配列にリストされ、その配列へのポ
インタが付される。例えば♯３の子輪郭線である♯５お
よび♯６は、以下のように記述される。Ｃｈｉｌｄｒｅ
ｎ［３］↑［１］＝５、Ｃｈｉｌｄｒｅｎ［３］↑
［２］＝６同じ親輪郭線をもつ輪郭線同士は兄弟輪郭線
と呼ばれる。図４（ａ）の場合、♯２と♯３が兄弟輪郭
線である。親輪郭線の親は祖父輪郭線、子輪郭線の子は
孫輪郭線と呼ばれる。また、内部に物体が存在する輪郭
線を中実輪郭線、存在しない輪郭線を中空輪郭線と呼
ぶ。図４（ａ）の場合、♯１、♯４、♯５、♯６、♯７
は中実輪郭線、♯２および♯３は中空輪郭線である。

【００４７】◎セルを接続するための演算子４つの演算子、Ｐｕｔｅ０、Ｐｕｔｅ１ｍｅｒｇ
ｅ、Ｐｕｔｅ１ｄｉｖｉｄｅ、Ｐｕｔｅ２を定義
する。これらがセルを貼り付ける演算子である。以下、
ｋ次元セルをｅｋと表示する。物体の構成は頂上から谷
底に向けて進む。処理は、それ以上セルを接続すること
ができなくなった時点で終了する。演算子によって構成
しようとする曲面の状態を示すために、各断面における
輪郭線を用いる。図５は、これらの演算子を用いてトー
ラスを構成する方法を示す。以下この図を用いて演算子
の機能を説明する。

【００４８】１．同図の一番上に示すとおり、ｅ^２を生
成するためにＰｕｔｅ２（０）を実行する。このパラ
メータ「０」は♯１が♯０の内側に生成されることを示
す。このセルの断面は同図の「断面表示」の箇所に示さ
れる。図のように、Ｐｕｔｅ２は断面の平面上に輪郭線
を生成する機能をもつ。演算子によって生成される輪郭
線に生成順の数字を与えるため、Ｐｕｔｅ２（０）に
よって生成された輪郭線は♯１である。新たに生成され
た輪郭線の状態は、初期値として常に「イネーブル」で
ある。イネーブルとは、その輪郭線に対してセルを接続
することが許される状態を示す。ｅ^２のアイコン表示を
同図「アイコン」の下に示す。

【００４９】２．つづいて、Ｐｕｔｅ１ｄｉｖｉｄ
ｅ（１，ｎｉｌ，ｉｎｓｉｄｅ）により、ｅ^２に対して
ｅ^１を貼り付ける。新たに生成された輪郭線を♯２とす
る。パラメータ「ｉｎｓｉｄｅ」は♯２がＰａｒｅｎｔ
♯［１］＝０の子輪郭線として生成されることを示す。
二番目のパラメータは参照すべき子輪郭線のリストを示
す。ここでは２番目のパラメータが「ｎｉｌ」であり、
ここでは子輪郭線に対する操作、具体的には子輪郭線の
削除はない。

【００５０】３．つぎに、Ｐｕｔｅ１ｍｅｒｇｅ
（１，２）を用いて別のｅ^１を貼り付け、♯１と♯２を
マージする。この演算子は、１番目、２番目のパラメー
タによって示される輪郭線を１番目のパラメータの側に
マージする。マージによって２番目のパラメータの示す
輪郭線は消滅するため、それがその親輪郭線のもつ子輪
郭線のリストから削除される。同時に、その輪郭線の状
態が「イネーブル」から「ディセーブル」に変更され
る。したがって、この輪郭線に新たにセルを接続するこ
とができない。

【００５１】４．最後にＰｕｔｅ０（１）を用いてｅ
^０を貼り付け、♯１を閉じる。♯１の状態はイネーブル
からディセーブルに変更される。アイコンがこの変更を
反映している。ある輪郭線にセルｅ^０が接続されたと
き、その輪郭線のもつすべての子輪郭線が予めディセー
ブルされていなければならない。以上の手順により、イ
ネーブルの状態で残っている輪郭線がなくなるため、演
算子によるセルの貼り付けは完了する。

【００５２】図６〜８は疑似パスカルコードによって演
算子のプログラミング例を示す図である。図において、
ＭａｘｃｈｉｌｄｒｅｎとＭａｘｃｏｎｔｏｕｒ
ｎｕｍｂｅｒは十分大きな正の整数であり、メモリーア
ロケーションのためだけに用いられる。図６において、
Ｎｕｍｂｅｒｏｆｃｈｉｌｄｒｅｎは各輪郭線の子
輪郭線の数、Ｍｏｓｔｒｅｃｅｎｔｌｙｃｒｅａｔ
ｅｄ♯は、最も最近生成された輪郭線の番号、Ｃｏｎｔ
ｏｕｒｓｔａｔｕｓは、各輪郭線がイネーブルである
かディセーブルであるかを示す。Ｃｈｉｌｄｒｅｎはあ
る輪郭線の子輪郭線のリストを保持するＣｈｉｌｄｌ
ｉｓｔという配列に対するポインタである。Ｃｈｉｌｄ
ｌｉｓｔの終了は定数Ｅｎｄｏｆｌｉｓｔによっ
て示される。これらの変数は以下の手順で初期化され
る。ｍｏｓｔｒｅｃｅｎｔｌｙｃｒｅａｔｅｄ♯：＝０；ｆｏｒｉ：＝０ｔｏｍａｘｃｏｎｔｏｕｒ₋ｎｕｍｂｅｒｄｏｎｕｍｂｅｒｏｆｃｈｉｌｄｒｅｎ［ｉ］：＝０；ｆｏｒｉ：＝１ｔｏｍａｘｃｎｔｏｕｒｎｕｍｂｅｒｄｏｃｏｎｔｏｕｒｓｔａｔｕｓ［ｉ］：＝ｄｉｓａｂｌｅｄ；ｃｏｎｔｏｕｒｓｔａｔｕｓ［０］：＝ｅｎａｂｌｅｄ：これにより、仮想輪郭線がイネーブルされる。つぎのｃ
ｒｅａｔｅｎｅｗｃｏｎｔｏｕｒは新しい輪郭線を作
り、Ｍｏｓｔｒｅｃｅｎｔｌｙｃｒｅａｔｅｄ♯を
増加させ、その状態を初期化する。

【００５３】図７において、後に使用するために２つのプロシージャ
と３つの関数を定義する。Ａｄｄｌｉｓｔｅｄｃｈ
ｉｌｄｒｅｎは第２パラメータであるｃｌｉｓｔにリス
トされている輪郭線を第１パラメータの子輪郭線（ｃｈ
ｉｌｄｒｅｎ［ｎ］↑）のリストに追加する。Ｒｅｍｏ
ｖｅｌｉｓｔｅｄｃｈｉｌｄｒｅｎは第１パラメー
タの子輪郭線（ｃｈｉｌｄｒｅｎ［ｎ］↑）のリストか
ら第２パラメータであるｃｌｉｓｔにリストされている
輪郭線を削除する。これらのプロシージャはまた、Ｎｕ
ｍｂｅｒｏｆｃｈｉｌｄｒｅｎおよびＰａｒｅｎｔ
♯の配列を更新する。

【００５４】一方、関数Ａｄｄｃｈｉｌｄｒｅｎ
（ｎ，ｃｌｉｓｔ）はｃｌｉｓｔのすべての輪郭線が♯
ｎの子輪郭線であるとき「真」を返す。それ以外の場合
「偽」を返す。関数ｉｎｌｉｓｔ（ｎ，ｃｌｉｓｔ）
はｃｌｉｓｔが♯ｎを含むとき「真」を返し、それ以外
の場合「偽」を返す。関数Ｌｉｓｔｃｏｎｔａｉｎｉ
ｎｇｏｎｌｙ（ｎ）は２つプロシージャ、Ａｄｄｌ
ｉｓｔｅｄｃｈｉｌｄｒｅｎおよびＲｅｍｏｖｅＬ
ｉｓｔｅｄｃｈｉｌｄｒｅｎに対して与えるべき輪郭
線を１つだけ含むリストを作るために定義される。

【００５５】これらにより、４つの演算子Ｐｕｔｅ
２、Ｐｕｔｅ０、Ｐｕｔｅ１ｄｉｖｉｄｅおよび
Ｐｕｔｅ１ｍｅｒｇｅを定義することができる。こ
れらは図８に示される。１．Ｐｕｔｅ２（ｎ）は♯ｎの子輪郭線として新たな
輪郭線を生成する。２．Ｐｕｔｅ０（ｎ）はｅ^０を貼り付けることによ
り、♯ｎを削除する。ここで、Ａｌｌｓｕｃｃｅｓｓ
ｏｒｓｄｉｓａｂｌｅｄ（ｎ，ｃｏｎｔｏｕｒｎｕｍ
ｂｅｒ）は、♯ｎのすべての子輪郭線がディセーブルで
あるときに限り「真」を返す。

【００５６】３．Ｐｕｔｅ１ｄｉｖｉｄｅ（ｎ，ｃ
ｌｉｓｔ，ｉｎｓｉｄｅ）は、♯ｎを分割して新たな輪
郭線を作る。Ｃｌｉｓｔにリストされている輪郭線は新
たに生成される輪郭線の子輪郭線になる。それらは、♯
ｒ＝♯ｎまたは♯ｒ＝ｐａｒｅｎｔ♯［ｎ］の一方が成
り立つとき、♯ｒの子輪郭線のリストから削除される。
（これは♯ｎまたはｐａｒｅｎｔ♯［ｎ］のいずれの子
輪郭線であったかに依存する）。これら２つの場合のみ
が許される。

【００５７】４．Ｐｕｔｅ１ｍｅｒｇｅ（ｃ１，ｃ
２）は♯ｃ２を♯ｃ１にマージする。♯ｃ２はＰａｒｅ
ｎｔ♯［ｃ２］の子輪郭線のリストから削除される。♯
ｃ２のすべての子輪郭線はＰａｒｅｎｔ♯［ｃ１］また
は♯ｃ１の子輪郭線になる（そのいずれであるかは、♯
ｃ１が♯ｃ２の親輪郭線であるか兄弟輪郭線であるかに
依存する）。これら２つの場合のみが許される。

【００５８】これらの演算子によって符号化される曲面
の構造を容易に理解するために、曲面のレーブグラフを
構成するセルの視覚的表示を提案する。図９に示すアイ
コンはそれぞれセルを表している。セルの貼り合わせ
は、一方のセルの平らな頂面と他方のセルの平らな底面
を接触させることによって行われる。中空輪郭線には白
いアイコン、中実輪郭線には黒いアイコンを用いる。ｅ
^１に関しては複数のアイコンが存在する。

【００５９】図１０はセルの貼り合わせを示す図であ
り、同図に示すごとく子輪郭線のアイコンはその親輪郭
線のアイコンの内側に描かれる。鉛直な軸に関する鏡像
のアイコンも認められる。アイコンの特徴は、それが貼
り付けられる輪郭線の構造を維持する点にある。例えば
図１０の上半分に示されるように、ｅ^１がセルに接続さ
れるとき、アイコンが接続されることになるセルの親子
関係の構造が維持される。

【００６０】図１０の下半分に示すように、セルの高さ
の調整が必要な場合にはダミーアイコンを挿入する。レ
ーブグラフは平面グラフではないため、ダミーアイコン
を用いてセルを交差させることもできる。この結果、ｅ
^１を離れたセルに接続することが可能となる。ｅ^１がセ
ルを交換するとき、同時にその内部構造も交換する。階
層的な輪郭線の構造を保持するために、ダミーアイコン
はそれが貼り付けられる輪郭線の親輪郭線の境界を越え
ることはできないし、他の輪郭線に侵入することもでき
ない。この理由から、ダミーアイコンを用いて交換する
ことのできる輪郭線は兄弟輪郭線に限られる。

【００６１】以上のまとめとして、図１１〜１３に演算
子を用いた物体の符号化の例を示す。図１１は、対象と
なる物体のレーブグラフをアイコンによって示したも
の、図１２はその物体の断面の輪郭線を示したもの、図
１３はその物体を構成するための演算子である。

【００６２】［２］演算子を用いた符号からの曲面の構
成（１）ホモトピーの軌跡としての曲面の生成前述の方法によって得られた符号化データをもとに物体
の曲面を構成する。すでに述べたとおり、臨界点を含む
断面どうしの間では輪郭線の位相は変化しない。頂点か
ら底辺まで走査したとき、輪郭線の形状は変化する。こ
の輪郭線の変形はホモトピーを用いてうまく表現するこ
とができる。ホモトピーはある関数を他の関数に変換す
る。以下の説明においては、すべての輪郭線は形状関数
によって表され、変形はホモトピーによって表されると
する。ホモトピーの定義は以下のとおりである。

【００６３】〔定義〕Ｘ、Ｙが位相空間であるとき、
ｆ、ｇ：Ｘ→Ｙという写像を考える。ここで、ｘ∈Ｘな
るすべての点ｘに対して、Ｆ（ｘ，０）＝ｆ（ｘ）Ｆ（ｘ，１）＝ｇ（ｘ）が成り立つような写像Ｆ：Ｘ×Ｉ→Ｙが存在する場合、
「ｆとｇはホモトープである」といわれる。ここでＩ＝
［０，１］∈Ｒである。またこのとき、写像Ｆは「ｆか
らｇへのホモトピー」と呼ばれる。Ｆが、Ｆ（ｘ，ｔ）＝（１−ｔ）ｆ（ｘ）＋ｔｇ（ｘ）で定義されるとき、これは直線ホモトピーと呼ばれる。
図１４には輪郭線のホモトピー変形が示されている。こ
の図において、一番上の輪郭線が形状関数ｆ、一方いち
ばん下の輪郭線はｇによって表されている。曲面はｆか
らｇへのホモトピーＦの軌跡として生成される。

【００６４】（２）演算子をインプリメントするための
要素図１４の曲面を生成するための演算子は、ホモトピーに
よって輪郭線を変形するものとして記述することができ
る。

【００６５】１．演算子を構成する要素図１５には、演算子を構成する以下の主な４つの要素が
描かれている。（ｉ）ｆ：Ｉ→Ｒ^３上の輪郭線の形状を与える（ｉｉ）ｇ：Ｉ→Ｒ^３下の輪郭線の形状を与える（ｉｉｉ）Ｆ：ｆからｇへのホモトピー（ｉｖ）ｈ：２つの輪郭線の高さの差２．形状関数ｆ、ｇとして以下の形状関数を準備する。（ｉ）点：常に固定点の位置を与える定数関数（ｉｉ）円：円の形状を与える（ｉｉｉ）多角形：任意の頂点を結ぶ多角形の形状を与
える（ｉｖ）ベジェ：ｎ次元のベジェ曲線で、次式で記述
される。

【００６６】

【数３】

【００６７】この関数は制御点Ｐｉ∈Ｒ^３と呼ばれるｎ
個の点の集合（順序つき）によって特定される。この制
御点はユーザーによって修正することができる。ここ
で、Ｂｎｉ（ｔ）はベルンシュタインの基底関数であ
り、次式で定義される。

【００６８】

【数４】

【００６９】（ｖ）ＮＵＲＢＳ（ＮｏｎＵｎｉｆｏｒ
ｍＲａｔｉｏｎａｌＢ−Ｓｐｌｉｎｅ）曲線：この
曲線の制御点もユーザーによって定義される。ＮＵＲＢ
Ｓ曲線は次の式で定義される。

【００７０】

【数５】

【００７１】ここでＷｉは各制御点の重みである。Ｎ
ｉ，ｋ（ｔ）はＢスプライン基底関数と呼ばれる（ｋ−
１）次の多項式の各区分の値を示す。これは次式で定義
される。

【００７２】

【数６】

【００７３】ＮＵＲＢＳは、非常に多くのＣＡＤシステ
ムで用いられている。ＮＵＲＢＳは二次曲面を正確に表
現することができ、また局所的な近似特性をもってい
る。すなわち、制御点またはそれに関連する重みが変化
したとき、その点の近傍でしか曲面の形状に影響を与え
ないため、局所変形操作に向く。

【００７４】３．ホモトピーＦ一方、ホモトピーＦとして以下の関数が導入される。こ
れらの関数は断面の輪郭線を出力する。（ｉ）線形：直線ホモトピー（ｉｉ）四分円形：

【００７５】

【数７】

【００７６】（ｉｉｉ）放物線：Ｆ（ｘ，ｔ）＝（１−
ｔ^２）ｆ（ｘ）＋ｔ^２ｇ（ｘ）（ｉｖ）カージナルスプライン：カージナルスプライ
ンは、一番上および一番下の輪郭線を内挿補間する。輪
郭線間の対応点を示す既知のトロイダルグラフを使うこ
とによってパラメータの決定を自動化することができ
る。

【００７７】（ｖ）ガイディングカーブ：輪郭線上の点
をガイディングカーブに沿って動かすことにより、輪郭
線を変形することができる。輪郭線に対して複数のガイ
ディングカーブを付けることができる。輪郭線がベジェ
曲線またはＮＵＲＢＳ曲線で表されるとき、ガイディン
グカーブは制御点に付けられ、変形は制御点の動きによ
って決定される。ガイディングカーブが付けられていな
い制御点の動きは、隣接する制御点のガイディングカー
ブを用いて計算することができる。

【００７８】図１６は、ユーザーがガイディングカーブ
を付けることにより、上の輪郭線が徐々に下の輪郭線に
変形される様子を示している。いずれの場合も、結果的
に得られた輪郭線の間をカージナルスプラインを用いて
パッチを当て、曲面を生成することができる。

【００７９】４．演算子のための輪郭線の形状関数演算子のための輪郭線の形状関数は以下のように与えら
れる。（ｉ）Ｐｕｔ₋ｅ２ｆ：点ｇ：ユーザーが特定（デフォルト：円）Ｆ：ユーザーが特定（デフォルト：四分円形）（ｉｉ）Ｐｕｔ₋ｅ０ｆ：ｅ^０が付けられる輪郭線の形状関数ｇ：点Ｆ：ユーザーが指定（デフォルト：四分円形）（ｉｉｉ）Ｐｕｔ₋ｅｌ₋ｄｉｖｉｄｅ、Ｐｕｔ₋ｅｌ
₋ｍｅｒｇｅｅ^１の道ｃ：［０，１］→Ｒ^３を決めなければならな
い。実際にインプリメントする場合、道ｃはｃ（０）、
ｃ（１／２）およびｃ（１）の位置によって特定され
る。道は滑らかでなければならず、またｃ（１／２）に
おける接線のベクトルはｘｙ平面に平行でなければなら
ない。したがって、ｃ（１／２）は生成された曲面の鞍
点になる。ｃ（１／２）の初期位置は、

【００８０】

【数８】

【００８１】である。ここで、

【００８２】

【数９】

【００８３】である。道の初期値はｃ（０）とｃ（１）
を接続する楕円の弧であり、０≦ｔ≦１／２について
は、

【００８４】

【数１０】

【００８５】で与えられ、一方、１／２≦ｔ≦１につい
ては、

【００８６】

【数１１】

【００８７】で与えられる。この道の初期値のｘｙ平面
への射影は、ｃ（０）およびｃ（１）を結ぶ線分にな
る。このｃ（ｔ）の式において、ルート（１／２乗）の
部分を（１−ｘ^２）に置き換えれば放物線の道を得るこ
ともできる。Ｐｕｔ₋ｅｌ₋ｄｉｖｉｄｅおよびＰｕｔ
₋ｅ１₋ｍｅｒｇｅの要素は以下のとおりである。・Ｐｕｔ₋ｅｌ₋ｄｉｖｉｄｅｆ：ｅ^１が付けられる輪郭線の形状関数ｃ．ｅｃ（０）、ｃ（１）：ｃ（０）＝ｆ（ｓ_１），ｃ（１）＝ｆ（ｓ_２）なる
ｓ_１、ｓ_２∈［０，１］で特定されるｇ_１、ｇ_２：輪郭線を道ｃに沿って分割することにより
得られる・Ｐｕｔ₋ｅｌ₋ｍｅｒｇｅｃ：ｅ^１の道ｆ_１、ｆ_２：ｅ^１が付けられる輪郭線の形状関数ｃ（０）、ｃ（１）：ｃ（０）＝ｆ_１（ｓ_１），ｃ（１）＝ｆ_２（ｓ_２）なる
ｓ_１、ｓ_２∈［０，１］で特定されるｇ：道ｃに沿って輪郭線をマージすることにより得られ
るＰｕｔ₋ｅｌ₋ｄｉｖｉｄｅによる変形は、ｅ^１の道を
ガイディングカーブとして用いることにより、輪郭線を
変形することで行われる。すなわち、・Ｆ（ｓ_１，ｔ）＝ｃ（ｔ／２）・Ｆ（ｓ_２，ｔ）＝ｃ（１−ｔ／２）である。一方、Ｐｕｔ₋ｅｌ₋ｍｅｒｇｅの変形は次式
によって得られる。

【００８８】・Ｆ_１（ｓ_１，ｔ）＝ｃ（ｔ／２）・Ｆ_２（ｓ_２，ｔ）＝ｃ（１−ｔ／２）以上が前提技術である。この前提技術を本発明との関連
を中心にまとめれば以下のとおりである。

【００８９】［１］についてモース理論によれば、特異点と指数の情報をもとに、多
様体であるもとのオブジェクトと同じホモトピータイプ
の位相空間を胞体（セル）によって構築することができ
る。数学的な厳密さを無視していえば、モース理論によ
って、もとのオブジェクトの三次元形状をきわめて少な
い特異点関連情報、ここでは特異点とその指数、および
特異点の並び方から概念的に再現することができる。し
かし、モース理論ではセルを具体的にどのように接続し
ていくか、つまりセルの連結成分まではわからない。

【００９０】レーブグラフはそうしたモース理論の問題
点の解消に役立つ。レーブグラフはまさにセルの連結成
分を示すものであり、特異点間、すなわちノード間の接
続関係がエッジ、つまりグラフの辺からわかる。モース
理論とレーブグラフを組み合わせることにより、オブジ
ェクトの三次元形状が判明する。より具体的には、オブ
ジェクトの形状を示す既存のポリゴンデータを取得し、
そのデータに対して設定されたモース関数の特異点に関
連する情報を抽出し、特異点間の接続情報を取得する。
原則としてそれだけの情報でもとのオブジェクトの形状
を捉えることができる。この捉え方は、オブジェクトに
一意的に曲面パッチが貼れるよう最も効率的にオブジェ
クトの表面を分割することのできる捉え方である。

【００９１】ここで注意すべきは、モース理論とレーブ
グラフで再現できるのが主にオブジェクトの構造または
骨格である点である。したがって、より正確な形状は付
加的な形状情報または外形情報に頼ることになる。本発
明ではそのためにオブジェクトの輪郭線情報を取得す
る。

【００９２】［２］について［１］によってオブジェクトの骨格が記述された後、オ
ブジェクトに曲面を貼る方法を示している。［１］では
ホモトピータイプという概念が現れたが、［２］では関
数のホモトピーという概念が登場する。本発明では、も
とのポリゴンデータが表現する曲面をホモトピーによっ
てより滑らかに、より少ないデータで表現する。

【００９３】［１］［２］によれば、臨界断面の間をホ
モトピーによって連続変形すればオブジェクトに曲面を
貼ることができる。臨界断面の間で輪郭線の位相が変化
することはなく、ホモトピーによる表現に向く。その一
方、臨界断面を横切れば輪郭線の位相が変化するため、
それまでとは別のホモトピーで曲面を表現する。つま
り、ホモトピーのような連続関数で表すことのできる必
要十分な数の分割を実現する断面が臨界断面である。

【００９４】従来よりＣＡＤのサーフェスモデルではス
キニング（ｓｋｉｎｉｎｇ）と呼ばれる手法がある。こ
の手法は、例えば飛行機の翼のようなオブジェクトを設
計するとき、まずそのリブの形状をいくつか指定する。
その後、リブの輪郭線間に曲面を貼り付けてオブジェク
トの表面を生成する。しかしこの手法では、例えばオブ
ジェクトに分岐があるときには対応できない。位相幾何
学的考察に基づかないためである。

【００９５】本発明では臨界断面はレーブグラフのノー
ドに対応する。臨界断面の間はエッジに相当する。した
がって、臨界断面間にホモトピーで曲面を貼ることは、
レーブグラフのエッジごとにその周りに円筒と同相の曲
面を貼ることに等しい。オブジェクトをレーブグラフで
表現しておけば、ノード間は必ずひとつの円筒と同相の
曲面が貼れる。円筒と同相の曲面は複数の四辺形領域に
分割できるため、ノード間は必ず複数の四辺形の曲面パ
ッチに分割できる。このことは、［１］［２］の理論に
より、どのようなオブジェクトにも恒常的かつ効率的に
曲面パッチが貼れることを意味し、複雑なオブジェクト
の自由曲面による容易かつ確実な表現という従来の課題
を解決する。この結果、ポリゴンデータという線形的な
表現を位相幾何学的データという非線形的な表現へ自動
変換する途が開ける。

【００９６】［実施の形態］図１７は本発明に係る構造
グラフ生成方法の処理手順を示すフローチャートであ
る。この図により、まず処理の概略を説明する。前提技
術では、設計者が自らレーブグラフを生成していった
が、本実施の形態では既存のポリゴンデータからレーブ
グラフを自動生成する。同図のごとく、オブジェクトの
形状を示すポリゴンデータを取得した後、まずオブジェ
クトの位相情報を抽出する（Ｓ１）。この位相情報はオ
ブジェクトの大域的（ｇｌｏｂａｌ）な構造を特徴づけ
るもので、単に、あるポリゴンの隣はどのポリゴンかと
いった局所的（ｌｏｃａｌ）な位相情報ではない。いず
れの場合もトポロジーと訳されることがあるが、前者は
主に数学で用いられることば、後者は主にＣＡＤについ
て用いられることばである。

【００９７】つづいて、この大域的な位相情報に基づ
き、オブジェクトの骨格グラフが生成される（Ｓ２）。
前提技術ではレーブグラフを用いたが、ここでは必ずし
もレーブグラフでなくともよい。例えばトーラスを単に
円で表現するごとく、オブジェクトの構造を単純化、符
号化、象徴化などするグラフであればよい。グラフは通
常ノードとエッジで構成されるが、トーラスを円で表現
する場合、この円にはノードがないともいえる。そうし
た場合、仮想的なノードを想定してグラフと呼ぶことに
決める。また、骨格グラフを生成するといっても、必ず
しもグラフの可視化は必要でない。したがって、骨格グ
ラフを生成するに足る情報を収集すればよいと決める。
これらふたつの規則は本明細書を通して有効とする。

【００９８】以上の処理により、オブジェクトの骨格グ
ラフがポリゴンデータから生成される。図１７の処理に
より、オブジェクトの形状データにオブジェクトの大域
構造情報が与えられる。図１８は図１７の処理を実現す
る構造グラフ生成装置１の構成図である。装置１は、ポ
リゴンデータを取得するデータ入力部２をもつ。データ
入力部２は、ネットワークからポリゴンデータを受信す
る通信部でもよいし、記憶装置からポリゴンデータを読
み出す記憶制御部でもよい。また、オブジェクトを撮影
してその曲面をポリゴン化する三次元ディジタイザな
ど、オブジェクトの座標を取得する装置でもよい。装置
１はさらに、取得されたポリゴンデータに対してモース
関数を定めるモース関数決定部３と、そのモース関数の
特異点を検出する特異点検出部４と、特異点どうしの接
続情報を取得する特異点接続情報取得部５を含む。

【００９９】図１９は装置１の動作を示すフローチャー
トである。まず、データ入力部２がオブジェクトのポリ
ゴンデータを入力する（Ｓ１０）。このポリゴンデータ
はモース関数決定部３に渡される。モース関数として高
さ関数を用いる。したがって、モース関数を決定するこ
とは高さ方向を決めることに還元される。高さ方向の決
め方の例は以下のとおりである。

【０１００】ｉ）ポリゴンデータ自身が有するｚ方向
（高さ方向）をそのままモース関数の高さ方向とする。ｉｉ）オブジェクトの形状に応じて決める。例えば、オ
ブジェクトの高さ方向の長さが最長になるように決め
る。ｉｉｉ）オブジェクトの位相幾何学的な特徴に応じて決
める。例えば、特異点がある程度多くとれるように決め
る。ｉｖ）ユーザの指示に従う。

【０１０１】モース関数決定部３では、これらのまたは
その他の方法のいずれかに基づき、モース関数を決定す
る（Ｓ１１）。なお、高さ関数以外のモース関数の例と
して、オブジェクト表面の曲率を採用してもよい。その
場合、ｚ軸の方向によらないという利点がある。

【０１０２】つづいて、処理は特異点検出部４に移る。
通常の滑らかな曲面からなるオブジェクトの場合、前提
技術で説明したごとく、オブジェクトを高さ方向にサー
チしていくことで特異点とその指数が判明する。しか
し、ここでは対象が微分不可能な頂点を含むポリゴンデ
ータであるから、特異点に新たな定義が要る。指数に応
じ、特異点を以下のように定義する。なお、あるポリゴ
ンのある頂点Ｖに集まる辺を時計回りに（または反時計
回りに）Ｅｉ（ｉ＝１、２、・・・ｎ）と表記し、Ｖか
ら見て辺Ｅｉが上昇線（ａｓｃｅｎｄｉｎｇｌｉｎ
ｅ）であるときその辺を「＋」、下降線（ｄｅｓｃｅｎ
ｄｉｎｇｌｉｎｅ）のとき「−」と表記する。

【０１０３】１．指数０（谷底点：ｐｉｔ）図２０に示すごとく、Ｅｉがすべて「＋」であるとき、
Ｖは指数０の特異点である。２．指数１（鞍点：ｓａｄｄｌｅ）図２１に示すごとく、ｎ＝４の場合、Ｅ１〜４が「＋−
＋−」または「−＋−＋」という順序ならＶは指数１の
特異点である。一般には、Ｅｌ〜Ｅｓ、Ｅｓ＋１〜Ｅ
ｔ、Ｅｔ＋１〜Ｅｕ、Ｅｕ＋１〜Ｅｎの４つの群が群単
位で「＋−＋−」か「−＋−＋」の順序であればよい。
ただし、ｓ≧１、ｔ≧ｓ＋１、ｕ≧ｔ＋１、ｎ≧ｕ＋１
である。３．指数２（頂点：ｐｅａｋ）図２２に示すごとく、Ｅｉがすべて「−」であるとき、
Ｖは指数２の特異点である。

【０１０４】特異点検出部４はこれらの定義に従い、ポ
リゴンデータの座標から特異点の座標とその指数を検出
する（Ｓ１２）。特異点の座標は特異点に関する幾何情
報の一種である。

【０１０５】指数０と指数２の特異点付近の断面形状は
それぞれ円（と同相の図形）に決まるが、指数１の特異
点は図２３のようにふたつの輪郭線が外接する点Ｎ１に
生じる場合と、図２４のようにひとつの輪郭線の中に他
の輪郭線があり、それらが接する点Ｎ２に生じる場合が
ある。点Ｎ１は、傾斜の「＋」「−」を考慮すれば、図
３（ａ）に示したトーラスに関するふたつの鞍点のうち
上にあるほうに相当する。点Ｎ２は、図２５のように斜
めに切った中空円筒の内壁上端Ｎ３に現れる。この実施
の形態でも、前提技術同様オブジェクトの内部構造まで
記述できるアイコン表示のレーブグラフを作ることがで
きる。その際、点Ｎ１の場合はふたつの輪郭線が「兄
弟」、Ｎ２では「親子」であり、処理が異なる。そのた
め、ここで予めいずれの形状であるか調べておく。アル
ゴリズムとしては、指数１の特異点が見つかったとき、
その点を含む断面の輪郭線の形を調べ、図２３、図２４
のいずれのパターンに当てはまるか調べればよい。

【０１０６】つぎに、特異点接続情報取得部５で特異点
どうし接続関係を把握する（Ｓ１３）。これは特異点に
関する位相情報である。図２６、図２７はそれぞれ、
「ふたつの独立したトーラス」からなるオブジェクト
（図２（ａ））、および「一回ひねったトーラス」（図
２（ｂ））に対応するレーブグラフである。これらのオ
ブジェクトは特異点とその指数が全く同じであるにも拘
らず、レーブグラフが異なる。このため特異点接続情報
取得部５は、ポリゴンの辺を辿ることによって接続情報
を得る。「ふたつトーラス」の場合、特異点Ｎ１とＮ
２、Ｎ２とＮ３を結ぶポリゴンの辺があるが、Ｎ２とＮ
７を結ぶものはない。「ひねったトーラス」の場合はＮ
２とＮ７を結ぶ辺が存在する。この方法を繰り返すこと
で特異点どうしの接続関係がすべて判明するため、レー
ブグラフが完成する。図２６、２７の場合、レーブグラ
フは特異点とその指数、および特異点間の接続情報で記
述されるが、オブジェクトの内部構造も考慮してレーブ
グラフを生成する場合、図５〜１３に示した演算子やそ
のアイコン表現でそれが記述される。

【０１０７】図２８は本発明のデータ変換方法の原理を
示すフローチャートである。ポリゴンデータを取得した
後、まずオブジェクトの位相情報を抽出する（Ｓ２
０）。この処理は図１７のＳ１と同様である。つづい
て、これらの情報を位相幾何学的データへ変換する（Ｓ
２１）。Ｓ２０とＳ２１の処理をコンピュータで読み取
り可能な記録媒体に記録して頒布等してもよい。

【０１０８】図２９はデータ変換の原理を別の表現で示
すフローチャートである。ポリゴンデータを取得した
後、そのデータを用いてまずオブジェクトの位相構造に
注目し（Ｓ３０）、その結果得られた情報をもとにポリ
ゴンデータを曲面データへ変換する（Ｓ３１）。この場
合もＳ３０とＳ３１の処理を記録媒体に記録することが
できる。

【０１０９】図３０はこれらのフローチャートに基づく
データ変換を行うデータ変換器２０を内蔵するデータ編
集装置１０の構成図である。装置１０は、データ変換器
２０の他に、変換したデータを確認するためデータを可
視化するレンダリング部３０と、可視化されたデータを
表示装置４３に出力するための制御を行う表示制御部４
０を含む。これらの構成はソフトウエアのモジュールで
実現してもよいし、ハードウエア回路などで実現しても
よい。

【０１１０】データ変換器２０は、ポリゴンデータ記憶
部４１から必要なオブジェクトのポリゴンデータを入力
するデータ入力部２１と、ポリゴンデータからオブジェ
クトの骨格グラフを生成する構造グラフ生成部２２と、
オブジェクトを適切な位置で切断する断面生成部２３
と、断面の輪郭線を滑らかにする輪郭線円滑化部２４
と、断面の輪郭線に関する情報を取得してこれを骨格グ
ラフに付加する輪郭線情報取得部２５を含む。構造グラ
フ生成部２２として、ここでは図１８に示した装置１を
そのまま利用する。

【０１１１】図３１は装置１０によってデータが変換さ
れる手順を示すフローチャートである。データ入力部２
１により、オブジェクトのポリゴンデータが入力され、
構造グラフ生成部２２で既述の方法によって骨格グラフ
が生成される（Ｓ４０）。つづいて、断面生成部２３が
オブジェクトを切断する（Ｓ４１）。切断は前提技術で
述べたごとく特異点を含む高さでｚ軸に垂直に行う。

【０１１２】図３２は概略ハート型のオブジェクトのポ
リゴンデータを可視化して示す図である。同図で点Ｎ１
とＮ２は頂点、Ｎ３は鞍点、Ｎ４は谷底点である。これ
らのうち、Ｎ３以外の点における断面は点であるから、
理論上はＮ３における断面の形状のみを知る必要があ
る。しかし位相幾何学データによる形状表現の精度を高
めるため、ここでは特異点以外の高さ、具体的にはＮ１
とＮ３の間の高さｚ＝ｚ１３およびＮ３とＮ４の間の高
さｚ＝ｚ３４に一箇所ずつ断面をとる。断面を追加すべ
き位置は自動判定してもよい。たとえば特異点間の距離
がある程度大きいとき、その中間に新たな断面を設ける
などの処理が考えられる。

【０１１３】図３３はこうして得られた３つの断面にお
ける輪郭線を示す図である。ここではＮ３の高さｚ＝ｚ
３における左右の輪郭線をそれぞれＣ３ａ、Ｃ３ｂと
し、ｚ＝ｚ１３における左右の輪郭線をそれぞれＣ１３
ａ、Ｃ１３ｂとし、ｚ＝ｚ３４における左右の輪郭線を
それぞれＣ３４ａ、Ｃ３４ｂとする。同図のごとく、こ
れらの輪郭線は多角形になる。輪郭線円滑化部２４はこ
れらの輪郭線に自由曲線を当てはめる。そのひとつの方
法として、、輪郭線の頂点を制御点として利用し、ＮＵ
ＲＢＳ曲線などのスプライン曲線やベジエ曲線をフィッ
ティングする（Ｓ４２）。この処理により、ポリゴンデ
ータの凹凸感がなくなる。

【０１１４】なお、ここでは断面をｚ軸と垂直にとった
が、別の実施の形態ではポリゴンの辺を含むように断面
をとる。図３４は図３３でｚ＝ｚ１３の左に存在する輪
郭線Ｃ１３ａ付近のポリゴンを拡大した図である。仮に
ｚ軸と垂直な断面が同図の破線５０のごとくポリゴンの
中を通る場合、これを同図の太線５２のごとくポリゴン
の辺Ｌ１、Ｌ２を通るような位置に修正する。この措置
により、輪郭線の頂点がポリゴンの頂点に一致し、計算
に好都合である。断面は必ずしもある一平面に乗ってい
なくともよく、できるだけ多くの辺を含むようにとって
もよい。

【０１１５】つづいて、輪郭線情報取得部２５により、
輪郭線に関する位相情報と幾何情報を取得する（Ｓ４
３、Ｓ４４）。輪郭線の位相情報には、輪郭線の包含関
係と対応関係がある。前者についてはすでに構造グラフ
生成部２２に内蔵される特異点検出部４（図１８）で取
得しており、ここではそれを流用する。後者について
は、例えば図３３においてｚ＝ｚ１３における輪郭線Ｃ
１３ａとｚ＝ｚ３における輪郭線Ｃ３ａ、Ｃ３ｂのいず
れが対応しあうか知る必要がある。特異点接続情報取得
部５では特異点どうしの接続関係は判明するが、輪郭線
どうしの接続関係は判明しない。そこで、今回は特異点
からではなく、ある輪郭線からポリゴンの辺を辿って別
の輪郭線に到達する経路を見つける。図３２および図３
３の場合、ｚ＝ｚ１３において左にあった輪郭線Ｃ１３
ａから出る辺はｚ＝ｚ３においても左にある輪郭線Ｃ３
ａに到達する。この方法により、（Ｃ１３ａ，Ｃ３ａ，
Ｃ３４）および（Ｃ１３ｂ，Ｃ３ｂ，Ｃ３４）という対
応関係がわかる。

【０１１６】一方、輪郭線の幾何情報には、輪郭線の形
状情報と輪郭線間の対応点の位置情報がある。前者は輪
郭線円滑化部２４で輪郭線の近似式である自由曲線式が
得られているため、これを流用する。後者は例えば以下
の方法で取得される。

【０１１７】ｉ）ポリゴンの辺を利用する。例えば図３
５のように、輪郭線Ｃｓ上の点Ｑｓからポリゴンの辺を
辿る経路のうち、輪郭線Ｃｔまでの距離が最短の経路６
０を選択すると点Ｑｔに到達する場合、ＱｓとＱｔを対
応点とし、それらの座標を取得する。ｉｉ）輪郭線どうしの距離を利用する。輪郭線ＣｓとＣ
ｔ上にそれぞれ複数の点を設け、それらのうち互いに最
も近いものどうしを対応点として座標を取得する。ｉｉｉ）輪郭線の周上位置を利用する。図３６のごと
く、まず輪郭線ＣｓとＣｔでｘ座標が最小になる点Ｑ１
ｓ、Ｑ１ｔをそれぞれを検出する。つぎにＱ１ｓ、Ｑ１
ｔから輪郭線の周囲の１／４進んだ点をそれぞれＱ２
ｓ、Ｑ２ｔとし、同様にＱ３ｓ、Ｑ３ｔ、Ｑ４ｓ、Ｑ４
ｔを決める。その後、Ｑ１ｓとＱ１ｔ、Ｑ２ｓとＱ２
ｔ、Ｑ３ｓとＱ３ｔ、Ｑ４ｓとＱ４ｔをそれぞれ対応点
とし、座標を取得する。以上で輪郭線情報取得部２５の
処理が終わる。

【０１１８】図３７はこれまでの処理で得られた特異点
Ｎ１〜Ｎ４、レーブグラフ６２、輪郭線Ｃ１３ａ、Ｃ１
３ｂ、Ｃ３ａ、Ｃ３ｂ、Ｃ３４、および破線６４でその
一部が示される対応点間の接続情報を表す。対応点間は
それらを制御点とする自由曲線でつながれており、これ
を前提技術同様ガイディングカーブとよぶ。ガイディン
グカーブは輪郭線の対応点をつなぐ経路の形状情報を与
える。

【０１１９】図３８は以上の処理から得られた情報（以
下「基本情報」とよぶ）を構成するデータ要素を示す。
図３８のごとく、レーブグラフに含まれるノードＮ１等
はその三次元座標（ｘ１，ｙ１，ｚ１）等およびそれら
の指数ｉｎｄｅｘ１等で記述される。エッジＥ１等はそ
れが貼られるノードの組（Ｎ１，Ｎ２）等で記述され
る。輪郭線Ｃ１等はそれが関連付けられるノードＮ１等
またはそれらのｚ座標、自由曲線式Ｃｅｑ１等、および
それに対応する他の輪郭線Ｃ２の表示等で記述される。
ガイディングカーブＧ１等は、それが通過するノードＮ
１等と輪郭線上の点Ｑ１ｓ、Ｑ１ｔ等の座標で記述され
る。なお、ガイディングカーブには自由曲線を採用した
が、より簡易的には、単にポリゴンの辺をつなぐ複数線
分としてもよい。

【０１２０】図３７に示すごとく、オブジェクトの輪郭
線間の部分（臨界断面は除く）はいずれも円筒と同相で
あり、必ず曲面パッチが貼れる。したがって、この基本
情報がポリゴンデータから変換された位相幾何学的デー
タの一例である。基本情報のうちガイディングカーブ
は、それが対応点から自動生成でき、対応点は輪郭線情
報から自動生成できるから、必須ではない。また、再現
される形状の精度を問題にしなければ、少なくとも特異
点を含まない断面に関する輪郭線も不要である。データ
編集装置１０はもとのポリゴンデータから基本情報を一
意的に生成することができるため、処理の自動化に向
く。

【０１２１】基本情報を生成した後、データ変換器２０
はこれを位相幾何学的データ記憶部４２に出力する（図
３０）。これで変換処理はひととおり終了するが、変換
結果を確かめるため、データ編集装置１０にはオプショ
ナルな構成としてレンダリング部３０が設けられてい
る。

【０１２２】レンダリング部３０は、基本情報を受けて
曲面パッチを貼り付ける曲面パッチ生成部３１を含む。
曲面パッチ生成部３１は、輪郭線とガイディングカーブ
によって囲まれたそれぞれ四辺形の領域にパッチを貼る
（Ｓ４５）。可視化部３２は貼られた各パッチを既存の
手法、例えばコンスタントシェーディングや自由曲面に
直接レイトレーシングを行うなどの処理で可視化する
（Ｓ４６）。可視化されたデータは表示制御部４０を経
て表示装置４３に表示される（Ｓ４７）。もとのポリゴ
ンデータが図３２に示すようなハート型である場合、こ
こで表示されるオブジェクトは図３９のごとくより滑ら
かなものとなる。

【０１２３】このデータ編集装置１０によれば、位相幾
何学的データ記憶部４２に記憶された基本情報のデータ
量は非常に少ない。それにも拘らず、もとのポリゴンデ
ータよりも一般に滑らかなオブジェクトを再現すること
ができる。人の掌のモデリングについて実験したとこ
ろ、ＶＲＭＬによって約６０００のポリゴンの頂点を記
述した場合のデータ量が約６４０キロバイト（ｇｚｉｐ
による圧縮時は約２００キロバイト）、これをデータ編
集装置１０による位相幾何学的データで記述した場合、
約３キロバイト（ｇｚｉｐによる圧縮時は約１．５キロ
バイト）であった。他のオブジェクトについても、肉眼
でポリゴンの頂点が確認できる程度のポリゴン数におい
て、ポリゴンデータの１００分の１程度のデータ量で形
状を表現することできた。これは本発明が単なるデータ
の圧縮技術ではなく、根本的に異なる形状表現を実現し
ていることを意味している。

【０１２４】データ編集装置１０で得られた位相幾何学
的データは軽く、当然ながら伝送、記憶、編集に有利で
ある。しかも今日まで蓄積されてきた膨大なポリゴンデ
ータを活かすことができる。いったん生成された位相幾
何学的データに編集を加えることで容易に別のオブジェ
クトを設計することもできる。編集は例えば輪郭線の形
状を変えたり、特異点の位置をずらすなど、ドローイン
グソフトウエア程度の簡単なユーザインタフェイスで実
現できる。

【０１２５】オブジェクトの可視化を考えた場合、市販
のレンダラーなどの中にはモデリングがポリゴンでなさ
れていないと動作しないものがある。図４０はそうした
場合に対応する処理の原理を示すフローチャートであ
る。同図のごとく、まず位相幾何学的データを取得し
（Ｓ５０）、そのデータ表現形式またはデータ構造に注
目しながらポリゴンデータへ逆変換する（Ｓ５１）。

【０１２６】図４１は図４０の処理を実現するデータ逆
変換器７０の構成図である。この装置は、位相幾何学的
データ記憶部７５からデータを入力するデータ入力部７
１と、入力したデータの構造を解析してオブジェクトの
曲面を構成するための要素を抽出するデータ構造解析部
７２と、抽出された要素から構成される曲面上に離散的
に点をとってこれをポリゴンの頂点と決めるポリゴン頂
点定義部７３をもつ。ポリゴンの頂点はポリゴンデータ
記憶部７６へ出力される。

【０１２７】この構成にて、まず位相幾何学的データま
たは基本情報が位相幾何学的データ記憶部７５からデー
タ入力部７１へ入力される。入力されたデータはデータ
構造解析部７２へ送られる。データは例えば図３８に示
す構造であり、データ構造解析部７２はそれらの中から
輪郭線とガイディングカーブに関する情報を読み出す。

【０１２８】つづいて、処理はポリゴン頂点定義部７３
に進む。図４２はふたつの輪郭線Ｃ１、Ｃ２と、ふたつ
のガイディングカーブＧ１、Ｇ２で囲まれる四辺形の領
域８０である。ポリゴン頂点定義部７３は、まず領域８
０にテンソル積曲面、クーンズ（Ｃｏｏｎｓ）曲面、グ
レゴリー（Ｇｒｅｇｏｒｙ）曲面などのパラメトリック
パッチＳ（ｕ，ｖ）（０≦ｕ，ｖ≦１）を貼る。ノード
を含む領域は三角形になるが、これは四辺形の縮退とし
て扱えばよく、従来の技術で対応できる。つづいて、パ
ラメータｕ，ｖを少しずつ変化させながらＳ（ｕ，ｖ）
の位置をプロットしていく。ポリゴンデータの精度を高
めたければｕ、ｖのステップを小さくとる。

【０１２９】図４３はこうしてプロットされた点を示し
ており、これらの点をポリゴンの頂点と決める。図４４
のごとく、例えばある三角形領域８２は、それを構成す
る３つの頂点（Ｎａ，Ｎｂ，Ｎｃ）で記述しておく。こ
うしてポリゴンデータへの変換が完了し、当該データが
ポリゴンデータ記憶部７６へ記録される。

【０１３０】図４５はデータ変換器９０とデータ逆変換
器９１をともに含むシステムの構成図である。同図のご
とく、データ変換器９０はまず、オブジェクト指定部９
５の指示に従ってユーザが求めるオブジェクトのポリゴ
ンデータを第１記憶部９２から読み出し、既述の方法で
位相幾何学的データへ変換して第２記憶部９３へ格納す
る。データ逆変換部９１は、オブジェクトの基本情報ま
たは位相幾何学的データを第２記憶部９３から読み出
し、これをポリゴンデータへ戻して第３記憶部９４へ格
納する。その際、ポリゴン数指定部９６で指定されたポ
リゴンの概数に近くなるよう前述のパラメータｕ、ｖの
ステップを決める。ポリゴン数指定部９６では、ポリゴ
ン数を直接指定するほか、ポリゴン数を多くする、少な
くする、といった指定も可能にすることが望ましい。ま
た、トータルのデータ量を指定する方法もある。このシ
ステムによれば、例えば粗いポリゴンデータをより細か
いポリゴンデータに変換するという、ポリゴンデータ間
の変換機能も実現する。

【０１３１】図４６はこのシステムを応用したサーバ・
クライアントシステム１００の構成図である。サーバ１
１０は既存のポリゴンデータを保持する第１サーバ記憶
部１１１と、データ変換器１１２と、変換で得られた位
相幾何学的データを格納する第２サーバ記憶部１１３
と、ネットワーク１３０を介してクライアント１２０と
通信する第１通信部１１４を含む。

【０１３２】クライアント１２０はサーバ１１０と通信
する第２通信部１２１と、受け取った位相幾何学的デー
タを格納する第１クライアント記憶部１２２と、データ
逆変換器１２３と、逆変換されたデータを格納する第２
クライアント記憶部１２４を含む。

【０１３３】図４７は図４６のシステム１００における
サーバ１１０、クライアント１２０間のやりとりを示す
図である。クライアント１２０で、あるオブジェクトの
データが必要になったとき、まず第２通信部１２１を通
してサーバ１１０にデータの要求を出す（Ｓ６０）。ネ
ットワーク１３０、第１通信部１１４を介してサーバ１
１０がその要求を受信する（Ｓ６１）。サーバ１１０
は、必要なポリゴンデータを第１サーバ記憶部１１１か
ら読み出した後データ変換器１１２で位相幾何学的デー
タに変換する（Ｓ６２）。この位相幾何学的データは第
２サーバ記憶部１１３に格納され（Ｓ６３）、クライア
ント１２０に送信される（Ｓ６４）。

【０１３４】クライアント１２０はそのデータを受信し
（Ｓ６５）、第１クライアント記憶部１２２に格納する
（Ｓ６６）。クライアント１２０はこのデータをそのま
ま利用してもよいが、ポリゴンデータが必要であればデ
ータ逆変換器１２３でポリゴンデータに戻した後（Ｓ６
７）、これを第２クライアント記憶部１２４に格納する
とともに利用する（Ｓ６８）。

【０１３５】なお、クライアントから要求されたデータ
がすでに位相幾何学的データとして第２サーバ記憶部１
１３に存在する場合、サーバ１１０はデータ変換を行わ
ず、単にこれを読み出してクライアント１２０へ送信す
ればよい。

【図面の簡単な説明】

【図１】特異点の指数、ｋ次元セルおよびそれによっ
て符号化される物体の関係を示す図である。

【図２】図２（ａ）〜（ｃ）はそれぞれが同じモース
の指数の配列をもつ３組の曲面を示す図である。

【図３】図３（ａ）〜（ｃ）はトーラスとそのレーブ
グラフの関係を示す図である。

【図４】図４（ａ）（ｂ）は輪郭線の親子関係、およ
びその木構造による表現を示す図である。

【図５】演算子を用いてトーラスを符号化する方法を
示す図である。

【図６】疑似パスカルコードによる演算子のプログラ
ミング例を示す図である。

【図７】疑似パスカルコードによる演算子のプログラ
ミング例を示す図である。

【図８】疑似パスカルコードによる演算子のプログラ
ミング例を示す図である。

【図９】それぞれがセルに対応するアイコンを示す図
である。

【図１０】セルの貼り合わせを示す図である。

【図１１】オブジェクトのレーブグラフをアイコンで
示した図である。

【図１２】オブジェクトの断面の輪郭線を示す図であ
る。

【図１３】オブジェクトを構成するための演算子を示
す図である。

【図１４】輪郭線のホモトピー変形を示す図である。

【図１５】演算子を構成する主な４つの要素を示す図
である。

【図１６】ガイディング曲線によって上の輪郭線が徐
々に下の輪郭線に変形される様子を示す図である。

【図１７】オブジェクトの構造グラフの生成手順を示
すフローチャートである。

【図１８】オブジェクトの構造グラフ生成装置の構成
図である。

【図１９】図１８の構造グラフ生成装置による処理を
示すフローチャートである。

【図２０】谷底頂点（ｐｉｔ）付近のポリゴンの辺を
示す図である。

【図２１】鞍点（ｓａｄｄｌｅ）付近のポリゴンの辺
を示す図である。

【図２２】頂点（ｐｅａｋ）付近のポリゴンの辺を示
す図である。

【図２３】指数１の特異点付近の輪郭線のひとつの形
状を示す図である。

【図２４】指数１の特異点付近の輪郭線の別の形状を
示す図である。

【図２５】図２４に示す輪郭線が生じるオブジェクト
を示す図である。

【図２６】「ふたつの独立したトーラス」のレーブグ
ラフを示す図である。

【図２７】「ねじれたトーラス」のレーブグラフを示
す図である。

【図２８】データ変換方法の処理を示すフローチャー
トである。

【図２９】データ変換方法の処理を別の表現で示すフ
ローチャートである。

【図３０】データ変換装置の構成図である。

【図３１】図３０のデータ変換装置による処理を示す
フローチャートである。

【図３２】ハート型オブジェクトのポリゴンデータを
可視化して示す図である。

【図３３】図３２のオブジェクトのいくつかの輪郭線
を示す図である。

【図３４】断面のとり方を示す図である。

【図３５】輪郭線の対応点を検出する方法を示す図で
ある。

【図３６】輪郭線の対応点を検出する別の方法を示す
図である。

【図３７】データ変換の結果得られた位相幾何学的デー
タを可視化して示す図である。

【図３８】基本情報のデータ構成図である。

【図３９】ハート型オブジェクトの位相幾何学的デー
タを可視化して示す図である。

【図４０】データの逆変換の手順を示すフローチャー
トである。

【図４１】データ逆変換器の構成図である。

【図４２】ガイディングカーブと輪郭線で形成される
四辺形領域を示す図である。

【図４３】図４２の四辺形領域にとられた格子点を示
す図である。

【図４４】図４２の四辺形領域にとられたポリゴンを
示す図である。

【図４５】データ変換および逆変換を行うシステムの
構成図である。

【図４６】図４５の応用例であるサーバ・クライアン
トシステムの構成図である。

【図４７】図４６のシステムの動作を示すフローチャ
ートである。

【符号の説明】

１構造グラフ生成装置、２データ入力部、３モー
ス関数決定部、４特異点検出部、５特異点接続情報
取得部、１０データ編集装置、２０データ変換器、
２１データ入力部、２２構造グラフ生成部、２３
断面生成部、２４輪郭線円滑化部、２５輪郭線情報
取得部、３０レンダリング部、３１曲面パッチ生成
部、３２可視化部、４０表示制御部、４１ポリゴ
ンデータ記憶部、４２位相幾何学的データ記憶部、４
３表示装置、５０断面を表す線、５２修正された
断面を表す線、７０データ逆変換器、７１データ入
力部、７２データ構造解析部、７３ポリゴン頂点定
義部、７５位相幾何学的データ記憶部、７６ポリゴ
ンデータ記憶部、８０四辺形領域、９０データ変換
器、９１データ逆変換器、９２第１記憶部、９３
第２記憶部、９４第３記憶部、９５オブジェクト指定
部、９６ポリゴン数指定部、１００サーバ・クライ
アントシステム、１１０サーバ、１１１第１サーバ
記憶部、１１２データ変換器、１１３第２サーバ記
憶部、１１４第１通信部、１２０クライアント、１２
１第２通信部、１２２第１クライアント記憶部、１
２３データ逆変換器、１２４第２クライアント記憶
部、１３０ネットワーク。

フロントページの続き (56)参考文献ＩＥＥＥＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓａｎｄＡｐｐｌｉｃａｔｉｏｎｓ、Ｖｏｌ．11、Ｎｏ．５（Ｓｅｐｔｅｍｂｅｒ 1991）、（米）、ＹｏｓｈｉｈｉｓａＳｈｉｎａｇａｗａａｎｄＴｏｓｈｉｙａｓｕＬ．Ｋｕｎｉｉ、「ＳｕｒｆａｃｅＣｏｄｉｎｇＢａｓｅｄｏｎＭｏｒｓｅＴｈｅｏｒｙ」、ｐ．66−78 ＩＥＥＥＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓａｎｄＡｐｐｌｉｃａｔｉｏｎｓ、Ｖｏｌ．11、Ｎｏ．６（Ｎｏｖｅｍｂｅｒ 1991）、（米）、ＹｏｓｈｉｈｉｓａＳｈｉｎａｇａｗａａｎｄＴｏｓｈｉｙａｓｕＬ．Ｋｕｎｉｉ、「ＣｏｎｓｔｒｕｃｔｉｎｇａＲｅｅｂＧｒａｐｈＡｕｔｏｍａｔｉｃａｌｌｙｆｒｏｍＣｒｏｓｓＳｅｃｔｉｏｎｓ」、ｐ．44−51 情報処理学会第54回（平成９年前期) 全国大会講演論文集（1997−３−12）情報処理学会、廣瀬和樹，品川嘉久、「形状の位相構造に基づいたポリゴンデータからの曲面の生成」ｐ．［４］215− ［４］216 (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06T 1/00 - 17/50 G06F 17/50

Claims

(57)【特許請求の範囲】

【請求項１】オブジェクトの形状を表すポリゴンデー
タを取得するデータ入力部と、取得されたポリゴンデータに対してモース関数を定める
モース関数決定部と、そのモース関数の特異点を検出する特異点検出部と、特異点どうしの接続情報を取得する特異点接続情報取得
部と、を含むことを特徴とするオブジェクトの構造グラフ生成
装置。
【請求項２】前記特異点検出部は、微分不可能な頂点
を含むポリゴンデータについて設けられた定義にしたが
って特異点を検出することを特徴とする請求項１に記載
の装置。
【請求項３】前記特異点接続情報取得部は、ポリゴン
の辺を辿ることによって特異点どうしの接続関係を取得
する請求項１、２のいずれかに記載の装置。
【請求項４】オブジェクトの形状を表すポリゴンデー
タを位相情報を利用した位相幾何学的なモデリングに基
づくデータへ変換する装置であって、当該装置は構造グラフ生成手段を含み、この構造グラフ生成手段は、オブジェクトの形状を表すポリゴンデータを入力する手
段と、そのポリゴンデータからオブジェクトの位相情報を抽出
する手段と、を含み、当該装置はさらに、抽出されたオブジェクトの位相情報
に加えて、そのオブジェクトに関する幾何情報を利用し
て前記位相幾何学的なモデリングに基づくデータを生成
することを特徴とするオブジェクトのデータ変換装置。
【請求項５】オブジェクトの形状を表すポリゴンデー
タを取得するデータ入力部と、取得されたポリゴンデータに関するモース関数の特異点
を検出する特異点検出部と、特異点どうしの接続情報を取得する特異点接続情報取得
部と、オブジェクトの断面の輪郭線情報を取得する手段と、を含むことを特徴とするオブジェクトのデータ変換装
置。
【請求項６】オブジェクトの形状を表すポリゴンデー
タを入力する手段と、入力されたポリゴンデータからオブジェクトの位相情報
を抽出することによってオブジェクトの骨格グラフを生
成する手段と、を含み、前記骨格グラフを生成する手段は、微分不可能
な頂点を含むポリゴンデータについて設けられた定義に
したがって特異点を検出することにより、前記骨格グラ
フを生成することを特徴とするオブジェクトの構造グラ
フ生成装置。
【請求項７】オブジェクトの形状を表すポリゴンデー
タを入力する手段と、そのポリゴンデータからオブジェクトの位相情報を抽出
することによってオブジェクトの骨格グラフを生成する
手段と、を含み、前記骨格グラフを生成する手段は、ポリゴンデータに対してモース関数を設定する手段と、そのモース関数に対して定まる特異点を検出する手段
と、検出された特異点間の接続情報を取得する手段と、を含むことを特徴とするオブジェクトの構造グラフ生成
装置。
【請求項８】オブジェクトの形状を表すポリゴンデー
タを入力する手段と、入力されたポリゴンデータからオブジェクトの位相情報
を抽出することによってオブジェクトの骨格グラフを生
成する手段と、入力されたポリゴンデータから、オブジェクトの断面の
輪郭線情報を取得する手段と、を含むことを特徴とするオブジェクトのデータ変換装
置。
【請求項９】前記骨格グラフを生成する手段は、ポリゴンデータに対してモース関数を設定する手段と、そのモース関数に対して定まる特異点を検出する手段
と、検出された特異点間の接続情報を取得する手段と、を含む請求項８に記載の装置。
【請求項１０】オブジェクトの位相情報を利用する位
相幾何学的なモデリングに基づくデータを入力する手段
と、そのモデリングにおけるオブジェクトの表現形式に注目
して前記データをポリゴンデータへ変換する手段と、を含み、前記変換する手段は、入力されたデータの構造を解析して曲面を構成する要素
を抽出する手段と、その要素から得られる曲面上で離散的にポリゴンの頂点
を定義する手段と、を含むことを特徴とするオブジェクトのデータ変換装
置。
【請求項１１】オブジェクトの形状を表すポリゴンデ
ータを位相幾何学的なモデリングに基づくデータへ変換
する手段と、その結果得られたデータを記憶する手段と、記憶されたデータを読み出し、そのデータ構造を解析し
てこれをポリゴンデータへ逆変換する手段と、を含むことを特徴とするオブジェクトのデータ変換シス
テム。