(57)【特許請求の範囲】
【請求項１】
文字コードと刻印板コードを入力するための文字刻印板コード入力手段と、
前記文字コードに対応する文字のアウトラインデータと前記刻印板コードに対応する刻印板のアウトラインデータを記憶する外周データ記憶手段と、
前記文字刻印板コード入力手段によって入力された文字コードと刻印板コードに基づいて、前記外周データ記憶手段から文字及び刻印板のアウトラインデータを取得する文字外周刻印板形状取得手段と、
前記文字外周刻印板形状取得手段において取得された文字のアウトラインデータに基づいて、前記文字の外周と当該文字に形成されている穴の外周の包含関係を解析して文字を構成する構成要素を特定し、前記刻印板の中に前記文字が存置し得る条件を算出し、その条件に基づいて刻印板のアウトラインデータを変換し、変換後の刻印板のアウトラインデータに基づいて、前記刻印板の外周と当該刻印板に形成されている穴の外周の包含関係を解析して刻印板下面を構成する構成要素を特定し、文字の外形を表す外周の点列を文字の穴を表す点列に変換し、文字の穴を表す外周の点列を文字の外形を表す点列に変換し、これら変換された点列に基づく新たな文字のアウトラインデータと前記変換後の刻印板のアウトラインデータとを合併したアウトラインデータを生成し、当該合併されたアウトラインデータに基づいて、前記変換後のアウトラインデータに係る刻印板の外周と前記新たなアウトラインデータに係る文字の外周の包含関係を解析して刻印板上面を構成する構成要素を特定する文字刻印板形状構造解析手段と、
前記文字刻印板形状構造解析手段において特定された文字と刻印板上面及び下面の構成要素ごとに、凸ポリゴンに分割する文字刻印板形状面凸ポリゴン分割手段と、
前記文字刻印板形状面凸ポリゴン分割手段においてポリゴン分割された刻印板の各構成要素を空間的に移動して刻印板の上面、下面及び側面を生成し、文字の上面の構成要素を所定の深さ分だけ空間的に移動して刻印板の堀込み部の下面と側面を生成する文字刻印板形状側面生成手段と
を備えることを特徴とする３次元図形データ生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２次元平面上の輪郭線で構成される文字等の任意の２次元形状を表すデータから、３次元形状を表すデータを生成するための３次元形状データ生成装置に関し、特に文字や図形についての３次元文字データ生成装置及び３次元図形データ生成装置に関する。
【０００２】
【従来の技術】
従来の３次元文字データ生成装置としては、例えば第１の従来例として、特開昭６３−１０３３８０号公報に開示された「３次元文字の作成装置」がある。この従来例について、図２７を参照しながら説明する。２次元文字は２次元文字入力装置１４０により入力され、ｘｙ平面上の２次元文字が記憶装置１２０内に定義される。次に、表示装置１１０の表示を見ながら行われる、操作者のｚ方向修正装置１３０の操作によって、３次元文字の形状設計が進められる。この際、ｘｚ投影面１１２またはｙｚ投影面１１３上で、各点のｚ座標値の変更が行なわれ、入力された２次元文字は３次元文字に修整される。修整中の３次元文字の立体像は立体像投影面１１４で確認することが可能である。次に、領域背景入力装置１５０から入力された絵柄の画像データに基づいて、記憶装置１２０内の３次元文字の表面に絵柄を付した状態の画像データが生成され、これが立体像投影面１１４に表示される。但し、この発明における３次元文字形状の生成は、ｘｚ投影面１１２またはｙｚ投影面１１３を利用して操作者が調整を行うものであり、自動生成ではない。
【０００３】
また、３次元文字形状の自動生成を目指したものとしては、例えば第２の従来例として、特開平１１−５３５７８号公報に開示された「形状変換方法、該方法の処理手順を記録した記録媒体、及び形状変換装置」がある。これは、２次元平面上での文字形状を表すアウトラインデータから文字の側面形状のみを生成するものである。従って、この従来例は、３次元形状の一部を生成するだけであり、文字の完全な３次元形状が得られるわけではない。
【０００４】
また、第３の従来例としては、特開平１１−５３５７９号公報に開示された「形状変換方法およびその変換手順を記録した記録媒体、ならびに形状変換装置」がある。これは、与えられた２次元のビットマップフォント文字を入力し、このビットマップフォント文字を構成する各ビットデータを３次元形状に対応させ、それらを合成することで文字全体としての３次元形状を生成するものである。しかし、ビットマップフォントは、輪郭においてジャギーが発生しやすく、このジャギーを目立たなくするためには、文字を構成するビット数の多い精緻なビットマップフォントを用いる必要がある。
【０００５】
【発明が解決しようとする課題】
しかしながら、上記の第１の従来例では、操作者が手動で３次元文字形状の生成を行うため、操作者の処理負担が大きく、また処理時間も多大に掛かり実時間での生成は不可能である。上記の第２の従来例は、３次元文字形状の自動での生成を目指したものではあるが、生成されるデータは側面のデータだけであり、特に重要な文字そのものの形状を表す表面、裏面がない不完全なもので、実用上役に立たないデータと言わざるを得ない。上記の第３の従来例では、とりあえず３次元文字形状は生成できるものの、ビットマップデータから生成するため、文字形状の輪郭部分にジャギーが発生する。従って、これを利用してＣＧ等で描画した場合には、更に描画時のジャギーが加わり、文字の品位は非常に低いものとなる。また、全てのビットマップ文字を３次元形状に対応させるため、ある程度の品位の３次元形状を実現しようとすると、非常に多くのデータ量が必要となる。
【０００６】
本発明は、上記問題に鑑みてなされたものであり、容易に高品位の３次元形状データの生成が可能な装置を提供することを目的とする。すなわち、操作者の手を煩わせることなく、与えられた２次元の文字や図形のアウトラインデータから、３次元形状を表すデータを自動かつ実時間で生成し、文字や図形の品位もビットマップフォントをベースに生成したものに比べ、はるかに高品位な３次元形状のデータ生成が可能な装置を提供する。また、３次元化した文字や図形の表面に様々なテクスチャ模様を施したり、文字形状の台座の据え付けや刻印板化することを可能とすることで、様々な３次元的文字表現に対応し得る３次元形状データ装置を提供する。
【０００７】
【課題を解決するための手段】
上記課題を解決するために、本発明に係る３次元図形データ生成装置は、文字コードと刻印板コードを入力するための文字刻印板コード入力手段と、前記文字コードに対応する文字のアウトラインデータと前記刻印板コードに対応する刻印板のアウトラインデータを記憶する外周データ記憶手段と、前記文字刻印板コード入力手段によって入力された文字コードと刻印板コードに基づいて、前記外周データ記憶手段から文字及び刻印板のアウトラインデータを取得する文字外周刻印板形状取得手段と、前記文字外周刻印板形状取得手段において取得された文字のアウトラインデータに基づいて、前記文字の外周と当該文字に形成されている穴の外周の包含関係を解析して文字を構成する構成要素を特定し、前記刻印板の中に前記文字が存置し得る条件を算出し、その条件に基づいて刻印板のアウトラインデータを変換し、変換後の刻印板のアウトラインデータに基づいて、前記刻印板の外周と当該刻印板に形成されている穴の外周の包含関係を解析して刻印板下面を構成する構成要素を特定し、文字の外形を表す外周の点列を文字の穴を表す点列に変換し、文字の穴を表す外周の点列を文字の外形を表す点列に変換し、これら変換された点列に基づく新たな文字のアウトラインデータと前記変換後の刻印板のアウトラインデータとを合併したアウトラインデータを生成し、当該合併されたアウトラインデータに基づいて、前記変換後のアウトラインデータに係る刻印板の外周と前記新たなアウトラインデータに係る文字の外周の包含関係を解析して刻印板上面を構成する構成要素を特定する文字刻印板形状構造解析手段と、前記文字刻印板形状構造解析手段において特定された文字と刻印板上面及び下面の構成要素ごとに、凸ポリゴンに分割する文字刻印板形状面凸ポリゴン分割手段と、前記文字刻印板形状面凸ポリゴン分割手段においてポリゴン分割された刻印板の各構成要素を空間的に移動して刻印板の上面、下面及び側面を生成し、文字の上面の構成要素を所定の深さ分だけ空間的に移動して刻印板の堀込み部の下面と側面を生成する文字刻印板形状側面生成手段とを備える。
【００１０】
なお、上記目的を達成するために、本発明は、上記３次元図形データ生成装置の特徴的な構成手段をステップとする３次元図形データ生成方法として実現したり、それらのステップを含むプログラムとして実現することもできる。そして、そのプログラムは、３次元図形データ生成装置が備えるＲＯＭ等に格納しておくだけでなく、ＣＤ−ＲＯＭ等の記録媒体や通信ネットワーク等の伝送媒体を介して流通させることもできる。
【００１１】
【発明の実施の形態】
以下、本発明に係る実施の形態１〜６について、図面を用いながら詳細に説明する。
（実施の形態１）
図１は、実施の形態１における３次元文字データ生成装置１０１の機能構成を示すブロック図である。３次元文字データ生成装置１０１は、文字コード入力部１、文字外周データ取得部２、文字外周データ記憶部３、文字形状構造解析部４、文字形状上下面凸ポリゴン分割部５、文字形状側面生成部６及び文字形状データ出力部７から構成されている。
【００１２】
文字コード入力部１は、いわゆるキーボードやマウスなどの入力装置で、これらの入力信号を変換し、ＡＳＣＩＩコードやＪＩＳコードなどの文字コード、図形コードを生成する。文字コード入力部１で生成された文字コードは、文字外周データ取得部２に出力される。
【００１３】
文字外周データ取得部２は、文字コード入力部１から入力した文字コードに対応する文字の、いわゆる外郭線データ（以下、「アウトラインデータ」ともいう。）を、文字外周データ記憶部３から取得する。
【００１４】
文字外周データ記憶部３には、予め、文字のアウトラインデータが、文字コードに対応して記憶されている。この場合、文字としては同一であってもフォントの種類が異なっている場合は、アウトラインデータも異なったものとなる。従って、文字外周データ記憶部３には、アウトラインデータが、文字コード及びフォントの種類に対応付けられて記憶されている。文字外周データ取得部２において取得されたアウトラインデータは、文字形状構造解析部４に出力される。
【００１５】
なお、一般にアウトラインデータは、点の総個数、曲線のタイプの識別子、開始点の座標データ（アウトラインデータにおける座標は、２次元ｘｙ座標とする。以下同じ。）、点間の接続方法（例えば、直線による接続方法や曲線による接続方法がある。）を表す識別子、文字の外周を構成する点列（または制御点列）の座標データ（以下、「点列座標データ」という。）などの１セットのデータが、１文字を構成する後述の文字部品の数だけ集まって構成されている。
【００１６】
通常、点間の接続は、直線または２次元のＢ−Ｓｐｌｉｎｅ曲線を用いることによって行われ、それら点間の接続をさらに接続することによって連続曲線が生成される。そのため、直線による接続方法においては、点列の位置データは端点を表し、曲線による接続方法においては、点列の位置データは曲線を生成する際の制御点を表す。また、点列の開始点と終点とを結ぶことで閉曲線を構成することができ、この閉曲線が文字の外周を表す曲線となる。なお、本実施の形態では、文字のアウトラインデータの中の点列座標データはｘｙ座標の値を示すものとし、文字を３次元で表す場合の高さ方向の座標軸はｚ軸とする。
【００１７】
さらに、文字によっては穴のあるトーラス構造を持つ場合があるため、アウトラインデータの点列には、文字の外形の外周を構成する点列（以下、「文字外周点列」という。）と、文字の穴の外周を構成する点列（以下、「穴外周点列」という。）の２種類が存在する。
【００１８】
漢字の「回」のように、文字の中には、複数の文字部品によって１文字が構成される場合がある。ここで、「文字部品」とは、文字を構成する、互いに非接続の要素をいう。上記の「回」の場合は、外側の「口」の文字部品と内側の「ロ」の文字部品から構成されている。また、ロシア語の「ё」の場合は、「・」、「・」及び「ｅ」の３つの文字部品から構成されている。従って、個々の文字部品は、文字外周点列を１つ有する。また、文字部品によっては、1つまたは複数の穴外周点列を有するものがある。
【００１９】
上記の文字外周点列と穴外周点列とを区別を実現するため、通常は、文字外周点列の個々の点を定義する際の各点の並べられる方向（即ち、各点を順に辿るときの回り方）と、穴外周点列における各点の並べられる方向とは、双方逆の関係にしている。ここでは、文字外周点列を辿る時の回り方は「時計回り」に、また、穴外周点列を辿る時の回り方は「反時計回り」になるように点列座標データが文字外周データ記憶部３に記憶されているものとする。但し、この回り方の決め方には、特別な理由はない。なお、明示的に文字外周と穴外周とを区別する識別子を設けても良いが、その場合は、文字外周データ記憶部３で記憶すべきデータ量が増大する。
【００２０】
図２は、上述のように、文字外周点列及び穴外周点列をたどるときの回り方を示したものである。図２では、文字外周点列を時計回りの黒点Ｐ0〜Ｐ9で表し、穴外周点列を反時計回りの白点Ｐ10〜Ｐ15で表している。
【００２１】
文字形状構造解析部４では、まず、受け取った文字のアウトラインデータの点列座標データに対して、文字外周点列なのか、穴外周点列なのかの判別を行う。この判別の手順について、図２を用いながら説明する。
【００２２】
（１）アウトラインデータから得られる点列をＰ0，Ｐ1，・・・，Ｐnとするとき、これらの点列から生成される２つの隣り合うベクトルＰiＰi+1とベクトルＰi+1Ｐi+2に対して、内積をなす角θi+1を求める（但し、i＝0，1，・・・，nであり、Ｐn+1＝Ｐ0とする。以下、同じ）。例えば、ベクトルＰ0Ｐ1とベクトルＰ1Ｐ2の場合の内積をなす角はθ1である。
【００２３】
（２）その内積をなす角θi+1に係る２つのベクトルの外積を求め、その値が正ならば正の符合を、負ならば負の符合を付加する。以上の内積をなす角θi+1を順次算出し、それらを合計した値が±２πである。
【００２４】
（３）上記（１）（２）で求めた符合付きの内積をなす角θi+1の合計を求め、その合計が−２πならば時計回りでたどる文字外周点列であると判別し、２πならば反時計回りでたどる穴外周点列であると判別する。
【００２５】
次に、上記（３）の判別の結果、文字外周点列だけで構成される文字の場合は、以下のバウンダリーボックスを求める処理を行った後、後述する構造解析結果情報とアウトラインデータとを文字形状上下面凸ポリゴン分割部５に出力する。文字外周点列と穴外周点列とが混在する場合は（即ち、穴外周点列が存在する場合）、以下で説明する構造解析（包含関係の解析）処理を行う。
【００２６】
以下では、図２に示されるように、数字の"０"を用いながら、文字外周点列の対するバウンダリーボックスを求める方法について説明する。
（１）文字外周点列から、ｘ座標の最小値（ｘo-min）と最大値（ｘo-max）、ｙ座標の最小値（ｙo-min）と最大値（ｙo-max）を求める。
（２）（１）で求められた最小値及び最大値に基づいて作成した４つの点Ａ（ｘo-min，ｙo-max）、点Ｂ（ｘo-max，ｙo-max）、点Ｃ（ｘo-max，ｙo-min）、点Ｄ（ｘo-min，ｙo-min）による、四角形ＡＢＣＤをバウンダリーボックスとする。但し、通常の数学表記の場合、反時計回りに頂点を指定していくが、本実施の形態では、文字外周点列の順序表記に合わせ、時計回りに頂点を指定している。
【００２７】
（３）バウンダリーボックスＡＢＣＤの各辺の長さの総和の半分（以下、「長さＬ」という。）を、長さＬ＝（辺ＡＢ）＋（辺ＢＣ）より算出する。
この処理後、点列座標データ、バウンダリーボックスの個数、バウンダリーボックスの４つの頂点の座標（または、ｘo-min，ｘo-max，ｙo-min，ｙo-max）、各辺の長さの総和を文字外周データ記憶部３に記憶する。穴外周点列に対しても、上記と同様のバウンダリーボックスａｂｃｄを構成する４つの座標値（以下「４座標値」という。）のｘh-min，ｘh-max，ｙh-min，ｙh-maxを求め、同様に文字外周データ記憶部３に記憶する。
【００２８】
以上のことより、例えば「回」という文字の場合は、外側の「口」の文字部品の文字外周点列と内側の「ロ」の文字部品の文字外周点列によって文字外周点列のグループを構成し、外側の「口」の文字部品と内側の「ロ」の文字部品の２つの文字穴の穴外周点列により穴外周点列のグループを構成する。従って、２つの文字外周点列に基づいて２つのバウンダリーボックスＡＢＣＤが作成され、２つの穴外周点列に基づいて２つのバウンダリーボックスａｂｃｄが作成されることとなる。
【００２９】
次に、文字外周点列のグループと、穴外周点列のグループの間の包含関係を明らかにするために、文字外周点列のバウンダリーボックス毎に、全ての穴外周点列のバウンダリーボックスを構成する４座標値に対して、次の包含関係の判定を行う。
【００３０】
（包含関係の判定）
「"ｘo-min＜ｘh-min＜ｘh-max＜ｘo-max"かつ"ｙo-min＜ｙh-min＜ｙh-max＜ｙo-max"ならば、当該穴外周は当該文字外周に含まれる。それ以外の場合は含まれない。」
【００３１】
上記の包含関係の判定では、１つの文字穴の穴外周点列が、複数の文字部品の文字外周点列に含まれたり、実際は含まれていないのに、見かけ上、含まれてしまっているという状態が起こり得る。例えば、「固」や「店」などの場合が、そのような場合に該当する。従って、このような場合は包含関係を修正する必要が有るが、それは以下の修正ルールによって実行し得る。
【００３２】
（修正ルール）
「一つの文字穴の外周が、複数の文字部品の外周に含まれている場合、その穴は最も内側の文字部品の外周に含まれる。」
以下では、この修正ルールを具体的に実施する２つの方法について述べる。まず第１の方法は下記の通りである。
（第１の方法）
２つの文字同士における文字外周間の内外判定は、先に求めておいた、文字外周点列のバウンダリーボックスの長さＬを比較することによって代替し、Ｌの値の小さい方が内側の文字であると判定する。この第１の方法は計算時間が短く、高速に包含関係が判定可能である。しかし、例外的なフォントの場合は、包含関係の判定が上手く行かないことがある。そこで、計算時間は掛かるものの、安定的に包含関係の判定ができる第２の方法ついて、以下で述べる。
【００３３】
（第２の方法）
（１）文字外周点列のバウンダリーボックスに対して、包含関係の判定を行う。つまり、「ある穴を含むと判定された複数の文字のうち、一の文字の文字外周点列のバウンダリーボックスの座標をｘoj-min，ｘoj-max，ｙoj-min，ｙoj-maxとすると（但し、ｊは文字穴を含む文字外形の添字であり、ｊ＝１〜ｎ）、あるｋに対して次の条件が成り立つならば、文字穴は添字ｋの文字の穴であると判定する。」
（条件）
「任意のｊ≠ｋに対して、ｘoj-min＜ｘok-min"かつ"ｙoj-min＜ｙok-min"かつ"ｘok-max＜ｘoj-max"かつ"ｙok-max＜ｙoj-max"」
【００３４】
この条件が成り立たないときは、次の（２）の判定を行う。なお、上の条件が成り立つときは、
ｘok-min＝ｍａｘ（ｘoj-min）
ｙok-min＝ｍａｘ（ｙoj-min）
ｘok-max＝ｍｉｎ（ｘoj-max）
ｙok-max＝ｍｉｎ（ｙoj-max）
である。従って、判定の手順としては、まず、ｍａｘ（ｘoj-min）＝ｘok-minよりｋを求め（バウンダリーボックスのｘ座標の最小値について、任意のバウンダリーボックス同士で比較し、その中で最大値を有するｊをｋとする）、そのｋに対して、残り３つの条件が成り立つかどうか調べれば良い。
【００３５】
（２）（１）の条件が成り立たないときは、穴外周点列ののバウンダリーボックスの重心から各文字外形の外周までの距離の最小値を算出し、それら最小距離の中で最小となる文字外形の外周にその穴は属すると判定する。但し、「文字穴のバウンダリーボックスの重心から文字外形の外周までの最小距離」とは、文字外周上の点までの距離の最小値と文字外周の辺までの距離の最小値を算出して、それら２つのうちの小さい方のことである。
【００３６】
文字外周上の点までの距離は、通常のユークリッド距離（２乗和のルート）を用いて算出する。文字外周の辺までの距離は以下のように求める。但し、文字外周点列をＰ0（ｐ0x，ｐ0y），Ｐ1（ｐ1x，ｐ1y），・・・，Ｐn（ｐnx，ｐny）とし、文字穴のバウンダリーボックスの重心をＣ（ｃｘ，ｃｙ）、Ｃから辺ＰｋＰｋ＋１に下ろした垂線の足をＨ（ｈｘ，ｈｙ）とする。
ａ＝ｐk+1ｘ−ｐkｘ，ｂ＝ｐk+1y−ｐkｙ，ｄ＝Ｃx−ｐkｘ
ｅ＝Ｃy−ｐkｙ
α＝（ａ×ｄ＋ｂ×ｅ）／（ａ**2＋ｂ**2）
ｈｘ＝α×ａ＋ｐｋｘ
ｈｙ＝α×ａ＋ｐｋｙ
但し、ｋ＝０，１，２，・・・，ｎであり、Ｐn+1＝Ｐ0とする（ここで、「Ｘ**Ｙ」はＸのＹ乗を表すものとする。以下、同様。）。
【００３７】
次に、ｍｉｎ（ｐkx，ｐk+1ｘ）≦ｈｘ≦ｍａｘ（ｐkｘ，ｐk+1ｘ）かつｍｉｎ（ｐkｙ，ｐk+1ｙ）≦ｈｙ≦ｍａｘ（ｐkｙ，ｐk+1ｙ）ならば、辺までの距離｜ＣＨ｜を以下の式で算出する。この条件が成り立たなければ、辺までの距離は存在しないので、次の辺の処理に移る。
0004028979.tif 000002
【００３８】
文字の構造解析結果情報は、文字の構造について、階層を有する木構造の情報（例えば、点列「ＬB」が点列「ＬA」に包含される場合は、"ＬA−ＬB"など）として表記することが可能である。この木構造で表された情報は、文字構造解析結果情報として、文字形状上下面凸ポリゴン分割部５に出力される。
【００３９】
以上のように構成される文字形状構造解析部４における処理について、漢字の「回」を例として挙げた図３及び図４を参照しながら詳細に説明する。
【００４０】
図３は、漢字の「回」について文字形状構造解析を実施した場合の模式図である。また、図４は、図３における包含関係解析処理における詳細な処理の流れを示すフローチャートである。なお、図３に示されるように、「回」の点列は、外側の「口」の部分の外周の点列４０１、外側の「口」の部分の穴の外周の点列４０２、内側の「ロ」の部分の外周の点列４０３及び内側の「ロ」の部分の穴の外周の点列４０４によって構成されている。
【００４１】
最初に、文字形状構造解析部４は、文字外周データ取得部２から受け取った「回」の点列に対して、上述の方法により、それが文字外周点列を表すのか、穴外周点列を表すのかについての判別を行う（Ｓ４０５）。その結果、点列４０１（Ｌo-1）及び点列４０３（Ｌo-2）が文字外周点列に該当し（４０６）、点列４０２（Ｌh-1）及び点列４０４（Ｌh-2）が穴外周点列に該当すると判別される（４０７）。この後、文字外周点列４０１、４０３についてはバウンダリーボックス及び長さＬが算出され（Ｓ４０８）、穴外周点列４０２、４０４についてはバウンダリーボックスが算出される（Ｓ４０９）。
【００４２】
次に、上記の穴外周点列４０２（Ｌh-1）及び穴外周点列４０４（Ｌh-2）が、どの文字外周点列に含まれるのかについての包含関係解析処理が実行される（Ｓ４１０）。
【００４３】
包含関係解析処理（Ｓ４１０）では、まず、解析対象とする文字外周点列（Ｌo-1、Ｌo-2）のバウンダリーボックスと穴外周点列（Ｌh-1、Ｌh-2）のバウンダリーボックスが特定され（Ｓ５０１）、穴外周点列のバウンダリーボックスが文字外周点列のバウンダリーボックスに包含されているか否かについて判定がなされる（Ｓ５０２、Ｓ５０３）。この判定は、すべての文字外周点列のバウンダリーボックスと穴外周点列のバウンダリーボックスとの組合せについて実施される（Ｓ５０４、Ｓ５０１〜Ｓ５０３）。「回」の場合であれば、文字外周点列Ｌo-1が穴外周点列Ｌh-1及びＬh-2を包含し、文字外周点列Ｌo-2が穴外周点列Ｌh-2を包含していると判定される（４１１）。
【００４４】
上記の判定において、１つの穴外周点列が複数の文字外周点列に含まれていると判定された場合は、その穴外周点列を包含する唯一の文字外周点列を特定する必要があるため、以下のような包含関係の修正を行う必要がある（Ｓ４１２、Ｓ４１３、Ｓ５０５）。
【００４５】
まず、１つの穴外周点列を特定し、これを包含する文字外周点列を全て（例えば、Ｎ個）特定し、さらに、前述の第１または第２（１）の方法によってＮ個の中から最も内側にある文字外周点列を特定する（Ｓ５０６、Ｓ５０９）。
【００４６】
もし、特定できなかった場合は（Ｓ５０７）、前述の第２（２）の方法によって、最も内側にある文字外周点列を特定する（Ｓ５０８、Ｓ５１０）。
【００４７】
以上により、「回」についての包含関係の判定は、内側の「ロ」の部分の穴外周点列（Ｌh-2）は、その「ロ」の部分の文字外周点列（Ｌo-2）のみに包含されるように修正され、この構造解析結果情報を木構造で表すことが可能となる（４１４）。
【００４８】
なお、文字（または文字部品）に穴がない場合は、その構造は階層のないフラットな構造であるとするという構造解析結果情報が、穴のある場合と同様に文字形状上下面凸ポリゴン分割部５に出力される。このように、文字（または文字部品）は、文字形状構造解析部４から得られる構造解析結果情報により、その構成要素を"外形のみ"または"外形＋文字穴"という木構造で表現することができる。ここで、「構成要素」とは、文字又は文字部品において後述のポリゴン分割の対象となる、文字外周点列によって定義される文字外周の内部領域（文字外周点列を含む）、又は文字外周点列によって定義される文字外周の内部領域から穴外周点列によって定義される穴の内側の内部領域を除いた領域（文字外周点列と穴外周点列とを含む）をいう。
【００４９】
文字形状上下面凸ポリゴン分割部５は、上述した構成要素に対して、それぞれ凸ポリゴン分割を行う。なお、本実施の形態では、凸ポリゴンの一例として三角形をとりあげ、これによってポリゴン分割を行う場合について説明する。
【００５０】
まず、文字形状上下面凸ポリゴン分割部５では、分割を行う構成要素に穴外周点列が含まれている場合に、三角形ポリゴン分割を行うための前処理として、文字外周点列と穴外周点列とを接続する処理を行い（以下「接続化」という。）、一つの外周の点列に変換する。同時に、点列番号（点列の並びの順序を表す番号）の付け替え処理を行う。この接続化は、上記のアウトラインデータに基づいて文字外周と穴外周とを接続して、いわゆる一筆書きが可能な並び方の点列座標データを生成する処理である。接続化は、以下の２つの方法により実現が可能である。
【００５１】
図５は、第１の接続化の方法を漢字の「田」に適用し、さらに点列番号の付け替えを実施した様子を示す図である。以下、第１の接続化の方法について図５を参照しながら説明する。なお、図５においては、各点列の点列番号のみを示している。
【００５２】
（第１の接続化の方法）
（１）全ての文字穴について、各文字穴の穴外周点列に基づいて、ｘ、ｙ座標の最大値ｘ−ｍａｘ，ｙ−ｍａｘと最小値ｘ−ｍｉｎ，ｙ−ｍｉｎを求め、各文字穴の中心座標（（ｘ−ｍａｘ＋ｘ−ｍｉｎ）／２，（ｙ−ｍａｘ＋ｙ−ｍｉｎ）／２）を求める。
【００５３】
（２）各文字穴の中心座標から最も近い文字外周点を求める（以下、「近接点」という。）。但し、この場合の距離は、計算量を減らすため、ｘ、ｙ座標の２乗和で代替し、ルートは取らないこととする。複数の文字穴がある場合は、近接点に重複がないよう、一つの文字穴に対して近接点を求めた後は、次の文字穴に対してはその近接点を除いた文字外周点から近接点を選択する。図５の例では、文字穴６１５についての近接点を文字外周点列の中の点「４」とする。
【００５４】
（３）上記の近接点に最も近い文字穴の穴外周点を求め、その点が始点となるように穴外周点列の順序を並べ変える（即ち、点列番号の付け替えを行う）。例えば、元の穴外周点列を｛Ｐ0，Ｐ1，・・・，Ｐk，・・・，Ｐm｝とし、近接点に最も近い文字穴の外周上の点がＰkのときは、｛Ｐk，・・・，Ｐm，Ｐ0，Ｐ1，・・・，Ｐk-1｝の順になるように点列番号を付け替える。図５の例であれば、文字穴６１５の穴外周点列｛０，１，２，３｝のうち、近接点に最も近い穴外周上の点は、点「２」であるため、｛２，３，０，１｝の順になるように点列番号を付け替える。
【００５５】
（４）文字外周点列に穴外周点列を埋め込み、点列番号の付け替えを行う。例えば、元の文字外周点列の点列番号が｛Ｑ0，Ｑ1，Ｑ2，・・・，Ｑi，Ｑi+1，・・・，Ｑn｝であり、上記（３）の付け替えを行った後の新たな穴外周点列が｛Ｐ0，Ｐ1，・・・，Ｐm｝で、近接点が「Ｑi」のときは、穴外周点列の埋め込みは、｛Ｑ0，Ｑ1，Ｑ2，・・・，Ｑi，｛Ｐ0，Ｐ1，・・・，Ｐm，Ｐ0｝，Ｑi，Ｑi+1，・・・，Ｑn｝のように行う。このように埋め込まれた点列に、新たに点列番号を付け替えると、それらは｛０，１，２，・・・，ｉ，ｉ＋１，・・・，ｉ＋ｍ＋１，ｉ＋ｍ＋２，ｉ＋ｍ＋３，・・・，ｎ＋ｍ＋３｝となる。複数の文字穴がある場合は、上記の近接点の点列番号の小さい方から、順次埋め込みを行って接続化を行う。図５の例の場合、便宜上、文字穴６１５の穴外周点列のみを埋め込むこととすると、文字外周点列の順序番号が｛０，１，・・・，４，・・・，１１｝であり、上記（３）の並べ替えを行った後の新たな穴外周点列を｛０，１，２，３｝とするときは、文字穴６１５についての近接点が点「４」であるので、穴外周点列を埋め込むと、｛０，１，・・・，４，｛０，１，２，３，０｝，４，・・・，１１｝となる。さらに、新たに点列番号を付け替えると、｛０，１，・・・，４，５，・・・，９，１０，・・・，１７｝となる。図５に示されるように、以上の接続化を他の文字穴６１６〜６１８についても適用すると、最終的には、新たに生成された外周の点列の点列番号は、｛０，１，・・・，３５｝となる。
【００５６】
この後、文字形状上下面凸ポリゴン分割部５は、この接続化によって新たに生成された外周の点列と接続化を行う前の文字外周点列及び穴外周点列とを対応付けて（例えば、テーブル形式で）文字外周データ記憶部３に記憶する。なお、この接続化によって生成された外周の点列には重複点が含まれているため、重複点であることを示す識別子についても合わせて文字外周データ記憶部３に記憶する。
【００５７】
次に、例外的な文字（または文字部品）に対しても処理が可能なように、上記第１の接続化の方法のアルゴリズムを強化修正した第２の接続化の方法について述べる。
【００５８】
（第２の接続化の方法）
（１）１つ処理対象とする文字穴に着目し、その穴外周点列の各点から文字外周点列の各点までの距離を算出し、その中から最小のもの（最小距離）を特定する。また、上記の穴外周点列の各点から文字外周の辺までの距離を算出し、その中から最小距離を特定する。
【００５９】
（２）上記（１）により特定された最小距離のうち、より小さい方を上記着目した文字穴の最小距離として採用し、その穴外周点列の点と文字外周点列の点（または、穴外周点列の点と文字外周の辺に下ろした垂線の足の点）の２つの点を決定する。
【００６０】
（３）上記（２）で決定した穴外周点列の点を始点とする順序に穴外周点列の点列番号の付け替えを行う。例えば、元の穴外周点列が｛０，１，・・・，ｋ，・・・，ｍ｝で、近接点に最も近い穴外周点が点「ｋ」のとき、｛ｋ，・・・，ｍ，０，１，・・・，ｋ−１｝の順になるように点列番号の付け替えを行う。
【００６１】
（４）文字外周までの最小距離の最小値を満たすものが文字外周点列の点の場合は、文字外周点列に穴外周点列を埋め込み、点列番号の付け替えを行う。例えば、元の文字外周点列の点列番号が｛０，１，２，・・・，ｉ，ｉ＋1，・・・，ｎ｝であり、上記（３）の並べ替えを行った後の穴外周点列の点列番号を｛０，１，・・・，ｍ｝とするとき、穴外周点列の始点に最も近い点がｉの場合の埋め込みは、｛０，１，２，・・・，ｉ，｛０，１，・・・，ｍ，０｝，ｉ，ｉ＋１，・・・，ｎ｝となり、これに対してシリアルに点列番号を付け替えるので、｛０，１，２，・・・，ｉ，ｉ＋１，・・・，ｉ＋ｍ＋１，ｉ＋ｍ＋２，ｉ＋ｍ＋３，・・・，ｎ＋ｍ＋３｝となる。これを新たな外周の点列とする。このとき、新たな外周の点列の他に、穴外周点列の始点と接続化前の文字外周点列及び穴外周点列、さらに、ｉ，ｉ＋１，ｉ＋ｍ＋１，ｉ＋ｍ＋２を重複点として文字外周データ記憶部３に記憶する。
【００６２】
一方、外周までの最小距離の最小値を満たすものが文字外形の辺に下ろした垂線の足の点の場合は、文字外周点列にこの垂線の足の点を埋め込み、点列番号の付け替えを行う。例えば、垂線の足が文字外周点列の点ｋとｋ＋１で生成される辺上にある場合は、ｋとｋ＋１の間にこの点を埋め込む。次に、この埋め込みが終わった文字外周点列に対して、上記と同様に穴外周点列を埋め込み、点列番号の付け替えを行うが、接続化は、上記の垂線の足の点（新たに埋め込まれた文字外周点ｋ＋１）を近接点として埋め込みを行う。この場合も、新たな外周の点列の他に、穴外周点列の始点と接続化前の文字外周点列及び穴外周点列、さらに、ｋ＋１，ｋ＋２，ｋ＋ｍ＋３，ｋ＋ｍ＋４を重複点として文字外周データ記憶部３に記憶する。
【００６３】
（５）複数の文字穴がある場合は、次の文字穴に対して上記（１）から（４）の処理を行う。但し、（４）において一旦重複点となった点については、（１）における最小距離の算出対象から除外する。
【００６４】
次に、構成要素の三角形分割の方法について、２通りの方法について説明する。
まず、第１の三角形分割方法について説明する。平面上の点列に対する凸包の三角形分割のアルゴリズムとしては、計算幾何学の分野で研究が行われており、著名なものとしては、Ｄｕｌａｕｎａｙの三角形分割アルゴリズムがある。また、点列に対する凸包の算出アルゴリズムとしては、Ｇｒａｈａｍのアルゴリズムや、Ｑｕｉｃｋｈｕｌｌのアルゴリズムがある。従って、構成要素が、文字外周のみで、しかも文字の外形が凸形ならばＤｕｌａｕｎａｙのアルゴリズムを適用することで三角形分割が完了する。しかし一般には、上記の説明からも判るように、構成要素には穴が存在したり、文字の外形は、例えば「あ」のように凹多角形であることが多い。そのため、以下で述べるような、これらのアルゴリズムを組合せ改良した方法によって、構成要素に対する三角形分割を行う。
【００６５】
（１）前述の接続化によって生成した外周の点列から、その後方に位置する重複点を除いた点列を新たに生成して（これを「点列Ｂ」とし）、その対応関係を文字外周データ記憶部３にテーブル形式で記憶する。つまり、このテーブルには、接続化した外周の点列と接続化する前の点列とが対応付けられており、接続化した外周の点列とそこから後方の重複点を除去した点列Ｂとが対応付けられている。
【００６６】
（２）点列Ｂに対して、ＧｒａｈａｍまたはＱｕｉｃｋｈｕｌｌの方法で、凸包を生成する。
（３）構成要素の外周の点列が１つの文字外形の点列で、しかも生成した凸包の外形の点列が、接続化する前の外周の点列と一致するならば識別子０を、そうでないものは識別子１を与える。
【００６７】
（４）Ｄｕｌａｕｎａｙのアルゴリズムにより、（２）で生成した凸包を三角形分割する。もし、識別子が０ならば次の構成要素に対して、上記（１）から処理を行い、識別子が１ならば（５）の処理に移る。
（５）（４）で生成した三角形の重心を算出する。
【００６８】
（６）前記接続化によって得られた外周の点列をＰ0，Ｐ1，・・・，Ｐmとすると、Ｐi、Ｐi+1に対応する点列Ｂの点を上記のテーブルを参照して求め、それをＱ，Ｒとすると、ＱＲを１つの辺として三角形を構成した場合のそれらの三角形の重心Ｃiに対して（このＣiは最多であっても２つである）、ベクトルＰiＰi+1とベクトルＰiＣiとの外積を計算する。但し、ＱＲを辺として含む三角形が２つある場合は、それぞれの重心に対して外積計算を行う。
【００６９】
このとき、文字形状が定義される空間の座標系が右手系であって、外積の計算結果が正の場合、その三角形は、文字外形の凹部に作られた三角形であるか、もしくは文字穴の内部の三角形であるので、棄却する。左手系の場合は、外積の結果が負の場合に棄却する。以上の処理をｉ＝０，・・・，ｍ−１に対して順次行う。このとき、Ｐi，Ｐi+1が共に重複点の場合は、それに対応するＰj-1（Ｐiに対応する重複点），Ｐj（Ｐi+1に対応する重複点）が点列Ｂの後方に存在する（つまり、ｉ＜ｊ−１）ことになるので、辺ＰiＰi+1に対する三角形の除去判定が終了したら、後方の辺Ｐｊ−１Ｐjの判定は行わないように終了識別子をテーブルに設定する。ｉ＝ｍ−１まで処理が終了したら、次の構成要素に対して、上記（１）から全ての構成要素に対して処理を繰り返す。
【００７０】
以上の第１の三角形分割方法を「田」について適用した場合の処理結果の例を、図６（ａ）に示す。但し、図中の番号は点列Ｂの点列番号を示している。三角形分割されたときの結果は、点列Ｂの３点の組で表される。一般に、右手系の場合、上記３点の並びが反時計回りとなる面が上面で、逆に時計回りとなる面を下面と定義される（反時計回りを下面、時計回りを上面としても何ら問題はない）。また、この並びの回転方向の判定は三角形を構成する３点をＰＱＲとすると、ベクトルＰＱとベクトルＰＲの外積を計算し、その符合によって判定できる。例えば、座標系が右手系で外積計算結果が正ならばＰＱＲの並びが反時計回りで、ＰＲＱの並びが時計回りである。左手系の場合も同様に判定が行える（但し、時計回りが一般には表面と定義される）。
【００７１】
次に、第２の三角形分割方法について説明する。前処理で得られた接続化した外周の点列をＰ0，Ｐ1，・・・，Ｐmとすると、第２の方法では以下のように処理を行う。但し、ここでは先のテーブルにおいて、文字外形の外周の凹部の点と文字穴の外周の点に対して識別子１を保持する。凹部の点の検出は文字外形の外周の点列から生成される２つのベクトルＰiＰi+1とベクトルＰi+1Ｐi+2の外積を計算し、右手系の場合ならばその符合が正の時、Ｐi+1が凹部の点である（左手系の場合は逆）。
【００７２】
（１）ベクトルＰ0Ｐ1とＰ1Ｐ2の外積を計算し、その符合を算出する（ここでは右手系として話を進めるが、左手系の場合も符合が逆なだけで同様に行える）。但し、下記（２ｂ）で点の除去が行われているので、最終的に点列の残りの点の個数が３つになったならば、外積は行わず、その３点をその順序で保持する。その３点によって構成される三角形が分割処理の最後の三角形であるため、そこで処理を終了する。
【００７３】
（２ａ）（１）の外積の結果が負ならば、三角形Ｐ0Ｐ1Ｐ2の内部に、テーブルに保持した文字穴の外周又は文字外形の凹部の点列Ｂの点が含まれていないかチェックする。このチェックは、ベクトルＰ0Ｐ1とＰ0とチェックを行う点を結んでできるベクトルの外積の符合が正で、ベクトルＰ1Ｐ2とＰ1とチェックを行う点を結んでできるベクトルの外積の符合が正で、ベクトルＰ２Ｐ0とＰ２とチェックを行う点を結んでできるベクトルの外積の符合が正の場合には、そのチェックした点は三角形の内部にあると判定される。
【００７４】
（２ｂ）（２ａ）の判定で三角形の内部に点が含まれていない場合は、３点Ｐ0Ｐ1Ｐ2をこの並びで保持し（この並びは時計回りに相当）、Ｐ1を点列Ｂから除去した新たな点列を生成し、三角形Ｐ0Ｐ2Ｐ3に対して引続き上記（１）から処理を行う。
【００７５】
（２ｃ）（２ａ）の判定で三角形の内部に点が含まれている場合は、Ｐ0を点列Ｂの最後部に移動した新たな点列を生成し、三角形Ｐ1Ｐ2Ｐ3に対して引続き上記（１）から処理を行う。
【００７６】
（２ｄ）（１）の外積の結果が正または０ならば、Ｐ0を点列Ｂの最後部に移動した新たな点列を生成し、三角形Ｐ1Ｐ2Ｐ3に対して引続き上記（１）から処理を行う。
【００７７】
以上の第２の三角形分割方法を「田」に適用した場合の処理結果の例を、図６（ｂ）に示す。但し、図中の番号は前処理で接続化を行った外周の点列の点列番号を示している。なお、上記の分割において生成された、辺と三角形とを複数組み合わせることにより、一般の多角形の形による分割が可能になる。
【００７８】
さらに、上記の第２の三角形分割方法をロシア語の「ё」に適用した場合の処理結果の例を、図７に示す。
各構成要素に対して、第１の三角形分割方法を適用することにより、点列Ｂの座標データ（ここでは２次元）と、分割された各三角形を表す３点の並びを表すデータ（点列Bにおける３つのインデックスにより表されるデータ）が生成される。一般に、右手系のデータ形式では、文字を３次元で表示する場合の下面の構成要素における上記３点の並び方は時計回り、上面の構成要素における上記３点の並び方は反時計回りとなる。また、第２の三角形分割方法を適用することにより、前記接続化した外周の点列の座標データ（ここでは２次元）と、同様に各三角形の３点の並びを表すデータ（接続化した外周の点列における３つのインデックスにより表されるデータ）が生成される。ここで、「インデックス」とは、分割された三角形の各頂点を表すための識別子をいう。例えば、三角形がP1P2P3で構成されている場合の「1」、「2」「3」がインデックスである。
以上の第１の三角形分割方法又は第２の三角形分割方法によって生成されたデータの形式は、一般にインデックスドサーフェースデータと呼ばれる。但し、左手系の場合の点列の並び方は、上記右手系の場合と逆になる。このように、文字形状上下面凸ポリゴン分割部５において、１つの文字に対する上面の各構成要素のインデックスドサーフェースデータと、下面の各構成要素のインデックスドサーフェースデータが生成され、文字形状側面生成部６に出力される。
【００７９】
文字形状側面生成部６は、文字形状上下面凸ポリゴン分割部５から出力されたインデックスドサーフェースデータを入力し、文字外周データ記憶部３から各構成要素に関する元の外周の点列（接続化される以前の形式の文字外周点列と穴外周点列）のデータを取得する。さらに、文字形状側面生成部６は、上記インデックスドサーフェースデータを三次元に拡張する。以下では、文字形状側面生成部６におけるインデックスドサーフェースデータを三次元に拡張する文字形状側面生成処理について、図８及び図９を参照しながら説明する。
【００８０】
図８は、文字形状側面生成処理における処理の流れを示すフローチャートである。図９（ａ）〜（ｄ）は、インデックスドサーフェースデータを三次元に拡張する際に必要となる、文字の上面を高さ方向に移動する４種類の方法について、それらの概要を示した図である。
【００８１】
最初に、文字形状側面生成部６は、初期化処理として、上記下面の各構成要素のインデックスドサーフェースデータのうち、点列座標データを３次元に拡張し、ｚ座標値に相当する部分を全て０にする。同様に、上記の元の外周の点列を３次元に拡張した下面における点列（以下「下点列」という。）の点列座標データのｚ座標値に相当する部分を全て０にする（Ｓ９０１）。
【００８２】
次に、文字の上面を高さ方向に移動する方法を特定し、それぞれの方法に基づいて（Ｓ９０２）、文字の上面の各構成要素のインデックスドサーフェースデータのうちの点列座標データのｚ座標値、及び元の外周の点列を３次元に拡張した上面における点列（以下「上点列」という。）の点列座標データのｚ座標値とを決定する。
【００８３】
図９（ａ）は、第１の方法の概要を示す図である。第１の方法は、文字の上面を高さ方向に垂直に持ち上げる方法である（持ち上げた高さをｈとする）。この場合は、文字の上面の各構成要素のインデックスドサーフェースデータのうち、点列座標データのｚ座標値を全てｈにする。同様に、元の外周の点列の点列座標データを３次元に拡張して上点列を生成し、そのｚ座標値に相当する部分を全てｈにする（Ｓ９０３）。
【００８４】
図９（ｂ）は、第２の方法の概要を示す図である。第２の方法は、基準ベクトルｖ（ｖｘ，ｖｙ，ｖｚ）の方向に平行移動する方法である。この場合は、文字の上面の各構成要素のインデックスドサーフェースデータのうち、点列座標データのｚ座標値を０として３次元に拡張し、これらに基準ベクトル分の座標値を加算する。同様に、元の外周の点列の点列座標データのｚ座標値を０にして３次元に拡張した上点列を生成し、これらに基準ベクトル分の座標値を加算する（Ｓ９０４）。
【００８５】
図９（ｃ）は、第３の方法の概要を示す図である。第３の方法は、文字を縮小変換または拡大変換した後に高さ方向へ移動する方法である（高さをｈとする）。この場合は、文字の上面の各構成要素のインデックスドサーフェースデータのうち、点列座標データに対して縮小または拡大変換を行い、ｚ座標値をｈとして３次元に拡張する。同様に、元の外周の点列の点列座標データに対して縮小又は拡大変換を行い、ｚ座標値をｈにして３次元に拡張した上点列を生成する（Ｓ９０５）。
【００８６】
図９（ｄ）は、第４の方法の概要を示す図である。第４の方法は、回転変換により移動する方法であり、適当な回転軸ベクトルと回転角θが予め与えられる。この場合は、文字の上面の各構成要素のインデックスドサーフェースデータのうち、点列座標データのｚ座標値を０として３次元に拡張し、これらの座標値に対して、予め与えられた回転軸ベクトルと回転角θによって定義される回転変換を施し、変換後の座標値を算出する。同様に、元の外周の点列の点列座標データのｚ座標値を０にして３次元に拡張した上点列を生成し、この座標値に対して、予め与えられた回転軸ベクトルと回転角によって定義される回転変換を施し、変換後の座標値を算出する（Ｓ９０６）。
【００８７】
なお、以上の処理からも判るように、３次元に拡張した上記元の外周の下点列と上点列は、点列番号が一致している。以上のように、文字形状側面生成部６において、３次元に拡張された文字上下面の各構成要素のインデックスドサーフェースデータが生成され（Ｓ９０７）、文字形状データ出力部７に出力される。
【００８８】
３次元に拡張した各構成要素の外周の下点列を｛Ｐ'n｝、上点列を｛Ｐn｝とすると、右手系の場合、側面は四角形ＰiＰ'iＰ'i+1Ｐi+1として生成できる（反時計回りの順で、左手系の場合は時計回りに並べ変えれば良い）。インデックスドサーフェースデータの形式の側面データとするためには、上点列の後に下点列を付加した点列（ここでは｛Ｑ２n｝）の点列座標データに、ＱiＱi+nＱi+1Ｑi+n+1の並びのインデックスデータを並べる。このように生成された、各構成要素の側面のインデックスドサーフェースデータは、文字形状データ出力部７に出力される。
【００８９】
文字形状データ出力部７では、文字形状側面生成部６から出力されてきた、文字の各構成要素の上下面のインデックスドサーフェースデータと、各構成要素の側面のインデックスドサーフェースデータを階層的な記述によって一まとめにして、外部（例えば、３次元図形表示装置等）へ出力する。なお、データ形式を変換する場合には、当該データ形式へ変換してから出力を行う。
【００９０】
以上のように、穴が含まれている文字について、文字や文字部品の外形と文字穴との包含関係を明確にすることにより、文字部品の単位までに分割した３次元表示を可能とすることができる。
【００９１】
（実施の形態２）
上記の実施の形態１では、文字の上面を高さ（ｚ軸）方向に直線的に持ち上げることによって、３次元文字の側面を直線的に形成し、３次元の文字を生成する実施例について述べたが、実施の形態２では、３次元の文字の側面に任意の中間外周を設け、その中間外周に基づいて種々のべベル形状の側面を形成する実施例について述べる。なお、本実施の形態では、上記実施の形態１と同じ構成部分についての説明は省略する。
【００９２】
図１０は、本実施の形態における３次元文字データ生成装置２０１の機能構成を示すブロック図である。本装置２０１は、前記文字形状側面生成部６に代えてべベル形状側面生成部１１を備え、前記文字形状データ出力部７に代えて文字形状データ出力部１２を備える。以上のように構成される３次元文字データ生成装置２０１について、以下詳細に説明を行う。
【００９３】
べベル形状側面生成部１１では、上記文字形状上下面凸ポリゴン分割部５の出力結果のほかに、上記実施の形態１と同様に元の外周の点列のデータを文字外周データ記憶部３から入力する。文字下面の各構成要素のインデックスドサーフェースデータのうち、点列座標データを３次元に拡張し、ｚ座標値に相当する部分を全て０にする。同様に、元の外周の点列の点列座標データを３次元に拡張した下点列を生成し、そのｚ座標値に相当する部分を全て０にする。
【００９４】
次に、高さ方向に垂直に持ち上げ（持ち上げた高さをｈとする）、文字上面の各構成要素のインデックスドサーフェースデータのうち、点列座標データを３次元に拡張し、ｚ座標値に相当する部分を全てｈにする。同様に、元の外周の点列の点列座標データを３次元に拡張した上点列を生成し、ｚ座標値に相当する部分を全てｈにする。３次元に拡張した上面及び下面の各構成要素のインデックスドサーフェースデータは文字形状データ出力部１２に出力される（但し、最後に述べる鋳型タイプのべベル形状を除く）。
【００９５】
図１１は、べベル形状の外形及びべベル形状の中間外周の生成方法を説明するための図である。
図１１（ａ）は、最も単純なベベル形状の外形を示した図である。図１１（ａ）では、文字の上下面の間に中間外周１２２０を生成し、文字の側面を斜めに切ったときの断面が凸六角形となるようにして、べベル形状を成形させている。この場合、文字の外側の中間外周１２２０は、文字の上面（または下面）の外周１２１０（又は１２３０）を拡大して生成し、文字穴の中間外周は、文字の上面（または下面）の穴外周を縮小して生成する。
【００９６】
その他のべベル形状としては、上記図１１（ａ）とは逆に、文字の側面を斜めに内側に切り、その断面が窪んだ凹六角となるようにしてべベル形状を成形させる場合が考えられる。この場合、文字の外側の中間外周は、文字の上面（または下面）の外周１２１０（又は１２３０）を縮小して生成し、文字穴の中間外周は、文字の上面（または下面）の穴外周を拡大して生成する。文字の外側の中間外周と文字穴の中間外周との組合せとしては、他に、文字外形、文字穴ともに拡大して生成した場合、文字外形、文字穴ともに縮小して生成した場合などがある。
【００９７】
以下では、中間外周を生成する方法について、図１１（ｂ）及び図１２のフローチャートを参照しながら説明する。
【００９８】
上記のように、中間外周を生成するためには、各構成要素の外周を拡大または縮小して生成する必要がある。中間外周は、構成要素の外周の法線ベクトルを求め、構成要素の外周の点列の点を法線方向へ移動（拡大の場合は、法線ベクトルを正の方向へ、縮小の場合は負の方向へ移動）することによって得られる。構成要素の外周上の点を、Ｐ0，Ｐ1，・・・，Ｐnとした場合の中間外周の生成方法を以下で説明する。
【００９９】
（１）ベクトルｐi＝ＰiＰi+1１３４０（添字ｉの点を始点とし、次の添字ｉ＋１の点を終点としたベクトル）を求める。但し、最後に求まるベクトルは、ｐn＝ＰnＰ0（添字が最後の外周上の点を始点とし、最初の点を終点としたベクトル）とする（Ｓ１３０１）。
【０１００】
（２）各ベクトルｐi＝（ｐix，ｐiy）の法線ベクトルＮi＝（Ｎix，Ｎiy）１３４１を求める（Ｓ１３０２）。法線ベクトルの求め方は以下の通りである。但し、法線ベクトルは２通りある。
（ｐix＊ｐiy≠０のとき）：
Ｎix＝±１／（１＋（ｐix／ｐiy）**2）**(1/2)，
−Ｎiy＝±（ｐix／ｐiy）×１／（１＋（ｐix／ｐiy）**2）**(1/2)
（ｐix＝０，ｐiy≠０のとき）：
Ｎix＝±１，Ｎiy＝０
（ｐix≠０，ｐiy＝０のとき）：
Ｎix＝０，Ｎiy＝±１
上記で求めた、２通りの法線ベクトルのうち、以下の条件を満たす方を選択する。
（条件式）：ｐix＊Ｎiy−ｐiy＊Ｎix＞０
【０１０１】
（３）外周の各点Ｐｉに対して、法線ベクトルＮＰi＝（ＮＰxi，ＮＰyi）を以下の式によって求める（Ｓ１３０３）。
ＮＰi＝（Ｎi-1＋Ｎi）／｜｜Ｎi-1＋Ｎi｜｜
＝（（Ｎi-1x＋Ｎix）／（（Ｎi-1x＋Ｎix）**2＋（Ｎi-1y＋Ｎiy）
**2））**(1/2)，（Ｎi-1y＋Ｎiy）／（（Ｎi-1x＋Ｎix）**2
＋（Ｎi-1y＋Ｎiy）**2））**(1/２)
但し、ＮＰ0については、以下の通りとする。
ＮＰ0＝（Ｎn＋Ｎ0）／｜｜Ｎn＋Ｎ0｜｜
＝（（Ｎnx＋Ｎ0x）／（（Ｎnx＋Ｎ0x）**2
＋（Ｎny＋Ｎ0y）**2））**(1/2)，
（Ｎny＋Ｎ0y）／（（Ｎnx＋Ｎ0x）**2＋（Ｎny＋Ｎ0y）**2））
**(1/2)）
【０１０２】
（４）外周を拡大／縮小する量をＬとしたとき、次のαｉを算出する（Ｓ１３０４）。但し、具体的な拡大／縮小量Ｌについては後述する。
αi＝Ｌ／ｃｏｓθi＝Ｌ／（ＮｐixＮix＋ＮｐiyＮiy）
但し、構成要素の外周の場合，上式の分母が０以下になることはない。従って、もし０以下になった場合は、異常が起こっている。
【０１０３】
（５）外周の各点Ｐｉに対応する中間外周の点をＰｉ'１２４２とすると、Ｐｉ'を以下の式によって求める。これらが拡大した中間外周を構成する点列になる（Ｓ１３０６）。
Ｐi'＝Ｐi＋αiＮＰi
縮小の場合の中間外周の点をＰi'については、
Ｐi'＝ＰiαiＮＰi
によって求める（Ｓ１３０７）。
【０１０４】
このように生成された中間外周の点列と上点列、下点列を用いて、側面形状の生成方法を図１１（ａ）を参照しながら説明する。まず、中間外周の点列を３次元に拡張し、ｚ座標値をここでは半分のｈ／２とする（この場合、ｚ座標値を０とｈの間の任意の値に設定することが可能である）。次に、上点列Ｐn，Ｐn+1に対応する中間外周の点列をＰcn，Ｐcn+1，下点列をＰn'，Ｐn+1'とすると、上面の外周と中間外周を接続することによって生成される側面は、反時計回りの場合「ＰnＰn+1Ｐcn+1Ｐcn」で、中間外周と下面の外周の接続で生じる側面は、「ＰcnＰcn+1Ｐn+1'Ｐn'」となる。
【０１０５】
従って、上面の外周と中間外周から生成される側面のインデックスドサーフェースデータは、上点列（個数ｎ）に中間外周の点列をアペンドした点列Ｑ1，・・・，Ｑn，Ｑn+1，・・・，Ｑ2nを構成し、反時計回りの場合は、インデックスをＱi，Ｑi+1，Ｑi+n+1，Ｑi+nとして順次構成する。同様に、中間外周と下面の外周から生成される側面のインデックスドサーフェースデータについても生成できる。
【０１０６】
次に、上記の中間外周を生成する場合の発展形として、中間外周を２つ生成し、文字外周の上面及び下面の端の角を削った形状、いわゆる典型的なベベル形状の生成方法について、図１３を参照しながら説明する。なお、この場合の中間外周の生成方法も、基本的には上記の生成方法と同様である。
【０１０７】
図１３（ａ）は、文字の上面及び下面よりも側面が突き出している、いわゆる凸状の側面を形成する２つの中間外周を生成する場合の概要を示す図である。図１３（ａ）において、生成する２つの中間外周のうち、上面に近い方を第１中間外周１４１１、下面に近い方を第２中間外周１４１２とする。次に、ベベル形状の削ぎ落とし角度を、図１３（ａ）に示したように、上面外周に対する削ぎ落とし角度をθ1、下面外周に対する削ぎ落とし角度をθ2とする。この場合、２つの中間外周１４１１、１４１２は、ともに上面の文字外周１４１０に対して拡大を行うこととなる。
【０１０８】
図１３（ａ）から分かるように、上面の文字外周１４１０を拡大して中間外周を生成する場合は、ｔａｎθi＝ｈi／Ｌiであるので、ｈi＝Ｌiｔａｎθiとなる。但し、この場合は、ｉ＝１または２である。以上の計算を行った後、ｈ0＝ｈ−（ｈ1＋ｈ2）を算出し、第１中間外周１４１１の点列のｚ座標値をｈ0＋ｈ2（＝ｈ−ｈ1）とし、第２中間外周１４１２の点列のｚ座標値をｈ２として３次元化した点列を生成する。側面の生成については、中間外周が１つ増えたことに注意すれば、上記で説明した、中間外周が１つの場合の側面を生成する方法と同様に行うことが可能となる。
【０１０９】
図１３（ｂ）は、上記図１３（ａ）とは逆に、凹状の側面を形成する２つの中間外周を生成する場合の概要を示す図である。この場合は、上面の文字外周１４２０に対して縮小を行うことによって２つの中間外周を生成することとなるが、基本的には、上記図１３（ａ）と同様の方法によって生成が可能である。
【０１１０】
次に、側面の形状が曲線の場合に、この曲線を多角形で近似し、その多角形に合わせて多数の中間外周を発生させて側面を生成する方法について、図１４に基づいて説明する。ここでは中間外周の生成を制御する曲線は、基本的には２次曲線とし、例えば円や放物線、スプライン曲線を想定して説明する。
【０１１１】
まず、図１４（ａ）に示したように、側面の形状が半円状に凸となっている場合について説明する。なお、拡大をＬ、立ち上げる高さをｈ(≧２Ｌ)、生成する中間外周の数を２ｎ＋１とする。なお、図１４（ａ）の例では、ｎ＝２とする。
【０１１２】
図１４（ａ）から分かるように、生成される中間外周は、高さｈ／２における中央の中間外周１５１１に関して対称となる。従って、中央の中間外周１５１１より上側（または下側）の中間外周を生成すれば、下側（または上側）の中間外周は対称性を利用して生成すれば良い。側面の生成については、上記に述べた方法によって生成する。中間外周の生成で問題となるのは、中央の中間外周１５１１以外の拡大量とそのｚ座標値を算出することである。これについて、図１４（ｃ）を参照しながら、その算出方法について説明する。
【０１１３】
図１４（ｃ）において、中央の中間外周１５１１を中間外周０とし、以降その両側に離れる順に、中間外周１，２，・・・とする。中間外周ｉの拡大量Ｌｉ、ｚ座標値ｚｉは、以下の式により算出することができる（ここで、べベル円の半径をｒとする）。
Ｌi＝Ｌ−ｒ（１−ｃｏｓ（２ｉθ／（ｎ＋１）））
ｚi＝ｈ／２±ｈi＝ｈ／２±ｒｓｉｎ（２ｉθ／（ｎ＋１））
ｒ＝１／２Ｌ（Ｌ**2＋ｈ**2／４）
θ＝ａｒｃｔａｎ（２Ｌ／ｈ）
但し、ｉ＝０，１，・・・，ｎで、ｚiはプラスのときが上側の中間外周のｚ座標で、マイナスのときが下側の中間外周のｚ座標を示す。
【０１１４】
図１４（ｂ）は、側面の形状が凹の場合のべベル形状の外観を示す。側面の形状が凹の場合は、Ｌｉについては符号をマイナスにして縮小量とするが、ｚiについては、上記図１４（ａ）の凸の場合と同じである。
【０１１５】
次に、側面のべベル形状が放物線の場合について説明する。円の場合と同様に、生成する中間外周の個数を２ｎ＋１、中間外周ｉの拡大／縮小量をＬi、ｚ座標値をｚi，ｉ＝０，１，・・・，ｎ，とすると、凸の場合は、
Ｌi＝Ｌ（１−ｉ**2／（ｎ＋１）**2）
ｚi＝ｈ／２±ｉｈ／２（ｎ＋１）＝ｈ（１±ｉ／（ｎ＋１））／２
但し、ｚiは、その値がプラスのときが上側の中間外周のｚ座標、マイナスのときが下側の中間外周のｚ座標を示す。なお、以上は凸の場合だが、凹の場合は、Ｌｉについては符号をマイナスにして縮小量とするが、ｚｉについては凸の場合と同じである。
【０１１６】
２次スプライン曲線を用いる場合は、下面と上面との間に仮想的にｚ座標値が０〜ｈのパラメータを導入することとする。本装置２０１の操作者によって入力された上面と下面との間の適当な制御点と、上記パラメータとに基づいてスプライン曲線を発生させる。但し、上面と下面部の端点は０に固定する。スプライン曲線によって凸／凹となった量が拡大／縮小量で、パラメータが有するｚ座標値が中間外周のｚ座標値となる。以上のように、２次スプライン曲線に合わせて中間外周を発生させ、文字の側面を上記と同様の方法で生成する。
【０１１７】
最後に、鋳型タイプのベベル形状の側面を生成させる場合について、図１５に基づいて説明する。鋳型タイプのベベル形状の側面を生成させる場合も、上述した中間外周を２つ発生させる方法を変形して適用することによって生成が可能である。以下では、３段の鋳型タイプのべベル形状の側面を生成する場合の手順を示す。
【０１１８】
（１）元の構成要素の外周と同一（但し、ｚ座標値は同一ではない。）の中間外周１６１０，１６１１と、元の外周を縮小した２つの中間外周１６２０、１６２１と、元の外周を拡大した２つの中間外周１６３０、１６３１を上記に述べた方法で生成する。
【０１１９】
（２）立ち上げ高さをｈ（このｈは、外部より入力するかデフォルト値を使用する）としたとき、縮小した２つの中間外周のｚ座標値をそれぞれｈ、２ｈ／３とし、元の外周と同一の２つの中間外周１６１０、１６１１のｚ座標値をそれぞれ２ｈ／３、ｈ／３とし、拡大した２つの中間外周のｚ座標値をそれぞれｈ／３、０とする。
【０１２０】
（３）縮小して生成した中間外周のうち、上位の中間外周により構成される面を構成要素の上面とし、それらの中間外周の点列のｚ座標値をｈにする（ｚ座標値がｈの縮小した中間外周によって上面を生成する）。
（４）拡大して生成した中間外周のうち、下位の中間外周により構成される面を構成要素の下面とし、それらの中間外周の点列のｚ座標値を０にする（ｚ座標値が０の拡大した中間外周によって下面を生成する）。
【０１２１】
（５）縮小して生成した２つの中間外周間において対応するそれぞれの点を結ぶことにより、上記と同様の方法で最上位の段の側面１６２２を生成する。
（６）縮小して生成した中間外周（ｚ座標値が２ｈ／３）と、元の外周と同一の中間外周のうち上位の中間外周（ｚ座標値が２ｈ／３）との対応点を結ぶことによって、上記と同様の方法で、中段の上面（水平面）を生成する。
【０１２２】
（７）元の外周と同一の２つの中間外周間において対応それぞれの点をむすぶことにより、上記と同様の方法で中段の側面１６１２を生成する。
（８）元の外周と同一の中間外周のうち下位の中間外周（ｚ座標ｈ／３）と拡大して生成した中間外周（ｚ座標値がｈ／３）との対応点を結ぶことにより、上記の方法と同様の方法で下段の上面（水平面）を生成する。
（９）拡大して生成した２つの中間外周間において対応するそれぞれの点を結ぶことにより、上記と同様の方法で最下位の段の側面１６３２を生成する。
【０１２３】
なお、上記方法により上面と下面を生成する際は、元の構成要素に対する三角形分割を行っておけば、外周のインデックスの対応関係自体は変化しないので、インデックスドサーフェースデータの点列座標データ部分だけに対して縮小、または拡大するだけで良い。また、この場合は、上記、元の構成要素の上面と下面のインデックスドサーフェースデータは、文字形状データ出力部１２には出力せず、ここで生成されたインデックスドサーフェースデータを生成後にまとめて送る。
【０１２４】
文字形状データ出力部１２では、べベル形状側面生成部１１から送られてきた、文字の各構成要素の上下面のインデックスドサーフェースデータと、各構成要素のべベル形状側面のインデックスドサーフェースデータを階層的な記述によって一まとめにして、外部へ出力する。なお、データ形式を変換する場合には、当該データ形式へ変換してから出力する。
【０１２５】
図１６（ａ）〜（ｄ）は、本実施の形態に係る４種類のべベル形状の例を示す。図１６（ａ）は、前記実施の形態１において、第１の方法として文字の上面を高さ方向に垂直に持ち上げた場合の側面の形状であり、「べベルなし」の場合である。図１６（ｂ）は、上記図１３（ａ）の形状と同様に、側面の断面が凸六角形状に突き出たべベル形状を生成した例である。図１６（ｃ）は、中間外周を２つ生成し、文字の上面及び下面の外周に対する削ぎ落とし角度が等しい場合の側面の断面が凸台形状のべベル形状を生成した例である。図１６（ｄ）は、上記図１５に示した「鋳型タイプ」のべベル形状の例である。
以上のように、中間外周を生成し、これに基づいて側面を生成するため、自動的により多様な３次元文字の側面形状を実現することが可能となる。
【０１２６】
（実施の形態３）
実施の形態３では、上記の文字外周点列や穴外周点列の点間を適当な点で補間することにより、より精細な３次元形状を可能とする場合の実施例について述べる。なお、本実施の形態では、上述した実施の形態と同じ構成部分についての説明は省略する。
【０１２７】
図１７は、本実施の形態３における３次元文字データ生成装置３０１の機能構成を示すブロック図である。３次元文字データ生成装置３０１は、文字外周データ補間部２１及び文字形状上下面凸ポリゴン再分割部２２及びテクスチャ座標生成部２４を新たに備え、前記文字形状側面生成部６に代えて文字形状側面生成部２３を、文字形状データ出力部７に代えて文字形状データ出力部２５を備える。以上のように構成される３次元文字データ生成装置３０１について、以下、詳細に説明する。
【０１２８】
文字外周データ補間部２１は、文字形状構造解析部４から出力される、各構成要素の文字外周点列や穴外周点列に、適当な点を補間して３次元で表現する文字の形状の精細化を行う。文字外周点列または穴外周点列に点を補間する方法は以下の通りである。
【０１２９】
（１）文字形状構造解析部４から送られてくる、各構成要素の文字外周点列、穴外周点列に対して、連続する２つの点を接続した場合の距離の総和である総和距離を算出する。また、その場合の点列の総個数を算出する。
（２）上記総和距離をその総個数で割り、平均距離を算出し、算出した平均距離を任意の細分化レベルに応じた数で除することにより基準距離を算出する。
（３）元の文字外周点列または穴外周点列のうち、連続する２つの点の間の距離が基準距離より大きい場合は、基準距離以下となるように中間に点を発生させる。発生させる点は、文字外周データ記憶部３に記憶されているアウトラインデータに指定されている、上述した直線によって接続したライン、又は曲線によって接続したライン上に発生させる。なお、既存の点列の間に新たに点を付加した場合であっても、その並びを保持しながら（新たな点の点列番号を最後にするのではなく）点列番号を修正する。
【０１３０】
図１８は、「回」に対して、点列の間に新たに点を補間した場合の一例である。図１８においては、文字外周点列１９１１に対して１辺あたり３つの点を補間し、穴外周点列１９１２に対して１辺あたり２つの点を補間している。以下同様に、文字外周点列１９１３及び穴外周点列１９１４においては、１辺あたり１つの点を補間している。
【０１３１】
以上の方法のように、文字外周データ補間部２１において、点が補間され修正された各構成要素の外周データが文字形状上下面凸ポリゴン分割部５に送られる。文字形状上下面凸ポリゴン再分割部２２では、文字形状上下面凸ポリゴン分割部５で、各構成要素を上記のように三角形分割した三角形を、更に分割する。この再分割は、文字形状上下面凸ポリゴン分割部５で生成される三角形ポリゴンの頂点は文字の外周上にあるため、形状を曲げたりねじったりする場合に、外周の変形が直線的になってしまい、不自然な状況が生じる可能性が高い。このような不自然さを防ぐために再分割を行う。
【０１３２】
次に、三角ポリゴンを再分割する方法について、図１９〜図２１を参照しながら説明する。
図１９は、元の三角形を４つに再分割する方法における処理の流れを示すフローチャートである。
図２１（ａ）は、三角形の辺の中点を用いて内分割を行う方法を説明するための図である。
本実施の形態では、図２１（ａ）に示したような三角形の辺の中点を用いた内分割法によって行う。この内分割法は、三角形の各辺の中点を算出し、中点間を結んだ３つの線分によって、元の三角形を４つに分割するというものである。従って、三角形の個数は、分割する毎に４倍で増えていく。
【０１３３】
ここで、各構成要素に対して、文字形状上下面凸ポリゴン分割部５の前処理で接続化された外周の点列を｛Ｐ［０］，Ｐ［１］，・・・，Ｐ［ｎ］｝とし、文字外形の外周の点列を｛Ｐo［０］，Ｐo［１］，・・・，Ｐo［ｌ］｝、文字穴の外周の点列を｛Ｐh［ｘ］［０］，Ｐh［ｘ］［１］，・・・，Ｐh［ｘ］［ｋｘ］とする。
以下、インデックスの並びが、｛ａ，ｂ，ｃ｝の三角形ポリゴンに対する内分割法についてそのアルゴリズムを説明する。
【０１３４】
（１）｜ａ−ｂ｜，｜ｂ−ｃ｜，｜ｃ−ａ｜の値を計算する。
（２）｜ａ−ｂ｜＝１ならば、Ｐ［ａ］Ｐ［ｂ］の中点Ｐabを求め、Ｐab＝Ｐ［ｌａｓｔ＋１］として点列の最後に加え、インデックスｌａｓｔ＋１＝αを保持する。
（３）｜ａ−ｂ｜≠１かつ（ａ，ｂ）≠（ｌａｓｔｏｒｇ，０）＆（ａ，ｂ）≠（０，ｌａｓｔｏｒｇ）ならば（但し、ｌａｓｔｏｒｇは、分割操作前の点列のインデックスの最後の値）、Ｐ［ａ］Ｐ［ｂ］の中点が求められていないかチェックする。チェックの結果、求められていたらそのインデックスをαとして保持し、後述のチェックリストからその中点のデータを除去する。求められていない場合は、Ｐ［ａ］Ｐ［ｂ］の中点Ｐabを求め、Ｐab＝Ｐ［ｌａｓｔ＋１］として点列の最後に加え、インデックスｌａｓｔ＋１＝αを保持する。同時に、チェックリストにインデックスの組番号（ａ，ｂ）とαを保持する。従って、チェックリストは、インデックスの組番号とそれによって生成されたインデックスで構成され、チェックにおいてはインデックスの組番号を順不同で比較する。
【０１３５】
（４）｜ｂ−ｃ｜，｜ｃ−ａ｜についても、上記（２）、（３）を同様に行い、｜ｂ−ｃ｜についてはインデックスβ、｜ｃ−ａ｜についてはインデックスγを保持する。
（５）三角形を規定するインデックス列｛ａ，ｂ，ｃ｝を除去し、４つの三角形を規定するインデックス列｛ａ，α，γ｝，｛ｂ，β，α｝，｛ｃ，γ，β｝，｛α，β，γ｝を代わりに挿入する。
【０１３６】
次に、三角形の再分割に伴う、文字外形の外周の点列の再構成について説明する。元の文字外形の外周の点列に対して次の操作を行う。
（１）｛Ｐo［０］，Ｐo［１］，・・・，Ｐo［ｎ］｝に対して、Ｐo［Ｉ］Ｐo［Ｉ＋１］の中点を求め、それらをＷ［Ｉ］とする。但し、Ｉ＝０，１，・・・，ｎでＰｏ［ｎ＋１］＝Ｐo［０］とする。
（２）｛Ｐo［０］，Ｐo［１］，・・・，Ｐo［ｎ］｝のインデックスの数を２倍して、｛Ｐo［０］，Ｐo［２］，Ｐo［４］，Ｐo［６］，・・・，Ｐo［２ｎ］｝に変更し、Ｗ［Ｉ］をＰo［２Ｉ＋１］として挿入する。このようにしてできた新たな点列｛Ｐo［０］，Ｐo［１］，Ｐo［２］・・・，Ｐo［２ｎ］，Ｐo［２ｎ＋１］｝が、再分割された３角形により生成される新たな文字の外周の点列である。なお、文字穴の外周の点列場合も、文字外形の外周の点列の場合と同様の処理によって、再分割された３角形により生成される新たな文字穴の外周の点列が求められる。
【０１３７】
上記の内分割法は、元の三角形を４つに分割するというものなので、三角形の個数は４倍で増えていく。再分割を一度も行っていない最初の状態をレベル０とし、１度の再分割でレベルが１ずつあがるとすると、レベル０に対して、レベルｒでは三角形が４ｒ倍に増加する。
【０１３８】
上記の内分割法の処理では、三角形の再分割のレベルをｒにしようとすると、ｒ回の処理が必要になる。そこで、一気に２レベル以上、上げることができる方法について、図２０及び図２１（ｂ）を参照しながら説明する。
【０１３９】
図２０は、三角形の再分割のレベルをｒにしようとする場合の再分割方法における処理の流れを示すフローチャートである。
図２１（ｂ）は、三角形の再分割のレベルをレベル０からレベルｒに一気に上げた場合の様子を示す図である。
図２１（ｂ）において、α［Ｉ］はＰ［ａ］Ｐ［ｂ］の内分点Ｐab［α［Ｉ］］のインデックス（Ｉ＝０，１，・・・，２**ｒ−２）であり、Ｐab［α［Ｉ］］は、
Ｐab［α［Ｉ］］
＝｛（Ｉ＋１）Ｐ［ｂ］＋（２**ｒ−Ｉ−１）Ｐ［ａ］｝／２**ｒ
から算出できる。同様に、β［Ｉ］はＰ［ｂ］Ｐ［ｃ］の内分点Ｐbc［β［Ｉ］］のインデックス（Ｉ＝０，１，・・・，２ｒ−２）であり、Ｐbc［β［Ｉ］］は、
Ｐbc［β［Ｉ］］
＝｛（Ｉ＋１）Ｐ［ｃ］＋（２**ｒ−Ｉ−１）Ｐ［ｂ］｝／２**ｒ
から算出できる。また、γ［Ｉ］はＰ［ｃ］Ｐ［ａ］の内分点Ｐca［γ［Ｉ］］のインデックス（Ｉ＝０，１，・・・，２ｒ−２）であり、Ｐca［γ［Ｉ］］は、
Ｐca［γ［Ｉ］］
＝｛（Ｉ＋１）Ｐ［ａ］＋（２**ｒ−Ｉ−１）Ｐ［ｃ］｝／２**ｒ
から算出できる。ξ［Ｉ］［ｋ］はＰ［α］Ｐ［γ］の内分点Ｐαγ［ξ［Ｉ］［ｋ］］のインデックス（Ｉ＝０，１，・・・，２**ｒ−３，０≦ｋ≦Ｉ，）であり、Ｐαγ［ξ［Ｉ］［ｋ］］は、
Ｐαγ［ξ［Ｉ］［ｋ］］
＝｛（Ｉ＋１−ｋ）Ｐ［α［Ｉ＋１］］
＋（ｋ＋１）Ｐ［γ［２**ｒ−Ｉ−３］］｝／（Ｉ＋２）
から算出できる。以上の内分点の発生に基づいて、アルゴリズムを説明する。
【０１４０】
（１）｜ａ−ｂ｜，｜ｂ−ｃ｜，｜ｃ−ａ｜の値を計算する。
（２）｜ａ−ｂ｜＝１ならば、Ｐ［ａ］Ｐ［ｂ］の上記の内分点Ｐab［α［Ｉ］］（Ｉ＝０，１，・・・，２**ｒ−２）を求め、Ｐab＝Ｐ［ｌａｓｔ＋１＋Ｉ］として点列の最後に加えていき、インデックスｌａｓｔ＋１＋Ｉ＝α［Ｉ］を保持する。
（３）｜ａ−ｂ｜≠１かつ（ａ，ｂ）≠（ｌａｓｔｏｒｇ，０）＆（ａ，ｂ）≠（０，ｌａｓｔｏｒｇ）ならば（但し、ｌａｓｔｏｒｇは、分割操作前の点列のインデックスの最後の値）、Ｐ［ａ］Ｐ［ｂ］の内分点が求められていないかチェックする。チェックの結果、求められていたらそのインデックスをα［Ｉ］として保持し、後述のチェックリストからその内分点のデータを除去する。求められていない場合は、Ｐ［ａ］Ｐ［ｂ］の上記の内分点Ｐab［α［Ｉ］］（Ｉ＝０，１，・・・，２**ｒ−２）を求め、Ｐab＝Ｐ［ｌａｓｔ＋１＋Ｉ］として点列の最後に加えていき、インデックスｌａｓｔ＋１＋Ｉ＝α［Ｉ］を保持する。同時に、チェックリストにインデックスの組番号（ａ，ｂ）とα［Ｉ］を保持する。従って、チェックリストは、インデックスの組番号とそれによって生成されたインデックスで構成され、チェックにおいてはインデックスの組番号を順不同で比較する。
【０１４１】
（４）｜ｂ−ｃ｜，｜ｃ−ａ｜についても，上記（２）、（３）を同様に行い、Ｐ［ｂ］Ｐ［ｃ］の内分点とＰ［ｃ］Ｐ［ａ］の内分点を求め、点列座標データに必要な場合は加えていく。また必要に応じて、チェックリストにインデックスの組番号（ｂ，ｃ）とβ［Ｉ］、インデックスの組番号（ｃ，ａ）とγ［Ｉ］を保持する。
（５）ｒ＞１のときは、上記のＰ［α］Ｐ［γ］の内分点Ｐαγ［ξ［Ｉ］［ｋ］］を求めて点列の最後に加えていき、インデックスｌａｓｔ＋１＋Ｉ（Ｉ＋１）／２＋ｋ＝ξ［Ｉ］［ｋ］を保持する。但し、Ｉ＝０，１，・・・，２**ｒ−３，０≦ｋ≦Ｉである。
【０１４２】
（６）ｒ＝１のときは、三角形を規定するインデックス列｛ａ，ｂ，ｃ｝を除去し、４個の三角形を規定するインデックス列｛ａ，α［０］，γ［０］｝，｛ｂ，β［０］，α［０］｝，｛ｃ，γ［０］，β［０］｝，｛α［０］，β［０］，γ［０］｝を代わりに挿入する。
【０１４３】
（７）ｒ＞１のときは、三角形を規定するインデックス列｛ａ，ｂ，ｃ｝を除去し、以下の４ｒ個の三角形を規定するインデックス列を代わりに挿入する。但し、Ｉ＝０，１，・・・，２**ｒ−１で、Ｉに応じて処理を行う。
・Ｉ＝０のときは、｛ａ，α［０］，γ［２**ｒ−２］｝を代わりに挿入する。
・Ｉ＝１のときは、｛α［０］，α［１］，ξ［０］［０］｝，｛α［０］，ξ［０］［０］，γ［２**ｒ−２］｝，｛γ［２**ｒ−２］，ξ［０］［０］，γ［２**ｒ−３］｝。
・Ｉ＝２のときは、｛α［１］，α［２］，ξ［１］［０］｝，｛α［１］，ξ［１］［０］，ξ［０］［０］｝，｛ξ［０］［０］，ξ［１］［０］，ξ［１］［１］｝，｛ξ［０］［０］，ξ［１］［１］，γ［２**ｒ−３］｝，｛γ［２**ｒ−３］，ξ［１］［１］，γ［２**ｒ−４］｝を代わりに挿入する。
・３≦Ｉ≦２ｒ−２のときは、｛α［Ｉ−１］，α［Ｉ］，ξ［Ｉ−１］［０］｝，｛α［Ｉ−１］，ξ［Ｉ−１］［０］，ξ［Ｉ−２］［０］｝の後、｛ξ［Ｉ−２］［ｋ］，ξ［Ｉ−１］［ｋ］，ξ［Ｉ−１］［ｋ＋１］｝と｛ξ［Ｉ−２］［ｋ］，ξ［Ｉ−１］［ｋ＋１］，ξ［Ｉ−２］［ｋ＋１］｝の組（但し，０≦ｋ≦Ｉ−３）の繰り返しの後（つまり、繰り返しはＩ−２回起こる）、｛ξ［Ｉ−２］［Ｉ−２］，ξ［Ｉ−１］［Ｉ−２］，ξ［Ｉ−１］［Ｉ−１］｝，｛ξ［Ｉ−２］［Ｉ−２］，ξ［Ｉ−１］［Ｉ−１］，γ［２**ｒ−１−Ｉ］｝，｛γ［２**ｒ−１−Ｉ］，ξ［Ｉ−１］［Ｉ−１］，γ［２**ｒ−２−Ｉ］｝で終わるインデックス列を代わりに挿入する。
【０１４４】
・Ｉ＝２**ｒ−１のときは、｛α［２**ｒ−２］，ｂ，β［０］｝，｛α［２**ｒ−２］，β［０］，ξ［２**ｒ−３］［０］｝の後、｛ξ［２**ｒ−３］［ｋ］，β［ｋ］，β［ｋ＋１］｝と｛ξ［２**ｒ−３］［ｋ］，β［ｋ＋１］，ξ［２**ｒ−３］［ｋ＋１］｝の組（但し、０≦ｋ≦２**ｒ−４）の繰り返しの後（つまり、繰り返しは２**ｒ−３回起こる）、｛ξ［２**ｒ−３］［２**ｒ−３］，β［２**ｒ−３］，β［２**ｒ−２］｝｛ξ［２**ｒ−３］［２**ｒ−３］，β［２**ｒ−２］，γ［０］｝，｛γ［０］，ξβ［２**ｒ−２］，ｃ｝で終わるインデックス列を代わりに挿入する。
【０１４５】
次に、文字外形の外周の点列の再生成について以下に説明する。
（１）｛Ｐo［０］，Ｐo［１］，・・・，Ｐo［ｎ］｝に対して、これを２**ｒ分割したときのＰo［Ｉ］Ｐo［Ｉ＋１］の内分点を求め、それらをＷ［Ｉ］［ｋ］とする。但し、Ｉ＝０，１，・・・，ｎで、特に、Ｐo［ｎ＋１］＝Ｐo［０］とする。また、ｋ＝０，１，・・・，２**ｒ−２で、Ｗ［Ｉ］［ｋ］は以下の式によって求める。
0004028979.tif 000003
【０１４６】
（２）｛Ｐo［０］，Ｐo［１］，・・・，Ｐo［ｎ］｝のインデックスを２**ｒ倍して、｛Ｐo［０］，Ｐo［２**ｒ］，Ｐo［２×２**ｒ］，Ｐo［３×２**ｒ］，・・・，Ｐo［ｎ×２**ｒ］｝に変更し、Ｗ［Ｉ］［ｋ］をＰo［Ｉ×２**ｒ＋ｋ＋１］として挿入する（但し、Ｉ＝０，１，・・・，ｎ，ｋ＝０，１，・・・，２**ｒ−２）。
【０１４７】
このようにしてできた新たな点列｛Ｐo［０］，Ｐo［１］，Ｐo［２］，Ｐo［３］，Ｐo［４］・・・，Ｐo［ｎ×２**ｒ］，Ｐo［ｎ×２**ｒ＋１］，Ｐo［（ｎ＋１）×２**ｒ−１］｝が、再分割された３角形により生成される新たな文字外形の外周の点列である。文字穴の外周の点列の場合も、同様の処理によって、再構成できる。
【０１４８】
文字形状上下面凸ポリゴン再分割部２２は、元の０レベルのデータを保持しておけば、常に０レベルから再分割を行うことで、一旦分割した三角形を粗い三角形に戻すという可逆的な分割が可能である。例えば、ｒレベルに上げた時、ｐレベルに下げたいならば、ｒレベルのデータを破棄して、新たに０レベルからｐレベルのデータを生成すれば、見かけ上はｒレベルからｐレベルに移行したことになる。
【０１４９】
文字形状側面生成部２３は、前記実施の形態１における文字形状側面生成部６、及び実施の形態２のべベル形状側面生成部１１と同様の処理により、文字の各構成要素の上下面と側面のインデックスドサーフェースデータを生成し、このデータをテクスチャ座標生成部２４に出力する。
【０１５０】
テクスチャ座標生成部２４は、各構成要素を下面と上面に対し、これを含む最小の正方形を生成する。この正方形の最下点と構成要素の下面の最下点とが原点で重なるように平行移動し、これらの平行移動後の点列の座標を求め、求められた座標値を正方形の辺の長さで除し、その結果をマッピング座標とする。これは、外包正方形を正規化したときの座標に相当する。側面に対しては、外周形状や穴形状を構成する閉曲線に対して周回長（点列における連続する２点間の距離の総和）を求め、開始点から各点までの２点間の距離と周回長の比を、その開始点か各点までの距離を表すパラメータ（０≦ｓ≦１）として割り振る（開始点は０と１が割り振られる）。高さ方向に関しては、下面に対してはｔ＝０で上面にはｔ＝１を割り付ける。
【０１５１】
なお、各構成要素（または全ての構成要素）を含む円筒を設け、この円筒に円筒座標系を定義し、構成要素の頂点を円筒の中心座標から投影し円筒座標系における座標を用いて、テクスチャ座標を決定できる。但し、円筒座標系は正規化をする必要がある。また、各構成要素（または全ての構成要素）を含む球を設け、この球に極座標系を定義し、構成要素の頂点を球の中心から投影した極座標系における座標値を用いてもテクスチャ座標を決定できる。但し、極座標系は正規化する必要がある。
【０１５２】
以上のように求めたテクスチャ座標については、インデックスドサーフェースデータの外周の点列座標データの順序と一致するように当該インデックスドサーフェースデータに各々付加し、文字形状データ出力部２５へ出力する。文字形状データ出力部２５では、テクスチャ座標生成部２４から送られてきた、文字の各構成要素の上下面のテクスチャ座標付のインデックスドサーフェースデータと、各構成要素の側面のテクスチャ座標付のインデックスドサーフェースデータを階層的な記述によって一まとめにして、外部へ出力する。なお、データ形式を変換する場合には、当該データ形式へ変換してから出力する。
以上のように、文字外周点列や穴外周点列の点間を適当な点で補間し、これに基づいてポリゴン分割を行うので、より精細な３次元文字を作成することが可能となる
【０１５３】
（実施の形態４）
上記の実施の形態１では、３次元の文字を生成する実施例について述べたが、実施の形態４では、３次元の文字の下部に円柱状等の台座を設ける場合の実施例について述べる。なお、本実施の形態では、上記実施の形態１と同じ構成部分についての説明は省略する。
【０１５４】
図２２は、実施の形態４における３次元文字データ生成装置４０１の機能構成を示すブロック図である。３次元文字データ生成装置４０１は、台座形状生成部３５を新たに備え、文字コード入力部１に代えて文字台座コード入力部３１を、文字外周データ取得部２に代えて文字外周台座形状取得部３２を、文字外周データ記憶部３に代えて文字外周台座形状記憶部３３を、文字形状構造解析部４に代えて文字台座形状構造解析部３４を、文字形状側面生成部６に代えて文字形状側面生成部３６を、文字形状データ出力部７に代えて文字台座形状データ出力部３７を備える。以上のように構成される３次元文字データ生成装置４０１について、以下、詳細に説明を行う。
【０１５５】
文字台座コード入力部３１は、実施の形態１の文字コード入力部１と同様に、いわゆるキーボードやマウスなどの入力装置で、これらの入力信号を変換し、ＡＳＣＩＩコードやＪＩＳコードなどの文字コードのほか、台座の形状を指定するための台座コードを生成する。文字台座コード入力部３１で生成された文字コードと台座コードは、文字外周台座形状取得部３２へ出力される。
【０１５６】
文字外周台座形状取得部３２は、文字台座コード入力部３１から受信した文字コードに対応する文字のアウトラインデータと、台座コードに対応する台座の３次元形状データを文字外周台座形状記憶部３３から取得する。上記実施の形態１の文字外周データ記憶部３と同様に、文字のアウトラインデータは、予め文字外周台座形状記憶部３３に文字コードに対応して記憶されている。また、台座の３次元形状データに関しても、台座コードに対応した台座の３次元形状データが、文字外周台座形状記憶部３３に予め記憶されている。文字外周台座形状取得部３２で取得された文字のアウトラインデータと台座の３次元形状データは、文字台座形状構造解析部３４に出力される。なお、台座の３次元形状データには、どの面が台座の上面（以下、「台座上面」という。）であるが定義されているものとする。
【０１５７】
文字台座形状構造解析部３４では、文字に関しては、上記の実施の形態１の文字形状構造解析部４と同様に、文字の構造解析結果情報を生成する。文字の構造解析結果情報としては、文字穴毎にその穴を包含する唯一の文字部品が特定され、その包含関係を表す情報が、上記実施の形態１と同様の方法によって作成される。
【０１５８】
文字外周台座形状構造解析部３４では、その他に文字全体のバウンダリーボックスとその中心座標（以下「文字中心座標」という。）、及び台座の３次元形状のバウンダリーボックス（直方体形状とする）と台座上面に対応するバウンダリーボックスの中心座標（以下「台座中心座標」という。）を求め、文字のバウンダリーボックスの中心と台座上面に対応するバウンダリーボックスの中心とが一致するように移動する。さらに、予め定めた余白量を文字のバウンダリーボックスに加算した拡大長方形を求め、これが移動された台座上面に対応するバウンダリーボックスの面に含まれるように、最小の台座スケーリング量を算出する。文字の構造解析結果情報は、文字形状上下面凸ポリゴン分割部５に送られ、実施の形態１と同様に処理される。また、文字のバウンダリーボックスの中心座標と台座中心座標、及び台座スケーリング量が、台座形状生成部３５に出力される。
【０１５９】
台座形状生成部３５では、文字台座形状構造解析部３４から出力される台座スケーリング量で台座の３次元形状データをスケーリング変換し、その変換後に得られる台座中心座標が、文字中心座標と一致するように、台座を平行移動し、移動後の台座の３次元の座標値を修正する。これらの変換後のデータは文字台座形状データ出力部３７に出力される。
【０１６０】
文字形状側面生成部３６では、上記実施の形態１の文字形状側面生成部６、及び実施の形態２のべベル形状側面生成部１１と同様に、各構成要素に基づいて、上面、下面、側面及びべベル形状側面を生成し、文字台座形状データ出力部３７に送られる。
【０１６１】
文字台座形状データ出力部３７では、台座形状生成部３５と文字形状側面生成部３６から送られてきた、台座の３次元形状データと文字の各構成要素に基づく上面及、下面及び側面のインデックスドサーフェースデータを階層的な記述によって一まとめにして、外部へ出力する。その際、データ形式を変換する必要がある場合であっても、一旦当該データ形式に変換を行い、これを変換する。
【０１６２】
図２３は、本実施の形態４によって生成された台座つきの３次元の漢字「田」の外観を示す。
以上のように、台座の３次元形状データに基づいて３次元文字の下部に円柱状等の台座を設けることを可能にしたので、より多彩な装飾を施した３次元文字を表示することができる。
【０１６３】
（実施の形態５）
上記実施の形態４では、台座の３次元形状データに基づいて台座付きの３次元文字を生成する場合について示したが、実施の形態５では、台座のアウトラインデータに基づいて台座付きの３次元文字を生成する場合の実施例について述べる。なお、本実施の形態では、上記実施の形態４と重複する構成部分についての説明は省略する。
【０１６４】
図２４は、本実施の形態５における３次元文字データ生成装置５０１の機能構成を示すブロック図である。３次元文字データ生成装置５０１は、文字台座コード入力部４１、文字台座外周データ取得部４２、外周データ記憶部４３、文字台座形状構造解析部４４、文字台座形状面凸ポリゴン分割部４５、文字台座形状側面生成部４６、文字台座形状データ出力部４７によって構成される。以上のように構成される３次元文字データ生成装置５０１について、以下、詳細に説明を行う。
【０１６５】
文字台座コード入力部４１は、実施の形態１の文字コード入力部１と同様に、いわゆるキーボードやマウスなどの入力装置で、これらの入力信号を変換し、ＡＳＣＩＩコードやＪＩＳコードなどの文字コードのほか、台座のアウトラインデータを指定するための台座コードを生成する。文字台座コード入力部４１で生成された文字コードと台座コードは、文字台座外周データ取得部４２へ送られる。
【０１６６】
文字台座外周データ取得部４２は、文字台座コード入力部４１から受け取った文字コードに対応する文字のアウトラインデータと、台座コードに対応する台座のアウトラインデータを、外周データ記憶部４３から取得する。文字のアウトラインデータに関しては、実施の形態１の文字外周データ記憶部３と同様に、予め外周データ記憶部４３に文字コードに対応付けられて記憶されている。また、台座のアウトラインデータに関しても、台座コードに対応付けられて外周データ記憶部４３に予め記憶されている。文字台座外周データ取得部４２で取得された文字のアウトラインデータと台座のアウトラインデータは、文字台座形状構造解析部４４に出力される。ここで、台座に穴が形成されている場合は、その穴を表すアウトラインデータが、予め外周データ記憶部４３に記憶されている。
【０１６７】
文字台座形状構造解析部４４は、文字のアウトラインデータ、台座のアウトラインデータの各々に関して、実施の形態１の文字形状構造解析部４と同様に、文字と台座の構造解析結果情報を生成する。文字の構造解析結果情報としては、文字穴毎にその穴を包含する唯一の文字部品が特定され、また、台座に穴が形成されている場合は、台座の構造解析結果情報として、台座の穴を包含する台座が特定され、これらの包含関係を表す情報が、上記実施の形態１と同様の方法によって作成される。文字台座形状構造解析部４４は、その他に、上記実施の形態４と同様に、文字中心座標、及び台座全体のバウンダリーボックスと台座中心座標を求め、文字の中心と台座の中心とが一致するように移動する。さらに、予め定めた余白量を文字のバウンダリーボックスに加算した拡大長方形を求め、これが台座上面に対応するバウンダリーボックスの面に含まれるように、最小の台座スケーリング量を算出する。文字と台座の構造解析結果情報、文字中心座標と台座中心座標、及び台座スケーリング量が、文字台座形状面凸ポリゴン分割部４５に出力される。
【０１６８】
文字台座形状面凸ポリゴン分割部４５は、文字の構成要素に対して、上記実施の形態１と同様に処理を行い、台座の構成要素に対しては、台座スケーリング量でスケーリング変換し、文字のバウンダリーボックスの中心座標と台座のバウンダリーボックスの中心座標が一致するように平行移動したデータに対して、文字と同様に処理を行う。処理結果である文字と台座の各構成要素のインデックスドサーフェースデータは、文字台座形状側面生成部４６に出力される。
【０１６９】
文字台座形状側面生成部４６では、上記実施の形態１の文字形状側面生成部６、及び実施の形態２のべベル形状側面生成部１１と同様に、文字と台座の各構成要素の上下面、側面またはべベル形状の側面を生成する。生成された台座の構成要素に関しては、生成後更に、立ち上げ量に相当する量だけ、ｚ軸の下方向へ平行移動する。但し、台座の側面が回転変換で生成された場合は、その際の回転量の分だけ逆回転変換を行う。以上の処理で生成された文字と台座の各構成要素の上下面、側面のインデックスドサーフェースデータの文字台座形状データ出力部４７に出力される。
【０１７０】
文字台座形状データ出力部４７では、文字台座形状側面生成部４６から送られた文字と台座の各構成要素の上下面、側面のインデックスドサーフェースデータを階層的な記述によって一まとめにして、外部へ出力する。データ形式を円筒座標または極座標等に変換する必要がある場合は、当該データ形式へ変換してから出力する。
なお、実施の形態４、実施の形態５において、文字の３次元形状の下面については、台座に接続されるので不可視なため省略が可能で、この省略によりデータ量の削減が行える。
【０１７１】
以上のように、台座のアウトラインデータに基づいて３次元文字の下部に円柱状等の台座を設けることを可能にしたので、より多様に装飾を施した３次元文字を表示することができる。
【０１７２】
（実施の形態６）
実施の形態６では、３次元の刻印板を生成する場合の実施例について述べる。なお、本実施の形態では、上記の実施の形態と同じ構成部分についての説明は省略する。
【０１７３】
図２５は、本実施の形態６における３次元文字データ生成装置６０１の機能構成を示すブロック図である。３次元文字データ生成装置６０１は、文字刻印板コード入力部５１、文字刻印板外周データ取得部５２、外周データ記憶部５３、文字刻印板形状構造解析部５４、文字刻印板形状面凸ポリゴン分割部５５、文字刻印板形状側面生成部５６、文字刻印板形状データ出力部５７によって構成される。以上のように構成される３次元文字データ生成装置６０１について、以下、詳細に説明を行う。
【０１７４】
文字刻印板コード入力部５１は、実施の形態１の文字コード入力部１と同様に、いわゆるキーボードやマウスなどの入力装置で、これらの入力信号を変換し、ＡＳＣＩＩコードやＪＩＳコードなどの文字コードのほか、刻印板のアウトラインデータを指定するための刻印板コードを生成する。文字刻印板コード入力部５１で生成された文字コードと刻印板コードは、文字刻印板外周データ取得部５２へ出力される。
【０１７５】
文字刻印板外周データ取得部５２は、文字刻印板コード入力部５１から受信した文字コードに対応する文字のアウトラインデータと、刻印板コードに対応する刻印板のアウトラインデータを、外周データ記憶部４３から取得する。文字のアウトラインデータに関しては、上記実施の形態１の文字外周データ記憶部３と同様に、文字のアウトラインデータは、予め外周データ記憶部５３に文字コードに対応して記憶されている。また、刻印板のアウトラインデータに関しても、刻印板コードに対応した刻印板のアウトラインデータが、外周データ記憶部５３に予め記憶されている。文字刻印板外周データ取得部５２で取得された文字のアウトラインデータと刻印板のアウトラインデータは、文字刻印板形状構造解析部５４に出力される。ここで、刻印板に穴が形成されている場合は、その穴に対応するアウトラインデータが、予め外周データ記憶部５３に記憶されている。
【０１７６】
文字刻印板形状構造解析部５４では、まず、文字全体の長方形バウンダリーボックスとその長方形中心座標、及び刻印板全体の長方形バウンダリーボックスとその長方形中心座標を求め、文字のバウンダリーボックスの中心と刻印板のバウンダリーボックスの中心とが一致するように移動する。さらに、予め定めた余白量を文字のバウンダリーボックスに加算した拡大長方形を求め、これが刻印板の上面に対応するバウンダリーボックスの面に含まれるように、最小の刻印板スケーリング量を算出する。次に、刻印板の外周の点列を刻印板スケーリング量でスケーリング変換し、文字の長方形中心座標とスケーリング変換後の刻印板長方形中心座標が一致するように平行移動したものを、刻印板の新たなアウトラインデータとする。
【０１７７】
文字のアウトラインデータ、新たな刻印板のアウトラインデータ、各々に関して、実施の形態１の文字形状構造解析部４と同様に、文字と刻印板の構造解析結果情報を生成する。文字の構造解析結果情報としては、文字穴毎にその穴を包含する唯一の文字部品が特定される。また、刻印板の構造解析結果情報としては、刻印板に穴がある場合は、その穴を包含する刻印板が特定され、これらの包含関係を表す情報が、上記実施の形態１と同様の方法によって作成される。但し、ここで生成される刻印板の構造解析結果情報は、刻印板形状の下面（これを「刻印板下面」という。）に適用される情報である。更に、刻印板の新たなアウトラインデータと、文字のアウトラインデータのうち、文字外形外周の点列と文字穴の外周の点列の順序を逆転したもの（文字外形を文字穴に、文字穴を文字外形に相当するような並びに変更することに相当する）とを合併したデータについても、実施の形態１の文字形状構造解析部４と同様に、構造解析結果情報を生成する。但し、ここで生成される刻印板の構造解析結果情報は、刻印板形状の上面に適用される情報である。
【０１７８】
文字刻印板形状面凸ポリゴン分割部５５では、文字、刻印板上下面の各構成要素に対して実施の形態１の文字形状上下面凸ポリゴン分割部５と同様に処理を行う。図２６（ａ）〜（ｃ）は、この分割を行った後の状態を示した例である（この例では、文字、刻印板上下面の構成要素が、各々１つ存在している）。処理結果の文字と刻印板上下面の各構成要素のインデックスドサーフェースデータは、文字刻印板形状側面生成部５６に送られる。
【０１７９】
文字刻印板形状側面生成部５６では、上記実施の形態１の文字形状側面生成部６、及び実施の形態２のべベル形状側面生成部１１と同様に、刻印板の各構成要素の上下面、側面またはべベル形状側面を生成する。次に、刻印板上面のｚ軸の位置に対して、文字上面の各部分構造をｚ軸の下方向（堀込みの深さに相当し、立ち上げの高さより小さいことが必要）へ移動し、刻印板上面の堀込み部の下面を生成する。最後に、堀込み部下面と刻印板上面の対応点を、上記実施の形態１の文字形状側面生成部６と同様の処理によって堀込み部の側面を生成するが、その際、インデックスの並びは、上記実施の形態１とは逆にする。
以上の処理で生成された文字と刻印板の各構成要素の上下面、側面のインデックスドサーフェースデータの文字刻印板形状データ出力部５７に出力される。
【０１８０】
文字刻印板形状データ出力部５７では、文字刻印板形状側面生成部５６から出力された文字と刻印板の各構成要素の上下面、側面のインデックスドサーフェースデータを階層的な記述によって一まとめにして、外部へ出力する。データ形式を円筒座標または極座標等に変換する必要がある場合は、当該データ形式へ変換してから出力する。
【０１８１】
以上のように、刻印板のアウトラインデータに基づいて３次元文字を含む刻印板の生成を可能にしたので、凹状のより複雑な３次元文字についても表示することができる。
なお、上記の実施の形態１から実施の形態６において、順次１文字ずつ処理を繰り返すことにより、連続した文字列に対する処理も可能である。また、文字列に対して１つの台座もしくは１つの刻印板で対応するためには、文字のバウンダリーボックスを文字列全体のバウンダリーボックスに拡大して処理を行えば良い。
【０１８２】
さらに、上記の実施の形態では、主に穴を含む文字を対象として説明したが、穴を有する一般の図形（図形を構成する図形部品を含む。）に対しても、上記と同様の構成により、自動的に高品位の３次元図形を表示し得る３次元データを生成することができる。
【０１８３】
【発明の効果】
以上のように、本発明に係る３次元文字データ生成装置は、２次元文字データから３次元文字データを生成する装置であって、２次元文字データを用いて、文字を構成する文字部品の外周及び当該文字に形成されている穴の外周を決定する外周決定手段と、前記外周決定手段により決定された穴の外周と包含関係を有し、且つ、当該穴の外周から直近の位置にある文字部品の外周を特定する包含関係特定手段と、前記包含関係特定手段により特定された文字部品の外周の内部領域から、その文字部品と包含関係にある穴の外周の内部領域を除いた領域をポリゴン分割し、特定されない文字部品の外周については、その内部領域をポリゴン分割する分割手段と、前記分割手段によりポリゴン分割された領域に係る文字部品の複製を移動し、前記文字部品と前記複製された文字部品との頂点から側面を生成する側面生成手段とを備えることを特徴とする。
【０１８４】
これにより、操作者の手を煩わせることなく、与えられた２次元の文字の輪郭線データから、３次元文字データを自動かつ実時間で生成し、ビットマップフォントをベースに生成した３次元文字に比べて、はるかに高品位な３次元文字の生成が可能となる。
【０１８５】
また、本発明に係る３次元文字データ生成装置における前記２次元文字データは、前記文字の輪郭や穴の輪郭を表す２次元平面で定義されたアウトラインデータであり、前記外周決定手段は、前記アウトラインデータを取得し、当該アウトラインデータを前記文字の輪郭を表す第１アウトラインデータと前記穴の輪郭を表す第２アウトラインデータとに分類し、分類された第１アウトラインデータに基づいて前記文字部品の外周を決定し、分類された第２アウトラインデータに基づいて前記穴の外周を決定することを特徴とする。
【０１８６】
また、前記包含関係特定手段は、前記文字部品の外周を囲う矩形を決定する第１決定部と、前記穴の外周を囲う矩形を決定する第２決定部と、前記第１決定部によって決定された矩形と前記第２決定部によって決定された矩形とを比較することにより、当該穴の外周を囲う矩形を包含する１又は複数の文字部品の外周を囲う矩形を特定する第１特定部と、前記第１特定部により特定された矩形のうち、最も内側の矩形に係る文字部品の外周を特定する第２特定部と、前記第２特定部により特定された文字部品の外周を、前記穴の外周を包含する唯一の文字部品の外周であると特定し、当該包含関係を表す情報を作成する包含情報作成部とを備えることを特徴とする。
【０１８７】
なお、前記包含関係特定手段は、前記文字部品の外周を囲う矩形を決定する第１決定部と、前記穴の外周を囲う矩形を決定する第２決定部と、前記第２決定部によって決定された穴の外周に係る矩形の重心と前記第１決定部によって決定された文字部品の外周に係る矩形の各辺との距離、又は前記重心と当該文字部品に係る前記点列のうちの一の点との距離のうち、短い方を当該文字部品についての最短距離と決定する最短距離決定部と、前記最短距離決定部により決定された最短距離を、全ての文字部品について比較し、最も短い最短距離に係る文字部品を前記穴の外周を包含する唯一の文字部品の外周であると判定し、当該包含関係を表す情報を作成する包含情報作成部とを備えるように構成することもできる。
【０１８８】
これにより、アウトラインデータによって表される文字に対して幾何学的な構造解析を行うので、文字に文字穴が形成されているか否かなどの文字の構造が明確となり、文字を構成する各文字部品に対しても３次元表示が可能となる。つまり、生成される３次元文字については、階層構造を有しているか否かが明確となるので、文字形状の編集などをする場合やアニメーションを行う場合に、文字部品の単位まで分割した、きめ細かな３次元表示が可能となる。
【０１８９】
また、前記３次元文字データ生成装置は、さらに、前記文字部品の構成要素の下面と上面に対し、これを含む最小の正方形を生成し、前記構成要素の上面及び下面を規定する点列が前記正方形に含まれるように当該正方形を平行移動して前記構成要素における個々の座標値を特定し、これらの座標値を前記正方形の辺の長さをで除した座標値をマッピング座標とし、前記生成された側面を規定する外周の点列の２点間の距離の総和と開始点から各点までの距離との比と、下面から上面までの高さと前記外周の点列における各点の高さとの比に基づいて、テクスチャ座標を生成するテクスチャ座標生成手段を備えるように構成することもできる。
【０１９０】
これにより、テクスチャ座標を生成するので、３次元化した文字表面に様々なテクスチャ模様を施すことが可能となる。
【０１９１】
また、前記３次元文字データ生成装置は、さらに、前記第１アウトラインデータ又は第２アウトラインデータに含まれる点列に対して、連続する２点間の平均距離を所定の値で除することによって基準距離を算出し、連続する２点間の距離が基準距離以上の場合に基準距離以下となるように、前記２点の間に新たに１又は複数の点を補間するデータ補間手段を備えるように構成しても良い。
【０１９２】
さらに、３次元文字データ生成装置は、前記分割手段により分割された凸ポリゴンを再分割する再分割手段を備えることとしても良い。
【０１９３】
これにより、文字外周点列や穴外周点列に対して点を補間し、また、分割されたポリゴンを再分割して、より精細なにポリゴン分割を行うので、３次元形状のさらなる高品位化を図ることが可能となる。
【０１９４】
また、本発明に係る３次元文字データ生成装置は、文字コードに対応する文字のアウトラインデータと台座コードに対応する台座の３次元形状データや台座コードに対応する台座のアウトラインデータとに基づいて、台座の上に３次元文字を据え付けたり、文字コードに対応する文字のアウトラインデータと刻印板コードに対応する刻印板のアウトラインデータとに基づいて、逆に３次元に凹状に掘り込ませた文字を表示するように構成することもできる。さらに、これらの３次元文字の側面の形状としてべベル形状を生成するように構成することもできる。
【０１９５】
これにより、台座に文字を据え付けたり文字の刻印板化を可能とし、側面形状についても種々のべベル形状を生成し得るので、文字の３次元表示に対する様々な要求に柔軟に対応することが可能となる。
【０１９６】
また、本発明に係る３次元図形データ生成装置は、２次元図形データから３次元図形データを生成する装置であって、２次元図形データを用いて、図形を構成する図形部品の外周及び当該図形に形成されている穴の外周を決定する外周決定手段と、前記外周決定手段により決定された穴の外周と包含関係を有し、且つ、当該穴の外周から直近の位置にある図形部品の外周を特定する包含関係特定手段と、前記包含関係特定手段により特定された図形部品の外周の内部領域から、その図形部品と包含関係にある穴の外周の内部領域を除いた領域をポリゴン分割し、特定されない図形部品の外周については、その内部領域をポリゴン分割する分割手段と、前記分割手段によりポリゴン分割された領域に係る図形部品の複製を移動し、前記図形部品と前記複製された図形部品との頂点から側面を生成する側面生成手段とを備えることを特徴とする。
【０１９７】
これにより、穴が形成された図形に対しても、操作者の手を煩わせることなく、与えられた２次元の図形の輪郭線データから、３次元データを自動かつ実時間で生成し、ビットマップフォントをベースに生成した３次元図形に比べて、はるかに高品位な３次元図形の生成が可能となる。
以上のことより、本発明による効果は絶大で、新たな恩恵をもたらすものと考える。
【図面の簡単な説明】
【図１】実施の形態１における３次元文字データ生成装置の機能構成を示すブロック図である。
【図２】文字外周点列及び穴外周点列をたどるときの回り方を示す図である。
【図３】漢字の「回」について文字形状構造解析を実施した場合の模式図である。
【図４】図３における包含関係解析処理における詳細な処理の流れを示すフローチャートである。
【図５】第１の接続化の方法を漢字の「田」に適用し、さらに点列番号の付け替えを実施した様子を示す図である。
【図６】（ａ）は、第１の三角形分割方法を「田」に適用した場合の処理結果の例を示す図である。
（ｂ）は、第２の三角形分割方法を「田」に適用した場合の処理結果の例を示す図である。
【図７】第２の三角形分割方法をロシア語の「ё」に適用した場合の処理結果の例を示す図である。
【図８】文字形状側面生成部における文字形状側面生成処理の流れを示すフローチャートである。
【図９】（ａ）は、文字の上面を高さ方向に移動する第１の方法の概要を示す図である。
（ｂ）は、文字の上面を高さ方向に移動する第２の方法の概要を示す図である。
（ｃ）は、文字の上面を高さ方向に移動する第３の方法の概要を示す図である。
（ｄ）は、文字の上面を高さ方向に移動する第４の方法の概要を示す図である。
【図１０】実施の形態２における３次元文字データ生成装置の機能構成を示すブロック図である。
【図１１】（ａ）は、最も単純なベベル形状の外形を示した図である。
（ｂ）は、べベル形状の中間外周の生成方法を説明するための図である。
【図１２】中間外周生成処理における処理の流れを示すフローチャートである。
【図１３】（ａ）は、凸状の側面を形成するために、２つの中間外周を生成する場合の概要を示す図である。
（ｂ）は、凹状の側面を形成するために、２つの中間外周を生成する場合の概要を示す図である。
【図１４】（ａ）は、半円状に凸となっている側面の形状を示す図である。
（ｂ）は、半円状に凹となっている側面の形状を示す図である。
（ｃ）は、半円状に凸となっている側面の中間外周における各値の算出方法を説明するための図である。
【図１５】、鋳型タイプのベベル形状の側面を生成させる場合について説明するための図である。
【図１６】（ａ）は、上記実施の形態１における文字の上面を高さ方向に垂直に持ち上げた場合の側面の形状を示す図である。
（ｂ）は、その断面が凸六角形状に突き出たべベル形状の側面を生成した例である。
（ｃ）は、中間外周を２つ生成し、文字の上面及び下面の外周に対する削ぎ落とし角度が等しい場合の側面の断面を凸台形状のべベル形状とした例である。
（ｄ）は、側面の形状を鋳型タイプのべベル形状とした例である。
【図１７】実施の形態３における３次元文字データ生成装置の機能構成を示すブロック図である。
【図１８】漢字の「回」に対して、２つの点の間に新たに点を補間した場合の一例を示す図である。
【図１９】元の三角形を４つに再分割する方法における処理の流れを示すフローチャートである。
【図２０】三角形の再分割のレベルをｒにしようとする場合の再分割方法における処理の流れを示すフローチャートである。
【図２１】（ａ）は、三角形の辺の中点を用いて内分割を行う方法を説明するための図である。
（ｂ）は、三角形の再分割のレベルをレベル０からレベルｒに一気に上げる場合の様子を示す図である。
【図２２】実施の形態４における３次元文字データ生成装置の機能構成を示すブロック図である。
【図２３】台座付き文字形状を説明するための図である。
【図２４】実施の形態５における３次元文字データ生成装置の機能構成を示すブロック図である。
【図２５】実施の形態６における３次元文字データ生成装置の機能構成を示すブロック図である。
【図２６】（ａ）刻印板上面を説明するための図である。
（ｂ）刻印板の文字彫り込み部下面を説明するための図である。
（ｃ）刻印板下面を説明するための図である。
【図２７】従来例における３次元文字の作成装置の機能ブロック図である。
【符号の説明】
１０１、１０２、    ３次元文字データ生成装置
１０３、１０４、
１０５、１０６
１              文字コード入力部
２              文字外周データ取得部
３              文字外周データ記憶部
４              文字形状構造解析部
５              文字形状上下面凸ポリゴン分割部
６、３６        文字形状側面生成部
７、１２、２５  文字形状データ出力部
１１              べベル形状側面生成部
２１              文字外周データ補間部
２２              文字形状上下面凸ポリゴン再分割部
２３              文字形状側面生成部
２４              テクスチャ座標生成部
３１、４１        文字台座コード入力部
３２              文字外周台座形状取得部
３３              文字外周台座形状記憶部
３４、４４        文字台座形状構造解析部
３５              台座形状生成部
３７、４７        文字台座形状データ出力部
４２              文字台座外周データ取得部
４３、５３        外周データ記憶部
４５              文字台座形状面凸ポリゴン分割部
４６              文字台座形状側面生成部
５１              文字刻印板コード入力部
５２              文字刻印板外周データ取得部
５４              文字刻印板形状構造解析部
５５              文字刻印板形状面凸ポリゴン分割部
５６              文字刻印板形状側面生成部
５７              文字刻印板形状データ出力部
【図１】
0004028979.tif 000004
【図２】
0004028979.tif 000005
【図３】
0004028979.tif 000006
【図４】
0004028979.tif 000007
【図５】
0004028979.tif 000008
【図６】
0004028979.tif 000009
【図７】
0004028979.tif 000010
【図８】
0004028979.tif 000011
【図９】
0004028979.tif 000012
【図１０】
0004028979.tif 000013
【図１１】
0004028979.tif 000014
【図１２】
0004028979.tif 000015
【図１３】
0004028979.tif 000016
【図１４】
0004028979.tif 000017
【図１５】
0004028979.tif 000018
【図１６】
0004028979.tif 000019
【図１７】
0004028979.tif 000020
【図１８】
0004028979.tif 000021
【図１９】
0004028979.tif 000022
【図２０】
0004028979.tif 000023
【図２１】
0004028979.tif 000024
【図２２】
0004028979.tif 000025
【図２３】
0004028979.tif 000026
【図２４】
0004028979.tif 000027
【図２５】
0004028979.tif 000028
【図２６】
0004028979.tif 000029
【図２７】
0004028979.tif 000030