(57)【特許請求の範囲】
【請求項１】
網目の密度を示す密度パラメータに基づき与えられる間隔Ｌｂでオブジェクトの輪郭上および輪郭内に網目点を生成する網目点生成手段と、
前記網目点生成手段により生成された網目点のうち、前記間隔Ｌｂより小さい最小長Ｌｍより離れていない網目点をマージすることにより完成された網点の集合に三角形網目要素を生成する三角形網目要素生成手段と、
前記三角網目要素生成手段により生成された三角形網目要素のうち、２つの隣接する三角形に共有されている辺が最長の辺である場合、２つの隣接する三角形を四辺形網目要素に変換する四辺形網目要素生成手段と、
網目の上経路を形成する流入曲線と網目の下経路を形成する流出曲線とを有する編み細工模様のタイルを、前記タイルの流入曲線および流出曲線の対の数および分布が前記三角形網目要素および前記四辺形網目要素における途切れていない連結の数および分布と一致するようにマッピングし、網目パターンを描写する描写手段と
を有することを特徴とする網目パターン描写装置。
【請求項２】
網目パターン描写装置の網目点生成手段が、網目の密度を示す密度パラメータに基づき与えられる間隔Ｌｂでオブジェクトの輪郭上および輪郭内に網目点を生成する網目点生成工程と、
網目パターン描写装置の三角形網目要素生成手段が、前記網目点生成工程により生成された網目点のうち、前記間隔Ｌｂより小さい最小長Ｌｍより離れていない網目点をマージすることにより完成された網点の集合に三角形網目要素を生成する三角形網目要素生成工程と、
網目パターン描写装置の四辺形網目要素生成手段が、前記三角網目要素生成工程により生成された三角形網目要素のうち、２つの隣接する三角形に共有されている辺が最長の辺である場合、２つの隣接する三角形を四辺形網目要素に変換する四辺形網目要素生成工程と、
網目パターン描写装置の描写手段が、網目の上経路を形成する流入曲線と網目の下経路を形成する流出曲線とを有する編み細工模様のタイルを、前記タイルの流入曲線および流出曲線の対の数および分布が前記三角形網目要素および前記四辺形網目要素における途切れていない連結の数および分布と一致するようにマッピングし、網目パターンを描写する描写工程と
を有することを特徴とする網目パターン描写方法。
【発明の詳細な説明】
【０００１】
【発明の分野】
本発明は、コンピュータ生成画像を制作するコンピュータ画像制作プログラムにより利用するための芸術的フォントの制作に関する。
【０００２】
【従来技術】
画像中のフォント文字の利用は非常に大衆化し、また、しばしば必要とされる。フォント文字自体は、その制作において相当な芸術的判断を必要とする。そのため、これまで幾千もの異なるフォントタイプが美術家によって制作されている。各フォントはアルファベット内の各文字について制作されねばならず、加えて、技巧的な体裁に調和させるよう、イタリックやボールドのフォントも制作されるのがふつうである。フォントの文字の制作は、それゆえ芸術的には困難な作業であり、特にアルファベットに多くの文字が含まれている場合には格別である。また、英語以外の言語は、中国語やアラビア語、ヘブライ語のように、英語で流布しているローマ字に加えて多くの文字を含んでいる。
【０００３】
新たなフォントを制作する場合、このように芸術的にきわめて複雑であれば、アーティストが重要な判断を行う。
【０００４】
西暦５６３年から７４４年の間のどこかで現れたと考えられる、人気のある伝統的な図版の型のひとつに、組み縄(woven plate)や編み細工(knotwork)を含む「ケルト風」スタイルがある。ケルト風の編み細工は、組み縄に基づいた独特の芸術スタイルであり、しばしば輪郭にはめ込まれる。その中では、入り組んだ編み目の効果を制作するために、系統的な方法でひもが断ち切られ、結ばれている。
【０００５】
まず図１を見ると、組み縄を基にした編み細工のデザインの簡単な例がいくつか図示されている。最初の例（ａ）は、飾り気のない組み縄を基にしており、例（ｂ）は、先端をとがらせた組み縄を基にし、例（ｃ）は、分割された組み縄を基にし、例（ｄ）は、一層込み入った分割の方法に基づいている。
【０００６】
ケルト風のタイプフォントについての更なる情報については、ジョージベインの著書「ケルトの芸術；構成の方法」（１９５１年ロンドン，コンスタブル）が、通常、ケルトの編み細工の構成技術についてもっとも信頼できるテキストであると見なされている。
【０００７】
また、多くの異なる可能なデザイン技法があり得、そこではほとんど芸術的な判断が生じ得ることにさらに注意すべきである。たとえば、図２は、文字「ｈ」についての編み細工の制作物の異なった芸術的描写のいくつかの例（ａ）−（ｄ）を図示したものである。
【０００８】
また、他のタイプの編み細工デザインは、図３に示したように、複数の繊維が交互に編まれたという特性を含んでいる。
【０００９】
高水準の芸術的努力が要求されるならば、ケルト風のタイプフォントを自動的に制作するシステムを提供することが望ましい。
【００１０】
【発明の要約】
本発明の第１の側面によれば、網目の密度を示す密度パラメータに基づき与えられる間隔Ｌｂでオブジェクトの輪郭上および輪郭内に網目点を生成する網目点生成手段と、前記網目点生成手段により生成された網目点のうち、前記間隔Ｌｂより小さい最小長Ｌｍより離れていない網目点をマージすることにより完成された網点の集合に三角形網目要素を生成する三角形網目要素生成手段と、前記三角網目要素生成手段により生成された三角形網目要素のうち、２つの隣接する三角形に共有されている辺が最長の辺である場合、２つの隣接する三角形を四辺形網目要素に変換する四辺形網目要素生成手段と、網目の上経路を形成する流入曲線と網目の下経路を形成する流出曲線とを有する編み細工模様のタイルを、前記タイルの流入曲線および流出曲線の対の数および分布が前記三角形網目要素および前記四辺形網目要素における途切れていない連結の数および分布と一致するようにマッピングし、網目パターンを描写する描写手段とを有する。
【００２１】
【好適な実施例及び他の実施例の説明】
好適な実施例において、内部点とそれらのドローネーの三角網の半規則的な分散に基づいて、任意の文字輪郭へと柔軟な網目を自動的にはめ込む方法が提供される。その網目は、ほとんど、編み細工デザインがそのときにそこで実現される付加的な支持三角形要素とともに、適切に形成された四辺形(quadelectral)要素から構成されるように処理される。
【００２２】
一般に、いかなるやり方の編み細工デザインも、下記の望ましい特徴をたいていはっきり示している。
【００２３】
格子の一致：ひもの径路は、その組み縄の格子からの派生物を表しつつ、しっかりと斜めになっている。
【００２４】
連続性：デザインは連続する径路につながる一本のひも（あるいはできるだけ少ない）から構成される。一本のひもで達成できる複雑さが制作者の技術の尺度である。
【００２５】
交互編み：ひもは、適当な点から始まって、各交点で交差するひもの上及び下を交互に通り、そのデザイン中でそのようになる。交互編みは、(i)３あるいはそれ以上の曲線が交差する点がなく、(ii)曲線が交差せずに接触する点がない、のであれば、いかなる閉曲線の集合に対しても適用可能である。
【００２６】
規則正しさ：ひもは間隔が均等であり、かつパターンに横断的に一様な密度である。切れ目は一般的には対照的かつ規則的な間隔に置かれる。
【００２７】
繰返し：編み細工の単位は、しばしばデザインに横断的に繰り返されるモチーフを形成し、隣接するユニットと連続して接続されている。輪郭の形状に合わせるために、モチーフの単位は一律にサイズを変更してもよいし、変形（できればアフィンでない変形）を経てもよい。
【００２８】
ひものインターレース：「インターレース」という用語は、一本のひもの径路を複数の平行なひもの径路で置換する技術をいう。インターレースしたひもは、そのうちの一本と位相幾何学的に等価である。また、交互編みの拘束にも従う。「Ｎ−インターレース」は、一本のひもの径路をＮ本のひもで置換することを言う。
【００２９】
【方法の好適な実施例】
図２１に、オブジェクトの輪郭内に芸術的効果を制作する好適な方法の流れ図が示されている。ステップ２１００において方法は開始され、あらゆる必要なパラメータが初期化される。次のステップ２１０２においては、タイルセットが利用者の入力に応じて生成される。タイルセットが生成される方法は、「１．タイルセットの生成」の見出しの下により詳細に論ずる。タイルセットの生成が完了すると、この方法は、網目を生成するステップ２１０４に進む。この網目が生成される方法は、「２．網目の生成」の見出しの下でより詳細に説明する。次のステップ２１０６においては、編み細工デザインが網目に適用される。このステップは、「３．網目への編み細工デザインの適用」の見出しの下で、より詳細に説明する。ステップ２１０６の後、この方法はステップ２１０８に進む。ここでは、タイルが網目の網目要素にマッピングされる。このステップは、「４．タイルの網目要素へのマッピング」の見出しの下でより詳細に説明する。次のステップ２１１０では、制作された編み細工フォントが格納され、描写される。フォントを描写する方法は、「５．編み細工フォントの描写」なるタイトルの付されたセクションで詳細に説明する。この方法は、ステップ２１１２で終了する。
【００３０】
１．タイルセットの生成
編み細工デザインを実現するために、分離したタイルセットの利用を含む様々な取り得る技術が知られている。スロス（Ａ,．スロス,「ケルト風編み細工の描き方：実践ハンドブック」ブランドフォード，ロンドン，１９９５）は、タイルを、単純で規則的な（正方形）４−網目に、必要に応じて回転して、直接当てはめることでこのアプローチを説明している。その結果は、図２の例（ａ）に説明されているのと同様である。けれども、この技術を規則的でない３，４−網目にうまく適用するためには、タイルセットは、任意の形状の四辺形のタイル（正方形のタイルにアフィン変換でない変換を適用して得られる）に「合う」三角形のタイルを含むように拡張されるべきである。ｎ−タイルセットは、ｎ個の辺に対して、あり得る流入／流出の組合せそれぞれについてひとつのタイルを含めば、完全である。図４は、３，４−網目中で発生し得る全ての場合を扱うことができる、最小の完全な３，４−タイルセットを示す。
【００３１】
標準的な右回りの網目を、本実施例の説明で用いられる取り決めとする。それゆえ、流入曲線はタイルの辺において上径路を形成し、流出曲線はタイルの辺において下径路を形成する。たとえば、図４に示されているように、タイル（ａ）は、辺３において、流入曲線２の下径路をなす流出曲線１を含んでいる。図３に示された曲線は、ひもの径路を表す誘導曲線（不図示）から得られる、ペアをなす派生物(paired offset)（正及び負）を示す。
【００３２】
各タイルは、各辺について、せいぜいひとつの流入曲線とひとつの流出曲線とを含み、流入曲線のある辺は常に対応する流出曲線を有する。流入及び流出曲線は開曲線である。「内部曲線」はタイルの境界内にあり、いかなる点でも境界に接触も交差もしない閉曲線で、その例が図４（ｆ）及び図４（ｊ）に示されている。
【００３３】
近傍のタイルとの幾何学的な連続性を保つために、流入及び流出の角度は一致していなければならず（この場合には４５度）、相対的な流入及び流出位置も一致しているべきである（単位三角形及び単位正方形タイルの双方について０．５）。
【００３４】
図５では、より複雑な、完全な３，４−タイルセットを説明している。趣のある編み目効果を制作するために、目的の網目に関連して異なるタイルセットからいくつのタイルでも組み合わせることができ、その結果得られるセットは目的の網目に関して完全である。完全な３−タイルセットあるいは４−タイルセット（完全な３，４−タイルセットのサブセット）は、さらに、それぞれ３−網目あるいは４−網目に合うように選ばれる。
【００３５】
１．１複数のひものインターレース
平面上の閉曲線の交互編みの特性は、図３（ａ）及び図３（ｃ）に図示されたような効果を作り出すために、ｎ−インターレースをタイルセットに自動的に適用するために利用できる。ｎ−インターレースで表されるひもの径路は、誘導（流入）曲線を指定されたひもの間隔にずらすこと(offsetting)により得られる。そして、ひもの縁は、ｎ個のひもの径路を、指定されたひもの幅に、ひもの径路に対して正及び負の方向にずらすことによって定めることができる。
【００３６】
図６をみると、複数のひものインターレース処理の例がここに図示される。ひとつの誘導ひもの径路５は、まず方向６，７双方に対してずらされる。ひもの縁、たとえば８，９は、ひもの径路たとえば７を、方向８，９双方に指定されたひもの幅でずらすことで得られる。
【００３７】
誘導及びひもの径路のずれの双方は、一定の許容範囲に収まるよう正確であるが、元の曲線の幾何学的な連続性に合った幾何学的な連続性が保証されるように処理されなければならない。ずれにより派生した曲線の末端は、切られるか、あるいは、必要に応じて端点を折るように延長され、単位となるタイルの形で切り取られる。流入点と流出点はタイルの辺において一定の間隔を維持するように調整される。
【００３８】
交互編みのパターンは、下の径路に対応する曲線の部分を隠すことで視覚化される。これは、交点において曲線を細分化し、４番目ごとの交差する区間を「隠蔽されている」ものと印を付けることで成し得る。交差の数は、インターレースされる曲線数倍に一致することに注意しなければならない。
【００３９】
ひもの径路の正及び負のずれは上及び下径路において一致していなければならないため、渦巻き型の誘導曲線や複数のインターレースについて、特に幅のより広いひもについて、無効な編み目パターンが生じる。この問題は次のような辺の適応型可変ずらしを用いることで回避される。
【００４０】
apply  一定のずれ          （一定のずれを適用する）
while  無効の編み目        （無効の編み目である間）
reduce  内部のずれ幅      （内部のずれ幅を減縮する）
apply   可変のずれ        （可変のずれを適用する）
曲線の端部が、隣接するタイルの曲線の端部に対応することを保証するために、内部のずれの範囲に関係なく曲線の流入点及び流出点におけるずれの範囲は一定に保たれる。簡単な発見的学習(heuristic)が、ずらされた各ひもについての交差の数に基づいて、編み目パターンが有効か判定するために用いられる。
【００４１】
図７は、ひもの幅を広げるための適応型可変ずらし処理を説明している。ここで、reは流入／流出点における一定のずれの範囲であり、riは、他の全ての（内部）点における可変な範囲のずれである。有効な編み目を許容するために、どの程度中間点における曲線の幅が実質的に縮小されるか、また、等間隔の流入／流出位置の条件は保持されるが、re:ri比（図７ｃのそれのように）がより大きくなれば、ずれに関して、４５度の流入／流出角度の条件が緩和されることが必要であるに注目せよ。ずれの範囲はタイル単位ごとに与えられ、そこでは各タイルの辺は長さが１．０単位で次のようなファイルを伴う：（ａ）一定のずれre ＝ri＝０．０７５（ｂ）可変のずれre＝０．１５，ri＝０．１２７５，（ｃ）可変のずれre＝０．１７５，ri＝０．１２６４。
【００４２】
それゆえ、ｎ−インターレースのタイルセットの生成はパラメータ化でき、(i)誘導曲線の集合，(ii)インターレースするずれにより派生したひもの数，(iii)ひもの分割、及び(iv)ひもの幅、を指定することで、幅広い多様なパターンを簡単に制作できる。編み細工デザインを生成するために使用されているタイルセットはこうして定義される。このようなタイルセットをその時々に生成するのでなく、タイルセットを、制作工程で利用者がアクセスできるライブラリに格納することもできる。次の工程は、タイルセットがマッピングされる、それに合った３，４−網目の生成である。
【００４３】
２．網目の生成
網目生成のアルゴリズムの例として、Ｙ．Ｔ．Ｌｅｅ及びＡ．Ｄｅ  Ｐｅｎｎｉｎｇｔｏｎの「幾何学モデルからの自動的な有限要素網目生成−点に基づいたアプローチ」，（ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｒ  Ｇｒａｐｈｉｃｓ，第３巻第４号，１９８４年１０月）を参照する。四辺形及び三角形の要素からなる有限要素網目の生成のための公知のアルゴリズムは、通常、構成的連続幾何学規則(constructive solid geometry rules(CSG))を用いてマージされた、規則的に分散された点の集合を伴う単純な形で構成されている。このアプローチは通常２つの主たる理由からここでは適していない：
形の複雑さ：文字の輪郭の形状は恣意的に複雑にでき、規則的に点が分散していない。網目点を受容可能に分散させる方法は、それに続くアルゴリズムに集約される。
【００４４】
方向の偏り：前項で参照した方法の能力のひとつは、網目点の効率的な円形の移動である。けれどもこれは、不規則な点の分散に対して特に顕著な左右の強い偏りをもたらす。編み細工デザインについては、網目要素が輪郭にきちんと合い、不明瞭さはその形状の中心に向けて生じることが望ましい。図８に示された例のように、編み細工デザインの周りの境界を生成するために、このことは特に重要である。
【００４５】
網目の格子のサンプルが図示された図９を見ての通り、本好適な実施例の解説においては、次の表記が用いられる。
【００４６】
ｖポイント（たとえば１２）＝輪郭の頂点上の網目点
ｅポイント（たとえば１３）＝頂点ではない輪郭上の網目点（すなわち辺の点）
ｂポイント＝境界点（ｅポイントあるいはｖポイント）
ｉポイント（たとえば１４）＝輪郭形状に対して内側の網目点
フォントの輪郭形状内の網目点を分散させることは、不連続な(discrete)段階で移動する波面を用いることでなされる。前線は輪郭から形の内側に向かって、対抗する波面によりうち消されるまで、等間隔の点を規則的な間隔でその周囲に置きながら進行する。網目の密度は密度パラメータにより決定される。基長（Ｌｂ）は、網目ｍの密度から直接決定される。基長は、網目要素の辺の好適な長さであり、網目点のデフォルトの間隔である。Ｌｂは、密度パラメータの逆数である。図１０ａから図１０ｃは、図１０ａは密度が０．１、図１０ｂは密度が０．５、図１０ｃは密度が０．８２５と、密度パラメータの変更の効果を示す。
【００４７】
要素の辺についての「最小長」（Ｌｍ）は、Ｌｍ＝Ｌｂ／√２によって与えられる。これは、ある程度の規則正しさを保証する網目要素のサイズの下限を与え、３つあるいは４つの合理的な間隔（距離Ｌｂ）の網目点Ｐｒの集合により記述された領域の内部のあらゆる網目点Ｐが、Ｐｒの少なくともひとつの要素からせいぜい距離Ｌｍ離れているであろうことを意味している。これは、波面に沿った干渉を検出すること、及び、波面の進行の終結を保証することおいて重大である。
【００４８】
図１１ａから１１ｃにおいて、網目生成処理の例を図示する。
【００４９】
図１１ａに示したように、波面は、ｖポイント、たとえば、継ぎ目を横切る第一度の幾何学的連続性を示さない輪郭曲線の端点に対応する１５の付加により開始される。輪郭に沿った連続するｖポイント間の間隔は、ｅポイント、たとえば可能な限りＬｂに近い距離の間隔が初めにきちんと開いた１６により、その種が蒔かれる(seeded)。この規則的な間隔は、凸型の間隔はより密集して詰められ、凹型の間隔はよりまばらに間隔が開くように（図１１ａの「ｎ」の弧１７を見よ）、局所的な輪郭の湾曲によって修正される。この湾曲に依存した間隔開けは、規則的な網目がねじられる場合に観察される点の間隔開けの影響を反映する。蒔かれた(seeded)ｅポイントもまた最初の波面に付加される（図８ａ参照）。
【００５０】
通常の方向ベクタｎ、たとえば１８は、最初の各種点(seed point)に関連づけられ、輪郭上のその対応点において、内側への曲線の法線により決定される。最初の波面を含む種点ｂポイントもまた、最初の網点Ｐｍの集合に付加される。波面は、次の方法によってＰｗが空になるまで、新たな点Ｐｍを付加しながら次第に前進する。
【００５１】
Ｐｍ＝Ｐｗ＝最初の種点
while Ｐw not empty        (Ｐwが空でない間)
for each Ｐ∈Ｐw            (Ｐwに属する各Ｐについて)
generate Ｐp’               (Ｐp’を生成)
merge Ｐｐ’ with Ｐｍ        (Ｐp’ とＰｍとをマージ)
add surviving Ｐｐ’ to Ｐｗ  (残ったＰp’をＰｗに付加)
remove Ｐ from Ｐｗ         (ＰｗからＰを除去)
ここでＰｐ’は点Ｐから得られた投影点の集合である。図１２に示したようにＰｐ’は３つの点を含む。(i)方向ｎへの前方投影点(Ｐｆ’)、(ii)ｎから反時計回りに９０度の方向への左投影点(Ｐl’)、(iii)ｎから時計回りに９０度の方向への右投影点(Ｐｒ’)である。３つの点全ては点Ｐから距離Ｌｂ離れている。輪郭形状の外側にある投影点はＰｐ’から除去される。
【００５２】
Ｐｐ’の各メンバは、存在している点Ｐｍへの近接度をテストされ、距離Ｌｍよりも離れていなければ、次の表で与えられる規則に従ってマージされる。ここでマージされる２点は(Ｐ１及びＰ２)である。動作は次のようなものである。
【００５３】
【表１】
0004475606.tif 000002
【００５４】
２つのｉポイントの平均をとることは、どちらかの点を、線分Ｐ１Ｐ２の中点に移動し、もう一方の点を削除することである。この中点はそれ自身が存在する点Ｐｍの間隔Ｌｍを乱すものであるから、後処理工程ではＰｍ内の無効なペアをマージする。点の対の近接度は、グリッドに基づいた、局所的な近傍の探索によって能率的に決定できる。
【００５５】
波面の前進の間に生成される全ての点はiポイントであり、この工程の間は、前記表の最後の行及び最後の列のみが適用される。けれども、たとえば、距離Ｌｍ離れていない隣接するｖポイントのような、波面がそこで開始される種点が生成される場合には、そのほかのケースも生じ得る。
【００５６】
波面は、マージ操作の間に削除されなかったＰｐ’の要素の追加により、連続する各ステップに伝達される（たとえば図１１（b)参照）。各網点には、その点がＰｍにどの波面の反復において追加されたかを示すタイムスタンプが付与されている。 Ｐｐ’の全要素は、対向する波面と出会うときにマージされ、図１１ｃに示すように、最終的な網格子を与えるそれらの点における波面を実際上消去する。前述した長さＬｍとＬｂとの関係は、波面が互いに「通過」しないことを保証する。波面は前進する間に独立した小地域に分離することがあり、その場合には集合Ｐｗは各小地域の要素点の和集合となる。波面の取消しの後、網点Ｐｍの集合が完成する。
【００５７】
最終的な点の分散は、要求通り、輪郭の周りでは完全に規則的である。しかし、形状の中心に向けて、ぼんやりとしてくる（図１１ｃの「ｎ」のアーチ１９において顕著である）。内部の規則性は、網目要素生成の次のステップの間に改善される。
【００５８】
ドローネーの三角網（ＤＴ）プロセスは、前述の工程で生成された網点の集合に適用される。ドローネーの三角網プロセスは、高品質の網点を生成するためにはよく知られたプロセスである。このプロセスのより深い検討のために、ダニ・リシンスキの「増強されたドローネーの三角網(Incremented Delaunay Triangulation)」グラフィクスジェムズ(Graphics Gems)第３巻第４号，アカデミックプレス(Academic Press)，ボストン，１９９４，第４７から５９ページが参考になる。
【００５９】
有限なデータ点集合のドローネーの三角網は、空の外接円特性(empty circumcircle property)を満足する三角網である。すなわち、 その外接円がドローネーの三角形の例を示す図１３ａから図１３ｃのあらゆるデータ点を含むようなＤＴ（ドローネーの三角網）内には三角形が存在しない。これは強力でよく文書化され、効率的なアルゴリズムが存在する技術である。
【００６０】
このアルゴリズムは、次のように要約できる。全網点を含むような既知の初期三角形から始めて、各網点は、空の外接円特性を保持するようなＤＴに追加される。各点がＤＴに追加されるため、新たな辺がそれに適合するように制作されねばならず、存在する辺は、空の外接円特性を維持するために、代わりの点の対の間にはじき出され(flipped)得る。この処理は実際には素早く収束するけれども、はじき出された辺は、それ自身が、さらにはじき出される辺を必要とすることもある。
【００６１】
リシンスキのアルゴリズムの欠点は、４あるいはそれ以上の共通する円周上の(cocircular)点が、図１３ｂ及び１３ｃに示したような固有でないＤＴとなることである。しかしながら、このように悪化した場合は、簡単に等価の四辺形網目要素（いずれにしてもこの場合４つの符合する点）に変換できるため、この問題は、３，４−網目生成のプロセスについては大した問題ではない。
【００６２】
２．１  網目要素の変換
３，４−網目生成の最後の工程は、ＤＴ三角形の四辺形及び三角形網目要素への変換である。この工程は次のように進行する。
【００６３】
内部三角形（中央の点が輪郭形状の内部にあるＤＴ三角形）が識別され、集合Ｔiに追加される。初期の３つのＤＴの種点から形成される三角形も含めて、内部三角形でないものは放棄される。悪化(degenerate)した三角形（ある閾値より小さい領域の三角形）も放棄される。各内部三角形は、頂点を含む網点の最小のタイムスタンプに対応するタイムスタンプが与えられている。
【００６４】
Ｔiの要素から形成することのできる最適の四辺形要素は識別されて３，４−網に追加される。最適の四辺形は、２つの隣接する三角形に共有されている辺が、各三角形の最長の辺である場合に発生し、共有される辺の除去により具体化される。たとえば図１４ａにおいて、最適の四辺形ＡＢＣＤは三角形Ｔ１及びＴ２に共通の辺ＡＣを除去することで得られる。２つの要素である三角形Ｔ１及びＴ２はＴiから除去される。個々の工程における最適な四辺形要素の外側への進行を促進するために、最初の径路はＴiの要素上に同じタイムスタンプで作られ、それから他の径路はタイムスタンプにかまわずに作られる。
【００６５】
Ｔiの残りの要素から形成できる良好な(Good)四辺形要素は、識別されて３，４−網に追加される。良好な四辺形は、隣接する三角形で共有される辺が除去され、得られた四辺形が、その形状及び面積に関して所定の条件を満たす場合に発生する。図１４ｂを見ると、１１ｂに適した、現在の実施において三角形Ｔ１及びＴ２に対して用いられる評価関数は次の通りである。
【００６６】
if [(Σ|ai-90|)/90 + (Σ|Li- Lavg|)/Lave] ＜ threshould
then 四辺形は良好
ここでａiは四辺形のｉ番目の頂点であり、 Ｌiは、ｉ番目の辺（ｉは１から４まで）の長さであり、 Ｌavgは、平均の辺の長さである。これは、ほぼ直角の内角と、ほぼ等しい長さの辺を持つ四辺形に対して好都合である。
【００６７】
良好な四辺形の制作に用いられる二つの要素三角形はＴiから除去される。再度、最初の径路が、Ｔiの要素上に同じタイムスタンプで作られ、他の径路はタイムスタンプにかまわずに作られる。
【００６８】
四辺形は、それが最適かあるいは良好であれば、適切に形成される。
【００６９】
残りのＴiの要素は、三角形網目要素として、３，４−網目要素に直接追加される。３，４−網目要素は、 Ｔiの全ての要素が、適切に形成された四辺形網目要素に変換されるか、あるいは直接追加されて構成される。図１５は、網目合わせプロセスの例を示し、ここでは網目２５は対応する最終的な網目２６に変換されている。
【００７０】
網目要素の一様性は、その時点で、各網目点が、網目要素の辺を共有する他の全ての網目点からできるだけ等距離になるように調整することで改善され得る。これは、網目２５から網目２６へと規則性が改善されていることにおいても明らかである。一様性パラメータを通して適用される、いくつもの調整段階についてパラメータを指定し得るが、実際には、２つの段階以上は必要ではない。
【００７１】
反対に、網目点は、各網目点をまちまちの方向にわずかな距離移動させることで混乱させることができる。これは、網目にエントロピを導入し、自動的に得られた格子に明らかな規則性を弱める。利用者は、この効果を達成するために混乱値を指定する。網目の混乱が適用された最終的な例を図２ｂ及び図２ｄに示している。
【００７２】
任意の輪郭形状についての３−網目は、四辺形の変換工程を除いた上記手順が後に続くＤＴから直接得ることができる。図１６は、三角形のタイルセットが適用された３−網目から形成された文字を示す。
【００７３】
四辺形要素への変換後まで残ったＴiの要素を、得られる網目の連結性への重大な影響なし廃棄することができないために、任意の輪郭形状の４−網目は上記手順を用いたＤＴからは得られない。代わりに、４−網目は、規則的な格子上において、充填された輪郭形状を「サンプリング」すること、及び、各占有された格子セルを、図１ａ及び図１ｂに例示された四辺形網目要素に直接変換することにより得ることができる。これは充填された輪郭形状を低解像度でピクセル化(pixelization)することに類似している。格子の解像度は密度パラメータに支配される。
【００７４】
利用者は、ダイアログを通して明示的に、あるいはタイルセットの選択を通して明示的に網目のタイプを選択できることが望ましい。
【００７５】
３．網目への編み細工デザインの適用
輪郭形状に合った３，４−網目があたえられたとすると、網目要素は、隣接する要素が共通の辺を横切って共に連結するように関連している。これにより、編み細工の連続はタイルの辺を横切るようになればよい。切れ目が、近傍の要素間の連結を厳格にすることによりデザインに導入される。図１７及び８は切れ目の例を示し、図１７は、混乱度＝０．４で、正方形の格子上の形状を横切るようなランダムな切れ目を有しており、図８は、境界幅＝１の３，４−網目である。
【００７６】
編み細工を境界と内部の領域に分割することは、ケルト風の編み細工に共通した意匠ではあるが、境界の幅より小さいかあるいは等しいタイムスタンプを持つ要素と、境界の幅よりも大きいタイムスタンプを持つ要素との間に切れ目を入れることで簡単になし得る。図８及び図１６にその例が示されている。境界の幅は利用者がセットするパラメータとすることができる。
【００７７】
編み細工のデザインが決定され実施されれば、編み細工のタイル及びその方向性は各網目要素に関連づけられる。各網目要素Ｅについて、調和するタイルの集合Ｔｍが決定され、Ｔｍに属する各タイルＴ（Ｔ∈Ｔｍ）はＥと同じ数の頂点を持ち、Ｔにおける流入及び流出曲線の対の数及び分布は、Ｅにおける途切れていない連結の数及び分布と一致する。 タイルＴ∈Ｔｍはランダムに選ばれ、ＴをＥに調和させるために必要な方向が記録される。
【００７８】
４．網目要素へのタイルのマッピング
最終的な編み細工を記述する筋道は次のように導かれる：タイルに関連した各網目要素(element)の構成要素(component)曲線がコピーされる。これらのタイル曲線のコピーは網目要素の位置、方向、形状に適合するようにマッピングされる。曲線を記述する制御点のみがマッピングされる。
【００７９】
四辺形の網目要素については、単位となる正方形タイルの曲線は、標準の、アフィン変換でないバイリニア歪みを用いてマッピングされる。元となる座標はタイルユニットの四角形の頂点であり、目的の座標は網目要素の頂点である。関連する方向の値は、元となる座標及び目的の座標を正確に整列させるために用いられる。
【００８０】
４．１  三角形の補間
三角形のタイルは、重心座標系の座標に基づいた補間スキームを用いた三角形網目要素へとマッピングされる。この処理の一例が、第１の三角形３０から第２の三角形３１への歪みを示した図１８に示されている。１個のタイルである三角形ＵＶＷの各制御点Ｐは、目的の三角形Ｕ’Ｖ’Ｗ’における点Ｐ’へとマッピングされる。
【００８１】
元の三角形ＵＶＷに対する重心座標系の座標ｕ,ｖ,ｗ、及び、目的の三角形Ｕ’Ｖ’Ｗ’に対するｕ’,ｖ’,ｗ’は、ｕ＋ｖ＋ｗ＝１及びｕ’＋ｖ’＋ｗ’＝１なる制約を受けている。これら座標は次のように評価される：
ｕ ＝Ａｕ／Ａ    ｖ ＝Ａｖ／Ａ    ｗ ＝Ａｗ／Ａ
ｕ’＝Ａｕ’／Ａ’    ｖ’＝Ａｖ’／Ａ’    ｗ’＝Ａｗ’／Ａ’
ここで、Ａは三角形ＵＶＷの領域であり、Ａｕは三角形ＰＶＷの領域、Ａｖは三角形ＰＷＵの領域、Ａｗは三角形ＰＵＶの領域であり、目的の領域Ａ’,Ａｕ’,Ａｖ’及び Ａｗ’についても同様である。三角形ＵＶＷの領域は：
Ａ＝1/2・[(Vx- Ux)(Wy- Uy)- (Wx- Ux)(Vy- Uy)]
によって、反時計回転の順で各頂点について与えられる。時計回転の方向の三角形に対しては、結果は負になるであろう。
【００８２】
三角形ＵＶＷから三角形Ｕ’Ｖ’Ｗ’内の点Ｐへの変換においては、点Ｐに関する重心座標系の座標が次式に示すように定数のままであるということが利点と成り得る。
【００８３】
ｕ ＝ ｕ’
Ａｕ／Ａ ＝ Ａｕ’／Ａ’
Ａｕ’ ＝ ＡｕＡ’／Ａ
Ａｕ’について領域方程式を置き換えて再配置すると、これは：
Px’(Vy’-Wy’)+ Py’(Wx’-Vx’)=2AuA’/A-Vx’Wy’+ Wx’Vy’
となる。ｖ＝ｖ’についても同様に：
Px’(Wy’-Uy’)+ Py’(Ux’-Wx’)=2AvA’/A-Wx’Uy’+ Ux’Wy’
となる。
【００８４】
これにより、Ｐ’を決定するために解かれるふたつの未知の値（Ｐｘ及びＰｙ）を伴ったふたつの線形方程式の体系が与えられる。
【００８５】
タイルの集合が網目にマッピングされた後、残った工程は最終的な結果の描写のみである。
【００８６】
５．編み細工フォントの描写
３，４−網目のタイリングによって生成された編み細工の曲線の集合のそれぞれは、各文字に対するひもについて、ひとつの辺レコードに格納できる。各辺レコードは径路に関連づけられている。そのような径路それぞれは、図１９に示されたような充填された文字図形や、より複雑な効果を制作するために異なる網目密度で生成された他の編み細工曲線の集合といった、他のグラフィックオブジェクトと簡単に合成できる。
【００８７】
注目すべき基本的な３つの描写スタイルがある：
線引きされた辺(stroked edges)：可視曲線が線引きのペン(stroked pen)によって開曲線として描かれる。
【００８８】
辺の混合：可視曲線が、それらの反対のずれによる派生物とともに対にされ（すなわち、正のひものずれによる派生物が、その負の対応物と対にされる）、それらの間で辺が混合された開曲線として描かれる。
【００８９】
充填された形状：可視曲線及びそれらの反対のずれによる派生物が閉じられて充填される。
【００９０】
強調及び陰影効果は、網目パターンを強調する視覚的な手がかりである。まずまずの深さの効果のひとつは、形状にぴったりと合ったより暗い色で充填された径路上で、中央部付近の完全な不透明さから周辺部の完全な透明さへと滑らかに変化する、辺が混合された径路を合成することで達成できる。その結果は充填された背景の形状の上に合成できる。同じ辺レコードは、能率をあげながら、本例における編み細工を作り上げる全径路について利用できる。
【００９１】
たとえば、図２０ａにおいては、辺３５，３６を有するロープ３４の一部が示されている。図２０ａの線Ａ−Ａ’を通って得られる不透明度の断面が図２０ｂに示されており、そこでは不透明度の断面が３７で示されている。
【００９２】
文字の編み細工デザインを幅広く提供するように、多くの他のバリエーションが成し得ることもまた明らかである。
【００９３】
半規則的な内部点の分布及びそれらのドローネーの三角形化に基づいて、的確な四辺形要素及び補助の三角形要素を含む柔軟な網目を輪郭形状に合わせるための方法について説明した。編み細工のタイルを柔軟な網目にマッピングする方法もまた提供される。
【００９４】
得られた文字は、相応に芸術的な優秀さを持ち、少しのパラメータで定義され、従来の技術によって同様な文字を得るのに要するであろう時間の何分の１かの時間で生成される。
【００９５】
網目生成のアルゴリズムの有用性は、編み細工の装飾に限定されず、可能なアプリケーションは幅広い（幾何学的配列や、空白で充填された曲線、エッシャーのようなタイル化を含む）。
【００９６】
装置の好適な実施例
オブジェクトの輪郭内における芸術的効果の制作の方法は、図１から２１のプロセスがコンピュータにより実行されるソフトウエアとして実施される、図２２にそのひとつを示した在来の汎用コンピュータを用いて行われるのが好ましい。特に、オブジェクトの輪郭内の芸術的効果を制作する方法の工程は、コンピュータにより実行されるソフトウエア中の命令により達成される。このソフトウエアは、２つの部分に分割される。ひとつは製作工程を実行するためのもので、もうひとつは後者と利用者との間のユーザインターフェースを管理するためのものである。このソフトウエアは、たとえば次に述べるような格納装置を含む、コンピュータ読み出し可能な媒体に格納できる。このソフトウエアは、コンピュータ読み出し可能な媒体からコンピュータへとロードされ、そのコンピュータにより実行される。このようなソフトウエアあるいは記録されたコンピュータプログラムを有するコンピュータ読み出し可能な媒体は、コンピュータプログラム製品である。このコンピュータプログラム製品のコンピュータにおける使用は、好ましくは、本発明の実施例に従うオブジェクトの輪郭内における芸術的効果を制作するために都合の良い装置をもたらす。
【００９７】
コンピュータシステム２２００は、コンピュータ２２００、ビデオディスプレイ２２１６、入力装置２２１８，２２２０から成る。さらに、コンピュータシステム２２００は、レーザプリンタやプロッタ、その他のコンピュータ２２００に接続された復元装置を含む、多くの他の出力装置のどれかを有することもできる。コンピュータシステム２２００は、モデム通信路やコンピュータネットワーク等といった適当な通信チャネル２２３０を用い、通信インターフェース２２０８ａを介して、ひとつあるいはそれ以上の他のコンピュータシステムと接続できる。このコンピュータネットワークは、ローカルエリアネットワーク（ＬＡＮ）やワイドエリアネットワーク（ＷＡＮ）、イントラネット、インターネットの少なくともいずれかを含めてよい。
【００９８】
コンピュータ２２００は、それ自身が中央処理ユニット（ここから単にプロセッサと呼ぶ）２２０４と、ランダムアクセスメモリ（ＲＡＭ）及びリードオンリメモリ（ＲＯＭ）を含むであろうメモリ２２０６と、入出力（Ｉ／Ｏ）インターフェース２２０８ａ，２２０８ｂと、ビデオインターフェース２２１０と、図２２のブロック２２１２で一般的に表されるひとつあるいはそれ以上の格納装置から成る。格納装置２２１２は、ひとつあるいはそれ以上の以下のものから成る。すなわち、フロッピディスク、ハードディスクドライブ、光磁気ディスクドライブ、ＣＤＲＯＭ、磁気テープ、あるいは当業者にはよく知られた他の多くの不揮発性の格納装置のいずれか、である。構成要素２２０４から２２１２の各々は、典型的には、順にデータ、アドレス、及びコントロールバスから構成されるバス２２１４を介してひとつあるいはそれ以上の他の装置に接続される。
【００９９】
ビデオインターフェース２２１０はビデオディスプレイ２２１６に接続され、ビデオディスプレイ２２１６に表示するためのコンピュータ２２０２からのビデオ信号を供給する。コンピュータ２２０２を操作するための利用者の入力は、ひとつあるいはそれ以上の入力装置２２０８ｂにより供給される。たとえば、オペレータはキーボード２２１８、及び、マウス２２２０のようなポインティングデバイスの少なくともいずれかを、コンピュータ２２０２に入力を行うために利用できる。
【０１００】
システム２２００は、単に説明のために用意したもので、本発明の範囲及び趣旨から逸脱することなく他の構成を用いることもできる。本実施例が実現される典型的なコンピュータは、ＩＢＭ−ＰＣ／ＡＴあるいは互換製品、マッキントッシュ（登録商標）ファミリのひとつのＰＣ、サンのスパークステーション（登録商標）等を含む。前述したものは、単に、本発明の実施例が実施されるコンピュータの類型の典型である。典型的には、実施例のプロセスは、後述するように、ソフトウエア、あるいは、コンピュータ読み出し可能な媒体としてハードディスク（図２２のブロック２２１２として一般的に描かれている）上に記録され、プロセッサ２２０４に読まれて制御されるプログラムとして備えられる。プログラム及びピクセルデータ及びネットワークからフェッチしたデータの中間的な格納は、半導体メモリ２２０６を用いて、場合によってはハードディスク２２１２と協力して行われる。
【０１０１】
いくつかの場合、このプログラムは、ＣＤ−ＲＯＭやフロッピディスク（ともにブロック２２１２によって一般的に描かれている）にエンコードされて利用者に提供される。あるいはその代わりに、このプログラムは、例えばコンピュータに接続されたモデム装置を介してそのネットワークから利用者が読み出すことができる。さらに、このソフトウエアは、磁気テープ、ＲＯＭあるいは集積回路、光磁気ディスク、コンピュータと他の装置との間の無線あるいは赤外線送信チャネル、ＰＣＭＣＩＡカードといったコンピュータ読み出し可能なカード、及び、ウエブサイト上に記録された情報及び電子メールの送信を含むインターネット及びイントラネット等を含む、コンピュータ読み出し可能な媒体から、コンピュータシステム２２００へとロードすることもできる。前述したものは、単なる適当なコンピュータ読み出し可能な媒体の例にすぎない。他のコンピュータ読み出し可能な媒体を、本発明の範囲及び趣旨から離れることなく用いることもできる。
【０１０２】
広く記述された本発明の趣旨あるいは範囲から逸脱することなく、実施例の示された本発明に対して、多くのバリエーションや変更を加え得ることは、当業者には理解できるであろう。本実施例は、それゆえ、全ての点において説明であり、限定的ではないものと見なされる。
【図面の簡単な説明】
【図１】図１（ａ）−（ｄ）は、編み細工の例をいくつか示した図である。
【図２】文字"h"のケルト風編み細工のデザイン例を示す図である。
【図３】図３（ａ）−（ｃ）は、編み細工デザインの種々のバリエーションを示す図である。
【図４】
【図５】編み細工デザインの利用及び構成のための異なる可能なタイル構成を示す図である。
【図６】好適な実施例による編み細工の重なり合いを処理するプロセスを示す図である。
【図７】編み細工デザインの太さを変化させるプロセスを示す図である。
【図８】境界部分及び内部部分を有する文字を示す図である。
【図９】好適な実施例を用いた単純な網目構造を示す図である。
【図１０】図１０（ａ）−（ｃ）は、編み細工構造における密度パラメータを変化させた効果を示す図である。
【図１１】図１１（ａ）−（ｃ）は、好適な実施例を用いた網目形成のプロセスを示す図である。
【図１２】好適な実施例の網目生成プログラムにより用いられる、定められた点から点を獲得するプロセスを示す図である。
【図１３】図１３（ａ）−（ｃ）は、いくつかのドローネーの三角形を示す図である。
【図１４】図１４（ａ）−（ｂ）は、好適な実施例で使用されているように、三角形から四辺形をを形成するプロセスを示す図である。
【図１５】好適な実施例の例について、最初と最後の網目を示す図である。
【図１６】好適な実施例により分割された、得られた文字のひとつの形を示す図である。
【図１７】好適な実施例の変形によって制作された文字の構造を示す図である。
【図１８】好適な実施例により用いられる三角形のひずみマッピングのプロセスを示す図である。
【図１９】ケルト風フォントのために生み出された第１の効果を示す図である。
【図２０】図２０（ａ）−（ｂ）は、ケルト風フォントの制作を用いる第２の効果を示す図である。
【図２１】好適に実施例のよって、オブジェクトの輪郭中に芸術的な効果を生み出す方法の流れ図である。
【図２２】コンピュータ的な実施例をインプリメントした汎用コンピュータのブロック図である。
【図１】
0004475606.tif 000003
【図２】
0004475606.tif 000004
【図３】
0004475606.tif 000005
【図４】
0004475606.tif 000006
【図５】
0004475606.tif 000007
【図６】
0004475606.tif 000008
【図７】
0004475606.tif 000009
【図８】
0004475606.tif 000010
【図９】
0004475606.tif 000011
【図１０】
0004475606.tif 000012
【図１１】
0004475606.tif 000013
【図１２】
0004475606.tif 000014
【図１３】
0004475606.tif 000015
【図１４】
0004475606.tif 000016
【図１５】
0004475606.tif 000017
【図１６】
0004475606.tif 000018
【図１７】
0004475606.tif 000019
【図１８】
0004475606.tif 000020
【図１９】
0004475606.tif 000021
【図２０】
0004475606.tif 000022
【図２１】
0004475606.tif 000023
【図２２】
0004475606.tif 000024