(57)【要約】【課題】条件分岐を含む処理を行わずに所定の頂点に関連する他の頂点を参照可能とし、処理時間を短縮させることができる情報処理装置等を提供する。【解決手段】本発明の一実施形態における情報処理装置は、多角形の頂点の各々を一意に識別可能な構成点識別子を、当該多角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、当該配列のうち当該所定の頂点から順に所定数の頂点の識別子を当該配列の後に転記し、かつ、当該配列のうち当該所定数以降の頂点の識別子を当該配列の前に転記した拡張配列を記憶する記憶部と、当該配列と当該拡張配列の中から当該多角形の頂点を参照する参照部と、を含み、当該参照部は、当該多角形のうちの任意の頂点を、当該配列から参照し、当該任意の頂点に関連する他の頂点の識別子を、当該任意の頂点を基準とする所定の定義に基づいて参照する。【選択図】図４
2018160032.tif 000002
【特許請求の範囲】
【請求項１】
多角形の頂点の各々を一意に識別可能な構成点識別子を、当該多角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、当該配列のうち当該所定の頂点から順に所定数の頂点の識別子を当該配列の後に転記し、かつ、当該配列のうち当該所定数以降の頂点の識別子を当該配列の前に転記した拡張配列を記憶する記憶部と、
前記配列と前記拡張配列の中から前記多角形の頂点を参照する参照部と、を含み、
前記参照部は、前記多角形のうちの任意の頂点を、前記配列から参照し、前記任意の頂点に関連する他の頂点の識別子を、当該任意の頂点を基準とする所定の定義に基づいて参照する情報処理装置。
【請求項２】
多角形は、Ｎ角形（Ｎは自然数）であり、
前記任意の頂点に関する他の頂点の識別子は、当該任意の頂点を基準として右（または左）にＭ個（Ｍは整数かつＮ＞Ｍ）並んだ要素および、当該任意の頂点を基準として左（または右）に（Ｎ−Ｍ―１）個並んだ要素から参照される
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記参照部は、前記隣接する頂点の識別子を、前記配列又は拡張配列のうち前記任意の頂点に隣接する要素から参照することを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
多角形は、Ｎ角形（Ｎは自然数かつ偶数）であり、
前記参照部は、前記任意の頂点の識別子について、当該任意の頂点を基準として（Ｎ／２）個先の要素を参照することで、任意の頂点に対する対角の頂点を参照することを特徴とする請求項１乃至３のいずれかに記載の情報処理装置。
【請求項５】
前記多角形は、三角形であり、
前記記憶部は、前記三角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、前記三角形のうちの前記所定の頂点の識別子を当該配列の後に転記し、かつ、当該配列において当該所定の頂点の２つ先の頂点の識別子を当該配列の前に転記した拡張配列を記憶することを特徴とする請求項１乃至４のいずれかに記載の情報処理装置。
【請求項６】
前記多角形は、四角形であり、
前記記憶部は、前記四角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、前記四角形のうちの前記所定の頂点および隣接する頂点の識別子を当該配列の後に転記し、かつ、当該配列において当該所定の頂点の３つ先の頂点の識別子を当該配列の前に転記した拡張配列を記憶することを特徴とする請求項１乃至５のいずれかに記載の情報処理装置。
【請求項７】
前記参照部は、前記他の頂点として前記任意の頂点の対角の点の識別子を参照する場合、前記配列又は拡張配列のうち当該任意の頂点の２つ先の要素を参照することを特徴とする請求項６に記載の情報処理装置。
【請求項８】
多角形の頂点の各々を一意に識別可能な構成点識別子を、当該多角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、当該配列のうち当該所定の頂点から順に所定数の頂点の識別子を当該配列の後に転記し、かつ、当該配列のうち当該所定数以降の頂点の識別子を当該配列の前に転記した拡張配列を記憶する記憶ステップと、
前記配列と前記拡張配列の中から前記多角形の頂点を参照する参照ステップと、を含み、
前記参照ステップにおいて、前記多角形のうちの任意の頂点を、前記配列から参照し、当該任意の頂点に関連する他の頂点の識別子を、当該任意の頂点を基準とする所定の定義に基づいて参照する情報処理方法。
【請求項９】
コンピュータに、
多角形の頂点の各々を一意に識別可能な構成点識別子を、当該多角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、当該配列のうち当該所定の頂点から順に所定数の頂点の識別子を当該配列の後に転記し、かつ、当該配列のうち当該所定数以降の頂点の識別子を当該配列の前に転記した拡張配列を記憶する記憶機能と、
前記配列と前記拡張配列の中から前記多角形の頂点を参照する参照機能と、を実行させ、
前記参照機能において、前記多角形のうちの任意の頂点を、前記配列から参照し、当該任意の頂点に関連する他の頂点の識別子を、当該任意の頂点を基準とする所定の定義に基づいて参照することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元グラフィックスにおいて多角形を描写する情報処理装置、情報処理方法およびプログラムに関するものである。
【背景技術】
【０００２】
三次元グラフィックスにおいて、三角形や四角形を描写するためには、当該三角形や四角形の頂点に関するデータを格納する配列を作成する。特許文献１および特許文献２には、三角形の頂点を識別する識別子を、所定の頂点から順に格納した配列が開示されている（特許文献１の図１Ｃや、特許文献２の図５を参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−２２１６５０号公報
【特許文献２】特開２００１−３５９０９３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１及び特許文献２に記載の配列を用いると、三角形の所定の頂点に関連する他の頂点を参照する場合、まず、当該所定の頂点の格納位置を特定する処理を行い、その後、特定した格納位置に基づいて他の頂点の識別子の格納位置を決定する。その場合において、特許文献１及び特許文献２に記載の技術では、他の頂点の識別子の格納位置を参照する際には、所定の頂点の格納位置に基づいて、適切な参照処理を選択し、実行する必要がある。すなわち、所定の頂点の格納位置に基づいて、他の頂点の識別子の格納位置を参照する処理が異なるため、該所定の頂点の格納位置に応じて、複数の処理から適切な参照処理を決定する必要がある。言い換えると、他の頂点の識別子の格納位置を参照するためには、所定の頂点の格納位置に基づく条件分岐を経る必要がある。そのため、特許文献１および特許文献２に記載の技術では、条件分岐を含む処理を実行する必要があり、その分だけ余計に処理時間を要していた。
【０００５】
そこで、本発明の目的は、上記の課題に鑑み、多角形の頂点に対応する識別子を格納した配列を拡張することで、条件分岐を含む処理を行わずに任意の頂点に関連する他の頂点を参照可能とし、該他の頂点の格納位置を参照する際の処理時間を短縮させることができる情報処理装置、情報処理方法およびプログラムを提供することである。
【課題を解決するための手段】
【０００６】
本発明の一実施形態における情報処理装置は、多角形の頂点の各々を一意に識別可能な構成点識別子を、当該多角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、当該配列のうち当該所定の頂点から順に所定数の頂点の識別子を当該配列の後に転記し、かつ、当該配列のうち当該所定数以降の頂点の識別子を当該配列の前に転記した拡張配列を記憶する記憶部と、当該配列と当該拡張配列の中から当該多角形の頂点を参照する参照部と、を含み、当該参照部は、当該多角形のうちの任意の頂点を、当該配列から参照し、当該任意の頂点に関連する他の頂点の識別子を、当該任意の頂点を基準とする所定の定義に基づいて参照する。
【０００７】
本発明の一実施形態における情報処理装置において、多角形は、Ｎ角形（Ｎは自然数）であり、当該任意の頂点に関する他の頂点の識別子は、当該任意の頂点を基準として右（または左）にＭ個（Ｍは整数かつＮ＞Ｍ）並んだ要素および、当該任意の頂点を基準として左（または右）に（Ｎ−Ｍ―１）個並んだ要素から参照されることを特徴としてもよい。
【０００８】
本発明の一実施形態における情報処理装置において、当該参照部は、当該隣接する頂点の識別子を、当該配列又は拡張配列のうち当該任意の頂点に隣接する要素から参照することを特徴としてもよい。
【０００９】
本発明の一実施形態における情報処理装置において、多角形は、Ｎ角形（Ｎは自然数かつ偶数）であり、当該参照部は、当該対角の頂点の識別子について、当該任意の頂点を基準として（Ｎ／２）個先の要素を参照することで、任意の頂点に対応する対角の頂点を参照することを特徴としてもよい。
【００１０】
本発明の一実施形態における情報処理装置において、当該多角形は、三角形であり、当該記憶部は、当該三角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、当該三角形のうちの当該所定の頂点の識別子を当該配列の後に転記し、かつ、当該配列において当該所定の頂点の２つ先の頂点の識別子を当該配列の前に転記した拡張配列とを記憶することを特徴としてもよい。
【００１１】
本発明の一実施形態における情報処理装置において、当該多角形は、四角形であり、当該記憶部は、当該四角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、当該四角形のうちの当該所定の頂点および隣接する頂点の識別子を当該配列の後に転記し、かつ、当該配列において当該所定の頂点の３つ先の頂点の識別子を当該配列の前に転記した拡張配列とを記憶することを特徴としてもよい。
【００１２】
本発明の一実施形態における情報処理装置において、当該参照部は、当該他の頂点として当該任意の頂点の対角の点の識別子を参照する場合、当該配列又は拡張配列のうち当該任意の頂点の２つ先の要素を参照することを特徴としてもよい。
【００１３】
本発明の一実施形態における情報処理方法は、多角形の頂点の各々を一意に識別可能な構成点識別子を、当該多角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、当該配列のうち当該所定の頂点から順に所定数の頂点の識別子を当該配列の後に転記し、かつ、当該配列のうち当該所定数以降の頂点の識別子を当該配列の前に転記した拡張配列を記憶する記憶ステップと、当該配列と当該拡張配列の中から当該多角形の頂点を参照する参照ステップと、を含み、当該参照ステップにおいて、当該多角形のうちの任意の頂点を、当該配列から参照し、当該任意の頂点に関連する他の頂点の識別子を、当該任意の頂点を基準とする所定の定義に基づいて参照する。
【００１４】
本発明の一実施形態におけるプログラムは、コンピュータに、多角形の頂点の各々を一意に識別可能な構成点識別子を、当該多角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列と、当該配列のうち当該所定の頂点から順に所定数の頂点の識別子を当該配列の後に転記し、かつ、当該配列のうち当該所定数以降の頂点の識別子を当該配列の前に転記した拡張配列を記憶する記憶機能と、当該配列と当該拡張配列の中から当該多角形の頂点を参照する参照機能と、を実行させ、当該参照機能において、当該多角形のうちの任意の頂点を、当該配列から参照し、当該任意の頂点に関連する他の頂点の識別子を、当該任意の頂点を基準とする所定の定義に基づいて参照することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、多角形の頂点に対応する識別子を格納した配列を拡張することで、条件分岐を含む処理を行わずに任意の頂点に関連する他の頂点を参照可能とし、該他の頂点の格納位置を参照する際の処理時間を短縮させることができる情報処理装置、情報処理方法およびプログラムを提供することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施態様における情報処理装置の構成例を示すブロック図である。
【図２】本発明の一実施態様における情報処理装置が描写する多角形の構成例を示す図である。
【図３】本発明の一実施態様における配列の構成例を示す表である。
【図４】本発明の一実施態様における拡張配列の構成例を示す表である。
【図５】本発明の一実施態様における情報処理装置の動作例を示すフローチャートである。
【図６】本発明の一実施態様における情報処理装置が描写する三角形の構成例を示す図である。
【図７】本発明の一実施態様における三角形の場合の配列の構成例を示す表である。
【図８】本発明の一実施態様における三角形の場合の拡張配列の構成例を示す表である。
【図９】本発明の一実施態様における三角形の場合の情報処理装置の動作例を示すフローチャートである。
【図１０】本発明の一実施態様における情報処理装置が描写する四角形の構成例を示す図である。
【図１１】本発明の一実施態様における四角形の場合の配列の構成例を示す表である。
【図１２】本発明の一実施態様における四角形の場合の拡張配列の構成例を示す表である。
【図１３】本発明の一実施態様における四角形の場合の情報処理装置の動作例を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、図面を参照しながら、本発明の一実施態様を詳細に説明する。
【００１８】
図１は、情報処理装置１００の構成例を示すブロック図である。図１に示すように、情報処理装置１００は、制御部１１０と、記憶部１２０を含む。また、制御部１１０は、拡張部１１１と、参照部１１２を含む。
【００１９】
情報処理装置１００は、ディスプレイ上に多角形を３次元グラフィックとして描画するコンピュータ等である。情報処理装置１００は、例えば、以下で説明する処理を含むプログラムを実行可能な情報処理装置である。情報処理装置１００は、以下の処理を実行可能な機器でありさえすれば具体的な機器は携帯端末に限定されず、例えば、スマートフォン、タブレット端末、家庭用ゲーム機、携帯電話（フィーチャーフォン）、パーソナルコンピュータ、その他の電子機器であってもよい。なお、上記プログラムは、ディスプレイ（表示部）と、指やスタイラス等によるタッチ入力を検知可能な入力領域（入力受付部）と、メモリと、メモリに格納された１つ又は複数のプログラムを実行可能な１つ又は複数のプロセッサとを備えた、マルチファンクションデバイス（例えば、スマートフォン等）において好適に実行される。
【００２０】
ここで、情報処理装置１００が多角形としてＮ角形を描画する場合、当該Ｎ角形は、Ｎ個の頂点によって規定される。Ｎ角形の各々の頂点は、それぞれの頂点を一意に識別可能な構成点ＩＤ（ＩＤｅｎｔｉｆｉｅｒ）が割り当てられる。
【００２１】
図２は、ディスプレイ上に３次元グラフィックとして描画されるＮ角形（多角形）の例を示す概略図である。図２に示すように、Ｎ角形には、Ｎ角形ＩＤとして「１」が割り当てられている。Ｎ角形ＩＤは、一のＮ角形を、他のＮ角形から一意に識別可能な識別子である。なお、Ｎは、自然数である。
【００２２】
また、Ｎ角形（多角形）の各頂点が該Ｎ角形（多角形）の構成点として登録され、そのうちの任意の頂点に対して、構成点ＩＤ−Ａとして「１」が割り当てられる。同様にして、該任意の頂点に隣接する各頂点に、構成点ＩＤ−Ｂとして「２」、構成点ＩＤ−Ｃとして「３」と、順次割り当てられる。そして、Ｎ個目の頂点に対応する頂点には、構成点ＩＤ−Ｎとして「Ｎ」が割り当てられる。構成点ＩＤは、Ｎ角形の頂点を一意に識別可能なＩＤである。
【００２３】
ここで、情報処理装置１００の記憶部１２０は、多角形の頂点の各々を一意に識別可能な構成点識別子を、当該多角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列を記憶する。
【００２４】
図３は、Ｎ角形（多角形）の頂点の配列の一例を示す表である。図２に示すように、Ｎ角形（多角形）の配列は、Ｎ角形（多角形）に含まれる頂点の各々について、当該頂点を一意に識別可能な識別子を含む。また、Ｎ角形（多角形）の配列は、任意の頂点の識別子から順に、隣接する頂点の識別子を並べた配列である。
【００２５】
ここで、図３に例示するように、配列において、Ｎ角形ＩＤが「１」のＮ角形に対し、所定の頂点の構成点ＩＤ−Ａとして「１」が、対応付けられている。また、Ｎ角形ＩＤが「１」のＮ角形の配列において、所定の頂点に隣接する他の頂点について順番に、構成点ＩＤ−Ｂとして「２」が、構成点ＩＤ−Ｃとして「３」が対応付けられている。同様にして、Ｎ番目の頂点には、構成点ＩＤ−Ｎとして「Ｎ」が対応付けられている。すなわち、図８に例示するように、図７に例示する三角形について、三角形ＩＤ「１」と、構成点ＩＤ―Ａ「１」と、構成点ＩＤ―Ｂ「２」と、構成点ＩＤ―Ｃ「３」と、・・・構成点ＩＤ−Ｎ「Ｎ」が対応付けて記憶されている。
【００２６】
図３に例示するように、ディスプレイ上に三角形を３次元グラフィックとして描画する場合、データを格納する配列において、Ｎ角形（多角形）のＮ角形ＩＤ１つに対して、Ｎ角形の頂点として構成点ＩＤがＮ個割り振られる。情報処理装置１００は、記憶された配列に基づいて、Ｎ角形（多角形）の所定の頂点に関連する他の頂点等を認識する。
【００２７】
情報処理装置１００の制御部１１０の参照部１１２は、多角形のうちの任意の頂点を、配列から参照する。参照部１１２は、当該多角形のうちの任意の頂点を、当該配列から参照し、当該任意の頂点に関連する他の頂点の識別子を、当該任意の頂点を基準とする所定の定義に基づいて参照する。具体的には、参照部１１２は、任意の頂点に関する他の頂点の識別子を、当該任意の頂点を基準として右（または左）にＭ個（Ｍは整数かつＮ＞Ｍ）並んだ要素および、当該任意の頂点を基準として左（または右）に（Ｎ−Ｍ―１）個並んだ要素から参照する。
【００２８】
任意の頂点に関する他の頂点は、例えば、Ｎ角形（多角形）の任意の頂点の隣接点である。すなわち、参照部１１２は、Ｎ角形（多角形）の任意の頂点の隣接点の構成点ＩＤを参照する処理を行う場合がある。以下では、Ｎ角形（多角形）の任意の頂点の隣接点の構成点ＩＤを参照する場合を例にして説明する。なお、参照部１１２は、隣接する頂点だけでなく、例えば任意の頂点の対角点を参照するなど、Ｎ角形（多角形）の任意の頂点に関連する他の頂点を参照する処理を行うことができる。
【００２９】
この場合において、図３の配列を用いる場合、参照部１１２は、まず構成点ＩＤが「１」の頂点が、構成点ＩＤ−Ａであることを検索する。その後、参照部１１２は、構成点ＩＤ−Ａが「１」であったことから、例えば、構成点ＩＤ−Ｂの頂点が右隣の頂点に該当し、構成点ＩＤ−Ｎの頂点が左隣の頂点に該当すると判定する。そして、参照部１１２は、構成点ＩＤが「１」の頂点の右隣の頂点の構成点ＩＤとして、構成点ＩＤ−Ｂの「２」を参照する。同様にして、参照部１１２は、構成点ＩＤが「１」の頂点の左隣の頂点の構成点ＩＤとして、構成点ＩＤ−Ｎの「Ｎ」を参照する。
【００３０】
このように、参照部１１２が、図３に例示する配列を用いて、Ｎ角形（多角形）の任意の頂点（構成点ＩＤが「１」）の隣接点（隣接する頂点）を参照する場合、まず任意の頂点の構成点ＩＤである「１」が、構成点ＩＤ−Ａ乃至Ｎのいずれかを特定する。例えば、参照部１１２は、任意の構成の構成点ＩＤである「１」が、構成点ＩＤ−Ａに格納されていると特定する。その後、参照部１１２は、特定の結果を用いて、任意の頂点に隣接する頂点が構成点ＩＤ−Ｂと構成点ＩＤ−Ｎに格納されていることを決定する。そして、参照部１１２は、任意の頂点に隣接する頂点の構成点ＩＤとして、構成点ＩＤ−ＢとＮに格納されている構成点ＩＤである「２」と「Ｎ」を参照することになる。
【００３１】
図３に例示する配列では、任意の頂点の構成点ＩＤである「１」が、構成点ＩＤ−Ａ乃至Ｎのいずれに格納されているか特定し、その後、該特定した格納位置に基づいて決定される処理ごとに、他の頂点の識別子の格納位置を決定する処理を実行する必要がある。すなわち、構成点ＩＤ「１」の格納位置に基づいて、他の頂点の識別子の格納位置を参照する処理が異なるため、該構成点ＩＤ「１」の格納位置に応じて、複数の処理から適切な参照処理を決定する必要がある。言い換えると、他の頂点の識別子の格納位置を参照するためには、構成点ＩＤ「１」の格納位置に基づく条件分岐を経る必要がある。そのため、条件分岐や、当該条件分岐に伴う情報処理端末１００のＣＰＵ内部の分岐予測、当該分岐予測に伴うパイプラインの生成を行う必要があり、その分だけ他の頂点の格納位置を参照する参照処理に要する処理時間が長くなってしまう。
【００３２】
そこで、本発明の情報処理装置１００では、拡張部１１１が、図４に例示する配列を拡張することにより、参照部１１２が、Ｎ角形（多角形）の任意の頂点とは異なる他の頂点の構成点ＩＤを参照するための処理を単純化して、当該処理を高速化する。具体的には、拡張部１１１が、配列のうち所定の頂点から順に所定数の頂点の識別子を当該配列の後に転記し、かつ、多角形の頂点のうち当該所定数以降の頂点の識別子を当該配列の前に転記した拡張配列を作成する。拡張配列を用いることにより、構成点ＩＤ「１」が配列のどこに格納されていても、他の頂点を参照する際に参照すべき格納位置は、該構成点ＩＤ「１」の格納位置から相対的に変化しないことになる。そのため、拡張部１１１は、配列における構成点ＩＤ「１」の格納位置に応じて、他の頂点を参照するための処理を変化させる必要がなくなる。
【００３３】
拡張配列は、多角形がＮ角形（Ｎは自然数）の場合、所定の頂点（任意の頂点）を基準として定義される拡張配列は、所定の頂点を基準として右にＭ個（Ｍは整数かつＮ＞Ｍ）の要素が該配列の右に並び、所定の頂点を基準として左に（Ｎ−Ｍ―１）個の要素が該配列の左に並ぶ配列である。
【００３４】
図４は、Ｎ角形（多角形）の場合における、拡張配列を示す表である。図４に示すように、情報処理装置１００の制御部１１０の拡張部１１１は、所定の頂点の識別子を図３に例示する配列の後に転記し、かつ、当該配列において当該所定の頂点の２つ先の頂点の識別子を当該配列の前に転記する。つまり、図４に例示するように、図３の配列に含まれる構成点ＩＤ−Ａの前に、所定数以降の配列である「構成点ＩＤ−Ｙ」から「構成点ＩＤ−Ｎ」を転記する。加えて、拡張部１１１は、図３の配列に含まれる構成点ＩＤ−Ｎの後に、所定数の配列である「構成点ＩＤ−Ａ」から「構成点ＩＤ−Ｘ」を転記する。このように、拡張部１１１は、図４に例示するように、図３の配列を拡張した拡張配列を、記憶部１２０に記憶する。
【００３５】
参照部１１２は、図４の拡張配列を参照して、例えば、任意の頂点の隣接点を参照する場合の処理を説明する。参照部１１２は、まず、配列に含まれる複数の要素のうち、任意の頂点の構成点ＩＤである「１」が格納されている要素を特定する。その後、参照部１１２は、配列において、特定した要素の前後の要素を参照し、隣接点（隣接する頂点）に対応する構成点ＩＤを決定する。
【００３６】
ここで、図４に例示する拡張配列を用いているため、配列に含まれる要素は、いずれもその前後に要素が存在することになる。例えば、図４の拡張配列の場合、配列に含まれる構成点ＩＤ−Ａの前には、拡張部１１１によって転記された要素である「構成点ＩＤ−Ｎ」が拡張されている。また、配列に含まれる構成点ＩＤ−Ｎの後には、拡張部１１１によって転記された要素である「構成点ＩＤ−Ａ」が拡張されている。その結果、配列に含まれるいずれの要素（要素Ａとする）についても、その両隣に要素（要素ＢおよびＣとする）が存在する。そして、その要素（要素Ａ）の両隣の要素は、その要素（要素Ａ）に対応する頂点に隣接する頂点の構成点ＩＤが格納されている。すなわち、拡張配列を用いることにより、構成点ＩＤ「１」が配列のどこに格納されていても、隣接する頂点の識別子の格納位置は、該構成点ＩＤ「１」の格納位置の前後となる。このように、拡張配列を用いると、任意の頂点の構成点ＩＤの格納位置に対する、他の頂点の構成点ＩＤの相対的な格納位置が変わらなくなる。その結果、任意の頂点の構成点ＩＤの格納位置に応じて、他の頂点の構成点ＩＤの格納位置を特定する処理（参照処理）を変更することなく、常に同一の参照処理を実行すればよいことになる。
【００３７】
なお、任意の頂点に隣接する頂点の構成点ＩＤの格納位置は、該任意の頂点の構成点ＩＤの格納位置の前後に限られず、例えば、任意の頂点の構成点ＩＤの格納位置を始点として右（または左）に連続した格納位置に格納されていてもよい。
【００３８】
参照部１１２は、任意の頂点の構成点ＩＤである「１」が格納されている要素を特定すれば、その後、特定した要素の前後の要素が、該任意の頂点に隣接する頂点の構成点ＩＤであると決定できる。そのため、図３の配列を用いて参照する場合に比べて、条件分岐を実行するための処理を行う必要が無くなり、多角形の任意の頂点に隣接する頂点の構成点ＩＤを参照するために要する参照処理を単純化できる。したがって、情報処理装置１００は、Ｎ角形の任意の頂点の隣接点の構成点ＩＤを参照する処理を実行する場合、図４に例示する拡張配列を用いることで、参照処理に要する処理負荷削減することが可能となり、処理時間を短縮させることができる。
【００３９】
また、参照部１１２が、図４の拡張配列を参照して、例えば、任意の頂点の対角点を参照する場合の処理を説明する。ただし、対角点を参照できるのは、対角点が存在する多角形に限られ、Ｎが偶数の場合のＮ角形である。参照部１１２は、まず、配列のうち任意の頂点の構成点ＩＤである「１」が格納されている要素を特定する。その後、参照部１１２は、配列及び拡張配列において、特定した要素の「Ｎ／２」個先の要素に対応する構成点ＩＤを決定する。なお、Ｎ角形において、特定した要素の「Ｎ／２」が対角点の要素となる。
【００４０】
ここで、図４に例示する拡張配列を用いているため、該拡張配列に含まれる配列のいずれの要素についても、その「Ｎ／２」個先の要素が存在することになる。例えば、図４の拡張配列の場合、構成点ＩＤ−Ａの前に、所定数以降の配列である「構成点ＩＤ−Ｙ」から「構成点ＩＤ−Ｎ」を転記されている。加えて、拡張部１１１は、図３の配列に含まれる構成点ＩＤ−Ｎの後に、所定数の配列である「構成点ＩＤ−Ａ」から「構成点ＩＤ−Ｘ」を転記されている。その結果、拡張配列に含まれる配列のうち、いずれの要素についても、「Ｎ／２」個先の要素が存在し、その要素の「Ｎ／２」個先の要素は、その要素の対角点の構成点ＩＤが格納されていることになる。すなわち、拡張配列を用いることにより、任意の頂点の識別子が配列のどこに格納されていても、対角点に対応する識別子の格納位置は、該任意の頂点の識別子の格納位置から相対的に変化せず、該任意の頂点の識別子の格納位置から常に「Ｎ／２」個先ということになる。
【００４１】
このように、参照部１１２は、配列のうち任意の頂点の構成点ＩＤである「１」が格納されている要素を特定すれば、その後、特定した要素の「Ｎ／２」個先の要素が、該任意の頂点の対角点の構成点ＩＤであると決定できる。そのため、図３の配列を用いて参照する場合に比べて、条件分岐を実行するための処理を行う必要が無くなり、任意の頂点の対角点の構成点ＩＤを参照するために要する参照処理を単純化できる。したがって、情報処理装置１００は、図４に例示する拡張配列を用いることで、参照処理に要する処理負荷を削減することが可能となり、処理時間を短縮させることができる。
【００４２】
図５は、情報処理装置１００の動作例を示すフローチャートである。
【００４３】
図５に示すように、記憶部１２０は、多角形の頂点の各々を一意に識別可能な構成点識別子を、当該多角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列を記憶する（Ｓ１０１）。
【００４４】
その後、制御部１１０の拡張部１１１は、配列のうち所定の頂点から順に所定数の頂点の識別子を当該配列の後に転記し、かつ、多角形の頂点のうち当該所定数以降の頂点の識別子を当該配列の前に転記した拡張配列を作成する（Ｓ１０２）。記憶部１２０は、拡張配列を記憶する（Ｓ１０３）。
【００４５】
そして、制御部１１０の参照部１１２は、多角形のうちの任意の頂点を、当該配列から参照し、当該任意の頂点に関連する他の頂点の識別子を、当該任意の頂点を基準とする所定の定義に基づいて参照する（Ｓ１０４）。具体的には、参照部１１２は、例えば、Ｎ角形（Ｎは自然数）について、当該任意の頂点に関する他の頂点の識別子を、当該任意の頂点を基準として右（または左）にＭ個（Ｍは整数かつＮ＞Ｍ）並んだ要素および、当該任意の頂点を基準として左（または右）に（Ｎ−Ｍ―１）個並んだ要素から参照する。
【００４６】
このように、情報処理装置１００は、図４に例示する拡張配列を用いることで、例えば、Ｎ角形（多角形）の任意の頂点の隣接点の構成点ＩＤを参照する処理を実行する場合などに、参照処理に要する処理負荷を削減することが可能となり、処理時間を短縮させることができる。
【００４７】
（三角形の場合の実施例）
図６は、ディスプレイ上に３次元グラフィックとして描画される三角形の例を示す概略図である。図６に示すように、三角形には、三角形ＩＤとして「１」が割り当てられている。三角形ＩＤは、一の三角形を、他の三角形から一意に識別可能な識別子である。
【００４８】
また、三角形の各頂点が該三角形の構成点として登録され、そのうちの任意の頂点に対して、構成点ＩＤ−Ａとして「１」が割り当てられる。同様にして、該任意の頂点に隣接する各頂点に、構成点ＩＤ−Ｂとして「２」、構成点ＩＤ−Ｃとして「３」がそれぞれ割り当てられる。構成点ＩＤは、三角形の頂点を一意に識別可能なＩＤである。
【００４９】
図７は、図６に例示した三角形の頂点に関する情報を示す配列の構成例を示す表である。
【００５０】
図７に例示するように、配列において、三角形ＩＤが「１」の三角形に対し、所定の頂点の構成点ＩＤ−Ａとして「１」が、対応付けられている。また、三角形ＩＤが「１」の三角形の配列において、所定の頂点に隣接する他の頂点について順番に、構成点ＩＤ−Ｂとして「２」が、構成点ＩＤ−Ｃとして「３」が対応付けられている。すなわち、図７に例示するように、図６に例示する三角形について、三角形ＩＤ「１」と、構成点ＩＤ―Ａ「１」と、構成点ＩＤ―Ｂ「２」と、構成点ＩＤ―Ｃ「３」と、が対応付けて記憶されている。
【００５１】
図７に例示するように、ディスプレイ上に三角形を３次元グラフィックとして描画する場合、データを格納する配列において、三角形の三角形ＩＤ１つに対して、三角形の頂点として構成点ＩＤが３つずつ割り振られる。情報処理装置１００は、記憶された配列に基づいて、三角形の任意の頂点や、当該任意の頂点に隣接する頂点等を認識する。
【００５２】
ここで、情報処理装置１００の参照部１１２は、三角形の任意の頂点の隣接点の構成点ＩＤを参照する処理を行う場合がある。この場合において、図７の配列を用いる場合、参照部１１２は、まず構成点ＩＤが「１」の頂点が、構成点ＩＤ−Ａであることを検索する。その後、参照部１１２は、構成点ＩＤ−Ａが「１」であったことから、構成点ＩＤ−Ｂの頂点が右隣の頂点に該当し、構成点ＩＤ−Ｃの頂点が左隣の頂点に該当すると判定する。そして、参照部１１２は、任意の頂点の右隣の頂点の構成点ＩＤとして、構成点ＩＤ−Ｂの「２」を参照する。同様にして、参照部１１２は、任意の頂点の左隣の頂点の構成点ＩＤとして、構成点ＩＤ−Ｃの「３」を参照する。
【００５３】
このように、参照部１１２が、図７に例示する配列を用いて、三角形の任意の頂点（構成点ＩＤが「１」）の隣接点（隣接する頂点）を参照する場合、まず任意の頂点の構成点ＩＤである「１」が、構成点ＩＤ−Ａ乃至Ｃのいずれかを特定する。例えば、参照部１１２は、任意の構成の構成点ＩＤである「１」が、構成点ＩＤ−Ａに格納されていると特定する。その後、参照部１１２は、特定の結果を用いて、任意の頂点に隣接する頂点が構成点ＩＤ−ＢとＣに格納されていることを決定する。そして、参照部１１２は、任意の頂点に隣接する頂点の構成点ＩＤとして、構成点ＩＤ−ＢとＣに格納されている構成点ＩＤである「２」と「３」を参照することになる。ここで、任意の頂点の構成点ＩＤである「１」の格納位置が配列のどこに格納されているかにより、他の頂点（隣接する頂点）の構成点ＩＤの格納位置を参照する処理が異なる。図７に例示する配列では、配列の一番左に所定の頂点の構成点ＩＤである「１」が格納されているため、隣接する頂点の構成点ＩＤは、配列の“真ん中”と“一番右”に格納されていることなる。一方、図７の例とは異なり、配列の一番右側に任意の頂点の構成点ＩＤである「１」が格納されている場合には、隣接する頂点の構成点ＩＤは、配列の“一番左”と“真ん中”に格納されていることになる。すなわち、任意の頂点の構成点ＩＤである「１」の格納位置に応じて、隣接する頂点の構成点ＩＤの格納位置を参照するための処理が異なることになる。
【００５４】
上記のとおり、図７に例示する配列では、任意の頂点の構成点ＩＤである「１」の格納位置に基づいて、他の頂点（隣接する頂点）の識別子の格納位置を参照する処理が異なるため、該構成点ＩＤ「１」の格納位置に応じて、複数の処理から適切な参照処理を決定する必要がある。言い換えると、他の頂点の識別子の格納位置を参照するためには、構成点ＩＤ「１」の格納位置に基づく条件分岐を経る必要がある。そのため、条件分岐や、当該条件分岐に伴う情報処理端末１００のＣＰＵ内部の分岐予測、当該分岐予測に伴うパイプラインの生成を行う必要があり、その分だけ他の頂点の格納位置を参照する参照処理に要する処理時間が長くなってしまう。
【００５５】
そこで、本発明の情報処理装置１００では、拡張部１１１が、図７に例示する配列を拡張することにより、参照部１１２が、任意の頂点の構成点ＩＤの格納位置に依存せず、いつでも同一の処理によって該任意の頂点に隣接する頂点の構成点ＩＤを参照することができるようにすることで、隣接する頂点の構成点ＩＤを参照するための参照処理を単純化して、当該参照処理を高速化する。
【００５６】
図８は、三角形の場合における、拡張配列を示す表である。図８に示すように、情報処理装置１００の制御部１１０の拡張部１１１は、所定の頂点の識別子を図６に例示する配列の後に転記し、かつ、当該配列において当該所定の頂点の２つ先の頂点の識別子を当該配列の前に転記する。つまり、図８に例示するように、図７の配列に含まれる構成点ＩＤ−Ａの前に、「構成点ＩＤ−Ｃ」を転記し、かつ、図７の配列に含まれる構成点ＩＤ−Ｃの後に、「構成点ＩＤ−Ａ」を転記する。三角形ＩＤが「１」の場合には、図８に例示するように、配列の後に、構成点ＩＤ−Ａである「１」を追加し、かつ、配列の前に、構成点ＩＤ−Ｃである「３」を追加する。このように、拡張部１１１は、図８に例示するように、図７の配列を拡張した拡張配列を、記憶部１２０に記憶する。
【００５７】
参照部１１２は、図８の拡張配列を参照して、例えば、任意の頂点の隣接点を参照する場合の処理を説明する。参照部１１２は、まず、拡張配列に含まれる配列のうち、任意の頂点の構成点ＩＤである「１」が格納されている要素を特定する。その後、参照部１１２は、配列において、特定した要素の前後の要素を参照し、隣接点（隣接する頂点）に対応する構成点ＩＤを決定する。
【００５８】
ここで、図８に例示する拡張配列を用いているため、該拡張配列に含まれる配列のいずれの要素についても、その前後の要素が存在することになる。例えば、図８の拡張配列の場合、配列に含まれる構成点ＩＤ−Ａの前には、拡張部１１１によって転記された要素である「構成点ＩＤ−Ｃ」が拡張されている。また、配列に含まれる構成点ＩＤ−Ｃの後には、拡張部１１１によって転記された要素である「構成点ＩＤ−Ａ」が拡張されている。その結果、拡張配列に含まれる配列のうち、いずれの要素（要素Ａとする）についても、その両隣に要素（要素ＢおよびＣとする）が存在し、その要素（要素Ａ）の両隣の要素は、その要素（要素Ａ）に対応する頂点に隣接する頂点の構成点ＩＤが格納されていることになる。
【００５９】
このように、参照部１１２は、任意の頂点の構成点ＩＤである「１」が格納されている要素を特定すれば、その後、特定した要素の前後の要素が、該任意の頂点に隣接する頂点の構成点ＩＤであることと決定できる。
【００６０】
なお、任意の頂点に隣接する頂点の構成点ＩＤの格納位置は、該任意の頂点の構成点ＩＤの格納位置の前後に限られず、例えば、任意の頂点の構成点ＩＤの格納位置を始点として、前２つ（又は後２つ）の格納位置に格納されていてもよい。この場合においても、参照部１１２は、任意の頂点の構成点ＩＤである「１」が格納されている要素を特定すれば、その後、特定した要素の前２つ（又は後２つ）の要素が、該任意の頂点に隣接する頂点の構成点ＩＤであることと決定できる。
【００６１】
上記の通り、三角形の任意の頂点に隣接する頂点の構成点ＩＤを参照する際に、図７の配列を用いて参照する場合に比べて、条件分岐を実行するための処理を行う必要が無くなり、任意の頂点に隣接する頂点の構成点ＩＤを参照するための参照処理を単純化できる。したがって、情報処理装置１００は、三角形の任意の頂点の隣接点の構成点ＩＤを参照する処理を実行する場合、図８に例示する拡張配列を用いることで、参照処理を単純化でき、その分処理時間を短縮させることができる。
【００６２】
図９は、情報処理装置１００の動作例を示すフローチャートである。
【００６３】
図９に示すように、記憶部１２０は、三角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列を記憶する（Ｓ２０１）。
【００６４】
その後、制御部１１０の拡張部１１１は、三角形のうちの所定の頂点の識別子を当該配列の後に転記し、かつ、当該配列において当該所定の頂点の２つ先の頂点の識別子を当該配列の前に転記する（Ｓ２０２）。なお、記憶部１２０は、拡張部１１１が作成した拡張配列を記憶する。
【００６５】
そして、制御部１１０の参照部１１２は、例えば、任意の頂点に隣接する頂点の構成点ＩＤについて、任意の頂点の構成点ＩＤが格納されている要素を特定する（Ｓ２０３）。その後、参照部１１２は、配列において、特定した要素の前後の要素を参照し（Ｓ２０４）、隣接点（隣接する頂点）に対応する構成点ＩＤを決定する（Ｓ２０５）。
【００６６】
このように、情報処理装置１００は、図８に例示する拡張配列を用いることで、例えば、三角形の任意の頂点の隣接点の構成点ＩＤを参照する処理を実行する場合などに、参照処理を単純化することが可能となり、処理時間を短縮させることができる。
【００６７】
（四角形の場合の実施例）
図１０は、ディスプレイ上に３次元グラフィックとして描画される四角形の例を示す概略図である。図１０に示すように、四角形には、四角形ＩＤとして「１」が割り当てられている。四角形ＩＤは、一の四角形を、他の四角形から一意に識別可能な識別子である。
【００６８】
また、四角形の各頂点が該四角形の構成点として登録され、そのうちの任意の頂点に対して、構成点ＩＤ−Ａとして「１」が割り当てられる。同様にして、該任意の頂点に隣接する各頂点に、構成点ＩＤ−Ｂとして「２」、構成点ＩＤ−Ｃとして「３」、四角形ＩＤ−Ｄとして「４」がそれぞれ割り当てられる。構成点ＩＤは、四角形の頂点を一意に識別可能なＩＤである。
【００６９】
図１１は、図１０に例示した四角形の頂点に関する情報を示す配列の構成例を示す表である。
【００７０】
図１１に例示するように、配列において、四角形ＩＤが「１」の四角形に対し、所定の頂点の構成点ＩＤ−Ａとして「１」が、対応付けられている。また、四角形ＩＤが「１」の四角形の配列において、所定の頂点に隣接する他の頂点について順番に、構成点ＩＤ−Ｂとして「２」が、構成点ＩＤ−Ｃとして「３」が、構成点ＩＤ−Ｄとして「４」が、対応付けられている。すなわち、図１１に例示するように、図１０に例示する四角形について、四角形ＩＤ「１」と、構成点ＩＤ―Ａ「１」と、構成点ＩＤ―Ｂ「２」と、構成点ＩＤ―Ｃ「３」と、構成点ＩＤ―Ｄ「４」と、が対応付けて記憶されている。
【００７１】
図１１に例示するように、ディスプレイ上に四角形を３次元グラフィックとして描画する場合、データを格納する配列において、四角形の四角形ＩＤ１つに対して、四角形の頂点として構成点ＩＤが４つずつ割り振られる。情報処理装置１００は、記憶された配列に基づいて、四角形の任意の頂点や、当該任意の頂点に隣接する頂点等を認識する。
【００７２】
ここで、情報処理装置１００の参照部１１２は、四角形の任意の頂点の対角点の構成点ＩＤを参照する処理を行う場合がある。この場合において、図１１の配列を用いる場合、参照部１１２は、まず構成点ＩＤが「１」の頂点が、構成点ＩＤ−Ａであることを検索する。その後、参照部１１２は、構成点ＩＤ−Ａが「１」であったことから、対角点が構成点ＩＤ−Ｃに該当すると判定する。そして、参照部１１２は、対角点の構成点ＩＤとして、構成点ＩＤ−Ｃの「３」を参照する。ここで、任意の頂点の構成点ＩＤである「１」の格納位置が配列のどこに格納されているかにより、他の頂点（対角点）の構成点ＩＤの格納位置を参照する処理が異なる。図１１に例示する配列では、配列の一番左に任意の頂点の構成点ＩＤである「１」が格納されているため、対角点の構成点ＩＤは、配列の“左から３番目”に格納されていることなる。一方、図１１の例とは異なり、配列の一番右側に任意の頂点の構成点ＩＤである「１」が格納されている場合には、対角点の構成点ＩＤは、配列の“左から２番目”に格納されていることになる。すなわち、任意の頂点の構成点ＩＤである「１」の格納位置に応じて、対角点の構成点ＩＤの格納位置を参照するための処理が異なることになる。
【００７３】
このように、参照部１１２が、図１１に例示する配列を用いて、四角形の任意の頂点（例えば、構成点ＩＤが「１」）の対角点を参照する場合、まず任意の頂点の構成点ＩＤである「１」が、構成点ＩＤ−Ａ乃至Ｄのいずれかを特定する。例えば、参照部１１２は、任意の頂点の構成点ＩＤである「１」が、構成点ＩＤ−Ａに格納されていると特定する。その後、参照部１１２は、特定の結果を用いて決定される処理から、対角点の構成点ＩＤを参照する。図１１の例では、参照部１１２は、任意の頂点の構成点ＩＤが配列の一番左側に格納されていることから、対角点の構成点ＩＤは配列の左から３番目に格納されていることを特定し、構成点ＩＤ−Ｃに格納されている構成点ＩＤである「３」を参照することになる。
【００７４】
上記のとおり、図１１に例示する配列では、任意の頂点の構成点ＩＤである「１」の格納位置に基づいて、他の頂点（対角点）の識別子の格納位置を参照する処理が異なるため、該構成点ＩＤ「１」の格納位置に応じて、複数の処理から適切な参照処理を決定する必要がある。言い換えると、対角点の識別子の格納位置を参照するためには、構成点ＩＤ「１」の格納位置に基づく条件分岐を経る必要がある。そのため、条件分岐や、当該条件分岐に伴う情報処理端末１００のＣＰＵ内部の分岐予測、当該分岐予測に伴うパイプラインの生成を行う必要があり、その分だけ対角点の格納位置を参照する参照処理に要する処理時間が長くなってしまう。
【００７５】
そこで、本発明の情報処理装置１００では、拡張部１１１が、図１１に例示する配列を拡張することにより、参照部１１２が、任意の頂点の構成点ＩＤの格納位置に依存せず、いつでも同一の処理によって対角点の構成点ＩＤを参照することができるようにすることで、対角点の構成点ＩＤを参照するための参照処理を単純化して、当該参照処理を高速化する。
【００７６】
図１２は、四角形の場合における、拡張配列を示す表である。図１２に示すように、情報処理装置１００の制御部１１０の拡張部１１１は、所定の頂点の識別子を図６に例示する配列の後に転記し、かつ、当該配列において当該所定の頂点の２つ先の頂点の識別子を当該配列の前に転記する。つまり、図１２に例示するように、図１１の配列に含まれる構成点ＩＤ−Ａの前に、「構成点ＩＤ−Ｄ」を転記し、かつ、図１１の配列に含まれる構成点ＩＤ−Ｄの後に、「構成点ＩＤ−Ａ」および「構成点ＩＤ−Ｂ」を転記する。四角形ＩＤが「１」の場合には、図１２に例示するように、配列の後に、構成点ＩＤ−Ａである「１」及び構成点ＩＤ−Ｂである「２」を追加し、かつ、配列の前に、構成点ＩＤ−Ｄである「４」を追加する。このように、拡張部１１１は、図１２に例示するように、図１１の配列を拡張した拡張配列を、記憶部１２０に記憶する。
【００７７】
参照部１１２は、図１２の拡張配列を参照して、例えば、任意の頂点の対角点を参照する場合の処理を説明する。参照部１１２は、まず、拡張配列に含まれる配列のうち、任意の頂点の構成点ＩＤである「１」が格納されている要素を特定する。その後、参照部１１２は、配列において、特定した要素の２つ先の要素に対応する構成点ＩＤを決定する。
【００７８】
ここで、図１２に例示する拡張配列を用いているため、該拡張配列に含まれる配列のいずれの要素についても、その２つ先の要素が存在することになる。例えば、図１２の拡張配列の場合、配列に含まれる構成点ＩＤ−Ａの前には、拡張部１１１によって転記された要素である「構成点ＩＤ−Ｄ」が拡張されている。また、配列に含まれる構成点ＩＤ−Ｄの後には、拡張部１１１によって転記された要素である「構成点ＩＤ−Ａ」及び「構成点ＩＤ−Ｂ」が拡張されている。その結果、拡張配列に含まれる配列のうち、いずれの要素についても、その２つ先に要素が存在し、その要素の２つ先の要素は、その要素の対角点の構成点ＩＤが格納されていることになる。
【００７９】
このように、参照部１１２は、任意の頂点の構成点ＩＤである「１」が格納されている要素を特定すれば、その後、特定した要素の２つ先の要素が、該任意の頂点の対角点の構成点ＩＤであることと決定できる。そのため、図１１の配列を用いて参照する場合に比べて、条件分岐を実行するための処理を行う必要が無くなり、任意の頂点に隣接する頂点の構成点ＩＤを参照するための参照処理を単純化できる。したがって、情報処理装置１００は、四角形の任意の頂点の対角点の構成点ＩＤを参照する処理を実行する場合、図１２に例示する拡張配列を用いることで、参照処理を単純化することが可能となり、その分参照処理に要する処理時間を短縮させることができる。
【００８０】
図１３は、情報処理装置１００の動作例を示すフローチャートである。
【００８１】
図１３に示すように、記憶部１２０は、四角形の頂点のうち所定の頂点から順に、隣接する頂点の識別子を一列に並べた配列を記憶する（Ｓ３０１）。
【００８２】
拡張部１１１は、四角形のうちの所定の頂点および隣接する頂点の識別子を当該配列の後に転記し、かつ、当該配列において当該所定の頂点の３つ先の頂点の識別子を当該配列の前に転記する（Ｓ３０２）。なお、記憶部１２０は、拡張部１１１が作成した拡張配列を記憶する。
【００８３】
そして、制御部１１０の参照部１１２は、例えば、任意の頂点の構成点ＩＤが格納されている要素を特定する（Ｓ３０３）。その後、参照部１１２は、配列において、特定した要素の２つ先の要素を参照し（Ｓ３０４）、対角点に対応する構成点ＩＤを決定する（Ｓ３０５）。
【００８４】
このように、情報処理装置１００は、図１２に例示する拡張配列を用いることで、例えば、四角形の任意の頂点の対角点の構成点ＩＤを参照する処理を実行する場合などに、参照処理を単純化することが可能となり、処理時間を短縮させることができる。
【００８５】
また、情報処理装置１００の制御部１１０は、集積回路（ＩＣチップ）等に形成された論理回路（ハードウェア）によって実現してもよいし、ＣＰＵ（Central Processing Unit）を用いてソフトウェアによって実現してもよい。後者の場合、情報処理装置１００は、各機能を実現するソフトウェアであるプログラムの命令を実行するＣＰＵ、上記プログラムおよび各種データが情報演算装置（またはＣＰＵ）で読み取り可能に記録されたＲＯＭ（Read Only Memory）または記憶装置（これらを「記録媒体」と称する）、上記プログラムを展開するＲＡＭ（Random Access Memory）等を備えている。そして、情報演算装置（またはＣＰＵ）が上記プログラムを上記記録媒体から読み取って実行することにより、本発明の目的が達成される。また、上記プログラムは、当該プログラムを伝送可能な任意の伝送媒体（通信ネットワークや放送波等）を介して上記情報演算装置に供給されてもよい。本発明は、上記プログラムが電子的な伝送によって具現化された、搬送波に埋め込まれたデータ信号の形態でも実現され得る。
【００８６】
なお、上記プログラムは、例えば、ActionScript、JavaScript（登録商標）等のスクリプト言語、Objective-C、Java（登録商標）等のオブジェクト指向プログラミング言語、HTML5等のマークアップ言語等を用いて実装できる。
【符号の説明】
【００８７】
１００  情報処理装置
１１０  制御部
１１１  拡張部
１１２  参照部
１２０  記憶部
【図１】
2018160032.tif 000003
【図２】
2018160032.tif 000004
【図３】
2018160032.tif 000005
【図４】
2018160032.tif 000006
【図５】
2018160032.tif 000007
【図６】
2018160032.tif 000008
【図７】
2018160032.tif 000009
【図８】
2018160032.tif 000010
【図９】
2018160032.tif 000011
【図１０】
2018160032.tif 000012
【図１１】
2018160032.tif 000013
【図１２】
2018160032.tif 000014
【図１３】
2018160032.tif 000015