(57)【要約】【課題】方法はオブジェクトの距離場を生成し、この距離場はセルの集合を含み、オブジェクトはアウトラインの集合を含む。【解決手段】この方法はコンピュータによって実行される。オブジェクトを取り囲むセルの集合の最初のセルを求める。外側再構成方法を、最初のセルに関連付ける。セルの集合のうちの境界セルの集合を求める。各当該境界セルは、アウトラインの集合における特定のアウトラインの一部を取り囲む。境界再構成方法を各境界セルに関連付ける。オブジェクトを取り囲むセルの集合の最後のセルを求める。内側再構成方法を最後のセルに関連付ける。外側再構成方法及び境界再構成方法を使用して、結合された距離を求める。この結合された距離を、内側再構成方法によってさらに処理して、オブジェクトの距離場を生成する。【選択図】図２
2010244519.tif 000002
【特許請求の範囲】
【請求項１】
オブジェクトの距離場を生成するための方法であって、前記距離場はセルの集合を含み、前記オブジェクトはアウトラインの集合を含み、前記方法はコンピュータによって実行され、前記方法は、
前記オブジェクトを取り囲む前記セルの集合の最初のセルを求めるステップと、
前記オブジェクトの外側の点に関する距離値を指定するステップであって、前記オブジェクトの外側の点に関する距離値は負である、指定するステップと、
外側再構成方法を前記最初のセルに関連付けるステップであって、前記外側再構成方法は、前記最初のセルの内側の各点について、前記オブジェクトの外側の前記点に関する前記指定された距離値に対して評価を行う、関連付けるステップと、
前記セルの集合のうちの境界セルの集合を求めるステップであって、各境界セルは、前記アウトラインの集合における特定のアウトラインの一部を取り囲む、求めるステップと、
境界再構成方法を各境界セルに関連付けるステップであって、前記境界再構成方法は、前記境界セルの内側の各点について、前記点から前記特定のアウトラインの前記取り囲まれた一部までの否定符号なし最小距離として、距離を評価する、関連付けるステップと、
前記オブジェクトを取り囲む前記セルの集合の最後のセルを求めるステップと、
内側再構成方法を前記最後のセルに関連付けるステップであって、前記内側再構成方法は、前記アウトラインの集合の内側の点と前記アウトラインの集合の外側の点とを区別する、関連付けるステップと、
前記最初のセルの内側の各点について、結合された距離を求めるステップであって、この求めるステップは、
前記外側再構成方法を使用して前記最初のセルの最初の距離値を求めるステップと、
各境界セルについて、前記境界再構成方法を使用して前記境界セルの境界距離値を求めるステップと、
前記最初のセルの前記最初の距離値及び前記境界セルの前記境界距離値から最大距離値を選択して、前記最初のセルの内側の前記点に関する前記結合された距離を求めるステップとをさらに含む、求めるステップと、
前記最後のセルの前記内側再構成方法を使用して前記アウトラインの集合の内側の各点に関する前記結合された距離の符号を反転して、前記オブジェクトの前記距離場を生成するステップと
を含む、オブジェクトの距離場を生成するための方法。
【請求項２】
前記距離場をレンダリングすることをさらに含む
請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、距離場（distance field）を生成することに関し、より詳細には、アウトラインによって表されるオブジェクトの距離場を生成することに関する。
【背景技術】
【０００２】
コンピュータグラフィックスの分野では、２次元オブジェクトのレンダリングが基本的に重要である。文字形状、企業ロゴ、及び文書に含まれるイラストの要素等の２次元オブジェクトは、静止画像として又はアニメーションを構成するフレームのシーケンスとしてレンダリングされる。２次元オブジェクトには多数の表現があり、レンダリング及び編集等の特定の操作については、或る表現の方が別の表現よりも優れているということが多々ある。これらの場合に、或る形態から別の形態への変換が実行される。
【０００３】
次の特許、すなわち、２００２年５月２８日に発行された「Detail-directed hierarchical distance fields」という発明の名称の米国特許第６，３９６，４９２号、２００７年３月１３日に発行された「Antialiasing an Object Represented as a Two-Dimensional Distance Field in Image-Order」という発明の名称の米国特許第７，０３４，８４５号、２００６年１０月１７日に発行された「Antialiasing a Set of Objects Represented as a Set of 2D Distance Fields in Image-Order」という発明の名称の米国特許第７，１２３，２７１号、及び、２００５年７月１２日に発行された「Method and Apparatus for Rendering Cell-based Distance Fields using Texture Mapping」という発明の名称の米国特許第６，９１７，３６９号によって実証されているように、距離場は、２次元形状のレンダリング及び編集を行うための効果的な表現であることが分かっている。これら特許のすべては、参照により本明細書に援用される。
【０００４】
本明細書では、おそらく最も一般的且つ重要な２次元オブジェクトであるデジタルタイプに主眼を置くが、以下の論述は、すべてのタイプの２次元オブジェクトに当てはまる。
【０００５】
まず、デジタルタイプに関するいくつかの基本的背景について説明する。Times New Roman又はArial等の一般的なラテン語フォントファミリーは、例えば、標準（regular）、斜体（italic）、太字（bold）、及び太字斜体（bold italic）といったフォントの集合を含む。各フォントは、グリフと呼ばれる個々の文字形状の集合を含む。各グリフは、基礎となるジオメトリ、ストロークの太さ、セリフ、ジョイナリ（joinery）、輪郭の配置及び個数、並びに細いストロークと太いストロークとの比等、そのさまざまなデザイン特徴によって区別される。
【０００６】
フォントを表現するには、アウトライン、均一幅ストローク、及びスタイル化ストローク（stylized stroke）を含めて複数の方法がある。
【０００７】
アウトラインベースの表現は、米国マサチューセッツ州ケンブリッジのBitstream Inc.、米国カリフォルニア州マウンテンビューのAdobe Systems Inc.、米国カリフォルニア州クパチーノのApple Computer, Inc.、米国ワシントン州ベルビューのMicrosoft Corporation、ドイツ国ハンブルクのＵＲＷ、及び米国マサチューセッツ州ウィルミントンのAgfa Compugraphicが採用し普及させている。
【０００８】
メモリ使用量を最適化するには、均一幅ストロークフォントを使用することができる。これらのフォントは、通常、部首又は書記素としても知られている均一幅ストロークの集合をグループ化している。均一幅ストロークは、一般に、中国語文字ではフォントの至るところで、文字全体にわたってさらに再利用される単一の単純な形状として、繰り返される。
【０００９】
スタイル化ストロークフォント（ＳＳＦ）は、ストロークが、可変の太さ及びスタイリッシュなストローク端部を有する、高度化されたストロークベースのフォントである。これについては、「An Improved Representation for Stroke-based Fonts」（SIGGRAPH 2006 Conference Abstracts and Applications, Elena J. Jakubiak, Ronald N. Perry, and Sarah F. Frisken）を参照されたい。
【００１０】
ＳＳＦは、参照により本明細書に援用される、２００９年１月２６日付けでJakubiak他によって出願された米国非仮特許出願第１２／３５９，８１９号「Method for Converting Outline Characters to Stylized Stroke Characters」にも記載されている。
【００１１】
ＳＳＦは、フォント内の形状の繰り返しを利用するモジュール構造を用い、ＳＳＦが、アウトラインフォントの表現力を、現在の均一幅ストロークフォントに相当するメモリフットプリントと調和させることを可能にする。
【００１２】
距離ベースのレンダリングの使用を可能にするには、例えば、参照により本明細書に援用される、米国特許第６，９１７，３６９号「Method and Apparatus for Rendering Cell-based Distance Fields using Texture Mapping」を参照されたい。編集等の他の操作をも可能にするには、さまざまな形態によって表されるグリフ等のオブジェクトの距離場を生成するための空間効率及び時間効率の良い方法が必要とされる。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
アウトラインによって表されるオブジェクトの距離場を生成するための空間効率及び時間効率の良い方法を提供することが本発明の目的である。
【課題を解決するための手段】
【００１４】
方法はオブジェクトの距離場を生成し、この距離場はセルの集合を含み、オブジェクトはアウトラインの集合を含む。この方法のステップを実行するためのプロセッサが含まれる。
【００１５】
オブジェクトを取り囲むセルの集合の最初のセルを求める。オブジェクトの外側の点に関する距離値を指定する。当該オブジェクトの外側の点に関する距離値は負である。外側再構成方法（outside reconstruction method）を、最初のセルに関連付ける。当該外側再構成方法は、最初のセルの内側の各点について、オブジェクトの外側の点に関する指定された距離値に対して評価を行う。
【００１６】
セルの集合のうちの境界セルの集合を求める。各当該境界セルは、アウトラインの集合における特定のアウトラインの一部を取り囲む。境界再構成方法（boundary reconstruction method）を各境界セルに関連付ける。当該境界再構成方法は、境界セルの内側の各点について、その点から特定のアウトラインの取り囲まれた一部までの否定符号なし最小距離（negated unsigned minimum distance）として、距離を評価する。
【００１７】
オブジェクトを取り囲むセルの集合の最後のセルを求める。内側再構成方法（inner reconstruction method）を最後のセルに関連付ける。当該内側再構成方法は、アウトラインの集合の内側の点とアウトラインの集合の外側の点とを区別する。
【００１８】
外側再構成方法を使用して最初のセルの最初の距離値を求め、各境界セルについて、境界再構成方法を使用して境界セルの境界距離値を求め、最初のセルの最初の距離値及び境界セルの境界距離値から最大距離値を選択して最初のセルの内側の点に関する結合された距離を求めることにより、最初のセルの内側の各点について、結合された距離を求める。
【００１９】
最後のセルの内側再構成方法を使用して、アウトラインの集合の内側の各点に関する結合された距離の符号を反転し、オブジェクトの距離場を生成する。
【図面の簡単な説明】
【００２０】
【図１】オブジェクトの周囲のアウトラインの集合によって記述される当該オブジェクトであって、当該オブジェクトの距離場が本発明の実施の形態に従って生成されレンダリングされる、オブジェクトの図である。
【図２】本発明の実施の形態による図１のオブジェクトの距離場を生成するための方法のフロー図である。
【発明を実施するための形態】
【００２１】
図１は、オブジェクト１０１を示す。このオブジェクトは、当該オブジェクトの周囲のアウトライン１０２の集合によって記述される。このオブジェクトの距離場は、本発明の実施の形態に従って生成されレンダリングされる。
【００２２】
図２は、本発明の実施の形態によるオブジェクト１０１の距離場２０１を生成するための方法を示す。この方法は、プロセッサ２００によって実行することができる。
【００２３】
この方法は、アウトライン１０２の集合からオブジェクト１０１の距離場２０１を生成する。距離場２０１はセルの集合を含み、オブジェクトはアウトライン１０２の集合を含む。
【００２４】
オブジェクト１０１を取り囲むセルの集合の最初のセルを求める（２１０）。オブジェクト１０１の外側の点に関する距離値を指定する（２２０）。オブジェクト１０１の外側の点に関する距離値は負である。外側再構成方法を、最初のセルに関連付ける（２３０）。外側再構成方法は、最初のセルの内側の各点について、オブジェクト１０１の外側の点に関する指定された距離値に対して評価を行う。
【００２５】
セルの集合のうちの境界セルの集合を求める（２４０）。各境界セルは、アウトライン１０２の集合における特定のアウトラインの一部を取り囲む。境界再構成方法を、各境界セルに関連付ける（２５０）。境界再構成方法は、境界セルの内側の各点について、その点から特定のアウトラインの取り囲まれた一部までの否定符号なし最小距離として距離を評価する。
【００２６】
オブジェクトを取り囲むセルの集合の最後のセルを求め（２６０）、内側再構成方法を、この最後のセルに関連付ける（２７０）。内側再構成方法は、アウトライン１０２の集合の内側の点とアウトライン１０２の集合の外側の点とを区別する。
【００２７】
最初のセルの内側の各点について、結合された距離を求める（２８０）。この求めること（２８０）は、以下のステップを含む。すなわち、
最初のセルの最初の距離値を、外側再構成方法を使用して求める（２８１）。
各境界セルについて、その境界セルの境界距離値を、境界再構成方法を使用して求め（２８２）、最大距離値を、最初のセルの最初の距離値及び境界セルの境界距離値から選択して、最初のセルの内側の点に関する結合された距離を求める（２８３）。
【００２８】
次に、アウトラインの集合の内側の各点に関する結合された距離の符号を、最後のセルの内側再構成方法を使用して反転し（２９０）、オブジェクト１０１の距離場２０１を生成する。
【００２９】
オブジェクト１０１の距離場２０１が生成されると、オブジェクト１０１を観察するための表示デバイスに距離場２０１をレンダリングすることができる。距離場２０１は、米国特許第６，９１７，３６９号「Method and Apparatus for Rendering Cell-based Distance Fields using Texture Mapping」等のさまざまな従来技術の方法を使用してレンダリングすることができる。
【００３０】
オブジェクト１０１の内側の点と外側の点とを区別するのに、異なる符号変換を使用できることに留意すべきである。例えば、オブジェクト１０１の外側の点に関する指定された距離値は、上述したような負ではなく正とすることができる。
【００３１】
動作環境
本発明は、多数の汎用又は専用のコンピューティングシステム環境又はコンピューティングシステム構成で動作可能である。本発明と共に使用するのに適した既知のコンピューティングシステム、コンピューティング環境、及び／又はコンピューティング構成の例には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイス又はラップトップデバイス、マルチプロセッサシステム又はマルチコアシステム、グラフィックス処理ユニット（ＧＰＵ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、マイクロコントローラベースシステム、セットトップボックス、プログラマブル民生用電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記システム又はデバイスの任意のものを含む分散コンピューティング環境等、すなわち一般的にはプロセッサが含まれるが、これらに限定されるものではない。モニタ又は他のタイプの表示デバイスが上記システムの任意のものに接続されて、本発明の実施の形態に従って生成されたオブジェクト１０１の距離場２０１のレンダリングが可能にされる。
【００３２】
上記から分かるように、本発明を並列に動作させる多数の機会がある。例えば、外側再構成方法、境界再構成方法、及び内側再構成方法は、互いの間に依存関係を含まず、したがって、本発明のハードウェア及びマルチコアの実施態様を利用して、オブジェクト１０１の距離場２０１の生成の性能を改善することができる。別の例として、特定の境界セルに関する境界距離値を求めること（２８２）は、相互依存関係を含まず、それによって、特定の境界セルについて境界距離値を並列に求めること（２８２）が可能となる。
【００３３】
特定の好ましい実施態様を参照して本発明を説明してきたが、本発明の精神及び範囲内において、他のさまざまな適合及び変更を行うことができることが理解されるべきである。したがって、本発明の真の精神及び範囲内に入るようなすべてのこのような変形及び変更をカバーすることが添付の特許請求の範囲の目的である。
【図１】
2010244519.tif 000003
【図２】
2010244519.tif 000004
【外国語明細書】
2010244519.tif 000005
2010244519.tif 000006
2010244519.tif 000007
2010244519.tif 000008
2010244519.tif 000009
2010244519.tif 000010
2010244519.tif 000011
2010244519.tif 000012
2010244519.tif 000013
2010244519.tif 000014
2010244519.tif 000015
2010244519.tif 000016
2010244519.tif 000017
2010244519.tif 000018