(57)【要約】【課題】  複数の描画要素に対応する複数のノードを接続することにより、画面構成に対応して形成されたツリー構造を利用した描画方法及び描画装置において、高速に描画する。【解決手段】  各ノードに、当該各ノードの描画順序を表す描画順位を付加するステップと、各ノードに、当該各ノードで描画を終了するか否かを決定するために参照される参照順位を付加するステップと、描画順序に従って、指定された起点ノードから、終点ノードまで、１乃至複数の描画要素を順々に描画するステップを備え、終点ノードとは、そのノードに付加されている参照順位が有効値であり、且つ、そのノードに付加されている参照順位が起点ノードの描画順位又はそれ以下となるようなノードである。【選択図】        図５
2006236078.tif 000002
【特許請求の範囲】
【請求項１】
複数の描画要素に対応する複数のノードを接続することにより、画面構成に対応して形成されたツリー構造を利用した描画方法であって、
各ノードに、当該各ノードの描画順序を表す描画順位を付加するステップと、
各ノードに、当該各ノードで描画を終了するか否かを決定するために参照される参照順位を付加するステップと、
を備えることを特徴とする描画方法。
【請求項２】
請求項１に記載の描画方法において、
各ノードを描画順位に従って記憶領域に記憶させることにより、前記描画順位の付加とすることを特徴とする描画方法。
【請求項３】
請求項１に記載の描画方法において、
各ノードに付加される前記描画順位は、ルートのノードを最初の親ノードとして扱った上で、親ノードの次に該親ノードの直下の子ノードを巡るような巡回を巡り会う子ノードについてもその子ノードを新たな親ノードとして扱った上で再帰的に行った場合の当該各ノードの順序であることを特徴とする描画方法。
【請求項４】
請求項１に記載の描画方法において、
ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがある場合には、その分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位と等しいことを特徴とする描画方法。
【請求項５】
請求項４に記載の描画方法において、
ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがない場合には、ルートのノードの描画順位と等しいことを特徴とする描画方法。
【請求項６】
請求項４に記載の描画方法において、
ツリーの末尾ノード以外のノードの参照順位は無効値であることを特徴とする描画方法。
【請求項７】
請求項１に記載の描画方法において、
各ノードの描画順位を生成するステップを更に備え、当該ステップにおいて、
ルートのノードを最初の親ノードとして扱った上で、親ノードの次に該親ノードの直下の子ノードを巡るような巡回を巡り会う子ノードについてもその子ノードを新たな親ノードとして扱った上で再帰的に行い、巡り会う順序に従って各ノードに描画順位を付加することを特徴とする描画方法。
【請求項８】
請求項１に記載の描画方法において、
各ノードの参照順位を生成するステップを更に備え、当該ステップは、
ツリーの末尾ノードの参照順位を、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがある場合には、その分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位と等しくするステップと、
ツリーの末尾ノードの参照順位を、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがない場合には、ルートのノードの描画順位と等しくするステップと、
ツリーの末尾ノード以外のノードの参照順位を、無効値とするステップと、
を備えることを特徴とする描画方法。
【請求項９】
請求項１に記載の描画方法において、
前記描画順序に従って、指定された起点ノードから、終点ノードまで、１乃至複数の描画要素を順々に描画するステップを更に備え、
前記終点ノードとは、そのノードに付加されている前記参照順位が有効値であり、且つ、そのノードに付加されている前記参照順位が前記起点ノードの描画順位又はそれ以下となるようなノードであることを特徴とする描画方法。
【請求項１０】
各描画要素が各ノードに対応するようなノードを接続することにより、画面構成に対応して形成されたツリー構造を利用した描画方法であって、
前記描画順序に従って、指定された起点ノードから、終点ノードまで、１乃至複数の描画要素を順々に描画するステップを備え、
前記描画順位とは各ノードの描画順序を表すものであり、
前記参照順位とは、各ノードで描画を終了するか否かを決定するために参照されるものであり、
前記終点ノードとは、そのノードに付加されている前記参照順位が有効値であり、且つ、そのノードに付加されている前記参照順位が前記起点ノードの描画順位又はそれ以下となるようなノードであることを特徴とする描画方法。
【請求項１１】
請求項１０に記載の描画方法において、
各ノードに付加される前記描画順位は、ルートのノードを最初の親ノードとして扱った上で、親ノードの次に該親ノードの直下の子ノードを巡るような巡回を巡り会う子ノードについてもその子ノードを新たな親ノードとして扱った上で再帰的に行った場合の当該各ノードの順序であることを特徴とする描画方法。
【請求項１２】
請求項１０に記載の描画方法において、
ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがある場合には、その分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位と等しいことを特徴とする描画方法。
【請求項１３】
請求項１２に記載の描画方法において、
ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがない場合には、ルートのノードの描画順位と等しいことを特徴とする描画方法。
【請求項１４】
請求項１２に記載の描画方法において、
ツリーの末尾ノード以外のノードの参照順位は無効値であることを特徴とする描画方法。
【請求項１５】
複数のノードに関するデータ構造を記録した、コンピュータ読取り可能な記録媒体において、
各ノードに関するデータ構造は、
当該各ノードの描画順序を表す描画順位と、
当該各ノードで描画を終了するか否かを判断するために参照される参照順位と、
を備え、
前記判断とは、描画順序に従って、指定された起点ノードから、１乃至複数の描画要素を順々に描画していく最中に、現在のノードに付加されている前記参照順位が有効値であり、現在のノードに付加されている前記参照順位が前記起点ノードの描画順位又はそれ以下である場合に現在のノードで描画を終了するような判断であることを特徴とする記録媒体。
【請求項１６】
請求項１５に記載の記録媒体において、
前記各ノードの描画順序は、各ノードに関するデータ構造のアドレスにより表されることを特徴とする記録媒体。
【請求項１７】
請求項１５に記載の記録媒体において、
各ノードに付加される前記描画順位は、ルートのノードを最初の親ノードとして扱った上で、親ノードの次に該親ノードの直下の子ノードを巡るような巡回を巡り会う子ノードについてもその子ノードを新たな親ノードとして扱った上で再帰的に行った場合の当該各ノードの順序であることを特徴とする記録媒体。
【請求項１８】
請求項１５に記載の記録媒体において、
ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがある場合には、その分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位と等しいことを特徴とする記録媒体。
【請求項１９】
請求項１８に記載の記録媒体において、
ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがない場合には、ルートのノードの描画順位と等しいことを特徴とする記録媒体。
【請求項２０】
請求項１８に記載の記録媒体において、
ツリーの末尾ノード以外のノードの参照順位は無効値であることを特徴とする記録媒体。
【請求項２１】
複数の描画要素に対応する複数のノードを接続することにより、画面構成に対応して形成されたツリー構造を利用した描画装置であって、
各ノードに、当該各ノードの描画順序を表す描画順位を付加する手段と、
各ノードに、当該各ノードで描画を終了するか否かを決定するために参照される参照順位を付加する手段と、
を備えることを特徴とする描画装置。
【請求項２２】
請求項２１に記載の描画装置において、
各ノードを描画順位に従って記憶領域に記憶させることにより、前記描画順位の付加とすることを特徴とする描画装置。
【請求項２３】
請求項２１に記載の描画装置において、
各ノードに付加される前記描画順位は、ルートのノードを最初の親ノードとして扱った上で、親ノードの次に該親ノードの直下の子ノードを巡るような巡回を巡り会う子ノードについてもその子ノードを新たな親ノードとして扱った上で再帰的に行った場合の当該各ノードの順序であることを特徴とする描画装置。
【請求項２４】
請求項２１に記載の描画装置において、
ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがある場合には、その分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位と等しいことを特徴とする描画装置。
【請求項２５】
請求項２４に記載の描画装置において、
ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがない場合には、ルートのノードの描画順位と等しいことを特徴とする描画装置。
【請求項２６】
請求項２４に記載の描画装置において、
ツリーの末尾ノード以外のノードの参照順位は無効値であることを特徴とする描画装置。
【請求項２７】
請求項２１に記載の描画装置において、
各ノードの描画順位を生成する手段を更に備え、当該手段において、
ルートのノードを最初の親ノードとして扱った上で、親ノードの次に該親ノードの直下の子ノードを巡るような巡回を巡り会う子ノードについてもその子ノードを新たな親ノードとして扱った上で再帰的に行い、巡り会う順序に従って各ノードに描画順位を付加することを特徴とする描画装置。
【請求項２８】
請求項２１に記載の描画装置において、
各ノードの参照順位を生成する手段を更に備え、当該手段は、
ツリーの末尾ノードの参照順位を、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがある場合には、その分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位と等しくする手段と、
ツリーの末尾ノードの参照順位を、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがない場合には、ルートのノードの描画順位と等しくする手段と、
ツリーの末尾ノード以外のノードの参照順位を、無効値とする手段と、
を備えることを特徴とする描画装置。
【請求項２９】
請求項２１に記載の描画装置において、
前記描画順序に従って、指定された起点ノードから、終点ノードまで、１乃至複数の描画要素を順々に描画する手段を更に備え、
前記終点ノードとは、そのノードに付加されている前記参照順位が有効値であり、且つ、そのノードに付加されている前記参照順位が前記起点ノードの描画順位又はそれ以下となるようなノードであることを特徴とする描画装置。
【請求項３０】
各描画要素が各ノードに対応するようなノードを接続することにより、画面構成に対応して形成されたツリー構造を利用した描画装置であって、
前記描画順序に従って、指定された起点ノードから、終点ノードまで、１乃至複数の描画要素を順々に描画する手段を備え、
前記描画順位とは各ノードの描画順序を表すものであり、
前記参照順位とは、各ノードで描画を終了するか否かを決定するために参照されるものであり、
前記終点ノードとは、そのノードに付加されている前記参照順位が有効値であり、且つ、そのノードに付加されている前記参照順位が前記起点ノードの描画順位又はそれ以下となるようなノードであることを特徴とする描画装置。
【請求項３１】
請求項３０に記載の描画装置において、
各ノードに付加される前記描画順位は、ルートのノードを最初の親ノードとして扱った上で、親ノードの次に該親ノードの直下の子ノードを巡るような巡回を巡り会う子ノードについてもその子ノードを新たな親ノードとして扱った上で再帰的に行った場合の当該各ノードの順序であることを特徴とする描画装置。
【請求項３２】
請求項３０に記載の描画装置において、
ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがある場合には、その分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位と等しいことを特徴とする描画装置。
【請求項３３】
請求項３２に記載の描画装置において、
ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがない場合には、ルートのノードの描画順位と等しいことを特徴とする描画装置。
【請求項３４】
請求項３２に記載の描画装置において、
ツリーの末尾ノード以外のノードの参照順位は無効値であることを特徴とする描画装置。
【請求項３５】
コンピュータに請求項１乃至１９の何れか１項に記載の方法を行わせるためのプログラム。
【請求項３６】
請求項３５に記載のプログラムを記録した、コンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の描画要素に対応する複数のノードを接続することにより、画面構成に対応して形成されたツリー構造を利用した描画方法及び描画装置に関する。
【背景技術】
【０００２】
近年、デジタル放送としてデジタル・テレビ放送の他にデジタル・データ放送が登場してきている。デジタル・データ放送では、ＢＭＬ(Broadcast Markup Language)ファイルに基づいて、文字、図形、静止画、動画等が表示される。また、ＢＭＬファイルはツリー構造を有し、ツリー構造に基づいて表示が行われる。
【０００３】
特許文献１には、ノードを結合して得られるツリー構造に従って描画を行う発明が記載されている。
【特許文献１】特開２００２−０３２７５０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、ＢＭＬファイルに基づいて描画を行う方法及び装置には、以下に示すような問題点があった。
【０００５】
例えば、カーネル領域とユーザ領域を設けるようなオペレーティング・システムを用いた場合、或るノードにある描画要素を再描画する場合、その描画要素を描画するための命令をユーザ管理領域からカーネル領域に対して発行するだけでなく、その配下にある個々の描画要素を再描画するための命令を個々にユーザ管理領域からカーネル領域に対して発行する必要があった。例えば、或るノードの配下に３つのノードが存在する場合、そのノードを再描画するためには、４（＝１＋３）個の描画命令をユーザ領域からカーネル領域に対して発行する必要があった。そうすると、描画命令をユーザ領域からカーネル領域に対して発行する度に、両領域を跨ぐためのオーバヘッドが発生するため、描画速度が低下してしまう。特に、組込み機器に用いられるような演算能力が低いＣＰＵを利用した場合、描画速度の低下は著しい。
【０００６】
また、ツリー構造を表すために、各ノードについて、そのノードの配下に子ノードが存在するならば、子ノードの数、子ノードへのポインタ等の子ノードに関する情報を付加する必要があり、これを記憶領域に格納する必要があった。また、ツリー構造を表すために、或るノードが或る親ノードの配下にあるならば、そのノードにその親ノードへのポインタを付加する必要があり、これを記憶領域に格納する必要があった。従って、記憶領域の記憶容量を圧迫していた。また、ポインタを利用して描画をする必要があるため、ポインタに関連した処理が必要であり、これが描画速度を遅くしていた。更に、表示のために分岐命令を多数実行する必要があるため、描画速度が遅くなっていた。
【０００７】
そこで本発明は、複数の描画要素に対応する複数のノードを接続することにより、画面構成に対応して形成されたツリー構造を利用した描画方法及び描画装置において、高速に描画することを可能とすることを目的とする。
【課題を解決するための手段】
【０００８】
本発明の第１の観点によれば、複数の描画要素に対応する複数のノードを接続することにより、画面構成に対応して形成されたツリー構造を利用した描画方法であって、各ノードに、当該各ノードの描画順序を表す描画順位を付加するステップと、各ノードに、当該各ノードで描画を終了するか否かを決定するために参照される参照順位を付加するステップと、を備えることを特徴とする描画方法が提供される。
【０００９】
上記の描画方法において、各ノードを描画順位に従って記憶領域に記憶させることにより、前記描画順位の付加とするようにしてもよい。
【００１０】
上記の描画方法において、各ノードに付加される前記描画順位は、ルートのノードを最初の親ノードとして扱った上で、親ノードの次に該親ノードの直下の子ノードを巡るような巡回を巡り会う子ノードについてもその子ノードを新たな親ノードとして扱った上で再帰的に行った場合の当該各ノードの順序であるようにしてもよい。
【００１１】
上記の描画方法において、ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがある場合には、その分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位と等しいようにしてもよい。
【００１２】
上記の描画方法において、ツリーの末尾ノードの参照順位は、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがない場合には、ルートのノードの描画順位と等しいようにしてもよい。
【００１３】
上記の描画方法において、ツリーの末尾ノード以外のノードの参照順位は無効値であるようにしてもよい。
【００１４】
上記の描画方法において、各ノードの描画順位を生成するステップを更に備え、当該ステップにおいて、ルートのノードを最初の親ノードとして扱った上で、親ノードの次に該親ノードの直下の子ノードを巡るような巡回を巡り会う子ノードについてもその子ノードを新たな親ノードとして扱った上で再帰的に行い、巡り会う順序に従って各ノードに描画順位を付加するようにしてもよい。
【００１５】
上記の描画方法において、各ノードの参照順位を生成するステップを更に備え、当該ステップは、ツリーの末尾ノードの参照順位を、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがある場合には、その分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位と等しくするステップと、ツリーの末尾ノードの参照順位を、当該ツリーの末尾のノードからルートのノードに向かって経路を遡って行った場合に遭遇する全ての分岐ノードのうちに、その分岐ノードから分岐していく他の経路上のその分岐ノードの直下のノードの描画順位がその分岐ノードから当該ツリーの末尾に至る経路上のその分岐ノードの直下のノードの描画順位よりも低いものがあるような分岐ノードがない場合には、ルートのノードの描画順位と等しくするステップと、ツリーの末尾ノード以外のノードの参照順位を、無効値とするステップと、を備えるようにしてもよい。
【発明の効果】
【００１６】
本発明によれば、各ノードに、そのノードの描画順序を表す描画順位を付加するステップと、各ノードに、そのノードで描画を終了するか否かを決定するために参照される参照順位を付加するステップと、描画順序に従って、指定された起点ノードから、現在のノードに付加されている参照順位が起点ノードの描画順位又はそれ以下となるまで、１乃至複数の描画要素を順々に描画するステップと、を有するので、準備段階で、各ノードに、そのノードの描画順序を表す描画順位を付加するステップと、各ノードに、そのノードで描画を終了するか否かを決定するために参照される参照順位を付加するステップを行い、描画段階で、描画順序に従って、指定された起点ノードから、現在のノードに付加されている参照順位が起点ノードの描画順位又はそれ以下となるまで、１乃至複数の描画要素を順々に描画するステップを行うことにより、描画段階で、起点ノードを指定し、現在のノードに付加されている参照順位が起点ノードの描画順位又はそれ以下となっているか否かの判断さえ行えば、描画順序に従うのみで、描画を高速に行うことができる。
【発明を実施するための最良の形態】
【００１７】
以下、図面を参照して本発明を実施するための最良の形態について詳細に説明する。
【００１８】
図１は、本発明の実施形態による描画装置の構成を示すブロック図である。
【００１９】
図１を参照すると、本発明の実施形態による描画装置は、受信部１０１、描画データ生成部１０２、描画データ１０３、描画命令部１０４及び描画部１０５を備える。描画データ生成部１０２及び描画命令部１０４は、ユーザ管理領域１０６に含まれる。描画部１０５はカーネル領域１０７に含まれる。
【００２０】
なお、描画データ生成部１０２、描画命令部１０４及び描画部１０５は、ハードウェアによって実現することも可能であるが、コンピュータをこれらの部分として機能させるためのプログラムをコンピュータが読み込んで実行することによっても実現することができる。
【００２１】
受信部１０１は、デジタル・データ放送局からの電波を受信し、デジタル・データの復調を行う。
【００２２】
受信したＢＭＬファイルは、図２に示すように、ツリー構造を有している。図２を参照すると、ＢＭＬファイルにおいては、最上位のノードの下に、タイトルのノード、スタイル情報のノード、文書の実体のノードが存在する。また、文書の実体のノードの下には、音声要素のノード、背景要素のノード及び描画要素１〜１５のノードが存在する。
【００２３】
描画データ生成部１０２は、デジタル・データを基にツリー構造を有する描画データ１０３を生成し、その描画データ１０３を記録媒体に記録する。
【００２４】
具体的には、描画データ生成部１０２は、図２に示すようなツリー構造から、最上位のノード、タイトルのノード、スタイル情報のノード、スクリプトのノード、背景要素のノード及び音声要素のノードを除き、図３に示すように、文書の実体のノード及び描画要素１〜１５のノードのみから成る新たなツリー構造を構築する。
【００２５】
次に、描画データ生成部１０２は、文書の実体のノード及び描画要素１〜１５のノードの描画順位を生成し、それらを文書の実体のノード及び描画要素１〜１５のノードに付加する。描画順位とは、再描画するときの各ノードの順序のことである。描画順位が付加されたノードより構成されるツリー構造を図４に示す。
【００２６】
次に、描画データ生成部１０２は、文書の実体のノード及び描画要素１〜１５のノードの参照順位を生成し、それらを文書の実体のノード及び描画要素１〜１５のノードに付加する。参照順位とは、再描画するときにどのノードで描画を終了するかを判断するために参照される順位のことである。描画順位と参照順位が付加されたノードより構成されるツリー構造を図５に示す。
【００２７】
次に、描画データ生成部１０２は、描画順位と参照順位が付加されたノードを含む描画データ１０３を記録媒体に記録する。
【００２８】
図６は、描画データ１０３の一例を示す。図６を参照すると、各ノード毎に、描画順位、参照順位、ポインタ及び描画要素が存在する。描画要素は、例えば、描画位置、描画サイズ、色、形状等を表すデータである。ポインタは、描画要素が格納されている位置を示す。
【００２９】
図７は、描画データ１０３の他の一例を示す。図７を参照すると、各ノード毎に、参照順位、ポインタ及び描画要素が存在する。図７の例では、描画順位が含まれていないが、これは、ノードのデータが格納される記憶領域のオフセット・アドレスによって表される。
【００３０】
描画命令部１０４は、描画部１０５に対して、描画命令を発行する。描画命令には、描画を開始するノードの描画順位が含まれる。図３及び図４を参照すると、例えば、文書の実体のノードを頂点としたツリーを再描画するための描画命令には、値が１である描画順位が含まれる。同様に、描画要素１のノードを頂点としたツリーを再描画するための描画命令には、値が２である描画順位が含まれる。同様に、描画要素２のノードを頂点としたツリーを再描画するための描画命令には、値が８である描画順位が含まれる。同様に、描画要素３のノードを頂点としたツリーを再描画するための描画命令には、値が３である描画順位が含まれる。
【００３１】
描画部１０５は、描画命令部１０４から受けた描画命令に従って、描画データ１０３を基に、レンダリングを行い、レンダリングの結果をモニタ１０８に出力する。
【００３２】
図８は描画部１０５により描画方法を説明するための図である。図５に示す描画順位及び参照順位をまとめると、図８の上方に示すようになる。
【００３３】
ツリーの末尾ノードではないノードで描画を終了することはあり得ないので、そのようなノードの参照順位は、無効値とする。図８の例では、無効値としてゼロを選択している。この他、無効値としては、最も低い順位よりも大きい値を選択することができる。図８の例では、最も低い順位よりも大きい値は１６よりも大きい値である。従って、無効値として１７、１８、１９等を選択することができる。
【００３４】
描画部１０５は、指定された起点ノードから描画順位に従って描画を行う。そして、現在のノードの参照順位が無効値でなく、且つ、現在のノードの参照順位が起点ノードの描画順位又はそれ以下であるか否かを判断する。その判断の結果が肯定的である場合は、現在のノードで描画を終了する。
【００３５】
図８の例でいうと、描画順位が１であるノードが起点ノードである場合には、全てのノードの描画要素を描画する。また、描画順位が２であるノードが起点ノードである場合には、参照順位が２であり描画順位が７である描画要素まで描画する。同様に、描画順位が３であるノードが起点ノードである場合には、参照順位が３であり描画順位が３である描画要素のみ描画する。描画順位が４であるノードが起点ノードである場合には、参照順位が２であり描画順位が７である描画要素まで描画する。描画順位が５であるノードが起点ノードである場合には、参照順位が２であり描画順位が７である描画要素まで描画する。以下同様である。
【００３６】
このようにして、描画命令部１０４から描画部１０５に対し、起点ノードの描画順位を伴う１つの描画命令を発行するのみで、必要な全ての描画要素を再描画することが可能となる。従って、ユーザ管理領域１０６からカーネル領域１０７に跨った通信を行うためのオーバーヘッドを削減することができる。
【００３７】
次に、図９を参照して、描画データ生成部１０２により描画順位をノードに付加する方法について説明する。
【００３８】
図９を参照すると、まず描画順位を１に初期化し（ステップＳ２０１）、ルートノードを親ノードとした上で（ステップＳ２０３）、単位処理Ｓ２０５を呼ぶ。
【００３９】
単位処理Ｓ２０５では、まず、現在の描画順位を親ノードの描画順位に代入する（ステップＳ２０７）。次に、子ノードを数えるための変数ｉをゼロに初期化する（ステップＳ２０９）。次に、描画順位を１だけ増加させる（ステップＳ２１１）。次に、現在の描画順位を現在の（ｉ番目の）子ノードの描画順位に代入する（ステップＳ２１３）。次に、現在の（ｉ番目の）子ノードの下に更なる子ノードが存在するか否かを判断する（ステップＳ２１５）。
【００４０】
現在の（ｉ番目の）子ノードの下に更なる子ノードが存在しない場合には（ステップＳ２１５でＮＯ）、変数ｉを１だけ増加させ（ステップＳ２１７）、増加後の変数ｉの値が現在の親ノードの下の子ノードの数と等しいか否かを判断する（ステップＳ２１９）。増加後の変数ｉの値が現在の親ノードの下の子ノードの数と等しい場合には（ステップＳ２１９でＹＥＳ）、処理を終了し、そうでない場合にはステップＳ２１１に戻る。
【００４１】
現在の（ｉ番目の）子ノードの下に更なる子ノードが存在する場合には（ステップＳ２１５でＹＥＳ）、描画順位を１だけ増加させ（ステップＳ２２１）、現在の（ｉ番目の）子ノードを新たな親ノードとした上で（ステップＳ２２３）、単位処理２０５を再帰的に呼ぶ。
【００４２】
こうすることにより図４に示すような描画順位が各ノードに付加される。
【００４３】
次に、図１０を参照して、描画データ生成部１０２により参照順位をノードに付加する第１の方法について説明する。
【００４４】
図１０を参照すると、ステップＳ２３３〜Ｓ２４９を全てのノードについて繰り返す（ステップＳ２３１）。
【００４５】
ステップＳ２３３では、自ノードの下に子ノードがあるか否かを判断する（ステップＳ２３３）。自ノードの下に子ノードがある場合には（ステップＳ２３３でＹＥＳ）、無効値を現在のノードの参照順位に代入する（ステップＳ２３５）。
【００４６】
自ノードの下に子ノードがない場合には（ステップＳ２３３でＮＯ）、自ノードを着目ノードとして（ステップＳ２３７）、着目ノードの上のノードを親ノードとする（ステップＳ２３９）。
【００４７】
次に、親ノードの下に着目ノード以外の子ノードがあり（ステップＳ２４１）、且つ、着目ノードの描画順位が親ノードの下の全ての子ノードの描画順位の中で最も高いか否かを判断する（ステップＳ２４３）。
【００４８】
そうである場合には（ステップＳ２４１及びＳ２４３でＹＥＳ）、着目ノードの描画順位を現在のノードの参照順位に代入する（ステップＳ２４９）。
【００４９】
親ノードの下に着目ノード以外の子ノードがない場合（ステップＳ２４１でＮＯ）、又は、着目ノードの描画順位が親ノードの下の全ての子ノードの描画順位の中で最も高くない場合には（ステップＳ２４３でＮＯ）、親ノードを新たな着目ノードとする（ステップＳ２４５）。次に、この新たな着目ノードが親ノードであるか否かを判断する（ステップＳ２４７）。この新たな着目ノードが親ノードである場合には（ステップＳ２４７）、この新たな着目ノードである親ノードの描画順位を現在のノードの参照順位に代入する（ステップＳ２４９）。この新たな着目ノードが親ノードでない場合には（ステップＳ２４７でＮＯ）、ステップＳ２３９に戻る。
【００５０】
こうすることにより図５にしめすような参照順位が各ノードに付加される。
【００５１】
次に、図１１及び図１２を参照して、描画データ生成部１０２により参照順位をノードに付加する第２の方法について説明する。この方法では、図１３に示すようなテーブルを利用する。テーブルは、「テーブル・インデックス」、「対象の描画要素情報」、「描画要素配下の処理した子要素数」及び「最終子要素処理ステータス」をフィールドとして有する。
【００５２】
図１１を参照すると、まず、描画順位１の「描画要素情報」を「処理対象要素」に代入する（ステップＳ２６１）。次に、ポインタにゼロを代入する（ステップＳ２６３）。つぎに、テーブルの行のうちのポインタで示される順位の行の「処理した子要素数」にゼロを代入する（ステップＳ２６５）。次に、「処理した子要素数」にゼロを代入する（ステップＳ２６７）。次に、「子要素数」を取得する（ステップＳ２６９）。次に、「子要素数」がゼロを超えるか否かを判断する（ステップＳ２７１）。
【００５３】
「子要素数」がゼロを超えている場合には（ステップＳ２７１でＹＥＳ）、テーブルの行のうちのポインタで示される順位の行の「描画要素情報」に「自要素情報」を代入する（ステップＳ２７３）。次に、「処理した子要素数」を１だけ増加させる（ステップＳ２７５）。次に、テーブルの行のうちのポインタで示される順位の行の「処理した子要素数」を１だけ増加させる（ステップＳ２７７）。次に、「処理した子要素数」を変数であるｍに代入する（ステップＳ２７９）。次に、「子要素数」が「処理した子要素数」と等しいか否かを判断する（ステップＳ２８１）。
【００５４】
「子要素数」が「処理した子要素数」と等しい場合には（ステップＳ２８１でＹＥＳ）、テーブルの行のうちのポインタで示される行の「最終子要素ステータス」にＴＲＵＥを代入する（ステップＳ２８３）。次に、「処理対象要素」（中間要素）の参照順位にゼロを代入する（ステップＳ２８５）。
【００５５】
「子要素数」が「処理した子要素数」と等しくない場合には（ステップＳ２８１でＮＯ）、テーブルの行のうちのポインタで示される行の「最終子要素ステータス」にＦＡＬＳＥを代入する（ステップＳ２９５）。
【００５６】
ステップＳ２８５又はステップＳ２９５の次に、「処理対象要素」にｍ番目の子要素を代入し（ステップＳ２８７）、ポインタを１だけ増加させ（ステップＳ２８９）、ステップＳ２６５に戻る。
【００５７】
「子要素数」がゼロを超えていない場合には（ステップＳ２７１でＮＯ）、ポインタがゼロであるか否かを判断し（ステップＳ２９１）、そうであれば（ステップＳ２９１でＹＥＳ）、「処理対象要素」の参照順位に１を代入し（ステップＳ２９３）、処理を終了する。
【００５８】
図１２を参照し、ポインタがゼロでない場合には（ステップＳ２９１（図１１）でＮＯ）、変数であるｎに１を代入し（ステップＳ２９７）、テーブルの行の内「ポインタ−１」で示される行の「最終子要素ステータス」がＴＲＵＥであるか否かを判断する（ステップＳ２９９）。
【００５９】
そうである場合には（ステップＳ２９９でＹＥＳ）、ポインタがｎであるか否かを判断する（ステップＳ３０１）。そうであれば（ステップＳ３０１でＹＥＳ）、「処理対象要素」の「参照順位」を１にして（ステップＳ３０３）、処理を終了する。
【００６０】
そうでない場合には（ステップＳ３０１でＮＯ）、ｎを１だけ増加させ（ステップＳ３０５）、ステップＳ２９９に戻る。
【００６１】
「ポインタ−１」で示されるテーブルの行の「最終子要素ステータス」がＴＲＵＥでない場合には（ステップＳ２９９でＮＯ）、ｎが１であるか否かを判断する（ステップＳ３０７）。
【００６２】
そうである場合には（ステップＳ３０７でＹＥＳ）、「処理対象要素」の「参照順位」に自身の描画要素の描画順位を代入する（ステップＳ３０９）。
【００６３】
そうでない場合には、「処理対象要素」の「参照順位」にテーブルの行のうちの「ｎ−１」番目の行の「描画要素情報の描画順位」を代入する（ステップＳ３１７）。
【００６４】
ステップＳ３０９又はＳ３１７の次に、ポインタをｎだけ減少させる（ステップＳ３１１）。次に、「処理対象要素」にテーブルの行のうちのポインタで示される行の「描画要素情報」を代入し（ステップＳ３１３）、「処理した子要素数」にテーブルの行のうちのポインタで示される行の「処理した子要素数」を代入し（ステップＳ３１５）、ステップＳ２６９に戻る。
【００６５】
こうすることにより図５にしめすような参照順位が各ノードに付加される。
【００６６】
図１１及び図１２に示される方法を実行している最中のテーブルの遷移の様子を図１３に示す。
【００６７】
次に、図１４を参照して、描画部１０５によるレンダリングの方法について説明する。
【００６８】
まず、起点ノードの指定を描画命令部１０４から受ける（ステップＳ３３１）。次に、起点ノードを注目ノードとする（ステップＳ３３３）。
【００６９】
次に、注目ノードの描画要素を描画するためのｂｉｔＢＬＴ(bit BLock Transfer)コマンドを生成し（ステップＳ３３５）、そのコマンドをコマンド・リストに登録する（ステップＳ３３７）。
【００７０】
次に、注目ノードの参照順位が有効値であるか否かを判断する（ステップＳ３３９）。そうでない場合には（ステップＳ３３９でＮＯ）、次の描画順位のノードを注目ノードとして（ステップＳ３４１）、ステップＳ３３５に戻る。
【００７１】
そうである場合には（ステップＳ３３９でＹＥＳ）、注目ノードの参照順位は起点ノードの描画順位以下であるか否かを判断する（ステップＳ３４３）。そうでなければ（ステップＳ３４３でＮＯ）、次の描画順位のノードを注目ノードとして（ステップＳ３４１）、ステップＳ３３５に戻る。
【００７２】
そうであれば（ステップＳ３４３でＹＥＳ）、ｂｉｔＢＬＴエンジンによりコマンド・リストを実行する（ステップＳ３４５）。
【図面の簡単な説明】
【００７３】
【図１】本発明の実施形態による描画装置の全体の構成を示すブロック図である。
【図２】本発明の実施形態による描画装置が受信するＢＭＬファイルのツリー構造を示す図である。
【図３】図２に示すツリー構造から不要な部分を取り除いて得たツリー構造を示す図である。
【図４】本発明の実施形態により描画順位が付加されたツリー構造を示す図である。
【図５】本発明の実施形態により描画順位及び参照順位が付加されたツリー構造を示す図である。
【図６】図１に示す描画データ生成部が生成した描画データの構造の一例を示す図である。
【図７】図１に示す描画データ生成部が生成した描画データの構造の他の一例を示す図である。
【図８】図１に示す描画部が行う描画を説明するための図である。
【図９】図１に示す描画データ生成部が描画順位をノードに付加する方法を説明するためのフローチャートである。
【図１０】図１に示す描画データ生成部が参照順位をノードに付加する第１の方法を説明するためのフローチャートである。
【図１１】図１に示す描画データ生成部が参照順位をノードに付加する第２の方法を説明するためのフローチャート（１／２）である。
【図１２】図１に示す描画データ生成部が参照順位をノードに付加する第２の方法を説明するためのフローチャート（２／２）である。
【図１３】図１に示す描画データ生成部が参照順位をノードに付加する第２の方法で利用するテーブルの遷移を示す図である。
【図１４】図１に示す描画部により行われるレンダリングの方法を説明するためのフローチャートである。
【符号の説明】
【００７４】
１０１  受信部
１０２  描画データ生成部
１０３  描画データ
１０４  描画命令部
１０５  描画部
１０６  ユーザ管理領域
１０７  カーネル領域
１０８  モニタ
【図１】
2006236078.tif 000003
【図２】
2006236078.tif 000004
【図３】
2006236078.tif 000005
【図４】
2006236078.tif 000006
【図５】
2006236078.tif 000007
【図６】
2006236078.tif 000008
【図７】
2006236078.tif 000009
【図８】
2006236078.tif 000010
【図９】
2006236078.tif 000011
【図１０】
2006236078.tif 000012
【図１１】
2006236078.tif 000013
【図１２】
2006236078.tif 000014
【図１３】
2006236078.tif 000015
【図１４】
2006236078.tif 000016